«Поиск Парето-оптимальных решений в задаче многокритериальной оптимизации» - Дипломная работа

Содержание

Введение… 9

Конструкторская часть… 10

1. Постановка задачи многокритериальной оптимизации и методы аппроксимации множества Парето 10

1.1. Постановка задачи многокритериальной оптимизации 10

1.2. Непопуляционные методы аппроксимации множества Парето 11

1.2.1. Сеточные методы 11

1.2.2. Методы на основе свертки целевых функций 11

1.3. Популяционные методы аппроксимации множества Парето 13

1.3.1. Лексикографическая турнирная селекция 13

1.3.2. Алгоритмы чередующихся целевых функций 14

1.3.3. Алгоритмы на основе ранжирования агентов 16

1.3.4. Алгоритмы, не использующие ранжирование агентов 19

1.4. Выводы 19

2. Метод адаптивных взвешенных сумм в задаче Парето-аппроксимации и его модификации 20

2.1. Схема AWS-метода… 20

2.2. Выбор метода аппроксимации целевых функций 23

2.3. Модификация на основе повышения разнообразия множества архивных точек… 25

2.4. Модификация на основе смещения области доверия… 27

2.5. Модификация на основе генерации начального приближения… 28

2.6. Выводы 28

Технологическая часть… 29

3. Программная реализация модернизированного метода AWS 29

3.1. Выбор средств разработки 29

3.2. Структура программной системы 29

3.3. Реализация алгоритма решения однокритериальных задач 30

3.4. Реализация алгоритма квадратичной аппроксимации целевых функций 30

3.5. Реализация алгоритма нейросетевой аппроксимации целевых функций 32

3.6. Тестирование программной системы 33

3.7. Выводы 34

Исследовательская часть… 35

4. Исследование эффективности канонического метода AWS и его модификаций 35

4.1. Критерии качества метода… 35

4.2. Тестовые задачи МКО 35

4.3. Результаты тестирования 37

4.3.1. Исследование эффективности различных способов аппроксимации целевых функций 37

4.3.2. Исследование эффективности модификации на основе повышения разнообразия множества архивных точек… 40

4.3.3. Исследование эффективности модификации на основе смещения области доверия… 46

4.4. Выводы 49

5. Приближенное построение множества Парето для обратных задач химической кинетики (ДИБАГ и ДИБАХ)… 50

5.1. Решение обратной задачи химической кинетики для реакции гидроалюминирования олефинов (ДИБАГ) 50

5.1.1. Постановка задачи 50

5.1.2. Вычислительный эксперимент 53

5.2. Решение обратной задачи химической кинетики для реакции гидроалюминирования олефинов (ДИБАХ)… 54

5.2.1. Постановка задачи 54

5.2.2. Вычислительный эксперимент 57

5.3. Выводы 59

Заключение… 60

Литература 61

Введение

Классические методы решения задачи многокритериальной оптимизации (МКО-задачи) основаны на использовании, помимо указанной информации о задаче, еще тем или иным образом формализованной информации о предпочтениях ЛПР. В результате задачу удается свести к совокупности задач глобальной однокритериальной оптимизации. Относительно новый и быстро развивающийся класс методов решения МКО- задачи образуют методы Парето-аппроксимации, предполагающие предварительное построение некоторой конечномерной аппроксимации множества, а тем самым, и фронта Парето.

Известно большое число популяционных и непопуляционных методов построения Парето-аппроксимации. Работа посвящена исследованию эффективности метода адаптивных взвешенных сумм (Adaptive Weighted Sum method, AWS-method), который предложили и разработали Рю, Ким и Ван (J-H. Ryu, S. Kim, H. Wan) [1]. Для решения задачи Парето-аппроксимации метод AWS использует аддитивную свертку частных критериев оптимальности. Однако в отличие от классического метода суммы взвешенных критериев (Weighted Sum method, WS-method), также использующего такую свертку, метод AWS предполагает адаптацию весовых коэффициентов в процессе итераций на основе информации о текущем положении подобласти поиска. Целью разработки метода AWS было преодоление известного недостатка метода WS, заключающегося в невозможности локализации точек множества Парето, которые соответствуют вогнутым фрагментам фронта Парето.

Дипломный проект посвящен исследованию эффективности AWS-метода, выявлению его недостатков и разработке с их учетом модификаций метода.

Заключение

В конструкторской части работы был произведен обзор популяционных и непопуляционных методов Парето-аппроксимации, рассмотрена схема AWS-метода, выявлены его недостатки и на основе них предложены модификации метода.

В технологической части разработана программная система для построения Парето-аппроксимации AWS-методом.

В исследовательской части дипломного проекта проведен анализ эффективности предложенных модификаций и решены практически важные задачи: обратные задачи химической кинетики ДИБАГ и ДИБАХ.

Список литературы

1. Jong-hyun Ryu, Sujin Kim, Hong Wan. Pareto front approximation with adaptive sum method in multiobjective simulation optimization // Proceedings of the 2009 Winter Simulation Conference, pp. 623 – 633.

2. Асатурян В.И. Теория планирования эксперимента. – М.: Радио и связь, 1983 – 248 с.

3. Карпенко А.П. Методы оптимизации [Электронный ресурс] / (http://bigor.b**tu.ru), дата последнего доступа: 24.06.2013.

4. Хайкин С. Нейронные сети: полный курс.- М.: И.Д. Вильямс, 2006.- 1104 с.

5. Рамбо Дж., Блаха М. UML 2.0. Объектно-ориентированное моделирование и разработкаи. – СПб.: Питер, 2007. – 54 с.

6. Susan M. Sanchez, Paul J. Sanchez. Very large fractional and central composite design // ACM Transactions on Modeling and Computer Simulation, vol. 15, no. 4, October 2005, pp. 362 – 377.

7. Audet C., Savard G., Zghal W. Multiobjective optimization through a series of single-objective formulations // SIAM Journal on Optimization, 2006, 17(1), pp. 188–210.

8. Zitzler E., Deb K., Thiele L. Comparison of Multiobjective Evolutionary Algorithms: Empirical Results // Evolutionary Computation, 2000, Vol. 8, No. 2, pp. 173-195.

9. Губайдуллин И.М., Коледина К.Ф., Спивак С.И. Последовательно параллельное определение кинетических параметров // Журнал СВМО. – 2009. –Т.11. –№2. – С.14-24.

Примечания

В данной работе проведен обзор методов Парето-аппроксимации, проведен анализ метода адаптивных взвешенных сумм, выявлены его недостатки и на основе них предложены модификации метода. Разработана программная система для приближенного построения множества Парето методом адаптивных взвешенных сумм и исследована его эффективность. Построено множество Парето для обратной задачи химической кинетики.

К работе прилагается презентация в формате PowerPoint