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

На правах рукописи

ГУМЕННИКОВА АЛЕКСАНДРА ВИКТОРОВНА АДАПТИВНЫЕ ПОИСКОВЫЕ АЛГОРИТМЫ ДЛЯ РЕШЕНИЯ СЛОЖНЫХ ЗАДАЧ МНОГОКРИТЕРИАЛЬНОЙ ОПТИМИЗАЦИИ 05.13.01 – Системный анализ, управление и обработка информации

АВТОРЕФЕРАТ

диссертации на соискание ученой степени кандидата технических наук

Красноярск – 2006

Работа выполнена в Государственном образовательном учреждении высшего профессионального образования «Сибирский государственный аэрокосмиче­ ский университет имени академика М.Ф. Решетнева», г. Красноярск

Научный консультант: доктор технических наук, профессор Семёнкин Евгений Станиславович

Официальные оппоненты: доктор технических наук, профессор Ловчиков Анатолий Николаевич кандидат технических наук, доцент Ефимов Сергей Николаевич

Ведущая организация: ГОУ ВПО «Томский государственный университет»

Защита состоится "22" июня 2006 года в 14 часов на заседании диссертационно­ го совета Д 212.249.02 при Сибирском государственном аэрокосмическом уни­ верситете имени академика М.Ф. Решетнева по адресу: 660014, г. Красноярск, пр. им. газеты «Красноярский рабочий»,

С диссертацией можно ознакомиться в научной библиотеке Сибирского госу­ дарственного аэрокосмического университета имени ак. М.Ф. Решетнева

Автореферат разослан "20" мая 2006 г.

Ученый секретарь диссертационного совета И.В. Ковалев

ОБЩАЯ ХАРАКТЕРИСТИКА РАБОТЫ

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

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

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

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

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

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

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

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

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

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

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

5. Разработать программную систему, реализующую предложенные ал­ горитмы и исследовать ее работоспособность и эффективность на те­ стовых задачах.

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

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

Научная новизна диссертационной работы состоит в следующем:

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

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

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

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

Реализация полученных результатов работы. Программная система решения многокритериальных задач условной и безусловной оптимизации с по­ мощью генетических алгоритмов прошла экспертизу и зарегистрирована в От­ раслевом фонде алгоритмов и программ при Федеральном агентстве по образо­ ванию (№ государственной регистрации 50200501526).

Построенные в диссертации формальные модели планирования произ­ водства и разработанная программная система использованы при решении ре­ альных задач планирования и анализа текущей деятельности Химзавода – фи­ лиала ФГУП «Красмашзавод» (п. Подгорный Красноярского края) и переданы для включения в состав автоматизированной системы управления предприятем.

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

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

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

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

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

Апробация работы. Основные положения и результаты диссертации докладывались и обсуждались на Всероссийской научно-практической конфе­ ренции «Решетневские чтения» (2003, 2004 гг.), Региональной конференции «Красноярский край – освоение, развитие, перспективы» (2003 г.), 4-й Между­ народной конференции «Актуальные проблемы современной науки» (г. Самара, 2003 г.), Всероссийской (с международным участием) научной конференции XI Туполевские чтения (г. Казань, 2003 г.), Международной научно-практической конференции «Системный анализ в проектировании и управлении» (г. Санкт Петербург, 2004 г.), III Всероссийской научно-практической конференции «Ин­ формационные технологии и математическое моделирование» (г. Анжеро-Су­ дженск, 2004 г.), Всероссийской научно-практической конференции «Актуаль­ ные проблемы авиации и космонавтики» (2005 г.), VI Всероссийской конферен­ ции молодых ученых по математическому моделированию и информационным технологиям с участием иностранных ученых (г. Кемерово, 2005 г.), Всероссий­ ской научно-технической конференции «Молодежь и наука: начало XXI века» (2005 г.), IX Международной научной конференции «Решетневские чтения» (2005 г.), а также на научных семинарах экспериментальной лаборатории ин­ теллектуальных технологий и адаптации и кафедры САИО в СибГАУ (2003 2005 гг.) и научном семинаре кафедры механики и процессов управления Крас­ ноярского государственного университета (2006 г.).

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

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

