Please use this identifier to cite or link to this item: http://repositorio.ufpa.br/jspui/handle/2011/8014
metadata.dc.type: Dissertação
Issue Date: 30-Jun-2015
metadata.dc.creator: FRANCO, Dielle da Silva Corrêa
metadata.dc.contributor.advisor1: OLIVEIRA, Roberto Célio Limão de
metadata.dc.contributor.advisor-co1: SANTANA, Ádamo Lima de
Title: Desempenho do algoritmo genético com iteração retroviral para otimização de funções com representação real
Other Titles: Performance evaluation of genetic algorithm with retroviral iteration for real-valued functions optimization
Citation: FRANCO, Dielle da Silva Corrêa. Desempenho do algoritmo genético com iteração retroviral para otimização de funções com representação real. 2015. 72 f. Dissertação (Mestrado) - Universidade Federal do Pará, Instituto de Tecnologia, Belém. 2015. Programa de Pós-Graduação em Engenharia Elétrica.
metadata.dc.description.resumo: A ideia da infecção viral vem sendo utilizada nos Algoritmos Genéticos (AG) para melhorar a taxa de busca dos algoritmos, superando a convergência prematura por meio do controle da diversidade da população, visto que na natureza a recombinação genética por vírus apresenta alta velocidade de replicação e frequente mutação. [Romano 2009]. A meta-heurística denominada AGRI adotou como fonte de inspiração biológica a família retroviridae, cujos vírus são baseados em RNA e atendem à necessidade de maior variação alélica do AG, visto que o RNA não possui os mecanismos de correção em seu genoma para eliminar o material viral recombinado. Neste algoritmo, os vírus são tratados como uma população separada da população de indivíduos. A cada infecção, o material genético viral é transmitido verticalmente entre os hospedeiros difundindo trechos de soluções dos vírus com melhor desempenho por toda população. A diversidade viral é mantida por meio de um mecanismo que substitui todos o vírus fora da taxa de elitismo viral. Nessa técnica, a população viral evolui junto com a população cromossômica, pois os vírus ineficientes são criados a partir do material genético dos indivíduos mais adaptados e de outros genes novos. O AGRI segue os princípios biológicos em vários aspectos da infecção e multiplicação viral. Por exemplo: cria a primeira população viral sem o material genético da população somática; escolhe aleatoriamente os vírus que irão infectar um indivíduo, possibilitando que parte da população nunca seja infectada por alguns vírus e que certos vírus infectem mais indivíduos. Além disso, a partir da segunda geração do AG, os vírus substituídos são criados com material genético de dois indivíduos, e tem diferentes quantidades de genes. Nesta abordagem, a maximização do espaço de busca é realizado utilizando três mecanismos: alta variabilidade genética da população viral com tamanhos diferentes dos trechos de soluções; efetivação da infecção apenas quando há um aumento no fitness do indivíduo; e possibilidade de um indivíduo ser infectado por quaisquer dos vírus da população viral. Para analisar o efeito dos parâmetros da infecção viral do AGRI e seu desempenho em comparação com outras meta-heurísticas bem conceituadas, as seguintes funções de benchmarking relacionadas com problemas de minimização foram selecionadas: F1 (Shifted Sphere Function), F2 (Shifted Schwefel’s Problem), F3 (Shifted Rotated High Conditioned Elliptic Function) e F5 (Schwefel’s Problem 2.6 with Global Optimum on Bounds). Os resultados mostraram que para funções unimodais propostas, o AGRI tem boa performance em comparação com as outras meta-heurísticas selecionadas podendo alcançar o ótimo global ou boas soluções com poucas iterações.
Abstract: Viral Infection is used to improve the performance in Genetic Algorithms (GA) by reducing premature convergence through the population diversity control, since viruses presents high replication and mutation rates in the nature. The metaheuristic called AGRI is inspired biologicaly in a viruses family based on RNA, which provide a high allelic variation to GA, since RNA doesn’t have genoma correction mechanisms to remove re-combined viral genetic material . In this algorithm, the viruses are a separate population. To each infection, the better performance viruses genomes are transmitted vertically spreading parts of solutions to GA population. The diversity viral is maintained through a mechanism that substitutes all viruses out of elitism viral rate. In this method, the virus population evolves along with GA population, so the inefficient viruses are created from genetic material of the better adapted individuals and other new genes. The algorithm AGRI follows biological principles in several viral infection and multiplication aspects. For example: it creates the first viral population without GA population genetic material; it sorts the viral population before infect an individual, making possible some viruses doesn’t infected a part of the population and other viruses infect more individuals. Since GA second-generation, the replaced viruses are created by both individuals genetic material and have different genes quantities. In this approach, the search space maximization is increased by three mechanisms: high viral population genetic variability by variety of sizes to solutions pieces; infection validation process that confirms the fitness increases in each individual and infection possibility by any viruses in the viral population. To analyse the AGRI’s viral infection parameters effects and comparate his performance with others high-performing metaheuristics, the following minimization benchmarking are selected: F1 (Shifted Sphere Function), F2 (Shifted Schwefel’s Problem), F3 (Shifted Rotated High Conditioned Elliptic Function) e F5 (Schwefel’s Problem 2.6 with Global Optimum on Bounds). The results to the functions unimodais proposed showed that AGRI has a good performance in comparison with others metaheuristics reaching in few iterations the global best or good results.
Keywords: Algoritmos genéticos
Infecção viral do AGRI
Otimização combinatória
Computação evolucionária
Algoritmo Genético Retroviral Iterativo (AGRI)
metadata.dc.subject.cnpq: CNPQ::CIENCIAS EXATAS E DA TERRA::CIENCIA DA COMPUTACAO
metadata.dc.publisher.country: Brasil
Publisher: Universidade Federal do Pará
metadata.dc.publisher.initials: UFPA
metadata.dc.publisher.department: Instituto de Tecnologia
metadata.dc.publisher.program: Programa de Pós-Graduação em Engenharia Elétrica
metadata.dc.rights: Acesso Aberto
Appears in Collections:Dissertações em Engenharia Elétrica (Mestrado) - PPGEE/ITEC

Files in This Item:
File Description SizeFormat 
Dissertacao_DesempenhoAlgoritmoGenetico.pdf2,41 MBAdobe PDFView/Open


This item is licensed under a Creative Commons License Creative Commons