Главная Обратная связь

Дисциплины:

Архитектура (936)
Биология (6393)
География (744)
История (25)
Компьютеры (1497)
Кулинария (2184)
Культура (3938)
Литература (5778)
Математика (5918)
Медицина (9278)
Механика (2776)
Образование (13883)
Политика (26404)
Правоведение (321)
Психология (56518)
Религия (1833)
Социология (23400)
Спорт (2350)
Строительство (17942)
Технология (5741)
Транспорт (14634)
Физика (1043)
Философия (440)
Финансы (17336)
Химия (4931)
Экология (6055)
Экономика (9200)
Электроника (7621)






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



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

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

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

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

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

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

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



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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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



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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

Таблица 1.

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

 
 

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


Эта страница нарушает авторские права

allrefrs.ru - 2017 год. Все права принадлежат их авторам!