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

На правахрукописи

ЧАСТИКОВА Вера Аркадьевна

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

Специальность: 05.13.01 - Системный анализ, управление и обработка информации (информационные и технические системы)

АВТОРЕФЕРАТ

диссертации на соискание ученой степени кандидата технических наук

Краснодар - 2005

Работа выполнена в Кубанском государственном технологическом университете

Научный руководитель: доктор технических наук,

профессор Симанков Владимир Сергеевич

Официальные оппоненты: доктор физико-математических наук,

профессор Чижиков Владимир Иванович

кандидат технических наук,

доцент Булатникова Инга Николаевна

Ведущая организация: Санкт-Петербургский государственный

электротехнический университет «ЛЭТИ» (г. Санкт-Петербург)

Защита диссертации состоится 8 июня 2005 г. в 14:00 на заседании диссертационного совета Д 212.100.04 в Кубанском государственном технологическом университете по адресу: 350072, г. Краснодар, ул. Московская 2А.

С диссертацией можно ознакомиться в библиотеке Кубанского государственного технологического университета по адресу: 350072, г. Краснодар, ул. Московская, 2А.

Автореферат разослан 6 мая 2005 г.

Отзывы на автореферат, заверенные печатью учреждения, просим 'направлять по адресу: 350072, г. Краснодар, ул. Московская, 2А, КубГТУ, ученому секретарю диссертационного совета Д 212.100.04, к.т.н., доцету Зайцеву И.В.

Ученый секретарь диссертационного совета Д 212.100

И.В. Зайцев

ОБЩАЯ ХАРАКТЕРИСТИКА РАБОТЫ

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

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

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

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

Задачи исследования:

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

• проведение анализа существующих методов поиска оптимальных решений в ЭС с продукционным представлением знаний;

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

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

• создание программного исследовательского комплекса, ядром которого является формальная модель ЭС (ФМЭС) для оценки эффективности и сравнительного анализа разработанных алгоритмов генетического поиска с другими алгоритмами;

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

• разработка пользовательского интерфейса и описание сценария работы программного исследовательского комплекса при проведении эксперимента;

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

Методы исследования. Поставленные задачи решены с применением методов искусственного интеллекта, инженерии знаний и экспертных систем, эволюционной теории и теории генетических алгоритмов (ГА), теории графов и нечетких множеств, методов математической статистики, оптимизации и математического моделирования. Научная новизна:

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

• теоретически обоснован и разработан новый метод - метод генетических схем (ГС) для оптимального поиска решений в продукционных ЭС с использованием генетических алгоритмов и специальным образом организованных метазнаний, формируемых в процессе подготовки системы к работе;

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

• на основе разработанного метода ГС построен алгоритм работы ЭС с продукционным представлением знаний в режиме консультации;

• создан программный исследовательский комплекс (ПИК) «Поиск», ядром которого является ФМЭС и который может быть использован как универсальный инструмент для исследования, сравнительного анализа и оценки эффективности различных методов оптимизации поиска решений в ЭС;

• исследовано влияние основных параметров нового метода ГС на эффективность поиска;

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

Практическая ценность. Впервые на практике ГА были применены в такой области, как интеллектуальные системы обработки экспертной информации.

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

Разработанный в диссертации ПИК «Поиск» позволяет строить экспертные системы продукционного типа для различных предметных областей, а также проводить эксперименты по поиску решений з этих системах, используя различные методы оптимизации. ПИК «Поиск» разработан средствами языка С+-4-Buildeг 6 с применением среды разработки притожений

ПИК «Поиск» и разработанный автором метод генетических схем были внедрены при проектировании ЭС для решения задач прогнозирования на предприятии Армавирские электрические сети АО Кубаньэнерго (г Армавир), а так-

же в учебном процессе КубГТУ в курсах «Системы искусственного интеллекта» V «Методы принятия решений», что подтверждается соответствующими актами

Апробация работы. Основные положения диссертационной работы докидывались и обсуждались на 14 Международных, Всероссийских и региональных научных конференциях и семинарах, в том числе: на X Международной конференции «Применение новых технологий в образовании» (Москва-Троицк, 1999) Международной научно-технической конференции «50 лет развития кибернетики» (Санкт-Петербург, 1999), Международной научно-технической конференции «Интеллектуальные многопроцессорные системы» (Таганрог, 1999), 2-й Международной чаучно-технической конференции «Информационные технологии в моделировании и управлении») (Санкт-Петербург, 2000), 1-й Межрегиональной научно-практической конференции молодых ученых «Перспективы развития сог ременных информационных технологий» (Краснодар, 2001), Международной тучно-практической конференции «Компьютерные технологии в науке, производстве, социальных и экономических процессах» (Новочеркасск, 2002), VIII Всероссийской научно-практической конференции «Инновационные процессы в гысшей школе» (Краснодар, 2002), Межрегиональном научном семинаре по проблемам современной математики и информатики (Армавир, 2003), X Юбилейной Всероссийской научно-практической конференции «Инновационные процессы в высшей школе» (Краснодар. 2004). Всероссийской научной конференции молодых ученых и студентов «Современное состояние и приоритеты развития фундаментальных наук в регионах» (Анапа, 2004) и других конференциях.

Данная работа выполнялась в рамках гранта Российского фонда фундаментальных исследований 0-01-96009 «Исследование и разработка принципов и методологии пос гроения регенеративных экспертных систем» и его развития.

Публикации. По теме диссертации опубликовано 24 печатные работы. Из них: 10 статей и 14 тезисов докладов на вышеперечисленных конференциях.

Основные положения, выносимые на защиту:

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

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

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

• программный исследовательский комплекс «Поиск» с ядром формальной ЭС для исследования и оценки эффективности различных методов оптимизации поиска решений;

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

Структура и объем диссертации. Диссертационная работа состоит из введения, четырех глав и заключения, изложенных на 183 страницах. Работа содержит 79 рисунков, 9 таблиц, библиографию из 102 наименований на 10 страницах и приложение.

КРАТКОЕ СОДЕРЖАНИЕ ДИССЕРТАЦИИ

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

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

пеней достоверности подмножества фактов (условий, не являющихся следствиями других правил).

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

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

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

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

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

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

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

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

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

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

1 - Л

гд,е/(Н) - средняя значимость схемы Н в момент времени ?;/= - средняя значимость всей популяции; рс, рт - вероятности кроссовера и мутации; 8(Н), о(Н), 1 - длина и порядок схемы, общая длина строки.

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

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

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

• для повышения эффективности работы машины логического Еывода (МЛВ) при доказательстве гипотез используются специальным образом организованные метазнания, надстраиваемые над БЗ, имеюшиг многоуровневую структуру и формируемые в процессе подготовки системы к работе;

• разрабатываемый метод опирается на нечеткую логику Заде;

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

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

где V, (¡=1,2, ...,п)~ степень достоверности факта /г„ д. = ...л'п) - степень достоверности гипотезы Н:.

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

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

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

Чтобы провести дискретизацию многопараметрического пространства Б и закодировать каждое возможное решение строкой з, «погрузим» равномерную сетку в пространство параметров, где каждый интервал разбивается на

к отрезков равной длины: И, - (Ь, - а) / к, / = 1, 2, ...,п. Используя двоичный алфавит {0,1} каждому узлу сетки s, можно присвоить уникальный бинарный код длины д, наиболее целесообразная и экономичная длина которого определяется из соотношения:

Проведя дискретизацию по всем N координатным осям, получим в л-мерном параллелепипеде Б пространственную решетку S с (к+1)" узлом, где каждый узел з можно представить в виде линейной последовательности таких записей (хромосом).

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

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

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

Рисунок 1 - Метод ГС: формирование второго метауровня БЗ

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

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

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

зация данных механизмов начинается с формирования для каждой гипотезы в соответствии с информацией 1-ого метауроЕНЯ БЗ хромосом по поступившим на вход системы значениям степеней достоверности терминальных фактов

Второй

М ножество особей с

/Л /< '

и множество особей с

=4=

ета уровень базы знаний

Два множества шаблонов с

ВЫСОКОЙ И (1ИЗХ0И

степенями

приспосо бтен

ности ЯТЯ гипотезы ИI

М ножество особей с

М2-> м'

и множество особей с

/Л р * к

Алгоритм Атгорнтм

формироьания формирования

двух хате! оркй двух категорий

шаблонов шабпонов

дтя гипотезы Я/ для гипотезы Н2

1 - - 1

Множество особей с

м'п > с' и множество особей с

V*» V ?

I

Алгоритм формирования двух категорий

шаблонов для гипотезы Н г

Два множества шаблонов с высокой и низкой степенями приспособлен

ности для гипотезы И] I

Два множества шаблонов с высокой н низкой степенями лрнсгособтен

ности дтя гипотезы Ип

Трети

метауровень базы знаний

Рисунок 2 - Метод ГС. формирование третьего метауровня 53

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

• проверка соответствия сформированной хромосомы одному из шаблонов третьего метауровня БЗ, если она подходит хотя бы к одной из схем «плохих» хромосом, то данная гипотеза отвергается, если она подходит к одной из схем «хороших» хромосом, то номер данной гипотезы заносится в 1-ый массив; если схемы третьего метауровня ни «хороших», ни «плохих» хромосом не включают сформированную кромосому. то номер данной гипотезы заносится во 2-ой массив;

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

• 2-ой массив применяется для пополнения информацией метауровней БЗ и используется в том случае, если 1-ый массив оказался пустым, для каждой

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

занная, и поиск заканчивается.

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

Третья глава посвящена созданию ПИК «Поиск», ядром которого является ФМЭС и который решает следующие задачи:

• создание, сохранение и выбор для исследования базы знаний;

• реализация и поддержка работы МЛВ:

• реализация ряда методов, з том числе метода ГС, поиска оптимальных решений в активной базе знаний;

• поддержка пользовательского интерфейса режима генерации метауров-ней БЗ методом ГС;

• поддержка процесса поиска оптимальных решений в активной БЗ любой совокупностью реализованных методов;

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

ПИК «Поиск» состоит из ряда модулей, основные из них: модуль генератора баз знаний, модуль МЛВ, модуль формирования метауровней БЗ. модуль накопления и анализа статистических данных (рис. 3).

Функционально ПИК «Поиск» объединяет две подсистемы: «Подготовка» и «Консультации». Первая - может быть запущена для использования сразу же после формирования БЗ для генерации метауровней, вторая - реализует непосредственно режим консультации и осуществляет поиск решений в ЭС четырьмя методами.

и

•е-

&

V

н в в я

а о л

н я а о м л Ч о

С

Рисунок 3 - Схема ПИК «Поиск»

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

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

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

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

деленным множеством влияющих на степень достоверности гипотезы терминальных фактов. Совокупность таких объектов используется для формирования 1 -ого метауровня БЗ для метода ГС. а также во всех других случаях, когда тре-

Генера ция

Генератор дерева вывода

Генератор степеней достоверностей фактов

Формирование информации 1 и2метадювнейБЗ

Формирование информации 3-его метауровня Б 3

Баз» млв

знании

Подго

товка

МгтодМО

Сташстюа метода МО

Консул ьтации

Т

Метод КГ

I Статистика I метода К Г

Метод ПГ

След метода МО

а

Мггод ГС

I

Дообучение

След Ста метода

метода КГ 1 ПГ

След метода ГС

ЕЕЕЕ

в & II

"3 с

&

Д.

Сравнительные диаграммы

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

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

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

Рисунок 4 - Влияние схемы размножения на количество холостых гипотез

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

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

та целевой функции и, следовательно к больше эффективному использованию ме тауровней базы знаний ЭС

Для сравнительной оценки эффекта* ности метода ГС с др\ гими методами были разработаны алгоритмы и программа накопления статистических данных для методов МО и КГ а также программным путем разработан и протестирован метод ПГ Результаты сравнения эффективности работы методов поиска приводятся на диаграммах, одна из которых показана на рис 5

Рисунок 5 - Сравните тьные диаграммы методов поиска

Причем сравнения проводитесь при различных значениях \же исследованных в работе параметров метода ГС, в частности при различных значениях параметров ГА Ллнейный тренд метода ГС свидететьствует о постепенном убывании числа холостых гипотез с ростом численности популяции ГА, и уже при числе особей р популяции большем 100 данный метод дает стабитьно лучшие, чем другие методы, результаты Количество гипотез, доказанных вхолостую при поиске решений в продукционной экспертной системе методом ГС, как минимум в 2-3 раза меньше, чем то, которое имеет ближайший по эффективности метод МО

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

В приложении приводятся акты внедрения результатов диссертационной работы

ВЫВОДЫ И РЕКОМЕНДАЦИИ В диссертационной работе теоретически обоснован, разработан, исследован и успешно реализован посредством (специально созданного для этих целей) программного исследовательского комплекса новый метод поиска опти-м&тьных решений в нечетких продукционных ЭС Основные научные результаты диссертации заключаются в следующем:

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

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

• проведен анализ существующих методов поиска оптимальных решений в ЭС с продукционным представ 1ением знаний, отмечены их достоинства и недостатки:

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

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

• показана необходимость трехуровневой архитектуры метазнаний, в которой первый метауровень представлен массивом множесгв терминальных фактов, каждое из которых используется при доказательстве определенной гипотезы: второй метауровень, формируемый с помощью ГА, содержит набор значений исходных параметров в виде хромосом, разбитых на две совокупности, для которых значения степени достоверности гипотезы ниже и выше заданного порога; а третий - предназначен для хранения двух совокупностей гиперплоскостей фактов, представляющих собой упакованные в схемы хромосомы второго уровня;

• определены характер и схемы использования информации каждого уровня

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

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

• создан программный исследовательский комплекс «Поиск», ядром которого является формальная модель ЭС, для экспериментального исследования разработанного в диссертации метода ГС и сравнения его с другими методами оптимизации;

• разработан и реализован сценарий формирования метауровней базы знаний в ПИК «ПОИСК»; описаны методика проведения эксперимента и средства управления его инициализацией и ходом процесса;

• показано, что созданный ПИК «Поиск» позволяет формально проектировать ЭС с продукционным представлением знаний и может быть использован как универсальный инструмент для исследования и оценки эффективности различных методов поиска;

• создана исследовательская среда в режиме «Консультации» для анализа процессов поиска оптимальных решений на основе метода ГС; разработаны алгоритм и программа реализации статистических методов поиска: математических ожиданий (МО) и корреляции (КГ);

• исследованы основные параметры метода ГС, при этом показано, что увеличение числа особей в поколении приводит к более плотному покрытию хромосомами участков ландшафта ЦФ и, следовательно, более эффективному использованию метауровней базы знаний ЭС;

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

СПИСОК ПУБЛИКАЦИЙ ПО ТЕМЕ ДИССЕРТАЦИИ

1. Частиков А.П., Алешин А.В., Частикова ВА Методология построения экспертных систем на основе инструментальных оболочек // Педагогические нововведения в высшей школе: технологии, методики, опыт. Материалы IV Всероссийской научно-методической конференции / КубГТУ. - Краснодар, 1998.

2. Частиков А.П, Савин ВА, Частикова З.А., Ничепуренко СВ. Проблемы создания экспертной системы синтеза ПТК для РСУ // Сб. Техническое и информационное обеспечение АСУ в пищевой промышленности / КубГТУ. - Краснодар, 1998.

3. Частиков А.П., Алешин А.В., Частикова ВА, Нилпуренко СВ. Принципы конструирования систем, основанных на знаниях // Педагогические нововведения в высшей школе: технологии, методики, опыт. Материалы IV Всероссийской научно-методической конференции / КубГТУ. - Краснодар, 1998.

4. Малыхина М.П., Частиков А.П., Частикова ВА Верификация баз знаний //Труды I Международной научно-практической конференции "Проб темы регионального управления, экономики, права и инновационных процессов в образовании". -Таганрог, 1999.

5. Малыхина М.П., Алешин А.В., Частикова ВА Процедуры регенеративного подхода к построению экспертных систем // Инновационные процессы в ЕЫС-шей школе. Материалы V Всероссийской научно-практической конференции /КубГТУ. - Краснодар, 1999.

6. Малыхина М.П., Алешин А.В., Частикова ВА Экспертная система для оценки качества учебных программ // Материалы X Международной конференции "Применение новых технологий в образовании", 30 июня-3 июля 1999 г. -Москва-Троицк, 1999.

7. Частиков А.П., Алешин А.В., Чгстикова ВА Использование метапродукций при проектировании систем, основанных на знаниях // Инновационные процессы в высшей школе. Материалы V Всероссийской научно-практической конференции / КубГТУ. - Краснодар, 1999.

8. Частиков А.П., Алешин А.В., Частикова ВА Выявление аномалий в базах знаний интеллектуальных систем // Международная научно-техническая конференция «50 лет развития кибернетики». Труды конференции. - СПб: СПбГТУ, 1999.

9. Частиков А.П., Алешин А.В., Частикова ВА Реализация параллельных вычислений в экспертных системах Ч Интеллектуальные много процессорные системы. Тезисы докладов международной научно-технической конференции 1-5 сентября 1999, Таганрог, 1999.

10. Частикова З.А., Алешин А.В. Технология разработки регенеративных экспертных систем // Сб. Информационные технологии в образовании. -Москва, 1999.

11. Частикова ВА, Мягкий А.Е., Ничепуренко СВ. Аномалии в экспертных системах // Сб. "Аппаратные и программные средства систем управления в пищевой промышленности". - Краснодар, 1999.

12. Частиков А.П., Алешин А.В., Частикова ВА. Принципы создания регенеративных экспертных систем // Информационные технологии в моделировании и управлении. Труды II Международной научно-практической конференции. СПб.: СПбГТУ, 2000.

13. Белов Д.Л.. Антонова О.Ю., Частикова ВА Методы решения задач с конфликтными ситуациями в системах принятия решений // Труды КубГТУ, том VII. - Краснодар, 2000.

14. Симанков B.C., Частикова ВА Генетические алгоритмы и программы для решения задач оптимизации // Материалы Международной научно-практической конференции "Компьютерные технологии в науке, производства социальных и экономических процессах". - Новочеркасск, 2000.

15. Частикова ВА., Алешин А.В. Применение механизмов параллельных вычис-пений в системах, основанных на знаниях // Материалы 1-й межрегиональной научно-практической конференции молодых ученых «Перспективы развития современных информационных технологий». - Краснодар, 2001.

16. Частикоза ВА Решение оптимизационных задач на основе генетических ал-гортмов // Материалы 1-й межрегиональной научно-практической конферен-

ции молодых ученых «Перспективы развития современных информационных технологий».-Краснодар, 2001.

17. Симанков B.C., Частикова В.А. Генетические алгоритмы: теория и приложения // Труды VII Международной научно-практической конференции "Инновационные процессы в высшей школе". - Краснодар, 2001.

18. Симанков B.C., Частикова В.А. Генетический поиск оптимальных решений в интеллектуальных системах, основанных на знаниях // Труды VIII Всероссийской научно-практической конференции "Инновационные процессы в высшей школе". - Краснодар, 2002.

19. Симанков B.C., Частикова В.А. Сравнительный анализ генетических алгоритмов с традиционными методами оптимизации // Труды К>бГТУ, том XVIII, серия «Информатика и управление». - Краснодар, 2003.

20. Симанков B.C., Частикова В.А. Генетические алгоритмы и поиск оптимальных решений // Автоматизация и современные технологии. - Москва, 2003, № 6.

21. Частикова В.А. Применение генетических алгоритмов для оптимизации процессов поиска решений в экспертных системах Ч Современные проблемы математики и информатики: Сб. науч. трудов. Вып. 1. - Армавир: РИУ АГПУ, 2004.

22. Частикова В.А. Имитационная модель интеллектуальной системы, основанной на знаниях // Материалы X Юбилейной Всероссийской научно-практической конференции «Инновационные процессы в высшей школе». -Краснодар, 2004.

23. Частикова В.А. Метод генетического поиска решений в экспертных системах с метауровневой организацией знаний // Материачы X Юбилейной Всероссийской научно-практической конференции «Инновационные процессы в высшей школе». - Краснодар, 2004.

24. Частикова В.А. Генетический поиск оптимальных решений в экспертных системах // Материалы Всероссийской научной конференции молодых ученых и студентов «Современное состояние и приоритеты развития фундаментальных наук в регионах». - Анапа, 2004.

Подписано в печать 28.04.05 г. Зак. № 1154. Тираж 100 экз.

Лиц. ПД№ 10-47020от 11.09.2000 Типография КубГТУ. 350058, Краснодар, ул. Старокубанская, 88/4

969

14 > г'

' - In

ВВЕДЕНИЕ.

1 СОСТОЯНИЕ ВОПРОСА. СУЩНОСТЬ ПРОБЛЕМЫ. АНАЛИТИЧЕСКИЙ ОБЗОР СУЩЕСТВУЮЩИХ МЕТОДОВ.

1.1 Общие сведения.

1.2 Проблема поиска решений в интеллектуальных системах обработки экспертной информации.

1.2.1 Детерминированные методы поиска.

1.2.2 Статистические методы поиска.

1.3 Генетические алгоритмы — новый подход к оптимизации процессов поиска решений в экспертных системах.

1.4 Цели и задачи исследования.

Выводы по главе 1.

2 ТЕОРЕТИЧЕСКОЕ ОБОСНОВАНИЕ И РАЗРАБОТКА МЕТОДА ОПТИМИЗАЦИИ ПРОЦЕССА ПОИСКА РЕШЕНИЙ В ЭКСПЕРТНЫХ СИСТЕМАХ НА ОСНОВЕ ГЕНЕТИЧЕСКИХ АЛГОРИТМОВ.

2.1 Некоторые сведения из эволюционной теории.

2.2 Теоретические основы ГА.

2.2.1 Простой ГА.

2.2.2 Модифицированный ГА.

2.2.3 Механизмы размножения ГА.

2.3 Теорема схем.

2.3.1 Последствия воздействия операторов ГА на состав схем.

2.3.2 Гипотеза о строительных блоках.

2.3.3 Область эффективного действия ГА.

2.3.4 Шаблоны схем и гиперплоскости.

2.4 Разработка метода поиска оптимальных решений в экспертных системах на основе ГА.

2.4.1 Исходные концепции.

2.4.2 Описание метода.

2.4.3 Алгоритм поиска решений.

Выводы по главе 2.

3 СОЗДАНИЕ ПРОГРАММНОГО ИССЛЕДОВАТЕЛЬСКОГО КОМПЛЕКСА «ПОИСК».

3.1 Цели и задачи комплекса.

3.2 Структура программного исследовательского комплекса «ПОИСК»

3.3 Генератор баз знаний.

3.4 Модуль машины логического вывода.

3.5 Методика проведения эксперимента на ПИК «ПОИСК».

Выводы по главе 3.

4 ИССЛЕДОВАНИЕ МЕТОДА ГЕНЕТИЧЕСКИХ СХЕМ И СРАВНИТЕЛЬНЫЙ АНАЛИЗ С ДРУГИМИ МЕТОДАМИ ПОИСКА РЕШЕНИЙ В ЭКСПЕРТНЫХ СИСТЕМАХ.

4.1 Исследовательская среда в режиме «Консультации».

4.2 Режимы метода генетических схем.

4.3 Исследование основных параметров ГА и их оптимизация.

4.3.1 Влияние численности популяции.

4.3.2 Влияние длины бинарных кодировок.

4.3.3 Механизм отбора родительских пар.

4.3.4 Выбор схемы размножения.

4.3.5 Выбор типа оператора кроссовера.

4.3.6 Выбор способа формирования родительской пары.

4.3.7 Влияние на эффективность поиска типа используемого оператора мутации.

4.3.8 Влияние оператора инверсии на эффективность поиска.

4.4 Сравнительная оценка эффективности метода ГС.

4.4.1 Параметры метода корреляции.

4.4.2 История консультаций.

4.4.3 Сравнительные диаграммы процессов поиска.

Выводы по главе 4.

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

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

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

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

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

Методы исследования. Поставленные задачи решены с применением методов искусственного интеллекта, инженерии знаний и экспертных систем, теории генетических алгоритмов (ГА) и эволюционного программирования, теории графов и нечетких множеств, методов математической статистики, оптимизации и математического моделирования. Научная новизна: сформулированы исходные положения для разработки метода поиска оптимальных решений в ЭС с продукционным представлением знаний на основе эволюционно-генетического подхода; теоретически обоснован и разработан новый метод - метод генетических схем (ГС) для оптимального поиска решений в продукционных ЭС с использованием генетических алгоритмов и специальным образом организованных метазнаний, формируемых в процессе подготовки системы к работе; обоснована и разработана трехуровневая организация базы метазнаний, определены характер и схемы использования информации каждого метауровня для обеспечения высокой эффективности поиска в режиме консультаций; на основе разработанного метода ГС построен алгоритм работы ЭС с продукционным представлением знаний в режиме консультации; создан программный исследовательский комплекс (ПИК) «ПОИСК», ядром которого является ФМЭС и который может быть использован как универсальный инструмент для исследования, сравнительного анализа и оценки эффективности различных методов оптимизации поиска решений в ЭС; исследовано влияние основных параметров нового метода ГС на эффективность поиска; показано на основании сравнительного анализа, что метод генетических схем при поиске решений с ростом численности популяции дает стабильно лучшие результаты, чем другие методы.

Практическая ценность. Впервые на практике ГА были применены в такой области, как системы обработки экспертной информации.

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

Разработанный в диссертации ПИК «ПОИСК» позволяет строить экспертные системы продукционного типа для различных предметных областей, а также проводить эксперименты по поиску решений в этих системах, используя различные методы оптимизации. ПИК «ПОИСК» реализован на персональном компьютере типа Pentium 4 и разработан средствами языка С++ Builder 6 с применением среды разработки приложений.

ПИК «ПОИСК» и разработанный автором метод генетических схем были внедрены при проектировании ЭС для решения задач прогнозирования на предприятии Армавирские электрические сети АО Кубаньэнерго (г. Армавир), а также в учебном процессе КубГТУ в курсах «Системы искусственного интеллекта» и «Методы принятия решений», что подтверждается соответствующими актами.

Апробация работы. Основные положения диссертационной работы докладывались и обсуждались на 14 Международных, Всероссийских и региональных научных конференциях и семинарах, в том числе: на X Международной конференции «Применение новых технологий в образовании» (Москва-Троицк, 1999), Международной научно-технической конференции «50 лет развития кибернетики» (Санкт-Петербург, 1999), Международной научно-технической конференции «Интеллектуальные многопроцессорные системы» (Таганрог, 1999), 2-й Международной научно-технической конференции «Информационные технологии в моделировании и управлении» (Санкт-Петербург, 2000), 1-й Межрегиональной научно-практической конференции молодых ученых «Перспективы развития современных информационных технологий» (Краснодар, 2001), -Международной научно-практической конференции «Компьютерные технологии в науке, производстве, социальных и экономических процессах» (Новочеркасск, 2002), VIII Всероссийской научно-практической конференции «Инновационные процессы в высшей школе» (Краснодар, 2002), Межрегиональном научном семинаре по проблемам современной математики и информатики (Армавир, 2003), X Юбилейной

Всероссийской научно-практической конференции «Инновационные процессы в высшей школе» (Краснодар, 2004), Всероссийской научной конференции молодых ученых и студентов «Современное состояние и приоритеты развития фундаментальных наук в регионах» (Анапа, 2004) и других конференциях.

Публикации. По теме диссертации опубликовано 24 печатные работы. Из них: 10 статей и 14 тезисов докладов на вышеперечисленных конференциях. Основные положения, выносимые на защиту: принципы, основные концепции эволюционно-генетического подхода к проблеме оптимизации процессов поиска решений в интеллектуальных системах обработки экспертной информации; метод генетических схем для поиска оптимальных решений в экспертных системах с продукционным представлением знаний; алгоритмическая и программная реализация метода генетических схем при работе экспертной системы в режиме консультаций; программный исследовательский комплекс «ПОИСК» с ядром формальной ЭС для исследования и оценки эффективности различных методов оптимизации поиска решений; методика и технология исследования основных параметров метода генетических схем и результаты сравнительного анализа его с другими методами при поиске оптимальных решений.

Структура и объем работы.

Работа содержит 79 рисунков, 9 таблиц, библиографию из 102 наименований на 10 страницах и приложения на 2 страницах.

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

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

Третья глава посвящена созданию программного исследовательского комплекса «ПОИСК» (ПИК «ПОИСК») с ядром формальной экспертной системы для экспериментального исследования разработанного в диссертации метода поиска оптимальных решений на основе ГА и сравнения его с другими методами оптимизации. Разработана структура ПИК «ПОИСК», определены основные функции и процессы взаимодействия всех составляющих программных модулей комплекса. Показано, что созданный ПИК «ПОИСК» позволяет проектировать экспертные системы с продукционным представлением знаний с различными параметрами, такими как, объем базы знаний (число правил), глубина базы знаний (число уровней), связанность базы знаний (число уровней в правиле), введение степеней достоверности при обработке нечетких знаний. Описан сценарий работы программного исследовательского комплекса «ПОИСК» при проведении экспериментов, и показана универсальность комплекса для исследования и оценки эффективности различных методов оптимизации поиска решений в экспертных системах.

Четвертая глава посвящена исследованию метода генетических схем и его сравнительному анализу с другими методами поиска решений в экспертных системах. Разработаны исследовательская среда в режиме «Консультации», алгоритмы и программы накопления статистических данных для использования методов математических ожиданий и корреляции для их сравнения с генетическим поиском. Исследованы основные параметры метода ГС, такие как, численность популяции, длина бинарных кодировок, тип используемого оператора кроссовера и количество решений, генерируемых на каждой итерации, вероятность применения и тип используемого оператора мутации, вероятность используемого оператора инверсии. Показано на основании сравнительного анализа, что линейный тренд метода ГС свидетельствует о постепенном убывании числа холостых гипотез при поиске решений с ростом численности популяции ГА и что уже при числе особей в популяции больше 100, разработанный метод дает стабильно лучшие результаты, чем другие методы. В этой главе доказано, что влияние численности популяции, увеличение числа особей в поколении приводит к более плотному покрытию хромосомами, а значит и шимами, удовлетворительных участков ландшафта целевой функции и, следовательно, к более эффективному использованию метауровней базы знаний экспертной системы. Также показано, что оптимальные значения ряда параметров ГА, такие как тип оператора кроссовера, вероятность и тип оператора мутации, вероятность оператора инверсии, используемые как факторы регулирования сходимости процесса поиска и его доводки, определяются в общем случае априори неизвестным поведением и сложностью ландшафта целевой функции и должны подбираться экспериментально с помощью средств программного исследовательского комплекса.

В приложении приведены акты внедрения результатов диссертационной работы.

Выводы по главе 4

1. Создана исследовательская среда режима «Консультации» для анализа процессов поиска оптимальных решений на основе метода генетических схем и сравнения его с другими методами.

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

3. Программным путем разработан и протестирован метод последовательного перебора для сравнительного анализа с новым методом на основе ГА.

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

5. На основании сравнительного анализа показано, что линейный тренд метода ГС свидетельствует о постепенном убывании числа холостых гипотез при поиске решений с ростом численности популяции ГА, и что уже при числе особей в популяции большем 100 разработанный метод дает стабильно лучшие результаты, чем другие методы.

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

ЗАКЛЮЧЕНИЕ

Основные научные результаты диссертационного исследования заключаются в следующем:

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

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

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

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

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

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

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

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

- создан программный исследовательский комплекс «ПОИСК», ядром которого является формальная ; модель экспертной системы, для экспериментального исследования разработанного в диссертации метода генетических схем и сравнения его с другими методами оптимизации;

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

- разработан и реализован сценарий формирования метауровней базы знаний в программном исследовательском комплексе «ПОИСК»; описана методика проведения на данном комплексе эксперимента, а также средства управления его инициализацией и ходом процесса;

- создана исследовательская среда в режиме «Консультации» для анализа процессов поиска оптимальных решений на основе метода ГС и сравнения его с другими методами, для чего разработаны алгоритм и программа накопления статистических данных для использования методов математических ожиданий (МО) и корреляции для сравнительного анализа с методом ГС;

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

- на основании сравнительного анализа показано, что метод ГС при поиске решений в продукционных экспертных системах с ростом численности популяций дает стабильно лучшие результаты, чем другие методы, причем количество гипотез, доказанных вхолостую при поиске решений методом ГС, как минимум в 2-3 раза меньше, чем то, которое имеет ближайший по эффективности метод МО; аналогичные сравнения метода ГС с методом перебора показали, что эффективность метода ГС также как минимум в 3-4 раза превосходит эффективность метода перебора и в 6-10 раз - метод корреляции, при этом метод ГС во всех проведенных экспериментах работает устойчиво и имеет наибольшую эффективность.

По теме диссертации опубликовано 24 печатных работы. Из них 10 статей и 14 тезисов докладов на Международных и Всероссийских конференциях.

1. Нечеткие множества в моделях управления и искусственного интеллекта / Аверкин А.Н., Батыршин И.З., Блишун А.Ф., Силов В.Б., Тарасов В.Б.; Под ред. Поспелова Д.А. М.: Наука. Гл. ред. физ.-мат. лит., 1986. -312с.

2. Амамия М., Танака Ю. Архитектура ЭВМ и искусственный интеллект. М.: Мир, 1993.-400с.

3. Батищев Д.И., Исаев С.А., Ремер Е.К. Эволюционно-генетический подход к решению задач невыпуклой оптимизации // Оптимизация и моделирование в автоматизированных системах: Сб. научных трудов. — Воронеж: Изд-во ВГТУ, 1998. с. 20-28.

4. Белов Д.Л., Антипова О.Ю., Частикова В.А. Методы решения задач с конфликтными ситуациями в системах принятия решений // Труды КубГТУ, том VII. Краснодар, 2001. - с. 153-159.

5. Бельченко В.Е., Дедкова Т.Г., Частиков А.П. Инструментальные средства программирования экспертных систем (Оболочки экспертных систем): Уч. пос. Краснодар: Изд-во КубГТУ, 1994.- 102 с.

6. Бельченко В.Е. Автореферат диссертации на соискание ученой степени кандидата технических наук по спец. 05.13.06 Автоматизированные системы управления. - Краснодар, 1995. - 25 с.

7. Брукинг А., Джонс П., Кокс Ф. и др.; под редакцией Форсайта Р. Экспертные системы. Принципы работы и примеры: Пер. с англ. — М.: Радио и связь, 1987.-224 с.

8. Букатова И.Л. Эволюционное моделирование и его приложения. М.: Наука, 1979.

9. Букатова И.Л. и др. Эвоинформатика. Теория и практика эволюционного моделирования. М: Наука, 1991.

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

11. Галеев Э.М., Тихомиров В.М. Оптимизация: теория, примеры, задачи. — М.: Эдиториал УССР, 2000. 320 с.

12. Девятков В.В. Системы искусственного интеллекта: Уч. пос. для вузов. М.: Изд-во МГТУ им. Н.Э. Баумана, 2001. - 352 с.

13. Джексон П. Введение в экспертные системы.: Пер. с англ.: Уч. пос. — М.: Издательский дом «Вильяме», 2001. 624 с.

14. Заде Л. Понятие лингвистической переменной и его применение к принятию приближенных решений. М.: МИР, 1976.

15. Искусственный интеллект: В 3 кн. 1 Системы общения и экспертные системы. Справочник под ред. Попова Э.В. М.: Радио и связь, 1990. -464 с.

16. Карманов В.Г. Математическое программирование. М.: Наука, 1975. -272 с.

17. Керов JI.A., Частиков А.П. и др. Экспертные системы: инструментальные средства разработки: Уч. пос. СПб.: Политехника, 1996. — 220 с.

18. Корнеев В.В., Гарев А.Ф., Васютин С.В., Райх В.В. Базы данных. Интеллектуальная обработка информации. М.: Нолидж, 2000. - 352 с.

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

20. Курейчик В.М. Методы генетического поиска: Учебное пособие. Часть I. Таганрог: Изд-во ТРТУ, 1998. - 118 с.

21. Курейчик В.М., Лебедев Б.К., Лях А.В., Проблемы эволюционной адаптации в САПР. Новинтех, №3, 1991.

22. Курейчик В.В. Генетические алгоритмы в проектировании СБИС: Учебное пособие. Таганрог: Изд-во ТРТУ, 1997.

23. Курейчик В.М., Зинченко Л.А. Эволюционное моделирование на основе символьных ИТ. Интеллектуальное управление: Новые ИТ в задачах управления. М.: Наука, Физматлит, 1999. с. 65-68.

24. Курейчик В.М. Генетические алгоритмы. Обзор и состояние. Новости искусственного интеллекта, №3. М: РАИИ, 1998. - с. 14-63.

25. Курейчик В.В. Эволюционные, синергетические и гомеостатические методы принятия решений. Монография. Таганрог: Изд-во ТРТУ, 2001.-221 с.

26. Курейчик В.М. Генетические алгоритмы. Монография. Таганрог: Изд-во ТРТУ, 1998. - 242 с.

27. Курейчик В.В., Курейчик В.М. Об управлении на основе генетического поиска. Автоматика и телемеханика, №10, 2001. - с. 174-187.

28. Курейчик B.M. Генетические алгоритмы. Состояние. Проблемы. Перспективы. Известия АН. Теория и системы управления, №1, 1999. - с. 144-160.

29. Малыхина М.П., Частиков А.П., Частикова В.А. Верификация баз знаний // Труды I Международной научно-практической конференции «Проблемы регионального управления, экономики, права и инновационных процессов в образовании». — Таганрог, 1999.

30. Малыхина М.П., Алешин А.В., Частикова В.А. Процедуры регенеративного подхода к построению экспертных систем // Инновационные процессы в высшей школе. Материалы V Всероссийской научно-практической конференции / КубГТУ. Часть II. Краснодар, 1999.

31. Моисеев Н.Н., Иванилов Ю.П., Столярова Е.М. Методы оптимизации. -М.: Наука, 1978.-352 с.

32. Попов Э.В. и др. Статистические и динамические экспертные системы.- М.: Финансы и статистика, 1996. 320 с.

33. Растригин JI.A. Статистические методы поиска. М.: Наука, 1968.

34. Симанков B.C. Автоматизация системных исследований: Монография.- Краснодар: Изд-во КубГТУ, 2002. 376 с.

35. Симанков B.C., Частикова В.А. Генетические алгоритмы: теория и приложения // Труды VII Международной научно-практической конференции «Инновационные процессы в высшей школе». Краснодар, 2001.

36. Симанков B.C., Частикова В.А. Генетический поиск оптимальных решений в интеллектуальных системах, основанных на знаниях // Труды VIII Всероссийской научно-практической конференции «Инновационные процессы в высшей школе». Краснодар, 2002.

37. Симанков B.C., Частикова В.А. Сравнительный анализ генетических алгоритмов с традиционными методами оптимизации // Труды КубГТУ, том XVIII, серия «Информатика и управление». Краснодар, 2003.

38. Симанков B.C., Частикова В.А. Генетические алгоритмы и поиск оптимальных решений // Автоматизация и современные технологии. — Москва, 2003, №6.

39. Сойер Б., Фостер Д.Л. Программирование экспертных систем на Паскале. М.: Финансы и статистика, 1990. - 191 с.

40. Таусенд К., Фохт Д. Проектирование и программная реализация экспертных систем на персональных ЭВМ. М.: Финансы и статистика, 1990.-320 с.

41. Уотерман Д. Руководство по экспертным системам. М.: Мир, 1989. — 300 с.

42. Фаронов В.В., Шумаков П.В. Delphi 5. Руководство разработчика баз данных. М.: Нолидж, 2000. - 640 с.

43. Частиков А.П., Гаврилова Т.А., Белов Д.Л. Разработка экспертных систем. Среда CLIPS. СПб.: BHV - Петербург, 2003. - 608 с.

44. Частиков А.П., Бельченко В.Е. и др. Построение продукционных экспертных систем в среде CLIPPER. Материалы конференции «Гибридные экспертные системы в задачах проектирования сложных технических объектов». СПб., 1992. - с. 126-128.

45. Частиков А.П., Бельченко В.Е. и др. Критерии оценки различных методологий построения экспертных систем. Материалы конференции «Гибридные экспертные системы в задачах проектирования сложных технических объектов». СПб., 1992. - с. 25-27.

46. Частиков А.П., Савин В.А., Частикова В.А., Ничепуренко С.В. Проблемы создания экспертной системы синтеза ПТК для РСУ // Сб. Техническое и информационное обеспечение АСУ в пищевой промышленности / КубГТУ. Краснодар, 1998.

47. Частиков А.П., Алешин А.В., Частикова В.А. Выявление аномалий в базах знаний интеллектуальных систем // Международная научно- техническая конференция «50 лет развития кибернетики». Труды конференции. СПб: СПбГТУ, 1999.

48. Частиков А.П., Алешин А.В., Частикова В.А. Реализация параллельных вычислений в экспертных системах // Интеллектуальные многопроцессорные системы. Тезисы докладов международной технической конференции 1-5 сентября 1999, Таганрог.

49. Частиков А.П., Алешин А.В., Частикова В.А. Принципы создания регенеративных экспертных систем // Информационные технологии в моделировании и управлении. Труды II Международной научно- практической конференции. СПб.: Изд-во СПбГТУ, 2000.

50. Частикова В.А., Мягкий А.Е., Ничепуренко С.В. Аномалии в экспертных системах // Сб. научных трудов «Аппаратные и программные средства систем управления в пищевой промышленности». Краснодар, 1999.

51. Частикова В.А., Алешин А.В. Технология разработки регенеративных экспертных систем // Информационные технологии в образовании. Часть II: Интеграция информационных технологий в образовании. Сб. трудов IX Международной конференции-выставки. Москва, 1999.

52. Частикова В.А. Решение оптимизационных задач на основе генетических алгоритмов // Материалы Первой межрегиональной научно- практической конференции молодых ученых «Перспективы развития современных информационных технологий». Краснодар, 2001.

53. Частикова В.А. Применение генетических алгоритмов для оптимизации процессов поиска решений в экспертных системах // Современные проблемы математики и информатики: Сб. науч. трудов. Вып. 1. Армавир, РИУ АГПУ, 2004, с. 72-76.

54. Частикова В.А. Имимтационная модель интеллектуальной системы, основанной на знаниях // Материалы X Юбилейной Всероссийской научно-практической конференции «Инновационные процессы в высшей школе». Краснодар, 2004.

55. Частикова В.А. Метод генетического поиска решений в экспертных системах с метауровневой организацией знаний // Материалы X Юбилейной Всероссийской научно-практической конференции «Инновационные процессы в высшей школе». Краснодар, 2004.

56. Частикова В.А. Генетический поиск оптимальных решений в экспертных системах // Материалы Всероссийской научной конференции молодых ученых и студентов «Современное состояние и приоритеты развития фундаментальных наук в регионах». Анапа, 2004.

57. Экспертные системы для персональных компьютеров: методы, средства реализации: Справочное пособие // Крисевич В.А., Кузьмич J1.A., Шиф A.M. и др. Минск: Вышэйшая школа. - 197 с.

58. Элти Дж., Кумбс М. Экспертные системы: концепции и примеры. М.: Финансы и статистика, 1987. - 190 с.

59. Holland J. Н. Adaptation in Natural and Artificial Systems. An Introductory Analysis with Application to Biology, Control, and Artificial Intelligence. University of Michigan, 1975, 210 p.

60. Goldberg David E. Genetic Algorithms in Search, Optimization and Machine Learning. Addison- Wesley Publishing Company, Inc, 1989, 412 p.

61. Handbook of Genetic Algorithms, Edited by Lawrence Davis. Van Nostrand Reinhold, New York, 1991, 412 p.

62. Foundation of Genetic Algorithms. Rawens Gregory (Editor). Morgan Kaufman Publishers, San Mateo, California, USA, 1991, 437 p.

63. Guckles B.P., Party F.E. Genetic Algorithms. IEEE Computer Society Press, Los Alamos, LA, USA, 1992, 89 p.

64. Koza J.R. Genetic Programming: On the Programming of Computers by Means of Natural Selection. MIT Press, Cambrige, Mass, 1992.

65. Mitchell M. An Introduction to Genetic Algorithms. MIT Press, Cambrige, Mass, 1996.

66. Michalewicz Z. Genetic Algorithms + Data Structures = Evolution Programs. Springer-Verlay, New York, 1992.

67. Fogel L.J., Ownes A.J., Walsh M.J. Artificial Intelligence through Simulated Evolution, J. Wiley & Sons, 1966.

68. Practical Handbook of GENETIC ALGORITHMS: applications, volume 1. Edited by Lance Chambers. CRC Press, 1995, 555 p.

69. Practical Handbook of GENETIC ALGORITHMS: new frontiers, volume 2. Edited by Lance Chambers. CRC Press, 1995, 435 p.

70. Practical Handbook of GENETIC ALGORITHMS: complex coding systems, volume 3. Edited by Lance Chambers. CRC Press, 1999, 572 p.

71. Genetic Algorithms and Evolution Strategy in Engineering and Computer Science. Edited by D. Quagliarella and et all. J. Wiley & Sons, NY, USA, 1998, 391 p.

72. Mange A.P., Mange E.J. Genetics Human Aspects Saunder College. Philadelphia, USA, 1982.

73. Ackley D.H. A Connection Machine for Genetic Hillclimbing. Kluwer Academic Publishers, Boston, USA, 1987, 240 p.

74. Mattfeld D.C. Evolutionary search and Job Shop: Investigations of Genetic Algorithms for Production Sheduling, Springer-Verlay, Berlin-Heidelberg,1996, 152 p.

75. Genetic Algorithms and Simulated Annealing. Editor L. Davis, Pitman, London, 1987,216 р.

76. Back Т., Fogel D.B., and Michalewicz Z. Handbook of Evolution Computation. Oxford University Press, New York, and Institute of Publishing, Bristol,1997.

77. Post C.I., Giddens T.D., Yadav S.B. The Development and Evaluation of an Improved Genetic Algorithm Based on Migration and Artificial selection. IEEE Trans. On Systems, Man and Gybernetics, vol. 24, № 1, 1994, p. 7386.

78. Shahookar R., Mazumder P. Genetic Approach to Standard Cell Placement Using Meta-genetic Parameter Optimization. IEEE Trans. On CAD, vol. 9, 1990, p. 500-511.

79. Goldberg D.E., Lingle R. Alleles, Loci, and the Traveling Salesman Problem. Proc. International Conference on Genetic Algorithms and their applications.

80. Grefenstette J., Gopal G., Rosmaita В., D. van Gucht. Genetic algorithms for the traveling salesman problem. Proc. Intern. Conf. of Genetic Algorithms and their applications. John Grefenstette, ed. P. 160-165.

81. Back T. Evolutionary Algorithmus in Theory and Practice. Oxford University Press, New York, 1996.

82. Grefenstette J.J. (ed) Genetic Algorithms for Machine Learning. Kluwer Academic Press, USA, 1994.

83. Herrera F., and Verdegay J.L. (eds) Genetic Algorithms and Soft Computing. Physica-Verlag, 1996.

84. Cohoon J.P. and Paris W.D. Genetic placement. IEEE Trans. Comput. -Aided Des. Integrated Circuits & Syst., vol. 6, no. 6, 1987, p. 956-964.

85. Chandraserharam R., Subhramanian S., Chaundhury S. Genetic algorithm for node partitioning problem and application in VLSIdesing. IEE Proceed-ings-E., vol. 140., no. 5, 1993, p. 255-260.

86. Newell A. Production systems: models of control structures // Visual Information processing. New York: Academic Press, 1973. - p. 463-526.