СОДЕРЖАНИЕ РАБОТЫ

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

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

Традиционные методы многокритериальной оптимизации можно условно разделить на 3 ключевых подхода. Первый связан с идеей ранжирования крите­ риев по важности и дальнейшей последовательной оптимизации каждого крите­ рия по отдельности с назначением допустимой величины изменения значения критерия, полученного на предыдущем шаге. Суть второго подхода состоит в выделении из всех критериев, а затем и оптимизации главного критерия и пере­ воде остальных в ограничения. Наиболее часто используемым на практике яв­ ляется третий подход – скаляризация векторного критерия в один обобщенный критерий. Основной проблемой, касающейся большинства традиционных мето­ дов, является необходимость прогонять алгоритм несколько раз для получения репрезентативной аппроксимации множества эффективных точек (число итера­ ций равно мощности предполагаемой аппроксимации множества Парето). Это и само по себе не очень удобно при решении практических задач, однако имеется и еще более существенный недостаток – получаемая аппроксимация множества недоминируемых решений может оказаться нерепрезентативной, т.к. генериру­ емые эффективные точки будут неравномерно распределены как в про­ странстве альтернатив, так и в пространстве критериев. Зачастую можно полу­ чить набор очень близких друг к другу решений при потенциально бесконеч­ ном множестве Парето. Основной причиной такой ситуации является то, что в каждом из них задача многокритериальной оптимизации сводится к одной или нескольким задачам однокритериальной оптимизации. Таким образом, теряется суть решаемой задачи – одновременный учет многих критериев.

В отличие от классических подходов к многокритериальной оптимиза­ ции, генетические алгоритмы (ГА) принадлежат к разряду многоточечных по­ исковых методов. Задача оптимизации с их помощью может быть решена даже в случае полимодального характера целевых функций. Более того, они также применимы к задачам с дискретным поисковым пространством. При решении многокритериальных задач генетические алгоритмы способны находить Паре­ то-оптимальное множество за один прогон, благодаря заложенному в них поли­ модальному поиску. Однако для обеспечения более репрезентативной аппрок­ симации необходимо принимать специальные меры.

Общая схема эволюционного алгоритма многокритериальной оптимиза­ ции приведена ниже. Существующие подходы отличаются способами реализа­ ции различных шагов (главным образом второго и третьего).

Пусть N – размер популяции ГА, T – максимальное число поколений, pc – вероятность скрещивания, pm – вероятность мутации, I – текущая популяция, A – недоминируемое множество.

1. Инициализация: положить P0= (начальная популяция), t=0 (t=1,…, T) и для i=1,…, N выполнить: а) выбрать индивида iI, б) добавить индивида i к множеству P0 (P0=P0+{i}).

2. Назначение пригодности: для каждого индивида iPt (текущая популя­ ция) определить закодированный вектор x=m(i) и вектор целей y=f(x), вычис­ лить скалярное значение функции пригодности пригодности F(i).

3. Селекция: положить P'= и для i=1,…, N выполнить: а) выбрать инди­ вида iPt согласно заданной схеме селекции и основываясь на его пригодности F(i), б) добавить индивида i к множеству P'=P'+{i}.

4. Рекомбинация (скрещивание): положить P'' = и для i=1,…, N/2 вы­ полнить: а) выбрать двух индивидов i, jP' и удалить их из P', б) осуществить скрещивание индивидов i и j, в результате получатся потомки l, kI, в) доба­ вить к P'' индивидов l и k с вероятностью pc или индивидов i и j с вероятностью (1– pc).

