luistavares

Exemplo de Algoritmo Genético v1

Jun 24th, 2013
70
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
  1. '''
  2. Created on 24/06/2013
  3.  
  4. @author: Luis Antonio Tavares (luis.tavares@msn.com)
  5. '''
  6. import string
  7. import random
  8.  
  9. def inicia():
  10.     alvo = 'BRASIL'                  # alvo pretendido pelo algoritmo
  11.     numIndividuos = 400                 # tamanho da populacao
  12.     pm = 0.02                           # porcentagem de mutacao
  13.     limite = 200                        # limite de geracoes
  14.    
  15.     comp = len(alvo)                    # comprimento da string
  16.    
  17.     print 'Exemplo Algoritmo Genetico'
  18.     print 'Individuo alvo: ', alvo
  19.     print 'Tamanho do individuo: ', comp
  20.     print 'Tamanho da populacao: ', numIndividuos
  21.     print 'Chance de mutacao: ', pm, '\n'
  22.    
  23.     p = geraPopulacaoInicial(comp, numIndividuos)    
  24.     print 'Populacao: ', p
  25.    
  26.     geracao = 1    
  27.     while geracao <= limite:
  28.  
  29.         '''Calculando o fitness de cada individuo (pais)'''
  30.         n = calculaNota(p, alvo, comp)
  31.        
  32.         ''' Mostrando melhor resultado ate o momento'''
  33.         nMelhor, vMelhor = achaMelhor(p, n)
  34.         print "\nGeracao: ", geracao
  35.         print "Melhor solucao: ", vMelhor
  36.         print "Fitness: ", nMelhor, "\n"      
  37.              
  38.         ''' Verificando se a resposta ja foi encontrada '''
  39.         if nMelhor == 0:
  40.             break
  41.            
  42.         ''' Fazendo o crossover de um ponto de 2 em 2 pais'''
  43.         filhos = reproduz(p, comp, numIndividuos)
  44.        
  45.         ''' Aplicando mutacao nos filhos gerados '''
  46.         filhos, numMutacoes = aplicaMutacao(filhos, comp, pm)
  47.         print 'Numero de mutacoes: ', numMutacoes
  48.        
  49.         ''' Calculando fitness dos filhos '''
  50.         notaFilhos = calculaNota(filhos, alvo, comp)
  51.        
  52.         ''' Mostrando melhor resultado entre os filhos ate o momento'''
  53.         nMelhor, vMelhor = achaMelhor(filhos, notaFilhos)
  54.         print "Melhor solucao entre os filhos: ", vMelhor
  55.         print "Fitness: ", nMelhor, "\n"
  56.        
  57.         ''' Verificando se ja achou a resposta entre os filhos gerados '''
  58.         if nMelhor == 0:
  59.             break
  60.        
  61.         ''' Juntando pais e filhos em uma mesma variavel '''
  62.         p = p + filhos
  63.         notas = n + notaFilhos
  64.  
  65.         ''' Selecionando os mais aptos para a proxima geracao '''
  66.         sobreviventes = roleta(p, notas, numIndividuos)
  67.         p = sobreviventes
  68.        
  69.         ''' Proxima geracao '''
  70.         geracao += 1
  71.  
  72. ''' Faz a selecao dos mais aptos para continuar na proxima geracao atraves da roleta viciada '''
  73. def roleta(p, notas, numIndividuos):
  74.     notasAux = map(lambda x: 1.0 / x, notas)
  75.     soma  = sum(notasAux)
  76.     normalizadas = map(lambda x: x / soma, notasAux)
  77.    
  78.     ''' Calculando os valores acumulados da nota '''
  79.     acumulada = []
  80.     vAcumulado = 0
  81.     for nota in normalizadas:
  82.         vAcumulado = vAcumulado+nota
  83.         acumulada.append(vAcumulado)
  84.    
  85.     ''' Sorteando individuos para compor a populacao pelo metodo da roleta viciada '''
  86.     selecionados = [0] * len(p)
  87.     i = 0               # conta quantos individuos ja foram selecionados
  88.     sobreviventes = []  # indica quem ja foi selecionado (valor 1), pra nao selecionar um cara 2 vezes
  89.     while (i <= numIndividuos):
  90.         vSorteo = random.random()
  91.         j = 0 # varre o vetor acumulada
  92.         while vSorteo > acumulada[j]:
  93.             j += 1
  94.         if selecionados[j] == 0:
  95.             sobreviventes.append(p[j])
  96.             selecionados[j] = 1
  97.             i += 1
  98.     return sobreviventes    
  99.        
  100. ''' Aplica mutacao nos individuos de acordo com porcentagem de chance '''
  101. def aplicaMutacao(filhos, comp, pm):
  102.     numMutacoes = 0
  103.     filhosPosMutacao = []
  104.     for filho in filhos:
  105.         acaso = random.random()
  106.         if acaso <= pm:
  107.             ponto = random.randint(0,comp-1)
  108.             letraAletoria = random.choice(string.ascii_uppercase)          
  109.             filhoMutante = filho[:ponto] + letraAletoria + filho[ponto+1:]
  110.             filho = filhoMutante
  111.             numMutacoes += 1
  112.         filhosPosMutacao.append(filho)
  113.     return filhosPosMutacao, numMutacoes
  114.  
  115. ''' Reproducao atraves de crossover de 2 pontos '''
  116. def reproduz(p, comp, nIndividuos):
  117.     f = []
  118.     i = 0
  119.     while i < nIndividuos:
  120.         ponto = random.randint(1,comp-1)
  121.        
  122.         pai1 = p[i]
  123.         pai2 = p[i+1]
  124.         filho1 = pai1[0:ponto] + pai2[ponto:comp]
  125.         filho2 = pai2[0:ponto] + pai1[ponto:comp]
  126.        
  127.         f.append(filho1)
  128.         f.append(filho2)
  129.         i += 2
  130.     return f
  131.        
  132.        
  133. ''' Encontra a melhor solucao ate o momento '''
  134. def achaMelhor(p, n):
  135.     melhorNota = min(n)
  136.     indice = n.index(melhorNota)
  137.     melhorValor = p[indice]
  138.     return melhorNota, melhorValor
  139.        
  140. ''' Calcula o fitness de toda a populacao '''
  141. def calculaNota(p, alvo, comp):
  142.     notas = []
  143.     for individuo in p:
  144.         dif = 0
  145.         for i in range(comp):
  146.             dif += abs(ord(individuo[i]) - ord(alvo[i]))
  147.         notas.append(dif)
  148.     return notas
  149.    
  150. ''' Gera a populacao inicial para o algoritmo '''
  151. def geraPopulacaoInicial(comp, numIndividuos):
  152.     pop = []
  153.     for i in range(numIndividuos):
  154.         tokens = string.ascii_uppercase #quais caracteres aceitos
  155.         numChar = comp #numero de caracteres por segmento
  156.         aleatoString = ''.join(random.choice(tokens) for y in range(numChar))  
  157.         pop.append(aleatoString)      
  158.     return pop
  159.  
  160. if __name__ == '__main__':
  161.     inicia()
RAW Paste Data