Пн. Дек 23rd, 2024

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

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

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

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

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

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

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

Автомат, который демонстрирует наилучшую способ­ность выполнять требуемые функции, сохраняется и поставляет «потомков» в следующее поколение. Таким образом производят­ся все лучшие и лучшие модели (программы) для решения по­ставленной задачи. Процесс завершается, когда получена доста­точно хорошая программа или исчерпаны ресурсы времени. Вся­кий раз, когда поступает новая информация, происходит эволю­ционный поиск логической структуры, обеспечивающей получе­ние наиболее приемлемого решения.

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

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

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

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

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

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