Problema de alocação de artigos - algoritmo genetico - python

Esta é uma pré-visualização de arquivo. Entre para ver o arquivo original

t1 - genetico/validade_cromossomo.py
#Verifica se o cromossono eh valido.
#Cada vez que o Id do revisor aparece no cromossomo
#eh tirado 1 da quantidade de artigos maxima daquele revisor.
#Se no final houver alguma posicao com valor negativo, quer
#dizer que algum revisor recebeu mais artigos do que deveria
from copy import copy, deepcopy
# t[0,1...m]: quantidade maxima de artigo de cada revisor
# t[3] = 1 entao o revisor 3 soh pega 1 artigo 
def validade_cromossomo(cromossomo, t):
	aux=[]
	aux = deepcopy(t)
	# cromossomo[1] = 3
	# aux[cromossomo[1]] = t[3] = 1
	for i in range (len(cromossomo)):
		aux[cromossomo[i]] = aux[cromossomo[i]] - 1
	for i in range (len(aux)):
		# se alguma posicao tiver numero negativo, entao
		# algum revisor recebeu mais artigos do que deveria
		if aux[i]<0:
			return 0
	return 1
t1 - genetico/alocacaoArtigos.py
t1 - genetico/roleta.py
from random import *
"""
Chamada: roleta_viciada(probabilidade)
probabilidade vem da funcao probabilidade.py
Para probabilidade[i] = [0.0, 33.33, 44.44, 22.22]
Os pedacos da roleta sao divididos da seguinte forma
0.0 - 0.0: 	0
0.1 - 33.33: 1
33.34 - 77.78: 2
77.79 - 100.00: 3
"""
def gera_cromossomo(probabilidade):
	somaPeso = 0
	cromossomo = []
	for i in range(len(probabilidade)):
		cromossomo.append((roleta_viciada(probabilidade, i, 100)+1))
	return cromossomo
def roleta_viciada(probabilidade, i, pesos):
	sorteio = round(random()*pesos, 2)
	posicaoEscolhida = -1
	somaPeso = 0
	while somaPeso<sorteio :
		posicaoEscolhida = posicaoEscolhida + 1
		somaPeso = somaPeso + probabilidade[i][posicaoEscolhida]
		
	#print 'probabilidade:', probabilidade,'cromo:', cromossomo
	return posicaoEscolhida
""" 
#Para teste
if __name__ == '__main__':
	probabilidade = [[0.0, 33.33, 44.44, 22.22], [0.0, 60.0, 0.0, 40.0], 
					[60.0, 0.0, 0.0, 40.0], [50.0, 0.0, 12.5, 37.5], [57.14, 14.29, 0.0, 28.57]]
	print gera_cromossomo(probabilidade)
"""
t1 - genetico/gera_grafico.py
# -*- coding: utf-8 -*-
#!/usr/bin/python
# c-cedilha: \u00E7
import numpy as np
import matplotlib.pyplot as plt
"""
Selecionando posição das legendas
"""
x = np.arange(1, 11)
print(x)
plt.figure(figsize=(6, 4))
plt.plot(x, 2*x, color='#17a589') # green
plt.plot(x, x/2, color='red')
plt.plot(x, x+3, color='#f4d03f') # yellow
plt.xlabel('x')
plt.ylabel('f(x)')
plt.grid(True)
plt.title('Retas Simples')
plt.legend(['f(x) = 2x', 'f(x) = x/2', 'f(x) = x + 3'], loc='best')
plt.savefig('reta-legendas-centro.png')
plt.show()
plt.close()
t1 - genetico/reproducao.py
from random import *
from copy import copy, deepcopy
import math as mt
import sys
def fitness(cromossomo, afinidade):
	fa = 0
	for j in range(len(cromossomo)):
		fa = afinidade[cromossomo[j]][j] + fa	
	return fa
def reproducao(nova_populacao, filho):
	afinidade = [[0, 0, 0, 0, 0], [0, 0, 3, 4, 4], [3, 3, 0, 0, 1], [4, 0, 0, 1, 0], [2, 2, 2, 3, 2]]
	aux1 = []
	if len(filho) > 0:
		for i in range(len(filho)):
			aux = []
			aux.append(fitness(filho[i], afinidade))
			aux.append(filho[i])
			aux1.append(aux)
		nova_populacao.extend(aux1)
		nova_populacao = sorted(nova_populacao)
	print nova_populacao, '\n\n', nova_populacao[len(nova_populacao)-1][0]
	if nova_populacao[len(nova_populacao)-1][0] > 14:
		print 'PORAA'
if __name__ == '__main__':
	filho = [[3, 4, 1, 4, 2], [2, 2, 1, 4, 4], [2, 2, 1, 4, 4], [3, 2, 4, 1, 4], [4, 2, 4, 1, 2], [2, 4, 1, 3, 4], [4, 2, 1, 4, 2]]
	nova = [[12, [4, 2, 1, 4, 2]], [12, [4, 2, 4, 1, 2]], [12, [4, 2, 4, 3, 1]], [13, [2, 2, 4, 3, 1]], [13, [3, 4, 1, 4, 2]], [15, [3, 2, 1, 4, 4]], [15, [3, 2, 4, 1, 4]], [15, [3, 2, 4, 1, 4]]]
	reproducao(nova, filho)
