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

DOI10.1007/S11047-010-9209-XzbMATH Open1213.68587arXiv0710.0672OpenAlexW2088358231MaRDI QIDQ537837FDOQ537837

Fabio R. J. Vieira, Valmir C. Barbosa

Publication date: 23 May 2011

Published in: Natural Computing (Search for Journal in Brave)

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.

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)

Cites Work

• Title not available (Why is that?)
• Title not available (Why is that?)
• Title not available (Why is that?)
• The program-size complexity of self-assembled squares (extended abstract)
• Combinatorial optimization problems in self-assembly
• Complexity of Graph Self-assembly in Accretive Systems and Self-destructible Systems
• Time Optimal Self-assembly for 2D and 3D Shapes: The Case of Squares and Cubes
• Running time and program size for self-assembled squares
• Complexities for Generalized Models of Self-Assembly
• Complexity of Self‐Assembled Shapes
• Title not available (Why is that?)
• A novel evolutionary formulation of the maximum independent set problem
• On the Complexity of Graph Self-assembly in Accretive Systems
• Two novel evolutionary formulations of the graph coloring problem
• A Self-assembly Model of Time-Dependent Glue Strength
• Toward Minimum Size Self-Assembled Counters
• Title not available (Why is that?)
• The emerging discipline of biomolecular computation in the US
• Arithmetic computation in the tile assembly model: addition and multiplication

Cited In (1)

• Engineering Self-Organising Systems

   Recommendations

• Algorithmic DNA Self-assembly 👍 👎
• Synthesizing Minimal Tile Sets for Patterned DNA Self-assembly 👍 👎
• Self-assembly of shapes at constant scale using repulsive forces 👍 👎
• Synthesizing small and reliable tile sets for patterned DNA self-assembly 👍 👎
• Search methods for tile sets in patterned DNA self-assembly 👍 👎

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)