На этом шаге мы начнем реализовывать этот алгоритм.
Генетические алгоритмы часто являются узкоспециализированными и рассчитаны на конкретное применение. В этом и следующем шагах мы построим обобщенный генетический алгоритм. Его можно использовать для множества задач, но он не особенно хорошо приспособлен ни для одной из них. Алгоритм будет включать в себя некоторые настраиваемые параметры, но наша цель состоит в том, чтобы показать его основы, а не настраиваемость.
Прежде всего определим интерфейс для особей, с которыми может работать универсальный алгоритм. Абстрактный класс Chromosome определяет четыре основных свойства. Хромосома должна уметь:
- определять собственную жизнеспособность;
- создавать экземпляр со случайно выбранными генами (для использования при заполнении первого поколения);
- реализовывать кроссинговер (объединяться с другим объектом того же типа, чтобы создавать потомков), другими словами, скрещиваться с другой хромосомой;
- мутировать - вносить в себя небольшое случайное изменение.
Вот код Chromosome, в котором реализованы эти четыре свойства (листинг 5.1).
from __future__ import annotations from typing import TypeVar, Tuple, Type from abc import ABC, abstractmethod T = TypeVar('T', bound='Chromosome') #чтобы возвращать self # Базовый класс для всех хромосом; все методы должны быть переопределены class Chromosome(ABC): @abstractmethod def fitness(self) -> float: ... @classmethod @abstractmethod def random_instance(cls: Type[T]) -> T: ... @abstractmethod def crossover(self: T, other: T) -> Tuple[T, T]: ... @abstractmethod def mutate(self) -> None: ...
Возможно, вы обратили внимание на то, что в конструкторе этого класса TypeVar Т связан с Chromosome. Это означает, что все, что заполняет переменную типа Т, должно
быть экземпляром класса Chromosome или подкласса Chromosome.
Мы реализуем сам алгоритм (код, который будет манипулировать хромосомами) как параметризованный класс, открытый для создания подклассов для будущих специализированных приложений. Но прежде, чем сделать это, вернемся к описанию генетического алгоритма, представленного в начале этого раздела, и четко определим шаги, которые он должен выполнить.
- Создать начальную популяцию случайных хромосом для первого поколения алгоритма.
- Измерить жизнеспособность каждой хромосомы в этом поколении популяции. Если жизнеспособность какой-то из них превышает пороговое значение, то вернуть его и закончить работу алгоритма.
- Выбрать для размножения несколько особей. С самой высокой вероятностью для размножения выбираются наиболее жизнеспособные особи.
- Скрестить (объединить) с некоторой вероятностью часть из выбранных хромосом, чтобы создать потомков, представляющих популяцию следующего поколения.
- Выполнить мутацию: мутируют, как правило, с низкой вероятностью некоторые из хромосом. На этом формирование популяции нового поколения завершено, и она заменяет популяцию предыдущего поколения.
- Если максимально допустимое количество поколений не получено, то вернуться к шагу 2. Если максимально допустимое количество поколений получено, вернуть наилучшую хромосому, найденную до сих пор.
На обобщенной схеме генетического алгоритма (рисунок 1) недостает многих важных деталей.
Рис.1. Обобщенная схема генетического алгоритма
Сколько хромосом должно быть в популяции? Какой порог останавливает алгоритм? Как следует выбирать хромосомы для размножения? Как они должны скрещиваться и с какой вероятностью? С какой вероятностью должны происходить мутации? Сколько поколений нужно создать?
Все эти точки будут настраиваться в классе GeneticAlgorithm. Мы будем определять этот класс по частям, чтобы обсуждать каждую отдельно.
from __future__ import annotations from typing import TypeVar, Generic, List, Tuple, Callable from enum import Enum from random import choices, random from heapq import nlargest from statistics import mean from chromosome import Chromosome C = TypeVar('C', bound=Chromosome) # тип хромосом class GeneticAlgorithm(Generic[C]): SelectionType = Enum("SelectionType", "ROULETTE TOURNAMENT")
GeneticAlgorithm принимает параметризованный тип, который соответствует Chromosome и называется С. Перечисление SelectionType является внутренним типом, используемым для определения метода отбора, применяемого в алгоритме. Существует два наиболее распространенных метода отбора для генетического алгоритма - отбор методом рулетки (иногда называемый пропорциональным отбором по жизнеспособности) и турнирный отбор. Первый дает каждой хромосоме шанс быть отобранной пропорционально ее жизнеспособности. При турнирном отборе определенное количество случайно выбранных хромосом борются друг с другом и выбираются обладающие лучшей жизнеспособностью:
def __init__(self, initial_population: List[C], threshold: float,
max_generations: int = 100, mutation_chance: float = 0.01,
crossover_chance: float = 0.7,
selection_type: SelectionType = SelectionType.TOURNAMENT) -> None:
self._population: List[C] = initial_population
self._threshold: float = threshold
self._max_generations: int = max_generations
self._mutation_chance: float = mutation_chance
self._crossover_chance: float = crossover_chance
self._selection_type: GeneticAlgorithm.SelectionType = selection_type
self._fitness_key: Callable = type(self._population[0]).fitness
В приведенном коде представлены все свойства генетического алгоритма, которые будут настроены в момент создания посредством выполнения метода __init__(). initial_population - хромосомы первого поколения алгоритма, threshold - порог жизнеспособности, который указывает на то, что решение задачи, над которым бьется генетический алгоритм, найдено. max_generations - максимальное число поколений, которое можно пройти. Если мы прошли столько поколений и не было найдено решение с уровнем жизнеспособности, превышающим threshold, то будет возвращено лучшее из найденных решений. mutation_chance - это вероятность мутации каждой хромосомы в каждом поколении. crossover_chance - вероятность того, что у двух родителей, отобранных для размножения, появятся потомки, представляющие собой смесь родительских генов, в противном случае они будут просто дубликатами родителей. Наконец, selection_tyре - это тип метода отбора, описанный в enum SelectionType.
Описанный ранее метод __init__() принимает длинный список параметров, большинство которых имеют значения по умолчанию. Они устанавливают версии экземпляров настраиваемых свойств, которые мы только что обсуждали. В наших примерах _population инициализируется случайным набором хромосом с помощью метода random_instance() класса Chromosome. Другими словами, первое поколение хромосом состоит из случайных особей. Это точка потенциальной оптимизации для более сложного генетического алгоритма. Вместо того чтобы начинать с чисто случайных особей, первое поколение благодаря некоторому знанию конкретной задачи может содержать особей, находящихся ближе к решению. Это называется посевом.
_fitness_key - ссылка на метод, который мы будем использовать в GeneticAlgorithm для расчета жизнеспособности хромосомы. Напомню, что этот класс должен работать с любым подклассом Chromosome. Следовательно, функции _fitness_key() будут разными в разных подклассах. Чтобы получить их, воспользуемся методом type() для ссылки на конкретный подкласс Chromosome, для которого мы хотим определить жизнеспособность.
На следующем шаге мы закончим изучение этого вопроса.