t1 - genetico/entrada.txt
0,0,3,4,4,1
3,3,0,0,1,2
4,0,0,1,0,1
2,2,2,3,2,2
t1 - genetico/probabilidade.py
import math
"""
 Calcula a probabilidade do revisor 'i' ficar com o artigo 'j'
 Essa probabilidade eh calculada usando um sistema de media ponderada.
 saida: probabilidade [0] sao as probabilidades do revisor 0 ficar com
 cada um dos artigos i
 iXj
"""
# cada posicao de probabilidade[j] possui os valores
# % do artigo j ficar com cada revisor i
def combinador(afinidade, peso, interesse, t):
	probabilidade = []
	
	for j in range(len(afinidade[0])):
		valor = []
		for i in range(len(afinidade)):
			if interesse[i] != 0:
				valor.append( round(float(afinidade[i][j]*100) / (peso[j]), 2))#*interesse[i]), 2 ))
		if len(valor) > 0:
			probabilidade.append(valor)
	#print probabilidade
	return gera_populacao(probabilidade, afinidade, t)
	#roleta_viciada(probabilidade)
"""
# cada posicao de probabilidade[i] possui os valores
# % do revisor i ficar com cada artigo j
def combinador1(afinidade, peso, interesse, t):
	probabilidade = []
	
	for i in range(len(afinidade)):
		valor = []
		for j in range(len(afinidade[0])):
			if interesse[i] != 0:
				valor.append( round(float(afinidade[i][j]*100) / (peso[j]*interesse[i]), 2 ))
		if len(valor) > 0:
			probabilidade.append(valor)
	print probabilidade
"""
t1 - genetico/funcao_avaliacao.py
# O valor em 'cromossomo[j]' representa o Id do revisor responsavel pelo artigo 'j'
# Na matriz afinidade[i][j], cada 'j' representa um artigo e cada 'i' representa o
# Id do revisor, logo, i = cromossomo[j]
##################################################################################
# Para o grafico precisa instalar MatPlotLib. No prompt: pip install matplotlib
import matplotlib.pyplot as plt
grafico_fitness = []
grafico_iteracao = []
iteracao = 0
# A funcao fitness avalia o quao bem os artigos foram dados a cada revisor,
# levanto em conta a finidade do revisor com o artigo.
# Assim, cada posicao do cromossomo eh mapeada na matriz afinidade[i][j], e os 
# valores sao somados. A valor maximo da funcao fitness eh 5xM, onde M eh a 
# quantidade de artigos a serem alocados, pois o melhor resultado seria se cada
# revisor recebesse o artigo com o qual possui maior afinidade.
def fitness(cromossomo, afinidade):
	fa = 0
	#iteracao = iteracao + 1
	for j in range(len(cromossomo)):
		fa = afinidade[cromossomo[j]][j] + fa
	
	#grafico_fitness.append(fa)
	#grafico_iteracao.append(iteracao)
	return fa
def gera_grafico():
	media = 0
	for i in range(len(grafico_fitness)):
		media = media +grafico_fitness[i]
	media = media/iteracao
	
	plt.plot(grafico_fitness, grafico_iteracao)
	plt.show()
t1 - genetico/saida-genetico.txt
[3, 2, 4, 4, 1]
t1 - genetico/apre.py
#!/usr/bin/python
# -*- coding: utf-8 -*-
import unicodedata
import re
if __name__ == '__main__':
	s = 'C:\Users\BIBI\Documents\t1.artigos.IA\t1'
	for i in range(len(s)):
		if s[i] == '\c':
			print 'OI'
t1 - genetico/entrada.py
# -*- coding: utf-8 -*-
#!/usr/bin/python
TAM_POPULACAO = 15
from random import *
from copy import copy, deepcopy
import math as mt
import sys
import numpy as np
import matplotlib.pyplot as plt
BEST = 0
MELHOR_SOL = []
MEDIAS_DEZ = []
"""
 Calcula a probabilidade do revisor 'i' ficar com o artigo 'j'
 Essa probabilidade eh calculada usando um sistema de media ponderada.
"""
def mutacao(filho, afinidade, probabilidade, t):
	# calcular fitness de cada cromossomo filho gerado
	fit = []
	peso_fit = 0
	for i in range(len(filho)):
		# menor fitness ficar com maior peso para que os piores 
		# cromossomos tenham mais chance de serem mutados
		fit.append(1000/ fitness(filho[i], afinidade)) 
		peso_fit = peso_fit + fit[i]
	# escolhe o cromossomo que vai sofrer mutacao, filho[x]
	x = roleta_viciada_mutacao(fit, peso_fit)
	# escolhe o gene que vai sofrer mutacao, filho[x][y]
	y = roleta_viciada_mutacao(filho[x], fit[x])
	# escolhe quem serah o novo gene
	z = roleta_viciada(probabilidade, y)
	
	aux = filho[x][y]
	filho[x][y] = z
	
	if validade_cromossomo(filho[x], t):
		return filho
	
	filho[x][y] = aux
	return mutacao(filho,
afinidade, probabilidade, t)
def roleta_viciada_mutacao(possibilidades,pesos):
	sorteio = round(random()*pesos, 2)
	posicaoEscolhida = -1
	somaPeso = 0
	while somaPeso<sorteio :
		posicaoEscolhida = posicaoEscolhida + 1
		somaPeso = somaPeso + 10000/possibilidades[posicaoEscolhida]
	return posicaoEscolhida
