Использование метода генетических алгоритмов для решения задачи компараторной идентификации модели многофакторного оценивания

обучения вплеск-нейронной сети // Сб. науч. тр. 1-го Международного радиоэлектронного форума «Прикладная радиоэлектроника. Состояние и перспективы развития» - МРФ-2002. Часть 2. Харьков: АН ПРЭ, ХНУРЭ, 2002. С.87-89. 11. Moody J, Darken C.J. Fast learning in networks of locally-tuned processing units // Neural Computation.1989.1.P.281-294. І2. ParkJ., Sandberg

I. W. Universal approximation using radial-basis-function networks // Neural Computation. 1991. 3. P.246-257. 13. Radial Basis Function Networks. Recent Developments in Theory and Applications / Eds. by RJ.Howlett, L.C.Jain. Berlin: Springer, 2001. 318p. 14. Widrow B., Hoff Jr.M.E. Adaptive switching circuits // 1960 IRE Western Electric Show and Connection Record. 1960. Part 4. P.96-104. 15. Widrow B, Lee M. 30 years of adaptive neural networks: perceptron, adaline and backpropagation // Proc. IEEE. 1990. 78. № 9. P.1415-1442. 16. Ham F.M, KostanicI. Principles of Neurocomputing for Science & Engineering. N.Y.: Mc Graw-Hill, Inc., 2001. 642p. 17.Chen S, Billings S.A., Cowan C.F.N, Grant P.M. Non-linear system identification using radial basis function / / Int. J. Syst. Sci. 1990. 21. № 12. P.2513-2539. 18. Chen S, Cowan C.EN, Grant P.M. Orthogonal least squares learning algorithm for radial basis function networks // IEEE. Trans. on Neural Networks. 1991. 2. № 12. P.302-308. 19. Chen S, Billings S.A., Grant P.M. Recursive hybrid algorithm for nonlinear system identification using radial basis function // Int. J. Contr. 1992. 55. № 5. P.1051-1070. 20. Shah S, PalmieriF, Datum M. Optimal filtering algorithms for fast learning in feedforward neural networks // Neural Networks. 1992. № 5. P.779-787. 21.Kasparian V., Batur C, ZhangH, Padovan

J. Davidon least squares-based learning algorithm for feedforward neural networks // Neural Networks. 1994. 7. № 4. P.661-670. 22.Sherstinsky A., Picard R.W On the efficiency of the orthogonal least squares training method for radial basis function networks // IEEE Trans. on Neural

Networks. 1996. 7. №1. P.195-200. 23. Fung C.F., Billings S.A., Luo W. On-line supervised adaptive training using radial basis function networks // Neural Networks. 1996. 9. №.9. P.1597-1617. 24.Goodwin G.C.,RamadgeP.J., Caines P.E. Discrete time stochastic adaptive control // SIAM J. Control and Optimization. 1981. 19. № 6. P.829-853. 25. Goodwin G.C., Ramadge P.J., Caines P.E. A globally convergent adaptive predictor // Automatica. 1981. 17. №1. P.135-140. 26. БодянскийE.B, ПлисеИ.П. Об одном модифицированном алгоритме одновременного действия для идентификации объектов управления. Харьков, 1981. 18с. Рук. деп. в ВИНИТИ 15.09.1981, № 4474 — 81 Деп. 27. Бодянский E.B., Плисе И.П. Об одном многошаговом адаптивном алгоритме идентификации нестационарных объектов. Харьков, 1984.8с. Рук. деп. в УкрНИИНТИ 03.02.1984, № 183 Ук-Д 84. 28. Бодянский E.B., Плисс И.П, Соловьева T.B. Многошаговые оптимальные упредители многомерных нестационарных стохастических процессов // Докл. АН УССР. 1986. Сер .А. № 12. С. 47-49.

Поступила в редколлегию 25.12.2002

Рецензент: д-р техн. наук, проф. Любчик Л.М..

Бодянский Евгений Владимирович, д-р техн. наук, профессор кафедры искусственного интеллекта, научный руководитель проблемной НИЛ АСУ ХНУРЭ, член IEEE, WSES. Научные интересы: нейро-фаззи-системы. Адрес: Украина, 61166, Харьков, пр. Ленина, 14, тел. 40-98-90. E-mail: bodya@kture.kharkov.ua

