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

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

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

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

Размещено на http://www.allbest.ru/

Размещено на http://www.allbest.ru/

Рисунок 20 - Схема алгоритма решения

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

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

3.5 Результаты решения условной задачи разработанным алгоритмом

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

Ниже на рисунках представлены результаты решения тестовой условной задачи (см. п. 2.6.1) - аппроксимация полученного множества Парето. На рисунке 21 жирными точками обозначены недоминируемые решения, а в виде дуг окружностей с центрами в точках, обозначенных ромбиками (нижняя точка - решение безусловной задачи), отображены ограничения. Соответственно на пересечении этих ограничений находится допустимая область решений. И как уже было сказано при описании результатов решения условной задачи методом SPEA (см. п. 2.6), точкой условного минимума, то есть решением рассматриваемой задачи, является нижняя точка криволинейного треугольника - допустимой области.

Слева на рисунке 21 представлены результаты решения условной задачи с помощью метода SPEA после 800-го поколения, когда задача оптимизации решается еще с учетом целевой функции. Справа же - результаты уже после остановки генетического алгоритма, то есть после 1000-го поколения. Эти результаты соответствуют результатам выполнения 2-го основного этапа алгоритма (см. п. 3.2).

а) после 800-го поколения б) после остановки генетического

алгоритма (после 1000-го поколения)

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

На рисунке 21 хорошо видно как недоминируемые точки, полученные после решения задачи с учетом целевой функции (слева) в результате решения задачи без ее учета, то есть, учитывая лишь ограничения, стягиваются в допустимую область, равномерно распределяясь по ней (справа). При этом в итоге после решения задачи методом SPEA по предложенной схеме среди результирующих недоминируемых точек недопустимых точек практически не содержится, о чем уже было сказано ранее.На рисунке 23 слева в виде криволинейного треугольника изображена допустимая область и точки, полученные после выполнения 3-го этапа алгоритма (см. п. 3.3). Справа же представлена часть допустимой области, увеличенная в районе точки условного оптимума. Жирными точками обозначены решения, полученные после “лечения” недопустимых точек, кружками - решения после просмотра 1-соседних точек, крестиками - после просмотра 2-соседних точек и ромбиками - после просмотра 3-соседних точек, которые и являются конечным результатом решения задачи.



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

с помощью паретовского локального поиска

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

Выводы

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

Глава 4 Практическая реализация разработанного алгоритма

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

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

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

4.1 Программная система для решения задач условной многокритериальной оптимизации

Для проведения сравнительного анализа методов многокритериальной оптимизации генетическими алгоритмами (см. п. 2.6) и осуществления проверки эффективности работы разработанного алгоритма (см. гл. 3) была создана программная система, о которой и пойдет речь далее.

4.1.1 Общие сведения

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

Языком реализации программного продукта Mnogokritga является язык программирования C++ с использованием интегрированной среды визуального программирования Borland C++Builder 5 [14]. Благодаря заложенным в нее возможностям при разработке системы использовался объектно-ориентированный подход, при котором вся система представляется как совокупность находящихся во взаимосвязи элементов.

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

Для установки и эксплуатации системы необходим IBM совместимый персональный компьютер в следующей конфигурации:

- процессор Intel Pentium с тактовой частотой не ниже Pentium II 300, рекомендуется Pentium IV с частотой 2,2 ГГц;

- операционная система Microsoft Windows 98/ME/2000/XP;

- оперативная память не менее 64 Мбайт, рекомендуется 512 Мбайт;

- не менее 8 Мбайт свободного пространства на жестком диске;

- мышь и клавиатура для осуществления ввода и изменения данных и параметров алгоритмов в интерактивном режиме;

- дисковод/дисковод для компакт-дисков CD-ROM, чтобы иметь возможность установки программы с дискеты или компакт-диска;

- монитор, поддерживающий разрешение экрана не менее 640x480 пикселов, рекомендуется 1024х768;

- видеокарта с памятью не менее 2 Мбайт, рекомендуется 4 Мбайт.

4.1.2 Функциональная структура

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

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

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

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

Размещено на http://www.allbest.ru/

