Другие журналы

научное издание МГТУ им. Н.Э. Баумана

НАУКА и ОБРАЗОВАНИЕ

Издатель ФГБОУ ВПО "МГТУ им. Н.Э. Баумана". Эл № ФС 77 - 48211.  ISSN 1994-0408

Эвристики и их комбинации в генетических методах дискретной оптимизации

#10 октябрь 2005

И

И. П. Норенков, д-р техн. наук, проф., МГТУ им. Н. Э. Баумана

 

Эвристики и их комбинации в генетических методах дискретной оптимизации

 

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

 

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

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

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

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

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

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

Подобный подход уже был успешно применен к задачам синтеза расписаний [1] и назван методом комбинирования эвристик (НСМ — Heuristics Combination Method). Данная статья посвящена иллюстрации возможностей и особенностей применения НСМ к ряду других задач дискретной оптимизации, упомянутых выше. Ниже дается краткое введение в НСМ, обсуждаются постановки задач и используемые эвристики, приводятся некоторые результаты численных экспериментов для ряда задач дискретной оптимизации. В заключении обсуждаются преимущества излагаемого подхода.

Введение в НСМ. В генетических методах (ГМ) любое решение задачи синтеза представляется хромосомой (другие названия — запись, фрейм), состоящей из генов (полей, слотов). Аллелями, т. е. значениями генов, являются значения проектных параметров.

Направленный перебор решений осуществляется с помощью генетических операторов выбора родителей, кроссовера, мутации, селекции, переупорядочения. Сначала формируется (обычно случайным образом) исходное поколение, состоящее из g хромосом. Далее случайным образом среди хромосом данного поколения выбираются пары родителей, причем вероятность выбора хромосом с лучшими значениями целевой функции должна быть выше. Следующее поколение образуется (селектируется) из g перспективных дочерних хромосом, являющихся результатом ряда операций кроссовера. Кроссовер заключается в разрыве двух родительских хромосом и рекомбинирования образовавшихся хромосомных отрезков. Мутации, т. е. случайные изменения некоторых аллелей, происходят по некоторому правилу (например, с заданной вероятностью) и служат для исключения застревания поиска в ограниченном подпространстве. Разновидности генетических операторов и их сочетаний порождают множество ГМ, описание которых можно найти, например, в [2, 3].

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

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

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

Рассмотрим постановки ряда сложных задач дискретной оптимизации для их решения методом НСМ.

Задача компоновки. Содержательной сутью задачи может быть распределение работ по исполнителям, микросхем по аппаратным блокам, приложений по подсетям виртуальной локальной вычислительной сети (ВЛВС) и т. п. Для определенности рассмотрим задачу распределения приложений по подсетям ВЛВС, обозначив эту задачу ADP (Application Distribution Problem). К исходным данным относятся:

·         множество приложений;

·         максимально возможное число подсетей т (или множество подсетей {В1, В2, ..., Вm});

·         матрица трафика между приложениями D (в общем случае матрица межкомпонентных связей);

·         ограничение на максимально допустимый трафик внутри каждой из подсетей (в общем случае задачи компоновки — на максимальное число компонентов в каждом блоке).

В качестве минимизируемой целевой функции используется внешний трафик F между подсетями ВЛВС.

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

S1) которому соответствует максимальный элемент в матрице D (без учета строк и столбцов уже распределенных приложений);

S2) с номером k, где k — порядковый номер подзадачи (если это приложение уже распределено, то эвристика с данным правилом просто пропускается);

S3) с максимальной связью (трафиком) с уже распределенными приложениями.

Вторая часть локальной задачи выполнялась по правилам QlQ4, в соответствии с которыми выбирается подсеть:

Q1) минимально загруженная;

Q2) максимально загруженная;

Q3) включающая приложение с максимальным взаимным трафиком с распределяемым приложением;

Q4) имеющая максимальный суммарный трафик с распределяемым приложением.

Из общего числа 12 возможных эвристик (сочетаний правил для первой и второй частей подзадачи) были использованы пять эвристик: (S1, Q1), (S2, Q1), (S3, Q3), (S3, Q4), (S1, Q2).

Приводимые ниже результаты решения относятся к тестовой задаче, обозначаемой ADP_39 и характеризуемой следующими данными: число приложений n = 39; максимальное число подсетей m = 10; ограничение на внутренний трафик = 540 условных единиц. Хромосома в ADP_39 состоит из 39 генов, аллелями могут быть номера эвристик, т. е. целые числа в диапазоне [1, 5].

Задача кластеризации. Эта задача может рассматриваться как разновидность задачи компоновки, отличающаяся от последней типом ограничений: вместо ограничения типа неравенства на объем внутренних для кластера (блока) связей вводится ограничение типа равенства на число элементов (компонентов) nj в каждом кластере. Другими словами, требуется равномерное распределение элементов по кластерам, минимизирующее связность кластеров друг с другом. В частности, в некоторых алгоритмах размещения микросхем на платах предварительно решается задача дихотомической кластеризации — разделения множества микросхем на два минимально связанных подмножества одинаковой (при четном числе элементов n) мощности [4].

Очевидно, что в задаче кластеризации после соответствующей корректировки можно использовать правила выбора очередного элемента и его размещения в одном из кластеров, аналогичные правилам в задаче компоновки. Так, в правиле Q1 загрузка кластера будет оцениваться не его внутренним трафиком (связностью), а числом размещенных в нем элементов; в используемых правилах Ql, Q3 и Q4 возможным кластером-кандидатом на размещение может быть только тот кластер, в котором еще не исчерпан лимит на размещение. Правила S1—S4 используются без изменений. При вычислении целевой функции штрафы за нарушение ограничений не предусматриваются, так как учет ограничений введен в эвристики. Полученный таким образом набор эвристик обозначим МЭ1.

Были опробованы и другие варианты множества эвристик. В варианте МЭ2 номер j очередного кластера определялся как j := (j + 1)% т при начальном j = 0 (здесь % — символ операции деления по модулю, m — число кластеров), что гарантировало выполнение заданных ограничений. Поэтому суть эвристики определялась только правилом выбора очередного размещаемого элемента.

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

S1) в строке которого в матрице связей находится максимальный элемент матрицы;

S2) имеющий максимальную суммарную связ­ность с уже размещенными элементами;

S3) имеющий минимальную суммарную связность с еще не размещенными элементами.

Для выбранного по одному из правил S1S3 элемента I определяется кластер, в котором:

Q1) имеется элемент, максимально связанный с I;

Q2) уже размещенные элементы максимально связаны с I (максимальна суммарная связность).

Из этих правил скомбинированы следующие эвристики:

 

Э1 = {S1, Q1}; Э2 = {S2, Q1); ЭЗ = {S3, Q2}; Э4 = {S2, Q2).

 

К этому набору была добавлена эвристика Э5, в которой сначала определялся кластер L по признаку минимальной загруженности, а затем для него определялся элемент по признаку максимальной связности с уже размещенными в L элементами. Ограничения на максимально допустимое число элементов в кластере также введены в эвристики.

Для проведения экспериментов использовалась тестовая задача CLS_80. В ней число элементов n = 80, число кластеров m = 4. Соответственно число генов в хромосоме равно 80, аллелями могут быть целые числа от 1 до 5.

Задача маршрутизации транспортных средств. Среди множества транспортных задач выделяются своей сложностью задачи маршрутизации транспортных средств с временными окнами VRPTW (Vehicle Routing Problem with Time Windows). Известны примеры применения генетических алгоритмов к некоторым разновидностям VRPTW [5, 6]. Нами с помощью НСМ решалась одна из наиболее сложных разновидностей VRPTW в следующей постановке.

Основные исходные данные: n — число узлов-потребителей продукта (k-й узел-потребитель отождествляется с k-м заказом); b — число узлов-ис­точников продукта; m — число серверов (транспортных средств); w — общее число узлов; V — исходное расположение потребителей, источников и серверов в узлах; D — матрица расстояний между узлами; T1i и T2i — нижняя и верхняя границы временного окна для выполнения i-го заказа; р — число типов продукта. Кроме того, для узлов-потребителей и узлов-источников заданы объемы соответственно заказанного и имеющегося продукта каждого типа, для серверов — максимальный объем перевозимого продукта, скорость движения, цена за единицу расстояния пробега, штрафы за нарушение временных ограничений (выход за пределы временных окон), причем штрафы зависят от цены единицы продукта каждого типа и от степени нарушения ограничений.

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

Задача декомпозируется на подзадачи, в каждой из которых применяются эвристики для следующих частей подзадачи: 1) выбор заказа (узла-потребителя); 2) выбор узла-источника; 3) выбор сервера (не исключено, что для выполнения конкретного заказа привлекается более чем по одному источнику и/или серверу).

