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

RATIONALE OF THE PROBLEM WITH PREDICTION OF GENETIC ALGORITHM RESULTS

Vladimir Ivanov

Candidate of Science, Assistant professor, Director of Center of eScience&Learning

of Tver State Technical University,

Russia, Tver

АННОТАЦИЯ

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

ABSTRACT

This article presents and explains the problem with prediction of the genetic algorithm results developed to perform a subject document search. The article alleges the necessity and usefulness of the verification Holland's scheme theorem for a specified algorithm. The correct test conditions and requirements including the query genotype representation and smoothing of the fitness function are described. The genotype representation method that uses the distance between vectors is offered.

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

Keywords: genetic algorithm; genotype; query; representation; crossover; defining length; order; schema; subject search; Holland's theorem; fitness function.

Введение

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

В настоящей статье обосновывается и формулируется постановка задачи прогнозирования результатов ГА, разработанного для выполнения документного тематического поиска. Отмечены условия корректной проверки выполнения теоремы Холланда, в частности требования к кодированию генотипа и сглаживанию фитнес-функции. Предложен метод кодирования генотипа, который использует расстояние между векторами. Тематика данной статьи продолжает ранее выполненные исследования автора и его коллег.

Теорема схем

В теории генетических алгоритмов (ГА) фундаментальная теорема схем Дж. Холланда [3] говорит нам, что схемы хромосом, имеющие короткую определяющую длину, низкий порядок и значение фитнес-функции выше среднего значения по популяции, экспоненциально увеличивают количество своих представителей в последовательности поколений. Математически это выражается следующим неравенством:

                            (1)

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

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

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

В целом теорема схем Холланда, а также теория схем Поли-Лэнгдона (Poli-Langdon) для генетического программирования [7] дают формальное обоснование понимания многих аспектов поведения ГА и позволяют выявить и использовать улучшающие модификации ГА, повышающие его адаптивность. Хорошим обзором на эту тему является [6].

Предыстория исследований

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

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

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

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

Постановка задачи

Предполагая применение более формальных методов, мы формулируем задачу исследования в общем виде как проверку выполнения теоремы Холланда для ГА, разработанного для документного тематического поиска.

Основные понятия подхода, использованного при разработке ГА, изложены в [5]. Так, исходные интерпретации следующие: запрос – это хромосома, кодированный набор термов запроса представляет собой генотип, замена терма запроса на другой терм определяется как кроссинговер, замена терма запроса на его синоним – как мутация. Дискуссионным вопросом является то, что считать фенотипом: набор исходных термов запроса (ключевых слов) или результаты запроса (найденные релевантные документы). Неоднозначность связана с принятым методом вычисления фитнес-функции, который предусматривает выполнение запроса поисковой системой и использование параметров множества найденных результатов.

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

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

Значение фитнес-функции для популяции запросов вычисляется следующим образом [5]:

                                                   (2)

где:  – популяция из N запросов;  – значение фитнес-функции j-го запроса.

                                                    (3)

где:  – значение фитнес-функции для i-го результата j-го запроса (зависит от позиции g в списке результатов поисковой системы, частоты p появления данного результата поиска в списках результатов всех N запросов); общее количество результатов запросов, степени сходства s краткого текста результата и поискового образа K.

Запрос (хромосома) в ГА кодируется вектором , где  – количество термов в запросе. Для выполнения генетических операций вектор  представляется в виде вектора  – двоичной строки с постоянной длиной , где  определяет локус ненулевого значения. Примеры кодирования запросов для  представлены в табл. 1, а пример выполнения одноточечного кроссинговера запросов – в табл. 2.

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

Таким образом, для проверки выполнения теоремы Холланда для ГА, разработанного для документного тематического поиска, необходимо:

1. Предложить такой метод кодирования генотипа, который обеспечивал бы небольшие значения определяющей длины и порядка схемы при сохранении существующих правил выполнения генетических операторов в обсуждаемом ГА.
2. Подтвердить для метода кодирования сглаженность фитнес-функции: малые изменения генотипа должны приводить к малым изменениям значений фитнес-функции. Поскольку значение фитнес-функции локально зависит от результатов выполнения запроса в поисковой системе, для подтверждения необходим вычислительный эксперимент.
3. Обеспечить генерацию неизоморфных схем из ранее полученных результатов работы обсуждаемого ГА [4; 5].
4. Выполнить экспериментальную проверку теоремы Холланда, а также оценить число схем, обрабатываемых в каждом поколении (по Холланду это число имеет порядок ).
5. При проверке использовать результаты тематического поиска, полученные для разных тематических сегментов, поскольку ГА разрабатывался как инвариантный к предметной области.

Таблица 1.

Примеры кодирования запросов в ГА

Таблица 2.

Пример выполнения одноточечного кроссинговера запросов в ГА

Выбор метода кодирования генотипа

В нашем случае компоненты вектора  или гены  имеют целочисленные значения. При двоичном представлении гена его размер вычисляется следующим образом:

                                                              (4)

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

                                                                      (5)

Например, при типичных значениях =50, =4 длина хромосомы будет равна  бита, что нельзя считать удовлетворительным значением (хотя оно и лучше, чем ).

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

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

                  (6)

                                              (7)

     (8)

             (9)

Отметим, что во всех случаях, кроме , требуется нормирование вещественных значений метрик на интервал [0, 1].

Примеры кодирования запросов для  представлены в табл. 3. Для определения , используется формула для расчета евклидова расстояния, начальный вектор – первый запрос. Результат нормирован с помощью выражения:

                                (10)

где:  и  – максимальное и минимальное значение среди всех результатов вычислений .

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

Таблица 3.

Примеры кодирования запросов с помощью расстояний между векторами

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

Заключение

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

Список литературы:

1. Иванов В.К., Мескин П.И. Реализация генетического алгоритма для эффективного документального тематического поиска // Программные продукты и системы. – Тверь: Центрпрограммсистем, 2014. – № 4 (108). – С. 125–134.
2. Goldberg D.E. Genetic Algorithms in Search, Optimization and Machine Learning. – Addison-Wesley, 1989. – 412 с.
3. Holland J.H. Adaptation in Natural and Artificial Systems: An Introductory Analysis with Applications to Biology, Control, and Artificial Intelligence (The MIT Press, 1992).
4. Ivanov V.K., Palyukh B.V., Sotnikov A.N. Approaches to the Intelligent Subject Search // Federated Conference on Computer Science and Information Systems (FedCSIS'2014) (September 7–10, 2014. Warsaw, Poland). Annals of Computer Science and Information Systems. Vol. 3. Position Papers, – Warsawa, 2014. – P. 13–20.
5. Ivanov V.K., Palyukh B.V., Sotnikov A. N. Efficiency of Genetic Algorithm For Subject Search Queries // Lobachevskii Journal of Mathematics, 2016, Vol. 37, № 3, P. 244–254.
6. Liles W.C. Introduction to Schema Theory: A survey lecture of pessimistic & exact schema theory / W.C. Liles, R.P. Wiegand // Summer Lecture Series, EC lab Activities, Computer Science Department, George Mason University. – 2002. – P. 12–23.
7. Poli W.B. Langdon, and N.F. McPhee. A field guide to genetic programming. Published via http://lulu.com and freely available at http://www.gp-field-guide.org.uk (With contributions by J.R. Koza) (Дата обращения 18.08.2016).