Гибридная метаэвристика, основанная на оптимизации муравьиными колониями и Н-методе
Предлагается метаэвристический метод комбинаторной оптимизации, который базируется на двух популяционных подходах – алгоритмах оптимизации муравьиными колониями и Н-метода. Этот метод предназначен для решения широкого круга задач комбинаторной оптимизации. Его эффективность проиллюстрирована на осно...
Gespeichert in:
| Datum: | 2009 |
|---|---|
| Hauptverfasser: | , |
| Format: | Artikel |
| Sprache: | Russian |
| Veröffentlicht: |
Інститут кібернетики ім. В.М. Глушкова НАН України
2009
|
| Schlagworte: | |
| Online Zugang: | https://nasplib.isofts.kiev.ua/handle/123456789/6258 |
| Tags: |
Tag hinzufügen
Keine Tags, Fügen Sie den ersten Tag hinzu!
|
| Назва журналу: | Digital Library of Periodicals of National Academy of Sciences of Ukraine |
| Zitieren: | Гибридная метаэвристика, основанная на оптимизации муравьиными колониями и Н-методе / Л.Ф. Гуляницкий, С.И. Сиренко // Компьютерная математика. — 2009. — № 1. — С. 142-151. — Бібліогр.: 19 назв. — рос. |
Institution
Digital Library of Periodicals of National Academy of Sciences of Ukraine| id |
nasplib_isofts_kiev_ua-123456789-6258 |
|---|---|
| record_format |
dspace |
| spelling |
Гуляницкий, Л.Ф. Сиренко, С.И. 2010-02-22T12:41:52Z 2010-02-22T12:41:52Z 2009 Гибридная метаэвристика, основанная на оптимизации муравьиными колониями и Н-методе / Л.Ф. Гуляницкий, С.И. Сиренко // Компьютерная математика. — 2009. — № 1. — С. 142-151. — Бібліогр.: 19 назв. — рос. ХХХХ-0003 https://nasplib.isofts.kiev.ua/handle/123456789/6258 519.21 Предлагается метаэвристический метод комбинаторной оптимизации, который базируется на двух популяционных подходах – алгоритмах оптимизации муравьиными колониями и Н-метода. Этот метод предназначен для решения широкого круга задач комбинаторной оптимизации. Его эффективность проиллюстрирована на основе результатов вычислительного эксперимента по решению ряда известных задач комбинаторной оптимизации. Пропонується метаевристичний метод комбінаторної оптимізації, який базується на двох популяційних підходах – алгоритмах оптимізації мурашиними колоніями та Н-методу. Цей метод призначений для розв’язання широкого кола задач комбінаторної оптимізації. Ефективність запропонованого підходу проілюстрована на основі результатів обчислювального експерименту з розв’язання ряду задач комбінаторної оптимізації. A metaheuristic method for solving combinatorial optimization problems is proposed, which is based on two population methods – ant colony optimization and H-method. The method is applicable to a wide range of combinatorial optimization problems. The efficiency of the approach proposed is illustrated by numerical experiment on solving well-known combinatorial optimization problems. ru Інститут кібернетики ім. В.М. Глушкова НАН України Теория и методы оптимизации Гибридная метаэвристика, основанная на оптимизации муравьиными колониями и Н-методе Гібридна метаевристика, що заснована на оптимізації мурашиними колоніями і Н-методі Hybrid metaheuristic based on ant colony optimization and H-method Article published earlier |
| institution |
Digital Library of Periodicals of National Academy of Sciences of Ukraine |
| collection |
DSpace DC |
| title |
Гибридная метаэвристика, основанная на оптимизации муравьиными колониями и Н-методе |
| spellingShingle |
Гибридная метаэвристика, основанная на оптимизации муравьиными колониями и Н-методе Гуляницкий, Л.Ф. Сиренко, С.И. Теория и методы оптимизации |
| title_short |
Гибридная метаэвристика, основанная на оптимизации муравьиными колониями и Н-методе |
| title_full |
Гибридная метаэвристика, основанная на оптимизации муравьиными колониями и Н-методе |
| title_fullStr |
Гибридная метаэвристика, основанная на оптимизации муравьиными колониями и Н-методе |
| title_full_unstemmed |
Гибридная метаэвристика, основанная на оптимизации муравьиными колониями и Н-методе |
| title_sort |
гибридная метаэвристика, основанная на оптимизации муравьиными колониями и н-методе |
| author |
Гуляницкий, Л.Ф. Сиренко, С.И. |
| author_facet |
Гуляницкий, Л.Ф. Сиренко, С.И. |
| topic |
Теория и методы оптимизации |
| topic_facet |
Теория и методы оптимизации |
| publishDate |
2009 |
| language |
Russian |
| publisher |
Інститут кібернетики ім. В.М. Глушкова НАН України |
| format |
Article |
| title_alt |
Гібридна метаевристика, що заснована на оптимізації мурашиними колоніями і Н-методі Hybrid metaheuristic based on ant colony optimization and H-method |
| description |
Предлагается метаэвристический метод комбинаторной оптимизации, который базируется на двух популяционных подходах – алгоритмах оптимизации муравьиными колониями и Н-метода. Этот метод предназначен для решения широкого круга задач комбинаторной оптимизации. Его эффективность проиллюстрирована на основе результатов вычислительного эксперимента по решению ряда известных задач комбинаторной оптимизации.
Пропонується метаевристичний метод комбінаторної оптимізації, який базується на двох популяційних підходах – алгоритмах оптимізації мурашиними колоніями та Н-методу. Цей метод призначений для розв’язання широкого кола задач комбінаторної оптимізації. Ефективність запропонованого підходу проілюстрована на основі результатів обчислювального експерименту з розв’язання ряду задач комбінаторної оптимізації.
A metaheuristic method for solving combinatorial optimization problems is proposed, which is based on two population methods – ant colony optimization and H-method. The method is applicable to a wide range of combinatorial optimization problems. The efficiency of the approach proposed is illustrated by numerical experiment on solving well-known combinatorial optimization problems.
|
| issn |
ХХХХ-0003 |
| url |
https://nasplib.isofts.kiev.ua/handle/123456789/6258 |
| citation_txt |
Гибридная метаэвристика, основанная на оптимизации муравьиными колониями и Н-методе / Л.Ф. Гуляницкий, С.И. Сиренко // Компьютерная математика. — 2009. — № 1. — С. 142-151. — Бібліогр.: 19 назв. — рос. |
| work_keys_str_mv |
AT gulânickiilf gibridnaâmetaévristikaosnovannaânaoptimizaciimuravʹinymikoloniâmiinmetode AT sirenkosi gibridnaâmetaévristikaosnovannaânaoptimizaciimuravʹinymikoloniâmiinmetode AT gulânickiilf gíbridnametaevristikaŝozasnovananaoptimízacíímurašinimikoloníâmiínmetodí AT sirenkosi gíbridnametaevristikaŝozasnovananaoptimízacíímurašinimikoloníâmiínmetodí AT gulânickiilf hybridmetaheuristicbasedonantcolonyoptimizationandhmethod AT sirenkosi hybridmetaheuristicbasedonantcolonyoptimizationandhmethod |
| first_indexed |
2025-11-26T00:06:47Z |
| last_indexed |
2025-11-26T00:06:47Z |
| _version_ |
1850591478229762048 |
| fulltext |
Компьютерная математика. 2009, № 1 142
Òåîðèÿ è ìåòîäû
îïòèìèçàöèè
Предлагается метаэвристический
метод комбинаторной оптимиза-
ции, который базируется на двух
популяционных подходах – алгорит-
мах оптимизации муравьиными ко-
лониями и Н-метода. Этот метод
предназначен для решения широ-
кого круга задач комбинаторной
оптимизации. Его эффективность
проиллюстрирована на основе ре-
зультатов вычислительного экс-
перимента по решению ряда изве-
стных задач комбинаторной оп-
тимизации.
© Л.Ф. Гуляницкий, С.И. Сиренко,
2009
ÓÄÊ 519.21
Ë.Ô. ÃÓËßÍÈÖÊÈÉ, Ñ.È. ÑÈÐÅÍÊÎ
ÃÈÁÐÈÄÍÀß ÌÅÒÀÝÂÐÈÑÒÈÊÀ,
ÎÑÍÎÂÀÍÍÀß ÍÀ ÎÏÒÈÌÈÇÀÖÈÈ
ÌÓÐÀÂÜÈÍÛÌÈ ÊÎËÎÍÈßÌÈ
È Í-ÌÅÒÎÄÅ
Введение. Задачи комбинаторной оптимиза-
ции (КО) возникают во многих областях при-
менения вычислительных методов, в част-
ности, таких как искусственный интеллект,
исследование операций, биоинформатика,
планирование, маршрутизация, составление
расписаний, распределение ресурсов и др.
[1]. Большинство практически важных задач
КО относится к числу NP-трудных, что
наряду с возможными погрешностями в за-
дании исходных данных и существенным
количеством локальных минимумов целевой
функции делает нецелесообразным исполь-
зование точных алгоритмов решения ввиду
значительных вычислительных затрат. Эти и
другие аспекты, а также прогресс в разра-
ботке высокопроизводительных средств вы-
числительной техники обусловили интенсив-
ное развитие в последние годы класса
приближенных методов, которые получили
название метаэвристических [2]. Хотя мета-
эвристические методы в ряде случаев
уступают по точности специальным методам
решения отдельных задач КО, в силу своей
структуры и гибкости они позволяют
создавать на основе единой вычислительной
схемы приближенные алгоритмы решения
довольно широкого класса задач с приемле-
мой для практики трудоемкостью. Несмотря
на отсутствие на данный момент общеприня-
того формального определения, метаэвристи-
ческие методы можно понимать как комби-
нацию двух техник: общая схема строится на
базовом методе, в который включается та
или иная встроенная процедура.
ГИБРИДНАЯ МЕТАЭВРИСТИКА, ОСНОВАННАЯ НА ОПТИМИЗАЦИИ МУРАВЬИНЫМИ ...
Компьютерная математика. 2009, № 1 143
Важным аспектом есть то, что встроенная процедура – это в большинстве
случаев самостоятельный алгоритм решения той же задачи, что и мета-
эвристический метод в целом. Многие из разработанных метаэвристических
методов относятся к классу популяционных алгоритмов [2], т.е. алгоритмов,
в которых, в отличие от траекторных, на каждой итерации обрабатывается
не один, а сразу несколько вариантов решения.
Далее предлагается и анализируется метаэвристический метод решения
задач КО, разработанный на основе комбинации двух популяционных подходов:
оптимизации муравьиными колониями и Н-метода.
В разд. 1 приведено формальное определение задачи КО. В разд. 2 описана
метаэвристика Н-метода [3], который является развитием метода деформи-
рованных многогранников [4]. Метод имеет определенные аналогии с извест-
ным в недифференцируемой непрерывной оптимизации методом Нелдера–
Мида, применяя в процессе поиска оптимального решения специальным обра-
зом определенные отрезки. Близкие идеи были предложены Гловером [5, 6]
в контексте табу поиска. Позже они получили развитие вместе с рассеянным
поиском и известны под названием перекомпоновка маршрутов (Path Relinking)
[7]. Алгоритмы оптимизации муравьиными колониями [8, 9], которые
представляют класс методов роевого интеллекта и успешно применяются
к сложным задачам КО, рассмотрены в разд. 3. Эти алгоритмы являются
многоагентными оптимизационными системами с распределенной непрямой
формой общения между агентами.
Разработанный метаэвристический метод описан в разд. 4, где рассмотрены
его пошаговая структура и особенности. В разд. 5 изложены результаты вычи-
слительного эксперимента по решению задач коммивояжера и многомерных
задач о назначении [10]. Выводы и возможные направления развития исследо-
вания приведены в заключении.
1. Определение задачи комбинаторной оптимизации
Приведем формальное определение задачи КО [3, 11]. Пусть заданы
{1,..., }Y m= , Z – некоторое дискретное пространство, ϕ – гомоморфизм,
:Y Zϕ → , удовлетворяющий заданной системе ограничений Ω .
Определение 1. Под комбинаторным объектом κ будем понимать триаду
( , , )Z= ϕ Ωκ .
Определение 2. Задачей КО, называется задача нахождения такого x* X∈ ,
что
* arg min { ( ) : }x f x x D X= ∈ ⊆ ,
где X – пространство решений задачи, элементами которого являются комбина-
торные объекты; D X⊆ – подпространство допустимых решений, определя-
емое некоторым предикатом Π , : Rf X → – заданная целевая функция задачи.
Л.Ф. ГУЛЯНИЦКИЙ, С.И. СИРЕНКО
144 Компьютерная математика. 2009, № 1
2. Общая схема Н-метода
В ряде алгоритмов КО во избежание концентрации поиска в ограниченной
подобласти пространства X и повышения точности получаемых решений
используются процедуры возмущения [12] или скрещивания и мутации (как
в эволюционных методах) [1], Заметим, что подобные процедуры порождают
подмножества вариантов решения, которые не согласованы с топологией прост-
ранства X . При этом примером подобного согласования является Н-метод.
На рис. 1 показана модификация Н-метода, которая используется в разрабо-
танном метаэвристическом подходе. От стандартного Н-метода [3, 13] эта моди-
фикация отличается отсутствием инициализации начальной популяции, явно
указанным сохранением наилучшего найденного решения и тем, что алгоритм
возвращает множество вариантов решений последней популяции.
Ключевой этап Н-метода – решение подзадач, определение которых требует
введения понятия d-отрезка [4], соединяющего две точки x, y X∈ ,
если X ( X ,d )= – метрическое пространство с метрикой d .
Определение 3. Назовем d-отрезком / x, y / , x, y X∈ , упорядоченную
совокупность точек 1ix X ,i ,...,k∈ = , удовлетворяющих условию: 1 kx x,x y= =
( ) ( ) ( ) 1,...,i id x,x +d x ,y d x,y , i k= = , и 1)( ) (i i+d x,x d x,x< , 1 1i ,...,k= − .
При этом не существует точки z X∈ , такой, что { } { }1:1,..., 1 i i+i k z x ,x∃ ∈ − ∉ ,
1 1( , ( ( )i i+ i i+d x z d z,x d x ,x)+ )= .
procedure Н (P, x);
begin
repeat
Р` := Ø;
for i:= 1 to k do
ОтборДляВариации (x,y∈P);
ПостроениеПолуинтервала <x,x∞/ : y∈ < x, x∞ / & f(y)≤ f(x);
z := arg min {f(u) : u ∈ <x,x∞/, u ∉ L ( y )};
ТраекторныйМетод (z);
Р` := P` ∪ z;
if f (x) > f (z) then
x := z;
end if
end for;
P := ОтборПопуляции (Р,P`);
until не выполняется условие завершения;
return P, x;
end
РИС. 1. Модифицированная метаэвристика Н-метода
ГИБРИДНАЯ МЕТАЭВРИСТИКА, ОСНОВАННАЯ НА ОПТИМИЗАЦИИ МУРАВЬИНЫМИ ...
Компьютерная математика. 2009, № 1 145
Определение 4. Назовем d-интервалом x, y< > , упорядоченную сово-
купность / x, y / без точек x, y , а d-полуинтервалом x, y /< – совокупность
/ x, y / без точки x .
На итерации Н-метода происходит порождение множества вариантов реше-
ний. Процедура ОтборДляВариации некоторым образом отбирает пару x , y
вариантов решений, на основании которых строится и решается подзадача вида
arg min { ( ) : , / , , /, ( ), ( ) ( )}f u u x x y x x u L y f y f x∞ ∞∈< ∈< ∉ ≤ ,
где ( )L y – окрестность точки y , точки которой, находящиеся на построенном
полуинтервале, исключаются из рассмотрения, а x∞ – точка, максимально
удаленная в пространстве вариантов решений от точки x . Ко всем найденным
субоптимальным таким образом решениям применяется траекторный метод
(например, локальный поиск). Порожденное множество вариантов решений P̀
обновляет текущую популяцию P с помощью процедуры ОтборПопуляции.
3. Оптимизация муравьиными колониями
В последние годы активно развиваются методы так называемого роевого
интеллекта, в которых совокупность сравнительно простых агентов конструи-
рует стратегию своего поведения без наличия глобального управления [14].
Один из широко известных роевых методов – метод оптимизации муравьиными
колониями (ОМК). По аналогии с биологической моделью, ОМК базируется на
непрямом обмене информацией колонии агентов, называемых искусственными
муравьями, использующих феромонные следы как коммуникационное средст-
во [8]. Феромонные следы в ОМК служат распределенной численной инфор-
мацией, которая, наряду с эвристической информацией о задаче, используется
муравьями для недетерминированного конструирования решений задачи и кото-
рую муравьи адаптивно изменяют для отображения опыта, накопленного
в процессе поиска решения. Важно отметить, что хотя каждый муравей
достаточно сложен, чтобы найти решение задачи, хорошие решения, обычно,
появляются только в результате коллективного взаимодействия между муравья-
ми, посредством записи / считывания значений феромонных следов. В изве-
стном смысле, это является распределенным процессом обучения, в котором
отдельные агенты, муравьи, не адаптируются, а наоборот, адаптивно изменяют
вид задачи и ее восприятие другими агентами.
Кроме построения муравьями решений, метаэвристика ОМК включает еще
две процедуры (рис. 2) [8]: обновление феромонных значений и действия демона
(включение процедуры действий демона необязательное). Главная процедура
метаэвристики ОМК – ПланированиеДействий не определяет, каким образом
распланированы и синхронизированы ПостроениеМуравьямиРешений,
ОбновлениеФеромона и ДействияДемона, что оставляет разработчику свободу
в определении способа взаимодействия этих трех процедур.
Л.Ф. ГУЛЯНИЦКИЙ, С.И. СИРЕНКО
146 Компьютерная математика. 2009, № 1
procedure ОМК()
while (не выполняется условие завершения)
ПланированиеДействий
ПостроениеМуравьямиРешений();
ОбновлениеФеромона();
ДействияДемона(); {необязательно}
end ПланированиеДействий
end while
end procedure
РИС. 2. Метаэвристика оптимизации муравьиными колониями
Обновление феромонных значений включает как увеличение – добавление
муравьями феромона согласно построенному ими решению, так и уменьшение –
испарение феромона, процесс с помощью которого интенсивность феромонного
следа автоматически уменьшается со временем. Испарение осуществляет полез-
ную форму «забывания», содействуя исследованию новых областей в простран-
стве поиска и избежанию очень быстрой сходимости алгоритма к субопти-
мальной области.
Действия демона могут использоваться для осуществления централи-
зованных процедур, которые не могут быть выполнены отдельными муравьями.
Например, активация процедуры локальной оптимизации или сбор глобальной
информации, которая может быть использована для принятия решения: будет
или не будет полезным откладывание дополнительного феромона для отклоне-
ния процесса поиска от локальной перспективы.
4. Метаэвристический метод на основе синтеза алгоритмов ОМК
и Н-метода
Предлагается новый метаэвристический метод КО, который базируется на
использовании идей двух вышеописанных популяционных методов – ОМК
и Н-метода. Алгоритмы этого метода сохраняют положительные стороны обоих
использованных подходов. Разработанный подход является методом, который
конкретизацией проблемно-зависимых частей позволяет решать как некоторый
класс близких по постановке задач КО, так и задачи КО из разных классов.
Метаэвристика предложенного подхода, который назовем ОМК-Н методом,
показана на рис. 3.
В начале работы метаэвристики ОМК-Н осуществляется инициализация
алгоритма ОМК, в частности феромонных значений T. Затем выполняется
построение муравьями решений с последующим применением к этим решениям
траекторного метода (например, локального поиска). На основе полученного
множества вариантов решений S обновляются феромонные значения
(необязательно) и это множество как начальная популяция передается
в модификацию алгоритма Н-метода (см. рис. 1) вместе с текущим лучшим
ГИБРИДНАЯ МЕТАЭВРИСТИКА, ОСНОВАННАЯ НА ОПТИМИЗАЦИИ МУРАВЬИНЫМИ ...
Компьютерная математика. 2009, № 1 147
найденным решением x. На основе возвращенных Н-методом вариантов
решений происходит обновление феромонных значений. В завершение итерации
алгоритма выполняются действия демона (необязательно). Описанные действия,
начиная с этапа построения решений, повторяются до выполнения условий
останова алгоритма ОМК. Алгоритм возвращает наилучшее найденное решение.
С точки зрения структуры данное комбинирование агрегирует такие две
альтернативы. С одной стороны, ОМК выступает генератором начальных
популяций для Н-метода. С другой стороны, Н-метод выступает в качестве
усложненной процедуры демона (вместо обычно используемых алгоритмов
локального поиска) для улучшения решений, построенных муравьями. В за-
висимости от соотношения условий останова в ОМК и Н-методе при реализации
ОМК-Н, он может быть более близок к тому или другому исходному методу.
Описанный алгоритм разработан для статических задач КО. Применение
данного подхода к динамическим задачам требует дальнейшего развития
метаэвристики ОМК-Н с учетом уже полученных результатов применения
алгоритмов ОМК к динамическим задачам.
procedure ОМК-H(x)
ИнициализацияФеромонныхЗначений(T );
x := НекотороеРешение();
repeat
S := Ø;
for i:=1 to m do
s := ПостроениеРешения(T );
if ДопустимоеРешение(s) then
ТраекторныйМетод (s);
if f (x) > f (s) then
x := s;
end if
S := S ∪ s ;
end if
end for;
ОбновлениеФеромонныхЗначений(T , S, x); {необязательно}
H(S, x);
ОбновлениеФеромонныхЗначений(T , S, x);
ДействияДемона(); {необязательно}
until не выполняется условие завершения;
return x ;
end procedure
РИС. 3. Метаэвристика, комбинирующая оптимизацию муравьиными колониями
и Н-метод
Л.Ф. ГУЛЯНИЦКИЙ, С.И. СИРЕНКО
148 Компьютерная математика. 2009, № 1
Целесообразность предложенного комбинирования можно обосновать таки-
ми соображениями. Во-первых, оба базовых метода представляют два принци-
пиально отличных подхода исследования пространства решения: ключевой
идеей ОМК является многоагентный поиск, а в основе Н-метода лежит исполь-
зование глобального сканирования пространства решений. Во-вторых,
предложенное объединение согласовано с идеологией обоих методов. Поэтому
комбинирование этих метаэвристических концепций потенциально повышает
вероятность нахождения более точных решений.
При параллельной реализации возможно организовывать более сложное
взаимодействие базовых методов – ОМК и Н-метода. Разработка и исследование
параллельных комбинированных метаэвристических методов на основе ОМК
и Н-метода – одно из важных направлений дальнейших исследований.
5. Вычислительный эксперимент
Поскольку теоретическое исследование алгоритмов КО крайне редко позво-
ляет получать практически применимые результаты, принято анализировать
показатели эффективности путем проведения вычислительных экспериментов.
С этой целью обычно используют «классические» модели КО – такие, например,
как задача коммивояжера (ЗК) [1]. Для проведения вычислительного экспе-
римента, кроме ЗК, была выбрана еще одна NP-трудная задача – многомерная
задача о назначении (МЗН). Кратко 3-мерный вариант этой задачи можно
описать как «минимизацию суммарной стоимости назначения объектов на пози-
ции в моменты времени» [10].
В проведенном вычислительном эксперименте по решению серии задач
коммивояжера предложенный подход сравнивался с реализованным алгоритмом
Н-метода для ЗК и одним из наиболее эффективных алгоритмов оптимизации
муравьиными колониями для решения ЗК – алгоритмом MMAS [16], реализация
которого взята из пакета ACOTSP [17]. На основе предварительного анализа
были выбраны такие значения параметров Н-метода: количество точек текущей
популяции составляло 50, на каждой итерации порождалось новые 20 точек,
точка x∞ и полуинтервал среди всех возможных определялись случайным обра-
зом, окрестность ( )L y состояла только из точки y . В качестве траекторного
алгоритма взята реализация алгоритма 3-opt [1] из пакета ACOTSP [17].
В алгоритме MMAS количество муравьев составляло 50, коэффициент
испарения феромона [9] ρ = 0.5, в псевдослучайном пропорциональном правиле
выбора [9], которое применяли муравьи при построении решений, были такие
значения параметров α = 1, β = 2. В качестве деятельности демона в алгоритме
MMAS ко всем построенным муравьями решениям применялся алгоритм 3-opt.
Параметрам алгоритма ОМК_Н были присвоены те же значения, что
и у базовых методов.
ГИБРИДНАЯ МЕТАЭВРИСТИКА, ОСНОВАННАЯ НА ОПТИМИЗАЦИИ МУРАВЬИНЫМИ ...
Компьютерная математика. 2009, № 1 149
В табл. 1 приведены результаты 20 вариантов решения задач, взятых из Ин-
тернет-библиотеки TSPLIB [18]. Здесь число в названии задачи обозначает ее
размерность, f* – известное значение целевой функции в точке глобального
минимума; f – лучшее найденное соответствующим алгоритмом значение целе-
вой функции; δ – средняя относительная погрешность алгоритма (%); tlim – огра-
ничение на время работы алгоритма; t – среднее время, на протяжении которого
алгоритмом было найдено лучшее решение на ПЭВМ класса Pentium-IV
2,66 ГГц (с).
Для проведения вычислительного эксперимента по решению МЗН были
реализованы Н-метод, вариант алгоритма MMAS и разработанный алгоритм
ОМК-Н. В качестве траекторного алгоритма использовался детерминированный
локальный поиск с окрестностями, построенными с использованием транс-
позиционной метрики.
В табл. 2 приведены усредненные результаты 20 вариантов решения МЗН
с известными уникальными оптимальными решениями, которые были получены
с помощью генератора задач МЗН, предложенного в [19]. В дополнение к преж-
ним обозначениям, здесь d обозначает количество измерений в задаче, а n –
размерность каждого измерения. Параметрам всех сравниваемых методов были
присвоены те же значения, что и в эксперименте по решению ЗК.
Как свидетельствуют результаты вычислений, во всех задачах, которые ис-
пользовались в исследовании, ОМК-H показал лучшие по точности результаты
(либо одинаковые, в случае когда все алгоритмы нашли оптимальное решение),
при этом время работы было сравнимым или лучшим. Именно достижение
повышения эффективности предложенного метода по сравнению с базовыми
методами является важным, поскольку цель работы заключалась в разработке
и исследовании подхода, который может быть использован для решения
широкого круга задач КО. Отметим, что разработка эффективных алгоритмов
решения ЗК и МЗН, ввиду широкого круга их практических применений и слож-
ности, также является важным направлением исследований.
ТАБЛИЦА 1. Результаты решения ЗК
MMAS H ОМК -H Задача f*
tlim, (с)
f δ(%) t (с) f δ(%) t (с) f δ(%) t (с)
а280 2579 2 2579 0,00 0,45 2579 0,00 0,27 2579 0,00 0,35
pcb442 50778 20 50778 0,24 12,33 50778 0,19 8,00 50778 0,18 9,19
rat783 8806 40 8806 0,11 27,12 8806 0,25 31,65 8806 0,18 31,54
d1291 50801 60 50828 0,19 37,09 50820 0,19 35,46 50801 0,15 33,80
pr2392 378032 80 380001 0,87 78,74 380761 0,93 78,98 379923 0,81 62,72
ТАБЛИЦА 2. Результати решения МЗН
Задача MMAS H ОМК -H
d n f* f δ(%) t (с) f δ(%) t (с) f δ(%) t (с)
5 5 26 26 0,38 2,36 27 4,23 0,03 26 0,78 2,73
10 3 13 14 7,69 0,01 14 7,69 0,03 14 7,69 0,02
5 8 31 32 3,23 1,02 32 5,8 0,06 32 3,23 0,35
5 12 53 55 4,15 3,75 55 6,03 0,13 54 3,01 1,94
3 100 482 560 16,76 10,27 559 16,35 8,87 558 16,16 12,8
Л.Ф. ГУЛЯНИЦКИЙ, С.И. СИРЕНКО
150 Компьютерная математика. 2009, № 1
Заключение. Предложенный подход, который базируется на двух попу-
ляционных методах – оптимизации муравьиными колониями и Н-методе, пока-
зал свою эффективность при экспериментальном исследовании. Комбинирова-
ние стратегий поиска, согласованное со структурой базовых методов, позволило
достичь лучших показателей эффективности при решении ряда задач КО.
Важной целью дальнейших исследований может стать экспериментальное
сравнение предложенного подхода с другими приближенными методами КО, а
также получение теоретических условий сходимости и трудоемкости алгорит-
мов метода, предназначенных для решения конкретных классов задач КО.
Целесообразно также исследовать вопросы эффективной реализации алгоритмов
ОМК-H на многопроцессорных вычислительных системах.
Л.Ф. Гуляницький, С.І. Сіренко
ГІБРИДНА МЕТАЕВРИСТИКА, ЩО ЗАСНОВАНА
НА ОПТИМІЗАЦІЇ МУРАШИНИМИ КОЛОНІЯМИ І Н-МЕТОДІ
Пропонується метаевристичний метод комбінаторної оптимізації, який базується на двох
популяційних підходах – алгоритмах оптимізації мурашиними колоніями та Н-методу. Цей
метод призначений для розв’язання широкого кола задач комбінаторної оптимізації.
Ефективність запропонованого підходу проілюстрована на основі результатів обчислю-
вального експерименту з розв’язання ряду задач комбінаторної оптимізації.
L.F. Hulianytskyi, S.I. Sirenko
HYBRID METAHEURISTIC BASED ON ANT COLONY OPTIMIZATION AND H-METHOD
A metaheuristic method for solving combinatorial optimization problems is proposed, which is
based on two population methods – ant colony optimization and H-method. The method is
applicable to a wide range of combinatorial optimization problems. The efficiency of the approach
proposed is illustrated by numerical experiment on solving well-known combinatorial optimization
problems.
1. Hoos H.H., Stützle T. Stochastic Local Search: Foundations and Applications. – San
Francisco: Morgan Kaufmann Publ., 2005. – 658 p.
2. Blum C., Roli A., Alba E. An introduction to metaheuristic techniques // Parallel
metaheuristics: A new class of algorithms (Ed. E.Alba). – Hoboken: John Wiley & Sons. –
2005. – P. 3–42.
3. Гуляницкий Л.Ф., Сергиенко И.В. Метаэвристический метод деформированного
многогранника в комбинаторной оптимизации // Кибернетика и системный анализ. –
2007. – № 6. – С. 70–79.
4. Гуляницкий Л.Ф. Метод деформаций в дискретной оптимизации // Исследование
операций и АСУ. – 1989. – Вып. 34. – С. 30–33.
5. Glover F. Genetic algorithms and scatter search: Unsuspected potentials // Statistics and
Computting. – 1994. – № 4. – P. 131–140.
ГИБРИДНАЯ МЕТАЭВРИСТИКА, ОСНОВАННАЯ НА ОПТИМИЗАЦИИ МУРАВЬИНЫМИ ...
Компьютерная математика. 2009, № 1 151
6. Glover F. Tabu search for nonlinear and parametric optimization (with links to genetic
algorithms) // Discrete Applied Mathematics. – 1994. – N 49. – P. 231–255.
7. Glover F. A template for scatter search and path relinking // Artificial Evolution: Lecture
Notes in Computer Sci. (Eds. J.-K. Hao, E. Lutton, E. Ronald, M. Schoenauer, D. Snyers).
– Springer, 1997. – 1363. – P. 13–54.
8. Dorigo M., Stützle T. Ant Colony Optimization. – Cambridge: MIT Press, MA, 2004. –
348 p.
9. Dorigo M., Blum C. Ant colony optimization theory: A survey // Theoretical computer
sci. – 2005. – 344. – P. 243–278.
10. Grundel Don A., Krokhmal P.A., Oliveira C.A.S., Pardalos P.M. On the number of local
minima for the multidimensional assignment problem // J. Combinatorial Optimization. –
2007. – 13, N 2. – P. 1–18.
11. Гуляницький Л.Ф. До формалізації та класифікації задач комбінаторної оптимізації //
Теорія оптимальних рішень. – 2008. – № 7. – С. 45–49.
12. Lourenço H. R., Martin O., Stützle T. Iterated local search // Handbook of Metaheuristics:
International Series in Operations Research & Management Sci. / Eds. F. Glover
and G. Kochenberger. – Norwell: Kluwer Academic Publishers, MA, 2002. – 57. –
P. 321–353.
13. Гуляницький Л.Ф. Один гібридний алгоритм комбінаторної оптимізації // Abstract of
Int. Ukrainian-Polish Workshop "Problems of Stochastic and Discrete Optimization"
(May 10–15, 2005, Kaniv, Ukraine). – Kaniv, 2005. – P. 63–65.
14. Kennedy J., Eberhart R. C. Swarm Intelligence. – San Francisco: Morgan Kaufmann
Publishers, 2001. – 512 p.
15. Raidl G.R. A Unified View on Hybrid Metaheuristics // Lecture Notes in Computer Sci. –
Springer-Verlag, 2006. – 4030. – P. 1–12.
16. Stützle T., Hoos H. Max – Min Ant System // Future Generation Computer Systems. –
2000. – N 8. – P. 889–914.
17. Stützle T. ACOTSP, Version 1.0 // http://www.aco-metaheuristic.org/aco-code. – 2004.
18. TSPLIB // http://elib.zib.de/pub/mp-testdata/tsp/tsplib/tsplib.html.
19. Grundel D.A., Pardalos P.M. Test Problem Generator for the Multidimensional
Assignment Problem // Computational Optimization and Applications. – 2005. – N 30. –
P. 133–146.
Получено 29.10.2008
Îá àâòîðàõ:
Гуляницкий Леонид Федорович,
доктор технических наук, ведущий научный сотрудник
Института кибернетики имени В.М. Глушкова НАН Украины,
hulianytsky@voliacable.com
Сиренко Сергей Игоревич,
аспирант Института кибернетики имени В.М. Глушкова НАН Украины.
s.sirenko@gmail.com
|