-
Notifications
You must be signed in to change notification settings - Fork 2
/
ieeewebinartsp2020.py
212 lines (166 loc) · 9.51 KB
/
ieeewebinartsp2020.py
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
206
207
208
209
210
211
212
# -*- coding: utf-8 -*-
"""IEEEWebinarTSP2020.ipynb
Automatically generated by Colaboratory.
Original file is located at
https://colab.research.google.com/drive/1kW4TXzxDALsJTbTfpTUaDXTbE5MxxZ2W
Resolución del problema del viajero o TSP utilizando deap
https://deap.readthedocs.io/en/master/
En primer lugar, debemos intalar la librería:
"""
!pip install deap
"""**Importamos las liberías necesarias:**
1. random: números pseudoaleatorios
2. numpy: arrays
3. maplotlib.pyplot: visualizar los resultados
4. deap.base: incluye las clases base de deap. En concreto dos son importantes en nuestro ejemplo, base.Fitness y base.Toolbox.
5. deap.creator: permite crear clases nuevas.
6. deap.tools: herramientas para implementar los algoritmos genéticos: operadores genéticos (selección, cruce y mutación), hallofFame, estadística, registro de evolución, etc.
7. deap.alorihtms: incluye implementaciones completas de algoritmos genéticos, nosotros vamos a utilizar eaSimple.
"""
import random
import numpy
import matplotlib.pyplot as plt
from deap import base
from deap import creator
from deap import tools
from deap import algorithms
"""**Diccionario que contiene los datos del problema:**
1. Toursize: número de ciudades.
2. OptTour: tour óptimo para este problema. Estamos haciendo trampa :) sabemos la solución, no es lo normal.
3. OptDistance: distancia recorrida por el agente para el tour óptimo.
4. DistanceMatrix: matriz de distancia.
"""
tsp = {
"TourSize" : 17,
"OptTour" : [15, 11, 8, 4, 1, 9, 10, 2, 14, 13, 16, 5, 7, 6, 12, 3, 0],
"OptDistance" : 2085,
"DistanceMatrix" :
[[0, 633, 257, 91, 412, 150, 80, 134, 259, 505, 353, 324, 70, 211, 268, 246, 121],
[633, 0, 390, 661, 227, 488, 572, 530, 555, 289, 282, 638, 567, 466, 420, 745, 518],
[257, 390, 0, 228, 169, 112, 196, 154, 372, 262, 110, 437, 191, 74, 53, 472, 142],
[91, 661, 228, 0, 383, 120, 77, 105, 175, 476, 324, 240, 27, 182, 239, 237, 84],
[412, 227, 169, 383, 0, 267, 351, 309, 338, 196, 61, 421, 346, 243, 199, 528, 297],
[150, 488, 112, 120, 267, 0, 63, 34, 264, 360, 208, 329, 83, 105, 123, 364, 35],
[80, 572, 196, 77, 351, 63, 0, 29, 232, 444, 292, 297, 47, 150, 207, 332, 29],
[134, 530, 154, 105, 309, 34, 29, 0, 249, 402, 250, 314, 68, 108, 165, 349, 36],
[259, 555, 372, 175, 338, 264, 232, 249, 0, 495, 352, 95, 189, 326, 383, 202, 236],
[505, 289, 262, 476, 196, 360, 444, 402, 495, 0, 154, 578, 439, 336, 240, 685, 390],
[353, 282, 110, 324, 61, 208, 292, 250, 352, 154, 0, 435, 287, 184, 140, 542, 238],
[324, 638, 437, 240, 421, 329, 297, 314, 95, 578, 435, 0, 254, 391, 448, 157, 301],
[70, 567, 191, 27, 346, 83, 47, 68, 189, 439, 287, 254, 0, 145, 202, 289, 55],
[211, 466, 74, 182, 243, 105, 150, 108, 326, 336, 184, 391, 145, 0, 57, 426, 96],
[268, 420, 53, 239, 199, 123, 207, 165, 383, 240, 140, 448, 202, 57, 0, 483, 153],
[246, 745, 472, 237, 528, 364, 332, 349, 202, 685, 542, 157, 289, 426, 483, 0, 336],
[121, 518, 142, 84, 297, 35, 29, 36, 236, 390, 238, 301, 55, 96, 153, 336, 0]]
}
"""Guardamos en dos variables distintas la matriz de distancia y el número de ciudades. Accedemos a los valores mediante las claves del diccionario."""
distance_map = tsp["DistanceMatrix"]
IND_SIZE = tsp["TourSize"]
"""Creamos la clase que define el fitness de los individuos **FitnessMin**. Este paso en la mayoría de los problemas será muy parecido. Siempre tendremos que heredar de base.Fitness. El atributo **weights** nos dice el número de objetivos de nuestro problema y el tipo (-1.0 para minimizar y 1.0 para maximizar). En este caso es un problema de **minimización** de **un objetivo**. **En deap el caso mono objetivo es un caso particula del multiobjetivo**."""
creator.create("FitnessMin", base.Fitness, weights=(-1.0,))
"""Ahora creamos la "plantilla" del individuo, **el cromosoma**. El individuo **será una lista** (hereda los métodos de la lista), pero tiene el atributo **FitnessMin** creado en la línea anterior. Representar los individuos como lista nos servirá en una gran cantidad de casos (lista de variables del problema)."""
creator.create("Individual", list, fitness=creator.FitnessMin)
"""El objeto toolbox funciona como una "caja de herramientas" donde **debemos registrar operaciones que nos hacen falta en el algoritmo genético**. Cosas que debemos registrar:
1. Funciones para crear tanto individuos aleatorios como la población inicial.
2. Operadores genéticos (selección, cruce y mutación).
3. La función de evaluación.
"""
toolbox = base.Toolbox()
"""Comenzamos registrando las funciones que nos permiten generar individuos aleatorios y la población incial. Empezamos por muestra aleatorias de individuos (cromosoma). **No es el individuo completo ya que no tiene el atributo fitness**."""
# Generación de un tour aleatorio
toolbox.register("indices", random.sample, range(IND_SIZE), IND_SIZE) # aquí debemos registar una función que generar una muestra de individuo
"""Podemos ver la muestra que se crea:"""
print(toolbox.indices())
"""Generamos indivuos aleatorios y población inicial"""
# Generación de inviduos y población
toolbox.register("individual", tools.initIterate, creator.Individual, toolbox.indices)
POP_SIZE=100
toolbox.register("population", tools.initRepeat, list, toolbox.individual, POP_SIZE) #
"""Vamos a ver cómo funcionan con un par de ejemplos:"""
ind = toolbox. individual() # creamos un individuo aleatorio
print(ind)
print(ind.fitness.values) # en fitness.values se guardará el fitness
pop = toolbox.population() # creamos una población aleatoria
print(pop[:5]) # imprimimos los 5 primeros individuos
"""**Definimos la función objetivo:**
1. En primer lugar calculamos la distancia entre la última ciudad y la primera
2. Recorremos dos listas la vez:
* individual[0:-1], son los elementos del primero al penúltimo
* individual[1:], son los elementos del segundo al último
Por lo tanto en cada interación, calculamos la distancia entre dos ciudades consecutivas.
**IMPORTANTE:** Siempre debemos devolver una tupla!!
"""
def evalTSP(individual):
""" Función objetivo, calcula la distancia que recorre el viajante"""
# distancia entre el último elemento y el primero
distance = distance_map[individual[-1]][individual[0]]
# distancia entre el resto de ciudades
for gene1, gene2 in zip(individual[0:-1], individual[1:]):
distance += distance_map[gene1][gene2]
return distance,
"""**Registro de operadores genéticos:**
1. Cruce ordenado.
2. Mutación mediante mezcla de índices.
3. Selección mediante torneo, tamaño del torneo igual a 3 (suele ir bien para la mayoría de problemas). Si tenemos muchas variables podemos probar a aumentarlo un poco.
4. Función de evaluación.
"""
toolbox.register("mate", tools.cxOrdered)
toolbox.register("mutate", tools.mutShuffleIndexes, indpb=0.05)
toolbox.register("select", tools.selTournament, tournsize=3)
toolbox.register("evaluate", evalTSP)
"""Función que nos permite visualizar la evolución del algoritmo. Recibe como entrada el registro de evolución."""
def plot_evolucion(log):
gen = log.select("gen")
fit_mins = log.select("min")
fit_maxs = log.select("max")
fit_ave = log.select("avg")
fig, ax1 = plt.subplots()
ax1.plot(gen, fit_mins, "b")
ax1.plot(gen, fit_maxs, "r")
ax1.plot(gen, fit_ave, "--k")
ax1.fill_between(gen, fit_mins, fit_maxs,
where=fit_maxs >= fit_mins,
facecolor="g", alpha=0.2)
ax1.set_xlabel("Generación")
ax1.set_ylabel("Fitness")
ax1.legend(["Min", "Max", "Avg"])
ax1.set_ylim([2000, 6000])
plt.grid(True)
plt.savefig("EvolucionTSP.eps", dpi=300)
"""En el main configuramos el algoritmo genético.
Ajuste de los operadores genéticos:
* *CXPB:* probabilidad de cruce
* *MUTPB:* probabilidad de mutación
Número de generaciones:
* *NGEN:* número de generaciones
El objeto **hof** almacena el mejor individuo encontrado a lo largo de las generaciones. Le tenemos que p
El objeto **stats** calcula las estadísticas de la población en cada generación. Cuando se define le tenemos que decir sobre qué se va a calcular las estadística. A continuación, se deben registrar las funciones estadísticas que se van a aplicar.
El objeto **logbook** almacena todas las estadísticas calculadas por generación en un solo objeto.
Algoritmo **eaSimple** parámetros que tenemos que pasar:
* poblacion (obligatorio)
* toolbox (obligatorio)
* probabilidad de cruce (obligatorio)
* probabilidad de mutación (obligatorio)
* número de generaciones (obligatorio)
* objeto de estadísticas (opcional)
* objeto hallofFame que almacena el mejor individuo (opcional)
* Si queremos que se muestre las estádisticas en cada generación, verbose = True (opcional)
"""
def main():
random.seed(42) # ajuste de la semilla del generador de números aleatorios
CXPB, MUTPB, NGEN = 0.7, 0.3, 120
pop = toolbox.population() # creamos la población inicial
hof = tools.HallOfFame(1)
stats = tools.Statistics(lambda ind: ind.fitness.values)
stats.register("avg", numpy.mean)
stats.register("std", numpy.std)
stats.register("min", numpy.min)
stats.register("max", numpy.max)
logbook = tools.Logbook()
pop, logbook = algorithms.eaSimple(pop, toolbox, CXPB, MUTPB, NGEN, stats=stats, halloffame=hof, verbose=True)
return hof, logbook
"""Lanzamos el algoritmo y mostramos los resultados."""
best, log = main()
print("Mejor fitness: %f" %best[0].fitness.values)
print("Mejor individuo %s" %best[0])
plot_evolucion(log) # mostamos la evolución