Quelle est la différence entre l'escalade stochastique et le recuit simulé?

Nov 24 2020

Je lis sur la recherche locale: l'escalade et ses types et le recuit simulé

L'une des versions d'escalade est "l'escalade stochastique", qui a la définition suivante:

L'escalade stochastique n'examine pas pour tout son voisin avant de se déplacer. Au contraire, cet algorithme de recherche sélectionne un nœud voisin au hasard et décide de le choisir comme état actuel ou d'examiner un autre état

Certaines sources ont mentionné qu'il peut être utilisé pour éviter les optima locaux.

Ensuite, j'ai lu sur le recuit simulé et sa définition:

A chaque itération, un mouvement aléatoire est choisi. Si cela améliore la situation, le mouvement est accepté, sinon il est accepté avec une probabilité inférieure à 1

Alors, quelle est la principale différence entre les deux approches? Le stochastique choisit-il uniquement un successeur aléatoire (en montée)? S'il choisit uniquement (successeurs en montée), comment évitera-t-il les optima locaux?

Réponses

4 nbro Nov 24 2020 at 03:56

Le livre de Russell et Norvig (3e édition) décrit ces deux algorithmes (section 4.1.1., P. 122) et ce livre est la référence que vous devriez généralement utiliser lorsque vous étudiez les algorithmes de recherche en intelligence artificielle. Je connais le recuit simulé (SA), étant donné que je l'ai implémenté dans le passé pour résoudre un problème combinatoire, mais je ne suis pas très familier avec l'escalade stochastique (SHC), alors laissez-moi citer les parties du livre qui décrivent SHC .

L'escalade stochastique choisit au hasard parmi les mouvements de montée; la probabilité de sélection peut varier avec la raideur de la montée. Cela converge généralement plus lentement que l'ascension la plus raide, mais dans certains paysages d'État, il trouve de meilleures solutions.

Ainsi, SHC choisit au hasard un "mouvement ascendant", c'est-à-dire un mouvement qui améliore la fonction objectif (par exemple, si vous essayez de résoudre le problème du voyageur de commerce , un "mouvement ascendant" pourrait être n'importe quel changement du cycle hamiltonien actuel , une solution, de sorte que le nouveau cycle halmitonien ait un coût plus court) parmi les mouvements en montée (donc parmi certains ensembles de mouvements qui améliorent l'objectif).

Dans le recuit simulé , vous effectuez un mouvement. Si cela conduit à une meilleure solution, vous gardez toujours la meilleure solution. Si cela conduit à une pire solution, vous acceptez cette pire solution avec une certaine probabilité. Il y a d'autres détails, comme la façon dont vous acceptez la pire solution (que vous pouvez trouver dans le livre de Russell et Norvig), mais cela devrait déjà clarifier que SA est différent de SHC: SA peut accepter les pires solutions afin d'échapper aux minima locaux, tandis que SHC n'accepte que les mouvements en montée.