Для первой части подзадач использовались правила S1—S3, в которых выбирается потребитель:

S7) с максимальным суммарным объемом заказанного продукта;

S2) с максимальной ценой заказанного продукта;

S3) с минимальной верхней границей временного окна.

Для второй части подзадач использовались правила Q1 и Q2 по отношению к источникам с запасом продукта хотя бы одного типа большим, чем заказанный объем; если таких источников нет, то применялось правило Q3. В правилах выбирается источник:

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

Q2) с минимальной суммой Д расстояний до узла-потребителя и до ближайшего узла, в котором имеется свободный сервер;

Q3) с минимальной величиной h = (L1 + L2) • U0/U, где L1 и L2 — расстояния соответственно до узла-потребителя и до ближайшего узла, в котором имеется свободный сервер; U0 — суммарный объем заказанного продукта; U— суммарный объем продукта в источнике.

Для третьей части подзадач использовались правила V1— V3, в которых выбирается сервер:

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

V2) с минимальным временем освобождения от предыдущего обслуживания;

V3) с минимальным временем выполнения маршрута.

В качестве тестовой использовалась задача VRP_80 со следующими исходными данными: w = 80, n = 25, b = 40, m = 12, р = 2.

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

Задача размещения двумерных разногабаритных компонентов. Эта задача известна как задача размещения электронных компонентов (в кристаллах БИС или на печатных платах), или как двумерная задача упаковки грузов в контейнеры, или как задача раскроя (одно из ее возможных обозначений 2DBPP - 2D Bin Packing Problem) [7, 8].

Постановка 2DBPP: задана полубесконечная полоса (контейнер с открытым верхом и шириной W) и множество разногабаритных прямоугольных компонентов с размерами Di Li. Требуется упаковать компоненты в контейнер с минимизацией высоты Н заполненной части контейнера (допускаются ориентации компонентов исходная и повернутая на 90°).

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

S1) выбирается еще не размещенный компонент, обеспечивающий наименьший горизонтальный зазор gap ≥ 0 (рис. 1); если gap > 0, то компонент размещается вплотную к тому краю участка, на котором меньше (по абсолютной величине) вертикальный зазор z; если компонентов с gap > 0 нет, то участок шириной а и высотой h объявляется пустотелым и заполняется фиктивным компонентом;

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

S3) то же, что и в S2, но сначала исследуются компоненты при повернутой ориентации;

S4) выбирается компонент с наибольшей площадью среди еще не размещенных компонентов и с положительным зазором gap.

Рис. 1. Размещение компонента в очередном участке

В тестовой задаче ВРР_100 в контейнере шириной 140 единиц требуется разместить n = 100 прямоугольных компонентов разных размеров. Хромосома включает 100 генов, их значениями могут быть номера эвристик в диапазоне [1, 4].

На рис. 2 приведен результат одного из прогонов более простой тестовой задачи ВРР_40 (n = 40), из которого можно получить представление о качестве получаемых с помощью НСМ решений (незаполненные участки пространства залиты на рис. 2 черной краской).

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

 

Синтез расписаний. Задачи синтеза расписаний фигурируют во многих приложениях, и генетические методы рассматриваются в качестве одного из наиболее перспективных подходов к их решению [9—12].

Нами решались задачи синтеза расписаний как с частично упорядоченным множеством работ, так и многостадийные задачи синтеза расписаний типа OSSP (Open Shop-Scheduling Problem). Постановки и эвристики задач OSSP для решения с помощью НСМ описаны в [1]. Там же охарактеризованы тестовые задачи N25 и N105. В первой из них заданы число работ n = 25, число стадий р = 4, число серверов m = 15, вторая задача отличается заметно большим числом работ n = 105.

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

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

 

Задача

Лучший из эвристических методов

НСМ

ADP 39

1857

913-929

3500

CLS 80

2008

1905*

3000

ВРР 100

2835

431-489

12 000

VRP 80

705

494—504

5400

N25

6006

5274-5337

25 000

N105

23 084

21 852-21 968

36 000

* Известное оптимальное значение целевой функции.

 

Следует заметить, что в отличие от НСМ, где требуется разнообразие эвристик, в обычных эвристических методах можно повысить эффективность решения, применяя в единственной эвристике по нескольку критериев с определенными весовыми коэффициентами. Как показали эксперименты на задаче N105, результаты улучшаются, но не настолько, чтобы конкурировать с НСМ — при оптимальных весовых коэффициентах в моноэвристичном методе получено F = 22326 [13].

