Complexidade temporal de algoritmos genéticos

9

Como você determina a complexidade temporal de um algoritmo genético (em geral)? Se possível.

Eu tenho pensado muito sobre isso, e todo o ensino que tive está relacionado à determinação da complexidade temporal de problemas de natureza muito menos estocástica.

Jack H
fonte
11
Não há praticamente nenhuma garantia de que um algoritmo genético encontre uma solução suficientemente boa. Portanto, é difícil falar sobre quanto tempo levará. Embora eu ache que você estava procurando uma abordagem probabilística para começar ... Aqui está um artigo que pesquisei no Google que parece relevante.
usar o seguinte código
Adorável obrigado. Isso deve ser uma leitura para o meu trem amanhã.
Jack H

Respostas:

8

Os algoritmos genéticos são uma metaheurística e, como tal, não existe uma análise geral que se aplique a todos os algoritmos genéticos de uma só vez (sem ser super flexível). Em geral, ao procurar informações sobre o tempo de execução dos algoritmos genéticos, você terá mais sorte se usar os termos "tempo de convergência", pois essa é a terminologia mais comum. Um bom começo para algumas técnicas formais:

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.

Para obter mais recursos sobre tratamentos formais, considere a questão da história: Declarações prováveis sobre algoritmos genéticos .

Artem Kaznatcheev
fonte
3

Concordo com as respostas anteriores e também adiciono o seguinte.

Normalmente, não nos importamos com a complexidade temporal de um algoritmo genético. Em geral, nos preocupamos com a qualidade dos resultados em comparação com alguns benchmarks e com a taxa de convergência.

Você pode ver, no entanto, que algoritmos genéticos são executados em iterações. Inicialmente, um conjunto de soluçõesS são gerados aleatoriamente (Sé chamado de população). Os custos das soluções deSsão computados. Algumas operações são feitas sobre as soluções deSem cada iterações como crossover, mutação etc .... Ao melhork soluções em k são mantidos em Se continuamos como anterior. Após a última iteração, produzimos a melhor solução que encontramos.

Você pode observar aqui que o custo de tempo de uma iteração depende das operações internas (por exemplo, crossovers, mutações e outras, encontrar as melhores k soluções distintas, gerar soluções aleatórias, calcular o custo das soluções de Setc.) que geralmente são simples de implementar e também dependem de problemas. Em geral, eles dependem do tamanho de uma solução.

O tempo de execução de um algoritmo genético também depende do número de iterações (obviamente!). Normalmente, queremos parar quando convergimos para uma solução que dificilmente é aprimorada. Como encontrar o número de iterações que garantem isso? existem algumas análises probabilísticas para encontrar o tempo médio de convergência. Veja por exemplo [1] (resultados bastante interessantes). Mas você notará que ainda não atingimos o nível de análise dos problemas complexos em que os algoritmos genéticos são usados. Portanto, em muitos casos, o número de iterações em um algoritmo genético é decidido experimentalmente.

[1] Oliveto, Pietro S., Jun He e Xin Yao. "Complexidade temporal de algoritmos evolutivos para otimização combinatória: uma década de resultados". International Journal of Automation and Computing 4.3 (2007): 281-293.

AJed
fonte