miércoles, 4 de julio de 2012

W.T.A.P. Metaheurística de recocido simulado

El meta-algoritmo llamado recocido simulado o enfriamiento simulado nos ayuda a encontrar una buena aproximación al valor óptimo de una función en un espacio de búsqueda grande. Por medio de este meta-algoritmo se busco encontrar un valor óptimo, donde primero tenemos un valor inicial y un valor modificado en el que se busca la diferencia de esos dos valores ( obji – objm ) para después evaluar el exponencial de la diferencia de los dos valores inicial y modificado entre temperatura, luego verificamos que el valor sea menor igual a un número pseudo aleatorio uniforme entre 0 y 1, y en caso de tomar un valor óptimo disminuimos la temperatura asignando la temperatura por un enfriamiento en el cual enfriamiento es un tasa porcentual de disminución a la temperatura. Las modificaciones relevantes ocurrieron en el método de búsqueda en el que se agregaron parámetros como temperatura y enfriamiento. Después se hizo lo anterior mencionado, tuvimos algunos errores ya que tomaba los valores factibles y no factibles y eso se corrigió dividiendo en dos condiciones la condición que verifica si es factible o no el valor.
def busqueda(rei, vuelta, armas, targets, matrix, cupo, temperatura, enfriamiento):
    mejor = sum(targets)
    resultado = None
    listaTabu = list()
    for r in range(rei):
        salida = open('reinicio%d.out' % r, 'w')
        paso = 0
        intentosRestantes = vuelta
        actual = asignacion(armas, targets, matrix)
        objAct = funcionObjetivo(armas, actual, targets, matrix)
        fact = factibilidad(actual, armas)
        mejor = objAct
        resultado = actual
        print >>salida, '%d %f' % (paso, mejor)
        while intentosRestantes > 0:
            exito = False
            paso += 1
            candidato = mejora(armas, targets, matrix, actual)
            objCand = funcionObjetivo(armas, candidato, targets, matrix)
            fact = factibilidad(candidato, armas)
            if tabu(listaTabu, candidato, cupo):
                if fact:
                    if objCand <= objAct: # acepto
                        exito = True
                        intentosRestantes = vuelta
                    elif temperatura > 0:
                        diferencia = (objAct - objCand) / temperatura
                        print diferencia, exp(diferencia)
                        if random.random() <= exp(diferencia):
                            exito = True
                            temperatura *= enfriamiento
                if exito:
                    actual = candidato
                    objAct = objCand
                    if objAct < mejor:
                        mejor = objAct
                        resultado = actual
                    print >>salida, '%d %f %f' % (paso, objAct, mejor)
            if not exito:
                intentosRestantes -= 1 #no mejora
        salida.close()
    return resultado