# ---
# jupyter:
#   jupytext:
#     text_representation:
#       extension: .py
#       format_name: light
#       format_version: '1.5'
#       jupytext_version: 1.14.4
#   kernelspec:
#     display_name: Python 3
#     language: python
#     name: python3
# ---

# +
###  NO OS OLVIDEIS DE PONER EL NÚMERO DE GRUPO Y VUESTROS NOMBRES 
# -

# # Práctica 2 - Sistemas Inteligentes
# ## <NAME> -  Facultad de Informática UCM
# ## Búsqueda local
# La primera parte son ejercicios paso a paso para familiarizarnos con la resolución de problemas sencillos de optimización, como la maximización o minimización de una función, o el problema de la mochila o del viajante, problemas conocidos cuya resolución se ha abordado con técnicas algorítmicas y que vamos a resolver utilizando algoritmos de búsqueda local. 
#
# En la segunda parte de la práctica se pide resolver algun problema de optimización a elegir de la hoja de ejercicios que está colgada en el campus. Los problemas tienen distinto nivel de dificultad por lo que puedes elegir uno o varios. 
# Es importante identificar problemas de optimización para los que los algoritmos de búsqueda local sean más adecuados que los problemas de búsqueda en espacio de estados vistos en la práctica 1. Algunos ejemplos son: el problema de las bolsas (14), el sudoku (21), el problema de las mesas (23), el problema de adjudicación de proyectos (26), el problema del ganadero (27) y el problema de la asignación de tareas (28).
#
#

# ### Algoritmo de escalada
# Hill Climbing es un algoritmo de búsqueda local heurística utilizada para problemas de optimización.
# Esta solución puede o no ser el óptimo global. El algoritmo es una variante del algoritmo de generación y prueba.
# <br>
# En general, el algoritmo funciona de la siguiente manera:
# - Evaluar el estado inicial.
# - Si es igual al estado del objetivo, terminamos.
# - Encuentra un estado vecino al estado actual
# - Evaluar este estado. Si está más cerca del estado objetivo que antes, reemplace el estado inicial con este estado y repita estos pasos.
# <br>
# Usaremos la implementación de AIMA que está en el módulo search.py
#
#     def hill_climbing(problem):
#         """From the initial node, keep choosing the neighbor with highest value,
#         stopping when no neighbor is better. [Figure 4.2]"""
#         current = Node(problem.initial)
#         while True:
#             neighbors = current.expand(problem)
#             if not neighbors:
#                 break
#             neighbor = argmax_random_tie(neighbors,
#                                      key=lambda node: problem.value(node.state))
#             if problem.value(neighbor.state) <= problem.value(current.state):
#                 break
#             current = neighbor
#         return current.state
#

# Como ejemplo, vamos a definir un problema sencillo de encontrar el punto más alto en una rejilla. Este problema está definido en el módulo search.py como PeakFindingProblem. Lo reproducimos aquí y creamos una rejilla simple.

from search import *

initial = (0, 0)
grid = [[3, 7, 2, 8], [5, 2, 9, 1], [5, 3, 3, 1]]

# +
# Pre-defined actions for PeakFindingProblem
directions4 = { 'W':(-1, 0), 'N':(0, 1), 'E':(1, 0), 'S':(0, -1) }
directions8 = dict(directions4) 
directions8.update({'NW':(-1, 1), 'NE':(1, 1), 'SE':(1, -1), 'SW':(-1, -1) })

class PeakFindingProblem(Problem):
    """Problem of finding the highest peak in a limited grid"""

    def __init__(self, initial, grid, defined_actions=directions4):
        """The grid is a 2 dimensional array/list whose state is specified by tuple of indices"""
        Problem.__init__(self, initial)
        self.grid = grid
        self.defined_actions = defined_actions
        self.n = len(grid)
        assert self.n > 0
        self.m = len(grid[0])
        assert self.m > 0

    def actions(self, state):
        """Returns the list of actions which are allowed to be taken from the given state"""
        allowed_actions = []
        for action in self.defined_actions:
            next_state = vector_add(state, self.defined_actions[action])
            if next_state[0] >= 0 and next_state[1] >= 0 and next_state[0] <= self.n - 1 and next_state[1] <= self.m - 1:
                allowed_actions.append(action)

        return allowed_actions

    def result(self, state, action):
        """Moves in the direction specified by action"""
        return vector_add(state, self.defined_actions[action])

    def value(self, state):
        """Value of a state is the value it is the index to"""
        x, y = state
        assert 0 <= x < self.n
        assert 0 <= y < self.m
        return self.grid[x][y]



