luistavares

Exemplo de Algoritmo Genético v2

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