Eu tenho lido sobre o Teorema Sem Almoço Gratuito, mas não consigo entender direito do que se trata. Ouvi esse teorema descrito em outro lugar como a alegação de que "não existe um otimizador universal de propósito geral". Por outro lado, o artigo da Wikipedia fala sobre 'soluções candidatas' que são "avaliadas uma a uma" - se considerarmos apenas algoritmos de uma forma específica, essa é uma afirmação muito mais limitada.
Alguém pode explicar o que esse teorema realmente afirma?
algorithms
terminology
optimization
heuristics
Casebash
fonte
fonte
Respostas:
O teorema do No Free Lunch (NFL) foi estabelecido para desmascarar reivindicações do formulário:
Em particular, tais alegações surgiram na área de algoritmos genéticos / evolutivos.
A afirmação é, grosso modo: toda estratégia de otimização tem um desempenho ruim em muitos problemas. Portanto, não pode haver sempre a melhor estratégia e sua afirmação sobre X está errada.
fonte
Até onde eu entendo, essa teoria visa métodos de otimização global como algoritmos genéticos, redes neurais, recozimento simulado e assim por diante ...
A principal alegação é que, se considerarmos todas as possíveis instâncias de problemas de um determinado problema, esses métodos são tão bons quanto qualquer outro otimizador que considere a mesma quantidade de soluções candidatas, inclusive a Random Walk, por exemplo.
Os otimizadores de uso geral provavelmente funcionarão bem em muitas instâncias de problemas populares / da vida real, mas elas não representam bem todo o espaço de possíveis instâncias de problemas.
fonte