Max Hernandez: Metaheurística de recocido simulado

[Imagen obtenida de: http://www.swissmetal.es/images/fundicion999.jpg]

Para el día de hoy analizamos el algoritmo de recocido simulado. Este algoritmo se basa en El nombre e inspiración viene del proceso de recocido del acero y cerámicas, una técnica que consiste en calentar y luego enfriar lentamente el material para variar sus propiedades físicas.
El calor causa que los átomos aumenten su energía y que puedan así desplazarse de sus posiciones iniciales (un mínimo local de energía); el enfriamiento lento les da mayores probabilidades de recristalizar en configuraciones con menor energía que la inicial (mínimo global).

El código es bastante parecido al que ya hemos utilizado anteriormente al que usamos para búsqueda tabú puesto que lo único que hicimos fue añadir la pequeña simulación de Markov si la solución no es mejorada para saber si aceptarla. Además de que se agregaron las variables de temperatura y de factor de enfriamiento para calcular la probabilidad de ser aceptadas.

"recocido_simulado.py"

    def recocido_simulado(self, maxReinicios, maxIntentos, cupo, temperaturaInicial, enfriamientoInicial):
        modificado = [] # Solucion modificada
        actual = [] # Solucion actual
        lista = [] # Lista de soluciones para la busqueda tabu
        intentos = 0 # Variable contador para los intentos
        mejor = self.instancia_inicial()
        
        for reinicios in range(maxReinicios):# Por cada reinicio
            actual = self.instancia_inicial()# genera una nueva instancia
        
            salida = open(('reinicio%d.out' % reinicios), 'w') # luego abre un archivo para guardar los datos a graficar
            paso = 0 # Inicializa los contadores, este contador sera para cada que haya una mejora
            intentos = 0 # Este sera para el numero de intentos
            temperatura = float(temperaturaInicial)
            enfriamiento = enfriamientoInicial

            lista = [] # crea una lista

            while intentos <= maxIntentos: # por cada Reintento osea cada que se genera una nueva solucion inicial hay una cantidad de intentos de mejorar la solucion mientas que no se cumplan estos intentos
                modificado = self.copiar(actual) # Se obtiene una copia de la solucion actual

                maximo = [self.sumatoria(modificado[0]), 0] # Se encuentra el procesador que tarda mas tiempo
                for i in range(1, len(modificado)): # obteniendo la sumatoria de tiempo que tarda cada procesador
                    suma = self.sumatoria(modificado[i])
                    if suma > maximo[0]: # Escogiendo el que tarda mas
                        maximo[0] = suma
                        maximo[1] = i
                procesador_origen = maximo[1] # Este procesador que toma mas tiempo sera al que se le quite una tarea para mandarla a otro
            
                while True: # de forma aleatoria se escoje procesador al cual asignar la tarea que se quite a la tarea con mas tiempo
                    procesador_destino = random.randint(0, self.nProcessors-1) 
                    if len(modificado[procesador_destino]) > 0 and procesador_origen != procesador_destino: #Si el procesador es el mismo que el de origen, se vuelve a escojer otro de forma aleatoria
                        break

                if len(modificado[procesador_origen]) == 0: #Ahora de forma aleatoria se escoje la tarea que se va a cambiar de procesador
                    tarea_origen = 0 #El if igual a cero es por que la funcion random no deja generar numeros de 0 a 0
                else:
                    tarea_origen = random.randint(0, len(modificado[procesador_origen])-1 )

                modificado[procesador_destino].append( modificado[procesador_origen].pop(tarea_origen) ) # la funcion pop elimina el valor de la lista y regresa ese mismo valor que despues es anadido al final de la lista destino con el metodo append()

                if self.tabu(lista,  modificado, cupo): # Verifica que la solucion este en la lista tabu, si no esta agregua dicha solucion y regresa True, en caso de ya estar solo regresa False y  la lista tabu queda igual
                    objetivo_modificado = self.funcion_objetivo(modificado)
                    objetivo_actual = self.funcion_objetivo(actual)
                    if objetivo_modificado <= objetivo_actual: # si la solucion modificada es mejor que la actual 
                        print >>salida, '%d %f' % (paso, objetivo_modificado) # Se grafica la nueva mejor solucion
                        paso += 1
                        actual = self.copiar(modificado) # Y ahora la solucion donde estamos actualmente es la que acabamos de modificar
                    else:
                        delta = objetivo_actual - objetivo_modificado

                        if random.random() <= math.exp( delta/temperatura ):
                            print >>salida, '%d %f' % (paso, objetivo_modificado) # Se grafica la nueva mejor solucion
                            paso += 1
                            actual = self.copiar(modificado) # Y ahora la solucion donde estamos actualmente es la que acabamos                         
                            temperatura *= enfriamiento
                        else:
                            intentos +=1

                else:
                    intentos +=1

                # Aqui termina el while de intentos de mejora de la solucion generada
            salida.close()# Se cierra el archivo 
            if self.funcion_objetivo(actual) <= self.funcion_objetivo(mejor): # Si la solucion es mejor que las encontradas en los pasados reintentos la guarda
                mejor = actual

        return mejor # Regresa la mejor solucion encontrada

Gráficas
Las siguientes gráficas, la primera muestra como se comporta el algoritmo mientras va cambiado de soluciones y la segunda muestra la mejor solución encontrada. La cantidad de soluciones iniciales generadas fueron 30 y la cantidad de intentos para mejorar dicha solución fueron 200 para todas las corridas.

Para Temperatura= 1000 y Factor de enfriamiento= 0.55 :