Винокурова Елена Анатольевна, аспирант кафедры искусственного интеллекта, младший научный сотрудник ПНИЛ АСУ ХНУРЭ. Научные интересы: искусственные нейронные сети, всплески (вейвлеты, wavelet). Адрес: Украина, 61166, Харьков, пр. Ленина, 14, тел.: 40-98-90. E-mail: elena_vinokurova@yahoo.com.

УДК 519.81

ИСПОЛЬЗОВАНИЕ МЕТОДА ГЕНЕТИЧЕСКИХ АЛГОРИТМОВ ДЛЯ РЕШЕНИЯ ЗАДАЧИ КОМПАРАТОРНОЙ ИДЕНТИФИКАЦИИ МОДЕЛИ МНОГОФАКТОРНОГО ОЦЕНИВАНИЯ

ПЕТРОВ Э.Г., БУЛАВИН Д.А.____________

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

1. Введение

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

зано с идентификацией модели формирования скалярной многофакторной оценки качества (эффективности) допустимых альтернативных решений X вида:

P

где ki(x), i = 1, n — частные критерии (характеристики), однозначно определенные для каждого x є X; Ai — коэффициенты изоморфизма, приводящие разнородные частные критерии к единой размерности (или безразмерному виду), одинаковому интервалу изменения и учитывающие различную их значимость (вес) в обобщенной оценке P(x).

В общем случае проблема идентификации модели (1) требует решения задач структурной и параметрической идентификации, т.е. соответственно определения вида оператора F и значений параметров Ai. При этом классические методы идентификации непригодны для идентификации моделей интеллектуальной деятельности. Перспективным для этих целей является использование метода компараторной идентификации [1,3].

2. Метод компараторной идентификации модели многофакторного оценивания

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

89

теории многофакторного оценивания в настоящее время общепринятой является гипотеза о существовании скалярной функции полезности [4]. Согласно этой гипотезе, каждая локальная характеристика альтернативного решения имеет некоторую полезность для лица, принимающего решения (ЛПР), и существует некоторая обобщенная полезность, являющаяся функцией локальных критериев. Таким образом, из двух альтернатив xj, х2 є X и при этом xj У х 2 (альтернатива xj предпочтительней альтернативы х 2) следует, что P(xj) > P(x2), где P(xj), P(x2) — функции полезности альтернатив [3], т.е. из двух альтернатив одна оказывается предпочтительней другой только в том случае, когда полезность первой альтернативы превосходит полезность второй:

xj ^ х2 «• P

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

Следовательно, полезность — это количественное измерение “качества” решения. Отсюда возникает проблема обоснования правила (метрики), по которому образуется функция полезности.

Важным является то, что объективного правила не существует, а принцип ранжирования решений отображает предпочтения ЛПР. Значит, теория полезности и выбор определенного вида функции полезности (оператора F) носит аксиоматический характер, причем аксиоматика отображает предпочтения определенного ЛПР.

Рассмотрим более подробно процедуру поиска метрики функции полезности.

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

Pk

i=1

и мультипликативная

Pk

i=1

Самой информативной ситуацией является та, в которой коэффициенты изоморфизма заданы численно. Так как X i — это константы, то (4) можно переписать следующим образом:

Pk

i=1 i=1

Рассмотрение (5) показывает, что мультипликативная оценка не позволяет учесть «веса» частных критериев, так как произведение i является по-

стоянным масштабным множителем и не влияет на соотношение полезностей различныхрешений x є X. Поэтому более универсальной, широко применяемой является аддитивная функция полезности.

Формула (3) имеет смысл только тогда, когда X i учитывают важность частных критериев и одновременно являются коэффициентами изоморфизма.

Чаще всего определение таких коэффициентов — большая проблема, поэтому было предложено представить аддитивную функцию полезности в виде:

P

i=1

где ai — относительные безразмерные весовые коэффициенты, для которых выполняются следующие ограничения:

0 < ai < 1, £ ai = 1,

i=1

а kf (x) — нормализованные, т.е. приведенные к изоморфному виду частные критерии. Нормализация производится по формуле

