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

Для исследования эффективности использования и оценки качественных характеристик теоретически обоснованного и разработанного автором метода генетических схем (ГС) для оптимального поиска решений в продукционных экспертных системах (ЭС) с использованием генетических алгоритмов и специальным образом организованных метазнаний и сравнения его с другими методами и алгоритмами оптимизации был создан специальный программный исследовательский комплекс (ПИК) «Поиск», ядром которого является формальная модель экспертной системы (ФМЭС) [1, 4]. ПИК «Поиск» решает следующие задачи:

• — создание базы знаний (БЗ) в соответствии с требуемой сложностью (число уровней, количество терминальных фактов, количество гипотез, максимальное число условий в правиле);
• — сохранение базы знаний;
• — выбор для исследования любой из хранимых баз знаний;
• — создание и поддержка функционирования машины логического вывода [5];
• — реализация ряда методов, в том числе метода ГС, поиска оптимальных решений в активной базе знаний;
• — поддержка пользовательского интерфейса режима генерации метауровней базы знаний методом ГС с возможностью вариации ряда ключевых параметров как генетических алгоритмов, так и ряда других алгоритмов, используемых методом ГС;
• — поддержка процесса поиска оптимальных решений в активной базе знаний любым реализованным методом, либо любой совокупностью выбранных из их числа методов;
• — поддержка сравнительного анализа качества поиска выбранных для исследования методов.

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

Рассматриваются следующие основные параметры ГА:

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

Оценка метода ГС, а также сравнение его с другими методами должна базироваться на некотором «алгоритмонезависимом» признаке, в качестве которого используется число оценок целевой функции (ЦФ), или иначе — число гипотез, доказанных вхолостую [5].

Влияние численности популяции на точность выхода на достоверную гипотезу. Исследование влияния численности популяции на эффективность поиска оптимального решения в ЭС проводилось при различных фиксированных значениях прочих параметров [2]. Характер влияния практически везде одинаков и совпадает с приведенным ниже случаем.

Для значений параметров, установленных в окне «Консультации» ПИК «Поиск» и представленных на рисунках 1 и 2, и различной численности популяций получены результаты, приведенные в таблице 1 и на диаграмме рисунка 3.

Рисунок 1 — Значения параметров метода ГС окна «Консультации».

Рисунок 2 — Метод ГС: окно «Параметры генетики».

Таблица 1 — Влияние численности популяции на количество холостых гипотез.

На диаграмме рисунка 3 приведено суммарное число холостых гипотез, полученное при выполнении 100 экспериментов при каждом запуске теста для одного и того же дерева БЗ.

Рисунок 3 — Влияние численности популяции на число гипотез, доказанных вхолостую Линейный тренд диаграммы влияния численности популяции на число гипотез, доказанных методом ГС вхолостую, приведенный на рисунке 4, свидетельствует о постепенном убывании числа холостых гипотез с ростом численности популяции ГА, и уже при числе особей в популяции большем 200 данный метод дает стабильно удовлетворительные результаты.

Рисунок 4 — Линейный тренд результатов поиска.

Влияние численности популяции на время работы ГА. От того, какова численность популяции, безусловно, зависит время работы ГА. Так, например, для дерева БЗ с 15-ю гипотезами и 4-мя уровнями при 200 особях в популяции максимальное время выполнения ГА max (t_ГА) = 0.016с., а при 800 особей при прочих равных условиях — max (t_ГА)=0.109 с. Помимо этого возрастает также время на упаковку хромосом в схемы. Тем не менее, стоит отметить тот факт, что, хотя с ростом численности популяции общее время на формирование метауровней БЗ возрастает, но это возрастание не столь масштабно. К тому же работа ГА осуществляется в рамках подсистемы «Подготовка» и на режим «Консультации» напрямую не влияет. Косвенное же влияние численности популяции на режим «Консультаций» сказывается в том, что увеличение числа особей в поколении приводит к более плотному покрытию хромосомами, а значит и схемами, ландшафта целевой функции и, следовательно, более эффективному использованию метауровней БЗ экспертной системы. бинарный кодировка генетический Определив порог численности популяции, преодолев который метод ГС позволяет выйти на стабильные результаты поиска решений в ЭС, в дальнейшем все внимание сосредоточено на исследовании влияния ряда параметров метода ГС, которые позволяют еще более повысить его эффективность.