Простой генетический алгоритм — это алгоритм, который имеет в своем составе операцию случайной генерации начальной популяции хромосом и ряд операторов, способных обеспечить генерацию новых популяций на базе начальной.
Введение
Генетический алгоритм является методом оптимизации, основанным на концепциях естественного отбора и генетики. В таком подходе переменные, которые характеризуют решение, представляются как гены в хромосоме. Генетический алгоритм способен оперировать не бесконечным множеством решений (популяцией), то есть он может генерировать новые решения в виде различных комбинаций частей решений популяции, применяя такие операторы, как отбор, рекомбинация (кроссинговер) и мутация. Новые решения должны позиционироваться в популяции согласно их положению на поверхности изучаемой функции.
Идея генетического алгоритма была подсказана самой природой и работами Дарвина. В основе алгоритма находится предположение, что если берутся два вполне нормальных решения задачи и каким-нибудь образом из них получается новое решение, то существует достаточно большая вероятность того, что новое решение будет достаточно хорошим или даже еще более лучшим.
Для того чтобы реализовать этот принцип, можно использовать моделирование эволюции (естественного отбора) или, если говорить более простым языком, то моделирование борьбы за выживание. В естественной природе, принимая во внимание упрощенную схему, все животные стремятся выжить, чтобы после них осталось как можно больше потомства. Выживать в подобных условиях способны только самые сильные.
В таком случае специалистам необходимо лишь организовать определенную среду, то есть, популяцию, наполнить (населить) ее решениями, то есть, особями, и организовать им борьбу. Для этого требуется определить функцию, по которой будет задаваться сила особи, то есть, качество предложенного ею решения. Опираясь на этот параметр можно назначить всем особям количество оставляемых ими потомков, или вероятность того, что эти особи оставят потомков. При этом, не исключается вариант, когда особь, имеющая слишком низкое значение данного параметра просто умрет.
Простой генетический алгоритм
Предположим, что необходимо оптимизировать определенную функцию $F(X_1, X_2,.., X_n)$, а именно, найти ее глобальный максимум. В таком случае, для реализации генетического алгоритма следует определить методику сохранения решений. По существу, требуется поместить все $X_1-X_n$ в какой-либо вектор, играющий роль хромосомы. Одним из самых распространенных методов является кодирование значений переменных в битовом векторе.
К примеру, можно выделить каждому $X_n$ по восемь бит. В таком случае данный вектор будет иметь длину:
$L=8*n$.
Чтобы упростить ситуацию, будем полагать, что биты расположены в массиве $X[0..L-1]$. Предположим, что каждая особь может состоять из массива X и значения функции F на переменных, считанных из данного массива. В таком варианте генетический алгоритм должен включать в свой состав следующие шаги:
- Осуществление генерация начальной популяции, то есть, заполнение популяции особями, в которых элементы массива X (биты) заполняются случайным порядком.
- Реализация выбора родительской пары. Здесь может быть использован принцип элитного отбора, то есть, следует взять K особей, имеющих максимальное значение функции F, и составить из них все возможные пары $(K*(K-1)/2)$.
- Далее реализуется кроссинговер, то есть, процесс обмена участками гомологичных хромосом. Необходимо взять случайную точку t на массиве X (0..L-1). Далее, все компоненты массива с индексами 0-t новой особи (потомка) нужно заполнить компонентами с такими же индексами, но из массива X первой родительской особи. Оставшиеся компоненты нужно заполнить из массива второй родительской особи. А для второго потомка следует все сделать наоборот, то есть, компоненты 0-t следует взять от второго потомка, а оставшиеся взять от первого.
- Новые особи с определенной степенью вероятности могут мутировать, то есть, может инвертироваться случайный бит массива X этой особи. Вероятность мутации, как правило, предполагается в районе одного процента.
- Сформированные особи, являющиеся потомками, следует добавить в популяцию после переоценки. Как правило, новая особь добавляется вместо самой плохой старой особи, при условии, что величина функции на новой особи больше значения функции на старой, то есть, плохой особи.
- В случае, когда наилучшее решение в популяции все-таки считается не удовлетворительным, то нужно перейти к шагу два. Но, как правило, такого условия нет, а итерации генетического алгоритма могут выполняться бесконечно.
Строго говоря, если буквально следовать правилам, то генетический алгоритм может иметь еще такие шаги как выбор особей для размножения и генерация пар из отобранных особей. Причем любую особь можно задействовать в одной и более пар, в зависимости от применяемого алгоритма. Однако лучше данную пару шагов совмещать, применяя принцип формирования пар «все на все» в элитной выборке, что будет проще выполнить.
Необходимо отметить следующие достоинства генетических алгоритмов:
- Им не требуется никакая информация о поверхности ответа.
- Разрывы, которые имеются на поверхности ответа, обладают незначительным влиянием на полную эффективность оптимизации.
- Алгоритмы являются достаточно стойкими к попаданию в локальные оптимумы.
- Алгоритмы могут хорошо работать при решении крупномасштабных проблем оптимизации.
- Алгоритмы можно использовать для решения широкого класса задач.
- Алгоритмы являются достаточно простыми и прозрачными в реализации.
- Алгоритмы можно использовать при решении задач с изменяющейся средой.
К недостаткам генетических алгоритмов следует отнести следующие аспекты:
- Не следует их использовать, если нужно определить точный глобальный оптимум.
- Их нельзя применять, если время выполнения функции оценки достаточно велико.
