WWW.LIBRUS.DOBROTA.BIZ
БЕСПЛАТНАЯ  ИНТЕРНЕТ  БИБЛИОТЕКА - собрание публикаций
 

Pages:   || 2 | 3 |

««Информатика и управление» РАН КИИ-2016 3–7 октября 2016 г. г. Смоленск, Россия ПЯТНАДЦАТАЯ НАЦИОНАЛЬНАЯ КОНФЕРЕНЦИЯ ПО ИСКУССТВЕННОМУ ИНТЕЛЛЕКТУ С МЕЖДУНАРОДНЫМ УЧАСТИЕМ Труды ...»

-- [ Страница 1 ] --

Российская ассоциация искусственного интеллекта

Федеральный исследовательский центр

«Информатика и управление» РАН

КИИ-2016

3–7 октября 2016 г .

г. Смоленск, Россия

ПЯТНАДЦАТАЯ

НАЦИОНАЛЬНАЯ КОНФЕРЕНЦИЯ

ПО ИСКУССТВЕННОМУ ИНТЕЛЛЕКТУ

С МЕЖДУНАРОДНЫМ УЧАСТИЕМ

Труды конференции

Том 3

Смоленск

Российская ассоциация искусственного интеллекта Федеральный исследовательский центр «Информатика и управление» РАН КИИ-2016 3–7 октября 2016 г .

Смоленск, Россия

ПЯТНАДЦАТАЯ

НАЦИОНАЛЬНАЯ КОНФЕРЕНЦИЯ

ПО ИСКУССТВЕННОМУ ИНТЕЛЛЕКТУ

С МЕЖДУНАРОДНЫМ УЧАСТИЕМ

Труды конференции Том 3 Смоленск УДК 004.8+004.89+004.82+004.032.26(045) ББК 32.813(2А/Я)я43

Организаторы конференции:

Российская ассоциация искусственного интеллекта ФГБУ Федеральный исследовательский центр «Информатика и управление» РАН ФГБУН Институт проблем управления им. В.А. Трапезникова РАН ФГБОУ ВО «Национальный исследовательский университет «МЭИ»

Администрация Смоленской области Филиал ФГБОУ ВО «Национальный исследовательский университет «МЭИ» в г. Смоленске Смоленское региональное объединение работодателей «Научно-промышленный союз»

Конференция проводится при поддержке Российского фонда фундаментальных исследований (проект № 16-07-20554) Пятнадцатая национальная конференция по искусственному интеллекту с международным участием КИИ-2016 (3–7 октября 2016 г., г. Смоленск, Россия). Труды конференции. В 3-х томах. Т 2.

– Смоленск:

Универсум, 2016. – 374 с .

ISBN 978-5-91412-316-8

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

Секция 9. «Моделирование рассуждений и неклассические логики», Секция 10 .

«Нечеткие модели и мягкие вычисления», Секция 11. «Прикладные интеллектуальные системы», Секция 12. «Программные продукты искусственного интеллекта», Воркшоп. «Поведение интеллектуальных систем» .

© Авторы ISBN 978-5-91412-316-8 © Российская ассоциация искусственного интеллекта, 2016

ПРЕДИСЛОВИЕ

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

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

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

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





Все эти сферы деятельности в той или иной степени отражены в трудах КИИ-2016 .

На конференцию было подано 186 докладов, прошедших рецензирование и последующий отбор Программным комитетом.

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

Секция 1. «Инженерия знаний и онтологии» – 16, Секция 2 .

«Интеллектуальные динамические и робототехнические системы – 7, Секция 3. «Интеллектуальные системы поддержки принятия решений и управления» – 8, Секция 4. «Интеллектуальный анализ данных» – 15, Секция 5. «Интеллектуальный анализ текстов и семантический WEB» – 17, Секция 6. «Классификация, распознавание и диагностика» – 11, Секция 7. «Когнитивные исследования» – 8, Секция 8. «Многоагентные и распределенные системы» – 8, Секция 9. «Моделирование рассуждений и неклассические логики» – 7, Секция 10. «Нечеткие модели и мягкие вычисления» – 13, Секция 11. «Прикладные интеллектуальные системы» – 7, Секция 12. «Программные продукты искусственного интеллекта» – 8 .

Кроме того, в рамках конференции состоится воркшоп на тему «Поведение интеллектуальных систем» (Intelligent System Behavior, ISB-2016). Доклады, представленные на воркшоп, также включены в настоящий сборник .

География участников настоящей пятнадцатой конференции достаточно обширна и охватывает 20 городов России: Москву, Новосибирск, Белгород, Воронеж, Ульяновск, Владивосток, Иркутск, Смоленск, Брянск, Тверь, СанктПетербург, Калугу, Киров, Казань, Томск, Таганрог, Апатиты, Красноярск, Калининград, Борок (Ярославской обл.) .

В работе КИИ-2016 участвуют и зарубежные ученые из Украины, Беларуси и США .

Г.С. Осипов ПРОГРАММНЫЙ КОМИТЕТ КИИ-2016 Васильев С.Н., академик РАН, ИПУ РАН, г. Москва (председатель) Осипов Г.С., д.ф.-м.н., проф., ФИЦ ИУ РАН, г. Москва (сопредседатель) Федулов А.С., д.т.н., проф., филиал НИУ МЭИ в г. Смоленске (зам. председателя) Аверкин А.Н., к.ф-м.н., доцент, ФИЦ ИУ РАН, г. Москва Вагин В.Н., д.т.н., проф., НИУ МЭИ, г. Москва Гаврилова Т.А., д.т.н., проф., СПбГУ, г. Санкт-Петербург Голенков В.В., д.т.н., проф., БГУИР, г. Минск Еремеев А.П., д.т.н., проф., НИУ МЭИ, г. Москва Карпов В.Э., к.т.н., доцент, НИЦ Курчатовский институт, г. Москва Кобринский Б.А., д.м.н., проф., ФИЦ ИУ РАН, г. Москва Кузнецов О.П., д.т.н., проф., ИПУ РАН, г. Москва Курейчик В.М., д.т.н., проф., ТТИ ЮФУ, г. Таганрог Лахути Д.Г., д.т.н., проф., РГГУ, г. Москва Михеенкова М.А., д.т.н., ФИЦ ИУ РАН, Москва Палюх Б.В., д.т.н., проф., ТвГТУ, г. Тверь Петровский А.Б., д.т.н., проф., ФИЦ ИУ РАН, г. Москва Плесневич Г.С., к.ф.-м.н., доцент, МЭИ, г. Москва Попков Ю.С., член-корр. РАН, ФИЦ ИУ РАН, г. Москва Поспелов Д.А., д.т.н., проф., ФИЦ ИУ РАН, г. Москва Ройзензон Г.В., к.т.н., ФИЦ ИУ РАН, г. Москва Рыбина Г.В., д.т.н., проф., НИЯУ МИФИ, г. Москва Стефанюк В.Л., д.т.н., проф., ИППИ РАН, г. Москва Тарасов В.Б., к.т.н., доцент, МГТУ, г. Москва Сулейманов Д .

Ш., академик АН РТ, ИПС АН РТ, г. Казань Тельнов Ю.Ф., д.э.н., проф., МЭСИ, г. Москва Тихомиров И.А., к.т.н., ФИЦ ИУ РАН, г. Москва Федунов Б.Е., д.т.н., проф., РосНИИ АС, г. Москва Финн В.К., д.т.н., проф., ФИЦ ИУ РАН, г. Москва Фоминых И.Б., д.т.н., проф., НИУ МЭИ, г. Москва Хорошевский В.Ф., д.т.н., ФИЦ ИУ РАН, г. Москва ОРГКОМИТЕТ КИИ-2016 Окунева О.В., заместитель Губернатора Смоленской области (председатель) Дли М.И., д.т.н., проф., филиал НИУ МЭИ в г. Смоленске (зам. председателя) Ананьева М.И., ФИЦ ИУ РАН, Москва Борисов В.В., д.т.н., проф., филиал НИУ МЭИ в г. Смоленске Карпов В.Э., к.т.н., доцент, НИЦ «Курчатовский институт», г. Москва Попов А.И., к.т.н., Научно-промышленный союз, г. Смоленск Тихомиров И.А., к.т.н. ФИЦ ИУ РАН, г. Москва

СЕКЦИЯ 9 МОДЕЛИРОВАНИЕ РАССУЖДЕНИЙ И

НЕКЛАССИЧЕСКИЕ ЛОГИКИ

УДК 004.853

ПОДСИСТЕМА АНАЛИЗА И ФОРМИРОВАНИЯ

СБОРНИКА WIKI-СТАТЕЙ НА ОСНОВЕ МЕТОДОВ

АНАЛОГИЙ И ПРЕЦЕДЕНТОВ1

–  –  –

Работа посвящена вопросам, связанным с разработкой программной системы, способной выполнять анализ информации, содержащийся в сети Интернет, и автоматически формировать сборник wiki-статей для электронных библиотек и баз знаний по различным предметным областям с использованием механизмов на основе аналогий и прецедентов .

Ключевые слова: технология wiki, семантический wiki, анализ Интернет-ресурсов, методы на основе аналогий и прецедентов Работа выполнена при финансовой поддержке проектов РФФИ № 14-01-00427, № 15-07-04574, № 16-51-00058 и проекта по государственному заданию № 2.737.2014/К .

Введение На сегодняшний день при рассмотрении вопросов, связанных с инженерией знаний и разработкой систем искусственного интеллекта, актуальной является проблема приобретения знаний из различных источников и, в частности, из гипертекстовых источников (например, Интернетресурсов, wiki-статей и др.) [Башмаков и др. 2005]. Наличие развитых средств приобретения и представления знаний необходимо для реализации современных интеллектуальных систем (ИС), ориентированных на решение широкого круга задач в различных предметных областях [Рассел и др. 2007]. Актуальность разработки методов и средств приобретения знаний из гипертекстовых источников объясняется бурным развитием Интернет-технологий и, в частности, технологии wiki, активно применяемой для создания электронных энциклопедий, библиотек (ЭБ), баз знаний (БЗ) и предметных онтологии [Гаврилова и др. 2000] .

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

Разрабатываемая программная подсистема способна выполнять анализ HTML-кода wiki-страниц и формирование подборки wiki-статей на основе определения сходства между анализируемыми статьями с использованием методов поиска решения по аналогии (ABR – Analogy-Based Reasoning) и прецедентам (CBR – Case-Based Reasoning), которые успешно применяются в различных областях человеческой деятельности (медицина, техника, юриспруденция и др.), в динамических ИС, в системах экспертного диагностирования, в ИС поддержки принятия решений, системах машинного обучения, при решении задач прогнозирования, обобщения накопленного опыта, поиска решения в малоизученных предметных областях и др. [Вагин и др. 2008] .

1. Технология wiki Wiki – открытая технология Интернет, основополагающий принцип которой заключается в том, что любой посетитель wiki-ресурса может самостоятельно изменять его структуру и содержимое с помощью инструментов, предоставляемых таким ресурсом .

Технология wiki характеризуется следующими основными признаками:

совместная работа и контроль версий;

язык wiki-разметки;

использование гипертекста .

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

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

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

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

Принято выделять следующие отличительные особенности семантических wiki-систем:

семантические аннотации (например, для указания типа связей ссылок между статьями);

контекстное представление данных (например, отображение схожих по тематике статей, контекстно-зависимые ссылки);

поддержка стандартов Semantic Web, поддержка форматов RDF, OWL, языка запросов SPARQL;

семантический поиск на основе запросов;

поддержка логического вывода .

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

3. Анализ и автоматическое формирование подборок wiki-статей Для получения (извлечения) необходимой человеку информации в Интернет требуется достаточно большое время. Затраты по времени не всегда зависят от скорости работы компьютеров и скорости передачи данных. Человеку требуется дополнительное время для анализа информации на предмет ее актуальности для него. Поэтому для уменьшения затрат на поиск информации в работе предлагается выполнять автоматическое извлечение информации в сети Интернет в виде wiki-статей и формирование подборки Интернет-статей (wiki-статей) для ЭБ и БЗ по определенной тематике, касающейся заданного пользователем понятия .

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

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

Каждая статья проходит процедуру индексирования, схема которой приведена на рис. 1 .

–  –  –

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

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

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

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

В данной реализации для определения сходства как для двух слов, так и для двух статей используется коэффициент Жаккара:

c Kj, abc где а – количество характеристик новой статьи, b – количество характеристик статьи, хранящейся в памяти приложения, с – количество общих характеристик для двух сравниваемых статей .

Сравнение двух статей включает следующие этапы:

1) проверка сходства URL, title и содержания статей;

2) определение сходства статей по ключевым словам;

3) определение сходства статей по ссылкам на другие статьи;

4) определение сходства статей по категориям;

5) определение сходства статей по структуре с использованием методов на основе аналогий и прецедентов [Алехин и др. 2014] .

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

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

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

Для определения степени сходства wiki-статей, представленных в структурированной виде, предлагается использовать метод аналогии на основе теории структурного отображения (SMT – Structure-Mapping Theory) [Варшавский и др. 2012] .

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

Процесс поиска решения на основе аналогий согласно SMT включает следующие основные этапы [Falkenhainer et al., 1989] .

Этап 1. Определение потенциальных аналогов .

Имея целевую ситуацию (цель), определить другую ситуацию (базу), которая является аналогичной или подобной целевой ситуации;

Этап 2. Отображение и вывод .

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

Этап 3.Оценка «качества» соответствия .

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

Предлагается осуществлять определение сходства двух wiki-статей в два этапа [Алехин и др.

2015]:

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

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

Цель первого этапа – определить возможные парные соответствия между двумя статьями и оценить их сходство .

На втором этапе для оценки близости статей используется метод ближайшего соседа, часто применяемый в прецедентных системах. Для каждого парного соответствия в выбранной метрике определяются расстояние dCQ между наборами количественных характеристик статей. Для определения значения степени сходства Sim(C,Q) необходимо найти максимальное расстояние dMAX в выбранной метрике, используя границы диапазонов параметров .

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

2013], которые могут быть выражены в процентах:

оценка на основе структурных представлений:

Sstruct = ki=1LSi/SESMAX, где k – количество соответствий, LSi – оценка правдоподобия для i соответствия, SESMAX – оценка для случая, когда каждый элемент в базовой области имеет родительское отношение и в качестве базовой области выбирается целевая;

оценка по методу ближайшего соседа: Sim(C,Q) = 1–dCQ/dMAX, где dCQ –расстояние между текущими статьями, dMAX – максимальное расстояние в выбранной метрике .

На основе полученных оценок сходства wiki-статей может приниматься решение о добавлении статьи в подборку .

5. Реализация подсистемы анализа и формирования подборки wiki-статей На рис. 2 отображена архитектура разработанной программной подсистемы анализа и формирования подборки wiki-статей .

Рис. 2. Архитектура подсистемы анализа и формирования подборки wiki-статей

Блок анализа содержит в себе несколько модулей: модуль анализа HTML-кода, который извлекает метаинформацию о статье; модуль анализа основного текста, который обеспечивает поиск и выделение ключевых слов; в блоке сопоставления двух статей реализована возможность сравнения статей по названию, содержанию, ключевым словам, ссылкам, категориям и с использованием методов на основе аналогий и прецедентов. Блок редактирования подборки позволяет пользователю добавлять и исключать wiki-статьи из подборки вручную .

Программная реализация подсистемы выполнена в среде Microsoft Visual Studio 2013 на языке C# .

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

Рис. 3. Результат создания подборки статей для понятия «Машинное обучение»

Заключение Описана программная подсистема для анализа и автоматического формирования подборок wiki-статей, способная уменьшить затраты при разработке ЭБ и БЗ на сбор и анализ информации из сети Интернет в виде wiki-статей по заданной пользователем тематике. Для определения сходства wiki-статей предложено использовать методы на основе аналогий и прецедентов. Разработана архитектура и выполнена программная реализация подсистемы в среде Microsoft Visual Studio 2013 на языке C#. Рассмотрен пример формирования подборки wiki-статей по тематике «Машинное обучение» .

Список литературы [Башмаков и др. 2005] Башмаков А.И., Башмаков И.А. Интеллектуальные информационные технологии: учеб. пособие. – М.: МГТУ им. Н.Э. Баумана, 2005 .

[Рассел и др. 2007] Рассел C., Норвиг П. Искусственный интеллект. Современный подход. 2-е изд. – М.: Вильямс, 2007 .

[Гаврилова и др. 2000] Гаврилова Т.А., Хорошевский В.Ф. Базы знаний интеллектуальных систем. – СПб.: Питер, 2000. – 384 с .

[Вагин и др. 2008] Вагин В.Н., Головина Е.Ю., Загорянская А.А., Фомина М.В .

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

// Под ред. В.Н. Вагина, Д.А. Поспелова. – М.: Физматлит, 2008 .

[Алехин и др. 2014] Алехин Р.В., Варшавский П.Р. Реализация прецедентного модуля для интеллектуальной системы поддержки принятия решений // Труды XIV Национальной конференции по искусственному интеллекту с международным участием (КИИ-2014). Т.2. – Казань: Изд-во РИЦ «Школа», 2014 .

[Варшавский и др. 2012] Варшавский П.Р., Алехин Р.В., Зо Лин Кхаинг. Применение онтологического подхода для реализации поиска решения на основе прецедентов в интеллектуальных системах поддержки принятия решений // Труды XIII Национальной конференции по искусственному интеллекту с международным участием (КИИ-2012). Т. 3. – Белгород: Изд-во БГТУ, 2012 .

[Falkenhainer et al. 1989] Falkenhainer B., Forbus K., Gentner D. The StructureMapping Engine: Algorithm and examples // Artificial Intelligence. 1989. 41 .

[Алехин и др. 2015] Алехин Р.В., Варшавский П.Р. Применение прецедентного модуля для решения задач экспертного диагностирования // Интегрированные модели и мягкие вычисления в искусственном интеллекте. Сборник научных трудов VIII-й Международной научно-практической конференции (Коломна, 18-20 мая 2015 г.). В 2-х томах. Т. 1. – М.: Физматлит, 2015 .

УДК 007.5

УПРАВЛЕНИЕ ПРОЦЕССОМ РАССУЖДЕНИЙ

ПРИ РЕШЕНИИ ЗАДАЧ В ЖЁСТКОМ

РЕАЛЬНОМ ВРЕМЕНИ 1

–  –  –

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

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

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

Работа выполнена при финансовой поддержке РФФИ (проекты №№ 14-07-00913, 14-07-00373, 15-07-02320, 15-07-08020) .

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

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

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

оценивать имеющийся у него временной ресурс;

контролировать промежуточные результаты и время, когда они уже должны быть получены;

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

Наличие указанных возможностей является необходимым условием, при котором управление процессом рассуждения имеет шанс парировать те угрозы, которые несут в себе аномалии, возникающие при решении задач в условиях жстких временных ограничений. Ниже будет рассмотрены вопросы, относящиеся к реализации указанных возможностей в контексте активной логики [Elgot-Drapkin, 1998], [Purang et al., 1999], [Purang et al., 2005], концептуальной системы, включающей в себя ряд формализмов, предназначенных для моделирования метарассуждений, которые ориентированы на специфику решения задач в режиме жсткого реального времени .

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

Нереалистичность этого допущения приводит к т.н. проблеме логического всеведения, хорошо известной в эпистемической логике. Соответственно, агенты, к которым эта проблема относится, называются всеведущими или идеальными [Бежанишвили, 2007]. Ясно, что идеальному агенту нет нужды, проводя рассуждения, учитывать имеющийся у него временной ресурс, поскольку все результаты он получает мгновенно. Однако, если допущение о всеведении агента не может быть принято, проблему, связанную с логическим всеведением, необходимо как-то решать .

Решения этой проблемы предлагались как в рамках модального подхода (см. например, [Fagin et al., 1988]), так и вне его [Elgot-Drapkin, 1998] .

Как было показано в [Виньков, 2011], те решения, которые относятся к модальному подходу, имеют общий недостаток, принципиально не позволяющий установить, способен ли (или не способен) агент i вывести формулу F, не выходя за временную границу t. Отметим, что именно такого рода результаты чрезвычайно важны для случая, когда временной ресурс агента i жстко ограничен. Вне рамок модального подхода данный недостаток преодолевается в системах, отвечающих концепции активной логики (или подобных им [Alechina et al., 2004]), для которых характерно, что рассуждения агента трактуются не как последовательность формул (утверждений), существующая вне времени, а как процесс, имеющий некоторую длительность .

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

В отношении этого предиката действует следующее правило вывода:

t: now(t). (2.1) t + 1: now(t + 1) Причем, формула now(t) не наследуется в момент времени (t + 1) на шаге вывода, как это происходит с «обычными» формулами благодаря правилу вывода t:. (2.2)

t + 1:

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

t: resource(t1), (2.3) t + 1: resource(t1 – 1) где t1 – ресурс времени, имеющийся у агента в момент времени t .

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

Это иллюстрирует правило вывода, являющееся «активным» аналогом modus ponens:

t:,. (2.4)

t + 1:

Данное правило «говорит» о том, что если в момент времени t агентом выведены в результате рассуждений или получены из наблюдения за внешней средой формулы и, то в момент времени t + 1 будет выведена формула. Более общая трактовка времени и способ его измерения были предложены в [Виньков, 2008]. При этом несправедливо допущение, что длительность дедуктивных циклов всегда одинакова. Моменты времени завершения шагов вывода образуют последовательность («часы»), которая является подпоследовательностью последовательности натуральных чисел, например, clock = 1, 3, 5, 7, 10, 14, …. В этом случае правило вывода, например, (2.3) примет вид t: resource(t1), (2.5) next t: resource (t1 – next t + t) где next t указывает следующий после t момент времени на «часах» .

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

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

