G.T.Dragon Software: Temas Selectos de Optimización

Mostrando entradas con la etiqueta Temas Selectos de Optimización. Mostrar todas las entradas

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

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

W.T.A.P. Mejora de Función Objetivo

-Cota Inferior: Asignación de objetivos a las armas con mayor probabilidad de destrucción sin importancia a disponibilidad -Cota Superior: Asignación de objetivos tomando en cuenta la disponibilidad y la mayor probabilidad de destrucción -Función Objetivo: Asignación de objetivos con armas aleatoriamente -Factibilidad: La verificación de no haber utilizado una arma que ya no este disponible Se realiza una búsqueda comparativa con función objetiva actual y la nueva funciones objetivo con selección de armas para los objetivos de manera aleatoria respetando disponibilidad, se comparan con diferentes nuevas funciones objetivo con la finalidad de encontrar la mínima expectativa de supervivencia del objetivo si la actual es mayor que la nueva se sustituye.

from numpy import *
import random
from sys import argv
from subprocess import call

def cotaSuperior(armas, targets, matrix, checa = True):
    cota = 0
    if checa:
        disponible = list(armas)
    for j in range(len(targets)):
        aux = 1.0
        arma = None
        for i in range(len(armas)):
            if (not checa or disponible[i] > 0) and matrix[i, j] < aux:
                aux = matrix[i, j]
                arma = i
        if checa and arma is not None:
            disponible[arma] -= 1
        cota += aux * targets[j]
        print 'Para target %d usamos arma %s con prob %f' % (j, str(arma), aux)
    return cota

def cotaInferior(armas, targets, matrix):
    return cotaSuperior(armas, targets, matrix, False)

def factibilidad(asig, armas):
    print asig, armas
    for i in range(len(armas)):
        #print 'En uso %d de %d disponibles' % (asig.count(i), armas[i])
        if armas[i] < asig.count(i):
            #print 'No respeta disponibilidad'
            
            return False
    return True

def funcionObjetivo(armas, asig, targets, matrix):
    objetivo = 0.0
    v = len(asig)
    for k in range(v):
        objetivo += targets[k] * matrix[asig[k], k]
    return objetivo

def mejora(armas, targets,matrix, asig):
    nuevo = list(asig)
    arma = random.randrange(0, len(armas))
    nuevo[random.randrange(0, len(targets))] = arma
    return nuevo

def asignacion(armas, targets, matrix):
    a = []
    disponible = list(armas)
    for target in targets:
        arma = None
        while True:
            arma = random.randrange(0,len(armas))
            if disponible[arma] > 0:
                break
        a.append(arma)
        disponible[arma] -= 1
    return a

def busqueda(rei, vuelta, armas, targets, matrix):
    mejor = sum(targets) 
    resultado = None
    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:
            paso += 1
            candidato = mejora(armas, targets, matrix, actual)
            objCand = funcionObjetivo(armas, candidato, targets, matrix)
            fact = factibilidad(candidato, armas)
            if fact and objCand <= objAct: # acepto
                actual = candidato
                objAct = objCand
                if objAct < mejor:
                    mejor = objAct
                    resultado = actual
                    print >>salida, '%d %f' % (paso, mejor)
            else:
                intentosRestantes -= 1 # no pude mejorar
        salida.close()
    return resultado

def grafica(reinicios, cotaInf, cotaSup):
    out = open('grafica.plot', 'w')
    print >>out, \
        '''set term png 24
set size 2, 1
set xlabel \"Iteracion\"
set ylabel \"Objetivo\"
set key off
set logscale y
set pointsize 1.2
set output \"grafica.png\"'''
    plot = 'plot '
    for r in range(reinicios):
        plot += '\"reinicio%d.out\" with linespoints, ' % r
    plot += ' %f with lines lw 4, %f with lines lw 4' % (cotaInf, cotaSup)
    print >>out, plot
    out.close()
    call(['gnuplot', 'grafica.plot'])
    return
     