Размещено на http://www.allbest.ru/

Рисунок 23 - Функциональная схема программной системы

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

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

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

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

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

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

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

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

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

4.1.3 Эксплуатация и применение программной системы

Работа с программной системой довольно проста и не требует особых навыков. После запуска программы Mnogokrit.exe появляется рабочее окно программной системы - пользовательский интерфейс.

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

Таким образом, диалог с пользователем осуществляется посредством интерфейса, представленного в виде окна и показанного на рисунке 24.

Рисунок 24 - Рабочее окно программы

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

Рассмотрим каждый блок по отдельности.

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

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

К специальным можно отнести такие параметры как: давление доминирования (количество индивидов в сравнительном множестве) и радиус ниши (используется для поддержания разнообразия) для метода NPGA (см. п. 2.5.3), а также размер внешнего множества (определяет количество итоговых точек-решений) для метода SPEA (см. п. 2.5.4).

Рисунок 25 - Блок задания параметров алгоритма

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

Рисунок 26 - Блок задания типов селекции, скрещивания и мутации

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

Рисунок 27 - Блок выбора задачи

После задания всех параметров (выполнив все установки) можно осуществлять запуск алгоритма. Для этого необходимо нажать кнопку в соответствующем блоке, показанном на рисунке 28.

Рисунок 28 - Блок запуска алгоритма

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

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

Рисунок 29 - Блок вывода результатов

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

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

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

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

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

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

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

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

Это так называемые Центры финансовой ответственности (ЦФО), которые непосредственно связанны с процессом производства [13].

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

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

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

Меру риска определяют на основании экспертной оценки рискованности каждого отдельного проекта [6].

Для формализованной записи рассматриваемой модели вводятся следующие обозначения [6]:

- плановый годовой объем прибыли, получаемый -м ЦФО от внедрения -го нововведения;

R_ij - экспертная оценка рискованности соответствующего инновационного проекта;

-- плановые годовые затраты финансовых средств -го ЦФО на -е нововведение, способствующее увеличению мощности ЦФО;

-- плановые годовые объемы финансовых средств, выделяемые ЦФО в план нововведений;

--плановый годовой объем финансовых средств, выделяемый центральной компанией в планы нововведений ЦФО;

-- допустимая средняя прибыль на 1 руб. затрат (норма прибыли на капитал);

-- искомый параметр, показывающий, планируется ли к внедрению на -м ЦФО -e нововведение (если , то планируется; если , не планируется).

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

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

; (1)

; (2)

; (3)

; (4)

.

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

4.3 Применение разработанного алгоритма при решении практической задачи

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

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

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

; (5)

; (6)

(7)

(8)

.

Таким образом, теперь нам необходимо решить задачу безусловной оптимизации с булевыми переменными четырех представленных критериев (5) - (8).

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

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

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

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

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

Таблица 2 - Результаты решения практической задачи после 800-го поколения

