import random
LON_CROMO = 50
POBLACION = 100
TASA_MUTACION = 0.001
TASA_CRUCE = 0.74
MAX_GENERACIONES = 300
class Cromosoma():
def __init__(self, cromosoma="-1", aptitud=-1):
if cromosoma == "-1":
self.cromosoma=self.GenesAleatorios()
else:
self.cromosoma=cromosoma
if aptitud == -1:
self.aptitud=0.0
else:
self.aptitud=aptitud
def GenesAleatorios(self):
for i in self.cromosoma:
if random.random() < 0.5: #devuelve float entre 0 y 1
i = "0"
else:
i = "1"
def CalcularAptitud(self, x_buscada, y_buscada, x, y):
for i in range(LON_CROMO-2):
gen = self.cromosoma[i:i+2]
if gen == "00": #arriba
x -= 1
elif gen == "01": #abajo
x += 1
elif gen == "10": #derecha
y += 1
elif gen == "11": #izquierda
y -= 1
if x == x_buscada and y == y_buscada:
return float(999)
else:
continue
return 1/float(abs((x_buscada + y_buscada) - (x + y)))
def Mutacion(self):
for i in range(LON_CROMO):
if random.random() < TASA_MUTACION:
if self.cromosoma[i] == "0":
self.cromosoma[i] = "1"
elif self.cromosoma[i] == "1":
self.cromosoma[i] = "0"
def MostrarCromo(self):
for i in range(LON_CROMO-2):
if self.cromosoma[i:i+2] == "00":
print "ve hacia arriba\n"
elif self.cromosoma[i:i+2] == "01":
print "ahora hacia abajo\n"
elif self.cromosoma[i:i+2] == "10":
print "gira a la derecha\n"
elif self.cromosoma[i:i+2] == "11":
print "ahora vete a la izquierda\n"
def cruce(t1, t2):
if random.random() < TASA_CRUCE:
punto = int(random.random() * LON_CROMO)
hijo1 = t1[0:punto] + t2[punto:]
hijo2 = t2[0:punto] + t1[punto:]
return hijo1, hijo2 #tupla de la que luego extraemos los datos
def ruleta(aptitud_total, poblacion):
porcion = float(random.random() * aptitud_total)
aptitud_acumulada = 0.0
for i in range(POBLACION):
aptitud_acumulada += poblacion[i].aptitud
if aptitud_acumulada > porcion:
return poblacion[i].genes
break
def main():
random.seed()
while True:
x = input("¿donde empezamos? (x): ")
y = input("¿en que parte del eje y?: ")
x_objetivo = input("destino en x: ")
y_objetivo = input("el destino y: ")
poblacion = []
for i in range(POBLACION):
poblacion.append(Cromosoma(-1, -1))
generaciones = 0
encontrado = 0 #si es 0 no hemos llegado llegado a una solución correcta
while not encontrado:
aptitud_total = 0.0
for i in range(POBLACION):
poblacion[i].CalcularAptitud(x_objetivo, y_objetivo, x, y)
aptitud_total += poblacion[i].aptitud
for i in range(POBLACION):
if poblacion[i].aptitud == 999:
print "solucion encontrada en ", generaciones, " generaciones!!!"
poblacion[i].MostrarCromo()
encontrado = 1
break
#empezamos a construir la nueva generacion
temporal[POBLACION] = Cromosoma()
i = 0
while i < POBLACION:
hijo1 = ruleta(aptitud_total, poblacion)
hijo2 = ruleta(aptitud_total, poblacion)
hijo1, hijo2 = cruce(hijo1, hijo2)
hijo1.mutacion()
hijo2.mutacion()
temporal[i] = Cromosoma(hijo1, 0.0)
i += 1
temporal[i] = Cromosoma(hijo2, 0.0)
i += 1
for i in range(POBLACION):
poblacion[i] = temporal[i]
if MAX_GENERACIONES < generaciones:
print "no hay solucion en ", generaciones, " generaciones"
encontrado = 1
#while not encontrado
return 0
main()