Utilize este identificador para referenciar este registo: http://hdl.handle.net/10400.1/6820
Título: Visualization of genetic algorithm operation on additive decomposable functions
Autor: Miquelina, Pedro Filipe Pereira
Orientador: Lobo, Fernando
Palavras-chave: Engenharia informática
Algoritmos genéticos
Data de Defesa: 2013
Resumo: In the past few years, there's been a growing interest in understanding genetic algorithm behavior and problem landscapes through visualization methods. This thesis tries to give an introduction to genetic algorithms and their theory, and describes a tool that attempts to better illustrate some of the important theoretical aspects behind a genetic algorithm, operating on additive decomposable functions, through the use of black and white images, in the form of an animation. Since these theoretical aspects can be hard to understand at first, this tool can be helpful for teaching purposes since it can provide different visualizations of a genetic algorithm working and provide real examples with images that can support some of the theory behind a genetic algorithm.
Inspirados pela seleção natural e pela genética, os algoritmos genéticos são métodos de otimização estocásticos utilizados para resolver problemas de otimização, tentando imitar a forma como a Natureza age. Na teoria de seleção natural, os indivíduos mais fortes de uma população sobrevivem e propagam as suas características genéticas para as gerações seguintes enquanto os mais fracos tendem a desaparecer. Na Natureza, uma população tem de se adaptar ao meio em que se encontra, mudando algumas características particulares ao longo de gerações através do uso da recombinação e da mutação. Ao trabalhar com algoritmos genéticos, um problema pode ser visto como um meio onde uma população de soluções se encontra e evolui ao longo de gerações, através do uso de uma combinação de seleção, recombinação e mutação para solucionar o problema. Podemos dizer que os algoritmos genéticos funcionam com uma população, isto é, um conjunto de soluções candidatas, que são normalmente inicializadas aleatoriamente, e que tem entre outros, dois importantes componentes, a seleção e a variação (recombinação e mutação). Para além da seleção e da variação, os algoritmos genéticos possuem outros componentes, tais como, a representação, a inicialização, a função de aptidão, a substituição da população, entre outros. Estes componentes, individualmente são fáceis de perceber, mas quando combinados, a teoria por detrás do funcionamento de um algoritmo genético é mais difícil de compreender. A teoria por detrás dos algoritmos genéticos baseia-se segundo John Henry Holland, no uso de esquemas. A teoria de esquemas de Holland, identifica as soluções como sendo parte de um conjunto de diversos padrões. Estes padrões, quanto menores e mais abrangentes, que possuam uma boa aptidão, são denominados de blocos construtores. Os algoritmos genéticos processam blocos construtores que são a chave para encontrar uma boa solução. É necessário que os blocos construtores sejam bem misturados e que cresçam em número. Para isto é essencial fornecer uma boa quantidade de blocos construtores na população inicial e o algoritmo genético deve saber escolher entre dois blocos construtores rivais. Os problemas unimodais (possuem só um máximo local), são fáceis de resolver para os algoritmos genéticos porque é fácil decidir entre blocos construtores, enquanto para problemas multimodais é mais complicado decidir entre blocos construtores devido à existência de pelo menos um máximo global e um máximo local. Neste tipo de problemas, onde se englobam as funções enganosas utilizadas nesta tese, quanto mais afastado o máximo global estiver do máximo local e quanto menor for a diferença entre eles, mais difícil se torna para os algoritmos genéticos resolverem o problema. Nos últimos anos tem existido um aumento na utilização de métodos visuais para tentar perceber melhor como funcionam os algoritmos genéticos e a teoria por detrás deles. Esta tese tenta fazer uma introdução aos algoritmos genéticos e à sua teoria, e descreve uma ferramenta que tenta ilustrar alguns dos aspetos importantes da teoria de algoritmos genéticos aplicados a funções de decomposição, com recurso a imagens a preto e branco em forma de animações. Tendo em conta que estes aspetos teóricos podem ser difíceis de compreender ao início, esta ferramenta pode ser uma boa ajuda para fins de ensino, uma vez que pode fornecer diferentes visualizações de algoritmos genéticos a trabalhar e fornecer exemplos reais com imagens para apoiar a teoria por detrás de um algoritmo genético.
URI: http://hdl.handle.net/10400.1/6820
Designação: Mestrado em Engenharia Informática
Aparece nas colecções:UA01-Teses

Ficheiros deste registo:
Ficheiro Descrição TamanhoFormato 
Pedro_Miquelina_-_Visualization_of_Genetic_Algorithms_Operation_on_Additive_Decomposable_Functions.pdf1,6 MBAdobe PDFVer/Abrir


FacebookTwitterDeliciousLinkedInDiggGoogle BookmarksMySpace
Formato BibTex MendeleyEndnote Degois 

Todos os registos no repositório estão protegidos por leis de copyright, com todos os direitos reservados.