Содержание

Содержание

Введение 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

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

Введение

Введение

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

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

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

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

Теория многокритериальной оптимизации зародилась более полувека назад. Задачи в этой области естественным образом возникли в математической экономике, а в последствии разрабатывались подходы к решению данного рода задач в различных областях: специалистами по системному анализу и теоретиками в области принятия решений.

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

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

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

Сформулированная цель предопределила совокупность решаемых задач:

1. На основе анализа классических подходов к решению задач многокритериальной оптимизации выявить области их недостаточной эффективности по сравнению с эволюционным подходом к решению задач данного класса.

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

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

4. Создать программный продукт, реализующий разработанный алгоритм и методы многокритериальной оптимизации генетическими алгоритмами.

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

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

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

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

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

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

Основные тезисы, выносимые на защиту:

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

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

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

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

Апробация работы. Результаты работы докладывались и обсуждались на следующих конференциях:

? Всероссийская научно-практическая конференция "Решетневские чтения" (г. Красноярск, Сибирский государственный аэрокосмический университет, 2002 г.);

? Региональная конференция «Красноярский край – освоение, развитие, перспективы» (2003 г.);

? 41-я Внутривузовская конференция творческой молодежи, посвященная Всемирному дню авиации и космонавтики (г. Красноярск, Сибирский государственный аэрокосмический университет, 2003 г.);

? 4-ая Международная конференция молодых ученых и студентов «Актуальные проблемы современной науки» (г. Самара, 2003 г.);

? XI туполевские чтения: Всероссийская (с международным участием) молодежная научная конференция (г. Казань, 2003 г.);

? XVII Краевая научная студенческая конференция по математике (г. Красноярск, Красноярский государственный университет, 2004 г.);

? 42-я Внутривузовская конференция творческой молодежи, посвященная Всемирному дню авиации и космонавтики 12 апреля (г. Красноярск, Сибирский государственный аэрокосмический университет, 2004 г.);

? VIII Международная научно-практическая конференция «Системный анализ в проектировании и управлении» (г. Санкт-Петербург, 2004 г.).

Публикации. Основные положения и результаты диссертации опубликованы в 10 работах, список которых указан в диссертации в конце списка использованных источников.

Структура и объем работы. Диссертация изложена на 99 страницах основного текста и состоит из введения, четырех глав, заключения, списка использованных источников (32 наименования) и приложения. Материал проиллюстрирован 29 рисунками и 3 таблицами.

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

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

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 с.

11. Семенкин Е.С., Семенкина О.Э., Коробейников С.П. Оптимизация технических систем. Учебное пособие. – Красноярск: СИБУП, 1996. 284 с.

12. Струнков Т. Что такое генетические алгоритмы / PC Week RE 19/99. URL: http://www.neuroproject.ru/gene.php .

13. Хайниш С.В., Клешков В.М., Бородин А.Н. Российское предприятие ВПК: выжить и развиваться. (На примере реформирования и развития Химзавода – филиала ФГУП «КРАСМАШ»). – М.: Рохос, 2003. – 240 с., цв. вкл. (Из опыта управленческого консультирования.)

14. Шамис В. Borland C++Builder 5: учебный курс. – СПб.: Питер, 2002. – 688 с.: ил.

15. Юдин Д.Б. Вычислительные методы теории принятия решений. – М.: Наука. Гл. ред. физ.-мат. лит., 1989. – 320 с. (Теория и методы системного анализа.)

16. Coello Coello Carlos A. An empirical study of evolutionary techniques for multiobjective optimization in engineering design. PhD thesis. Department of computer science, Tulane university. New Orleans, LA, apr 1996.

17. Coello Coello C.A. A comprehensive survey of evolutionary-based multiobjective optimization techniques.

18. Fonseca C.M., Fleming P.J. Multiobjective optimization and multiple constraint handling with evolutionary algorithms - Part I: A unified formulation. Technical report 564, University of Sheffield, Sheffield, UK, January 1995.

19. Fonseca C.M., Fleming P.J. Multiobjective optimization and multiple constraint handling with evolutionary algorithms - Part II: Application example. Technical report 565, University of Sheffield, Sheffield, UK, January 1995.

20. Holland, J.H. Adaptation in Natural and Artificial Systems. Cambridge, MA: MIT Press, 1992 (2nd edition).

