Para optimizar nuestra respuesta se utilizo la búsqueda tabú que consiste en ir descartando asignaciones que ya se usaron para evitar repetir la misma asignación, lo que hace es usar el candidato que es la asignación de una mejor función objetivo comparando con la lista tabú para evitar repetir la misma asignación y dándole un limite a la lista tabú de valores y si se llena el y encuentra otro valor menor se sustituye por el primero de la lista tabú
def tabu(lista, candidato, cupo):
if candidato in lista:
return False # rechazar los que ya estan incluidos
else:
lista.append(candidato) # agregar al final
if len(lista) > cupo:
del lista[0] # eliminar el primero (mas viejo)
return True
def busqueda(rei, vuelta, armas, targets, matrix, cupo):
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 and objCand exito = True
actual = candidato
objAct = objCand
if objAct < mejor: mejor = objAct resultado = actual print >>salida, '%d %f' % (paso, mejor)
if not exito:
intentosRestantes -= 1 #no mejora
else:
intentosRestantes = vuelta
print intentosRestantes
salida.close()
return resultado
También se modifico esta parte para mandar llamar el cupo limite de la lista tabú, y se le agrego a las funciones gráfica, búsqueda y tabú
def main():
armas, targets, matrix = instancia()
cotaSup = cotaSuperior(armas, targets, matrix)
cotaInf = cotaInferior(armas, targets, matrix)
rei = 10
cupoTabu = int(raw_input("Largo de la lista tabu: "))
busqueda(rei, 40, armas, targets, matrix, cupoTabu)
grafica(rei, cotaInf, cotaSup, cupoTabu)
main()
No hay comentarios:
Publicar un comentario