Universit Cadi Ayyad Dpartement de Mathmatique

Laboratoire LAMAI

ALGORITHME GENETIQUE

Devoir I

F. IAFCS

Une entreprise spcialise dans la fabrication dune marque de tlphone

portable. Son produit final est lassemblage des lments qui sont fabriqus

respectivement dans 9 sites diffrents numrots 1,2,,9.

Vu la crise conomique mondiale, cette entreprise veut engager une politique de

rduction de ces dpenses, elle pense donc reprer les sites les mois

importants afin de les rduire ou bien de les fermer. Vu la complexit des liens

entre ces sites, lentreprise pense donc dfinir les sites importants:

Ainsi on crit j ! i si le site j pointe vers le site i (le produit doit passer par le

site i pour tre trait dans le site j. Ainsi chaque site j met un certains nombre

Lj de liens vers des sites voisines . Le graphe prcdent, par exemple, scrit

comme suit:

1!23456 ; 2!3 ; 3!14 ; 4!15 ; 5!12 ; 6!789 ; 7!81 ; 8!6 ; 9!8

Elle a dcid dassocier chaque site i = 1,2,,14 une mesure dimportance m(i)

(avec la convention que plus m(i) est grand, plus le site i est important ).

Le principe adopt par cette entreprise : un site i est important si beaucoup

de sites importants pointent vers i :

1( ) ( ) ( )

j i

IMP m i m jLj

Plus explicitement, pour tout couple dindices i, j 2 f19g, on dfinit aij par

1 si

0 sinon

j iLjaij

On obtient ainsi une matrice A = (aij) et notre solution du systme (IMP) est :

9

1

(1)

(2)

.Trouver m qui ralise le minimum de la fonction ( ) * , * - , *

.

.

(9)

= ( ) * ( ) ( on le calcul par exemple sous matlab par sum(X.*Y))k

k

m

m

f m A m A m m A m

m

o X k Y k

Nous proposons daider cette entreprise prendre la bonne dcision pour cela on

doit trouver les sites importants et les sites moins importants.

Pour cela nous proposons que la rsolution se fasse par Algorithme Gntique.

1) Donner la matrice A.

2) Ecrire un script randpop qui permet de gnrer alatoirement une population de N=1000 individus.

(un individu est une permutation de [1,2,..,9]).

3) Ecrire un script selection qui permet de raliser la slection par roue de la fortune.

4) Ecrire un script croisement qui permet de raliser le croisement par hybridation des individus de la population alatoirement avec une probabilit

pc=0.7.

5) Ecrire un script mutation qui permet de raliser la mutation flip des individus de la population par permutation de deux chromosomes dont les places sont tirs

au hasard et avec une probabilit pm= 0.01.

6) Ecrire un script Newpop qui permet de garder llite de chaque population de gnration en gnration.

7) Ecrire un script f qui permet de calculer le cot de chaque individu. 8) Ecrire un script fitnesse qui permet de calculer le score de chaque population.

9) Ecrire un script AG_importance qui est le programme principale qui permet la rsolution de notre problme aprs un nombre de gnration nbrgn= 50.