import numpy as np
import pandas as pd
import matplotlib.pyplot as plt
import random
#mutacion
#probabilidad de mutacion
p_mutacion=0.9
#cantidad de generaciones
g=100
#poblacion
p=10
#poblacion elite
pe = 5
#df1 = pd.read_excel('Libro1.xlsx', sheet_name='Hoja1',index_col=0)
#print(df1)
#df2 = pd.read_excel('Libro1.xlsx', sheet_name='Hoja4',index_col=0)
#print(df2)
#lista = [] #lista vacia para llenarla con datos
#for i in range(len(df2)):
# lista.append(list(df2.iloc[i,:]))
#lista
#matriz de factibilidad, posibilidades que tiene cada crew de atender los vuelos
# 0: si la crew no puede atender el vuelo f
# 1: si puede atender el vuelo f
matriz = []
bin = [0,1]
for i in range(10):
matriz.append([])
for j in range(10):
matriz[i].append(random.choice(bin))
matriz
#definir los costos
#costo de asignar el emparejamiento p perteneciente a Pk a la tripulacion k
cp = [200,300,400,200,300,500,300,400,400,600]
#costo de no cubrir el vuelo
uf = [2000,1000,1000,9000,7000,2000,5000,7000,4000,3000]
#costo de cada tripulacion que se desplaza en el vuelo f
df = [[57, 115, 90, 130, 112, 191, 121, 173, 102, 147],
[198, 173, 183, 154, 193, 176, 116, 169, 126, 172],
[135, 146, 162, 199, 124, 52, 115, 148, 55, 63],
[90, 56, 140, 194, 106, 195, 175, 182, 138, 66],
[69, 142, 126, 81, 105, 74, 87, 148, 102, 103],
[89, 59, 135, 157, 86, 76, 161, 55, 192, 194],
[133, 183, 75, 87, 132, 91, 121, 185, 116, 93],
[171, 89, 86, 131, 138, 175, 66, 101, 106, 132],
[175, 129, 116, 172, 191, 104, 153, 191, 126, 143],
[168, 172, 136, 139, 156, 196, 185, 89, 145, 174]]
#costo de no asignar emparejamiento a la tripulacion k
qk= [400,500,600,400,200,100,500,300,300,500]
#1 si ek vuelo f esta cubierto por el emparejamiento p
afp=50
#vuelo = [A,B,C,D,E,F,G,H,I,J]
k = 0
print("-----------------------------\nEstado inicial\n-----------------------------\n")
for i in range(len(matriz)):
k = k + 1
vuelo = ""
c = 0
ceros = 0
for j in range(len(matriz)):
c = c + 1
if matriz[i][j]==1:
ceros = ceros + 1
vuelo = vuelo + "f" + str(c) + " "
if ceros == 0:
vuelo = "---------sin asignar---------"
print(f"La tripulacion K{k} puede atender los vuelos: {vuelo}")
# generar posibles atenciones (cromosoma)
# se tiene presente las posibilidadesde atencion para que el cromosoma sea factible
emparejamiento = []
bin = [0,1]
pos = []
for i in range(len(matriz)):
emparejamiento.append([])
c = 0
for j in range(len(matriz)):
c = c + 1
if matriz[i][j]==1 and j not in pos:
#puede realizarse o no el emparejamiento
emparejamiento[i].append(random.choice(bin))
#registrar los emparejamientos ya realizados
if emparejamiento[i][j] == 1:
pos.append(j)
else:
emparejamiento[i].append(0)
print(str(pos) + "\n")
emparejamiento
def Emparejamiento (matriz):
emparejamiento = []
bin = [0,1]
pos = []
for i in range(len(matriz)):
emparejamiento.append([])
c = 0
for j in range(len(matriz)):
c = c + 1
if matriz[i][j]==1 and j not in pos:
#puede realizarse o no el emparejamiento
emparejamiento[i].append(random.choice(bin))
#registrar los emparejamientos ya realizados
if emparejamiento[i][j] == 1:
pos.append(j)
else:
emparejamiento[i].append(0)
print(str(pos) + "\n")
return emparejamiento
emparejamiento
#Funcion Objetivo
#cp = [200,300,400,200,300,500,300,400,400,600]
FO= []
bin = [0,1]
for i in range(10):
z = 0
NoEmp = 0
for j in range(10):
if emparejamiento[i][j] == 0:
NoEmp = NoEmp + 1
z = z + emparejamiento[i][j]*cp[j] + emparejamiento[i][j]*df[i][j]
if NoEmp == 10:
z = z + qk[j]
FO.append(z)
print(FO)
nc = []
for fil in range(10):
NoCubierto = 0
for col in range(10):
NoCubierto = emparejamiento[col][fil] + NoCubierto
if NoCubierto == 0:
nc.append(uf[fil])
print(f"nc {nc}")
aa = 0
for suma in range(len(FO)):
aa = FO[suma] + aa
aaa = 0
for suma in range(len(nc)):
aaa = FO[suma] + aaa
fitness = aa + aaa
print(f"fitness : {fitness}")
#comparar listas
a = Emparejamiento(matriz)
b = Emparejamiento(matriz)
emp_a = []
pos_a = []
emp_b = []
pos_b = []
#valores de a
for i in range(10):
emp_a = []
for j in range(10):
if a[i]==b[j]:
booleano = True
else:
booleano = False
emp_a.append(booleano)
print(f"a{i} {a[i]} ----> b{j} {b[j]} {booleano}")
#a[i]==b[j]
print("-------------------------------------------------------------------------------")
if True not in emp_a:
pos_a.append(i)
print(pos_a)
#valores de b
for i in range(10):
emp_b = []
for j in range(10):
if b[i]==a[j]:
booleano = True
else:
booleano = False
emp_b.append(booleano)
print("-------------------------------------------------------------------------------")
if True not in emp_b:
pos_b.append(i)
print(pos_b)
#comparar listas
a = Emparejamiento(matriz)
b = Emparejamiento(matriz)
emp_a = []
pos_a = []
emp_b = []
pos_b = []
#valores de a
for i in range(10):
emp_a = []
for j in range(10):
if a[i]==b[j]:
booleano = True
else:
booleano = False
emp_a.append(booleano)
print(f"a{i} {a[i]} ----> b{j} {b[j]} {booleano}")
print("-------------------------------------------------------------------------------")
if True not in emp_a:
pos_a.append(i)
print(pos_a)
#valores de b
for i in range(10):
emp_b = []
for j in range(10):
if b[i]==a[j]:
booleano = True
else:
booleano = False
emp_b.append(booleano)
print("-------------------------------------------------------------------------------")
if True not in emp_b:
pos_b.append(i)
print(pos_b)
a = Emparejamiento(matriz)
b = Emparejamiento(matriz)
f1 = []
k1 = []
for i in range(10):
for j in range(10):
if a[i][j]==1:
f1.append(j)
k1.append(i)
print("cromosomas")
print(f"f (vuelo) : {f1}")
print(f"k (tripulacion): {k1}")
print("-----------------|-|--|--|--|--|--|--|--|--|--|")
f2 = []
k2 = []
for i in range(10):
for j in range(10):
if b[i][j]==1:
f2.append(j)
k2.append(i)
print(f"f (vuelo) : {f2}")
print(f"k (tripulacion): {k2}")
print(f1)
print(k1)
print("")
print(f2)
print(k2)
f_hijo = []
k_hijo = []
posicion = []
for vu in range(10):
# print(vu)
eleccion = random.randint(0,1)
condicion_1 = vu in f1
condicion_2 = vu in f2
if condicion_1 or condicion_2 == True:
if eleccion == 0:
if vu not in f1:
#posicion.append(f2.index(vu))
pos = f2.index(vu)
f_hijo.append(vu)
k_hijo.append(k2[pos])
else:
#posicion.append(f1.index(vu))
pos = f1.index(vu)
f_hijo.append(vu)
k_hijo.append(k1[pos])
elif eleccion ==1:
if vu not in f2:
#posicion.append(f2.index(vu))
pos = f1.index(vu)
f_hijo.append(vu)
k_hijo.append(k1[pos])
else:
#posicion.append(f2.index(vu))
pos = f2.index(vu)
f_hijo.append(vu)
k_hijo.append(k2[pos])
print("cromosoma hijo")
print(f"f (vuelo) : {f_hijo}")
print(f"k (tripulacion): {k_hijo}")
k2
hijo = []
for i in range(10):
hijo.append([])
for j in range(10):
hijo[i].append(0)
for cr in range(len(f_hijo)):
hijo[k_hijo[cr]][f_hijo[cr]] = 1
hijo
#crear poblacion
poblacion = []
for i in range(0, 10):
poblacion.append(Emparejamiento(matriz))
poblacion
#seleccionar poblacion de elite
def Fitness(emparejamiento, cp, df, qk):
FO= []
bin = [0,1]
for i in range(10):
z = 0
NoEmp = 0
for j in range(10):
if emparejamiento[i][j] == 0:
NoEmp = NoEmp + 1
z = z + emparejamiento[i][j]*cp[j] + emparejamiento[i][j]*df[i][j]
if NoEmp == 10:
z = z + qk[j]
FO.append(z)
print(FO)
nc = []
for fil in range(10):
NoCubierto = 0
for col in range(10):
NoCubierto = emparejamiento[col][fil] + NoCubierto
if NoCubierto == 0:
nc.append(uf[fil])
print(nc)
aa = 0
for suma in range(len(FO)):
aa = FO[suma] + aa
aaa = 0
for suma in range(len(nc)):
aaa = FO[suma] + aaa
fitness = aa + aaa
print(f"fitness : {fitness}")
return fitness
#Evaluar poblacion
def Evaluar(poblacion,cp,df,qk):
resultados = []
for i in range(len(poblacion)):
fo = Fitness(poblacion[i], cp, df, qk)
resultados.append(fo)
return resultados
rr = Evaluar(poblacion,cp,df,qk)
rr
#saber el ranking de las posiciones
orden = sorted(rr, reverse = False)
#print(orden)
print(f"Ranking : {orden}")
posicion = []
for p in range(len(orden)):
posicion.append(rr.index(orden[p]))
posicion
#seleccion de poblacion de elite, individuos que pasan a la siguiente generacion
print("los mejores individuos son: ")
for e in range(10):
a = "cromosoma :" + str(poblacion[posicion[e]]) + " costo: " + str (rr[posicion[e]])
print(a)
# ver los cromosomas de la poblacion
for pob in range(len(poblacion)):
f1 = []
k1 = []
for i in range(10):
for j in range(10):
if poblacion[pob][i][j]==1:
f1.append(j)
k1.append(i)
print(f"cromosoma {pob} Funcion Objetivo: {rr[pob]} ")
print(f"ƒ (vuelo) : {f1}")
print(f"k (tripulacion): {k1}")
def orden(resultados):
#saber el ranking de las posiciones
orden = sorted(resultados, reverse = False)
#print(orden)
print(f"Ranking : {orden}")
print("--------------------------------------------------------------------")
return orden
o = orden(rr)
def Posicion(resultados, orden):
posicion = []
for p in range(len(orden)):
posicion.append(resultados.index(orden[p]))
return posicion
possss = Posicion(rr, o)
possss
def elite(matriz,resultados,posicion,pe):
top = []
for t in range(pe):
top.append(matriz[posicion[t]])
#seleccion de poblacion de elite, individuos que pasan a la siguiente generacion
#print("los mejores individuos son: ")
#print(top)
return top
t = elite(poblacion, rr, possss, pe)
t
#crear lista de combinaciones de padres
def ListaPares(elite,pe):
largo = pe
pares = []
c = 0
for i in range(largo):
dos = []
c = i
for ji in range(largo):
c = c + 1
if c <= (largo-1):
print(f"{i} {c}")
dos.append(i)
dos.append(c)
pares.append(dos)
if len(dos)== 2:
dos = []
return pares
pares = ListaPares(elite,pe)
pares
kakaka = pares[len(pares)-1]
def ParesPadres(pares,poblacion):
pos_p1 = pares[random.randint(0,len(pares)-1)][0]
pos_p2 = pares[random.randint(0,len(pares)-1)][1]
a = poblacion[pos_p1]
b = poblacion[pos_p2]
f1 = []
k1 = []
for i in range(10):
for j in range(10):
if a[i][j]==1:
f1.append(j)
k1.append(i)
print("cromosomas")
print(f"f (vuelo) : {f1}")
print(f"k (tripulacion): {k1}")
print("-----------------|-|--|--|--|--|--|--|--|--|--|")
f2 = []
k2 = []
for i in range(10):
for j in range(10):
if b[i][j]==1:
f2.append(j)
k2.append(i)
print(f"f (vuelo) : {f2}")
print(f"k (tripulacion): {k2}")
return f1,k1,f2,k2
print("cromosomas")
print("padre 1")
print(f"f (vuelo) : {f1}")
print(f"k (tripulacion): {k1}")
print("-----------------|-|--|--|--|--|--|--|--|--|--|")
print("padre 2")
print(f"f (vuelo) : {f2}")
print(f"k (tripulacion): {k2}")
def cruce(f1,k1,f2,k2):
f_hijo = []
k_hijo = []
posicion = []
for vu in range(10):
# print(vu)
eleccion = random.randint(0,1)
condicion_1 = vu in f1
condicion_2 = vu in f2
if condicion_1 or condicion_2 == True:
if eleccion == 0:
if vu not in f1:
#posicion.append(f2.index(vu))
pos = f2.index(vu)
f_hijo.append(vu)
k_hijo.append(k2[pos])
else:
#posicion.append(f1.index(vu))
pos = f1.index(vu)
f_hijo.append(vu)
k_hijo.append(k1[pos])
elif eleccion ==1:
if vu not in f2:
#posicion.append(f2.index(vu))
pos = f1.index(vu)
f_hijo.append(vu)
k_hijo.append(k1[pos])
else:
#posicion.append(f2.index(vu))
pos = f2.index(vu)
f_hijo.append(vu)
k_hijo.append(k2[pos])
print("cromosoma hijo---------------------------------")
print(f"f (vuelo) : {f_hijo}")
print(f"k (tripulacion): {k_hijo}")
print("")
return f_hijo,k_hijo
print("cromosoma hijo---------------------------------")
print(f"f (vuelo) : {f_hijo}")
print(f"k (tripulacion): {k_hijo}")
def mutacion(hijo,matriz,p_mutacion):
cambiofila = []
cambiocolumna = []
for fila in range(10):
for columna in range(10):
if hijo[fila][columna]==1:
if (fila not in cambiofila) and (columna not in cambiocolumna):
mut = random.uniform(0,1)
if mut <= p_mutacion:
reubicacion = random.randint(0,9)
while matriz[reubicacion][columna] == 1:
reubicacion = random.randint(0,9)
hijo[fila][columna] = 0
hijo[reubicacion][columna] = 1
cambiofila.append(reubicacion)
cambiocolumna.append(columna)
return hijo
def RepresentacionHijo(f_hijo,k_hijo):
hijo = []
for i in range(10):
hijo.append([])
for j in range(10):
hijo[i].append(0)
for cr in range(len(f_hijo)):
hijo[k_hijo[cr]][f_hijo[cr]] = 1
return hijo
hijos = []
for i in range(5):
f1,k1,f2,k2 = ParesPadres(pares,t)
f_hijo,k_hijo = cruce(f1,k1,f2,k2)
hijo = RepresentacionHijo(f_hijo,k_hijo)
hijo_mutado = mutacion(hijo,matriz,p_mutacion)
hijos.append(hijo_mutado)
hijos
hijo
for fil in range(10):
NoCubierto = 0
for col in range(10):
NoCubierto = emparejamiento[col][fil] + NoCubierto
if NoCubierto == 0:
nc.append(uf[fil])
reubicacion = random.randint(0,9)
while matriz[reubicacion][3] == 1:
reubicacion = random.randint(0,9)
reubicacion
#nueva generacion (5 x elite + 5 x hijos)
ng = t + hijos
len(ng)
#definir los costos
#costo de asignar el emparejamiento p perteneciente a Pk a la tripulacion k
cp = [200,300,400,200,300,500,300,400,400,600]
#costo de no cubrir el vuelo
uf = [2000,1000,1000,9000,7000,2000,5000,7000,4000,3000]
#costo de cada tripulacion que se desplaza en el vuelo f
df = [[57, 115, 90, 130, 112, 191, 121, 173, 102, 147],
[198, 173, 183, 154, 193, 176, 116, 169, 126, 172],
[135, 146, 162, 199, 124, 52, 115, 148, 55, 63],
[90, 56, 140, 194, 106, 195, 175, 182, 138, 66],
[69, 142, 126, 81, 105, 74, 87, 148, 102, 103],
[89, 59, 135, 157, 86, 76, 161, 55, 192, 194],
[133, 183, 75, 87, 132, 91, 121, 185, 116, 93],
[171, 89, 86, 131, 138, 175, 66, 101, 106, 132],
[175, 129, 116, 172, 191, 104, 153, 191, 126, 143],
[168, 172, 136, 139, 156, 196, 185, 89, 145, 174]]
#costo de no asignar emparejamiento a la tripulacion k
qk= [400,500,600,400,200,100,500,300,300,500]
#1 si ek vuelo f esta cubierto por el emparejamiento p
afp=50
matriz = []
bin = [0,1]
for i in range(10):
matriz.append([])
for j in range(10):
matriz[i].append(random.choice(bin))
k = 0
print("-----------------------------\nEstado inicial\n-----------------------------\n")
for i in range(len(matriz)):
k = k + 1
vuelo = ""
c = 0
ceros = 0
for j in range(len(matriz)):
c = c + 1
if matriz[i][j]==1:
ceros = ceros + 1
vuelo = vuelo + "f" + str(c) + " "
if ceros == 0:
vuelo = "---------sin asignar---------"
print(f"La tripulacion K{k} puede atender los vuelos: {vuelo}")
#emparejamiento = Emparejamiento (matriz)
#crear poblacion con combinaciones viables
poblacion = []
for i in range(0, 10):
poblacion.append(Emparejamiento(matriz))
#listas para los graficos
grafico = []
FitnessPromedio = []
#----------------------------inicio------------------------------------------------------
for generation in range(1000): # cambiar a g
#leer represntacion cromosomica de la poblacion
for pob in range(len(poblacion)):
f1 = []
k1 = []
for i in range(10):
for j in range(10):
if poblacion[pob][i][j]==1:
f1.append(j)
k1.append(i)
print(f"cromosoma {pob} Funcion Objetivo: {rr[pob]} ")
print(f"ƒ (vuelo) : {f1}")
print(f"k (tripulacion): {k1}")
#evaluar fenotipo de la poblacion
rr = Evaluar(poblacion,cp,df,qk)
#grafico
grafico.append(rr[0])
mean = np.mean(rr)
FitnessPromedio.append(mean)
#ordenar la lista de menor a mayor fitness
o = orden(rr)
#posiciones de la lista ordenada
position = Posicion(rr, o)
#lista de los mejores 5 individuos
t = elite(poblacion, rr, position, pe)
pares = ListaPares(elite,pe)
hijos = []
for i in range(5):
f1,k1,f2,k2 = ParesPadres(pares,t)
f_hijo,k_hijo = cruce(f1,k1,f2,k2)
hijo = RepresentacionHijo(f_hijo,k_hijo)
hijo_mutado = mutacion(hijo,matriz,p_mutacion)
hijos.append(hijo_mutado)
ng = t + hijos
poblacion = ng
grafico[999]
ejex = []
cuenta = 0
for j in range(len (grafico)):
cuenta = cuenta + 1
ejex.append(cuenta)
import matplotlib.pyplot as plt
fig, ax = plt.subplots()
generaciones = ejex
fitness = grafico
ax.plot(generaciones, fitness, marker = 'o')
plt.figure(figsize=(20,10))
plt.show()
import matplotlib.pyplot as plt
import numpy as np
plt.figure(figsize=(30,10))
x = ejex
y = grafico
plt.plot(x, y,'--')
x1 = ejex
y1 = FitnessPromedio
plt.plot(x1, y1, '-')
plt.xlabel("X - Generación")
plt.ylabel("Y - Costo solución")
plt.title("Mejor Fitness vs Fitness Promedio")
plt.show()
import matplotlib.pyplot as plt
import numpy as np
ejex = [1,2,3,4,5,6,7]
mutacion = [0.1,0.2,0.3,0.4,0.5,0.6,0.7,0.8,0.9]
fitness = [4886, 4533,4795, 4549, 4685, 4649, 4572, 4898,5429]
plt.figure(figsize=(15,10))
x = mutacion
y = fitness
plt.plot(x, y,'--')
#x1 = mutacion
#y1 = FitnessPromedio
#plt.plot(x1, y1, '-')
plt.xlabel("X - Pb. mutacion")
plt.ylabel("Y - Fitness ")
plt.title("Fitness vs Probabilidad Mutación")
plt.show()
ejex = []
cuenta = 0
for j in range(len (grafico)):
cuenta = cuenta + 1
ejex.append(cuenta)
import matplotlib.pyplot as plt
fig, ax = plt.subplots()
generaciones = ejex
fitness = grafico
ax.plot(generaciones, fitness, marker = 'o')
plt.figure(figsize=(20,10))
plt.show()