def crossover(auxA, auxB, crossoverRate, t):
	#tratando a taxa de crossover
	x = len(auxA[0][1]) # tamanho do cromossomo
	# para que tam fique sempre != 0
	if crossoverRate > 0.8:
		tam = int(mt.floor(x*crossoverRate)) # piso de x*taxa de crossover
	else:
		tam = int(mt.ceil(x*crossoverRate)) # teto de x*taxa de crossover
	
	
	#tratando os pais; removendo a fitness
	paiA = []
	paiB = []
	for i in range(len(auxA)):
		paiA.append(auxA[i][1])
	for i in range(len(auxB)):
		paiB.append(auxB[i][1])
	#tratando casos onde len(paiA) != len(paiB)
	if len(paiA) < len(paiB):
		limite = len(paiA)
	else:
		limite = len(paiB)	
	
	filho = []
	for i in range(limite):
		auxFio = []
		for j in range(tam):
			auxFio.append(paiA[i][j])
		for k in range(tam, x):
			auxFio.append(paiB[i][k])
		if validade_cromossomo(auxFio, t):
			filho.append(auxFio)
	for i in range(limite):
		auxFio = []
		for j in range(tam):
			auxFio.append(paiB[i][j])
		for k in range(tam, x):
			auxFio.append(paiA[i][k])
		if validade_cromossomo(auxFio, t):
			filho.append(auxFio)
	return filho
def roleta_viciada_selecao(possibilidades,pesos):
	sorteio = round(random()*pesos, 2)
	posicaoEscolhida = -1
	somaPeso = 0
	while somaPeso<sorteio :
		posicaoEscolhida = posicaoEscolhida + 1
		somaPeso = somaPeso + possibilidades[posicaoEscolhida][0]
	return posicaoEscolhida
def selecao(populacao):
	piores = []
	melhores = []
	# populacao eh um vetor em ordem crescente de fitness
	# assim os piores sao o n primeiros, os melhores sao x-n restante
	# n = populacao/2 e x = len(populacao)
	for l in range(len(populacao)/2):
		piores.append(populacao[l])
	for l in range(len(populacao)/2, len(populacao)):
		melhores.append(populacao[l])
	# 
	peso_piores = 0
	peso_melhores = 0
	for l in range(len(piores)):
		peso_piores = peso_piores + piores[l][0]
	for l in range(len(melhores)):
		peso_melhores = peso_melhores + melhores[l][0]
	
	pais_piores = []
	pais_melhores = []
	tam = len(piores)/2
	for l in range(tam):
		indice = roleta_viciada_selecao(piores,peso_piores)
		pais_piores.append(piores[indice])
		peso_piores = peso_piores - piores[indice][0]
		# cada cromossomo que eh selecionado, eh removido para que
		# nao seja selecionado novamente
		del piores[indice]
	tam = len(melhores)/2
	for l in range(tam):
		indice = roleta_viciada_selecao(melhores, peso_melhores)
		pais_melhores.append(melhores[indice])
		peso_melhores = peso_melhores - melhores[indice][0]
		del melhores[indice]
	
	nova_populacao = []
	nova_populacao.extend(piores)
	nova_populacao.extend(melhores)
	return pais_melhores, pais_piores, nova_populacao
	
def reproducao(nova_populacao, filho):
	aux1 = []
	if len(filho) > 0:
		for i in range(len(filho)):
			aux = []
			aux.append(fitness(filho[i], afinidade))
			aux.append(filho[i])
			aux1.append(aux)
		nova_populacao.extend(aux1)
		nova_populacao = sorted(nova_populacao)
	return nova_populacao
def fitness(cromossomo, afinidade):
	fa = 0
	for j in range(len(cromossomo)):
		fa = afinidade[cromossomo[j]][j] + fa	
	return fa
def validade_cromossomo(cromossomo, t):
	aux=[]
	aux = deepcopy(t)
	# cromossomo[1] = 3
	# aux[cromossomo[1]] = t[3] = 1
	for i in range (len(cromossomo)):
		aux[cromossomo[i]] = aux[cromossomo[i]] - 1
	for i in range (len(aux)):
		# se alguma posicao tiver numero negativo, entao
		# algum revisor recebeu mais artigos do que deveria
		if aux[i]<0:
			return 0
	return 1
def roleta_viciada(probabilidade, i):
	#evitar que escolha-se os extremos
	while True:
		sorteio = round(random()*100, 2)
		if sorteio != 0 and sorteio != 100:
			break
	posicaoEscolhida = -1
	somaPeso = 0
	while somaPeso<sorteio :
		posicaoEscolhida = posicaoEscolhida + 1
		somaPeso = somaPeso + probabilidade[i][posicaoEscolhida]
	return posicaoEscolhida
def gera_cromossomo(probabilidade):
	somaPeso = 0
	cromossomo = []
	for i in range(len(probabilidade)):
		cromossomo.append((roleta_viciada(probabilidade,i)+1))
	return cromossomo
def gera_primeira_populacao(probabilidade, afinidade, t):
	populacao = []
	cromossomo = []
	while (len(populacao)<TAM_POPULACAO):
		aux = []
		cromossomo =gera_cromossomo(probabilidade)
		if (validade_cromossomo(cromossomo, t)):
			aux.append(fitness(cromossomo, afinidade))
			aux.append(cromossomo)
			populacao.append(aux)
	return populacao
def combinador(afinidade, peso, interesse):
	probabilidade = []
	
	for j in range(len(afinidade[0])):
		valor = []
		for i in range(len(afinidade)):
			if interesse[i] != 0:
				valor.append( round(float(afinidade[i][j]*100) / (peso[j]), 2))#*interesse[i]), 2 ))
		if len(valor) > 0:
			probabilidade.append(valor)
	
	return probabilidade
def gera_txt(c):
	f1= open("saida-genetico.txt","w+")
	f1.write("%s" % c)
	f1.close() 
def media_fitness(populacao):
	soma = 0
	tam = len(populacao)
	for i in range(tam):
		soma = soma + populacao[i][0]
	return soma / (tam)
