Significado de métodos (meta) heurísticos

1. Para otimização, da Wikipedia :

   Na ciência da computação, a metaheurística designa um método computacional que otimiza um problema, tentando iterativamente melhorar uma solução candidata em relação a uma determinada medida de qualidade. As metaheurísticas fazem poucas ou nenhuma suposição sobre o problema que está sendo otimizado e podem pesquisar espaços muito grandes de soluções candidatas. No entanto, as metaheurísticas não garantem que uma solução ideal seja encontrada. Muitas metaheurísticas implementam alguma forma de otimização estocástica.

   Outros termos com um significado semelhante ao metaheurístico são: pesquisa direta, livre de derivativos, caixa preta ou apenas otimizador heurístico. Vários livros e documentos de pesquisa foram publicados sobre o assunto.

   • Gostaria de saber como saber se um método de otimização é metaheurístico ou não? Por exemplo,

     (1) O método simplex para programação linear é metaheurístico?

     (2) A maioria dos métodos de programação não linear, como descida em gradiente, método multiplicador Lagrangiano, métodos de penalidade, métodos de pontos interiores (métodos de barreira), são metaheurísticos?

     (3) Todos os métodos sem gradiente, como o método Nelder – Mead ou o método simplex em declive, são metaheurísticos?

   • Quais são alguns métodos de otimização que não são metaheurísticos?

2. Mais geralmente (indo além da otimização) para técnicas de resolução de problemas, da Wikipedia :

   Heurística refere-se a técnicas baseadas na experiência para resolução de problemas, aprendizado e descoberta . Onde uma pesquisa exaustiva é impraticável, métodos heurísticos são usados ​​para acelerar o processo de encontrar uma solução satisfatória. Exemplos desse método incluem o uso de uma regra de ouro, um palpite fundamentado, um julgamento intuitivo ou bom senso.

   Em termos mais precisos, heurísticas são estratégias que utilizam informações prontamente acessíveis, embora pouco aplicáveis, para controlar a resolução de problemas em seres humanos e máquinas.

   Gostaria de saber como entender o significado de "heurística"?

   • como posso saber se uma técnica de "solução de problemas, aprendizado e descoberta" é heurística ou não?

   • Quais são algumas técnicas de "resolução de problemas, aprendizado e descoberta" que não são heurísticas?

Obrigado e cumprimentos!

A heurística é algo que funciona em muitos casos na prática, embora não exista um argumento detalhado sobre por que deve funcionar bem.

Metaheurísticas não é um algoritmo, mas um esquema ou idéia heurística geral que pode ser usada dentro de algoritmos específicos.

Por exemplo, o algoritmo simplex para programação linear não é heurística nem metaheurística, pois possui uma teoria de convergência bem estabelecida. O sqame vale para programação quadrática estática ou métodos de pontos internos. (Os métodos pontuais interiores são um esquema geral, mas não heurístico e, portanto, não uma metaheurística, pois existe uma teoria bastante forte associada a ele.)

O algoritmo Nelder-Mead = simplex em declive para minimizar uma função é heurística (na verdade, pode falhar em problemas bastante simples em dimensões mais altas), e a pesquisa por tabu é meta-heurística (já que muitos algoritmos diversos podem ser escritos que empregam a pesquisa por tabu, mas são de outra forma de qualidade bastante diferente.

Não vou repetir o simplex e o Nelder-Mead, já que o @ArnoldNeumaier já deu uma explicação muito boa, mas queria adicionar meus 2 centavos.

Uma das melhores citações que ouvi há algum tempo atrás para descrever a diferença entre heurística e metaheurística: Uma heurística é uma regra muito boa. Uma metaheurística é uma regra muito boa para encontrar regras muito boas.

Você deve ver isso como uma maneira de encontrar boas heurísticas para problemas específicos; basicamente, se você se perguntar uma das seguintes perguntas, está falando de uma metaheurística:

• Como devo ajustar os parâmetros dessa heurística para melhorar o desempenho desse problema?
• Essa heurística é melhor que a heurística?

Há várias metaheurísticas que você pode usar para solucionar problemas, aprender e descobrir , a saber:

• Recozimento simulado : usei este em um problema para otimizar o posicionamento dos componentes conectados em uma grade para minimizar o custo total da conexão, por exemplo.
• Enxame de partículas
• Colônia de formigas
• Pesquisa por tabu

Acho que a maioria das metaheurísticas é um pouco inspirada em fenômenos naturais, difíceis de explicar rigorosamente, mas com boas propriedades de convergência.

Aqui está um bom link, se você quiser ler mais sobre outras técnicas metaheurísticas