1. Accueil
  2. Python
  3. Sources Python
  4. Sources Math & Algorithmes
  5. Algorithmime genetique : probleme du voyageur de commerce

Algorithmime genetique : probleme du voyageur de commerce

Soyez le premier à donner votre avis sur cette source.

Vue 23 274 fois - Téléchargée 2 242 fois

Télécharger le projet
Commenter

Description

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)
Télécharger le projet

Codes Sources

A voir également

Ajouter un commentaire Commentaires
Signaler

Il y a beaucoup d'erreurs dans le code pour python 3. J'ai apporté quelques corrections, cependant la lembda fonction ne marche pas. Je partage ma correction :)

#!/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 = list(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(key=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 = int(l / 2)
p2 = i2.genes[a:l]
p1 = i1.genes[0:a]
choices =list(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))
Signaler

j'essai d'éxecuter ce code en python 2.7 et je trouve l'erreur suivant:
Traceback (most recent call last):
File "C:\Python25\gen.py", line 111, in <module>
p = population (10,50) # population de 50 individus puis on initialise les distances
File "C:\Python25\gen.py", line 62, in __init__
self.individus.append (individu(nombre_genes))
File "C:\Python25\gen.py", line 7, in __init__
if random == -1 : self.random ()
AttributeError: individu instance has no attribute 'random'on):
NameError: name 'self' is not defined
SVP comment faire pour éliminer cet erreur,
Signaler
Messages postés
336
Date d'inscription
samedi 26 novembre 2005
Statut
Membre
Dernière intervention
8 novembre 2011
 2
Il y a un forum pour ce genre de question.

Dans un premier temps tu parrais utiliser python 2.6, il serait préférable que tu utilises python 3.3, le nom du programme a changé de python à python3.

Et je ne comprends pas vraiment ce que tu veux faire avec ta boucle de shuffle...

Sinon pour créer un matrice en python, il faut utiliser Numpy. Cependant vu ton niveau je ne te conseillerai pas de t'aventurer dans ce genre de librairie, ce que je te conseille c'est de faire une liste de liste.

Pour une matrice 5x4, tu peux créer 5 listes dans une liste :

matrice=[]
for n in range (0,5):
matrice.append([])

Pui la remplire comme tu le veux :

for x in range (0,5):
for y in range (0,4):
matrice[x][y]= "x:%s y:%s"%(x,y)

print (matrice)

Et sérieusement, ta grammaire -.-
Signaler

merci,je suis un débutant en python. et j'essaie de faire un petit prog en python pour résoudre le problème de voyageur de commerce en AG; et comme 1ère étape j'ai généré une population initial dont le nombre d'individu est nb; ce processus ça marche bien , et après je veut également créé une matrice distance pour la remplir par les distances entre chaque de villes mais je ne sais pas exactement une méthode pour le faire SVP aide moi par votre idées. merci
voila mon code py:

#!/usr/bin/python
import random
print ('entrer le nombre de villes:')
n = input()
list= range(n)
print (list)
print('Population initial: choix aleatoir des individus, avec nombre de villes='),n
print ('entrer le nombre d'individus:')
nb = input()
for i in range(nb):
random.shuffle(list)
print('gene'), i
print (list)
Signaler
Messages postés
336
Date d'inscription
samedi 26 novembre 2005
Statut
Membre
Dernière intervention
8 novembre 2011
 2
-___-

Quand tu as copié le code source tu l'as copié avec des esoaces devant toutes les lignes, python te dit donc que l'indentation est mauvaise.

Au pire ajoute "if 1:" à la première ligne pour forcer l'indentation.
Afficher les 11 commentaires
S'inscrire maintenant

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.

Du même auteur (mehdicherti)