LOGISPLAN est développé en utilisant des techniques d'optimisation basée sur des algorithmes génétiques.
L'application de l'optimisation des algorithmes génétiques, permettent de résoudre des problèmes comme la NP-complets, ces problèmes nécessitent un temps pratiquement infini d'être résolu et, par les techniques utilisées par Evolution Algorithms, peut être résolu en quelques minutes.
Caractéristiques:
Un algorithme est une série organisée d'étapes qui décrit le processus à suivre pour résoudre un problème spécifique.
Les algorithmes génétiques ont plusieurs caractéristiques qui les rendent particulièrement adapté pour résoudre des problèmes complexes.
- Les algorithmes génétiques sont appelées ainsi parce qu'elles sont inspirées par l'évolution biologique et génétique moléculaire de base.
- Ces algorithmes ne évoluer une population d'individus soumis à des mesures aléatoires similaires à ceux qui opèrent dans l'évolution biologique (mutation et la recombinaison génétique), ainsi qu'une sélection, selon certains critères, en termes de qui décide de la individus les plus forts qui survivent, et qui sont moins en forme sont jetés.
- Les algorithmes génétiques éliminer l'un des plus grands obstacles à la conception classique de programmes, est la nécessité de préciser à l'avance toutes les caractéristiques et les particularités d'un problème et les actions nécessaires pour y remédier.
- En utilisant des algorithmes génétiques peuvent résoudre les problèmes qui sont révélés définition même impossible en ce qui concerne la multiplicité des formes de son potentiel propre.
- Rush résoudre des problèmes complexes avec une structure aussi du potentiel énorme complexité inhérente, de sorte que, comme elle était la complexité de sonde, avec la complexité. Pour utiliser une analogie, serait de prendre une grille de capteurs sur un paysage de vallées et sommets (fonction d'évaluation minimale et maximale), plutôt que de procéder à des mesures séquentielles à certains critères, qui est ce qu'ils font habituellement des algorithmes spécifiques classiques.
- Tous les processus évolutif employé par la nature est un processus qui fonctionne avec un haut degré de parallélisme:. Tous les individus dans une population contemporaine sont soumis à la fois la fonction d'évaluation de l'environnement (environnement, prédateurs, etc) et survivre, se reproduire et mourir, sans ingérence dans la simultanéité de ces événements. En utilisant un mécanisme similaire, algorithmes génétiques, mais sont généralement mis en œuvre sur des ordinateurs dans l'ordre, sont dues à la nature intrinsèque d'un design bien adapté pour fonctionner dans le traitement parallèle. Avec le développement qui sera sans aucun doute dans les futurs systèmes avec plusieurs processeurs, ces algorithmes sont bien adaptées pour le déploiement de tels systèmes, avec des bénéfices conséquente des performances.
- De nombreux algorithmes sont conçus pour le cas où les coefficients impliqués dans le problème sera corrigé. Par exemple, si le problème d'affectation, qui tente de faire correspondre ces gens emplois ajuster leurs profils respectifs, l'algorithme hongrois (méthode classique utilisée pour sa solution) est la constance des coefficients. Cela signifie que si les valeurs utilisées pour le calcul et le changement des conditions environnementales durant le processus, la méthode doit être arrêté et redémarré à nouveau. Les algorithmes génétiques, cependant, de réorienter ses propres intrinsèques automatiquement la cible de nouvelles et de poursuivre le processus de convergence vers l'optimum dicté par les nouvelles conditions. Nous pouvons donc dire que les algorithmes génétiques sont capables de converger vers des solutions optimales, même lorsque les coefficients varient en raison de la disposition des missions. Dans le problème d'affectation, la méthode hongroise ne permet pas de considérer le cas où le coefficient d'une personne change en fonction de la position occupée par un autre, comme quand une personne est affectée à un poste dans la même section travail conjoint, par exemple, l'algorithme génétique s'adapte aussi bien aux circonstances du problème.
- Les algorithmes génétiques dans les années 70 est venu de la main de John Henry Holland et David Goldberg et depuis lors, son application dans la résolution des problèmes de recherche et d'optimisation a été fortement contrastées. .
Fonctionnement:
Un algorithme génétique peut avoir plusieurs variantes, selon la façon dont ils appliquent les opérateurs génétiques (croisement, mutation) de la façon dont ils choisissent et comment décider le remplacement des individus de former la nouvelle population.
Un schéma de fonctionnement de base est résumée dans les étapes suivantes:
- Initialisation: générés aléatoirement population initiale, qui consiste en un ensemble de chromosomes qui constituent des solutions possibles au problème. Ne pas le faire au hasard, il est important de s'assurer que dans la population initiale, il a la diversité structurelle de ces solutions ont une représentation de la majorité de la population ou au moins possible pour éviter convergence prématurée.
- Évaluation: Pour chacun des chromosomes de cette population va appliquer la fonction de remise en forme afin de déterminer comment «bien» est la solution qui est codé.
- Statut d'achèvement: L'algorithme génétique doit s'arrêter lorsque vous atteignez la solution optimale, mais cela est généralement inconnu, vous devez donc utiliser d'autres critères de détention. Normalement en utilisant deux critères: l'algorithme génétique exécuter un nombre maximum d'itérations (générations) ou s'arrêter quand aucun changement dans la population. Jusqu'au terme de condition est la suivante:
- Sélection: Après avoir pris connaissance de l'aptitude de chaque chromosome est nécessaire de choisir les chromosomes d'être franchi dans la prochaine génération. Les chromosomes avec une meilleure condition physique sont plus susceptibles d'être sélectionnés.
- Crossover: Le crossover est le principal opérateur génétique, représente la reproduction sexuée, opère sur deux chromosomes à la fois de générer deux descendants, qui combine les caractéristiques des deux parents chromosomes.
- Mutation: changement aléatoire du chromosome de personnes, et peut atteindre les zones de l'espace de recherche qui ne sont pas couverts par les individus de la population actuelle.
- Remplacement: une fois appliqué opérateurs génétiques, les meilleurs individus sont sélectionnés pour former la population de la prochaine génération.
|
