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