авторефераты диссертаций БЕСПЛАТНАЯ БИБЛИОТЕКА РОССИИ

КОНФЕРЕНЦИИ, КНИГИ, ПОСОБИЯ, НАУЧНЫЕ ИЗДАНИЯ

<< ГЛАВНАЯ
АГРОИНЖЕНЕРИЯ
АСТРОНОМИЯ
БЕЗОПАСНОСТЬ
БИОЛОГИЯ
ЗЕМЛЯ
ИНФОРМАТИКА
ИСКУССТВОВЕДЕНИЕ
ИСТОРИЯ
КУЛЬТУРОЛОГИЯ
МАШИНОСТРОЕНИЕ
МЕДИЦИНА
МЕТАЛЛУРГИЯ
МЕХАНИКА
ПЕДАГОГИКА
ПОЛИТИКА
ПРИБОРОСТРОЕНИЕ
ПРОДОВОЛЬСТВИЕ
ПСИХОЛОГИЯ
РАДИОТЕХНИКА
СЕЛЬСКОЕ ХОЗЯЙСТВО
СОЦИОЛОГИЯ
СТРОИТЕЛЬСТВО
ТЕХНИЧЕСКИЕ НАУКИ
ТРАНСПОРТ
ФАРМАЦЕВТИКА
ФИЗИКА
ФИЗИОЛОГИЯ
ФИЛОЛОГИЯ
ФИЛОСОФИЯ
ХИМИЯ
ЭКОНОМИКА
ЭЛЕКТРОТЕХНИКА
ЭНЕРГЕТИКА
ЮРИСПРУДЕНЦИЯ
ЯЗЫКОЗНАНИЕ
РАЗНОЕ
КОНТАКТЫ


Pages:   || 2 | 3 | 4 | 5 |   ...   | 7 |
-- [ Страница 1 ] --

Институт проблем управления

им. В.А. Трапезникова РАН

УПРАВЛЕНИЕ

БОЛЬШИМИ

СИСТЕМАМИ

Выпуск 40 СБОРНИК

ТРУДОВ

Ноябрь 2012

ISSN 1819-2467

Регистрационный номер Эл №ФС77-44158 от 09 марта 2011 г.

Москва – 2012

РОССИЙСКАЯ АКАДЕМИЯ НАУК

Институт проблем управления

им. В.А. Трапезникова

УПРАВЛЕНИЕ

БОЛЬШИМИ

СИСТЕМАМИ СБОРНИК ТРУДОВ Выпуск 40 Москва – 2012 УДК 519 ISSN 1819-2467 ББК 32.81 У 67 Управление большими системами / Сборник трудов. Выпуск 40. М.: ИПУ РАН, 2012. – 328 с. Дата опубликования: 30.11.2012.

КООРДИНАЦИОННЫЙ СОВЕТ Академики РАН: Васильев С.Н., Емельянов С.В., Коровин С.К., Куржанский А.Б., Федо сов Е.А., Черноусько Ф.Л.;

члены-корреспонденты РАН: Желтов С.Ю., Каляев И.А., Пархоменко П.П., Попков Ю.С.;

д-ра техн. наук: Бутковский А.Г., Дорофеюк А.А., Куз нецов О.П., Кульба В.В., Кротов В.Ф., Лотоцкий В.А., Павлов Б.В., Поляк Б.Т., Рутков ский В.Ю.

РЕДАКЦИОННАЯ КОЛЛЕГИЯ Главный редактор: член-корр. РАН Новиков Д.А. Отв. секретарь: к.т.н. Губко М.В.

Д-ра техн. наук: проф. Алескеров Ф.Т. (ГУ ВШЭ), проф. Артамонов Е.И. (ИПУ РАН), д р экон. наук, проф. Архипова М.Ю. (ИПИ РАН), д-ра техн. наук: проф. Афанасьев В.Н.

(МИЭМ), проф. Бахтадзе Н.Н. (ИПУ РАН), проф. Бурков В.Н. (ИПУ РАН), проф.

Вишневский В.М. (ИППИ РАН), д-р экон. наук, проф. Голиченко О.Г. (ЦЭМИ РАН), д-р физ.-мат. наук, проф. Добровидов А.В. (ИПУ РАН), д-ра техн. наук: проф. Заложнев А.Ю. (ИПУ РАН), проф. Ириков В.А. (МФТИ), проф. Калянов Г.Н. (ИПУ РАН), проф.

Касаткин С.И. (ИПУ РАН), проф. Каравай М.Ф. (ИПУ РАН), канд. техн. наук Квинто Я.И. (ИПУ РАН), д-р экон. наук, проф. Клочков В.В. (ИПУ РАН), д-ра техн. наук: проф.

Кононенко А.Ф. (ВЦ РАН), канд. техн. наук Куливец С.Г. (ИПУ РАН), проф. Курдюков А.П. (ИПУ РАН), проф. Лебедев В.Г. (ИПУ РАН), к-т техн. наук, доцент Лебедев В.Н.

(ИПУ РАН), д-р экон. наук, проф. Ловчиновский Э.В. (ИПУ РАН), д-р техн. наук, проф.

Мандель А.С. (ИПУ РАН), д-р экон. наук, проф. Нижегородцев Р.М. (ИПУ РАН), д-ра техн. наук: проф. Новосельцев В.Н. (ИПУ РАН), проф. Орлов А.И. (МВТУ), д-р физ. мат.наук, проф. Рапопорт Л.Б. (ИПУ РАН), д-р техн. наук, проф. Рыков А.С. (МИСИС), д-р экон. наук, проф. Секерин В.Д. (ИПУ РАН), д-ра техн. наук: проф. Сидельников Ю.В. (МАИ), проф. Совлуков А.С. (ИПУ РАН), д-р экон. наук, проф. Сухарев О.С. (Ин-т экономики РАН), д-ра техн. наук: проф. Уткин В.А. (ИПУ РАН), проф. Хоботов Е.Н.

(МВТУ), д-ра физ.-мат. наук: доцент Чеботарев П.Ю. (ИПУ РАН), проф. Чхартишвили А.Г. (ИПУ РАН), проф. Щербаков П.С. (ИПУ РАН).

РЕГИОНАЛЬНЫЕ РЕДАКЦИОННЫЕ СОВЕТЫ Волгоград – д-ра физ.-мат. наук: проф. Воронин А.А., проф. Лосев А.Г. (ВолГУ);

Воронеж – д-р техн. наук, проф. Баркалов С.А., д-р физ.-мат. наук, проф. Головинский П.А. (ВГАСУ), д-р техн. наук, проф. Подвальный С.Л. (ВГТУ);

Ижевск – д-р физ.-мат.

наук, проф. Непейвода Н.Н., к-т физ.-мат. наук, проф. Родионов В.И. (УдмГУ);

Иркутск – д-ра физ.-мат. наук: проф. Бычков И.В., проф. Лакеев А.В. (ИДСТУ СО РАН);

Казань – д-р физ.-мат. наук, проф. Маликов А.И., д-р техн. наук, проф. Сиразетдинов Р.Т.

(КГТУ-КАИ);

Липецк – д-ра техн. наук: проф. Кузнецов Л.А., проф. Погодаев А.К.

(ЛГТУ);

Самара – д-ра экон. наук: проф. Богатырев В.Д., проф. Гераськин М.И., д-р техн. наук, проф. Засканов В.Г. (СГАУ);

Санкт-Петербург – д-ра физ.-мат. наук: проф.

Петросян Л.А. (СПбГУ), проф. Фрадков А.Л. (ИПМ РАН);

Старый Оскол – д-р техн.

наук, проф. Еременко Ю.И. (СТИ);

Тверь – д-ра техн. наук: проф. Кузнецов В.Н., проф.

Палюх Б.В. (ТГТУ).

Адрес редакции: 117997, г. Москва, ул. Профсоюзная, д. 65.

Адрес в Интернет: ubs.mtas.ru.

Номер гос. регистрации электронного научного издания (ЭНИ): 0421200023.

ИПУ РАН, СОДЕРЖАНИЕ Системный анализ Абаев Л. Ч.

Экспертное упорядочение альтернатив в задачах боль шой размерности.................................................................

Кучуганов В. Н.

Элементы теории ассоциативной семантики...................

Орлов А. И., Пугач О. В.

Подходы к общей теории риска.......................................... Математическая теория управления Агалаков Ю. Г.

Оценивание вероятностей редких событий в вычисли тельных экспериментах с имитационными моделями......

Усков А. А., Киселев И. А.

Комплексный и матричный методы выполнения ариф метических операций над нечёткими числами...................

Черных Н. В.

Моделирование решений СДУ с марковскими переключе ниями....................................................................................

Анализ и синтез систем управления Фуртат И. Б.

Адаптивное управление объектом с запаздыванием по управлению без использования прогнозирующих уст ройств..................................................................................

Информационные технологии в управлении Душкин Д. Н.

Анализ чувствительности веб-сервисов в задаче выбора оптимальной конфигурации систем с сервисно ориентированной архитектурой........................................ Управление в социально-экономических системах Астанин С. В., Жуковская Н. К.

Идентификация команды исполнителей организационно го подразделения на основе анализа согласованности поведения в процессе тестирования................................... Баранов А. А., Файзрахманов Р. А.

Метод оценки влияния процесса термической обработки на эффективность отрасли производства стали.............

Вилисов В. Я.

Управление переключениями тарифных планов сотовой связи..................................................................................... Гольдовская М. Д., Дорофеюк Ю. А., Черняв ский А. Л.

Оценка состояния и эффективности управления соци ально-экономическими системами методами экспертно классификационного анализа..............................................

Управление техническими системами и технологиче скими процессами Горюнов А. Г.

Система автоматического управления каскадом цен тробежных экстракторов................................................. Сизиков А. П.

Разработка предметно-ориентированных систем опти мизации (на примере нефтеперерабатывающего произ водства)............................................................................... Управление подвижными объектами и навигация Николаев Д. А.

Моделирование и управление движением агента в неоп ределенной внешней среде методами идемпотентной алгебры.................................................................................

Системный анализ УДК 519. ББК ЭКСПЕРТНОЕ УПОРЯДОЧЕНИЕ АЛЬТЕРНАТИВ В ЗАДАЧАХ БОЛЬШОЙ РАЗМЕРНОСТИ Абаев Л. Ч. (Российский институт стратегических исследований, Москва) В статье рассматривается задача экспертного упорядочения альтернатив, которые могут быть представлены элементами N-мерного пространства. Для решения таких задач предлага ются декомпозиционные методы, позволяющие экспертам надежно упорядочить существенно большее число альтерна тив, нежели в обычных экспертных процедурах. Для устране ния возможных экспертных противоречий предлагается гене тический алгоритм решения задачи нп-триангуляции матриц.

Ключевые слова: экспертные методы, упорядочение альтер натив, декомпозиция, генетические алгоритмы 1. Введение Одной из широко распространенных задач, решение кото рых часто оказывается невозможным без привлечения экспер тов, является задача оценки альтернативных вариантов. Во многих случаях построение даже относительно «грубых» мате матических моделей, позволяющих «автоматически» вычислять оценки альтернатив, оказывается невозможным. Особенно часто это имеет место при исследовании слабоформализуемых про блем, например, военно-политического анализа, анализа между народных отношений, макропрогнозирования социально экономических процессов, проектирования больших техниче Лев Черменович Абаев, доктор технических наук, ведущий научный сотрудник (abaev_lev@mail.ru).

Управление большими системами. Выпуск ских систем и др. Соответственно, в данных задачах оценка альтернатив осуществляется экспертными методами.

Наиболее информативными оценками в этом случае оказы ваются количественные экспертные оценки, представляющие собой измерения в метрических шкалах (шкале разностей, от ношений или абсолютной). Однако измерения в метрической шкале, как показывает практика, часто оказываются довольно сложной задачей для экспертов, что может приводить к значи мым ошибкам в точности экспертных измерений. Кроме того, в задачах, для которых отсутствуют «естественные» измеритель ные шкалы, построение метрических шкал для экспертной оценки вариантов является достаточно эффективной лишь в случае относительно небольшого числа альтернатив. Действи тельно, для «четкого» сравнения n альтернатив необходимо зафиксировать n значений на интервальной шкале (и, соответст венно, дать «лингвистическое», вербальное описание каждого значения). Уже для n = 20 формирование шкалы с 20-ю значе ниями становится весьма затруднительным. В случае же мень шего числа градаций на шкале не менее двух альтернатив полу чат одинаковую оценку, хотя их сравнительная эффективность может быть существенно разной. Поэтому во многих случаях представляется более надежным прямое упорядочение альтерна тив. Но и здесь возникает проблема экспертного анализа боль шого числа альтернативных вариантов. Исследования в области психологических аспектов принятия решений показали, что даже высококвалифицированный эксперт в состоянии корректно проранжировать не более 7–8, максимум 10 альтернатив [7]. В то же время при анализе реальных задач число вариантов, под лежащих оценке, может существенно превосходить это число.

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

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

1.1. ТЕОРЕТИКО-ИГРОВЫЕ ЗАДАЧИ Рассмотрим некооперативную игру N лиц с произвольной суммой. Пусть у i-го игрока есть Li возможных стратегий пове дения. Тогда множество возможных исходов представляется в виде N-мерного пространства размерности L1 L2 … LN, причем элемент Si1i2...iN характеризует ситуацию, «порождаемую»

стратегиями i1, i2, …, iN соответственно 1-го, 2-го,..., N-го игро ков. Анализ подобных игровых моделей становится возможным лишь при наличии оценок предпочтительности ситуаций Si1i2...iN.

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

1.2. МОРФОЛОГИЧЕСКИЙ АНАЛИЗ Морфологический анализ является одним из достаточно распространенных методов, используемых в практике норма тивного прогнозирования, проектирования (в широком смысле Заметим, кстати, что упорядочение ситуаций по предпочтитель ности в теоретико-игровых задачах позволяет получить весьма важную информацию, например, определить стратегии гарантиро ванного результата, выделить ситуации равновесия в чистых стра тегиях (если они существуют), провести «коалиционный» анализ и др. Таким образом, в ряде случаев возникает возможность сущест венно упростить работу экспертов, поскольку упорядочение ситуа ций по предпочтительности представляет собой менее сложную процедуру, нежели определение количественных оценок. При этом информативность получаемых результатов останется на доста точно высоком уровне.

Управление большими системами. Выпуск слова), системного анализа и т.д. Его суть заключается в том, что исследуемая проблема S представляется в виде ряда состав ляющих ее подпроблем Si, i = 1, …, N. Для каждой подпроблемы Si предлагается ряд альтернативных вариантов ее решения Sij, j = 1, …, Li. Решение проблемы S представляет собой совокуп ность различных вариантов решения подпроблем Si. Таким образом, любое решение проблемы S может быть представлено N-мерного как элемент пространства размерности L1 L2 … LN, где элемент Si1i2...iN представляет собой решение проблемы S как совокупность i1, i2, …, iN вариантов решения соответственно подпроблем S1, S2, …, SN. В случае ранжирова ния этих вариантов по степени эффективности снова приходим к задаче упорядочения альтернатив в N-мерном пространстве.

1.3. МЕТОДЫ ПРОГНОЗНЫХ СЦЕНАРИЕВ Рассмотрим задачу формирования прогнозного сценария развития некоторого процесса. В том случае, когда известны вариативные прогнозы развития N подпроцессов, прогнозный сценарий представляет собой наиболее вероятное сочетание прогнозных вариантов подпроцессов. Если затруднено количе ственное определение вероятностей реализации прогнозных вариантов, но возможно их упорядочение по критерию «вероят ность реализации», то вновь получим задачу упорядочения альтернатив, являющихся элементами N-мерного пространства.

Предлагаемый в работе метод упорядочения альтернатив, являющихся элементами N-мерного пространства, основан на декомпозиции исходной задачи упорядочения на ряд взаимосвя занных подзадач существенно меньшей размерности с после дующим синтезом полученных решений и окончательным упо рядочением исходного множества альтернатив. «Базовой»

процедурой метода является процедура упорядочения «двумер ного» множества альтернатив, которая рассматривается ниже.

Далее будет рассмотрен общий случай N-мерного пространства.

Системный анализ 2. Упорядочение «двумерного» множества альтернатив Рассмотрим матрицу ||sij||, i = 1, …, N, j = 1, …, M, где sij яв ляются элементами двумерного пространства S1 S2. Например, для модели игры двух лиц S1 будет представлять собой множе ство стратегий 1-го игрока, S2 – множество стратегий игрока 2, а элементы sij – ситуации, «порождаемые» i-й стратегией игрока и j-й стратегией игрока 2.

Требуется упорядочить элементы sij по тому или иному за ранее определенному критерию (например, по предпочтительно сти с точки зрения того или иного игрока). Уже при N = M = число элементов, подлежащих экспертному упорядочению, становится равным 16, что не позволяет провести их корректное ранжирование «напрямую».

Рассмотрим декомпозиционную процедуру упорядочения, включающую следующие этапы.

1. Для каждого i = 1, …, N проведем экспертное упорядоче ние элементов sij, j = 1, …, M. В итоге получим N ранжировок по M элементов в каждой, которые можно формально представить в виде N невзаимосвязанных ориентированных графов линейно го порядка, состоящих из M вершин каждый (дуги графа харак теризуют сравнительную предпочтительность элементов sij).

2. Для каждого j = 1, …, M проведем экспертное упорядоче ние элементов sij, i = 1, …, N. В итоге получим M ранжировок по N элементов в каждой, которые аналогично представим в виде M невзаимосвязанных ориентированных графов линейного порядка, состоящих из N вершин каждый.

3. Синтезируем из N + M графов граф G((sij), V), где sij – вершины графа G, а дуги vij V характеризуют сравнитель ную предпочтительность элементов sij. Поскольку линейные графы, полученные на этапах 1 и 2, содержат общие вершины Sij, граф G будет иметь структуру «сетчатого» типа (рис. 1).

4. В синтезированном графе G выделяются все контуры (циклы) графа (контур – замкнутый путь в графе вида si1 j1 si2 j2... sil jl si1 j1, для примера на рис. 1 контур выде Управление большими системами. Выпуск лен). Наличие контура в графе характеризует противоречивость эксперта, проводившего упорядочение. Естественно, что чем больше выделено контуров в графе G, тем более противоречивы оценки эксперта.

Рис. 5. Выделенные контуры графа представляются эксперту для корректировки своих ранговых оценок и, в конечном итоге, удаления контуров3.

6. Формируется новый граф G*((sij), V*), представляющий со бой отношение квазипорядка, причем полученный квазипорядок может лишь незначительно отличаться от отношения полного порядка.

7. Граф G* представляется в виде слоистой структуры (верх ний слой представляет собой множество вершин sij, не домини рующихся другими вершинами графа, во второй слой попадают вершины, не доминирующиеся оставшимися элементами мно жества S и т.д.). Подобное представление графа позволяет дос Заметим, что если экспертная корректировка ранговых оценок не позволит удалить контуры в графе G (например, удаление одних контуров приведет к появлению других), то для решения данной задачи можно использовать рассматриваемую ниже процедуру аппроксимации графа G «ближайшим» к нему ацикличным графом.

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

8. Проводится дополнительный экспертный опрос (попарное сравнение) и формируется итоговое полное упорядочение (до классов эквивалентности) множества анализируемых вариантов.

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

Таблица 1.

Стратегии игрока Стратегии игрока 1 1 2 1 2 2 1 3 2 Таким образом, результаты этого этапа могут быть пред ставлены в виде трех невзаимосвязанных орграфов линейного порядка по три вершины в каждом.

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

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

Управление большими системами. Выпуск Таблица 2.

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

Рис. 2.

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

Системный анализ Рис. 3.

Для полного упорядочения оказалось достаточным прове дение четырех парных сравнений ситуаций (результаты этих сравнений показаны на рис. 3 пунктирными стрелками). В результате был сформирован линейный порядок на множестве возможных исходов игры по их предпочтительности с точки зрения первого игрока (рис. 4).

Рис. 4.

Рассмотренная процедура упорядочения, как было отмечено выше, основана на декомпозиции исходной задачи ранжирова ния N M элементов на совокупность задач упорядочения N и M элементов. А поскольку эксперт может достаточно надежно проранжировать до 10 элементов (т.е. Nmax = Mmax = 10), то и оказывается возможным корректное упорядочение 100-элементного множества вариантов.

Кроме того, разработанная процедура существенно упроща ет работу эксперта. Дело в том, что варианты, являющиеся элементами двумерного пространства, по существу, определя ются номером строки i и столбца j матрицы S. А поскольку эксперт ранжирует альтернативы при фиксированных значени ях i (этап 1) и j (этап 2), то во многих случаях упорядочение Управление большими системами. Выпуск альтернатив оказывается достаточно тривиальным. Например, в игровых моделях упорядочиваются стратегии одного из игроков при фиксированной стратегии другого. Если эти стратегии строятся по принципу возрастания степени «эскалационности», то решение задачи ранжирования существенно упрощается. Что касается этапа доупорядочения альтернатив (этап 8), то здесь проводится попарное сравнение вариантов (причем во многих случаях довольно небольшое их число), что также упрощает работу экспертов.

Рассмотрим теперь общий случай N-мерного пространства.

3. Упорядочение множества альтернатив в N-мерном пространстве Рассмотрим множества Si, i = 1, …, N, и их декартово про изведение S1 S2 … SN. Тогда объект si1i2...iN S 1 S 2... S N будет представлять собой элемент N-мерного пространства.

Например, в задаче морфологического анализа Si будет пред ставлять собой множество вариантов решения i-й подпроблемы, а si1i2...iN – вариант решения проблемы S как совокупность i1, i2, …, iN вариантов решения подпроблем S1, S2, …, SN.

Требуется упорядочить элементы si1i2...iN по определенному критерию.

Метод решения данной задачи основан на сведении ее к со вокупности задач упорядочения альтернатив в двумерном про странстве. Действительно, зафиксируем два произвольных множества Si и Sj, а для остальных множеств Sk, k = 1, …, N, k i, k j, зафиксируем конкретные значения skl (например, для задачи морфологического анализа фиксируются конкретные варианты решения (N – 2) подпроблем). Тогда задача сводится к упорядочению альтернатив в двумерном пространстве S1 S2.

Решая совокупность таких задач (с использованием процедуры упорядочения «двумерного» множества альтернатив) для раз личных i, j и различных значений skl, мы получим совокупность множеств упорядоченных альтернатив. Ввиду наличия в них Системный анализ общих элементов, можно сформировать граф G, формализую щий экспертные предпочтения элементов всего N-мерного мно жества S.

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

Первая состоит в очень высокой трудоемкости решения за дачи упорядочения множества альтернатив в N-мерном про странстве с использованием рассмотренного метода.

Легко показать, что полное число N двумерных задач упо рядочения, на которые «разбивается» исходная задача S, опреде ляется по следующей формуле:

N N 1 N (1) N L, i j 1 k j 1 i i j ik где N – размерность задачи S (например, число игроков в теоре тико-игровых задачах или число подпроблем, составляющих проблему S в задаче морфологического анализа);

Li – число альтернативных вариантов решения i-й подзадачи (например, число стратегий i-го игрока в теоретико-игровых задачах или число альтернативных вариантов решения i-ой подпроблемы в задаче морфологического анализа).

Соответственно, общее число R экспертных ранжирований рассчитывается по формуле N N 1 N (2) R ( L j Lk ) Li.

j 1 k j 1 i i j ik Уже при N = 4, Li = 5 (например, в случае наличия четырех подпроблем с пятью вариантами решения каждая в задаче мор фологического анализа) число двумерных задач ранжирования будет 150, а число необходимых экспертных ранжировок – (следует отметить, что, с другой стороны, и число ранжируемых объектов здесь весьма велико – 625). При этом с увеличением N N и R растут экспоненциально. Поэтому при практическом использовании представленной схемы необходимо существенно снизить ее трудоемкость.

Управление большими системами. Выпуск Вторая особенность связана с возможностью появления в графе G контуров (т.е. противоречий в оценках эксперта), но в отличие от задачи упорядочения в двумерном пространстве, здесь эта проблема оказывается более сложной. Дело в том, что даже если эксперт корректно решит все двумерные задачи упо рядочения, это не гарантирует отсутствие контуров (т.е. проти воречий) в «итоговом» графе G. Другими словами, возможно появление контуров в графе G упорядочения элементов N мерного пространства, несмотря на отсутствие контуров во всех «двумерных» подграфах Gij.

При этом процедура экспертной корректировки оценок (т.е.

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

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

Граф G представляется в виде матрицы смежности X = ||xij||, где строки и столбцы матрицы соответствуют верши нам графа (т.е. упорядочиваемым элементам), а xij = 1, если в графе G существует ориентированная дуга из i-й вершины в j-ю (т.е. если эксперт упорядочил элементы N-мерного множества таким образом, что i-й элемент оказался предпочтительнее j-го) и 0 в противном случае.

Матрица X имеет следующие свойства.

1. Если xij = 0 для всех i j (т.е. для всех элементов ниже главной диагонали), то отношение предпочтения на множестве элементов, описываемое данной матрицей, будет отношением квазипорядка (частичного порядка).

2. Перестановка i-й и j-й строк матрицы и i-го и j-го столб цов соответствует перенумерации i-го и j-го элементов графа G.

Системный анализ Указанные свойства позволяют представить задачу коррек тировки контуров в графе G как задачу поиска графа G*, наибо лее «близкого» к графу G и удовлетворяющего свойству 1.

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

перенумерации вершин графа G), позволяющую получить мат рицу X* с минимальным числом ненулевых элементов ниже главной диагонали. Обнуляя эти элементы, мы и получим граф G*, минимально отличающийся от графа G и не имеющий кон туров. Содержательно данная процедура означает удаление минимального числа экспертных оценок, приводящее к отсутст вию экспертных противоречий. Далее производится экспертное доупорядочение элементов графа G* и получение итогового линейного упорядочения альтернативных вариантов.

Рассматриваемая задача известна как задача наилучшей приближенной триангуляции матрицы (нп-триангуляции). К ней сводится целый ряд задач обработки и анализа экспертной информации (ранжирования объектов, парных экспертных сравнений), структурного анализа сложных систем [1], моделей обработки межотраслевого баланса, сетевых моделей. Поэтому исследование задачи нп-триангуляции важно не только как элемент рассматриваемого метода экспертного упорядочения элементов N-мерного пространства, но имеет и самостоятельное значение.

Для получения точного решения задачи нп-триангуляции было предложено большое число алгоритмов, основанных на целочисленном линейном программировании [14], динамиче ском программировании [12, 22, 23], методе ветвей и границ [5, 9–11, 15, 17].

В [2, 3] был предложен один из наиболее быстрых алгорит мов методов ветвей и границ, использующий скоростной спуск по дереву вариантов. Однако, как было отмечено в данных работах, и этот алгоритм оказывается вполне эффективен (в смысле трудоемкости) лишь в том случае, когда число вершин в графе (т.е. число упорядочиваемых вариантов) не превышает 20–25. Это связано с тем, что рассматриваемая задача относится Управление большими системами. Выпуск к классу NP-сложных задач комбинаторной оптимизации, для которых в общем случае не существует алгоритмов гарантиро ванного нахождения оптимальных решений, трудоемкость которых была бы существенно меньше трудоемкости алгорит мов полного перебора.

Поэтому в случае, когда число вершин в графе оказывается существенно большим, в [3] было рекомендовано не искать точное решение задачи нп-триангуляции, а ограничиться нахо ждением локального оптимума.

Процедура поиска локального оптимума была предложена в [4] и представляла собой так называемое локально сбалансированное упорядочение. Решение, основанное на ло кально-сбалансированном упорядочении объектов, обладает тем свойством, что оно не может быть улучшено за счет произволь ного «перемещения» любого из объектов. Формально для ло кально-сбалансированного упорядочения I = (i1, i2, …, in) долж ны выполняются следующие условия:

x x | j s 1, t is ij (3) для s, t : 1 s t n.

xit xi j | j s, t Отношение группового доминирования означает сле дующее [3, 4]: xi Y ( aij a ji ) 0, x j Y где Y – подмножество множества упорядочиваемых объектов;

aij – элемент матрицы парных экспертных сравнений ранжируе мых объектов.

Можно показать, что поиск локально-сбалансированных упорядочений объектов оказывается достаточно простым и эффективным в смысле трудоемкости.

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

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

Генетические алгоритмы, впервые предложенные Дж. Холландом [20], представляют собой, по мнению автора, алгоритмы поиска, построенные на принципах, сходных с принципами естественного отбора и генетики. Обобщенно они объединяют в себе принцип выживания наиболее перспектив ных особей – вариантов решений и структурированный обмен информацией, в котором присутствует элемент случайности, который моделирует природные процессы наследования и мута ции. Дополнительным свойством этих алгоритмов является невмешательство человека в процесс поиска, он может влиять на него лишь опосредованно, задавая определенные параметры.

В настоящее время генетические алгоритмы представляют собой достаточно динамично развивающееся направление ис следований и находят применение при решении широкого круга задач, в том числе и в задачах комбинаторной оптимизации [6, 8, 17, 18].

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

Этап 1. Создание исходной популяции допустимых решений.

На этом этапе случайным образом формируется популяция (множество) допустимых решений задачи нп-триангуляции.

Каждое решение (называемое в генетических алгоритмах хромо сомой, особью или индивидуумом) представляет собой упорядо чение I = (i1, i2, …, in), где ik {1, …, n}, и ik ij, k, j = 1, …, n, т.е. представляет собой некоторую перестановку множества {1,..., n}. Легко понять, что любое упорядочение данного мно жества являтся допустимым решением задачи нп-триангуляции.

Размер популяции (т.е. число случайных перестановок) N является управляющим параметром генетического алгоритма и задается пользователем. При решении задачи нп-триангуляции Управление большими системами. Выпуск наилучшие результаты, как показало проведенное автором тестирование предлагаемого алгоритма, были получены, когда N варьировалась от 50 до 70.

Этап 2. Для каждой особи сформированной популяции (ка ждого допустимого варианта решения задачи из сформирован ного множества) оценивается мера ее «приспособленности» (т.е.

определяется значение целевой функции каждого варианта решения задачи).

Для задачи нп-триангуляции целевая функция варианта I = (i1, i2, …, in) определяется следующим образом:

n(n 1) n 1 n akl ( I ), (4) F ( I ) 2 l 1 k l где akl(I) – элемент матрицы парных сравнений A(I), соответст вующей упорядочению объектов I (другими словами, матрица A(I) представляет собой матрицу смежности графа G(I), в кото ром вершины {1,..., n} перенумерованы исходя из упорядоче ния I).

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

F ( I ) max, причем если возможно найти такое I*, что I F(I*) = n(n – 1)/2, то оно заведомо будет решением задачи, так как ниже главной диагонали матрицы A(I) ненулевых элементов не будет.

Этап 3. На данном этапе происходит отбор особей «родителей» с наилучшей мерой «приспособленности» для процесса «размножения», т.е. выбираются варианты решения задачи с наилучшими значениями целевой функции.

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

Существует целый ряд операторов отбора. Для задачи нп-триангуляции использовался оператор отбора, основанный Системный анализ на методе «рулетки», для которого вероятность участия особи в процессе размножения вычисляется по формуле F (5) P( I ) N i.

Fj j Очевидно, что при таком отборе варианты решения с боль шим значением целевой функции будут выбираться чаще, чем варианты с меньшим ее значением. Легко заметить также, что одна особь (один вариант решения задачи) может быть задана в нескольких родительских парах.

Этап 4. На этом этапе происходит «скрещивание» лучших особей, отобранных на этапе 3. Данная процедура призвана моделировать природный процесс наследования, т.е. обеспечить передачу свойств «родителей» «потомкам». Предполагается, что при скрещивании лучших «родителей» их «потомки» будут обладать еще более высокой степенью «приспособленности», т.е.

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

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

Для реализации «скрещивания» используется так называе мый оператор кроссинговера. В настоящее время существует целый ряд таких операторов для задач комбинаторной оптими зации. Наиболее применяемыми из них являются оператор кроссинговера с частичными соответствиями, упорядоченный оператор кроссинговера, циклический оператор кроссинговера [8].

Например, для «родительских» особей I1 = {9 8 2 1 7 4 Управление большими системами. Выпуск 6 3} и I2 = {1 3 4 5 8 7 9 6 2} применение циклического операто ра кроссинговера приведет к появлению следующих потомков I 1 = {9 3 4 1 8 7 5 6 2} и I 2 = {1 8 2 5 7 4 9 6 3}.

Можно заметить, что каждая из особей-«потомков» «насле дует» свойства обоих особей-«родителей», что позволяет пред положить, что степень «приспособленности» (целевая функция) «потомков» окажется лучше, нежели у «родителей».

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

Поэтому в настоящей работе предлагается использовать разра ботанный оператор «жадного» кроссинговера.

Суть процедуры «скрещивания» с использованием операто ра «жадного» кроссинговера состоит в следующем.

Пусть имеются две особи-«родителя» I1 = (i11, i21, …, in1) и I = (i12, i22, …, in2). Рассмотрим элементы i11 и i12 (гены, согласно терминологии генетических алгоритмов). Значения i11 и i представляют собой какие-то числа из множества{1,..., n} и определяют, какие из ранжируемых объектов являются лучшими (стоящими на первом месте) соответственно для ранжировок I1 и I2.

Определим лучший объект для одной из особей-«потомков»

1 (i 1, i 1,..., i 1 ) следующим образом:

2 n I если в графе G парных сравнений ранжируемых вариантов объект i11 доминируется меньшим числом альтернатив, нежели объект i12 (т.е., если в графе G число дуг, входящих в вершину i меньше, чем число дуг, входящих в вершину i12), то первый ген i11 в особи-«потомке» I 1 будет i11, в противном случае – i12.

Аналогично определяется и второй ген i21 особи-«потомка»

I 1 – сравниваются, соответственно, гены i21 и i22 особей «родителей», но при этом не учитываются дуги, исходящие из вершины i11 графа G (действительно, поскольку объект i11 упо рядочивается, как более предпочтительный, то его возможное доминирование над «нижестоящими» объектами является впол не допустимым).

Системный анализ Таким же образом определяется третий ген i31 (не учитыва ются, соответственно, дуги, исходящие из вершин i11 и i21 ) и т.д.

Если на каком-то шаге один из генов i11 или il2 оказывается «использованным» ранее, то «свободный» ген и определяет значение il1. Если же «использованными» ранее оказываются оба гена il1 и il2, то значение определяется случайным образом (естественно, из числа «неиспользованных»). Таким образом формируется одна из особей-«потомков» I 1.

Другая особь-«потомок» I «строится» по тому же принци пу, но «с конца строки».

Например, последний ген in2 особи-«потомка» I 2 определя ется следующим образом: если в графе G парных сравнений ранжируемых вариантов объект in1 доминируется большим числом альтернатив, нежели объект in2 то in2 принимает значе ние in1, в противном случае – in2.

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

Этап 5. Сформированные на этапе 4 особи (варианты реше ний) с заданной пользователем вероятностью могут быть под вергнуты мутации. Оператор мутации предполагает замену какого-либо гена (элемента) особи I l на ген другой особи I k ;

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

Управление большими системами. Выпуск Для рассматриваемого алгоритма нп-триангуляции исполь зовался оператор мутации, предполагающий перестановку в строке I l (i1l, i2l,..., inl ) двух случайным образом выбранных элементов.

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

Хотя, как правило, вероятность мутации, в отличие от веро ятности скрещивания, выбирается достаточно малой (порядка 0,1), в рассматриваемой задаче, как показало проведенное авто ром тестирование предлагаемого алгоритма, лучшие результаты в его работе были получены в случае, когда вероятность мута ции варьировалась от 0,3 до 0,4.

Этап 6. В результате проведения этапов 2–5 формируется новая популяция, особи которой, исходя из «законов генетики», должны обладать более высокой степенью «приспособленно сти», нежели представители предыдущей популяции.

Эта новая популяция, в свою очередь, подвергается проце дурам отбора, селекции и мутации. Этапы 2–6 повторяются до тех пор, пока не окажется выполненным критерий остановки работы алгоритма. Критерии остановки работы алгоритма также задаются пользователем и могут определяться временными ограничениями, ограничениями на число генерируемых популя ций, достижением определенного значения целевой функции или же отсутствием улучшения ее значений в процессе работы алгоритма и др.

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

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

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

Что касается метода ветвей и границ [2, 3], то, как показал эксперимент, в отличие от него, генетический алгоритм позво лял решать в реальном масштабе времени задачи нп-триангуляции матриц, размерность которых существенно превышала ограничение в 20–25 объектов.

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

Тестирование показало (было решено порядка 100 задач, размерность матрицы варьировалась от 50 до 80), что во всех случаях упорядочение, полученное с использованием генетиче ского алгоритма, оказалось не хуже локально сбалансированного упорядочения, а примерно в 10% случаев превысило его (правда, увеличение значения целевой функции было небольшим).

Управление большими системами. Выпуск Рис. 5.

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

В заключение отметим следующее:

– декомпозиционный метод экспертного упорядочения эле ментов N-мерного пространства позволяет надежно проранжи ровать достаточно большое число исследуемых вариантов;

– использование данного метода существенно упрощает ра боту экспертов, поскольку они имеют возможность проводить упорядочение «многомерных» альтернативных вариантов, учитывая лишь один из нескольких критериев их оценки;

– предложенный генетический алгоритм решения задачи нп-триангуляции матриц позволяет довольно эффективно ре Системный анализ шить проблему устранения противоречий в экспертных оценках, которые могут возникать при ранжировании вариантов;

– развитие предлагаемого подхода может идти в направле нии снижения трудоемкости экспертных процедур по упорядо чению исследуемых объектов путем поиска «наиболее вероятно го» или «наиболее близкого» упорядочения. В этом направлении интерес представляют работы [13, 19, 21].

Литература.

1. БЕЛКИН А.Р., ЛЕОНОВ В.Ю. Об одном подходе к струк турному преобразованию сложных систем // Проблемы бионики. – 1987. – №39. – С. 70–75.

2. БЕЛКИН А.Р. Приближенная триангуляция матриц в зада чах ранжирования и обработки межотраслевого баланса // Изв. АН СССР. Техн. кибернетика. – 1981. – №1. – С. 26– 31.

3. БЕЛКИН А.Р., ЛЕВИН М.Ш. Принятие решений: комбина торные модели аппроксимации информации. – М.: Наука.

Гл. ред. физ.-мат. лит., 1990. – 160 с.

4. БЕЛКИН А.Р., ШАХНОВ И.Ф. Об одной модели группового упорядочения // Интерактивные системы принятия решений в планировании и управлении большим городом: Тезисы докл. Всес. семинара – М.: НПО АСУ «Москва», 1981. – С. 190–193.

5. БУРКОВ В.Н., ГРОППЕН В.О. Разрезы в сильно связных графах и потенциалы перестановок // Автоматика и теле механика. – 1972. – №6. – С. 111–119.

6. ЕМЕЛЬЯНОВ В.В., КУРЕЙЧИК В.М. Теория и практика эволюционного моделирования. – М.: ФИЗМАТЛИТ, 2003. – 432 с.

7. КОЗЕЛЕЦКИЙ Ю. Психологическая теория решений. – М.:

Прогресс, 1979. – 504 с.

8. КУРЕЙЧИК В.М. Генетические алгоритмы. Обзор и со стояние // Новости искусственного интеллекта –1998. – №3. – С. 14–63.

Управление большими системами. Выпуск 9. ЛИТВАК Б.Г. Об упорядочении объектов по предпочтени ям // Математические вопросы управления производством – 1973. – №5. – С. 47–56.

10. МИРКИН Б.Г. Анализ качественных признаков и струк тур. – М.: Статистика, 1980. – 320 с.

11. ПАВЛОВ Ю., ТОНЕВ М. Комбинаторный алгоритм нахо ждения медианы Кемени на множестве частичных отно шений // Оптимизация, принятие решений, микропроцес сорные системы. Труды 8-го Болгарско–польского симп. – София, 1985. – C. 138–147.

12. BHAT V.S., KINARIVALA B. Optimal tearing in large scale systems and minimum feedback cutsets of a digraph // Journal of Franklin Inst. – 1979. – Vol. 307, №2. – P. 83–94.

13. CRITCHLOW D.E., FLIGNER M.A. Paired comparison, triple comparison, and ranking experiments as generalized linear models, and their implementation in GLIM // Psychometrika. – 1991. – №56. – P. 517–533.

14. DE CANI J.S. Maximum-likelihood paired comparison ranking by linear programming // Biometrika. – 1969. – Vol. 56, №3. – P. 537–545.

15. DE CANI J.S. A branch and bound algoritmh for maximum likelihood paired comparison ranking // Biometrika. – 1972. – Vol. 59, №1. – P. 131–135.

16. FLUECK J.A., KORSH J.F. A branch search algoritmh for maximum likelihood paired comparison ranking // Biometrika. – 1974. – Vol. 61, №3. – P. 621–626.

17. GOLDBERG D.E. Genetic Algorithms in Search. Optimization and Machine Learning. – New York: Addison–Wesley Publish ing Company, Inc., 1989. – 372 p.

18. Handbook of Genetic Algoritms / Ed. by L. Davis. – New York:

Van Nostrand Reinhold, 1991. – 385 p.

19. HATZINGER R., DITTRICH R. An R Package for Modeling Preferences Based on Paired Comparisons, Rankings, or Rat ings // J. of Statist. Soft. – 2012. – Vol. 48, №10. – P. 1–31.

20. HOLLAND J.H. Adaptation in natural and artificial systems.

An introductory analysis with application to biology, control, Системный анализ and artificial intelligence. – London: Bradford book edition, 1994 – 211 p.

21. PENDERGRASS R.N., BRADLEY R.A. Ranking in triple comparisons // In: I. Olkin and others (ED.), Contributions to probability and statistics. Stanford Univ. Press, 1960. – P. 331– 351.

22. REMAGE R., THOMPSON W.A. Maximum-likelihood paired comparison rankings // Biometrika. – 1966. – Vol. 53, № 1–2. – P. 143–149.

23. SPIRCU T. Sur le probleme de la triangulation // Rev.

Roumaine de Math. Pures et Appl. – 1980. – Vol. XXV, №2. – P. 271–276.

EXPERT RANKING OF ALTERNATIVES IN HIGH DIMENSIONAL PROBLEMS Lev Abaev, Russian Institute for Strategic Studies, Moscow, Doctor of Science, leading researcher (abaev_lev@mail.ru).

Abstract: The problem is considered of expert ranking of alterna tives, which can be matched to elements of an N-dimensional space.

To solve this problem we propose decomposition methods, which help to significantly increase the number of alternatives reliably ranked by experts as compared to traditional expert procedures. To eliminate possible expert contradictions we propose the genetic algorithm to solve the problem of matrix triangulation.

Keywords: the expert methods, ranking of alternatives, decompo sition, genetic algorithms.

Статья представлена к публикации членом редакционной коллегии Ю. В. Cидельниковым Управление большими системами. Выпуск УДК 007:519. ББК 32. ЭЛЕМЕНТЫ ТЕОРИИ АССОЦИАТИВНОЙ СЕМАНТИКИ* Кучуганов В. Н. (ФГБОУ ВПО «Ижевский государственный технический университет», Ижевск) В статье предлагается инструментарий, призванный умень шить неоднозначность семантических моделей высказываний и тем самым повысить толерантность человеко-машинного диалога и эффективность систем извлечения знаний. Семан тическая модель ситуации, сюжета описывается плекс грамматикой, содержащей 4 сорта символов с различным ко личеством точек примыкания. Процесс синтеза семантической модели текста рассматривается как процесс вывода коррект ной означивающей конструкции, адекватной человеческому восприятию текста. Предлагаются операции сопоставления и сшивания графов образов. Оценка адекватности семантиче ской модели осуществляется путем проверки грамматической корректности модели, установления соответствия между элементами новой модели и имеющимися в базе системы, а также выявления отличий в свойствах, отношениях и связях новых элементов.

Ключевые слова: семантическая модель, плекс-грамматика, граф образа, ассоциативная семантика, вектор виртуально сти, оценка адекватности.


* Работа выполнена при поддержке Федеральной целевой программы «Научные и научно-педагогические кадры инновационной России»

Правительства Российской Федерации (проект №16.740.11.0423).

Валерий Никонорович Кучуганов, доктор технических наук, профес сор (kuchuganov@istu.ru).

Системный анализ 1. Введение Этот материал следует рассматривать скорее не как теорию, а как очередную попытку формализовать такое многогранное понятие, как семантика контекстно-зависимых высказываний.

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

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

Назначение текста – описать реальный или виртуальный (вымышленный) сюжет, продукт, изделие. Чем отличаются тех нические тексты от произведений искусства, «физика от лири ки»? Утрированно ценность последней возрастает по мере роста смысловой многозначности, тогда как в математике и технике это серьезнейший недостаток.

Герменевтика – теория понимания смысла – доказала, что нельзя добиться однозначности истолкования естественно языкового текста. Полифония высказывания заключается в том, что истина – это не конечное высказывание, а процесс. Совет ский философ Михаил Бахтин (1895–1975) открыл полифонию художественного высказывания, развив заимствованное у Эйн штейна и Германа Минковского понятие «пространство–время»

и назвал его «хронотоп» (от греческого хронос – время и топос – пространство). Бахтин утверждает, что слово есть хронотоп, оно многомерное и говорит о неисчислимости смыслов, которые содержатся в любом высказывании.

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

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

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

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

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

Представим семантическую модель (СеМ) текста, описы вающего ситуацию, в виде нечеткого графа ситуации, все вер шины и ребра которого связаны с записями онтологического толкового словаря (ОТС), описывающими методы их интерпре тации.

Системный анализ Теорию ассоциативной семантики (ТАС) определим как теорию TAS(O(OV, {G}, {Pattern}, {R}), {P}, V), где O – онтологическая модель предметной области;

OV – он тологический толковый словарь, в котором каждое слово или устойчивое словосочетание имеет несколько толкований со ссылками на онтологию, где эти понятия реализуются;

{G} – множество грамматик, задающих правила построения сложных понятий из простых;

{Pattern} – множество графов образов субъектов (экземпляров понятий);

{R} – множество от ношений;

{P} – множество операций с образами;

V – вектор виртуальности системы управления, реализующей ТАС – сово купность параметров настройки, которые задают прагматику системы.

Логический вывод путем моделирования рассуждений – это исчисление истинности высказывания (вопроса) по заданному описанию ситуации. При этом рассуждениями считается цепоч ка подстановок в процессе поиска ответа.

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

Задача (вопрос) ставится следующим образом.

Имеется:

1) онтологическая модель предметной области (ОМПрО);

2) текст, описывающий ситуацию/сюжет – условие задачи.

Требуется найти значение свойства, отношения, сущности.

Решение:

1. Построить адекватную СеМ ситуации/сюжета.

2. Дополнить СеМ информацией из аналогов с помощью ас социативных связей.

3. Извлечь (вычислить) ответ.

Управление большими системами. Выпуск 3. Семантическая модель ситуации Для формализации семантической модели текста, описы вающего ситуацию (СеМС), воспользуемся плекс-грамматикой [1, 2], где символы грамматических конструкций имеют не две (слева, справа), а N «точек примыкания».

Выделим 4 сорта элементов (деталей), из которых состав ляются модели ситуаций, и представим их в виде символов (рис. 1).

Рис. 1. Символы деталей семантической модели ситуации:

а) процесс;

б) предмет;

в) свойство;

г) отношение Процессы в точках примыкания соединяются с элементами, отвечающими на вопросы:

(кто), {из чего}, {чем}, (где), (как), (что), (сколько), (кому), (для чего), (когда).

Фигурные скобки обозначают, что несколько символов од ного сорта может быть связано с данным символом. Например, для процесса может потребоваться несколько наименований ма териалов (из чего), инструментов (чем).

Предметы в точках примыкания связываются с другими элементами в соответствии с вопросами:

(из чего), {какой}, (чей), {для чего}.

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

Свойство связывается с одной сущностью, которую оно характеризует.

Отношение связывает формулой две или более сущности.

Системный анализ Плекс-грамматику, порождающую множество семантиче ских моделей ситуаций, представим как шестерку VT, VN, RS, R0, Q, q0, где VT – множество основных символов;

VN – множество производных (вспомогательных) символов;

RS – множество сис темных правил подстановки;

R0 – множество предметных пра вил подстановки;

Q – множество идентификаторов – меток то чек примыкания;

q0 – специальной (пустой) идентификатор.

Основные символы изображены на рис. 1.

Производные элементы накапливаются в ПрО как устойчи вые сочетания сущностей. Например: человек – паспорт – квар тира;

театр – гардероб – фойе – зрительный зал.

Идентификаторы точек примыкания для одного и того же элемента должны быть различными. В какой-то ПрО это множе ство может быть сокращено или расширено. Здесь множество идентификаторов точек примыкания приближено к вопроси тельным словам русского языка.

Идентификатор q0 служит для заполнения места, не связан ного ни с какой сущностью, т.е. является признаком неполноты СеМС.

Правила подстановки – это правила построения конструк ций из символов и ранее определенных конструкций, т.е. из ос новных элементов и производных.

Минимальной конфигурацией ситуации можно считать Sit p s, где p – процесс;

s – предмет – субъект, выполняю щий процесс.

Например: Имеется стол.

Системные правила подстановки. Первую группу сис темных правил подстановки составляют правила, основанные на падежной грамматике Ч. Филмора [11], определяющей семанти ческие валентности слов, т.е. их роли в предложении (глубин ные падежи).

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