def gera_grafico():
	data1 = MEDIAS_DEZ
	data2 = MELHOR_SOL
	x = np.array(range(len(data1)))
	plt.plot( x, data1, 'go') # green bolinha
	plt.plot( x, data2, 'r^') # red triangulo
	plt.plot( x, data1, 'k:', color='orange') # linha pontilha orange	
	plt.plot( x, data2, 'k--', color='blue') # linha tracejada azul
	plt.legend([u'M\u00e9dia das 10 repeti\u00E7\u00f5es', u'Melhor solu\u00E7\u00e3o'], loc='best')
	plt.axis([0, 9, 0, 20]) #limites
	plt.title(u"Evolu\u00E7\u00e3o da Fitness")
	plt.grid(True)
	plt.xlabel(u"Itera\u00E7\u00e3o")
	plt.ylabel("Fitness")
	plt.savefig('fitness.png')
if __name__ == '__main__':
	#### Recebendo parametros ####
	x = []
	for param in sys.argv :
		x.append(param)
	if len(x) < 4:
		print 'Entre com os dados na ordem:\n0 <= Taxa de crossover < 1\n0 <= Taxa de mutacao< 1\nCaminho para o arquivo de entrada separado por "/"\n Maximo de geracoes (opcional)'
		exit()
	else:
		crossoverRate = float(x[1])
		mutationRate = float(x[2])
		inputPath = x[3]
	if len(x) == 5:
		maxgen = int(x[4])
	else: 
		maxgen = 100	
	#####Parametros recebidos#####
	###Tratando dados de entrada###
	f = open ( inputPath , 'r')
	aux = []
	entrada = []
	entrada = [[int(num) for num in line.split(',')] for line in f if line.strip() != "" ]
	f.close()
	# Insere uma linha de zeros
	aux.append( [0] * len(entrada[0]))
	aux.extend(entrada)
	entrada = aux
	del(aux)
	# T: vetor das quantidades.
	# t[i] = quantidade maxima de artigos do i-esimo revisor
	t = []
	for i in range(len(entrada)):
		t.append(entrada[i][len(entrada)])
	# afinidade[i][j]: matriz de afinidades revisorXartigo
	# revisor 'i' tem afinidade[i][j] pelo artigo 'j'
	afinidade = []
	afinidade = entrada
	for i in range(len(entrada)):
		del(afinidade[i][len(entrada)])
	# total_peso[j]: quao desejado o artigo 'j' eh.
	# usado para caucular a probabilidade de um revisor 'i' 
	# ficar com um artigo 'j'
	total_peso = []
	for j in range(len(afinidade[0])):
		peso = 0
		for i in range(len(afinidade)):
			peso = peso + afinidade[i][j]
		total_peso.append(peso)
	
	# total_artigos[i]: por quantos artigos o revisor 'i'
	# manifestou interesse
	total_artigos = []
	for i in range(len(afinidade)):
		quantidade = 0
		for j in range(len(afinidade[0])):
			if afinidade[i][j] != 0:
				quantidade = quantidade + 1
		total_artigos.append(quantidade)
	#####Dados tratados de entrada#####
	for j in range(10):
		#populacao ordenada por fitness
		probabilidade = combinador(afinidade, total_peso, total_artigos)	
		populacao = sorted(gera_primeira_populacao(probabilidade, afinidade, t))
		##############################
for i in range(maxgen):
			if len(populacao) < 3:
				break
			
			selecionados = selecao(populacao) #return pais_melhores, pais_piores, nova_populacao
			filho = crossover(selecionados[0], selecionados[1], crossoverRate, t)	
			# Verificar se 0 <= mutationRate < 1
			if random() > mutationRate or len(filho)<=0:
				populacao = reproducao(selecionados[2], filho)
			else:
				filho = mutacao(filho, afinidade, probabilidade, t)
				populacao = reproducao(selecionados[2], filho)
		
		if populacao[len(populacao)-1][0] > BEST:
			BEST = populacao[len(populacao)-1]
		MEDIAS_DEZ.append(media_fitness(populacao))
		MELHOR_SOL.append(populacao[len(populacao)-1][0])
	print MEDIAS_DEZ
	print MELHOR_SOL
	print BEST
	gera_grafico()
	gera_txt(BEST[1])
	
	
 
t1 - genetico/fitness.png
t1 - genetico/selecao.py
from random import *
def roleta_viciada_selecao(probabilidade,pesos, t):
	sorteio = round(random()*pesos, 2)
	posicaoEscolhida = -1
	somaPeso = 0
	while somaPeso<sorteio :
		posicaoEscolhida = posicaoEscolhida + 1
		somaPeso = somaPeso + probabilidade[posicaoEscolhida][0]
		
	#print 'probabilidade:', probabilidade,'cromo:', cromossomo
	return posicaoEscolhida
def selecao(populacao):
	t=[1,2,1,2]
	piores = []
	melhores = []
	for l in range(len(populacao)/2):
		piores.append(populacao[l])
	for l in range(len(populacao)/2, len(populacao)):
		melhores.append(populacao[l])
	#Selecao por roleta viciada
	peso_piores = 0
	peso_melhores = 0
	for l in range(len(piores)):
		peso_piores = peso_piores + piores[l][0]
	for l in range(len(melhores)):
		peso_melhores = peso_melhores + melhores[l][0]
	
	pais_piores = []
	pais_melhores = []
	tam = len(piores)/2
	print '\npiores', len(piores), '\nmelhores', len(melhores)
	for l in range(tam):
		indice = roleta_viciada_selecao(piores,peso_piores, t)
		pais_piores.append(piores[indice])
		peso_piores = peso_piores - piores[indice][0]
		del(piores[indice])
	tam = len(melhores)/2
	for l in range(tam):
		indice = roleta_viciada_selecao(melhores, peso_melhores, t)
		pais_melhores.append(melhores[indice])
		peso_melhores = peso_melhores - melhores[indice][0]
		del(melhores[indice])
	print '\npiores', len(piores), '\npiores pais', len(pais_piores), '\nmelhores', len(melhores), '\nmelhores pais', len(pais_melhores)
