Содержание к диссертации
Введение
1. Анализ состояния теории и практики создания интеллекту альных систем поддержки принятия решении (ИСППР) в трудно формализуемых задачах 19
1.1. Проблемы формализации поиска и принятия решений в ИСППР 19
1.2. Подходы к решению трудно формализуемых задач на основе систем обработки знаний 23
1.2.1. Характеристика трудно формализуемой задачи и пути ее решения 23
1.2.2. Методы решения трудно формализуемых задач с помощью классических систем искусственного интеллекта 25
1.2.3. Нейросетевой подход к решению трудно формализуемых задач 34
1.2.4. Проблемы создания гибридных моделей 37
1.3. Принципы построения программного обеспечения ИСППР 45
1.4. Обзор программных средств и технологий для организации поиска решений 47
1.4.1. Не йр о сете вые пакеты 47
1.4.2. Пакеты на основе нечеткой логики 54
1.4.3. Программные продукты для генетических алгоритмов 57
1.4.4. Опыт использования интеграции программных средств для построения гибридных моделей 59
1.5. Обзор программных средств для анализа решений методами моделирования 62
1.5.1. Программные среды для моделирования компьютерных сетей 64
1.5.2. Моделирующие системы 69
1.6. Задачи исследования 71
1.7. Выводы 77
2. Организация нейросстевых баз знаний в ИСППР 80
2.1. Особенности формирования нейросетевой базы знаний 80
2.2. Алгоритмы обработки исходной информации для формирования обучающих выборок 82
2.3. Синтез нейронной сети для решения прикладных задач 89
2.3.1. Выбор типа НС 90
2.3.2. Влияние алгоритма обучения на эффективность НС 97
2.3.3. Проблемы формирования топологии НС 106
2.3.4. Постановка задачи синтеза нейронной сети 115
2.4. Принципы организации нейросетевой базы знаний 116
2.5. Задача интерпретации результатов работы нейронной сети в ИСППР и ее решение 122
2.6. Выводы 126
3. Разработка методов и алгоритмов настройки и адаптации нейронных модулей к решаемой задаче 130
3.1. Проблемы создания генетических алгоритмов для решения задач адаптации и настройки НС 130
3.1.1. Кодирование потенциальных решений 132
3.1.2. Разработка и исследование генетических операторов 135
3.1.3. Разработка новых операторов селекции хромосом 138
3.1.4. Механизм фильтрации хромосом 140
3.1.5. Разработка способов задания функций качества хромосом. 143
3.1.6. Разработка и оценка качества многопопуляционного алгоритма 146
3.2. Алгоритм обучения НС на основе генетического алгоритма и его оценка 150
3.2.1. Экспериментальное исследование генетического алгоритма для построения эффективного алгоритма обучения НС 150
3.2.2. Разработка и исследование двухэтапного алгоритма оптимизации на основе генетического алгоритма 166
3.2.3. Построение генетического алгоритма с помощью генетического алгоритма , 168
3.2.4. Генетический алгоритм обучения нейронной сети 173
3.3. Алгоритмы настройки НС на решаемую задачу 178
3.3.1. Модификация конструктивного метода формирования топологии НС 179
3.3.2. Формирование топологии нейронных сетей с помощью генетического алгоритма 182
3.3.3. Экспериментальное исследование алгоритмов формирования топологии нейронных сетей 186
3.4. Выводы 190
4. Методы повышения эффективности использования пейросетевых и гибридных технологий в ИСППР 193
4.1. Повышение вычислительной эффективности алгоритмов обучения многослойного персептрона 193
4.1.1. Использование нечеткой логики для регулирования скорости обучения МНС 193
4.1.2. Комбинированный алгоритм обучения МНС с использованием ГА и имитации отжига 200
4.1.3. Сравнительный анализ нейросетевых классификаторов на основе МНС 205
4.1.4. Решение задачи автоматизации останова обучения МНС .212
4.1.5. Пример применения многослойного персептрона к выбору параметров компьютерной сети 216
4.2. Повышение скорости сходимости самоорганизующейся сети Кохонена 223
4.3. Развитие нечеткой нейронной сети Кохонена для повышения скорости обучения и качества распознавания. 230
4.4. Повышение качества и уменьшение трудоемкости вывода решений на основе нейросетевых нечетких моделей 237
4.5. Выводы 244
5. Анализ и оценка решений с помощью методов моделирования 247
5.1 Особенности построения модельной среды 247
5.1.1. Принципы формирования базы имитационных модулей 250
5.1.2. Интеграция аналитических и имитационных моделей 259
5.2. Методы и алгоритмы управления модельным экспериментом 285
5.2.1. Организация системы имитационного моделирования 286
5.2.2. Управление имитационным экспериментом с помощью методов планирования экспериментов. Ранжирование уровней параметров модели 291
5.3. Оптимизация параметров имитационной модели на основе генетического алгоритма и нейронной сети 299
5.3.1. Проблемы выбора нейронной сети для моделирования функции фитнесса 303
5.3.2. Алгоритм оптимизации параметров имитационной модели на основе генетического алгоритма 309
5.4. Выводы 312
6. Применение разработанных методов, алгоритмов и программных средств 314
6.1. Обзор инструментальных средств поддержки исследования компьютерных сетей 314
6.2. Состав и реализация функций ИСППР 318
6.2.1. Функциональная схема выбора варианта построения копьютерной сети 318
6.2.2. Архитектура ИСППР 322
6.3. Комплекс инструментальных средств для реализации основных функций ИСППР 329
6.3.1. Нейроимитатор 329
6.3.2. Система нечеткого вывода решений 331
6.3.3. Конструктор генетических алгоритмов 338
6.3.4. Организация пользовательского интерфейса с базой экспертных знаний 341
6.3.5. Организация инструментальной среды для распределенной обработки информации в ИСППР 344
6.4. Примеры решения практических задач 348
6.4.1.Разработка и исследование локальной вычислительной сети Калужского управления подземного хранения газа (КУПХГ) 349
6.4.2. Выбор варианта организации комплекса обработки телеметрической информации для ГУП ОКБ "СПЕКТР" 357
6.4.3. Повышение эффективности функционирования распределенной вычислительной системы для диагностики бортовых технологических объектов 363
6.4.4. Разработка информационно - вычислительной сети кафедры КФ МГТУ им. Н.Э. Баумана 367
6.5. Внедрение в учебный процесс 370
6.6. Выводы 371
Заключение 374
Литература 382
Приложение 403
- Подходы к решению трудно формализуемых задач на основе систем обработки знаний
- Алгоритмы обработки исходной информации для формирования обучающих выборок
- Алгоритм обучения НС на основе генетического алгоритма и его оценка
- Повышение скорости сходимости самоорганизующейся сети Кохонена
Введение к работе
Интеллектуальные компьютерные технологии в настоящее время являются одним из ключевых направлений развития информатики. Проведение исследований по форме и методам построения интеллектуальных систем позволяет России оставаться среди стран, влияющих на мировое развитие науки.
Особенно важным в этих исследованиях представляется создание интеллектуальных систем поддержки принятия решений (ИСППР), которые благодаря огромному прогрессу в области вычислительной техники находят все более широкое применение при решении сложных трудно формализуемых задач, какими являются задачи автоматизированного проектирования, робототехники, управления, информационного мониторинга, диагностики и т.д.
Отличительными признаками трудно формализуемой задачи являются неполнота исходных данных о решаемой задаче, их неточность и неоднородность, высокая вычислительная сложность их анализа даже на быстродействующих компьютерах. Трудно формализуемая задача не имеет точного решения и требует применения приближенных методов, основанных на широком использовании эмпирических данных, экспертного оценивания, нечетких и неклассических логик, моделирования, специально разработанных методик. Современные методы построения ИСППР берут начало в работах таких российских и зарубежных ученых, как Глушков В.М., Амосов Н.А., Поспелов Д.А., Вииер Н., Минский М., Ларичев О.И., Лорьер Ж-Л,, Розенблатт Ф., Пейперт С, Стефанюк В.Л., Гладун В.П., Попов Э.В., Осипов Г.С, Загоруйко Н.Г., Борисов A.IL, Вагин В.Н., Финн В.К. и др.
Основные ограничения известных методов и технологий, используемых в настоящее время в системах поддержки принятия решений в трудно формализуемых задачах, обусловлены недостаточной эффективностью решения в них проблем обучения, настройки и адаптации к проблемной области, обработки неполной и неточной исходной информации, интерпретации данных и накопления знаний экспертов, единообразного представления информации, поступающей из различных источников и т.д. Эти ограничения могут быть устранены на основе использования перспективных нейросстсвых методов и технологий, эволюционного моделирования и генетических алгоритмов, нечеткой логики, различных гибридных технологий или технологий мягких вычислений - Soft computing (нейро-нечетких, нейро-генетических и т.п.). Исследованию и практическому применению перечисленных методов и технологий для решения практических задач посвящены работы Галушкина А.И., Горбаня А.Н., Курейчика В.М., Омату С, Заде Л., Касабова Н., Гольд-берга Д., Дэвиса Л., Лина С, Филаретова Г.Ф., Фоминых И.Б., Нечаева Ю.И. Васильева В.И., Редько В.Г., Ярушкиной Н.Г., Аверкина А.Н.и др.
Вместе с тем, несмотря на активные исследования в этой области, все еще остаются не полностью решенными многие проблемы, связанные с раз работкой методов и алгоритмов синтеза нейронной сети и интерпретации результатов ее работы для конкретных приложений, недостаточно проработаны вопросы интеграции различных информационных технологий и особенности их реализации в ИСППР.
Таким образом, решаемые в диссертационной работе задачи исследования нейросетевых и гибридных методов и технологий в ИСППР для повышения эффективности реализации в них механизмов обучения, самообучения и адаптации к особенностям проблемной среды являются важными и актуальными.
Целью диссертации является развитие теории, создание, исследование и совершенствование методов и алгоритмов, составляющих основу нейросетевых и гибридных технологий, повышающих эффективность процессов обработки информации в интеллектуальных системах, предназначенных для поддержки принятия решений. Эффективность применения технологий оценивается по качеству решений, срокам их получения, а также по возможности расширения класса решаемых в рамках ИСППР задач.
Для достижения поставленной цели в диссертации решаются следующие основные задачи.
1. Разработка и исследование методов и алгоритмов, нацеленных на повышение эффективности применения нейросетевых и гибридных методов и технологий в интеллектуальных системах поддержки принятия решений.
2. Разработка и исследование принципов построения нейросетевой базы знаний с использованием базовых нейронных модулей, ориентированных на специфику предметной области и предназначенных для комплексного решения типовых задач, лежащих в основе создания интеллектуальной системы поддержки принятия решений.
3. Разработка алгоритмов и методики построения нейронных сетей и гибридных моделей с заданными характеристиками, в зависимости от специфики их применения для решения конкретных задач в рамках интеллектуальной системы поддержки принятия решений с возможностью их адаптации в условиях процесса поиска решения.
4. Разработка методики и алгоритмов анализа прогнозируемых на основе нейронных сетей и гибридных моделей альтернативных вариантов решений, обеспечивающих обобщение результатов моделирования и оптимизацию параметров моделей при существенном сокращении времени исследования.
5. Исследование на практике эффективности применения созданных методов, алгоритмов и инструментальных средств, точности заложенных в них методов и алгоритмов подготовки и выбора решения.
Методы исследования. Проведенные теоретические и прикладные исследования базируются на методах современного системного анализа, теории принятия решений, иейроинформатики, генетических и эволюционных алгоритмов, теории нечеткой логики, теории распознавания образов, теории оптимизации, методах математической статистики, теории планирования экспериментов, имитационного моделирования, объектно-ориентированного программирования. Научная новизна. Разработанные в диссертации теоретические основы построения ыейросстевых и гибридных моделей поиска и оценки решений в трудно формализуемых задачах с помощью ИСППР, обеспечивающих реализацию механизмов обучения, самообучения и адаптации к особенностям проблемной среды, и методы их анализа являются существенным вкладом в развитие фундаментальных исследований в области теории принятия решений, создания и исследования новых технологий проектирования сложных программных систем, расширяющих интеллектуальные возможности компьютеров и компьютерных систем.
Конкретно на защиту выносятся следующие новые научные положения и результаты:
• методы и алгоритмы повышения эффективности применения нейросе-тевых и гибридных технологий в интеллектуальных системах поддержки принятия решений, выражающейся в повышении качества формируемых решений и в сокращении сроков их получения;
• методика и алгоритмы формирования специализированных нейросете-вых баз знаний на основе предварительно обученных нейронных модулей, обеспечивающих гибкость и накопление опыта эксперта в заданной предметной области;
• методика и алгоритмы синтеза нейронной сети и гибридных моделей с требуемыми свойствами для конкретных приложений;
• методы и алгоритмы анализа альтернативных вариантов решений методами моделирования, обеспечивающие развитие предпочтительного варианта и оценку результата для принятия окончательного решения.
Практическая значимость результатов диссертационной работы определяется созданием комплекса программных инструментальных средств, повышающих эффективность процессов обработки информации в интегрированных интеллектуальных системах поддержки принятия решений и позволяющих использовать разработанные методы, модели и программные системы, отвечающие конкретным приложениям. Созданный комплекс инструментальных средств может служить как для научных исследований и обучения, так и для комплсксирования с другими информационными системами коммерческих и государственных предприятий посредством стандартных интерфейсов DCOM, DDE, CORBA и др. с целью получения доступа к реальным базам данных и знаний. Предлагаемые методы, алгоритмы и программные системы применены при решении конкретных задач исследования специализированных компьютерных систем обработки данных, а также при выборе компонентов программного и аппаратного обеспечения компьютерных сетей, разрабатывавшихся как для учебного заведения, так и для государственных и коммерческих организаций.
Достоверность. Достоверность научных положений, теоретических выводов и практических результатов, полученных в диссертации, подтверждена результатами практической проверки методов, алгоритмов и программного обеспечения с использованием стандартных и специально разработанных тестов на основе существующих методик, корректным обоснованием и анализом моделей с применением методов математической статистики, использованием результатов работы другими авторами, а также результатами практического использования разработанных в диссертации математических, алгоритмических и программных методов и средств.
Внедрение и реализация результатов работы. Диссертация является теоретическим обобщением научных исследований, выполненных автором в течение 25 лет на кафедре "Компьютерные системы и сети" КФ МГТУ им. Н.Э. Баумана в результате сотрудничества со многими промышленными предприятиями и фирмами. Теоретический базис разработанного подхода к построению интеллектуальных систем поддержки принятия решений в трудно формализуемых задачах основан на исследованиях, результаты которых обобщены в монографии, учебных пособиях, научных статьях и в докладах на национальных и международных конференциях. Наиболее важная часть разработанного программного обеспечения зарегистрирована в Роспатенте (имеется 7 авторских свидетельств об официальной регистрации программ для ЭВМ). Выполнены 17 хоздоговорных и госбюджетных НИР, в которых автор являлся руководителем, заместителем руководителя, ответственным исполнителем и исполнителем темы.
Основные результаты диссертационной работы нашли свое применение в виде инженерных рекомендаций и методик, пакетов прикладных программ и инструментальных средств при разработке Государственной сети вычислительных центров (Гос. per. № 74066264, Х« 74017988. -М.:МЭИ,1974 1975г.г.), выборе комплекса аппаратных и программных средств проблемно-ориентированных вычислительных систем и сетей (Гос. per. № 77077691-М. :МЭИ, ЦНИИ "АГАТ" 1976-1977г.г.), создании специализированных распределенных вычислительных комплексов управления цехом сборки интегральных схем, техпроцессом, динамическими объектами (Гос.рег. №79076603, №78007065, №81018468. -М.:МВТУ им. Н.Э. Баумана, 1978-198lr.r.), разработке обобщенной имитационной модели комплекса обработки телеметрической информации в реальном масштабе времени и имитационных моделей специализированных устройств (Гос.рег. №81011976. -М.:МВТУ им. Н.Э. Баумана, 1985г.), разработке и исследовании специализированных распределенных вычислительных комплексов (Гос. per. №86015052. -М.:МГТУ им. Н.Э. Баумана, 1990 г.г.), проектировании и анализе информационно-вычислительной сети КФ МГТУ им. Н.Э. Баумана, (Гос. per. №01950002971. -М.:МГТУ им. Н.Э. Баумана, 1991-1995г.г.), развитие и применение новых технологий проектирования вычислительных систем и сетей (Гос. регистр. № 01980003288. - М.: МГТУ им. Н.Э. Баумана, 1998), создании и развитии региональных и локальных сетей на предприятиях и в офисах (Гос. per. 01990004086, № 01200107595 -М.:МГТУ им. Н.Э. Баумана, 1996-2001 г.г.).
Полученные в диссертации результаты внедрены на ГУП ОКБ "СПЕКТР" (г. Рязань), на ГУП КНИИТМУ (Калужский научно-исследовательский институт телемеханических устройств), на ОАО "Восход" - Калужский радиоламповый завод (КРЛЗ), на ОАО "Тайфун" - Калужский приборостроительный завод, в научно-производственной фирме "ЭВЕРЕСТ", в учебный процесс. Наибольшее отражение в работе нашли результаты, полученные автором и руководимой им научной группой при совместной работе с Особым конструкторским бюро "Спектр" (1975-2002 г.г.), связанные с разработкой и анализом специализированных распределенных вычислительных комплексов, предназначенных для оперативной обработки телеметрической информации и проведении наземных испытаний бортовых систем.
Результаты диссертационной работы активно используются в учебном процессе: при чтении лекций, при курсовом и дипломном проектировании, проведении студенческих НИР, при подготовке кандидатских диссертаций (автор имеет 4 аспиранта) и в лабораторных работах на кафедре "Компьютерные системы и сети" КФ МГТУ им. Н.Э. Баумана, на межвузовском факультете КГПУ (Калужского Государственного педагогического университета). Монография, учебное пособие "Нейрокомпьютеры", допущенное Министерством образования Российской Федерации для студентов высших учебных заведений, и 5 учебных пособий (МГТУ им. Н.Э. Баумана), разработанные автором, в отсутствии широко доступных учебников по теме диссертации, используются для подготовки инженеров по специальности "Вычислительные машины, комплексы, системы и сети" направления подготовки дипломированных специалистов "Информатика и вычислительная техника". Полученные автором результаты вошли в программы дисциплин "Вычислительные системы и сети", "Программные средства проектирования вычислительных систем", "Экспертные системы", "Системы искусственного интеллекта", "Перспективные направления развития СИИ", "Нейрокомпьютеры", "Эволюционное моделирование", "Интеллектуальные САПР , в читаемые лекционные курсы для студентов 4-го, 5-го, 6-го и 7-го курсов КФ МГТУ им. Н.Э.Баумана, а также используются в учебном процессе других Российских ВУЗов.
Практическое использование результатов диссертационной работы подтверждено соответствующими актами о внедрении. Акты о внедрении и использовании результатов работы, а также копии авторских свидетельств (Роспатент) представлены в Приложении к диссертации.
Апробация работы. Результаты исследований, составляющих содержание работы, докладывались и обсуждались на Всероссийской конференции с международным участием "Нейрокомпьютеры и их применение" (Москва, 1999, 2000, 2001, 2002), на Всероссийской научно-технической конференции "Нейроинформатика" (Москва, 2000, 2001, 2002, 2003, МИФИ), на Всероссийском семинаре "Нейроинформатика и ее приложения" (Красноярск, 2000, 2001, 2002, СО РАН), на Международном форуме "Информационные средства и технологии МФИ" (Москва, МЭИ, 1999, 2000, 2001, 2002), на Международной конференции "Lyap-2001", посвященной памяти Ляпунова А.А. (Новосибирск, СО РАН, 2001),на Восьмой национальной конференции по искусственному интеллекту КИИ 2002 (Коломна, 2002), на Международной конференции CAD/ САМ/ PDM "Системы проектирования, технологической подготовки производства и управления этапами жизненного цикла промышленного продукта" (Москва, 2001,2002,2003, ИПУ РАН), на Международной конференции SicPro- "Идентификация систем и задачи управления" (Москва, 2000, 2003 ИПУ РАН), на Международном научно-практическом семинаре "Интегрированные модели и мягкие вычисления в искусственном интеллекте" (Коломна, 2001, 2003), на XII Международной конференции "Интеллектуальные САПР" (Геленджик, 2002), на Международной ШЕЕ конференции "Искусственные интеллектуальные системы" ICAIS 2002 (Геленджик, 2002), на Втором российско-украинском семинаре "Интеллектуальный анализ информации ИАИ- 2002 (Киев, 2002), на Научной сессии МИФИ -2002 "Интеллектуальные системы и технологии" (Москва, 2002, 2003, МИФИ), на Международной конференции ТАС - "Теория активных систем" (Москва, 2001, ИПУ РАИ), на II Международной конференции CASC-2002 "Когнитивный анализ и управление развитием ситуаций" (Москва, 2002, ИПУ РАН), на Международной научной школе МА БРК - "Моделирование и анализ безопасности, риска и качества в сложных системах" (Санкт-Петербург, 2001, 2002, ИПМ РАН), на Пятом Международном симпозиуме " Интеллектуальные системы" - INTELS 2002 - пленарный доклад (Калуга-Москва, 2002), на I и II Всесибнрском конгрессе женщин-математиков (Красноярск, 2000, 2002, СО РАН), на Международной научно-технической конференции "Системные проблемы качества, математического моделирования и информационных технологий" (Сочи, 1999, 2000-пленариый доклад), на Российском научном симпозиуме "Современные проблемы информатики и кибернетики"- пленарный доклад (Сочи, 2001), на Всероссийской научно-технической конференции "Моделирование неравновесных систем" (Красноярск, 1999, 2000, 2001, 2002, СО РАН), на Международной конференции по проблемам управления, посвященной 60-летию ИПУ (Москва, 1999, ИПУ РАН), на Международной конференции "Континуальные логико-алгебраические исчисления и нейро-математика в науке, технике и экономике"- КЛИН (Ульяновск, 2001, 2002, 2003), на 8-ом Международном научно-техническом семинаре "Современные технологии в задачах управления, автоматики и обработки информации" (Алушта, 1999), на Всероссийском научно-практическом семинаре "Новые информационные технологии" (Москва, 2001, 2002, МГИЭМ), на Третьей Международной конференции "Измерение, контроль, информатизация" ИКИ-2002 (Барнаул, 2002), на Первой Международной конференции "Современные сложные системы управления -СССУ/ HTCS - High Technology Control Systems" (Липецк, 2002), на Всероссийских научно-технических конференциях "Автоматизация исследования, проектирования и испытания сложных систем" (Калуга, 1980 - 2002), на Международной конференции "Шаг в будущее" (Москва, 1995), на Международной конференции "Современные проблемы моделирования" (Киев, 1994), на Всесоюзном семинаре по автоматизированным обучающим системам (Киев, 1985), на Всесоюзных школах-семинарах по высокопроизводительным вычислительным системам (Москва, 1984; Чернигов, 1991), на Всесоюзных симпозиумах по математическому обеспечению (ИК АН УССР, Киев, 1974, 1983), на Всесоюзных конференциях " Применение микропроцессоров в управляющих вычислительных машинах и средах" (Рязань, 1979; Клайпеда, 198І; Ленинград, 1983; Ереван, 1986), на Всесоюзной конференции " Применение вычислительной техники в автоматизированном проектировании сложных систем" (Таллин, 1980), на Всесоюзных научно-технических совещаниях "Перспективы развития микропроцессорных систем" (Рига, 1980, 1981), а также на научных семинарах Российской ассоциации искусственного интеллекта и Российской ассоциации нейроинформатики (Москва), НИЦЭВТ (Москва), МЭИ (Москва), МГУ (Москва), МГИЭМ (Москва), Всесоюзного института электротехники (Рига), ГУП ОКБ "Спектр" (Рязань), МГТУ им. Н.Э. Баумана (Москва).
Публикации. По теме диссертации опубликовано 53 основных работы, б учебных пособий, одна монография, имеется 7 авторских свидетельств об официальной регистрации программ для ЭВМ (Роспатент), зарегистрировано 17 отчетов по НИР.
Структура и объем работы. Диссертация состоит из введения, шести глав, заключения, пяти приложений, содержит 436 страницы машинописного текста, 89 рисунков, 32 таблицы, библиографический список из 260 наименований.
Работа выполнена на кафедре "Компьютерные системы и сети" в Калужском филиале МГТУ им. Н.Э.Баумана.
Подходы к решению трудно формализуемых задач на основе систем обработки знаний
Процесс поиска решений с помощью систем поддержки принятия решений является в определенном смысле решением задачи: как достичь той или иной цели наилучшим образом, т.е. при минимальных затратах. Проблемы принятия решений связаны с выбором ЛГТР конкретного варианта решения (альтернативы) из имеющегося множества при наличии информации о состоянии внешней среды, критериев, решающих правил, собственных предпочтений ЛПР. При этом процедура получения результата может быть представлена следующими этапами [10]: 1) извлечение (приобретение), представление и структуризация знаний о проблемной области; 2) построение адекватных моделей принятия решений; 3) прогноз возможных вариантов решений (поиск решений); 4) обеспечение анализа и оценки эффективности предлагаемых решений; 5) выбор решения. В зависимости от степени неопределенности задачи принятия решений могут быть подразделены на [12, 20]: - задачи, для которых возможна объективная оценка результатов решения или сравнительной оценки хотя бы двух решений; - задачи, для которых невозможна объективная оценка, и ее заменяют экспертные оценки специалистов исследуемой предметной области. Первый тип задач относится к слабоструктурировашшм и трудно формализуемым проблемам, для которых характерным является присутствие как количественных, так и качественных зависимостей между элементами исследуемых систем, причем качественные имеют тенденцию доминировать. Второй тип задач относится к неструктурированным (неформализуемым) проблемам, особенность которых состоит лишь в качественном описании систем, количественные зависимости между элементами системы отсутствуют, что и определяет необходимость использования экспертных оценок [11, 20]. Задачи раннего этапа проектирования компьютерных сетей, относятся к трудно формализуемым задачам, для которых характерным является [14, 15]: - высокая размерность пространства решений; - высокая динамичность развития предметной области; - параметры объекта не могут быть представлены только в числовой форме; - цели не всегда могут быть сформулированы в терминах точно опре деленной целевой функции; - неполнота, неоднозначность, противоречивость исходных данных и знаний о предметной области.
Для трудно формализуемых задач сложно строить формальные теории и применять классические математические методы из-за недостаточного уровня формализации предметной области и значительных вычислительных затрат на их реализацию, а таюке необходимости учитывать субъективный опыт и интуицию эксперта [20]. Эти задачи относятся к классу NP-полных задач, которые невозможно решать только математическими методами [103]. Таким образом, при решении трудно формализуемых задач наряду с количественными данными, зависимостями требуется учитывать качественные зависимости, опыт, здравый смысл и интуицию специалистов.
Решение этих задач в настоящее время ведется в рамках таких научных направлений, как искусственный интеллект, теория распознавания образов, теория принятия решений и т.д., которым посвящено значительное количество работ. Развитие подходов к решению таких задач связано с именами Д.Л. Поспелова, О.И. Ларичева, Стефанюка В.Л., Э. Ханта, Н. Нильсона, Н.Г. За-горуйко, Г.С. Осипова, Э.В. Попова, В.П. Гладуна, В.К. Финна, и др. Рассмотрим возможные подходы к решению трудно формализумых задач.
Методы классического искусственного интеллекта (ИИ) долгое время базировались лишь на использовании символьного подхода, при использовании которого решение сложных задач основывалось не на моделировании человеческого интеллекта в целом или его отдельных составляющих, а связывалось с созданием формальных логических систем, в рамках которых выполнялись операции над символами [188]. Особенность развития этих систем состоит в том, что в них имитируются только тс механизмы человеческого мышления, которые ответственны за обработку информации. Доминирование символьного направления развития ИИ в течение длительного периода времени было обусловлено следующими причинами [107]: требуемый результат можно получить на основе заданной системы аксиом; процесс формализации приводит к понятию формального рассуждения, которое считается адекватным естественному; формальные рассуждения строятся с помощью общих правил, которые не зависят от проблемной области, что делает процедуру рассуждений доступной для анализа и проверки; результат формального рассуждения может быть получен как вывод в некотором исчислении, который легко реализовать на компьютере.
Центральным элементом в таких системах является база знаний. Интеллектуальные системы, в которых используется логический вывод в базе знаний, -это системы, основанные на знаниях - СОЗ [18]. Успех применения СОЗ в различных предметно-проблемных областях во многом определяется качеством заложенных в нее знаний, поэтому важным моментом при их создании является приобретение и представление знаний.
Для приобретения и представления знаний можно использовать метод прямого извлечения экспертных знаний с помощью интервьюирования эксперта в данной предметной области через посредство инженеров-когнитологов (например, система KADS, Амстердамский университет), которые помогают представлять в удобном виде экспертные знания, проверять отдельные правила вывода, в компактном виде хранить полученные знания. Развитие такого подхода стимулировалось появлением языков представления знаний (Пролог, Лисп, Смолток и им подобных). Основные проблемы, связанные с использование данного метода, сводятся к следующему [12, 17-19, 20-21,37-41]: трудоемкость выявление правил у эксперта; отсутствие гарантии полноты и непротиворечивости создаваемой базы знаний; в некоторых случаях возможен вывод при неполной базе (например, алгоритм ZET [57]).
Попытка преодоления этих недостатков в настоящее время - разработка новых языков представления знаний, программ поддержки инженеров - ког-нитологов, применение нетрадиционных логик, моделирование неопределенности в суждениях эксперта путем введения коэффициентов уверенности и нечетких переменных и т.д.
Алгоритмы обработки исходной информации для формирования обучающих выборок
Для формирования и пополнения базы знаний необходимо их выявление в источнике, преобразование во внутреннее представление и перенос в базу знаний. Формирование баз знаний в ИСППР На рис. 2.2. представлены основные источники информации, используемые для формирования баз знаний. При этом используются разнообразные алгоритмы обработки разнотипных данных и знаний, представленных в шкалах: числовых, интервальных, лингвистических, порядка, наименований. Формирование баз знаний осуществляется на основе объединения нескольких информационных потоков, а именно: фундаментальных ЗЕШНИЙ об исследуемой предметной области, представленных в форме жестких структур, таких, как математические зависимости, законы, схемы, стандарты и т.д.; экспериментальной информации, получаемой при моделировании или из натурного эксперимента; экспертной информации в форме текстов, экспертных правил и отдельных примеров (невербализованных описаний); экспертной информации о качественных и количественных характеристиках конкретных объектов исследуемой предметной области; экспертной информации мета-уровня, определяющей правила использования фундаментальных знаний в экспертных заключениях. Экспертные знания формируются как результат субъективной интерпретации эмпирической информации (результаты моделирования, натурный эксперимент), отражают примеры решения реальных задач из предметной области и играют существенную роль при представлении и использовании знаний.
Перейдем к вопросу выбора способов обработки и кодирования информации, поступающей из различных источников для формирования обучающих выборок. Методика обработки эмпирической информации в СОЗ [51-53] с помощью эксперта сводится к следующему: 1) выделение множества характерных фрагментов полученной информации (например, в виде статистических характеристик результатов моделирования и натурных испытаний или усреднения взвешенных оценок нескольких экспертов); 2) определение множества информативных параметров (что дает возможность исключения этапа кодирования не существенных параметров и их селекции в процедуре машинного обучения); 3) выбор шкапы, на основе которой осуществляется кодирование выбранных параметров; 4) кодирование параметров с целью создания входного обучающего набора примеров для формирования базы знаний. Пункты 3 и 4 тесно связаны и могут рассматриваться как одна процедура. Формирование нейросетевой базы знаний и ее последующая корректировка сводится по сути к разработке алгоритмов обработки разнотипных данных и знаний, представленных в разной форме, и приведении их к виду, удобному для последующего использования. Кодирование параметров может выполняться в различных шкалах, исследование свойств которых было проведено автором в [60]. Рассматриваемые в работе приложения касаются анализа предметной области, связанной с исследованием специализированных систем обработки данных и компьютерных сетей, при этом требования к реализации объекта и параметры объекта могут носить как качественный, так и количественный характер. В связи с этим в работе используются следующие способы кодирования исходной информации для формирования обучающих выборок. 1.
Экспертное интервальное кодирование предполагает наличие высо коквалифицированных специалистов - экспертов, которые не только опреде ляют необходимое количество параметров, но и соответствующей шкапы ко дирования (в общем случае неравномерной). Так, если кодируемый параметр является количественным (например, цикл процессора), то могут быть ис пользованы следующие интервалы: 2. Интервальное кодирование с помощью лингвистических термов ос новывается на использовании понятия нечетких переменных, введенное Л. Заде [57]. Преобразование четких переменных х1,х2,...,хп , где п - число чет ких переменных, в лингвистические с соответствующими функциями при надлежности дДл-,), цв{х2), ..., //с(;сп) нечетким множествам Л, В, ..., С осу ществляется с помощью процедуры фазификации. Эта процедура каждому интервалу изменения четкой переменной (базовой переменной) ставит в со ответствие значение функции принадлежности некоторому множеству из ин тервала [0, 1]. Наиболее часто на практике используются функции принад лежности в виде функции Гаусса, треугольной или трапецеидальной функ ции [60]. Для кодирования количественных переменных используются числовые шкалы изменения базовых переменных, для качественных - порядковые (балльные) шкалы. В некоторых случаях более удобно задавать значения функций принадлежности не в виде нечетких множеств, а в виде синглето нов. Пример кодирования качественного параметра, определяющего уровень готовности информационной системы с вариантами: низкий - SP (Small Positive), средний -MP (Middle Positive), высокий - LP (Large Positive) представлен на рис. 2.3.
Алгоритм обучения НС на основе генетического алгоритма и его оценка
Обзор методов настройки (автоматического формирования топологии) и адаптации (построение эффективного алгоритма обучения) нейронной сети к конкретной решаемой задаче показал, что одними из наиболее эффективных методов являются эволюционные, основанные па использовании генетических алгоритмов. Основными параметрами генетического алгоритма (ГА), влияющими на процесс получения решений, являются генетические операторы: сг -кроссинговер, т -мутация, оператор селекции - способ выбора родительских пар для скрещивания si, оператор отбора - способ отбора хромосом в новую популяцию о/, функция приспособленности Fit, размер популяции / , способ кодирования решений и формирования начальной популяции, вид критерия останова. Выбор этих параметров при создании конкретного ГА во многом определяет качество решения [8, 203-206, 220, 259-260]. В настоящее время в работах, посвященных использованию генетических алгоритмов [8, 203-206] для решения задач оптимизации, разработано большое количество возможных вариантов их реализации. При решении реальных задач необходимо конструировать такой генетический алгоритм, на страивая соответствующие параметры, который в наилучшей степени учитывал бы специфику каждой конкретной задачи. Поэтому необходимо создать Конструктор ГА, помогающий ЛПР выбирать параметры алгоритма и настраивать его на решение определенной проблемы [207], либо автоматически создающий алгоритм оптимизации. Взаимосвязь основных блоков, входящих в состав Конструктора, представлена на рис. 3.1. Классический генетический алгоритм [203] записывается в следующем виде. Шаг 1. Задать размер популяции г , число поколений с, тип генетических операторов cr, т, si, ot, вид функции Fit. Шаг 2. Провести кодирование хромосом одним из предложенных методов. Шаг 3. Сформировать популяцию из г хромосом. Шаг 4.
Применить генетические операторы к популяции. Шаг 5. Провести расчет функции Fit для каждой хромосомы, предварительно их декодируя. Шаг 6. Сохранить лучшую хромосому популяции. Шаг 7. Проверить условие окончания работы алгоритма. с:=с-1; Если с=0, перейти к ш. 9. Шаг 8. Провести фильтрацию хромосом: выбрать г хромосом в новую популяцию. Перейти к ш. 4. Шаг 9. Выбрать лучшую хромосому из всех популяций. Шаг 10. Останов. Конструктор должен быть открытой системой, в которую можно добавлять новые генетические операторы, способы кодирования хромосом (потен циальных решений), новые функции Fit и т.д. Особенностью Конструктора является возможность применения средств ГА для выбора параметров ГА, который будет наиболее эффективным при решении конкретной оптимизационной задачи. Рассмотрим некоторые предложенные в настоящей работе дополнительные методы кодирования, реализованные в Конструкторе. Для каждого вида кодирования в ГА используются соответствующие операторы кроссинговера и мутации. I. Числовое кодирование. Будем представлять решение в виде одной хромосомы, состоящей из генов. Для каждого і-го гена будем задавать диапазон [ 3(...,], в котором могут изменяться его значения. В этом случае область поиска задается в виде многомерного прямоугольного параллелепипеда. С помощью явного задания системы уравнений, которым должна удовлетворять хромосома, определяется некоторая подобласть этого параллелепипеда, в которой осуществляется поиск решения.
При инициализации работы ГА каждому і-му гену в хромосоме случайным образом ставится в соответствие некоторое число из области его значений [cii.,.Ь,]. Затем проверяется, принадлежит ли хромосома области поиска (не является ли она запрещенной комбинацией). Если не принадлежит, то процесс повторяется сначала до тех пор, пока значение хромосомы не попадет в область поиска. В общем случае область изменения значений гена может представлять собой не один отрезок, а некоторое их множество, что расширяет возможный диапазон задания значений параметров xt,x2,...7xn. При выполнении операции мутации случайным образом выбирается ген хромосомы, над которым будет произведена мутация, и к его предыдущему значению добавляется небольшое число (величина которого определяется как некоторый процент от диапазона изменения данного гена). Затем происходит проверка хромосомы на принадлежность области поиска. Если хромосома не удовлетворяет заданной системе уравнений, процедура мутации повторяется снова. Оператор скрещивания может выполняться так же, как и при кодировании хромосомы битовой строкой. Дополнительно в Конструкторе реализован однородный кроссинговер (сегрегация) [205], при котором выбранные случайным образом из родительской пары гены копируются в потомка. 2. Интервальный метод. Для каждого і-го гена хромосомы определяется область изменения его значений, состоящая из нескольких интервалов внутри диапазона [o,-...bf]. Для каждого интервала путем проведения предварительных расчетов задается вероятность его принадлежности области значений гена, а также его максимальная и минимальная границы.
Повышение скорости сходимости самоорганизующейся сети Кохонена
Поэтому при практической реализации ГА можно рекомендовать их равновероятный выбор.
Предложенный оператор рекомбинации оказывается наиболее эффективным при оптимизации функции многих переменных (F6 и F1) и при поиске глобального экстремума. В экспериментах (рис.3.11) наименьшие отклонения значений оптимизируемых функций (F4, F6, F7) от экстремума получены при использовании именно этого оператора. Причина заключается в большем охвате исследуемой области за счет одновременного скрещивания четырех хромосом, максимально удаленных друг от друга. В этом случае вероятность нахождения глобального экстремума значительно повышается. Для простых функций типа F\ этот оператор оказывается неэффективным. Таким образом, предложенный оператор рекомбинации целесообразно использовать для оптимизации функций многих переменных с одним или несколькими глобальными экстремумами.
При сравнении типов генной и хромосомной мутации оказалось, что генная наиболее предпочтительна для унимодальных функций (типа F1), поскольку связана с локальным изменением значений одного гена, приводящего к формированию мутанта, незначительно отличающегося от родителя. Таким образом, генная мутация целесообразна при исследовании одноэкстремальных функций. Для более сложных функций эффективным является использование инверсии. Причина заключается в том, что перестановка местами генов в хромосомах позволяет быстро перейти в другие области поиска, а для определения глобального экстремума, например, в F4, F6 и F1 больше внимания необходимо уделять именно вопросу поиска возможной области существования экстремума. Оператор хромосомной мутации- транслокация может быть полезен так же, как и генная мутация, при оптимизации одноэкс-тремальных функций, поскольку образует изохромосому, незначительно отличающуюся от родительской. Таким образом, для быстрой локализации одного оптимального решения необходимо использовать генную мутацию или транслокацию, а для определения нескольких или всех глобальных решений -инверсию.
Использование многопопуляционного алгоритма (МГА) во всех экспериментах приводит к повышению значений функции качества. Например, для МГА при k=3 Fit увеличивается примерно в 2 раза (при увеличении числа вычислений в 3 раза по сравнению с ГА), а при к=10 Fit увеличивается в 8 и более раз для функций Fl, F5, F6 (число вычислений функции более 10 000), однако для сложной функции F7 увеличение числа одновременно развивающихся популяций не приводит к существенному улучшению Fit. Это связано с существованием для этой функции большого числа локальных экстремумов
В МГА тип операторов сг и т не так критичен к форме области поиска (ландшафту) оптимизируемой функции, поскольку обмен между хромосомами разных популяций вносит большее генетическое разнообразие, чем локальные изменения хромосом в одной популяции. Однако выявленная в ГА тенденция влияния определенных типов генетических операторов сг и т на качество Fit сохраняется: для сложных функций наиболее предпочтительным является использование рекомбинации и инверсии, для одноэкстремальных -одноточечных или двухточечных кроссипговеров и генной мутации.
Таким образом, проведенные эксперименты позволили определить взаимосвязь сложности оптимизируемой функции и видов генетических операторов кроссииговера и мутации, использование которых приводит к лучшей сходимости ГЛ. Несмотря на то, что многопопуляционный МГА значительно повышает вероятность нахождения глобального экстремума, вычислительная сложность алгоритма также высока, что, в свою очередь, приводит к снижению скорости сходимости алгоритма. Поэтому реализация МГА целесообразна в распределенных системах, обеспечивающих параллельное и совместное использование вычислительных ресурсов. Эти проблемы рассматриваются в главе б.
Основываясь на полученных в предыдущем разделе экспериментальных результатах, можно предположить, что генетический алгоритм будет наиболее эффективной процедурой па первоначальном этапе поиска решения, на котором определяется область существования глобального экстремума. Второй этап поиска будет связан с уточнением минимума на основе локального алгоритма оптимизации [137].