Управление большими системами. Выпуск (1) Situation p s (кто – для чего), Situation a Situation (где – какой) a Situation (чье – как), (2) Situation s Situation (для чего – что) s Situation (для чего – из чего) s Situation (для чего – чем) s Situation (для чего – где) s Situation (для чего – кому) s Situation (для чего – из чего) s Situation (для чего – чей) (3) Situation r Situation (что, с чем – чьеij, чьеkl) r Situation (что, с чем – sj, sl), j l r Situation (что, с чем – pj, pl), j l r Situation (что, с чем – sj, pl), (4) (5) Situation p r Situation (когда H, когда K – что, с чем – pi, ps), где p – процесс;

s – предмет;

a – свойство;


r – отношение.

Первое правило соединяет процесс и предмет через их точ ки примыкания «кто» (делает), «для чего» (предназначен) соот ветственно.

Второе правило добавляет к ситуации свойство, соединяя точку примыкания «чье» свойства с точкой примыкания «ка кой» предмета или процесса.

Третье правило присоединяет к ситуации новый предмет с помощью его точки примыкания «для чего» и точки примыка ния процесса «что» или «из чего», или «чем», или «где», или «кому», или точек примыкания другого предмета «из чего», или «чей».

Отношение как метод вычисления значений связывает зна чение неизвестного параметра одного объекта относительно значения однотипного параметра другого объекта. Напомним, что формулой любого отношения может быть константа.

Четвертое правило показывает, как отношение связывает i-е свойство j-го объекта с k-м свойством l-го объекта (рис. 3а) или связывает объекты в целом в случае, если это отношения родст ва, толерантности, сопутствия, сопоставления (сходства) и неко торые другие (рис. 2б, 2в).

Системный анализ Рис. 2. Примеры подстановки отношений Пятое правило присоединяет к ситуации новый процесс.

Правило показывает, что вначале нужно связать его во времени с какими-то имеющимися процессами с помощью отношения следования. Другие связи нового процесса построятся рекур сивно с помощью правил (2), (3), (4).

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

Тогда везде, где вместо идентификатора записан q0, можно под ставить элемент из соответствующего множества взаимозаме няемых. Например, экскаватор лопата.

Пусть имеется некоторая обобщенная производственная си туация SituationO. Обозначим S qi(p) нечеткое множество взаимо ~ заменяемых участников процесса p в точке примыкания qi Q.

Нечеткое множество S – это множество пар x, (x), где ~ (x): S M, M = {0, 1} – функция, которая отображает x на еди ничный отрезок M, определяя степень принадлежности элемента x множеству S. Предметное правило подстановки имеет вид:

SituationO (qi(p) = q0) ( S qi(p) ) qi(p) = x, (x), ~ т.е. элемент x может быть подставлен вместо отсутствующего элемента со степенью адекватности (x).

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

Пример 1. Ёж [7]. Раз шел я по берегу нашего ручья и под кустом заметил ежа. Он тоже заметил меня, свернулся и за шипел. Я прикоснулся к нему кончиком сапога, он страшно фыркнул и поддал своими иголками в сапог.

На рис. 3 показана семантическая модель (схема) сюжета, составленная с помощью плекс-грамматики из символов про цессов, предметов, свойств и отношений. Пунктиром здесь обо значены связи между одними и теми же (копируемыми) элемен тами, описанными в разных предложениях, т.е. когда один субъ ект имеет несколько разных идентификаторов. Например, Ива нов – Он – Студент – Антон;

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

Рис. 3. Пример семантической модели текста, составленной с помощью плекс-грамматики 4. Вектор виртуальности Рассмотрим высказывание A B (из А следует B). Логиче Системный анализ ской связке «следует» в различных предметных областях могут быть поставлены в соответствие одно или несколько свойств (параметров), принимающих каждое одно из двух или более значений и выражающих различные аспекты отношения выска зывания к реальности:

1) вероятность истинности в действительности;

2) модальность – степень необходимости выполнения выска зывания (желательно, возможно, необходимо…);

3) временную зависимость достоверности высказывания, на пример, вчера оно было истинным, а сегодня – не совсем;

4) сослагательность – гипотетичность высказывания («Если бы…»);

5) возвратность и притяжательность – отношение принад лежности высказывания автору или другому субъекту;

6) толерантность – отношение субъекта к высказыванию («Мне нравится, что я больна не Вами»);

7) источник утверждения – органы чувств (зрение, слух, обоняние, вкус), интуиция, мыслительные, речевые, письменные и другие процессы, выражаемые в естественном языке менталь ными глаголами. Например, «Лучше один раз увидеть, чем сто раз услышать» выражает степень достоверности обсуждаемой характеристики некоего предмета.

Поскольку понятие «ментальность» не присуще компьюте ру, заменим его на виртуальность – мнимость, искусственность, нереальность.

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

(A) или {1, 2,…, n} (A), … n читается как «постольку, поскольку 1, 2, …, то A», где 1, …, n – лингвистические переменные [4, 5], принимающие нечеткие значения соответствующих параметров отношения вы сказывания к действительности. Иначе говоря, виртуальность – это вектор в пространстве лингвистических переменных, харак Управление большими системами. Выпуск теризующий отношение между высказыванием и действитель ностью.

Вектор виртуальности умножается на значение истинности высказывания и тем самым корректирует влияние ментальности эксперта на принятие решений. Естественно-языковое предло жение, как правило, описывает несколько фактов. Виртуаль ность может относиться к отдельному факту, предложению или рассказу в целом.

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

Если иметь в виду технические тексты, то оценить адекват ность семантической модели (СеМ) реальной информации, по ступившей на вход системы, можно путем сопоставления СеМ с имеющимися в базе опыта. Исходя из предположения, что новая СеМ будет составлена из известных элементов, в которых изме нены какие-то свойства, отношения, взаимосвязи, достаточно установить соответствие с известными, выявить отличия и про верить корректность построенной модели. Заметим, что если хотя бы один параметр отличается от аналогов, то в технике это либо изобретение, либо чрезвычайная ситуация, а в искусстве – это «что-то интересное».

Граф образа объекта Qu порядка u – это граф Gu = G(V, E, A), где V – множество вершин g, отображающих подобъекты qu–1;

E – семейство ребер e E = (giu–1 Riju–1 gju–1), giu–1, gju–1 V, ото бражающих отношения между образами подобъектов;

A = (AH, EH) – гиперграф атрибутов ai1(gi),..., aim(gi) AH вер шин и ребер eh EH, которые показывают принадлежность ат рибутов из множества A некоторой вершине gi V.

Для реализации подхода нам потребуются операции с об разами [3]:

1) абстрагирование – отключение параметров, не существен ных для задачи;

Системный анализ 2) идеализация образа – замена нескольких параметров од ним обобщенным;

3) аморфное преобразование образа (масштабирование) с со хранением внутренних и внешних систем отношений. Напри мер, размерная параметризация геометрических моделей в САПР. Например, «Лето – это маленькая жизнь» (Олег Митя ев). В технике такой прием используется при «заимствовании», например, киль самолета киль яхты;

4) сопоставление (сравнение) образов – выявление сходства и отличий;

5) сшивание образов – стыковка подграфов известных обра зов для получения графа нового образа;

6) визуализация – перевод вербального в образное.

Рассмотрим подробнее некоторые из них.

Сравнение образов.

Пусть G1 = G(V1, E1, A1) – граф известного (эталонного) об раза;

G2 = G(V2, E2, A2) – граф анализируемого образа;

r = A', A" – гребенка (набор) анализируемых признаков, где A' – множество имен признаков, определяющее степень абст ракции, A" – множество коэффициентов, определяющих точ ность сравнения признаков как dai = a1i * a"k.

