Диссертация (1137100), страница 8

Просмтор этого файла доступен только зарегистрированным пользователям. Но у нас супер быстрая регистрация: достаточно только электронной почты!

Текст из файла (страница 8)

Расчет значений функции приспособленности - Слева SPEA2,справа SPEA4950Следует отметить, что в стандартном виде ни один из существующих методовне справляются с поиском Парето-оптимальных решений в задачах большойразмерности, где порожденное пространство поиска решений настолько велико,что для предотвращения преждевременного схождения к зонам локальногооптимума необходимо оперировать чрезмерно большим числом особей, что влечеткрайне большое число расчета фитнес-функций и, соответственно, неприемлемоевремя решение задачи [10].

Для решения проблемы временной эффективностизначительные усилия исследователей направлены на сокращение времени поискарешений за счет применения алгоритмов параллельных вычислений.Первым систематическим изучением параллельных ГА с множествомпопуляций была диссертация Р.Б.Гроссо (Grosso). Его целью было имитироватьвзаимодействие параллельных субкомпонентов эволюционирующей популяции.Сегодня существуют следующие методики распараллеливания вычислений дляГА: GPGA (Global Parallel Genetic Algorithm) – однопопуляционный алгоритм.Host-процессор содержит всё поколение в своей памяти и выполняет надним операции селекции, кроссовера и мутации. Функции пригодностииндивидов вычисляются на slave-процессорах. Основная проблема –балансировки загрузки slave-процессоров. Данный алгоритм ориентированна MIMD-вычислительные системы. DGA (Distributed Genetic Algorithm) или Островная модель – этомногопопуляционный алгоритм, также ориентированный на MIMDвычислительныесистемы.Каждыйпроцессориспользуетсвойсобственный генетический алгоритм на выделенной ему части всейпопуляции.[24] MPGA(MassivelyParallelGeneticAlgorithm)илиCellularAlgorithm (клеточный алгоритм) ориентирован на вычислительныемашины класса SIMD [5].

В этом случае каждым процессорным элементом5051в один момент времени обрабатывается один индивид. Индивидывыбирают пару и рекомбинируют со своими непосредственными соседями. Hierarchical PGA представляют собой алгоритмы, в которых на разныхуровнях иерархии реализованы разные ПГА. Обычно используются 2-хуровневые иерархии: DGA-модель – на верхнем уровне; GPGA- или MPGAмодель – на нижнем уровне. Hybrid PGA – класс алгоритмов, использующих сочетание параллельныхгенетических алгоритмов и классических оптимизационных методов.Первым систематическим изучением параллельных ГА с множествомпопуляций была диссертация Р.Б.Гроссо (Grosso).

Сегодня существуют следующиеметодики распараллеливания вычислений для ГА: GPGA (Global Parallel Genetic Algorithm) – однопопуляционный алгоритм.Главный процессор содержит всё поколение в своей памяти и выполняет надним операции селекции, кроссовера и мутации.

Функции пригодностииндивидов вычисляются на других процессорах. Балансировка загрузки на этихпроцессорах является основной проблемой. Данный алгоритм ориентирован наMIMD-вычислительные системы. DGA (Distributed Genetic Algorithm) или «Островная модель» – этомногопопуляционныйалгоритм,такжеориентированныйнаMIMD-вычислительные системы. Самый распространенный метод распараллеливаниявычислений, при котором каждый процессор реализует собственный ГА навыделенной ему части всей популяции. MPGA (Massively Parallel Genetic Algorithm) или Cellular Algorithm (клеточныйалгоритм) ориентирован на вычислительные машины класса SIMD.

В этомслучаекаждымпроцессорнымэлементомводинмоментвремениобрабатывается один индивид. Индивиды выбирают пару и рекомбинируют сосвоими непосредственными соседями. Hierarchical PGA представляют собой алгоритмы, в которых на разных уровняхиерархии реализованы разные параллельные ГА. Обычно используются 2-х5152уровневые иерархии: DGA-модель – на верхнем уровне; GPGA- или MPGAмодель – на нижнем уровне.В случае с однокритериальной оптимизацией при небольшом пространствепоиска решений (меньше 10 переменных) хорошо зарекомендовал себя способраспараллеливания вычислений согласно «Островной модели». Однако в случаебольшого пространства поиска решений (более 10 переменных) ни «Островнаямодель», ни другие способы распараллеливания вычислений при решениимногокритериальных оптимизационных задачах методами эволюционного поиска(SPEA2,NSGA-IIит.п.)неприводиткзначимомуповышениюпроизводительности.В случае, если имеется большое пространство поиска решений, нередкоприменяют аппроксимационные алгоритмы для построения поверхности отклика,по которой далее происходит оптимизация.

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

Данный метод был выбран, т.к. в сравнительныхисследованиях он показывает лучшие результаты при выпуклом фронта Парето снеизолированными решениями, а функциям в ИМ, как правило, свойственны этихарактеристики.Отличия MAGAMO от параллельной модификации SPEA2 в виде «Островноймодели» заключаются в следующем (рис. 10):52531. В MAGAMO используется агентный подход для распараллеливаниявычислений. Согласно нему все пространство поиска решений равномерноделится между агентами, поэтому каждый агент имеет собственнуюфитнес-функцию, содержащую свой набор переменных. А все «острова»,напротив, имеют равное по размеру пространство поиска решений (общийнабор переменных), и, чем оно больше, тем длиннее хромосома, тембольший размер популяции необходим и тем экспоненциально большезатрачиваетсявременинарасчетыфитнес-функций.MAGAMOэффективно решает описанную выше проблему: за счет сниженияразмерности пространства поиска решений достигается резкое сокращениеколичества расчетов фитнес-функций у каждого агента.