5. Мутация: положить P'''= и для каждого iP'' выполнить: а) мутиро­ вать индивида i с вероятностью pm, в результате получится индивид jI, б) до­ бавить индивида j к множеству P'''=P'''+{j}.

6. Завершение: положить Pt+1 =P''' и t=t+1, если t T, из последней попу­ ляции отбираются недоминируемые индивиды, т. е. получается результирую­ щее множество А = P(m(Pt)), иначе переходим на 2 этап.

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

Метод VEGA (Schaffer, 1985) использует селекцию по переключающимся целевым функциям, т.е. селекция производится по пригодности индивидов от­ носительно каждого из K критериев в отдельности. Тем самым промежуточная популяция заполняется равными порциями индивидов, отобранных по каждому из частных критериев.

Метод FFGA (Fonseca and Fleming, 1993) использует основанную на Па­ рето-доминировании процедуру ранжирования индивидов, где ранг каждого индивида определяется числом доминирующих его индивидов, т.е. пригодность определяется не значениями целевых функций, а рангом каждого индивида в популяции.

В методе NPGA (Horn, Nafpliotis and Goldberg, 1994, В.Р. Гарипов, 1998) этап назначения пригодности заменяется модифицированной схемой деления пригодности с использованием понятия ниши, которая определяется для инди­ видов в пространстве альтернатив или целевых функций и обеспечивает воз­ можность поддержания разнообразия, позволяя получить представительное множество Парето.

Метод SPEA (Zitzler and Thiele, 1998, В.М. Клешков, 2002) создает внеш­ нее множество, в котором хранятся индивиды, недоминируемые относительно других членов популяции и представляющие в итоге недоминируемый фронт.

Число индивидов во внешнем множестве регулируется с помощью кластерного анализа. Назначение индивидам скалярного значения пригодности в методе SPEA осуществляется только относительно индивидов внешнего множества, участвующих в селекции наравне с другими членами популяции. При этом, как и в методе FFGA, используется концепция Парето-доминирования.

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

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

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

Применение метода FFGA (рисунок 1, б) обеспечивает по сравнению с предыдущим методом нахождение более представительного множества реше­ ний. Однако разнообразие чаще всего поддерживается лишь по одной из пере­ менных, в чем метод FFGA в некотором смысле схож по действию со схемой селекции VEGA.

При использовании метода NPGA (рисунок 1, в) множество недоминируе­ мых точек получается еще более равномерно распределенным. В то же время результирующее множество решений содержит довольно много непаретовских точек, что является существенным недостатком представленного подхода.

Метод SPEA (рисунок 1, г) сочетает в себе достоинства указанных выше методов и дает по совокупности лучшие результаты по сравнению с остальны­ ми методами. При его работе использованием кластеров обеспечивается разно­ образие популяции, а за счет того, что во внешнем множестве накапливаются и хранятся недоминируемые относительно всех популяций точки-решения, в ре­ зультате обеспечивается хорошая аппроксимация множества и фронта Парето.

Однако по-прежнему итоговая популяция включает непаретовские точки, хотя и лежащие в непосредственной близости от множества Парето.

7 7 5 3 x2 x 1 X2 X 1 3 5 5 5 3 1 1 3 5 7 5 3 1 1 3 5 5 x1, X1 5 x1, X 7 а б 7 5 3 x2 x 1 X2 X 1 3 5 5 3 1 1 3 5 7 5 3 1 1 3 5 x1, X1 x1, X в г Рисунок 1 – Результаты решения четырехкритериальной задачи с критериями – квадратичными функциями:

а – методом VEGA;

б – методом FFGA;

в – методом NPGA;

г – методом SPEA Далее в диссертации рассматриваются задачи условной многокритериаль­ ной оптимизации и методы их решения.

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

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

5 3 1 1 3 5 Рисунок 2 – Множество Парето и "недоминируемые" точки при решении задачи условной многокритериальной оптимизации методом SPEA В более сложных задачах ситуация, анализируемая по числовым характе­ ристикам аппроксимации множества Парето, выглядит аналогично.

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

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

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

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

