3.8.2. Генетические алгоритмы

Идея генетических алгоритмов была предложена Дж. Холландом в 70-х годах XX в. [41], а их интенсивное развитие и практическая реализация для численных оптимизационных расчетов были инициированы Д. Гольдбергом [41]. Эти алгоритмы имитируют процессы наследования свойств живыми организмами и генерируют последовательности новых векторов w, содержащие

оптимизированные переменные: При этом выполняются операции трех видов: селекция, скрещивание и мутация.

Отдельные компоненты вектора могут кодироваться в двоичной системе либо натуральными числами [41]. При двоичном кодировании применяется обычный код, или код Грея. После соответствующего масштабирования отдельные биты представляют конкретные значения параметров, подлежащих оптимизации. Каждому вектору и» сопоставляется определенное значение целевой функции. Генетические операции (селекция, скрещивание и мутация) выполняются для подбора таких значений переменных вектора при которых максимизируется величина так называемой функции приспособленности (англ.: fitness function). Функция приспособленности определяется через целевую функцию путем ее инвертирования (целевая функция минимизируется, а функция приспособленности максимизируется). Например, она может иметь вид:

На начальной стадии выполнения генетического алгоритма инициализируется определенная популяция хромосом (векторов и»). Она формируется случайным образом, хотя применяются также и самонаводящиеся способы (если их можно определить заранее). Размер популяции, как правило, пропорционален количеству оптимизируемых параметров. Слишком малая популяция хромосом приводит к замыканию в неглубоких локальных минимумах. Слишком большое их количество чрезмерно удлиняет вычислительную процедуру и также может не привести к точке глобального минимума. При случайном выборе векторов составляющих исходную популяцию хромосом, они статистически независимы и представляют собой начальное погружение в пространство параметров. Одна часть этих хромосом лучше “приспособлена к существованию” (у них большие значения функции соответствия и меньшие - целевой функции), а другая часть хуже. Упорядочение хромосом в популяции, как правило, производится в направлении от лучших к худшим. Хромосомы отбираются (подвергаются селекции) для формирования очередного поколения по значениям функции соответствия.

Селекция хромосом для спаривания (необходимого для создания нового поколения) может основываться на различных принципах. Одним из наиболее распространенных считается принцип элитарности, в соответствии с которым наиболее приспособленные хромосомы сохраняются, а наихудшие отбраковываются и заменяются вновь созданным потомством, полученным в результате скрещивания пар родителей. На этапе скрещивания подбираются такие пары хромосом, потомство которых может быть включено в популяцию путем селекции. Существует огромное количество методов спаривания, от полностью случайного (как правило, среди наиболее приспособленных хромосом), через взвешенно-случайное спаривание и вплоть до так называемой турнирной системы. В последнем случае случайным образом отбирается несколько хромосом, среди которых определяются наиболее приспособленные

(с наименьшим значением целевой функции). Из победителей последовательно проведенных турниров формируются пары для скрещивания.

При взвешенно-случайной системе в процессе отбора учитывается информация о текущем значении функции приспособленности. Отбор может происходить по принципу “рулетки”, при этом площадь сегмента колеса рулетки, сопоставленного конкретной хромосоме, пропорциональна величине ее относительной функции приспособленности. Ситуация, типичная для такого отбора, иллюстрируется на рис. 3.9. Полная площадь круга соответствует сумме значений функций приспособленности всех хромосом данной популяции.

Рис. 3.9. Схема “рулетки”, используемая при выборе родителей для будущего поколения. Площадь отдельных сегментов пропорциональна значениям соответствующих функций приспособленности

Каждый выделенный сегмент отвечает конкретной хромосоме. Наиболее приспособленным особям отводятся большие сегменты колеса рулетки, увеличивающие их шансы попадания в переходную популяцию.

Рис. 3.10. Иллюстрация операции скрещивания, применяемой в генетическом алгоритме

Процесс скрещивания основан на рассечении пары хромосом на две части (рис. 3.10) с последующим обменом этих частей в хромосомах родителей. Место рассечения также выбирается случайным образом. В ситуации, показанной на

рис. 3.10, после скрещивания хромосомы 1 (фрагменты ) с хромосомой 2 (фрагменты ) образовалась пара новых хромосом: хромосома 3 (фрагменты ) и хромосома 4 (фрагменты 63 и Количество новых потомков равно количеству отбракованных в результате селекции. После их добавления к оставшимся хромосомам размер популяции остается неизменным. Как правило, признается допустимым перенос в очередное поколение некоторых случайно выбранных хромосом вообще без скрещивания. Это соответствует ситуации, когда скрещивание достигает успеха с определенной вероятностью, обычно на уровне

Последняя генетическая операция — это мутация, состоящая в замене значений отдельных битов (при двоичном кодировании) на противоположные. При кодировании натуральными десятичными цифрами мутация заключается в замене значения какого-либо элемента вектора другим, случайно выбранным допустимым значением. Мутация обеспечивает защиту как от слишком раннего завершения алгоритма (в случае выравнивания значений всех хромосом и целевой функции), так и от представления в какой-либо конкретной позиции всех хромосом одного и того же значения. Однако необходимо иметь в виду, что случайные мутации приводят к повреждению уже частично приспособленных векторов. Обычно мутации подвергается не более 1-5% бит всей популяции хромосом. Как и при выполнении большинства генетических операций, элемент, подвергаемый мутации, отбирается случайным образом.

На рис. 3.11 представлены схема формирования переходной популяции и проводимые после него операции скрещивания и мутации, приводящие к образованию популяции потомков. Отметим, что в этих операциях не обязательно участвуют все хромосомы, входящие в переходную популяцию.

Исследованиями доказано [41], что каждое последующее поколение, сформированное после выполнения селекции, скрещивания и мутации, имеет статистически лучшие средние показатели приспособленности (меньшие значения целевой функции). Типичная динамика изменения среднего по популяции и минимального (т.е. соответствующего наиболее приспособленной хромосоме) значения целевой функции для последовательных поколений генетического процесса представлена на рис. 3.12.

В качестве окончательного решения принимается наиболее приспособленная хромосома, имеющая минимальное значение целевой функции. Генетический процесс завершается либо в момент генерации удовлетворяющего нас решения, либо при выполнении максимально допустимого количества итераций. При реализации генетического процесса отслеживается, как правило, не только минимальное значение целевой функции, но и среднее значение по всей популяции хромосом, а также их вариации. Решение об остановке алгоритма может приниматься и в случае отсутствия прогресса минимизации, определяемого по изменениям названных характеристик.

Хорошие результаты обучения приносит объединение алгоритмов глобальной оптимизации с детерминированными методами. На первом этапе обучения сети

(кликните для просмотра скана)

Рис. 3.12. Типичная динамика среднего и минимального значения целевой функции в последовательных поколениях генетического алгоритма

применяется выбранный алгоритм глобальной оптимизации, а после достижения целевой функцией определенного уровня включается детерминированная оптимизация с использованием какого-либо локального алгоритма (наискорейшего спуска, переменной метрики, Левенберга-Марквардта или сопряженных градиентов).