Utilize este identificador para referenciar este registo:
https://hdl.handle.net/10316/13900
Título: | Transposição : estudo de um novo operador genético inspirado biologicamente | Autor: | Simões, Anabela Borges | Orientador: | Costa, Ernesto Jorge Fernandes | Palavras-chave: | Algoritmos genéticos; Inteligência artificial | Data: | 1999 | Citação: | SIMÕES, Anabela Borges - Transposição : estudo de um novo operador genético inspirado biologicamente. Coimbra, 1999 | Título da revista, periódico, livro ou evento: | Transposição : estudo de um novo operador genético inspirado biologicamente | Local de edição ou do evento: | Coimbra | Resumo: | Desde 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. |
Descrição: | Dissertação de mestrado em Engenharia Informática apresentada ao Departamento de Engenharia Informática da Fac. de Ciências e Tecnologia de Coimbra | URI: | https://hdl.handle.net/10316/13900 | Direitos: | openAccess |
Aparece nas coleções: | UC - Dissertações de Mestrado FCTUC Eng.Informática - Teses de Mestrado |
Ficheiros deste registo:
Ficheiro | Descrição | Tamanho | Formato | |
---|---|---|---|---|
Transposição.pdf | 2.42 MB | Adobe PDF | Ver/Abrir |
Visualizações de página
241
Visto em 15/out/2024
Downloads
249
Visto em 15/out/2024
Google ScholarTM
Verificar
Todos os registos no repositório estão protegidos por leis de copyright, com todos os direitos reservados.