(

kf (x) =

ki(x) - kif

Л

ki - ki

v АНП LfK J

здесь ki(x) — значение частного критерия; ki , ki — соответственно наилучшее и наихудшее

значения частного критерия, которые он принимает на области допустимых значений x є X .

В зависимости от вида экстремума частного критерия имеем

ki

нл

maxki(x),если ki(x) ^ max,

_ xeX

minki(x),eom ki(x) ^ min;

.xeX

ki

fx

minki(x),если ki(x) ^ max,

_ xeX

maxki(x),если ki(x) ^ min.

_ xeX

Таким образом, на аксиоматическом уровне решена задача структурной идентификации функции полезности. Однако практическое использование формулы (6) возможно только при условии, что известны коэффициенты ai. Следовательно, возникает задача параметрической идентификации модели (6). Ее решение в настоящее время основано на различных методах экспертного оценивания, когда спецалисты—ЛПР и эксперты побуждаются к осознанию и структуризации своих предпочтений относительно значимости различных частных критериев ki(x).

Альтернативным является компараторный метод параметрической идентификации. Он заключается в следующем. ЛПР предлагается множество допустимых решений X = {xj}, j = 1,m и предлагается указать наиболее предпочтительную, по его мнению, альтернативу. Предположим, что это альтернатива x j. Тогда на основе соотношения (2) можно записать, что

P

В результате получим (m -1) неравенство,опреде-ляющее область возможных значений весовых коэффициентов ai, i = 1, n . В качестве точечного значения весовых коэффициентов принимается Чебышевская точка [2,3].

90

РИ, 2003, № 1

Для описанной выше процедуры идентификации аддитивной функции полезности характерны следующие особенности:

— субъективизм и слабая аргументированность выбора структуры оценки;

— невозможность в рамках аддитивной оценки учесть нелинейность полезности частных критериев от их абсолютного значения и их взаимовлияние;

— низкая точность как экспертных, так и компараторных процедур определения значений весовых коэффициентов а^.

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

3. Постановка задачи

Пусть имеется множество альтернатив (решений) X = {x j}, j = 1,m , каждая из которых характеризуется набором частных критериев , i = 1,n . Значения частных критериев ki(xj) однозначно определены. На основе анализа указанной информации ЛПР осуществляет:

— выбор из X наиболее предпочтительного решения, например xj;

— ранжирование всех решений x є X в порядке убывания их предпочтительности, т.е. устанавливает отношение порядка на множестве альтернатив X : xi ^ х 2 ^...^ xm.

Это означает, что в первом случае справедливо утверждение (11), а во втором — соотношение вида

P

На основе этой информации необходимо синтезировать математическую модель индивидуального выбора ЛПР, т.е. модель формирования обобщенной полезности P(xi). При этом априорные ограничения на вид функции P(xi) не накладываются.

4. Решение задачи компараторной идентификации математической модели индивидуальной функции полезности с использованием генетических алгоритмов

Структуру модели будем определять как частный случай полинома Колмогорова-Габора: n n n

P

i=1 i=lg=1 ,v '

i = 1,n;g = 1,n.

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

Задача заключается в выборе в рамках полинома (13) такой структуры модели функции полезности (1) минимальной сложности, которая удовлетворя-

РИ, 2003, № 1

ет, в зависимости от вида исходной информации, соответственно неравенству (11) или (12). Это означает, что необходимо решить задачи структурной (определить число членов полинома и конкретный вид каждого из них) и параметрической (определить значения коэффициентов при всех членах полинома) идентификации.

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

P

i=1 i=1g=1

i = 1,n;g = 1,n.

Эвристическое обоснование этого допущения базируется на следующих соображениях. В функции полезности коэффициенты ai служат для регулирования (увеличения или уменьшения) влияния (веса) каждого частного критерия k? (x) на обобщенную функцию полезности. Но такого же эффекта можно добиться, учитывая для каждого критерия квадратичные и более высокого порядка добавки, т.е. аппроксимацией вида

aik? (x) = 51k? (x) + 52k2? (x) +

~ , 3?, ,

+ $3ki (x) + •••>

где 5 — булева переменная, принимающая значения 0 или 1. Аппроксимация (15) обеспечивается выбором конкретных значений кортежа булевых переменных А = ^1,52,53,...) .

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

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

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

[5].

ГА начинает работу с некоторого случайного набора решений, который называется популяцией. Каждый

91

элемент из популяции называется хромосомой и представляет некоторое решение проблемы. Хромосомы эволюционируют на протяжении множества итераций, носящих название поколений (генераций). По результатам итераций хромосома оценивается с использованием функции соответствия [6].

Существует несколько способов решения задач с помощью ГА. Самые известные и наиболее часто применяемые:

— регулярная (общая) рекомбинация, представляющая собой кроссинговер, т.е. обмен гомологичными участками в различных точках гомологичных хромосом, приводящий к появлению нового сочетания сцепленных генов;

