На этом шаге мы проведем тестирование созданного алгоритма.

    Параметризованный генетический алгоритм GeneticAlgorithm будет работать с любым типом, который реализует Chromosome. В качестве теста выполним простую задачу, которую легко решить традиционными методами. Мы попробуем найти максимизирующие значения для уравнения 6х - х² + 4у - у² - другими словами, значения x и y, при которых результат этого уравнения будет наибольшим.

    Для того чтобы найти максимизирующие значения, можно использовать математический анализ - взять частные производные и установить каждую из них равной нулю. Результатом будет х = 3 и у = 2. Сможет ли наш генетический алгоритм получить тот же результат без применения математического анализа? Давайте разберемся.

from __future__ import annotations
from typing import Tuple, List
from chromosome import Chromosome
from genetic_algorithm import GeneticAlgorithm
from random import randrange, random
from copy import deepcopy

class SimpleEquation(Chromosome):
    def __init__(self, x: int, y: int) -> None:
        self.x: int = x
        self.y: int = y

    def fitness(self) -> float: # 6х - х^2 + 4у - у^2
        return 6 * self.x - self.x * self.x + 4 * self.y - self.y * self.y

    @classmethod
    def random_instance(cls) -> SimpleEquation:
        return SimpleEquation(randrange(100), randrange(100))


    def crossover(self, other: SimpleEquation) -> Tuple[SimpleEquation, SimpleEquation]:
        child1: SimpleEquation = deepcopy(self)
        child2: SimpleEquation = deepcopy(other)
        child1.y = other.y
        child2.y = self.y
        return child1, child2

    def mutate(self) -> None:
        if random() > 0.5: #мутация х
            if random() > 0.5:
                self.x += 1
            else:
                self.x -= 1
        else: # иначе - мутация у
            if random() > 0.5:
                self.y += 1
            else:
                self.y -= 1

    def __str__(self) -> str:
        return f"X: {self.x} Y: {self.y} Жизнеспособность: {self.fitness()}"

    Класс SimpleEquation соответствует Chromosome и в соответствии со своим названием делает это как можно проще. Гены хромосомы SimpleEquation можно рассматривать как х и у.

    Метод fitness() оценивает жизнеспособность х и у с помощью уравнения 6х - х² + 4у - у². Чем больше значение, тем выше жизнеспособность данной хромосомы в соответствии с GeneticAlgorithm. При использовании случайного экземпляpa x и у изначально присваиваются случайные целые числа из диапазона 0... 100, поэтому random_instance() нужно только создать новый экземпляр SimpleEquation с этими значениями. Чтобы скрестить два SimpleEquation в crossover(), значения у этих экземпляров просто меняются местами для создания двух дочерних элементов. Метод mutate() случайным образом увеличивает или уменьшает х или у. В общих чертах это все.

    Поскольку SimpleEquation соответствует Chromosome, то мы сразу можем подключить его к GeneticAlgorithm.

if __name__ == "__main__":
    initial_population: List[SimpleEquation] = \
        [SimpleEquation.random_instance() for _ in range(20)]
    ga: GeneticAlgorithm[SimpleEquation] = \
        GeneticAlgorithm(initial_population=initial_population,
                         threshold=13.0, max_generations=100,
                         mutation_chance=0.1,
                         crossover_chance=0.7)
    result: SimpleEquation = ga.run()
    print(result)

    Использованные здесь параметры были получены методом догадки и проверки. Вы можете попробовать другие методы. Значение threshold было установлено равным 13.0, поскольку мы уже знаем правильный ответ. При х = 3 и у = 2 значение уравнения равно 13.

    Если ответ заранее не известен, вы, возможно, захотите получить наилучший результат, который можно найти за определенное количество поколений. В этом случае можно установить порог равным произвольному большому числу. Помните: поскольку генетические алгоритмы являются стохастическими, все проходы алгоритма будут разными.

    Вот пример выходных данных одного из проходов, при котором генетический алгоритм решил уравнение за шесть поколений:

Генерация 0 Лучшая -592 Среднее -6351.6
Генерация 1 Лучшая 9 Среднее -1854.3
Генерация 2 Лучшая 12 Среднее -342.1
Генерация 3 Лучшая 12 Среднее 3.7
Генерация 4 Лучшая 12 Среднее 11.45
Генерация 5 Лучшая 12 Среднее 12
X: 3 Y: 2 Жизнеспособность: 13

    Как видите, алгоритм пришел к правильному решению, полученному ранее с применением математического анализа: х = 3, у = 2. Вы также могли заметить, что почти в каждом поколении алгоритм все ближе подходил к правильному ответу.

    Следует принять во внимание, что для поиска решения генетический алгоритм потребовал больше вычислительных ресурсов, чем другие методы. В реальном мире применение генетического алгоритма для столь простой задачи, как поиск максимума, едва ли будет хорошей идеей. Но этой простой реализации достаточно, чтобы показать: наш генетический алгоритм работает.

    На следующем шаге мы вернемся к задаче SEND + MORE = MONEY.

Предыдущий шаг Содержание Следующий шаг