Advertisement
Not a member of Pastebin yet?
Sign Up,
it unlocks many cool features!
- '''
- Created on 24/06/2013
- @author: Luis Antonio Tavares (luis.tavares@msn.com)
- '''
- import string
- import random
- def inicia():
- alvo = 'BRASIL' # alvo pretendido pelo algoritmo
- numIndividuos = 400 # tamanho da populacao
- pm = 0.02 # porcentagem de mutacao
- limite = 200 # limite de geracoes
- comp = len(alvo) # comprimento da string
- print 'Exemplo Algoritmo Genetico'
- print 'Individuo alvo: ', alvo
- print 'Tamanho do individuo: ', comp
- print 'Tamanho da populacao: ', numIndividuos
- print 'Chance de mutacao: ', pm, '\n'
- p = geraPopulacaoInicial(comp, numIndividuos)
- print 'Populacao: ', p
- geracao = 1
- while geracao <= limite:
- '''Calculando o fitness de cada individuo (pais)'''
- n = calculaNota(p, alvo, comp)
- ''' Mostrando melhor resultado ate o momento'''
- nMelhor, vMelhor = achaMelhor(p, n)
- print "\nGeracao: ", geracao
- print "Melhor solucao: ", vMelhor
- print "Fitness: ", nMelhor, "\n"
- ''' Verificando se a resposta ja foi encontrada '''
- if nMelhor == 0:
- break
- ''' Fazendo o crossover de um ponto de 2 em 2 pais'''
- filhos = reproduz(p, comp, numIndividuos)
- ''' Aplicando mutacao nos filhos gerados '''
- filhos, numMutacoes = aplicaMutacao(filhos, comp, pm)
- print 'Numero de mutacoes: ', numMutacoes
- ''' Calculando fitness dos filhos '''
- notaFilhos = calculaNota(filhos, alvo, comp)
- ''' Mostrando melhor resultado entre os filhos ate o momento'''
- nMelhor, vMelhor = achaMelhor(filhos, notaFilhos)
- print "Melhor solucao entre os filhos: ", vMelhor
- print "Fitness: ", nMelhor, "\n"
- ''' Verificando se ja achou a resposta entre os filhos gerados '''
- if nMelhor == 0:
- break
- ''' Juntando pais e filhos em uma mesma variavel '''
- p = p + filhos
- notas = n + notaFilhos
- ''' Selecionando os mais aptos para a proxima geracao '''
- sobreviventes = roleta(p, notas, numIndividuos)
- p = sobreviventes
- ''' Proxima geracao '''
- geracao += 1
- ''' Faz a selecao dos mais aptos para continuar na proxima geracao atraves da roleta viciada '''
- def roleta(p, notas, numIndividuos):
- notasAux = map(lambda x: 1.0 / x, notas)
- soma = sum(notasAux)
- normalizadas = map(lambda x: x / soma, notasAux)
- ''' Calculando os valores acumulados da nota '''
- acumulada = []
- vAcumulado = 0
- for nota in normalizadas:
- vAcumulado = vAcumulado+nota
- acumulada.append(vAcumulado)
- ''' Sorteando individuos para compor a populacao pelo metodo da roleta viciada '''
- selecionados = [0] * len(p)
- i = 0 # conta quantos individuos ja foram selecionados
- sobreviventes = [] # indica quem ja foi selecionado (valor 1), pra nao selecionar um cara 2 vezes
- while (i <= numIndividuos):
- vSorteo = random.random()
- j = 0 # varre o vetor acumulada
- while vSorteo > acumulada[j]:
- j += 1
- if selecionados[j] == 0:
- sobreviventes.append(p[j])
- selecionados[j] = 1
- i += 1
- return sobreviventes
- ''' Aplica mutacao nos individuos de acordo com porcentagem de chance '''
- def aplicaMutacao(filhos, comp, pm):
- numMutacoes = 0
- filhosPosMutacao = []
- for filho in filhos:
- acaso = random.random()
- if acaso <= pm:
- ponto = random.randint(0,comp-1)
- letraAletoria = random.choice(string.ascii_uppercase)
- filhoMutante = filho[:ponto] + letraAletoria + filho[ponto+1:]
- filho = filhoMutante
- numMutacoes += 1
- filhosPosMutacao.append(filho)
- return filhosPosMutacao, numMutacoes
- ''' Reproducao atraves de crossover de 2 pontos '''
- def reproduz(p, comp, nIndividuos):
- f = []
- i = 0
- while i < nIndividuos:
- ponto = random.randint(1,comp-1)
- pai1 = p[i]
- pai2 = p[i+1]
- filho1 = pai1[0:ponto] + pai2[ponto:comp]
- filho2 = pai2[0:ponto] + pai1[ponto:comp]
- f.append(filho1)
- f.append(filho2)
- i += 2
- return f
- ''' Encontra a melhor solucao ate o momento '''
- def achaMelhor(p, n):
- melhorNota = min(n)
- indice = n.index(melhorNota)
- melhorValor = p[indice]
- return melhorNota, melhorValor
- ''' Calcula o fitness de toda a populacao '''
- def calculaNota(p, alvo, comp):
- notas = []
- for individuo in p:
- dif = 0
- for i in range(comp):
- dif += abs(ord(individuo[i]) - ord(alvo[i]))
- notas.append(dif)
- return notas
- ''' Gera a populacao inicial para o algoritmo '''
- def geraPopulacaoInicial(comp, numIndividuos):
- pop = []
- for i in range(numIndividuos):
- tokens = string.ascii_uppercase #quais caracteres aceitos
- numChar = comp #numero de caracteres por segmento
- aleatoString = ''.join(random.choice(tokens) for y in range(numChar))
- pop.append(aleatoString)
- return pop
- if __name__ == '__main__':
- inicia()
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement