Нечеткий генетический алгоритм решения многокритериальной задачи о назначениях

Размещено на http://www.allbest.ru//

Размещено на http://www.allbest.ru//

Технологический институт Южного федерального университета

Нечеткий генетический алгоритм решения многокритериальной задачи о назначениях

Л.А. Гладков

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

Введение

В общем виде, задача о назначениях может быть сформулирована следующим образом. Пусть имеется n работников, которые претендуют на n вакансий. Каждый из работников может выполнять только одну работу. Эффективность выполнения i-м работником j-й работы различна. Она зависит от квалификации работника и задается квадратной матрицей стоимостей C = ||cij||nЧn. Необходимо распределить работников по видам работ таким образом, чтобы суммарная эффективность выполнения всех видов работ была максимальной.

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

Подобные задачи часто называют многокритериальными задачами о назначениях. Постановка многокритериальной задачи о назначениях может быть сформулирована следующим образом [Ларичев, 2000]:

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

Очевидно, что решение для решения многокритериальной задачи о назначениях невозможно без эффективных человеко-машинных систем поиска и поддержки принятия решений [Ларичев и др., 1998].

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

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

1. Описание алгоритма

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

На основании приведенных выше соображений можно использовать следующий комплексный критерий оценки эффективности работы i-й команды [Hongboetal., 2000]:

Ei = (ai + bi + ci + di + …) pi1pi2pi3pi4pi5 … (1.1)

гдеai, bi, ci, di, … - эффективность работы членов i-той команды;

pi1, pi2, pi3, pi4, pi5, …- изменяющиеся коэффициенты i-того модуля, которые определяют учитываемые нечеткие показатели. При этом должно соблюдаться условие:

pi1pi2pi3pi4pi5 … ? 1.

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

.(1.2)

1.2 Структура алгоритма

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

Методика кодирования решений: ГА работает с популяцией хромосом, каждая из которых представляет собой альтернативный вариант решения проблемы. Методика кодирования в генетическом алгоритме - основа его развития, которая непосредственно влияет на механизм и виды применяемых генетических операторов и на работу генетического алгоритма в целом. В нашем случае решение будет представлять собой матрицу, состоящую из нулевых элементов. Изменение значения элемента матрицы подразумевает назначение i-го работника в j-ю команду. Каждая из специальностей имеет свой номер. Например, ненулевой элемент матрицы 20…01, означает, что работник специальности № 2 назначен в команду № 1 и т.д. Столбец матрицы подразумевает некий вариант распределения специалистов соответствующей категории по командам. Например:

Начальная популяция: начальная популяция создается случайным образом. Возможен вариант, когда число команд и число кандидатов в различных категориях специалистов могут не совпадать. Например, в конкурсе могут участвовать 6 кандидатов специальности № 1; 8 кандидатов специальности № 2; 7 кандидатов специальности № 3 и т.д., которых нужно назначить в 6 команд. При этом каждый кандидатов в пределах своей категории имеет одинаковые шансы присоединиться к любой команде.

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

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

Кроссинговер: оператор кроссинговера применяется к выбранным парам родителей с вероятностью равной заданной норме кроссинговера. В данном алгоритме применяется модифицированный оператор кроссинговера, позволяющий оперировать с элементами матрицы и при этом не создавать некорректных решений (когда один кандидат одновременно назначается в разные команды) в процессе выполнения операции. Например, из решений A и B после выполнения операции кроссинговера создаются решения C и D:

Мутация: операция мутации изменяет одно из решений. При этом необходимо, чтобы полученные решения были корректными. Для этого те кандидаты, которые не принимали участие в процессе назначения в последнем поколении, в максимально степени должны включаться в группу для обмена и создания новых решений. Так, перед выполнением оператора мутации новые кандидаты той же специальности добавляются в конец списка (фрагмент A). Пусть случайным образом из списка выбраны точки 3 и 7. В результате после выполнения оператора мутации получим фрагмент B:

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

1.3 Нечеткий логический контроллер

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

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

