Os algoritmos genéticos não recebem muita tração no mundo da teoria, mas são um método metaheurístico razoavelmente bem usado (por metaheurístico, quero dizer uma técnica que se aplica genericamente a muitos problemas, como recozimento, descida de gradiente e outros). De fato, uma técnica do tipo GA é bastante eficaz para o TSP euclidiano na prática.
Algumas metaheurísticas são razoavelmente bem estudadas teoricamente: há trabalhos sobre busca local e recozimento. Temos um bom senso de como a otimização alternada ( como k-means ) funciona. Mas até onde eu sei, não há nada realmente útil sobre algoritmos genéticos.
Existe alguma teoria algorítmica / complexidade sólida sobre o comportamento dos algoritmos genéticos, de alguma forma, forma ou formato? Embora tenha ouvido falar de coisas como a teoria de esquemas , a excluiria da discussão com base no meu entendimento atual da área por não ser particularmente algorítmica (mas posso estar enganado aqui).
fonte
Respostas:
Y. Rabinovich, A. Wigderson. Técnicas para limitar a taxa de convergência de algoritmos genéticos. Algoritmos de Estruturas Aleatórias, vol. 14, n. 2, 111-138, 1999. (Também disponível na home page de Avi Wigderson )
fonte
Veja o trabalho de Benjamin Doerr, do grupo Algorithms at Max Planck (MPI). Trata-se de tentar fazer contribuições prováveis para algoritmos evolutivos.
Em particular, Doerr co-editou um livro recente relevante, Theory of Randomized Search Heuristics
fonte
Além de trabalhar no recozimento simulado, Ingo Wegener teve alguns resultados teóricos sobre algoritmos evolutivos. A tese de seu aluno de doutorado Dirk Sudholt também merece uma olhada.
fonte
Você conhece este artigo:
Jens Jägersküpper. Combinando Análise de Cadeia de Markov e Análise de Deriva: O Algoritmo Evolucionário (1 + 1) em Funções Lineares Recarregadas .
fonte
Durante a última década, houve um progresso significativo na análise em tempo de execução de algoritmos evolutivos, otimização de colônias de formigas e outras metaheurísticas. Para uma pesquisa, consulte Oliveto et al. (2007) .
fonte
fonte
Verifique estas referências:
Lothar Schmitt, Teoria dos algoritmos genéticos II: modelos para operadores genéticos sobre a representação tensor de cordas de populações e convergência para ótimos globais para função de aptidão arbitrária sob escala
Shiu Yin Yuen; BKS Cheung, Limites para probabilidade de sucesso do algoritmo genético clássico baseado na distância de hamming
Chang CY Dorea; Judinor A. Guerra Jr .; Rafael Morgado; Andre GC Pereira, Modelagem em Cadeia Markov de Vários Estágios do Algoritmo Genético e Resultados de Convergência
C. Dombry, um modelo de caminhada aleatória ponderada. Aplicação a um algoritmo genético
fonte
Há também um artigo de D. BHANDARI, CA MURTHY e SK PAL (infelizmente indisponível online) que fornece uma prova de convergência sob duas suposições:
A prova de convergência usa um modelo de cadeia de Markov.
Aqui está a referência: Dinabandhu Bhandari, CA Murthy: algoritmo genético com modelo elitista e sua convergência. IJPRAI 10 (6): 731-747 (1996)
fonte
Os modelos matemáticos de algoritmos genéticos com populações finitas, mas não unitárias, são difíceis de manejar e, até o momento, mostraram-se inamovíveis para a análise de todas as funções de aptidão, exceto as mais triviais. Curiosamente, se você estiver disposto a aceitar um argumento de simetria , um argumento, em outras palavras, não formulado dentro dos limites de um sistema axiomático formal, haverá um resultado interessante e bonito a ser obtido sobre o poder computacional dos algoritmos genéticos.
Especificamente, um algoritmo genético com cruzamento uniforme é capaz de avaliar um grande número de partições de esquema grosso implicitamente e em paralelo, e pode identificar eficientemente partições cujos esquemas constituintes têm valores médios de aptidão diferentes. Essa forma de paralelismo implícito é realmente mais poderosa do que o tipo descrito por John Holland e seus alunos, e ao contrário do paralelismo implícito descrito por Holland, pode ser verificado experimentalmente. (Veja esta postagem no blog.)
O artigo a seguir explica como algoritmos genéticos com parlay de cruzamento uniforme implicam paralelismo em uma heurística de otimização global de uso geral chamada hipercalta :
Explicando a otimização em algoritmos genéticos com cruzamento uniforme . Participar dos trabalhos da conferência Foundations of Genetic Algorithms 2013.
(Isenção de responsabilidade: eu sou o autor do artigo)
fonte
Raphael Cerf fez sua tese de doutorado sobre algoritmos genéticos em Montpellier, sob a supervisão de Alain Berlinet, do ponto de vista matemático. É bastante antigo, mas provavelmente pertenceria a qualquer bibliografia sobre algoritmos genéticos.
fonte