— спрайт — специфическая рекомбинация, иными словами, обмен генных носителей, часто разных по объему и составу генетической информации, на коротких специализированных участках;

— иллегальная рекомбинация, включающая негомологичные обмены, т.е. транслокации, инверсии, иногда случаи неравного кроссинговера.

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

Простой генетический алгоритм был впервые описан Гольдбергом на основе работ Холланда [5]. Механизм простого ГА несложен, он копирует последовательности и переставляет их части. Предварительно ГА случайно генерирует популяцию последовательностей — хромосом, а впоследствии, применяя множество простых операций к начальной популяции, генерирует новые популяции. Простой ГА состоит из трех операторов: репродукция, кроссинговер и мутация.

В подобных задачах наиболее часто используются следующие операции генетических алгоритмов: механизм кроссинговера (или скрещивания) и механизм мутации.

Скрещивание является главной генетической операцией. Она выполняется над двумя хромосомами — родителями и создает отпрыск (или хромосому -ребенок) путем комбинирования особенностей обоих родителей. Для начала выбирается некоторая точка скрещивания, после этого создается хромосома -ребенок путем комбинирования сегмента первого родителя слева от точки скрещивания и сегмента второго родителя справа от точки скрещивания.

Мутация — это фоновая операция, производящая случайное изменение в различных хромосомах. Самый простой вариант мутации состоит в случайном изменении одного и более генов [6].

Рассмотрим пример с 5 альтернативами и соответственно 4 частными критериями: частота процессора, ОЗУ, объем жесткого диска и цена.

92

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

Таблица 1

Ki K 2 K 3 K 4

Ri 1000 132 40 2300

R2 600 198 80 1600

R3 900 256 50 2700

R4 600 256 70 1200

R5 900 132 60 2300

После того, как ЛПР занес данные в таблицу, он должен определить, какие критерии стремятся к максимуму, а какие — к минимуму. Затем количественные характеристики критериев нормируются по формуле (8). В данном случае первые три частных критерия стремятся к максимуму, а последний — к минимуму. В результате преобразований получаем отнормированные данные, представленные в табл. 2.

Таблица 2

K1 K 2 K3 K 4

R1 1 0 0 0,267

R2 0 0,532 1 0,733

R3 0,75 1 0,25 0

R4 0 1 0,75 1

R5 0,75 0 0,5 0,267

Далее ЛПР предлагается выбрать наилучшую, по его мнению, альтернативу. Допустим, что ЛПР выбрал третью альтернативу, как самую лучшую. Приступим к механизму ГА.

Пусть существует две хромосомы: одна—родитель, содержащая в себе полностью записанный полном Колмогорова-Габора (14), а вторая — ребенок, содержащая в себе только составляющие первого слагаемого:

Pi = Е ki = k1 + k2 + k3 + k4

i=1

Хромосома-ребенок будет для нас результирующей, т.е. кратчайшим полиномом, удовлетворяющим условию:

R3 У Ri, R3 У R2 , R3 У R4, R3 У R5 .

Именно это условие будет критерием, на основе которого мы будем проводить отбор.

Тогда, с помощью механизма кроссинговера, один ген родителя переходит к ребенку, и в случае улучшения хромосомы — остается, иначе возвращается обратно. Иными словами, сначала от хромосомы-родителя к хромосоме-ребенку переходит одно слагаемое, и хромосома-ребенок принимает следующий вид:

Pi = k1 + k2 + k3 + k4 + k? .

РИ, 2003, № 1

После этого проверяется, удовлетворяет ли хромо -сома-ребенок нашему условию; если нет, слагаемое возвращается хромосоме-родителю, а в хромосому-ребенок направляется следующее слагаемое. Таким образом, выполняется вся схема, пока не переберутся все гены хромосомы-родителя. Если оптимальный вариант не найден, начинается постановка генов — попарно. И снова до тех пор, пока не произойдет полный перебор всех генов. Если оптимальный вариант снова не найден, начинаем передавать по три гена. И так до тех пор, пока не найдется вариант, удовлетворяющий оптимальному критерию (17).

Таким образом, после нахождения полинома Колмогорова-Габора оптимальной длины, удовлетворяющего условию (17), мы выполняем проверку данного полинома, для выбранной альтернативы подставляя частные критерии. В нашем случае получается полином следующей длины:

Pi = kj + k2 + кз + k4 + kjk2 + kjk^ . (19) Отсюда полезность альтернатив:

R3 = 2,9375 ; R4 = 2,75 ; R2 = 2,265; R5 = 1,892; Ri = 1,267.

