Algoritmo evolutivo centrado nos genes

Data
2017-09-18
Título da revista
ISSN da revista
Título do Volume
Editora
Projetos de investigação
Unidades organizacionais
Fascículo
Resumo
Todas as espécies biológicas, nas suas diferentes formas microbianas, animal ou vegetal, estão sujeitas a processos de evolução que resulta da luta continuada pela sobrevivência, na melhoria das suas capacidades de integração no seu ecossistema, no aperfeiçoamento das suas capacidades em se adaptar ao meio ambiente e às suas perturbações, por vezes na forma de cataclismos, mas também de assegurar a transmissão dos seus genes às gerações seguintes. O seu estado presente como espécie é fruto da evolução que nunca parou de acontecer desde que o elemento primário da vida se despoletou na Terra, aproximadamente entre 3,5 a 3,8 mil milhões de anos atrás. A evolução é a mudança nas características hereditárias das populações biológicas ao longo das gerações sucessivas. Os processos evolutivos dão origem à biodiversidade em todos os níveis da organização biológica, incluindo os níveis de espécies, organismos individuais e moléculas. A transposição deste mecanismo para o mundo dos computadores levou ao desenvolvimento do designado algoritmo genético (AG). Este algoritmo é do tipo meta-heurístico de inspiração no processo de seleção natural, fazendo parte de uma classe maior designada de algoritmos evolutivos (AE). Algoritmos genéticos são tipicamente usados para gerar soluções de alta qualidade para otimização e problemas de pesquisa, confiando em operadores de inspiração biológicos ligados à seleção e reprodução, como sejam a mutação, cruzamento e seleção. Este trabalho tem como objetivo principal contribuir na linha dos algoritmos genéticos com o desenvolvimento de uma abordagem paralela em duas frentes: a evolução geracional dos indivíduos em multipopulações com a existência de processos migratórios e a evolução de genes, tomando-os como entidades passíveis de se envolverem num processo evolutivo. O paradigma norteador deste trabalho visa explorar a simultaneidade de um processo evolutivo focalizado em duas entidades no indivíduo e nos genes. O foco secundário e complementar, por poder-se revelar computacionalmente eficiente, está na estrutura de paralelização, ou seja, o modelo de algoritmo genético paralelo. A arquitetura modelada é baseada nos conceitos de programação orientada a objetos e explora o paralelismo de sistemas de multiprocessadores ao mesmo tempo que permite a distribuição através de uma rede de workstations. O algoritmo genético paralelo está modelado segundo o conceito de populações cooperantes, coordenadas por um nó central. Nesse modelo, cada máquina é responsável por processar uma população com N indivíduos. A troca de informação genética entre populações é realizada através da migração de indivíduos, alocados fisicamente a cada máquina. Os indivíduos foram modelados como unidades autónomas com a responsabilidade da aplicação dos operadores de crossover e mutação. Cada indivíduo é também responsável pela determinação da sua aptidão. Esta perspetiva torna simples a exploração do paralelismo encontrado nos sistemas multiprocessados. A hipótese defendida indica que um conjunto de populações cooperantes, executando em paralelo, equivale a uma grande população. Para avaliar o desempenho desta nova abordagem, foram realizados testes utilizando um algoritmo para simular o ambiente distribuído e o paralelismo dos sistemas multiprocessados, através de programação concorrente. Foram usados dois exemplos de teste e validação do algoritmo. Os resultados obtidos evidenciam a virtude do paralelismo do algoritmo genético multipopulacional, na perspetiva da evolução conjunta e concorrente dos indivíduos e dos seus genes.
All biological species, in their different microbial forms, animal or plant, subject to evolutionary processes that result from the continuous struggle for survival, in the improvement of their capacity of integration in their ecosystem, on the improvement of their capacities in adapting to the environment and their disruptions, sometimes in the form of cataclysms, but also to ensure a transmission of their genes to subsequent generations. Its state is the fruit of evolution that has never stopped happening since the primary element of life sprang on Earth, about 3.5 to 3.8 billion years ago. Evolution is the change in the hereditary characteristics of biological populations over successive generations. Evolutionary processes give rise to biodiversity at all levels of the biological organization, including levels of species, individual organisms and molecules. The transposition of this mechanism to the world of computers led to the development of the so-called genetic algorithm (GA). This algorithm is of the metaheuristic type of inspiration in the natural selection process, being part of a larger class called evolutionary algorithms (EA). Genetic algorithms are typically used to generate high-quality solutions for optimization and research problems, relying on biological inspiration operators linked to selection and reproduction, such as mutation, crossover, and selection. The main objective of this work is to contribute with the development of a parallel approach on two fronts: the generational evolution of individuals in multipopulations with the existence of migratory processes; The evolution of genes, taking them as entities that can be involved in an evolutionary process. The guiding paradigm of this work aims to explore the simultaneity of an evolutionary process focused on two entities in the individual and genes. The secondary and complementary focus, because it can be computationally efficient, is in the structure parallelization, that is, the parallel genetic algorithm model. The modeling architecture is based on the concepts of object-oriented programming and exploits the parallelism of multiprocessor systems while allowing distribution across a network of workstations. The parallel genetic algorithm has modeled according to the concept of cooperating populations, coordinated by a central node. In this model, each machine is responsible for processing a population with N individuals. The exchange of genetic information among populations is accomplished through the migration of individuals, physically allocated to each machine. Individuals were modeled as autonomous units with responsibility for the application of crossover and mutation operators. Each individual is also responsible for determining their fitness. This perspective makes it simple to explore the parallelism found in multiprocessor systems. The hypothesis advocated indicates that a set of cooperating populations, running in parallel, is equivalent to a large population. To evaluate the performance of this new approach, tests were performed using an algorithm to simulate the distributed environment and the parallelism of the multiprocessor systems, through concurrent programming. Two tests and validation algorithm samples were used. The results obtained evidenced the virtue of the parallelism of the multipopulation genetic algorithm, in the perspective of the grouped and concurrent evolution of individuals and their genes.
Descrição
Dissertação de Mestrado em Engenharia Eletrotécnica e de Computadores
Palavras-chave
Algoritmos genéticos , Indivíduo , Evolução , Gene , Paralelismo , Multipopulação
Citação