Застосування Н-методу для розв’язання задач комбінаторної оптимізації на перестановках
A hybrid algorithm class for combinatorial optimization problems solving is considered. The class is named the H-method and built on the basis of synthesis of the accelerated probabilistic simulation algorithm (G-algorithm) and the modified discrete downhill simplex method. Algorithms for segment an...
Gespeichert in:
| Datum: | 2018 |
|---|---|
| Hauptverfasser: | , |
| Format: | Artikel |
| Sprache: | Ukrainisch |
| Veröffentlicht: |
The National Technical University of Ukraine "Igor Sikorsky Kyiv Polytechnic Institute"
2018
|
| Online Zugang: | https://journal.iasa.kpi.ua/article/view/127656 |
| Tags: |
Tag hinzufügen
Keine Tags, Fügen Sie den ersten Tag hinzu!
|
| Назва журналу: | System research and information technologies |
| Завантажити файл: |  |
Institution
System research and information technologies| _version_ | 1866302203102232576 |
|---|---|
| author | Hulianytskyi, L. F. Gobov, D. A. |
| author_facet | Hulianytskyi, L. F. Gobov, D. A. |
| author_sort | Hulianytskyi, L. F. |
| baseUrl_str | http://journal.iasa.kpi.ua/oai |
| collection | OJS |
| datestamp_date | 2018-04-11T11:12:54Z |
| description | A hybrid algorithm class for combinatorial optimization problems solving is considered. The class is named the H-method and built on the basis of synthesis of the accelerated probabilistic simulation algorithm (G-algorithm) and the modified discrete downhill simplex method. Algorithms for segment and half-interval building in the permutation space are proposed and proved. They are used for quadratic assignment problem solving. The computational experimental results are given, which demonstrate a high efficiency of the developed algorithms in comparison with some known algorithms. |
| first_indexed | 2025-07-17T10:23:44Z |
| format | Article |
| fulltext |
© Л.Ф. Гуляницький, Д.А. Гобов, 2007
74 ISSN 1681–6048 System Research & Information Technologies, 2007, № 2
TIДC
МЕТОДИ ОПТИМІЗАЦІЇ, ОПТИМАЛЬНЕ
УПРАВЛІННЯ І ТЕОРІЯ ІГОР
УДК 519.854
ЗАСТОСУВАННЯ Н-МЕТОДУ ДЛЯ РОЗВ’ЯЗАННЯ ЗАДАЧ
КОМБІНАТОРНОЇ ОПТИМІЗАЦІЇ НА ПЕРЕСТАНОВКАХ
Л.Ф. ГУЛЯНИЦЬКИЙ, Д.А. ГОБОВ
Запропоновано клас гібридних алгоритмів розв’язання задач комбінаторної
оптимізації (H-метод), який побудовано на основі синтезу алгоритму приско-
реного ймовірнісного моделювання (G-алгоритм) та модифікованого дискрет-
ного методу деформованих багатогранників. Обґрунтовано алгоритми побудо-
ви відрізків та напівінтервалів у просторі перестановок для розв’язання
квадратичної задачі про призначення. Наведено результати обчислювального
експерименту, що демонструють ефективність розроблених алгоритмів у по-
рівнянні з деякими відомими.
ВСТУП
Труднощі розв’язання задач комбінаторної оптимізації загальновідомі.
Практично всі вони належать до класу NP-складних задач. Внаслідок швид-
ко зростаючої обчислювальної складності задач при збільшенні розмірності
існує необхідність у розробці методів і алгоритмів, які б дозволяли отриму-
вати придатний для застосування розв’язок задачі за умови використання
обмежених обчислювальних ресурсів. Одним із перспективних напрямків
розвитку алгоритмів розв’язання задач комбінаторної оптимізації є розробка
метаевристичних (гібридних) алгоритмів.
Термін метаевристика (metaheuristics) вперше був застосований Гло-
вером у 1986 р. як поєднання двох грецьких слів: евристика походить від
дієслова heuriskein, що означає шукати, суфікс мета — над, на верхнім рів-
ні. Перед тим як цей термін набув поширення у зарубіжній літературі, за-
мість нього часто використовували термін сучасні евристики. Існує велика
кількість означень для терміну метаевристика. Підсумовуючи варіанти
означень із [1–3] можна сказати, що метаевристики є високорівневими стра-
тегіями для дослідження простору розв’язків за допомогою використання
різних методів. Більшість відомих метаевристик базується на поєднанні по-
пуляційних алгоритмів, перш за все генетичних (ГА), та алгоритмів пошуку
в околах (локальний пошук, табу-пошук, імітаційний відпал) [4, 5]. Найпо-
ширенішими є меметичні алгоритми (деякі автори називають їх гібридними
генетичними), що оперують у просторі локальних екстремумів. ГА виступає в
Застосування Н-методу для розв’язання задач комбінаторної оптимізації на перестановках
Системні дослідження та інформаційні технології, 2007, № 2 75
якості метаевристики, а вбудованою евристикою є процедура локального по-
шуку, яка оперує з усіма точками популяції.
У роботі розглядаються гібридні алгоритми розв’язання задач ком-
бінаторної оптимізації, названі Н-алгоритмами. Вони побудовані на основі
синтезу алгоритму прискореного ймовірнісного моделювання (G-алгоритм)
та дискретного методу, названого методом деформованих багатогранників
[6, 7].
Під задачею комбінаторної оптимізації далі будемо розуміти пошук та-
кого Xx∈ , при якому задана цільова функція )(xf досягає оптимуму, де
X —деякий скінченний простір. Більш детально розглянемо задачі на пере-
становках. Ефективність алгоритмів досліджується при розв’язуванні однієї
із найвідоміших моделей комбінаторної оптимізації — квадратичної задачі
про призначення [1, 4].
ПОБУДОВА НАПІВІНТЕРВАЛІВ У ПРОСТОРІ ПЕРЕСТАНОВОК
Введемо означення метрики d у просторі перестановок X . Відстань між
двома довільними перестановками a та b Xbabad ∈,),,( визначимо як
мінімальну кількість транспозицій, що перетворюють перестановку a в b
(під транспозицією розуміється обмін місцями двох компонентів пере-
становки).
Введемо означення відрізка у просторі перестановок X з метрикою d .
Послідовність перестановок ),...,( 1 qllL= , де al =1 , bl q = ,
1),( 1 =+ii lld , 1,...,1 −= qi , є d -відрізком між перестановками ),...,( ni aaa =
та ),...,( 1 nbbb = у просторі перестановок X з метрикою d , якщо
),( badq = .
Наведемо алгоритм побудови d -відрізка >< ba, . Нехай він складаєть-
ся з перестановок ),...,( 1 qllL = , де blal q == ,1 , а qil i ,...,2, = , які поро-
джуються шляхом транспозиції двох елементів перестановки 1−il .
Алгоритм 1.
Будуємо d-відрізок >< ba, таким чином:
1,1 == kal .
2l . Якщо 1
1
1 bl ≠ , то ),...,,...,,( 121
2
naaabl = , покладаємо 1: += kk , а
елемент 1a переміщуємо у позицію, в якій стояв елемент 1b .
wl . Якщо i
w
i bl ≠−1 , то ),...,,...,,,...,( 111
11
−−−
+= w
n
w
i
w
ii
w lllbbl , 1: += kk ,
1−w
il , переміщується на позицію, на якій стояв елемент ib . Кінець
алгоритму.
Для кожної пари перестановок a та b алгоритм будує один відрізок з
множини можливих відрізків між a та b .
Нехай маємо перестановку ),,,,,( fedcba , яку необхідно перетвори-
ти у перестановку ),,,,,( aebfdc . Циклічний запис цієї процедури буде
Л.Ф. Гуляницький, Д.А. Гобов
ISSN 1681–6048 System Research & Information Technologies, 2007, № 2 76
мати вигляд )( fca )( db , що означає « a переходить в c , c в f , f в a , b
в d , d в b ». Тобто цикл ),...,,( 21 nxxx означає, що 1x переходить в 22 , xx
в 13 ,..., +nxx в nn xx , в 1x . Тому що елемент е є фіксованим (тобто перехо-
дить сам у себе), він не з’являється у циклічному записі, оскільки одиничні
цикли записувати не прийнято.
Легко побачити, що будь-яку процедуру по перетворенню однієї пере-
становки в іншу можна подати у циклічному записі.
Розглянемо таку процедуру. У просторі перестановок розмірності n по-
трібно перетворити перестановку a в перестановку b , причому кількість
пар }|,{ iiii baba = дорівнює r . Позначимо елементи, з яких складаються
перестановки a та b , як nxx ,...,1 . Нехай, починаючи з елемента 1x , маємо,
що 1x переходить у 22 , xx в 3x і так далі, доки не прийдемо до елементу
1+px , який вже зустрічався серед pxx ,...,1 . Цей елемент 1+px повинен дорів-
нювати 1x . Припустимо, що 31 xx p =+ . Але це неможливо, бо в 3x перехо-
дить 2x , а за припущенням в 1+px переходить 2xx p ≠ . Ці міркування мо-
жуть бути повторені для будь-якого 1, ≠wxw . Таким чином 11 xx p =+ , і ми
отримуємо цикл )...,,( 2,1 pxxx , що є частиною процедури по перетворенню
a в b . Якщо rnp −≠ , то існує елемент 1y такий, що pixy i ,...,1,1 −≠ , для
якого за допомогою аналогічних міркувань отримуємо цикл ),...,,( 21 pyyy .
Жоден з pjy j ,...,1, = не може дорівнювати довільному pixi ,...,1, = , тому
що з ji yx = випливає 11 ++ = ji yx і т.д. Для деякого k отримуємо 1yxk = , що
суперечить припущенню при виборі 1y . Діючи подібним чином, можна
знайти всі цикли, які виникають при перетворенні перестановки a у пере-
становку b .
Теорема 1. Для того щоб при перетворенні перестановки а у переста-
новку b здійснити переміщення всіх елементів, які належать одному циклу
розмірності k, необхідно виконати щонайменше 1−k крок.
Доведення. Використаємо метод математичної індукції.
1. Для 1=k процедура є виродженою, тобто елемент x з перестановки
a необхідно перемістити в елемент х перестановки b, що виконується за оче-
видним правилом.
2. Виходячи з того, що для nk ≤∀ теорема виконується, доведемо
справедливість для 1+= nk . Маємо: 1a переходить в nab ,...,1 в nb . Пере-
визначимо елементи: 1x переходить в ixx ,...,2 в ji xx ,...,1+ в nj xx ,...,1+ в 1x .
Нехай у перестановці a поміняли місцями елементи ix та jx . Внаслі-
док цієї транспозиції отримуємо, що 1x переходить в ixx ,...,2 в 11, ++ jj xx в
nj xx ,...,2+ в 11, +ixx в ji xx ...,,2+ в ix .
Застосування Н-методу для розв’язання задач комбінаторної оптимізації на перестановках
Системні дослідження та інформаційні технології, 2007, № 2 77
У такий спосіб отримаємо два цикли розмірності 1++− ijn та ij − .
Для першого циклу, оскільки його розмірність менша за 1+n , для пере-
ведення всіх його елементів потрібно зробити 1+− jn крок, а для друго-
го циклу — відповідно 1−− ij крок. Таким чином будуть зроблені
nijijn =−−++−+ )1()(1 кроків. Теорему доведено.
Теорема 2. Процедура перетворення перестановки a у перестановку b
шляхом транспозицій елементів перестановки b при умові, що задача міс-
тить t циклів розмірності tkkk ...,,, 21 , де Nk
t
i
i =∑
=1
, має щонайменше
tn − кроків, де n — розмірність простору перестановок.
Доведення. Зрозуміло, що в результаті транспозиції двох елементів ia
та ja , можливі два випадки: або елементи ia та ja належать двом циклам,
або одному.
Розглянемо перший випадок. Нехай маємо два цикли: 1x перетворю-
ється в uxx ,...,2 в pu xx ,...,1+ в 1x , де iu ax =+1 та 1y в hyy ,...,2 в qh yy ,...,1+
в 1y , де jh ay =+1 .
Поміняємо місцями елементи 1+ux та 1+hy . Отримаємо: 1x перетворю-
ється в uxx ,...,2 в qh yy ,...,1+ в 1y , 1y в hyy ,...,2 в pu xx ,...,1+ в 1x . Тепер
маємо один цикл розмірності qp + . Для перетворення всіх елементів, які
належать до цього циклу, згідно із теоремою 1 необхідно зробити 1−+ qp
крок, а для вихідних циклів — 2−+ qp . Таким чином, кожна транспозиція
елементів, що належать до різних циклів, збільшує кількість необхідних
транспозицій для перетворення перестановки a в b на 2.
Якщо на кожному кроці будемо змінювати місцями елементи, які на-
лежать до одного циклу, то для перетворення всіх елементів цього циклу,
необхідно буде зробити кількість кроків, яка дорівнює розмірності циклу
зменшену на одиницю (виходячи з теореми 1), тобто ( ) =−∑
=
t
i
ik
1
1
tNtk
t
i
i −=−=∑
=1
. Теорему доведено.
Теорема 3. Алгоритм 1 будує послідовність перестановок найменшої
довжини, а саме перетворює перестановку a в перестановку b за мінімаль-
но можливу кількість транспозицій, тобто будує між ними d -відрізок.
Доведення. На кожному кроці алгоритм 1 міняє місцями два елементи,
які належать до одного циклу. Це виходить з того, що j
il перетворюється в
ib , і ми шукаємо таке j
dl , що дорівнює ib i яке належить до одного циклу з
j
il . Повторюючи відповідні міркування з доведення теореми 2, отримаємо,
Л.Ф. Гуляницький, Д.А. Гобов
ISSN 1681–6048 System Research & Information Technologies, 2007, № 2 78
що алгоритм 1 перетворить перестановку a в b за ( )∑
=
−
t
i
ik
1
1 , де tkkk ,...,, 21
— розмірності циклів у вихідній задачі. Виходячи з теореми 2, ця кількість
кроків є мінімальною. Теорему доведено.
Розглянемо поняття напівінтервала у просторі перестановок. Виходячи
з теореми 1 та 2, точка c є найбільш віддаленою від точки a , якщо
1),( −= ncad .
Теорема 4. При використанні алгоритму 1 максимальна кількість
транспозицій для перетворення будь-якої перестановки a в c дорівнює 1−n ,
де n — розмірність простору перестановок.
Доведення. Нехай процедура по перетворенню перестановки a в c має
t циклів. Тоді, згідно із теоремою 2, необхідно зробити ( )∑
=
−
t
i
ik
1
1 кроків, де
Nk
t
i
i =∑
=1
. Перетворимо цей вираз:
( ) tNtkk
t
i
i
t
i
i −=−=− ∑∑
== 11
1 .
Через те що кількість циклів більша або дорівнює 1, цей вираз набуває
максимуму для 1=t . Таким чином отримали максимум, який дорівнює
1−n .
Розглянемо алгоритм побудови напівінтервала через дві задані точки.
Нехай вихідна задача перетворення перестановки a в b має t циклів. Тоді за
теоремою 2 кількість кроків буде дорівнювати tn − . Теорему доведено.
Оберемо t елементів з перестановки b , з кожного циклу вихідної зада-
чі по одному елементу та модифікуємо алгоритм 1.
Алгоритм 2.
Будуємо множину перестановок L таким чином:
1,1,1 === pkal .
2l . Якщо 1
1
1 bl ≠ , то },...,,...,,{ 121
2
naaabl = , покладаємо 1: += kk , 1a
переміщуємо в позицію, в якій стояв елемент 1b ; якщо 1
1
1 bl = , то
1:,1
1 +== pplm p .
Провівши аналогічні дії, завершимо їх для wl .
wl . Якщо i
w
i bl ≠−1 , то },...,,...,,,...,{ 11
11
−−
+= w
ni
w
ii
w lalbbl , 1: += kk , ia
переміщуємо в позицію, в якій стояв елемент ib ; якщо i
w
i bl =−1 , то
1:,1 +== − pplm w
ip .
Зрозуміло, що Tp = . Всі Tpm p ,...,1, = , належать до різних циклів ви-
хідної задачі.
Застосування Н-методу для розв’язання задач комбінаторної оптимізації на перестановках
Системні дослідження та інформаційні технології, 2007, № 2 79
Очевидно, що у випадку транспозиції двох елементів im буде отримана
перестановка, яка не зустрічалась раніше.
Формуємо множину S всіх пар 1],,...,1[,,),,( =∈≠ iTjijimm ji .
Виконуємо T раз такі дії:
1. Обираємо випадково чи за певним правилом з множини S пару
),( ji mm .
2. Міняємо місцями ці елементи у перестановці
1−+iwl і отримуємо пе-
рестановку iwl + .
3. Виключаємо з множини S пари ),( ji mm та ),( ij mm .
4. 1: += ii .
Таким чином ми отримали послідовність 1,...,1, −= nil i , тобто побу-
дували напівінтервал, який проходить через точки a та b.
Наведений алгоритм дозволяє будувати напівінтервали, причому з
множини всіх можливих напівінтервалів завжди вибирається лише один, що
дозволяє відбраковувати пари точок, які були вже задіяні у побудові напів-
інтервалу. Слід зауважити: як параметр зазначеного алгоритму може вико-
ристовуватись номер елемента у перестановці, з якого починається дія алго-
ритма побудови напівінтервалу. У такому випадку можуть відбраковуватись
вже дві-три перестановки та номер елемента, з якого починає діяти такий
алгоритм.
Відзначимо, що подібні результати можна отримати і для інших
метрик.
ГІБРИДНИЙ МЕТОД ДЕФОРМАЦІЙ (H-МЕТОД)
Основна ідея Н-методу полягає в тому [8], що формується початкова мно-
жина розв’язків, які грають роль віддалено подібну ролі багатогранника у
методі пошуку по деформованому багатограннику (метод Нелдера-Міда
[9]). Із цієї множини певним чином вибираються декілька пар точок. Для
кожної з них будується напівінтервал у просторі варіантів розв’язку задачі,
який проходить через вибрані точки, і на ньому відшукується найкраща для
цільової функції точка. Знайдений варіант передається як початкове набли-
ження для покращення G-алгоритмом. У результаті таких дій знаходиться
сукупність покращуючих точок. Ці точки включаються у багатогранник за-
мість найгірших для вибраного критерію точок, і описана процедура
повторюється до виконання критерію завершення.
Наведемо більш формально обчислювальну схему Н-методу, викорис-
товуючи термінологію еволюційних обчислень.
procedure H-Algorithm )(x ;
begin
;;0: 0 ∅== Ph
for 1:=j to m do
Л.Ф. Гуляницький, Д.А. Гобов
ISSN 1681–6048 System Research & Information Technologies, 2007, № 2 80
=:x ГенераціяДопустимогоВаріанту;
);(_: xSearchGx =
;: xPP hh ∪=
endfor; {формування початкової популяції}
repeat
hPP =:
for 1:=i to k do
ВідбірДляВаріації ))()(:,( yfxfPyx >∈ ;
/};,)},(/\,:)({minarg: ∞∞ ∈<<∈= xxyyLxxuufz
);(_: zSearchGz =
;: zPP h ∪=
endfor; {сформовано тимчасовий багатогранник із )( km + точок}
for 1:=i to l do
ВідбірДляМутації );( Px∈
=:x Мутація )(x ;
);(_: xSearchGx =
;: xPP hh ∪=
endfor; {сформовано тимчасовий багатогранник із lkm ++ точок}
=:hP ВідбірПопуляції )(P ;
;1: += hh
until виконується умова завершення;
;}:)({minarg: Pyyfx ∈=
return x ;
end.
Позначення.
/,ba< — напівінтервал у просторі перестановок від перестановки a
до b , виключаючи перестановку b ;
)(yL — заданий окіл точки Py∈ .
Параметри.
m — число вершин багатогогранника (число осіб у популяції в термі-
нах ГА);
k — кількість пар вершин, які вибираються для дослідження (прове-
дення напівпрямих від поточної точки до максимально віддаленої та пошуку
мінімуму на цих прямих);
l — кількість вершин, які підлягають мутації;
∞x — точка, максимально віддалена у просторі варіантів розв’язку від
початкової точки x (діаметрально протилежна у просторі X );
G_Search — процедура G -алгоритму;
Застосування Н-методу для розв’язання задач комбінаторної оптимізації на перестановках
Системні дослідження та інформаційні технології, 2007, № 2 81
ВідбірПопуляції — процедура відбору, наприклад, ))(( lkm ++ -
стратегія: вибір m точок із )( lkm ++ точок тимчасового багатогогранника
(популяції).
Використання наведеної схеми може породжувати сімейство алгорит-
мів комбінаторної оптимізації за рахунок можливих способів конкретизації
(із урахуванням досвіду застосування та специфіки задачі) таких її аспектів.
1. Правила відбору чергової пари точок Pyx ∈, для варіації:
• вибір таких точок, які відповідають найкращому і найгіршому зна-
ченню цільової функції серед точок P ;
• випадковий вибір точок;
• вибір «найгіршої» точки x і випадковий вибір точки y.
2. Відбір для мутації. Використовується випадковий відбір l точок.
Сама мутація полягає у збуренні декількох компонентів вибраного варіанта
розв’язку.
3. Стратегія формування нового багатогранника, що повинен складати-
ся із m точок тимчасового багатогранника обсягом )( lkm ++ точок:
• відбір m кращих точок;
• включення нащадків на основі критерію Метрополіса [6];
• заміна всіх m батьків кращими із )( lk + нащадків, lkm +≤ .
4. Критерієм завершення обчислювального процесу може бути:
• перевищення заданої кількості maxH оновлення множини P : алго-
ритм завершує роботу, коли maxHh > ;
• прагнення до нуля розкиду значень цільової функції у точках мно-
жини P :
}:)(min{}:)({max PxxfPxxf ∈−∈=σ ;
• всі пари точок вже прийняли участь у формуванні напівінтервалів,
якщо використовується однозначний спосіб побудови /, ∞< xx .
5. Спосіб побудови напівінтервалів /, ∞< xx . Скінченні комбінаторні
метричні простори, які розглядаються, мають дві характерні особливості:
• для довільного Px∈ «максимально віддаленою» є точка, що задо-
вольняє умові: }:),(max{ Xuuxdx ∈=∞ , де ),( uxd — метрика на Х
(часто це значення дорівнює діаметру простору X );
• між двома несусідніми точками Pyx ∈, можна побудувати не один,
а декілька d -відрізків, тому при реалізації H -алгоритмів слід роз-
різняти випадок, коли із множини можливих d -відрізків
2),(,, >>< yxdyx завжди за конкретним правилом/способом побу-
дови вибирається лише один чи коли можуть розглядати-
ся/будуватися всі можливі відрізки. У залежності від цього може мо-
дифікуватися і правило «ВідбірДляВаріації»: якщо розглядається
один можливий напівінтервал /, ∞< xx , причому /, ∞∈< xxy , то
Л.Ф. Гуляницький, Д.А. Гобов
ISSN 1681–6048 System Research & Information Technologies, 2007, № 2 82
вершини yx, після відбору слід помітити як «відпрацьовані»,
оскільки їх повторний вибір уже стає недоречним. Якщо ж є можли-
вість будувати всі чи декілька можливих напівінтервалів /, ∞< xx , то
повторний відбір пари yx, стає доцільним, якщо при цьому буде
побудований новий напівінтервал.
ОБЧИСЛЮВАЛЬНИЙ ЕКСПЕРИМЕНТ
Оцінювання ефективності H -алгоритму проводилося у два етапи. Перший
передбачав розв’язання квадратичних задач про призначення, для яких
відомі розв’язки [10]. На другому етапі розв’язувались серії квадратичних
задач про призначення (КЗП) різних розмірностей з невідомим точним
розв’язком.
Ефективність H -алгоритму порівнювалась з алгоритмами детермі-
нованого пошуку, а саме з методом вектора спаду з кільцевим алгорит-
мом перебору точок в околі (АКП) [11]), з алгоритмами імітаційного від-
палу та мультистартового G -алгоритму [6, 11]. Під мультистартовим
G -алгоритмом розуміється така процедура: обирається випадкова переста-
новка, що подається як початкове наближення на вхід G -алгоритму, а
отриманий варіант розв’язку додається до множини розв’язків. Подібні дії
повторюються задану кількість разів і з отриманої множини розв’язків оби-
рається найкращий. Крім того були реалізовані ГА у загальному вигляді
(ЗГА), меметичний алгоритм (Mem), гібридний генетичний алгоритм на ос-
нові G -алгоритму ( G -ГА), мультистартовий G-алгоритм (MG), метод де-
формованих багатогогранників (МДМ ), гібридний метод деформованих
багатогранників (МДМ+ G ). Обчислювальний експеримент проводився на
робочій станції з характеристиками: процесор Athlon 900 Mhz, RAM
256 Mb. Результати розв’язання відомих задач наведені в табл. 1, де для ко-
жного методу розв’язку вказано процент відхилення від глобального опти-
муму, n — розмірність задачі, t — обмеження на час роботи алгоритмів в с.
Параметри H -алгоритму та вбудованого G -алгоритму подані у табл. 2, де
M — кількість переходів в одному прогоні [6]. Назва задач в таблиці — це
їх ідентифікатори в роботі [10].
При опрацюванні поточного багатогранника будувались п’ять напівін-
тервалів. Мутації підлягали три вершини багатогранника, в кожній з яких
випадковим чином змінювали місця три елемента. Критерій завершення ро-
боти алгоритму — час роботи більше заданого обмеження. Для побудови
кожного напівінтервалу обирались дві довільні точки з множини P, які ще
не використовувались для напівінтервалів. Якщо при заданому параметрі µ
виконано k прогонів і отримані значення kff ,...,1 , то вважалося, що досяг-
нута рівновага, якщо ε≤
−+
f
ff k 1 , де f — краще середнє значення цільо-
вої функції за k прогонів.
Застосування Н-методу для розв’язання задач комбінаторної оптимізації на перестановках
Системні дослідження та інформаційні технології, 2007, № 2 83
Т а б л и ц я 1 . Точність розв’язання КЗП
Назва
задачі n АКП Відпал ГА Mem ГА+G MG МДМ МДМ
+G H-алг. t
Els19 19 4,21 4,21 16,03 0,00 0,00 0,90 32,12 12,00 0,00 10
Chr20a 20 56,48 20,53 46,26 0,00 1,82 1,37 14,96 9,76 0,00 10
Chr20b 20 35,16 14,19 15,58 7,31 6,44 7,40 6,53 5,13 3,48 10
Chr20c 20 83,04 34,44 45,34 0,00 0,00 0,00 44,68 28,60 0,00 10
Nug21 21 2,38 0,00 0,00 0,00 0,00 0,00 5,09 0,90 0,00 10
Nug22 22 2,84 0,50 1,33 0,00 0,00 0,00 1,84 1,00 0,00 10
Lip40a 40 1,41 1,14 1,78 1,19 1,13 1,14 1,68 1,02 1,01 40
Lip40b 40 18,85 0,00 20,48 0,00 0,00 0,00 19,97 16,59 0,00 40
Lipa50a 50 1,41 0,97 1,62 1,15 1,00 0,99 1,71 0,98 0,97 63
Lipa50 50 18,11 17,08 20,30 0,00 0,00 0,00 22,20 17,40 0,00 63
Esc64a 64 5,17 0,00 15,52 0,00 0,00 0,00 8,62 0,00 0,00 10
Sco81 81 1,98 0,97 10,54 1,10 0,49 1,17 12,24 1,91 0,34 400
Tai100b 100 6,51 5,20 10,14 1,84 1,52 2,16 24,34 3,17 1,34 850
Tai150b 150 2,79 3,92 1,73 0,65 1,48 1,75 1,73 1,58 1,18 1900
Т а б л и ц я 2 . Параметри G та Н-алгоритмів
m Н γ M ε
20 0,01 2,5 5 0,00001
Як обмеження у часі для G -алгоритму використовувався час
5,05*клп += ttG ,
де клпt —– час роботи алгоритма AКП.
Результати розв’язання випадково згенерованих серій задач наведені на
рисунку.
Генерування проводилось на основі датчика випадкових чисел з рівно-
мірним розподілом. Розв’язувались задачі розмірності від 20 до 100 з кро-
ком 10. Для кожної розмірності — по 20 задач. При опрацюванні поточного
багатогранника будувались три напівінтервали. При відборі популяції бра-
лися кращі m точок. Критерій завершення роботи алгоритму — це час ро-
боти більше 1000с або переглянуті всі пари точок у поточному багатогран-
нику. У табл. 3 наведено середній час роботи алгоритмів. Для побудови
напівінтервалу обирались дві точки, що відповідають найкращому і найгір-
шому значенням цільової функції серед точок P . На кожному прогоні для
мутації обирались три точки з багатогранника. Мутація вплинула на три еле-
менти перестановки. Відсоток покращення рахувався від початкового
розв’язку, який генерувався випадково. Обсяг багатогогранників дорівню-
вав 50; 1,0=H ; 4,1=γ .
Л.Ф. Гуляницький, Д.А. Гобов
ISSN 1681–6048 System Research & Information Technologies, 2007, № 2 84
Т а б л и ц я 3 . Середній час роботи алгоритмів
n АКП Імітаційний відпал MG H-алгоритм
20 0,02 9,66 86,38 86,38
30 0,07 64,62 423,21 423,21
40 0,35 140,74 1000 1000
50 0,53 264,33 1000 1000
60 1,18 1000 1000 1000
70 2,43 1000 1000 1000
80 4,47 1000 1000 1000
90 7,56 1000 1000 1000
100 12,43 1000 1000 1000
У табл. 4 наведено значення середньоквадратичного відхилення σ та
величина довірчого інтервалу δ для покращання значення цільової функції.
Т а б л и ц я 4 . Дисперсія ефективності алгоритмів
АКП Імітаційний
відпал G-алгоритм H-алгоритм n
σ δ σ δ σ δ σ δ
20 2,48 1,75 2,39 1,69 2,11 1,49 2,12 1,5
30 1,66 1,17 1,56 1,1 1,46 1,03 1,34 0,95
40 1,34 0,95 1,34 0,95 1,32 0,93 1,27 0,9
50 0,81 0,57 0,9 0,64 0,85 0,6 0,77 0,54
60 0,77 0,54 0,69 0,49 0,64 0,45 0,63 0,44
70 0,68 0,48 0,69 0,49 0,48 0,34 0,5 0,35
80 0,29 0,2 0,31 0,22 0,4 0,28 0,26 0,18
90 0,44 0,31 0,34 0,24 0,31 0,22 0,42 0,3
100 0,36 0,25 0,31 0,22 0,25 0,18 0,21 0,15
Результат розв’ язання серії задач: 1 — H-алгоритм; 2 — MG-алгоритм; 3 — іміта-
ційний відпал; 4 — АКП
7
8
9
10
11
12
13
14
15
16
17
18
19
20 30 40 50 60 70 80 90 100
Розмірність
П
ок
ра
щ
ен
ня
1
2
3
4
, %
Застосування Н-методу для розв’язання задач комбінаторної оптимізації на перестановках
Системні дослідження та інформаційні технології, 2007, № 2 85
Як бачимо, довірчі інтервали достатньо малі, тому оцінки ефективності
алгоритмів можна вважати достовірними.
ВИСНОВКИ
Обчислювальний експеримент показав високу ефективність Н-алгоритмів як
відносно алгоритмів локального пошуку, так і імітаційного відпалу, мульти-
стартового G-алгоритму, модифікацій генетичних алгоритмів та алгоритмів
методу деформацій. При проведенні досліджень виявлено, що великий
вплив на ефективність Н-алгоритму мають параметри використовуваного
G-алгоритму, і тому вибір їх значень стає актуальним.
Потребує додаткового вивчення залежність ефективності Н-алгоритму
від кількості напівінтервалів, які будуються на кожному кроці алгоритму, а
також залежності оптимальної розмірності популяції від розмірності задачі.
Цікавим для дослідження є теоретичний аналіз ефективності Н-алгоритмів з
різними правилами вибору точок із популяції для побудови напівінтервалу.
Важливий напрямок подальших розробок — теоретичні дослідження
трудомісткості алгоритму та оцінок збіжності при розв’язанні конкретних
типів задач комбінаторної оптимізації.
Реалізовано клас нових ефективних гібридних алгоритмів розв’язання
задач комбінаторної оптимізації на перестановках, побудований на основі
методу деформованих багатогогранників та G-алгоритмів. Запропоновано
алгоритми побудови відрізків та напівінтервалів у просторі перестановок,
які проходять через дві задані точки.
Досліджено ефективність одного алгоритму з розробленого класу при
розв’язанні відомих квадратичних задачах про призначення та серії згенеро-
ваних задач у порівнянні з методами локального пошуку, ймовірнісними
методами, модифікаціями генетичного алгоритму. Продемонстровано кон-
курентоспроможність розробленого класу алгоритмів у порівнянні з наведе-
ними відомими алгоритмами.
ЛІТЕРАТУРА
1. Meta-Heuristics – Advances and Trends in Local Search Paradigms for Opti-
mization / S. Vob, S. Martello, I.H. Osman, C. Roucaisol. — Dordrecht: Klu-
wer Academic Publishers. — 1999. — 528 p.
2. Osman I. H., Laporte G. Metaheuristics: A bibliography// Ann. Oper. Res. —
1996. — № 63. — P. 513–623.
3. Metaheuristics network website // http: www.metaheuristics.net.
4. Hoos H.H., Stützle T. Stochastic Local Search: Foundations and Applications. — San
Francisco: Morgan Kaufmann Publ., 2005. — 658 p.
5. Blum C., Roli A. Metaheuristics in Combinatorial Optimization: Overview and
Conceptual Comparison // ACM Computing Surveys. — 2003. — 35, №. 3. —
Р. 268–308.
Л.Ф. Гуляницький, Д.А. Гобов
ISSN 1681–6048 System Research & Information Technologies, 2007, № 2 86
6. Гуляницкий Л.Ф. Решение задач комбинаторной оптимизации алгоритмами
ускоренного вероятностного моделирования // Компьютерная математи-
ка. — 2004. — № 1. — С. 64–72.
7. Гуляницкий Л.Ф. Метод деформаций в дискретной оптимизации // Исследова-
ние операций и АСУ. — 1989. — Вып. 34. — С. 30–33.
8. Гуляницький Л.Ф. Один гібридний алгоритм комбінаторної оптимізації //
Abstract of Int. Ukrainian-Polish Workshop «Problems of Stochastic and
Discrete Optimization» (May 10 – 15, 2005, Kaniv, Ukraine). — Kaniv, 2005. —
С. 63–65.
9. Химильблау Д. Прикладное линейное программирование. — М.: Мир, 1974. —
534 с.
10. QAPLIB // http://www.opt.math.tu-graz.ac.at/qaplib/.
11. Гуляницкий Л.Ф., Гобов Д.А. О сравнении эффективности алгоритмов решения
одного класса задач размещения прямоугольников на полубесконечной
ленте // Компьютерная математика. — 2003. — № 1. — С. 64–72.
Надійшла 20.07.2006
|
| id | journaliasakpiua-article-127656 |
| institution | System research and information technologies |
| keywords_txt_mv | keywords |
| language | Ukrainian |
| last_indexed | 2025-07-17T10:23:44Z |
| publishDate | 2018 |
| publisher | The National Technical University of Ukraine "Igor Sikorsky Kyiv Polytechnic Institute" |
| record_format | ojs |
| resource_txt_mv | journaliasakpiua/a6/c384fc6a36e54e333e7621134348d9a6.pdf |
| spelling | journaliasakpiua-article-1276562018-04-11T11:12:54Z Application of the H-method to solving combinatorial optimization problems on permutations Использование Н-метода для решения задач комбинаторной оптимизации на перестановках Застосування Н-методу для розв’язання задач комбінаторної оптимізації на перестановках Hulianytskyi, L. F. Gobov, D. A. A hybrid algorithm class for combinatorial optimization problems solving is considered. The class is named the H-method and built on the basis of synthesis of the accelerated probabilistic simulation algorithm (G-algorithm) and the modified discrete downhill simplex method. Algorithms for segment and half-interval building in the permutation space are proposed and proved. They are used for quadratic assignment problem solving. The computational experimental results are given, which demonstrate a high efficiency of the developed algorithms in comparison with some known algorithms. Предложен класс гибридных алгоритмов решения задач комбинаторной оптимизации (H-метод), построенный на основе синтеза алгоритма ускоренного вероятностного моделирования (G-алгоритм) и модифицированного дискретного метода деформированных многогранников. Обоснованы алгоритмы построения отрезков и полуинтервалов в пространстве перестановок для решения квадратичной задачи о назначениях. Приведены результаты вычислительного эксперимента, которые демонстрируют эффективность разработанных алгоритмов в сравнении с некоторыми известными. Запропоновано клас гібридних алгоритмів розв’язання задач комбінаторної оптимізації (H-метод), який побудовано на основі синтезу алгоритму прискореного ймовірнісного моделювання (G-алгоритм) та модифікованого дискретного методу деформованих багатогранників. Обґрунтовано алгоритми побудови відрізків та напівінтервалів у просторі перестановок для розв’язання квадратичної задачі про призначення. Наведено результати обчислювального експерименту, що демонструють ефективність розроблених алгоритмів у порівнянні з деякими відомими. The National Technical University of Ukraine "Igor Sikorsky Kyiv Polytechnic Institute" 2018-04-02 Article Article application/pdf https://journal.iasa.kpi.ua/article/view/127656 System research and information technologies; No. 2 (2007); 74-86 Системные исследования и информационные технологии; № 2 (2007); 74-86 Системні дослідження та інформаційні технології; № 2 (2007); 74-86 2308-8893 1681-6048 uk https://journal.iasa.kpi.ua/article/view/127656/122423 Copyright (c) 2021 System research and information technologies |
| spellingShingle | Hulianytskyi, L. F. Gobov, D. A. Застосування Н-методу для розв’язання задач комбінаторної оптимізації на перестановках |
| title | Застосування Н-методу для розв’язання задач комбінаторної оптимізації на перестановках |
| title_alt | Application of the H-method to solving combinatorial optimization problems on permutations Использование Н-метода для решения задач комбинаторной оптимизации на перестановках |
| title_full | Застосування Н-методу для розв’язання задач комбінаторної оптимізації на перестановках |
| title_fullStr | Застосування Н-методу для розв’язання задач комбінаторної оптимізації на перестановках |
| title_full_unstemmed | Застосування Н-методу для розв’язання задач комбінаторної оптимізації на перестановках |
| title_short | Застосування Н-методу для розв’язання задач комбінаторної оптимізації на перестановках |
| title_sort | застосування н-методу для розв’язання задач комбінаторної оптимізації на перестановках |
| url | https://journal.iasa.kpi.ua/article/view/127656 |
| work_keys_str_mv | AT hulianytskyilf applicationofthehmethodtosolvingcombinatorialoptimizationproblemsonpermutations AT gobovda applicationofthehmethodtosolvingcombinatorialoptimizationproblemsonpermutations AT hulianytskyilf ispolʹzovanienmetodadlârešeniâzadačkombinatornojoptimizaciinaperestanovkah AT gobovda ispolʹzovanienmetodadlârešeniâzadačkombinatornojoptimizaciinaperestanovkah AT hulianytskyilf zastosuvannânmetodudlârozvâzannâzadačkombínatornoíoptimízacíínaperestanovkah AT gobovda zastosuvannânmetodudlârozvâzannâzadačkombínatornoíoptimízacíínaperestanovkah |