Типичный пример результата, получаемого гибридным алгоритмом, при­ веден на рисунке 3. Для большей наглядности представлена задача трехкрите­ риальной оптимизации квадратичных функций. k y 1 krit Yp o in ts 0 20 40 60 80 100 5 3 1 1 3 5 k2, krit x, Xp o in ts Рисунок 3 – Множество Парето и фронт Парето, полученные гибридным алгоритмом Результаты решения тестовых задач предложенным алгоритмом позволя­ ют сделать вывод об успешности выполненной модификации – точки располо­ жены практически равномерно и по всему множеству, доминируемых решений нет. Разумеется, в реальных задачах трудно ожидать похожей эффективности, но очевидно преимущество предложенного подхода над существующими.

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

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

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

Как было установлено, наилучшие результаты дает следующая схема ги­ бридного адаптивного алгоритма. 85% от общего заданного числа поколений (выделенного на оптимизацию ресурса) преобразованная многокритериальная задача оптимизации решается с использованием гибридной схемы SPEA+ПЛП.

Оставшуюся часть времени (15% ресурса) решается задача оптимизации без учета целевых функций исходной задачи, т.е. поиск решения проводится только по функциям-ограничениям, что приводит большую часть популяции в допу­ стимую область, хотя и с некоторой потерей качества по исключенным крите­ риям.

На следующем этапе работы алгоритма осуществляется "лечение" недо­ пустимых решений с помощью обычного локального поиска (ЛП) - минимиза­ ция степени нарушенности всех ограничений. В результате такого "лечения" все индивиды популяции становятся допустимыми по функциям-ограничениям.

Исходная многокритериальная задача условной оптимизации Преобразование Безусловная многокритериальная задача Решение гибридным методом SPEA+ПЛП (85% ресурса) Промежуточная популяция точек-решений Решение гибридным методом SPEA+ПЛП без учета целевых функций (15% ресурса) Точки-решения после остановки гибридного алгоритма «Лечение» недопустимых точек с помощью ЛП Решение многокритериальной задачи – недоминируемое множество Улучшение допустимых точек решений с помощью ПЛП Результат – решение условной задачи Рисунок 4 – Схема адаптивного поискового алгоритма решения многокритериальных задач условной оптимизации На последнем этапе работы алгоритма индивиды улучшаются с помощью ПЛП по всем критериям. Т.к. допустимые индивиды не могут доминироваться недопустимыми, улучшение происходит только по целевым функциям исход­ ной задачи. При этом ПЛП включает просмотр 1-соседних, 2-соседних и 3-со­ седних точек окрестности для преодоления множеств постоянства.

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

На рисунке 5 представлены результаты решения тестовой задачи в про­ странстве двух переменных. Жирными точками обозначены недоминируемые точки, получаемые в процессе работы алгоритма. Кружками отмечены решения после просмотра 1-соседних точек, крестиками – после просмотра 2-соседних точек и ромбиками – после просмотра 3-соседних точек, которые и являются конечным результатом решения задачи. Точкой условного минимума, то есть решением рассматриваемой задачи, является нижняя точка криволинейного четырехугольника – допустимой области. Рисунок 5, б отображает часть допу­ стимой области, укрупненную в районе точки условного оптимума.

4. 3. 2. 1. 1. а б 0. Рисунок 5 – Результаты решения условной задачи с помощью гибридного алгоритма 0. 1 0.3 0.4 1.1 1.8 2.5 3. Нетрудно видеть, что предложенный гибридный алгоритм требует на­ много большего количества вычислений функций задачи, чем обычные эволю­ ционные алгоритмы. Однако если предоставить эволюционным алгоритмам данное количество ресурса, они все равно не могут улучшить свою эффектив­ ность в смысле репрезентативности аппроксимации множества и фронта Паре­ то, т.е. дополнительные затраты не приводят к улучшению конечного результа­ та. Сравнение с мультистартом паретовского локального поиска тоже показало преимущество предложенного гибридного алгоритма.

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

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

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

