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

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

ГУМЕННИКОВА АЛЕКСАНДРА ВИКТОРОВНА

АДАПТИВНЫЕ ПОИСКОВЫЕ АЛГОРИТМЫ

ДЛЯ РЕШЕНИЯ СЛОЖНЫХ ЗАДАЧ МНОГОКРИТЕРИАЛЬНОЙ ОПТИМИЗАЦИИ

13.01 - Системный анализ, управление и обработка информации

АВТОРЕФЕРАТ

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

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

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

Научный руководитель:

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

Официальные оппоненты:

доктор технических наук, профессор Ловчиков Анатолий Николаевич

кандидат технических наук, доцент Ефимов Сергей Николаевич

Ведущая организация.

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

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

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

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

Ученый секретарь диссертационного совета

И В Ковалев

2_ООб 6

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

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

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

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

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

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

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

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

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

РОС. НАЦИОНАЛЬНАЯ БИБЛИОТЬК<\

выявления наиболее перспективного подхода и направления его совершено кования.

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

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

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

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

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

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

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

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

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

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

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

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

лиала ФГУП «Красмашзавод» (п. Подгорный Красноярского края) и переданы для включения в состав автоматизированной системы управления предприятем

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

1. Инициализация: положить Р<г& (начальная популяция), í=0 (<=1,..., Г) и для . , N выполнить: а) выбрать индивида ге/, б) добавить индивида i к множеству Ро (P0=Po+{i})•

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

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

4. Рекомбинация (скрещивание): положить Р" =0 и для г-1,..., N12 выполнить: а) выбрать двух индивидов i, jsP' и удалить их из Р', б) осуществить скрещивание индивидов г и у, в результате получатся ноюмки /, в) добавить к Р" индивидов / и к с вероятностью рс или индивидов г и j с вероятностью (1 ~Рс)-

5 Мушция' положить Р"'-0 и для каждого ieP" выполнить: а) мутировать индивида i с вероятностьюрт> в результате получится индивидуе/. б) добавить индивида j к множеству P"'=P"'+{j}

6. Завершение положить Р,+, ~Р'" и 1, если t >Т. из последней популяции отбираются недоминируемые индивиды, т е получаемся результирующее множество А ~ Р(т(Р,)), иначе переходим на 2 этап

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

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

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

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

Метод SPEA (Zit/ler and Thiele, 1998, B.M Клешков, 2002) создает внешнее множество, в котором хранятся индивиды, недоминируемые относительно дру! их членов популяции и представляющие в итоге недоминируемый фрон1. Число индивидов во внешнем множестве регулируется с помощью кластерного анализа Назначение индивидам скалярной) значения пригодности в методе SPEA осуществляется только относительно индивидов внешнего множества, участвующих в селекции наравне с дру1 ими членами популяции При этом, как и в методе FFGA, используется концепция Парето-доминирования

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

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

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

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

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

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

а

б

'I-г

5 ' 3 ■ 1 '

_1_I_L

Рисунок 1 - Результаты решения четырехкритериальной задачи с критериями - квадратичными функциями: а - методом VEGA, б - методом FFGA; в - методом NPGA, г - методом SPEA

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

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

чения) не упрощает ситуацию, но делает модель менее адекватной реальной ситуации

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

Рисунок 2 - Множество Парето и "недоминирусмые" точки 'при решении ¡адачи условной многокритериальной оптимизации методом БРРА

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

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

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

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

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

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

Рисунок 3 - Множество Парето и фронт Парето, полученные гибридным алгоритмом

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

В качестве базового алгоритма решения условных задач многокритериальной оптимизации был выбран разработанный выше гибридный эволюционный алгоритм, который и исследовался на эффективность на тестовых задачах. Хотя результаты, полученные гибридным алгоритмом, оказались лучтпе, чем у обычных эволюционных алгоритмов многокритериальной оптимизации, включая ЗРЕЛ, они, тем не менее, не были в полной мере удовлетворительными Поэтом} далее в диссертации были выполнены исследования по выбору наиболее эффективной схемы сочетания паретовского локального поиска и 8РРА

