Transposição : estudo de um novo operador genético inspirado biologicamente

Dissertação de mestrado em Engenharia Informática apresentada ao Departamento de Engenharia Informática da Fac. de Ciências e Tecnologia de CoimbraDesde os estudos pioneiros realizados por John Holland até aos trabalhos de investigação actuais, o Algoritmo Genético (AG) conheceu inúmeras variantes, quer a nível da representação, quer nas características dos operadores genéticos utilizados. Grande parte dos AG's implementados para a resolução de problemas específicos, "afastam-se" das ideias básicas da genética, utilizando operadores mais adequados à representação e dependentes do domínio sobre o qual operam. Sem criticar estes AG's, alguns autores alertaram para o facto de as novas descobertas da biologia molecular poderem fornecer ideias para novos algoritmos genéticos, mais próximos da biologia. Neste sentido, trabalhos recentes procuram aproximar o modelo computacional dos modelos biológicos, colocando mais genética na sua implementação. Este trabalho segue esta linha de orientação e teve como objectivo encontrar nos sistemas biológicos operadores genéticos, responsáveis pela diversidade das populações, que pudessem ser adaptados e integrados no AG tradicional. Apesar dos sistemas biológicos nos fornecerem um grande número destes mecanismos, testes preliminares com um deles conduziram a resultados promissores que achámos que deveriam ser solidificados. Este mecanismo, objecto de estudo deste trabalho, designa-se por transposição. Foram propostas duas variantes do mecanismo de transposição. A primeira, denominada por transposição simples, envolve troca bidireccional de material genético de determinadas características (o transposão) entre dois indivíduos escolhidos aleatoriamente. A segunda designada por transposição baseada em torneio, caracteriza-se pela transferência unidireccional do transposão, de um indivíduo (o vencedor do torneio) para outro (o perdedor). Para estudar as potencialidades deste operador genético, utilizámos o AG no domínio clássico de optimização, substituindo o operador de crossover tradicional (com 1 ponto de corte, 2 pontos de corte e uniforme) pelas duas variantes do mecanismo de transposição. Realizou-se um extenso estudo empírico envolvendo a optimização de dezoito funções, todas elas abrangendo diferentes características e já utilizadas por diversos autores como medida de eficiência do AG. A transposição foi implementada variando um parâmetro, o tamanho das sequências flanqueadoras, cuja escolha se revelou de muita importância para a qualidade das soluções encontradas. A análise dos resultados foca dois aspectos principais. O primeiro descreve a forma encontrada para escolher o valor para o tamanho das sequências flanqueadoras que conduz ao desempenho máximo do AG. O segundo aspecto foca a análise comparativa entre o mecanismo de transposição e os operadores de crossover. Os resultados demonstraram que a transposição, no domínio de optimização de funções, permite ao AG obter melhores resultados do que os operadores clássicos de crossover. Além disso, a principal vantagem do mecanismo proposto é permitir que o AG, mesmo com populações pequenas, encontre melhores soluções do que os operadores de crossover, com populações de maiores dimensões.Since John Holland's pioneering work, the Genetic Algorithm (GA) undergo several modifications, concerning representation issues and genetic operators. The majority of current GA's, applied to specific problems, "deviate" from the basic ideas of genetics and use domain dependent genetic operators, more suitable to the selected representation. Without criticizing these GA's, several authors emphasize the last discoveries of molecular biology as a good source of inspiration for new genetic algorithms more close to biology. Following these guidelines, recent works try to reduce the gap between natural biological systems and the corresponding computational models, putting more genetics in their implementation. The main goal of this work was to look for genetic operators, present in the biological systems, responsible for genetic diversity of the populations, that could be adapted and integrated in the simple GA. Nature is a good source of inspiration and we found a large set of genetic operators, capable of rearranging the genetic material of the individuals. Preliminary experiments with one of those mechanisms produced promising results and we decided to study it thoroughly. This mechanism, and the main goal of this work, is called transposition. We proposed two variations of the mechanism of transposition. The first, called simple transposition, implies the bidireccional exchange of specific genetic material (the transposon) between to individuals randomly chosen. The second variation, called tournament-based transposition, characterizes itself by the unidirectional exchange of the transposon, from one individual (the winner of the tournament) to another individual (the loser). To study the effectiveness of the proposed mechanism we used the GA in the classical domain of optimization, being the traditional crossover operator (with one cut point, 2 cut points and uniform) replaced by transposition. We carried out an extensive empirical study using a set of eighteen test functions, covering a large set of characteristics and already used by several authors as benchmarks to evolutionary approaches. The mechanism of transposition was implemented varying a parameter, the flanking sequence length, which must be selected very carefully in order to achieve good results. The analysis of the results focus to main situations. First, we describe the heuristics that should be applied to chose the flanking sequence length leading the GA to the best solutions. Secondly, we present the comparative analysis of the results achieved with transposition and crossover. The results showed that, in the selected domain - function optimization -, the modified GA with transposition can obtain better results than the standard GA using crossover. Moreover, one clear advantage of using the GA with transposition is that, even with smaller populations, it can obtain much better results than when used with crossover, with larger populations