Метаэвристический метод комбинаторной оптимизации ОМК-Н
Запропоновано гібридний метаевристичний метод комбінаторної оптимізації ОМК-Н, який базується на двох популяційних підходах — алгоритмах оптимізації мурашиними колоніями і Н-методі. Отримано умови, що визначають збіжність за значенням до оптимального розв’язку задачі. Ефективність алгоритмів методу...
Збережено в:
| Опубліковано в: : | Проблемы управления и информатики |
|---|---|
| Дата: | 2010 |
| Автори: | , |
| Формат: | Стаття |
| Мова: | Російська |
| Опубліковано: |
Інститут кібернетики ім. В.М. Глушкова НАН України
2010
|
| Теми: | |
| Онлайн доступ: | https://nasplib.isofts.kiev.ua/handle/123456789/210744 |
| Теги: |
Додати тег
Немає тегів, Будьте першим, хто поставить тег для цього запису!
|
| Назва журналу: | Digital Library of Periodicals of National Academy of Sciences of Ukraine |
| Цитувати: | Метаэвристический метод комбинаторной оптимизации ОМК-Н / Л.Ф. Гуляницкий, С.И. Сиренко // Проблемы управления и информатики. — 2010. — № 4. — С. 31-42. — Бібліогр.: 35 назв. — рос. |
Репозитарії
Digital Library of Periodicals of National Academy of Sciences of Ukraine| _version_ | 1859545762943205376 |
|---|---|
| author | Гуляницкий, Л.Ф. Сиренко, С.И. |
| author_facet | Гуляницкий, Л.Ф. Сиренко, С.И. |
| citation_txt | Метаэвристический метод комбинаторной оптимизации ОМК-Н / Л.Ф. Гуляницкий, С.И. Сиренко // Проблемы управления и информатики. — 2010. — № 4. — С. 31-42. — Бібліогр.: 35 назв. — рос. |
| collection | DSpace DC |
| container_title | Проблемы управления и информатики |
| description | Запропоновано гібридний метаевристичний метод комбінаторної оптимізації ОМК-Н, який базується на двох популяційних підходах — алгоритмах оптимізації мурашиними колоніями і Н-методі. Отримано умови, що визначають збіжність за значенням до оптимального розв’язку задачі. Ефективність алгоритмів методу ілюструють результати обчислювального експерименту з розв’язання низки відомих задач комбінаторної оптимізації.
A metaheuristic method ACO-Н for combinatorial optimization problems is proposed, which is based on two population methods — ant colony optimization and H-method. A convergence in value to an optimal solution for a class of method’s algorithms is shown. The experiment conducted on a number of combinatorial optimization problems shows efficiency of the proposed approach of combining ACO and H-method.
|
| first_indexed | 2026-03-13T11:23:54Z |
| format | Article |
| fulltext |
© Л.Ф. ГУЛЯНИЦКИЙ, С.И. СИРЕНКО, 2010
Международный научно-технический журнал
Проблемы управления и информатики, 2010, № 4 31
ОПТИМАЛЬНОЕ УПРАВЛЕНИЕ
И МЕТОДЫ ОПТИМИЗАЦИИ
УДК 519.8
Л.Ф. Гуляницкий, С.И. Сиренко
МЕТАЭВРИСТИЧЕСКИЙ МЕТОД
КОМБИНАТОРНОЙ ОПТИМИЗАЦИИ ОМК-Н
Несмотря на отсутствие общепринятого формального определения, метаэв-
ристические методы можно понимать как комбинацию двух техник: общая схема
строится на базовом методе, в который включается та или иная встроенная проце-
дура. Важным аспектом есть то, что встроенная процедура — это в большинстве
случаев самостоятельный алгоритм решения той же задачи, что и метаэвристиче-
ский метод в целом. В последнее время начались разработки гибридных мета-
эвристик, объединяющих в единую схему уже не «простые» алгоритмы, а метаэв-
ристики. Многие из разработанных метаэвристических методов относятся к клас-
су популяционных алгоритмов [1], т.е. алгоритмов, в которых, в отличие от одно-
точечных, на каждой итерации обрабатывается не один, а сразу несколько вариан-
тов решения.
В настоящей работе предлагается и анализируется гибридный метаэвристи-
ческий метод решения задач комбинаторной оптимизации (КО), который разрабо-
тан на основе комбинации двух популяционных подходов [2]: оптимизации мура-
вьиными колониями (ОМК) [3] и Н-метода [4].
Существует большое количество работ, посвященных гибридизации алго-
ритмов ОМК и других эвристик (метаэвристик) для задач КО. Ранние публикации
касаются преимущественно гибридизации с такими одноточечными методами,
как локальный поиск [5], имитационный отжиг [6], G-алгоритм [7] и табу-по-
иск [8]. Локальный поиск на данный момент стал стандартной подпроцедурой
в большинстве алгоритмов ОМК. Некоторые аналогии с предлагаемым подходом
имеет структура взаимодействия алгоритмов ОМК и локального поиска, предло-
женная в [9]. Среди первых популяционных алгоритмов, с которыми осуществля-
лась гибридизация ОМК, были генетические алгоритмы [10, 11] и методы, бази-
рующиеся на иммунной парадигме [12]. Также наличествует ряд гибридов со спе-
циализированными эвристиками (см. [13, 14]). Последние работы включают, но
не ограничиваются гибридами с меметическими алгоритмами [15], рассеянным
поиском [16], перекомпоновкой маршрутов [17], оптимизацией роем части-
чек [18], а также развитием ранее предложенных подходов [19–21]. Предложено
также значительное количество успешных гибридных алгоритмов, объединяющих
ОМК и точные методы, их приближенные варианты и другие подходы из области
исследования операций, но они находятся вне рассмотрения данной работы.
Н-метод гибридизировался с алгоритмом поиска в переменных окрест-
ностях [22].
В разд. 1 описана модифицированная метаэвристика Н-метода, которая ис-
пользуется в разработанном подходе. Предложенный метаэвристический метод
32 ISSN 0572-2691
описан в разд. 2, где рассмотрены его пошаговая структура и особенности. В разд. 3
получены условия, определяющие класс алгоритмов, сходящихся по значению
к оптимальному решению задачи. В разд. 4 изложены результаты вычислительно-
го эксперимента по решению задач коммивояжера [1] и многомерных задач о
назначении [23].
Далее рассматриваются задачи КО, определенные на конечном пространстве
решений X, однако разработанный подход может применяться и ко многим дру-
гим задачам со счетным множеством решений.
1. Н-метод
В ряде алгоритмов КО во избежание концентрации поиска в ограниченной
подобласти пространства X и повышения точности получаемых решений исполь-
зуются процедуры возмущения [24] или скрещивания и мутации (как в эволюци-
онных методах) [25]. Заметим, что подобные процедуры порождают подмноже-
ства вариантов решения, которые не согласованы с топологией пространства X. В
то же время примером подобного согласования выступает Н-метод, который яв-
ляется развитием дискретного метода деформированных многогранников [26]. Ме-
тод имеет определенные аналогии с известным в недифференцируемой непрерыв-
ной оптимизации методом Нелдера–Мида, применяя в процессе поиска оптималь-
ного решения специальным образом определенные отрезки. Подобные идеи были
предложены Гловером [27, 28] в контексте табу поиска; позже они получили разви-
тие вместе с рассеянным поиском и известны как перекомпоновка маршрутов [29].
На рис. 1 приведена модификация Н-метода, которая используется в разрабо-
танном метаэвристическом подходе. От стандартного Н-метода [4, 30] она отли-
чается инициализацией начальной популяции вне алгоритма, явно указанным со-
хранением наилучшего найденного решения и тем, что алгоритм возвращает
множество вариантов решений, которыми он оперировал на последней итерации.
procedure Н (P, x*);
begin
repeat
Р` := ø;
for i:= 1 to r do
ОтборДляВариации (x,yP: f (y) f (x));
ПостроениеОтрезка (/x,x
∞
/ : y /x, x
∞
/ );
z := arg min {f (u) : u /x,x
∞
/, y /x, x
∞
/, u )(xL , u )(yL };
ТраекторныйМетод (z);
Р` := P` {z};
if f (x*) > f (z) then
x* := z;
end if
end for;
P := ОтборПопуляции (Р,P`);
until не выполняется условие завершения;
return P, x*;
end
Рис. 1
Ключевой этап Н-метода — решение подзадач, определение которых требует
введения понятия ориентированного d-отрезка [26], соединяющего две точки:
,, Xyx если ),( dXX — метрическое пространство с метрикой d. Будем счи-
тать, что с каждой точкой ассоциировано несколько окрестностей (например,
метрические окрестности разных радиусов).
Назовем d-отрезком /,,/ yx ,, Xyx упорядоченную совокупность точек
,Xxi ,...,,1 ki удовлетворяющих условиям: ,1 xx ,yxk ),(),( yxdxxd ii
Международный научно-технический журнал
Проблемы управления и информатики, 2010, № 4 33
,),( yxd ,...,,1 ki и ),,(),( 1 ii xxdxxd ;1...,,1 ki при этом не существует
точки Xz такой, что },,{:}1...,,1{ 1 ii xxzki ),(),( 1ii xzdzxd
).,( 1 ii xxd
Алгоритм получает на входе начальное множество решений P и некоторое
субоптимальное решение .x
На итерации Н-метода генерируется множество вариантов решений. Проце-
дура ОтборДляВариации определенным образом отбирает пару yx, вариантов
решений, на основании которых строится и решается подзадача вида
)}.(),(/,,//,,/:)({argmin yLuxLuxxyxxuuf (1)
Здесь x — некоторая точка, максимально удаленная в пространстве вариантов
решений от точки x, выбранная так, чтобы /,,/ xxy а )(),( yLxL — окрест-
ности, поставленные в соответствие ,, yx точки которых, находясь на построенном
отрезке, исключаются из рассмотрения. На практике окрестности )(xL и )(yL
часто задаются на основе метрики пространства. В этом случае подзадача (1) при-
обретает вид
},),(,),(/,,//,,/:)({argmin RuydRuxdxxyxxuuf
где 0, RR — заданные радиусы окрестностей.
Ко всем найденным таким образом субоптимальным решениям применяется
траекторный метод (например, локальный поиск). Порожденное множество ва-
риантов решений `P обновляет текущую популяцию P с помощью процедуры
ОтборПопуляции.
Схема Н-метода подобна схеме эволюционных методов. В контексте тополо-
гических операторов кроссовера и мутации [31] решение подзадачи (1) можно
рассматривать как объединенное применение субоптимальных операторов крос-
совера и мутации.
В стандартной реализации алгоритма пары точек выбираются из текущей по-
пуляции случайным образом, значения радиусов RR , полагаются равными 2,
точка x и отрезок /,/ xx выбираются случайным образом среди всех возмож-
ных. Поиск минимума на отрезке осуществляется с помощью полного перебора.
Отбор точек в популяцию для следующей итерации проводится с помощью прин-
ципа элитаризма. Алгоритм останавливается, если на протяжении наперед задан-
ного количества итераций не найдено улучшения текущего рекорда.
Детально метод описан в работе [4].
2. Cинтез алгоритмов ОМК и Н-метода
Предлагается новый метаэвристический метод КО, который базируется на
использовании идей двух описанных выше популяционных методов — ОМК
и Н-метода. Алгоритмы этого метода сохраняют положительные стороны обоих
использованных подходов. Предложенный метод конкретизации проблемно-
зависимых частей позволяет решать как некоторый класс близких по постановке
задач КО, так и задачи КО из разных классов.
В начале работы метаэвристики ОМК-Н осуществляется инициализация ал-
горитма ОМК, в частности феромонных значений T (рис. 2). Далее производится
построение муравьями r (r — заданное значение) решений с последующим при-
34 ISSN 0572-2691
менением к этим решениям траекторного метода (например, локального поиска).
В случае выполнения условий передачи управления от алгоритма ОМК к алго-
ритму Н-метода множество вариантов решений S как начальная популяция пере-
дается в модификацию алгоритма Н-метода (см. рис. 1). На основе возвращенных
Н-методом вариантов решений происходит обновление феромонных значений
(возможно также необязательное обновление феромона перед запуском алгоритма
Н-метода). В завершение итерации алгоритма выполняются действия демона
(необязательно). Описанные действия, начиная с этапа построения решений, по-
вторяются до выполнения условий останова алгоритма ОМК. Алгоритм возвра-
щает наилучшее найденное решение .x
procedure ОМК-H()
ИнициализацияФеромонныхЗначений(T );
x* := ПустоеРешение();
f (x*) := ;
repeat
S := ø;
for i:=1 to r do
s := ПостроениеМуравьямиРешения (T );
if ДопустимоеРешение(s) then
ТраекторныйМетод (s);
if f (x*) > f (s) then
x* := s;
end if
S := S {s};
end if
end for;
if выполняется условие передачи управления then
ОбновлениеФеромонныхЗначений(T, S, x*); {необязательно}
H(S, x*);
end if
ОбновлениеФеромонныхЗначений(T, S, x*);
ДействияДемона(); {необязательно}
until не выполняется условие завершения;
return x* ;
end procedure
Рис. 2
Процедуры ПостороениеМуравьямиРешения, ОбновлениеФеромонныхЗначе-
ний и ДействияДемона являются стандартными процедурами общего алгоритма
ОМК [3].
Разработано следующее адаптивное условие возврата управления от Н-ме-
тода к ОМК. Алгоритм Н-метода переключается между двумя возможными со-
стояниями — нормальным режимом и пробным. Пробный режим характеризуется
более «слабым» условием завершения. Алгоритм Н-метода переключается
в пробный режим в случае, если он не находит улучшения рекорда своей началь-
ной популяции. Это позволяет уменьшить количество безрезультатных запусков
алгоритма Н-метода и дает возможность алгоритму ОМК исследовать простран-
ство поиска более эффективно. Если алгоритм Н-метода находит улучшение, он
возвращается в нормальный режим работы.
С точки зрения структуры, данное комбинирование агрегирует такие две аль-
тернативы. С одной стороны, ОМК выступает генератором начальных популяций
для Н-метода (рис. 3, а). С другой стороны, Н-метод выступает в качестве услож-
ненной процедуры демона (вместо обычно используемых алгоритмов локально-
го поиска) для улучшения решений, построенных муравьями (рис. 3, б). В зави-
симости от соотношения условий передачи управления между базовыми алго-
ритмами при реализации ОМК-Н он может быть более близок к тому или
другому исходному методу.
Международный научно-технический журнал
Проблемы управления и информатики, 2010, № 4 35
Инициализация
ОМК
Построение
решений
Обновление
феромона
ОМК
H-метод
Завершение
работы?
Завершение
Действия демона
Нет
Да
Действия демона
ОМК
Построение
решений
Обновление
феромона
H-метод
а б
Рис. 3
Описанный алгоритм разработан для статических задач КО. Применение
данного подхода к динамическим задачам требует дальнейшего развития метаэв-
ристики ОМК-Н с учетом уже полученных результатов применения алгоритмов
ОМК к динамическим задачам.
Обоснуем целесообразность предложенного комбинирования. Во-первых,
оба базовых метода представляют два принципиально отличных подхода иссле-
дования пространства решения: ключевой идеей ОМК является многоагентный
поиск, а в основе Н-метода лежит использование глобального сканирования про-
странства решений. Во-вторых, предложенное объединение согласовано с идеоло-
гией обоих методов. Поэтому комбинирование этих метаэвристических концеп-
ций потенциально повышает вероятность нахождения более точных решений.
При параллельной реализации возможна организация более сложного взаи-
модействия базовых методов — ОМК и Н-метода. Разработка и исследование
параллельных комбинированных метаэвристических методов на основе ОМК
и Н-метода — одно из важных направлений дальнейших исследований.
3. Сходимость метода ОМК-Н
Опишем формально, с использованием понятия комбинаторного объекта,
предложенного в [32], постановку задач КО.
Рассмотрим задачу нахождения Xx
такого, что
),(minArg
*
xfx
XDx
где X — конечное пространство решений задачи, элементами которого являются
комбинаторные объекты, XD — подпространство допустимых решений задачи,
которое определяется ограничениями задачи, 1R: Xf — целевая функция задачи.
Под комбинаторным объектом будем понимать гомоморфизм ,
~
: XY ко-
торый удовлетворяет системе ограничений, заданной некоторым предикатом ,
где ,,}...,,1{ mmY а nzzX n},...,,{
~
1 — некоторое конечное множество
с заданным строгим линейным порядком, именуемым впредь базовым, — мно-
жество натуральных чисел.
Муравьи в алгоритме ОМК осуществляют поиск в расширенном относитель-
но Х пространстве задачи S, которое формально опишем так:
,
,...,1
i
mi
XS
.,1...,,1}},...,,1{,
~
:{ XXmiiYXYX mii
i
i
36 ISSN 0572-2691
Здесь i — комбинаторный объект, который удовлетворяет некоторой системе
ограничений, описанной предикатом i (определяется условиями задачи), и име-
ют место такие условия: 1) ,1 ii
mi ...,,2 (под понимается отношение
импликации); 2) .m
Будем считать, что на пространстве S определена система окрестностей
||2: SSN :
.если,
;1...,,2,если,:
)(
1
1
11
1
m
i
ii
Y
i
i
i
XsX
miXsX
sN i
Для задач КО в таком представлении исследуем вопрос сходимости алгорит-
мов ОМК-Н. Одним практически важным типом сходимости стохастических
алгоритмов является сходимость по значению, которая означает, что алгоритм
гарантировано найдет, по крайней мере, одно оптимальное решение с вероятно-
стью, которая может быть близкой к 1, при наличии достаточного времени.
В работе [3], в частности, показана сходимость по значению для алгоритмов ОМК
класса .ACO
minbs, Покажем, что гибридизация алгоритмов ОМК этого класса
с модифицированным Н-методом в методе ОМК-Н приводит к алгоритмам, схо-
дящимся по значению.
Не ограничивая общности, будем считать, что феромонные значения T в ба-
зовом алгоритме ОМК — это матрица, каждый элемент которой ассоциируется
с парой элементов базового пространства },...,1{,)(:
~
njizz ji
TX (для других слу-
чаев описание класса алгоритмов и доказательство сходимости осуществляется
аналогичным способом). В дальнейшем величину ,,)(,)( iijxix Xx
ji
,jj Xx
когда это не будет вызывать двусмысленности, будем обозначать .
ji xx Также
предположим, что для каждой пары Xzz ji
~
, определено значение ,
ji zz кото-
рое отображает эвристическую информацию о задаче, причем ],,[ maxmin
ji zz
где .0 maxmin Аналогично предыдущему, когда это не будет вызывать
двусмысленности, вместо ,)(,)( jxix ji
jjii XxXx , будем писать .
jixx
Рассмотрим класс ОМК-
min
H алгоритмов метода ОМК-Н, который обладает
такими свойствами:
1) все феромонные значения ограничены снизу положительной величиной
;0min
2) имеется испарение феромона с показателем ;10
3) построение решений муравьями осуществляется по такому правилу: от ча-
стичного решения ,1...,,1, miXx ii они переходят к частичному (или пол-
ному, если )1 mi решению 11 ii Xx с вероятностью
случае, противном в0
),(если,
),(
),(
)(
1
)(
1
11
ii
xxxx
xNx
xxxx
ii
xNx
F
F
xxP jiji
ij
iiii
(2)
где ),( F — некоторая неубывающая и монотонная по первой переменной
функция;
Международный научно-технический журнал
Проблемы управления и информатики, 2010, № 4 37
4) объем феромона, который произвольный муравей может добавить в тече-
ние итерации, ограниченный некоторой величиной .τ0
Отметим, что условия 2)–4) свойственны большинству алгоритмов ОМК,
которые могут выступать базовыми при разработке алгоритма ОМК-Н. В рабо-
те [3] показано, что условие 1) имеет место для таких практически важных ал-
горитмов ОМК, как ММАS [3, 33] и ACS [3]. Следовательно, ограничения
класса ОМК-
min
H позволяют использовать большинство алгоритмов ОМК как
базовые. Ограничения на Н-метод, как базовый, в классе ОМК-
min
H отсутствуют.
Аналогично [4] докажем, что алгоритмы этого класса сходятся по значению.
Теорема. Пусть )θ(p — вероятность того, что алгоритм класса ОМК-
min
H
найдет оптимальное решение, по крайней мере, один раз в течение первых ите-
раций. Тогда имеет место .1)(lim
p
Доказательство. Максимально возможный объем феромона, который мо-
жет быть добавлен муравьями к произвольному значению
ji zz в течение про-
извольной итерации, составляет .τr Понятно, что максимально возможное зна-
чение феромона на итерации 1 составляет τ)1( 0 r , на итерации 2 —
ττ)1()1( 0
2 rr и так далее. Следовательно, путем испарения феромона
феромонные значения на итерации θ ограничены сверху величиной
.τ)1()1()( 1
1
0
max
r
i
Поскольку ,10 эта сумма совпадает асимптотически с /τmax r От-
сюда следует что феромонные значения на произвольной итерации ограничены
величинами min и .max
Поскольку функция ),( F монотонна по первому аргументу, то для ,iz
Xz j
~
имеет место соотношение
,),( maxmin FFF
jiji zzzz
где ),,(min min
},...,1{,
min jizz
nji
FF
).,(max max
},...,1{,
max jizz
nji
FF
Благодаря этому можно гарантировать, что каждый допустимый выбор по
правилу (2) осуществляется с вероятностью .0min p
Тривиальный нижний предел для minp составляет
.
)1( minmax
min
minmin
FFn
F
pp
Следовательно, произвольное решение, в частности оптимальное, может
быть сгенерировано с вероятностью .0min rpp
Поскольку достаточно, чтобы
лишь один муравей сгенерировал оптимальное решение, то нижний предел )(p
для )(* p составляет
.)1(1)θ( θ* pp
Отсюда имеем .1)(lim *
θ
p
Теорема доказана.
38 ISSN 0572-2691
Полученные результаты не предоставляют информации о скорости сходимо-
сти алгоритмов метода ОМК-Н. Исследование скорости сходимости — важное
направление дальнейших теоретических исследований. Другим направлением
возможного развития исследования является экспериментальное сравнение алго-
ритмов ОМК-Н, принадлежащих классу ОМК- ,H
min с алгоритмами, которые
этому классу не принадлежат.
4. Вычислительный эксперимент
Поскольку теоретическое исследование алгоритмов КО крайне редко позво-
ляет получать практически значимые результаты, принято анализировать показа-
тели эффективности путем проведения вычислительных экспериментов. С этой
целью обычно используют «классические» модели КО — такие как задача комми-
вояжера (ЗК) [1]. Для проведения вычислительного эксперимента, кроме ЗК, была
выбрана еще одна NP-трудная задача — многомерная задача о назначении (МЗН).
Кратко, 3-мерный вариант этой задачи можно описать как «минимизацию сум-
марной стоимости назначения объектов на позиции в моменты времени» [23].
В вычислительном эксперименте по решению серии ЗК предложенный под-
ход сравнивался с реализованным алгоритмом Н-метода для ЗК и одним из
наиболее эффективных алгоритмов ОМК для решения ЗК — алгоритмом MMAS
[33], реализация которого взята из пакета ACOTSP [34]. На основе предваритель-
ного анализа выбраны такие значения параметров Н-метода: количество точек те-
кущей популяции составляло 25, на каждой итерации порождалось шесть новых
точек; d-отрезки строились на основе транспозиционной метрики. Независимый
алгоритм Н-метода перезапускался в случае, если на протяжении 75 итераций не
было найдено улучшения текущего рекорда. В качестве траекторного алгоритма
взята реализация алгоритма 3-opt [1] из пакета ACOTSP. В алгоритме MMAS ко-
личество муравьев составляло 25, коэффициент испарения феромона 0,5, в
псевдослучайном пропорциональном правиле выбора [3], которое применяли му-
равьи при построении решений, были такие значения параметров: 1, = 2. В
качестве деятельности демона в алгоритме MMAS ко всем построенным муравья-
ми решениям применялся алгоритм 3-opt. Параметрам алгоритма ОМК-Н были
присвоены те же значения, что и у базовых методов. Передача управления осу-
ществлялась после каждых 25 итераций алгоритма MMAS. Алгоритм Н-метода в
ОМК-Н останавливался в случае 75 итераций без улучшения в нормальном режи-
ме и после 25 итераций в пробном режиме.
В табл. 1–3 приведены результаты 20 вариантов решения ЗК, взятых из
Интернет-библиотеки TSPLIB [35]. Здесь число в названии задачи обозначает
ее размерность, tlim — ограничение на время работы алгоритма, bf — лучшее
найденное соответствующим алгоритмом значение целевой функции,
** /)(100 fffavg avgf( — усредненное по 20 попыткам значение
наилучшего найденного решения) — средняя относительная погрешность ал-
горитма (%), t — среднее время, на протяжении которого алгоритмом было
найдено лучшее решение на ПЭВМ класса Pentium Core Duo 2 ГГц (с). В про-
цессе эксперимента использовалось только одно ядро процессора. Ограничения
по времени выбирались таким образом, чтобы алгоритм MMAS мог выполнить
как минимум две тысячи итераций на ЗК и 200 на МЗН. Алгоритмы были реа-
лизованы с использованием языка ANSI C++.
Для проверки достоверности результатов использовался критерий суммы
рангов Уилкоксона c коррекцией вероятности ошибки множественных сравнений
по методу Холма–Бонферрони. Лучшие результаты в табл. 1–3 обозначены полу-
жирным, статистически отличающиеся результаты — курсивом. Все тесты прово-
дились с уровнем значимости 5 %.
Международный научно-технический журнал
Проблемы управления и информатики, 2010, № 4 39
Таблица 1
Задача c,limt bf
MMAS ОМК-H H-метод
lin318 75 42029 42029 42029
d493 100 35002 35002 35002
att532 100 27686 27686 27686
ali535 100 202339 202339 202339
p654 100 34649 34643 34643
d657 100 48913 48913 48920
rat783 150 8806 8806 8809
pr1002 200 259045 259045 259128
u1060 200 224210 224147 224245
vm1084 200 239297 239297 239328
pcb1173 225 56896 56892 56918
d1291 250 50801 50801 50801
pr2392 350 378191 378065 379180
Таблица 2
Задача c,limt , %
MMAS ОМК-H H-метод
lin318 75 0,000 0,000 0,000
d493 100 0,014 0,011 0,007
att532 100 0,018 0,020 0,043
ali535 100 0,008 0,003 0,065
p654 100 0,049 0,008 0,016
d657 100 0,074 0,034 0,065
rat783 150 0,034 0,017 0,091
pr1002 200 0,122 0,020 0,136
u1060 200 0,241 0,071 0,156
vm1084 200 0,009 0,015 0,042
pcb1173 225 0,042 0,047 0,258
d1291 250 0,006 0,015 0,082
pr2392 350 0,222 0,217 0,494
Таблица 3
Задача c,limt T, с
MMAS ОМК-H H-метод
lin318 75 8,01 7,95 4,36
d493 100 58,86 49,62 37,86
att532 100 52,76 43,09 62,23
ali535 100 44,85 36,41 28,04
p654 100 71,56 46,84 68,94
d657 100 45,14 51,96 92,56
rat783 150 60,13 57,90 40,63
pr1002 200 151,65 128,40 155,23
u1060 200 154,22 146,67 75,07
vm1084 200 109,15 101,19 111,67
pcb1173 225 118,33 124,00 132,01
d1291 250 82,81 73,86 154,34
pr2392 350 306,44 279,91 323,43
Для проведения вычислительного эксперимента по решению МЗН были реа-
лизованы: Н-метод, вариант алгоритма MMAS и разработанный алгоритм ОМК-Н.
Детали реализации алгоритма MMAS для МЗН следующие. Феромонные значе-
ния ассоциировались с позициями элементов в перестановках по измерениям
и эвристическая информация (данные задачи) не использовалась. Муравьи кон-
струировали решения, присваивая элементы на позиции в каждом измерении
(списки близости компонент при этом не использовались). Испарение применя-
лось ко всем феромонным значениям. Обновление феромона, вычисление феро-
монных границ и реинициализация феромонных значений были реализованы так
же, как в стандартном алгоритме MMAS для ЗК. Параметрам всех сравниваемых
методов были присвоены те же значения, что и в эксперименте по решению ЗК.
40 ISSN 0572-2691
В качестве траекторного алгоритма использовался детерминированный ло-
кальный поиск с окрестностями, построенными с использованием транспозици-
онной метрики (расстояние суммировалось по всем измерениям). Эта же метрика
использовалась при построении отрезков в Н-методе.
Реализованная процедура построения решений в ОМК вычислительно слож-
ная. Поэтому в целях увеличения количества итераций алгоритма ОМК в гибрид-
ной метаэвристике алгоритм Н-метода прекращал работу в случае отсутствия
улучшения на протяжении 35 итераций. Кроме того, Н-метод запускался после
каждой итерации алгоритма ОМК. Независимый алгоритм Н-метода перезапус-
кался, как в случае ЗК, после 75 итераций без улучшения.
В табл. 4 отображены усредненные результаты 20 вариантов решения МЗН
(с известными уникальными оптимальными решениями), полученных с помощью
генератора задач МЗН, предложенного в работе [23]. В дополнение к прежним
обозначениям здесь в названии задачи число после символа d обозначает ко-
личество измерений в задаче, а число после символа n — размерность каждого
измерения.
Таблица 4
Задача c,limt
bf , % T, с
MMAS ОМК-H
H-
метод
MMAS ОМК-H
H-
метод
MMAS ОМК-H
H-
метод
n5d5prob1 20 26 26 26 1,15 0,77 0,38 2,36 5,10 5,17
n10d5prob2 25 53 53 53 1,92 1,92 1,92 1,605 0,2 0,34
n3d10prob1 25 13 13 13 3,46 0,38 0,38 1,47 8,08 5,12
n20d5prob1 30 105 105 105 2,36 1,97 2,16 9,57 11,58 10,84
n100d3prob1 50 522 519 522 11,59 10,90 11,65 40,59 25,12 26,93
n100d3prob2 50 529 528 529 11,18 10,64 11,02 24,09 25,41 29,04
Лучшие результаты в табл. 4 обозначены полужирным. Результаты решения
МЗН также проверялись на статистическую значимость и статистические отлича-
ющиеся средние отклонения от оптимума обозначены курсивом.
В целом задачи МЗН по сравнению с ЗК оказались более сложными для всех
алгоритмов.
Как свидетельствуют результаты вычислений, во всех задачах, которые ис-
пользовались в исследовании, ОМК-H показал в среднем лучшие по точности
результаты (либо статистически одинаковые). В то же время наблюдается тенден-
ция к падению эффективности гибридного алгоритма по сравнению с базовым ро-
стом размерности задач ЗК. Время работы при этом было сравнимым.
Заключение
Предложен гибридный метаэвристический метод решения задач КО ОМК-H,
который базируется на двух популяционных методах — оптимизации муравьи-
ными колониями и Н-методе. Разработанный подход показал свою эффективность
при экспериментальном исследовании. Комбинирование стратегий поиска, согла-
сованное со структурой базовых методов, позволило достичь лучших показателей
эффективности при решении ряда задач КО. Именно достижение повышения эф-
фективности предложенного метода по сравнению с базовыми методами является
важным, поскольку цель заключалась в разработке и исследовании подхода, кото-
рый мог бы использоваться для решения широкого круга задач КО. Отметим, что
разработка эффективных алгоритмов решения ЗК и МЗН, ввиду широкого круга
их практических применений и сложности, — также важное направление иссле-
дований. Негативным эффектом, который проявился при проведении вычисли-
тельных экспериментов по решению ЗК, является снижение эффективности
в среднем алгоритма ОМК-H относительно базовых методов при возрастании
размерности задачи.
Международный научно-технический журнал
Проблемы управления и информатики, 2010, № 4 41
Получены условия, которые гарантируют сходимость по значению к гло-
бальному оптимальному решению задачи. В то же время полученные результаты
ничего не говорят о скорости сходимости алгоритмов метода.
Важной целью дальнейших исследований может стать экспериментальное
сравнение предложенного подхода с другими приближенными методами КО,
а также получение теоретических оценок трудоемкости алгоритмов метода, пред-
назначенных для решения конкретных классов задач КО. Целесообразно также
исследовать вопросы эффективной реализации алгоритмов ОМК-H на многопро-
цессорных вычислительных системах.
Л.Ф. Гуляницький, С.І. Сіренко
МЕТАЕВРИСТИЧНИЙ МЕТОД
КОМБІНАТОРНОЇ ОПТИМІЗАЦІЇ ОМК-Н
Запропоновано гібридний метаевристичний метод комбінаторної оптимізації
ОМК-Н, який базується на двох популяційних підходах — алгоритмах оптимі-
зації мурашиними колоніями і Н-методі. Отримано умови, що визначають збіж-
ність за значенням до оптимального розв’язку задачі. Ефективність алгоритмів
методу ілюструють результати обчислювального експерименту з розв’язання
низки відомих задач комбінаторної оптимізації.
L.F. Hulianytskyi, S.I. Sirenko
ACO-Н — METAHEURISTIC
COMBINATORIAL OPTIMIZATION METHOD
A metaheuristic method ACO-Н for combinatorial optimization problems is pro-
posed, which is based on two population methods — ant colony optimization
and H-method. A convergence in value to an optimal solution for a class of method’s
algorithms is shown. The experiment conducted on a number of combinatorial opti-
mization problems shows efficiency of the proposed approach of combining ACO
and H-method.
1. Hoos H.H., Stьtzle T. Stochastic local search: foundations and applications. — San Francisco :
Morgan Kaufmann Publ., 2005. — 658 p.
2. Гуляницкий Л., Сиренко С. Комбинирование алгоритмов оптимизации муравьиными коло-
ниями и Н-метода // International Book Series «Information science & computing» (Eds.
K. Markov, K. Ivanova, S. Mitov). — Sofia : ITHEA, 2008. — 15, N 3. — P. 95–102.
3. Dorigo M., Stützle T. Ant colony optimization. — Cambridge, (MA) : MIT Press, 2004. — 348 p.
4. Гуляницкий Л.Ф., Сергиенко И.В. Метаэвристический метод деформированного многогран-
ника в комбинаторной оптимизации // Кибернетика и системный анализ. — 2007. — № 6. —
С. 70–79.
5. Dorigo M., Gambardella L.M. An ant colony system hybridized with a new local search for the
sequential ordering problem // J. Computing. — 2000. — 12, N 3. — P. 237–255.
6. Chen C.-H., Ting C.-J., Chang P.-C. Applying a hybrid ant colony system to the vehicle routing
problem // Lect. Notes Computer Sci. (Eds. O. Gervasi, M.L. Gavrilova, V. Kumar et al.). —
Heidelberg : Springer, 2005. — 3483. — P. 417–426.
7. Гуляницький Л.Ф., Сіренко С.І. Про наближені методи комбінаторної оптимізації та їх за-
стосування до задачі комівояжера // Abstract of Int. Conf. «Problems of Decision Making un-
der Uncertainties (PDMU–2005)» (Sept. 12–17, 2005, Berdyansk, Ukraine). — Kyiv, 2005. —
P. 138–139.
8. Lourenço H.R., Serra D. Adaptive approach heuristics for the generalized assignment problem:
(Techn. rep.) / Univ. Pompeu Fabra. — Economic Working Papers Series No. 288. — Pompeu,
1998. — 20 p.
9. Pellegrini P., Moretti E. A Computational analysis on a hybrid approach: Quick-and-dirty ant
colony optimization // Appl. Mathemat. Scie. — 2009. — 23, N 3. — P. 1127–1140.
10. Reimann M., Shtovba S., Nepomuceno E. A hybrid ACO-GA approach to solve Vehicle Routing
Problems // Tech. rep., Student Papers of the Complex Systems Summer School, Budapest, July
15–August 9, 2001. — Santa Fe Institute, 2001. — 8 p.
42 ISSN 0572-2691
11. Acan A. GAACO: A GA + ACO hybrid for faster and better search capability // Lect. Notes
Comput. Scie. (Eds. M. Dorigo, G. Di Caro, M. Sampels). — Heidelberg : Springer, 2002. —
2463. — P. 15–26.
12. Lee Z.-J., Lee C.-Y., Su S.-F. An immunity based ant colony optimization algorithm for solving
weapon-target assignment problem // Appl. Soft Comput. — 2002. — 2. — P. 39–47.
13. Bouhafs L., Hajjam A., Koukam A. A hybrid ant colony system approach for the capacitated vehi-
cle routing problem // Lect. Notes Comput. Scie. (Eds. M. Dorigo, M. Birattari, M. Blum,
L.M. Gambardella, F. Mondada, T. Stьtzle). — Heidelberg : Springer, 2004. — 3172. —
P. 414–415.
14. Blum C. Beam-ACO: hybridizing ant colony optimization with beam search: an application to
open shop scheduling // Comput. and Oper. Res. — 2005. — 32, N 6. — P. 1565–1591.
15. Duan H., Yu X. Hybrid ant colony optimization using memetic algorithm for traveling salesman
problem // Proc. IEEE Intern. Symp. on Approximate Dynamic Programming and Reinforcement
Learning. — New York : IEEE press, 2007. — P. 92–95.
16. An efficient hybrid algorithm for resource-constrained project scheduling / W. Chen, Y.-J. Shi,
H.-F. Teng et al. // Inform. Scie. — 2010. — 180. — P. 1031–1039.
17. Zhang X., Tang L. A new hybrid ant colony optimization algorithm for the traveling salesman
problem // Lect. Notes Artificial Intelligence (Eds. D.-S. Huang, D.C. Wunsch, D.S. Levine
et al.). — Heidelberg : Springer, 2008. — 5227. — P. 148–155.
18. Kaveh A., Talatahari S. A discrete particle swarm ant colony optimization for design of steel
frames // Asian J. of Civil Engineer. — 2008. — 9. — P. 563–575.
19. Zhou P., Deng Q. Hybridizing fast taboo search with ant colony optimization algorithm for solv-
ing large scale permutation flow shop scheduling problem // Proc. 5th IEEE Intern. Conf. on
Granular Comput. — New York: IEEE press, 2009. — P. 809–813.
20. Ayob M., Jaradat G. Hybrid ant colony systems for course timetabling problems // Proc. 2nd
Conf. on Data Mining and Optimization. — Malaysia : Universiti Kebangsaan, 2009. —
P. 120–126.
21. Lee C.-Y., Lee Z.-J., Lin S.-W., Ying K.-C. An enhanced ant colony optimization (EACO) applied
to capacitated vehicle routing problem // Appl. Intelligence. — 2010. — 32, N 1. — P. 88–95.
22. Гобов Д.А. Про одну модифікацію Н-методу // Пр. Міжн. симпозіуму «Питання оптимізації
обчислень (ПОО–ХХХV)», (24–29 вересня, 2009 р., смт. Кацівелі, Крим,). — К. : ІК НАН
України, 2009. — 1. — С. 146–150.
23. Grundel D.A., Pardalos P.M. Test problem generator for the multidimensional assignment prob-
lem // Comput. Optimizat. and Appl. — 2005. — 30, N 2. — P. 133–146.
24. Lourenço H.R., Martin O., Stützle T. Iterated local search // Handbook of metaheuristics (Eds.
F. Glover, G. Kochenberger). — Norwell, (MA): Kluwer Academ. Publ., 2002. — P. 321–353.
25. Leguizamon G., Blum C., Alba E. Evolutionary computation // Handbook of approximation algo-
rithms and metaheuristics (Ed. T.F. Gonzalez). — Boca Raton, (FL) : CRC press, 2007. —
P. 372–386.
26. Гуляницкий Л.Ф. Метод деформаций в дискретной оптимизации // Исследование операций
и АСУ. — 1989. — № 34. — С. 30–33.
27. Glover F. Genetic algorithms and scatter search: unsuspected potentials // Statist. and Comput. —
1994. — 4, N 2. — P. 131–140.
28. Glover F. Tabu search for nonlinear and parametric optimization (with links to genetic algo-
rithms) // Discrete Appl. Mathemat. — 1994. — 49, N 1–3. — P. 231–255.
29. Glover F. A template for scatter search and path relinking // Lect. Notes Computer Sci. (Eds.
J.-K. Hao, E. Lutton, E. Ronald et al.). — Heidelberg : Springer, 1997. — 1363. — P. 13–54.
30. Гуляницький Л.Ф. Один гібридний алгоритм комбінаторної оптимізації // Abstract of Int.
Ukrainian-Polish Workshop «Problems of Stochastic and Discrete Optimization» (May 10–15,
2005, Kaniv, Ukraine). — Kaniv, 2005. — P. 63–65.
31. Moraglio A., Poli R. Topological interpretation of crossover // Lect. Notes Comput. Scie. (Eds.
K. Deb et. al.). — Heidelberg : Springer, 2004. — 3102. — P. 1377–1388.
32. Гуляницкий Л.Ф. До формалізації та класифікації задач комбінаторної оптимізації // Теорія
оптимальних рішень. — 2008. — № 7. — С. 45–49.
33. Stützle T., Hoos H. Max–min ant system // Future Generation Comput. Systems. — 2000. — 16,
N 8. — P. 889–914.
34. Stützle T. ACOTSP, Version 1.0. — 2004. — // http://www.aco-metaheuristic.org/aco-code.
35. TSPLIB. — // http://comopt.ifi.uni-heidelberg.de/software/TSPLIB95/.
Получено 01.02.2010
После доработки 20.04.2010
|
| id | nasplib_isofts_kiev_ua-123456789-210744 |
| institution | Digital Library of Periodicals of National Academy of Sciences of Ukraine |
| issn | 0572-2691 |
| language | Russian |
| last_indexed | 2026-03-13T11:23:54Z |
| publishDate | 2010 |
| publisher | Інститут кібернетики ім. В.М. Глушкова НАН України |
| record_format | dspace |
| spelling | Гуляницкий, Л.Ф. Сиренко, С.И. 2025-12-16T22:47:27Z 2010 Метаэвристический метод комбинаторной оптимизации ОМК-Н / Л.Ф. Гуляницкий, С.И. Сиренко // Проблемы управления и информатики. — 2010. — № 4. — С. 31-42. — Бібліогр.: 35 назв. — рос. 0572-2691 https://nasplib.isofts.kiev.ua/handle/123456789/210744 519.8 10.1615/JAutomatInfScien.v42.i7.20 Запропоновано гібридний метаевристичний метод комбінаторної оптимізації ОМК-Н, який базується на двох популяційних підходах — алгоритмах оптимізації мурашиними колоніями і Н-методі. Отримано умови, що визначають збіжність за значенням до оптимального розв’язку задачі. Ефективність алгоритмів методу ілюструють результати обчислювального експерименту з розв’язання низки відомих задач комбінаторної оптимізації. A metaheuristic method ACO-Н for combinatorial optimization problems is proposed, which is based on two population methods — ant colony optimization and H-method. A convergence in value to an optimal solution for a class of method’s algorithms is shown. The experiment conducted on a number of combinatorial optimization problems shows efficiency of the proposed approach of combining ACO and H-method. ru Інститут кібернетики ім. В.М. Глушкова НАН України Проблемы управления и информатики Оптимальное управление и методы оптимизации Метаэвристический метод комбинаторной оптимизации ОМК-Н Метаевристичний метод комбінаторної оптимізації ОМК-Н ACO-Н — metaheuristic combinatorial optimization method Article published earlier |
| spellingShingle | Метаэвристический метод комбинаторной оптимизации ОМК-Н Гуляницкий, Л.Ф. Сиренко, С.И. Оптимальное управление и методы оптимизации |
| title | Метаэвристический метод комбинаторной оптимизации ОМК-Н |
| title_alt | Метаевристичний метод комбінаторної оптимізації ОМК-Н ACO-Н — metaheuristic combinatorial optimization method |
| title_full | Метаэвристический метод комбинаторной оптимизации ОМК-Н |
| title_fullStr | Метаэвристический метод комбинаторной оптимизации ОМК-Н |
| title_full_unstemmed | Метаэвристический метод комбинаторной оптимизации ОМК-Н |
| title_short | Метаэвристический метод комбинаторной оптимизации ОМК-Н |
| title_sort | метаэвристический метод комбинаторной оптимизации омк-н |
| topic | Оптимальное управление и методы оптимизации |
| topic_facet | Оптимальное управление и методы оптимизации |
| url | https://nasplib.isofts.kiev.ua/handle/123456789/210744 |
| work_keys_str_mv | AT gulânickiilf metaévrističeskiimetodkombinatornoioptimizaciiomkn AT sirenkosi metaévrističeskiimetodkombinatornoioptimizaciiomkn AT gulânickiilf metaevrističniimetodkombínatornoíoptimízacííomkn AT sirenkosi metaevrističniimetodkombínatornoíoptimízacííomkn AT gulânickiilf aconmetaheuristiccombinatorialoptimizationmethod AT sirenkosi aconmetaheuristiccombinatorialoptimizationmethod |