кр. Ю. Ю. Громов, О. Г. Иванова, В. В. Алексеев, М. П. Беляев, Д. П. Швец, аи. Елисеев интеллектуальные информационные системы и технологии
 Скачать 2.03 Mb.
|
|
87 Рис. 3.11. Древовидное представление компьютерных моделей, отобранных для скрещивания а – родитель 1; б – родитель 2 Рис. 3.12. Модели-потомки, полученные в результате скрещивания Представленные на рис. 3.11 модели соответствуют выражениям V i = (0,85 + ВНП82) / ВНП82 и V j = l,65FM – FM. Операция скрещивания начинается со случайного и независимого выбора точки кроссинговера в каждой из двух моделей-родителей. Отсечённые фрагменты программ-родителей, обозначенные пунктиром, меняются местами, ив результате образуются две модели-потомка (рис. 3.12). Потомкам соответствуют уравнения V k = Пи+ ВНП82 – М Оператор мутации в данном примере выполнялся путём замены функций в узлах деревьев либо путём случайного изменения значений константа) б) 88 Используя статистические данные залет (заметим, что в примере исследовалась экономика США в период с 1959 по 1988 г, генетический алгоритм за 50 последовательных генераций выдал наилучшее решение GD = П, которое хорошо согласуется с известным эконометрическим уравнением обмена Р = MV/Q, где Р – уровень цен М – запасы денежной массы V – скорость обращения денег в экономике Q – валовой национальный продукт. Эволюционное программирование. В х гг. Л. Фогель, А. Оуэне и М. Уолш предложили схему эволюции логических автоматов, решающих задачи предсказания, диагностики, распознавания и классификации образцов, а также задачи управления объектом с неизвестным характером [12]. Исследования, идейно очень близкие к работам Л. Фогеля с сотрудниками, были разносторонне развиты и описаны в работах ИЛ. Букатовой [2, 3]. В более поздних работах Л. Фогеля [20, 21] эволюционное программирование используется для решения систем линейных алгебраических уравнений. Логические (конечные) автоматы – это модели, описывающие средствами формальной логики возможные переходы исследуемой системы из некоторого начального состояния в заключительное. Удобной формой представления конечных автоматов являются ориентированные графы (рис. 3.13), где вершина q 0 – начальное состояние q f – заключительное состояние q 1 , q 2 – промежуточные состояния {0,1} – символы входного словаря. Конечные автоматы используются в задачах распознавания, управления и многих других приложениях. Знаменитая машина Тью- ринга является разновидностью конечного автомата. Эволюционная программа реализует моделирование процессов естественной эволюции моделей-автоматов, причём в каждый момент времени сохраняется тот организм, который наилучшим образом может справиться сданной задачей. Родительский организм оцени- Рис. 3.13. Ориентированный граф, соответствующий конечному автомату 89 вается в зависимости от способности принимать требуемое решение на основе имеющихся данных. Этот организм подвергается мутации и производит на свет потомка, которому ставится та же задача и который оценивается таким же образом. Автомат, который демонстрирует наилучшую способность выполнять требуемые функции, сохраняется и поставляет потомков в следующее поколение. Таким образом производятся всё лучшие и лучшие модели (программы) для решения поставленной задачи. Процесс завершается, когда получена достаточно хорошая программа или исчерпаны ресурсы времени. Всякий раз, когда поступает новая информация, происходит эволюционный поиск логической структуры, обеспечивающей получение наиболее приемлемого решения. В эволюционном программировании объектами эволюции являются конечные автоматы, способные реагировать на стимулы, поступающие из внешней среды. Каждый автомат на основе текущей информации предсказывает состояние, соответствующее определённому значению функции ценности. Решение ищется постепенным отбором автоматов-родителей, к которым применяется мутация наследующем шаге эволюции. В эволюционном программировании используются следующие способы реализации оператора мутации изменение заключительного состояния изменение условия перехода из одного состояния в другое добавление нового состояния удаление состояния изменение начального состояния. Обобщённый алгоритм эволюционного программирования включает следующие шаги. 1. Формулируется постановка задачи. Формируются входной словарь, множество входных и выходных состояний, набор возможных состояний, условия переходов из состояния в состояние, функция ценности для характеристики генерируемых моделей. 2. Случайным образом генерируется начальная популяция конечных автоматов-родителей. 3. Выполняется тестирование автоматов-родителей путём решения поставленной задачи (на вход модели подаётся заданный образец) и оценка полученных результатов на основе выбранной функции ценности. Отсев неперспективных моделей. 5. На основе случайного применения оператора мутации к авто- матам-родителям производятся потомки-члены новой популяции. 90 6. Тестирование моделей-потомков путём решения поставленной задачи и оценка полученных результатов. 7. Отбор наиболее перспективных потомков. 8. Проверка условий окончания процесса эволюции, в качестве которых могут быть достижение оптимального значения функции ценности и/или достижение предельных значений, ограничивающих длительность процесса. Если условия завершения эволюции удовлетворены, то переход на шаг 9, в противном случае – возврат на шаг 5, где объекты последней сгенерированной популяции выступают в качестве родителей. 9. Конец алгоритма. Дальнейшая эволюция автоматов возможна на основе предъявления автоматам более сложных задач. Эволюционные стратегии. Эволюционные стратегии были предложены в х гг. [31, 32] в качестве стохастического метода нахождения глобального минимума функций многих переменных F(X), суть которого состоит в следующем. Из случайных векторов решения задачи многокритериальной оптимизации { } ij x x = , j = 1, .., Р, Р – размерность пространства параметров оптимизации, формируется начальная популяция объектов эволюции, над которыми выполняются следующие действия. 1. Из решений х формируются новые объекты-потомки i x ′ путём сложения каждой компоненты ij ij ij x x ξ + = со случайной переменной ij ξ , имеющей нормальный закон распределения с нулевым математическим ожиданием. 2. Вычисляются значения целевой функции ( ) i x F и ( и осуществляется выбор наилучшего (минимального) решения, которое отбирается в новую популяцию. 3. Процесс продолжается до тех пор, пока не будет достигнуто приемлемое решение. Каждый объект в популяции характеризуется двумя векторами – вектором решения и случайным вектором, модифицирующим это решение. Случайный вектор характеризуется вектором дисперсии, который хранится в процессе поиска, и может быть дополнен корректирующим вектором, ускоряющим сходимость алгоритма. Значение моделирует величину шага изменения параметров, выбираемую случайным образом. В общем случае ij ξ может принимать любые значения, однако в схеме моделирования эволюционных механизмов величина отражает интенсивность мутаций родителя и поэтому не слишком велика. Совокупность полученных точек составляет очередное поколение решений, которые оцениваются по значениям миними- зируемой функции F(X). В результате отбора одни особи гибнут, а другие живут и размножаются. Эту простую схему легко усовершенствовать, вводя по аналогии с естественными закономерностями зависимость числа порождаемых потомков от значений функций ценности родителей. Соответствующие эволюционные стратегии поиска известны и широко используются на практике. Популяции можно формировать следующими способами 1) µ родителей порождают λ потомков, все решения борются за выживание, и лучшие µ объектов отбираются в следующую популяцию) время жизни объекта ограничено одной генерацией, те. µ родителей, произведя λ потомков, погибают. Заместо в следующей популяции соревнуются только λ потомков, причём в данном способе должно выполняться условие λ > µ (рекомендуемое соотношение λ / µ > 7). Такой подход применим к задачам с изменяющимся оптимумом и с зашумлёнными данными. В эволюционных стратегиях используется оператор рекомбинации (в эволюционном программировании, в отличие от эволюционных стратегий, рекомбинация не применяется, который аналогичен скрещиванию в генетических алгоритмах. При этом компоненты вектора потомка создаются из компонент векторов решений двух родителей. Это можно сделать разными способами, например компоненты вектора потомка выбираются случайным образом из векторов родителей компоненты вектора потомка получаются как средние арифметические значения компонент обоих родителей, а затем к полученному потомку применяется оператор мутации. В эволюционных стратегиях иногда применяется глобальная рекомбинация, при которой компоненты вектора каждого потомка случайным образом выбираются из векторов всей популяции родителей. Следует отметить, что моделирование естественных процессов развития, в том числе и эволюции, было и остаётся одним из самых перспективных научных направлений. Кроме описанных методов эволюционных вычислений, на основе естественных аналогий придуманы нейронные сети, предложены методы эволюционного синтеза систем и методы эволюционного проектирования технических объектов. Особенностью подходов, базирующихся на эволюционных аналогиях, является контраст между достаточно простым математическим аппаратом (по сравнению с другими методами) и впечатляющими результатами в области решения слабоструктурированных и плохо обусловленных проблем. Великий Гёте назвал природу творцом всех творцов, поэтому разработчикам ИИС ещё предстоит очень многому у неё научиться. 3.3. Контрольные вопросы и задания 1. Перечислите основные направления эволюционного моделирования и приведите основные факторы, определяющие неизбежность эволюции. 2. Какие алгоритмы называют генетическими Сформулируйте основные особенности генетических алгоритмов. 3. Охарактеризуйте простой генетический алгоритм. Приведите пример. 4. Опишите операторы репродукции и кроссинговера в простом генетическом алгоритме. Приведите примеры. 5. Приведите примеры использования простого генетического алгоритма для вычисления функции ( ) 4 x x f = на интервале [0, 1, 2, 3, 4]. 6. Составьте примеры, иллюстрирующие работу операторов репродукции, кроссинговера, мутации и инверсии. 7. Дайте характеристику понятию схема в простом генетическом алгоритме. Расскажите о назначении и способах использования схем. Приведите примеры. 8. Расскажите о фундаментальной теореме генетического алгоритма. Приведите пример применения фундаментальной теоремы генетического алгоритма. 10. Сформулируйте прикладную экономическую или управленческую оптимизационную задачу и опишите её решение с применением генетического алгоритма. 11. Расскажите о классифицирующих системах Холланда. Приведите пример. 12. Перечислите основные этапы технологии генетического программирования. В чём особенности эволюционного программирования Приведите основные шаги обобщённого алгоритма эволюционного программирования. Охарактеризуйте метод эволюционных стратегий. В чём его отличие от эволюционного программирования и от генетических алгоритмов. Расскажите о применении эволюционных вычислении в ИИС. Каким образом применяют ГА для обучения нейронных сетей Приведите небольшой содержательный пример, демонстрирующий применение ГА для формирования продукционных правил интеллектуальной системы. 16. Расскажите об устойчивости и эффективности генетического алгоритма. 17. Расскажите про генетические операторы и порядок их выполнения. Сформулируйте критерии завершения работы генетического алгоритма. 19. Расскажите про обобщённый алгоритм эволюционного программировании, поясните каждый шаг. 20. Приведите пример конечного автомата, изобразите соответствующий ориентированный граф. 21. Расскажите оконечных автоматах. 22. Перечислите популярные программные средства, реализующие технологии оптимизации с применением генетических алгоритмов. 23. Дайте краткую характеристику средств, реализующих технологии оптимизации с применением генетических алгоритмов. 24. Сформулируйте общую задачу оптимизации сети. 25. Изобразите схему обработки правил в классифицирующей системе. 3.4. Список литературы 1. Батищев, Д.И. Генетические алгоритмы решения экстремальных задач : учеб. пособие / Д.И. Батищев. – Воронеж : Изд-во ВГТУ, 1995. 2. Букатова, ИЛ. Эволюционное моделирование и его приложения ИЛ. Букатова. – М. : Наука, 1979. 3. Букатова, ИЛ. Эвоинформатика. Теория и практика эволюционного моделирования / ИЛ. Букатова и др. – М. : Наука, 1991. 4. Гудман, Э.Д. Эволюционные вычисления и генетические алгоритмы Э.Д. Гудман, А.П. Коваленко // Обозрение прикладной и промышленной математики. – М. : ТВП, 1996. – Т. 3. – Вып. 5. 5. Корнеев, В.В. Базы данных. Интеллектуальная обработка информации В.В. Корнеев и др. – М. : Нолидж, 2000. 6. Корячко, В.П. Теоретические основы САПР / В.П. Корячко, В.М. Курейчик, И.П. Норенков. – М. : Энергоатомиздат, 1987. 94 7. Курейчик, В.М. Генетические алгоритмы : монография / В.М. Курейчик. – Таганрог : Изд-во ТРТУ, 1998. 8. Курейчик, В.М. Генетические алгоритмы в проектировании СБИС : учеб. пособие / В.М. Курейчик. – Таганрог : Изд-во ТРТУ, 1997. 9. Курейчик, В.М. Методы генетического поиска : учеб. пособие / В.М. Курейчик. – Таганрог : Изд-во ТРТУ, 1998. 10. Растршин, Л.А. Статистические методы поиска / Л.А. Рас- тршин. – М. : Наука, 1968. 11. Стецюра, Г.Г. Эволюционные методы в задачах управления, выбора и оптимизации / Г.Г. Стецюра // Приборы и системы управления. Фогель, Л. Искусственный интеллект и эволюционное моделирование Л. Фогель, А. Оуэне, М. Уолш. – М. : Мир, 1969. 13. Фролов, Ю.В. Интеллектуальные системы и управленческие решения / Ю.В. Фролов. – М. : Изд-во МГПУ, 2000. 14. Холланд, Дж. Генетические алгоритмы / Дж. Холланд // В мире науки. – 1992. – № 9, 10. 15. Цетлин, МЛ. Исследование по теории автоматов и моделирование биологических систем / МЛ. Цетлин. – М. : Наука, 1969. 16. Ackley, D.H. A Connection machine for genetic hillclimbing / D.H. Ackley. – Boston : Kluwer Academic Publishers, USA, 1987. 17. Booker, В. Classifier systems and genetic algorithms / В. Boo- ker, D.E. Goldberg, J.H. Holland // Ibid. – 1989. – Vol. 40, No. 1–3. 18. Branke, J. A distributed genetic algorithm improving the generali- zation behavior of neural networks / J. Branke, U. Kohlmorgen, H. Sshmeck // LNAI. – 1995. – Vol. 912. 19. Dzerovski, S. Discovering dynamics with genetic programming / S. Dzerovski, I. Petrovski // LNAI. – Vol. 783. 20. Fogel, D. Evolutionary computatio / D. Fogel. – IEEE press, 1995. 21. Fogel, В. Comparing genetic operators with gaussian mutations in simulated evolutionary process using linear systems / В. Fogel, J.W. Atmar // Biol. Cybernetics. – 1990. – Vol. 63. 22. Foundation of Genetic Algorithms / Ed. by rawens gregory. – San Mateo : Morgan Kaufman Publishers, California, USA, 1991. 23. Goldberg, David E. Genetic algorithms in search, optimization and machine learning / David E. Goldberg. – Addison–Wesley Publishing Company, Inc. 1989. 24. Gruckles, B.P. Genetic algorithms / B.P. Gruckles, F.E. Party. – Los Alamos : IEEE Computer Society Press, LA, USA, 1992. 25. Handbook of Genetic Algorithms // Ed. by Lawrense Davis, Van Nostrand Reinholds. – New York, 1991. 95 26. Holland, J.H. Adaptation in natural and artificial systems. An in- troductory analysis with application to biology, control and artificial intelli- gence / J.H. Holland. – University of Michigan, 1975. 27. Koza, J. Genetic evolution and coevolution of computer programs / J. Koza // Artificial life 2. Proceedings of the Workshop on Artificial life, 1990. 28. Koza, J. Genetic programming / J. Koza // MIT press. – 1992. 29. Koza, J. GP2: Automatic discovery of reusable programs / J. Koza // MIT press. – 1993. 30. Ono, N. Self-organization of communication in distributed earning classifier systems. Artificial neural nets and genetic algorithms / N. Ono, A. Rahmani // Proceedings of the International Conference. – 1993. – Р. 361 – 367. 31. Schwefel, H.P. Numerical optimization of computer models / H.P. Schwefel. – New York : John Willey, 1981. 32. Schwefel, H.P. Evolution and optimum searching / H.P. Schwefel. – New York : John Willey, 1995. 4. ИНТЕЛЛЕКТУАЛЬНЫЕ МУЛЬТИАГЕНТНЫЕ СИСТЕМЫ Интеллектуальные мультиагентные системы – одно из новых перспективных направлений искусственного интеллекта, которое сформировалось на основе результатов исследований в области распределён- ных компьютерных систем, сетевых технологий решения проблем и параллельных вычислений. В мультиагентных технологиях заложен принцип автономности отдельных частей программы (агентов, совместно функционирующих в распределённой системе, где одновременно протекает множество взаимосвязанных процессов. Под агентом подразумевают автономный искусственный объект (компьютерную программу, обладающий активным мотивированным поведением и способный к взаимодействию с другими объектами в динамических виртуальных средах. Каждый агент может принимать сообщения, интерпретировать их содержание и формировать новые сообщения, которые либо передаются на доску объявлений, либо направляются другим агентам. Агентно-ориентированный подход уже нашёл применение в таких областях, как распределённое решение сложных задач, реинжиниринг предприятий, электронный бизнес и т.п. Важной областью применения мультиагентных технологий является моделирование. В этой области ДА. Поспелов [9] выделяет два класса задач. К первому классу он относит задачи распределённого управления и задачи планирования достижения целей, где усилия разных агентов направлены на решение общей проблемы, и необходимо обеспечение эффективного способа |