Содержание к диссертации
ВВЕДЕНИЕ 4
1 СОСТОЯНИЕ ВОПРОСА. СУЩНОСТЬ ПРОБЛЕМЫ-
АНАЛИТИЧЕСКИЙ ОБЗОР СУЩЕСТВУЮЩИХ МЕТОДОВ 13
1,1 Общие сведения 13
12 Проблема поиска решений в интеллектуальных системах
обработки экспертной информации 21
1.Z1 Детерминированные методы поиска 22
1.2.2 Статистические методы поиска , 29
13 Генетические алгоритмы — новый подход к оптимизации
процессов поиска решений в экспертных системах 36
1.4 Цели и задачи исследования 40
Выводы по главе 1 42
2 ТЕОРЕТИЧЕСКОЕ ОБОСНОВАНИЕ И РАЗРАБОТКА
МЕТОДА ОПТИМИЗАЦИИ ПРОЦЕССА ПОИСКА РЕШЕНИЙ
В ЭКСПЕРТНЫХ СИСТЕМАХ НА ОСНОВЕ ГЕНЕТИЧЕСКИХ
АЛГОРИТМОВ 43
Некоторые сведения из эволюционной теории 43
Теоретические основы ГА 46
Простой ГА 48
Модифицированный ГА 59
Механизмы размножения ГА 61
2.3 Теорема схем 64
2.3.1 Последствия воздействия операторов ГА насоставсхем 65
23.2 Гипотеза о строительных блоках 70
2.33 Область эффективного действия ГА 72
23А Шаблоны схем и гиперплоскости 75
2.4 Разработка метода поиска оптимальных решений
в экспертных системах на основе ГА 77
2 АЛ Исходные концепции 77
2А.2 Описание метода 79
2А.3 Алгоритм поиска решений 95
Выводы по главе 2 99
з создание программного исследовательского
КОМПЛЕКСА «ПОИСК» 102
ЗЛ Цели и задачи комплекса 102
Структура программного исследовательского комплекса «ПОИСК» 103
Генератор баз знаний 108
Модуль машины логического вывода 114
Методика проведения эксперимента на ПИК «ПОИСК» 117
Выводы по главе 3 125
4 ИССЛЕДОВАНИЕ МЕТОДА ГЕНЕТИЧЕСКИХ СХЕМ И
СРАВНИТЕЛЬНЫЙ АНАЛИЗ С ДРУГИМИ МЕТОДАМИ ПОИСКА
РЕШЕНИЙ В ЭКСПЕРТНЫХ СИСТЕМАХ 127
Исследовательская среда в режиме «Консультации» 127
Режимы метода генетических схем 130
43 Исследование основных параметров ГА и их оптимизация 132
4.3.1 Влияние численности популяции 133
Влияние длины бинарных кодировок 136
Механизм отбора родительских пар 138
4. ЗА Выбор схемы размножения 140
Выбор типа оператора кроссовера 143
Выбор способа формирования родительской пары 145
4.3.7 Влияние на эффективность поиска типа используемого оператора
мутации 148
43.8 Влияние оператора инверсии на эффективность поиска 150
4,4 Сравнительная оценка эффективности метода ГС 154
4.4. Ї Параметры метода корреляции 154
4Л.2 История консультаций 157
4.4.3 Сравнительные диаграммы процессов поиска 163
Выводы по главе 4 169
ЗАКЛЮЧЕНИЕ 171
СПИСОК ИСПОЛЬЗОВАННЫХ ИСТОЧНИКОВ 174
ПРИЛОЖЕНИЕ А АКТЫ ВНЕДРЕНИЯ ПИК «ПОИСК» 184
Введение к работе
Актуальность проблемы, В настоящее время, когда возрастает важность наиболее эффективного использования природных и людских ресурсов, материальных и финансовых средств, особое значение приобретают задачи поиска оптимальных решений той или иной проблемы.
Одной из таких проблем является проблема оптимизации процессов поиска решений в интеллектуальных системах обработки экспертной информации, или экспертных системах (ЭС), Эта проблема на сегодняшний день стоит остро в связи с увеличивающимся объемом баз знаний современных экспертных систем. Основная идея поиска оптимальных решений в экспертных системах заключается в уменьшении количества гипотез, доказанных вхолостую, и как следствие - увеличение скорости процесса поиска.
Существующие методы поиска оптимальных решений имеют ряд ограничений и недостатков, связанных с предварительным накоплением информации, необходимой для их поддержки и, соответственно, требуют больших временных затрат для их реализации. Поэтому разработка новых методов поиска оптимальных решений в экспертных системах, основанных на новых принципах, является актуальной задачей.
Цель работы. Разработка на основе эволюционно-генетического подхода метода генетического поиска оптимальных решений в ЭС с продукционным представлением знаний и создание программной среды для его реализации и исследования.
Задачи исследования: определение проблемы поиска решений в интеллектуальных системах
обработки экспертной информации на основании обзора, изучения и
анализа литературных источников, посвященных созданию и практике
работы существующих систем;
проведение анализа существующих методов поиска оптимальных решений в ЭС с продукционным представлением знаний;
создание метода поиска оптимальных решений, основанного на эволюционно-генетическом подходе, на абстрагировании больших пространств поиска, не тяготеющего к узкой предметной области;
разработка и исследование алгоритмов и программ генетического поиска оптимальных решений, необходимых для реализации создаваемого нового метода;
создание программного исследовательского комплекса, ядром которого является формальная модель ЭС (ФМЭС) для оценки эффективности и сравнительного анализа разработанных алгоритмов генетического поиска с другими алгоритмами;
определение критерия, по которому должен проводиться сравнительный анализ алгоритмов генетического поиска с другими алгоритмами;
разработка пользовательского интерфейса и описание сценария работы программного исследовательского комплекса при проведении эксперимента;
обобщение полученных результатов исследований и выработка рекомендаций для дальнейшего их использования.
Методы исследования. Поставленные задачи решены с применением методов искусственного интеллекта, инженерии знаний и экспертных систем, теории генетических алгоритмов (ГА) и эволюционного программирования, теории графов и нечетких множеств, методов математической статистики, оптимизации и математического моделирования.
Научная новизна:
сформулированы исходные положения для разработки метода поиска
оптимальных решений в ЭС с продукционным представлением знаний
на основе эволюционно-генетического подхода;
теоретически обоснован и разработан новый метод - метод генетических схем (ГС) для оптимального поиска решений в продукционных ЭС с использованием генетических алгоритмов и специальным образом организованных метазнаний, формируемых в процессе подготовки системы к работе;
обоснована и разработана трехуровневая организация базы метазнаний, определены характер и схемы использования информации каждого метауровня для обеспечения высокой эффективности поиска в режиме консультаций;
на основе разработанного метода ГС построен алгоритм работы ЭС с продукционным представлением знаний в режиме консультации;
создан программный исследовательский комплекс (ПИК) «ПОИСК», ядром которого является ФМЭС и который может быть использован как универсальный инструмент для исследования, сравнительного анализа и оценки эффективности различных методов оптимизации поиска решений в ЭС;
исследовано влияние основных параметров нового метода ГС на эффективность поиска;
показано на основании сравнительного анализа, что метод генетических схем при поиске решений с ростом численности популяции дает стабильно лучшие результаты, чем другие методы.
Практическая ценность. Впервые на практике ГА были применены в такой области, как системы обработки экспертной информации.
На основе разработанного метода ГС был экспериментально осуществлен генетический поиск оптимальных решений в ЭС с продукционным представлением знаний. Причем практическая реализация метода показала, что на его базе можно строить ЭС с высокой эффективностью и скоростью поиска оптимальных решений-
Разработанный в диссертации ПИК «ПОИСК» позволяет строить экспертные системы продукционного типа для различных предметных областей, а также проводить эксперименты по поиску решений в этих системах, используя различные методы оптимизации, ПИК «ПОИСК» реализован на персональном компьютере типа Pentium 4 и разработан средствами языка C++ Builder 6 с применением среды разработки приложений.
ПИК «ПОИСК» и разработанный автором метод генетических схем были внедрены при проектировании ЭС для решения задач прогнозирования на предприятии Армавирские электрические сети ЛО Кубаньэиерго (г. Армавир), а также в учебном процессе КубГТУ в курсах «Системы искусственного интеллекта» и «Методы принятия решений», что подтверждается соответствующими актами.
Апробация работы. Основные положения диссертационной работы докладывались и обсуждались на 14 Международных, Всероссийских и региональных научных конференциях и семинарах, в том числе: на X Международной конференции «Применение новых технологий в образовании» (Москва-Троицк, 1999), Международной научно-технической конференции «50 лет развития кибернетики» (Санкт-Петербург, 1999), Международной научно-технической конференции «Интеллектуальные многопроцессорные системы» (Таганрог, 1999), 2-й Международной научно-технической конференции «Информационные технологии в моделировании и управлении» (Санкт-Петербург, 2000), 1-й Межрегиональной научно-практической конференции молодых ученых «Перспективы развития современных информационных технологий» (Краснодар, 2001), -Международной научно-пратегической конференции «Компьютерные технологии в науке, производстве, социальных и экономических процессах» (Новочеркасск, 2002), VIII Всероссийской научно-практической конференции «Инновационные процессы в высшей школе» (Краснодар, 2002), Межрегиональном научном семинаре по проблемам современной математики и информатики (Армавир, 2003), X Юбилейной
9 Всероссийской научно-практической конференции «Инновационные процессы в высшей школе» (Краснодар, 2004), Всероссийской научной конференции молодых ученых и студентов «Современное состояние и приоритеты развития фундаментальных наук в регионах» (Анапа, 2004) и других конференциях.
Публикации. По теме диссертации опубликовано 24 печатные работы. Из них: 10 статей и 14 тезисов докладов на вышеперечисленных конференциях.
Основные положения, выносимые на защиту: " принципы, основные концепции эволюционно-генетического подхода к
проблеме оптимизации процессов поиска решений в интеллектуальных
системах обработки экспертной информации;
метод генетических схем для поиска оптимальных решений в экспертных системах с продукционным представлением знаний;
алгоритмическая и программная реализация метода генетических схем при работе экспертной системы в режиме консультаций;
программный исследовательский комплекс «ПОИСК» с ядром формальной ЭС для исследования и оценки эффективности различных методов оптимизации поиска решений;
ж методика и технология исследования основных параметров метода
генетических схем и результаты сравнительного анализа его с другими
методами при поиске оптимальных решений.
Структура и объем работы.
Работа содержит 79 рисунков, 9 таблиц, библиографию из 102 наименований на 10 страницах и приложения на 2 страницах.
В первой главе определена проблема поиска решений в интеллектуальных системах обработки экспертной информации. Проведен анализ существующих методов поиска оптимальных решений в интеллектуальных системах с продукционным представлением знаний, таких как, метод полного перебора (исчерпывающий поиск), метод упорядочения гипотез по убыванию математических ожиданий их степеней достоверности,
10 метод кластеризации гипотез, основанный на исследовании корреляционной зависимости между ними. Оценены их достоинства и существенные недостатки. Определены и сформулированы основные цели и задачи исследования данной диссертационной работы.
Во второй главе описаны теоретические положения эволюционно-генетического подхода, генетических алгоритмов и проблемы их использования для поиска оптимальных решений. Проанализированы некоторые виды генетических алгоритмов, их свойства, структура, алгоритмы работы и их реализации для решения задач оптимизации. Сформулированы исходные положения для разработки метода поиска оптимальных решений в продукционных экспертных системах. Теоретически обоснован и разработан новый метод - метод генетических схем для оптимального поиска решений в ЭС с продукционным представлением знаний с использованием генетических алгоритмов и специальным образом организованных метазнаний, формируемых в процессе подготовки системы к работе. Обоснована трехуровневая структура метазнаний, определены характер и схемы использования информации каждого метауровня для обеспечения высокой эффективности поиска в режиме консультаций. Показана возможность работы метода в режиме дообучения с накоплением на втором и третьем уровнях метазнаний хромосом с высокой приспособленностью. На основе разработанного автором метода генетических схем построен алгоритм работы продукционной экспертной системы.
Третья глава посвящена созданию программного исследовательского комплекса «ПОИСК» (ПИК «ПОИСК») с ядром формальной экспертной системы для экспериментального исследования разработанного в диссертации метода поиска оптимальных решений на основе ГА и сравнения его с другими методами оптимизации. Разработана структура ПИК «ПОИСК», определены основные функции и процессы взаимодействия всех составляющих программных модулей комплекса. Показано, что созданный ПИК «ПОИСК» позволяет проектировать экспертные системы с продукционным
представлением знаний с различными параметрами, такими как, объем базы знаний (число правил), глубина базы знаний (число уровней), связанность базы знаний (число уровней в правиле), введение степеней достоверности при обработке нечетких знаний. Описан сценарий работы программного исследовательского комплекса «ПОИСК» при проведении экспериментов, и показана универсальность комплекса для исследования и оценки эффективности различных методов оптимизации поиска решений в экспертных системах.
Четвертая глава посвящена исследованию метода генетических схем и его сравнительному анализу с другими методами поиска решений в экспертных системах. Разработаны исследовательская среда в режиме «Консультации», алгоритмы и программы накопления статистических данных для использования методов математических ожиданий и корреляции для их сравнения с генетическим поиском. Исследованы основные параметры метода ГС, такие как, численность популяции, длина бинарных кодировок, тип используемого оператора кроссовера и количество решений, генерируемых на каждой итерации, вероятность применения и тип используемого оператора мутации, вероятность используемого оператора инверсии. Показано на основании сравнительного анализа, что линейный тренд метода ГС свидетельствует о постепенном убывании числа холостых гипотез при поиске решений с ростом численности популяции ГА и что уже при числе особей в популяции больше 100, разработанный метод дает стабильно лучшие результаты, чем другие методы. В этой главе доказано, что влияние численности популяции, увеличение числа особей в поколении приводит к более плотному покрытию хромосомами, а значит и шимами, удовлетворительных участков ландшафта целевой функции и, следовательно, к более эффективному использованию метауровней базы знаний экспертной системы. Также показано, что оптимальные значения ряда параметров ГА, такие как тип оператора кроссовера, вероятность и тип оператора мутации, вероятность оператора
12 инверсии, используемые как факторы регулирования сходимости процесса поиска и его доводки, определяются в общем случае априори неизвестным поведением и сложностью ландшафта целевой функции и должны подбираться экспериментально с помощью средств программного исследовательского комплекса.
В приложении приведены акты внедрения результатов диссертационной работы.
