<jupyter_start><jupyter_text>Ejercicio 3Intente resolver el problema de las N-Reinas usando Hill Climbing y un Algoritmo Evolutivo.a) Proponga una representación adecuada para las soluciones.b) Proponga una función de evaluación que le permita cali car que tan buena es una solución.c) De na de que manera se obtendrán las soluciones vecinas para Hill Climbing y que operadores van a usarse con el Algoritmo Evolutivo.d) Implemente y pruebe lo de nido en los puntos anteriores para el caso donde N=16. Evalúe los resultados obtenidos. Detalle todos los parámetros usados. Justifique.<jupyter_code>import numpy as np
import matplotlib.pyplot as plt
from matplotlib import pylab
import mpld3

%matplotlib inline
mpld3.enable_notebook()

from busqueda_local import hill_climb

# -*- coding: utf-8 -*-

QUEENS = 100

def amenaza(fila_1, col_1, fila_2, col_2):
    "Determina a partir de sus posiciones si dos reinas se están amenazando."
    return ( (fila_1 == fila_2) or (col_1 == col_2) or
             (abs(fila_1 - fila_2) == abs(col_1 - col_2)) )

"""
Para la cantidad máxima de amenazas, si la reina A amenaza a la reina B, la
reina B también amenaza a la reina A pero sólo se contabiliza como una amenaza.
"""
MAX_AMENAZAS = (QUEENS * (QUEENS-1)) / 2<jupyter_output><empty_output><jupyter_text>Hill Climbing Evaluacion<jupyter_code>def evaluacion(x):
    t=0
    for i in range(0,x.size-1):
        for j in range(i+1,x.size):
            if amenaza(i,x[i],j,x[j]):
                t+=1
    return -t<jupyter_output><empty_output><jupyter_text>Vecinos<jupyter_code>def invertirPos(x,pos1,pos2):
    aaa=x[pos1]
    x[pos1]=x[pos2]
    x[pos2]=aaa
    return x

def vecinos(x):
    v = []
    pos=np.random.randint(0,x.size,3)
    while pos[0]==pos[1] & pos[1]==pos[2]:
        pos=np.random.randint(0,x.size,3)
    v.append(invertirPos(x,pos[0],pos[1]))
    v.append(invertirPos(x,pos[0],pos[2]))
    v.append(invertirPos(x,pos[1],pos[2]))
    return v<jupyter_output><empty_output><jupyter_text>Nuevos<jupyter_code>def nuevos(q):
    a=np.arange(q)
    np.random.shuffle(a)
    return a<jupyter_output><empty_output><jupyter_text>Busco<jupyter_code>def buscar(i,reinas):
    mejor = nuevos(reinas)
    for j in range(i):
        mejor, evaluaciones = hill_climb(mejor, evaluacion, vecinos)
        print("\nEvaluacion mejor",evaluacion(mejor))
        print("Evaluaciones:",evaluaciones)
        if evaluacion(mejor)==0:
            print("Ganadora:",mejor)
            tablero=np.empty((reinas,reinas),np.str_)
            for i in range(reinas):
                tablero[i,mejor[i]]='X'
            print(tablero)
    return
def buscarMejor(reinas):
    mejor = nuevos(reinas)
    while evaluacion(mejor)!=0:
        mejor, evaluaciones = hill_climb(mejor, evaluacion, vecinos)
    print("Evaluaciones:",evaluaciones)
    print("Ganadora:",mejor)
    tablero=np.empty((reinas,reinas),np.str_)
    for i in range(reinas):
        tablero[i,mejor[i]]='X'
    print(tablero)
    return mejor
buscarMejor(8)<jupyter_output>Evaluaciones: 10
Ganadora: [5 2 0 7 4 1 3 6]
[['' '' '' '' '' 'X' '' '']
 ['' '' 'X' '' '' '' '' '']
 ['X' '' '' '' '' '' '' '']
 ['' '' '' '' '' '' '' 'X']
 ['' '' '' '' 'X' '' '' '']
 ['' 'X' '' '' '' '' '' '']
 ['' '' '' 'X' '' '' '' '']
 ['' '' '' '' '' '' 'X' '']]<jupyter_text>Algoritmo Evolutivo<jupyter_code>QUEENS=16<jupyter_output><empty_output><jupyter_text>Defino Fitness Esperado<jupyter_code>creator.create("FitnessMax", base.Fitness, weights=(-1,))
creator.create("Individual", list, fitness=creator.FitnessMax)<jupyter_output><empty_output><jupyter_text>Defino ADN del Individuo<jupyter_code>toolbox = base.Toolbox()
toolbox.register("cromo_gen", nuevos, QUEENS)
toolbox.register("individual", tools.initIterate, creator.Individual, toolbox.cromo_gen)
toolbox.register("population", tools.initRepeat, list, toolbox.individual)
bit = toolbox.cromo_gen()
ind = toolbox.individual()
pop = toolbox.population(n=3)

