miércoles, 4 de julio de 2012

W.T.A.P. Búsqueda Tabú

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()