Abstract

Abstract

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

Full Text

В настоящей работе рассматривается следующая задача. Задано множество допустимых решений D, и на нем определены m знакопостоянных целевых функций (критериев эффективности) fi(X), по которым лицо, принимающее решение, (ЛПР) оценивает решения. Необходимо помочь ЛПР выбрать наилучшее в смысле его предпочтений решение на D. Для решения этой задачи построим генетический алгоритм. Известно, что решение многокритериальной задачи следует искать на множестве Парето [1]. Элементы этого множества будем порождать генетическим алгоритмом. Для получения паретовских решений используем свертку (1) где – веса критериев, удовлетворяющие условиям (2) , (3) для критерия на минимум и , (4) для критерия на максимум, и – минимальное и максимальное значения i-го критерия на множестве D. Свертка (1) при условиях (2) гарантирует, как минимум, слабую эффективность получаемых решений [1]. В качестве параметров фенотипа возьмем веса критериев . В генотипе используем вещественное кодирование параметров и число генов, равное m – 1. Последнее обусловлено необходимостью выполнения равенства в (2). Таким образом, генотип представляется строкой фиксированной длины g1g2. . .gi. . .gm–1 При этом аллели генов gi должны удовлетворять неравенству 0 < gi < 1, i =1, 2… m – 1. (5) Для удобства декодирования хромосом наложим еще одно требование на генотип: аллели генов слева направо должны строго возрастать. Тогда веса критериев определяются по формулам: (6) В качестве функции приспособленности (fitness function) можно взять , (7) где Xj – решение задачи (1) для j-й хромосомы, или , (8) где в случае fi ®min соответствующее слагаемое заменяется на . Тогда в идеальном (утопическом) решении будем иметь: При необходимости ЛПР может задать коэффициенты важности li слагаемых в (7) или (8), которые при условиях не изменяют идеальных значений и Но в отличие от весов коэффициенты li остаются неизменными на протяжении всей работы алгоритма (они применяются только к уже найденным решениям). Как следует из вышеприведенных формул, перед обращением к генетическому алгоритму необходимо знать значения всех С этой целью решаются m однокритериальных задач: Теперь опишем генетический алгоритм. Предварительный этап состоит в создании начальной популяции. Она генерируется датчиком случайных чисел с равномерным распределением или для более равномерного покрытия области (5) в виде ЛПt-последовательности [2, 3]. Завершается создание начальной популяции упорядочением генов во всех хромосомах по возрастанию их аллелей. Для оценки качества хромосомы она декодируется по формулам (6), затем решается задача (1)–(2), дающая значения всех критериев fi, и, наконец, вычисляется функция приспособленности. Очевидно, что эти действия повторяются Np раз, где Np – размер популяции. Основной этап алгоритма начинается с селекции – отбора родительских хромосом. Целесообразно использовать один из двух стандартных методов: метод рулетки или турнирный метод. Для увеличения контрастности качества хромосом в первом методе вероятности их перехода в родительский пул можно находить по формуле (9) где . Дважды применив к текущей популяции выбранный оператор селекции, получаем родительскую пару. Учитывая специфику задачи, используем элитизм: при нечетном значении Np в следующее поколение переходит без изменений лучшая особь, а при четном Np – две лучшие особи текущего поколения, и число родительских пар будет равно (Np – 1)/2 или (Np – 2)/2. При этом ко всем родительским парам применяется оператор скрещивания. Исходя из того, что у потомков гены должны сохранять упорядоченность по аллелям, используем одноточечный кроссовер. Если применение кроссовера приводит к нарушению упорядоченности генов в потомках, его действие отменяется, а в качестве потомков принимаются родители. Из описания оператора следует, что вероятность скрещивания Pc < 1. Потомки подвергаются мутации с вероятностью Pm. Гены просматриваются последовательно, и если случайное число соответствует принятой величине Pm, ген мутирует. При этом ген принимает новое случайное значение из диапазона gi–1 < gi <gi+1 при i Î[2, m – 2], а значения крайних генов должны быть в пределах 0<g1<g2, gm–2< gm– 1 < 1. Такое условие мутирования сохраняет упорядоченность генов потомков. В результате действия операторов селекции, скрещивания и мутации создается новая популяция. Качество ее особей оценивается так же, как на предварительном этапе. Условием окончания работы алгоритма (критерием останова) может быть неулучшение среднего значения функции приспособленности популяции или значения функции приспособленности лучшей особи на протяжении заданного числа поколений. Если критерий останова не выполняется, происходит переход на основной этап алгоритма. После остановки поиска лучшие хромосомы предъявляются ЛПР в декодированном виде. ЛПР оценивает решения непосредственно по значениям всех критериев. При этом для сужения множества выбора ЛПР может задавать нижние (верхние) допустимые значения некоторых критериев, опираясь на реально полученные значения всех критериев во всех решениях. Если ни одно из предъявленных решений не удовлетворяет ЛПР, скорее всего, это свидетельствует о неравнозначности отклонений критериев от их оптимальных значений. Тогда ЛПР может ввести в формулы оценки качества хромосом (7) или (8) коэффициенты важности критериев li и повторить генетический поиск с целью получения нового подмножества лучших хромосом. Поскольку в повторном поиске снова будут оцениваться паретовские решения, возможное число повторений алгоритма (изменений li) до достижения приемлемого ЛПР решения не может быть большим. Проиллюстрируем описанный алгоритм небольшим примером. Пусть требуется найти решение следующей линейной задачи: f1(X) = 3x1 + 4x2 ® max, f2(X) = –x1 + 3x2 ® max, f3(X) = x1 + 5x2 ® max, f4(X) = 3x1 + 8x2 ® max, f5(X) = 16x1 + 13x2 ® max при условиях –2x1 + x2 £ 4, x1 + 8x2 £ 68, 5x1 + 16x2 £ 152, x1 + 2x2 £ 22, x1 + x2 £ 16, 2x1 + x2 £ 28, 0 £ x1 £ 13, 0 £ x2 £ 8. Для нахождения оптимальных решений использовалась программа LINGO. Результаты решения однокритериальных задач приведены в табл. 1. Таблица 1 Результаты решения однокритериальных задач ЗадачаРешениеЗначения критериев x1x2f1f2f3f4f5Ф2 f1(X)®max10654840782384,213 f2(X)®max28382242701364,08 f3(X)®max5,3337,83347,3331844,578,671874,444 f4(X)®max87521343802194,418 f5(X)®max12452032682443,532 Из этой таблицы имеем: Задачу (1) преобразуем к линейной следующим образом: (10) Обозначив выражение (10) запишем в равносильной форме: (11) Линейная задача, эквивалентная задаче (11), имеет вид (12) (13) Задача (12)–(13) решается для каждой хромосомы, и ее результатом являются Xj и fi(Xj), Для решения исходной задачи применим генетический алгоритм. В рассматриваемом случае длина хромосомы равна 4. Примем Np = 7, Pm = 0,1 и элитарную стратегию: в новую популяцию переходит без изменения одна лучшая хромосома. Используя равномерно распределенные случайные числа, получаем начальную популяцию, представленную в табл. 2. В ней же даны соответствующие веса ai, вычисленные по формулам (6). Таблица 2 Начальная популяция № хром.g1g2g3g4a1a2a3a4a5 10,510,530,880,970,510,020,350,090,03 20,130,220,470,530,130,090,250,060,47 30,240,560,890,910,240,320,330,020,09 40,120,560,690,980,120,440,130,290,02 50,360,380,630,770,360,020,250,140,23 60,080,440,620,940,080,360,180,320,06 70,040,730,790,800,040,690,060,010,2 В результате решения задачи (12)–(13) получили оценки начальной популяции, которые приведены в табл. 3. Таблица 3 Оценки начальной популяции № хром.Решение XjЗначения критериев x1x2f1f2f3f4f5Ф2 13,148,041,4220,8643,1473,42154,244,2345 27,1797,25750,5614,5943,4679,59209,24,4284 38,07,052,013,043,080,0219,04,4176 411,7514,24952,250,99732,99769,246243,253,617 52,08,038,022,042,070,0136,04,08 611,094,9152,913,62635,6372,53241,283,8405 78,07,052,013,043,080,0219,04,4176 Случайным образом с вероятностями (9) образуем родительские пары 3–6, 1–4, 7–3 и затем так же случайно определяем соответствующие им точки разбиения 2, 3 и 1. При таком разбиении оператор скрещивания срабатывает для всех пар, так как образование потомков не приводит к нарушению упорядоченности генов (см. табл. 2). К полученным потомкам применяем оператор мутации. Он вызвал мутации гена g1 у 1-го потомка 1-й пары и генов g1 и g3 у 2-го потомка 2-й пары (выделены полужирным шрифтом). Потомки до и после мутации показаны в табл. 4. Таблица 4 Результаты скрещивания и мутации № хром./ род. параПотомки до мутацииПотомки после мутации g1g2g3g4g1g2g3g4 8/3-60,240,560,620,940,460,560,620,94 9/3-60,080,440,890,910,080,440,890,91 10/1-40,510,530,880,980,510,530,880,98 11/1-40,120,560,690,970,360,560,710,97 12/7-30,040,560,890,910,040,560,890,91 13/7-30,240,730,790,800,240,730,790,80 2––––0,130,220,470,53 В последних четырех столбцах этой таблицы представлены хромосомы второго поколения. Хромосома 2 перешла в него, минуя операции скрещивания и мутации (а в родители она не попала случайно). Для оценки качества нового поколения хромосомы декодировались, и с полученными ai решалось 6 задач (12)–(13) (для хромосомы 2 решение найдено раньше). Сводные итоги решения приведены в табл. 5. Таблица 5 Оценки второго поколения № хром.Решение XjЗначения критериев x1x2f1f2f3f4f5Ф2 27,1797,25750,5614,5943,4679,59209,24,4284 88,3826,80952,3812,0442,4376,62222,634,3785 98,07,052,013,043,080,0219,04,4176 105,7617,69948,0817,3444,2678,88192,284,4470 1111,1834,81752,823,2735,2772,08241,553,8100 128,07,052,013,043,080,0219,04,4176 138,07,052,013,043,080,0219,04,4176 Как следует из табл. 5, во втором поколении появилась хромосома 10 с функцией приспособленности Ф2 выше, чем у лучшей хромосомы 2 первого поколения. Это дает основание для продолжения итераций. Аналогично 1-й итерации сформированы родительские пары хромосом 11–10, 11–13, 13–8 и определены для них точки разбиения 2, 1 и 3 соответственно. Скрещивание с такими точками сохраняет упорядоченность генов потомков. Мутации подверглись только ген g4 1-го потомка и ген g2 2-го потомка первой пары. Хромосома 10 перешла в третье поколение без изменений. Оценивалось третье поколение по той же схеме, что и предыдущие поколения. Опуская данные по всем хромосомам третьего поколения, отметим, что лучшую приспособленность показала хромосома 15, второй потомок 1-й пары. Ее данные: x1 = 5,3(3); x2 = 7,83(3); f1 = 47,33; f2 = 18,17; f3 = 44,5; f4 = 78,67; f5 = 187,17; Ф2 = 4,4526. Если на этом шаге остановить генетический алгоритм, то ЛПР будут интересны хромосомы 15, 10 и 2, показавшие наивысшие значения Ф2. Определим процент достижения максимально возможного значения для хромосомы 15. Этот показатель равен 87,65 % по 1-му критерию, 82,59 % по 2-му, 100 % по 3-му, 98,3 % по 4-му и 76,71 % по 5-му критерию, что свидетельствует об отсутствии провалов по отдельным критериям. Аналогичные данные можно вычислить для хромосом 10 и 2. Если полученные результаты не устроят ЛПР, тогда третье поколение можно принять за начальную популяцию, ввести коэффициенты важности критериев li в функцию приспособленности Ф2 и повторить итерации генетического алгоритма. Таким образом, предложенный генетический алгоритм решает поставленную задачу, обеспечивая целенаправленное и детальное исследование множества Парето, что позволяет ЛПР более обоснованно делать свой выбор.