Часть диссертации по теме: Разработка и исследование адаптивного поискового алгоритма для решения многокретериальных задач условной оптимизации (магистерская диссертация)

Название работы: Разработка и исследование адаптивного поискового алгоритма для решения многокретериальных задач условной оптимизации (магистерская диссертация)

Скачать демоверсию

Тип работы:

Часть диссертации

Предмет:

Финансовый менеджмент, финансовая математика

Страниц:

105 стр.

Год сдачи:

2007 г.

Содержание:

Глава 1 Теоретические основы многокритериальных задач

оптимизации и основные подходы к их решению 10

1.1 ПОСТАНОВКА МНОГОКРИТЕРИАЛЬНОЙ ЗАДАЧИ 11

1.1.1 Формулировка задачи векторной оптимизации 11

1.1.2 Парето-оптимальность 12

1.1.3 Концепция доминирования по Парето 13

1.1.4 Множество и фронт Парето 13

1.2 КЛАССИЧЕСКИЕ МЕТОДЫ РЕШЕНИЯ ЗАДАЧИ С ВЕКТОРНЫМ

КРИТЕРИЕМ 14

1.2.1 Метод последовательных уступок 15

1.2.2 Метод выделения основного частного критерия 17

1.2.3 Свертка критериев 18

1.3 ЭВОЛЮЦИОННЫЙ ПОДХОД К ВЕКТОРНОЙ ОПТИМИЗАЦИИ 21

1.4 ВЫВОДЫ 22

Глава 2 Генетические алгоритмы для многокритериальной оптимизации 24

2.1 РЕШЕНИЕ МНОГОКРИТЕРИАЛЬНОЙ ЗАДАЧИ С ПОМОЩЬЮ

ГЕНЕТИЧЕСКИХ АЛГОРИТМОВ 25

2.1.1 Основные принципы эволюционной теории 25

2.1.2 Общий эволюционный алгоритм 31

2.2 ПОДХОДЫ К НАЗНАЧЕНИЮ ПРИГОДНОСТИ И СЕЛЕКЦИИ 33

2.3 ПОДДЕРЖАНИЕ РАЗНООБРАЗИЯ ПОПУЛЯЦИИ 34

2.4 ЭЛИТИЗМ 37

2.5 МЕТОДЫ МНОГОКРИТЕРИАЛЬНОЙ ОПТИМИЗАЦИИ ГЕНЕТИЧЕСКИМИ

АЛГОРИТМАМИ 38

2.5.1 Метод VEGA (Vector Evaluated Genetic Algorithm) 39

2.5.2 Метод FFGA (Fonseca and Fleming’s Multiobjective Genetic

Algorithm) 40

2.5.3 Метод NPGA (Niched Pareto Genetic Algorithm) 42

2.5.4 Метод SPEA (Strength Pareto Evolutionary Algorithm) 44

2.6 СРАВНИТЕЛЬНЫЙ АНАЛИЗ МЕТОДОВ МНОГОКРИТЕРИАЛЬНОЙ

ОПТИМИЗАЦИИ ГЕНЕТИЧЕСКИМИ АЛГОРИТМАМИ 51

2.6.1 Тестовые задачи 52

2.6.2 Параметры алгоритмов 53

2.6.3 Результаты решения тестовых задач методами VEGA,

FFGA, NPGA и SPEA 54

2.7 ВЫВОДЫ 66

Глава 3 Алгоритм решения многокритериальной задачи

условной оптимизации 68

3.1 СВЕДЕНИЕ УСЛОВНОЙ ЗАДАЧИ К БЕЗУСЛОВНОЙ

МНОГОКРИТЕРИАЛЬНОЙ ЗАДАЧЕ 70

3.2 РЕШЕНИЕ УСЛОВНОЙ ЗАДАЧИ МЕТОДОМ SPEA 70

3.3 ЛЕЧЕНИЕ ТОЧЕК-РЕШЕНИЙ ЛОКАЛЬНЫМ ПОИСКОМ 71

3.4 СХЕМА АЛГОРИТМА РЕШЕНИЯ МНОГОКРИТЕРИАЛЬНОЙ ЗАДАЧИ

УСЛОВНОЙ ОПТИМИЗАЦИИ 73

3.5 РЕЗУЛЬТАТЫ РЕШЕНИЯ УСЛОВНОЙ ЗАДАЧИ РАЗРАБОТАННЫМ

АЛГОРИТМОМ 75

3.6 ВЫВОДЫ 77

Глава 4 Практическая реализация разработанного

алгоритма 78

4.1 ПРОГРАММНАЯ СИСТЕМА ДЛЯ РЕШЕНИЯ ЗАДАЧ УСЛОВНОЙ