21. Horn, J., Nafpliotis N., Goldberg D. E. A niched Pareto genetic algorithm for multiobjective optimization. In Proceedings of the First IEEE Conference on Evolutionary Computation, Vol. 1, Piscataway, 1994. - P. 82-87.

22. Schaffer, J.D. Multiple objective optimization with vector evaluated genetic algorithms. In J. J. Grefenstette (Ed.), Proceedings of an International Conference on Genetic Algorithms and Their Applications, Pittsburgh, PA, 1985. - P. 93-100.

23. Zitzler E., Thiele L. Multiobjective evolutionary algorithms: A comparative case study and the strength Pareto approach // IEEE Transactions on Evolutionary Computation, 1999.

Публикации диссертанта:

24. Gumennikova, A.V. Comparative analysis of multiobjective optimization methods by genetic algorithms / A.V. Gumennikova // Красноярский край: освоение, развитие, перспективы: Тез. Докл. Регион. Студ. Науч. Конф. Ч. 1/ Краснояр. Гос. Аграр. Ун-т; Сост. О.Н. Чепалова. – Красноярск, 2003, с. 33-34.

25. Гуменникова, А.В. Об эволюционных алгоритмах решения сложных задач оптимизации / А.В. Гуменникова, М.Н. Емельянова, Е.С. Семенкин, Е.А. Сопов // Вестник Сибирского государственного аэрокосмического университета имени академика М.Ф. Решетнева: Сб. науч. тр./ Под ред. Проф. Г.П. Белякова; СибГАУ. – Вып. 4. – Красноярск, 2003, с. 14-23.

26. Гуменникова, А.В. О решении задачи многокритериальной оптимизации генетическими алгоритмами / А.В. Гуменникова // XI туполевские чтения: Всероссийская (с международным участием) молодежная научная конференция, Казань, 8 – 10 октября 2003 года: Тезисы докладов. Том III. Казань: изд-во Казан. Гос. Техн. Ун-та. 2003. с. 7.

27. Гуменникова, А.В. Один подход к решению многокритериальной задачи условной оптимизации генетическими алгоритмами / А.В. Гуменникова // Труды 4-ой Международной конференции молодых ученых и студентов «Актуальные проблемы современной науки». Естественные науки. Часть 17 Секции: информатика, вычислительная техника и управление. – Самара, 2003, с. 31-34.

28. Гуменникова, А.В. Эволюционные алгоритмы для многокритериальной и многоэкстремальной оптимизации / А.В. Гуменникова, М.Н. Емельянова, В.М. Клешков // Вестник НИИ СУВПТ, № 13: Сб. научн. трудов. – Красноярск: НИИ СУВПТ, 2003. – Вып. 13, с. 237-248.

29. Семенкин, Е.С. Распределение ресурсов при управлении инновациями реструктурированного предприятия ВПК / Е.С. Семенкин, В.М. Клешков, К.В. Гупалов, А.В. Гуменникова // – Красноярск: СибГАУ, 2004, с. 124-134.

30. Гуменникова, А.В. Модели и алгоритмы формирования инновационной программы реструктурированного предприятия ВПК / А.В. Гуменникова, К.В. Гупалов // Сборник трудов межрегиональной научно-практической конференции «Интеллект 2004». – Красноярск: СИБУП, 2004, с. 3-5.

31. Гуменникова, А.В. Алгоритм решения многокритериальных задач условной оптимизации / А.В. Гуменникова // Труды 42-й Внутривузовской конференции творческой молодежи, посвященной Всемирному дню авиации и космонавтики 12 апреля. – Красноярск: СибГАУ, 2004.

32. Гуменникова, А.В. Об эволюционном подходе к решению многокритериальных задач условной оптимизации / А.В. Гуменникова // Труды VIII Международной научно-практической конференции «Системный анализ в проектировании и управлении». – Санкт-Петербург, 2004, с. 72-76.

33. Гуменникова, А.В. Гибридный алгоритм адаптивного поиска для решения задач условной многокритериальной оптимизации / А.В. Гуменникова, Т.Р. Ильина // Вестник Сибирского государственного аэрокосмического университета имени академика М.Ф. Решетнева: Сб. науч. тр./ Под ред. Проф. Г.П. Белякова; СибГАУ. – Вып. 5. – Красноярск, 2004, с. 70-76.

Примечания:

Примечаний нет.