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

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

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

Тип работы:

Дипломная

Предмет:

Матметоды в эк-ке

Страниц:

100 стр.

Год сдачи:

2004 г.

Содержание:

Введение 4

Глава 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

Выдержка:

Введение:

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

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

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

Формализация задач, укладывающихся в рамки математического программирования, не связана с принципиальными трудностями – понятие «приемлемое решение» здесь обычно без труда определяется извне из содержательных соображений. Совсем иная ситуация возникает при формализации задач теории выбора решений, связанных с достижением многих целей, с согласованием интересов группы лиц, с преодолением конфликтов. Здесь, кроме вычислительных трудностей, появляются трудности концептуального характера, связанные с определением понятий «компромисс», «равновесие», «справедливое решение». Выбор «компромиссных» многоцелевых решений, характеризующийся множеством критериев с определенными ограничениями на параметры, требует принципиально новых подходов, существенно более широких и гибких, чем в традиционной теории оптимизации.

Глава 4:

Для решения этой задачи разработанным алгоритмом использовались реальные данные, взятые из практики работы предприятия. В приложении А приведен список ЦФО, инновационные проекты, планируемые для внедрения, а также соответствующие им числовые данные: планируемые прибыльность, затраты и рискованность внедрения.

Согласно постановке задачи допустимая область находится на пересечении ограничений (3) и (4). В связи с тем, что область поиска по сравнению с тестовыми задачами расширяется, а возможных вариантов решения становится больше, размер внешнего множества в методе SPEA был увеличен до 40 (см. п. 2.5.4). Остальные настройки алгоритма не менялись.

Были проверены различные варианты значений параметров задачи (плановый годовой объем финансовых средств, выделяемый цен¬тральной компанией в планы нововведений ЦФО ( ) и норма прибыли на капитал ( )) и на всех рассмотренных вариантах алгоритм показал свою эффективность. Далее приводятся результаты решения практической задачи при =40 и =0.5.

Результаты решения практической задачи

В таблице 2 приведены недоминируемые решения (колонка 2), получающиеся после 800-го поколения при решении задачи с помощью метода SPEA. Соответствующие им значения критериев (5) – (8) представлены в колонках 3-6.

Заключение:

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

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

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

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

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