Полезность альтернативы R3 максимальна, следовательно, остальные альтернативы действительно хуже, и задача решена правильно.

УДК 539.87

ОРГАНИЗАЦИЯ ЭКСПЕРТНЫХ СИСТЕМ ПРОДУКЦИОННОГО ТИПА НА ЛОКАЛЬНОПАРАЛЛЕЛЬНЫХ НЕЧЕТКИХ АЛГОРИТМАХ

МИХАЛЬ О.Ф.__________________________

Рассматриваются принципы организации нечеткой экспертной системы (ЭС) продукционного типа на локально-параллельных (ЛП) алгоритмах. ЭС содержит каналы взаимодействия с оператором и объектом управления, поддерживает четыре режима: базовое обучение, адаптация, автономная подстройка и рабочий. Показывается, что перспективной областью применения ЛП алгоритмических решений могут стать интеллектуальные распределенные сетевые ЭС с децентрализованным использованием и обновлением знаний.

Интеллектуализация компьютерных систем, применяемых в управлении, разворачивается преимущественно в двух направлениях: описание объектов и явлений предметной области на основе аппарата нечеткой логики (НЛ) [1] и использование экспертных знаний (ЭЗ). Перспективным является пересечение указанных направлений—нечеткие экспертные системы (ЭС) [2] — по следующей причине. Носителем ЭЗ есть человек, непрерывная циклическая познавательная деятельность которого (ги-

5. Выводы

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

Литература: 1. Эйкофф П. Основы идентификации систем управления. М.: Мир, 1975. 238с. 2. Овезгелъдыев А.О., Петров Э.Г., Петров К.Э. Синтез и идентификация моделей многофакторного оценивания и оптимизации. К.: Наук. думка, 2002. 161 с. 3. Овезгелъдыев А. О., Петров К.Э. Компараторная идентификация параметров линейных моделей многофакторного оценивания // Радиоэлектроника и информатика. 1998. №2(03). С. 41-43. 4. Нейман Дж., Моргенштерн О. Теория игр и экономическое поведение. М.: Наука, 1970. 124с. 5. Курейчик В.М Генетические алгоритмы. Состояние. Проблемы. Перспективы. Таганрог, 1999. 6. Ротштейн А.П. Интеллектуальные технологии идентификации. Винница: «Универсум-Винница», 1999. 320с.

Поступила в редколлегию 03.12.2002

Петров Эдуард Георгиевич, д-р техн. наук, профессор, зав. кафедрой системотехники ХНУРЭ. Научные интересы: математическое моделирование, теория принятия решений. Адрес: Украина, 61166, Харьков, пр. Ленина, 14, тел. 40-93-06.

Булавин Дмитрий Алексеевич, аспирант кафедры системотехники ХНУРЭ. Научные интересы: теория принятия решений, генетические алгоритмы. Увлечения: футбол, музыка, история. Адрес: Украина, 61166, Харьков, ул. Ленина, 3, кв. 20, тел. 45-38-87, e-mail: dimetroid@yandex.ru.

потеза — эксперимент — обобщение — новая гипотеза) априорно предполагает на любом этапе неполноту и последовательное уточнение ЭЗ, а следовательно, их нечеткость. Поэтому представление ЭЗ средствами НЛ включает минимум промежуточных преобразований и вносит в них минимум искажений, что необходимо для достижения адекватного поведения ЭС в предметной области. Важной характеристикой при технической реализации НЛ систем является быстродействие. Его повышение диктуется потребностями предметной области и достигается либо аппаратно, специализированными средствами обработки - нечеткими процессорами; либо алгоритмически, в частности, использованием принципа локалъной параллелъности (ЛП) [3]. Основные ЛП-алгоритмы НЛ описаны в [3,4]. Функционирование ЭС включает два фундаментальных процесса: приобретение и исполъзование ЭЗ. Процесс использования ЭЗ реализуется в ЭС, в частности, в составе системы управления. ЭС при этом в основных чертах функционально аналогичны блоку обработки в цепи обратной связи. Элементы организации подобных нечетких структур на ЛП-алгоритмах описаны в [5,6].

Цель настоящей работы—описание организации на ЛП-алгоритмах нечеткой ЭС, реализующей оба процесса: приобретение и использование ЭЗ, включая согласование вновь приобретенных ЭЗ со старыми. Описание приводится применительно к ЭС продукционного типа.

РИ, 2003, № 1

93