print("bit is of type %s and has value\n%s" % (type(bit), bit))
print("ind is of type %s and contains %d bits\n%s" % (type(ind), len(ind), ind))
print("pop is of type %s and contains %d individuals\n%s" % (type(pop), len(pop), pop))<jupyter_output>bit is of type <class 'numpy.ndarray'> and has value
[ 2 10 12 14  4  7 13  9  6  3 11  0 15  1  5  8]
ind is of type <class 'deap.creator.Individual'> and contains 16 bits
[13, 8, 2, 10, 14, 5, 11, 12, 1, 6, 9, 4, 3, 15, 0, 7]
pop is of type <class 'list'> and contains 3 individuals
[[12, 10, 4, 5, 0, 2, 14, 13, 11, 8, 9, 6, 3, 7, 15, 1], [9, 7, 0, 5, 14, 6, 12, 13, 4, 2, 10, 8, 3, 1, 15, 11], [12, 11, 7, 0, 3, 8, 5, 1, 10, 9, 15, 6, 4, 14, 2, 13]]<jupyter_text>Defino Evaluacion, Seleccion y Mutacion<jupyter_code>def evaluarADN(x):
    t=0
    pos=x
    for i in range(0,QUEENS-1):
        for j in range(i+1,QUEENS):
            if amenaza(i,pos[i],j,pos[j]):
                t+=1
    return [t]
toolbox.register("evaluate", evaluarADN)
toolbox.register("mate", tools.cxOrdered)
toolbox.register("mutate", tools.mutShuffleIndexes, indpb=0.20)
toolbox.register("select", tools.selTournament, tournsize=3)<jupyter_output><empty_output><jupyter_text>Pruebo evaluacion<jupyter_code>ind = toolbox.individual()
print(ind)
toolbox.evaluate(ind)<jupyter_output>[1, 4, 2, 0, 9, 7, 15, 8, 6, 12, 11, 14, 5, 13, 3, 10]<jupyter_text>Pruebo mutacion<jupyter_code>ind = toolbox.individual()
print(ind)
toolbox.mutate(ind)
print(ind)<jupyter_output>[0, 3, 7, 2, 14, 9, 15, 5, 8, 13, 11, 12, 6, 10, 4, 1]
[6, 5, 11, 2, 14, 9, 15, 3, 13, 8, 7, 4, 0, 10, 12, 1]<jupyter_text>Pruebo emparejar<jupyter_code>ind = toolbox.individual()
print(ind)
ind2 = toolbox.individual()
print(ind2)
toolbox.mate(ind,ind2)<jupyter_output>[6, 9, 13, 14, 5, 0, 12, 7, 4, 10, 2, 15, 3, 11, 8, 1]
[2, 11, 0, 15, 3, 6, 1, 10, 8, 13, 9, 4, 7, 14, 12, 5]<jupyter_text>Pruebo seleccion<jupyter_code>popu = toolbox.population(n=50)
jeje=toolbox.select(popu,1)
evaluarADN(jeje[0])<jupyter_output><empty_output><jupyter_text>Busco<jupyter_code>def main():    
    pop = toolbox.population(n=1000)
    hof = tools.HallOfFame(1)
    stats = tools.Statistics(lambda ind: ind.fitness.values)
    stats.register("avg", np.mean)
    stats.register("min", np.min)
    stats.register("max", np.max)
    
    pop, logbook = algorithms.eaSimple(pop, toolbox, cxpb=0.5, mutpb=0.2, ngen=10, stats=stats, halloffame=hof, verbose=True)
    
    return pop, logbook, hof
if __name__ == "__main__":
    pop, log, hof = main()
    print("Best individual is: %s\nwith fitness: %s" % (hof[0], hof[0].fitness))
    gen, avg, min_, max_ = log.select("gen", "avg", "min", "max")
    plt.plot(gen, avg, label="average")
    plt.plot(gen, min_, label="minimum")
    plt.plot(gen, max_, label="maximum")
    plt.xlabel("Generation")
    plt.ylabel("Fitness")
    plt.legend(loc="lower right")
tablero16=[1, 12, 0, 7, 11, 4, 14, 9, 13, 5, 2, 6, 15, 10, 8, 3]
tablero=np.empty((reinas,reinas),np.str_)
    for i in range(reinas):
        tablero[i,mejor[i]]='X'
    print(tablero)<jupyter_output><empty_output>
{'fraction_non_alphanumeric': 0.164513839602555, 'fraction_numerical': 0.04840312278211498, 'mean_word_length': 4.262135922330097, 'pattern_counts': {'":': 1, '<': 55, '<?xml version=': 0, '>': 55, 'https://': 0, 'lorem ipsum': 0, 'www.': 0, 'xml': 0}, 'pii_count': 0, 'substrings_counts': 0, 'word_list_counts': {'cursed_substrings.json': 0, 'profanity_word_list.json': 0, 'sexual_word_list.json': 0, 'zh_pornsignals.json': 0}}
{'chain_length': '14', 'dir': 'jupyter-structured-clean-dedup', 'id': '85224', 'license': 'MIT', 'n_tokens_mistral': 3144, 'n_tokens_neox': 2857, 'n_words': 668, 'path': 'Argentina - Mondiola Rock - 90 pts/Practica/TP2/ejercicio 3/Ejercicio 3-Copy1.ipynb', 'repo_name': 'parolaraul/itChallengeML2017', 'size': '7045'}