Как было установлено, наилучшие результаты дает следующая схема гибридного адаптивного алгоритма 85% от общего заданного числа поколений (выделенною на оптимизацию ресурса) преобразованная многокритериальная задача оптимизации решается с использованием тибридной схемы ЯРЕА+ГООТ Оставшуюся часть времени (15% ресурса) решается задача оптимизации без учета целевых функций исходной задачи, т е поиск решения проводится только по функциям-ограничениям, чго приводит большую часть популяции в допустимую область, хотя и с некоторой потерей качества по исключенным критериям.

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

120

Т~ I

100

ция степени нарушенное™ всех ограничений В результате такого "лечения" все индивиды популяции становятся допустимыми по функциям-ограничениям.

Исходная многокритериальная задача

условной оптимизации

+ -

Преобразование

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

На последнем этапе работы алгоритма индивиды улучшаются с помощью ПЛП по всем критериям. Т.к. допустимые индивиды не могут доминироваться

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

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

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

Рисунок 5 - Результаты решения условной задачи с помощью гибридного алгоритма

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

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

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

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

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

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

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

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

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

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

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

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

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

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

рованного предприятия ОГГК, взятых с реального предприятия (Химзавода -филиала ФГУП «Красмаш»),

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

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

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

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

Введем переменные принятия решения Пусть для проекта с полной информацией х'1 - объем ресурса к-го типа, вкладываемого в 1-й инновационный проект в ]-м временном интервале, к=1,...,К, ]=1, ,Т. ¡=1 ,пь Хч = (х'{ . , гI). а для проекта с неполной информацией у/ (у,) объем ресурса к-го типа, вкладываемого в]-м временном интервште при условии, что ьй проект реализуется по у,-му варианту, к=1, ,Т, ¡=1, .,п2.

Пусть также 11(ХЧ), Р(Хи) - оценки риска невыполнения и прибыльное!и. соошетственно, для 1-го инновационного проекта с полной информацией в ]-м временном интервале, а ЩуО, Р(у,) - оценки риска невыполнения и прибыльности для ¡-то инновационного проекта с неполной информацией при условии, что он выполняется по угму варианту Данные оценки получены для каждого проекта независимо, т е без учета их взаимно! о влияния друг на друга

Тогда задача распределения ресурсов при управлении инновационной

программой может бьиь формализована следующим образом 1 +

¡-1 1-1 ,-1 * 'У'

+ |>/(Л)< К/, к= 1, ... , К, j = 1, ..., Т,

О < у, ^ Ь„ ¡ = 1, ...,п2, х'1>о,\ = 1, ,пь]=1, ,.,т,к=1, .,к, где - уровень к-го ресурса, доступный в ]-м временном интернале.

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

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

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

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

ОСНОВНЫЕ РЕЗУЛЬТАТЫ РАБОТЫ И ВЫВОДЫ

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

10 Гуменникова Л В О коэволюционном алгоритме для решения mhoi о-критериальных задач оптимизации / А В Гуменникова // IX Междунар науч конф «Рететневские чтения» / СибГАУ - Красноярск, 2005 -С 17-18

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

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

13 Гуменникова А В. Применение локального поиска для повышения эффективности алгоритма решения многокритериальных задач условной оптимизации / А В Гуменникова Н VIII Всерос науч. конф с междунар участием «Решетневские чтения» / СибГАУ - Красноярск, 2004. - С. 183

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

15 Гуменникова А В Один подход к решению многокритериальной задачи условной оптимизации генетическими алгоритмами / А.В Гуменникова // 4-я Международная конференция «Актуальные проблемы современной науки»

Fe гественные науки Часть 17 секции- информатика, вычислительная техника и управление. - Самара, 2003 -С 31-34

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

Гуменникова Александра Викторовна

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

Автореферат

Подписано к печати 19.05.2006 Форма! 60x84/16. Бумага писчая. Печ. л. 1.0 Тираж 100 экз. Заказ № £65

Отпечатано в отделе копировальной и множительной техники СибГАУ 660014 г Красноярск, пр. им. газеты «Красноярский рабочий», 31

гоос fi ^eSO

Введение.

Глава 1 Теоретические основы многокритериальных задач оптимизации и подходы к их решению.

§ 1.1 Постановка многокритериальной задачи.

§ 1.2 Классические методы решения задачи с векторным критерием.

§ 1.3 Эволюционный подход к векторной оптимизации.