Таким образом, разработанная программная система характеризуется ря­ дом особенностей, благодаря которым в одном приложении становится возмож­ ным:

решать многокритериальные задачи оптимизации различными эволю­ ционными методами, меняя при необходимости значения их парамет­ ров;

осуществлять как безусловную, так и условную многокритериальную оптимизацию;

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

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

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

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

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

Программная система MultiobjectiveGA отвечает современным требова­ ниям разработки программных продуктов, что подтверждено экспертизой и регистрацией в Отраслевом фонде алгоритмов и программ (№ гос. регистрации 50200501526).

Апробация разработанных в диссертации алгоритмов решения сложных задач многокритериальной оптимизации проводилась на актуальных задачах принятия решений при управлении инновационными процессами реструктури­ рованного предприятия ОПК, взятых с реального предприятия (Химзавода – филиала ФГУП «Красмаш»).

При реструктуризации предприятия его руководство (центральная компа­ ния) создает систему, которая позволит всем подразделениям стать материаль­ но заинтересованными в выборе новой продукции, развитии и увеличении объемов производства. Это так называемые Центры финансовой ответственно­ сти (ЦФО), которые непосредственно связанны с процессом производства.

Центральный офис предприятия реализует инвестиционную политику сов­ местной деятельности ЦФО и других участников объединения. С этой целью он концентрирует ресурсы и вкладывает их в новые инновационные проекты, ре­ конструкцию и модернизацию ЦФО и обслуживающих подразделений.

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

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

переменные принятия решения могут быть вещественными или целочисленны­ ми), а во втором случае необходимо выбрать вариант реализации (следователь­ но, переменные принятия решения могут быть целочисленными или бинарны­ ми).

Введем переменные принятия решения. Пусть для проекта с полной ин­ формацией xkij - объем ресурса k-го типа, вкладываемого в i-й инновационный проект в j-м временном интервале, k=1,…,K, j=1,…,T, i=1,…,n1, Xij = ( x1ij, x 2,…, ij x K ), а для проекта с неполной информацией vkj (yi) – объем ресурса k-го типа, ij вкладываемого в j-м временном интервале при условии, что i-й проект реализу­ ется по yi-му варианту, k=1,…,K, j=1,…,T, i=1,…,n2.

Пусть также R(Xij), P(Xij) – оценки риска невыполнения и прибыльности, соответственно, для i-го инновационного проекта с полной информацией в j-м временном интервале, а R(yi), P(yi) – оценки риска невыполнения и прибыльно­ сти для i-го инновационного проекта с неполной информацией при условии, что он выполняется по yi-му варианту. Данные оценки получены для каждого проекта независимо, т.е. без учета их взаимного влияния друг на друга.

Тогда задача распределения ресурсов при управлении инновационной программой может быть формализована следующим образом:

1 T n1 1 n R( X ) + n = 1 R( yi ) mini, ij T n1 j = 1 i = 1 X ij, y 2i n1 n T P( X ) + P( yi ) max, ij ij X, yi j= 1 i= 1 i= n1 n xk + vkj ( yi ) Vk j, k = 1, …, K, j = 1, …, T, ij i= 1 i= 0 yi hi, i = 1, …,n2, xk 0, i = 1, …,n1, j = 1, …, T, k = 1, …, K, ij где Vjk – уровень k-го ресурса, доступный в j-м временном интервале.

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

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

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

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

ОСНОВНЫЕ РЕЗУЛЬТАТЫ РАБОТЫ И ВЫВОДЫ Проведен анализ классических подходов к решению сложных задач 1.

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

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

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

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

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

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

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

Основные положения и результаты диссертационной работы пред­ ставлены в следующих работах автора:

1.Гуменникова А.В. Об эволюционных алгоритмах решения сложных за­ дач оптимизации / А.В. Гуменникова, М.Н. Емельянова, Е.С. Семенкин, Е.А. Сопов // Вестник Сибирского государственного аэрокосмического университета имени академика М.Ф. Решетнева: Сб. науч. тр. / СибГАУ.

– Красноярск, 2003. – Вып. 4. – С. 14-23.

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

3.Ильина Т.Р. Алгоритмы формирования производственной программы при инновационных процессах в малом и среднем бизнесе / Т.Р. Ильина, А.В. Гуменникова // Вестник Сибирского государственного аэрокосмиче­ ского университета имени академика М.Ф. Решетнева / СибГАУ. – Крас­ ноярск, 2006. – Вып. 2 (9).

4.Гуменникова А.В. Решение многокритериальных задач условной и без­ условной оптимизации с помощью генетических алгоритмов Multiobjec­ tiveGA v.1.0 / А.В. Гуменникова, Е.С. Семенкин // М.: ВНТИЦ, 2005. № гос. рег. 50200501526. – 12 с.

5.Гуменникова А.В. Решение многокритериальных задач условной и без­ условной оптимизации с помощью генетических алгоритмов Multiobjec­ tiveGA v.1.0 / А.В. Гуменникова, Е.С. Семенкин // Компьютерные учеб­ ные программы и инновации. – 2005, №8. – С. 16.

6.Гуменникова А.В. Распределение ресурсов при управлении инновация­ ми реструктурированного предприятия ВПК / А.В. Гуменникова, К.В. Гу­ палов, В.М. Клешков, О.Э. Семенкина // Инвестиционный и инновацион­ ный потенциал региона. Сб. научн. тр. - Красноярск: СибГАУ, 2004. – С.

56-66.

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

8.Гуменникова А.В. Об исследовании эффективности использования па­ ретовского локального поиска на различных этапах алгоритма решения многокритериальных задач условной оптимизации / А.В. Гуменникова // Всероссийская научно-техническая конференция «Молодежь и наука: на­ чало XXI века» / ИПЦ КГТУ. – Красноярск, 2005. – Ч. 3. – С. 80-87.

9. Гуменникова А.В. О настройке многокритериального коэволюционно­ го алгоритма / А.В. Гуменникова // VI Всероссийская конференция моло­ дых ученых по математическому моделированию и информационным технологиям (с участием иностранных ученых). – Кемерово, 2005. – С.

34.

10. Гуменникова А.В. О коэволюционном алгоритме для решения много­ критериальных задач оптимизации / А.В. Гуменникова // IX Междунар.

науч. конф. «Решетневские чтения» / СибГАУ. – Красноярск, 2005. – С.

17-18.

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

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

13. Гуменникова А.В. Применение локального поиска для повышения эф­ фективности алгоритма решения многокритериальных задач условной оптимизации / А.В. Гуменникова // VIII Всерос. науч. конф. с междунар.

участием «Решетневские чтения» / СибГАУ. – Красноярск, 2004. – С. 183.

14.Гуменникова А.В. Адаптивный поисковый алгоритм для решения за­ дач условной оптимизации / А.В. Гуменникова // III Всерос. научно-прак­ тическая конференция «Информационные технологии и математическое моделирование» / Томск. ун-т. – Анжеро-Судженск: филиал КемГУ, 2004. – Ч. 2. – С. 68-69.

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

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

Гуменникова Александра Викторовна Адаптивные поисковые алгоритмы для решения сложных задач многокритериальной оптимизации Автореферат Подписано к печати 19.05. Формат 60х84/16. Бумага писчая. Печ. л. 1. Тираж 100 экз. Заказ № Отпечатано в отделе копировальной и множительной техники СибГАУ 660014 г. Красноярск, пр. им. газеты «Красноярский рабочий»,