3.7.1. Эволюционные алгоритмы

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

3.7.1.1. Эволюционный алгоритм случайного поиска

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

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

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

Теперь среди потомков вступает в действие «естественный отбор», при котором с большей вероятностью вымирает потомок, имеющий большее значение минимизируемой функции. Моделируется это следующим образом.

Пусть вероятность «вымирания» пропорциональна значению минимизируемой функции, т. е.

Далее разыгрываем процесс вымирания до тех пор, пока не останется «выживших» потомков. Популяция сформирована и может давать потомство для следующего этапа отбора.

Опыт показывает, что такая грубая модель эволюции (даже при позволяет очень эффективно оптимизировать многоэкстремальные функции при наличии ограничений . В этом случае потомок, нарушивший ограничение, т. е. «вымирает» сразу независимо от значения [16, 154, 155].

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

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

В практической биологии этот феномен играет огромную роль и во многом определяет механизм эволюции окультуренных видов. Рассмотренный в § 3.3 (подраздел 3.3.3.1) случайный поиск с помощью коллектива независимых автоматов с целесообразным поведением является хорошей основой для моделирования указанных биологических явлений в процессах случайного поиска. Рассмотрим некоторые из них [136].

3.7.1.2. Популяционный алгоритм случайного поиска

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

где компоненты анкеты определяют прошлую работу автомата на каждом канапе оптимизируемого объекта следующим образом:

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

Теперь введем скрещивание. Для этого надо оценить эффективность автомата. Она определяется суммой

Легко заметить, что чем больше эта величина, тем лучше работает автомат. Поэтому величина определяет приоритет автомата в выборе пары. Первым, естественно, выбирает пару автомат с максимапьной эффективностью а, причем с большей вероятностью он выбирает себе в пару автомат с большим а (как видно, этот алгоритм моделирует механизм образования брачных пар в животном мире). Далее по тому же принципу выбирает себе пару автомат с меньшим значением эффективности и т. д. Естественно вводить и «холостые» автоматы, которым с определенной вероятностью не удается найти себе пары. Эта вероятность должна увеличиваться с уменьшением а, моделируя «неприспособленность» автоматов с малым а.

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

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

Вероятность сохранения автомата при селекции пропорциональна его эффективности а, что естественно при реализации искусственного отбора.

Эксперименты с алгоритмами случайного поиска [136], моделирующими описанный механизм искусственного отбора, показали их большую гибкость, надежность и эффективность.