# -

problem = PeakFindingProblem(initial, grid, directions4)

## Resolvemos el problema con escalada. Comenta la solución encontrada. ¿es óptima? ¿cómo se puede mejorar la resolución del problema con este algoritmo? 
hill_climbing(problem)

problem.value(hill_climbing(problem))


## copiamos aqui el codigo de search.py
def hill_climbing(problem):
    """From the initial node, keep choosing the neighbor with highest value,
    stopping when no neighbor is better. [Figure 4.2]"""
    current = Node(problem.initial)
    while True:
        neighbors = current.expand(problem)
        if not neighbors:
            break
        neighbor = argmax_random_tie(neighbors,
                                     key=lambda node: problem.value(node.state))
        if problem.value(neighbor.state) <= problem.value(current.state):
            break
        current = neighbor
    return current.state


solution = problem.value(hill_climbing(problem))
solution

# ### Ejercicio 1.  Resuelve el problema anterior de encontrar el punto máximo en una rejilla. Comenta y razona los resultados obtenidos en distintas rejillas de mayor tamaño con el algoritmo de escalada por máxima pendiente. 
# Observar los posibles efectos de usar distinto número de direcciones y de número de ejecuciones para encontrar el mejor resultado posible. 
# Es muy importante comentar los resultados. 
# Prueba con varias rejillas e indica las propiedades de optimalidad (en que % de las pruebas obtiene la solución óptima), tiempo, completitud. 

solution = problem.value(hill_climbing(problem))
solution

solutions = {problem.value(hill_climbing(problem)) for i in range(100)}
max(solutions)

# Ejemplo de rejilla para pruebas.
#
# grid2 = [[0.00, 0.00, 0.00, 0.00, 0.00, 0.00, 0.00, 0.00, 0.00],
#         [0.20, 0.20, 0.20, 0.20, 0.00, 0.00, 0.00, 0.00, 0.00],
#         [0.20, 0.20, 0.20, 0.40, 0.40, 0.00, 0.00, 0.00, 0.00],
#         [0.00, 0.00, 0.00, 0.00, 0.00, 0.00, 0.00, 0.70, 1.40],
#         [2.20, 1.80, 0.70, 0.00, 0.00, 0.00, 0.00, 0.00, 0.00],
#         [2.20, 1.80, 4.70, 6.50, 4.30, 1.80, 0.70, 0.00, 0.00],
#         [0.00, 0.00, 0.00, 0.00, 0.00, 0.00, 11.2, 0.70, 1.40],
#         [2.20, 1.80, 0.70, 0.00, 0.00, 9.00, 0.00, 0.00, 0.00],
#         [2.20, 1.80, 4.70, 6.50, 4.30, 1.80, 0.70, 0.00, 0.00],
#         [0.00, 0.00, 0.00, 0.00, 0.00, 0.00, 0.00, 0.70, 1.40],
#         [2.20, 1.80, 0.70, 0.00, 0.00, 0.00, 0.00, 0.00, 0.00],
#         [2.20, 1.80, 4.70, 8.50, 4.30, 1.80, 0.70, 0.00, 0.00]]

problem.value(hill_climbing(problem))

# ### Algoritmos genéticos
#

# Se define una clase ProblemaGenetico que incluye los elementos necesarios para la representación de un problema de optimización que se va a resolver con un algoritmo genético. Los elementos son los que hemos visto en clase:
#
#  - genes: lista de genes usados en el genotipo de los estados.
#  - longitud_individuos: longitud de los cromosomas
#  - decodifica: función de obtiene el fenotipo a partir del genotipo.
#  - fitness: función de valoración.
#  - muta: función de mutación de un cromosoma 
#  - cruza: función de cruce de un par de cromosomas

import random