if __name__ == '__main__':
	populacao =	[[9, [4, 2, 4, 3, 2]], [10, [4, 2, 1, 3, 2]], [11, [2, 2, 4, 3, 4]], 
				[11, [4, 2, 1, 3, 4]], [11, [4, 2, 1, 3, 4]], [12, [2, 2, 1, 3, 4]], 
				[12, [2, 4, 1, 4, 2]], [12, [2, 4, 4, 1, 2]], [12, [4, 2, 1, 4, 2]], 
				[13, [3, 4, 1, 4, 2]], [13, [3, 4, 4, 1, 2]], [14, [2, 2, 1, 4, 4]], 
				[14, [2, 2, 4, 1, 4]], [14, [3, 2, 1, 4, 2]], [15, [2, 2, 4, 4, 1]], 
				[15, [3, 2, 1, 4, 4]], [16, [3, 2, 4, 4, 1]], [16, [3, 2, 4, 4, 1]], 
				[16, [3, 2, 4, 4, 1]], [16, [3, 2, 4, 4, 1]]]
	selecao(populacao)
t1 - genetico/gera_populacao.py
def gera_populacao(probabilidade, afinidade, t):
	populacao = []
	cromossomo = []
	while (len(populacao)<TAM_POPULACAO):
		aux = []
		cromossomo =gera_cromossomo(probabilidade)
		if (validade_cromossomo(cromossomo, t)):
			aux.append(fitness(cromossomo, afinidade))
			aux.append(cromossomo)
			populacao.append(aux)
	return populacao
# nao sendo usado
def gera_populacao1(probabilidade, afinidade, t):
	populacao = []
	cromossomo = []
	while (len(populacao)<TAM_POPULACAO):
		aux = []
		cromossomo = roleta_viciada(probabilidade)
		if (validade_cromossomo(cromossomo, t)):
			aux.append(fitness(cromossomo, afinidade))
			aux.append(cromossomo)
			populacao.append(aux)
	return populacao
"""
ITERACAO = 0
media_fitness = []
melhor_fitness = []
def gera_populacao(probabilidade, afinidade, t):
	global ITERACAO 
	ITERACAO = ITERACAO + 1
	populacao = []
	cromossomo = []
	media = 0
	melhor = 0
	while (len(populacao)<TAM_POPULACAO):
		aux = []
		cromossomo = roleta_viciada(probabilidade)
		if (validade_cromossomo(cromossomo, t)):
			fitness1 = fitness(cromossomo, afinidade)
			aux.append(fitness1)
			aux.append(cromossomo)
			populacao.append(aux)
	################## Para o grafico
			media = media + fitness1
			if fitness1 > melhor:
				melhor = fitness1
	media_fitness.append(media / 50)
	melhor_fitness.append(melhor)
	return populacao
"""
t1 - genetico/reserva.py
def gera_txt(c):
	f1= open("saida-genetico.txt","w+")
	f1.write("%s" % c)
	f1.close() 
def media_fitness(populacao):
	soma = 0
	tam = len(populacao)
	for i in range(tam):
		soma = soma + populacao[i][0]
	return soma / (tam)
def gera_grafico():
	data1 = MEDIAS_DEZ
	data2 = MELHOR_SOL
	x = np.array(range(len(data1)))
	plt.plot( x, data1, 'go') # green bolinha
	plt.plot( x, data2, 'r^') # red triangulo
	plt.plot( x, data1, 'k:', color='orange') # linha pontilha orange	
	plt.plot( x, data2, 'k--', color='blue') # linha tracejada azul
	plt.legend([u'M\u00e9dia das 10 repeti\u00E7\u00f5es', u'Melhor solu\u00E7\u00e3o'], loc='best')
	plt.axis([0, 9, 0, 20]) #limites
	plt.title(u"Evolu\u00E7\u00e3o da Fitness")
	plt.grid(True)
	plt.xlabel(u"Itera\u00E7\u00e3o")
	plt.ylabel("Fitness")
	plt.savefig('fitness.png')
t1 - genetico/Documento sem título.docx
a) Verificar se a máquina se encontra cadastrada no SGR; 
b) Verificar se a máquina está cadastrada na rede correta. 
c) Verificar se há duas interfaces de redes, e se as mesmas estão ativas e cadastradas; 
d) Verificar se o IP está fixo, se estiver coloque automático. (Exceto em raros setores onde possa ser fixo o IP);
e) Verificar a existência de loop entre hubs, switch’s e entre outros; 
f) Verificar se os equipamentos (hubs, switch’s e entre outros) não estão travados. (Caso esteja, reiniciar); 
g) Verificar se o IP está automático, porém o DNS está estático. Caso esteja, altere para automático; 
h) Verificar se está sem link de internet; 
i) Verificar se o firewall do Windows está ativado, caso esteja desative e veja se a internet voltou, senão ative novamente; 
j) Verificar se o Proxy do navegador está marcado. (Vá a um navegador ou painel de controle, acesse “Opções da Internet”, acesse a aba “Conexões”, clique no botão “Configurações da LAN” e desabilite a opção de Servidor proxy, por fim aplique as configurações); 
k) A placa de rede pode estar clonada. (Acesse “Central de Rede e Compartilhamento”, no Menu lateral acesse “Alterar as configurações do adaptador”, clique com o botão direito em cima da interface e acesse a opção “Propriedades”, após, pressione o botão [Configurar...] na tela de (Propriedades de Conexão local), acesse a aba “Avançado”, na lista de Propriedades selecione a opção “Endereço de Rede” e marque a opção “Ausente”. Aplique as configurações realizadas clicando no botão [OK]; 
l) Fixar IP manualmente de acordo com as configurações do SGR; 
m) Verificar se há configuração alternativa de IP. (Acesse Propriedades de Conexão Local, selecione o protocolo e pressione o botão [Propriedades], após acesse a aba [Configuração Alternativa] e selecione a opção “Endereço IP particular automático”);
 n) Verificar se o cabo é crossover. (Caso haja um link de switch para switch, verifique se o switch é MDI/MDIX, se for MDIX verificar se o cabo é crossover, pois o cabo padrão não funciona com tecnologia MDIX (Media Dependent Interface with Crossover)).
