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
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.
Suscribirse a:
Enviar comentarios (Atom)
No hay comentarios:
Publicar un comentario