Paralellisierung eines genetischen Algorithmus in Python ist langsamer ⇐ Python

[Anonymous]

Ich habe einen genetischen Algorithmus kodiert, um TSP mithilfe der DEAP -Bibliothek von Python zu lösen. Ich habe meine eigene Graph -Klasse und eine Algorithmusklasse implementiert, die die GA in einer Graphinstanz ausführt. Beim Hinzufügen einer Paralelisierung innerhalb der Algorithmus._define_toolbox () dauert meine Hauptklasse länger. Ich habe gelesen, wie man die Serialisierung mit der Multiprozziereinbibliothek mit Deap anwendet, und ich weiß, dass eine Hauptmethode erforderlich ist, aber mein GA wird von den Haupt- und Läufen langsamer als die Verwendung von Paralellisierung. PrettyPrint-Override ">

Code: Select all

class Algorithms():
# prev. code
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", tools.cxOrdered)
toolbox.register("mutate",
tools.mutShuffleIndexes,
indpb=1.0 / self.graph.nodes)

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 run_ga_tsp(self,
ngen: int = 100,
cxpb: float = 0.9,
mutpb: float = 0.1,
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
< /code>
 Main.py
import os
from model import Graph
from algorithms import Algorithms

def run():
"""An example of using the model & algorithms modules."""
g = Graph()
print("Loading graph")
g.populate_from_file(os.getcwd() + "/files/test2.txt")
#g.populate_from_file(os.getcwd() + "/Algorithm/AlgoCode/files/test2.txt")
print("Graph loaded")
algo = Algorithms(g)
_, v = algo.run_ga_tsp(ngen=500,
pop_size=500,
idx=0,
dir=os.getcwd() + "/plots",
vrb=False)
print(f"Total value (TSP): {v}")

def main():
run()

if __name__ == '__main__':
main()
< /code>
Wie angegeben, habe ich versucht, < /p>
 hinzuzufügenpool = multiprocessing.Pool()
toolbox.register("map", pool.map)

zu Algorithmuss._define_toolbox () , aber ohne Erfolg.