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

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

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

Благодаря заложенному параллелизму, у генетических алгоритмов есть большой потенциал в нахождении множества Парето-оптимальных решений при однократном запуске. Однако в большинстве сложных задач невозможно сгенерировать эффективные точки, представляющие более-менее полное множество Парето. Поэтому цель многокритериальной оптимизации может быть переформулирована и представлена в общем виде в виде трех подцелей [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 с.