авторефераты диссертаций БЕСПЛАТНАЯ  БИБЛИОТЕКА

АВТОРЕФЕРАТЫ КАНДИДАТСКИХ, ДОКТОРСКИХ ДИССЕРТАЦИЙ

<< ГЛАВНАЯ
АГРОИНЖЕНЕРИЯ
АСТРОНОМИЯ
БЕЗОПАСНОСТЬ
БИОЛОГИЯ
ЗЕМЛЯ
ИНФОРМАТИКА
ИСКУССТВОВЕДЕНИЕ
ИСТОРИЯ
КУЛЬТУРОЛОГИЯ
МАШИНОСТРОЕНИЕ
МЕДИЦИНА
МЕТАЛЛУРГИЯ
МЕХАНИКА
ПЕДАГОГИКА
ПОЛИТИКА
ПРИБОРОСТРОЕНИЕ
ПРОДОВОЛЬСТВИЕ
ПСИХОЛОГИЯ
РАДИОТЕХНИКА
СЕЛЬСКОЕ ХОЗЯЙСТВО
СОЦИОЛОГИЯ
СТРОИТЕЛЬСТВО
ТЕХНИЧЕСКИЕ НАУКИ
ТРАНСПОРТ
ФАРМАЦЕВТИКА
ФИЗИКА
ФИЗИОЛОГИЯ
ФИЛОЛОГИЯ
ФИЛОСОФИЯ
ХИМИЯ
ЭКОНОМИКА
ЭЛЕКТРОТЕХНИКА
ЭНЕРГЕТИКА
ЮРИСПРУДЕНЦИЯ
ЯЗЫКОЗНАНИЕ
РАЗНОЕ
КОНТАКТЫ

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

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

ГУМЕННИКОВА АЛЕКСАНДРА ВИКТОРОВНА АДАПТИВНЫЕ ПОИСКОВЫЕ АЛГОРИТМЫ ДЛЯ РЕШЕНИЯ СЛОЖНЫХ ЗАДАЧ МНОГОКРИТЕРИАЛЬНОЙ ОПТИМИЗАЦИИ 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 г. Красноярск, пр. им. газеты «Красноярский рабочий»,

 

Похожие работы:





 
2013 www.netess.ru - «Бесплатная библиотека авторефератов кандидатских и докторских диссертаций»

Материалы этого сайта размещены для ознакомления, все права принадлежат их авторам.
Если Вы не согласны с тем, что Ваш материал размещён на этом сайте, пожалуйста, напишите нам, мы в течении 1-2 рабочих дней удалим его.