Содержание к диссертации
Введение
Глава 1. Классическая задача о ранце в однокритериальной и многокритериальной постановках. алгоритмы решения 10
1.1. Классическая задача о ранце и алгоритмы поиска точного решения 10
1.2. Многомерная задача о ранце 26
1.3. Алгоритмы синтеза Парето-оптимальных решений для многокритериальной задачи о ранце на основе принципа динамического программирования 36
1.4. Синтез полной совокупности эффективных оценок многокритериальной задачи о ранце методом ветвей и границ 43
Глава 2. Синтез представительных совокупностей эффективных оценок для многокритериальной задачи о ранце 53
2.1. Концепция оператора, строящего представительную совокупность. Понятие консервативного оператора 54
2.2. Алгоритм синтеза совокупностей эффективных оценок, удовлетворяющих пороговым ограничениям 56
2.3. Синтез -разреженных совокупностей эффективных оценок 57
2.4. Алгоритмы построения совокупностей эффективных оценок получаемых применениями типовых схем компромисса при варьируемых параметрах этих схем 58
2.4.1. Метод последовательных уступок 58
2.4.2. Линейная свертка критериев 59
2.4.3. Метод главного критерия 61
2.4.4. Метод идеальной точки 62
2.5. Результаты вычислительных экспериментов 64
Глава 3. Подходы к ускорению счета при поиске решений многокритериальной задачи о ранце 69
3.1. Эффективные оценки. Синтез совокупностей - эффективных оценок методом ветвей и границ 69
3.2. Применение эволюционно-генетических алгоритмов для получения эвристических решений 72
3.3. Комбинированные алгоритмы решения задач о ранце 81
3.4. Некоторые вопросы эффективности программной реализации сложных вычислительных алгоритмов 85
Глава 4. Некоторые модификации задачи о ранце и методы их решения 89
4.1. Задача о ранце с аддитивным и точечным критериями 89
4.1.1. Математическая постановка задачи и алгоритмы ее точного решения.. 89
4.1.2. Эволюционно-генетический алгоритм решения задачи 94
4.2. Задачи с несколькими ранцами 97
4.2.1. Математические постановки задач с несколькими ранцами и алгоритмы их точного решения 97
4.3.2. Эволюционно-генетические алгоритмы решения задач 105
Глава 5. Об одной задаче выбора ограниченного представительного подмножества объектов 108
5.1. Математическая модель задачи и ее интерпретация. Алгоритм поиска точного решения 108
5.2. Эвристические алгоритмы поиска решения 111
Заключение 118
Литература 120
Приложение
- Алгоритмы синтеза Парето-оптимальных решений для многокритериальной задачи о ранце на основе принципа динамического программирования
- Алгоритм синтеза совокупностей эффективных оценок, удовлетворяющих пороговым ограничениям
- Применение эволюционно-генетических алгоритмов для получения эвристических решений
- Математические постановки задач с несколькими ранцами и алгоритмы их точного решения
Введение к работе
Классическая задача о ранце (КЗР) относится к числу широко известных задач дискретной оптимизации. Данная задача впервые была сформулирована Д. Данцигом в работе [120] и с тех пор активно исследуется. Популярность КЗР вызвана большим количеством ее приложений, поскольку многие из реально возникающих задач описываются в рамках данной модели. Основные сферы применения находятся в областях планирования и управления производственными и транспортными системами. В частности, отметим формулируемые в рамках КЗР задачи объемного планирования.
Историческую хронологию этапов изучения КЗР и наиболее важные результаты данных исследований можно представить следующим образом.
1950 гг. - Постановка КЗР; алгоритм решения, использующий принцип динамического программирования (R. Bellman, G. Dantzig- [16, 17,25, 120]).
1960 гг. — Первый алгоритм решения КЗР, основанный на методе ветвей и границ; совершенствование алгоритмов использующих принцип динамического программирования (G. Dantzig, А.Н. Land и A.G. Doig, P. Gilmore, R. Gomory, P.J. Kolesar- [25, 120, 141]).
1970 гг. — Исследование вычислительной сложности КЗР, доказательство ее NP-трудности, выделение частных полиномиально разрешимых подклассов. Разработка нескольких приближенных методов решения КЗР, имеющих полиномиальные оценки вычислительной сложности. Применение двойственности для повышения эффективности метода ветвей и границ. Изложенные результаты описаны в работах О.Г. Алексеева, В.А. Емеличева, Ю.Ю. Финкельштейна, М. Garey и D. Johnson, O.Ibarra и С. Kim, С. Ра-padimitriou и К. Steiglitz, S. Sahni - [1,24,29,46,47,67, 92-95, 135, 154].
1980 гг. - Выделение новых полиномиально разрешимых подклассов КЗР; доказательство ряда важных свойств; введение понятий «ядро» и «расширяющееся ядро» и построение приближенных схем решения, основанных на этих понятиях. Разработка комбинированных подходов к решению КЗР, сочетающих применение комбинаторных методов (динамическое программирование или метод ветвей и границ) с приближенными и эвристическими алгоритмами. Полученные результаты отражены в публикациях В.А. Емеличева, И.В. Сергиенко, И.Х. Сигала, Е. Balas, T.Hu, S. Martello, D. Pisinger, P. Toth, E. Zemel - [79, 80,98, 108, 147].
1990 гг. - Применение эвристических алгоритмов, нейронных сетей, параллельных алгоритмов, эволюционно-генетического подхода к решению ранцевых задач. Достигнутые результаты изложены А.А. Корбут, И. X. Сигалом, S. Khuri, W. Loots, Z. Michaleviwicz, M. Ohlsson, С. Peterson, D. Pisinger, T.H.C. Smith- [27, 82, 137, 138, 146, 148,150-153].
2000 гг. - Новые оценки трудоемкости метода ветвей и границ; параллельные реализации методов ветвей и границ и динамического программирования; комбиниро ванный параллельный алгоритм решения КЗР. Описанные результаты получены P.M. Колпаковым, М.А. Посыпкиным, И.Х Сигалом [35-38, 74-76].
Начиная с 60-70-х гг. XX века стали рассматриваться различные модификации КЗР. В частности, была изучена КЗР с дробимыми предметами (решающий алгоритм разработан Д. Данцигом [25, 120]) и КЗР в многомерной постановке (см., например [47]). Последняя математическая модель, в отличие от КЗР, позволяет учитывать для каждого из предметов несколько ограничивающих его факторов. Присутствие такой возможности позволяет описать в рамках многомерной КЗР множество прикладных задач, которые было невозможно адекватно выразить в рамках математической постановки КЗР. К примеру, в задачах объемного планирования, когда трудоемкость производственных задач оценивается по видам или группам работ. Таким образом, оценивая трудоемкость вектором, получаем многомерную КЗР. Фонд рабочего времени и ресурсов также представлен вектором.
Одновременно с этим, исследуется КЗР, где требование булевозначности переменных заменено требованием принадлежности их некоторому множеству неотрицательных целых чисел в ограниченном.диапазоне. Вообще говоря, некоторые авторы (см. например [98, 102]) под КЗР понимают задачу с неотрицательными целочисленными переменными. Также встречаются постановки КЗР с нелинейными критериями, в частности Д.И. Батищев и Д.И. Коган в своей работе [7] рассматривают задачу о ранце с се-парабельным критерием.
Последнее десятилетие значительное внимание уделяется ранцевым задачам в многокритериальных постановках. Данное обстоятельство вызвано стремлением более адекватно описать возникающие на практике ситуации. Зачастую многие реальные задачи оценивают принимаемое решение по нескольким показателям, а критерии, по которым оценивается решение, не всегда выражаются аддитивными функциями. Можно утверждать, что все задачи, реально возникающие в экономических системах по сути своей многокритериальны. Это объективно связано с тем, что в каждой экономической системе имеется ряд участников, каждый из которых по-своему оценивает качество принимаемых решений. Кроме того, некоторые участники могут оценивать принимаемые решения по нескольким показателям. Задачей о ранце в многокритериальной постановке занимаются Д.И. Батищев, В.А. Емеличев, А.П. Иванова, Д.И. Коган, М.В. Лейкин, И.И. Меламед, И.Х. Сигал, J.R. Figueira, М.Н. Karwan, K.Klamroth, J. Teghem, L. Thiele, E.L. Ulungu, B. Villarreal, M. Wiecek, E. Zitzler и др. Основные результаты, полученные данными учеными, представлены в работах [6, 8-12, 14, 15, 30-32, 40, 41, 43, 51-59,64,65, 83, 84, 125,139,160-162,166-168].
Несмотря на внешнюю простоту математической модели, вычислительную сложность задачи о ранце характеризует результат об ее NP-трудности уже в одномерном однокритериальном случае [24]. Наличие каждого дополнительного факта, вносимого в данную модель, значительно увеличивает трудоемкость решающих ее алгоритмов.
Известны два регулярных метода решения задач о ранце (в том числе многомерных многокритериальных) - принцип динамического программирования [5, 10, 16, 17, 40, 59, 139, 161] и схема ветвей и границ [43, 47, 82, 141, 160, 162]. Каждый из них до пускает несколько реализаций и обладает своими достоинствами и недостатками; вместе с тем, оба они достаточно гибки и универсальны.
В настоящее время для поиска решения задач дискретной многокритериальной оптимизации используются два основных подхода.
Первый подход заключается в привлечении имеющейся у лица, принимающего решение (ЛПР), дополнительной информации и назначении одной из типовых схем компромисса. Реализация каждой из таких схем сводит решение исходной многокритериальной задачи к решению одной или нескольких специальным образом построенных однокритериальных задач. Основное преимущество данного подхода заключается в возможности использования большого набора хорошо изученных методов однокритери-альной оптимизации. Среди наиболее часто применяемых схем компромисса отметим метод последовательных уступок, аддитивную свертку критериев, метод главного критерия и метод идеальной точки. Каждая из схем имеет свои особенности и специфику применения. Данный подход не лишен недостатков, поскольку у ЛПР, не всегда хватает дополнительной информации, чтобы определиться в выборе наиболее целесообразной схемы компромисса и определить необходимые для ее реализации параметры. Кроме того, однокритериальные задачи, получаемые в результате применения некоторых схем компромисса, оказываются достаточно сложными.
Второй подход базируется на принятии концепции эффективной оценки и Паре-то-оптимального решения [73, 110]. В данном случае, технология решения многокритериальной задачи заключается в построение для нее полной совокупности эффективных оценок с одновременным обеспечением возможности восстановления по любой эффективной оценке Парето-оптимального решения ее порождающего. Данная совокупность позволяет ЛПР составить полное представление о задаче и выбрать любое целесообразное для него решение. С другой стороны, полная совокупность может быть достаточно велика, а ее синтез, как правило, требует больших вычислительных затрат.
В связи с этим, возникает вопрос построения частных, удовлетворяющих определенным условиям подмножеств эффективных оценок без предварительного построения полной совокупности. В качестве частных (представительных) подмножеств могут выступать либо разреженная в том или ином смысле совокупность эффективных оценок, либо совокупность, удовлетворяющая заданным пороговым ограничениям, либо совокупность, удовлетворяющая одной из типовых схем компромисса при варьируемых параметрах этой схемы. В реальных условиях ЛПР достаточно сложно зафиксировать параметры определенной схемы компромисса, намного проще назначить диапазон их изменения. Таким образом, варьируя параметры выбранной схемы в заданном диапазоне, мы получим частное подмножество эффективных оценок. Следует отметить, что схемы компромисса должны так реализоваться, чтобы давать Парето-оптимальные решения.
В жизни, при предъявлении полной совокупности эффективных оценок, ЛПР, как правило, выбирает некоторую его часть, используя собственные дополнительные соображения. Аналогичная идея используется в динамическом программировании при синтезе представительных совокупностей эффективных оценок. Реализована данная идея через концепцию оператора выбора; результативность данного оператора возможна только при условии его консервативности (см. например, [10,40]). Альтернативный подход решения задач дискретной многокритериальной оптимизации основывается на использовании приближенных алгоритмов решения задачи, основным критерием эффективности которых, служит точность и полнота полученных решений. В настоящее время все большую популярность приобретают эволюционно-генетические алгоритмы (ЭГА) - алгоритмы случайного поиска, имитирующие в своей работе процесс эволюции популяции особей [13,23, 127, 129]. Также, в данный момент, вызывают большой интерес алгоритмы муравьиных колоний [2, 104, 122, 123].
Широкими возможностями по ускорению поиска точного решения задач дискретной оптимизации обладает комбинированный подход. Основная идея данного подхода заключается в комбинировании эвристических и точных алгоритмов решения — эвристические алгоритмы служат для достаточно быстрой генерации предварительных (приближенно-оптимальных) решений; полученные таким образом решения используются для ускорения счета процедур поиска точного решения. Наиболее удачной видится комбинирование эвристических алгоритмов с методом ветвей и границ.
Отдельное направление исследований формируют вопросы эффективной реализации вычислительных алгоритмов на ЭВМ. Конечной стадией разработки любого алгоритма является его программная реализация с целью применения в автоматизированных системах принятия решений. Вычислительная среда (аппаратная архитектура, операционная система, компилятор и т.д.) обладает своими особенностями, что не может не повлиять на работу алгоритма. Так же сюда можно отнести современные технологии параллельной реализации вычислительных алгоритмов на многопроцессорных системах (см., например [19]).
Данная диссертационная работа посвящена рассмотрению многокритериальных задач ранцевого типа, разработке и сравнительному анализу решающих алгоритмов. Проверка эффективности предложенных алгоритмов на практике осуществлена выполненной серией вычислительных экспериментов.
Актуальность исследования вызвана широкой распространенностью многокритериальных задач ранцевого типа и важностью их прикладного значения.
Диссертационная работа состроит из введения, пяти глав, списка использованных литературных источников, заключения и одного приложения.
Первая глава посвящена классической задаче о ранце, ее многомерной и многокритериальной модификациям. Детально исследуются алгоритмы поиска точных решений и вопросы их вычислительной сложности.
В разделе 1.1 приводятся математическая постановка классической задачи о ранце и алгоритмы ее решения, основанные на принципе динамического программирования и на схеме ветвей и границ. В раздел 1.2 излагаются модификации описанных выше алгоритмов в применении к многомерной задаче о ранце. В разделе 1.3 вводится многокритериальная задача о ранце; дан обзор основных подходов к решению задач дискретной многокритериальной оптимизации; приводится описание схем решения многокритериальной задачи о ранце, основанных на многокритериальном аналоге принципа динамического программирования. В разделе 1.4 излагаются общая схема адаптации метода ветвей и границ для решения многокритериальных задач дискретной оптимизации и конкретизация данной схемы в применении к многокритериальной задаче о ранце. Вопросы вычислительной сложности рассматриваются по мере описания алгоритмов. Программная система, решающая бикритериальные задачи о ранце, прошла апробацию во ФГУП «ФНГЩ НИИИС им. Ю.Е. Седакова» при решении задач размещения компонентов интегральных схем, возникающих при проектировании больших интегральных схем на базовых матричных кристаллах с аналоговой частью (имеется акт об использовании).
Во второй главе изучаются вопросы синтеза представительных совокупностей эффективных оценок для многокритериальной задачи о ранце.
В разделе 2.1 рассматриваются особенности построения представительных подмножеств эффективных оценок методами, реализующими принцип многокритериального динамического программирования. Вводится понятие оператора, строящего представительную совокупность, а также концепция консервативного оператора. Излагается ряд полученных ранее результатов о консервативности и не консервативности некоторых конкретных операторов выбора. Разделы 2.2 - 2.4 посвящены изложению методов синтеза представительных совокупностей эффективных оценок для многокритериальной многомерной задачи о ранце; указанные методы являются модификациями рассмотренного в разделе 1.4 алгоритма ветвей и границ. Уделяется внимание построению представительных совокупностей эффективных оценок в случае, когда это невозможно применением принципа многокритериального динамического программирования (оператор выбора является неконсервативным). Данный факт является несомненным преимуществом схемы ветвей и границ перед принципом динамического программирования.
В третьей главе предлагается несколько подходов к сокращению и ускорению вычислений при поиске решения многокритериальной задачи о ранце.
В разделе 3.1 излагаются процедуры адаптации метода ветвей и границ для синтеза приближенных решений многокритериальной задачи о ранце с заданной точностью. Раздел 3.2 посвящен применению эволюционно-генетических алгоритмов для получения эвристических решений. Произведен обзор имеющихся технологий и подходов. Предложены собственные реализации эволюционно-генетических алгоритмов учитывающие специфику задачи и преодолевающие недостатки существующих подходов. Раздел 3.3 содержит описание комбинированных алгоритмов решения задач о ранце. Рассмотрены варианты комбинирования метода ветвей и границ и эволюционно-генетических алгоритмов для ускорения поиска точного решения задач о ранце; дана экспериментальная оценка ускорения от применения данного подхода. В разделе 3.4 рассматриваются некоторые вопросы эффективности программной реализации сложных вычислительных алгоритмов на ЭВМ.
Четвертая глава описывает некоторые модификации задачи о ранце и методы их решения. Возникающие прикладные проблемы достаточно часто требуют тех либо иных обобщений стандартной ранцевой модели, а также наложения некоторых дополнительных условий. Важным направлением для обобщений является введение точечного критерия или моделей с несколькими ранцами. В рамках моделей задач с несколькими ранцами естественно и адекватно формулируется ряд задач объемно-календарного планирования, в рамках постановки задачи о ранце с аддитивным и точечным критериями -задача оптимальной загрузки транспортных средств.
В разделе 4.1 вводится математическая постановка задачи о ранце с аддитивным и точечным критериями. Излагаются решающие процедуры поиска точных решений, ос нованные как на принципе динамического программирования, так и на схеме ветвей и границ. В качестве эвристического алгоритма описывается конкретная реализация ЭГА. Рассматривается прикладная задача оптимальной загрузки судов, адекватно формализуемая в рамках построенной модели. Разработанные алгоритмы и реализованная на их основе программная система используются в ОАО «АЗИМУТ» для решения задач планирования транспортно-технологических процессов на внутреннем водном транспорте (имеется акт о внедрении).
Раздел 4.2 посвящен двум постановкам задачи с несколькими ранцами. Приводятся алгоритмы поиска точных решений. Предлагаемые решающие процедуры основаны на принципе многокритериального динамического программирования (его списковой реализации). Описывается возможность дополнительного использования верхних и нижних оценок для сокращения объема выполняемых вычислений. Рассматриваются основанные на ЭГА эвристические процедуры решения поставленных задач.
В пятой главе рассматривается актуальная в экономических приложениях задача выбора ограниченного представительного подмножества объектов. Вводится математическая модель задачи, предлагаются два подхода к ее решению.
В разделе 5.1 приводится математическая постановка задачи и одна из ее интерпретация. Излагается адаптация ранее представленного алгоритма решения КЗР для поиска точного решения описанной задачи. Раздел 5.2 посвящен рассмотрению эвристических алгоритмов, реализующих второй подход к решению поставленной задачи. Предложенные алгоритмы основаны на сведении исходной задачи к специальным образом построенной многомерной задаче о ранце и ее решении ранее описанными методами. В качестве альтернативы излагается эволюционно-генетический алгоритм поиска решений. Каждый из представленных алгоритмов программно реализован и прошел тестирование на реальных задачах. В частности, результаты проведенных исследований нашли применение в ЗАО "Бизнес Аналитика", г. Москва. На данном основании имеется акт о внедрении научно-технической разработки.
Представленные в основном тексте алгоритмы имеют программную реализацию. Все разделы сопровождаются результатами вычислительных экспериментов. Программно-аппаратным средствам и условиям проведения вычислительных экспериментов посвящено приложение к диссертационной работе.
Основные результаты, полученные в ходе работы над диссертацией, изложены в одиннадцати публикациях [42-45, 78, 86-91, 124], в том числе восемь из них в центральной печати [43, 45, 86-91], четыре в материалах и тезисах докладов на международных [44,78, 124] и российских конференциях [42].
Алгоритмы синтеза Парето-оптимальных решений для многокритериальной задачи о ранце на основе принципа динамического программирования
Для задачи (1.1.1)-(1.1.3) общепринята следующая интерпретация. Имеется совокупность предметов П1?...,П,;; каждый предмет Пу характеризуется стоимостью Cj и весом «у, J = 1,п. Предметы считаются недробимыми, т.е. любой из предметов может быть помещен в ранец только целиком. Необходимо максимизировать суммарную стоимость помещенных в ранец предметов, при условии, что суммарный вес предметов в ранце не может превосходить значение заданной константы Ъ.
В решении, определяемом вектором X = (xi,x2,...,x„) с булевозначными координатами предмет П і кладется в ранец тогда и только тогда, когда х ,=\. Ограничение (1.1.2) именуется весовым ограничением. Считается, что суммарный вес всех предметов не превосходит величину Ь, т.е. выполняется неравенство cij b. Задачу (1.1.1) (1.1.3) далее будем именовать задачей Z.
Существует два стандартных подхода к решению классической задачи о ранце -принцип динамического программирования [5, 16, 17, 40] и схема ветвей и границ [47, 83, 136, 141]. В основу метода динамического программирования положен принцип оптимальности, сформулированный Р.Беллманом [16]. Этот принцип устанавливает, что часть оптимальной траектории от любого ее состояния л до конца траектории, сама является оптимальной траекторией с началом в состоянии х. Практически метод динамического программирования как правило реализуется с помощью некоторой системы рекуррентных соотношений. Реализация схемы ветвей и границ заключается в построении дерева вариантов решений, при этом считаются определенными процедуры вычисления верхних и нижних оценок в вершинах дерева, а также процедуры ветвления и отсева бесперспективных направлений. Сначала изложим метод ветвей и границ. Метод ветвей и границ
Дерево вариантов для задачи Z - это дерево, каждое ребро которого фиксирует значение какой-либо переменной; любой путь от начальной вершины (корня) к конечной вершине дерева (листу) полностью определяет соответствующее допустимое решение. Конструируя полное дерево вариантов, мы графически изображаем все множество допустимых решений. Реализация метода ветвей и границ сводится к построению некоторого фрагмента дерева вариантов с анализом получаемых в процессе построения вершин; чем меньший фрагмент придется построить для решения задачи Z, тем более эффективным окажется применение метода ветвей и границ.
Для каждой вершины V дерева вариантов однозначно определен путь, который ведет из корня в V. Этот путь фиксирует значения ряда переменных, число составляющих его ребер именуется рангом вершины V. Примем для ранга обозначение r(V). Вершине V соответствует частная задача Z(K), отличие которой от исходной задачи Z состоит лишь в том, что значения некоторых переменных уже определены путем из корня в данную вершину. При анализе каждой получаемой вершины V определяем для нее две оценки, верхнюю (примем для нее обозначение P(V)) и нижнюю (примем для нее обозначение H(V)). Верхняя оценка Р(У) характеризует оптимальное решение в задаче Z(V) как некоторую надежду. Нижняя оценка порождается определенным допустимым решением задачи Z(V).
Метод ветвей и границ основывается на трех составляющих: способе получения верхней и нижней оценок в вершинах; правиле выбора вершины, в которой будет выполняться очередное ветвление; способе ветвления. Способ ветвления определяет переменную, различные значения которой фиксируются ребрами, исходящими из вершины. Поскольку переменные задачи Z булевозначны, то при выполнении ветвления в вершине V из нее проводится два новых ребра, получаем две новые вершины.
В процессе выполнения алгоритма определяющую роль играет текущий рекорд R. Изначально в конструируемом фрагменте имеется только корень, текущий рекорд R пуст.
Вершине-корню V0 дерева вариантов соответствует задача Z(V0), которая совпадает с задачей Z. Функционирование алгоритма начинается с вычисления нижней и верхней оценок в корне; нижняя оценка присваивается R. Если оказывается, что верхняя и нижняя оценки совпадают, оптимальное решение задачи Z уже найдено, это R; решение задачи закончено. В противном случае в корне реализуется ветвление; проводимые из корня ребра по-разному фиксируют значения какой-либо переменной, получаем ряд новых вершин.
В каждой новой вершине V для соответствующей задачи Z(V) определяются нижняя и верхняя оценки. Вновь полученная нижняя оценка сравнивается с R; из двух значений выбирается большее, оно и присваивается R. В результате получаем новое значение текущего рекорда R. Знание оценок в получаемых вершинах достаточно часто дает возможность ограничить перебор путем отбрасывания заведомо бесперспективных ветвей (подмножеств решений).
На любой фазе построения дерева вариантов определяется вершина, в которой выполняется очередное ветвление. При этом совокупность имеющихся вершин делится на три группы. Первая группа - закрытые вершины; вершина V закрыта, если ветвление в ней уже выполнено. Вторая группа - терминальные вершины; вершина V является терминальной, если для приписанной данной вершине верхней оценки выполняется условие P(V) R. Не входящие в число закрытых и терминальных вершины именуем открытыми, они образуют третью группу. Вершина, в которой выполняется очередное ветвление, должна выбираться только из числа открытых. Процесс решения задачи Z завершается в ситуации, когда в построенном фрагменте дерева вариантов не оказывается открытых вершин; полученное на этот момент значение текущего рекорда R совпадает с оптимальным значением критерия задачи Z. Чем меньше построенный на момент завершения процесса решения фрагмент дерева вариантов, тем эффективнее оказывается применение метода ветвей и границ.
Отметим, что изложенное к настоящему моменту можно рассматривать как общую схему решения задач дискретной оптимизации с максимизируемым критерием методом ветвей и границ.
Для полноты описания метода ветвей и границ в применении к задаче Z осталось определить процедуры подсчета верхней и нижней оценок в вершинах дерева вариантов, способ ветвления, а также правило выбора вершины, в которой будет выполняться очередное ветвление.
Алгоритм синтеза совокупностей эффективных оценок, удовлетворяющих пороговым ограничениям
Адаптируем изложенную выше общую схему ветвей и границ на случай задач с минимизируемым критерием. Изменения коснуться ролей верхней и нижней оценок (поскольку задача на минимум их роли поменяются), способа определения текущего рекорда и понятия терминальной вершины. Нижняя оценка H(V) будет характеризовать оптимальное решение в задаче Z(V) как некоторую надежду, в то время как верхняя оценка P(V) порождается определенным допустимым решением задачи Z(V). В начале функционирования алгоритма, т.е. при вычислении оценок в корне дерева вариантов, верхняя оценка присваивается R. В каждой новой вершине V для соответствующей задачи Z(V) определяются нижняя и верхняя оценки. Вновь полученная верхняя оценка сравнивается с R; из двух значений выбирается меньшее, оно и присваивается R.
В результате получаем новое значение текущего рекорда R. Вершина V является терминальной, если для приписанной данной вершине нижней оценки выполняется условие H(V) R. Конкретизация метода ветвей и границ в применении к задаче Z заключается в определении процедур подсчета верхней и нижней оценок в вершинах дерева вариантов, способа ветвления, а также правила выбора вершины, в которой будет выполняться очередное ветвление. Процедура определения оценок. Рассмотрим задачу Z iV), отличие которой от задачи Z{V) заключается только в том, что переменные множества M(V) принимают значения на числовом отрезке [0,l]. Для поиска оптимального решения задачи Z\V) также воспользуемся алгоритмом Данцига. Синтезируя оптимальное в Z (V) решение, выстраиваем соответствующие переменным множества M(V) предметы в очередь по возрастанию показателя //=- - Далее предметы удаляются из ранца (значения соответствующих переменных полагаются равными 1) в порядке установленной очередности до тех пор, пока весовое ограничение не превратится в равенство. Если для выполнения условия (1.1.14) как равенства необходимо удалить некоторую часть очередного предмета, то это делается, и соответствующая разделенному на части предмету переменная принимает значение, равное отношению веса части, удаленной из ранца, к полному весу разделенного предмета. Синтезированное таким образом решение, обозначим его Y (F), в задаче Z (V) является оптимальным.
Не следует повторять действия по упорядочиванию предметов при вычислении оценок в очередной вершине, необходимо изначально упорядочить и перенумеровать предметы соответствующим образом (дальнейшие рассуждения подразумевают выполнение данного условия). Обозначим через Y (V) решение, полученное из Y (V) заменой имеющейся нецелочисленной координаты на единицу. Рассмотрим процедуру улучшения решения Y (V). Соответствующие единичным координатам решения Y (V) и одновременно принадлежащие множеству M(V) предметы, по порядку, т.е. в порядке увеличения их номеров, помещаются обратно в ранец, если этому не противоречит весовое ограничение (1.1.14), значение соответствующей координаты вектора Y (V) принимает нулевое значение, в противном случае остается единичным. Результатом проделанных операций яв-ляется решение Y (V). Решение Y (V) является заведомо лучше, если при его построении удалось поместить обратно в ранец хотя бы один дополнительный предмет. Решения Y\V) и Y (V) являются допустимыми решениями задачи Z (V), поскольку не нарушается ни одно из ограничений (1.1.14) и (1.1.15) по построению. п Итак, вершине V ставится в соответствие нижняя оценка H(V)= Y, сіУ)(У) где операция [У] означает округление до ближайшего целого вверх, а также верхняя оценкаР(Г)=Іср/(П. Способ ветвления.
Пусть V - открытая в построенном фрагменте дерева вариантов вершина, выбранная для дальнейшего ветвления. Ветвление выполняется по переменной, значение которой в векторе Y (V) оказалось нецелочисленным. В результате ветвления получаем две новые вершины, ранг которых равен r(V) +1. Правило выбора вершины, в которой будет выполняться очередное ветвление. Для каждого очередного ветвления выбирается открытая вершина V с наименьшим значением нижней оценки H(V). Если таких вершин несколько, из них выбирается вершина наибольшего ранга. Для изложенного алгоритма примем обозначение ВГКЗР Табличный алгоритм Сформулируем совокупность частных задач Z(f,p), /є {1,2,..., п}, р є {1,2,...,b}: Частная задача Z(f, p) определяется имеющимися в наличии только первыми / предметами, суммарный вес предметов, которые не следует помещать в ранец, должен быть больше или равен р. Оптимальное значение критерия задачи Z(f,p) обозначим W(f,p). Очевидно, что задача Z(n,b) совпадает с задачей Z. Таким образом W(n,b) - оптимальное значение критерия задачи Z. Запишем рекуррентные соотношения динамического программирования для синтеза оптимального в задаче Z решения: где символ ос означает неразрешимую ситуацию. Операции сложения и взятия минимума с аргументом ос определяются как: Подробно рассмотрим равенство (1.1.19). Пока выполняется условие р аь т.е. мы можем обеспечить выполнение условия (1.1.17) тем, что не помещаем первый предмет в ранец, мы так и делаем, что обеспечивает значение критерия равное С\. При условии р щ мы получаем неразрешимую ситуацию. Соотношение (1.1.20) означает следующее. В случае р ау+і, обеспечить выполнение условия (1.1.17) можно двумя способами, либо не помещать в ранец предмет Яу+1, либо остаться в рамках ситуации при вычислении W(f,p), если она не является неразрешимой. Если имеет место р ау+1, выполнить условие (1.1.17) становится сложнее. Можно воспользоваться ситуацией при вычислении W(f,p) либо, не помещать предмет Яу+1 стоимостью су+1 в ранец и поскольку вес этого предмета составляет cif+\, попытаться добрать недостающий вес, оказавшись в условиях задачи Z(f,p-af+i). Данную ситуацию характеризует величина cy+l +W(f,p-aj-+i). В каждом из случаев, из двух возможных альтернатив мы выбираем лучшую, т.е. обеспечивающую минимальное значение критерия. Процедура вычисления значений функции W(f,p) реализуется как процесс последовательного заполнения клеток таблицы стоимостей. Заголовками столбцов данной таблицы являются натуральные числа от 1 до /, по возрастанию, заголовками строк -натуральные числа от 1 до р, тоже по возрастанию. Каждой клетке (f,p) соответствует показатель W(f,p). Заполнение первой строки происходит в соответствии с формулой (1.1.19). Каждая последующая строка заполняется согласно соотношению (1.1.20).
Применение эволюционно-генетических алгоритмов для получения эвристических решений
Метод ветвей и границ для решения однокритериальных задач о ранце изложен в разделах 1.1 и 1.2. Многокритериальный аналог этого метода предназначен для синтеза совокупностей эффективных оценок в задачах с несколькими аддитивными критериями.
Для начала рассмотрим общую схему ветвей и границ для решения многокритериальных задач дискретной оптимизации на примере задачи (1.3.1), примем для нее обозначение Z . Для сохранения целостности, в процессе описания общей схемы решения задачи Z мы повторим все необходимые нам понятия уже введенные в разделе 1.1. Z - задача с максимизируемыми критериями К Х), k = \J, в которой каждая переменная Xj принимает значения из конечного множества )., j = \,п; имеются также некоторые другие ограничения, связывающие значения различных переменных; считается, что при любых допустимых значениях переменных критерии принимают целочисленные значения. Ставим целью синтез полной совокупности эффективных в задаче Z оценок вместе с Парето-оптимальными решениями, которые эти оценки порождают.
Дерево вариантов для задачи Z — это дерево, каждое ребро которого фиксирует значение какой-либо переменной; любой путь от начальной вершины (корня) к конечной вершине дерева (листу) полностью определяет соответствующее допустимое решение. Конструируя полное дерево вариантов, мы графически изображаем все множество допустимых решений. Реализация многокритериального аналога метода ветвей и границ сводится к построению некоторого фрагмента дерева вариантов с анализом получаемых в процессе построения вершин; чем меньший фрагмент придется построить для решения задачи Z , тем более эффективным окажется применение данного метода.
Для каждой вершины V дерева вариантов однозначно определен путь, который ведет из корня в V; этот путь фиксирует значения ряда переменных, число составляющих его ребер именуется рангом вершины V; примем для ранга обозначение r(V).
Вершине V соответствует частная задача Z (V), отличие которой от исходной задачи z состоит лишь в том, что значения некоторых переменных уже определены путем из корня в данную вершину, критерии остаются прежними. При анализе каждой получаемой вершины V определяем для нее два множества векторов, верхних оценочных (примем для этого множества обозначение Weepx" (V) ) и нижних оценочных (примем для него обозначение WHUDICH(y")). Совокупность Weepx"(V) характеризует множество E(V) эффективных в задаче Z1 (V) оценок следующим образом: для любой оценки (vi,v2,...,v/) из E(V) в совокупности Weepx"(V) найдется вектор (wuw2,...,Wi) такой, что wk vk, для всех k = \,l. Нижние оценочные векторы порождаются некоторыми допустимыми решениями задачи Z (V): если X - одно из таких решений, то {К Х ІК Х І К Х1)) є Wum(V).
Многокритериальная реализаций метода ветвей и границ основывается на четырех составляющих: способе получения в вершинах множеств нижних оценочных векторов; способе получения в вершинах множеств верхних оценочных векторов; правиле выбора вершины, в которой будет выполняться очередное ветвление; способе ветвления. Способ ветвления определяет переменную, различные значения которой фиксируются ребрами, исходящими из вершины. Если переменные задачи булевозначны, то при выполнении ветвления в вершине V из нее проводится два новых ребра, получаем две новые вершины.
В процессе выполнения алгоритма определяющую роль играет текущее множество рекордных векторов-оценок R. Изначально в конструируемом фрагменте имеется только корень, текущее множество R пусто.
Вершине-корню VQ дерева вариантов соответствует задача Z (У0), которая совпадает с задачей Z . Функционирование алгоритма начинается с вычисления нижних и верхних оценочных векторов в корне; нижние оценочные векторы вносятся в совокупность R. Если оказывается, что множества верхних и нижних оценочных векторов в корне совпадают, полная совокупность эффективных в решаемой задаче оценок уже найдена, это полученная совокупность R; решение задачи закончено. В противном случае в корне реализуется ветвление; проводимые из корня ребра по-разному фиксируют значения какой-либо переменной, получаем ряд новых вершин.
В каждой новой вершине V для соответствующей задачи Z (V) определяются множества нижних и верхних оценочных векторов. Вновь полученные нижние оценочные векторы включаются в имеющуюся совокупность R; из таким образом пополненного множества R изымаются векторы, которые в пополненной совокупности оказались доминируемыми. В результате получаем новый состав текущего множества рекордных оценок R. Знание векторных оценок в получаемых вершинах достаточно часто дает возможность ограничить перебор путем отбрасывания заведомо бесперспективных ветвей (подмножеств решений).
На любой фазе построения дерева вариантов определяется вершина, в которой выполняется очередное ветвление. При этом совокупность имеющихся вершин делится на три группы. Первая группа - закрытые вершины; вершина V закрыта, если ветвление в ней уже выполнено. Вторая группа - терминальные вершины; вершина V является терминальной, если для каждой приписанной данной вершине верхней векторной оценки (wi,w2,...,wi) в R найдется векторная оценка (v!,v2,...,v/) такая, что для любого к = 1,1, выполняется Wfr vk. Если V - терминальная вершина, то никакая из эффективных для задачи Z1(V) оценок пополнить совокупность R не сможет. Не входящие в число закрытых и терминальных вершины именуем открытыми, они образуют третью группу. Вершина, в которой выполняется очередное ветвление, должна выбираться только из числа открытых. Если открытых вершин несколько, то возможны различные стратегии выбора. Способ выбора более экономичен, если для решения задачи Z строится меньший фрагмент дерева вариантов. Вопрос об оптимальном способе выбора однозначного и независящего от типа решаемой задачи ответа не имеет.
Процесс решения задачи Z завершается в ситуации, когда в построенном фрагменте дерева вариантов не оказывается открытых вершин; полученное на этот момент текущее множество оценок R совпадает с полной совокупностью эффективных в Z оценок. Чем меньше построенный на момент завершения процесса решения фрагмент дерева вариантов, тем эффективнее оказывается применение данного метода. Трудоемкость реализации изложенного алгоритма может принимать широкий спектр значений (в лучшем случае оказывается достаточным вычислить только векторные оценки в корне дерева вариантов, в худшем - построить его полностью, вычисляя оценки в корне и во всех промежуточных вершинах).
Математические постановки задач с несколькими ранцами и алгоритмы их точного решения
Примером важной прикладной проблемы, записываемой в рамках модели (4.2.1)-(4.2.4), может служить формулируемая следующим образом задача оптимального размещения баз снабжения (см. [18]).
Задано множество потребителей Р = {Р1,Р2,...,РГ}, в настоящее время они получают сырье от некоторых старых баз. Имеется набор Г = {ГЬГ2,...,ГА.} возможных точек размещения новых сырьевых баз. Должно быть создано не более р новых баз, здесь 1 р к; мощность каждой новой базы может быть назначена произвольным образом (под мощностью базы понимается максимально возможный объем поставок из нее). Известна (гхк) - матрица экономии С = (с,-,-j с положительными элементами, где Су - годовая экономия при организации доставки сырья потребителю Pt из точки Tj. Требуется: а) определить, в каких точках следует разместить новые базы; б) для каждого потребителя указать место расположения новой базы, за которой он закрепляется. Решение должно обеспечить максимальную годовую экономию при доставке сырья потребителям множества Р.
Выполним сведение сформулированной задачи, назовем ее задачей Z, к задаче о к ранцах Z вида (4.2.1) - (4.2.4). При этом каждой возможной точке размещения сырьевой базы Tj ставим в соответствие ранец R,вместимости / (по числу потребителей), у = 1,к. Каждому потребителю Pt ставим в соответствие предмет Я, единичного веса, / = 1,г. Предметы, соответствующие потребителям, именуем основными предметами. Кроме того, в формулируемой задаче считаем присутствующими дополнительные предметы Пг+\ Пг+2,-Мг+к-р каждый дополнительный предмет имеет вес г. По указанным исходным данным, в задаче P(Z) имеется n-r+k- р предметов и любой дополнительный предмет полностью загружает любой из ранцев. Считаем, что каждый основной предмет Я/ характеризуется вектором стоимостей с, =(c/i,C/2,...,c; ), где с у стоимость предмета Я,, если его поместить в ранец Rj, здесь i = l,r, j = l,k. Каждый дополнительный предмет характеризуется А:-мерным вектором стоимостей (D,D,...,D), где D - любая, не меньшая тахсц константа. Задача Z сформулирована полностью. Легко видеть, что благодаря наложенному на константу D ограничению, в любом оптимальном решении задачи Z все дополнительные предметы оказываются в ранцах, а оптимальное значение критерия записывается в виде суммы {к - p)D +, где // .
Оптимальное решение задачи Zk в терминах исходной задачи Z трактуется следующим образом: если в ранец Rj помещен некоторый дополнительный предмет, то точка не является местом размещения новой сырьевой базы; если в ранец Rj помещены основные предметы Пх ,ПХ ,...,ПХ , то точка Г.- является местом размещения новой сырьевой базы, потребители Рх ,РХ ,...,РХ закрепляются за этой базой (если объем требуемых потребителю Ph поставок обозначить через щ, то мощность указанной базы должна равняться axi X если в ранец R; не помещен ни один предмет (основной или дополнительный), то точка 7\- не является местом размещения новой сырьевой базы, здесь j = \,k. Полученным решением задачи Z обеспечивается оптимальное значение ее критерия, оно оказывается равным //.
Для реализации любого эволюционно-генетического алгоритма (ЭГА) необходимо определить составляющие его генетические операторы применительно к решаемой задаче (см. раздел 3.2). Конкретизируем данные операторы относительно задачи Z .
Процедура генерации начальной популяции. В качестве хромосомы выступает матрица-заполнение Х = Су], / = 1,и, j = \,k. Изначально все предметы Я;, / = 1,л считаются свободными, т.е. не находящимися ни в одном из ранцев Rj, j = \,к. Генерация каждой из S хромосом начальной популяции осуществляется согласно следующему правилу-последовательности действий: 1. Случайным образом выбирается свободный предмет Я,, і = \,п; 2. Случайным образом выбирается ранец Rj, j = \,к; 3. Предмет Я,- помещается в ранец /?, (соответствующая координата матрицы заполнения X устанавливается в единицу Ху=1, остальные координаты xig, g j, принимают нулевые значения xt„ =0), если позволяет ограничение (4.2.2.), в противном случае, предмет помещается в один из оставшихся случайным образом выбранный ранец. Если, таким образом, не получается поместить предмет Я,- ни в один из ранцев не нарушив условие (4.2.2), то предмет помечается как неиспользуемый и изымается из дальнейшего рассмотрения (соответствующие предмету / координаты матрицы-заполнения X фиксируют нулевые значения Хц =0, для любого j = \,k).
Данная процедура повторяется, пока все предметы будут либо помещены в ранцы, либо помечены как неиспользуемые. Один из первых двух этапов, использующий случайный принцип выбора предмета (п.1) или ранца (п.2), может быть заменен последовательным перебором предметов, либо ранца, в порядке возрастания индекса / = \,п и
Оператор кроссинговера. Пусть имеются две родительские особи с хромосомами X и X . Формирование хромосомы новой особи-потомка осуществляется следующим образом. В порядке возрастания индекса i = \,n, предмет Я, помещается в ранец согласно матрице-заполнению случайно выбранной родительской особи; если это не позволяет сделать весовое ограничение (4.2.2), то предмет Я; размещается согласно решению-хромосоме оставшейся родительской особи; если и это нарушает условие допустимости (4.2.2), то предмет считается неиспользуемым (т.е. не помещается ни в один из ранцев).
Оператор мутации. Данный оператор реализуется как равновероятностное применение одного из трех видов модификации хромосомы. Первый вид - случайным образом выбранный неиспользуемый предмет (т.е. не находящийся ни в одном из ранцев) помещается в случайно выбранный ранец. Второй вид - случайным образом выбираются два ранца; в каждом из ранцев случайным образом выбирается по предмету, которые меняются местами. Третий вид — случайным образом выбирается ранец; случайным образом выбирается предмет в данном ранце и обменивается со случайно выбранным неиспользуемым предметом. Каждый из видов мутации принимается только в случае удовлетворения весовому ограничению (4.2.2) и улучшения значения фитнес-функции (ФФ).
