Диссертация (1137155), страница 16
Текст из файла (страница 16)
25).Парето-оптимальные решения выделены заливкой.Рисунок 25. Парето-оптимальные решенияДалее лицо, принимающее решение, должно выбрать один извариантов, входящих Парето-множество, на основе собственныхпредпочтений.Два выделенных Парето-оптимальных решения соответствуютследующим сценариям:1. Решение № 35 (,,)–болеесоответствуетприоритетам бизнес-ценности, но изменения будут проходить наотдельных участках немного сложнее, чем в случае решения № 102.Траекторииотвечает следующий порядок преобразований:сначала вместо больших запасов компания начинает работать вусловиях низких запасов и поставок точно в срок, затем снижаетсяколичество уровней управления, после чего расширяется сфераответственности персонала, внедряется оптимизация на линии,специализированное оборудование заменяется на гибкое и, наконец,устанавливается фиксированная оплата труда вместо сдельной.1182.
Решение№102(,,–)соответствует более легким изменениям, хотя при этом в меньшейстепени соблюдаются приоритеты бизнеса. Траекторииследующийпорядокпреобразований:сначалаотвечаетвыполняютсяорганизационные преобразования (меньше уровней управления,расширение ответственности), затем внедряется оптимизация налинии, устанавливается фиксированная оплата труда вместо сдельной,далее снижаются запасы продукции и устанавливается гибкоеоборудование взамен специализированного.Графики легкости изменений для Парето-оптимальных решенийпредставлены на рис.
26.Рисунок 26. Графики легкости изменений для Парето-оптимальных решений119Ясно, что количество решений, которые находит реализованнаяпрограмма, зависит от числа ограничений. В худшем случае (безограничений) программа должна выдатьрешений(равноколичествуперестановокэлементарныхпреобразований). Если заданы только ограничения явной заменыпрактик (2.32), то количество допустимых решений будет| |(равноколичествуперестановокпарныхпреобразований).Проверим корректность работы алгоритма, задав толькоограничения (2.32).
В этом случае программа, как и ожидалось,выдает 720 допустимых решений (время работы – 0,3 секунды).При увеличении числа ограничений (2.33) с двух до трехпрограмма работает 0,05 секунд и выдает 60 допустимых решений(время работы вдвое меньше по сравнению с первоначальновведенными тестовыми данными).Программа, реализующая алгоритм построения допустимыхтраекторий была также запущена для матрицы, содержащей 16базовых, 19 целевых и 27 постоянных практик, построенной на основебизнес-кейса по разработке архитектуры предприятия (приложение 5).Однако за сутки работы программа не успевает построить множествовсехдопустимыхрешений,чтонеявляетсяприемлемым иподтверждает необходимость применения приближенных методов дляматриц большой размерности.Выводы по результатам вычислительного эксперимента:1.
Функции(2.21)и(2.26)пригодны для оценки траекторий в соответствии с содержательнойпостановкой задачи, описанной в параграфе 2.2.1202. Оптимизация по Парето для данной задачи дает приемлемыеварианты решений.3. Полученноепостоянноезначениесуммарнойлегкостиэлементарных преобразований подтверждает справедливость теоремыо суммарной легкости преобразований для использованных тестовыхданных.4. Целевые функции (2.30), (2.31) являются мультимодальными(многоэкстремальными).5. Графики целевых функций (2.30), (2.31), построенные дляодних и тех же решений в зависимости от роста их полноты (от 2 до 6элементарныхпреобразованийвтраектории)неявляютсямонотонными.6.
Целевые функции (2.30), (2.31) не являются аддитивными.7. В случае малой размерности матрицы изменений к решениюзадачи (2.30) – (2.33), применим алгоритм поиска с возвратами.8. Введение дополнительных ограничений (2.33) на порядокизменений существенно снижает время работы программы.3.5.Выбор метода решения задачиПроведенныйнецелесообразностьпоставленнойвычислительныйразработкизадачи.(мультимодальность,экспериментточныхХарактернемонотонностьнаметодовпоказываетрешенияцелевыхфункцийучасткахтраектории)позволяет говорить о неприменимости таких распространенныхточных методов решения задач дискретной оптимизации, как методветвей и границ и динамическое программирование.
Использованиепоиска с возвратами позволяет решить задачу только в случае малойразмерности, для которых этими методами возможно построениемножества всех допустимых решений за приемлемое время. Кроме121того, при уменьшении числа ограничений закономерно увеличиваетсяколичестводопустимыхрешений(вхудшемслучаеможетпотребоваться полный перебор). Напомним, что содержательнаяпостановка задачи не оговаривает обязательности ограничений,поэтому применение поиска с возвратами может стать проблемойдаже при решении задачи малой размерности.Остановимсянеобходимостьюнанекоторыхпереходаотсоображениях,точногосвязанныхрешениязадачискприближенному [43]: нахождение точного решения задачи может потребоватьслишкомбольшихпреодолениемвычислительныхвычислительныхресурсов,трудностейисвязаноспринципиальногохарактера; в прикладных задачах математическая модель является, какправило, лишь приближенным описанием реальной задачи, получениеточногорешениявэтомслучаеможетпредставлятьлишьакадемический интерес, и вряд ли оправдано; параметрыматематическоймоделиизвестныспогрешностями, и нахождение точного решения в этом случае непредставляется оправданным.Модель (2.9), описывающая взаимосвязи архитектурных блоков,основывается на экспертных оценках и априори не является точной.Эта модель (как и матрица изменений, и архитектура предприятия, наоснове которых она построена) представляет собой приближенноеописание реальности, и должна восприниматься, скорее, не какинструмент для выработки точных решений, а как средствоподдержки решений, используемое специалистами при подготовкеархитектурной дорожной карты.122Приведенныевычислительногосоображения,экспериментаатакжеговоряторезультатыцелесообразностиприменения приближенных методов решения.
Причем, посколькузадача (2.30) – (2.33) имеет два критерия оптимальности, необходиморассматривать приближенные методы решения многокритериальныхзадач дискретной оптимизации.Обычно указанные методы строят на основе эволюционныхалгоритмов и чаще всего – на основе генетических алгоритмов [21],позволяющих аппроксимировать множество Парето. При этомсоответствующиеметодыназываютмногокритериальнымигенетическими алгоритмами (МГА) или эволюционными методамиПарето-аппроксимации.Принципиальным в этих методах является не использованиеименно эволюционных алгоритмов, а правила формирования фитнессфункции, обеспечивающие перемещение индивидов популяции, вконечном счете, в направлении множества Парето.
Эволюция же этихиндивидов может протекать по законам, отличным от законов,используемых в эволюционных алгоритмах, например, по законаммиграции частиц в алгоритме роя частиц. Поэтому в качестве общегоназвания рассматриваемых методов в литературе используется такжетермин «популяционные методы Парето-аппроксимации» [21].В настоящее время МГА условно разделены на два поколения,причем второе поколение является развитием соответствующихалгоритмов первого за счет использования средств реализации в МГАстратегииэлитизма,вторичнойпопуляции(Парето-архива)испециальных методов ее обработки.Как показывает опыт, обычно не удается заранее определить,какой из алгоритмов окажется наиболее эффективным при решенииконкретной прикладной задачи [51].
Однако некоторые алгоритмы123могут быть отброшены при анализе их соответствия исходнымданным и структуре модели. Ряд рассмотренных алгоритмов МГА неподходят для решения задачи (2.30) – (2.33) ввиду особенностей ихпостроения. Например, применение метода взвешенных критериев(Sum of Weighted Objectives, SWO) и метода идеальной точкинецелесообразно, поскольку они требуют расстановки весовыхкоэффициентовкритериевоптимальности.Тоестьлицо,принимающее решение, должно заранее в количественном выраженииприсвоить веса критериям.
Кроме того, SWO работает только длявыпуклых Парето-фронтов, а нам ничего неизвестно о форме Паретофронта нашей задачи.НаиболеерекомендованныечастокиспользуемымиприменениюпоявляютсярезультатамМГА,обширногоисследования этого класса алгоритмов [108]: Nondominated SortingGenetic Algorithm (NSGA), Niched-Pareto Genetic Algorithm (NPGA),Multi-Objective Genetic Algorithm (MOGA).
В сравнении с другимигенетическими алгоритмами, эти алгоритмы позволяют решать задачимногокритериальноймногокритериальнойоптимизациипостановке,виспользуютестественнойнеобходимыетехнологии поддержания разнообразия популяции (niching, fitnesssharing), имеют приемлемую вычислительную сложность.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
