Probleme du voyageur de commerce avec 10 villes : consiste à trouver la distance minimale pour passer par toutes les villes sachant les distances entre chaque ville
la resolution est faite en utilisant l'algorithme genetique
Source / Exemple :
#!/usr/bin/env python
# *-* coding: utf8 *-*
import random,sys,os,time
class individu:
def __init__ (self,nombre_genes,random=-1):
self.genes = []
self.nombre_genes = nombre_genes
if random == -1 : self.random ()
"""
random : initialise aleatoirement les genes
"""
def random (self):
self.genes = []
f = range(0,self.nombre_genes)
for v in range(self.nombre_genes):
val = random.choice (f)
f.remove (val)
self.genes.append (val)
"""
evaluation : compare l'individu avec un tableau d'autres individus
retourne le nombre d'individus auquel l'individu self est superieur et de meilleure
qualité
"""
def evalutation (self,autres_individus,distances):
valeur_individu = 0
for v in autres_individus:
if self.compare(v,distances) > 0 : valeur_individu = valeur_individu + 1
self.valeur_individu = valeur_individu
return valeur_individu
"""
compare : compare l'individu self avec un autre individu
retourne un nombre positif s'il est superieur
un nombre negatif s'il est inferieur
le nombre 0 s'il est égal
"""
def calcul_distance (self,distance):
a = self.genes[0]
dist = 0
for b in self.genes[1:]:
min=0
max=0
if a > b :
min = b
max = a
else :
min = a
max = b
dist = dist + (distance[min])[max-min-1]
a = b
self.distance = dist
return dist
def compare (self,individu,distance):
individu.calcul_distance (distance)
self.calcul_distance (distance)
return self.distance - individu.distance
class population:
def __init__ (self,nombre_genes,nombre_initial_population=50):
self.nombre_genes = nombre_genes
self.distances = [[]] * nombre_genes
self.individus = []
self.nombre_initial_population = nombre_initial_population
for v in range(self.nombre_initial_population):
self.individus.append (individu(nombre_genes))
"""
selection : methode de selection des meilleurs N individus
"""
def selection (self , N=-1):
if N == -1 : N = len(self.individus)
for v in self.individus:
v.evalutation (self.individus,self.distances)
self.individus.sort (lambda a,b : a.valeur_individu - b.valeur_individu)
if N <= len(self.individus) : self.individus = self.individus[0:N]
"""
croisement : selectionne deux individus et croise leur gênes pour en creer de nouveaux
"""
def croisement_deux (self , i1 , i2):
i = individu (self.nombre_genes)
l = len(i1.genes)
a = l / 2
p2 = i2.genes[a:l]
p1 = i1.genes[0:a]
choices = range(0,l)
for v in p1:
try:choices.remove (v)
except : pass
for v in p2:
try : choices.remove (v)
except : pass
idc = 0
for id in range(len(p2)):
if p2[id] in p1:
p2[id] = choices[idc]
idc = idc + 1
i.genes = p1 + p2
return i
""" croise tous les individus entre eux"""
def croisement_all (self):
new = []
for v1 in range(len(self.individus)):
for v2 in range(v1,len(self.individus)):
new.append ( self.croisement_deux (self.individus[v1] , self.individus[v2]))
self.individus = self.individus + new
""" croise nombre_croisement individus aleatoires entre eux """
def croisement_nombre (self , nombre_croisement):
new = []
for r in range(nombre_croisement):
v1 = random.randint (0 , len(self.individus)-1)
v2 = random.randint (0 , len(self.individus)-1)
new.append (self.croisement_deux (self.individus[v1] , self.individus[v2]) )
self.individus = self.individus + new
if __name__ == "__main__" :
""" population de 50 individus"""
p = population (10,50)
""" initialise les distances """
p.distances[0] = [2,3,4,5,6,7,8,9,10 ] # distance de la premiere ville avec la 2eme , 3eme , ... , 10eme
p.distances[1] = [11,12,13,14,15,16,17,18 ] # distance de la deuxieme ville avec la 3eme , 4eme , ... ,10eme
p.distances[2] = [19,20,21,22,23,24,25] #etc...
p.distances[3] = [26,27,28,29,30,31]
p.distances[4] = [32,33,34,35,36]
p.distances[5] = [37,38,39 ,40]
p.distances[6] = [41,42,43]
p.distances[7] = [44,45]
p.distances[8] = [46] # distance de la 9eme ville avec la 10eme ville
"""
10 generations
a chaque fois fait 100 croisements
et selectionne les 10 premiers
"""
for i in range(10):
p.croisement_nombre (100)
p.selection (10)
for v in p.individus:
print v.genes,v.calcul_distance (p.distances)
Vous n'êtes pas encore membre ?
inscrivez-vous, c'est gratuit et ça prend moins d'une minute !
Les membres obtiennent plus de réponses que les utilisateurs anonymes.
Le fait d'être membre vous permet d'avoir un suivi détaillé de vos demandes et codes sources.
Le fait d'être membre vous permet d'avoir des options supplémentaires.