t:, (3.1) next t; K(t, ) t:, sub(, ), [], (3.2) next t; K(t, ) где – любая формула, не известная агенту в момент времени t, но являющаяся подформулой некоторой известной ему формулы, т.е. осознаваемая агентом; sub(, ) – двухместный метапредикат, выражающий отношение «быть подформулой»; [] – нотация, означающая, что формула отсутствует в текущих знаниях агента в момент времени t; K(, ) – двухместный метапредикат (а не модальный оператор!), выражающий тот факт, что агенту известна некоторая формула в некоторый момент времени .

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

В ситуациях, когда временной ресурс жстко ограничен, возникновение противоречий вполне естественно и при этом чрезвычайно важно, чтобы столкнувшийся с противоречивой информацией агент не терял от этого работоспособность [Cox et al., 2007], а наоборот, мог использовать е с пользой при контроле за ходом познавательного процесса .

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

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

t:,, (3.3) next t; contra(t,, ) где contra (,, ) – специальный трхместный метапредикат, принимающий значение «истина», если в момент времени t текущие знания агента содержат формулы и .

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

Пример .

0: … now(0), now(1) K (2, A ) … 1: … now(1), now(1) K (2, A ), … 2: … now(2), now(1) K (2, A ), K(2, A ) … 3: … now(3), now(1) K (2, A ), K(2, A), K(2, A ) … 4: … now(4), now(1) K (2, A ), K(2, A), K (2, A ), contra (3, K(2, A), K(2, A)) … Здесь ожидание агента, что некоторое событие А (например, осознание им некоторой формулы), наступит в момент времени 2, вступило в противоречие с действительностью, что было обнаружено в момент времени 4 .

Этого не произошло, если бы в момент времени 1 была выведена формула. Тогда в момент времени 2 не сработало бы правило вывода и прямого противоречия не возникло .

Следует отметить, однако, что до настоящего времени отсутствует удовлетворительное определение декларативной семантики систем активной логики, в которых используется обнаружение и устранение прямых противоречий [Anderson et al., 2005], [Priest et al., 2004] .

4. Моделирование эмоций в контексте коррекции познавательного процесса Анализ выявленных аномалий в условиях жстких временных ограничений перед лицом возможных катастрофических последствий их несоблюдения не предполагает исчерпывающей полноты. Главная задача, решаемая в ходе такого анализа, состоит в оценке степени угрозы пересечения дедлайна, таящейся в выявленной аномалии, а также размеров имеющегося временного ресурса, который может быть использован для того, чтобы этой угрозы избежать. Ясно, что во многих случаях такая оценка может быть лишь весьма приблизительной. Особо сложна для агента ситуация, когда можно предполагать, что дедлайн весьма близок, но точно неизвестно, насколько. У людей и животных в таких случаях, когда уже думать некогда, но надо, тем не менее, что-то делать, весьма важную роль начинают играть эмоции. Как известно [Анохин, 1964], эмоции у живых организмах выполняют функцию локального критерия эффективности управления, помогая организму понять, что хорошо и что плохо в данных конкретных условиях. По П.К. Анохину эмоция играет роль «пеленга», который подсказывает организму, движется ли он к цели или от не. В первом случае эмоция положительна («радость»), во втором – отрицательна («страдание») .

Заключение Процесс реализации рассмотренных выше принципов управления познавательным процессом агента в режиме жсткого реального времени пока нельзя считать изученным в полном объме .

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

Список литературы [Беженишвили, 2007] Беженишвили М.Н. Логика модальностей знания и мнения/Предисл. В.К. Финна. – М.: КомКнига, 2007 .

[Виньков, 2008] Виньков М.М. Время, как внешняя сущность при моделировании рассуждений рационального агента с ограниченными ресурсами //Труды XI Национальной конференции по искусственному интеллекту с международным участием (КИИ-2008). – М.: Физматлит, 2008 .

[Виньков, 2011] Виньков М.М. Моделирование эмоций интеллектуального агента с ограниченным временным ресурсом в непредвиденных ситуациях // Сборник научных трудов VI Международ. научно-технич. конф. «Интегрированные модели и мягкие вычисления в искусственном интеллекте». – М.: Физматлит, 2011 .

[Попов, 1987]Попов Э.В. Экспертные системы: Решение неформализованных задач в диалоге с ЭВМ. – М.: Наука. Гл. ред. физ.-мат. лит., 1987 .

[Alechina et al., 2004] Alechina N., Logan B., Whitsey M. A complete and decidable logic for resource-bounded agents // In Proc. Third International Joint Conference on Autonomous Agents and Multi-Agent Systems (AAMAS 2004). 2004 .

[Anderson et al., 2004] Anderson M.L., Lee B.. Empirical results for the use of metalanguage in dialog management // Proceedings of the 26th Annual Conference of the Cognitive Science Society. 2004 .

[Anderson et al., 2005] Anderson M.L., Gomaa W., Grant J., Perlis D. On the reasoning of real-world agents: Toward a semantics for active logic // In Proc. of the 7th Annual Symposium on the Logical Formalization of Commonsense Reasoning, Corfu, Greece, 2005 .

[Cox et al., 2007] Cox M.T., Raja A.. Metareasoning: Manifesto // In BBN Technical Memo TM-2028, 2007 [Elgot-Drapkin, 1998] Elgot-Drapkin J. Step Logic: Reasoning situated in time. PhD thesis. Department of computer science, University of Maryland, Colledge-Park, Maryland, 1988 .

[Fagin et al., 1988] Fagin R., Halpern J.Y. Belief, awareness and limited reasoning // Artificial Intelligence 1988. 34 .

[Priest et al., 2004] Priest G., Tanaka K. Paraconsistent logic. – In Edward N. Zalta, editor. – The Stanford Encyclopedia of Philosophy. Winter, 2004 .

[Purang et al., 1999] Purang K., Purushothaman D., Traum D., Andersen C., Traum D., Perlis D. Practical Reasoning and Plan Executing with Active Logic // Proceedings of the IJCAI'99, Workshop on Practical Reasoning and Rationality. 1999 .

[Purang et al., 2005] Perlis D., Purang K., Purushothaman D., Andersen C., Traum D .

Modeling time and meta-reasoning in dialog via active logic //Working Notes of AAAI Fall Symposium on Psychological Models of Communication. 2005 .

УДК 004.89, 004.832.2

ПРИМЕНЕНИЕ МЕТОДОВ РАСПРОСТРАНЕНИЯ

ОГРАНИЧЕНИЙ В СЛАБО ФОРМАЛИЗОВАННЫХ

ПРЕДМЕТНЫХ ОБЛАСТЯХ1

–  –  –

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

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

В теории удовлетворения ограничений для ограничений над конечными доменами (областями определения переменных) разработаны специализированные алгоритмы [Bartak, 1999] в частности, алгоритмы предварительной проверки (forward checking), достижения вершинной и дуговой Работа выполнена при финансовой поддержке РФФИ (проекты №№ 14-07-00205a, 16-07-00273a, 16-07-00377a, 16-07-00313a, 16-07-00562a) .

совместностей (node consistency, arc consistency), которые ускоряют поиск решения задачи удовлетворения ограничений (constraint satisfaction problem – CSP). Однако, как и в случае бесконечных доменов, эти ограничения носят характер числовых зависимостей и задаются с помощью базового набора арифметических операций, бинарных отношений равно/неравно, больше/меньше и т.п., для которых разработаны специализированные процедуры-пропагаторы. Другими словами, при использовании той или иной системы программирования в ограничениях предполагается, что все области определения переменных задачи CSP являются подмножествами одного и того же множества чисел .

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

При работе со слабо формализованными предметными областями требуется совместно обрабатывать числовые и нечисловые ограничения. По мнению автора, подобную совместную обработку целесообразно реализовывать в рамках парадигмы программирования в ограничениях. Предлагается качественные зависимости представлять в виде матриц ограничений (С- и D-систем) [Кулик и др., 2010], а вывод на С- и D-системах выполнять с помощью авторских методов распространения нечисловых ограничений [Зуенко, 2014], [Зуенко, 2015] .

Ниже в кратком изложении приводятся базовые принципы решения задач CSP на основе матричного представления ограничений .

1. Матричное представление ограничений Согласно [Russel et al., 2003] задача удовлетворения ограничений определена множеством переменных x1, x2,..., xn и множеством ограничений Cl, C2,..., Cm. Каждая переменная xi имеет непустую область определения Di (домен). Каждое ограничение Ci включает некоторое подмножество переменных и задает допустимые комбинации значений для этого подмножества. Состояние задачи описывается как присваивание значений некоторым (частичное присваивание) или всем переменным (полное присваивание): {xi=vi, xj=vj,...}. Решением задачи CSP является полное присваивание, которое удовлетворяет всем ограничениям .

Как и в статье [Кулик и др., 2010], здесь для представления данных и знаний используются два типа матрицеподобных структур: C-системы и D-системы. Особенностью настоящих исследований является то, что эти структуры предлагается рассматривать как ограничения над конечными доменами, а рассуждения на данных структурах реализовывать в форме процедур удовлетворения ограничений .

С помощью С-систем удобно моделировать дизъюнктивные нормальные формы (ДНФ) конечных предикатов. Продемонстрируем это на примере. Пусть задан конечный предикат:

(x, y, z) = (x=a,b) (y=a,c) (z=d) .

Для простоты все переменные определены на одном и том же множестве {a, b, c, d}. Здесь и далее будем использовать запись вида (x = a, b) для обозначения выражения (x = a) (x = b).

Учитывая, что область истинности одноместного предиката (x = a, b) есть {a, b}, то область истинности предиката (x, y, z) может быть представлена в виде следующей C-системы:

–  –  –

Атрибуты X, Y, Z С-системы R[XYZ] соответствуют переменными x, y, z формулы (x, y, z). Заметим, что * – сокращенное обозначение всего диапазона возможных значений (домена) атрибута. С-систему R[XYZ] можно преобразовать в многоместное отношение следующим образом:({a, b}{a, c}{a, b,c, d})({a, b, c, d}{a, b, c, d}{d}) .

С помощью D-систем моделируются конъюнктивные нормальные формы (КНФ) конечных предикатов. D-система записывается как матрица компонент-множеств, которые заключены в перевернутые скобки .

D-системы позволяют легко вычислять дополнение C-систем: берется дополнение для каждой компоненты-множества .

Например, предикат (( x = a, b) (y = a, c)) ( z = d), что, c учетом конечных областей определения переменных, равносильно ((x = c, d) (y = b, d)) (z =a, b, c).

Предикат может быть выражен как D-система R [XYZ]:

{c, d } {b, d } R [XYZ] = {a, b, c} .

Пустая компонента – это фиктивная компонента, не содержащая ни одного значения .

Задачу CSP, обычно, удобно представлять в виде D-систем, а ее решения искать в виде С-систем .

C помощью структур алгебры кортежей (С- и D-систем) можно моделировать и анализировать не только классические ограничения с конечными доменами, но и ограничения с недоопределенными параметрами, поскольку компоненты кортежей С- и D-систем содержат в качестве значений множества, а не отдельные элементы. Под недоопределенностью в настоящей работе понимается особый вид неопределенности [Нариньяни и др., 1997] .

В работах [Зуенко, 2014], [Зуенко, 2015] приводятся конкретные методы решения задач CSP, основанные на матричном представлении ограничений с конечными доменами. В силу требований к объему доклада, приведем здесь лишь утверждения, используемые в дальнейшем в примерах .

Для простоты будем считать, что ограничения CSP могут быть представлены в виде единственной D-системы. В реальных же задачах – это совокупность С- и D- систем, числовых ограничений, а также глобальных ограничений [Ruttkay, 1998] .

Утверждение 1 (У1). Если хотя бы одна строка D-системы пуста (содержит все пустые компоненты), то D-система пуста (соответствующая система ограничений несовместна, задача CSP не имеет решения) .

Утверждение 2 (У2). Если все компоненты некоторого атрибута пусты, то данный атрибут можно удалить из D-системы (удаляются все компоненты, стоящие в соответствующем столбце) .

Утверждение 3 (У3). Если в D-системе есть строка (кортеж), содержащая лишь одну непустую компоненту, то все значения, не входящие в эту компоненту, удаляются из соответствующего домена .

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

Утверждение 5 (У5). Если компонента атрибута D-системы содержит значение, не принадлежащее соответствующему домену, то это значение удаляется из компоненты .

Утверждения 1–5 позволяют исключать «лишние» значения из отдельных компонент, из доменов переменных (атрибутов), элиминировать строки и/или столбцы матриц ограничений, «сужая» область поиска и ускоряя получение решений задачи CSP. На основе перечисленных утверждений были модифицированы известные алгоритмы достижения дуговой и вершинной совместностей для случая нечисловых ограничений [Зуенко, 2015]. Упомянутые авторские алгоритмы выполняются за полиномиальное время. Они останавливаются, достигнув некоторой неподвижной точки, при этом решение задачи CSP может быть еще не получено. Поэтому подобные алгоритмы обычно применяются совместно с алгоритмами поиска с возвратами, обеспечивающими систематическое исследование пространства поиска [Зуенко, 2014] .

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

–  –  –

Строка №3 содержит лишь одну непустую компоненту, а, значит, домен атрибута W (целевое данное) может быть сужен до {b}. Следовательно, из компонент атрибута W вычеркиваем значения, не принадлежащие {b}. Откуда несложно заключить, что для Z домен сузится до {a} .

Окончательное решение: X – {b}, Y – {a, b}, Z – {a}, W – {b} .

Домены параметров существенно сузились: X, Z, W стали полностью определенными, лишь значение Y осталось полностью неопределенным .

3. Интеллектуальные динамические системы Динамическая система, основанная на правилах – это четверка [Осипов, 2011]: D=X, T,,, где X – множество фактов, Т – дискретное упорядоченное множество моментов времени, : 2X 2X – функция замыкания, : 2X T 2X – функция переходов. Причем, функции замыкания и переходов реализуются правилами замыкания ПСL и переходов ПТR, соответственно .

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

Другими словами, в докладе предлагается:

1. Задачу пополнения описания состояния динамической системы рассматривать как CSP. Правила замыкания рассматривать как ограничения и записывать в виде совокупности С- и D-систем .

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

4. Структурный синтез на элементах с ограниченной сочетаемостью Рассмотрим задачу структурного синтеза в следующей формулировке .

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

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

Обычно такого рода задачи решаются с привлечением алгоритмов на графах, например алгоритмов нахождения полных подграфов. Однако задачу структурного синтеза можно решать и методами удовлетворения ограничений. Далее показано как типовые бинарные запреты представить в виде строк D-системы. Пусть X и Y переменные c областями определения D(X), D(Y), соответственно .

1. Принуждение .

Выбор элемента a D(X) влечет выбор элемента b D(Y) .

На языке логики:

(X = a) (Y = b) или (X = a) (Y = b) .

С помощью матриц ограничений:

R[XY] = ] D(X)\{a}, {b} [ .

2. Бинарный запрет на сочетание .

Элементы a D(X) и b D(Y) не могут входить в одно решение .

На языке логики:

((X = a) (Y = b)) или (X = a) (Y = b) .

С помощью матриц ограничений:

R[XY] = ]D(X)\{a}, D(Y)\{b}[ .

3. Двойное принуждение. a D(X) и b D(Y) входят в решение одновременно .

На языке логики:

((X = a) (Y = b)) .

С помощью матриц ограничений:

R[XY] =[{a}, {b}] .

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

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

Список литературы [Божко и др., 2004] Божко А.Н. Структурный синтез на элементах с ограниченно сочетаемостью // Инженерное образование.2004. №5 .

[Зуенко, 2014] Зуенко A.A. Вывод на ограничениях с применением матричного представления конечных предикатов // Искусственный интеллект и принятие решений. 2014. 3 .

[Зуенко, 2015] Зуенко А.А. Совместное применение алгоритмов фильтрации и распространения ограничений на основе матриц ограничений // Шестая Междунар. конф. «Системный анализ и информационные технологии» САИТ-2015 (Россия, Калининградская обл., г. Светлогорск, 15-20 июня 2015): Тр. конф. в 2-х т. – Т.1., 2015 .

[Кулик и др., 2010] Кулик Б.А., Зуенко А.А., Фридман А.Я. Алгебраический подход к интеллектуальной обработке данных и знаний – СПб.: Изд-во Политехнического ун-та, 2010 .

[Нариньяни и др., 1997] Нариньяни А.С. Недоопределенное календарное планирование: новые возможности // Информационные технологии. 1997. № 1 .

[Осипов, 2011] Осипов, Г.С. Методы искусственного интеллекта. – М.:

Физматлит, 2011 .

[Bartak, 1999] Bartak R. Constraint Programming: In Pursuit of the Holy Grail // Proceedings of the Week of Doctoral Students (WDS99),Part IV. – Prague: MatFyzPress, 1999 .

[Russel et al., 2003] Russel S. and Norvig P. Artificial Intelligence: A Modern Approach. Second edition. – Prentice Hall, 2003 .

[Ruttkay, 1998] Ruttkay Z. Constraint satisfaction a survey // CWI Quarterly. 1998. V.1 .

УДК 004.8

–  –  –

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

Ключевые слова: метод Мамдани, нечеткая логика, нечеткий логический вывод, нечеткая степень истинности Введение Для нечтких входов лучше всего известны и наиболее часто применяются нечткие системы подхода Мамдани, в которых используется логический вывод, основанный на операциях max-min, либо max-product .

Операторы min (взятие минимума) и product (арифметическое произведение) являются t-нормами [Alsina et al., 2006] и соответствуют правилам вывода Мамдани [Mamdani, 1974] и Ларсена [Larsen, 1980]. Но при других t-нормах, необходимость в изменении вида которых возникает при настройке нечтких систем, логический вывод не может быть реализован с полиномиальной вычислительной сложностью, как при классическом подходе [Zadeh, 1973]. В данной работе развивается подход Мамдани с вычислительной сложностью, равной полиномиальной. В первом разделе рассматривается вывод для одного правила «Если… то…», во втором и третьем — для блока правил с использованием методов дефаззификации по среднему центру и центру тяжести соответственно .

Работа выполнена при финансовой поддержке РФФИ (грант № 14-07-00154а) .

1. Нечткий вывод для системы с несколькими входами

Нечткий выход Bk для системы с n нечткими входами с использованием нечткой степени истинности, следуя [Куценко и др., 2015], [Куценко и др., 2008], записывается следующим образом:

–  –  –

щение соотношения [Yager, 1983], которое, согласно определению, является мерой возможности Dk при условии истинности C [Дюбуа и др., 1990] .

Рассмотрим вывод, основанный на правилах «Если… то…», который относится к так называемым FITA-подходам (First Inference, Then Aggregate), т.е. когда сначала производится вывод по каждому правилу, а затем выполняется агрегация результатов.

В качестве примера используем tнорму Лукасевича [Alsina et al., 2006]:

T Dk |C Bk ( y ) max 0, Dk |C Bk ( y ) 1. (1.4) Уже применение этой t-нормы, следуя классическому алгоритму вывода Мамдани, не дат возможности реализовать его с полиномиальной вычислительной сложностью. FITA-нечткий процесс на основе (1.4) показан на рис. 1 .

На рис. 1 последовательно изображены три нечткие множества Bk, k 1, 3, с гауссоподобными функциями принадлежности. Считаем, что эти нечткие множества нормальные, т. е. значения Bk(y') = 1. Каждое из нечтких множеств Bk получено по отдельному правилу в соответствии с формулой (1.4) из нечткого множества Bk путм сдвига его вниз .

В нижней части рис. 1 изображена функция принадлежности, полученная с помощью объединения нечтких множеств Bk, k 1, 3, с использованием операции max. Если сравнить формы нечтких множеств Bk, полученных на основе t-нормы Лукасевича, с нечткими множествами, выведенными в системах Мамдани и Ларсена, то в первом случае функции принадлежности Bk «обрезаются», а во втором — «масштабируются»

[Круглов и др., 2001] .

Рис. 1. Нечткий вывод, основанный на t-норме Лукасевича

–  –  –

в котором x1,, xn – чткие скалярные входные значения, подаваемые на соответствующие входы системы; T – t-норма, выражающая конъюнкцию в антецеденте k-го правила. Тогда

–  –  –

Рис. 2. Сетевая структура нечткой системы, Рис. 3. Сетевая структура нечткой системы, описываемой выражением (2.5) описываемой выражениями (3.3) и (3.5) Если предположить, что B j ( yk ) 0 для j, k 1, N и j k, (3.6) то в этом случае соотношение (3.3) примет вид выражения (2.5), т.е. сетевая архитектура, представленная на рис. 3, сводится к архитектуре, изображнной на рис. 2. Заметим, что B j ( yk ) 0 для j, k 1, N и j k, если консеквенты правил являются одноточечными множествами [Круглов и др., 2001] .

Если для нечтких множеств Bk, k 1, N, выполняется условие (3.6), то метод дефаззификации по среднему центру приводит к тому же результату (при тех же нечтких выходных множествах), что и при использовании метода дефаззификации по центру тяжести, определяемому соотношением (3.1) .

Заключение Применение вывода на основе нечткой степени истинности дат возможность обобщить подход Мамдани на различные t-нормы (включая параметрические) при нечтких входах .

Обобщение меры возможности [Дюбуа и др., 1990] при использовании дефаззификации по среднему центру приводит вывод к взвешенной сумме центров функций принадлежности консеквентов блока правил .

На рис. 3 изображена сетевая структура нечткой системы, соответствующая методу дефаззификации по центру тяжести. Она представляет собой более общий случай и содержит больше элементов, чем структура нечткой системы, представленной на рис. 2. В частности, при выполнении условия (3.6) происходит преобразование е к структуре, соответствующей методу дефаззификации по среднему центру. Полученные соотношения вывода нечтких систем (2.5) и (3.3) с учтом (3.5) представляет собой выражения, имеющие полиномиальную вычислительную сложность .

Список литературы [Дюбуа и др., 1990] Дюбуа Д., Прад А. Теория возможностей. Приложение к представлению знаний в информатике. – М.: Радио и связь, 1990 .

[Круглов и др., 2001] Круглов В.В., Дли М.И., Голунов Р.Ю. Нечеткая логика и искусственные нейронные сети. – М.: Физматлит, 2001 .

[Куценко и др., 2005] Куценко Д.А., Синюк В.Г. Методы вывода для систем со многими нечткими входами // Известия РАН. Теория и системы управления .

2015. № 3 .

[Куценко и др., 2008] Куценко Д.А., Синюк В.Г. Косвенный метод нечеткого вывода для продукционных систем сомногими входами // Программные продукты и системы. 2008. № 1 .

[Пегат, 2009] Пегат А. Нечеткое моделирование и управление. – М.: БИНОМ, Лаборатория знаний, 2009 .

[Рутковский, 2010] Рутковский Л. Методы и технологии искусственного интеллекта. – М.: Горячая линия – Телеком, 2010 .

[Alsina et al., 2006] Alsina C., Frank M.J., Schweizer B. Associative Functions: Triangular Norms and Copulas. – Singapore: World Scientific, 2006 .

[Cordn et al., 2004] Cordn O., Herrera F., Mrquez F.A. et al. A Study on the Evolutionary Adaptive Defuzzification Methods in Fuzzy Modeling // Intern. J. Hybrid Intelligent Systems. 2004. V. 1. № 1 .

[Larsen, 1980] Larsen P.M. Industrial applications of fuzzy logic control // International Journal of Man-Machine Studies. 1980. V. 12. № 1 .

[Mamdani, 1974] Mamdani E.H. Applications of Fuzzy Algorithm for Control a Simple Dynamic Plant // Proc. IEEE. 1974. V. 121. № 12 .

[Yager, 1983] Yager R.R. Some relationships between possibility, truth and certainty // Fuzzy Sets and Systems. 1983. 11 .

[Zadeh, 1973] Zadeh L.A. Outline of a New Approach to the Analysis of Complex Systems and Decision Processes // IEEE Transactions on Systems, Man and Cybernetics. 1973. V. SMC-3. № 1 .

[Zadeh, 1978] Zadeh L.A. PRUF – A Meaning Representation Language for Natural Language // Intern. J. Man-Machine Studies. 1978. V. 10 .

УДК 004.832.32

–  –  –

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

Ключевые слова: системы логического типа, обобщенное правило modus ponens, max-min композиция .

Введение В последнее время нечеткие множества и нечеткая логика, представленные Лотфи Заде [Zadeh, 1965], используются в широком спектре проблемно-ориентированных областей, таких как управление технологическими процессами, обработка изображений, распознавание и классификация, принятие решений и многих других. Разработано множество практических приложений, включая управление в стиральных машинах, фокусировка в видео и фотокамерах, настройка цветов в телевизоре, управление переключением автомобильной трансмиссии и т.д. [Hirota, 1993]. В то же время активно развиваются технологии на основе нейронных сетей. Нечеткие системы, нейронные сети, эволюционные алгоритмы образуют Работа выполнена при финансовой поддержке РФФИ (проект № 16-07-00487) .

объединение методов, которое называется «мягкие вычисления» и используются совместно [Aliev, 2001] .

Наиболее популярные подходы в реализации нейро-нечетких структур сводятся к следующим:

метод Такаги Сугено;

метод Мамдани;

системы логического типа .

Метод Мамдани, наиболее часто применяемый в инженерных приложениях, не лишен недостатков, как отмечается в работе [Yager, 1992]. Для их преодоления предлагается использовать системы логического типа .

Рассмотрим один подход к нечеткому выводу с полиномиальной вычислительной сложностью, основанный на композиционном правиле вывода для логических систем MISO структуры [Rutkowski, 2003] .

1. Сложность нечеткой продукции с n входами

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

Если 1 есть A1 и 2 есть A2 и … и n есть An, то есть B, где: Аi – терм входной i –ой лингвистической переменной, которая формализуется нечеткой переменной, Ai, Xi, i ; Xi – область определения A xi нечеткой переменной, Ai, xi X i нечеткое множество описыi <

–  –  –

3. Вычисление выхода для блока правил Блок правил представляет собой совокупность импликаций относительно термов выходной лингвистической переменной B и представляется в виде R : Если A11 * A12 *...* A1n то B1,

–  –  –

Заключение В работе предложен подход к нечеткому выводу для нечетких систем логического типа на основе модифицированного композиционного правила вывода. Входные данные в общем случае могут быть как четкими значениями, так и представлять собой нечеткие множества. Полиномиальная вычислительная сложность предложенного механизма вывода позволяет эффективно использовать его для решения задач моделирования, диагностики, прогнозирования в системах со многими входами. Данный подход был использован при разработке нейро-нечеткой системы для распознавания нештатных режимов работы вращающейся цементной печи обжига клинкера [Синюк и др., 2014]. В рамках проекта была разработана нейронечеткая сеть на основе предложенного модифицированного композиционного правила вывода. Выполнена настройка функций принадлежности генетическим алгоритмом [Рутковская и др., 2006]. А также создано средство для разработки программ на языке нечеткого управления (FCL), которое представляет собой транслятор настроенной и обученной сети в текст на стандартизованном языке FCL, а также позволяет выполнять обратное преобразование [Синюк и др., 2011]. Разработано соответствующее программное обеспечение, позволяющее решать задачи нечеткого моделирования в различных проблемно-ориентированных областях .

Список литературы [Aliev et al., 1982] Aliev R.A., Krivosheev V.P., Liberzon M.I. Optimal Decision Coordination in Hierarchical Systems // News of Academy of Sciences of USSR, Tech .

Cybernetics. 1982. No. 2 .

[Aliev, 2001] Aliev R.A., Aliev R.R. Soft Computing and its Applications. – World Scientific Publishing, Singapore-New Jersey-London-Hong Kong, 2001 .

[Hirota, 1993] Hirota K.. Industrial Applications of Fuzzy Technology. – Springer Verlag, Tokyo, Berlin, Heidelberg, New York, 1993 .

[Rutkowski, 2003] Rutkowski L., Cpaku K. Flexible Neuro-Fuzzy Systems // IEEE Trans. Neural Networks. 2003. Vol. 14, Iss. 3 .

[Yager, 1992] Yager R.R. A general approach to rule aggregation in fuzzy logic control // Appl. Intelligence. 1992. Vol. 2 .

[Zadeh, 1965] Zadeh L.A. // Fuzzy sets, Information and Control. 1965. Vol. 8. No. 3 .

[Zadeh, 1975] Zadeh L.A. The concept of a linguistic variable and its application to approximate reasoning // Information Science.1975. Part I, vol. 8; Part II, vol. 8;

Part III, vol. 9 .

[Рутковская и др., 2006] Рутковская Д., Пилиньский М., Рутковский Л. Нейронные сети, генетические алгоритмы и нечеткие системы – М.: Горячая линия – Телеком, 2006 .

[Синюк и др., 2011] Синюк В.Г., Поляков В.М., Панченко М.В. Программное обеспечение для нечеткого языка моделирования с использованием языка FCL // Вестник РГУПС. 2011. №3 .

[Синюк и др., 2014] Синюк В.Г., Поляков В.М., Панченко М.В. Диагностика нештатных режимов работы вращающейся печи обжига клинкера на основе нейро-нечеткой сети // Приборы и системы. Управление, контроль, диагностика .

2014. № 9 .

УДК 004.81

ФОКУСИРОВАННЫЕ ГИБРИДНЫЕ ВЫВОДЫ

В ПРОДУКЦИОННЫХ СИСТЕМАХ

–  –  –

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

Ключевые слова: продукционные системы, правила, алгоритм логического вывода Введение Эксперт, приглашенный для работы в составе некоторого консилиума, обязан считаться с (мотивированными) мнениями коллег. Зачастую под воздействием альтернативных суждений эксперту приходится изменять собственную точку зрения. На этом эффекте, в частности, построен дельфийский метод группового принятия решений [Орлов, 2005]. Способность к модификации собственных суждений под воздействием альтернативной аргументации без сомнения относится к интеллектуальным способностям человека, а алгоритм, имитирующий эту способность, представляется необходимым компонентом сетевых интеллектуальных систем .

В [Ginkul at al., 2013] рассмотрен простейший вариант задачи модификации суждений, когда в формальном консилиуме участвуют две продукционные системы с обратным выводом, а собственно модификация сводится к заимствованию продукционных правил альтернативной системы .

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

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

1. Задача цитирования Будем рассматривать две продукционные системы с монотонным выводом [Осипов, 2013], одна из которых называется оригинальной, а другая – альтернативной. Основное изложение ведется от имени оригинальной системы, а альтернативная система рассматривается как поставщик дополнительных продукционных правил (правил-цитат). Считается, что обе продукционные системы различаются: (1) процедурами разрешения конфликтов, (2) наборами правил OPS и APS, а также (3) списками потенциально возможных целевых заключений (диагнозов) .

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

Относительно каждой системы предполагается:

все продукционные правила имеют вид IF f1 &... & fn THEN f;

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

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

Под мотивированным заключением диагноза d понимается минимальное по количеству элементов множество продукций P(d), удовлетворяющее следующим свойствам:

P(d) содержит ровно одно правило вида IF... THEN d;

если P(d) содержит правило IF h1 &... & hn THEN h, то для каждой посылки hi (i = 1…n) справедливо одно из двух: либо hi S, либо P(d) содержит единственное правило вида IF... THEN hi .

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

Каждое мотивированное заключение можно однозначно представить деревом с помеченными вершинами (деревом вывода), в котором корень помечен диагнозом d;

терминальные вершины помечены фактами из множества S;

внутренние вершины помечены подтвержденными гипотезами;

если h – метка вершины v, и заключение P(d) содержит правило IF h1 &... & hn THEN h, то вершина v имеет ровно n потомков, помеченных фактами h1,..., hn .

На рис.1 представлено дерево вывода для мотивированного заключения, состоящего из трех продукций:

IF a & b & c THEN d, IF e & b THEN a, IF f & g THEN c .

d

–  –  –

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

Пусть P(d) – некоторое мотивированное заключение. Если P(d) OPS или P(d) APS, то P(d) – мотивированное заключение, полученное соответственно оригинальной или альтернативной продукционными системами. Построением мотивированного заключения в пределах той или иной продукционной системы занимается блок логического вывода .

Задача цитирования состоит в том, чтобы по заданному мотивированному заключению PA(d) APS, полученному в альтернативной системе, построить силами оригинальной системы мотивированное заключение P(d) OPS PA(d) .

Заметим, что с формальной точки зрения задача цитирования всегда имеет решение: достаточно положить P(d) = PA(d). Проблема лишь в том, чтобы построить фокусированный гибридный вывод – суть – множество P(d), в котором все сторонние продукции из P(d) \ OPS образуют минимальный связный подграф .

2. Фокусированный гибридный вывод Предположим, что оригинальная продукционная система располагает мотивированным заключением P(d), где d – диагноз, который требуется подтвердить. Для каждого правила IF... THEN h из множества P(d) можно проверить выводимость гипотезы h в оригинальной продукционной системе. При этом все гипотезы и факты, упомянутые в P(d), распадаются на два непересекающихся подмножества: H(A) – гипотезы, подтверждающиеся только в альтернативной системе; H(#) – факты из S, а также гипотезы, подтверждающиеся в обеих системах .

Случай d H(#) означает, что диагноз d выводим в оригинальной системе без привлечения сторонних правил, и использование механизма цитирования является избыточным. В дальнейшем будем полагать, что d H(#) .

Если h – некоторая гипотеза, и h H(#), то, с одной стороны, в оригинальной системе существует хотя бы одно мотивированное заключение PO(h), а, с другой стороны, из правил PA(d) можно сконструировать мотивированное заключение PA(h). Вообще говоря, PO(h) и PA(h) – разные множества правил, подтверждающие гипотезу h .

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

Наличие непересекающихся подмножеств H(A) и H(#) порождает раскраску (двумя красками) вершин дерева мотивированного заключения PA(h). Пример раскраски приводится в левой части рис. 2. По построению на каждом пути от корня дерева вывода к терминальной вершине найдется (первое по порядку) ребро, вершины которого окрашены по-разному .

Упомянутые ребра образуют сечение дерева. Назовем доминантой дерева вывода альтернативного заключения его максимальную (по числу вершин) шапку, не содержащую ребра сечения. Будем использовать обозначение для количества различных гипотез задействованных в качестве меток доминанты. Для доминанты, представленной в правой части рис. 2, имеем: = 6 .

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

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

Для оценки правдоподобия доминанты рассмотрим – см.

пример на рис.3 – два дерева вывода одного и того же диагноза d:

дерево вывода в альтернативной продукционной системе;

дерево фокусированного гибридного вывода .

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

1. Изоморфные вершины шапок помечены одинаковыми диагнозами/гипотезами/фактами .

2. Шапки не поддаются расширению с сохранением свойства 1 .

d A d A

–  –  –

Рис.3. Пример дерева вывода в альтернативной продукционной системе (слева) и дерева фокусированного гибридного вывода (справа) Нетрудно убедиться, что общая часть (см., например, левую часть рис. 4) включает в себя доминанту и ее окрестность первого порядка, однако может содержать и другие вершины (такие как r и p). С содержательной точки зрения общая часть деревьев представляет собой совместный продукт двух продукционных систем, в котором можно определить доли их участия. Одну из этих долей предлагается использовать в качестве искомой оценки правдоподобия: = /, где – количество гипотез в общей части, подтверждаемых правилами оригинальной продукционной системы, а – количество гипотез в общей части. Понятно, что = ( ) / .

Для примера, представленного на рис. 3 и рис. 4, общая часть содержит шесть различных гипотез: d, u, b, e, r, h, первые четыре из которых входят в доминанту, то есть = 4, = 6 и, окончательно, = 1/3 .

–  –  –

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

Список литературы [Орлов, 2005] Орлов А.И. Теория принятия решений. – М.: Экзамен, 2005 .

[Осипов, 2013] Осипов Г.С. Лекции по искусственному интеллекту. – М.: Либроком, 2013 .

[Ginkul at al., 2013] Ginkul G. and Soloviev S. The Quoting-Based Algorithm for Cooperative Decision Making in Production Systems // Proc. Int. Conf. IIS, Chisinau:

IMCS. 2013. – http://park.glossary.ru?24 УДК 004.832.38

–  –  –

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

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

Введение С увеличением объемов и сложности обрабатываемой информации все более актуальным становится использование систем искусственного интеллекта. При этом одной из наиболее распространенных моделей представления знаний является продукционная [Джарратано и др., 2007]. Алгоритмы поиска решений в таких системах основаны на механизме логического вывода. На практике существует большое число задач принятия решений в условиях неопределенности, для которых получение информации о состоянии предметной области является ресурсоемкой операцией .

Такие задачи возникают, например, когда робот исследует поверхность другой планеты. Если цель робота состоит в том, чтобы добраться до определенной скалы, но будущий маршрут является наблюдаемым лишь отчасти, то робот должен попытаться выработать оптимальное решение, касающееся того, как достичь цели с учетом ограниченности ресурсов, доступных для дополнительной разведки местности. Другим примером, в котором стоимость получения новой информации может быть высокой, является коммерческая медицина. Для минимизации издержек, необходимо находить приемлемый способ лечения с помощью минимального количества анализов, выполненных за минимальное время. Задержка в предоставлении лечения, в целях проведения дополнительных анализов, Работа выполнена при финансовой поддержке РФФИ (проект № 15-07-05341) .

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

С фактором ресурсоемкости операций получения данных, необходимых для принятия решения, связана задача минимизации числа запросов о состоянии предметной области в ходе логического вывода. Данная задача является NP-трудной [Махортов и др., 2013]. Для достижения глобальной минимизации числа внешних запросов, предложен общий метод LPвывода [Махортов, 2009a]. К сожалению, он обладает экспоненциальной вычислительной сложностью относительно числа атомарных фактов в базе знаний. Идея кластерно-релевантного LP-вывода [Махортов, 2009b], основана на вычислении специфических оценок (показателей релевантности) для ограниченного подмножества продукций и на обобщении полученных оценок на все множество продукций. Исследования и эксперименты показывают [Болотова и др., 2011], что при использовании метода LP-вывода, по сравнению с обычным обратным выводом, снижение числа внешних запросов составляет в среднем 15–20% .

Ранее [Шмарин и др., 2015] были рассмотрены структурные свойства разбиения бинарного отношения, на основании которых можно выбирать для анализа такое подмножество продукций, которое наиболее существенно влияет на показатель релевантности .

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

1. О методе нечеткого LP-вывода Пусть задано конечное множество F { f }. На его основе определим атомно-порожденную ограниченную алгебраическую решетку L ( F ), где функция-булеан [Салий и др., 1997]. На решетке зададим дополнительное бинарное отношение R r, f : L, f F, являющееся каноническим [Болотова и др., 2011] .

–  –  –

Если же f Finit, то есть атом является начальным, то f M init f .

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

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

2. Реализация системы нечеткого LP-вывода Разработанная программная система нечеткого LP-вывода является развитием пакета LPExpert [Махортов, 2009a]. Она содержит следующие компоненты: ядро логического вывода, модуль работы с нечеткими LPструктурами. Архитектура системы представлена на рис. 1 .

Графический интерфейс пользователя реализован на C++ и основан на фреймворке Qt4 [Бланшет и др., 2008]. Компилятор базы знаний реализован с помощью GNU Flex (генератора лексических анализаторов) и GNU Bison (генератора синтаксических анализаторов). Для построения нечеткой LP-структуры реализована классовая иерархия, основанная на базовом классе LPStructure. Процесс вычисления показателей релевантности, а также выбор очередного вопроса, выполняется в отдельном потоке, который синхронизируется с основным потоком графического интерфейса пользователя .

На рис. 2 показан алгоритм главного рабочего процесса системы – проведение экспертизы. Вначале, выполняется загрузка модели знаний, которая компилируется в промежуточное представление LP-структуры .

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

Рис.1. Архитектура системы нечеткого LP-вывода Рис.2. Алгоритм проведения экспертизы Заключение Рассмотрена компьютерная реализация системы нечеткого LP-вывода .

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

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

Список литературы [Бланшет и др., 2008] Бланшет Ж., Саммерфилд М. Qt 4. Программирование GUI на С++. – М: КУДИЦ-Пресс, 2007 .

[Болотова и др., 2011] Болотова С.Ю., С.Д. Махортов Алгоритмы релевантного обратного вывода, основанные на решении продукционно-логических уравнений // Искусственный интеллект и принятие решений. 2011. №2 .

[Джарратано и др., 2007] Джарратано Д., Райли Г. Экспертные системы: принципы разработки и программирование. – М.: Вильямс, 2007 .

[Махортов и др., 2013] Махортов С.Д., Шмарин А.Н. Оптимизация метода LPвывода // Нейрокомпьютеры. Разработка, применение. 2013. № 9 .

[Махортов, 2009a] Махортов С.Д. Основанный на решетках подход к исследованию и оптимизации множества правил условной системы переписывания термов // Интеллектуальные системы. Теория и приложения. 2009. Т. 13 .

[Махортов, 2009b] Махортов С.Д. Интегрированная среда логического программирования LPExpert // Информационные технологии. 2009. Т. 12 .

[Пегат, 2013] Пегат А. Нечеткое моделирование и управление. – М.: БИНОМ .

Лаборатория знаний, 2013 .

[Салий и др., 1997] Салий В.Н., Богомолов В.А. Алгебраические основы теории дискретных систем. – М.: Физматлит, 1997 .

[Шмарин и др., 2015] Шмарин А.Н. Махортов С.Д. О приближенных оценках количества слоев без циклов в задаче нечеткого LP-вывода // Нейрокомпьютеры. Разработка, применение. 2015, № 12 .

СЕКЦИЯ 10 НЕЧЕТКИЕ МОДЕЛИ И

МЯГКИЕ ВЫЧИСЛЕНИЯ

УДК 004.85

ОРИГИНАЛЬНЫЙ АЛГОРИТМ ПОСТРОЕНИЯ

НЕЧЕТКОГО АППРОКСИМАТОРА ПОТОКОВЫХ

ДАННЫХ1

–  –  –

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

Ключевые слова: потоковые данные, нечеткий аппроксиматор типа Ангелова–Ягера, облако данных Введение Нечеткие модели типа Такаги–Сугено давно и успешно применяются для идентификации систем в пакетном режиме, когда разработчику предоставлен Исследование выполнено при финансовой поддержке РФФИ в рамках научного проекта № 16-07-00034а и 16-37-60051 .

весь набор данных [Gacto et al., 2014]. В случае потоковых данных модель должна перестраиваться по мере поступления новых данных. Нечеткие системы, получившие сокращенное название AnYa (по первым буквам фамилий авторов P. Angelov, R. Yager) [Angelov et al., 2011], способны работать в режиме реального времени за счет снижения вычислительной сложности ЕСЛИчасти правил. Основой систем типа AnYa является база правил, в которой каждое правило – это локальная модель (подсистема), построенная на основе выделяемой группировки данных или облака. Облако соответствует ЕСЛИчасти правила. Таким образом, концепция систем типа AnYa не предполагает определения искусственных функций принадлежности по каждой переменной, вместо этого используется реальное распределение данных. Описание облака задается в векторной форме, тем самым устраняется необходимость использования логических связок и операции агрегирования. Важной особенностью систем типа AnYa является использование функции плотности данных для получения уровня активации каждого правила [Angelov et al., 2011] .

В данной работе представлен вычислительно менее сложный алгоритм построения базы правил системы типа AnYa. Уменьшение сложности достигается за счет хранения усредненных значений параметров о каждом облаке, а также отказа от расчета глобальной плотности, расчет которой ведется в алгоритмах Ангелова [Angelov et al., 2011] .

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

1. Нечеткая система типа Ангелова-Ягера Правило Ri нечеткой системы типа AnYa имеет следующий вид [Angelov et al., 2011]:

R i : IF x i THEN ui, где x = [x1, x2, …, xn] – вектор входных данных; ui – консеквент i-го правила; символ «~» означает отношение «связано с облаком»; i – i-е облако входных данных, i = 1, 2, …, N; N – число нечетких правил .

Используя множество правил типа Ri, можно описать нелинейную, нестационарную, недетерминированную систему посредством ранее наблюдаемых входов и выходов zj = [xj, yj], j = 1, 2, …, k–1 и текущего входа xk .

Выход нечеткой системы для k-го входа вычисляется следующим образом:

N

–  –  –

2. Алгоритм построения базы правил системы типа Ангелова-Ягера Введем следующие обозначения: r – граница по расстоянию на входном пространстве, L – граница по расстоянию на выходном пространстве, N – количество нечетких правил (облаков), pki – количество точек в облаке i на k-й итерации алгоритма .

Псевдокод алгоритма приведен ниже .

Вход: z, r, L .

Выход: R .

Получить первый экземпляр данных z1, R:={1(µ11=x1), 11=y1}, N:=1, k:=1;

цикл пока (возможно получить экземпляр данных zk) Рассчитать ki по формуле (3) при i=1, 2, …N;

near : arg max( k ) ;

i

–  –  –

0,10 0,10 0,08 0,08 0,06 0,06 0,04

–  –  –

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

В [Lisin et al., 1999] аппроксимация первого набора данных была выполнена на 12 правилах алгоритмом Mitaim–Kosko с ошибкой RMSE = 1,426, для алгоритма Lisin и Gennert RMSE = 0,247. При аппроксимации этого же набора данных нечеткой системой типа синглтон, построенной с применением непрерывного алгоритма муравьиной колонии и метода наименьшего квадрата ошибка RMSE составила 0,0191 [Ходашинский и др., 2012]. Нечеткий аппроксиматор, построенный на основе предложенного нами алгоритма, имеет 16 правил, а ошибка аппроксимации RMSE составила 0,0581 .

В работе [Blazic et al., 2015] аппроксимация третьего набора данных была выполнена на 17 правилах нечеткой системой типа AnYa с использованием евклидова расстояния, ошибка MSE составила 0,0232; для нечеткой системы AnYa, построенной с использованием расстояния Махланобиса и базой из 4 правил, MSE = 0,0172. Нечеткий аппроксиматор, построенный на основе предложенного нами алгоритма, имеет 6 правил, а ошибка аппроксимации MSE составила 0,0213 .

Заключение В работе представлен алгоритм построения базы правил нечеткого аппроксиматора типа AnYa. Алгоритм позволяет модифицировать нечеткую систему по мере поступления новых данных. Проведеный анализ влияния параметров алгоритма на точность вывода нечеткого аппроксиматора позволил дать рекомендации по выбору параметров r и L. Проведено сравнение с результатами нечетких систем, построенных в пакетном режиме, и методом Ангелова для формирования нечетких систем типа AnYa. По результатам сравнения можно сделать вывод о том, что предложенный нами алгоритм сопоставим по точности и количеству правил с алгоритмами построения нечетких аппроксиматоров как в пакетном режиме, так и в режиме онлайн .

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

Список литературы [Ходашинский и др., 2012] Ходашинский И.А., Дудин П.А. Идентификация нечетких систем на основе непрерывного алгоритма муравьиной колонии // Автометрия. 2012. Т. 48. № 1 .

[Angelov et al., 2011] Angelov P., Yager R. Simplified fuzzy rule-based systems using non-parametric antecedents and relative data density // IEEE Workshop Evol. Adapt .

Intell. Syst. 2011 .

[Blazic et al., 2015] Blazic S., Angelov P., Skrjanc I. Comparison of approaches for identification of all-data cloud-based evolving systems // IFAC-PapersOnLine .

2015. Vol. 48 .

[Gacto et al., 2014] Gacto M.J., Galende M., Alcal R., Herrera F. METSK-HD: A multiobjective evolutionary algorithm to learn accurate TSK-fuzzy systems in highdimensional and large-scale regression problems // Information Sciences. 2014. Vol. 276 .

[Lisin et al., 1999] Lisin D., Gennert M. A. Optimal Function Approximation Using Fuzzy Rules // Proc. 18th Int. Conf. North American Fuzzy Information Processing Society. IEEE Press, New York, 1999 .

УДК 681.5.01

НЕЙРО-НЕЧЕТКИЕ АЛГОРИТМЫ В ЗАДАЧЕ

ДИАГНОСТИКИ КОТЕЛЬНОГО АГРЕГАТА1

–  –  –

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

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

Для мощных котлоагрегатов АСУТП представляют собой многоуровневые иерархические системы распределнного типа, в которых нижний уровень представлен микропроцессорными устройствами сбора и обработки информации, а верхний уровень – средствами сбора и обработки Работа выполнена при финансовой поддержке РФФИ (проект № 16-07-00491а) .

информации на базе IBM PC совместимых компьютеров. Применение компьютеров позволяет относительно просто, только за счет усложнения алгоритма, ввести в состав АСУТП еще один уровень иерархии обработки информации отвечающий за диагностические процедуры углубленного анализа данных (Data Mining) .

1. Структура обработки информации в системе управления Для реализации дополнительного уровня иерархии системы обработки информации в АСУТП котлоагрегатом были применены такие интеллектуальные методы, как нечеткая логика и искусственные нейронные сети. В результате общая структура управления получила вид, показанный на рис. 1 .

Рис. 1. Структура управления котельным агрегатом

Использование в АСУТП ОС Windows делает возможным и удобным проведение углубленного анализа состояния объекта управления с привлечением алгоритмически сложных методов. Учитывая инерционность котлоагрегата, время, затрачиваемое на текущую обработку информации о его состоянии становится не критичным. Это оправдывает применение программной системы как MatLAB, предоставляющей широкий спектр прикладных пакетов для интеллектуальной обработки информации .

Конкретизируем назначение и функции блоков, используемых диагностики: нечеткой фильтрации калмановского типа и искусственной нейронной сети (ИНС).

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

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

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

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

2. Описание алгоритма обработки информации В работе в составе алгоритмического обеспечения АСУТП котельного агрегата предлагается применить процедуру решения обратных задач динамики на основе ИНС. Поясним структуру применения ИНС. Пусть Х – выходной сигнал объекта управления (вектор состояния), V – входной сигнал .

Обучение ИНС проходит на наборах исходных данных вида {Х, V} .

Обучающая выборка составляется в соответствии с требованиями [Дли и др., 2001] и представляет собой входной вектор X = {xi} и вектор целей V = {v i}, где i = 1, …, Nв, где Nв – объем обучающей выборки .

Как показано на рис. 1, перед ИНС стоит цифровой фильтр, реализующий обработку данных на основании дискретного калмановского алгоритма оценки параметров состояния управляемого объекта. Выбор этого варианта фильтрации обусловлен рядом достоинств, в частности таких как, удобство реализации на цифровой вычислительной технике и наличие возможности восстановить все компоненты вектора состояния по наблюдению лишь части из них. Фильтр Калмана позволяет учесть априорную информацию о статистических характеристиках случайных процессов, что позволяет минимизировать ошибку оценку вектора состояний объекта управления X(t) или его дискретного аналога X(k), где k – номер дискретного отсчета вектора состояний .

Применение предварительной фильтрации входного сигнала ИНС с помощью калмановских алгоритмов освещалась в литературе и ранее, например [Пучков и др., 2012], но там для определения значений элементов матрицы А (матрица формирующего фильтра, являющегося моделью системы в алгоритме Калмана) предлагался подход на основе только экспертных правил, оформленных в виде нечеткой базы знаний. В данном случае предлагается модификация этого подхода – применение гибридной ИНС с архитектурой ANFIS способной самостоятельно извлекать знания из получаемых данных .

3. Результаты численного эксперимента Для обоснования работоспособности предлагаемого совершенствования архитектуры АСУТП проведен численный эксперимент в среде Simulink. В качестве объекта управления была выбрана вторая ступень пароперегревателя котла ТП-81. Регулировка температуры перегретого пара в нем осуществляется впрыском собственного конденсата. При работе на проектном топливе давление перегретого пара Р = 140 кгс/см2, температура перегретого пара 550°С. Автоматическое регулирование перегрева пара должно обеспечить поддержание температуры перегретого пара на постоянном уровне с отклонениями не более 5оС от номинала. Объект управления описывался передаточной функцией в виде инерционного звена второго порядка с запаздыванием, применимость которой обоснована в [Кулаков, 2003] .

Учитывая тот факт, что наличие запаздывания у объекта приводит к тому, что ИНС, решая обратную задачу, получает псевдорешение отстающее на время запаздывания, для вычисления ошибки показания входного измерителя сдвигаются назад на величину этого времени .

В модели была создана ситуация, когда входные и выходные измерения зашумлены. Для входного сигнала предусмотрена возможность его считывания из файла, но в данном примере сигнал представляет собой постоянную величину, что позволяет избежать влияние переходных процессов на показания. Интервал дискретизации Т0 выбран в соответствии с рекомендациями [Изерман, 1984]: Т0 = Т95/12, где Т95 – время достижения переходным процессом величины 95% от установившегося значения. Алгоритмы работы фильтров, ИНС и диагностики оформлены в виде функций MatLAB .

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

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

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

На рис. 2 показаны графики входного сигнала, зашумленные измерения входного измерителя и выхода ИНС для прогона модели с одним из наборов исходных данных .

Рис. 2. Результаты моделирования

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

Моменты появления предельных рассогласований соответствовали тем интервалам времени, когда разность между показаниями входного измерителя и ИНС становилась больше, чем «расстояние» от показаний измерителя до края диапазона допустимого интервала температуры. Предполагается, что данная ситуация указывает на то, что необходимо принять дополнительные меры для контроля входного сигнала .

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

Список литературы [Дли и др., 2001] Дли М.И., Круглов В.В., Голунов Р.Ю. Нечеткая логика и искусственные нейронные сети. / – М.: Физматлит, 2001 .

[Изерман, 1984] Изерман Р. Цифровые системы управления. – М.: Мир, 1984 .

[Кулаков, 2003] Кулаков Г.Т. Анализ и синтез систем автоматического регулирования. – Минск: Технопринт, 2003 .

[Пучков и др., 2012] Пучков А.Ю., Павлов Д.А. Варианты построения алгоритма поиска решения обратных задач с применением нейронных сетей // Программные продукты и системы. 2012. № 2 (98) .

[Сизиков, 2003] Сизиков В.С. О способах невязки при решении некорректных задач // Журнал вычислительной математики и математической физики. –

2003. Т. 43, № 9 .

УДК 007:519.816

ОЦЕНКА РИСКОВ НА ОСНОВЕ ТЕМПОРАЛЬНЫХ

НЕЧЕТКИХ БАЙЕСОВСКИХ СЕТЕЙ

–  –  –

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

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

Наиболее полно описанные особенности решаемых задач позволяют учесть байесовские сети доверия и другие модели, принадлежащие одноименному классу. Байесовская сеть представляет собой ациклический направленный граф, в котором узлы сопоставлены случайным элементам, а вероятностная зависимость между ними определяется тензорами условных вероятностей. В начале 80-х годов Д. Перл предложил метод осуществления вероятностного вывода в древовидных сетях на основе передачи сообщений [Pearl, 1989]. Впервые понятие байесовской сети доверия предложено в работе [Pearl, 1986], а в работе [Pearl, 1988] представлен аппарат вывода на ее основе .

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

Нечткие байесовские сети доверия [Fogelberg, 2008], [0] являются результатом гибридизации байесовских сетей доверия и элементов теории нечтких множеств. Основными известными способами введения нечткости в байесовские сети являются: введение в байесово правило функции принадлежности значения переменной-предка, определенной на множестве значений переменной-потомка; использование операций t- и s-норм над нечткими множествами; использование расширенных (по принципу обобщения) арифметических операций над нечткими числами. Данный вид моделей, обладая достоинствами байесовских сетей доверия, позволяет представлять и обрабатывать данные в условиях как стохастической, так и нестохастической неопределенности. Тем не менее, нечеткие байесовские сети не позволяют учитывать ни количественные, ни качественные временные зависимости .

Наиболее полно вышеописанным требованиям удовлетворяют темпоральные нечеткие байесовские сети (ТНБС) [Захаров, 2014] .

Темпоральная нечткая байесовская сеть (ТНБС) – это байесовская сеть доверия, в которой антецедентом причинно-следственной связи выступает сложное темпоральное высказывание, а в качестве меры истинности высказываний используется нечткая вероятностная мера .

1. Программные средства для моделирования рассуждений с использованием ТНБС Для реализации моделирования рассуждений с использованием ТНБС были разработаны программные средства, модульная структура которых представлена на рис. 1 [Захаров, 2016]. Основными модулями разработанных программных средств являются следующие: инфраструктурный, нечетких вычислений, правдоподобных рассуждений, построения ТНБС, анализа результатов моделирования .

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

–  –  –

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

По результатам опроса экспертов были выбраны значения длительности сбоя напряжения в системе противоаварийной защиты: 10, 25, 45 и 60 сек. Также от экспертов были получены данные о том, что максимальная задержка между моментом сбоя напряжения и поступлением в систему информации об аварийной ситуации не превышает 18 сек .

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

Рис. 2. ТНБС для оценки рисков на ОПО П-201

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

в начале моделирования в модель вносилось свидетельство «L = l2», проводилось моделирование в течение периода времени равного текущей величине задержки, после чего в модель вносилось свидетельство «L = l1» .

В табл. 2 представлены значения нечеткой вероятности (риска) события «Несчастный случай на производстве» (W = w1) для различных значений длительности сбоя напряжения и задержки поступления информации об аварийной ситуации. Данные в таблице представлены в формате [a; b; c], где a – левая граница нечеткости, b – мода нечеткого числа, c – правая граница нечеткости .

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

–  –  –

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

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

2. Изменить порядок устранения неисправностей в работе печи П-201 .

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

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

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

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

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

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

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

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

Список литературы [Pearl, 1989] Pearl J. Reverend Bayes on inference engines: A distributed hierarchical approach // Proceedings of the National Conference on Artificial Intelligence.– Pittsburgh, Pennsylvania. Morgan Kaufmann, 1982 .

[Pearl, 1986] Pearl J. Fusion, propagation, and structuring in belief networks // Artificial Intelligence. No. 29 (3). 1986 .

[Pearl, 1988] Pearl J. Probabilistic reasoning in Intelligent Systems. – NYC: Morgan Kaufmann, 1988 .

[Fogelberg, 2008] Fogelberg С. Fuzzy bayesian networks for network inference. Transfer Report, Computing Laboratory, Wolfson Building, Parks Road, Oxford, OX13QD, 2008 .

[Halliwell, 2003] Halliwell J., Keppens J., Shen Q. Linguistic Bayesian networks for reasoning with subjective probabilities in forensic statistics // Proc. of the 5th International Conference on AI and Law, 2003 .

[Захаров, 2014] Захаров А.С. Особенности построения нечтких байесовских сетей доверия для моделирования темпоральных рассуждений // Сб.тр. XIV конференции по искусственному интеллекту с международным участием КИИ-2014. Т.1. – Казань: Изд-во РИЦ «Школа», 2014 .

[Захаров, 2016] Захаров А.С., Борисов В.В. Программа для моделирования приближнных рассуждений «Temporal»// Свидетельство о государственной регистрации программы для ЭВМ № 2016610375, 11.01.2016 .

УДК 303.732.4

ЭКСТРАПОЛЯЦИОННЫЕ САМООРГАНИЗУЮЩИЕСЯ

ГЕНЕТИЧЕСКИЕ АЛГОРИТМЫ И НЕЙРОННЫЕ СЕТИ

В.Б. Звонков (vladimirzvonkov802@yandex.ru) Сибирский государственный аэрокосмический университет им. акад. М.Ф. Решетнева, Красноярск В работе описываются современные актуальные исследования в области проектирования и настройки генетических алгоритмов и искусственных нейронных сетей применительно к различным классам задач. Приведены исследования автора в данном направлении .

Ключевые слова: генетический алгоритм, самоорганизация, искусственные нейронные сети Введение На сегодняшний день генетические алгоритмы (ГА) и искусственные нейронные сети (ИНС) являются эффективным инструментом решения различных комбинаторных задач оптимизации. Их гибридизация позволяется увеличить эффективность решения различных задач, а также расширить класс решаемых задач. Так называемые «нейроэволюционные алгоритмы» уже достаточно давно применяются различными исследователями [Fullmer et al., 1992], существуют различные способы их гибридизации, влияющие в целом на эффективность подхода. У каждого исследователя существуют свои модификации алгоритмов, т.к. рассматриваемое поле деятельности – эвристические численные алгоритмы комбинаторной оптимизации в пространствах высокой размерности без априорных знаний о решаемой задаче (наиболее общий случай). Использование априорных знаний возможно, когда исследователь точно знает свойства решаемой задачи [Полупанов, 2003] .

Самоорганизация в самом ГА достаточно перспективна с точки зрения сокращения машинного времени на настройку параметров алгоритма под каждую задачу [Лебедев, Полупанов, 2002] .

В исследованиях автора настоящей статьи самоорганизация осуществляется путем автоматизации настройки основных генетических операторов (статья в рамках конференции КИИ-2010) и их параметров (самонастройка алгоритма) с гибридизацией с ИНС (персептронами Розенблатта - с автоматическим проектированием структуры и обучением модифицированным ГА) и некоторыми классическими методами комбинаторной бинарной оптимизации, вещественной оптимизации .

В исследованиях других авторов используются ИНС с радиальными базисными функциями и вертикальными субпопуляциями [Гагарин, 2006], в то время как автором настоящей работы в качестве активационных функций ИНС используются 15 элементарных функций .

Вопрос автоматической настройки популяции в ГА рассмотрен в работе [Цой, Спицын, 2005]. Автором настоящей работы проведено исследование влияния размера популяции и количества поколений на скорость сходимости генетического алгоритма на бинарных строках в тестовых задачах отыскания строки с максимальным числом переходов 0–1, отыскания строки с максимальным числом 1, а также на задачах оптимизации вещественных функций в бинаризованном пространстве, но в ручном режиме с шагом 10 индивидов и 10 поколений. Выводы исследователей подтвердились. Алгоритмы ученых осуществляют это автоматически с шагом 1 .

Рассматриваемый класс алгоритмов проверяется на тестовых задачах, а также широко применяется в прикладных реальных задачах, что описано в монографии [Манов и др., 2010], например, при прогнозировании активной и реактивной нагрузок узлов региональной ЭЭС с использованием ИНС. Рассматриваются электрические сети США и Канады .

Исследования таких алгоритмов проводятся ведущими российскими и зарубежными специалистами [Gladun et al. (editors), 2005], [Holst, 1997] и др .

На настоящий момент достаточно перспективным направлением исследований в России является экономика, а именно применение коллективов ГА и ИНС к прогнозированию различных котировок, курсов валют, ценных бумаг организаций, фьючерсов на нефть и т.д. Исследования автора приведены в статье [Звонков, 2016] .

1. Постановка задачи Пусть имеются исторические значения курсов евро и доллара США в дискретные моменты времени, взятые с официального сайта ЦБ России www.cbr.ru (вся находящаяся в открытом доступе история) или с сайта Forex (выборка из генеральной совокупности, т.к. значения курсов на реальном рынке меняются каждую секунду в зависимости от происходящих политических и экономических событий на рынке, ожиданий инвесторов, действий спекулянтов, открытия или закрытия позиций крупных игроков), а также характеристика фундаментальной составляющей мировой ситуации – вектор входных переменных задачи. Необходимо по имеющимся входным переменным спрогнозировать значения курсов евро и доллара США в следующие будущие дискретные моменты времени .

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

Рассмотрим формализованную математическую постановку задачи и структурную схему SADT-моделирования (Structured Analysis and Design Technique) и RUP-моделирования (Rational Unified Process) бизнеспроцессов с точки зрения автора статьи (рис. 1) .

v (1), v ( 2),..., v ( n ) - вектор значений известных курсов валют в исторические периоды времени – часть входного вектора параметров (массив констант);

u1 (t ), u2 (t ), u3 (t ) - векторы входных параметров – управляемые измеряемые (с помощью механизмов нечткой логики), характеризующие фундаментальную составляющую мировой ситуации на валютных рынках, политическую ситуацию в различных странах (на основании рейтингов Глав Государств и высокопоставленных чиновников), высказывания политиков и Глав Государств в ходе официальных выступлений (пример рассмотрен в таблице 2 в публикации автора статьи в материалах конференции «Системный анализ и информационные технологии» САИТ-2015);

(t ) – действия зарубежных конкурентов, партнеров (шумовая переменная);

(t ) – высказывания зарубежных конкурентов, партнеров (шумовая переменная);

M1(t) – механизм управления сложной системой в виде алгоритмического ядра самоорганизующихся комитетов ГА и ИНС;

M2(t) – механизм управления сложной системой в виде коррекции спрогнозированного алгоритмами вероятностного курса валютной пары по фундаментальным событиям;

v _ out ( t i ) - будущие неизвестные значения валютного курса (окно прогнозирования), т.е. выходная переменная задачи (скаляр);

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

v _ out (t i ) Function(v, u1 (t ), u2 (t ), u3 (t ), (t ), (t )), 1 i N – суть задачи прогнозирования .

Здесь:

u10 (t ) обстановка в России, u1 (t ) обстановка в Австрии, u 2 (t ) обстановка в Бельгии,.. .

u (t ) обстановка в 27 й стране Евросоюза Эстонии, u1 (t ) 1 (прим. Великобритания вышла из ЕС ) u 29 (t ) обстановка на Украине, u130 (t ) обстановка в США,.. .

u 49 (t ) обстановка в последней из крупнейших стран мира .

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

Для проверки правильности и корректности функционирования алгоритмов разработанных программных систем проводилось сравнение с результатами, полученными в системах Deductor Studio Academic, Rapid Miner, Statistica, MathCAD, Matlab and Simulink. Генетический алгоритм первоначально был протестирован на задачах оптимизации из научных отчтов [Hansen et al., 2009], [Suganthan et al., 2005] .

Аппаратно-математическая часть (разработанное автором ПО, методика эксперимента, конфигурации вычислительных систем) описана в публикациях [Zvonkov, 2015] и [Звонков, 2015] .

2. Настройки алгоритмов и результаты прогнозирования Настройки ИНС Ф. Розенблатта для первоначального построения регрессионной модели (для доллара США период от 01.07.1992 до 01.01.2016, для евро период от 01.01.1999 до 01.01.2016) для последующего прогнозирования: обучение методом обратного распространения ошибки, самоорганизующимся ГА. Общие настройки: 20 нейронов на 20 слоях, разделение имеющейся выборки на обучающую и экзаменующую случайным образом в соотношении 90% и 10% соответственно. Алгоритм обратного распространения ошибки: скорость обучения – 0,3, момент инерции – 0,2, число эпох – 2000. Самоорганизующийся ГА: набор из 15 активационных функций кодируется в бинарные строки, автоматический выбор методов, настройка параметров. Выборка официальных курсов евро не нормализовалась, выборка доллара США была нормализована до подачи на ИНС (меньше ошибка решения задачи из-за разброса курсов доллара США в тысячи раз вследствие дефолта рубля 1998 года). Численные критерии эффективности решения задач приведены в табл. 1 .

–  –  –

Заключение К достоинствам разработанных алгоритмов и программных систем следует отнести модульность их построения. Каждая библиотека содержит набор функций, типов данных для решения определенного класса задач: безусловной и условной однокритериальной оптимизации, безусловной и условной многокритериальной оптимизации, нейросетевого моделирования с использованием типовых методов, нейросетевое моделирование с использованием самоорганизующегося ГА, библиотека для работы с файлами ОС и др. Программный код основан на структурах и функциях, динамическом распределении памяти, имеет понятные комментарии, логично и четко выстроенную систему переменных, констант, массивов, пользовательских типов данных в виде структур с использованием современных стандартов программирования языка С++, что обеспечивает более простое программирование и последующее модифицирование кода на структурах, чем при использовании классов объектноориентированного программирования. Создание же программного кода только с использованием многомерных массивов приведет в последующем к усложнению модифицирования программ, так как значительно увеличится количество переменных языка программирования. Этот реализуемый подход является компромиссом приемлемой сложности программирования и понимания функционирования алгоритмов в сравнении с ассемблером или Rapid Miner. Несомненным бонусом разработанных алгоритмов в сравнении с Rapid Miner является отсутствие необходимости ручной настройки алгоритмов ГА и ИНС пользователем .

Предложенные алгоритмы (комитеты из 16 лучших ИНС, проектируемые и настраиваемые самоорганизующимся ГА) продемонстрировали высокую точность при решении задач прогнозирования курса евро и доллара США. В работе в рамках материалов конференции САИТ-2015 автором был проведен трендовый анализ, сглаживание временных рядов, построение общего тренда, подсчет волатильности временных рядов, анализ фундаментальных факторов и экстраполяция на 3 месяца полиномиальным трендом. Построен более точный прогноз с использованием сложных нейросетевых и эволюционных моделей [Zvonkov, 2015]. В марте 2015 был рассчитан прогноз, что рубль РФ будет укрепляться относительно евро в 2015 году. Прогноз подтвердился. Ошибка решения задачи регрессии немного выше из-за сложности задач: многолетняя история курсов валют, высокая волатильность .

В рамках данной работы длительность рассматриваемого исторического периода была увеличена на 1 год, что позволило получить новые результаты прогнозирования курсов двух валютных пар по отношению к российскому рублю. Рассчитано, что рубль РФ в 2016 году будет ослабевать в пределах запланированной ЦБ инфляции. Для выявления сезонной составляющей и долгосрочных трендов во временных рядах проводилось сглаживание данных тремя методами: скользящее среднее, медиана (робастная оценка), экспоненциальное забывание информации .

Список литературы [Гагарин, 2006] Модифицированные генетические алгоритмы с применением нейронных сетей и вертикальных субпопуляций // Вестник УГАТУ. 2006. Т. 8. № 5 .

[Звонков, 2015] Прогнозирование евро и доллара США самоорганизующимися алгоритмами на аппаратно-программных комплексах // Интеллектуальные системы и технологии: современное состояние и перспективы. Сб. науч. трудов III Междунар .

школы-семинара по искусственному интеллекту. – Тверь: Изд-во ТвГТУ, 2015 .

[Звонков, 2016] Гибридные и синергетические интеллектуальные системы: материалы III Всероссийской Поспеловской конференции с международным участием. – Калининград: Изд-во БФУ им. И. Канта, 2016 .

[Лебедев, Полупанов, 2002] Генетический алгоритм компоновки с элементами самоорганизации // Известия ТРТУ. 2002. №3(26) .

[Манов и др., 2010] Методы и модели исследования надежности электроэнергетических систем. – Сыктывкар: Коми научный центр УрО РАН, 2010 .

[Полупанов] Использование знаний о решаемой задаче для генерации стартовой популяции решений // Известия ТРТУ. 2003. №2(31) .

[Цой, Спицын] Исследование генетического алгоритма с динамически изменяемым размером популяции // Труды Международной научно-технической конференции «Интеллектуальные системы» (IEEE AIS’05).– М.: Физматлит, 2005 .

[Fullmer et al., 1992] Using marked-based genetic encoding of neural networks to evolve finite-state behavior // Proceedings of the First European Conference on Artificial Life (ECAL-91). – Cambridge, MA: MIT Press, 1992 .

[Gladun et al. (editors), 2005] Proceedings of the XIth International Conference “KnowledgeDialogue-Solution” – Varna, 2005, Vol. 1, Sofia, FOI-COMMERCE, 2005 .

[Hansen et al., 2009] Real-Parameter Black-Box Optimization Benchmarking 2009:

Noiseless Functions Definitions. Theme COG - Systemes cognitifs. Equipes-Projets Adaptive Combinatorial Search et TAO, Rapport de recherch. 2009. No 6829 .

[Holst, 1997] The Use of a Bayesian Neural Network Model for Classification Tasks / Dissertation, 1997 Studies of Artificial Neural Systems. – Royal Institute of Technology, Stockholm, Sweden, 1997 .

[Suganthan et al., 2005] Problem Definitions and Evaluation Criteria for the CEC // Special Session on Real-Parameter Optimization. Technical Report. – Nanyang Technological University, Singapore And KanGAL (Kanpur Genetic Algorithms Laboratory, IIT Kanpur), 2005 .

[Zvonkov, 2015] Zvonkov V.B. Modified intelligent algorithms committees for optimization and time series forecasting. Collection of scientific papers of International conference “Interactive systems: Problems of Human - Computer Interaction”. – Ulyanovsk: Publishing house of USTU, 2015 .

УДК 004.89+004.021

ОБ ОДНОЙ СХЕМЕ ДИФФЕРЕНЦИАЛЬНОЙ

ЭВОЛЮЦИИ ДЛЯ ГЕНЕТИЧЕСКИХ АЛГОРИТМОВ

МНОГОКРИТЕРИАЛЬНОЙ ОПТИМИЗАЦИИ

–  –  –

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

Ключевые слова: многокритериальная оптимизация, множество и граница Парето, многокритериальные генетические алгоритмы, дифференциальная эволюция Введение Задачи многокритериальной оптимизации (МКО) очень часто возникают в самых разных теоретических и прикладных областях. Качество их решения зависит от точности найденного множества Парето [Ногин, 2004], [Соболь и др., 2006], определение которого остается достаточно сложной и плохо автоматизированной вычислительной процедурой. Основная причина этого в теоретически неограниченном числе недоминируемых решений, образующих множество Парето. Традиционные методы МКО, как правило, исключают процесс определения всего множества Парето, например посредством преобразования задачи со множеством критериев к однокритериальной ее постановке. Негативной стороной этого пути является существенное снижение точности найденных оптимальных решений и их количества .

В настоящее время одним из перспективных подходов к определению множества Парето в задачах МКО является использование эволюционных методов [Гладков и др., 2006], а именно специальных версий генетических алгоритмов для многокритериальной оптимизации (ГА МКО) [Deb et al., 2009]. Главное их преимущество связано с возможностью определения за один запуск целого множества Парето-оптимальных решений без изменения исходной постановки задачи МКО. Сложности анализа многомерных пространств переменных и критериев, вычислительная трудоемкость определения множества Парето привели к появлению ряда эффективных ГА МКО, а также технологий их совершенствования. В статье предлагается подход к развитию возможностей ГА МКО посредством использования в них принципов дифференциальной эволюции. В дополнение к достаточно развитым возможностям этих алгоритмов исследовать пространство критериев, она позволяет повысить разнообразие популяции, а также эффективность анализа решений в пространстве переменных .

1. Применение дифференциальной эволюции в генетических алгоритмах Идея дифференциальной эволюции (Differential Evolution – DE) была предложена Прайсом и Сторном (K. Price, R. Storn) [Storn et al., 1997] как расширение генетических алгоритмов для повышения их точности и скорости схождения при оптимизации с непрерывными значениями переменных. Главная особенность DE состоит в том, что каждое новое поколение формируется с участием индивидов текущей и промежуточной (пробной) популяций. Ее члены образуются посредством определения различий между выбранными по определенным правилам индивидами текущей популяции. Конкретная реализация этого зависит от так называемой схемы DE, параметры которой записываются в виде следующей последовательности DE///. Здесь указывает на изменяемый родительский индивид, - число различных индивидов, участвующих в изменении, а определяет тип используемого кроссинговера (exp – экспоненциальный, bin - бинарный). В случае экспоненциального кроссинговера значения изменяемых генов потомка берутся только у первого индивида-родителя .

При бинарном кроссинговере каждое значение гена потомка формируется из двух соответствующих генов индивидов-родителей. В качестве родительского может выступать как лучший индивид текущей популяции ( = best), так и случайно выбранный индивид ( = rand). Классической и часто применяемой является схема DE/rand/1/bin, алгоритм ее выполнения приведен в [Storn et al., 1997], [Пупков и др., 2004]. На процесс дифференциальной эволюции влияют два управляющих параметра – CR[0, 1] и F 0, значения которых не меняются в процессе работы генетического алгоритма и определяются экспериментально. Параметр CR (Crossover Rate) отвечает за кроссинговер и определяет вероятность изменения каждого гена промежуточного индивида. Параметр F позволяет усилить или ослабить такие изменения, определяя тем самым силу мутации генов. Для управления процессом генерации и исследования новых решений могут использоваться различные варианты схем DE. Друг от друга они отличаются реализацией кроссинговера, а также числом и правилами выбора индивидов для определения векторов в траектории направления поиска [Mezura-Montes et al., 2006] .

Возможности дифференциальной эволюции впоследствии были применены и при решении задач многокритериальной оптимизации [MezuraMontes et al., 2006]. При этом особенности задачи МКО потребовали корректировки существующих и создания новых схем DE, в которых принципы Парето используются на разных этапах ее выполнения. Так, в работе [Xue et al., 2003] была предложена общая концепция дифференциальной эволюции для многокритериальной оптимизации – MODE (MultiObjective Differential Evolution). В ней классическая схема DE дополнена механизмами управления популяцией, использующимися в основных генетических алгоритмах МКО SPEA2, NSGA-II [Deb et al., 2009]. Также следует отметить и модификации этих алгоритмов NSDE [Iorio, 2006], DEMONS-II [Robic, 2005] и DEMOSP2 [Robic, 2005], в которых действия операторов кроссинговера и мутации заменены операциями дифференциальной эволюции. Сравнительное исследование указанных алгоритмов на различных тестовых задачах МКО показали, что во многих случаях полученные DEMONS-II и DEMOSP2 результаты оказались лучше значений соответствующих показателей эффективности алгоритмов NSGA-II и SPEA2 [Tusar et al., 2007]. Однако было выявлено снижение качества результатов при увеличении числа критериев оптимизации независимо от варьирования управляющих параметров CR и F. Одной из причин этого может быть независимость траекторий поиска в пространствах переменных и критериев. Простое использование операции рекомбинации, заимствованной из DE для однокритериальной оптимизации, и учитывающей только особенности размещения решений в пространстве переменных, оказывается недостаточным при исследовании пространства критериев .

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

2. Схема дифференциальной эволюции DE/rand/1X/bin Анализ различных схем дифференциальной эволюции [Mezura-Montes et al., 2006] позволяет сделать вывод, что очень часто выбор второго родителя, а также остальных (два и более) индивидов, необходимых для создания потомка, производится случайно. При этом не гарантируется, что полученный в итоге новый индивид окажется лучше своего родителя .

В общем случае это приводит к снижению разнообразия популяции, а в условиях МКО - сохранению в ней неизменяемой в процессе поиска небольшой доли недоминируемых решений. Увеличение интенсивности операции рекомбинации для DE часто приводит к росту случайной составляющей в процессе оптимизации, потере найденных оптимальных решений. В то же время, для увеличения вероятности создания индивидов, доминирующих своих родителей, могут быть исследованы различные варианты векторов их изменений, образуемые множеством сочетаний выбранных для рекомбинации индивидов. Для классической схемы DE/rand/1/bin это означает, что каждый из участвующих в DE индивидов (с индексами r1, r2, r3 ) может быть выбран в качестве второго родителя (рис. 1) .

Рис. 1. Влияние выбора разных родительских индивидов в DE при поиске Парето-оптимальных решений В случае, когда не одно из сочетаний индивидов в операторе рекомбинации не позволило получить индивида-потомка лучше своего индивидародителя, то последний переходит в следующее поколение. В целом, такая схема дифференциальной эволюции - DE/rand/1X/bin должна обеспечить более активное замещение доминируемых индивидов популяции .

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

Алгоритм DE/rand/1X/bin ( nP, nG, CR, F ), где nP, nG - размер популяции и число поколений соответственно .

Шаг 1. Создать начальную популяцию размером nP и вычислить значения пригодности ее индивидов. t = 0 .

Шаг 2. Для каждого индивида популяции ci, i 1,..., nP выполнить следующие действия .

2.1. Выбрать три разных случайных числа (индекса индивидов) q, r, s 1,..., nP | q r s .

2.2. Множество индивидов, выбранных кандидатами в родители, сделать пустым R = .

2.3. Среди множества индексов индивидов {q, r, s} выбрать любой, не принадлежащий R. Присвоить его переменной r3 и считать индексом индивида-родителя. R R {r3 } | r3 R .

2.4. Переменным r1, r2 произвольно присвоить остальные выбранные индексы. r1 q r s | r1 r3, r2 q r s | r2 r1 r3 .

2.5. Выбрать случайное число k 1,..., n .

2.6. На основе всех генов ci, j, j 1,..., n индивида ci, сформировать промежуточный индивид c 'i :

cr, j (t ) F (cr1, j (t ) cr2, j (t )), если (rand(0,1) CR) (j k );

c 'i, j (t 1) 3 ci, j (t ), иначе .

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

а) если c 'i (t 1) ci (t ), то ci (t 1) c 'i (t 1) ;

б) если ci (t ) c 'i (t 1) и {q, r, s} R, то перейти к шагу 2.3;

в) если ci (t ) c 'i (t 1) и {q, r, s} R, то ci (t 1) ci (t ) ;

c 'i (t 1), то ci (t 1) ci (t ) или ci (t 1) c 'i (t 1) .

г) если ci (t ) Шаг 3. t = t+1 .

Шаг 4. Если t nG, то закончить, иначе перейти к шагу 2 .

Таким образом, предлагаемый вариант DE отличается возможностью формирования пробного индивида с привлечением различных пар родительских индивидов. В них первый индивид остается неизменным, а второй может многократно выбираться из множества случайно отобранных в текущей популяции индивидов перед процедурой рекомбинации. В обычном случае максимальное число таких пар не превышает трех, однако, при использовании альтернативных правил рекомбинации в схеме DE [Mezura-Montes et al., 2006], таких пар может быть больше. Число проверок разных комбинаций родительских индивидов для формирования одного потомка зависит от состава текущей популяции. Практические исследования рассматриваемой схемы дифференциальной эволюции показали, что чаще всего несколько «попыток» при создании пробного индивида используется, когда в популяции много копий одного индивида, либо она заполнена большим числом недоминируемых индивидов. В таких случаях генерация разных вариантов одного промежуточного индивида позволяет поддерживать разнообразие популяции, снизить вероятность схождения алгоритма к локально оптимальному множеству Парето. В отличие от обычной, в предлагаемой версии дифференциальной эволюции, траектория поиска в пространстве переменных формируется в зависимости от расположения индивидов и, прежде всего, получаемого потомка в пространстве критериев. В итоге, исследуются те участки пространства переменных, где содержатся решения, являющиеся недоминируемыми относительно уже исследованных решений. Следует отметить, что при сравнении пробного и текущего индивидов оба могут оказаться недоминируемыми (операция 2.7 правило (г)) и, следовательно, претендовать на переход в следующее поколение. В этом случае процедура выбора индивида (индивидов) должна определяться ГА МКО, использующим данную схему дифференциальной эволюции .

Как следует из приведенного алгоритма DE/rand/1X/bin, он содержит только средства изменения популяции, направленные на поиск и исследование недоминируемых решений. Для увеличения их численности, управления распределением на границе Парето необходимы дополнительные процедуры, реализованные в ряде известных ГА МКО, например, в таких как NSGA-II и SPEA2. Интеграция в них предлагаемой схемы DE (подобно алгоритмам NSDE, DEMONS-II и DEMOSP2) позволит получить новые версии этих алгоритмов, расширяющие свои функциональные возможности при исследовании пространств переменных и критериев .

3. Исследование эффективности использования схемы DE\rand\1X\bin Для оценки эффективности использования предложенной схемы дифференциальной эволюции был проведен ряд экспериментов. Они заключались в решении набора тестовых задач многокритериальной оптимизации (DTLZ1, DTLZ2, DTLZ3, DTLZ6) [Казаков, 2012] с различным числом критериев m = {2, 4, 6, 8}. Это позволило оценить влияние схемы DE/rand/1X/bin на сохранение эффективности использующих ее алгоритмов NSGA-II (NSGA-II+DE*) и SPEA2 (SPEA2+DE*) при росте сложности решаемых задач. В сравнении участвовали результаты, полученные оригинальными версия этих алгоритмов, их модификациями с классической схемой дифференциальной эволюции, а также алгоритмом MODE .

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

Для их вычисления использовался набор индикаторов [Казаков, 2012], позволяющий оценить различные свойства найденного ГА МКО множества Парето в пространстве решений или критериев:

I ONVG (Overall Nondominated Vector Generation) - определяет мощность найденного множества Парето;

I S (Spacing) - используется для оценки равномерности распределения решений вдоль границы Парето;

I DE (Dimensions Extent) - позволяет оценить максимальную протяженность границы Парето по каждой из размерностей;

I GD (Generational Distance) - позволяет оценить степень близости между полученной и заданной эталонной границами Парето;

I OT (Overall Time Computing) - ориентирован на оценку временной эффективности МГА при определении множества Парето .

Условия проведения испытаний, а также полученные числовые показатели приведены в [Казаков, 2015]. Сравнительный их анализ позволил сформулировать следующие выводы .

1. Применение дифференциальной эволюции во всех случаях позволило улучшить сходимость алгоритмов к глобальной границе Парето. В то же время, в 3-х задачах качество найденных решений по индикатору I GD оказалось наилучшим при использовании предложенной схемы DE/rand/1X/bin .

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

3. При решении задач DTLZ1, DTLZ2 и DTLZ6 алгоритмы, использующие схему DE/rand/1X/bin, по большинству показателей (в задаче DTLZ1 по всем) превзошли оригинальные версии SPEA2, NSGA-II .

4. При решении задач с m = {6, 8} результаты SPEA2+DE*, NSGAII+DE* почти по всем индикаторам оказались лучше алгоритмов, использующих обычную схему DE .

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

6. Во всех случаях общее время вычислений при использовании схемы DE/rand/1X/bin превысило значения соответствующего индикатора остальных анализируемых алгоритмов не более чем на 15% .

7. Результаты алгоритма MODE, использующего как дифференциальную эволюцию, так и ключевые особенности SPEA2, NSGA-II, по всем показателям оказались достаточно близки к наилучшим их значениям (по некоторым индикаторам MODE превзошел SPEA2, NSGA-II) .

Заключение Применение дифференциальной эволюции при решении задач многокритериальной оптимизации оказывает существенное влияние на возможность нахождения глобального множества Парето. Достигается это, прежде всего, за счет повышения эффективности исследования пространства решений. Однако для условий многокритериальной оптимизации этого может оказаться недостаточно, так как необходимо учитывать действия дифференциальной эволюции и в пространстве критериев. Один из вариантов реализации этого предложен в виде ее модификации – схемы DE/rand/1X/bin. Она может быть использована с любым ГА МКО, не требует подбора значений дополнительных управляющих параметров, не более чем на 15% увеличивает временную сложность базового алгоритма .

Анализ применения этой схемы DE при решении большинства тестовых задач МКО с пространством критериев различной размерности показал улучшение качества результатов в сравнении с другими используемыми алгоритмами .

Список литературы [Гладков и др., 2006] Гладков Л.А., Курейчик В.В., Курейчик В.М. Генетические алгоритмы. - М.: ФИЗМАТЛИТ, 2006 .

[Казаков, 2012] Казаков П.В. Оценка эффективности генетических алгоритмов многокритериальной оптимизации. Часть 1 // Информационные технологии .

2012. №8 .

[Казаков, 2015] Казаков П.В. Использование дифференциальной эволюции при определении множества Парето генетическими алгоритмами многокритериальной оптимизации // Информационные технологии. 2015. №2 .

[Ногин, 2004] Ногин В.Д. Принятие решений в многокритериальной среде: количественный подход. 2-е изд., испр. и доп. – М.: Физматлит, 2004 .

[Пупков и др., 2004] Пупков К.А., Феоктистов В.А. Алгоритм дифференциальной эволюции для задач технического проектирования // Информационные технологии. 2004. №8 .

[Соболь и др., 2006] Соболь И.М., Статников Р.Б. Выбор оптимальных параметров в задачах со многими критериями. 2-е изд., перераб. и доп. – М.: Дрофа, 2006 .

[Deb et al., 2009] Deb K. Multi-Objective Optimization Using Evolutionary Algorithms. – Hoboken: Wiley, 2009 .

[Iorio, 2006] Iorio A., Li X. Incorporating directional information within a differential evolution algorithm for multi-objective optimization. // Proceedings of the 2006 Genetic and Evolutionary Computation Conference – GECCO 2006. 2006. Vol. 1 .

[Mezura-Montes et al., 2006] Mezura-Montes E., Velazques-Reyes J., Coello C. Comparing Differential Evolution Models for Global Optimization // Proc. of the 2006 Genetic and Evolutionary Computation Conference – GECCO 2006. 2006. Vol. 1 .

[Robic, 2005] Robic T., Filipic B. DEMO: Differential evolution for multiobjective optimization. // Proceedings of the Third International Conference on Evolutionary Multi-Criterion Optimization – EMO 2005. 2005 .

[Storn et al., 1997] Storn R., Price K. Differential Evolution – A Fast and Efficient Heuristic for Global Optimization over Continuous Spaces. // Journal of Global Optimization. 1997. № 11 .

[Tusar et al., 2007] Tusar T., Filipic B. Differential Evolution Versus Genetic Algorithms in Multiobjective Optimization // Proceedings of the Fourth International Conference on Evolutionary Multi-Criterion Optimization – EMO 2007. 2007 .

[Xue et al., 2003] Xue F., Sanderson A., Graves R. Pareto-based multi-objective differential evolution. // Proceedings of the 2003 Congress on Evolutionary Computation – CEC 2003. 2003. Vol. 2 .

УДК 004.056

ГЕНЕТИЧЕСКИЕ АЛГОРИТМЫ ДЛЯ БУЛЕВОЙ

МАТРИЧНОЙ ФАКТОРИЗАЦИИ ПРИМЕНИТЕЛЬНО

К ЗАДАЧАМ РАЗГРАНИЧЕНИЯ ДОСТУПА

В КОМПЬЮТЕРНЫХ СЕТЯХ1

–  –  –

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

Ключевые слова: генетические алгоритмы, булева матричная факторизация, разграничение доступа Введение Задача булевой матричной факторизации (БМФ) заключается в нахождении двух булевых матриц, булево матричное произведение которых равно исходной булевой матрице. К задаче БМФ могут быть сведены задачи во многих предметных областях, в частности, рассматриваемая в настоящей статье задача поиска ролей в ролевой схеме доступа [Lu et al., 2008]. По своей вычислительной сложности задача БМФ является NP-полной [Miettinen et al., 2011]. Методы БМФ заслуженно считаются методами Data Mining. Для частных случаев задач БМФ предложены математические методы решения [Miettinen, 2012; Cergani et al., 2013]. Однако в общем случае высокая сложность задачи БМФ определяет необходимость поиска эвристических методов ее решения. В [Tai et al., 2011] предложено для решения Работа выполнена при финансовой поддержке РФФИ (проекты №№14-07-00697, 14-07-00417, 15-07-07451, 16-37-00338, 16-29-09482 офи_м), при частичной поддержке бюджетных тем № 0073-2015-0004 и №0073-2015-0007, а также гранта РНФ №15-11-30029 в СПИИРАН .

задачи БМФ применять методы кластерного анализа. Однако область применения этого метода ограничена только мобильными сетями. В [Janecek et al., 2011] предложено использовать для решения задач БМФ биоинспирированные алгоритмы, основанные на популяциях. К их числу отнесены следующие алгоритмы: генетические, оптимизации роя частиц, дифференциальной эволюции, рыбного косяка и фейерверка. Сравнительная оценка этих алгоритмов показала, что наибольшей эффективностью при решении задач, подобных БМФ, обладают генетические алгоритмы. Этот же вывод был получен в работах [Saenko et al., 2010; Saenko et al., 2011] .

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

1. Постановки задач БМФ в области разграничения доступа в компьютерных сетях

1.1. Общая постановка задачи БМФ Положим, что A = A [n, m] есть булева матрица, элементы которой принимают значение «0» или «1». Задача БМФ заключается в нахождении булевых матриц W = W [n, k] и H = H [k, m], связанных с A уравнением A = WH, (1.1) где символ обозначает булево матричное умножение, которое является формой матричного умножения, основанной на правилах булевой алгебры. Булево матричное умножение позволяет получать элементы матрицы A согласно следующему выражению: aij nj 1 wij h ji .

1.2. Постановка задачи оптимизации схемы ролевого доступа Механизм ролевого доступа в компьютерных сетях основан на анализе связей между элементами трех множеств: множеств пользователей, ролей и ресурсов. Задача оптимизации схемы ролевого доступа относится к группе задач, объединенных названием «проблема поиска ролей» (Role Mining Problem). Сущность этой задачи заключается в нахождении такого вида матрицы «пользователи» – «роли» и матрицы «роли» – «ресурсы», при котором результирующая матрица «пользователи» – «ресурсы», отражающая реальную схему доступа, совпадает с требуемой .

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

Требуется найти минимально необходимое количество ролей K, а также матрицу X = X [n, k] «пользователи» – «роли» и матрицу Y = Y [k, m] «роли» – «ресурсы», которые обеспечивают полное совпадение результирующей реальной матрицы доступа с требуемой. Требуемая матрица доступа A = A [n, m] связана с матрицами X и Y условием БМФ, выраженным уравнением (1.1) .

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

Формально критерий оптимизации в задаче имеет следующий вид:

K min, D A X Y 0, (1.2) где D – метрика расстояния между матрицами A и X Y. В простейшем случае она задается евклидовом расстоянием и определяется выражением n m K

–  –  –

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

1.3. Постановка задачи первоначального конфигурирования схемы виртуальной локальной компьютерной сети Под виртуальной локальной компьютерной сетью (Virtual Local Area Network, VLAN) будем понимать сеть, в которой реализовано множество виртуальных подсетей. Обмен между узлами в сети VLAN регламентируется следующими условиями:

оба узла, между которыми разрешен обмен, должны принадлежать одной и той же виртуальной подсети;

один и тот же узел может одновременно находиться в различных подсетях;

количество виртуальных подсетей не ограничивается .

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

Положим, что в сети VLAN находится n компьютеров, и между этими компьютерами задана схема разрешенных информационных потоков, определяемая булевой матрицей A[n, n]. Если aij = 1 (i, j = 1, …, n), то обмен между компьютерами i и j разрешен. В противном случае этот обмен невозможен .

Далее положим, что мы сформировали в компьютерной сети k виртуальных подсетей. Каждая из этих подсетей объединяет два и более компьютеров. Зададим распределение компьютеров по подсетям с помощью матрицы X[n, k]. Если xij = 1 (j = 1, …, k), то компьютер i принадлежит подсети j. В противном случае подсеть j не охватывает компьютер i .

Матрица X связана с матрицей А следующим выражением:

A = X X T, (1.4) где XT – транспонированная матрица X. Легко заметить, что матрица A всегда является симметричной .

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

Первое условие есть равенство m = n. Второе условие имеет следующий вид: wij = hji для любых i = 1, …, n и j = 1, …, k. Следовательно, задача (1.4) является разновидностью БМФ. Однако этот вид БМФ является более сложным, чем (1.1), так как в (1.4) обе матрицы, на которые раскладывается матрица A, связаны друг с другом, а в задаче (1.1) они не связаны .

По этой причине задачу (1.4) мы предлагаем называть задачей булевой матричной автофакторизации (БМАФ) .

Как и в предыдущей задаче поиска минимального количества ролей, в задаче (1.4) критерием является минимальное количество k при условии полного совпадения A и X XT .

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

Исходными данными в этой задаче являются:

1) исходная матрица A0[n, n];

2) новая матрица A1[n, n];

3) исходная матрица X0[n, k], отвечающая уравнению (1.4) .

Требуется: найти матрицу X[n, k] такую, что

1) X1 X1T = A1, где X1 = X0 + X;

2) |X| min .

Операция «+» рассматривается как «исключающее ИЛИ» .

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

Положим, что в силу изменения политики безопасности возникла необходимость изменить матрицу A0 на величину A, чтобы между компьютерами появилась новая матрица связности A1 = A0 + A. Следовательно, необходимо сформировать новую схему доступа X1. Можно получить X1, решая задачу первоначального конфигурирования. Однако в результате может получиться матрица, достаточно сильно отличающаяся от исходной матрицы X0. Следовательно, это решение может потребовать от администратора выполнения достаточно большого количества действий по изменению схемы доступа. Поэтому в качестве критерия поиска решения мы выбираем минимум действий, затрачиваемых администратором на реконфигурирование.

Это условие можно записать следующим образом:

x min .

|X| = (1.5) ij n k

Используя матрицу изменения связности A, задачу реконфигурирования схемы доступа VLAN можно записать как задачу поиска (при заданных матрицах X0, A0 и A) матрицы X из следующего уравнения:

(X0 + X) ( X0 + X)T = (A0 + A). (1.6) Задача реконфигурирования, как и задача первоначального конфигурирования, относится к задачам БМАФ и является NP-полной .

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

2.1. Общая структура генетического алгоритма Генетические алгоритмы являются хорошо известным и достаточно распространенным типом эволюционных алгоритмов оптимизации. Однако существуют различные взгляды на последовательность и содержание шагов генетического алгоритма [Goldberg, 1989; Eiben et al., 2007; Гладков и др., 2010]. Будем придерживаться перечисленных ниже шагов генетического алгоритма .

1. Определение функции пригодности .

2. Формирование хромосом .

3. Формирование исходной популяции особей .

4. Выбор пар особей для скрещивание и выполнение скрещивания .

5. Выбор особей для мутации хромосом и проведение мутации .

6. Селекция популяции по значению функции пригодности особей .

7. Завершения работы алгоритма либо переход к этапу 3 .

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

Остальные этапы являются стандартными .

2.2. Формирование структуры хромосомы В задаче (1.2) имеется две булевы матрицы переменных, а в задачах (1.4) и (1.6) – всего одна. Поэтому структура хромосом для этих задач будет различна .

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

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

Однако в этом случае длина хромосом у разных особей будет неодинаковой и будет зависеть от текущего значения K. В результате будет чрезвычайно затруднителен корректный обмен генетическим материалом при скрещивании .

Для преодоления этого недостатка предложим следующие решения:

матрицы X и Y преобразуются таким образом, чтобы их столбцы соответствовали ролям;

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

гены в хромосомах для матриц X и Y имеют не бинарные значения, а являются столбцами соответствующих матриц;

для представления информации о количестве активных и пассивных ролей вводится в рассмотрение третья хромосома Z, которая является бинарной строкой. Если ген этой хромосомы равен 1, то тогда соответствующая роль активная, иначе – пассивная .

2.2.2. Структура хромосомы для задачи первоначального конфигурирования VLAN. Будем использовать одну хромосому, кодирующую матрицу X. Однако в качестве гена хромосомы будет рассматриваться не отдельный элемент матрицы, а вектор xi = (xi1, xi2, …, xjn). Вектор xi играет роль столбца матрицы X .

2.2.3. Структура хромосомы для задачи реконфигурирования VLAN .

Будем использовать в качестве возможного решения не матрицу X, которая играет роль переменной в задаче (1.6), а матрицу X1, которая определяется как сумма («исключающее ИЛИ») X и известной матрицы X0 .

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

В этом случае в качестве гена хромосомы будет рассматриваться вектор x1i = (x1i1, x1i2, …, x1jn), который является столбцом матрицы X1 .

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

–  –  –

2.4. Порядок выполнения операций скрещивания и мутации 2.4.1 Задача поиска ролей. В силу того, что особи имеют по три хромосомы, скрещивание выполняется в три этапа:

на первом этапе проходит обмен частями родительских хромосом Z. Результат показывает, сколько активных ролей будет у потомков и каковы они;

на втором этапе своими частями обмениваются хромосомы X и Y;

на третьем этапе новые хромосомы X и Y корректируют свои гены в соответствии с информацией, содержащейся в новой хромосоме Z .

При мутации вначале корректируется хромосома Z. Затем, изменяются матрицы X и Y в части «активных» ролей .

2.4.2 Задачи конфигурирования VLAN. Операция скрещивания должна дополнительно осуществлять обмен частями генов. Чтобы обеспечить такой режим обмена, предлагается двумерный режим скрещивания, при котором матрицы родительских хромосом перед скрещиванием делятся на две части по диагонали .

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

3. Экспериментальные результаты Экспериментальная оценка разработанных алгоритмов проводилась на компьютере следующей конфигурации: процессор Intel(R) Atom(TM) CPU N2800, оперативная память 2 Gb, операционная система Windows 7, программный код выполнен на C#. Оценивались затраченное количество итераций (T) и длительность одной итерации () алгоритма при различных размерностях задачи. При малой размерности (n = 10) значение T лежало в диапазоне от 26 до 45 при 0,003 сек. При n = 25: T 130 250, 0,15 сек., а при n = 50: T 530 850, 1,1 сек. При любых размерностях достигалось полное совпадение реальной и требуемой схем доступа .

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

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

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

Список литературы [Гладков и др., 2010] Гладков Л.А., Курейчик В.В., Курейчик В.М. Генетические алгоритмы. – М.: Физматлит, 2010 .

[Cergani et al., 2013] Cergani E., Miettinen P. Discovering Relations using Matrix Factorization Methods // Proc. 22nd ACM International Conference on Information & Knowledge Management, New York. 2013 .

[Eiben et al., 2007] Eiben A.E., Smith J.E. Introduction to Evolutionary Computing. – Springer, Heidelberg, 2007 .

[Goldberg, 1989] Goldberg D.E. Genetic Algorithms in Search, Optimization, and Machine Learning. – Addison-Wesley Longman Publishing, Boston, 1989 .

[Janecek et al., 2011] Janecek A., Tan Y. Using Population Based Algorithms for Initializing Nonnegative Matrix Factorization // Advances in Swarm Intelligence. Lecture Notes in Computer Science. 2011. Vol. 6729 .

[Lu et al., 2008] Lu H., Vaidya J., Atluri V. Optimal Boolean Matrix Decomposition:

Application to Role Engineering // Proc. 24th IEEE International Conference on Data Engineering. 2008 .

[Miettinen et al., 2011] Miettinen P. and Vreeken J. Model Order Selection for Boolean Matrix Factorization // Proc. 17th ACM SIGKDD Conference on Knowledge Discovery and Data Mining, New York. 2011 .

[Miettinen, 2012] Miettinen P. Dynamic Boolean Matrix Factorizations // Proc. 12th IEEE International Conference on Data Mining, New York. 2012 .

[Saenko et al., 2010] Saenko I., Kotenko I. Genetic Optimization of Access Control Schemes in Virtual Local Area Networks // Fifth International Conference "Mathematical Methods, Models and Architectures for Computer Networks Security" (MMM-ACNS-10). Lecture Notes in Computer Science. 2010. Vol. 6258 .

[Saenko et al., 2011] Saenko I., Kotenko I. Genetic Algorithms for Role Mining Problem // Proc. of 19th International Euromicro Conference on Parallel, Distributed and Network-based Processing. Ayia Napa, Cyprus, 2011 .

[Tai et al., 2011] Tai Ch.-F., Chiang Tz.-Ch., Hou T.-W. A virtual subnet scheme on clustering algorithms for mobile ad hoc networks // Expert Systems with Applications: An International Journal. 2011. Vol.38. Iss.3 .

УДК 007:519.816

ПРИМЕНЕНИЕ НЕЧЕТКОЙ ВРЕМЕННОЙ ЛОГИКИ

РЕАЛЬНОГО ВРЕМЕНИ ПРИ ПОСТРОЕНИИ

ПОДСИСТЕМЫ ДИАГНОСТИКИ И МОНИТОРИНГА

ДЛЯ ИНТЕЛЛЕКТУАЛЬНОЙ СИСТЕМЫ УПРАВЛЕНИЯ

КРУПНЫМ ПАРКОВОЧНЫМ КОМПЛЕКСОМ1

–  –  –

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

Ключевые слова: интеллектуальная система, временная логика, нечеткая временная логика реального времени Введение Современные интеллектуальные системы (ИС) управления крупными парковочными пространствами (УКПП) интегрируют в единое целое распределенные программно-аппаратные комплексы обеспечения безопасности, контроля доступа и противодействия мошенничеству. Применение при разработке таких систем современных технологий искусственного интеллекта (ИИ) позволяет с одной стороны получить богатые функциональные возможности, а с другой стороны позволяет радикально упростить процедуры диагностики, экспертного анализа нештатных ситуаций и технического обслуживания [Eremeev et al., 2015] .

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

Работа выполнена при финансовой поддержке РФФИ (проекты № 15-07-04574-а, № 14-01-00427-а) .

2. Практическая задача В крупных парковочных системах с большой интенсивностью нагрузки применяются полностью автоматизированные парковочные системы [Борисов и др., 2005]. При этом минимизируется человеческий фактор и исключается необходимость в присутствии оператора .

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

В связи с тем, что подобные системы осуществляют охранные, контролирующие функции, а также функции тарификации и сбора оплаты, они часто становятся объектами вандализма, мошенничества и иных видов атак, связанных с человеческим фактором. Причем, не всегда в штатной работе комплекса заинтересован даже рядовой обслуживающий персонал, получающий прямую выгоду от возможности неконтролируемого сбора оплаты за парковку в «ручном» режиме, в случае неработоспособности комплекса. С другой же стороны, руководство технических объектов на автоматизированных паркингах, обычно заинтересованное в бессбойном режиме аппаратуры и средств контроля, вынужденно сталкиваться с часто нетривиальной задачей анализа причин разнообразных сбоев и отказов. В связи с этим, для упрощения диагностики происходящего на объекте, а также для обеспечения системы возможностью интеллектуального противодействия фактам мошенничества и намеренного вандализма, в Российских и зарубежных программно-аппаратных комплексах автоматизации крупных парковочных пространств в настоящее время применяются современные технологии ИИ. Одним из таких применений может рассматриваться предмет данной статьи – распределенная подсистема автоматической диагностики, мониторинга, противодействия и объяснения нештатных ситуаций, использующая технологии рассуждений на основе темпоральных прецедентов, временные логики и продукционные системы [Еремеев и др., 2007] .

Благодаря наличию большого числа датчиков на точках въезда, выезда и оплаты, такая подсистема может включать средства отслеживания хода операций. Они расширяют возможности ИС УКПП в плане реакции на нетиповые ситуации. При построении таких средств может быть использован тот факт, что операции, протекающие на точках доступа в штатном режиме, формируют во времени достаточно стандартные последовательности событий, что можно проиллюстрировать на примерах типовых событий при операциях проезда [Еремеев и др., 2010]. Процесс работы точки может быть представлен в виде последовательности однотипных операций, каждая из которых также есть совокупность наблюдаемых стандартных событий. Аномальные ситуации могут быть выделены за счет анализа такой последовательности путем проверки соответствия наблюдаемых в процессе конкретной операции событий и эталонных моделей штатного или нештатного развития ситуации (на основе прецедентов). При этом следует анализировать ситуацию «в динамике», принимая решения с учетом истории развития процесса. Поэтому используются правила, содержащие выражения временной логики. Выбранная за основу временная логика оказывает влияние как на выразительные возможности при написании правил, так и на производительность получающегося механизма .

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

2. Нечеткая временная логика реального времени Приведем основные определения используемые для построения нечеткой временной логики реального времени [Subhankar et al, 2013] .

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

Если ( ) и ( ) задают значения функций принадлежности для интервалов t t0 и t t0, то они могут быть выражены следующий образом:

() () {

–  –  –

В случае интервала, -,, - ( ) ( ) .

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

–  –  –

В данном случае ( ) означает изменение состояния утверждения B с 0 на 1, ( ) означает изменение состояния утверждения B с 1 на 0, ( ) означает любое изменение истинности B .

–  –  –

( )/ ( )

-( )( ))))) (, Другие логические операторы стандартной логики такие как или (), исключающее или (), импликация () выводятся аналогично тому, как это делается в классической нечеткой логике. Темпоральные операторы, такие как «в будущем» (F), «всегда» (G), и др., выводятся по аналогии с тем, как это сделано в работе [Alur 1996] при описании логики MITL .

Например:

( ) ( ( ) ( )) ( ( ( ))))

-( (, ) ( ) ( ( ) ) Алгоритмы вывода для нечеткой временной логики реального времени можно посмотреть в работе [Subhankar et al, 2013] .

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

–  –  –

Заключение Нечеткая временная логика реального времени обладает достаточной выразительностью для описания правил для систем промышленной автоматизации. Изначально разработанная специально для применения в составе встраиваемых систем (см. [Subhankar et al, 2013]) эта логика позволяет организовать быстродействующий и нересурсомкий механизм мониторинга для интеллектуальной распределенной системы управления крупными парковочными пространствами .

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

Список литературы [Alur, 1996] Alur R., Feder T., Henzinger T.A. The Benefits of Relaxing Punctuality // Journal of the ACM. 1996. 43. (1rst published in PODC'91) .

[Eremeev et ak, 2015] Kurilenko I.E., Varshavskiy P.R., Eremeev A.P. Temporal CaseBased Reasoning System for Automatic Parking Complex // International Journal of Computer, Electrical, Automation, Control and Information Engineering. 2015 .

Vol 2. №5 .

[Subhankar et al, 2013] Subhankar Mukherjee, Pallab Dasgupta A fuzzy real-time temporal logic // International Journal of Approximate Reasoning. 2013. Vol. 54, Iss. 9 .

[Борисов и др., 2005] Борисов А.В., Куриленко И.Е. О современных подходах к построению систем учета автотранспорта. Программные и аппаратные средства. // Информационные технологии моделирования и управления. 2005. № 5 .

[Еремеев и др., 2007] Еремеев А.П., Куриленко И.Е. Реализация механизма временных рассуждений в современных интеллектуальных системах // Известия РАН. Теория и системы управления. 2007. № 2 .

[Еремеев и др., 2010] Еремеев А.П., Куриленко И.Е. Средства темпорального вывода для интеллектуальных систем реального времени / Интеллектуальные системы. Коллективная монография. Вып. 4. – М.: Физматлит, 2010 .

УДК 004.838.3:004.827

ПРИМЕНЕНИЕ НЕЧЕТКИХ МУЛЬТИМНОЖЕСТВ

ДЛЯ ОЦЕНКИ БЛИЗОСТИ ПРЕЦЕДЕНТОВ 1

–  –  –

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

Ключевые слова: прецедентный подход, нечеткие мультимножества, оценка близости, метрика Введение Для решения широкого круга задач, связанных с получением решений на основании ранее накопленного опыта и знаний, может быть применен прецедентный подход [Aamodt at el., 1994; Берман и др., 2015; Николайчук и др., 2009]. В результате проведенного аналитического обзора было отмечено, что в рамках данного подхода экспертные знания описываются четкими понятиями, соответственно для вывода новых знаний используются разнообразные методы обработки точных знаний, которые могут быть как числовыми, так и вербальными .

Для представления нечеткости в знаниях экспертов Л. Заде был предложен аппарат нечетких множеств, который активно развивается и применяется при решении различных задач. В работах [Yager, 1986: Yager 1987] было введено понятие «fuzzy bag» (нечеткий портфель), которое позволяет обобщать различные мнения относительно нечетко заданных Работа выполнена при частичной финансовой поддержке РФФИ (проект №15-07-05641) .

разнородных характеристик объектов. Позже были введены понятия «multi-fuzzy set» [Syropoulos, 2001], «fuzzy multiset» [Miyamoto, 1997]. Многообразие терминов связано с наличием различных подходов к формализации структуры мультимножеств. Среди российских исследователей используется термин «нечеткое мультимножество» [Петровский, 2003] .

В настоящее время задача выбора конструкционных материалов решается либо «по аналогии» [Машиностроение, 2004], либо по описанию эксплуатационных и технологических свойств материала [Справочник, 2005], либо методом экспертного оценивания [Машиностроение, 2004] с дальнейшим применением методов многокритериальной оптимизации. В работе [Берман и др., 2015] для решения задачи предложено совместно использовать прецедентный подход и методы группового многокритериального выбора для упорядочения извлеченных прецедентов-аналогов. Следует отметить, что во всех вышеперечисленных работах экспертные знания представлены точными значениями (числовыми или вербальными) .

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

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

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

Обозначим через A = (A1, A2, …, AN) множество всех возможных конструкционных материалов, из которых необходимо выбрать вариант (или несколько вариантов), расположенных на минимальном расстоянии от заданной цели и имеющихся условий (ограничений). В процессе выбора необходимо учитывать оценки материалов по набору параметров (критериев) C = (C1, C2,…,CM) .

Для решения поставленной задачи предлагается применить: рассуждения на основе прецедентов (case-based reasoning) [Aamodt at el., 1994], что обеспечит поиск и извлечение материалов, подходящих под определенные условия функционирования (эксплуатации); модель представления экспертных знаний в виде нечетких мультимножеств и методы оценивания расстояний от заданной ситуации до имеющихся прецедентов [Miyamoto, 2008] для выявления наиболее походящих в заданной ситуации конструкционных материалов .

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

Ниже приведен фрагмент описания прецедента:

–  –  –

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

Все прецеденты в базе (библиотеке) прецедентов индексируются [Николайчук и др., 2009] .

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

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

1.2. Нечеткие мультимножества Первые работы, содержащие понятие нечетких мультимножеств (fuzzy bags), были опубликованы в 1986 году Ягером [Yager, 1986]. Последующие исследования в данном направлении связаны с расширением области применения (практических приложений) и определением новых операций и метрик в пространстве нечетких мультимножеств [Miyamoto, 2008;

Syropoulos, 2001; Rocacher, 2003; Петровский, 2003; Тарасов, 2008] .

Существуют различные подходы к определению понятия нечеткого мультимножества [Miyamoto, 2008; Yager,1986; Сенько, 2012]. В общем виде нечеткое мультимножество определяется следующим образом .

Рассмотрим универсальное множество X, на котором для каждого элемента xi X определена вероятность его принадлежности in некоторому нечеткому множеству Bi :

–  –  –

2. Пример совместного использования прецедентного подхода и нечетких мультимножеств

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

–  –  –

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

База прецедентов содержит описание материалов [Кузнецова и др., 1999; Справочник, 2005] и технологических условий их эксплуатации .

Технологические требования в прецеденте описываются в виде лингвистических переменных и их значений: расчетная нагрузка – низкая (менее 150 МПа), средняя (150-300 МПа), высокая (более 300 МПа); расчетная температура – низкая (менее 1500С), средняя (150–3500С), высокая (более 3500С); среда – слабощелочная (менее 7–8 pH), среднещелочная (8– 12 pH), сильнощелочная (более 12 pH). На рис. 1 показаны функции принадлежностей лингвистических переменных, а в табл. 1 приведено описание рассматриваемой ситуации .

В соответствии с табл. 1 по прецедентам–аналогам P1, P2 можно построить мультимножества следующего вида:

P1= ((1*нз, 2*ср, 0*вс)/С1, (0*нз, 3*ср, 0*вс)/С2, (0*сл-щ, 3*ср-щ, 0*слн-щ)/С3, A1);

P2= ((0*нз, 1*ср, 1*вс)/С1, (0*нз, 2*ср, 0*вс)/С2, (0*сл-щ, 1*ср-щ, 1*слн-щ)/С3, A2) .

Для сравнения осуществим оценку близости на основе метрик расстояния между нечеткими мультимножествами и нечеткими множествами .

Например, в качестве метрики определения расстояния между нечеткими прецедентами возьмем метрику Хэмминга:

d FS Pi, Pj inm jnm .

nm

–  –  –

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

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

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

Список литературы [Aamodt at el., 1994] Aamodt A., Plaza E. Case-based reasoning: Foundational issues, methodological variations, and system approaches // AI Communications. 1994 .

Vol. 7. No. 1 .

[Miyamoto, 1997] Miyamoto S. Fuzzy multisets with infinite collections of memberships // In Proc.of the 7th International Fuzzy Systems Association World Congress (IFSA 1997), Prague, Chech. 1997. Vol. 1 .

[Miyamoto, 2008] Miyamoto S. Fuzzy Bags: Theory and Applications toward a Model of Uncertainty and Clustering // Proc. International Symposium on Management Engineering, Japan, 2008 .

[Syropoulos, 2001] Syropoulos A. Mathematics of Multisets // Multiset Processing .

Lecture Notes in Computer science. Vol. 2235. – Berlin: Springer Verlag, 2001 .

[Rocacher, 2003] Rocacher D. On FuzzyBags and Their Application to Flexibile Querying // Fuzzy Sets and systems. 2003. Vol. 140 .

[Yager, 1986] Yager R. On the Theory of Bags // International Journal of General Systems. 1986. Vol. 13 .

[Берман и др., 2015] Берман А.Ф., Малтугуева Г.С., Юрин А.Ю. Поддержка принятия решений при выборе конструкционных материалов для обеспечения безопасной эксплуатации оборудования // Заводская лаборатория. Диагностика материалов. 2015. №11 (81) .

[Кузнецов и др., 1999] Сосуды и трубопроводы высокого давления: Справочник под редакцией А.М. Кузнецова и В.И. Лившица. 2-е изд. – Иркутск: Типография №1, 1999 .

[Машиностроение, 2004] Машиностроение. Энциклопедия / Ред. совет:

К.В. Фролов (пред.) и др. – М.: Машиностроение. Машины и аппараты химических производств. Т. IV-12 / М.Б. Генералов и др., 2004 .

[Николайчук и др., 2009] Николайчук О.А., Юрин А.Ю. Применение прецедентного подхода для автоматизированной идентификации технического состояния деталей механических систем // Автоматизация и современные технологии. 2009. №5 .

[Петровский, 2003] Петровский А.Б. Основные понятия теории мультимножеств. – М.: Едиториал УРСС, 2003 .

[Сенько, 2012] Сенько А.Е. Моделирование конечных нечетких структур мультимножеств // Компьютерная математика. 2012. №2 .

[Справочник, 2005] Справочник по конструкционным материалам: Справочник/ Б.Н. Арзамасов и др.; под ред. Б.Н. Арзамасова. – М.: МГТУ им Н.Э. Баумана, 2005 .

[Тарасов, 2008] Тарасов В.Б. От параметризированных нечетких множеств к нечетким мультимножествам уровня // Нечеткие системы и мягкие вычисления .

Сб. науч. тр. II Всеросийской науч. конф. – Ульяновск: УлГТУ, 2008 .

УДК 331.101:331.5:510.64

НЕЧЕТКАЯ ОЦЕНКА КОНКУРЕНТОСПОСОБНОСТИ

ВЫПУСКНИКОВ ВЫСШИХ УЧЕБНЫХ ЗАВЕДЕНИЙ1

Н.Ю. Мутовкина (letter-boxNM@yandex.ru) Б.В. Палюх (boris@tstu.tver.ru) А.Ю. Клюшин (klalex@inbox.ru) Тверской государственный технический университет, Тверь В статье рассматривается модель нечеткой оценки конкурентоспособности выпускников современных высших учебных заведений. В основе модели находится нечеткий вывод относительно представлений о соответствии подготовки студентов ожидаемым результатам со стороны работодателей. Модель может быть применена для оптимизации образовательных программ высшего образования с целью сокращения разрыва между результатами подготовки студентов и результатами, которые хотят получить потенциальные работодатели .

Ключевые слова: нечеткая логика, конкурентоспособность выпускника, рынок труда, нечеткий вывод, образовательная программа Введение В настоящее время одним из приоритетных направлений деятельности любой образовательной организации, особенно – высшего учебного заведения (ВУЗа) является подготовка высококвалифицированных личностей, которые смогут в дальнейшем обеспечить достойную жизнь как для себя, так и для своих близких, а также внести положительный вклад в развитие экономики в целом. В российской системе высшего образования сейчас как никогда обострились конкуренция и соперничество, очевидна тенденция сокращения ВУЗов. Поэтому каждый ВУЗ, стремящийся занять выгодное положение на рынке образовательных услуг, должен прислушиваться к мнениям потенциальных работодателей и готовить студентов в соответствии с их требованиями. Уровень востребованности выпускников выступает одним из ключевых показателей, определяющих рейтинг учебного заведения в условиях все возрастающей конкуренции [ARES, 2016] .

Работа выполнена при финансовой поддержке РФФИ (проект № 15-01-05545) .

Таким образом, актуальность рассматриваемой темы состоит также в том, что конкурентоспособность ВУЗа можно оценить через конкурентоспособность его выпускников. Для наиболее достоверной оценки конкурентоспособности выпускников ВУЗов как нельзя лучше подходят методы нечетких множеств и нечеткой логики. На основе понятий, представимых нечеткими множествами, можно интерпретировать человеческие суждения, которые далее можно применить для моделирования и прогнозирования конкурентоспособности выпускников. Каждому человеку удобнее применять качественные нечеткие оценки, например: «низкий или высокий уровень подготовки», «высокая квалификация», «недостаточный уровень знаний», «высокая степень риска» и т.п. Функция принадлежности для каждого нечеткого множества определяется субъективно. В данном случае вид функции принадлежности нечеткого множества «КОНКУРЕНТОСПОСОБНЫЕ ВЫПУСКНИКИ» отражает точку зрения независимого эксперта с учетом статистических данных относительно трудоустройства выпускников ВУЗов из перечня [ARES, 2016] и отзывов представителей крупных и средних как российских компаний, так и зарубежных фирм .

1. Факторы конкурентоспособности выпускников ВУЗов Конкурентоспособность выпускника – это свойство выпускника, объединяющее его знания, умения и навыки, а, следовательно, и компетенции, что позволяет удовлетворять потребности рынка труда лучшим образом по сравнению с другими выпускниками. Конкурентоспособность выпускника определяет его способность выдерживать конкуренцию по сравнению с другими выпускниками в конкретном секторе рынка труда. По результатам исследований, как проведенных авторами на примере Тверского региона, так и по результатам обзора Российских Интернетисточников, содержащих информацию о предпочтениях и представлениях работодателей о современных выпускниках, например [Портал Superjob.ru, 2016], основные компоненты модели конкурентоспособности выпускника представлены в табл. 1 .

Как видно из табл.1, представления друг о друге у работодателей и выпускников ВУЗов существенно различаются. В опросе принимали участие 1 000 российских компаний – потенциальных работодателей и 1 600 студентов старших курсов и выпускников ВУЗов. Студенты и выпускники выбрали три самых важных для критерия, которыми они руководствуются при выборе постоянной работы; кроме того, они должны были назвать три главных критерия, на которые, по их мнению, чаще всего обращают внимание компании при приеме на работу недавних студентов. Рекрутеры отвечали на обратные вопросы: что для них важно при найме молодых специалистов и чем руководствуется молодежь при выборе места работы .

Табл. 1 .

Ожидания работодателей от выпускников и представления ожиданий работодателей студентами и выпускниками,(в % от числа опрошенных) Представления Критерии оценки № Ожидания ра- выпускников об Лингвистическое Условное п/п ботодателей ожиданиях рабоописание обозначение тодателей 1 Мотивация к работе k1 65 33 Готовность к обучению и 2 дальнейшему личностно- k2 60 42 му развитию Активная жизненная поk3 зиция Общий уровень образо- k4 ванности, культуры Уровень знаний (теоретиk5 ческая подготовленность) 6 Авторитетность ВУЗа k6 16 23 Соответствие корпоративk7 ной культуре компании 8 Опыт работы k8 10 58 Результаты внутреннего k9 тестирования 10 Желаемое вознаграждение k10 8 10 11 Средний балл диплома k11 5 5 Индексы критериев указывают на их приоритетность для работодателя .

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

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

Дерево целей предназначено для задания связей между истоками и целевой вершиной (рис. 1). Истоками в данном случае будут критерии оценки конкурентоспособности выпускника из табл. Истокам соответствуют значения: k1 – есть, нет; k 2 – есть, нет; k 3 – да, нет; k 4 – низкий, средний, высокий; k5 – низкий, средний, высокий; k 6 – низкая, средняя, высокая (для сравнения на международном уровне: категория A, B, C или D); k 7 – готов соответствовать, не готов соответствовать; k 8 – есть, нет;

k9 – удовлетворительные, неудовлетворительные; k10 – адекватное, завышенное; k11 – удовлетворительно, хорошо, отлично .

Целевая вершина – «Оценить конкурентоспособность выпускника»

имеет три возможных значения: «не конкурентоспособен», «средняя конкурентоспособность», «вполне конкурентоспособен» .

Количество правил в БЗ называется мощностью базы и может быть рассчитано по дереву целей:

n БЗ xi, (2.1) i 1 где x i – число всех возможных вариантов по каждому критерию (вершине); n – число вершин .

Для структуры дерева целей на рис. 1, мощность БЗ равна:

БЗ 2 2 2 3 3... 2 3 10368 правил. Для сокращения числа правил можно ввести промежуточные вершины. Из анализа дерева целей на рис. 1 видно, что вершины k1, k 2 и k 3 логически описывают личностный аспект конкурентоспособности выпускника, поэтому их можно объединить общей вершиной «Личностные качества» с возможными значениями: не развиты, средне развиты, хорошо развиты. Вершины k 4, k5 и k11 можно объединить вершиной «Уровень образования», значения которого: низкий, средний, высокий (рис. 2) .

Рис. 1. Дерево целей для БЗ «Оценить конкурентоспособность выпускника»

Рис. 2. Дерево целей с промежуточными вершинами

–  –  –

Все решения определяются экспертами, составляющими БЗ. При этом, как правило, всегда актуально применение процедур согласования экспертных оценок (решений), представленных, например, в [Мутовкина и др., 2010], [Коновалова и др., 2011]. Если анализ выдвинутых положений приводит к выводу об избыточности дерева решений, то лишние варианты (тавтологии) можно исключить из БЗ, отсекая ветви в дереве решений .

Далее строится дерево правил, предназначенное для отображения всех правил БЗ. Если для БЗ дерево решений было сокращено, то в дереве правил появятся правила, к которым присоединяются не все истоки .

Лингвистические значения критериев представимы числовыми значениями из отрезка [0, 1], которые являются их функциями принадлежности. Нечеткое множество «КОНКУРЕНТОСПОСОБНЫЕ ВЫПУСКНИКИ», несмотря на размытость границ, может быть точно определено сопоставлением каждому значению, получаемому посредством нечеткого логического вывода, числа из отрезка [0, 1], которое представляет его принадлежность к заданному множеству .

Например, есть шесть выпускников, конкурентоспособность которых определена множеством:

ВЫПУСКНИКИ x1 / 0, 2; x2 / 0, 6; x3 / 0, 45; x4 / 0,85; x5 / 0, 73; x6 / 0, 65,

КОНКУРЕНТОСПОСОБНЫЕ

x4 / 0,85; x5 / 0, 73 .

тогда множество ВЫПУСКНИКИ Продукционная модель позволяет имитировать поведение человека при решении неформализованных или слабо формализованных задач. Подобно знаниям в долговременной памяти продукционные правила не изменяются при решении задачи. Новые правила могут быть просто добавлены в БЗ, если возникнет такая необходимость. Примерами продукций, представленных на рис. 3, могут служить следующие выражения:

П1: Если личностные качества не развиты, то выпускник не конкурентоспособен .

П2: Если личностные качества хорошо развиты и уровень образования высокий и авторитетность ВУЗа высокая и выпускник готов соответствовать корпоративной культуре компании и он имеет опыт работы и результаты его внутреннего тестирования удовлетворительны и желаемое вознаграждение адекватное или неадекватное, то выпускник конкурентоспособен .

Помимо продукционных правил БЗ также содержит факты – простые утверждения, например: «выпускник должен соответствовать корпоративной культуре компании при поступлении на работу». Факты поступают в ЭС через интерфейс пользователя или выводятся при поиске решения задачи. Факты, являясь истинными утверждениями, копируются в рабочую память для применения в цикле распознавание – действие. Последовательная активация правил порождает цепочку нечеткого вывода относительно представлений о соответствии подготовки студентов ожиданиям потенциальных работодателей .

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

Список литературы [Коновалова и др., 2011] Коновалова А.С., Мутовкина Н.Ю. Проектирование предметно-деятельностной структуры содержания образования на примере высшего экономического образования // Системы управления и информационные технологии. 2011. № 2 (44) .

[Мутовкина и др., 2010] Мутовкина Н.Ю., Павлов В.А. Метод формирования активной системы по принятию управленческих решений на промышленных предприятиях // Вестник Тверского государственного университета: научный журнал. Серия «Прикладная математика». – Тверь: ТвГУ, 2010. № 9 .

[Портал Superjob.ru, 2016] Работодатели не понимают поколение «Y»: статья от 26.06.2015 г. / Исследовательский центр портала Superjob.ru [Электронный ресурс]. URL: http://www.superjob.ru/research/articles/111816/rabotodateli-neponimayut-pokolenie-y/ (дата обращения: 02.03.2016 г.) .

[ARES, 2016] Academic Ranking of World Universities – European Standard ARESЭлектронный ресурс] URL: http://eurochambres.org/ares-2016/russianfederation/ (дата обращения: 10.05.2016 г.) .

УДК 004.832

СПОСОБ РАСПРЕДЕЛЕНИЯ ЛОГИСТИЧЕСКИХ

ЗАКАЗОВ НА ОСНОВЕ АЛГОРИТМА

ГЕНЕТИЧЕСКОЙ КЛАСТЕРИЗАЦИИ

–  –  –

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

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

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

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

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

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

1. Зональное разбиение территории для распределения логистических заказов на основе алгоритма генетической кластеризации В последнее время все большую популярность среди транспортных компаний, служб такси и других организаций, обладающих собственным автопарком, приобретают системы GPS | ГЛОНАСС слежения за автомобилями. Это система слежения, позволяющая контролировать любые перемещения транспорта при помощи спутниковой навигационной системы GPS или ГЛОНАСС. GPS мониторинг транспорта позволяет узнать точное местоположение машины, подсчитать ее пробег или простои, вычислить маршрут движения. В свою очередь зональное разбиение территории позволяет оптимально использовать имеющиеся рабочие ресурсы, сократить расходы на горюче-смазочные материалы, повысить дисциплину среди водителей, уменьшить время подъезда к заказам и многое другое, что положительно сказывается на эффективности работы всего автопарка .

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

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

Рассмотрим процедуру зонального разбиения территорий на основе алгоритма генетической кластеризации:

Шаг 1. Задание целевой функции (приспособленности) для особей популяции .

Шаг 2. Создание начальной популяции (с использованием алгоритма k-средних формируется заданное число кластеров – зон) .

Шаг 3. Скрещивание (оно представлено обменом домами, находящимися на границе смежных между собой зон, что приводит к «плавному»

изменению границ зон) .

Шаг 4. Мутация (произвольный переход одного или нескольких, находящихся на границе, домов из одной смежной зоны в другую) .

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

Шаг 6. Формирование нового поколения (селекция зон с лучшими значениями целевой функции) .

Шаг 7. Если критерий остановки алгоритма не удовлетворен, то возврат к шагу 3 .

Условиями остановки являются:

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

достижение разницы между значениями целевых функций смежных зон меньше заданной [Гладков и др., 2010] .

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

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

уменьшается трудоемкость расчетов по сравнению с алгоритмами формального элемента и k-средних [Воронцов, 2008];

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

сочетаются достоинства алгоритмов кластеризации и генетических алгоритмов .

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

2. Распределение логистических заказов на основе предлагаемого способа При реализации подхода без разделения территории на зоны, как правило, используется алгоритм Куна или венгерский метод. Однако их вычислительная сложность составляет O(nm), где n – количество заказов, а m – количество транспортных средств [Сонькин, 2009] .

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

Задача распределения заказов на обслуживание клиентов использует представление в виде двудольного графа G = (Z, A), где Z {z1,..., zn } – множество поступающих заказов и A {a1,..., am } – множество транспортных средств, готовых их выполнить, а Y { yij }, i 1, n, j 1, m – множество ребер, связывающих вершины из множества Z c вершинами множества A .

В соответствии с алгоритмом Куна при распределении заказов необхоm n димо из всего множества возможных заказов iZ или jA j 1 i 1 выбрать такую совокупность паросочетаний (заказ–автомобиль), которая в наилучшей степени удовлетворяла бы заданному интегральному критерию эффективности kij K, который может быть поставлен в соответствие каждому ребру из Y. При этом kij f (kij, kij,..., kijp ), где p – число локальных весовых коэффициентов, таких как: удаленность от места назначения, тип автомобиля, процент выполнения дневного плана, тип клиента, дополнительные требования клиента к характеристикам автомобиля (наличие детского кресла, большой багажник и т.д.) и другие .

Таким образом, задача распределения заказов в каждой зоне сводится к нахождению оптимального паросочетания вершин множества Z с вершинами множества A так, чтобы каждой вершине z i соответствовала только одна вершина a j и наоборот .

При этом необходимо распределить полученные заказы (множество Z) между транспортными средствами таким образом, чтобы достичь максимальной эффективности F при их выполнении:

n m F ki, j xi, j max, i 1 j 1

–  –  –

где ki, j – интегральный критерий эффективности, учитывающий p весовых локальных коэффициентов для i-го водителя при выполнении j-го заказа;

xi, j – элемент искомой матрицы назначений. Интегральный критерий эффективности отображает предпочтительность выполнения i-ым водителем j-го заказа, он рассчитывается с помощью метода парных сравнений Терстоуна. С привлечением экспертов производится ранжирование компонентов критерия эффективности по предпочтительности. К таким компонентам относятся: удаленность от заказа, соответствие типа автомобиля и его характеристик требованиям клиента, процент выполнения дневного плана, наличие выполняемого заказа, километраж холостого пробега. Такие показатели, как удаленность от заказа и километраж холостого пробега рассчитываются с помощью координат, получаемых в режиме реального времени от систем GPS | ГЛОНАСС, установленных в автомобилях .

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

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

На рис. 1 представлен «каркас» предлагаемого способа распределения заказов. К набору компонентов критериев отбора относится расширенная, по сравнению с [Сонькин, 2009], совокупность характеристик транспортных средств и окружающей обстановки .

–  –  –

Оценка изменения времени подъезда транспортного средства с учетом зонального разбиения территории на основе предлагаемого алгоритма генетической кластеризации проводилась для каждой зоны путем сопоставления расчетного времени подъезда к заказу и времени, реально затраченному при подъезде к заказу на примере одной из служб такси г. Смоленска. В табл.1 представлены средние оценки изменения эффективности зонального разбиения территорий при использовании предлагаемого способа, позволяющие сделать вывод о целесообразности предварительного зонального разбиения территории на основе разработанного алгоритма генетической кластеризации. При этом «цепочка» критериев для каждого транспортного средства своя, что позволяет распараллелить вычисления для каждой зоны и, тем самым повысить оперативность распределения заказов в среднем на 20% .

–  –  –

Заключение В работе предложен способ распределения логистических заказов .

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

Список литературы [Воронцов, 2008] Воронцов К.В. Лекции по алгоритмам кластеризации и многомерного шкалирования. 2008. – http://www.ccas.ru/voron/download/Clustering.pdf .

[Гладков и др., 2010] Гладков Л.А., Курейчик В.В., Курейчик В.М. Генетические алгоритмы / Под ред. В.М. Курейчика. 2-е изд., исправл. и доп. – М.: Физматлит, 2010 .

[Рязанов и др., 2014] Рязанов А.В., Борисов В.В. Зональное разбиение территории на основе алгоритма генетической кластеризации // Энергетика, информатика, инновации-2014 – ЭИИ-2014. Т. 2. – Смоленск: Универсум, 2014 .

[Сонькин, 2009] Сонькин Д.М. Адаптивный алгоритм распределения заказов на обслуживание автомобилями такси // Известия Томского политехнического университета. 2009. Т. 315. №5 .

УДК 004.891 + 311.2

СТРУКТУРНЫЙ СИНТЕЗ

БАЙЕСОВСКОЙ СЕТИ ДОВЕРИЯ

ПО ПУАССОНОВСКОЙ МОДЕЛИ ПОВЕДЕНИЯ1

–  –  –

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

Проведено сравнение двух структур такой модели:

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

Ключевые слова: моделирование поведения, байесовские сети доверия, синтез структур, оценка интенсивности, рискованное поведение Введение Во многих задачах, например, в психологии, социологии, эпидемиологии, необходимо измерять параметры поведения индивида [Афанасьев, 2006; Leigh et al., 1993; Азаров и др., 2012]. Одним из подобных примеров является оценивание риска передачи или получения ВИЧ-инфекции на основе данных о числе эпизодов рискованного поведения (употребление инъекционных наркотиков, рискованное сексуальное поведение) [Lemelin et al., 2014]. Однако, применение прямых методов (то есть непосредственное измерение числа эпизодов) часто невозможно, что требует развития косвенных методов оценки [Graham et al., 2003; Bolger et al., 2003] .

Статья содержит материалы исследований, частично поддержанных грантами РФФИ 16-31-60063-мол_а_дк, 16-31-00373-мол_а .

В работах [Суворова, 2013, Суворова и др., 2014] предложен подход к построению байесовской сети доверия для моделирования рискованного поведения на основе данных о нескольких последних эпизодах такого поведения. Байесовские сети доверия позволяют представить сложные взаимосвязи между элементами, входящими в модель, в виде разложения на более простые элементы, что упрощает как описание всей системы, так и ее интерпретацию [Тулупьев и др., 2006; Pearl, 2000; Neapolitan, 2003], в то время как выводы делаются с учетом полной системы. Кроме того, аппарат байесовской сети доверия позволяет учитывать как имеющиеся статистические данные, так и экспертную информацию об интересующей исследователя области [Тулупьев и др., 2006; Pearl, 2000, Neapolitan, 2003].

Причем, уровень вовлечения экспертов может быть очень разным:

от выбора методов, используемых для построения модели до полного задания модели, включая ее структуру и параметры [Mkrtchyan et al., 2015, Trucco et al, 2008, Constantinou et al., 2016, Du et al., 2015] .

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

1. Описание модели Как уже было отмечено, в качестве исходных данных для вычисления оценки интенсивности рискованного поведения было предложено [Тулупьева и др., 2008] использовать сведения о трех последних эпизодах поведения t01, t12, t23 (точнее – длины интервалов между этими эпизодами) и сведения о минимальном и максимальном интервале ( tmin и tmax ) между эпизодами за исследуемый промежуток времени. Моделью поведения выступает пуассоновский случайный процесс, то есть длины интервалов между эпизодами распределены экспоненциально. Кроме того, модель содержит также оцениваемую величину, соответствующую интенсивности поведения, и скрытую переменную n – число эпизодов, произошедших за исследуемый промежуток времени .

Для построения байесовской сети возможные значения всех непрерывных величин (, t01, t12, t23, tmin, tmax ) разбиваются на дискретные интервалы; таким образом, распределения являются мультиномиальными. Во всех примерах, рассмотренных в данной работе, используется дискретизация вида: для случайной величины, (1) 0;0, 01, соответствующей интенсивности поведения (2) 0,01;0,03, (3) 0, 03;0, 05, (4) 0, 05;0,1, (5) 0,1;0, 2, (6) 0, 2;0,3, (7) 0,3;0,5, (8) 0,5;0, 7, (9) 0, 7;1, (10) 1; ; для случайных величин t j, j 1, tmin, tmax, характеризующих длины интервалов между эпизодами, t (1) 0;0,1, t (2) 0,1;1, t (3) 1;7, t (4) 7;30, t (5) 30;180, t (6) 180; .

В первоначальной модели, предложенной в [Суворова, 2013], экпертно задана структура (рис.1), а тензоры условной вероятности, характеризующие переходы между узлами сети, определяются аналитически, согласно предположению о пуассоновском процессе в качестве модели поведения. Формулы представлены в [Суворова и др., 2014] .

Рис. 1. Структура БСД для моделирования рискованного поведения, заданная экспертно Однако в данной работе кроме предложенной структуры также исследуется структура, полученная автоматически по данным, описание которых приведено в следующем разделе. Таблицы условных вероятностей также вычисляются на основе данных. Все вычисления и анализ выполнены с помощью языка R [RProject, 2016], в частности, для работы с байесовскими сетями использовался пакет bnlearn [Scutari, 2009] .

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

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

Далее для каждого значения интенсивности генерируется 20 «респондентов» – последовательностей точек, расстояния между которыми подчиняются экспоненциальному распределению с соответствующим значением интенсивности. Из каждой такой последовательности выделяются исходный данные для оценки: длины интервалов между тремя последними точками, минимальный и максимальный интервал за промежуток длиной 365 «дней», удаляются последовательности, у которых нет хотя бы двух точек за этот промежуток. Таким образом, конечный обучающий набор включает 5936 «респондентов», причем для каждого дополнительно известно исходное значение интенсивности, что позволяет сравнить его с итоговой оценкой .

Аналогичным образом были сгенерированы тестовые данные для дальнейшей оценки построенных моделей (50 значений интенсивности, 15 последовательностей для каждого значения, всего 730 «респондентов») .

3. Обучение структуры БСД по данным Для построения структуры байесовской сети доверия по сгенерированным данным был использован алгоритм оптимизации меры качества сети Hill-Climbing (HC) [Scutari, 2009], мерой качества являлся BIC (Bayesian Information Criterion) .

Полученная в результате обучения структура байесовской сети доверия представлена на рис. 2 .

Рис.2. Структура БСД для моделирования рискованного поведения, обученная на данных Следует отметить, что данная структура имеет достаточно простую интерпретацию: интенсивность поведения (другими словами – частота поведения) определяется через число эпизодов поведения, произошедших за рассматриваемый промежуток времени (в текущем примере 365 дней) .



Pages:   || 2 | 3 |



Похожие работы:

«Вестник ТГПУ (TSPU Bulletin). 2018. 2 (191) ФУНКЦИОНАЛЬНАЯ СТИЛИСТИКА. КОММУНИКАТИВНАЯ СТИЛИСТИКА МЕДИАТЕКСТА УДК 81’42 DOI: 10.23951/1609-624X-2018-2-54-60 СОВРЕМЕННЫЕ ПОДХОДЫ К ИЗУЧЕНИЮ НАУЧНОГО ТЕКСТА Е. А. Баженова Пермский государственный национальный...»

«RU 2 421 403 C1 (19) (11) (13) РОССИЙСКАЯ ФЕДЕРАЦИЯ (51) МПК C01G 47/00 (2006.01) ФЕДЕРАЛЬНАЯ СЛУЖБА ПО ИНТЕЛЛЕКТУАЛЬНОЙ СОБСТВЕННОСТИ, ПАТЕНТАМ И ТОВАРНЫМ ЗНАКАМ (12) ОПИСАНИЕ ИЗОБРЕТЕНИЯ К ПАТЕНТУ (21)(22) Заявка: 2009140329/05, 02.11.2009 (72) Автор(ы): Палант Алексей Александрович (RU), (24) Дата начала...»

«ЛАБОРАТОРНОЕ ОБОРУДОВАНИЕ для контроля качества зерна, муки, кормов и пищевых продуктов 2018–2019 Уважаемые Дамы и Господа! Компания Лаборатория оборудования рада возможности предложить Вам широкий спектр лабораторного оборудования для решения ана...»

«ISSN 24101583 Министерство науки и высшего образования Российской Федерации Правительство Алтайского края Совет по вопросам реализации государственной национальной политики в Алтайском крае Алтайский государственный университет Факультет социологии Ресурсный центр по разв...»

«Теоретические и экспериментальные исследования УДК 81’27 DOI 10.30982/2077-5911-2018-37-3-22-35 ВЛИЯНИЕ ПСИХОЛОГИЧЕСКОГО ФАКТОРА НА ВИТАЛЬНОСТЬ ЯЗЫКА Кондрашкина Елена Алексеевна старший...»

«36 За период 1959—1989 гг. доля эстонцев в населении Эстонии снизилась с 75 до 61%, а латышей в населении Латвии — с 62 до 52%. По словам Кроуфорда Янга, "за немногими исключениями, международн...»

«Глава 23 Духовная жизнь России во второй половине XIX века § 1. Образование и наука Эпоха Освобождения дала сильный толчок культурному развитию России . Втягивание в рыночные отношения все более широких слоев крестьянства со всей остротой поставило вопрос о начальном народном обра...»

«ГУМАНИТАРНЫЕ НАУКИ Н.Н. ГАБДУЛОВА, Б.К. ЛИССОВ, III курс ФаИ СОВРЕМЕННОЕ ТВОРЧЕСТВО В ИНТЕРАКТИВНОМ ПРОСТРАНСТВЕ В данной работе рассматриваются особенности, характерные для современного творчества, вышедшего за пределы индивидуального. Также даются основные отличия нового творчества от прежних его форм....»

«УДК 316.624:364-212 Блинова и. Ю., магистрант крутько и. с., др психол. наук соЗдаНие ПревеНТолоГиЧескоГо ЦеНТра как средсТва ПоПУлЯриЗаЦии ПревеНТолоГии и ПроФессии ПревеНТолоГа 1 В статье проанализированы основные предпосылки для создания превентологического цент...»

«УДК 3 7 3. 167.1:514 ББК 22.151Я.721 Г 36 А та н а с я н Л. С., Б у ту з о в В. Ф., К а д о м ц е в С. Б., Ю д и н а И. И. Геометр и я . 7 к л асс. — М.: ФИЗМАТЛИТ, 2005. — 120 с. — ISBN 5-9221-0572-8. Настоящее издание является первой част...»

«УДК 32.019.51 ББК 66 КОНЦЕПЦИЯ КУЛЬТУРНОЙ ГЕГЕМОНИИ А. ГРАМШИ КАК МЕТОДОЛОГИЧЕСКАЯ ОСНОВА ИНФОРМАЦИОННОПСИХОЛОГИЧЕСКОЙ ВОЙНЫ Шевченко, М.А. студентка 4 курса, бакалавриат. ФГАОУ ВО Уральский федеральный университет имени первого Президента России Б.Н. Ельцина. г. Екатеринбург, Россия maria241120@mail.r...»

«Инструкции по эксплуатации и важная информация O-Box Интерфейс O-BoxB ЛИЦЕНЗИЯ НА ИСПО ЛЬЗОВАНИЕ ПРОГРАММНОГО ОБЕСПЕЧЕНИЯ КОНЕЧНЫМ ПОЛЬЗОВАТЕЛЕМ Программы O-Box Software Desktop и O-Box Software Mobile защищены законами об авторских правах...»

«ПЛАН МЕРОПРИЯТИЙ, приуроченных к Международному дню интеллектуальной собственности, проводимых в 2018 году в системе Роспатента и регионах Российской Федерации, с администрациями (правительст...»

«g-ae s оо шчч, оо CD CD О оiS IV) Ц CD 2 тз EPSON Фоторепродукционное качество печати струйных фотопринтеров Epson обеспечивается уникальной системой воспроизведения изображений PerfectPicture Imaging System, состоя...»

«1 ПРОЧИТАЙТЕ ДО ИСПОЛЬЗОВАНИЯ ПРИБОРА МЕТАЛЛОИСКАТЕЛЬ LETHRUS A1 ИНСТРУКЦИЯ ПО ПРИМЕНЕНИЮ МЕТАЛЛОИСКАТЕЛЯ WWW. LETHRUS. RU, TEL +7 (495) 795-82-81 Вы держите в руках интеллектуальный металлоискатель со множеством функций. Это одно из воплощений современной микропроцессорной техн...»

«Революционная разработка Днепропетровских ученых Что такое композит? Композиционный материал, или композит это вещество, состоящее из двух и более составляющих и обладающее новыми свойствами. Видов композитов много...»

«Материалы Х международной научно практической конференции Екатеринбург, 26 апреля 2018 г. Министерство образования и науки Российской Федерации ФГАОУ ВО "Уральский федеральный университет имени первого Президента России Б.Н.Ельцина" Интеллектуальная собственность и инновации Материалы X международ...»

«Новости Тихоокеанского Объединения,. Новости Тихоокеанского Объединения,. https://us9.admin.mailchimp.com/campaig. Ноябрьский выпуск новостей Объединения View this email in your browser Английская версия кликните здесь ЧИТАЙТЕ В ЭТОМ ВЫПУСКЕ. Н...»

«Инструкции по эксплуатации и важная информация O-Box Интерфейс O-BoxB ЛИЦЕНЗИЯ НА ИСПОЛЬЗОВАНИЕ ПРОГРАММНОГО ОБЕСПЕЧЕНИЯ КОНЕЧНЫМ ПОЛЬЗОВАТЕЛЕМ Программы O-Box Software Desktop и O-Box Software Mobile защищены зак...»

«I• -.-.,..)"Лг.а. АКАДЕМИЯ НАУК УКРАИНСКОЙ ССР ИТФ-89-82Р А.Г.Загородний, Г.М.Корчинский, И.II.Якименко ПОВЕРХНОСТНЫЕ ВОЛНЫ В ПОЛУПРОСТРАНСТВЕ И ОЖЖ НЕОДНОРОДНОЙ ПЛЛЗМН УДК 533,932 А.Г.Загородили, Г.М.Корчинск...»

«ZOOMIX СКАЧАЙТЕ БЕСПЛАТНО ПРИЛОЖЕНИЕ GEOPLANER Для быстрого перехода к загрузке приложения откройте страницу: wochi.ru/download или отсканируйте QR код . Скачайте бесплатное приложение geoplaner из AppStore или Google Play в зависимости от операци...»

«Европейский диалог по модернизации с беларусским обществом: актуальное состояние и проблемы развития Policy paper Андрей Егоров © Центр европейской трансформации, 2013. Центр европейской трансформации разрешает свободное...»

«Данный файл является фрагментом электронной копии издания, опубликованного со следующими выходными данными: УДК 338.5 ББК 65.9 (2Р)-86 К 142 Рецензенты: А.Т. Юсупова – д.э.н., профессор, ИЭОПП СО РАН Н.А. Кравченко – д.э.н., профессор, ИЭОПП СО РАН И.В. Князева – д.э.н., профессор, Сибирский институт управления – филиал РАНХиГС Каза...»







 
2019 www.librus.dobrota.biz - «Бесплатная электронная библиотека - собрание публикаций»

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