tp3 Mancer
tp3 Mancer
tp3 Mancer
tp n: 3
Le but du TP :
Le but de ce TP est de réaliser des programmes en Matlab permettant
de traiter et de bien comprendre les points suivants :
1-Se familiariser avec l’algorithme génétique Gatool-ToolBox intégré
sous l’environnement Matlab.
2-Realiser des fonctions spécifiques.
3-Comprendre le principe d’optimisation base sur ToolBox.
4-Optimiser des fonctions mathématiques.
5-Application sur des problèmes lies à la planification des réseaux
électriques et en particulier le dispatching économique.
Introduction :
Les algorithmes génétiques (AG) appartiennent à la famille des
algorithmes évolutionnistes développés par J. Holland présentent des
qualités intéressantes pour la résolution de problèmes d’optimisation
complexes.
Leurs fondements théoriques furent exposés par Goldberg (Goldberg,
1994). Ils tentent de simuler le processus d’évolution des espèces dans
leur milieu naturel : soit une transposition artificielle de concepts
basiques de la génétique et des lois de survie énoncés par Darwin.et
aussi de la théorie de décision du mathématicien Hadamard du siècle
passé.
Rappelons que la génétique représente un individu par un code, c’est-
à-dire un ensemble de données (appelées chromosomes), identifiant
complètement l’individu.
La reproduction est dans ce domaine un mixage aléatoire de
chromosomes de deux individus, donnant naissance à des individus
enfants ayant une empreinte génétique nouvelle, héritée des parents.
La mutation génétique est caractérisée dans le code génétique de
l’enfant par l’apparition d’un chromosome nouveau, inexistant chez les
individus parents.
Ce phénomène génétique d’apparition de " mutants" est rare mais
permet d’expliquer les changements dans la morphologie des espèces,
toujours dans le sens d’une meilleure adaptation au milieu naturel. La
disparition de certaines espèces est expliquée par " les lois de survie "
selon lesquelles seuls les individus les mieux adaptés auront une
longévité suffisante pour générer une descendance. Les individus peu
adaptés auront une tendance à disparaître.
C’est une sélection naturelle qui conduit de génération en génération à
une population composée d’individus de plus en plus adaptés.
Un algorithme génétique est construit de manière tout à fait analogue.
Dans l’ensemble des solutions d’un problème d’optimisation, une
population de taille est constituée de solutions (les individus de la
population) convenablement marquées par un codage qui les identifie
complètement. Une procédure d’évaluation est nécessaire à la
détermination de la force de chaque individu de la population.
Viennent ensuite une phase de sélection (en sélectionnant les
individus suivant de leur force) et une phase de recombinaison
(opérateurs artificiels de croisement et de mutation) qui génèrent une
nouvelle population d’individus, qui ont de bonnes chances d’être plus
forts que ceux de la génération précédente.
De génération en génération, la force des individus de la population
augmente et après un certain nombre d’itérations, la population est
entièrement constituée d’individus tous forts, soit de solutions quasi-
optimales du problème posé.
Applications :
Les algorithmes génétiques sont déjà très utilisés et très répandus,
dans des domaines très différents. On a des exemples en économie
pour faire des modèles de prévisions, on en trouve dans l'analyse
d'image (recherche de motifs, etc.) mais aussi dans le développement
(tests unitaires automatisés, les algorithmes permettent de vérifier
l'efficacité et convergent vers les points sensibles).
A l'avenir, bien que ce soit déjà le cas, c'est dans le développement de
l'intelligence artificielle que les algorithmes génétiques trouvent toute
leur utilité et leur puissance. Cela est utilisé dans les robots intelligent
(envoyés sur mars, chien-robot célèbre, etc.) mais également dans les
jeux vidéo où il faut faire évoluer des personnages sans joueur par
exemple.
Le programme réalisé :
function [C]=dispatch (pg)
%Ng c b a Pmin Pmax
cout=[1 0.00375 2 0 50 200
2 0.0175 1.75 0 20 80
5 0.0625 1 0 15 50
8 0.00834 3.25 0 10 35
11 0.025 3 0 10 30
13 0.025 3 0 12 40]
pd=283.4
C=sum(cout(:,4)+cout(:,3).*pg'+cout(:,2).*pg'.^2)
Résultats :
1- Commande Windows : c = 285.8715
2- Toolbox (Genetic Algorithm) :
Exmpel :
Programme :
function[c]=ali(pg)
cout=[1 0.008 2 25 10 60;
2 0.003 1.8 60 20 110;
3 0.0012 2.1 100 30 180;
4 0.0010 2 120 40 250;
5 0.0015 1.8 40 50 300];
pd=410;
c=sum(cout(:,4)+cout(:,3).*pg'+cout(:,2).*pg'.^2+1000.*(abs(sum(pg')-
pd)));
Conclusion :
Le but des algorithmes génétiques est d'obtenir une solution
approchée à un problème d'optimisation, lorsqu'il n'existe
pas de méthode exacte (ou que la solution est inconnue) pour
le résoudre en un temps raisonnable. Les algorithmes
génétiques utilisent la notion de sélection naturelle et
l'appliquent à une population de solutions potentielles au
problème donné.