class ProblemaGenetico(object):
        def __init__(self, genes,fun_dec,fun_muta , fun_cruza, fun_fitness,longitud_individuos):
            self.genes = genes
            self.fun_dec = fun_dec
            self.fun_cruza = fun_cruza
            self.fun_muta = fun_muta
            self.fun_fitness = fun_fitness
            self.longitud_individuos = longitud_individuos
            """Constructor de la clase"""
                
        def decodifica(self, genotipo):
            """Devuelve el fenotipo a partir del genotipo"""
            fenotipo = self.fun_dec(genotipo)
            return fenotipo
        def muta(self, cromosoma,prob):
            """Devuelve el cromosoma mutado"""   
            mutante = self.fun_muta(cromosoma,prob)
            return mutante
        def cruza(self, cromosoma1, cromosoma2):         
            """Devuelve el cruce de un par de cromosomas"""
            cruce = self.fun_cruza(cromosoma1,cromosoma2)
            return cruce 
        def fitness(self, cromosoma):    
            """Función de valoración"""
            valoracion = self.fun_fitness(cromosoma)
            return valoracion


# En primer lugar vamos a definir una instancia de la clase anterior correspondiente al problema de optimizar (maximizar o minimizar) la función cuadrado x^2 en el conjunto de los números naturales menores que 2^{10}.
#
# Vamos a usar este problema unicamente como ejemplo (ya que sabemos la solución por otros métodos matemáticos) para ver todos los elementos de los algoritmos genéticos y poder observar el comportamiento de distintas configuraciones.

# +
# Será necesaria la siguiente función que interpreta una lista de 0's y 1's como un número natural:  
# La siguiente función que interpreta una lista de 0's y 1's como
# un número natural:  

def binario_a_decimal(x):
    return sum(b*(2**i) for (i,b) in enumerate(x)) 


# -

list(enumerate([1, 0, 0]))


# +
# En primer luegar usaremos la clase anterior para representar el problema de optimizar (maximizar o minimizar)
# la función cuadrado en el conjunto de los números naturales menores que
# 2^{10}.

# Tenemos que definir funciones de cruce, mutación y fitness para este problema.