§ 1.4 Методы многокритериальной оптимизации генетическими алгоритмами.

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

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

Выводы.

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

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

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

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

Выводы.

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

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

§ 3.2 Задача принятия решений при управлении инновационными процессами реструктурированного предприятия ОПК.

§ 3.3 Решение задачи распределения общих ресурсов при управлении инновациями предприятия ОПК.

§ 3.4 Задача принятия решений при планировании программы выпуска инновационной продукции.

Выводы.

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

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

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

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

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

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

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 печатных работ, перечень которых приводится в конце библиографического списка [100-115].

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

Выводы

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

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

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

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

Заключение

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

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

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

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

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

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

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

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

1. Аоки М. Введение в методы оптимизации. Перев. с англ., М.: Наука. Главная редакция физико-математической литературы, 1977. - 344 с.

2. Банди Б. Методы оптимизации. Вводный курс: Пер. с англ. М.: Радио и связь, 1988. - 128 е.: ил.

3. Батищев Д.И. Генетические алгоритмы решения экстремальных задач/ Уч. пособие. Воронеж: ВГТУ, 1995. - 69 с.

4. Беляков Г.П. и др. Основы системотехники: Учеб. Пособие для вузов/ Г.П. Беляков, В.А. Сарычев, В.А. Сорокин, В.О. Чернышев. Под ред. В.О. Чернышева. Томск: МГП «РАСКО», 1992. 312 с.: ил.

5. Березовский Б.А., Гнедин А.Г. Задача наилучшего выбора / Отв. ред. Трахтенгерц Э.А. М.: Наука, 1984. - 196 с.

6. Букатова И.Л., Ю.И. Михасев, A.M. Шаров. Эвоинформатика: Теория и практика эволюционного моделирования. М.: Мир, 1991. - 206 с.

7. Вороновский Г.К., и др. Генетические алгоритмы, искусственные нейронные сети и проблемы виртуальной реальности. X.: ОСНОВА, 1997.

8. Гарипов В.Р. Многокритериальная оптимизация систем управления сложными объектами методами эволюционного поиска. — Дисс. канд. техн. наук. Красноярск: САА, 1999.

9. Гафт М.Г. Принятие решений при многих критериях. М., 1979.

10. Горелик В.А., Горелов М.А., Кононенко А.Ф. Анализ конфликтных ситуаций в системах управления. М.; Радио и связь, 1991. - 288 с.

11. Дегтярев Ю. И. Системный анализ и исследование операций. М.: Высшая школа, 1996.

12. Дубов Ю.А., Травкин С.И., Якимец В.Н. Многокритериальные модели формирования и выбора вариантов систем. М.: Наука. Гл. ред. физ.-мат. лит., 1986. — 296 с. - (Теория и методы системного анализа.)

13. Емельянов С.В., Ларичев О.И. Многокритериальные методы принятия решений. М.: Знание, 1985. - 32 с. - (Новое в жизни, науке, технике. Сер. «Математика, кибернетика»; № 10).

14. Журавлев Ю.И., Финкельштейн Ю.Ю. Локальные алгоритмы для задач линейного целочисленного программирования. Проблемы кибернетики. -М.: Наука, 1965. Вып. 14. С. 289-295.

15. Исаев С.А. Популярно о генетических алгоритмах. URL: http://saisa.chat.m/ga/ga-pop.html#top.

16. Искусство программирования на С. Фундаментальные алгоритмы, структуры данных и примеры приложений: Энциклопедия программиста: Пер. с англ. / Р. Хэзфилд, Л. Кирби, Д. Корбит и др.- К.: Диасофт, 2001.- 736 с.

17. Кинев Ю.Ю. Оценка рисков финансово-хозяйственной деятельности предприятий на этапе принятия управленческого решения // Маркетинг в России и за рубежом, №5, 2000.

18. Кини Р.Л., Райфа X. Принятие решений при многих критериях: предпочтения и замещения: Пер. с англ./Под ред. И.Ф. Шахнова. — М.: Радио и связь, 1981. 560 с. ил.

19. Клешков В.М. Модели и алгоритмы распределения общих ресурсов при управлении инновациями реструктурированного предприятия ВПК. Дисс. канд. техн. наук. - Красноярск: НИИ СУВПТ, 2003, 165 с.

