На этом шаге мы рассмотрим решение этой задачи с использованием генетического алгоритма.
На 45 шаге мы решили классическую криптоарифметическую цифровую задачу SEND + MORE = MONEY, используя структуру с ограничениями. Эта задача может быть решена за разумное время и с помощью генетического алгоритма.
Одной из самых больших трудностей при формулировании задачи для ее решения с помощью генетического алгоритма является определение того, как ее представить. Удобное представление для криптоарифметических задач - использование индексов списка в виде цифр.
Abbasian R., Mazloom М. Solving Cryptarithшetic Рrоblems Using Parallel Genetic Algorithш // Second lntemational Conference on Coшputer and Electrical Engineering, 2009.
Таким образом, для представления десяти возможных цифр (0, 1, 2, 3, 4, 5, 6, 7, 8, 9) требуется список из десяти элементов. Символы, которые нужно найти в задаче, можно затем перемещать с места на место. Например, если есть подозрение, что решение задачи включает в себя символ Е, представленный цифрой 4, то list[4] = "Е". В записи SEND + MORE = MONEY используются восемь различных букв (S, Е, N, D, М, О, R, Y), так что два слота в массиве останутся пустыми. Их можно заполнить пробелами без указания буквы.
Хромосома, представляющая задачу SEND + MORE = MONEY, выражена в виде SendMoreMoney2. Обратите внимание на то, что метод fitness() поразительно похож на satisfied() из SendMoreMoneyConstraint 45 шага.
from __future__ import annotations from typing import Tuple, List from chromosome import Chromosome from genetic_algorithm import GeneticAlgorithm from random import shuffle, sample from copy import deepcopy class SendMoreMoney2(Chromosome): def __init__(self, letters: List[str]) -> None: self.letters: List[str] = letters def fitness(self) -> float: s: int = self.letters.index("S") e: int = self.letters.index("E") n: int = self.letters.index("N") d: int = self.letters.index("D") m: int = self.letters.index("M") o: int = self.letters.index("O") r: int = self.letters.index("R") y: int = self.letters.index("Y") send: int = s * 1000 + e * 100 + n * 10 + d more: int = m * 1000 + o * 100 + r * 10 + e money: int = m * 10000 + o * 1000 + n * 100 + e * 10 + y difference: int = abs(money - (send + more)) return 1 / (difference + 1) @classmethod def random_instance(cls) -> SendMoreMoney2: letters = ["S", "E", "N", "D", "M", "O", "R", "Y", " ", " "] shuffle(letters) return SendMoreMoney2(letters) def crossover(self, other: SendMoreMoney2) -> Tuple[SendMoreMoney2, SendMoreMoney2]: child1: SendMoreMoney2 = deepcopy(self) child2: SendMoreMoney2 = deepcopy(other) idx1, idx2 = sample(range(len(self.letters)), k=2) l1, l2 = child1.letters[idx1], child2.letters[idx2] child1.letters[child1.letters.index(l2)], child1.letters[idx2] = child1.letters[idx2], l2 child2.letters[child2.letters.index(l1)], child2.letters[idx1] = child2.letters[idx1], l1 return child1, child2 def mutate(self) -> None: # поменять две буквы местами idx1, idx2 = sample(range(len(self.letters)), k=2) self.letters[idx1], self.letters[idx2] = self.letters[idx2], self.letters[idx1] def __str__(self) -> str: s: int = self.letters.index("S") e: int = self.letters.index("E") n: int = self.letters.index("N") d: int = self.letters.index("D") m: int = self.letters.index("M") o: int = self.letters.index("O") r: int = self.letters.index("R") y: int = self.letters.index("Y") send: int = s * 1000 + e * 100 + n * 10 + d more: int = m * 1000 + o * 100 + r * 10 + e money: int = m * 10000 + o * 1000 + n * 100 + e * 10 + y difference: int = abs(money - (send + more)) return f"{send} + {more} = {money} Разница: {difference}"
Однако существует серьезное различие между методом satisfied() и методом fitness(), приведенным на этом шаге. Здесь мы возвращаем 1 / (difference + 1). difference - это абсолютное значение разности между MONEY и SEND + MORE. Оно показывает, насколько далека данная хромосома от решения задачи. Если бы мы пытались минимизировать fitness(), то возвращения одного лишь значения difference было бы достаточно. Но поскольку GeneticAlgorithm пытается максимизировать fitness(), необходимо вычислить обратное значение, чтобы меньшие значения выглядели как большие, и поэтому мы делим 1 на difference. Для того чтобы difference(0) было равно не fitness(0), a fitness(l), к difference сначала прибавляется 1. В таблице 1 показано, как это работает.
| difference | difference + 1 | fitness(l / (difference + 1)) |
|---|---|---|
| 0 | 1 | 1,000 |
| 1 | 2 | 0,500 |
| 2 | 3 | 0,250 |
| 3 | 4 | 0,125 |
Помните: чем меньше разность, тем лучше и чем больше жизнеспособность, тем лучше. Поскольку данная формула объединяет эти два фактора, то она хорошо работает. Деление 1 на значение жизнеспособности - простой способ преобразования задачи минимизации в задачу максимизации. Однако это вносит некоторые сдвиги, так что результат оказывается ненадежным.
Например, мы могли бы получить больше чисел, находящихся ближе к 0, чем к 1, если бы просто делили 1 на равномерное распределение целых чисел, которое с учетом особенностей интерпретации
типичными микропроцессорами чисел с плавающей точкой могло бы привести к неожиданным результатам. Альтернативный способ превратить задачу минимизации в задачу максимизации - просто
сменить знак (плюс на минус). Однако это будет работать только в том случае, если изначально все значения положительные.
В методе random_instance() используется функция shuffle() из модуля random. Метод crossover() выбирает два случайных индекса в списках letters обеих хромосом и переставляет буквы так, чтобы одна из букв первой хромосомы оказалась на том же месте во второй хромосоме и наоборот. Он выполняет эти перестановки в дочерних хромосомах, так что размещение букв в двух дочерних хромосомах оказывается комбинацией родительских хромосом. Метод mutate() меняет местами две случайные буквы в списке letters.
SendMoreMoney2 подключается к GeneticAlgorithm так же легко, как и SimpleEquation. Имейте в виду: это довольно сложная задача и ее выполнение займет много времени, если неудачно настроить исходные параметры.
Но даже при правильной настройке существует определенный элемент случайности! Задача может быть решена в течение нескольких секунд или нескольких минут. К сожалению, такова природа генетических алгоритмов.
if __name__ == "__main__": initial_population: List[SendMoreMoney2] = \ [SendMoreMoney2.random_instance() for _ in range(1000)] ga: GeneticAlgorithm[SendMoreMoney2] = \ GeneticAlgorithm(initial_population=initial_population, threshold=1.0, max_generations=1000, mutation_chance = 0.2, crossover_chance = 0.7, selection_type=GeneticAlgorithm.SelectionType.ROULETTE) result: SendMoreMoney2 = ga.run() print ( result)
Следующие результаты были получены при запуске алгоритма, при котором задача была решена за одиннадцать поколений с использованием 1000 особей в каждом поколении, созданном ранее. Проверьте, удастся ли вам настроить параметры GeneticAlgorithm так, чтобы получить аналогичный результат с меньшим количеством особей. Вам не кажется, что этот алгоритм лучше работает с отбором по методу рулетки, чем с турнирным отбором?
Генерация 0 Лучшая 0.07142857142857142 Среднее 0.00020336925100772904 Генерация 1 Лучшая 0.25 Среднее 0.011841586891375148 Генерация 2 Лучшая 0.5 Среднее 0.04592748302654117 Генерация 3 Лучшая 0.5 Среднее 0.08623172328056587 Генерация 4 Лучшая 0.5 Среднее 0.14916778635929773 Генерация 5 Лучшая 0.5 Среднее 0.20205430672003463 Генерация 6 Лучшая 0.5 Среднее 0.2494528850226178 Генерация 7 Лучшая 0.5 Среднее 0.28576921796287247 Генерация 8 Лучшая 0.5 Среднее 0.316173401968973 Генерация 9 Лучшая 0.5 Среднее 0.34783247319352684 Генерация 10 Лучшая 0.5 Среднее 0.35962658587203367 8542 + 915 = 9457 Разница: 0
На следующем шаге мы рассмотрим оптимизацию сжатия списка.
