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

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

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

РАЗРАБОТКА И ИССЛЕДОВАНИЕ

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

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

Содердание

Введение

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

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

1.1.1 Формулировка задачи векторной оптимизации

1.1.2 Парето-оптимальность

1.1.3 Концепция доминирования по Парето

1.1.4 Множество и фронт Парето

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

критерием

1.2.1 Метод последовательных уступок

1.2.2 Метод выделения основного частного критерия

1.2.3 Свертка критериев

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

1.4 Выводы

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

2.1 Решение многокритериальной задачи с помощью

генетических алгоритмов

2.1.1 Основные принципы эволюционной теории

2.1.2 Общий эволюционный алгоритм

2.2 Подходы к назначению пригодности и селекции

2.3 Поддержание разнообразия популяции

2.4 Элитизм

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

алгоритмами

2.5.1 Метод VEGA (Vector Evaluated Genetic Algorithm)

2.5.2 Метод FFGA (Fonseca and Fleming's Multiobjective Genetic

Algorithm)

2.5.3 Метод NPGA (Niched Pareto Genetic Algorithm)

2.5.4 Метод SPEA (Strength Pareto Evolutionary Algorithm)

2.6 Сравнительный анализ методов многокритериальной

оптимизации генетическими алгоритмами

2.6.1 Тестовые задачи

2.6.2 Параметры алгоритмов

2.6.3 Результаты решения тестовых задач методами VEGA,

FFGA, NPGA и SPEA

2.7 Выводы

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

3.1 Сведение условной задачи к безусловной

многокритериальной задаче

3.2 Решение условной задачи методом SPEA

3.3 Лечение точек-решений локальным поиском

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

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

алгоритмом

3.6 Выводы

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

алгоритма

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

многокритериальной оптимизации

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

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

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

4.2 Задача принятия решений при управлении инновационными

процессами реструктурированного предприятия ВПК

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

Выводы

Заключение

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

Приложение

Введение

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

Апробация работы. Результаты работы докладывались и обсуждались на следующих конференциях:

- Всероссийская научно-практическая конференция "Решетневские чтения" (г. Красноярск, Сибирский государственный аэрокосмический университет, 2002 г.);

- Региональная конференция «Красноярский край - освоение, развитие, перспективы» (2003 г.);

- 41-я Внутривузовская конференция творческой молодежи, посвященная Всемирному дню авиации и космонавтики (г. Красноярск, Сибирский государственный аэрокосмический университет, 2003 г.);

- 4-ая Международная конференция молодых ученых и студентов «Актуальные проблемы современной науки» (г. Самара, 2003 г.);

- XI туполевские чтения: Всероссийская (с международным участием) молодежная научная конференция (г. Казань, 2003 г.);

- XVII Краевая научная студенческая конференция по математике (г. Красноярск, Красноярский государственный университет, 2004 г.);

- 42-я Внутривузовская конференция творческой молодежи, посвященная Всемирному дню авиации и космонавтики 12 апреля (г. Красноярск, Сибирский государственный аэрокосмический университет, 2004 г.);

- VIII Международная научно-практическая конференция «Системный анализ в проектировании и управлении» (г. Санкт-Петербург, 2004 г.).

Публикации. Основные положения и результаты диссертации опубликованы в 10 работах, список которых указан в диссертации в конце списка использованных источников.

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

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

Разработка методов и моделей принятия решений является важной и актуальной проблемой. Математическая теория и общая методология принятия решений относится к наиболее интенсивно развивающимся в настоящее время направлениям системного анализа [4].

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

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

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

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

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

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

Понятие «решение многокритериальной задачи» в известной мере субъективно и зависит от шкалы ценностей ЛПР, который не только принимает решение, но и готов нести ответственность за его последствия. Формально любая концепция выбора описывается функцией выбора. Поэтому можно связывать многокритериальную оптимизацию не с предпочтением ЛПР, а с функцией выбора на допустимом множестве значений векторного критерия [15].

1.1.1 Формулировка задачи векторной оптимизации

