Optimization of supply diversity for the self-assembly of simple objects in two and three dimensions

DOI10.1007/S11047-010-9209-XMaRDI QIDQ537837zbMATH OpenOpenAlexFDO

Authors Fabio R. J. Vieira, Valmir C. Barbosa

Publication date 23 May 2011

Published in Natural Computing (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/0710.0672

zbMATH Keywords

algorithmic self-assemblymulti-objective evolutionary algorithmsminimum tile set problem

Mathematics Subject Classification ID

Problem solving in the context of artificial intelligence (heuristics, search strategies, etc.) (68T20) Combinatorial aspects of tessellation and tiling problems (05B45)

Abstract: The field of algorithmic self-assembly is concerned with the design and analysis of self-assembly systems from a computational perspective, that is, from the perspective of mathematical problems whose study may give insight into the natural processes through which elementary objects self-assemble into more complex ones. One of the main problems of algorithmic self-assembly is the minimum tile set problem (MTSP), which asks for a collection of types of elementary objects (called tiles) to be found for the self-assembly of an object having a pre-established shape. Such a collection is to be as concise as possible, thus minimizing supply diversity, while satisfying a set of stringent constraints having to do with the termination and other properties of the self-assembly process from its tile types. We present a study of what we think is the first practical approach to MTSP. Our study starts with the introduction of an evolutionary heuristic to tackle MTSP and includes results from extensive experimentation with the heuristic on the self-assembly of simple objects in two and three dimensions. The heuristic we introduce combines classic elements from the field of evolutionary computation with a problem-specific variant of Pareto dominance into a multi-objective approach to MTSP.

Recommendations

• Algorithmic DNA Self-assembly
• Synthesizing Minimal Tile Sets for Patterned DNA Self-assembly
• Synthesizing small and reliable tile sets for patterned DNA self-assembly
• Search methods for tile sets in patterned DNA self-assembly

Cites work

• scientific article; zbMATH DE number 1010621 (Why is no real title available?)
• scientific article; zbMATH DE number 194544 (Why is no real title available?)
• scientific article; zbMATH DE number 795587 (Why is no real title available?)
• A Self-assembly Model of Time-Dependent Glue Strength
• A novel evolutionary formulation of the maximum independent set problem
• Arithmetic computation in the tile assembly model: addition and multiplication
• Combinatorial optimization problems in self-assembly
• Complexities for Generalized Models of Self-Assembly
• Complexity of Graph Self-assembly in Accretive Systems and Self-destructible Systems
• Complexity of Self‐Assembled Shapes
• Evolutionary computation: a unified approach.
• Invadable self-assembly: combining robustness with efficiency
• On the Complexity of Graph Self-assembly in Accretive Systems
• Running time and program size for self-assembled squares
• The emerging discipline of biomolecular computation in the US
• The program-size complexity of self-assembled squares (extended abstract)
• Time Optimal Self-assembly for 2D and 3D Shapes: The Case of Squares and Cubes
• Toward Minimum Size Self-Assembled Counters
• Two novel evolutionary formulations of the graph coloring problem

Cited in

(1)

• Engineering Self-Organising Systems

This page was built for publication: Optimization of supply diversity for the self-assembly of simple objects in two and three dimensions

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q537837)