[imagen obtenida de: http://www.exponent.com/files/Uploads/Images/pharma/dna1.jpg]
Para la clase de hoy, nos hemos dado a la tarea de programar un algoritmo genético. Estos son llamados así porque se inspiran en la evolución biológica y su base genético-molecular. Estos algoritmos hacen evolucionar una población de individuos sometiéndola a acciones aleatorias semejantes a las que actúan en la evolución biológica (mutaciones y recombinaciones genéticas), así como también a una Selección de acuerdo con algún criterio, en función del cual se decide cuáles son los individuos más adaptados, que sobreviven, y cuáles los menos aptos, que son descartados.
Pongo la parte del código ya presentado en publicaciones anteriores haciendo modificaciones utilizadas para construir el algoritmo:
"genetico.py"
def generar_poblacion(self, lenPoblacion):
poblacion = list()
for i in range(lenPoblacion):
poblacion.append( self.instancia_inicial_pos() )
return poblacion
def mutar(self, solucion):
maximo = [self.sumatoria_pos(solucion[0]), 0] # Se encuentra el procesador que tarda mas tiempo
for i in range(1, len(solucion)): # obteniendo la sumatoria de tiempo que tarda cada procesador
suma = self.sumatoria_pos(solucion[i])
if suma > maximo[0]: # Escogiendo el que tarda mas
maximo[0] = suma
maximo[1] = i
procesador_origen = maximo[1] # Este procesador que toma mas tiempo sera al que se le quite una tarea para mandarla a otro
while True: # de forma aleatoria se escoje procesador al cual asignar la tarea que se quite a la tarea con mas tiempo
procesador_destino = random.randint(0, self.nProcessors-1)
if len(solucion[procesador_destino]) > 0 and procesador_origen != procesador_destino: #Si el procesador es el mismo que el de origen, se vuelve a escojer otro de forma aleatoria
break
if len(solucion[procesador_origen]) == 0: #Ahora de forma aleatoria se escoje la tarea que se va a cambiar de procesador
tarea_origen = 0 #El if igual a cero es por que la funcion random no deja generar numeros de 0 a 0
else:
tarea_origen = random.randint(0, len(solucion[procesador_origen])-1 )
solucion[procesador_destino].append( solucion[procesador_origen].pop(tarea_origen) ) # la funcion pop elimina el valor de la lista y regresa ese mi
return solucion
def procrear(self, poblacion, madre, padre):
hijo = list()
for i in range(self.nProcessors): #Crea una lista con los procesadores
hijo.append([])
hija = list()
for i in range(self.nProcessors): #Crea una lista con los procesadores
hija.append([])
genoma = [list(range(self.nTasks)), list(range(self.nTasks))]
for i in range(len(madre)):
for j in range(len(madre[i])):
genoma[0][madre[i][j]] = i
for i in range(len(padre)):
for j in range(len(padre[i])):
genoma[1][padre[i][j]] = i
for i in range(self.nTasks):
hijo[genoma[random.randint(0,1)][i]].append(i)
hija[genoma[random.randint(0,1)][i]].append(i)
poblacion.extend([hijo, hija])
def seleccionar_uno(self, valores_objetivo):
ruleta = list(valores_objetivo)
total = 0.0
for i in ruleta:
total += i
for i in range(1, len(ruleta)):
ruleta[i] = ruleta[i]/total
for i in range(1, len(ruleta)):
ruleta[i] = ruleta[i] + ruleta[i-1]
valor = random.uniform(0, 1)
for i in range(len(ruleta)):
if (ruleta[i] >= valor):
return i
def sangrienta_masacre(self, poblacion, lenPoblacion):
valores_objetivo = list()
for i in range(len(poblacion)):
valores_objetivo.append(self.funcion_objetivo_pos(poblacion[i]))
sujetos = len(poblacion)
nueva_poblacion = list()
while sujetos > lenPoblacion:
pos = self.seleccionar_uno(valores_objetivo)
valores_objetivo.pop(pos )
poblacion.pop(pos )
sujetos -= 1
def obtener_minimo( self, poblacion):
minimo = [float('Inf'), 0.0]
for i in range(len(poblacion)):
temp = self.funcion_objetivo_pos(poblacion[i])
if temp < minimo[0]:
minimo[0] = temp
minimo[1] = i
return int(minimo[1])
""" Algoritmo Genetico """
def genetico(self, maxReinicios, maxIntentos, lenPoblacion):
reinicios = 0
mejor_global = [list(),float('Inf')]
while reinicios < maxReinicios:
poblacion = self.generar_poblacion(lenPoblacion)
salida = open(('reinicio%d.out' % reinicios), 'w') # luego abre un archivo para guardar los datos a graficar
intentos = 0
paso = 0
mejor_local = [list(),float('Inf')]
while intentos < maxIntentos:
mitad = len(poblacion)/2
lon = len(poblacion)
for i in range(mitad):
self.procrear(poblacion, poblacion[i], poblacion[i+mitad])
for i in range(len(poblacion)):
poblacion[i] = self.mutar(poblacion[i])
self.sangrienta_masacre(poblacion, lenPoblacion)
pos = self.obtener_minimo(poblacion)
obj = self.funcion_objetivo_pos(poblacion[pos])
if mejor_local[1] >= obj:
mejor_local[0] = poblacion[pos]
mejor_local[1] = obj
else:
intentos += 1
print >>salida, '%d %f' % (paso, obj ) # Se grafica la nueva mejor solucion
paso += 1
salida.close()
if mejor_global >= mejor_local[1]:
mejor_global[0] = mejor_local[0]
mejor_global[1] = mejor_local[1]
reinicios += 1
return self.convertir_pos_tiempo(mejor_global[0])
Gráficas
Las instancias son de un promedio de 500 tareas y un promedio de duración de 120 ms por tarea. El número de intentos son 200 y el número de re intentos 10.
Para una población de 10 individuos:
Para una población de 15 individuos:
Para una población de 20 individuos:
Conclusiones:
Me parece que este algoritmo es mucho más elegante y pesado tanto de construí como de implementar que los demás que hemos probado. Pero una vez analizando el funcionamiento de esté mis conclusiones son:
- El algoritmo es mucho más seguro que otros puesto que ofrece mucha más aleatoriedad de búsqueda de soluciones.
- Es mucho más elegante, puesto que esta basado en genética.
Referencias:
http://es.wikipedia.org/wiki/Algoritmo_gen%C3%A9tico
La mutación se me hace más rolloso de lo necesario. Podría ser simplemente elegir un trabajo al azar y moverlo a un procesador elegido al azar. Van 10 pts.
ResponderBorrar