Declarações prováveis ​​sobre algoritmos genéticos

56

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).

Suresh Venkat
fonte
5
Para alguma inspiração, veja também a p. 25–29 dos slides do FCRC de Papadimitriou em 2007 .
Jukka Suomela 01/09/10
11
@ Suresh: Eu preferiria vê-lo como uma pergunta ao invés de uma resposta ; Eu ficaria encantado se alguém tivesse o trabalho de explicar mais especificamente qual é o resultado a que Papadimitriou se refere nos slides. :)
Jukka Suomela 01/09/10
11
aqui está uma versão pop-sci desse trabalho: tinyurl.com/2f39jrb
Suresh Venkat
11
Recentemente, fez um curso de GA e meu hype sobre GA diminuiu quando eu aprendi o almoço Teorema Sem Free: en.wikipedia.org/wiki/No_free_lunch_in_search_and_optimization
Alexandru
11
Alexandru, por que isso? Deveria ser bastante óbvio que quase qualquer técnica será melhor que outras em alguns casos e pior em outros. Você realmente acreditava que o GA seria uniformemente superior?
Raphael

Respostas:

29

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 )

Joshua Grochow
fonte
Parece que o primeiro link está desativado.
Jeremy Kun
@JeremyKun: Eu apenas tentei e funcionou muito bem ... (Ele me faria triste se um link doi foi extinta, derrotando um dos principais objetivos do sistema de doi ...)
Joshua Grochow
Ainda estou recebendo o erro "Página não encontrada" da Biblioteca Wiley. Poderia ser um problema de formatação / navegador?
Jeremy Kun
@ JeremyKun: Poderia ser. Se você tem acesso a MathSciNet, tente este link em vez disso: ams.org/mathscinet-getitem?mr=1667317
Joshua Grochow
Não é um problema, porque o link para sua página inicial funciona. Eu só estava tentando ajudar a fazer esta resposta melhor :)
Jeremy Kun
13

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

Alex Lopez-Ortiz
fonte
11
Adicionar um link melhoraria esta resposta.
Dave Clarke
10

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.

Rahul Savani
fonte
10

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) .

Per Kristian Lehre
fonte
Por Kristian Lehre, eu apenas o vi e vi sua área de interesse, então gostaria de perguntar: você acha que ferramentas semelhantes podem ser usadas para analisar o tempo de execução dos algoritmos de otimização de colônias de formigas e as perguntas do tipo "Algoritmo Natural" de Chazelle ( taxa de convergência do número de aves)? No momento, as técnicas de Chazelle parecem uma ilha para elas mesmas, e eu estou me perguntando se há alguma imagem maior.
Aaron Sterling
2
Sim, essas técnicas podem ser adaptadas para analisar o tempo de execução dos ACOs. Recentemente, co-autor de um artigo sobre ACOs para o problema MinCut. Além disso, consulte a pesquisa de Witt (2009): springerlink.com/content/3727x3255r1816g4 Não conheço nenhum link atual desta pesquisa para o trabalho de Chazelle, mas certamente vale a pena explorar.
Por Kristian Lehre
7

O(n4)

Joshua Grochow
fonte
11
hey, ele está de volta :)
Suresh Venkat
6

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

Mohammad Al-Turkistany
fonte
6

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:

  • tt+1
  • O operador de mutação permite alternar de qualquer solução para outra em um número finito de etapas

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)

Lamine
fonte
6

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)

kburjorj
fonte
é inteligente / inovador usar o SAT aleatório como referência para o GA e mostra uma idéia que parece que poucos trabalhos exploraram. suponha que o GA possa trabalhar em qualquer classe de complexidade arbitrária e talvez seja realmente uma maneira de criar algoritmos em uma classe de complexidade "mais alta" com base nos resultados de algoritmos em uma classe de complexidade "mais baixa" ... então, em certo sentido, isso realmente não faz sentido para analisar a "complexidade" de AGs porque eles podem transcender classe classificação complexidade ....
vzn
5

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.

Jeremy
fonte