close

Вход

Забыли?

вход по аккаунту

?

8233.Решение задач поиска и оптимизации решений на основе нечетких генетических алгоритмов и многоагентных подходов

код для вставкиСкачать
Известия ТРТУ
Тематический выпуск
14. Арсеньев С.В., Бородина Н.В., Тарасов В.Б., Черепанов Н.В. О комбинированном под-
ходе к формированию знаний на начальных этапах проектирования с использованием
методологии агентов // Труды 9-й национальной конференции по искусственному интеллекту КИИ-2004 (Тверь, 28 сентября-2 октября 2004 г.). Т.3. – М.: Физматлит, 2004.
– С. 946-958.
15. Poon J., Maher M.L. Emergent Behaviour in Co-Evolutionary Design // Artificial Intelligence
in Design '96/ J.S. Gero and F. Sudweeks (eds). Dordrecht: Kluwer Academic Publishers,
1996. – pp. 703-722.
16. Bentley P. (ed.). Evolutionary Design by Computers. – San Francisco: Morgan Kaufmann,
1999.
17. Langton C.G. Artificial Life: an Overview. – Cambridge MA: MIT Press, 1995.
18. Редько В.Г. Эволюционная кибернетика. – М.: Наука, 2001.
19. Голубин А.В. Инструментальная среда исследования генетических алгоритмов «GenSearch» // Программные продукты и системы. Приложение к Международному журналу
«Проблемы теории и практики управления». – 2005, №3. – С. 37-42.
Л.А. Гладков
РЕШЕНИЕ ЗАДАЧ ПОИСКА И ОПТИМИЗАЦИИ РЕШЕНИЙ НА ОСНОВЕ
НЕЧЕТКИХ ГЕНЕТИЧЕСКИХ АЛГОРИТМОВ
И МНОГОАГЕНТНЫХ
ПОДХОДОВ*
Введение. Научным направлением, занимающимся проблематикой создания
и использования интегрированных интеллектуальных систем является «вычислительный интеллект» (Computational Intelligence). Свидетельством международного
признания этого научного направления явилось проведение в 1994 году первого
Всемирного конгресса по вычислительному интеллекту под эгидой IEEE (Institute
of Electrical and Electronics Engineers). В рамках этого конгресса были проведены
три научных конференции, ставшие в последствии традиционными: по нейронным
сетям, по нечетким системам и по эволюционным вычислениям.
Каждое звено этой триады является самостоятельным направлением исследований объединенных общей целью создания эффективных интеллектуальных систем.
В ходе становления и развития каждого из этих направлений становилось
очевидным наличие глубоких взаимосвязей, взаимозависимости между ними. Изучение этих взаимозависимостей, их влияния на конечный результат и в итоге их
практическое применение является одной из главных задач вычислительного интеллекта.
При этом соединение в единое целое разнородных составляющих дает синергетический (нелинейный) эффект, позволяющий во многом компенсировать минусы, присущие каждому методу в отдельности [1,2].
Примерами подобной интеграции могут служить нейро-логические, нейронечеткие модели, нечеткие логические регуляторы, контроллеры и т.д. [1,3,4].
Логическим следствием процесса интеграции различных компонент триады
вычислительного интеллекта явилось появление и развитие новой области научных
исследований - «нечеткие генетические (адаптивные, эволюционные) алгоритмы».
Работа выполнена при поддержке РФФИ, грант № 04 – 01 – 00174 и программы развития
научного потенциала высшей школы 2006-2008 гг. (РНП.2.1.2. 3193)
*
82
Раздел II. Эволюционное моделирование и генетические алгоритмы
Нечеткие генетические алгоритмы. Одним важных моментов построения
нечетких генетических алгоритмов является нечеткое кодирование. Известно, что
при применении генетических алгоритмов все переменные задачи оптимизации
должны быть определенным образом закодированы. Сущность кодирования заключается в преобразовании любого числового значения в некоторую последовательность символов конечного алфавита, состоящего обычно из небольшого числа
элементов. Наиболее известный пример такого кодирования – это двоичное кодирование и представление решений в виде последовательности нулей и единиц.
В общем случае можно провести аналогию между процессами кодирования и
фаззификации, т.е. преобразования исходных числовых величин в распределения,
соответствующие термам лингвистической переменной. При этом каждое числовое
значение описывается одним или несколькими термами, а степень соответствия
определяется степенью его принадлежности нечеткому множеству [1].
Термины конечного алфавита нечетких множеств могут включать такие понятия как «больше», «меньше», «немного больше (меньше)», «значительно больше
(меньше)», «примерно ноль», «малая отрицательная (положительная)» и др. Использование таких алфавитов при кодировании решений в генетических алгоритмах дает возможность построить неоднородное разделение пространства поиска.
Кроме того, закодированные последовательности могут иметь различную степень
детализации.
Степень детализации и характер распределения решений в пространстве поиска может определяться на основе начальных знаний о решаемой задаче. Такое
кодирование позволяет сосредоточить основные усилия на поиске в наиболее перспективных областях. В свою очередь, для поиска в неперспективных областях (не
содержащих элементов, которые оптимизируют функцию пригодности), определяют последовательности относительно низкой степени детализации.
Можно отметить, по крайней мере, два преимущества нечеткого кодирования. Во-первых, кодовые последовательности могут быть неоднородными и ориентироваться на отдельные многообещающие области поиска, что позволит сократить область поиска и соответственно вычислительные затраты. Кроме того, в закодированную последовательность может быть неявным образом включена функция пригодности.
Во-вторых, нечеткое кодирование позволяет выполнять так называемое слабое кодирование оптимизируемых структур. Слабое кодирование, в отличие от
обычного (сильного) кодирования, не подразумевает жесткое соответствие типа
«один – к – одному» между генотипом и фенотипом в кодируемой структуре.
Основная идея слабого кодирования состоит в использовании отношений типа «один - ко – многим» в процессе задания соответствия генотип - фенотип. Благодаря этому мы получаем единственный генотип, которому соответствует нечеткое семейство фенотипов. Это позволяет нам использовать все преимущества лингвистических переменных при сохранении двоичного кодирования.
Широкое распространение получили также методики кодирования решений в
виде вещественных чисел [5-7].
Следующим шагом в развитие нечетких генетических алгоритмов является
модификация существующих и разработка новых нечетких генетических операторов. Простейшим примером таких операторов могут служить нечеткие операторы
кроссинговера и мутации на основе логических операций [8].
83
Известия ТРТУ
Тематический выпуск
Согласно определению, данному в работе [9] нечеткий генетический алгоритм – это генетический алгоритм в котором реализованы компоненты использующие инструментарий нечеткой логики. Такими компонентами можно считать
нечеткие операторы и нечеткие правила для создания генетических операторов с
различными свойствами; системы нечеткого логического контроля параметров ГА
в соответствии принятыми критериями; нечеткие критерии остановки процесса
генетического поиска. Например, для подбора значений вероятности операторов
кроссинговера и мутации могут использоваться правила работы нечеткого логического контроллера [3].
Описание нечеткого генетического алгоритма для решения задачи составления графика работы ремонтных мастерских приведено в работе [10]:
1. Задание методики кодирования решений. Каждая хромосома состоит из
двух подхромосом, одна из которых представляет собой перечень имеющегося
оборудования, а вторая правила составления последовательности выполнения заказов;
2. Определение целевой функции. При определении целевой функции основными параметрами являются время выполнения или время завершения работы. В
качестве критерия использовалось следующее выражение:
~
~
F (C j ) = π C~ (d j ) = sup min{µC~ (t ), µ d~ (t )},
j
j
j
~
где π C~ j (d j ) - вероятностный критерий оценки возможности совершения нечет~
~
кого события C j на нечетком множестве d j ;
~
~
µC~ (t ) и µ d~ (t ) - функции принадлежности нечетких множеств C j и d j
j
соответственно.
j
3. Инициализация популяции решений. Инициализация подхромосомы оборудования осуществляется путем случайного выбора машины i, i = 1, …, m. Инициализация подхромосомы правил осуществляется на основе случайного выбора
одного из следующих четырех правил: первый оплаченный заказ, самый короткий
по времени процесс, самый длинный по времени процесс, самое длинное время
хранения;
4. Селекция. Используется метод элитной селекции на основе моделирования
колеса рулетки, когда хромосомы выживают с вероятностью пропорциональной
величине их функции пригодности, и лучшие по значению целевой функции хромосомы популяции переходят в следующее поколение;
5. Применение оператора кроссинговера. Оператор кроссинговера применяется с некоторой вероятностью, такой чтобы в ходе рекомбинации родительских
хромосом и создания потомков не получались не корректные решения;
6. Применение оператора мутации. Оператор мутации осуществляет случайный выбор и применяется независимо к обоим подхромосомам;
В состав описываемого нечеткого генетического алгоритма часто включают
блок нечеткого логического контроллера. Например, описываемый в [11] нечеткий
логический контроллер представляет собой двумерную систему, задаваемую параметрами e1, e2. Значения параметров определяются по формулам:
84
Раздел II. Эволюционное моделирование и генетические алгоритмы
f max (t ) − f ave (t )
;
f max (t )
f (t ) − f ave (t − 1)
,
e2 (t ) = ave
f max (t )
e1 (t ) =
где
fmax(t) – лучшее значение целевой функции на итерации t;
fave(t) – среднее значение целевой функции на итерации t;
fave(t - 1) – среднее значение целевой функции на итерации t - 1;
Очевидно, что использование нечеткого логического контроллера
позволяет
осуществлять корректировку значений основных параметров генетического алгоритма в зависимости от качества решений, получаемых в процессе поиска.
Архитектура подсистемы оптимизации. Одним из наиболее перспектвных
подходов к организации процесса поиска оптимальных решений является организация на основе мультиагентных архитектур.
Под «агентом» может пониматься все, что способно воспринимать свою среду обитания с помощью датчиков (сенсоров) и воздействовать на нее с помощью
исполнительных механизмов [12]. Например, программное обеспечение, выступающее в роли агента, в качестве входных данных получает коды нажатия клавиш,
содержимое файлов и сетевые пакеты, а его отклик выражается в выводе данных
на экран, записи и передаче файлов. При этом принимается допущение, что каждый агент может воспринимать свои действия.
Если имеется возможность определить, какое действие будет выполнено
агентом в ответ на некоторую последовательность входных данных, то можно утверждать, что поведение некоторого агента может быть описано с помощью функции агента. Функция агента отображает любую конкретную последовательность
входных данных на некоторое совершаемое агентом действие.
Внутреннее описание агента должно включать таблицу соответствия, определяющую какая функция данного агента реализуется с помощью программы агента.
При этом различают понятия функции и программы агента. Функция агента представляет собой абстрактное математическое описание, а программа агента – это
конкретная реализация, действующая в рамках архитектуры агента [12].
Понятие агента применительно к различным прикладным системам может
трактоваться по разному. С рассмотренных выше позиций, агент может рассматриваться как искусственный организм в популяции себе подобных, стремящийся
обучаться и адаптироваться к внешней среде, для того чтобы выжить в ней.
Тогда многоагентная система может рассматриваться как популяция простых
и независимых агентов, каждый агент которой самостоятельно реализуется в локальной среде и взаимодействует с другими агентами. Связи между различными
агентами являются горизонтальными, а глобальное поведение агентов определяется на основе расплывчатых правил.
Тогда одной из основных задач построения эффективных интеллектуальных
систем поиска и оптимизации является создание программы агента, которая реализует функцию агента, отображая входные воздействия в ответные реакции.
При этом можно предложить использовать формальный механизм нечетких
множеств для создания и вывода нечетких правил. С этой точки зрения такой механизм может восприниматься как функция агента, а программа, реализующая эту
функцию применительно к решению каждой конкретной оптимизационной задачи,
85
Известия ТРТУ
Тематический выпуск
будет представлять собой нечеткий генетический алгоритм, настраиваемый в соответствии с текущими результатами.
В целом структура каждого агента может быть условно обозначена следующей формулой:
Агент = Архитектура + Программа.
Применение принципов построения многоагентных систем к задаче синтеза
архитектуры прикладной подсистемы оптимизации позволяет организовать распараллеливание основных технологических процессов при поиске и выборе решений.
Таким образом, исходя из вышеперечисленного можно предложить следующую архитектуру подсистемы оптимизации (рис.1).
Рис.1. Архитектура подсистемы оптимизации
БИБЛИОГРАФИЧЕСКИЙ СПИСОК
1. Тарасов В.Б. От многоагентных систем к интеллектуальным организациям: философия,
психология, информатика. – М.: Эдиториал УРСС, 2002.
2. Ярушкина Н.Г. Основы теории нечетких и гибридных систем. Учебное пособие. – М.:
Финансы и статистика, 2004.
3. Herrera F., Lozano M. Adaptation of genetic algorithm parameters based on fuzzy logic controllers. In: F. Herrera, J. L. Verdegay (eds.) Genetic Algorithms and Soft Computing,
Physica-Verlag, Heidelberg, 1996. – pp. 95-124.
4. Herrera F., Herrera-Viedma E., Lozano M., Verdegay J.L. Fuzzy tools to improve genetic
algorithms. // In Proc. Of the European Congress on Intelligent Techniques and Soft Computing, 1994. – p. 1532-1539.
5. Herrera F., Lozano M., Verdegay J.L. The use of fuzzy connectives to design real-coded genetic algorithms. Mathware and Soft Computing, 1, 1995. – p. 239-251.
6. Голубин А.В., Тарасов В.Б. Нечеткие генетические алгоритмы. // Международные научно-технические конференции AIS’05 и CAD-2005. Труды конференций. – М.: Физматлит, 2005. – С. 39-45.
7. Kalyanmoy D., Dhiraj J., Ashish A. Real-Coded Evolutionary Algorithms with Parent-Centric
Recombination. Indian Institute of Technology, Kanpur. KanGAL Report No 2001003.
86
Раздел II. Эволюционное моделирование и генетические алгоритмы
8. Гладков Л.А. Алгоритм выделения ядер в нечетких графах на основе моделирования
эволюции. IX национальная конференция по искусственному интеллекту с международным участием КИИ’2004. Труды конференции. – М.: Физматлит, 2004. – С. 346-355.
9. Galantucci L.M., Percoco G., Spina R. Assembly and Disassembly Planning by using Fuzzy
Logic & Genetic Algorithms. // International Journal of Advanced Robotic Systems, Vol. 1, №
2, 2004. – p. 67-74.
10. Fayad C., Petrovic S. A Genetic Algorithm for the Real-World Fuzzy Job Shop Scheduling.
School of Computer Science and Information Technology University of Nottingham,
http://www.cs.nott.ac.uk/~cxf,~sxp
11. Hongbo Liu, Zhanguo Xu, Ajith Abraham. Hybrid Fuzzy-Genetic Algorithm Approach for
Crew Grouping.
12. Рассел С., Норвиг П. Искусственный интеллект: современный подход. − М.: Издательский дом «Вильямс», 2006.
87
Документ
Категория
Без категории
Просмотров
16
Размер файла
185 Кб
Теги
решение, многоагентных, подходов, алгоритм, оптимизация, нечеткие, генетический, основы, задачи, поиск, 8233
1/--страниц
Пожаловаться на содержимое документа