Многокритериальная оптимизация, также известная как векторная оптимизация, может быть определена как задача нахождения вектора переменных-решений, которые удовлетворяют ограничениям и доставляют оптимум вектор-функции, чьи элементы представляют собой целевые функции. Эти функции формируют математическое описание представления критериев, которые обычно находятся в конфликте друг с другом. Поэтому термин «оптимизировать» означает нахождение такого рода решения, которое бы давало значения всех целевых функций, приемлемых для ЛПР [17].

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

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

,

 - вектор решений, удовлетворяющий ограничениям ,

- вектор целевых функций.

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

Помимо самой постановки задачи многокритериальной оптимизации необходимо также ввести еще ряд определений и понятий, характерных для теории решения многокритериальных задач [11, 16, 17, 23].

Допустимое множество определяется как множество векторов-решений , которые удовлетворяют ограничениям :

.

Тогда допустимая область в пространстве целей - образ , обозначается через

.

1.1.2 Парето-оптимальность

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

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

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

1.1.3 Концепция доминирования по Парето

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

1. Решение доминирует решение : , если .

2. Решение слабо доминирует решение : , если .

3. Решения и несравнимы: , если .

Таким образом, если недоминируем относительно , то он называется Парето-оптимальным, т.е. если не существует , то x является Парето-оптимальным.

При этом вектор , называется недоминируемым относительно некоторого множества , если не существует .

1.1.4 Множество и фронт Парето

Множество всех эффективных точек называется множеством Парето в пространстве переменных (альтернатив), а их образ в критериальном пространстве - фронтом Парето.

С точки зрения концепции Парето-доминирования получаем следующую формулировку этого определения.

Функция дает множество недоминируемых решений в , : ={- недоминируем относительно }. Тогда множество назовем недоминируемым множеством относительно , а соответствующее множество целевых векторов - недоминируемым фронтом относительно .

Множество называется Парето-оптимальным множеством, а множество определяет Парето-оптимальный фронт.

Таким образом, имея множество Парето можно построить фронт Парето.

Из всего вышесказанного можно сделать следующий вывод.

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

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

С точки зрения математики решения из множества Парето не могут быть предпочтены друг другу, поэтому после формирования множества Парето задача может считаться математически решенной [11].

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

Очень многие задачи принятия решений могут быть сформулированы как задачи выбора единственной наилучшей в каком-либо смысле альтернативы из допустимого множества. Если качество или полезность альтернатив измеряются с помощью известной скалярной функции, то методологических проблем не возникает, и возможны лишь вычислительные трудности, связанные с необходимостью решения соответствующей экстремальной задачи. Совсем по-другому обстоит дело с многокритериальными задачами. Здесь центр тяжести безусловно смещен в сторону определения - а что же следует считать наилучшей альтернативой в задаче с несколькими целевыми функциями, которые противоречивы и достигают оптимума в различны точках множества альтернатив [3]?

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

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

1. Ранжирование частных критериев по важности (приоритетности) и их последовательное применение.

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

3. Построение обобщенного критерия в форме свертки частных критериев.

Рассмотрим основные особенности этих подходов, приводимые в большинстве литературы по теории многокритериального выбора [2-5, 8-11, 15].

1.2.1 Метод последовательных уступок

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

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

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

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

Недостатками подхода является то, что величины уступок не соизмеримы друг с другом (что исключительно затрудняет их выбор), и то, что в общем случае могут быть получены точки, не являющиеся Парето-оптимальными [11].

1.2.2 Метод выделения основного частного критерия

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

