En este algoritmo una solución optima es buscada generando una solución inicial y después por pasos o intentos, mejorarla haciendo cambios aleatorios y observando si el cambio es más o menos optimo. Este proceso se repite una pequeña cantidad de veces y se toma como la respuesta más optima la que haya arrojado el mejor resultado.
El código es el siguiente, la parte gráfica donde se utiliza gnuplot fue copiada del código de ejemplo que utilizo la doctora Elisa en su página.
"voraz.py"
#! /usr/bin/python
import sys
import random
from subprocess import call
from Tkinter import *
class Heuristico:
"""Las soluciones son vectos donde [] la primera dimension son los procesadores y la segunda las tareas"""
def __init__(self, nameOfFile, nProcessors):
"""Funcion que recibe como parametros el nombre del archivo donde se encuentran las instancias iniciales y el numero de procesadores, luego crea un vector donde se encuentran todas las tareas"""
self.tasks = []
self.nProcessors = nProcessors
for line in open(nameOfFile,'r'):
self.tasks.append( float(line.replace("\n", "")) )
def cota_superior(self):
suma = 0
for i in range(len(self.tasks)):
suma = suma + self.tasks[i]
return suma
def cota_inferior(self):
inferior = self.tasks[0]
for i in range(len(self.tasks)):
if self.tasks[i] > inferior:
inferior = self.tasks[i]
return inferior
def verificar_factibilidad(self, solucion):
verificar = self.funcion_objetivo(solucion)
if (verificar >= self.cota_inferior() ) and (verificar <= self.cota_superior() ):
return True
else:
return False
def funcion_objetivo(self, solucion):
longitud = 0.0
temp = 0.0
for i in solucion:
temp = 0.0
for j in i:
temp = temp + j
if temp > longitud:
longitud = temp
return longitud
def instancia_inicial(self):
"""Soluciones vector[procesadores][tareas]"""
solInicial = []
for i in range(self.nProcessors):
solInicial.append([])
for i in self.tasks:
solInicial[random.randint(0, self.nProcessors-1)].append(i)
return solInicial
def graficar_rectangulos(self, solucion):
master = Tk()
max_width = self.funcion_objetivo(solucion)
width = 850.0
height = 315.0
w = Canvas(master, width=width, height=height, background="white")
w.pack()
x = y = 0.0
process_len = height/self.nProcessors
color = random.randint(0, 16**2)
for i in solucion:
for j in i:
w.create_rectangle( (x/max_width)*width, y, ((x+j)/max_width)*width, y+process_len, fill=('#%02x%04x'%(color, random.triangular(0, 16**4))), width=1)
x = x + j
x = 0.0
y = y + process_len
mainloop()
def grafica(self, reinicios, cotaInf, cotaSup):
out = open('grafica.plot', 'w')
print >>out, \
'''set term postscript eps color 24
set size 4, 2
set xlabel \"Iteracion\"
set ylabel \"Objetivo\"
set key off
set pointsize 1.2
set output \"grafica.eps\"'''
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 sumatoria(self, vector):
suma = 0.0
for i in vector:
suma = suma + i
return suma
""" Parametros(matriz con soluciones inicial, numero de iteraciones) """
def busqueda_voraz(self, maxReinicios, maxIntentos):
modificado = []
actual = []
mejor = self.instancia_inicial()
for reinicios in range(maxReinicios):## intend hacia adelante
actual = self.instancia_inicial()
salida = open(('reinicio%d.out' % reinicios), 'w')
paso = 0
for intentos in range(maxIntentos):
modificado = actual
maximo = [self.sumatoria(modificado[0]), 0]
for i in range(1, len(modificado)):
suma = self.sumatoria(modificado[i])
if suma > maximo[0]:
maximo[0] = suma
maximo[1] = i
procesador_origen = maximo[1]
while True:
procesador_destino = random.randint(0, self.nProcessors-1)
if len(modificado[procesador_destino]) > 0 and procesador_origen != procesador_destino:
break
if len(modificado[procesador_origen]) == 0:
tarea_origen = 0
else:
tarea_origen = random.randint(0, len(modificado[procesador_origen])-1 )
modificado[procesador_destino].append( modificado[procesador_origen].pop(tarea_origen) )
objetivo_modificado = self.funcion_objetivo(modificado)
objetivo_actual = self.funcion_objetivo(actual)
if objetivo_modificado <= objetivo_actual:
print >>salida, '%d %f' % (paso, objetivo_modificado)
paso += 1
actual = modificado
intentos += 1
salida.close()
if self.funcion_objetivo(actual) <= self.funcion_objetivo(mejor):
mejor = actual
return mejor
h = Heuristico(sys.argv[1], int(sys.argv[2]))
#h.graficar_rectangulos(solucion)
mejor = h.busqueda_voraz(30, 1000)
inferior = h.cota_inferior()
superior = h.cota_superior()
print "Funcion Objetivo de la mejor solucion: ", h.funcion_objetivo(mejor )
h.grafica(30, inferior , inferior)
h.graficar_rectangulos(mejor)
Esta gráfica es la solución mas optima encontrada por el programa donde las filas representan cada procesador y el largo de las columnas representa la longitud de cada tarea. Y siguiente a esta se puede ver la mejor solución evaluada en la función objetivo en mili segundos que arroja el programa:
La siguiente gráfica muestra todas las soluciones que fue encontrando el programa en cada intento, vale la pena recordar que en el código cada intento es una nueva solución inicial generada que después es mejorada en pasos de manera aleatoria:
El número de intentos por solución inicial fueron 1000, los re intentos con otras soluciones fueron 30, y no se logra apreciar pero la cota inferior se encuentra abajo de la gráfica y la superior decidí no agregarla puesto que esta demasiado arriba y no deja apreciar bien los demás elementos.
Referencias:
http://elisa.dyndns-web.com/~elisa/teaching/opt/heur/
http://es.wikipedia.org/wiki/Algoritmo_voraz
Acentos, corazoncitos. Sería bueno separar lo de mejora a una subrutina aparte. Así sale más fácil modificar el código para que aguante múltiples diferentes metaheurísticos. Van 10 pts por hoy.
ResponderBorrarme podrian ayudar con el codigo, no logro entenderlo
ResponderBorrar