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

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

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

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

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

Глава 4:

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

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

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

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

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

Заключение:

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

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

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

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