[2]2. В MAGAMO в процессе эволюции всей системы с определеннойпериодичностьюпроисходитдинамическоеперераспределенияпространства поиска решений между агентами. В «Островной модели»пространство поиска решений фиксировано. [2]3. Агенты, в отличие от «островов», наделены элементами интеллекта – онимогут самостоятельно инициировать обмен лучшими результатами поискав случае, если другие агенты достигли очередного улучшения своихсубоптимальных решений.

В результате во всей системе поэтапнопроисходит нахождение глобальных Парето-оптимальных решений. [2]4. В MAGAMO используется общий (глобальный) архив лучших решений,через который происходит обмен результатами поиска между агентами. Позавершении очередного эволюционного цикла каждым из агентов, агентобращается в глобальный архив и замещает в нем имеющиеся решениянайденными более хорошего качества. После этого агент получает новыезначения своих «неактивных» переменных из других лучших архивныхрешений, которые были получены другим агентом. Так происходит обменрезультатамипоискарешениймеждуагентами.Позавершениивзаимодействия агента с глобальным архивом, агент начинает новыйэволюционный цикл поиска подмножества Парето-оптимальных решений5354с помощью SPEA2. С каждым из таких циклов решения из глобальногоархива движутся к фронту Парето наивысшего ранга – к глобальнымПарето-оптимальным решениям.

[2]Рисунок 10. Схема Островной модели и Агентной моделиЗа счет перечисленных особенностей MAGAMO эффективно справляется споиском решений при более чем 100 переменных – примерно в 3-5 раз больше, чемв случае классической «Островной модели».В разделе 2.1 диссертации представлено техническое описание MAGAMO.Введем следующие ключевые обозначения: = 1. . – агенты – размер популяции – длина хромосомы = 2 – размер архива лучших решений -агента – глобальный архив результирующих Парето-оптимальных решений – целевой размер глобального архива. , – конкретная особь в единой популяции для и  ≻ означает, что i-ая особь доминирует по Парето j-ую особь. = 1.

. – шаг эволюции – популяция на шаге эволюции  – популяция архивного множества на шаге эволюции 5455 = 1. . – массив всех переменных, составляющий общее пространство поискарешений. Причем элементы массива одной переменной представляются каксамостоятельные переменные . – набор «активных» переменных для -агента, варьируемых в ходе ГА. = − – набор «неактивных» переменных для -агента, значения которыхфиксированы в ходе одного эволюционного цикла -агента. – определенное количество генов для кодирования значений каждойпеременнойПри реализации MAGAMO каждым из -агентов используются следующиеключевые операторы и формулы:1)Исходное распределение пространства поиска решений между агентами.Бинарная длина пространства поиска решений = ∑1 (22).2) Исходно распределять пространство решений по агентам необходиморавномерно и добиваться максимальной однородности переменных внутриодного агента, чтобы длина хромосомы агентов =максимальноравна(рис.11).Длядостижения(23) былаоднородностираспределения следует использовать экспертный и статистических анализ,выявляющий степень зависимости переменных друг от друга и объединятьнаиболее зависимые в единые кластеры.Рисунок 11.

Целевая длина хромосомы агентаВ результате равномерного распределение переменных по агентам, каждый агентполучает свой массив «активных» переменных , по которым будет происходить5556поиск решений. Создается начальная популяция 0 . Переменные кодируются спомощью кода Грея, также для переменных с большой областью допустимыхзначений применяется логарифмическое кодирование.Остальные переменные становятся для агента «неактивными» со случайнымификсированными значениями. Их значения не меняются до момента очередногоперераспределения пространства решений между агентами.3)Расчет фитнес-функции для -ой особи выглядит следующим образом:() = () + () (24), где величина () отражает силу Парето-доминирования,а () – коэффициент разряженности.() =∑() (25), ∈ + ,≻при этом () = |{ | ∈ + ∧ ≻ }| (26) – это мощность множества особей jиз множества + , которые доминируют по Парето i-ую особь.() =1(27), + 2при этом – это геометрическая дистанция до -ого ближайшего элемента, гдевеличину рекомендуется определять по формуле = √ + (28)4)Формирование нового архива решений:+1 = { | ∈ + ∧ () < 1} (29)Есличислоэлементовв +1превышает ,тонеобходимосократитьмножество +1 посредством оператора усечения, при котором в результате|+1 | − итераций исключаются особи с минимальным расстоянием до другойособи.Иначе если +1 меньше , тогда в +1 необходимо добавить − |+1 | штуклучших доминируемых решений с самой большой функцией приспособленностииз + .Процесс усечения представлен на рис.

12.5657Рисунок 12. Действие оператора усечения SPEA25)Оператор селекции реализован в виде бинарного турнирного отбора. Всеособи случайным образом разделяются на пары, для каждой из которыхустраивается турнир. В турнире побеждает особь с более высоким значением (),после чего она допускается к скрещиванию.6)Оператор скрещивания используется 2-х точечный.7)Оператор мутации. Вероятность мутации особи = 0.01. При этоммутации подвергаются max(1, % 100) генов, которые выбираются случайнымобразом.8)Обновление глобального архива происходит по средствам копированияв него результирующей популяции +1 после завершения эволюционного циклаочередного агента. Затем происходит расчет () для каждой особи множества ииз него исключаются ||− особей с самым низким значением ().9)Перераспределение пространства поиска решений между агентами.Каждые эволюционных циклов происходит перераспределение пространствапоиска решений между агентами.

Характеристики

Список файлов диссертации