Автореферат (Агрегированная с многоагентным генетическим алгоритмом имитационная модель предприятия дистанционной торговли для решения задачи многокритериальной оптимизации), страница 3

Данные измерения могутсодержать заданное число элементов. Для демонстрационного решениярассматриваемой оптимизационной задачи для действующего ПДТ былоопределено 5 кластеров товарных категорий, 6 кластеров городов, 3 клиентскихсегмента, 12 месяцев моделирования. Таким образом, общее число переменных воптимизационной задаче достигает 98, что характеризует ее размерность каксверхбольшую и требует новых подходов к эффективному решению.Вторая глава диссертационного исследования посвящена методам решениямногокритериальных оптимизационных задач.

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

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

Но длялица, принимающего решения (далее ЛПР), при управлении ПДТ достаточнонайденных субоптимальных решений, близких к глобальным.Классическая модель ГА была впервые предложена в 1975 J. Holland, вдальнейшем D. Goldberg выдвинул ряд гипотез и теорий, помогающих глубжепонять природу ГА. К настоящему моменту на основе ГА разработаны различныеметоды нахождения Парето-оптимальных решений: VEGA (Vector Evaluated Genetic Algorithm) предложен в 1984 году Шафером.В данном методе селекция производится для каждого из критериев отдельно. FFGA (Fonseca and Fleming’s Multiobjective Genetic Algorithm 1993)представляет собой основанную на Парето-доминировании процедуруранжирования индивидов MOGA (Multi-Objective Genetic Algorithm), предложенный Фонсека (C. M.Fonseca) и Флемингом (P.

J. Fleming) в 1993 г. В методе предполагается, чторанг особи равен числу особей в популяции, которые ее доминируют. NPGA (Niched Pareto Genetic Algorithm) (1994) был предложен Хорном,принципиально отличается от двух предыдущих, так как в нем заложен13механизм поддержания разнообразия. NSGA-II (Fast and Elitist Multiobjective Genetic Algorithm for Multi-ObjectiveOptimization (Kalyanmoy Deb, Samir Agrawal, Amrit Pratap, T Meyarivan, 2002))— является развитием метода недоминируемой сортировки NSGA (Srinivasand Deb, 1994), в котором при формировании архива отвергаются особи срасстоянием до других особей в архиве не превышаем заданной величины. SPEA-2 (Strength Pareto Evolutionary Algorithm (Eckart Zitzler, Marco Laumanns,and Lothar Thiele, 2001)) является развитием метода SPEA (1998) и основан напринципе оценки Парето-силы для ранжирования особей. Методадаптивныхвзвешенныхсумм(AdaptiveWeightedSummethod)предложили J-H.

Ryu, S. Kim,H. Wan. Метод основан на аддитивной сверткечастных критериев оптимальности с адаптируемыми коэффициентами.Врядесравнительныхисследованийпоэффективностивышеперечисленных методов установлено, что SPEA-2 и NSGA-II лучше прочихсправляются со своей задачей. Причем установлено, что при выпуклом фронтеПарето SPEA-2 сходится быстрее, чем NSGA-II.Для повышения временной эффективности вычислительной процедурызначительные усилия исследователей направлены на сокращение времени поискарешений за счет применения алгоритмов параллельных вычислений. Первымсистематическим изучением параллельных ГА с множеством популяций быладиссертация Р.Б.Гроссо (Grosso). Сегодня существуют следующие методикираспараллеливания вычислений для ГА: Островная модель – это самый распространенный метод распараллеливаниявычислений, при котором каждый процессор реализует собственный ГА навыделенной ему части всей популяции.

С определенной периодичностьюпроисходит обмен части популяции между «островами». Однопопуляционный алгоритм – главный процессор содержит всё поколениев своей памяти и выполняет операторы селекции, кроссовера и мутации.Функции пригодности индивидов вычисляются на других процессорах. Клеточный алгоритм – в этом случае каждым процессорным элементом в одинмомент времени обрабатывается один индивид.Проведенный анализ вариаций ГА для поиска Парето-оптимальных14решений позволил выявить ключевой фактор их неэффективности в задачах сбольшим пространством поиска решений – это длина кодирующей хромосомы.Величина прямо пропорциональна необходимому размеру популяции и,соответственно, кол-ву расчетов фитнес-функции.

С хромосомой из более чем 10переменных (условная длина более 100 генов) перечисленные методы поискаПарето-оптимальных решений теряют свою эффективность. Полученные выводылегливосновуновогомногоагентногогенетическогоалгоритмадлямногокритериальной оптимизации (multi-agent genetic algorithm for multi-objectiveoptimization – MAGAMO). Его эффективность достигается за счет особойметодики распараллеливания вычислений, при которой → min.В основе MAGAMO лежит динамическое взаимодействие асинхронныхинтеллектуальных агентов, каждый из которых выполняет свой эволюционныйпроцесс согласно методу SPEA2. Данный метод был выбран, т.к.

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

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

Результатысравнения приведены в разделе 2.4 диссертации.Блок-схема MAGAMO изображена на рис. 1. Серым цветом выделеныблоки, которые отражают научную новизну в разработанном алгоритме.Начало работы Эволюционнойсети из N агентовИсходное распределение пространствапоиска решений между агентамиНачало работы Агента № 1Начало работы Агента № 2..N1.

Создание исходной популяции...(аналогично Агенту №1)Начало нового эволюционногоцикла агента2. Реализация алгоритма поискаПарето-оптимальных решений SPEA23. Выгрузка новых Парето-оптимальныхрешений в глобальный архив4. Глобальный критерийсходимости достигнут?данет5. Перераспределение пространствапоиска решений между агентами(опционально по критерию)6. Получение новых значений неактивныхпеременных из глобального архивВ глобальном архиве содержатсяискомые решения.Конец работы агентов и всейЭволюционной сети.Рисунок 1. Блок-схема работы MAGAMOПринцип работы MAGAMO наглядно представлен на рис. 2.