Quand choisir l'escalade stochastique plutôt que l'escalade la plus raide?

Stochastique Climbing Hill est généralement moins performant que Steepest Climbing Hill , mais ce sont les cas où les meilleurs anciens réalise?

Les algorithmes d'escalade les plus raides fonctionnent bien pour l'optimisation convexe. Cependant, les problèmes du monde réel sont généralement du type optimisation non convexe: il y a plusieurs pics. Dans de tels cas, lorsque cet algorithme démarre avec une solution aléatoire, la probabilité qu'il atteigne l'un des pics locaux, au lieu du pic global, est élevée. Des améliorations telles que le recuit simulé améliorent ce problème en permettant à l'algorithme de s'éloigner d'un pic local, augmentant ainsi la probabilité qu'il trouve le pic global.

Évidemment, pour un problème simple avec un seul pic, l'escalade la plus raide est toujours meilleure. Il peut également utiliser un arrêt précoce si un pic global est trouvé. En comparaison, un algorithme de recuit simulé sauterait réellement d'un pic global, reviendrait en arrière et repartirait encore. Cela se répéterait jusqu'à ce qu'il soit suffisamment refroidi ou qu'un certain nombre prédéfini d'itérations soit terminé.

Les problèmes du monde réel traitent de données bruyantes et manquantes. Une approche stochastique d'escalade de colline, bien que plus lente, est plus robuste à ces problèmes, et la routine d'optimisation a une plus grande probabilité d'atteindre le pic mondial par rapport à l'algorithme d'escalade de colline le plus raide.

Épilogue: C'est une bonne question qui soulève une question persistante lors de la conception d'une solution ou du choix entre différents algorithmes: le compromis coût-performance-calcul. Comme vous vous en doutez, la réponse est toujours: cela dépend des priorités de votre algorithme. S'il fait partie d'un système d'apprentissage en ligne qui fonctionne sur un lot de données, il y a alors une contrainte de temps forte, mais une contrainte de performance faible (les prochains lots de données corrigeront le biais erroné introduit par le premier lot de données). D'un autre côté, s'il s'agit d'une tâche d'apprentissage hors ligne avec toutes les données disponibles en main, la performance est la principale contrainte et les approches stochastiques sont recommandées.

Commençons par quelques définitions en premier.
L'escalade est un algorithme de recherche qui exécute simplement une boucle et se déplace continuellement dans le sens d'une augmentation de la valeur, c'est-à-dire en montée. La boucle se termine lorsqu'elle atteint un pic et qu'aucun voisin n'a une valeur plus élevée.

L'escalade stochastique , une variante de l'escalade, choisit un hasard parmi les mouvements en montée. La probabilité de sélection peut varier en fonction de la pente du mouvement en montée. Deux méthodes bien connues sont les suivantes:
Escalade de premier choix: génère des successeurs de manière aléatoire jusqu'à ce qu'une génération soit meilleure que l'état actuel. * Considéré comme bon si l'État a de nombreux successeurs (comme des milliers ou des millions).
Escalade à redémarrage aléatoire:Fonctionne sur la philosophie "Si vous ne réussissez pas, essayez, essayez à nouveau".

Passons maintenant à votre réponse. L'escalade stochastique peut en fait donner de meilleurs résultats dans de nombreux cas . Considérez le cas suivant. L'image montre le paysage de l'espace d'état. L'exemple présent dans l'image est tiré du livre, Intelligence artificielle: une approche moderne .

Supposons que vous vous trouviez au point indiqué par l'état actuel. Si vous implémentez un algorithme simple d'escalade, vous atteindrez le maximum local et l'algorithme se terminera. Même s'il existe un état avec une valeur de fonction objective plus optimale mais, l'algorithme ne parvient pas à y arriver car il est resté bloqué à un maximum local. L'algorithme peut également rester bloqué sur des maxima locaux plats .
Le redémarrage aléatoire de l'escalade effectue une série de recherches d'escalade à partir d'états initiaux générés aléatoirement jusqu'à ce qu'un état de but soit trouvé.

Le succès de l'escalade dépend de la forme du paysage de l'espace étatique. Dans le cas où il n'y a que quelques maxima locaux, des plateaux plats; la montée en côte à redémarrage aléatoire trouvera très rapidement une bonne solution. La plupart des problèmes de la vie réelle ont un paysage d'espace d'état très rugueux, ce qui les rend inadaptés à l'utilisation de l'algorithme d'escalade ou de l'une de ses variantes.

REMARQUE: l' algorithme Hill Climb peut également être utilisé pour trouver la valeur minimale , et pas seulement les valeurs maximales. J'ai utilisé le terme maximum dans ma réponse. Si vous recherchez des valeurs minimales, tout sera inversé, y compris le graphique.

Je suis également nouveau dans ces concepts, mais d'après ce que j'ai compris, l'escalade stochastique fonctionnerait mieux dans les cas où le temps de calcul est précieux (comprend le calcul de la fonction de fitness) mais il n'est pas vraiment nécessaire d'atteindre le meilleur solution possible. Atteindre même un optimum local serait acceptable. Les robots opérant dans un essaim seraient un exemple où cela pourrait être utilisé.

La seule différence que je vois dans l'escalade la plus raide est le fait qu'il recherche non seulement les nœuds voisins mais aussi les successeurs des voisins, un peu comme la façon dont un algorithme d'échecs recherche de nombreux autres mouvements avant de sélectionner le meilleur mouvement.

$S$$S$