t1 - genetico/Trabalho1(1).pdf
Inteligeˆncia Artificial - T01
Prof. Bruno M. Nogueira
Faculdade de Computac¸a˜o - UFMS
Trabalho I - Algoritmos de Busca
Neste primeiro trabalho, voceˆs devem, em grupos de no mı´nimo 3 e no ma´ximo 4 pessoas,
implementar algoritmos de busca para resolver os problemas destacados.
1 Problema do Jogo Resta Um
Resta um e´ jogo de tabuleiro cujo objetivo e´, por meio
de movimentos “pula-pec¸a”, deixar apenas
uma pec¸a no tabuleiro. No in´ıcio do jogo, ha´ 32 pec¸as no tabuleiro, deixando vazia a posic¸a˜o
central, tal como exibido na Figura 1.
Figura 1: Configurac¸a˜o inicial do tabuleiro do jogo Resta Um.
Pec¸as podem saltar sobre outras imediatamente na horizontal ou imadiatamente na vertical,
desde que o salto termine em um espac¸o vazio. A pec¸a que foi “saltada” e´ retirada do tabuleiro.
O jogo termina quando na˜o e´ mais poss´ıvel fazer nenhum outro movimento. O jogador ganha se
restar apenas uma pec¸a no tabuleiro.
Implemente uma soluc¸a˜o em Python para o problema do Resta Um, utilizando o algoritmo
A*. Os estados sera˜o representados por uma matriz nume´rica (lista de listas) de tamanho 6x6.
Posic¸o˜es ocupadas sera˜o representadas pelo valor 1, enquanto posic¸o˜es vazias sera˜o ocupadas pelo
valor 0. As posic¸o˜es fora do intervalo va´lido (as duas primeiras e duas u´ltimas colunas para as
duas primeiras e duas u´ltimas linhas) devera˜o, sempre, ter valor 0 - na˜o fazem parte do tabuleiro
e, portanto, na˜o podem ser ocupadas. Assim, o estado inicial do problema sera´, sempre, da forma:
[[0,0,1,1,1,0,0],[0,0,1,1,1,0,0], [1,1,1,1,1,1,1], [1,1,1,0,1,1,1], [1,1,1,1,1,1,1], [0,0,1,1,1,0,0], [0,0,1,1,1,0,0]]
Ao encontrar um estado final, deve-se listar, em ordem, todos os movimentos realizados, de
maneira a identificar a transic¸a˜o de estado escolhida. Cada movimento deve ser identificado com
(X, Y ) − (X ′, Y ′), em que o par (X, Y ) determina a linha e a coluna em que se encontra a pec¸a
a ser movida, enquanto (X ′, Y ′) indicam a linha e a coluna de destino da pec¸a movida. Linhas
e colunas sa˜o numeradas de 0 a 6, como mostrado na Figura 1. Por exemplo, um dos poss´ıveis
movimentos iniciais seria (3, 1)− (3, 3), indicando a movimentac¸a˜o da pec¸a da linha 3, coluna 1,
para o espac¸o em branco na linha 3, coluna 3. Neste movimento, a pec¸a localizada em (3, 2) foi
pulada e, portanto, deve ser removida.
Voceˆ devera´ reportar o tempo de execuc¸a˜o e o nu´mero de estados expandidos (enfileirados)
ate´ encontrar a soluc¸a˜o. A heur´ıstica a ser utilizada devera´ ser desenvolvida pelo grupo. Seu
programa devera´ gerar um arquivo denominado “saida-resta-um.txt”, que devera´ conter todas as
soluc¸o˜es encontradas pelo seu programa, seguindo EXATAMENTE o seguinte formato:
• Cada soluc¸a˜o deve ser precedida da diretiva ==SOLUCAO ;
• Cada linha deve conter um movimento, com par ordenado da posic¸a˜o de origem - par orde-
nado da posic¸a˜o de destino da pec¸a movimentada. Observem a existeˆncia de um espac¸o em
branco antes e apo´s o h´ıfen;
• O movimento que leva ao estado final deve ser iniciado com a diretiva FINAL, seguido de
um espac¸o em branco e a posterior sequeˆncia de pares identificando o movimento;
• As soluc¸o˜es devem ser separadas por exatamente uma linha em branco.
Abaixo, um exemplo do conteu´do esperado do arquivo de sa´ıda.
==SOLUCAO
(X1, Y1) - (X2, Y2)
...
FINAL (XN, YN) - (XK, YK)
==SOLUCAO
(X1, Y1) - (X2, Y2)
...
FINAL (XT, YT) - (XS, YS)
2 Problema de alocac¸a˜o de artigos
Confereˆncias cient´ıficas baseiam a selec¸a˜o de artigos a serem publicados em processos de revisa˜o
por pares. Nestes, cientistas proeminentes da a´rea da confereˆncia sa˜o convidados a contribuir,
revisando artigos submetidos pelos autores, indicando a aprovac¸a˜o ou rejeic¸a˜o dos mesmos.
Um dos grandes problemas enfrentados pelos organizadores dos eventos, no entanto, consiste na
atribuic¸a˜o dos artigos aos revisores. Em geral, um processo de votac¸a˜o e´ feito antes da atribuic¸a˜o,
no qual os revisores sa˜o apresentados ao t´ıtulo e ao resumo dos artigos a serem avaliados e atribuem
uma nota inteira de afinidade entre 0 (na˜o desejo revisar, na˜o conhec¸o o tema do artigo) e 5 (desejo
muito revisar, sou especialista na a´rea do artigo). Ale´m disso, os revisores indicam quantos artigos,
no ma´ximo, gostariam de revisar para este evento. O grande desafio consiste em atribuir os artigos
recebidos aos melhores revisores, buscando sempre respeitar os limites de cada colaborador.
Elabore uma soluc¸a˜o de atribuic¸a˜o de artigos baseada em algoritmos gene´ticos, implementada
em Python, para auxiliar este processo. Sua soluc¸a˜o devera´ atribuir artigos de maneira a maximi-
zar a afinidade revisor / artigo da distribuic¸a˜o. Nenhum artigo pode ficar sem revisa˜o e deve-se,
sempre, respeitar o ma´ximo de artigos que um revisor pode receber.
Seu algoritmo deve receber como entrada uma matriz NxM + 1, lida a partir de um arquivo
textual. Nesta matriz, N e´ o nu´mero de revisores cadastrados e M e´ o nu´mero de artigos a serem
atribu´ıdos. Ao final de cada linha, estara´ expresso o ma´ximo de artigos que o revisor aceita receber
(sempre maior ou igual a 1). Abaixo, um exemplo de entrada:
0,0,3,4,4,1
3,3,0,0,1,2
4,0,0,1,0,1
2,2,2,3,2,2
Neste exemplo, 5 artigos foram recebidos e 4 revisores esta˜o dispon´ıveis. O revisor 1 tem
afinidade 0 com os artigos 1 e 2; afinidade 3 com o artigo 3; afinidade 4 com os artigos 4 e 5; e
aceita receber, no ma´ximo, 1 artigo para revisar.
Na sua soluc¸a˜o, deve-se ler uma matriz a partir de um arquivo de entrada, no formato NxM+1,
como a de exemplo apresentada anteriormente. A codificac¸a˜o gene´tica dos estados deve ser definida
por voceˆ. Voceˆ deve inicializar os indiv´ıduos aleatoriamente. Por isso, 10 repetic¸o˜es devem
ser feitas para um mesmo problema. Voceˆ devera´ utilizar os operadores de selec¸a˜o, mutac¸a˜o e
crossover. Devem ser paraˆmetros do seu algoritmo a taxa de crossover (com o nome crossoverrate),
a taxa de mutac¸a˜o (com o nome mutationrate), o ma´ximo de gerac¸o˜es a serem desenvolvidas (com
o nome maxgen e valor padra˜o de 100) e o caminho para o arquivo de entrada da matriz (com o
nome inputpath). A func¸a˜o de fitness a ser utilizada tambe´m deve ser definida por voceˆ, devendo
ser aplicada para o processo de selec¸a˜o por roleta.
Seu programa devera´ gerar um gra´fico da evoluc¸a˜o da func¸a˜o de fitness ao longo das gerac¸o˜es
(gra´fico de linha, com o nome “fitness.png”). Duas linhas devem estar no gra´fico, uma para a
melhor soluc¸a˜o e outra para a me´dia das 10 repetic¸o˜es.
Tambe´m, deve ser gerado um arquivo “saida-genetico.txt”, reportando o resultado obtido ao
final da execuc¸a˜o que, dentre as 10 repetic¸o˜es, teve a melhor func¸a˜o de fitness. Nesta sa´ıda, uma
u´nica linha de tamanho M deve ser gerada, indicando o ı´ndice do revisor atribu´ıdo a um determi-
nado artigo. Abaixo, um exemplo de sa´ıda para o problema de entrada reportado anteriormente.
3,2,1,4,4
Neste exemplo, o artigo 1 foi atribu´ıdo ao revisor 3; o artigo 2 ao revisor 2; o artigo 3 ao revisor
1; o artigo 4 ao revisor 4; e o artigo 5 tambe´m ao revisor 4.
3 Entregas
Para estes problemas, deve-se entregar soluc¸o˜es codificadas em Python. Para o primeiro problema,
deve-se denominar o script principal de restaUm.py. Para o segundo problema, o script principal
deve ser denominado alocacaoArtigos.py. Todos os scripts devem ter no cabec¸alho o nome e o
RGA de cada membro do grupo, bem como comenta´rios ao longo do co´digo que possam facilitar
o entendimento do mesmo.
Junto ao co´digo, deve ser entregue um relato´rio no formato PDF, de tamanho entre duas a
quatro pa´ginas. Este relato´rio deve estar identificado com o nome de todos os integrantes do grupo
e deve, obrigatoriamente, apresentar:
1. Uma explicac¸a˜o das heur´ısticas utilizadas (func¸o˜es de custo, avaliac¸a˜o e fitness). As func¸o˜es
devem ser aplica´veis e condizentes com os problemas. Deve-se mostrar matematicamente
como sa˜o expressas as func¸o˜es escolhidas, bem como explicar a intuic¸a˜o que motivou a
escolha da mesma.
2. Para o primeiro problema, deve-se reportar tempo de execuc¸a˜o e nu´mero de estados
expan-
didos. E´ deseja´vel, mas na˜o obrigato´rio, que mais de uma heur´ıstica seja adotada, para fins
de comparac¸a˜o. Gra´ficos e tabelas, com as respectivas explicac¸o˜es, devem ser apresentados
no relato´rio.
3. Para o segundo problema, deve-se testar, pelo menos, treˆs combinac¸o˜es de paraˆmetros dife-
rentes, reportando os resultados obtidos utilizando os gra´ficos de evoluc¸a˜o do fitness ao longo
das iterac¸o˜es. Tambe´m deve ser mensurado o tempo de execuc¸a˜o e o nu´mero de iterac¸o˜es
levado ate´ a convergeˆncia (se ocorrer). Tambe´m, e´ obrigato´rio o uso de gra´ficos e tabelas,
com as respectivas explicac¸o˜es, para reportar os valores dos resultados.
O prazo para entrega do trabalho sera´ as 23:55 do dia 05/05/2019. Devera˜o ser entregues
todos os scripts com os co´digos das soluc¸o˜es, bem como o relato´rio em formato PDF. Todos os
arquivos devem ser compactados em um u´nico arquivo (.rar ou .zip). Uma u´nica entrega por
grupo deve ser feita, via Moodle (EAD). Entregas fora do prazo, ou feitas por outros meios, sera˜o
desconsideradas.
O professor consultara´ os alunos para que os integrantes apresentem os co´digos. Inicialmente,
tal apresentac¸a˜o esta´ marcada para o dia 07/05/2019, podendo ser ajustada a crite´rio do professor,
em acordo com os alunos. Todos os membros devera˜o estar presentes no momento da apresentac¸a˜o,
quando um dos integrantes sera´ sorteado como apresentador e cabendo a ele, e somente ele, as
explicac¸o˜es solicitadas pelo professor. A auseˆncia de algum membro implicara´ em nota zero ao
mesmo.
ATENC¸A˜O: Os co´digos sera˜o submetidos a ana´lise de pla´gio em sistemas pro´prios para isso.
Na˜o sera´ tolerado pla´gio de quaisquer fontes, mesmo que parcial. Quando detectado pla´gio, o
trabalho tera´ nota zero.
Havendo qualquer du´vida, consulte o professor.
Bom trabalho!
t1 - genetico/crossover.py
from copy import deepcopy
import math as mt
def validade_cromossomo(cromossomo, t):
	aux=[]
	aux = deepcopy(t)
	# cromossomo[1] = 3
	# aux[cromossomo[1]] = t[3] = 1
	print cromossomo, aux
	for i in range (len(cromossomo)):
		print i
		aux[cromossomo[i]] = aux[cromossomo[i]] - 1
	for i in range (len(aux)):
		# se alguma posicao tiver numero negativo, entao
		# algum revisor recebeu mais artigos do que deveria
		if aux[i]<0:
			return 0
	return 1
def crossover(auxA, auxB, crossoverRate, t):
	#tratando a taxa de crossover
	x = len(auxA[0][1]) # tamanho do cromossomo
	# para que tam fique sempre != 0
	if crossoverRate > 0.8:
		tam = int(mt.floor(x*crossoverRate)) # piso de x*taxa de crossover
	else:
		tam = int(mt.ceil(x*crossoverRate)) # teto de x*taxa de crossover
	#print tam
	
	#tratando os pais; removendo a fitness
	paiA = []
	paiB = []
	for i in range(len(auxA)):
		paiA.append(auxA[i][1])
	for i in range(len(auxB)):
		paiB.append(auxB[i][1])
	
	filho = []
	for i in range(len(paiA)):
		auxFio = []
		for j in range(tam):
			auxFio.append(paiA[i][j])
		for k in range(tam, x):
			auxFio.append(paiB[i][k])
		if validade_cromossomo(auxFio, t):
			filho.append(auxFio)
	for i in range(len(paiB)):
		auxFio = []
		for j in range(tam):
			auxFio.append(paiB[i][j])
		for k in range(tam, x):
			auxFio.append(paiA[i][k])
		if validade_cromossomo(auxFio, t):
			filho.append(auxFio)
	return filho
if __name__ == '__main__':
	paiA = [[11, [1, 3, 4, 4, 2]], [14, [2, 2, 1, 4, 4]], [11, [2, 2, 4, 3, 4]]]
	paiB = [[16, [2, 2, 4, 4, 3]], [14, [2, 2, 4, 1, 4]], [14, [3, 2, 4, 1, 2]]]
	t = [0, 1, 2, 1, 2]
	crossover(paiA, paiB, 0.2, t)
	
	
