Магия генетических алгоритмов: глубокое погружение в код природы
«Любая достаточно продвинутая технология неотличима от магии». Артур Кларк
В области искусственного интеллекта и машинного обучения эта цитата Артура Кларка звучит особенно верно. Одной из таких «магических» технологий является генетический алгоритм, эвристика поиска, вдохновленная теорией естественной эволюции Чарльза Дарвина. Этот алгоритм отражает процесс естественного отбора, когда наиболее приспособленные особи отбираются для размножения, чтобы произвести потомство следующего поколения.
На первый взгляд генетический алгоритм может показаться фокусом, сложным и загадочным процессом, который волшебным образом решает задачи оптимизации и поиска. Это зрелище, как он превращает совокупность случайных решений в почти оптимальное решение, казалось бы, вытаскивая ответ из шляпы.
Но настоящее волшебство Генетического Алгоритма не в его способности решать проблемы как по волшебству, а в его элегантной простоте. Как только вы заглянете за занавеску и поймете ее внутреннюю работу, вы поймете, что ее магия заключается в подражании тем самым процессам, которые сформировали жизнь на Земле.
В этом сообщении блога мы демистифицируем генетический алгоритм, разберем его механизмы и покажем, как его можно просто реализовать в коде. В конце вы увидите, что истинное волшебство технологии не в ее сложности, а в красоте ее замысла и элегантности ее исполнения.
Итак, давайте приоткроем занавес и вместе исследуем магию генетических алгоритмов.
Что такое генетический алгоритм?
В природе живая популяция эволюционирует, чтобы лучше адаптироваться к окружающей среде, тем самым повышая свои шансы на выживание и рост с каждым новым поколением. По мере размножения особей в каждом поколении они создают новых особей с новыми характеристиками (ДНК). Более сильные из этих особей имеют больше шансов выжить и передать свои характеристики следующему поколению в результате так называемого естественного отбора или выживания наиболее приспособленных. Поскольку популяция развивается в течение длительного времени и многих поколений, она становится лучше, сильнее и более приспособленной к своей конкретной среде.
Генетический алгоритм берет эти концепции и абстрагирует их так, чтобы, моделируя процесс эволюции, он мог вырабатывать все более и более лучшие решения данной проблемы с каждым новым поколением.
В алгоритме люди представляют возможные решения проблемы, а их ДНК представляет входные переменные, влияющие на результат решения. По мере развития алгоритма решения «воспроизводятся» для создания новых решений, лучшие из них выживают, и на протяжении многих поколений решения становятся все лучше и лучше, пока мы не достигнем желаемого оптимума или решения просто перестанут улучшаться.
Если это все еще трудно понять, не волнуйтесь! Сначала мы разобьем его на псевдокод, а затем пройдемся по фактической реализации.
Анатомия генетического алгоритма
Несмотря на свою неоспоримую мощь, базовая структура генетического алгоритма довольно проста и включает в себя всего несколько операций. Начиная со случайной группы людей (каждый из которых представляет собой потенциальное решение оптимизируемой проблемы), алгоритм продолжает «разрабатывать» новые решения посредством трех основных процессов: Выбор, Кроссовер,и Мутация.
Существуют различные другие процессы и операции, а также множество различных способов реализации генетического алгоритма. Ниже приведен простой псевдокод, отражающий суть алгоритма и основные необходимые шаги.
Реализация
Нам действительно нужны только три основных класса для этой простой реализации:
- Население — совокупность отдельных лиц.
- Индивидуальное – представляет возможное решение в виде двоичной строки, состоящей из 0 и 1.
- FitnessFunction — работает с бинарной последовательностью индивидуума, чтобы оценить физическую форму индивидуума.
Население
Отдельно
Индивидуум представляет собой возможное решение в популяции и представляет собой не что иное, как двоичную последовательность нулей и единиц. Есть много представлений, которые можно использовать, и нам не нужно явно использовать двоичные значения, но списком нулей и единиц действительно легко манипулировать, что значительно упрощает реализацию других методов, таких как мутация и кроссовер.
Мы используем двоичную последовательность для кодирования входных переменных задачи, которую мы пытаемся оптимизировать. По мере того, как люди подвергаются кроссоверу и мутации, их двоичные последовательности нулей и единиц перемешиваются и изменяются. Если мы затем декодируемэти последовательности после изменений, у нас будут новые значения переменных, которые они представляют, чтобы мы могли оценить пригодность нового человека.
Фитнес-функция
Мы определяем интерфейс для всех фитнес-функций. Каждая фитнес-функция будет иметь метод Evaluate, который принимает человека и возвращает двойное значение, представляющее физическую форму человека. Он также предоставит метод DecodeBinarySequence, который берет индивидуума и декодирует его двоичную последовательность в массив двойников.
Инициализация
Чтобы алгоритм функционировал, ему нужна начальная популяция для работы. Мы инициализируем эту популяцию значением, указывающим ее размер или количество особей в популяции. У каждого человека будет случайная двоичная последовательность заданной длины.
Затем мы оцениваем приспособленность каждого человека в популяции, используя функцию приспособленности. Фитнес-функция берет индивидуума и из его двоичной строки вычисляет значение, указывающее, насколько «хорош» этот индивидуум. По сути, он присваивает балл каждому человеку, чтобы мы могли позже использовать его для выбора наиболее эффективных людей в популяции. Эта оцененная популяция является отправной точкой для генетического алгоритма.
Отбор: выживает сильнейший.
Учитывая начальную популяцию, теперь нам нужно выбрать несколько особей в качестве родителей для производства потомства. Существуют различные методы отбора, которые могут быть реализованы, включая Пропорциональный отбор по фитнесу, Отбор на основе вознаграждения и Отбор на турнире. Цель здесь состоит в том, чтобы выбрать наиболее эффективных людей из популяции, чтобы гарантировать, что следующее поколение будет лучше, чем предыдущее.
В этой реализации я выбрал Tournament Selection. Это включает в себя выбор ряда потенциальных кандидатов (размер турнира) и выбор из них лучшего кандидата (победителя турнира).
Важно отметить, что цель здесь состоит в том, чтобы выбирать лучших людей чаще, чем худших, чтобы они стали родителями нового потомства. Здесь важно значение параметра tournamentSize. Из кода видно, что если tourSize равен 1, мы получим чисто случайный выбор. Если это большое число, скажем, в 100 раз превышающее размер популяции, то мы будем выбирать одних и тех же людей снова и снова (то есть лучших из лучших). Мы собираемся использовать значение 2, чтобы гарантировать, что мы получим хорошее разнообразие, а также подходящих родителей. Это известно как Выбор бинарного турнира.
кроссовер
Кроссовер — это алгоритмический эквивалент Netflix and Chill. Генетический материал от двух родителей, выбранных в процессе отбора, смешивается для создания нового потомства. Как и в случае с отбором и другими генетическими операторами, существуют различные доступные методы, включая одноточечный, двойной точечный и унифицированный кроссовер. В зависимости от характера решаемой проблемы, некоторые из них могут быть более подходящими, чем другие, но цель одна и та же — создать новых уникальных личностей, которые разделяют часть своей ДНК со своими родителями.
Для одноточечного кроссовера точка вдоль бинарных последовательностей родителей выбирается случайным образом. Все биты в последовательности после этой точки меняются местами, что приводит к появлению двух новых потомков.
Мутация
Мутация — это механизм, который вносит разнообразие в популяцию путем внесения случайных изменений в генетическую последовательность особей. Поскольку он случайный, он может создавать как малоэффективных людей (т. е. плохие решения), так и, как Люди Икс, супергероев (т. е. гораздо лучшие решения). Менее приспособленные остаются позади во время отбора, и супергерои начинают передавать свои лучшие гены следующему поколению, улучшая общую физическую форму.
В коде это реализовано как метод, который работает с индивидуальной двоичной последовательностью, переключающей 0 на 1 и 1 на 0.
Частота возникновения мутаций контролируется параметром mutationProbability, который принимает значения от 0 до 1. При значении 0 двоичная последовательность остается неизменной. При значении 1 инвертируется каждый бит в последовательности.
Мутация хороша в малых количествах! Как правило, очень малые значения для mutationProbability используются для внесения случайности и, следовательно, разнообразия в генофонд. Это хорошо, поскольку увеличивает потенциал разработки лучших решений. Нам также нужно не забыть установить individual.Fitness в 0 после мутации.
Элитарность
Элитарность — это механизм, гарантирующий, что следующее поколение будет как минимум не хуже предыдущего. Это достигается путем отбора процента наиболее эффективных особей (элитных особей) из текущей популяции и включения их без мутации в новое поколение.
В коде мы выбираем процент населения и сортируем его в порядке убывания по Individual.Fitness свойству Individual.IsElite, равному true.
Обсуждаемый выше метод BinaryMutation мутирует только особей, свойство IsElite которых установлено на false. Это гарантирует, что лучшие из лучших будут включены в следующее поколение без изменений.
Реализация
Всю реализацию рассмотренных выше классов и методов вы можете посмотреть на Github.
Время пробного запуска!
Теперь, когда мы реализовали код, пришло время повеселиться! Чтобы протестировать генетический алгоритм, нам нужна задача, достаточно сложная для решателя и с известным глобальным минимумом. Бинарная функция F6 Шаффера обеспечивает идеальную тестовую среду для GeneticSolver, поскольку она имеет единственный глобальный минимум в точке (0,0) и множество пиков и впадин. Долины представляют собой локальные оптимумы, в которых алгоритм может застрять. Зная, что нам нужно минимизировать функцию до (0,0).
- Настройка фитнес-функции. Мы формулируем функцию приспособленности для оценки приспособленности человека на основе бинарной функции Шаффера F6, разделив бинарную последовательность ДНК на две части и преобразовав первую половину последовательности в двойную для представления координаты x, а вторую половину в двойную для представления координата у.
Чтобы запустить решатель, нам просто нужно установить некоторые параметры конфигурации и вызвать метод GeneticSolver.Run(). Конфигурация, которую я использовал ниже, была найдена путем игры с параметрами, чтобы найти подходящую конфигурацию для проблемы. В частности
Generation 0 Individual 1: (-38.2069, 31.8626) Individual 2: (-5.2586, -51.6650) Individual 3: (6.5522, 19.3870) Individual 4: (2.0262, 28.7743) Individual 5: (28.7289, 2.3476) Min Fitness: 0.0488 Max Fitness: 0.955 Average Fitness: 0.5033 Total Fitness: 503.3465 Generation 30 Individual 1: (-0.0047), (-0.0012) Individual 2: (-0.0047), (-0.0003) Individual 3: (-0.0047), (-0.0012) Individual 4: (-0.0047), (-0.0012) Individual 5: (-0.0047), (-0.0003) Min Fitness: 0.4437 Max Fitness: 0.9999 Average Fitness: 0.9913 Total Fitness: 991.3704 Generation 100 Individual 1: (-2.3841E-05, -2.3841E-05) Individual 2: (-2.3841E-05, -2.3841E-05) Individual 3: (-2.3841E-05, -2.3841E-05) Individual 4: (-2.3841E-05, -2.3841E-05) Individual 5: (-2.3841E-05, -2.3841E-05) Min Fitness: 0.9999 Max Fitness: 0.9999 Average Fitness: 0.9999 Total Fitness: 999.9999
Как показывают приведенные выше результаты, мы начинаем с совершенно случайной популяции особей, и благодаря магии эволюции мы можем минимизировать тестовую функцию до точки (-2,3841E-05, -2,3841E-05). Это не совсем (0, 0) и никогда не будет, но очень близко! Конечно, в пределах приемлемого допуска для этого теста.
Обратите внимание, как средняя приспособленность популяции в течение примерно 40 поколений приближается к 1,0. Поскольку ГА будет продолжать работать, если его не остановить, мы также должны определить критерии остановки. Мы можем остановить алгоритм на основе одного из трех условий; мы достигаем желаемого порога приспособленности, скорость изменения приспособленности между поколениями падает ниже некоторого порога, или мы достигаем заданного максимального числа поколений.
Давайте на минутку восхитимся экстраординарными возможностями этого, казалось бы, простого алгоритма. Мы отправились в это путешествие с совершенно случайной начальной популяцией, где x и y были рождены из непредсказуемой двоичной строки. Тем не менее, благодаря применению нескольких простых процессов, отражающих суть биологической эволюции — элитизм, отбор, скрещивание и мутация — алгоритм поразительно выработал оптимальное решение нашей проблемы!
В этом и заключается настоящая магия Генетического Алгоритма: его способность преобразовывать хаос в порядок, а случайность в точность, следуя при этом фундаментальным законам природы.
Я надеюсь, что это исследование не только расширило ваши знания, но и снабдило вас инструментами для самостоятельного экспериментирования с этим увлекательным алгоритмом. Если эта статья пробудила в вас свет любопытства или если вам просто понравилось путешествие, не стесняйтесь выразить свою признательность аплодисментами.
Помните, что в мире технологий понимание волшебства — это только начало приключения.
