Quelles sont les différences entre le recuit simulé et les algorithmes génétiques?

Bien strictement parlant, ces deux choses - recuit simulé (SA) et algorithmes génétiques ne sont ni des algorithmes, ni leur but data mining".

Les deux sont méta-heuristiques - un couple de niveaux au-dessus de "algorithme" sur l'échelle d'abstraction. En d'autres termes, les deux termes renvoient à haut niveau de métaphores--l'un emprunté à partir de la métallurgie et de l'autre de la biologie évolutive. Dans la méta-heuristique de la taxonomie, SA est une seul état de la méthode et GA est un de la population de la méthode (dans une sous-classe avec PSO, l'ACO, et al, généralement dénommé biologiquement inspiré des méta-heuristiques).

Ces deux méta-heuristiques sont utilisées pour résoudre des problèmes d'optimisation, en particulier (mais pas exclusivement) dans optimisation combinatoire (aka de la contrainte de la satisfaction de la programmation). Optimisation combinatoire se réfère à l'optimisation en sélectionnant parmi un ensemble d'éléments discrets--en d'autres termes, il n'y a aucune fonction à minimiser. Le problème de sac-à-dos, problème du voyageur de commerce, la coupe du stock de problème--sont tous les problèmes d'optimisation combinatoire.

La connexion à l'exploration de données est le cœur de beaucoup (la plupart?) supervisé l'Apprentissage de la Machine (ML) des algorithmes est la solution d'un problème d'optimisation--(Multi-Layer Perceptron et les Machines à Vecteurs de Support, par exemple).

Toute solution technique pour résoudre cap problèmes, indépendamment de l'algorithme, consistera pour l'essentiel de ces mesures (qui sont généralement codé comme un seul bloc à l'intérieur d'une boucle récursive):

1. coder le domaine des détails spécifiques
   dans une fonction de coût (c'est le
   pas-sage de la minimisation de la valeur
   retourné à partir de cette fonction que
   constitue une "solution" à la c/o
   problème);

2. évaluer la fonction de coût de passage
   dans une première série de "deviner" (pour commencer
   itération);

3. basée sur la valeur retournée par la
   la fonction de coût, de générer une ultérieure
   candidat de la solution (ou de plus de
   l'un, en fonction de la
   méta-heuristiques) pour le coût
   fonction;

4. évaluer chaque solution proposée par
   en passant dans un argument,
   la fonction de coût;

5. répétez les étapes (iii) et (iv) jusqu'à ce
   un critère de convergence est
   satisfait ou un nombre maximal de
   itérations est atteint.

Méta-heuristiques sont dirigés à l'étape (iii) ci-dessus; par conséquent, SA et GA diffèrent dans leur façon de générer des solutions pour évaluation par la fonction de coût. En d'autres termes, c'est l'endroit à regarder pour comprendre comment ces deux méta-heuristiques diffèrent.