t1 - genetico/Documento sem título(1).docx
Algoritmo Genetico:
Função Fitness: Cada revisor diz qual o grau de afinidade que possui com o artigo em questão. Assim, a melhor combinação possivel de artigos e revisores seria aquela onde todos os revisores ficassem com o artigo o qual tem mais afinidade. Sabendo que a afinidade vai de 0 a 5, a melhor fitness de um cromossomo seria: 5*Quantidade_de_Artigos.
Então, para calcular a fitness de um cromossomo basta somar as afinidades.
As afinidades foram mapeadas da matriz de entrada [N]x[M+1] em uma matriz [N+1]x[M], onde a primeira linha são zeros. Isso foi feito para “ignorar” a linha de índice zero fazendo com que a linha de índice 1 da matriz representasse o revisor 1.
Logo: afinidade[ i ]x[ j ], onde ‘i’ são os revisores e ‘j’ os artigos.
O cromossomo é uma lista tamanho M que indica o índice do revisor atribuído a um determinado artigo. 
Ex:
Afinidade
N é o número de revisores cadastrados e M é o número de artigos a serem atribuídos. Ao final de cada linha, estará expresso o máximo de artigos que o revisor aceita receber (sempre maior ou igual a 1).
		0
		0
		0
		0
		0
		0
		0
		3
		4
		4
		3
		3
		0
		0
		1
		4
		0
		0
		1
		0
		2
		2
		2
		3
		2