Вопрос или проблема
Я написал генетический алгоритм на Python с использованием библиотеки DEAP для решения модифицированной задачи коммивояжера, где функция оценки:
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)
Где edge.value — это сумма расстояния между двумя узлами и времени, необходимого для их преодоления. Учитывая граф в этом ссылке на pastebin (где структура:
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
Где n — это количество узлов для чтения, за которым следуют
параметры каждого узла, а m — это количество рёбер для
чтения, за которым следуют параметры каждого ребра.
Почему мой генетический алгоритм работает настолько плохо? Вот несколько решений, которые я получаю, используя различные алгоритмы спаривания/мутации. Обратите внимание, что все запуски проведены с 1000 поколениями и 500 индивидами/поколение, использовался элитизм, а мат.prob и мутация.prob равны 0,99 и 0,01 соответственно.
Используя спаривание cxOrdered (OX) и мутацию ShuffleIndex:
Используя пользовательскую перестановку рёбер (ERX) и мутацию на 2 оптимизации:
Приложение
Релевантный код класса алгоритма:
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():
"""Класс, содержащий различные алгоритмы поиска пути.
Аргументы:
graph: Граф, на котором будут рассчитываться пути.
"""
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:
# общее время = время на ребре + 2 минуты, чтобы забрать контейнер.
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, ...]:
"""Оценивает значение целевой функции для пути.
Алгоритмы, используемые в этой задаче, являются генетическими алгоритмами и, как таковые, пытаются минимизировать/максимизировать значение функции для поиска решения задачи. В данном случае, задача заключается в нахождении пути в графе, который оптимизирует серию показателей. Эти показатели формируют целевую функцию. Функция ``evaluate`` проверяет результат оценки этой целевой функции для заданного пути.
В настоящее время, целевая функция возвращает стоимость пути, которая равна сумме значений рёбер, формирующих путь, и штрафу, цель которого — попытка посетить узлы с более высокой массой позже в пути, так как перемещение на большую дистанцию с более тяжёлой нагрузкой увеличивает стоимость обслуживания грузовика.
Аргументы:
individual: Путь для оценки.
Returns:
Кортеж, содержащий значение целевой функции.
"""
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:
"""Определяет deap creator для генетических алгоритмов.
Модуль ``deap.creator`` является частью фреймворка DEAP и используется для расширения существующих классов, добавляя новые функциональности. Эта функция извлекает инстанцию ``creator`` из функции ``run_ga_tsp``, чтобы код было легче читать и следовать.
Внутри объекта ``creator`` определяется цель генетического алгоритма, а также то, каким будут индивиды. В данном случае, цель — минимизировать значение целевой функции, и индивиды — это списки целых чисел, содержащие индексы узлов графа в порядке, в котором они будут посещены.
Returns:
Создатель, определённый для генетического алгоритма.
"""
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:
"""Определяет deap toolbox для генетических алгоритмов.
Модуль ``deap.base.createor`` является частью фреймворка DEAP. Он используется в качестве контейнера для функций, а также позволяет создавать новые операторы, настраивая существующие. Эта функция извлекает инстанцию ``toolbox`` из функции ``run_ga_tsp`` для облегчения чтения и следованию коду.
В объекте ``toolbox`` определяются функции, используемые генетическим алгоритмом, такие как функции оценки, селекции, кроссовера и мутации.
Returns:
Инструментарий определён для генетического алгоритма.
"""
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]:
"""Определяет атрибуты для генетического алгоритма.
Функция определяет популяцию, статистику и галерею славы для генетического алгоритма, предназначенного для решения задачи коммивояжера.
Аргументы:
toolbox: Инструментарий для генетического алгоритма.
pop_size: Размер популяции.
Returns:
Кортеж, содержащий популяцию, статистику и галерею славы.
"""
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__):
"""Этот алгоритм похож на DEAP eaSimple() алгоритм, с модификацией, что halloffame используется для реализации механизма элитизма. Индивиды, содержащиеся в halloffame, непосредственно внедряются в следующее поколение и не подвержены генетическим операторам селекции, кроссовера и мутации.
"""
logbook = tools.Logbook()
logbook.header = ['gen', 'nevals'] + (stats.fields if stats else [])
# Оценивает индивидов с недопустимой пригодностью
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.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)
# Начало процесса поколений
for gen in range(1, ngen + 1):
# Выбор следующих поколений индивидов
offspring = toolbox.select(population, len(population) - hof_size)
# Разнообразие пула индивидов
offspring = algorithms.varAnd(offspring, toolbox, cxpb, mutpb)
# Оценивает индивидов с недопустимой пригодностью
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
# добавить лучших в популяцию:
offspring.extend(halloffame.items)
# Обновить галерею славы с созданными индивидами
halloffame.update(offspring)
# Заменить текущую популяцию на потомков
population[:] = offspring
# Добавить статистику текущего поколения в логбук
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]:
"""Запускает генетический алгоритм для задачи коммивояжера.
Эта функция вызывает функции-оболочки, которые определяют creator, инструментарием и атрибутами для генетического алгоритма, предназначенного для решения задачи коммивояжера. Затем он запускает генетический алгоритм и возвращает наилучший найденный путь и его общую стоимость, также вызывая функцию-оболочку для построения результатов.
Аргументы:
ngen (optional): Количество поколений. По умолчанию — 100.
cxpb (optional): Вероятность спаривания. По умолчанию — 0.9.
mutpb (optional): Вероятность мутации. По умолчанию — 0.1.
pop_size (optional): Размер популяции. По умолчанию — 200.
dir (optional): Директория, где должны быть сохранены построения.
По умолчанию None, в этом случае построение(я) не будут сохранены.
idx (optional): Индекс для построения, которое сохраняется. По умолчанию — 0.
vrb: (optional): Запустить алгоритм в режиме с вывода выполнения или без.
По умолчанию — True.
Returns:
Кортеж, содержащий наилучший найденный путь и его полную стоимость.
"""
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_path)
print("-- Наилучшая когда-либо пригодность = ", 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
```
После множества проб и ошибок я нашёл хорошее решение (по крайней мере для моего решения на 50 узлов). Я перечислю все изменения, которые сделал:
- Я вернулся назад и упростил свою функцию оценки, теперь она берёт значение ребра, без штрафов, так как я выяснил, что мои штрафы оказывали слишком большое влияние на результат.
- Я добавил локальный поиск (меметизация) в используемый алгоритм.
- Я уменьшил размер галереи славы до 1.
- Я добавил обнаружение стагнации. Если алгоритм не улучшается после 25 поколений, я увеличиваю скорость мутации. После 5 увеличений я восстанавливаю популяцию, используя лучшего индивида и сбрасываю скорость мутации на исходную. После 3 циклов этого алгоритм генетического алгоритма завершает работу.
После этих улучшений я наконец получил следующий график:
Смотря на график эволюции, вы можете чётко видеть, как сброс популяции привёл к более лучшему пути.
Любые дальнейшие советы будут очень полезны! 🙂
Окончательный код:
# Предыдущий код
def eaSimpleWithElitism(self,
population,
toolbox,
cxpb,
mutpb,
ngen,
stats=None,
halloffame=None,
verbose=__debug__):
"""Этот алгоритм похож на DEAP eaSimple() алгоритм, с модификацией, что halloffame используется для реализации механизма элитизма. Индивиды, содержащиеся в halloffame, непосредственно внедряются в следующее поколение и не подвержены генетическим операторам селекции, кроссовера и мутации.
"""
logbook = tools.Logbook()
logbook.header = ['gen', 'nevals'] + (stats.fields if stats else [])
# Оценивает индивидов с недопустимой пригодностью
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 не может быть пустым!")
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
# Начало процесса поколений
for gen in range(1, ngen + 1):
# Выбор будущих поколений индивидов
offspring = toolbox.select(population, len(population) - hof_size)
# Разнообразие пула индивидов
offspring = algorithms.varAnd(offspring, toolbox, cxpb, mutpb)
# Оценивает индивидов с недопустимой пригодностью
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)
# добавляет лучших в популяцию:
offspring.extend(elite)
# Обновить галерею славы с созданными индивидами
halloffame.update(offspring)
# Заменить текущей популяцией потомков
population[:] = offspring
# Добавить статистику текущего поколения в логбук
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("Застопорилось")
if mut_exploder < 5:
toolbox.register("mutate",
tools.mutShuffleIndexes,
indpb=1/(self.graph.nodes - mut_exploder))
mut_exploder += 1
else:
print("Сброс...")
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]:
"""Запускает генетический алгоритм для задачи коммивояжера.
Эта функция вызывает функции-оболочки, которые определяют creator, инструментарием и атрибутами для генетического алгоритма, предназначенного для решения задачи коммивояжера. Затем он запускает генетический алгоритм и возвращает наилучший найденный путь и его общую стоимость, также вызывая функцию-оболочку для построения результатов.
Аргументы:
ngen (optional): Количество поколений. По умолчанию — 100.
cxpb (optional): Вероятность спаривания. По умолчанию — 0.9.
mutpb (optional): Вероятность мутации. По умолчанию — 0.1.
pop_size (optional): Размер популяции. По умолчанию — 200.
dir (optional): Директория, где должны быть сохранены построения.
По умолчанию None, в этом случае построение(я) не будут сохранены.
idx (optional): Индекс для построения, которое сохраняется. По умолчанию — 0.
vrb: (optional): Запустить алгоритм в режиме с вывода выполнения или без.
По умолчанию — True.
Returns:
Кортеж, содержащий наилучший найденный путь и его полную стоимость.
"""
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)
print("-- Наилучшая когда-либо пригодность = ", 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:
"""Определяет deap toolbox для генетических алгоритмов.
Модуль ``deap.base.createor`` является частью фреймворка DEAP. Он используется в качестве контейнера для функций, а также позволяет создавать новые операторы, настраивая существующие. Эта функция извлекает инстанцию ``toolbox`` из функции ``run_ga_tsp`` для облегчения чтения и следованию коду.
В объекте ``toolbox`` определяются функции, используемые генетическим алгоритмом, такие как функции оценки, селекции, кроссовера и мутации.
Returns:
Инструментарий определён для генетического алгоритма.
"""
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
# Оставшийся код
Ответ или решение
Генетические алгоритмы (ГА) являются популярной методикой оптимизации, используемой для решения комбинаторных задач, таких как задача коммивояжера (TSP). Однако в Вашем случае производительность алгоритма оказалась ниже ожидаемой, чего можно было бы ожидать по нескольким причинам. Давайте разберем подробно, почему это произошло и что можно сделать, чтобы улучшить результаты.
### Теория
Генетический алгоритм – это эволюционная методология, которая имитирует процесс естественного отбора. В общем случае генетический алгоритм начинается с случайной популяции решений (индивидов) и постепенно улучшает ее путем селекции, кроссовера и мутации, направленных на минимизацию или максимизацию функции оценки.
Проблема коммивояжера, TSP, заключается в нахождении кратчайшего возможного маршрута, который позволяет посетить каждый город ровно один раз и вернуться в исходный пункт. Это задача NP-полного класса сложности, что означает, что число возможных решений экспоненциально возрастает с увеличением числа узлов.
В Вашем случае генетический алгоритм был использован для решения модифицированной задачи TSP, где в оценке маршрута учитывается суммарное значение вдоль пути, время, необходимое для его прохождения, и штраф за посещение узлов в определенном порядке. Если общее время превышает максимально допустимое, решение оценивается значением в 100000, которое значимо увеличивает стоимость маршрута.
### Пример
Рассмотрим Ваш алгоритм с использованием DEAP. Вы использовали несколько методов кроссовера (например, cxOrdered и edge_recombination_crossover) и мутаций (например, mutShuffleIndexes и 2opt-модификация). Однако главный недостаток заключался в области функции оценки, которая оказалась чрезмерно чувствительной к “пенализациям” (штрафам), усложняя алгоритму нахождение оптимальных решений.
Кроме этого, настройка вероятностей операций кроссовера и мутации также играет ключевую роль. Высокая вероятность кроссовера (около 0.99) вместе с низкой вероятностью мутации означают, что алгоритм склонен к сохранению особей с плохими характеристиками.
### Применение
#### Оптимизация функции оценки
Вы уже сделали значительный шаг, упростив функцию оценки, убрав ненужные штрафы. Это улучшило результаты и уменьшило влияние штрафных коэффициентов, которые слишком сильно искажают оценку.
#### Введение локального поиска
Добавление локального поиска (например, 2-оптимизация) помогает улучшить схождения, потому что позволяет исследовать близлежащие решения более эффективно, внося улучшения в маршруты путем перестановки пар узлов для уменьшения общей длины пути.
#### Модификация параметров
Изменение размера популяции, вероятности мутации и методов обработки стагнации – это эффективные способы избегания попадания в локальные минимумы. Например, увеличение вероятности мутации может способствовать более широкому исследованию пространства поиска.
Вы также добавили механизм, который увеличивает вероятность мутации при обнаружении стагнации (отсутствия улучшений) в течение определенного числа поколений. Генерация новой популяции на основе наилучшего найденного решения после нескольких циклов стагнации позволила избежать давления на процесс оптимизации от локальных минимумов.
#### Реализация адаптивности
Алгоритм должен адаптироваться к стагнации и менять свои параметры динамически в случае, если не наблюдается улучшений. Это позволит эффективно использовать вычислительные ресурсы.
### Заключение
Подводя итог, в вашем случае одной из основных причин плохих решений оказалась слишком сложная функция оценки, чрезмерно чувствительная к штрафам, что вы уже исправили. Благодаря добавлению локального поиска и введению адаптивных механизмов обработки стагнации, ваш генетический алгоритм теперь способен находить лучшие решения, избегая локальных минимумов.
Совершенствование этого подхода может включать в себя точную настройку параметров алгоритма, увеличение разнообразия в сформированных особях и тестирование других подобных частичных решений, например, с использованием гибридных методов, которые могут еще улучшить результаты.
Разработка и настройка эффективного генетического алгоритма – сложная задача, требующая экспериментов и тестирования. Ваши попытки уже привели к заметным улучшениям, и дальнейшая работа в этом направлении может еще больше оптимизировать результаты.