Эволюционное прогаммирование

В 1960-х гг. Л. Фогель, А. Оуэне и М. Уолш предложили схему эволюции логических автоматов, решающих задачи предсказа­ния, диагностики, распознавания и классификации образцов, а также задачи управления объектом с неизвестным характером.

Логические (конечные) автоматы — это модели, описываю­щие средствами формальной логики возможные переходы иссле­дуемой системы из некоторого начального состояния в заключи­тельное. Удобной формой представления конечных автоматов яв­ляются ориентированные графы (рис. 6.13), где вершина д₀ — на­чальное состояние,— заключительное состояние,— про­межуточные состояния; {0, 1} — символы входного словаря.

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

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

Рис. 6.13. Ориентированный граф, соответствующий конечному автомату

Этот организм подвергается мутации и производит на свет «потомка», которому ставится та же задача и который оценивается таким же образом.

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

В эволюционном программировании используются следую­щие способы реализации оператора мутации:

• изменение заключительного состояния;
• изменение условия перехода из одного состояния в другое;
• добавление нового состояния;
• удаление состояния;
• изменение начального состояния.

Обобщенный алгоритм эволюционного программирования включает следующие шаги.

1. Формулируется постановка задачи. Формируются входной словарь, множество входных и выходных состояний, набор возможных состояний, условия переходов из состояния в состояние, функция ценности для характеристики генерируемых моделей.
2. Случайным образом генерируется начальная популяция конечных автоматов-родителей.
3. Выполняется тестирование автоматов-родителей путем ре­шения поставленной задачи (на вход модели подается заданный образец) и оценка полученных результатов на основе выбранной функции ценности.
4. Отсев неперспективных моделей.
5. На основе случайного применения оператора мутации к ав­томатам-родителям производятся потомки-члены новой попу­ляции.
6. Тестирование моделей-потомков путем решения постав­ ленной задачи и оценка полученных результатов.
7. Отбор наиболее перспективных потомков.
8. Проверка условий окончания процесса эволюции, в качестве которых могут быть: достижение оптимального значения функции ценности и/или достижение предельных значений, ог­раничивающих длительность процесса. Если условия завершения эволюции удовлетворены, то переход на шаг 9, в противном слу­чае — возврат на шаг 5, где объекты последней сгенерированной популяции выступают в качестве родителей.
9. Конец алгоритма.

Дальнейшая эволюция автоматов возможна на основе предъ­явления автоматам более сложных задач.