Algoritmo genético - rotas
Publicado por César tinum da silva (última atualização em 08/12/2009)
[ Hits: 23.501 ]
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
Combinações de letras, números e muito mais
Agora temos uma assistente virtual no fórum!!! (246)
Compartilhando a tela do Computador no Celular via Deskreen
Como Configurar um Túnel SSH Reverso para Acessar Sua Máquina Local a Partir de uma Máquina Remota
Configuração para desligamento automatizado de Computadores em um Ambiente Comercial
Efeito "livro" em arquivos PDF
Como resolver o erro no CUPS: Unable to get list of printer drivers
Flatpak: remover runtimes não usados e pacotes
Mudar o gerenciador de login (GDM para SDDM e vice-versa) - parte 2
Como eu faço para ativar o sistema de gestos do mousepad? (4)
NGNIX - Aplicar SNAT para evitar roteamento assimetrico (13)
[Python] Automação de scan de vulnerabilidades
[Python] Script para analise de superficie de ataque
[Shell Script] Novo script para redimensionar, rotacionar, converter e espelhar arquivos de imagem
[Shell Script] Iniciador de DOOM (DSDA-DOOM, Doom Retro ou Woof!)
[Shell Script] Script para adicionar bordas às imagens de uma pasta