Оптимизация естественным отбором
Эволюционные алгоритмы - это эвристический подход к решению проблем, которые не могут быть легко решены за полиномиальное время, таких как классические NP-Hard задачи и все остальное, что требует слишком много времени для исчерпывающей обработки. Когда они используются сами по себе, они обычно применяются к комбинаторным задачам; однако генетические алгоритмы часто используются в тандеме с другими методами, действуя как быстрый способ найти в некоторой степени оптимальную отправную точку для работы другого алгоритма.
Предпосылка эволюционного алгоритма (который в дальнейшем будет известен как EA) довольно проста, учитывая, что вы знакомы с процессом естественного отбора. Советник состоит из четырех общих этапов: инициализация, выбор, генетические операторы и завершение. Каждый из этих шагов примерно соответствует определенному аспекту естественного отбора и предоставляет простые способы модульной реализации реализации этой категории алгоритмов. Проще говоря, в EA более приспособленные члены будут выживать и размножаться, в то время как непригодные члены вымирают и не вносят вклад в генофонд следующих поколений, как в естественном отборе.
Контекст
В рамках этой статьи мы обычно определяем проблему как таковую: мы хотим найти лучшую комбинацию элементов, которая максимизирует некоторую функцию пригодности, и мы примем окончательное решение, как только мы запустим алгоритм для некоторого максимального количества итераций, или мы достигли некоторого порога пригодности. Этот сценарий явно не единственный способ использования советника, но он охватывает множество распространенных приложений в дискретном случае.
Инициализация
Чтобы начать наш алгоритм, мы должны сначала создать начальную популяцию решений. Популяция будет содержать произвольное количество возможных решений проблемы, часто называемых членами. Часто он создается случайным образом (в рамках ограничений задачи) или, если известны некоторые предварительные знания о задаче, приблизительно сосредоточен на том, что считается идеальным. Важно, чтобы популяция охватывала широкий спектр решений, потому что она, по сути, представляет собой генофонд; Следовательно, если мы хотим исследовать множество различных возможностей в ходе работы алгоритма, мы должны стремиться к тому, чтобы присутствовало много разных генов.
Выбор
После создания популяции ее члены должны быть оценены в соответствии с функцией пригодности. Фитнес-функция - это функция, которая принимает характеристики члена и выводит числовое представление о том, насколько это жизнеспособное решение. Создание фитнес-функции часто может быть очень трудным, и важно найти хорошую функцию, которая точно представляет данные; это очень проблематично. Теперь мы вычисляем физическую форму всех участников и выбираем часть участников, набравших наибольшее количество баллов.
Несколько целевых функций
Советники также могут быть расширены для использования нескольких фитнес-функций. Это несколько усложняет процесс, потому что вместо того, чтобы идентифицировать одну оптимальную точку, мы вместо этого получаем набор оптимальных точек при использовании нескольких функций пригодности. Набор оптимальных решений называется границей Парето и содержит элементы, которые одинаково оптимальны в том смысле, что ни одно решение не доминирует над любым другим решением на границе. Затем используется решающий элемент, чтобы сузить набор единственного решения в зависимости от контекста проблемы или какой-либо другой метрики.
Генетические операторы
На самом деле этот шаг состоит из двух подэтапов: кроссовер и мутация. После выбора верхних элементов (обычно 2 верхних, но это число может варьироваться), эти элементы теперь используются для создания следующего поколения в алгоритме. Используя характеристики выбранных родителей, создаются новые дети, которые представляют собой смесь их качеств. Это часто может быть затруднено в зависимости от типа данных, но обычно в комбинаторных задачах можно смешивать комбинации и выводить допустимые комбинации из этих входных данных. Теперь мы должны ввести в поколение новый генетический материал. Если мы не сделаем этот важный шаг, мы очень быстро застрянем в локальных экстремумах и не получим оптимальных результатов. Этот шаг - мутация, и мы делаем это очень просто, изменяя небольшую часть детей так, чтобы они больше не полностью отражали подмножества генов родителей. Мутация обычно происходит вероятностно, так как вероятность того, что ребенок получит мутацию, а также серьезность мутации, регулируются распределением вероятностей.
Прекращение
В конце концов, алгоритм должен закончиться. Обычно это происходит в двух случаях: либо алгоритм достиг некоторого максимального времени выполнения, либо алгоритм достиг некоторого порога производительности. На этом этапе выбирается и возвращается окончательное решение.
Пример
Теперь, чтобы проиллюстрировать результат этого процесса, я покажу пример советника в действии. На следующем гифке показано несколько поколений динозавров, которые учатся ходить, оптимизируя структуру своего тела и применяя мышечные силы. Слева направо генерация увеличивается, поэтому чем дальше вправо, тем более оптимизирован процесс ходьбы. Несмотря на то, что динозавры раннего поколения не могли ходить, EA смогла развить динозавров с течением времени посредством мутации и кроссовера в форму, которая могла ходить.
