ISSN 0236-235X (P)
ISSN 2311-2735 (E)

Journal influence

Higher Attestation Commission (VAK) - К1 quartile
Russian Science Citation Index (RSCI)

Bookmark

Next issue

4
Publication date:
09 September 2024

Determination of weight coefficients for additive fitness function of genetic algorithm

Date of submission article: 16.12.2019
UDC: 004.89;519.816
The article was published in issue no. № 1, 2020 [ pp. 047-053 ]
Abstract:The paper presents a solution for the problem of choosing a method for analytical determining of weight factors for a genetic algorithm additive fitness function. This algorithm is the basis for an evolu-tionary process, which forms a stable and effective query population in a search engine to obtain high-ly relevant results. The paper gives a formal description of an algorithm fitness function, which is a weighted sum of three heterogeneous criteria. The selected methods for analytical determining of weight factors are described in detail. It is noted that expert assessment methods are impossible to use. The authors present a research methodology us-ing the experimental results from earlier in the discussed project “Data Warehouse Support on the Base Intellectual Web Crawler and Evolutionary Model for Target Information Selection”. There is a de-scription of an initial dataset with data ranges for calculating weights. The calculation order is illustrat-ed by examples. The research results in graphical form demonstrate the fitness function behavior dur-ing the genetic algorithm operation using various weighting options. The analysis of the results implies that it is more preferable to calculate fitness function weight fac-tors for this query population then using the results of all population queries. The conclusion is based on the presence of successive improvements in query populations which reflect the correct operation of genetic algorithms, as well as on the obvious detection of local and global maxima in the fitness function during experiments. When using other methods of calculating weighting factors there is no such thing. Thus, a method for determining weight factors for an additive optimality criterion can improve ge-netic algorithm quality to generate effective search queries. In particular, the probability of rapid detection of fitness function local extremes is increased and this local extreme can become the optimal solution the function domain.
Аннотация:Представлено возможное решение задачи выбора способа аналитического определения весовых коэффициентов для аддитивной фитнес-функции генетического алгоритма. Этот алгоритм является основой эволюционного процесса, формирующего в поисковой системе устойчивую и эффективную популяцию запросов для получения высокорелевантных результатов. Приведено формальное описание фитнес-функции алгоритма, которая представляет собой взвешенную сумму трех неоднородных критериев. Подробно описаны выбранные способы аналитического определения весовых коэффициентов, при этом отмечается невозможность использования методов экспертных оценок. Рассмотрена методика проведения исследований. Описывается исходный набор данных, в том числе диапазоны данных, принятые для вычисления весовых коэффициентов различными способами. Порядок вычислений проиллюстрирован примерами. Результаты исследований, показанные в графической форме, наглядно демонстрируют поведение фитнес-функции при работе генетического алгоритма с использованием различных вариантов весовых коэффициентов. Анализ результатов позволяет сделать вывод о предпочтительности расчета весовых коэффициентов фитнес-функции данной популяции запросов, выполненного с использованием результатов всех запросов этой популяции. Вывод базируется на наличии последовательных улучшений популяций запросов, характерных для корректной работы генетических алгоритмов, а также на очевидном обнаружении в ходе экспериментов локальных и глобального максимумов фитнес-функции. При использовании других способов расчета весовых коэффициентов подобного не наблюдается. Способ определения весовых коэффициентов для аддитивного критерия оптимальности может повысить качество работы генетического алгоритма для формирования эффективных поисковых запросов. В частности, повышается вероятность быстрого обнаружения локальных экстремумов фитнесфункции, которые на заданной области ее определения могут стать оптимальным решением.
Authors: Ivanov V.K. (mtivk@mail.ru) - Tver State Technical University, Tver, Russia, Ph.D, D.S. Dumina (dumina97@mail.ru) - Tver State Technical University (Graduate Student), Tver, Russia, Semenov N.A. (dmitrievtstu@mail.ru) - Tver State Technical University, Tver, Russia, Ph.D
Keywords: relevancy, search query, data warehouse, fitness function, weight factor, additive function, generic algorithm
Page views: 6638
PDF version article
Full issue in PDF (4.91Mb)

Font size:       Font:

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

