Пт. Мар 1st, 2024

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

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

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

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

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

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

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

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

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

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

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

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

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

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

Ads Blocker Image Powered by Code Help Pro

Обнаружен блокировщик рекламы! Пожалуйста, обратите внимание на эту информацию.

We\'ve detected that you are using AdBlock or some other adblocking software which is preventing the page from fully loading.

У нас нет баннеров, флэшей, анимации, отвратительных звуков или всплывающих объявлений. Мы не реализовываем эти типы надоедливых объявлений! Нам нужны деньги для обслуживания сайта, и почти все они приходят от нашей интернет-рекламы.

Пожалуйста, добавьте tehnar.info к вашему белому списку блокирования объявлений или отключите программное обеспечение, блокирующее рекламу.

Powered By
Best Wordpress Adblock Detecting Plugin | CHP Adblock