Генетический алгоритм оптимизации функций. Основные принципы работы и область применения
В процессе разработки программного обеспечения с использованием современных технологий искусственного интеллекта часто возникают задачи, решение которых требует производить оптимизацию различных функций. Данные функции могут выступать в качестве критериев оптимальности каких-либо процессов, происходящих в системе. Одним из эффективных подходов к решению задач оптимизации является использование эволюционных методов (генетических алгоритмов), основу которых составляют концепция естественного отбора и генетические механизмы, действующие в живой природе.
При использовании генетических алгоритмов (ГА) разработчики применяют специальную терминологию. Например, особь – это одно из возможных решений задачи. Популяция – конечное множество особей. Ген – переменная, характеризующая решение. Набор таких переменных образует хромосому. Функция приспособленности (целевая функция) – функция, с помощью которой определяется качество предложенного каждой особью решения.
При использовании генетических алгоритмов (ГА) разработчики применяют специальную терминологию. Например, особь – это одно из возможных решений задачи. Популяция – конечное множество особей. Ген – переменная, характеризующая решение. Набор таких переменных образует хромосому. Функция приспособленности (целевая функция) – функция, с помощью которой определяется качество предложенного каждой особью решения.
В генетических алгоритмах применяется ряд операций, суть которых аналогична процессам, происходящим при эволюции живых организмов.
Мутация – это преобразование хромосомы, случайно изменяющее одну или несколько ее позиций (генов). Наиболее распространенный вид мутаций – случайное изменение только одного из генов хромосомы.
Скрещивание – это операция, при которой из двух хромосом порождается одна или несколько новых хромосом. В простейшем случае скрещивание в генетическом алгоритме реализуется так же, как и в биологии. При этом хромосомы разрезаются в случайной точке и обмениваются частями между собой. Например, если хромосомы (1, 2, 3, 4, 5) и (0, 0, 0, 0, 0) разрезать между третьим и четвертым генами и обменять их части, то получатся потомки (1, 2, 3, 0, 0) и (0, 0, 0, 4, 5).
Мутация – это преобразование хромосомы, случайно изменяющее одну или несколько ее позиций (генов). Наиболее распространенный вид мутаций – случайное изменение только одного из генов хромосомы.
Скрещивание – это операция, при которой из двух хромосом порождается одна или несколько новых хромосом. В простейшем случае скрещивание в генетическом алгоритме реализуется так же, как и в биологии. При этом хромосомы разрезаются в случайной точке и обмениваются частями между собой. Например, если хромосомы (1, 2, 3, 4, 5) и (0, 0, 0, 0, 0) разрезать между третьим и четвертым генами и обменять их части, то получатся потомки (1, 2, 3, 0, 0) и (0, 0, 0, 4, 5).
Отбор – выбор из популяции особей, функция приспособленности которых удовлетворяет определенным требованиям. Как правило функция приспособленности – это функция нескольких переменных, по которым необходимо провести оптимизацию.
Простейший ГА выполняется следующим образом. Генерируется начальная популяция особей (индивидуумов), т.е. некоторый набор решений задачи. Как правило, это делается случайным образом или с помощью специальных алгоритмов. Затем отбирается несколько пар индивидуумов, производится скрещивание между хромосомами в каждой паре, а полученные новые хромосомы помещаются в популяцию нового поколения. В генетическом алгоритме сохраняется основной принцип естественного отбора – чем более приспособлен индивидуум (чем больше соответствующее ему значение целевой функции), тем с большей вероятностью он будет участвовать в скрещивании. Далее моделируются мутации – в нескольких случайно выбранных особях нового поколения изменяются некоторые гены. Затем старая популяция частично или полностью уничтожается и происходит рассмотрение следующего поколения. Сохранение лучшего индивидуума данной популяции называется стратегией «элитизма». Популяция следующего поколения в большинстве реализаций генетических алгоритмов содержит столько же особей, сколько начальная, но, в силу отбора, приспособленность в ней в среднем выше. Далее описанные процессы отбора, скрещивания и мутации повторяются уже для этой популяции и т. д.
В каждом следующем поколении будет наблюдаться возникновение совершенно новых решений поставленной задачи. Среди них будут как плохие, так и хорошие, но, благодаря отбору, число хороших решений будет возрастать. Алгоритм продолжит работать до тех пор, пока среди полученных особей не появится решение, функция приспособленности которого будет удовлетворять заданному критерию оптимальности.
Простейший ГА выполняется следующим образом. Генерируется начальная популяция особей (индивидуумов), т.е. некоторый набор решений задачи. Как правило, это делается случайным образом или с помощью специальных алгоритмов. Затем отбирается несколько пар индивидуумов, производится скрещивание между хромосомами в каждой паре, а полученные новые хромосомы помещаются в популяцию нового поколения. В генетическом алгоритме сохраняется основной принцип естественного отбора – чем более приспособлен индивидуум (чем больше соответствующее ему значение целевой функции), тем с большей вероятностью он будет участвовать в скрещивании. Далее моделируются мутации – в нескольких случайно выбранных особях нового поколения изменяются некоторые гены. Затем старая популяция частично или полностью уничтожается и происходит рассмотрение следующего поколения. Сохранение лучшего индивидуума данной популяции называется стратегией «элитизма». Популяция следующего поколения в большинстве реализаций генетических алгоритмов содержит столько же особей, сколько начальная, но, в силу отбора, приспособленность в ней в среднем выше. Далее описанные процессы отбора, скрещивания и мутации повторяются уже для этой популяции и т. д.
В каждом следующем поколении будет наблюдаться возникновение совершенно новых решений поставленной задачи. Среди них будут как плохие, так и хорошие, но, благодаря отбору, число хороших решений будет возрастать. Алгоритм продолжит работать до тех пор, пока среди полученных особей не появится решение, функция приспособленности которого будет удовлетворять заданному критерию оптимальности.
Генетический алгоритм как метод оптимизации имеет ряд достоинств:
Основной недостаток ГА заключается в том, что данный метод неэффективен для поиска глобального экстремума. То есть в общем случае с помощью генетического алгоритма можно быстро найти хорошее решение задачи, но не наилучшее.
В настоящее время генетические алгоритмы применяются для решения множества различных задач (в том числе и при использовании технологий искусственного интеллекта), среди них:
- способность работать с функциями, зависящими от нескольких переменных (многопараметрическая оптимизация);
- устойчивость к попаданию в локальные оптимумы;
- отсутствие требования дополнительной информации о пространстве решений;
- · успешное использование при большом количестве возможных решений.
Основной недостаток ГА заключается в том, что данный метод неэффективен для поиска глобального экстремума. То есть в общем случае с помощью генетического алгоритма можно быстро найти хорошее решение задачи, но не наилучшее.
В настоящее время генетические алгоритмы применяются для решения множества различных задач (в том числе и при использовании технологий искусственного интеллекта), среди них:
- оптимизация запросов в базах данных;
- настройка и обучение искусственных нейронных сетей;
- разработка игровых стратегий;
- задачи на графах (задача коммивояжера и т.п.);
- составление расписаний;
- создание искусственной жизни.