Значение фитнес-функции ГАП определяет качество поисковых запросов и вычисляется для каждого найденного документа в результате выполнения запроса. Это значение зависит от следующих факторов: позиция документа в ранжированном списке результатов запроса, вхождение данного документа в списки результатов других запросов, семантическая близость к адаптивно модифицируемому исходному набору ключевых термов – поисковому паттерну.

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

Описание ГАП и его фитнес-функции

В работах [1, 2] отмечается, что в ГАП поисковый паттерн K для документов есть набор термов, относящихся к некоторой предметной области. Каждый поисковый запрос представлен вектором  = (c1, c2, …, cn, …, cm), где cn = {kn, wn, Sn}, kn Î K – терм; wn – вес терма; Sn – множество синонимов терма kn; m – количество термов в запросе. Результат выполнения запроса – это набор документов R, ½R½ = D. Исходная популяция из N поисковых запросов представлена множеством Q0, где ½Q0½ = N, N < ½K½/2,  Î Q0. Результатом поискового запроса является множество документов R, которое формируется после выполнения  в поисковой системе (Bing, Google, БД SQL, данные в структуре XML и т.п.).

Эволюционная операция скрещивания (одно- или двухточечный кроссовер) реализуется обменом термами между запросами, то есть компонентами векторов  для репродукции запросов используется генотипный аутбридинг. Адекватная операция мутации – это вероятностная замена синонимом k’n Î Sn  случайно выбранного терма запроса kn. При формировании новой популяции запросов используется элитарный отбор. Условием остановки алгоритма в общем случае считается стабильность популяции.

Значение фитнес-функции, или функции пригодности  определяет качество запросов; ГАП ищет максимум

                                (1)

где  – фитнес-функция j-го запроса популяции,

                               (2)

где wi – фитнес-функция для i-го результата j-го запроса – результата ri имеет вид аддитивного критерия оптимальности:

wi = wgg + wpp + wss.                                (3)

Значение g учитывает ранг для ri, установленный поисковой системой:

, ,    (4)

где  – номер позиции ri в ранжированном списке результатов j-го запроса популяции; gmax, gmin – наибольшее и наименьшее значения g(ri, R) среди всех результатов запросов популяции.

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

, ,      (5)

где , если ri присутствует в списке результатов j-го запроса, иначе ; pmax, pmin – наибольшее и наименьшее значения p(ri, R) среди всех результатов запросов популяции.

Значение s определяет семантическую близость ri и поискового образа K. В работе используется косинусная мера близости векторов документов, как это принято в векторной модели пространства документов [3]. Таким образом,

,                           (6)

где  – вектор i-го результата запроса, T – количество термов в тексте результата запроса после морфологического анализа (принимаются во внимание только существительные и прилагательные) и лемматизации (в качестве текста результата используются заголовок документа и его краткое описание (сниппет)),  – вес i-го терма из текста результата запроса,  – частота использования термина в этом тексте, , Rn – число результатов, текст которых содержит n-й терм i-го результата;  – вектор поискового образа документов K,  – вес m-го терма из K, , Rm – число результатов, текст которых содержит m-й терм из K; wg, wp, ws – весовые коэффициенты для g, p, s соответственно.

Способы аналитического определения весовых коэффициентов

Как уже отмечалось, задачей являлось исследование способов аналитического определения веса (или значимости) каждого фактора, влияющего на значение фитнес-функции. То есть необходимо определить значения весовых коэффициентов wg, wp и ws для факторных переменных g, p и s в соответствии с (3).

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

Оценка значений весовых коэффициентов с использованием экспертных методов включает следующие основные этапы: определение цели, формирование группы экспертов, разработка сценария и процедур экспертизы, сбор и анализ экспертной информации, анализ результатов экспертизы. Очевидно, что в рассматриваемом случае даже хорошо обоснованные экспертные методы [7] не подходят. Основная причина в отсутствии критериев для совместной сравнительной оценки факторов экспертами. Поэтому разумным представляется принять, что wg = wp = ws.

Рассмотрим некоторые способы и приемы, позволяющие по информации о качестве значений факторных переменных определять значения весовых коэффициентов wk [8, 9].