def fun_cruzar(cromosoma1, cromosoma2):
    """Cruza los cromosomas por la mitad"""
    l1 = len(cromosoma1)
    l2 = len(cromosoma2)
    cruce1 = cromosoma1[0:l1//2]+cromosoma2[l1//2:l2]
    cruce2 = cromosoma2[0:l2//2]+cromosoma1[l2//2:l1]
    return [cruce1,cruce2]

def fun_mutar(cromosoma,prob):
    """Elige un elemento al azar del cromosoma y lo modifica con una probabilidad igual a prob"""
    l = len(cromosoma)
    p = random.randint(0,l-1)
    if prob > random.uniform(0,1):
        cromosoma[p] =  (cromosoma[p]+1)%2
    return cromosoma

def fun_fitness_cuad(cromosoma):
    """Función de valoración que eleva al cuadrado el número recibido en binario"""
    n = binario_a_decimal(cromosoma)**2
    return n

cuadrados = ProblemaGenetico([0,1],binario_a_decimal,fun_mutar, fun_cruzar, fun_fitness_cuad,10)
# -

# Una vez definida la instancia cuadrados que representa el problema genético, probar alguna de las funciones definidas en la clase anterior, para esta instancia concreta. Por ejemplo:

cuadrados.decodifica([1,0,0,0,1,1,0,0,1,0,1])
# Salida esperada: 1329

cuadrados.fitness([1,0,0,0,1,1,0,0,1,0,1])
# Salida esperada: 1766241

cuadrados.muta([1,0,0,0,1,1,0,0,1,0,1],0.1)
# Posible salida: [1, 0, 0, 0, 1, 1, 0, 0, 1, 0, 1]

cuadrados.muta([1,0,0,0,1,1,0,0,1,0,1],0.1)
# Posible salida: [0, 0, 0, 0, 1, 1, 0, 0, 1, 0, 1]

cuadrados.cruza([1,0,0,0,1,1,0,0,1,0,1],[0,1,1,0,1,0,0,1,1,1])
# Posible salida: [[1, 0, 0, 0, 1, 0, 0, 1, 1, 1], [0, 1, 1, 0, 1, 1, 0, 0, 1, 0, 1]]

# ### Ejercicio 2
#
#    - Definir una función poblacion_inicial(problema_genetico,tamaño), para definir una población inicial de un tamaño dado, para una instancia dada de la clase anterior ProblemaGenetico
#
# sugerencia: usar random.choice
#
#    - Definir una función de cruce que recibe una instancia de Problema_Genetico y una población de padres (supondremos que hay un número par de padres), obtiene la población resultante de cruzarlos de dos en dos (en el orden en que aparecen)
#
# cruza_padres(problema_genetico,padres)
#
#    - Definir la función de mutación que recibe una instancia de Problema_Genetico, una población y una probabilidad de mutación, obtiene la población resultante de aplicar operaciones de mutación a cada individuo llamando a la función muta definida para el problema genético.
# muta_individuos(problema_genetico, poblacion, prob)

# + active=""
# def poblacion_inicial(problema_genetico, size):
#     return .... 
#     
# Ejemplo de llamada:
# poblacion_inicial(cuadrados,10)

# + active=""
# def cruza_padres(problema_genetico,padres):
#     
#     return ..........
#     

# + active=""
# p1 = [[1, 1, 0, 1, 0, 1, 0, 0, 0, 1],
#       [0, 1, 0, 1, 0, 0, 1, 0, 1, 1],
#       [0, 0, 1, 0, 0, 0, 1, 1, 1, 0],
#       [0, 0, 1, 1, 1, 1, 1, 1, 1, 0],
#       [0, 1, 1, 0, 0, 0, 0, 0, 0, 0],
#       [1, 0, 1, 1, 1, 0, 1, 1, 0, 1]]
#
# cruza_padres(cuadrados,p1)
# # Posible salida
# # [[1, 1, 0, 1, 0, 0, 1, 0, 1, 1],
# #  [0, 1, 0, 1, 0, 1, 0, 0, 0, 1],
# #  [0, 0, 1, 1, 1, 1, 1, 1, 1, 0],
# #  [0, 0, 1, 0, 0, 0, 1, 1, 1, 0],
# #  [0, 1, 1, 1, 1, 0, 1, 1, 0, 1],
# #  [1, 0, 1, 0, 0, 0, 0, 0, 0, 0]]

# + active=""
# Este os doy hecho:
#
# def muta_individuos(problema_genetico, poblacion, prob):
#     return [problema_genetico.muta(x, prob) for x in poblacion]
# -

muta_individuos(cuadrados,p1,0.5)
# Posible salida:
#  [[1, 1, 0, 1, 0, 1, 0, 0, 0, 1],
#   [0, 1, 0, 1, 0, 0, 1, 0, 0, 1],
#   [0, 0, 1, 0, 0, 0, 1, 0, 1, 0],
#   [0, 0, 1, 1, 1, 1, 1, 1, 1, 0],
#   [0, 1, 0, 0, 0, 0, 0, 0, 0, 0],
#   [1, 0, 1, 1, 1, 0, 1, 1, 0, 1]]

p1 = [[1, 1, 0, 1, 0, 1, 0, 0, 0, 1],
      [0, 1, 0, 1, 0, 0, 1, 0, 1, 1],
      [0, 0, 1, 0, 0, 0, 1, 1, 1, 0],
      [0, 0, 1, 1, 1, 1, 1, 1, 1, 0],
      [0, 1, 1, 0, 0, 0, 0, 0, 0, 0],
      [1, 0, 1, 1, 1, 0, 1, 1, 0, 1]]

muta_individuos(cuadrados,p1,0.5)


# ### Ejercicio 3
#
# Se pide definir una función de selección mediante torneo de n individuos de una población.  
# La función recibe como entrada:
#  - una instancia de la clase ProblemaGenetico
#  - una población
#  - el número n de individuos que vamos a seleccionar
#  - el número k de participantes en el torneo
#  - un valor opt que puede ser o la función max o la función min (dependiendo de si el problema es de maximización o de minimización, resp.).
#
# seleccion\_por\_torneo(problema_genetico,poblacion,n,k,opt) 
#
# INDICACIÓN: Usar random.sample para seleccionar k elementos de una secuencia. 
# Por ejemplo, random.sample(population=[2,5,7,8,9], k=3) devuelve [7,5,8]. 

def seleccion_por_torneo(problema_genetico, poblacion, n, k, opt):
    """Selección por torneo de n individuos de una población. Siendo k el nº de participantes
        y opt la función max o min."""
    seleccionados = []
     # un individuo puede ganar varias selecciones en el torneo. No eliminar repetidos.
    return seleccionados  


#Ejemplo
seleccion_por_torneo(cuadrados, poblacion_inicial(cuadrados,8),3,6,max)
# Posible salida: [[1, 1, 1, 1, 1, 0, 0, 0, 1, 1], [1, 0, 0, 1, 1, 1, 0, 1, 0, 1], [1, 1, 1, 1, 0, 1, 1, 1, 0, 1]]


seleccion_por_torneo(cuadrados, poblacion_inicial(cuadrados,8),3,6,min)
# [[0, 0, 1, 1, 0, 1, 1, 0, 0, 0], [1, 0, 1, 0, 1, 1, 1, 0, 0, 0], [1, 1, 0, 1, 0, 0, 1, 0, 1, 0]]

# +
# La siguiente función implementa una posibilidad para el algoritmo genético completo: 
# inicializa t = 0 
# Generar y evaluar la Población P(t)
# Mientras no hemos llegado al número de generaciones fijado:  t < nGen
#    P1 = Selección por torneo de (1-size)·p individuos de P(t)
#    P2 = Selección por torneo de (size·p) individuos de P(t)
#    Aplicar cruce en la población P2
#    P4 = Union de P1 y P3
#    P(t+1) := Aplicar mutación P4 
#    Evalua la población P(t+1) 
#    t:= t+1
        
# Sus argumentos son:
# problema_genetico: una instancia de la clase ProblemaGenetico con la representación adecuada del problema de optimización 
# que se quiere resolver.
# k: número de participantes en los torneos de selección.
# opt: max ó min, dependiendo si el problema es de maximización o de minimización. 
# nGen: número de generaciones (que se usa como condición de terminación)
# size: número de individuos en cada generación
# prop_cruce: proporción del total de la población que serán padres. 
# prob_mutación: probabilidad de realizar una mutación de un gen.

def algoritmo_genetico(problema_genetico,k,opt,ngen,size,prop_cruces,prob_mutar):
    poblacion= poblacion_inicial(problema_genetico,size)
    n_padres=round(size*prop_cruces)
    n_padres= int (n_padres if n_padres%2==0 else n_padres-1)
    n_directos = size-n_padres
    for _ in range(ngen):
        poblacion= nueva_generacion(problema_genetico,k,opt,poblacion,n_padres, n_directos,prob_mutar)

    mejor_cr= opt(poblacion, key=problema_genetico.fitness)
    mejor=problema_genetico.decodifica(mejor_cr)
    return (mejor,problema_genetico.fitness(mejor_cr)) 



# -

# La función auxiliar nueva_generacion(problema_genetico,poblacion,n_padres,n_directos,prob_mutar) que dada una población calcula la siguiente generación.

#Definir la función nueva_generacion
def nueva_generacion(problema_genetico, k,opt, poblacion, n_padres, n_directos, prob_mutar):
    padres2 = seleccion_por_torneo(problema_genetico, poblacion, n_directos, k,opt) 
    padres1 = seleccion_por_torneo(problema_genetico, poblacion, n_padres , k, opt)
    cruces =  cruza_padres(problema_genetico,padres1)
    generacion = padres2+cruces
    resultado_mutaciones = muta_individuos(problema_genetico, generacion, prob_mutar)
    return resultado_mutaciones


# ### Ejercicio 4.  Ejecutar el algoritmo genético anterior, para resolver el problema anterior (tanto en minimización como en maximización).  
#
# Hacer una valoración de resultados y comentarios sobre el comportamiento del algoritmmo. 
# En la resolución del problema hay que tener en cuenta que el algoritmo genético devuelve un par con el mejor fenotipo encontrado y su valoración.
#
# Observar como afectan los párametros, probabilidades y presión de selección a la calidad de los resultados. 
#
# Opcionalmente se puede modificar la función a optimizar para que no sea tan simple como x^2 
# Puedes cambiar la funcion X^2 por otra función cambiando la función de fitness.
#

# + active=""
# Por ejemplo 
# funcion_objetivo(x, y, z):
#        f= ((x**3 - y**2) * z) - x**4
#        return(f)
# -

algoritmo_genetico(cuadrados,3,min,20,10,0.7,0.1)
# Salida esperada: (0, 0)

algoritmo_genetico(cuadrados,3,max,20,10,0.7,0.1)
# Salida esperada: (1023, 1046529)

# + active=""
# Elige la mejor configuración de parámetros y luego puedes realizar varias ejecuciones para obtener el mejor resultado posible.
#
# import numpy as np
# arr = np.array([algoritmo_genetico(cuadrados, 3, min, 20, 10, 0.7, 0.1)[0] for _ in range(1000)])
# m = np.mean(arr)
# v = np.std(arr)
# print(f"{m} +- {v} expected 0")
#
# arr = np.array([algoritmo_genetico(cuadrados, 3, max, 20, 10, 0.7, 0.1)[0] for _ in range(1000)])
# m = np.mean(arr)
# v = np.std(arr)
# print(f"{m} +- {v} expected 1023")
# -

# ### Pruebas para determinar cuales son los mejores parámetros concretos

# #### Presión de selección

# #### Proporción de cruce

# #### Probabilidad de mutación

# ##  El problema de la mochila 

# Se plantea el típico problema de la mochila en el que dados n objetos de pesos conocidos pi y valor vi (i=1,...,n) hay que elegir cuáles se meten en una mochila que soporta un peso P máximo. La selección debe hacerse de forma que se máximice el valor de los objetos introducidos sin superar el peso máximo.

# ### Ejercicio 5
# Se pide definir la representación del problema de la mochila usando genes [0,1] y longitud de los individuos n.
#
# Los valores 1 ó 0 representan, respectivamente, si el objeto se introduce o no en la mochila Tomados de izquerda a derecha, a partir del primero que no cabe, se consideran  todos fuera de la mochila,independientemente del gen en su posición. De esta manera, todos los individuos representan candidatos válidos.
#
# El numero de objetos n determina la longitud de los individuos de la población.
# En primer lugar es necesario definir una función de decodificación de la mochila que recibe como entrada:
# * un cromosoma (en este caso, una lista de 0s y 1s, de longitud igual a n_objetos) 
# * n: número total de objetos de la mochila
# * pesos: una lista con los pesos de los objetos
# * capacidad: peso máximo de la mochila.
# La función decodifica recibe (cromosoma, n, pesos, capacidad) y devuelve una lista de 0s y 1s que indique qué objetos están en la mochila y cuáles no (el objeto i está en la mochila si y sólo si en la posición i-ésima de la lista hay un 1). Esta lista se obtendrá a partir del cromosoma, pero teniendo en cuenta que a partir del primer objeto que no quepa, éste y los siguientes se consideran fuera de la mochila, independientemente del valor que haya en su correspondiente posición de cromosoma. 

def decodifica_mochila(cromosoma, n, pesos, capacidad):
    peso_en_mochila = 0
    l = []
    for i in range(n):
        if cromosoma[i] == 1 and peso_en_mochila + pesos[i] <= capacidad:
            l.append(1)
            peso_en_mochila += pesos[i]
        elif cromosoma[i]== 0 or peso_en_mochila + pesos[i] > capacidad:
            l.append(0)
    return l 


decodifica([1,1,1,1,1], 5, [2,3,4,5,1], 5)


# Para definir la función de evaluación (fitness) necesitamos calcular el valor total de los objetos que están dentro de la mochila que representa el cromosoma según la codificación utilizada en la función anterior. 
#
# Se pide la función fitness (cromosoma, n_objetos, pesos, capacidad, valores) donde los parámetros son los mismos que en la función anterior, y valores es la lista de los valores de cada objeto
#
# fitness(cromosoma, n_objetos, pesos, capacidad, valores)
#
# Ejemplo de uso:
#    fitness([1,1,1,1], 4, [2,3,4,5], 4, [7,1,4,5])
#    7

def fitness_mochila(cromosoma, n_objetos, pesos, capacidad, valores):
    ......
    return valor


fitness_mochila([1,1,1,1], 4, [2,3,4,5], 4, [7,1,4,5])

# Damos tres instancias concretas del problema de la mochila. Damos también sus soluciones optimas, para que se puedan comparar con los resultados obtenidos por el algoritmo genético:

# +
# Problema de la mochila 1:
# 10 objetos, peso máximo 165
pesos1 = [23,31,29,44,53,38,63,85,89,82]
valores1 = [92,57,49,68,60,43,67,84,87,72]

# Solución óptima= [1,1,1,1,0,1,0,0,0,0], con valor 309

# +
# Problema de la mochila 2:
# 15 objetos, peso máximo 750

pesos2 = [70,73,77,80,82,87,90,94,98,106,110,113,115,118,120]
valores2 = [135,139,149,150,156,163,173,184,192,201,210,214,221,229,240]

# Solución óptima= [1,0,1,0,1,0,1,1,1,0,0,0,0,1,1] con valor 1458

# +
# Problema de la mochila 3:
# 24 objetos, peso máximo 6404180
pesos3 = [382745,799601,909247,729069,467902, 44328,
       34610,698150,823460,903959,853665,551830,610856,
       670702,488960,951111,323046,446298,931161, 31385,496951,264724,224916,169684]
valores3 = [825594,1677009,1676628,1523970, 943972,  97426,
       69666,1296457,1679693,1902996,
       1844992,1049289,1252836,1319836, 953277,2067538, 675367,
       853655,1826027, 65731, 901489, 577243, 466257, 369261]

# Solución óptima= [1,1,0,1,1,1,0,0,0,1,1,0,1,0,0,1,0,0,0,0,0,1,1,1] con valoración 13549094
# -

# ### Ejercicio 6
#
# Definir variables m1g, m2g y m3g, referenciando a instancias de Problema_Genetico que correspondan, respectivamente, a los problemas de la mochila anteriores. Resuelve los problemas y comentar los resultados obtenidos en cuanto a eficiencia y calidad de los resultados obtenidos.

# Algunas de las salidas posibles variando los parámetros.

# +
# >>> algoritmo_genetico_t(m1g,3,max,100,50,0.8,0.05)
# ([1, 1, 1, 1, 0, 1, 0, 0, 0, 0], 309)

# >>> algoritmo_genetico_t(m2g,3,max,100,50,0.8,0.05)
# ([1, 1, 1, 0, 0, 0, 0, 1, 1, 0, 1, 1, 1, 0, 0], 1444)
# >>> algoritmo_genetico_t(m2g,3,max,200,100,0.8,0.05)
# ([0, 0, 1, 0, 1, 1, 1, 1, 1, 1, 0, 0, 1, 0, 0], 1439)
# >>> algoritmo_genetico_t(m2g,3,max,200,100,0.8,0.05)
# ([1, 0, 1, 0, 1, 0, 1, 1, 1, 0, 0, 0, 0, 1, 1], 1458)

# >>> algoritmo_genetico_t(m3g,5,max,400,200,0.75,0.1)
# ([1, 1, 0, 1, 0, 1, 1, 0, 1, 1, 1, 0, 1, 0, 0, 1, 0, 0, 0, 0, 0, 1, 0, 0], 13518963)
# >>> algoritmo_genetico_t(m3g,4,max,600,200,0.75,0.1)
# ([1, 1, 0, 1, 1, 1, 1, 0, 0, 1, 1, 0, 1, 0, 0, 1, 1, 0, 0, 1, 0, 1, 0, 0], 13524340)
# >>> algoritmo_genetico_t(m3g,4,max,1000,200,0.75,0.1)
# ([1, 1, 0, 1, 0, 0, 0, 0, 1, 1, 1, 0, 1, 0, 0, 1, 1, 0, 0, 0, 0, 0, 0, 0], 13449995)
# >>> algoritmo_genetico_t(m3g,3,max,1000,100,0.75,0.1)
# ([1, 1, 0, 0, 0, 1, 1, 0, 1, 1, 1, 0, 1, 1, 0, 1, 1, 0, 0, 0, 0, 0, 0, 0], 13412953)
# >>> algoritmo_genetico_t(m3g,3,max,2000,100,0.75,0.1)
# ([0, 1, 0, 1, 0, 1, 0, 0, 1, 1, 1, 0, 1, 1, 0, 1, 0, 0, 0, 0, 0, 0, 0, 0], 13366296)
# >>> algoritmo_genetico_t(m3g,6,max,2000,100,0.75,0.1)
# ([1, 1, 0, 1, 1, 1, 0, 0, 0, 1, 1, 0, 1, 0, 0, 1, 0, 0, 0, 0, 0, 1, 1, 1], 13549094)

# +

def fitness_mochila_1(cromosoma):
    v = fitness_mochila(cromosoma, 10, pesos1, 165, valores1)
    return v
def decodifica_mochila_1(cromosoma):
    v = decodifica_mochila(cromosoma, 10, pesos1, 165)
    return v
m1g = ProblemaGenetico([0,1], decodifica_mochila_1, fun_mutar, fun_cruzar, fitness_mochila_1,10)

def fitness_mochila_2(cromosoma):
    v = fitness_mochila(cromosoma, 15, pesos2, 750, valores2)
    return v
def decodifica_mochila_2(cromosoma):
    v = decodifica_mochila(cromosoma, 14, pesos2, 750)
    return v
m2g = ProblemaGenetico([0,1], decodifica_mochila_2, fun_mutar, fun_cruzar, fitness_mochila_2,15)

def fitness_mochila_3(cromosoma):
    v = fitness_mochila(cromosoma, 24, pesos3,6404180 , valores3)
    return v
def decodifica_mochila_3(cromosoma):
    v = decodifica_mochila(cromosoma, 24, pesos3, 6404180)
    return v
m3g = ProblemaGenetico([0,1], decodifica_mochila_3, fun_mutar, fun_cruzar, fitness_mochila_3,24)

# -

algoritmo_genetico(m3g,5,max,400,200,0.75,0.1)

# ### Ejercicio 7
# Resolver mediante una configuración de un algoritmo genético el problema del cuadrado mágico que consiste en colocar en un cuadrado n × n los números naturales de 1 a n^2, 
# de tal manera que las filas, las columnas y las diagonales principales sumen los mismo. 
# Ejemplo: una solucion para n= 3
#     
#     4 3 8
#     9 5 1
#     2 7 6
#     
# - Dimensionn del cuadrado: N
# - Suma común: SUMA=(N·(N^2 + 1))/2
#     
#     Comenta el resultado y el rendimiento del algoritmo para distintos parámetros.
#     
#
#     
#     

# ###  Enfriamiento simulado ( simulated annealing)
# El algoritmo de enfriamiento simulado puede manejar las situaciones de óptimo local o mesetas típicas en algoritmos de escalada.
# El enfriamiento simulado es bastante similar a la escalada pero en lugar de elegir el mejor movimiento en cada iteración, elige un movimiento aleatorio. Si este movimiento aleatorio nos acerca al óptimo global, será aceptado, pero si no lo hace, el algoritmo puede aceptar o rechazar el movimiento en función de una probabilidad dictada por la temperatura. Cuando la temperatura es alta, es más probable que el algoritmo acepte un movimiento aleatorio incluso si es malo. A bajas temperaturas, solo se aceptan buenos movimientos, con alguna excepción ocasional. Esto permite la exploración del espacio de estado y evita que el algoritmo se atasque en el óptimo local.
#
# Usaremos la implementación de AIMA del modulo search.py
#
# def simulated_annealing(problem, schedule=exp_schedule()):
# """[Figure 4.5] CAUTION: This differs from the pseudocode as it
# returns a state instead of a Node."""
# current = Node(problem.initial)
# for t in range(sys.maxsize):
#     T = schedule(t)
#     if T == 0:
#         return current.state
#     neighbors = current.expand(problem)
#     if not neighbors:
#         return current.state
#     next_choice = random.choice(neighbors)
#     delta_e = problem.value(next_choice.state) - problem.value(current.state)
#     if delta_e > 0 or probability(math.exp(delta_e / T)):
#         current = next_choice

# Como hemos visto en clase hay varios métodos de enfriamiento (scheduling routine) 
# Se puede variar el método de enfriamiento. En la implementación actual estamos usando el método de enfriamiento exponencial (que se pasa como parámetro). 
#
#     def exp_schedule(k=20, lam=0.005, limit=100):
#         """One possible schedule function for simulated annealing"""
#         return lambda t: (k * math.exp(-lam * t) if t < limit else 0)

# Resuelve alguno de los problemas vistos en esta práctica usando el algoritmo de enfriamiento simulado y comenta los resultados obtenidos.  Por ejemplo, puedes utilizar el problema del máximo en una rejilla resuelto con Escalada en el ejercicio 1.

problem = PeakFindingProblem(initial, grid, directions4)

## Ejecuta varias veces esta celda. ¿Obtienes siempre el mismo resultado? ¿encuentra la solución óptima?
simulated_annealing(problem)

problem.value (simulated_annealing(problem))

# +
# Lo resolvemos con 100 ejecuciones del algoritmo de enfriamiento simulado. ¿encuentra la solución óptima?

solutions = {problem.value(simulated_annealing(problem)) for i in range(100)}
max(solutions)
# -

# ### Ejercicio 8.  
# Resuelve el problema anterior de encontrar el punto máximo en una rejilla. Comenta y razona los resultados con enfriamiento simulado comparandolo con la resolución con escalada del ejercicio 1.
#
#

StarcoderdataJupyterScriptsDedupFiltered