Pelo que entendi, algoritmos genéticos experimentam múltiplas variações e avaliam a adequação de cada variação. Depois, eles selecionam as melhores variações, alteram-nas um pouco e continuam o processo com a próxima geração.
Mas e se tivermos recursos computacionais ilimitados? Podemos então experimentar todas as variações possíveis e avaliar sua adequação sem recorrer ao complexo processo de criação de novas gerações? Em outras palavras, os algoritmos genéticos são necessários apenas quando o cálculo é caro e quando um método de força bruta é impossível? Ou eles acrescentam outros benefícios também?
genetic-algorithms
Eugene
fonte
fonte
Respostas:
Os algoritmos genéticos são basicamente uma metodologia guiada de tentativa e erro. A única vantagem que posso pensar para um GA em relação a uma pesquisa exaustiva é que, como o GA otimiza uma função de condicionamento físico em etapas, você pode obter uma solução ideal mais rapidamente, porque o GA favorecerá soluções que são incrementalmente melhores. Uma pesquisa exaustiva, garantida para encontrar uma solução, pode percorrer o longo caminho.
Se "recursos de computação" significa CPU, mas não memória, o pool genético do GA pode ter um espaço menor de memória, exigindo menos memória.
Por outro lado, por causa da escalada, um GA pode ficar preso no máximo local e quaisquer mutações podem não ser suficientes para soltá-lo.
Além disso, o tempo de pesquisa para o GA aumenta exponencialmente com o tamanho da entrada, portanto, uma pesquisa exaustiva pode acabar sendo mais rápida, dependendo do tamanho do espaço que você está pesquisando e se você pode restringir o tamanho do espaço excluindo possibilidades.
...
Ultimamente, tenho pensado nos AGs em termos de "entropia por segundo" e medindo o progresso do meu AG como uma medida de quantas possibilidades distintas ele percorre por segundo. Então eu posso comparar isso com a entropia total do espaço do problema. Se uma pesquisa de força bruta pode superar essa entropia por segundo com paralelização ou processadores rápidos, a "melhor pontuação" de um GA não é melhor do que a "melhor pontuação" descoberta.
Mas eu acabei de pensar nisso; Ainda não instrumentei um GA dessa maneira.
(Entropia é
ln(N)para N estados possíveis ouln(N) - sum(n * ln(n) for all n) / Nondenestão as maneiras possíveis de obter um resultado dentre N possíveis resultados.)Pergunta interessante :)
fonte
Sim, se a computação fosse gratuita, você não precisaria de algoritmos genéticos. Mas lembre-se de que este é um enorme "se" que nenhum de nós jamais viverá para ver!
Ainda assim, já que você está perguntando ... se a computação fosse infinitamente rápida, não haveria motivo para não aplicar a marreta mais simples de gerar e testar combinatória de força bruta a um problema. Toda pergunta que possa ser respondida com um conjunto finito de informações (isto é, um problema de satisfação de restrição no sentido mais amplo possível desse termo, que é bastante flexível) seria instantaneamente solucionável; escaladas, heurísticas e todas as simplificações inteligentes que usamos agora para construir, por exemplo, um motor de xadrez de classe mundial simplesmente não seriam necessárias.
Em outras palavras, se a computação se aproximar da velocidade infinita, a decisão de qual abordagem usar se baseia em quão difícil é escrever o programa de computador a ser executado, e não em quanto tempo leva para ser executado; e isso significa que simplesmente não vale a pena inventar um algoritmo mais complicado quando o mais simples possível também funcionar e executar ao mesmo tempo.
Indiscutivelmente, a computação tem realmente se movido nessa direção, mas lembre-se de que ainda não chegamos lá, e provavelmente nunca estaremos. (A menos que o computador quântico seja aperfeiçoado, é claro.)
fonte
O problema com cálculos infinitamente rápidos é que eles cobrem infinitamente rápido um espaço de estados que é maior que o limite de informações do nosso universo conhecido. Você mencionou "força bruta", no entanto, considere que o xadrez de força bruta, por exemplo, pode produzir uma saída que excede em tamanho o número de átomos no universo.
Tomando o exemplo do xadrez ainda mais, à medida que você bruta a força bruta, você precisa diminuir o número de combinações de tabuleiro de xadrez que considera e terá que tomar uma decisão sobre quais estados manter e quais descartar - algoritmos realmente seletivos, como algoritmos genéticos, sempre será necessário.
fonte
Se por "recursos de computação ilimitados" você quer dizer que seu algoritmo levaria 0 tempo e que a memória é ilimitada e a eletricidade não é preocupante, eu diria que o único algoritmo a ser utilizado seria um algoritmo de força bruta que tenta todas as entradas possíveis e é garantido para encontrar o melhor. Se você está se referindo à memória ilimitada, mas é possível uma diferença de tempo possível, um algoritmo genético pode ser preferível, pois pode chegar a uma solução mais rapidamente que um algoritmo de força bruta. Mas a solução do algoritmo genético pode não ser a ideal, portanto, dependendo do contexto e de seus requisitos, você ainda pode preferir o método da força bruta.
Dado que recursos ilimitados de computação não são possíveis, a questão parecia a princípio especulação inativa. Mas, à medida que obtemos cada vez mais poder computacional, a questão se torna mais relevante, pois talvez não precisemos de algoritmos genéticos em uma época de enormes supercomputadores. No entanto, notei que, à medida que os computadores se tornam mais poderosos, continuamos pedindo que façam cálculos cada vez mais difíceis com mais e mais dados. Então, no final, acho que os algoritmos genéticos estarão conosco no futuro próximo e serão usados mesmo quando houver muito poder de computação disponível.
No entanto, se recursos de computação verdadeiramente ilimitados se tornassem disponíveis, muito mais mudaria do que o uso ou não de algoritmos genéticos.
fonte