Quais são as limitações do algoritmo de escalada e como superá-las?

Respostas:

6

Como a @nbro já disse que o Hill Climbing é uma família de algoritmos de busca local . Então, quando você disse que Hill Climbing na pergunta, eu assumi que você está falando sobre a escalada padrão. A versão padrão da subida de montanha tem algumas limitações e geralmente fica presa no seguinte cenário:

  • Máximos locais: o algoritmo de escalada que atinge nas proximidades um valor máximo local, é atraído para o pico e fica preso lá, não tendo outro lugar para ir .
  • Pontes: são seqüências de máximos locais , dificultando a navegação do algoritmo.
  • Platôs: Esta é uma região plana do espaço de estados . Como não há subidas, o algoritmo geralmente se perde no platô.

Para resolver esses problemas, muitas variantes de algoritmos de subidas foram desenvolvidas. Estes são os mais usados:

  • A Escalada Estocástica em Colinas seleciona aleatoriamente os movimentos de subida. A probabilidade de seleção varia com a inclinação do movimento para cima.
  • A Escalada de Primeira Escolha implementa a anterior, gerando sucessores aleatoriamente até que uma melhor seja encontrada.
  • Pesquisas de alpinismo de reinício aleatório a partir de movimentos iniciais gerados aleatoriamente até que o estado do objetivo seja atingido.

O sucesso dos algoritmos de subidas depende da arquitetura da paisagem do espaço de estados. Sempre que existem poucos máximos e platôs, as variantes dos algoritmos de busca em subidas em colinas funcionam muito bem. Mas, no mundo real, os problemas têm uma paisagem que se parece mais com uma família amplamente dispersa de porcos-espinhos calvos em um piso plano, com porcos-espinhos em miniatura vivendo na ponta de cada agulha de espinhos-de-porco-espinho (conforme descrito no 4º capítulo do livro Inteligência Artificial: A Abordagem Moderna). Os problemas de NP-Hard normalmente têm um número exponencial de máximos locais para travar.
Algoritmos específicos foram desenvolvidos para superar esses tipos de problemas:

  • Recozimento estimulado
  • Pesquisa de vigas locais
  • Algorítmos genéticos

Livro de Referência - Inteligência Artificial: Uma Abordagem Moderna

Ugnes
fonte
Existem mais alternativas disponíveis para superar os problemas da escalada; ou seja, grupos de permutação, bancos de dados de padrões e pesquisa baseada em gramática. Eles estão usando conhecimento específico do domínio para pesquisar mais rapidamente no espaço de estado.
Manuel Rodriguez
Sim @ManuelRodriguez. Algoritmos dependentes do conhecimento específico do domínio fornecem excelentes resultados. Mas tentei manter a resposta para problemas genéricos, mencionando algumas das maneiras que podem superar as limitações do Hill Climb Search.
Ugnes
5

A escalada não é um algoritmo, mas uma família de algoritmos de "pesquisa local". Os algoritmos específicos que se enquadram na categoria de algoritmos de "escalada" são 2-opt, 3-opt, 2.5-opt, 4-opt ou, em geral, qualquer N-opt. Veja o capítulo 3 do artigo " O Problema do Vendedor Viajante: Um Estudo de Caso em Otimização Local " (de David S. Johnson e Lyle A. McGeoch) para obter mais detalhes sobre alguns desses algoritmos de busca local (aplicados ao TSP).

O que diferencia um algoritmo dessa categoria do outro é a "função de vizinhança" que eles usam (em palavras simples, a maneira como encontram soluções vizinhas para uma determinada solução). Observe que, na prática, esse nem sempre é o caso: geralmente esses algoritmos têm várias implementações diferentes.

A limitação mais evidente dos algoritmos de alpinismo se deve à sua natureza, ou seja, são algoritmos de busca local. Portanto, eles geralmente apenas encontram o máximo local (ou mínimo). Portanto, se algum desses algoritmos já convergiu para um mínimo local (ou máximo) e, no espaço de solução ou pesquisa, existe, próximo a essa solução encontrada, uma solução melhor, nenhum desses algoritmos será capaz de encontrar isso. melhor solução. Eles basicamente ficarão presos.

Os algoritmos de pesquisa local geralmente não são usados ​​sozinhos. Eles são usados ​​como sub-rotinas de outros algoritmos meta-heurísticos, como recozimento simulado, pesquisa local iterada ou em qualquer um dos algoritmos de colônia de formigas. Portanto, para superar suas limitações, geralmente não as usamos sozinhas, mas as usamos em conjunto com outros algoritmos, que têm uma natureza probabilística e podem encontrar mínimos ou máximos globais (por exemplo, qualquer um dos algoritmos de colônia de formigas).

nbro
fonte
Boa resposta (+1)! Você pode recomendar um recurso (YouTube, postagem no blog, artigo arxivo, livro) para aprender sobre os algoritmos de colônia de formigas? Eu nunca ouvi falar disso e gostaria de ter uma idéia aproximada deles.
22418 Martin Thoma
11
@MartinThoma Acho que realmente não conheço um tutorial muito bom sobre o ACS. Talvez você possa começar com o seguinte breve tutorial e a implementação correspondente: cleveralgorithms.com/nature-inspired/swarm/… . Se você também estiver interessado em uma implementação mais séria, aplicada ao TSP, dê uma olhada neste: aco-metaheuristic.org/aco-code , implementado por Stützle (e outros), um dos colaboradores do desenvolvimento dessas técnicas.
Nbro
O autor da pergunta sabe qual é a definição formal de escalada porque ele leu o artigo da Wikipedia. A questão vai mais na direção de como usá-lo para Inteligência Artificial. Sabe-se que a escalada em montanhas só pode pesquisar no espaço local, o que dificulta os problemas relacionados à IA. Geralmente, a pesquisa fica presa em um local ideal, o que significa que não é possível encontrar a rota mais curta no problema do vendedor ambulante.
Manuel Rodriguez
11
De qualquer forma, você também pode dar uma olhada nos trabalhos de pesquisa. Só posso lhe dizer alguns pesquisadores importantes: Dorigo (o primeiro que introduziu essas técnicas, AFAIK), Gambardella e Stützle. Olhe para os papéis deles. Não sei ao certo qual sugerir. Além disso, há um livro dedicado à inteligência de enxame (de Bonabeau), se você realmente quiser entrar em detalhes.
Nbro