def instancia():
    armas = []
    targets = []
    try:
        datos = open(argv[1], 'r')
        tipos = datos.readline()
    #print tipos
        for t in tipos.split():
            armas.append(int(t))
        obj = datos.readline()
    #print obj
        for o in obj.split():
            targets.append(float(o))
        row = len(armas)
        print row
        col = len(targets)
        print col
    #print targets
    #print row, col
        matrix = empty((row, col))
        i = 0
        j = 0
        for linea in datos.readlines():
            elementos = linea.split()
            j = 0
        #print elementos
            for e in elementos:
            #print i, j
                matrix[i, j] = float(e)
                j += 1
            i += 1
        datos.close()
        
    except:

        row = int(argv[1])
        col = int(argv[2])
        print row
        print col
        for i in range(col):
            targets.append(random.uniform(1.0, 20.0))

        for i in range(row):
            armas.append(random.randrange(1, 10))

            matrix = empty((row, col))
        for i in range(row):
            for j in range(col):
                matrix[i, j] = random.random()
    
    print 'Numero de armas disponibles'
    s = ''
    for a in armas:
        s += '%d '% a
    print s
    
    print ' Objetivos '
    s = ''
    for t in targets:
        s += '%f ' % t
    print s
    print '\n'
    
    print 'Probabilidades de supervivencia'
    for i in range(row):
        s = ''
        for j in range(col):
            s += '%f ' % matrix[i, j]
        print s
    return armas, targets, matrix

def main():
    armas, targets, matrix = instancia()
    cotaSup = cotaSuperior(armas, targets, matrix)
    cotaInf = cotaInferior(armas, targets, matrix)
    rei = 10
    print busqueda(rei, 3300, armas, targets, matrix)
    grafica(rei, cotaInf, cotaSup)
   # print "Lista de asignacion:"
   # for i in range(10):
    #    fact = asignacion(armas, targets, matrix)
     #   print fact
      #  if factibilidad(fact, armas):
       #     print "Factible"
        #else:
         #   print "No factible"
          #  print "\n"
main()

Gráfica se gráfica con base de las cotas inferior y superior las cuales nos marcan una linea horizontal dando un limite sobre la gráfica para poder observar la graficación de las funciones objetivos como se va encontrando el mínimo hasta llegar a la cota inferior o casi llegar sin sobrepasarla

W.T.A.P. Función Objetivo, Factibilidad, Solución

En la versión estática de el problema WTA todas las entradas están fijas, significa que conocemos todos los enemigos y todas las armas posibles y también sabemos que arma confronta a que objetivo en un solo escenario.

WTA = determinar el numero de armas Xij para minimizar el valor total de supervivencia de todos los objetivos En palabras mortales: usar menos armas pero igual poder matar a todos los objetivos Evaluando la función objetivo: Observamos la cantidad de objetivos que se aproximan a la "base"(por así decirlo), así de esa manera asignaremos una arma y obtendremos una probabilidad de supervivencia. Obtendremos una lista con asignaciones Xij y lo que estaremos evaluando es que la asignacion de armas no sobrepase la cantidad de armas que tenemos en la base. Factibilidad: La cantidad de armas que asignamos esta evaluada con Wi asi que no debe de ser mayor a la cantidad de armas que tenemos, de manera que si este sobrepasa no sera una solución factible. Generar una solución:

......Pendiente de revisión

W.T.A.P. Cotas

Cota Superior: Sumatoria de probabilidades de supervivencia del objetivo según el arma con mayor ataque se toma así ya que esto sería el arma que causa mayor daño y deja un mínimo de sobrevivientes que es lo que se busca. Cota Inferior: Sumatoria de probabilidades de supervivencia del objetivo según el arma con menor ataque se toma así porque seria el menor que se puede obtener que deja un mínimo de sobrevivientes ya que es la que tiene menor poder de ataque.

from numpy import *
import random
from sys import argv

armas = list()
targets = list()

def cotaSuperior(armas):
    arma_mejor = armas.index(max(armas))
    return arma_mejor

def cotaInferior(armas):
    arma_peor = armas.index(min(armas))
    return arma_peor

try:
    datos = open(argv[1], 'r')
    tipos = datos.readline()
    #print tipos
    for t in tipos.split():
        armas.append(int(t))
    obj = datos.readline()
    #print obj
    for o in obj.split():
        targets.append(float(o))
    row = len(armas)
    col = len(targets)
    #print targets
    #print row, col
    matrix = empty((row, col))
    i = 0
    j = 0
    for linea in datos.readlines():
        elementos = linea.split()
        j = 0
        #print elementos
        for e in elementos:
            #print i, j
            matrix[i, j] = float(e)
            j += 1
        i += 1
    datos.close()

