Autores

4419
163,1980
4420
163,1980

Informações:

Publicações do PESC

Título
Otimização do Conjunto de Peças para Auto-Montagem
Linha de pesquisa
Otimização
Tipo de publicação
Dissertação de Mestrado
Número de registro
Data da defesa
5/9/2007
Resumo

Auto-montagem ("Self-Assembly") é o processo espontâneo pelo qual objetos simples unem-se para formar estruturas complexas. Posteriormente esses objetos, denominados ladrilhos, interagem para formação de macro-estruturas, como por exemplo, o DNA. A Auto-montagem propõem soluções ecientes para diversas áreas como: construção automatizada, integração de circuitos, computação em DNA e construção de nanorobôs. Em 1998, Erik Winfree sugeriu um modelo matemático para este processo, denominado Auto-montagem Algorítmica, com a capacidade de construir formas geométricas em duas dimensões. Posteriormente, Adleman propôs um problema de otimização combinatória, denominado problema do conjunto mínimo de ladrilhos para a Auto-montagem. Neste trabalho estendemos o modelo bidimensional de Winfree, permitindo rotações nos ladrilhos, pois este movimento era proibido. Esta extensão facilita a construção de formas geométricas em duas dimensões, reduzindo a variabilidade de ladrilhos e conseqüentemente diminuindo o espaço de busca do modelo original. Para criação de formas geométricas em três dimensões, criamos o modelo tridimensional de Auto-montagem. Para resolver o problema do conjunto mínimo de ladrilhos, desenvolvemos uma Heurística Evolucionária Multi-Objetivo, denominada Algoritmo Genético Multi-Objetivo Simples(AMS). As soluções para o conjunto mínimo de tipos de ladrilhos são apresentadas para o modelo bidimensional, assim como para a extensão deste modelo e para o modelo tridimensional. As rotações permitiram melhores soluções para a extensão do modelo bidimensional, se comparado ao modelo original deWinfree. AMS obteve sucesso na solução do problema do conjunto mínimo de ladrilhos.

Abstract

Self-assembly is the ubiquitous process by which simple objects autonomously assemble into intricate structures. These structures can then grow into macrostructures, like DNA. Self-assembly suggests solutions for many elds, like autonomous construction, circuit fabrication, DNA computation, and nano-robotics. In 1998, Erik Winfree proposed a mathematical model for this process, called the Tile Assembly Model. This model can build two-dimensional geometric forms. Later, Adleman introduced a combinatorial optimization problem, called the Minimum Tile Set Problem. In this study, we extendWinfree's model, to allow tile rotations. This extension facilitates the construction of two-dimensional geometric forms by decreasing the search space. We also introduce a three-dimensional model. We have created a heuristic multiobjective algorithm to solve the Minimum Tile Set Problem. We have demonstrated that the two-dimensional model with rotation is capable of yielding better solutions than the original two-dimensional model. As for the threedimensional model, the solutions we have found are the rst ever to be obtained.

Arquivo
Topo