№ п/п	Решение условной задачи	Значение , млн. руб.	Значение	Значение	Значение
1	2	3	4	5	6
1	1011101111111111111100001	98.95	1.87895	0	0.2025
2	0001100001111011000100001	48	1.5	0	0
3	0011110101111111110100001	87.95	1.8	0	0
4	0001100101111111010100001	69.6	1.67692	0	0
5	0011110101111111000100001	79.7	1.74286	0	0
6	0001100001111111000000001	51.5	1.52	0	0
7	1011101101111111111100001	89.6	1.81111	0	4.41
8	0001100101111111000000001	59	1.59091	0	0
9	0011111101111111010100001	91	1.8125	0	0
10	0011100001111111000000001	54.7	1.54545	0	0
11	0011100001111011000000001	45.2	1.47	0	0
12	0011111101111111110110001	104.65	1.90556	0	0
13	0001100101111111000100001	65	1.63333	0	0
14	1011110111111111110110001	110.8	1.95789	0	0
15	0001100001111111000100001	57.5	1.57273	0	0
16	0011100001111111000100001	60.7	1.59167	0	0
17	1011101101111111110100001	86.65	1.78824	0	0.5625
18	0001101101111111110100001	79.95	1.76	0	0
19	0011111111111111110110001	114	1.96842	0	0
20	0011100101111111000000001	62.2	1.60833	0	0
21	0011100101111111000100001	68.2	1.64615	0	0
22	0011100001111111010100001	65.3	1.63846	0	0
23	1011100101111111110100001	79.95	1.75	0	2.56
24	0011110101111111010100001	84.3	1.77333	0	0
25	1011111101111111110110001	108.15	1.92105	0	0
26	0011101101111111000000001	68.9	1.66923	0	0
27	1011111101111111111110001	111.1	1.935	0	0.9025
28	0011111101111111000100001	86.4	1.78667	0	0
29	0011101101111111110100001	83.15	1.7625	0	0
30	0011111101111111010110001	101	1.88824	0	0
31	0001100001111011000000001	42	1.43333	0	0
32	0011111101111111110100001	94.65	1.83529	0	0
33	0001100001111011000000000	41	1.425	0	0
34	0011100101111111110100001	76.45	1.72	0	0
35	1011111101111111111100001	101.1	1.87368	0	0.9025
36	1011110101111111110100001	91.45	1.82353	0	0.2025
37	1011111111111111110110001	117.5	1.98	0	0
38	1011110101111111110110001	101.45	1.89444	0	0.2025
39	1011111101111111110100001	98.15	1.85556	0	0
40	0011101101111111000100001	74.9	1.7	0	0

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

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

Таблица 3 - Результаты решения практической задачи разработанным алгоритмом

№ п/п	Решение условной задачи	Значение , млн. руб.	Значение	Значение	Значение
1	2	3	4	5	6
1	1011111111111111110110001	117.5	1.98	0	0
2	0011101101111111000000001	68.9	1.66923	0	0
3	0011100001111111010100001	65.3	1.63846	0	0
4	0001100101111111010100001	69.6	1.67692	0	0
5	0011111111111111110110001	114	1.96842	0	0
6	0001100001111011000000001	42	1.43333	0	0
7	0011111101111111110110001	104.65	1.90556	0	0
8	0011100001111111000000001	54.7	1.54545	0	0
9	0011100001111111000100001	60.7	1.59167	0	0
10	0001100101111111000000001	59	1.59091	0	0
11	0011110101111111010100001	84.3	1.77333	0	0
12	0001100001111111000000001	51.5	1.52	0	0
13	0001100101111111000100001	65	1.63333	0	0
14	0011111101111111110100001	94.65	1.83529	0	0
15	0001100001111011000100001	48	1.5	0	0
16	0011110101111111000100001	79.7	1.74286	0	0
17	0001101101111111110100001	79.95	1.76	0	0
18	0011111101111111010100001	91	1.8125	0	0
19	0011101101111111010100001	79.5	1.73333	0	0
20	1011111111111111111100001	110.45	1.935	0	0
21	1011111101111111110100001	98.15	1.85556	0	0
22	0011100101111111010100001	72.8	1.68571	0	0
23	0011100101111111000100001	68.2	1.64615	0	0
24	0011100001111011000000001	45.2	1.47	0	0
25	0001100001111111000100001	57.5	1.57273	0	0
26	0011101101111111000100001	74.9	1.7	0	0
27	0011100101111111000000001	62.2	1.60833	0	0
28	1011111101111111110110001	108.15	1.92105	0	0
29	0011111101111111000100001	86.4	1.78667	0	0
30	0011111101111111010110001	101	1.88824	0	0
31	0011110101111111110100001	87.95	1.8	0	0

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

Выводы

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

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

Заключение

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

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

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

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

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

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

Список использованных источников

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

16. 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.

17. Coello Coello C.A. A comprehensive survey of evolutionary-based multiobjective optimization techniques.

18. 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.

19. 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.

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

21. 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.

22. 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.

23. Zitzler E., Thiele L. Multiobjective evolutionary algorithms: A comparative case study and the strength Pareto approach // IEEE Transactions on Evolutionary Computation, 1999.

Публикации диссертанта:

24. Gumennikova, A.V. Comparative analysis of multiobjective optimization methods by genetic algorithms / A.V. Gumennikova // Красноярский край: освоение, развитие, перспективы: Тез. Докл. Регион. Студ. Науч. Конф. Ч. 1/ Краснояр. Гос. Аграр. Ун-т; Сост. О.Н. Чепалова. - Красноярск, 2003, с. 33-34.

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

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

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

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

29. Семенкин, Е.С. Распределение ресурсов при управлении инновациями реструктурированного предприятия ВПК / Е.С. Семенкин, В.М. Клешков, К.В. Гупалов, А.В. Гуменникова // - Красноярск: СибГАУ, 2004, с. 124-134.

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

31. Гуменникова, А.В. Алгоритм решения многокритериальных задач условной оптимизации / А.В. Гуменникова // Труды 42-й Внутривузовской конференции творческой молодежи, посвященной Всемирному дню авиации и космонавтики 12 апреля. - Красноярск: СибГАУ, 2004.

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

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

Приложение

Числовые данные для задачи принятия решений при управлении инновационными процессами реструктурированного предприятия ВПК

№ п/п	ЦФО	Пij, млн. руб.	Rij	Ci млн. руб.	cij, млн. руб.
	1. ПТНП
(1) 1-1	Производство форточных вентиляторов из УВС	3,5	2,2		2,5
(2) 1-2	Организация совместной деятельности по производству посуды из полимеров	5,0	3,0		3,0
(3) 1-3	Литье под давлением изделий из полимеров	3,2	1,8		4,9
(4) 1-4	Изготовление блоков-приборов и других комплектующих для завода холодильников "Бирюса"	6,2	1,9		8,0
(5) 1-5	Продукция ветеринарного и зоотехнического назначения	4,0	1,2		11,3
(6) 1-6	Производство настенных воздухоочистителей-ионизаторов из УВС	11,5	3,0		25,3
(7) 1-7	Производство из УВС нагревателей воздуха для автокарбюраторов	6,7	2,4		15,1
(8) 1-8	Производство тепловентиляторов из УВС	7,5	2,3		15,5
	Всего по ЦФО 1	47,6	17,8	70,0	85,6
	2. ПЭП
(9) 2-1	Трубы полиэтиленовые с радиационной обработкой	9,4	3,1		22,0
(10) 2-2	Производство профилей из соэкструдированного жесткого и мягкого ПВХ	7,6	1,5		9,8
(11) 2-3	Экструзия полимеров	4,5	1,4		10,8
(12) 2-4	Производство комплектующих для уплотнителей дверей холодильников	6,0	1,2		11,0
(13) 2-5	Утилизация ПЭТ бутылок	4,0	1,5		17,0
(14) 2-6	Производство напольных офисных покрытий	9,5	2,3		12,5
	Всего по ЦФО 2	40,9	11,0	72,0	83,1
	3. Цех 43
(15) 3-1	Организация совметной деятельности по газификации жидкого кислорода	4,3	1,5		10,2
(16) 3-2	Утилизация супертоксикантов	4,5	1,2		17,0
(17) 3-3	Производство сжиженного и газообразного аргона	3,7	2,2		6,8
(18) 3-4	Производство сжиженного и газообразного азота	4,6	2,2		5,3
(19) 3-5	Производство сжиженного и газообразного кислорода	3,0	2,2		3,2
	Всего по ЦФО 3	20,0	9,3	35,0	42,5
	4. ПТПП
(20) 4-1	Производство геополотна	6,0	2,1		13,6
(21) 4-2	Производство тканой полипропиленовой продукции	10,0	3,1		20,0
(22) 4-3	Производство пропиленовых мешков	6,9	3,3		9,1
	Всего по ЦФО 4	22,9	8,5	32,0	42,7
	5. Цех 40
(23) 5-1	Производство дифференциального редуктора	3,0	3,5		3,0
(24) 5-2	Производство электромагнитного инжектора	2,5	4,0		3,5
(25) 5-3	Комплектация ГБО ГИГ	1,0	1,5		0,5
	Всего по ЦФО 5	6,5	9,0	12,0	7,0
	Итого	137,8	55,6	221,0	260,9

Размещено на Allbest.rue