Algoritmo genético - rotas
Publicado por César tinum da silva (última atualização em 08/12/2009)
[ Hits: 24.005 ]
Homepage: www.google.com
Bom galera, aí vai um algoritmo genético desenvolvido para resolver a heurística do caixeiro viajante utilizando programação paralela.
Qualquer dúvida meu email está no arquivo py. Favor manter a nota de autoria. Tentei comentar o código ao máximo para melhor compreensão posterior.
Para executar, entre no diretório onde se encontra o arquivo py pelo terminal e digite "python AG.py".
############################################################
#ALGORITMO GENETICO DESENVOLVIDO PARA DISCIPLINA INTELIGENCIA ARTIFICIAL #
#OBJETIVO: SOLUCAO EFICIENTE PARA O PROBLEMA DE ROTEAMENTO DE VEICULOS #
#AUTOR: CESAR TINUM ,SABRINE HENRIQUE DATA:06-11-2009 #
#CENTRO UNIVERSITARIO DE BELO HORIZONTE DCE - 7 PERIODO MANHA #
#CONTATO : magodoschatsbh@gmail.com , sabrine@2xt.com.br #
############################################################
#SELECAO #MUTACAO #CROSSOVER
import random #GERACAO NUMEROS ALEATORIOS
from threading import Thread #BIBLIOTECA DE GERACAO DE SUBPROCESSOS (THREADS)
from math import ceil #BIBLIOTECA DE ARREDONDAMENTO NUMERICO
from time import time, strftime
class AG:
def __init__(self, mutacao,crossover,tamPopulacao,fitnes, cidades, maxdistancia, geracoes, numthreads, naoalcanco):
start = time()
self.MAX_DIST = maxdistancia
self.mutacao = mutacao #propriedade de mutacao
self.crossover = crossover
self.NAOALCANCO = naoalcanco #possibilidade de nao haver caminho entre cidades
self.tamPopulacao = tamPopulacao #numero populacao inicial
self.fitnes = fitnes #funcao de avaliacao
self.populacao = [] #vetor contendo a populacao
self.fitPopulacao = [] #vetor com resultado avaliacao de cada elem da populacao
self.distancia = {}
self.NUM_THREADS = numthreads
self.geracoes = geracoes
self. cidades = cidades
self.disCidades(cidades)
self.populacaoInicial = []
self.__initGeracao()
self.selecao()
self.populacaoInicial = self.populacao
for i in range(self.geracoes):
self.__nextGeracao()
self.__crossover()
self.selecao()
finish = time()
self.time = finish - start
self.__header()
#FIM CLASSE INICIALIZACAO
def __initGeracao(self):
try:
threads = []
for i in range(self.NUM_THREADS):
threads.append(self.__startThreads('self.geraPopulacao', {})) #DISPARANDO THREADS PARA GERAR POPULACAO E AVALIACAO DOS ELEMENTOS
self.__endThreads(threads) #ESPERA THREADS ACABAREM
except Exception, e:
print e
def __nextGeracao(self):
try:
threads = []
tamMutacao = round(ceil(float(self.tamPopulacao) / 2)* self.mutacao) #NUMERO DE INDIVIDUOS QUE SOFRERAO MUTACAO
faixa = int(ceil(tamMutacao / self.NUM_THREADS))
r = int((tamMutacao>self.NUM_THREADS and self.NUM_THREADS or tamMutacao)) #VERIFICA SE NUM THREADS E MAIOR QUE NUM ELEMENTOS QUE SOFRERAO MUTACAO
for i in range(r):
threads.append(self.__startThreads('self.geraMutacao', {'ini':i+1, 'tam':faixa})) #DISPARANDO THREADS PARA EFETUAR MUTACAO NOS PIORES ELEMENTOS DA POPULACAO EM FAIXAS
self.__endThreads(threads) #ESPERA THREADS ACABAREM
except Exception, e:
print e
def __endThreads(self, threads):
for t in threads:
t.join(10)
return
def geraMutacao(self,ini, tam):
try:
sorteados = [] #GUARDA ELEMENTOS SORTEADOS PARA QUE O ALGORITMO NAO ENTRE EM LOOP SORTEANDO SEMPRE O MESMO NODO
tamC = self.tamPopulacao
ini = tamC - (2*ini)
flag = True
limite = ini + tam
numCidades = len(self.cidades)
while ini <= limite:
tenhoCidades = True
if flag:
cont = 0
posCorte = random.randint(3, numCidades -1) #PONTO DE CORTE PARA MUTACAO ALEATORIO
n = numCidades-posCorte #NUMERO DE ELEMENTOS QUE SERAO TROCADOS
list = self.populacao[ini][2:posCorte]
del self.populacao[ini][posCorte:] #DELETO O RESTO DO VETOR A PARTIR DO PONTO DE CORTE PARA INSERIR NOVOS ELEMENTOS
sorteados = []
i = 0
j = 0
while tenhoCidades:
flag = False
nodo = self.cidades[random.randint(0, numCidades-1)]
if cont > numCidades - 1:
flag = True
break
if nodo in sorteados or nodo in list:
cont+=1
continue
try:
if self.populacao[ini][posCorte - 1]:
d = (self.adjacencia(nodo, self.populacao[ini][posCorte-1]) and True or None)
else:
d = True
except Exception, e:
d = None
if d:
self.populacao[ini].append(nodo)
list.append(nodo)
res = self.geraFitnes(self.populacao[ini], 2)
self.populacao[ini][0] = res[0]
self.populacao[ini][1] = res[1]
i+=1
tenhoCidades = not self.__sublist(list, self.cidades)
if not flag:
ini+=1
return True
except Exception, e:
return False
def __startThreads(self, funcAlvo, k):
try:
t = Thread(target = eval(funcAlvo), kwargs = k)
t.start()
return t
except Exception, e:
print e
def disCidades(self, cidades): #GERA DISTANCIA ENTRE CIDADES , MATRIZ DE ADJACENCIA
for i in cidades:
self.distancia[i] = {}
for j in cidades:
if not self.distancia[i].has_key(j): #SE J NAO ESTA NO DICIONARIO DA CIDADE I VOU INCLUI-LA
if self.distancia.has_key(j) and j!=i: #SE CIDADE J ESTA NO DICIONARIO (JA TENHO VALOR) E J!=I (NAO E A MESMA CIDADE)
self.distancia[i][j] = self.distancia[j][i]
continue
if i == j:
self.distancia[i][j] = 0
continue
alcanco = random.randint(1, self.NAOALCANCO) #CHANCE DE CIDADES NAO SE ALCANCAREM = 1 EM NAO ALCANCO (PARAMETRO)
if alcanco == 1:
self.distancia[i][j] = 100000 #ATRIBUI VALOR DISTANCIA MUITO ALTO = CIDADE NAO ALCANCAVEL
continue
self.distancia[i][j] = random.randint(1, self.MAX_DIST) #SORTEIA VALOR DA DISTANCIA ALEATORIAMENTE ENTRE 1 - MAX_DIST SE FOR A MESMA CIDADE VALOR DISTANCIA 0
return
def selecao(self): #DIVIDIR A POPULACAO EM GRUPOS PARA APLICAR FUNCAO DE AVALIACAO POR THREADS.
self.populacao.sort()
def geraPopulacao(self):
tam = int(ceil(float(self.tamPopulacao)/4))
try:
for i in range(tam):
d = []
sorteados = []
d.append(self.cidades[random.randint(0, len(self.cidades) - 1)]) #1 CIDADE ALEATORIA
sorteados.append(d[0])
cont = 1
while not self.__sublist(d, self.cidades): #RODA LOOP ENQUANTO NAO TEM TODAS CIDADES NA ROTA - SE IMPASSE ATE 100 ITERACOES - COMECA DE NOVO
b = self.cidades[random.randint(0, len(self.cidades) - 1)]
cont+=1
if cont >len(self.cidades):
cont = 0
d = []
sorteados = []
d.append(self.cidades[random.randint(0, len(self.cidades) - 1)]) #1 CIDADE ALEATORIA
sorteados.append(d[0])
elif b in sorteados:
continue
sorteados.append(b)
c = (self.adjacencia(d[len(d)-1],b) and d.append(b) or False) #VERIFICA SE CIDADES SAO ADJACENTES (EXISTE ROTA ENTRE ELAS)
if len(self.populacao) == self.tamPopulacao: #COMO AS THREADS PODEM SE DIVIDIR EM MAIS ELEMENTOS QUE O TAMANHO ORIGINAL PRAMETRIZADO
return False #DEVIDO AO ARREDONDAMENTO DE VEZES PARA CADA THREAD CRIAR ELEMENTOS
res = self.geraFitnes(d, 0) #VERIFICO AQUI SE TAMANHO TOTAL DE ELEMENTOS JA FOI CRIADO ANTES SE INSERIR CADA ELEMENTO
d.insert(0, res[0])
d.insert(1, res[1])
self.populacao.append(d)
return True
except Exception, e:
print e
def adjacencia(self, a, b):
return ((self.distancia[a][b]<9999 and a!=b or False) and True or False) #SE A DISTANCIA MENOR QUE 9999 AVALIA SE A!=B PARA EVITAR IR E VOLTAR NA MESMA CIDADE
def geraFitnes(self, mat, pos): #AVALIA CADA ROTA POSSIVEL DA POPULACAO
try:
d = []
e = mat[pos:]
mat = mat[pos:]
f = self.cidades
tenhoTodasCidades = ((self.__sublist(mat, f) and True or False) and 1 or 100) #VERIFICA SE ROTA SENDO AVALIADA POSSUI TODAS AS CIDADES
d.extend(self.distancia[mat[i]][mat[i+1]] for i in range(len(mat)))
return [tenhoTodasCidades, sum(d)] #SOMA VALOR DE DISTANCIA ENTRE CIDADES DA ROTA
except Exception, e:
return [tenhoTodasCidades, sum(d)]
def load(self, url):
try:
file = open(url, 'r')
fileLines= file.readlines()
for linha in fileLines:
linha = linha.split(" ")
for indice, distancia in enumerate(linha):
pass
#LE CADA LINHA E ATRIBUI VALOR DE DISTANCIAS
except Exception, e:
print e
def __sublist(self, filho, mae):
try:
contem=[]
contem.extend((item in filho and 1 or 0) for item in mae) #VERIFICA SE ROTA POSSUI TODAS CIDADES
if 0 in contem:
return False
else:
return True
except Exception, e:
print 'Erro na busca de sublista, ', e
def __crossover(self): #IMENDA ROTAS MAIS BEM AVALIADAS EM ROTAS MAL AVALIADAS A PARTIR DE PONTO EM COMUM
try:
tamCrossOver = round(ceil(self.tamPopulacao / 2)* self.crossover) #NUMERO DE INDIVIDUOS QUE SOFRERAO MUTACAO
faixa = int(ceil(tamCrossOver / self.NUM_THREADS))
r = int((tamCrossOver>self.NUM_THREADS and self.NUM_THREADS or tamCrossOver)) #VERIFICA SE NUM THREADS E MAIOR QUE NUM ELEMENTOS QUE SOFRERAO MUTACAO
threads = []
for i in range(r):
threads.append(self.__startThreads('self.geraCrossOver', {'ini':i+1, 'tam':faixa})) #DISPARANDO THREADS PARA EFETUAR MUTACAO NOS PIORES ELEMENTOS DA POPULACAO EM FAIXAS
self.__endThreads(threads)
except Exception, e:
print e
def geraCrossOver(self, ini, tam, nodo=None):
try:
tamC = self.tamPopulacao
ini = tamC - (tam*ini)
flag = True
limite = ini + tam
numCidades = len(self.cidades)
melhorRota = self.populacao[0][2:] #AS CIDADES DA MELHOR ROTA, 2 EM DIANTE POS 0 E 1 SAO AVALIACOES
while ini < limite:
if limite>=self.tamPopulacao:
break
while nodo == None:
posCorte = random.randint(3, len(self.cidades)-1) #PONTO DE CORTE ONDE SERA FEITO A JUNCAO
nodo = (lambda nodo: nodo in melhorRota and nodo or None)(self.populacao[ini][posCorte])
del self.populacao[ini][:2] #RETIRA VALORES AVALIACAO
v = {len(self.populacao[ini][:self.populacao[ini].index(nodo)]):'esq', len(self.populacao[ini][self.populacao[ini].index(nodo):])-1:'dir'} #NUMERO DE ELEMENTOS A DIREITA E ESQUERD DA POSICAO DE CORTE
g = {len(melhorRota[:melhorRota.index(nodo)]):'esq', len(melhorRota[melhorRota.index(nodo):])-1:'dir'} #NUMERO DE ELEMENTOS A DIREITA E ESQUERD DA POSICAO DE CORTE DA MELHOR ROTA
ladoV = max(v.items()) #CRUZAR O LADO QUE TIVER MAIOR NUMERO DE ELEMENTOS [0] = LADO [1] = NUM ELEM
ladoG = max(g.items()) #CRUZAR O LADO QUE TIVER MAIOR NUMERO DE ELEMENTOS [0] = LADO [1] = NUM ELEM
cont=0
c=0
######################################################
#VALIDAR NUM ELEMENTOS EQUIPARANDO AO VETOR BASE ( MELHOR ROTA)
######################################################
if ladoG[0]<ladoV[0]:
ladoV = min(v.items()) #MANTER O LADO DO MELHOR VETOR COMO MAIOR PARA NAO FALTAR INDICE
indiceNodo = self.populacao[ini].index(nodo)
indiceNodoG = melhorRota.index(nodo)
if ladoV[1] == 'esq':
try:
if indiceNodo>0:
del self.populacao[ini][:indiceNodo-1] #DELETA ELEMENTOS A ESQUERDA DO INICIO ATE O INDICE DO VETOR DE JUNCAO
indiceNodo = (indiceNodo > 0 and (indiceNodo - 1))
for indice in range(indiceNodo):
indiceNodoG = (ladoG[1] == 'dir' and (indiceNodoG +1) or (indiceNodoG -1))
self.populacao[ini].insert(indice, melhorRota[indiceNodoG]) #ADICIONANDO ELEMENTOS A DIREITA NO VETOR DE MELHOR ROTA
except Exception, e:
pass
else:
try:
indiceNodo = self.populacao[ini].index(nodo)
if indiceNodo<len(self.populacao[ini])-1:
del self.populacao[ini][indiceNodo+1:] #DELETA ELEMENTOS A ESQUERDA DO INICIO ATE O INDICE DO VETOR DE JUNCAO
indices = []
ind = indiceNodo
id = len(self.cidades) - indiceNodo
while len(indices) < id:
ind+=1
indices.append(ind)
for indice in indices:
indiceNodoG = (ladoG[1] == 'dir' and (indiceNodoG +1) or (indiceNodoG -1))
self.populacao[ini].insert(indice, melhorRota[indiceNodoG]) #ADICIONANDO ELEMENTOS A DIREITA NO VETOR DE MELHOR ROTA
except Exception, e:
pass
############################################
#INSERIR ELEMENTOS PARA QUE ROTA CONTENHA TODAS CIDADES
############################################
list = []
list= self.populacao[ini]
c = 0
try:
while not self.__sublist(self.populacao[ini], self.cidades) and c<50: #TENTO 20 VEZES INSERIR ELEMENTO NA LISTA PARA COMPLETA-LA
cont=0
c+=1
elem = self.cidades[random.randint(0, len(self.cidades)-1)]
while elem in list and cont < 50:
elem = self.cidades[random.randint(0, len(self.cidades)-1)]
cont+=1
if cont < 50:
if self.adjacencia(elem, self.populacao[ini][len(self.populacao[ini])-1]): #VERIFICA ADJACENCIA ENTRE O ELEMENTO E O ULTIMO DO VETOR
self.populacao[ini].append(elem)
break
except Exception, e:
print 'Erro ao completar rota, ', e
res = self.geraFitnes(self.populacao[ini], 0) #VERIFICO AQUI SE TAMANHO TOTAL DE ELEMENTOS JA FOI CRIADO ANTES SE INSERIR CADA ELEMENTO
self.populacao[ini].insert(0, res[0])
self.populacao[ini].insert(1, res[1])
ini+=1
except Exception, e:
pass
def __header(self):
try:
print "**************************************************************************************"
print "* ALGORITMO GENETICO - HEURISTICA DO CAIXEIRO VIAJANTE UNI-BH *"
print "* AUTOR: CESAR T. SILVA, SABRINE HEQUER - cesarts25@gmail.com / sabrinesa@gmail.com*"
print "* DISCIPLINA: INTELIGENCIA ARTIFICIAL PROF: ANA PAULA LADEIRA CCM7 *"
print "**************************************************************************************"
print ""
print " PARAMETROS DE ENTRADA PARA O AG "
print "PROBABILIDADE DE MUTACAO = %f"%self.mutacao
print "PROBABILIDADE DE CRUZAMENTO = %f"%self.crossover
print "PROBABILIDADE DE NAO ALCANCABILIDADE ENTRE CIDADES = 1/%d"%self.NAOALCANCO
print "TAMANHO DA POPULACAO = %d"%self.tamPopulacao
print "CIDADES - ", self.cidades
print "DISTANCIA MAXIMA ENTRE AS CIDADES = %d"%self.MAX_DIST
print "NUMERO DE GERACOES = %d"%self.geracoes
print "NUMERO DE THREADS UTILIZADAS = %d"%self.NUM_THREADS
print ""
print " MATRIZ DE ADJACENCIA "
c = " "
for i in self.cidades:
c += " "+i
print c
for i in self.cidades:
c = []
for j in self.cidades:
c.append(self.distancia[i][j])
print i, c
print ""
print ""
print " RESULTADOS OBTIDOS "
print "MELHOR ROTA - ", self.populacao[0][2:]
print "CUSTO EM KM - ", self.populacao[0][1]
print "TEMPO GASTO PELO ALGORITMO - ", self.time, " segundos."
print ""
pop = raw_input("IMPRIMIR POPULACAO (S/N): ")
if pop.lower() =='s':
print " POPULACAO INICIAL "
for i , j in enumerate(self.populacaoInicial):
print i , '- ', j
if pop.lower() =='s':
print " POPULACAO FINAL "
for i , j in enumerate(self.populacao):
print i , '- ', j
print ""
print " BELO HORIZONTE %s"%(strftime("%d/%m/%Y"))
except Exception, e:
print e
###################
#INSTANCIA CLASSE
####################
if __name__ == "__main__":
try:
print " -- COLETA DE DADOS -- "
ger = input("NUMERO DE GERACOES: ")
pop = input("TAMANHO DA POPULACAO: ")
citys = input("NUMERO DE CIDADES: ")
c = []
c.extend(str(city) for city in range(citys))
print " CALCULANDO ROTA..."
ag = AG(0.3,0.7,pop,'2x+30x2', c, 1200, ger, 4, 50)
except Exception, e:
print e
Scripts recomendados
O maior quebra cabeças de sempre
Implementação simples de um programa antivírus em Python 3.10 para Linux
Como rodar músicas mp3 pelo Python
Comentários
[1] Comentário enviado por FIR3FL4M3 em 08/12/2009 - 13:10h
Meu amigo, esse probleminha é uma dor de cabeça e há algum tempo atrás me deparei com um parecido e lembro que rodei um bocado pra achar um exemplo para me guiar.
Valeu pela disponibilização do codigo e parabens.
Meu amigo, esse probleminha é uma dor de cabeça e há algum tempo atrás me deparei com um parecido e lembro que rodei um bocado pra achar um exemplo para me guiar.
Valeu pela disponibilização do codigo e parabens.
[2] Comentário enviado por mago_dos_chats em 08/12/2009 - 16:18h
vlw, somente um ajudando o outro que cresceremos.... abraço
vlw, somente um ajudando o outro que cresceremos.... abraço
[3] Comentário enviado por albfneto em 08/12/2009 - 23:11h
Bonito código! Um amigo meu é especialista em algoritmos genéticos, ele é matemático.
Bonito código! Um amigo meu é especialista em algoritmos genéticos, ele é matemático.
[4] Comentário enviado por mago_dos_chats em 09/12/2009 - 14:38h
vlw albfneto, o codigo ta disponivel ai pra quem quiser usar, so manter a autoria ne.. =)
vlw albfneto, o codigo ta disponivel ai pra quem quiser usar, so manter a autoria ne.. =)
Patrocínio
Site hospedado pelo provedor RedeHost.
Destaques
Artigos
Porque Gentoo semi-binário atualmente (desabafo)
A combinação de WMs com compositores feitos por fora
Audacious, VLC e QMMP - que saudades do XMMS
SUNO OpenSource: Crie um servidor de gerador de música com IA
Dicas
Como configurar cores no prompt do Bash para usuário e root no Arch Linux
Tópicos
Alguns aplificativos em Flatpak não rodam no Debian (0)
Cursor do mouse parou [RESOLVIDO] (9)
Top 10 do mês
-
Xerxes
1° lugar - 132.540 pts -
Fábio Berbert de Paula
2° lugar - 63.522 pts -
Buckminster
3° lugar - 39.659 pts -
Alberto Federman Neto.
4° lugar - 30.008 pts -
Alessandro de Oliveira Faria (A.K.A. CABELO)
5° lugar - 20.909 pts -
Daniel Lara Souza
6° lugar - 20.521 pts -
edps
7° lugar - 19.984 pts -
Mauricio Ferrari (LinuxProativo)
8° lugar - 19.646 pts -
Sidnei Serra
9° lugar - 17.417 pts -
Andre (pinduvoz)
10° lugar - 15.045 pts
Scripts
A maior comunidade GNU/Linux da América Latina! Artigos, dicas, tutoriais, fórum, scripts e muito mais. Ideal para quem busca auto-ajuda.
Site hospedado por:
