Seul un état but est recherche, le chemin y menant n'a pas d'importance. Le principe consiste à modifier l'état courant en l'améliorant au fur et à mesure.
Le problème ainsi que le modèle-monde change de nature. Puisque le chemin ne nous intéresse plus, la notion de graphe et d'arcs perd son sense et on le remplace par des coordonnées et une notion plus générale de voisinage.
On conçois un espace de points `x` dans lequel il y a un champ potentiel scalaire `f(x)`. L'espace est simplement munie d'une notion de voisinage discret c'est à dire qu'à chaque point `x` de l'espace il existe un nombre fini de points `x_1,x_2,x_3,...x_d` dits voisins du point `x`. La relation de voisinage est par principe une relation symétrique, si `x` est un voisinage de `y` alors `y` est un voisinnage de `x`. Aucune hypothèse n'est faite sur la nature des points `x, y,... `
Liste des points voisins du point `x` Potentiel au point `x`.
Le modèle monde étant en place, on définit ce qu'est un problème. La recherche d'un potentiel maximum en partant d'un point initial `S`.
On se déplace toujours vers le point le plus haut de notre voisinage.
On s'arrète lorsque auncun point de notre voisinage n'est strictement supérieur.
ESCALADE(problème) :| Initialiser l'état courant à l'état initial. Répéter indéfiniment :
|
« retourner `x` » signifie terminer la fonction en retournant la valeur `x`.
Déplacement lattéraux : On autorise des mouvements latéraux c'est à dire à valeur constante, mais seulement un nombre de fois consécutifs (par exemple 100 fois) pour éviter les boucles sans fin.
Escalade stochastique : On choisi au hasard un voisin de valeur strictement supérieure.
Escalade du premier choix : Générer des successeurs au hasard jusqu'à que l'un d'eux soit meilleur que l'état courant.
Escalade avec reprise aléatoire : Lors d'un blocage, recommencer l'escalade à partir d'un autre état initiale choisi au hasard.
Choisir au hasard un voisin, si celui-ci amméliore la situation alors il est accepté. Sinon il est accepté seulement avec une probabilité
`p=e^((DeltaE)/T)`
Où `DeltaE` est négatif et désigne la baisse de l'évaluation `f(X')-f(X)`. Le parmètre `T` est la température. Elle est élevé au début, puis diminue et finit par tendre vers zéro.
On fait évoluer `T` selon une fonction `T"=Shema"(t)` où le paramètre `t` est incrémenté à chaque itération et qui fini par être égal à zéro.
RECUIT-SIMULE(problème, `"Shema"`) :| Initialiser l'état courant `e` à l'état initial. Pour `t":="1` jusqu'à `oo` faire :
|
Exploration locale en faisceau : On mémorise `k` états courant au lieu d'un seul. On commence par `k` états au hasard. A chaque étape, tous les successeurs des `k` états sont générés. si l'un deux est un but l'algorithme s'arrête. Sinon elle selectionne les `k` meilleurs successeurs parmi la liste complète.
Exploration locale en faisceau stochastique : Sinon elle choisit les `k` successeurs au hasard parmi la liste complète selon une probabilité proportionnelle à la valeur du successeur.
On crée une population de n individu caractérisé par un chromozone, une chaine de caractères, qui joue le role de paramètres pour une fonction d'aptitude.
On choisie aléatoirement `2` parents, chaque parent étant sélectionné avec une probabilité proportionnelle à son adaptabillité.
Le couple d'individu crée un enfant (ou deux enfants) par croisement, en composant une portion du chromozone d'un parent avec une portion complémentaire de l'autre paren, selon un point au hasard.
On lui applique une mutation avec une faible probabilité.
On ajoute cet enfant (ou les deux enfants) dans la nouvelle population.
On arrête quand on à `n` individus. On remplace l'ancienne génération par la nouvelle génération.
`"GENETIQUE"(`P`, `"Aptitude"`)` :Répéter :
|
`"taille"(P)` : Retourne la taille de la population `P`.
`x:="Selection-au-hasard"(P,"Aptitude")` : Choix aux hasard d'un individu `x` dans la population `P` selon une probabilité proportionnelle à une valeur d'aptitude `"Aptitude"(x)`.
`e := "Reproduction"(x,y)` : Crée un individu `e` en combinant une première partie d'une copie du chromozone `x` avec la seconde partie d'une copie du chromozone `y`, le lieu de coupure entre les deux parties étant choisi au hasard.
`"hasard"()"` : Retourne un nombre réel au hasard compris entre `0` et `1` selon une loi équiprobable.
`e:="Mutation"(e)` : Effectue une mutation sur l'individu `e`.
`epsilon` : Probabilité qu'un individu à sa naissance subisse une mutation.
Description du problème :
Un état est une assignation de valeur pour toutes les variables.
L'état initial : Assignation au hasard qui en générale ne respecte pas les contraintes.
Un état but : Assignation cohérente c-à-d satisfaisant les contraintes.
La fonction successeur change la valeur d'une variable à la fois. A chaque itération, on choisit une variable au hasard parmi celles en conflit (qui viole au moins une contrainte). Parmi toutes les valeurs possibles pour cette variables, on choisie celle qui minimise le nombre de conflits (Heuristique min-conflits).
`"GENETIQUE"(`P`, `"Aptitude"`)` :
Répéter :
|