МНОГОКРИТЕРИАЛЬНОЙ ОПТИМИЗАЦИИ 78

4.1.1 Общие сведения 79

4.1.2 Функциональная структура 80

4.1.3 Эксплуатация и применение программной системы 82

4.2 ЗАДАЧА ПРИНЯТИЯ РЕШЕНИЙ ПРИ УПРАВЛЕНИИ ИННОВАЦИОННЫМИ

ПРОЦЕССАМИ РЕСТРУКТУРИРОВАННОГО ПРЕДПРИЯТИЯ ВПК 87

4.3 ПРИМЕНЕНИЕ РАЗРАБОТАННОГО АЛГОРИТМА ПРИ РЕШЕНИИ

ПРАКТИЧЕСКОЙ ЗАДАЧИ 89

4.4 ВЫВОДЫ 93

Заключение 94

Список использованных источников 96

Приложение А 100

Выдержка:

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

Для того чтобы осуществить «хороший» выбор, т.е. выбрать наилучшее решение, наиболее точно соответствующее достижению цели ЛПР, необходимо располагать предварительным множеством альтернатив-решений, из которых и предстоит сделать окончательный выбор. Множество альтернатив должно быть по возможности наиболее полным и представительным, учитывающим все возможные варианты решения. Второй неотъемлемой составляющей является способ сравнения альтернатив между собой – критерий оценки их качества, позволяющий осуществлять непосредственный отбор наиболее предпочтительных альтернатив из первоначального множества.

Благодаря заложенному параллелизму, у генетических алгоритмов есть большой потенциал в нахождении множества Парето-оптимальных решений при однократном запуске. Однако в большинстве сложных задач невозможно сгенерировать эффективные точки, представляющие более-менее полное множество Парето. Поэтому цель многокритериальной оптимизации может быть переформулирована и представлена в общем виде в виде трех подцелей [23]:

 отдаленность полученного недоминируемого фронта от Парето-оптимального фронта должна быть минимальна;

 желательно хорошее (в большинстве случаев однородное) распределение найденных решений;

 разброс полученного недоминируемого фронта должен быть максимален, то есть для каждой целевой функции результирующими недоминируемыми решениями должен покрываться как можно более широкий диапазон ее значений.

Как показали проведенные исследования 4 методов многокритериальной оптимизации генетическими алгоритмами (см. п. 2.6), наиболее хорошо достичь всех подцелей, а, следовательно, и наиболее точно решить исходную задачу многокритериальной оптимизации удается при использовании метода SPEA.

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

1. Аоки М. Введение в методы оптимизации. Перев. с англ., – М.: Наука. Главная редакция физико-математической литературы, 1977. – 344 с.

2. Беляков Г.П. и др. Основы системотехники: Учеб. Пособие для вузов/ Г.П. Беляков, В.А. Сарычев, В.А. Сорокин, В.О. Чернышев. Под ред. В.О. Чернышева. – Томск: МГП «РАСКО», 1992. 312 с.: ил.

3. Дубов Ю.А., Травкин С.И., Якимец В.Н. Многокритериальные модели формирования и выбора вариантов систем. – М.: Наука. Гл. ред. физ.-мат. лит., 1986. – 296 с. – (Теория и методы системного анализа.)

4. Емельянов С.В., Ларичев О.И. Многокритериальные методы принятия решений. – М.: Знание, 1985. – 32 с. – (Новое в жизни, науке, технике. Сер. «Математика, кибернетика»; № 10).

5. Кини Р.Л., Райфа Х. Принятие решений при многих критериях: предпочтения и замещения: Пер. с англ./Под ред. И.Ф. Шахнова. – М.: Радио и связь, 1981. – 560 с. ил.

6. Клешков В.М. Модели и алгоритмы распределения общих ресурсов при управлении инновациями реструктурированного предприятия ВПК. –Дисс. канд. техн. наук. – Красноярск: НИИ СУВПТ, 2003, 165 с.

7. Круглов М. Генетические алгоритмы. Компьютерная газета. URL: http://www.nestor.minsk.by/kg.

8. Перегудов Ф.И., Тарасенко Ф.П. Основы системного анализа: Учеб. 2-е изд., доп. – Томск: Изд-во НТЛ, 1997. – 369 с.: ил.

9. Подиновский В.В., Ногин В.Д. Парето-оптимальные решения многокритериальных задач. – М.: Наука. Главная редакция физико-математической литературы, 1982. – 256 с.

10. Подиновский В.В., Гаврилов В.М. Оптимизация по последовательно применяемым критериям. М., «Сов. радио», 1975, 192 с.

Скачать демоверсию

Похожие работы на данную тему