Why does this Genetic Algorithm give such bad solutions to a TSP?
I coded a Genetic Algorithm in Python using the DEAP library to solve a modified TSP problem, where the evaluation function is:
def evaluate(self, individual: list[int]) -> float:
total_value = 0
total_time = 0
current = self.graph.center
for idx in individual:
aux = self.graph.get_node(idx)
curr_edge = self.graph.get_edge(
current, aux)
total_value += curr_edge.value
total_time += curr_edge.time + 0.03
if total_time > self.max_time: return 100000
current = aux
total_value += self.graph.get_edge(current, self.graph.center).value
penalty = sum(
self.graph.get_node(node).weight *
(len(individual) - i) for i, node in enumerate(individual))
return (total_value + 0.2 * penalty + 0.5 * total_time)
Where edge.value is a sum of the distance between two nodes and the time it takes to traverse them. Given the graph in this pastebin link (where the structure is:
n
idx_1 weight_1 x_1 y_1
idx_2 weight_2 x_2 y_2
...
idx_n weight_n x_n y_n
m
speed_1 origin_1 dest_1
speed_2 origin_2 dest_2
...
speed_m origin_m dest_m
Where n is the number of nodes to be read, followed by the
parameters of each node and m is the number of edges to be
read, followed by the parameters of each edge.
Why is my Genetic Algorithm running so bad? Here are a few solutions I get when using different mating/mutating algorithms. Note that all runs have been made with 1000 generations and 500 individuals/generation, elitism has been used, and matingprob and mutprob are 0,99 and 0,01 respectively.
Using cxOrdered (OX) mating and ShuffleIndex mutation:
Using custom edge_recombination_crossover (ERX) and 2opt-mutation:
Annex
Code of the Algorithm class:
def stochastic_2opt(ind, indpb):
if random.random() < indpb:
i = random.randint(0, len(ind) - 1)
j = random.randint(0, len(ind) - 1)
if i > j:
i, j = j, i
ind[i:j+1] = reversed(ind[i:j+1])
return ind,
def edge_recombination_crossover(ind1: list[int], ind2: list[int]):
edge_map = {}
for idx in range(len(ind1)):
neighbors = set()
neighbors.add(ind1[(idx - 1) % len(ind1)])
neighbors.add(ind1[(idx + 1) % len(ind1)])
neighbors.add(ind2[(idx - 1) % len(ind1)])
neighbors.add(ind2[(idx + 1) % len(ind1)])
edge_map[ind1[idx]] = neighbors
curr = random.choice([ind1[0], ind2[0]])
offspring = [curr]
while len(offspring) < len(ind1):
neighbors = edge_map[curr]
next_node = None
for n in neighbors:
if n not in offspring:
next_node = n
break
if next_node is None:
rem = [n for n in ind1 if n not in offspring]
next_node = random.choice(rem)
offspring.append(next_node)
curr = next_node
return offspring, offspring
class Algorithms():
"""Class containing the diferent path-finding algorithms.
Args:
graph: The graph object where the paths will be calculated on.
"""
def __init__(self, graph: 'Graph'):
self.graph = graph
self.convert = None
self.truck_capacity = None
self.max_time = 8
def evaluate(self, individual: list[int]) -> float:
# total time = edge time + 2minutes to pick up bin.
total_value = 0
total_time = 0
current = self.graph.center
for idx in individual:
aux = self.graph.get_node(idx)
curr_edge = self.graph.get_edge(
current, aux)
total_value += curr_edge.value
total_time += curr_edge.time + 0.03
if total_time > self.max_time: return 100000
current = aux
total_value += self.graph.get_edge(current, self.graph.center).value
penalty = sum(
self.graph.get_node(node).weight *
(len(individual) - i) for i, node in enumerate(individual))
return (total_value + 0.2 * penalty + 0.5 * total_time)
def evaluate_tsp(self, individual: list[int]) -> tuple[float, ...]:
"""Evaluates the objective function value for a path.
The algorithms used for this problem are genetic algorithms and, as
such, try to minimize/maximize the value of a function to find a
solution to a problem. In this case, the problem is finding the path
in a graph that optimizes a series of objectives. Those individual
objectives form an objective function. The ``evaluate`` function checks
the result of evaluating said objective function for a given path.
Currently, the objective function gives the cost of the path, which is
the sum of the values of the edges that form the path, and a penalty,
whose objective is to try and visit higher-weighted nodes later in the
path, as running for a longer distance with a heavier load increases
the maintenance cost of the truck.
Args:
individual: The path to evaluate.
Returns:
A tuple containing the value of the objective function.
"""
return (self.evaluate([self.convert[node] for node in individual])),
def _erx(self, ind1, ind2):
a, b = edge_recombination_crossover(
[i for i in ind1], [j for j in ind2])
off1 = creator.Individual(a)
off1.fitness.values = ind1.fitness.values
off2 = creator.Individual(b)
off2.fitness.values = ind2.fitness.values
return off1, off2
def _2opt(self, ind, indpb):
a = stochastic_2opt([i for i in ind], indpb)[0]
mut = creator.Individual(ind)
return mut,
def _clone(self, ind):
new_ind = creator.Individual(ind)
new_ind.fitness.values = ind.fitness.values
return new_ind
def _define_creator(self) -> creator:
"""Defines a deap creator for the genetic algorithms.
The ``deap.creator`` module is part of the DEAP framework and it's used
to extend existing classes, adding new functionalities to them. This
function extracts the ``creator`` instantiation from the ``run_ga_tsp``
function so the code is easier to read and follow.
Inside the ``creator`` object is where the objective of the genetic
algorithm is defined, as well as what will the individuals be like.
In this case, the objective is to minimize the value of the objective
function, and the individuals are lists of integers, containing the
indices of the nodes of the graph in the order they will be visited.
Returns:
The creator defined for the genetic algorithm.
"""
if hasattr(creator, 'FitnessMin'):
del creator.FitnessMin
if hasattr(creator, 'Individual'):
del creator.Individual
creator.create("FitnessMin", base.Fitness, weights=(-1.0,))
creator.create("Individual",
list,
typecode='i',
fitness=creator.FitnessMin)
return creator
def _define_toolbox(self) -> base.Toolbox:
"""Defines a deap toolbox for the genetic algorithms.
The ``deap.base.createor`` module is part of the DEAP framework. It's
used as a container for functions, and enables the creation of new
operators by customizing existing ones. This function extracts the
``toolbox`` instantiation from the ``run_ga_tsp`` function so the code
is easier to read and follow.
In the ``toolbox`` object is where the functions used by the genetic
algorithm are defined, such as the evaluation, selection, crossover
and mutation functions.
Returns:
The toolbox defined for the genetic algorithm.
"""
nodes = [node.index for node in self.graph.node_list]
genes = [i for i in range(len(nodes))]
self.convert = {i: node for i, node in enumerate(nodes)}
toolbox = base.Toolbox()
toolbox.register("random_order", random.sample, genes, len(nodes))
toolbox.register("individual_creator", tools.initIterate,
creator.Individual, toolbox.random_order)
toolbox.register("population_creator", tools.initRepeat, list,
toolbox.individual_creator)
toolbox.register("evaluate", self.evaluate_tsp)
toolbox.register("select", tools.selTournament, tournsize=2)
toolbox.register("mate", self._erx)
toolbox.register("mutate",
self._2opt,
indpb=1.0 / self.graph.nodes)
toolbox.register("clone", self._clone)
return toolbox
def _define_ga(self, toolbox: base.Toolbox,
pop_size: int) -> tuple[list, dict, list]:
"""Defines the attributes for the Generic Algorithm.
The function defines the population, statistics and hall of fame for
the Genetic Algorithm designed to solve the Traveling Salesman Problem.
Args:
toolbox: The toolbox for the genetic algorithm.
pop_size: The size of the population.
Returns:
A tuple containing the population, statistics and hall of fame.
"""
population = toolbox.population_creator(n=pop_size)
stats = tools.Statistics(lambda ind: ind.fitness.values)
stats.register("min", np.min)
stats.register("avg", np.mean)
hof = tools.HallOfFame(30)
return population, stats, hof
def eaSimpleWithElitism(self,
population,
toolbox,
cxpb,
mutpb,
ngen,
stats=None,
halloffame=None,
verbose=__debug__):
"""This algorithm is similar to DEAP eaSimple() algorithm, with the modification that
halloffame is used to implement an elitism mechanism. The individuals contained in the
halloffame are directly injected into the next generation and are not subject to the
genetic operators of selection, crossover and mutation.
"""
logbook = tools.Logbook()
logbook.header = ['gen', 'nevals'] + (stats.fields if stats else [])
# Evaluate the individuals with an invalid fitness
invalid_ind = [ind for ind in population if not ind.fitness.valid]
fitnesses = toolbox.map(toolbox.evaluate, invalid_ind)
for ind, fit in zip(invalid_ind, fitnesses):
ind.fitness.values = fit
if halloffame is None:
raise ValueError("halloffame parameter must not be empty!")
halloffame.update(population)
hof_size = len(halloffame.items) if halloffame.items else 0
record = stats.compile(population) if stats else {}
logbook.record(gen=0, nevals=len(invalid_ind), **record)
if verbose:
print(logbook.stream)
# Begin the generational process
for gen in range(1, ngen + 1):
# Select the next generation individuals
offspring = toolbox.select(population, len(population) - hof_size)
# Vary the pool of individuals
offspring = algorithms.varAnd(offspring, toolbox, cxpb, mutpb)
# Evaluate the individuals with an invalid fitness
invalid_ind = [ind for ind in offspring if not ind.fitness.valid]
fitnesses = toolbox.map(toolbox.evaluate, invalid_ind)
for ind, fit in zip(invalid_ind, fitnesses):
ind.fitness.values = fit
# add the best back to population:
offspring.extend(halloffame.items)
# Update the hall of fame with the generated individuals
halloffame.update(offspring)
# Replace the current population by the offspring
population[:] = offspring
# Append the current generation statistics to the logbook
record = stats.compile(population) if stats else {}
logbook.record(gen=gen, nevals=len(invalid_ind), **record)
if verbose:
print(logbook.stream)
return population, logbook
def run_ga_tsp(self,
ngen: int = 100,
cxpb: float = 0.99,
mutpb: float = 0.01,
pop_size: int = 200,
dir: str | None = None,
idx: int = 0,
vrb: bool = True) -> tuple[list[int], float]:
"""Runs the Genetic Algorithm for the Traveling Salesman Problem.
This function calls the wrapper functions that define the creator,
toolbox and the attributes for the Genetic Algorithm designed to solve
the Traveling Salesman Problem. It then runs the Genetic Algorithm and
returns the best path found and its total value, while also calling the
wrapper function to plot the results.
Args:
ngen (optional): The number of generations. Defaults to 100.
cxpb (optional): The mating probability. Defaults to 0.9.
mutpb (optional): The mutation probability. Defaults to 0.1.
pop_size (optional): The size of the population. Defaults to 200.
dir (optional): The directory where the plots should be saved.
Defaults to None, in which case the plot(s) won't be saved.
idx (optional): The index for the plot to save. Defaults to 0.
vrb: (optional): Run the algorithm in verbose or non-verbose mode.
Defaults to True.
Returns:
A tuple containing the best path found and its total value.
"""
creator = self._define_creator()
toolbox = self._define_toolbox()
population, stats, hof, = self._define_ga(toolbox, pop_size)
population, logbook = self.eaSimpleWithElitism(population,
toolbox,
cxpb=cxpb,
mutpb=mutpb,
ngen=ngen,
stats=stats,
halloffame=hof,
verbose=vrb)
best = [self.convert[i] for i in hof.items[0]]
best_path = ([self.graph.center.index] + best +
[self.graph.center.index])
total_value = self.evaluate_tsp(hof[0])[0]
if vrb:
print("-- Best Ever Individual = ", best_path)
print("-- Best Ever Fitness = ", hof.items[0].fitness.values[0])
if dir:
self._plot_ga_results(best_path, logbook, dir, idx)
else:
self._plot_ga_results(best_path, logbook).show()
return best_path, total_value
Solution
After a bunch of trial and error, i've found a good solution (at least for my 50-node solution. I'll list all the changes I did:
- I've gone back and simplified my evaluation function, now it takes the value of an edge, without penalization, as I found out my penalization was causing too much of an effect on the result.
- I've added local search (memetization) on the algorithm used.
- I've decreased the HallOfFame size to 1.
- I added stagnation detection. If the algorithm doesn't improve after 25 generations, I increase the mutation rate. After 5 increases, I regenerate the population using the best individual and reset the mutation rate to the original. After 3 cycles of this, the genetic algorithm halts.
After this improvements, I finally got the following graph:
Looking at the evolution graph, you can clearly see the population resets that lead to a better path.
Any further tips will be greatly appreciated! :)
Final code:
# Previous code
def eaSimpleWithElitism(self,
population,
toolbox,
cxpb,
mutpb,
ngen,
stats=None,
halloffame=None,
verbose=__debug__):
"""This algorithm is similar to DEAP eaSimple() algorithm, with the modification that
halloffame is used to implement an elitism mechanism. The individuals contained in the
halloffame are directly injected into the next generation and are not subject to the
genetic operators of selection, crossover and mutation.
"""
logbook = tools.Logbook()
logbook.header = ['gen', 'nevals'] + (stats.fields if stats else [])
# Evaluate the individuals with an invalid fitness
invalid_ind = [ind for ind in population if not ind.fitness.valid]
fitnesses = toolbox.map(toolbox.evaluate, invalid_ind)
for ind, fit in zip(invalid_ind, fitnesses):
ind.fitness.values = fit
if halloffame is None:
raise ValueError("halloffame parameter must not be empty!")
halloffame.update(population)
hof_size = len(halloffame.items) if halloffame.items else 0
record = stats.compile(population) if stats else {}
logbook.record(gen=0, nevals=len(invalid_ind), **record)
if verbose:
print(logbook.stream)
best_val = float('inf')
gens_stagnated = 0
mut_exploder = 1
cicles = 0
# Begin the generational process
for gen in range(1, ngen + 1):
# Select the next generation individuals
offspring = toolbox.select(population, len(population) - hof_size)
# Vary the pool of individuals
offspring = algorithms.varAnd(offspring, toolbox, cxpb, mutpb)
# Evaluate the individuals with an invalid fitness
invalid_ind = [ind for ind in offspring if not ind.fitness.valid]
fitnesses = toolbox.map(toolbox.evaluate, invalid_ind)
for ind, fit in zip(invalid_ind, fitnesses):
ind.fitness.values = fit
elite = halloffame.items
for i, e in enumerate(elite):
ie = self.local_search_2opt(e)
e[:] = ie[:]
e.fitness.values = self.evaluate_tsp(e)
# add the best back to population:
offspring.extend(elite)
# Update the hall of fame with the generated individuals
halloffame.update(offspring)
# Replace the current population by the offspring
population[:] = offspring
# Append the current generation statistics to the logbook
record = stats.compile(population) if stats else {}
logbook.record(gen=gen, nevals=len(invalid_ind), **record)
if verbose:
print(logbook.stream)
val = halloffame[0].fitness.values[0]
if val < best_val:
best_val = val
gens_stagnated = 0
else:
gens_stagnated += 1
if gens_stagnated >= 25:
print("Stagnated")
if mut_exploder < 5:
toolbox.register("mutate",
tools.mutShuffleIndexes,
indpb=1/(self.graph.nodes - mut_exploder))
mut_exploder += 1
else:
print("Reseting...")
for i, ind in enumerate(population):
population[i] = halloffame.items[0]
mut_exploder = 1
toolbox.register("mutate",
tools.mutShuffleIndexes,
indpb=1/(self.graph.nodes))
cicles += 1
gens_stagnated = 0
if cicles >= 3: break
return population, logbook
def run_ga_tsp(self,
ngen: int = 3000,
cxpb: float = 0.7,
mutpb: float = 0.2,
pop_size: int = 1000,
dir: str | None = None,
idx: int = 0,
vrb: bool = True) -> tuple[list[int], float]:
"""Runs the Genetic Algorithm for the Traveling Salesman Problem.
This function calls the wrapper functions that define the creator,
toolbox and the attributes for the Genetic Algorithm designed to solve
the Traveling Salesman Problem. It then runs the Genetic Algorithm and
returns the best path found and its total value, while also calling the
wrapper function to plot the results.
Args:
ngen (optional): The number of generations. Defaults to 100.
cxpb (optional): The mating probability. Defaults to 0.9.
mutpb (optional): The mutation probability. Defaults to 0.1.
pop_size (optional): The size of the population. Defaults to 200.
dir (optional): The directory where the plots should be saved.
Defaults to None, in which case the plot(s) won't be saved.
idx (optional): The index for the plot to save. Defaults to 0.
vrb: (optional): Run the algorithm in verbose or non-verbose mode.
Defaults to True.
Returns:
A tuple containing the best path found and its total value.
"""
random.seed(169)
if not self.graph.distances: self.graph.set_distance_matrix()
creator = self._define_creator()
toolbox = self._define_toolbox()
population, stats, hof, = self._define_ga(toolbox, pop_size)
population, logbook = self.eaSimpleWithElitism(population,
toolbox,
cxpb=cxpb,
mutpb=mutpb,
ngen=ngen,
stats=stats,
halloffame=hof,
verbose=vrb)
best = [i for i in hof.items[0]]
best += [best[0]]
total_value = self.evaluate_tsp(best)[0]
if vrb:
print("-- Best Ever Individual = ", best)
print("-- Best Ever Fitness = ", total_value)
if dir:
self._plot_ga_results(best, logbook, dir, idx)
else:
self._plot_ga_results(best, logbook).show()
return best, total_value
def _define_toolbox(self) -> base.Toolbox:
"""Defines a deap toolbox for the genetic algorithms.
The ``deap.base.createor`` module is part of the DEAP framework. It's
used as a container for functions, and enables the creation of new
operators by customizing existing ones. This function extracts the
``toolbox`` instantiation from the ``run_ga_tsp`` function so the code
is easier to read and follow.
In the ``toolbox`` object is where the functions used by the genetic
algorithm are defined, such as the evaluation, selection, crossover
and mutation functions.
Returns:
The toolbox defined for the genetic algorithm.
"""
toolbox = base.Toolbox()
toolbox.register("random_order",
random.sample,
range(self.graph.nodes),
self.graph.nodes)
toolbox.register("individual_creator", tools.initIterate,
creator.Individual, toolbox.random_order)
toolbox.register("population_creator", tools.initRepeat, list,
toolbox.individual_creator)
toolbox.register("evaluate", self.evaluate_tsp)
toolbox.register("select", tools.selTournament, tournsize=2)
toolbox.register("mate", tools.cxOrdered)
toolbox.register("mutate",
tools.mutShuffleIndexes,
indpb=1.0/self.graph.nodes)
toolbox.register("clone", self._clone)
return toolbox
# Rest of code
- replace CRLF characters in middle of row for unquoted csv file using python
- Python Unittest: No tests discovered in Visual Studio Code
- How to add separator to menuBar in pyqt5
- Does Lua support Decorators?
- 'The parameter `image` must be a 2-dimensional array'
- Pytest caplog not capturing logs
- 'virtualenv' is not recognized as an internal or external command, operable program or batch file
- Transpose list of lists
- How do I transpose rows to columns with a triangular array?
- How do I save word cloud as .png in python?
- OpenAI Assistants with citations like【4:2†source】and citeturnXfileY
- How can I make cuts into a numerical column based on a categorical column
- How to make an immutable object in Python?
- Can or How to use Python asyncio on Google Cloud Functions?
- Accessing dict_keys element by index in Python3
- Resize images in python using PIL
- eglInitialize failed with EGL_NOT_INITIALIZED
- how can I get the name of svg element when i click on it in nicegui
- Python - Convert String date "17 Apr" to Date "17-04-2018"
- Making file hidden in Windows using Python blocks file writing
- Why is the continued fraction expansion of arctangent combined with half-angle formula not working with Machin-like series?
- Why is my Python code displaying CSV file with right sided alignment?
- Visual Studio Code terminal doesn't activate Conda environment
- Add a new row as the average of columns
- Insert a list of dictionary using sqlalchemy efficiently
- Trying to create a Menu Bar Class in Tkinter but I can't get it to work
- "PACKAGES DO NOT MATCH THE HASHES" error with pip
- Pandas get the most frequent values of a column
- pyserial doesnt read full line
- replace part of the string in pandas data frame