Comment fonctionne la recherche de nouveautés?

16

Dans cet article , l'auteur affirme que guider l'évolution par la seule nouveauté (sans objectifs explicites) peut résoudre les problèmes encore mieux que l'utilisation d'objectifs explicites. En d'autres termes, l'utilisation d'une mesure de nouveauté comme fonction de fitness pour un algorithme génétique fonctionne mieux qu'une fonction de fitness orientée vers un objectif. Comment est-ce possible?

rcpinto
la source

Réponses:

7

Comme expliqué dans une réponse à cette question AI SE , les GA sont des «satisfaisants» plutôt que des «optimiseurs» et ont tendance à ne pas explorer les régions «périphériques» de l'espace de recherche. Au contraire, la population a tendance à se regrouper dans des régions qui sont «assez bonnes» selon la fonction de fitness.

En revanche, je pense que la nouveauté offre une sorte de fitness dynamique, tendant à éloigner la population des zones précédemment découvertes.

NietzscheanAI
la source
6

La recherche de nouveauté sélectionne le «nouveau comportement», selon une définition de nouveauté dépendant du domaine. Par exemple, la nouveauté dans un domaine de résolution de labyrinthe pourrait être «la différence de route explorée». Finalement, les réseaux qui empruntent tous les itinéraires possibles à travers le labyrinthe seront trouvés, et vous pourrez alors sélectionner le plus rapide. Cela fonctionnerait bien mieux qu'un "objectif" naïf, comme la distance au but, ce qui pourrait facilement entraîner un optima local qui ne résout jamais le labyrinthe.

From Abandoning Objectives: Evolution through the Search for Novelty Alone (accent sur le mien):

Dans la recherche de nouveautés, au lieu de mesurer les progrès globaux avec une fonction objectif traditionnelle, l'évolution utilise une mesure de nouveauté comportementale appelée métrique de nouveauté. En effet, une recherche guidée par une telle métrique effectue explicitement ce que fait naturellement l'évolution passive, c'est-à-dire accumulant progressivement de nouvelles formes qui montent dans l'échelle de complexité.
Par exemple, dans un domaine de locomotion bipède, les premières tentatives peuvent simplement échouer. La métrique de nouveauté récompenserait simplement la chute d'une manière différente, qu'elle soit plus proche du comportement objectif ou non. En revanche, une fonction objective peut récompenser explicitement la chute la plus éloignée, ce qui ne conduit probablement pas à l'objectif ultime de la marche et illustre ainsi un optimum local trompeur. En revanche, dans la recherche de nouveauté, un ensemble d'instances sont maintenues qui représentent les découvertes les plus nouvelles. Une recherche plus approfondie saute ensuite de ces comportements représentatifs. Après avoir découvert quelques façons de tomber, la seule façon d'être récompensé est de trouver un comportement qui ne tombe pas tout de suite . De cette façon, la complexité comportementale augmente de bas en haut.Finalement, pour faire quelque chose de nouveau, le bipède devra marcher avec succès sur une certaine distance même si ce n'est pas un objectif .

micimiser
la source