Нечеткий логический контроллер оперирует лингвистическими переменными, такими как, NL (negativelarge) - «значительное ухудшение», NS (negativesmall) - «незначительное ухудшение», ZE (zero) - «частичное изменение», PS (positivesmall) - «незначительное улучшение», PL (positivelarge) - «значительное улучшение».

Формирование управляющего воздействия НЛК осуществляет на основе оценки двух параметров [Hongboetal., 2000]:

,

,

гдеt - временной шаг;

fmax(t) - лучшее значение ЦФ на итерации t;

fave(t) - среднее значение ЦФ на итерации t;

fave(t - 1) - среднее значение ЦФ на итерации (t - 1).

Параметры e1, e2 заданы на следующем интервале:

e1[0; 1];

e2[-1; 1].

Выходной параметр ?Pc(t) определяющий вероятность выполнения кроссинговера задан на интервале: ?Pc(t) [-0.1; 0.1]. Выходной параметр для оператора мутации ?Pm(t) тот, же что и для кроссинговера. Отсюда видно, что вероятности могут меняться не более, чем на 10%. Тогда используем четкие значения, чтобы изменить вероятности Pc и Pm следующим образом:

Pc(t) = Pc(t- 1) + ?Pc(t),

Pm(t) = Pm(t- 1) + ?Pm(t).

НЛК представляет собой двумерный набор нечетких правил

Табл. 1.

Нечеткие правила для ОК (?Pc(t))

Табл. 2.

Нечеткие правила для ОM (?Pm(t))

Так, например, если на входе нечеткого логического контроллера заданы следующие параметры e1 = ZE и e2 = NL, то согласно приведенным таблицам получим:

?Pc(t) = NS, ?Pm(t) = PS.

многокритериальный нечеткий генетический алгоритм

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

Pc(t) = Pc(t -1) + NS,

Pm(t) = Pm(t-1) + PS.

То есть, при заданных значениях параметров e1 и e2 вероятность кроссинговера «немного» уменьшится, а вероятность мутации «значительно» увеличится.

Для эффективной работы нечеткого генетического алгоритма необходимо провести тестирование и настройку, как входных сигналов, так и соответствующих им управляющих воздействий нечеткого логического контроллера [Гладков и др., 2009].

1.4 Псевдокод алгоритма

Предложенную структуру нечеткого генетического алгоритма можно описать в виде следующего псевдокода:

Начало НГА

t = 0 Iterationcounter

Формирование начальной популяцииP(t)

Расчет ЦФ популяции P(t)

Пока (не выполнено условие останова)

{

t = t + l

Селекция

ОКP(t)

ОМP(t)

Расчет ЦФP(t)

ОтборP(t)

Регулировка параметров ГА

{

НЛК (e1, e2)

Обновляем параметры

}

}

Конец НГА

Заключение

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

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

Благодарности. Работа выполнена при поддержке РФФИ, грант № 08-01-00473 и программы развития научного потенциала высшей школы 2009-2010 гг. (РНП. 2.1.2.1652)

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

[Гладков и др. 2009] Гладков Л.А., Кныш Д.С., Криницкая А.Е. Решение задач оптимизации на основе нечетких генетических алгоритмов. // Интеллектуальные системы. Коллективная монография. Выпуск третий. - М.: Физматлит, 2009.

[Ларичев 2000] Ларичев О.И. Теория и методы принятия решений. - М.: Логос, 2000.

[Ларичев и др., 1998] Ларичев О. И., Стернин М. Ю. Человеко-машинные методы решения многокритериальной задачи о назначениях // Автоматика и телемеханика. 1998. Т. 59, № 7.

[Herrera et al., 1996] Herrera F., Lozano M. Adaptation of genetic algorithm parameters based on fuzzy logic controllers. In: F. Herrera, J. L. Verdegay (eds.) Genetic Algorithms and Soft Computing, Physica-Verlag, Heidelberg, 1996.

[Hongbo et al., 2000]Hongbo Liu, Zhanguo Xu, Ajith Abraham. Hybrid Fuzzy-Genetic Algorithm Approach for Crew Grouping. - Source unknown.

Размещено на Allbest.ru