Otimização do Conjunto de Peças para Auto-Montagem

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.