Диссертация (1137155), страница 17
Текст из файла (страница 17)
Однако, какбыло показано в [20], у NSGA по сравнению с двумя другимиупомянутыми МГА оказалась наиболее равномерно заполненнаяграница Парето. Поэтому результаты, полученные NSGA, являютсяболее предпочтительными для последующих обработки и выбора ЛПРокончательного решения.Также имеется ряд работ, в которых алгоритмы NSGA иNSGA-II успешно применяются при решении задач календарного124планирования, составления расписаний и задачи коммивояжера [71],[88], [89].NSGA-IIявляетсяразвитиемNSGA,устраняющимряднедостатков последнего [72]. Поэтому для решения задачи построенияархитектурной дорожной карты выбран генетический алгоритммногокритериальной оптимизации NSGA-II.3.6.Описание выбранного метода решения (генетическогоалгоритма NSGA-II)Алгоритм NSGA-II (как и NSGA) использует ранжированиеагентов популяции.
В его основе лежит метод недоминируемойсортировки (Non-Dominated Sorting, NDS). Основой этого методаявляется присвоение особи ранга, который зависит от количестваособей, представляющих доминируемые или (в зависимости отконкретного алгоритма) доминирующие решения (рис. 27).Рисунок 27. Ранжирование особей в методе недоминируемой сортировкиНиже приведено описание NSGA-II согласно [98].125Краткое описание NSGA-II.Популяция инициируется любым выбранным способом. Послеинициализации популяция сортируется по «недоминированию» длякаждого Парето-фронта.
Первый фронт состоит из множестваполностью недоминируемых особей текущей популяции. Второйфронт состоит из особей, которые доминируются только особями изпервого фронта и так далее от фронта к фронту. Каждой особи вкаждом фронте присваивается значения ранга (приспособленности) наоснове фронта, к которому они принадлежат. Особям из первогофронта присваивается значение приспособленности 1, особям извторого фронта – значение приспособленности 2 и так далее.В добавление к значению приспособленности в NSGA-II длякаждой особи вычисляется новый по сравнению с NSGA параметр,называемый «расстоянием скученности». Расстояние скученности –это мера того, насколько особь близка к своим соседям.
Более высокоесреднее значение расстояния скученности соответствует лучшемуразнообразию в популяции.Родителивыбираютсяизпопуляциисиспользованиембинарного турнира на основании ранга и расстояния скученности.Особь выбирается, если у нее ранг меньше или ее расстояниескученности больше, чем у другой особи. Выбранная популяцияпроизводит потомков при помощи операторов кроссовера и мутации,которые будут описаны ниже.Популяция, включающая текущую популяцию и текущихпотомков, снова сортируется по «недоминированию» и отбираютсятольколучшиеN особей(N – размер популяции).
Выборосновывается на ранге и «расстоянии скученности».126Недоминируемая сортировка.В NSGA-II применен быстрый (усовершенствованный посравнению с NSGA) алгоритм недоминируемой сортировки.127Алгоритм 3. Быстрая недоминируемая сортировкаПроцедура non_domination_sort_mod()1: для каждой особи p в популяции P цикл‘массив будет содержать особи, доминируемые p2:Sp :=3:np := 0 ‘счетчик особей, доминирующих p4:для каждой особи q в P цикл5:если p доминирует q6:Sp := Sp {q}7:иначе если q доминирует p8:9:np := np + 1если np = 0 ‘ нет особей, доминирующих p10:prank = 1 ‘ особи p присваиваем ранг 111:F1 := F1 {p} ‘ добавляем особь p в первый фронт12:кесли13:14:i := 115:пока Fi ≠цикл‘ массив для хранения особей i+1-го фронта16:Q :=17:для каждой особи p в Fi цикл18:для каждой особи q в Sp цикл19:nq := nq – 120:если nq = 021:qrank := i + 122:Q := Q {q}23:Fi := Fi {q}кесли24:25:26:кциклкцикл12827:i := i + 128:Fi := Q29:кцикл30:кциклКонец процедурыРасчет расстояния скученности.Послевыполнениянедоминируемойсортировкиособямприсваивается расстояние скученности, вычисляемое между особямикаждого фронта в отдельности по следующему алгоритму.Алгоритм 4.
Расчет расстояния скученности1: для каждого фронта Fi цикл ‘ n – число особей фронтадля каждой j-й особи цикл2:Fi(dj) := 0 ‘ инициализация расстояния скученности3:для каждой m-й целевой функции цикл4:I := sort(Fi, m) ‘особи, сортированные по m-й функции5:6:I(d1) = ∞; I(dn) = ∞7:для k := 2 до (n – 1) цикл8:‘I(k).m – значение m-й целевой функции k-й особи в I9:10:кцикл11:кциклОсновнаяидеярасчетарасстоянияскученности–этонахождение расстояния между особями фронта по их m целевымфункциям в m-мерном гиперпространстве.129Селекция.После недоминируемой сортировки и присвоения особямрасстояний скученности выполняется селекция на основе операторасравнения.
Сравнение особей p и q выполяется следующимобразом:Если p и q принадлежат разным фронтам, то, если prank < qrank.Если p и q принадлежат одному и тому же фронту Fi, то, если Fi(dp) > Fi(dq)Особи отбираются с использованием бинарного турнира.Генетические операторы.В оригинальной реализации NSGA-II используется бинарныйкроссовер Simulated Binary Crossover (SBX) и полиномиальнуюмутацию(polynomialmutation).Однаковвидуособенностейпостановки задачи и структуры исходных данных будут использованыдругие генетические операторы (см. параграф 3.7).Рекомбинация и селекция.Популяция потомков комбинируется с популяцией текущегопоколения, после чего выполняется селекция особей в следующеепоколение. Таким образом обеспечивается элитизм, поскольку вселучшие особи содержатся в популяции, подвергаемой селекции.После селекции все особи сортируются в порядке недоминирования.Новое поколение заполняется последовательно от фронта к фронту,пока размер получаемой популяции не превышает размера текущейпопуляции.
Если при добавлении особей в j-й фронт размерпопуляции превышает N, особи отбираются в этот фронт в порядкеубывания их расстояния скученности до тех пор, пока размер130популяции не достигнет N. Далее процесс повторяется для генерацииследующих поколений.3.7.Кодирование решений и выбор генетических операторовПри реализации генетических алгоритмов важным этапомявляется выбор способа кодирования решений и соответствующихэтому способу генетических операторов, которые лучше всегоподходят к условию и исходным данным задачи.Кодирование решений.Поскольку решения задачи (2.30) – (2.33) представляют собойперестановки,тодлякодированияхромосомцелесообразноиспользовать простое порядковое n-арное кодирование [7].
Дляуменьшенияразмерностизадачи,атакжедляисключенияограничений (2.32) (явные замены практик) из рассмотрения будемкодироватьнетраектории(определение 5),вСледовательно,,которыхгенамибудутаэтиметатраекторииограниченияпарныеужеучтены.преобразования(определение 4), а хромосомой – их перестановка, соответствующаяметатраектории. Каждая позиция в кодирующей строке будет| |.принимать одно из значений в пределахПроиллюстрируем принятую кодировку на тестовых данных,приведенных в параграфе 3.4.Множество всех парных преобразованийЗафиксируем порядковые номера элементов для данногопредставления множества , и введем следующую кодировку:123456(1,6)(2,7)(3,9)(4,8)(5,10)( ,11)131Тогда можно привести примеры кодированных решений изприложения 1:Решениеg1g2g3g4g5g6131452690465321180654321Оператор кроссовера.Очевидно, что в хромосоме, представляющей решения задачи(2.30) – (2.33), не должно быть одинаковых генов.
Также генетическиеоператоры должны учитывать, что не все перестановки в данномслучае являются допустимыми, поскольку существуют ограниченияна порядок выполнения изменений (2.33).Дляповышенияколичестважизнеспособныхособей,получаемых в результате кроссовера, в подобных случаях применяютспециальные операторы, учитывающие порядок следования генов(genetic sequencing operators), например, такие как циклическийкроссовер (CX), кроссовер порядка (OX), частично-отображающийкроссовер (PMX).Выберем частично-отображающий кроссовер (partially-mappedcrossover, PMX), поскольку он дает лучшие результаты средиперечисленных алгоритмов, если в потомках важно сохранитьинформацию о порядке следования генов из родительских хромосом[102].Кроссовер PMX строго отображает часть генотипа 1-го«родителя» в генотип «потомка» генотип потомка, а остальнаяинформацияогенотипе2-го«родителя»изменяетсяпослесоответствующих операций обмена так, чтобы сохранить порядок ипозиции как можно большего числа генов из этого «родителя» в132генотипепотомка.Используядопустимыегенотипыдвух«родительских» особей, кроссовер PMX сохраняет допустимость«потомства» [7].
Тем не менее, часть потомков, получаемых врезультате кроссовера PMX, все же могут не удовлетворятьограничениям задачи.Как показывают исследования, оператор PMX дает хорошиерезультаты в задачах составления расписаний [16].Продемонстрируем применение кроссовера PMX для решений 1и 90 (приложение 1). Pi – родители, Offj – потомки. Жирными линиямипоказаны случайно выбранные точки разреза.P1314526P90465321Off1463521Off2514326Проверим допустимость потомков.
Ограничение (2.33) задано вприведенном примере как(параграф 3.4). Длякодированных решений это означает, что 5 должно следовать раньше,чем 2, а 3 – раньше, чем 1. На основании этого условия видно, чтопотомок Off1 является допустимым, а потомок Off2 – недопустимым.Для недопустимых потомков далее должна применятьсяоперациякоррекции,исправляющаявыявленныенарушенияограничений.Локальная оптимизация.Исследования показывают, что применение одного толькогенетическогоалгоритманевсегдаэффективнобезихкомбинирования с алгоритмами локального поиска [61]. Поэтомупосле кроссовера потомок будет улучшаться при помощи полногопереборадопустимыхрешенийдлянесколькихпоследних133элементарных преобразованийв траектории (на основеалгоритма поиска с возвратами (алгоритм 2)).
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
