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

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

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

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

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

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

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

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

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

• изменение заключительного состояния;

• изменение условия перехода из одного состояния в другое;

• добавление нового состояния;

• удаление состояния;

• изменение начального состояния.

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

1. Формулируется постановка задачи. Формируются входной словарь, множество входных и выходных состояний, набор воз-

можных состояний, условия переходов из состояния в состояние, функция ценности для характеристики генерируемых моделей.

2. Случайным образом генерируется начальная популяция
конечных автоматов-родителей.

3. Выполняется тестирование автоматов-родителей путем ре­
шения поставленной задачи (на вход модели подается заданный
образец) и оценка полученных результатов на основе выбранной
функции ценности.

4. Отсев неперспективных моделей.

5. На основе случайного применения оператора мутации к ав­
томатам-родителям производятся потомки-члены новой попу­
ляции.

6. Тестирование моделей-потомков путем решения постав­
ленной задачи и оценка полученных результатов.

7. Отбор наиболее перспективных потомков.

8. Проверка условий окончания процесса эволюции, в каче­
стве которых могут быть: достижение оптимального значения
функции ценности и/или достижение предельных значений, ог­
раничивающих длительность процесса. Если условия завершения
эволюции удовлетворены, то переход на шаг 9, в противном слу­
чае — возврат на шаг 5, где объекты последней сгенерированной
популяции выступают в качестве родителей.

9. Конец алгоритма.

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

Эволюционные стратегии

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

1. Из решений х формируются новые объекты — потомки путем сложения каждой компоненты со случайной пе-

ременной имеющей нормальный закон распределения с нуле/-вым математическим ожиданием.

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

3. Процесс продолжается до тех пор, пока не будет достигну­
то приемлемое решение.

Каждый объект в популяции характеризуется двумя вектора­ми — вектором решения и случайным вектором, модифицирую­щим это решение. Случайный вектор характеризуется вектором дисперсии, который хранится в процессе поиска, и может быть дополнен корректирующим вектором, ускоряющим сходимость алгоритма. Значение моделирует величину шага изменения па­раметров, выбираемую случайным образом. В общем случае может принимать любые значения, однако в схеме моделирова­ния эволюционных механизмов величина отражает интенсив­ность мутаций «родителя» и поэтому не слишком велика. Сово­купность полученных точек составляет очередное поколение ре­шений, которые оцениваются по значениям минимизируемой функции F(X). В результате отбора одни особи гибнут, а другие живут и размножаются. Эту простую схему легко усовершенство­вать, вводя по аналогии с естественными закономерностями за­висимость числа порождаемых потомков от значений функций ценности «родителей». Соответствующие эволюционные страте­гии поиска известны и широко используются на практике. Попу­ляции можно формировать следующими способами:

1) родителей порождаютпотомков, все решения борются за выживание и лучшие объектов отбираются в следующую по­пуляцию;

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

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

• компоненты вектора потомка выбираются случайным обра­
зом из векторов родителей;

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

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

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

7.ПЗ₇. Интеллектуальные мультиагентные системы.

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

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

Основные понятия теории агентов

Понятие агент соответствует аппаратно или программно реа­лизованной сущности, которая способна действовать в интересах достижения целей, поставленных перед ней владельцем и/или пользователем.

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

Идея мультиагентных систем появилась в конце 1950-х гг. в научной школе М.Л. Цетлина, которая занималась исследования­ми коллективного поведения автоматов . Агентами {малень­кими животными) были названы искусственные существа, обла­дающие свойством реактивности, т. е. способные воспринимать и интерпретировать сигналы, поступающие из внешней среды, и формировать ответные сигналы. В роли маленьких животных выступали конечные автоматы, которые не имели априорных знаний о свойствах окружающей среды и о наличии в ней других существ. Единственным знанием, которым они обладали, была цель их деятельности и способность оценивать поступающие сиг­налы относительно достижения этой цели. Оказалось, что даже такие простые структуры, как конечные автоматы, демонстрируют хорошие способности к адаптации в ста­ционарных вероятностных средах. Одной из главных характерис­тик агентов-автоматов была рациональность, которая определя­лась как сумма положительных откликов среды, накопленных агентом за некоторый период его существования. В дальнейши исследованиях структура маленьких животных усложнялась. Сна чала появились вероятностные автоматы с переменной структу рой, адаптирующейся к характеристикам среды, затем появилиа агенты, способные изменять свои реакции на основании преды стории и анализа состояния окружения. Серьезным шагом в раз витии мультиагентных технологий стала реализация способности агентов к рассуждениям. Простейшие модели взаимодей­ствия агентов предусматривали их общение через среду. При ston на каждом шаге функционирования агенты совершают выбо^ возможных для них действий. Множество действий всех агенто! обусловливает распределение откликов среды для всех участни­ков, которые могут его использовать либо не использовать при формировании своих ответных реакций.

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

Таблица 1.

Классификация агентов

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