Общая характеристика генетических алгоритмов
Генетический алгоритм – это один из методов эволюционного моделирования, основанный на выполнении действий по аналогии с процессами генетического наследования и естественного отбора.
Эволюционное моделирование – это направление в искусственном интеллекте, построенное на принципах из области эволюционной биологии и популяционной генетики, связанное с применением компьютерных методов моделирования.
Рассмотрим основные понятия, которые потребуются при изучении генетических алгоритмов.
Популяция – это множество особей с определённым в нём количеством элементов, т.е. с заданной численностью.
Индивидуум (особь) представляет собой закодированное в виде хромосом (кодовых рядов, генов) множество параметров задачи.
Инициализация предполагает создание начальной популяции произвольным образом (популяция должна быть разнообразной).
Функция приспосабливаемости (или оценки) отражает уровень (степень) приспосабливаемости индивидуума к популяции.
Задачей генетического алгоритма является выбор наиболее приспособленной особи, т.е. такой особи, для которой функция оценки будет принимать максимальное значение. Такие задачи решаются с помощью оптимизационных методов, связанных с поиском экстремумов целевой функции.
Согласно принципу эволюции, выживает сильнейший и наиболее приспособленный индивидуум. Степень его адаптации к популяции зависит от характерных особенностей, наследуемых от родителей.
В процессе эволюции в популяцию добавляются особи с хорошим генетическим кодом, так как, согласно теореме Холланда, известно, что при отборе здоровых особей в популяции остаются только те, которые оказываются наиболее приспособленными к окружающей среде.
Особенности и преимущества генетических алгоритмов
К особенностям генетических алгоритмов относится то, что:
- они используют параметры в закодированном виде;
- поиск решения в задачах осуществляется при известном наборе начальных точек (т.е. алгоритм применяется не к единственной точке, а сразу же к полной популяции).
- такие алгоритмы используют вероятностные правила выбора, а не детерминированные;
- для их выполнения требуется только функция оценки (без какой-либо дополнительной информации);
- при поиске решения используется значение самой целевой функции, а не её приращения;
- при работе алгоритма одновременно выполняется анализ различных областей из пространства решений, что позволяет находить новые области с лучшими значениями целевой функции с помощью учёта эффективных решений для каждой рассматриваемой популяции.
Всё это позволяет сделать выводы о следующих преимуществах генетических алгоритмов:
- кодирование начальных данных;
- возможность исследовать целые популяции, работая с группой решений;
- стохастические действия эффективно влияют на устойчивость моделей, что позволяет их сделать защищёнными от различных помех и влияний;
- независимость технологии решения от вида целевой функции, которая также может быть задана в неаналитической форме, и от её области определения;
- в такие алгоритмы легко добавлять новые команды;
- есть возможности по организации параллельных вычислений.
Принцип организации генетических алгоритмов
В генетическом алгоритме используются некоторые из генетических операторов, к которым относятся следующие: оператор отбора (селекции), оператор кроссинговера (рекомбинации), оператор мутации и оператор инверсии.
Оператор отбора особей для их дальнейшего существования в другой популяции является наиболее важной стадией при составлении генетических алгоритмов.
Кроссинговер (воспроизведение) – действие, при котором два генетических кода обмениваются своими частями.
Мутация – случайное изменение одной или нескольких позиций в бинарной последовательности, задающей генетический код.
Инверсия – изменение порядка следования битов во всём генетическом коде или в его отдельном фрагменте.
Условиями выхода из генетического алгоритма являются:
- Достижение нужного числа поколений;
- Снижение разнообразия популяции и её вырождение (если большинство из особей в популяции оказываются одинаковыми по степени своей приспособленности);
- Снижение скорости сходимости алгоритма (когда на протяжении некоторого числа поколений результаты качественно не меняются);
- Истечение времени, отведённого на поиск решения в задаче;
- Получение ответа, который позволяет пользователю сделать необходимые для него выводы.
Результатом работы генетического алгоритма является особь из последнего поколения, для которой функция оценки принимает экстремальное значение.
Создание генетического алгоритма в среде Matlab
Начиная с версии Matlab 7.0.1, в пакете программирования Matlab появился специальный тулбокс Genetic Algorithm and Direct Search Toolbox, предназначенный для реализации генетических алгоритмов.
Такие алгоритмы обычно применяются для исследования поведения целевой функции, которая является разрывной, существенно нелинейной, стохастической и не имеет производных (или же они не всюду определены).
Вспомогательное окно Genetic Algorithm с возможностями по реализации генетических алгоритмов вызывается из командной строки Matlab при помощи специальной команды gatool.
В Direct Search Toolbox (вызывается командой psearchtool) содержится набор инструментов, предназначенных для составления генетических алгоритмов и их комбинаций с другими оптимизационными методами.
К основным функциям для работы с генетическими алгоритмами относятся:
- ga – функция, позволяющая найти минимум целевой функции;
- gaoptimset – устанавливает параметры генетического алгоритма;
- gaoptimget – возвращает параметры рассматриваемого генетического алгоритма.
Далее на рисунке представлен вид окна тулбокса Genetic Algorithm:
Рисунок 1. Окно программы. Автор24 — интернет-биржа студенческих работ