В третьей колонке дан диапазон значений F, полученных в нескольких прогонах задачи по методу НСМ. В четвертой колонке охарактеризована принятая в экспериментах продолжительность генетического поиска, измеряемая числом обращ­ний к модели приложения (к процедуре вычисления целевой функции), в каждом прогоне. При этом затраты машинного времени на один прогон составляли от десятков секунд (ADP_39) до десятков минут (N105) на Pentium 100MHz.

Заключение. Рассмотрим преимущества НСМ.

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

Большая эффективность НСМ в сравнении с обычными генетическими методами обусловливается следующими причинами:

1. Существенное сокращение поискового пространства за счет использования ограниченного числа разумных эвристик (следовательно, сокращение идет за счет неперспективных областей пространства решений). Например, в таких задачах, как задача назначения n исполнителей на n работ или задача коммивояжера с n городами, мощность множества возможных решений есть п! В то же время в НСМ при использовании набора из т эвристик мощность уменьшается до mn.

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

3. Не требуется выполнять операции корректировки хромосом после кроссовера или мутации.

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

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

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

 

Список литературы

1. Норенков И. П. Генетические методы структурного синтеза проектных решений // Информационные технологии, 1998. № 1.С. 9-13.

2. Goldberg D. Genetic Algorithms in Search, Optimization, and Machine Learning // Adison-Wesley Publ., 1989.

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

4. Кокотов В. 3. Алгоритм плотного размещения разногабаритных элементов на плате // Информационные технологии, 1998. № 11. С. 16-22.

5. Blanton J., Wainwright R. Multiple Vehicle Routing with Time and Capacity Constraints Using Genetic Algorithms // Proc. of 5th Int. Conf. on GA, Morgan Kaufmann Publ., San Mateo, 1993.

6. Thanglash S., Vinayagamoorty R., Gabbi A. Vehicle Routing and Time Deadlines Using Genetic and Local Algorithms // Proc. of 5th Int. Conf. on GA, Morgan Kaufmann Publ., San Mateo, 1993.

7. Kroger B. Guillotinable Bin Packing: a Genetic Approach // European Journal of Operational Research, 84, 1995.

8. Arenales M., Morabito R. An AND/OR-graph Approach to the Solution of Two-dimensional Non-guillotine Cutting Problems // European Journal of Operational Research, 84, 1995.

9. Whitley D., Starkweather Т., Fuduay D. Schedulong Problems and Traveling Saleman: the Genetic Edge Recombination Operator // Proc. of 3d Int. Conf. on GA, 1989.

10. Nakano R. Conventional Genetic Algorithm for Job Shop Problems // Proc. of 4th Int. Conf. on GA, Morgan Kaufmann Publ., San Francisco, 1991.

11. Bruns R. Direct Chromosome Representation and Advanced Genetic Operators for Production Scheduling // Proc. of 5th Int. Conf. on GA, 1993.

12. Kobayashi S., Ono I., Yamamura M. An Efficient Genetic Algorithm for Job Shop Scheduling Problem // Proc. of 6th Int. Conf. on GA, Morgan Kaufmann Publ., San Francisco, 1995.

13. Tcheprasov V., Punch W., Goodman E., Ragatz G., Norenkov I. A Genetic Algorithm to Generate a Pro-Active Scheduler for Printed Circuit Board Assembly // Proc. EvCA'96, Moscow, 1996.

 

ИНФОРМАЦИОННЫЕ ТЕХНОЛОГИИ, № 1, 1999

МЕТОДЫ ОПТИМИЗАЦИИ

 

Ключевые слова: Дискретная оптимизация, комбинирование эвристик, генетические методы, HCM, распределение ограниченных ресурсов.

Поделиться:
 
ПОИСК
 
elibrary crossref ulrichsweb neicon rusycon
 
ЮБИЛЕИ
ФОТОРЕПОРТАЖИ
 
СОБЫТИЯ
 
НОВОСТНАЯ ЛЕНТА



Авторы
Пресс-релизы
Библиотека
Конференции
Выставки
О проекте
Rambler's Top100
Телефон: +7 (915) 336-07-65 (строго: среда; пятница c 11-00 до 17-00)
  RSS
© 2003-2020 «Наука и образование»
Перепечатка материалов журнала без согласования с редакцией запрещена
 Тел.: +7 (915) 336-07-65 (строго: среда; пятница c 11-00 до 17-00)