5.3.2. Процесс работы генетического алгоритма
Общая схема работы генетического алгоритма представлена на рис. 5.12.
Формирование исходной популяции происходит, как правило, с использованием какого-либо случайного закона, на основе которого выбирается нужное количество точек поискового пространства. Исходная популяция может также быть результатом работы другого алгоритма оптимизации.
Рис. 5.12. Процесс работы генетического алгоритма
Основой порядка применения операторов отбора родительских пар и уничтожения особей является принцип «выживания сильнейшего». При случайном выборе особи для размножения вероятность ее участия в этом процессе вычисляется по формуле:
|
, (5.11) |
где i – номер особи,
N – размер популяции,
fi – значение целевой функции для i-й особи.
Целью поиска является нахождение особи с максимумом целевой функции. Очевидно, что одна особь может быть задействована в нескольких родительских парах.
Аналогично может быть решен вопрос уничтожения особей. Вероятность уничтожения должна быть обратно пропорциональна качеству особей, однако обычно просто уничтожаются особи с наихудшим качеством.
Таким образом, выбирая для размножения наилучшие (самые сильные) с точки зрения целевой функции особи и уничтожая наихудшие (самые слабые), генетический алгоритм постоянно улучшает популяцию, приводя к формированию лучших решений.
Природный процесс наследования, т.е. передача свойств родителей потомкам, моделируется оператором скрещивания.
Простейший оператор скрещивания выполняется в два этапа. Пусть особь представляет собой строку из т элементов. На первом этапе равновероятно выбирается натуральное число k в диапазоне [1, т-1]. В соответствии с этим числом, называемым также точкой разбиения, обе исходные строки делятся на две подстроки. На втором этапе строки обмениваются своими подстроками, лежащими после точки разбиения, то есть элементами с k+1 по т. В результате получаются две новые строки, унаследовавшие частично свойства обоих родителей (рис. 5.13).
Рис. 5.13. Иллюстрация процесса скрещивания
Для того чтобы обеспечить постоянное появление новых особей в интересах расширения пространства поиска, вероятность применения оператора скрещивания обычно выбирается в пределах от 0,9 до 1.
Количество элитных особей определяется обычно по формуле:
К = N × (1 - Р), (5.12)
где К – количество элитных особей,
Р – вероятность применения оператора скрещивания,
N – размер популяции.
В случае использования стратегии элитизма скрещиванию подвергаются все выбранные родительские пары, несмотря на то, что вероятность применения оператора скрещивания меньше 1.
Оператор мутации моделирует аналогичный природный процесс. Его применение в генетических алгоритмах обусловлено тем, что исходная популяция, какой бы большой она ни была, охватывает лишь часть пространства поиска. Оператор скрещивания расширяет эту область только до определенной степени, так как использует ограниченный набор значений, заданный исходной популяцией. Внесение случайных изменений в особи позволяет преодолеть это ограничение, значительно сократить время поиска и улучшить качество результата.
Вероятность мутации, в отличие от вероятности скрещивания выбирается, как правило, достаточно малой. Сам процесс мутации заключается в замене одного из элементов строки на другое значение. Это может быть перестановка двух элементов в строке, замена элемента строки значением элемента из другой строки, в случае битовой строки – инверсия одного из битов и др.
В процессе работы алгоритма все указанные выше операторы применяются многократно и ведут к постепенному изменению исходной популяции. Поскольку операторы отбора, скрещивания, мутации и редукции по своей сути направлены на улучшение каждой отдельной особи, то результатом их работы является постепенное улучшение популяции в целом. В этом и заключается основной смысл работы генетического алгоритма – улучшить популяцию решений по сравнению с исходной.
После завершения работы генетического алгоритма из конечной популяции выбирается особь, которая дает экстремальное (максимальное или минимальное) значение целевой функции и является, таким образом, результатом работы генетического алгоритма. За счет того, что конечная популяция лучше исходной, полученный результат представляет собой улучшенное решение.