De manière informelle, l'essence même d'un algorithme dirigé vers la solution d'optimisation combinatoire est la façon dont il traite d'un candidat à la solution dont la valeur renvoyée par la fonction de coût est pire que l'actuel meilleur candidat de la solution (la seule qui retourne la plus petite valeur de la fonction de coût). La façon la plus simple pour un algorithme d'optimisation pour gérer un tel candidat solution est à rejeter d'emblée--c'est ce que l'escalade la colline algorithme. Mais en faisant cela, simple d'escalade la colline manqueront toujours une meilleure solution séparée de la solution actuelle par une colline. Mettre une autre manière, un système sophistiqué algorithme d'optimisation doit inclure une technique pour (temporairement) l'acceptation d'un candidat à la solution de pire que d' (c'est à dire, en amont de) la meilleure solution actuelle, car une solution encore meilleure que l'actuelle, on peut se situent le long d'un chemin à travers que la pire solution.

---

Alors, comment faire SA et GA générer des solutions?

L'essence de SA est généralement exprimée en termes de probabilité que les coûts sont plus élevés candidats solution sera acceptée (l'ensemble de l'expression à l'intérieur de la double parenthèse est un exposant:

p = e((-highCost - lowCost)/temperature)

Ou en python:

p = pow(math.e, (-hiCost - loCost) /T)

La 'température' terme est une variable dont la valeur se désintègre pendant le déroulement de l'optimisation--et par conséquent, la probabilité que SA va accepter une aggravation de la solution diminue à mesure que nombre d'itérations augmente.

Dans l'autre sens, lorsque l'algorithme commence itération, T est très grand, comme vous pouvez le voir, les causes de l'algorithme de déplacer à chaque nouvellement créé candidat de la solution, que ce soit mieux ou pire que la meilleure solution actuelle--c'est à dire, il est en train de faire un marche aléatoire dans l'espace de solution. Comme le nombre d'itérations augmente (c'est à dire, dès que la température se refroidit) l'algorithme de recherche de la solution de l'espace devient moins permissif, jusqu'à T = 0, le comportement est identique à celui d'un simple escalade de l'algorithme (c'est à dire, que des solutions mieux que la meilleure solution actuelle sont acceptés).

Algorithmes génétiques sont très différentes. Pour une chose, et c'est une grande chose, il génère pas un candidat unique solution, mais d'un ensemble de "population". Il fonctionne comme ceci: GA appelle la fonction de coût sur chaque membre (candidat de la solution) de la population. Puis, il les classe, du meilleur au pire, commandé par la valeur renvoyée par la fonction de coût ('mieux' a la valeur la plus faible). À partir de ces classé valeurs (et leurs solutions) la population suivante est créée. Les nouveaux membres de la population sont créés essentiellement dans l'une des trois façons. Le premier est généralement dénommé "l'élitisme" et, dans la pratique, se réfère généralement à la mieux classée parmi les candidats des solutions et de les transmettre directement par le biais de--non modifié--à la prochaine génération. Les deux autres moyens que les nouveaux membres de la population sont généralement qualifiés de "mutation" et de "crossover'. La Mutation implique généralement un changement d'un élément dans une solution proposée vecteur de la population actuelle pour créer une solution de vecteur dans la nouvelle population, par exemple, [4, 5, 1, 0, 2] => [4, 5, 2, 0, 2]. Le résultat de l'opération de croisement est ce qui arriverait si les vecteurs avoir des relations sexuelles--c'est à dire, un enfant nouveau vecteur dont les éléments sont composés de certains de chacun des deux parents.

Donc, ceux qui sont l'algorithmique différences entre GA et SA. Quelles sont les différences de performances?

Dans la pratique: (mes observations sont limitées à des problèmes d'optimisation combinatoire) GA, presque toujours, les battements de SA (retourne un faible "meilleure" valeur de retour de la fonction de coût--c'est à dire, une valeur proche de l'espace des solutions du minimum global), mais à un plus haut de calcul des coûts. Autant que je sache, les manuels et les publications techniques réciter la même conclusion sur la résolution.

mais voici la chose: GA est intrinsèquement parallélisables; ce qui est plus, il est trivial de le faire, parce que la personne "agents" qui composent chaque population n'a pas besoin d'échanger des messages--c'est à dire, ils fonctionnent indépendamment les uns des autres. Évidemment cela signifie que GA calcul peut être distribué, ce qui signifie dans la pratique, vous pouvez obtenir de bien meilleurs résultats (plus proche du minimum global) et de meilleures performances (vitesse d'exécution).

Dans quelles circonstances SA surpasser GA? Le scénario général je pense que ce serait ceux de problèmes d'optimisation avoir un petit espace de solution, de sorte que le résultat de SA et GA sont pratiquement les mêmes, mais le contexte d'exécution (par exemple, des centaines de problèmes similaires à exécuter en mode batch) favorise l'algorithme plus rapide (ce qui devrait toujours être SA).

OriginalL'auteur doug

Je suis loin d'être un expert sur ces algorithmes, mais je vais essayer de vous aider.

Je pense que la plus grande différence entre les deux est l'idée de crossover et GA donc un exemple d'une tâche d'apprentissage qui est le mieux adapté pour GA que SA va dépendre de ce crossover signifie dans cette situation et comment il est mis en œuvre.

L'idée de crossover est que vous pouvez combiner de manière significative deux solutions pour produire un meilleur. Je pense que cela n'a de sens que si les solutions à un problème, ils sont structurés d'une certaine façon. Je ne pouvais imaginer, par exemple, en multi-classe de la classification de la prise de deux (ou plusieurs) des classificateurs bon au classement d'une catégorie donnée et de les combiner en votant pour faire un bien meilleur classifieur. Un autre exemple pourrait être Programmation Génétique, d'où la solution peut être exprimé comme un arbre, mais j'ai du mal à venir avec un bon exemple où l'on pouvait combiner deux programmes afin de créer un meilleur.

Je pense qu'il est difficile de trouver des arguments convaincants pour l'un sur l'autre, parce qu'ils sont tout à fait semblables à des algorithmes, peut-être d'avoir été développé à partir de situations très différentes.

OriginalL'auteur Stompchicken