except:

    row = int(argv[1])
    col = int(argv[2])

    for i in range(col):
        targets.append(random.uniform(1.0, 20.0))

    for i in range(row):
        armas.append(random.randrange(1, 10))

    matrix = empty((row, col))
    for i in range(row):
        for j in range(col):
            matrix[i, j] = random.random()
s = ''
for a in armas:
    s += '%d '% a
print s

s = ''
for t in targets:
    s += '%f ' % t
print s

sumatoria =0
for i in range(row):
    s = ''
    for j in range(col):
        s += '%f ' % matrix[i, j]
    print s

for i in range(row):
    sumatoria += matrix[i, cotaSuperior(armas)]
print sumatoria

sumatoria2 =0
for i in range(row):
    sumatoria2 += matrix[i, cotaInferior(armas)]
print sumatoria2

W.T.A.P. Datos y Benchmark

Code:

from numpy import *
import random
from sys import argv

#Fila y columna de la matriz, se les pide como parámetros desde la terminal
row = int(argv[1])
col = int(argv[2])

#Creamos las listas para guardar los valores de armas y objetivos
armas = list()
targets = list()

#Insertar un valor pseudo-aleatorio uniforme de objetivos
for i in range(col):
  targets.append(int(random.uniform(1.0, 20.0)))
#Insertar un valor pseudo-aleatorio en un rango de 1 a 10 para definir el arma
for i in range(row):
  armas.append(random.randrange(1, 10))

#Matriz con valores pseudo-aleatorio de daños a los objetivos
matrix = empty((row, col))
for i in range(row):
  for j in range(col):
   matrix[i, j] = random.random()

print "Las armas: ",armas
print "Los objetivos: ", targets
print "La matriz de indice de supervivencia: \n",matrix

Benchmark: -En este benchmark nos basaremos ya que es el más parecido Branch and bound: http://www.dodccrp.org/events/10th_ICCRTS/CD/papers/182.pdf -Si no funciona pasaremos a la segunda opción MMR: http://research.engineering.wustl.edu/~mchan/projects/mitll/wta.pdf

martes, 26 de junio de 2012

El problema: Weapon Target Assignment

¿Quiénes somos?
Saúl Gausin
Calificación esperada: 130
Omar Jair Montalvo Aquines
Calificación esperada: 82
David Sosa Valdes
Calificación esperada: 80

Lenguajes: Python, JAVA(Posible).

Descripción del problema: Weapon-Target Assignment Problem (WTA) consiste en buscar una asignación óptima de un conjunto de armas de varios tipos a un conjunto de objetivos en orden para maximizar el daño total esperado hacia un oponente.

Se tiene un número de armas y un número de objetivos. Las armas son de tipo i = 1, 2, ..., m. Nosotros tenemos Wi armas disponibles de tipo i. De igual manera nosotros tenemos j = 1, 2, ..., n objetivos, y cada uno con un valor Vj. Cualquiera de estas armas se les puede asignar a cualquier objetivo. Cada tipo de arma tiene una cierta probabilidad de destruir cada objetivo, denotado por Pij.

Optimización: Se busca tener un máximo daño Pij Vj hacia un oponente dada la asignación de armas a objetivos. Esto esta formulado por medio de un problema entera no lineal.

esta sujeto a algunas limitantes,

En donde la variable Xij representa la asignacion de cuantos tipo de armas del tipo i confrontan a objetivos j y Qij es la probabilidad de supervivencia(i-Pij). La primera restricción requiere que el número de armas de cada tipo asignado no exceda el número disponible. La segunda restricción es la restricción integral.

Decisión: Si es posible lograr un daño mayor o superior a un valor establecido D.

NP-Dureza: El problema NP-completo 3-cubierta exacta se reduce a Weapon Target Assignment, lo que le hace NP duro.

http://md1.csa.com/partners/viewrecord.php?requester=gs&collection=TRD&recid=1342858CI&q=Lloyd+Witsenhausen+Weapon+allocation+NP-complete+Simulation+&uid=790227805&setcookie=yes

Tamaño (Medida de blancos y defensas): Seleccionamos un rango de 80 a 200 armas y objetivos a base del siguiente artículo.
http://web.mit.edu/sloan-msa/Papers/1.5.pd f