Диссертация (1137100), страница 7
Текст из файла (страница 7)
При имитационноммоделировании использовался метод системной динамики, также рассмотренный впервой главе.Разработанная имитационная модель предприятия дистанционной торговлиотличается от существующих моделей математическим описанием всех ключевыхбизнес-процессовдеятельностикомпаниииучетомсложнойдинамикитрансформации клиентской базы. Эти особенности позволили синтезировать из неезадачуматематическогопрограммирования–аименно,задачумногокритериальной оптимизации с тремя конкурентными критериями для поискарациональных решений при управлении предприятием дистанционной торговли.Такимобразом,имитационнаямодельпозволяетформироватьцелевыефункционалы для многокритериальной оптимизационной задачи.4445Глава 2. Разработка многоагентного генетического алгоритма2.1 Используемые численные методы решения многокритериальныхоптимизационных задачСуществуютследующиеметодырешениямногокритериальныхоптимизационных задач [58, 65, 80-84]:1.
Выбор главного критерия.2. Метод последовательных уступок.3. Использование составных критериев: аддитивного илимультипликативного.4. Правило паритета5. Правило «близости к идеалу».6. Использование принципа Парето – подходит наилучшим образом дляпоиска рациональных решений ввиду отображения на фронте Парето всехвозможных вариантов для последующей помощи в выборе стратегии.ХарактерЦелевыхфункций(многоэкстримальный,неаддитивный,немонотонный на частичных решениях) в сложных имитационных моделей собратными связями позволяет говорить о неприменимости точных методоврешения оптимизационных задач.В этом случае хорошо зарекомендовали себя различные численные методы,а именно алгоритмы метаэвристического класса, позволяющие, не исследуяполностью область допустимых решений, с определенной вероятностью находитьглобальный экстремум в однокритериальных задачах и фронт Парето вмногокритериальных.В диссертации были изучены следующие методы зондирования пространствапоиска решений, основанные на численных методах оптимизации [14, 15, 41-48]o Вариация методов, основанных на генетических алгоритмах –пожалуй,алгоритмовнаиболеедляраспространенныйнахождениякласспопуляционныхПарето-оптимальныхрешений.Классическая модель ГА была впервые предложена в 1975 J.
Holland4546[18, 21], в дальнейшем (D. Goldberg выдвинул ряд гипотез и теорий,помогающих глубже понять природу генетических алгоритмов.Наиболее известные NSGA2 Fast and Elitist Multiobjective GeneticAlgorithm for Multi-Objective Optimization (Kalyanmoy Deb, SamirAgrawal,AmritPratap,andTMeyarivan,2002)–методнедоменируемой сортировки, SPEA2 (Strength Pareto EvolutionaryAlgorithm Eckart Zitzler, Marco Laumanns, and Lothar Thiele, 2001) [26,26] – метод, основанный на силе Парето-доменирования [11, 12, 13].o Метод композитных точек предложили Филдсенд (J.E.
Fieldsend) иСинх (S. Singh) в 2002 г.o Сигма-метод (sigmamethod) предложили Мостагхим (S. Mostaghim)и Тич (J. Teich) в 2003 г.o В основе метода гиперкубов, предложенного Коэлло (C.A. Coello) иЛечунга (M.S. Lechunga) в 2002 г.o Метод динамических соседей предложили Хью (X. Hu) и Эберхарт(R. Eberhart) в 2002 г.o Методхищник-жертва(predator-prey)предложилЛауманс(M. Laumanns) с соавторами в 1998 г.o MOPSO(Multi-ObjectiveоптимизацииметодомSwarmроячастицOptimization)для–вариациямногокритериальнойоптимизации.o CIAC – вариация оптимизации методом колонии муравьев длямногокритериальной оптимизации.Наиболее проработанной в литературе темой является использованиегенетических алгоритмов (далее ГА) для решения оптимизационных задач.Доказано, что ГА обладают значительно большей временной эффективностью, чемпростой метод перебора, и рядом плюсов по сравнению с другими численнымиспособами решения оптимизационных задач.
Классическая модель ГА былавпервые предложена в 1975 J. Holland [18], в дальнейшем (D. Goldberg выдвинул4647ряд гипотез и теорий, помогающих глубже понять природу генетическихалгоритмов.ГА получили много вариаций, в т.ч. много исследований посвященоиспользованию ГА для многокритериальной оптимизации. Разработано большоеколичество методов: На основе ГА разработаны различные методы нахожденияПарето-оптимальных решений в многокритериальных оптимизационных задачах[8,9,17]: VEGA (Vector Evaluated Genetic Algorithm) был предложен в 1984 годуШафером. В данном методе селекция производится для каждого из Kкритериев отдельно, тем самым промежуточная популяция заполняетсяравными порциями индивидов, отобранных по каждому из критериев. FFGA (Fonseca and Fleming’s Multiobjective Genetic Algorithm 1993)представляет собой основанную на Парето-доминировании процедуруранжирования индивидов, где ранг каждого индивида определяетсячислом доминирующих его индивидов MOGA(Multi-ObjectiveGeneticAlgorithm),предложенныйФонсека(C.
M. Fonseca) и Флемингом (P. J. Fleming) в 1993 г. [10]. В методепредполагается, что ранг агента равен числу агентов в популяции, которыеего доминирует. NPGA (Niched Pareto Genetic Algorithm) (1994) был предложен Хорном,принципиально отличается от двух предыдущих, так как в нем заложенмеханизм поддержания разнообразия. Метод основан на формированиипопуляционных ниш [19]. NSGA (Srinivas and Deb in 1994) и NSGA-II (Fast and Elitist MultiobjectiveGenetic Algorithm for Multi-Objective Optimization (Kalyanmoy Deb, SamirAgrawal, Amrit Pratap, and T Meyarivan, 2002) — развитием методанедоминируемойсортировкиявляетсяметод,вкоторомприформировании архивов отвергают агентов, расстояние которых до другихагентов в архиве не превышает заданной величины.4748 SPEA (Strength Pareto Evolutionary Algorithm (1998)) и SPEA-2 (EckartZitzler, Marco Laumanns, and Lothar Thiele, 2001).
Иное правилоранжирования агентов популяции используется в методе Паретосилы(Paretostrength).РазвитиемалгоритмаSPEAявляетсяалгоритм SPEA-2, который подобно алгоритму NGSA-IIиспользует оценкиравномерностиПарето-аппроксимацииВажнымсвойствомметода SPEA является возможность априорного задания количестваитоговых точек в искомой аппроксимации множества Методадаптивныхвзвешенныхсумм(AdaptiveWeightedSum (AWS) method) предложили Рю, Ким и Ван (JH. Ryu, S. Kim,H. Wan). Метод основан на аддитивной свертке частныхкритериев оптимальности, но, в отличие от классического метода суммывзвешенныхкритериев(WeightedSum(WS)method)[1],такжеиспользующего такую свертку, предполагает адаптацию весовыхкоэффициентов в процессе итераций на основе информации о текущемположении подобласти поиска.Что касается поиска Парето-оптимальных решений путем зондированияпространства, то тут возникает проблема вычислительной сложности, в связи с чемзначительные усилия исследователей направлены на сокращение временивычислений за счет применения алгоритмов параллельных вычислений.
Значимымпреимуществом ГА является возможность эффективного распараллеливаниявычислений [3,4]. Однако ГА всегда имеет риск схождения к локальным субоптимальным решениям вместо глобальных. Но для ЛПР в ряде задач достаточнои суб-оптимального решения, близкого по значению к глобальному оптимуму.В ряде сравнительных исследований по эффективности вышеперечисленныхметодов установлено, что SPEA-2 и NSGA-II лучшие остальных методовсправляются со своей задачей.
Причем, при выпуклом фронте Парето SPEA-2сходится быстрее, чем NSGA-II. При невыпуклом фронте – наоборот.4849Эккарт Цитцлер, Марко Ломаннс и Лотар Тиеле разработали алгоритм сархивом, использующий понятие силы (или, что более корректно, хилости), иизвестный как Strength Pareto Evolutionary Algorithm (или SPEA). На данныймомент его улучшенный вариант, SPEA2, непосредственно конкурирует с NSGAII и другими стохастическими многокритериальными алгоритмами оптимизации8.
Как и NSGA-II, SPEA2 сохраняет архив наилучших найденных особей на границеПарето, равно как и некоторое количество других особей. Однако в SPEA2используется Парето-мера wimpiness, и степень перенаселения популяцииопределяется на основе расстояний между особями в многокритериальномпространстве, а не в пространстве рангов. Мера схожести в SPEA2 [6] вычисляетсякак расстояние до других особей популяции, в частности, до k-й ближайшей особи.Алгоритм SPEA2 на высоком уровне:Отличие расчета фитнес-функции SPEA и SPEA2 представлены на рис. 9:Рисунок 9.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