Этот метод (также его называют дискриминационным [11]) состоит в том, что исходная многокритериальная задача сводится к задаче оптимизации по одному частному критерию, который объявляется основным, или главным, при условии, что значения остальных частных критериев должны быть не меньше некоторых установленных величин («требуемых» значений). Выделение одного критерия в качестве основного и назначение пороговых величин для остальных частных критериев фактически означает, что все решения разбиваются на два класса. К одному относятся решения, которые удовлетворяют ограничениям; такие решения можно назвать допустимыми. К другому классу относятся такие решения, которые не удовлетворяют хотя бы одному ограничению. Наконец, среди допустимых решений предпочтительнее считается то, для которого значение основного критерия больше (в случае задачи минимизации - меньше). Метод последовательных уступок формально можно рассматривать как особую разновидность метода выделения основного частного критерия, отличающуюся наличием специфической процедуры назначения величин ограничений для задачи максимизации (минимизации) остальных частных критериев [10].

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

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

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

1.2.3 Свертка критериев

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

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

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

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

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

Суммируя сказанное можно сделать следующий вывод. Метод сверток применялся и применяется наиболее часто, но имеет труднопреодолимые недостатки [11, 17]:

- не всегда потеря качества по одному критерию компенсируется приращением по другому. «Оптимальное» по свертке решение может характеризоваться низким качеством некоторых частных критериев и в связи с этим будет неприемлемым;

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

- результат сильно зависит от предпочтений ЛПР, который чаще всего назначает веса, исходя из интуитивного представления о сравнительной важности критериев;

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

- многократный запуск алгоритма по свертке может давать только несколько различных точек Парето (или одну и ту же) даже в случае, когда в действительности этих точек очень много;

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

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

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

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

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

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

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

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

Выводы

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

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

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

алгоритм оптимизация многокритериальный

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

Термин эволюционные алгоритмы принято относить к числу стохастических поисковых и оптимизационных методов, моделирующих процессы естественной эволюции [17, 23]. Генетические алгоритмы, впервые преложенные Холландом [19], принадлежат к классу эволюционных алгоритмов и обладают рядом характеристик, делающих их более предпочтительными, чем классические методы оптимизации [16]:

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

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

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

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

2.1 Решение многокритериальной задачи с помощью генетических алгоритмов

Со времен первой основополагающей работы Розенберга конца 60-х годов прошлого столетия, касающейся возможности использования поиска, основанного на генетических алгоритмах, применительно к множеству целевых функций, эта область исследований (сейчас также известная как эволюционная многокритериальная оптимизация) значительно разрослась. На это указывает значительное увеличение (главным образом за последние 15 лет) технических статей в специализированных журналах, специальных секций на международных конференциях и исследователей, интересующихся данным вопросом в Интернете [17]. Но стоит отметить, что наиболее бурно разработки в сфере многокритериальной оптимизации генетическими алгоритмами ведутся за рубежом, вследствие чего большая часть работ не доходит до российских специалистов, а о достижениях в этой области можно судить лишь по немногочисленным зарубежным (в основном англоязычным) публикациям, которые распространяются преимущественно посредством сети Интернет [16, 17, 18, 19, 21, 22, 23].

2.1.1 Основные принципы эволюционной теории

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

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

Следовательно, эволюция -- это процесс постоянной оптимизации биологических видов. Естественный отбор гарантирует, что наиболее приспособленные особи дадут достаточно большое потомство, а благодаря генетическому наследованию мы можем быть уверены, что часть этого потомства не только сохранит высокую приспособленность родителей, но будет обладать и некоторыми новыми свойствами. Если эти новые свойства окажутся полезными, то с большой вероятностью они перейдут и в следующее поколение. Таким образом, происходит накопление полезных качеств и постепенное повышение приспособляемости биологического вида в целом. В результате смены поколений, в конце концов, вырабатывается такое решение поставленной задачи, которое уже не может быть далее улучшено. Зная, как решается задача оптимизации видов в природе, исследователи стали применять похожий метод для решения различных реальных задач [12].

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

В процессе селекции, который может быть как стохастическим, так и детерминированным, худшие решения - неприспособленные индивиды - удаляются из популяции, в то время как индивиды с большей пригодностью - наиболее приспособленные - подвергаются репродукции. Цель состоит в том, чтобы усилить поиск в определенных областях поискового пространства и увеличить среднее «качество» внутри популяции. Качество индивида при решении задачи оптимизации определяется скалярным значением, так называемой пригодностью. Заметим при этом, что, так как качество индивида определяется на основании значений целевых функций, прежде чем вычислить его пригодность, предварительно индивид должен быть декодирован, получен его фенотип. Эта ситуация показана на рисунке 1: первоначально имеем индивида (генотип), далее, используя декодирующий алгоритм, с помощью функции из извлекается вектор-решение (фенотип); применяя к получается соответствующий целевой вектор, на основе которого назначается пригодность индивида .

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

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

Рисунок 1 - Взаимосвязь между пространством индивидов,

пространством решений и критериальным пространством

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

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

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

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

- скрещивание - операция, при которой две хромосомы обмениваются своими частями;

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

- приспособленность индивида - значение целевой функции на этом индивиде (его фенотипе);

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

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

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

Стоит также отметить еще 2 механизма, применение которых в генетических алгоритмах играет большую роль - это «разработка» (exploitation) и «исследование» (exploration) [16]. «Разработка» обеспечивает нахождение оптимального решения вблизи элитарного (лучшего) решения. А посредством «исследования» оптимальное решение может быть найдено в любой части поискового пространства. В однокритериальной оптимизации генетическими алгоритмами «исследование» осуществляется на ранних стадиях поиска, а «разработка» - на поздних. Иначе обстоит дело в генетических алгоритмах, применяемых при многокритериальной оптимизации. Здесь и механизм «исследования», и механизм «разработки» должны быть представлены в течение всей процедуры поиска.

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

«Исследование» - процесс просмотра абсолютно новых регионов пространства поиска, чтобы обнаружить возможные многообещающее области. В отличие от механизма «разработки», «исследование» подразумевает скачки в неизвестные регионы поискового пространства. Примером использования механизма «исследования» может служить случайный поиск. Задачи с множеством локальных оптимумов иногда могут быть решены только с применением механизма «исследования» в виде локального поиска. В генетических алгоритмах в качестве механизма «исследования» используется мутация [16].

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

2.1.2 Общий эволюционный алгоритм

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

Схема общего эволюционного алгоритма выглядит следующим образом [23]:

Вход: (размер популяции),

(максимальное число поколений),

(вероятность скрещивания),

(степень (вероятность) мутации).

Выход: (недоминируемое множество).

1 этап) инициализация:

положить =0 (начальная популяция),

= 0 () и для выполнять следующее:

а) выбрать индивида ,

б) добавить индивида к множеству

=+.

2 этап) назначение пригодности:

для каждого индивида определить закодированный вектор

и вектор целей

, вычислить скалярное значение

пригодности .

3 этап) селекция:

положить =0 и для

выполнять следующее:

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

б) добавить индивида к множеству

=+ (промежуточное множество).

4 этап) рекомбинация (скрещивание):

положить =0 и для

выполнять следующее:

а) выбрать двух индивидов и удалить их из ,

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

в) добавить к индивидов и с вероятностью или индивидов и с вероятностью

(1-). =+ или =+.

5 этап) мутация:

положить=0 и для каждого выполнить следующее:

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

б) добавить индивида к множеству

=+.

6 этап) останов (окончание):

Положить

и ,

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

, иначе перейти на 2 этап.

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

При этом отличие всех методов многокритериальной оптимизации генетическими алгоритмами состоит в модификации этапов назначения пригодности (2 этап) и селекции (3 этап).

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

Далее рассматриваются основные подходы к назначению пригодности и селекции (п. 2.2), способы, которыми обеспечивается разнообразие популяции (п. 2.3), а также конкретные алгоритмы, реализующие некоторые из них (п. 2.5).

2.2 Подходы к назначению пригодности и селекции

Различают эволюционные алгоритмы многокритериальной оптимизации [23], 1) где целевые функции рассматриваются по отдельности, 2) подходы, базирующиеся на классических методах построения обобщенного критерия и 3) методы, которые непосредственно используют концепцию доминирования по Парето.

1. Селекция по переключающимся целевым функциям

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