20. Коробейников С.П. Методы многокритериальной оптимизации для задач синтеза управления сложными объектами. — Дисс. на соиск. уч. степ. канд. техн. наук. Красноярск: ГХК, 1997. 174 с.

21. Круглов М. Генетические алгоритмы. Компьютерная газета. URL: http://www.nestor.rninsk.by/kg.

22. Крыжановский В.Г. Реструктуризация предприятия. Конспект лекций. М.: Издательство ПРИОР, ИВАКО Аналитик, 1998. - 48 с.

23. Кузин Б.И., Юрьев В.Н., Шахдинаров Г.М. Методы и модели управления фирмой. СПб.: Питер, 2001. - 432 с.

24. Курейчик В.М. Генетические алгоритмы. Таганрог: изд-во ТРТУ, 1998.-242 с.

25. Ларичев О.И. Наука и искусство принятия решений. М.: Наука, 1979.

26. Липский В. Комбинаторика для программистов: пер. с польск. М.: Мир, 1988.-213 с.

27. Мазур И.И., Шапиро В.Д. Реструктуризация предприятий и компаний. Справочное пособие для специалистов и предпринимателей. М.: Высшая школа, 2000. - 587 с.

28. Макаров И.М. и др. Теория выбора и принятия решений. М., 1987.

29. Математика. Большой энциклопедический словарь / Гл. ред. Ю.В. Прохоров. 3-е изд. - М.: Большая Российская энциклопедия, 1998. -848 с.

30. Машунин Ю.К. Модели и методы многокритериальной оптимизации. -М: Наука, 1982.-128 с.

31. Многокритериальная оптимизация. Математические аспекты. / Березовский Б.А. и др. М.: Наука, 1989. - 128 с.

32. Многокритериальные задачи принятия решений. Под ред. Д.М. Гви-шиани, С.В. Емельянова. М.: Машиностроение, 1978.

33. Одинцов М.В., Ежкин Л.В. Корпоратизация и реструктуризация как две стороны реформирования предприятия // Маркетинг в России, № 6, 2000.

34. Озерной В.М. Принципы построения и использования многокритериальных моделей задач принятия решений // Проблемы принятия решений. Вып. 5. М.: ИПУ, 1974. С. 3-15.

35. Орлов С.А. Технологии разработки программного обеспечения: Учебник / С.А. Орлов. СПб.: Питер, 2002 - 464 с.

36. Памятка автору: методические указания по типологии, стандартизации и структуре вузовской литературы / Сиб. гос. аэрокосмич. ун-т. Красноярск, 2005. - 72 с.

37. Первозванский А.А. Математические модели в управлении производством. М.: Наука, 1975.

38. Перегудов Ф.И., Тарасенко Ф.П. Основы системного анализа: Учеб. 2-е изд., доп. Томск: Изд-во HTJT, 1997. - 369 е.: ил.

39. Подиновский В.В. Многокритериальные задачи с упорядоченными по важности однородными критериями / В.В. Подиновский // Автоматика и телемеханики, 1976. №11. С. 118-127.

40. Подиновский В.В. Об относительной важности критериев в многокритериальных задачах принятия решений / В.В. Подиновский // Многокритериальные задачи принятия решений. М.: Машиностроение, 1978. С. 48-82.

41. Подиновский В.В., Гаврилов В.М. Оптимизация по последовательно применяемым критериям. М., «Сов. радио», 1975. 192 с.

42. Подиновский В.В., Ногин В.Д. Парето-оптимальные решения многокритериальных задач. М.: Наука. Главная редакция физико-математической литературы, 1982. — 256 с.

43. Прангишвили И.В. Энтропийные и другие системные закономерности: Вопросы управления сложными системами / И.В. Прангишвили; Ин-т проблем управления им. В.А. Трапезникова М.: Наука, 2003 — 428 с.

44. Пугачев B.C. Теория вероятностей и математическая статистика: Учеб. пособие / B.C. Пугачев 2-е изд., испр. и доп.- М.: Физматлит, 2002496 с.

45. Растригин JI.A. Случайный поиск. М.: Знание, 1979.

46. Редько В. Прикладное эволюционное моделирование. Генетический алгоритм. Оценка эффективности генетического алгоритма. URL:http://www.keldysh.ru/BioCvber/Lecturel 0.html.

47. Резников Б.А. Методы и алгоритмы оптимизации на дискретных моделях сложных систем. JL: ВИКИ им. Можайского, 1983. - 250 с.

48. Реформирование предприятий. Типовая программа. Методические рекомендации. Опыт реструктуризации. Сб. документов. М.: Издательский центр «Акционер», 1998. - 151 с.

49. Семенкин Е.С., Лебедев В.А. Метод обобщенного адаптивного поиска для синтеза систем управления сложными объектами. М.: МАКС-Пресс, 2002. - 320 с.

50. Семенкин Е.С., Семенкина О.Э., Коробейников С.П. Адаптивные поисковые методы оптимизации сложных систем. Красноярск: СИБУП, 1996.-275 с.

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

52. Семенкин Е.С., Семенкина О.Э., Терсков В.А. Методы оптимизации в управлении сложными системами. Красноярск: СЮИ МВД РФ, 2001. - 325 с.

53. Семенкин Е.С., Терсков В.А. Модели и методы оптимизации сложных систем. Красноярск: СибЮИ MB РФ, 2000. - 211 с.

54. Семенкина О.Э., Жидков В.В. Оптимизация управления сложными системами методом обобщенного локального поиска. М.: МАКС Пресс, 2002.-215 с.

55. Серов В.А. Генетический алгоритм многокритериальной оптимизации / В.А. Серов, Ю.В. Горячев // Проблемы теории и практики в инженерных исследованиях: Сб. научных трудов. М.: Машиностроение, 1999, с. 23-29.

56. Соммервилл И. Инженерия программного обеспечения: 6-е издание: Пер. с англ. / И. Соммервилл -М: Издательский дом "Вильяме", 2002624 с.

57. Стариков A. BaseGroup Labs. Генетические алгоритмы математический аппарат. URL: http://vyww.basegroup.ru/genetic/rnath.htrri.

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

59. Трахтенгерц Э.А. Компьютерная поддержка принятия решений / Э.А. Трахтенгерц. М.: Синтег, 1998 - 376 с.

60. Тренев В.Н., Ириков В.А., Ильдеменов С.В., Леонтьев С.В., Балашов В.Г. Реформирование и реструктуризация предприятия. Методика и опыт. М.: Издательство ПРИОР, 1998. - 320 с.

61. Фогель Л., Оуэне А., Уолш М. Искусственный интеллект и эволюционное моделирование. Пер с англ. Зайченко Ю.П. Под ред. Ивахненко А.Г. М.: Мир, 1969. - 230 с.

62. Фокс Дж. Программное обеспечение и его разработка: Пер. с англ. / Дж. Фокс.-М.: Мир, 1985 368 с.

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

64. Черноруцкий И.Г. Методы оптимизации и принятия решений: Учебное пособие / И.Г. Черноруцкий СПб: Лань, 2001 - 384 с.

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

66. Шилдт Г. Полный справочник по С: 4-е издание: Пер. с англ. / Г. Шилдт.-М.: Издательский дом "Вильяме", 2002.- 704 с.

67. Экономико-математические модели в организации и планировании промышленного предприятия / Под ред. Кузина Б.И. Л: Изд-во ЛГУ, 1982.

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

69. Antamoshkin A., Schwefel Н.-Р., Torn A., Yin G., Zilinskas A. System Analysis, Design and Optimization. An Introduction. Krasnoyarsk, 1993. - 203 p.

70. Baker J. Adaptive selection methods for genetic algorithms. Proc. International Conf. on Genetic Algorithms and Their Applications. J. Grefenstette, ed. Lawrence Erlbaum, 1985.

71. Baker J. Reducing Bias and Inefficieny in the Selection Algorithm. Genetic Algorithms and Their Applications: Proc. Second International Conf. J. Grefenstette, ed. Lawrence Erlbaum, 1987.

72. Bentley P.J., Wakefield J.P. Finding Acceptable Solutions in the Pareto-Optimal Range using Multiobjective Genetic Algorithms. In Proceedings of the 2nd On-Line World Conference on Soft Computing in Engineering Design and Manufacturing, 1997.

73. Cieniawski S. E. An investigation of the ability of genetic algorithms to generate the tradeoff curse of a multi-objective groundwater monitoring problem. Master's thesis. University of Illinois at Urbana-Champaign. 1993.

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

75. Coello Coello C.A. A comprehensive survey of evolutionary-based multiobjective optimization techniques. Laboratorio Nacional de Informatica Avanzada, Veracruz, Mexico, 1998.

76. Cohon J. Multiobjective Programming and Planning, John Wiley, New York, 1978.

77. Deb K. Multi objective genetic algorithms: Problems difficulties and construction of test Functions / Evolutionary Computation, Vol. 7. Pp. 205230, 1999.

78. Deb K. Multi-objective Optimization using Evolutionary Algorithms. Chichester, UK: Wiley, 2001.

79. Deb K., Pratap A., Agarwal S., Meyarivan T. A Fast and Elitist Multi-objective Genetic Algorithm: NSGA II. KanGAL Report No. 200001. Indian Institute of Technology, Kanpur, India, 2000.

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

81. Fonseca C.M., Fleming P.J. Genetic algorithms for multi-objective optimization: Formulation, discussion and generalization / In Proceedings of the First International Conference on Genetic Algorithms, San Mateo, 1993. -Pp. 416-423.

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

83. Goldberg D.E. Genetic Algorithms in Search, Optimization and Machine Learning. Reading, MA: Addison-Wesley, 1989.

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

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

86. Kauffman S.A. Adaptation on rugged fitness landscapes. In lectures Notes on Complexity, D. Stein (Ed.), Addison-Wesley, pp. 527-618, 1989.

87. Knowles J., Corne D. The Pareto archived evolution strategy: A new baseline algorithm for multiobjective optimization. Proceedings of the 1999 Congress on Evolutionary Computation, Piscataway, New Jersey: IEEE Service Center, 1999, pp. 98-105.

88. Koski J., Oscyczka A. Multi-criteria Design Optimization. Springer-Verlag, 1990.

89. Michalewicz Z. Genetic algorithms, numerical optimization and constraints. // Proc. of the Sixth Int. Conf. on Genetic Algorithms and their Applications, Pittsburgh, PA, 1995.

90. Ray Т., Kang Т., Chye S. Multiobjective design optimization by an evolutionary algorithm. Engineering Optimization, 2001.

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

92. Schwefel H.-P. Evolution and Optimum Seeking.-N.Y.: Whiley Publ., 1995.-612 pp.

93. Steuer R.E. Multiple Criteria Optimization. John Wiley, New York, 1986.

94. Srinivas N., Deb K. Multiple-Objective function optimization using non-dominated sorting genetic algorithms. Evolutionary Computation, Vol. 2, pp. 221-248, 1995.

95. Van Veldhuizen D. Multiobjective evolutionary algorithms: Classifications, analyses, and new innovations. PhD Dissertation and Technical Report No. AFIT/DS/ENG/99-01, Dayton, Ohio: Air Force Institute of Technology,1999.

96. Watanabe S., Hiroyasu Т., Miki M. NCGA: Neighborhood Cultivation Genetic Algorithm for Multi-Objective Optimization Problems. Proceedings of the Genetic and Evolutionary Computation Conference, pp. 458-465, 2002.

97. Zitzler E., Deb K., Thiele L. Comparison of multiobjective evolutionary algorithms: Empirical results. Evolutionary Computation, Vol. 8, pp. 173-195,2000.

98. Zitzler E., Thiele L. Multiobjective evolutionary algorithms: A comparative case study and the strength Pareto approach // IEEE Transactions on Evolutionary Computation, Vol. 3, No. 4, pp. 257-271, 1999.

99. Публикации автора диссертации:

100. СибГАУ. Красноярск, 2003. - Вып. 4. - С. 14-23.

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

102. Щ ярск, 2003. Вып. 13. - С. 237-248.

103. Красноярск, 2004. Вып. 5. - С. 70-76.

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

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

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

107. Гуменникова А.В. О коэволюционном алгоритме для решения многокритериальных задач оптимизации / А.В. Гуменникова // IX Междунар. науч. конф. «Решетневские чтения» / СибГАУ. — Красноярск, 2005. С. ' 17-18.