Будем называть общей гомоморфной частью (G1') графов G1 и G2 часть G2', определенную на множестве V2' и состоящую из всех ребер (E1) = E2 = (g2i, g2j), g2i, g2j V2' V2, для кото рых существуют соответствующие ребра E1 = (g1i, g1j) = –1(E2) = ( –1(g2i), –1(g2j)), g1i, g1j V1, в графе G1, при этом однозначное отображение существует тогда и только тогда, когда вершины g2i, g2j и соответствующие им прообразы g1i, g1j совпадают в n-мерном пространстве A' ана лизируемых признаков с точностью, заданной A".

Оценка сходства образов, взвешенная по k-му свойству, n Lk ( D '2 j ) есть C jn1, где Lk(D1i) и Lk(D'2j) – протяженность всех i1 Lk ( D2i ) несоприкасающихся цепочек в эталоне и совпавших в анализи руемом графе (соответственно), вычисленная с помощью сум мируемых по цепочке значений k-го свойства вершин, что авто матически придает больший вес совпадению тех элементов объ Управление большими системами. Выпуск ектов, которые в соответствии с заданной гребенкой признаков идентификации считаются более существенными.

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

Сшивание образов.

Пусть графы G1 и G2 образов имеют некоторую общую го моморфную часть(G1'), найденную с помощью операции срав нения образов и выражающую их сходство.

Обозначим через H2 общую гомоморфную часть (G1'), а ее дополнение в графе G2 – через H 2. Прообраз общей гомоморф ной части обозначим через H1, а его дополнение в G1 – через H1.

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

1. Объединение G1P с частью H2: G1P 2(H1').

2. Сшивание части H1 с частью 2( H 2 ) путем построения час c c ти H = G(E ) так, что e2 = ((g1), 2–1(2(g2))) G2P 2(e2) Hc.

Тогда граф G3 = G1 ( H 2 ) Hc отображает новый образ, который включает в себя два известных подобраза.

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

Атрибутивные связи (кто – какой, кто – чей) описывают свойства объектов, принадлежность, родство и другие их харак теристики.

Ролевые связи (кто – кому – что – как – для чего – где – ко гда и т.д.) устанавливаются при выявлении отношений процес суальных, системных, коммуникации, положения, следования, в результате чего строится концептуальная модель процесса.

Помимо вышеперечисленных, в ходе обучения и накопле ния опыта возникают ассоциативные связи – по сходству сущ Системный анализ ностей или их атрибутов или их отношений. Психологи разли чают 3 вида ассоциаций: по сходству;

по смежности;

по контра сту.

– Что ли, ножик – вилкин муж? [9] – по-видимому, из часто встречающейся ситуации, в которой нож и вилка сопутствуют друг другу, при том что нож мужского рода, а вилка – женского, у девочки возникает модель семейной пары и теперь она спра шивает подтверждения у взрослых.

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

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

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

Таким образом, логика процессуальных отношений – это вычисление истинности (качества) процессуальных отношений.

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

Вычисление оценок (например, «хорошо», «удовлетвори тельно», «плохо») каждой составляющей (см., например, [2, 8]), а также процессов, в результате которых появились «плохие»

составляющие, позволит за несколько шагов по ассоциативной цепочке придти к первопричине возникновения неудовлетвори Управление большими системами. Выпуск тельной ситуации. Тогда, чтобы получить ответ на извечный во прос «что делать?», надо выполнить некоторые преобразования и подстановки в графе процессуальных отношений задачи.

Пример 2. «Тише едешь – дальше будешь» (пословица).

Во-первых, тире здесь, очевидно, обозначает импликацию, а высказывание в целом – правило продукционного вида если – то.

Во-вторых, многие из нас ответили бы: смотря на чем и ку да – на личном авто?, в аэропорт? и т.п.

Семантическая модель (СеМ) высказывания:

Глагол Ехать обозначает действие. СеМ ситуации, описы ваемой в посылке, содержит 2 символа: процесс и отношение (рис. 1). Изначально мы имеем несколько открытых точек при мыкания, которые инициируют запросы к базе знаний: кто?, куда?, чем (на чем)? и т.д. Для отношения Тише не закрыта точ ка примыкания по сравнению с чем?

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

В части следствия глагол Быть обозначает состояние – со вокупность значений параметров процессов и участвующих в них субъектов и, соответственно, могут быть найдены (если быть дотошным) ответы на вопросы: где?, когда?

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

Пример 3. Задача про Ивана-царевича [6]. Собрался Иван-царевич на бой со Змеем Горынычем, трехглавым и трех хвостым. «Вот тебе меч-кладенец, – говорит ему баба Яга. – Одним ударом ты можешь срубить либо одну голову, либо две головы, либо один хвост, либо два хвоста. Но запомни: срубишь один хвост – два вырастут, срубишь два хвоста – голова вы растет, срубишь голову – голова вырастет, срубишь две головы – ничего не вырастет». За сколько ударов Иван-царевич может срубить Змею все головы и хвосты?

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

Таблица 1. Предметы Ситуация Наименование Головы, шт. Хвосты, шт.

Начальная Змей Г. 3 Целевая Змей Г. 0 Таблица 2. Действия Наименование Кто Чем Как Что Сколько Кому Иван Срубать Меч Вычесть ? ? Змей Г.

царевич Вырастать – – Прибавить ? ? Змей Г.

Таблица 3. Отношения № п/п Формула Срубать.Что IN [Голова, Хвост] Срубать.Сколько IN [1, 2] (Срубать.Что = «Хвост» (Срубать.Ск = 1) (Вырастать.Что = «Хвост»), (Вырастать.Ск = 2) (Срубать.Что = «Хвост») (Срубать.Ск = 2) (Вырастать.Что = «Голова»), (Вырастать.Ск = 1) (Срубать.Что = «Голова») (Срубать.Ск = 1) (Вырастать.Что = «Голова»), (Вырастать.Ск = 1) (Срубать.Что = «Голова») (Срубать.Ск = 2) (Вырастать.Что = nil) 7. Заключение Таким образом, процесс синтеза семантической модели тек ста, описывающего ситуацию или сюжет, мы интерпретируем как процесс вывода корректной означивающей конструкции, адекватной человеческому восприятию текста.

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

Оценка адекватности семантической модели позволяет:

– оценить степень новизны ситуации;

– проверить корректность формулировки задачи;

– пополнить проблемную ситуацию информацией, подразу меваемой, но не заданной в явном виде или достроить (доопре делить) ситуацию по аналогии с известными.

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

В целом, на наш взгляд, инструментарий ассоциативной се мантики повысит качество коммуникаций «человек–машина».

Литература ЗАДЕ Л.А. Роль мягких вычислений и нечеткой логики в по 1.

нимании, конструировании и развитии информационных интеллектуальных систем // Новости Искусственного Ин теллекта. – 2001. – №2–3. – С. 7–11.

ИВИН А.А. Основы теории аргументации. – М.: ВЛАДОС, 2.

1997.

КУЧУГАНОВ В.Н. Автоматический анализ машино 3.

строительных чертежей. – Иркутск: Изд-во Иркутского ун-та, 1985. – 112 с.

Системный анализ КУЧУГАНОВ В.Н. Вербализация реальности и виртуаль 4.

ности. Ассоциативная семантика // Искусственный интел лект и принятие решений. – 2011. – №1. – С. 55–66.

КУЧУГАНОВ В.Н., СЕНТЯКОВА А.В. Интеллектуальный 5.

тренажер по программированию // Труды Конгресса по ин теллектуальным системам и информационным технологиям «AIS'10». Научн. издание в 4-х томах. – М.: Физматлит, 2010. – Т.1. – С. 534–541.

ЛИХТАРНИКОВ Л.М. Занимательные логические задачи.

6.

(Для учащихся начальной школы). – Спб.: Лань, МИК, 1996. — 125 с.

ПРИШВИН М. Ёж. Сб. рассказов «Зеленый шум». – М.:

7.

«Правда», 1983.

ТАРАСОВ В.Б., КАРЛУЦКАЯ А.П. Нечеткие лингвисти 8.

ческие модели предпочтений когнитивных агентов // Труды Конгресса по интеллектуальным системам и информацион ным технологиям «AIS'10». Научн. издание в 4-х томах. – М.: Физматлит, 2010. – Т.2. – С. 277–284.

ЧУКОВСКИЙ К.И. От двух до пяти. Собр. соч. в 6 томах.

9.

Том 1. – М.: Худ. лит., FEDER J. Plex languages // Information Science. – 1971. – 10.

№3. – P. 255–241.

FILLMORE CH.J. The case for case // Universals in Linguistic 11.

Theory / Eds. E. Bach, R.T. Harms. – New York, FU K.S. Syntactic Methods in pattern recognition. – Academic 12.

Press, New York and London, 1974. Русский перевод: Фу К.

Структурные методы в распознавании образов. – М.: Мир, 1977.

ZADEH L.A. Toward a Theory of Fuzzy Information Granula 13.

tion and its Centrality in Human Reasoning and Fuzzy Logic // Fuzzy Sets and Systems. – 1997. – Vol. 90. – P. 111–127.



Pages:   || 2 | 3 | 4 | 5 |   ...   | 7 |
 





 
© 2013 www.libed.ru - «Бесплатная библиотека научно-практических конференций»

Материалы этого сайта размещены для ознакомления, все права принадлежат их авторам.
Если Вы не согласны с тем, что Ваш материал размещён на этом сайте, пожалуйста, напишите нам, мы в течении 1-2 рабочих дней удалим его.