miércoles, 4 de julio de 2012

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