Способ 1. Для каждого частного критерия Fk(X) > 0, k = 1, 2, …, c, вычисляется коэффициент относительного разброса dk, который определяет максимально возможное отклонение по k-му частному критерию:

,                            (7)

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

                                     (8)

Способ 2. Пусть все  тогда можно рассмотреть отклонение частного критерия от его наименьшего значения:

.                               (9)

Предположим, что важность k-го критерия зависит от выполнения неравенства

                                           (10)

Величины xk задаются из условия, что, чем важнее критерий, тем меньшее значение xk выбирается. Геометрическая интерпретация выполнения неравенства (10) будет следующей. Пусть  – наибольший радиус шара, постро- енного около точки минимума  для критерия Fk(X), внутри которого точки  удовлетворяют условию (10). Тогда

.                     (11)

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

.                                (12)

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

Методика проведения исследований

Для вычисления весовых коэффициентов описанными выше способами использовались результаты экспериментов с ГАП, выполненных ранее (https://www.rfbr.ru/rffi/ru/project_ search/o_2071601). Исходный набор K был сформирован из терминов предметной области, касающейся управления эволюцией технологических процессов на промышленных предприятиях. Использовались поисковая система Bing и следующий исходный набор значений основных параметров:

-     количество запросов в генерируемых популяциях K = 5;

-     количество ключевых слов в каждом генерируемом запросе M = 8;

-     максимальное количество результатов поиска, возвращаемых запросом Rq = 20, либо популяцией запросов RQ = 20, либо суммарно всеми популяциями R = 20;

-     вероятность мутации запроса pm = 0,1;

-     число проходов алгоритма (или число генерируемых популяций) NQ = 200.

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

Фрагмент исходных данных в качестве примера представлен в таблице.

Весовые коэффициенты wg, wp и ws необходимо вычислить способами 1 и 2. Причем вычисления должны быть произведены для следующих диапазонов исходных данных:

-     результаты выполнения каждого запроса популяции, 1 £ ri £ Rq;

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

-     результаты выполнения запросов всех популяций,

Фрагмент исходных данных

Source data chunk

№ популяции

№ особи (запроса)

g(ri, R)

g

p(ri, R)

p

s(ri, R)

s

145

559

44,00

0,43

7,75

1,00

0,05

0,42

145

559

44,00

0,43

7,75

1,00

0,07

0,56

145

559

26,00

0,66

2,50

0,32

0,06

0,45

145

559

23,00

0,70

1,75

0,23

0,06

0,46

….

….

145

560

8,00

0,90

1,75

0,23

0,07

0,54

145

560

4,00

0,95

1,00

0,13

0,07

0,54

145

560

6,00

0,92

1,00

0,13

0,07

0,55

145

560

44,00

0,43

7,75

1,00

0,08

0,61

145

561

21,00

0,73

1,75

0,23

0,09

0,70

145

561

4,00

0,95

1,00

0,13

0,07

0,51

….

….

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

dg = 1 – (0,43/0,95) = 0,5474,

dp = 1 – (0,13/1,00) = 0,8700,

ds = 1 – (0,05/0,09) = 0,4444.

Тогда весовые коэффициенты примут следующие значения:

wg = 0,5474/(0,5474 + 0,8700 + 0,4444) = 0,294,

wp = 0,8700/(0,5474 + 0,8700 + 0,4444) = 0,467,

ws = 0,4444/(0,5474 + 0,8700 + 0,4444) = 0,239.

Отметим, что wg + wp + ws = 1.

Порядок вычислений значений весовых коэффициентов по способу 2 (пример). В качестве исходных данных также примем исходные данные из таблицы. Пусть xg = 33, xp = 33, xs = 34. Тогда, в соответствии с (10):

bg = (F(g) – 0,43)/0,43 £ 0,33 при F(g) £ 0,4719,

bp = (F(p) – 0,13)/0,13 £ 0,33 при F(g) £ 0,3729,

bs = (F(s) – 0,42)/0,42 £ 0,32 при F(g) £ 0,4828.

Следовательно:

Тогда весовые коэффициенты примут следующие значения:

wg = 0,4719/(0,4719 + 0,3729 + 0,4828) = 0,355,

wp = 0,3729/(0,4719 + 0,3729 + 0,4828) = 0,281,

ws = 0,4828/(0,4719 + 0,3729 + 0,4828) = 0,364.

Отметим, что wg + wp + ws = 1.

Вычисленные значения весовых коэффициентов wg, wp и ws = 1, а также весовые коэффициенты для случая wg = wp = ws должны быть использованы для вычисления фитнес-функции  Далее должен быть проведен сравнительный анализ поведения функции при выполнении ГАП с исходным набором K.

 

Результаты исследований

 

На рисунке 1 представлены графики зависимости значений фитнес-функции  от номеров популяций запросов, порожденных ГАП. Вычисление  производилось для документов из диапазона , где ri – номер i-го документа в результатах выполнения запросов всех популяций.

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

На рисунке 3 приведены графики зависимости значений фитнес-функции  от номеров первых 10 популяций запросов, порожденных ГАП. Вычисление  производилось для документов из диапазона 1 £ ri £ Rq.

Во всех случаях весовые коэффициенты wg, wp и ws принимались равными друг другу, а также вычислялись описанными выше способами 1 и 2. Соответственно, на графиках использованы следующие обозначения фитнес-функции: Wequ при wg = wp = ws; Wdis при вычислении wg, wp и ws способом 1; Wrad при вычислении wg, wp и ws способом 2.

Обсуждение результатов

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

1. Как следует из рисунка 1, графики фитнес-функций Wequ, Wdis и Wrad, значения которых вычислены по результатам выполнения за-  

Рис. 1. Значения фитнес-функции   
вычисленные по результатам выполнения
запросов всех популяций

Fig. 1. The values of   fitness function 
calculated by query execution results 
of all populations

 

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

Fig. 2. The values of   fitness function 
calculated by query execution results 
of every population

 

Рис. 3. Значения фитнес-функции   
вычисленные по результатам выполнения
каждого запроса популяции

Fig. 3. The values of fitness function calculated 
by execution results of every population query
просов всех популяций, в большой степени по- хожи. Можно предположить, что Wrad = Wequ + + dequ и Wrad = Wdis + ddis, причем ddis > dequ  и , где  и R(d) – области значений  и d соответственно. На всех трех графиках отчетливо видны локальный и глобальный максимумы  достигаемые практически в одних и тех же точках. В целом при данном диапазоне исходных данных ни один из предложенных способов расчета весовых коэффициентов не дает очевидных преимуществ.

2. При анализе графика функции Wrad на рисунке 2 можно увидеть, что при работе ГАП на заданной области определения Wrad отчетливо видны два локальных максимума, причем первый из них достигается достаточно быстро (в пределах 10 популяций). Также можно видеть последовательные улучшения популяций запросов, характерные для корректной работы генетических алгоритмов. На графиках функций Wequ и Wdis подобного не наблюдается: точка первого локального максимума пропущена, точка второго локального максимума совпадает с аналогичной точкой для Wrad, но сам максимум менее выражен. Вывод – расчет весовых коэффициентов по способу 2 с использованием результатов выполнения запросов каждой популяции представляется более предпочтительным.

3. Графики фитнес-функций Wequ, Wdis и Wrad показывают наличие локальных максимумов, найденных ГАП. Однако точки максимумов различны для всех вариантов  Из-за небольшого количества шагов выполнения ГАП формулировка каких-либо выводов для данного диапазона исходных данных, используемого при расчете весовых коэффициентов, пока преждевременна.

Заключение

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

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

Исследование выполнено при финансовой поддержке РФФИ в рамках научного проекта № 18-07-00358 А.

Литература

1.    Ivanov V.K., Palyukh B.V., Sotnikov A.N. Efficiency of genetic algorithm for subject search queries. Lobachevskii J. of Mathematics, 2016, vol. 12, no. 3, pp. 244–254.

2.    Иванов В.К., Мескин П.И. Реализация генетического алгоритма для эффективного документального тематического поиска // Программные продукты и системы. 2014. № 4. С. 118–126. DOI: 10.15827/0236-235X.108.118-126.

3.    Salton G., Wong A., Yang C.S. A vector space model for automatic indexing. Communications of the ACM, 1975, vol. 18, pp. 613–620.

4.    Подиновский В.В., Потапов М.А. Метод взвешенной суммы критериев в анализе многокритериальных решений: Pro et contra // Бизнес-информатика. 2013. № 3. С. 41–48.

5.    Подиновский В.В. Чувствительность многокритериального выбора к изменению оценок важности неоднородных критериев // ИТНОУ. 2017. № 4. С. 23–27.

6.    Sorooshian S., Parsia Y. Modified weighted sum method for decisions with altered sources of information. Mathematics and Statistics, 2019, vol. 7, no. 3, pp. 57–60. URL: http://www.hrpub.org/download/20190630/MS1-13412797.pdf (дата обращения: 10.12.2019). DOI: 10.13189/ms.2019.070301.

7.    Спиридонов С.Б., Булатова И.Г., Постников В.М. Анализ подходов к выбору весовых коэффициентов критериев методом парного сравнения критериев // Науковедение. 2017. Т. 9. № 6. URL: https://naukovedenie.ru/PDF/16TVN617.pdf (дата обращения: 10.12.2019).

8.    Гудков П.А. Методы сравнительного анализа. Пенза, 2008. 81 с.

9.    Карпушкин С.В. Теория принятия проектных решений. Тамбов: Изд-во ТГТУ, 2015. 86 с.

10. Al-Shargabi B., Sabri O., Aljawarneh Sh. An enhanced arabic information retrieval using genetic algorithms: an experimental study and results. Aust. J. Basic & Appl. Sci., 2013, vol. 7, no. 13, pp. 242–248.

References

  1. Ivanov V.K., Palyukh B.V., Sotnikov A.N. Efficiency of genetic algorithm for subject search queries. Lobachevskii J. of Mathematics. 2016, vol. 12, no. 3, pp. 244–254.
  2. Ivanov V.K., Meskin P.I. Genetic algorithm implementation for effective document subject search. Software & Systems. 2014, no. 4, pp. 118–126. DOI: 10.15827/0236-235X.108.118-126 (in Russ.).
  3. Salton G., Wong A., Yang C.S. A vector space model for automatic indexing. Communications of the ACM. 1975, vol. 18, pp. 613–620.
  4. Podinovsky V.V., Potapov M.A. Weighted sum method in the analysis of multicriterial decisions: pro et contra. Business Informatics. 2013, no. 3, pp. 41–48 (in Russ.).
  5. Podinovsky V.V. Sensitivity of multi-criterial selection to change assessment assessments of inhomogeneous criteria. ITNOU. 2017, no. 4, pp. 23–27 (in Russ.).
  6. Sorooshian S., Parsia Y. Modified weighted sum method for decisions with altered sources of information. Mathematics and Statistics. 2019, vol. 7, no. 3, pp. 57–60. Available at: http://www.hrpub.org/download/20190630/MS1-13412797.pdf (accessed December, 10, 2019). DOI: 10.13189/ms.2019.070301.
  7. Spiridonov S.B., Bulatova I.G., Postnikov V.M. Analysis of approaches to the choice of weighting criteria method of pair comparison of criteria. Int. J. Naukovedenie. 2017, vol. 9, no. 6. Available at: https://naukovedenie.ru/PDF/16TVN617.pdf (accessed December, 10, 2019) (in Russ.).
  8. Gudkov P.A. Benchmarking Methods. Penza, 2008, 81 p.
  9. Karpushkin S.V. Decision Theory. Tambov, TSTU Publ., 2015, 86 p. (in Russ.).
  10. Al-Shargabi B., Sabri O., Aljawarneh Sh. An enhanced arabic information retrieval using genetic algorithms: an experimental study and results. Aust. J. Basic & Appl. Sci. 2013, vol. 7, no. 13, pp. 242–248.

Permanent link:
http://swsys.ru/index.php?page=article&id=4676&lang=&lang=en&like=1
Print version
Full issue in PDF (4.91Mb)
The article was published in issue no. № 1, 2020 [ pp. 047-053 ]

Perhaps, you might be interested in the following articles of similar topics: