Informacijos mokslai ISSN 1392-0561 eISSN 1392-1487
2019, vol. 85, pp. 115–134 DOI: https://doi.org/10.15388/Im.2019.85.19
Dviejų lygių iteracinis tabu paieškos algoritmas kvadratinio paskirstymo uždaviniui
Alfonsas Misevičius
Kauno technologijos
universiteto
Multimedijos inžinerijos katedros tech. m. dr.,
profesorius
Kaunas University of Technology,
Department of
Multimedia Engineering, Dr., Prof.
Studentų g. 50-400/416a, LT-51368
Kaunas
El. paštas alfonsas.misevicius@ktu.lt
Dovilė
Kuznecovaitė (Verenė)
Kauno technologijos
universiteto
Multimedijos inžinerijos katedros doktorantė
Kaunas
University of Technology,
Department of Multimedia Engineering, PhD
Student
Studentų g. 50-408, LT-51368 Kaunas
El. paštas dovile.kuznecovaite@ktu.lt
Santrauka. Šiame straipsnyje nagrinėjamas vadinamasis dviejų lygių iteracinis tabu paieškos (ITP) algoritmas kvadratinio paskirstymo (KP) uždaviniui. Algoritmo naujumas yra tas, jog į jį yra integruotos sprendinių mutavimo procedūros, kurių esminė paskirtis yra diversifikuoti paieškos procesą, išvengiant paieškos stagnacijos ir taip padidinant jos efektyvumą. Algoritmo veikimas išbandytas su įvairių tipų mutavimo procedūrų realizavimo variantais. Atlikti kompiuteriniai eksperimentai su KP uždavinio testavimo duomenų pavyzdžiais iš standartinių pavyzdžių bibliotekos QAPLIB. Pateikti eksperimentų rezultatai, kurie iliustruoja, kaip skirtingos prigimties mutavimo procedūros, esančios ITP sudėtyje, gali įvairiai paveikti algoritmo efektyvumą.
Pagrindiniai žodžiai: skaitmeninis intelektas, kombinatorinis optimizavimas, euristiniai optimizavimo algoritmai, tabu paieška, mutavimo procedūros, kvadratinio paskirstymo uždavinys.
A 2-Level Iterated Tabu Search Algorithm for the Quadratic Assignment Problem
Summary. In this paper, a 2-level iterated tabu search (ITS) algorithm for the solution of the quadratic assignment problem (QAP) is considered. The novelty of the proposed ITS algorithm is that the solution mutation procedures are incorporated within the algorithm, which enable to diversify the search process and eliminate the search stagnation, thus increasing the algorithm’s efficiency. In the computational experiments, the algorithm is examined with various implemented variants of the mutation procedures using the QAP test (sample) instances from the library of the QAP instances – QAPLIB. The results of these experiments demonstrate how the different mutation procedures affect and possibly improve the overall performance of the ITS algorithm.
Keywords: computational intelligence, combinatorial optimization, heuristic algorithms, tabu search, mutation procedures, quadratic assignment problem.
Received: 25/10/2018. Accepted: 14 /2/2019
Copyright © 2018 Alfonsas Misevičius, Dovilė Kuznecovaitė (Verenė). Published by Vilnius University Press. This is an Open Access article distributed under the terms of the Creative Commons Attribution Licence, which permits unrestricted use, distribution, and reproduction in any medium, provided the original author and source are credited.
Įvadas
Kvadratinio
paskirstymo (KP) uždavinys (angl. quadratic assignment problem
(QAP)) matematiškai formuluojamas taip. Duotos dvi neneigiamų
sveikųjų skaičių matricos ir
, taip pat aibė
, kurią sudaro
visi galimi natūrinių skaičių nuo
iki
perstatymai[1]. Tikslas yra surasti perstatymą
ir tokį, jog būtų minimizuota ši funkcija:
. (1)
Dėstymo teorijos
(angl. location theory) kontekste su KP uždaviniu gali būti
modeliuojamas įrengimų išdėstymas į
paskyrimo vietų, turint tikslą
minimizuoti bendrą kainą, atsižvelgiant į įrengimų susietumą ir atstumus
tarp paskyrimo vietų (Koopmans, Beckmann, 1957). Čia matricos
reikšmės
asocijuojamos su įrengimų susietumo svoriais, o matricos
reikšmės nurodo
atstumus tarp paskyrimo vietų.
Dar vienas kvadratinio paskirstymo
uždavinio taikymo pavyzdys – tai elektroninių komponentų išdėstymas
spausdinto montažo plokštės (ar kristalo) pozicijose (Hanan, Kurtzberg,
1972). Šiame kontekste matricos elementai yra elektrinių
sujungimų tarp komponentų porų kiekiai. Matricos
elementai atitinka atstumus
tarp fiksuotų pozicijų montažinėje plokštėje (kristale). Tuomet perstatymas
gali būti interpretuojamas kaip atskira komponentų išdėstymo pozicijose
konfigūracija. Perstatymo elementas
šiuo atveju nurodo numerį
pozicijos, į kurią paskirtas i-tasis komponentas. Tokiu būdu
(tiksliau,
) gali būti suprantamas kaip bendras sujungimų tarp komponentų
ilgis, kuomet visi
komponentai yra išdėstyti
atitinkamose
pozicijų. (Literatūroje galima rasti ir dar daugiau KP
uždavinio praktinio taikymo pavyzdžių aprašymų (Çela, 1998).)
Kita
vertus, KP uždavinys yra matematinis uždavinys, t. y. kombinatorinio
optimizavimo uždavinys. Šiuo atveju tikslas yra surasti optimalų sprendinį,
kur sprendiniai yra išreiškiami natūrinių skaičių perstatymais. Optimalumo
kriterijus aprašomas (1) formule, o funkcija yra vadinama tikslo funkcija
(TF).
Įrodyta, jog KP uždavinys priklauso NP sunkių optimizavimo
uždavinių klasei (Sahni, Gonzalez, 1976). Tai reiškia, kad skaičiavimų
laikas, reikalingas optimumui pasiekti, yra susietas su uždavinio apimtimi
eksponentine priklausomybe. Dėl šios priežasties KP uždavinio sprendimui
naudojami euristiniai optimizavimo algoritmai (Michalewicz, Fogel, 2000;
Yang, 2010; Edelkamp, Schrödl, 2012; Siarry, 2016). Nors šie algoritmai
negarantuoja optimalaus sprendinio suradimo, tačiau jie leidžia gauti
pakankamai aukštos kokybės (artimus optimaliems) sprendinius per priimtiną
skaičiavimų laiką. KP uždaviniui sėkmingai išbandyti šie euristiniai
algoritmai: atkaitinimo modeliavimas (angl. simulated annealing)
(Misevičius, 2003), genetiniai algoritmai (angl. genetic algorithms)
(Merz, Freisleben, 2000; Drezner, 2003; Misevicius, 2004; Tang ir kt., 2006;
Ahmed, 2015; Benlic, Hao, 2015; Chmiel, Kwiecień, 2018), tabu paieška (angl.
tabu search) (Taillard, 1991; Misevicius, 2005; Shylo, 2017),
godžiosios randomizuotos adaptyvios paieškos procedūros (angl. greedy
randomized adaptive search procedures (GRASP)) (Li ir kt., 1994),
iteratyvioji lokalioji paieška (angl. iterated local search)
(Stützle, 2006), skruzdėlių kolonijų (Gambardella ir kt., 1999), bičių
spiečių (Dokeroglu ir kt., 2019) imitavimo algoritmai (angl. artificial
bee colony, ant colony optimization) ir kt. (Benlic, Hao, 2013;
Hafiz, Abdennour, 2016; Aksan ir kt., 2017; Abdel-Basset ir kt., 2018;
Chmiel, 2019). Nepaisant pasiektų daug žadančių rezultatų, euristinių
algoritmų KP uždaviniui tolesnio išvystymo ir tobulinimo klausimai vis dar
išlieka aktuali mokslinių tyrinėjimų tema.
Šiame straipsnyje aprašomas patobulintas tabu paieškos (TP) algoritmas – vadinamasis dviejų lygių iteracinis tabu paieškos (ITP) algoritmas. Algoritmo veikimo principo naujoviškumas yra tas, kad tabu paieškos procedūra yra vykdoma iteraciniu būdu, pradedant vis nuo naujo sprendinio (pereinant tarp skirtingų lokaliai optimalių sprendinių). Iteracinį tabu paieškos algoritmą sudaro šie pagrindiniai komponentai: tabu paieškos procedūra, sprendinio-kandidato parinkimas, parinkto sprendinio mutavimas. TP procedūra atliekama kuo greičiau, panaudojant nedidelį iteracijų skaičių. Gautas TP procedūros sprendinys po to yra perturbuojamas mutavimo procedūroje tam, kad būtų diversifikuotas paieškos procesas, taip bandant išvengti paieškos stagnacijos, kas yra viena pagrindinių kliūčių vykdant standartinę, neiteracinę TP. Siekiant nustatyti galimą efektyviausią ITP modifikaciją, buvo tirta daugiau nei 10 mutavimo proceso realizavimo variantų.
Straipsnio struktūra yra tokia. Iš pradžių pateikiamos bazinės formuluotės. Po to aprašomas dviejų lygių iteracinis tabu paieškos algoritmas ir į jį integruotos sprendinių mutavimo procedūros. Taip pat pateikiami kompiuterinių-eksperimentinių tyrimų rezultatai, gauti išbandžius įvairius mutavimo procedūrų algoritminio realizavimo variantus. Straipsnis baigiamas apibendrinamosiomis pastabomis.
Dviejų lygių iteracinis tabu paieškos algoritmas
Bazinės formuluotės
Pradžioje pateikiame bazines formuluotes (apibrėžimus).
1. Tarkime, kad (
) ir
(
,
) yra du
perstatymo (sprendinio)
elementai, kurie vykdant
algoritmą gali būti sukeisti vietomis. Tuomet
apibrėšime taip:
.
(2)
Tai reiškia, kad perstatymas gaunamas iš perstatymo
, tame
perstatyme sukeičiant elementus
ir
vietomis. Galima pastebėti,
kad galioja tokios lygybės:
,
,
. Taip pat bet kokiems
tarpusavyje skirtingiems
galioja
,
.
2. Tikslo
funkcijos () pokytis (
), sukeitus
sprendinio-perstatymo elementus
ir
vietomis, apskaičiuojamas
pagal šią bendrą formulę:
.
(3)
Tikslo funkcijos pokytį dviem „perstatymams-kaimynams“ ir
, kai
,
galima apskaičiuoti ir žymiai greičiau – su sąlyga, jog yra įsimintos
(išsaugotos) visos ankstesnių pokyčių reikšmės
(
). Pokyčiams saugoti pakanka
dvimatės matricos, o pokyčio reikšmė gaunama, panaudojant
operacijų
(Taillard, 1991). Atlikus elementų
ir
sukeitimą, naujos pokyčių
reikšmės
(
,
,
,
) apskaičiuojamos pagal šią formulę:
+
. (4)
Pastaba. Jeigu
arba
arba
arba
, tai turi būti
taikoma (3) formulė. Nors pastarosios formulės sudėtingumas yra
, tačiau
ji taikoma tik keturioms indeksų poroms, o tai įgalina visas pokyčių
reikšmes apskaičiuoti panaudojant tik
operacijų. Išimtį sudaro
inicializacijos fazė, t. y. pirmoji pokyčių apskaičiavimo iteracija, kurios
metu reikia (bet tik vieną kartą) atlikti
operacijų.
Jeigu
matrica ir / arba matrica
yra simetrinė(s), tai (3)
formulė supaprastėja. Sakykime, kad matrica
yra simetrinė. Tuomet galima
transformuoti (asimetrinę) matricą
į simetrinę matricą
; tam
pakanka sudėti atitinkamus matricos
elementus. Taip gauname
žemiau pateikiamą formulę:
; (5)
čia ,
,
,
.
Analogiškai (4) formulė virsta tokia formule:
. (6)
Jeigu i = u(v) arba j = u(v), tai turi būti taikoma (5) formulė.
Disponuojant pakankamos apimties
kompiuterine atmintimi, galima vietoje dvimačių matricų ir
panaudoti
atitinkamas trimates matricas
ir
. Tarkime, kad
,
o
, čia
,
,
. Tuomet tikslo funkcijos
pokyčius galime apskaičiuoti panaudodami labai kompaktiškas
formules:
, (7)
+
. (8)
Matricoms ir
suformuoti panaudojama
operacijų; tas atliekama dar
prieš pradedant vykdyti algoritmą. Taigi, tai neturi kiek nors žymesnės
įtakos bendram algoritmo sudėtingumui; atvirkščiai, atlikti praktiniai
eksperimentai patvirtino išankstinę prielaidą, jog galima sutaupyti iki 20
proc. procesorinio laiko. (Aišku, kompiuterinės atminties sunaudojimas
išauga: matricų
,
saugojimui reikia
atminties.)
3. Atstumas
(vadinamasis Hemingo atstumas) tarp dviejų perstatymų ir
apibrėžiamas kaip
.
Galioja tokios lygybės:
,
,
,
,
. Pastebėsime, jog bet kuriems
(
,
,
)
.
Apskritai, jei turime
skirtingų
, tai yra teisinga
ši lygybė:
.
4. Sprendinio-perstatymo aplinka (porinių sukeitimų
aplinka)
apibrėžiama pagal formulę:
. Kitaip tariant, aplinką
sudaro sprendiniai:
,
, …,
,
, …,
, …,
,
,
…,
, …,
. Tokiu būdu aplinkos
dydis
yra lygus
. Tiek žingsnių reikia atlikti norint visiškai išnagrinėti
esamo sprendinio
aplinką
. Taigi, šiai aplinkai
išnagrinėti pakanka
operacijų. Gali būti
apibrėžiamos ir kitokios aplinkos (bendruoju atveju sprendinio
aplinką
žymėsime
). Sprendinių aplinkų visuma sudaro sprendinių paieškos aibę
(sprendinių paieškos erdvę).
5. Sprendinys vadinamas lokaliai optimaliu
sprendiniu aplinkos
atžvilgiu, jeigu kiekvienam
sprendiniui
iš aplinkos
galioja
(kitaip tariant,
sprendinio
aplinkoje
nėra nė vieno geresnio
sprendinio už
).
6. Mutavimo (angl. mutation) procesas
sprendinių-perstatymų atveju gali būti apibrėžiamas panaudojant formalų
operatorių :
. Taigi, jeigu
, tai
; be to,
. Galima
naudoti ir labiau formalizuotą operatorių
:
, kuris esamą sprendinį
transformuoja į naują sprendinį
ir tokį, jog
. Skaitytojas
galėtų įsitikinti, kad bet kuriam mutuotam sprendiniui-perstatymui
egzistuoja skaičių seka
ir tokia, jog
. Dydį
(parametrą)
vadinsime mutavimo laipsniu (stiprumu). Akivaizdu, jog 2
. Taigi,
po mutavimo pakinta
procentų sprendinio elementų.
Parametras
yra iš esmės vienintelis kiekybinis mutavimo procesą
reguliuojantis veiksnys. Kuo didesnė
reikšmė, tuo daugiau
sprendinio elementų sukeičiama (tuo didesniu mastu pakinta sprendinys, tuo
labiau mutuotas sprendinys „nutolsta“ nuo esamo sprendinio) ir atvirkščiai.
Galima šiuo atveju manyti, kad mutavimo operatorius
transformuoja
esamą sprendinį
į kitą sprendinį, priklausantį sprendinio
aplinkai
. Dar
sakoma, jog atliekamas perėjimas (
perėjimas) iš sprendinio
į
sprendinį
(sprendinio
pakeitimas sprendiniu
).
Atskiras mutavimo operatoriaus atvejis yra dviejų perstatymo elementų
sukeitimo operatorius
:
, kuris sukeičia perstatymo
u-tąjį ir v-tąjį elementus vietomis, t. y.
. Daugelis
euristinių algoritmų KP uždaviniui remiasi būtent šio operatoriaus ir
aplinkos
, kaip nereikalaujančios didelio skaičiavimų kiekio,
panaudojimu.
Grįždami prie mutavimo, pastebėsime, jog mutavimas kartu su kryžminimu yra pagrindiniai evoliucinių (genetinių) algoritmų operatoriai. Trumpai sakant, mutavimui savybingas grynai atsitiktinis pobūdis, mutavimo procesas savo prigimtimi yra indeterminuotas procesas. Tuo mutavimas iš esmės skiriasi nuo kryžminimo procedūrų. Mutavimo proceso metu generuojamos, apskritai kalbant, naujos sprendinių savybės, nauja informacija; o kryžminimo procedūros paprastai tik (re)kombinuoja informaciją, esančią pirmtakuose. Skirtingai negu standartinėse kryžminimo procedūrose, kur yra paveldimas sukauptas genetinis kodas iš dviejų pirmtakų ir daugiau niekur kitur, mutavimo procedūrose pagrindinis dalykas yra ne informacijos perdavimas, o kitos, naujos informacijos įnešimas, informacijos, kurios prieš tai dar nebuvo, sukūrimas. Šiuo požiūriu mutavimo procesas yra labiau kaip potencialaus naujumo generavimo procesas, kaip labiau kuriantysis, užuomazginis procesas, palyginti su kryžminimu. Be to, mutavimui nebūtina sprendinių populiacija, pakanka tik vieno sprendinio.
Tabu paieškos algoritmas
Skirtingai nuo tradicinių lokaliosios paieškos algoritmų, kurie apsiriboja vieno lokaliai optimalaus sprendinio suradimu, TP algoritmai tęsia paiešką ir tuo atveju, kai gauto sprendinio aplinkoje nebeegzistuoja geresnių sprendinių-kaimynų. Esminė TP idėja yra ta, jog yra (laikinai) uždraudžiama grįžti į tuos pačius, neseniai nagrinėtus sprendinius tam, kad būtų išvengta paieškos ciklinimosi, t. y. kartojimo nuo to paties išeities „taško“ (Glover, Laguna, 1997). Tam tikrais periodais atskiri sprendiniai yra uždraudžiami („įšaldomi“), skelbiami „tabu“. Laikinų draudimų strategija leidžia „neįstrigti“ lokaliųjų optimumų zonose ir suteikia galimybes po laikinų TF pablogėjimų tęsti paiešką naujose sprendinių erdvės srityse. Taip galima pereiti nuo vieno lokaliai optimalaus sprendinio prie kito, tikėtina, geresnio; tai kartojant daug kartų, žymiai išauga tikimybė surasti aukštesnės kokybės sprendinius.
Vykstant TP
procesui analizuojama esamojo sprendinio aplinka (mūsų atveju —
) ir
atliekamas tas nedraudžiamas perėjimas, kuris labiausiai pagerina (sumažina)
tikslo funkcijos
reikšmę. Jeigu nėra pagerinančių perėjimų, tai pasirenkamas
tas, kuris mažiausiai pablogina TF reikšmę. Tam, kad būtų eliminuoti
paieškos ciklai, atvirkštinis perėjimas, taip pat grįžimas į kitus neseniai
aplankytus sprendinius turi būti uždraudžiamas apibrėžtam laikotarpiui.
Draudimai saugomi tabu atmintyje, t. y. sąraše
, įsimenant paskutinius
nagrinėtus sprendinius. Mūsų atveju tabu sąrašas
realizuotas kaip dvimatė
dydžio
matrica. Šiuo atveju matricos elementas
saugo esamos iteracijos
numerį ir uždraudimo periodą (angl. tabu tenure)
; tokiu būdu ši
reikšmė nurodo, nuo kurios iteracijos vėl galima sukeisti perstatymo
i-tąjį ir j-tąjį narius. Parametro
reikšmė mūsų ITP algoritme yra
prilyginta
. Elementų
,
sukeitimas (perėjimas į
sprendinį
) yra negalimas, jeigu reikšmė
yra didesnė negu esamas
paieškos iteracijos numeris. Draudimas yra anuliuojamas atsitiktiniais
momentais su labai maža tikimybe
(
). (Tai leidžia truputį
padidinti nedraudžiamų sprendinių kiekį ir ne taip apriboti galimas paieškos
kryptis.) Draudimas taip pat yra ignoruojamas, kai patenkinama aspiracijos
sąlyga (angl. aspiration criterion), t. y. po sukeitimo gaunamas
sprendinys, kuris yra geresnis už iki šiol atliekant tabu paieškos procedūrą
rastą geriausią sprendinį. Tabu sąrašas yra dinamiškai atnaujinamas vykdant
algoritmą (kai tik esamas sprendinys pakeičiamas nauju).
Kartu su tabu
sąrašu mūsų tabu paieškos procedūra dar naudoja papildomą atmintį (antrinę
atmintį-archyvą (angl. secondary memory)) (Dell’amico, Trubian,
1998). Šios atminties paskirtis yra išsaugoti aukštos kokybės sprendinius,
kurie nors ir buvo įvertinti kaip labai geri, bet nebuvo pasirinkti.
Konkrečiai sakant, į antrinę atmintį kiekvienos iteracijos metu įtraukiami
sprendiniai, likę „antri“ po aplinkos
patikrinimo. Jeigu vykdant
tabu paieškos procedūrą geriausias rastas sprendinys nesikeičia daugiau kaip
iteracijų, tai tabu sąrašas išvalomas ir paieška paleidžiama, pradedant nuo
vieno iš „antrųjų“ sprendinių iš antrinės atminties
(čia
yra
nustatytas TP procedūros vykdymo iteracijų skaičius, o
– parinktas
tuščios eigos limito koeficientas, toks, jog
). Reikia pastebėti, jog
archyve išsaugomos ir visos tikslo funkcijos pokyčių reikšmės (
), tai
padidina atminties sąnaudas, bet skaičiavimų laikui tai labai didelės įtakos
nedaro. TP algoritmo sudėtingumas išlieka proporcingas
, o tokio archyvo
panaudojimas, kaip rodo eksperimentų rezultatai, prisideda prie to, jog
efektyvumas padidėja dėl to, jog sumažinamas neigiamas paieškos stagnacijos
poveikis. Antrinė atmintis išvaloma, pasibaigus TP procedūrai.
TP
procesas yra baigiamas, kai tik atliekamas iš anksto pasirinktas TP vykdymo
iteracijų skaičius (). TP algoritmo detalizuotas
formalus aprašymas pateiktas 1 pav.
procedure Tabu_Paieška; // tabu paieškos algoritmas KP uždaviniui
// duomenys: p - esamas sprendinys-perstatymas (kartu su atitinkamais tikslo funkcijos reikšmių pokyčiais (Δ)),
// n - uždavinio dydis (perstatymo dydis)
// rezultatai: p• - geriausias rastas sprendinys (kartu su TF reikšmių pokyčiais)
// valdymo parametrai: τ - tabu paieškos vykdymo iteracijų skaičius, h - uždraudimo (tabu) periodas,
// α - tabu paieškos randomizavimo koeficientas, β - tuščios eigos limito koeficientas
begin
p• := p; k := 1; k′ := 1; archyvo_skaitiklis := 0; L := ; // L - tuščios eigos
limitas
while (k ≤ τ) begin // pagrindinis tabu paieškos iteracijų vykdymo ciklas
delta′min := ∞; delta′′min := ∞; u′ := 1; v′ := 2;
// nagrinėjama sprendinio p aplinka Θ2(p) ir ieškomas geriausias sprendinys, kuris nėra uždraustas (tabu)
for i := 1 to n - 1 do
for j := i + 1 to n do begin
delta := Δ (pi, j, p);
tabu := iif((tij ≥ k) and (random() ≥ α), TRUE, FALSE); aspiracija := iif(z(p) + delta < z(p•), TRUE, FALSE);
if ((delta < delta′min) and (tabu = FALSE)) or (aspiracija = TRUE) then begin
if delta < delta′min then begin
delta′′min := delta′min; u′′ := u′; v′′ := v′; delta′min := delta; u′ := i; v′ := j endif
else if delta < delta′′min then begin delta′′min := delta; u′′ := i; v′′ := j endif
endif
endfor;
if delta′′min < ∞ then begin // „antrojo“ sprendinio įtraukimas į archyvą (antrinę atmintį) G
archyvo_skaitiklis := archyvo_skaitiklis + 1; Γ [archyvo_skaitiklis] ← p, Δ, u′′, v′′ endif;
if delta′min < ∞ then begin
; // esamas sprendinys
pakeičiamas nauju sprendiniu
perskaičiuoti tikslo funkcijos pokyčius
, i, j = 1, ..., n;
if z(p) < z(p•) then begin p• := p; k′ := k endif; // išsaugomas geriausias rastas sprendinys
// elementų
p(u′), p(v′)
sukeitimas uždraudžiamas būsimoms h iteracijų
endif;
if (k - k′ > L) and (k <τ - L) then begin // tabu paieškos paleidimas, panaudojant sprendinį iš archyvo
išvalyti tabu sąrašą T;
atsitiktinio_išrinkimo_indeksas := random(archyvo_skaitiklis * 0.8, archyvo_skaitiklis);
p, Δ, u′′, v′′ ← Γ[atsitiktinio_išrinkimo_indeksas];
:=
; perskaičiuoti tikslo funkcijos pokyčius
, i, j = 1, ..., n;
; k′ := k
endif;
k := k + 1
endwhile;
išvalyti tabu sąrašą T
end.
Pastabos. 1. Tiesioginio vykdymo „if“ funkcija iif(x, y1, y2) grąžina y1, jeigu x = TRUE, kitu atveju grąžinama y2. 2. Funkcija random() generuoja (pseudo)atsitiktinį realųjį skaičių, patenkantį į intervalą [0, 1]. 3. Funkcija random(x1, x2) generuoja (pseudo)atsitiktinį sveikąjį skaičių iš intervalo [x1, x2].
1 pav. Tabu paieškos algoritmo aprašymas
Iteracinis tabu paieškos algoritmas
Tabu paieškos algoritmo panaudojimas dar neužtikrina aukštos surastų sprendinių kokybės dėl jau minėto paieškos stagnacijos efekto pasireiškimo. Vienas iš būdų sumažinti paieškos stagnavimo poveikį yra išplėsti standartinį TP algoritmą taip, kad jis būtų vykdomas ne vieną, bet keletą kartų. Taip gaunama iteratyvioji tabu paieška (ITP) (angl. iterated tabu search), kurios veikimo principo pagrindas yra daugkartinis TP algoritmo panaudojimas, iteratyviu būdu vykdant TP kartotinį procesą ir kombinuojant tabu paiešką su papildomomis sprendinių pertvarkymo, t. y. mutavimo, procedūromis[2]. Iteratyviajai tabu paieškai, savo ruožtu, taip pat gali būti taikomas daugkartinis panaudojimas; taip gaunamas 2 lygių iteratyviosios tabu paieškos algoritmas – savotiškas hierarchinis iteratyviosios tabu paieškos algoritmas. Tokio tipo algoritmo skiriamoji savybė yra ta, jog jis pasižymi savo struktūros hierarchiškumu, tiksliau, panašumumu į save (angl. self-similarity). Panašumas į save, kaip žinoma, yra turbūt vienas iš fundamentaliausių gamtos principų. Mūsų atveju dviejų lygių ITP algoritmą sudaro du panašūs į save struktūriniai lygiai. Aukštesniojo (2-ojo) lygmens algoritmas kreipiasi į žemesniojo (1-ojo) lygio algoritmą, kuris jau betarpiškai naudoja TP algoritmą. Šiuo atveju TP procedūra, galima įsivaizduoti, yra savotiškas iteracinio algoritmo „branduolys“. Būtent ši ir tik ši procedūra vykdo betarpišką sprendinio pagerinimą (atlieka paieškos intensifikavimą).
Du lygiai yra iš esmės tos pačios struktūros. Esamo lygio algoritmą sudaro trys esminiai komponentai: 1) žemesnio lygio algoritmo panaudojimas (iškvietimas); 2) sprendinio-kandidato parinkimas mutavimui; 3) atrinkto sprendinio mutavimas. Nors atskirų lygių struktūra yra išties paprasta, tačiau šių lygių tinkamas sujungimas leidžia žymiai padidinti paieškos efektyvumą. Aišku, paieškos laikas išauga, bet tai yra kompensuojama aukštesne rezultatų kokybe. Atkreiptinas dėmesys į tai, kad sprendinio mutavimas yra labai svarbus komponentas ITP algoritme ir jis yra reikalingas tam, kad būtų galima pereiti į kitas, nenagrinėtas sprendinių aibės (paieškos erdvės) sritis ir išvengti paieškos stagnacijos. Matyti, jog sprendinio mutavimas vykdomas kiekviename lygyje – skirtingai nuo „branduolio“ procedūros (TP procedūros), kuri atliekama tik žemiausiame lygyje. Taigi, iteracinio algoritmo atveju dominuoja paieškos diversifikavimo faktorius, o tai ir yra labai svarbu, vykdant paiešką didžiulėje sprendinių erdvėje su daug lokaliai optimalių sprendinių. Kas dėl sprendinio-kandidato parinkimo mutavimui, tai visada imamas paskutinis gautas (vis kitas) pagerintas sprendinys. Toks parinkimas leidžia išžvalgyti galimai didesnę sprendinių erdvės dalį.
Vieno ir dviejų lygių ITP algoritmų detalizuoti formalūs aprašymai pateikti 2 ir 3 pav.
procedure 1-Lygio_Iteracinė_Tabu_Paieška; // vieno lygio iteracinės tabu paieškos algoritmas KP uždaviniui
// duomenys: p - esamas sprendinys-perstatymas
// rezultatai: pÑ - geriausias rastas sprendinys-perstatymas (kartu su tikslo funkcijos reikšmių pokyčiais (Δ))
// valdymo parametras: Q1 - 1 lygio tabu paieškos vykdymo iteracijų skaičius
begin
pÑ := p;
for q1 := 1 to Q1 do begin
vykdyti procedūrą Tabu_Paieška sprendiniui p, gauti (pagerintą) sprendinį p•;
if z(p•) < z(pÑ) pÑ := p•; // įsimenamas geriausias rastas sprendinys (kartu su TF pokyčiais)
if q1 < Q1 then begin
p := Sprendinio_Kandidato_Parinkimas_Mutavimui(p·, pÑ);
vykdyti mutavimo procedūrą sprendiniui p, grąžinti mutuotą sprendinį p~;
p := p~
endif
endfor
end.
2 pav. Vieno lygio iteracinės tabu paieškos algoritmo aprašymas
procedure 2-jų_Lygių_Iteracinė_Tabu_Paieška; // dviejų lygių iteracinės tabu paieškos algoritmas KP uždaviniui
// duomenys: p° - pradinis sprendinys-perstatymas
// rezultatai: pÑÑ - geriausias rastas sprendinys-perstatymas
// valdymo parametras: Q2 - 2 lygio tabu paieškos vykdymo iteracijų skaičius
begin
generuoti atsitiktiniu būdu pradinį sprendinį-perstatymą p°;
apskaičiuoti tikslo funkcijos pokyčius
, i, j = 1, ..., n;
inicializuoti tabu sąrašą T;
p := p°; pÑÑ := p°;
for q2 := 1 to Q2 do begin
vykdyti procedūrą 1-Lygio_Iteracinė_Tabu_Paieška sprendiniui p, gauti (pagerintą) sprendinį pÑ;
if z(pÑ) < z(pÑÑ) pÑÑ := pÑ; // įsimenamas geriausias rastas sprendinys
if q2 < Q2 then begin
p := Sprendinio_Kandidato_Parinkimas_Mutavimui(pÑ, pÑÑ);
vykdyti mutavimo procedūrą sprendiniui p, grąžinti mutuotą sprendinį p~;
p := p~
endif
endfor
end.
3 pav. Dviejų lygių iteracinės tabu paieškos algoritmo aprašymas
Mutavimo proceso
bazinių variantų algoritminis realizavimas nėra labai sudėtingas. Teorinis
pagrindas yra mutavimo operatorius , formaliai aprašytas sk.
„Bazinės formuluotės“. Atsižvelgiant į mutavimo algoritminio realizavimo
skirtumus (ypatumus), galima sudaryti įvairių tipų mutavimo
procedūras.
Toliau trumpai aprašomos mūsų sudarytos ir tyrime naudotos mutavimo procedūros.
Atsitiktiniai poriniai elementų sukeitimai
Ši mutavimo procedūra yra labai nesudėtinga (žr.
4 pav.). Sukuriamas sprendinio-perstatymo klonas
. Perstatyme
atsitiktinai parenkamos pozicijos
,
, sugeneruojant du skirtingus
(pseudo)atsitiktinius sveikuosius skaičius iš intervalo
pagal tolygiojo
pasiskirstymo dėsnį. (Kad būtų išvengta pasikartojančių atsitiktinių skaičių
generavimo, yra iš anksto sugeneruojamas perstatymas
, sudarytas iš
atsitiktinai sumaišytų sveikųjų skaičių nuo
iki
. Skaičių poros
tokiu būdu nurodo
perstatymo
atsitiktinių pozicijų indeksų poras.) Pradedama nuo poros
, ir
perstatymo
elementai, esantys šiose pozicijose, sukeičiami (iš
pereinama į
). Po to imama pora
ir t. t. Tai kartojama
skaičių
kartų; čia
– algoritmo tyrėjo / vartotojo iš anksto nustatyta (norima)
mutavimo laipsnio reikšmė. Mutavimo procedūros rezultatas – mutuotas
sprendinys
, tenkinantis sąlygą
. Aišku, kad formuojant
mutuotą sprendinį-perstatymą yra užtikrinamas reikalavimas, jog gautame
sprendinyje-perstatyme jokie elementai nesikartoja, t. y.,
. Mutavimo proceso
stiprumas kontroliuojamas panaudojant parametrą
(teoriškai 2
).
Remiantis šiuo mutavimo algoritmo principu galima sudaryti ir daug įvairių kitų modifikuotų mutavimo procedūrų.
4 pav. Mutavimo
procedūros pavyzdžio iliustracija (n = 9, m = 5)
(Šiame pavyzdyje
mutavimo procesas yra toks: elementas 3 keičiamas su elementu 4 (elementas 3
patenka į 3-iąją poziciją); 3 (esantis 3-iojoje pozicijoje) keičiamas su 1;
3 (esantis 4-ojoje pozicijoje) keičiamas su 8; 3 (esantis 6-ojoje
pozicijoje) keičiamas su 5 (3 patenka į 8-ąją
poziciją))
Poriniai elementų sukeitimai panaudojant atsitiktinį raktą
Mutavimo procedūrą šiuo atveju sudaro
du žingsniai: 1) atsitiktiniai poriniai elementų sukeitimai; 2) sukeistų
elementų išmaišymas, panaudojant atsitiktinį raktą. Atsitiktinis raktas yra
papildomas atsitiktinių indeksų nuo iki
masyvas (rinkinys
).
Atsitiktinio rakto reikšmės nurodo, kokie anksčiau sukeisti elementai su
kokiais elementais maišomi. Taip bandoma gauti „giliau“ mutuotą sprendinį,
daugiau randomizuotą elementų išmaišymą. Tuomet vykstant TP procesui ne taip
paprasta grįžti į ankstesnę situaciją, tik atliekant porinius elementų
sukeitimus.
Mutavimas panaudojant priešines (opozicines) reikšmes
Šioje mutavimo procedūroje sprendinio klone
atsitiktinai parenkama pozicija, tarkime,
. Tuomet sprendinio
esama
elemento reikšmė
pakeičiama tokia priešine (opozicine) (angl.
opposition) reikšme:
, čia
žymi liekanos
gavimo operaciją. Po šio sukeitimo taip pat turi būti pakeistas sprendinio
elementas, kuris prieš tai buvo lygus
. Po abiejų sukeitimų
tampa
lygus
,
– lygus
,
rodo sprendinio
elemento
reikšmės, kuri buvo lygi
,
indeksą.
Maksimalaus elementų atstumo mutavimas
Duotoje procedūroje sukeičiamų sprendinio elementų pozicijų
indeksai generuojami taip, jog atstumas () tarp tų pozicijų būtų galimai
didesnis. Panaudota tokia sukeičiamų sprendinio elementų indeksų reikšmių
generavimo formulė:
, čia
,
–
(pseudo)atsitiktinis realusis skaičius iš intervalo
,
,
; pradinė
reikšmė
(
)
– tai atsitiktinis sveikasis skaičius iš intervalo
. Tokiu būdu yra
sugeneruojama
atsitiktinių indeksų reikšmių (priminsime, kad
yra mutavimo
laipsnis). Šiuo atveju rekomenduojama, kad
neviršytų
.
Modifikuotas atsitiktinių elementų sukeitimų mutavimas - I
Ši procedūra panaši į
atsitiktinių porinių elementų sukeitimų mutavimo procedūrą. Generuojamas
atsitiktinių realiųjų skaičių iš intervalo rinkinys (angl. real-coded
values). Sugeneruoti skaičiai (kartu su juos atitinkančiais teigiamais
indeksais (angl. smallest positive values)) išrikiuojami didėjimo
tvarka. Išrikiuotus atsitiktinius skaičius atitinkantys išmaišyti indeksai
ir nurodo, kurias sprendinio
elementų poras reikia sukeisti
(žr. sk. „Atsitiktiniai poriniai elementų
sukeitimai“).
Modifikuotas atsitiktinių elementų sukeitimų mutavimas - II
Duota procedūra yra irgi panaši
į procedūrą, aprašytą sk. „Atsitiktiniai poriniai elementų sukeitimai“.
Procedūros tikslas – nuosekliai, vienas po kito generuojant atsitiktinius
sveikuosius skaičius iš intervalo , iš karto gauti sprendinio
sukeičiamų elementų porų indeksus. Tačiau, kaip pastebėta, atsitiktiniai
sveikieji skaičiai gali dubliuotis. Tam, kad nebūtų dubliavimosi,
sugeneruoti atsitiktiniai sveikieji skaičiai surikiuojami (žr. sk.
„Modifikuotas atsitiktinių elementų sukeitimų mutavimas - I“). Surikiuotus
skaičius atitinkantys indeksai nurodo reikalingus sumaišyti
elementus.
Kombinuoto mutavimo procedūra
Kombinuoto mutavimo procedūroje yra nuosekliai sujungtos dvi mutavimo procedūros. Iš pradžių nustatomi atsitiktiniai perstatymo elementų indeksai, kaip aprašyta sk. „Modifikuotas atsitiktinių elementų sukeitimų mutavimas - II“. Po to nustatyti elementai yra mutuojami, panaudojant priešines reikšmes (žr. sk. „Mutavimas panaudojant priešines (opozicines) reikšmes“).
Randomizuotos lokalios paieškos mutavimas
Šiuo atveju iš pradžių vykdomi atsitiktiniai poriniai elementų sukeitimai (kaip aprašyta sk. „Atsitiktiniai poriniai elementų sukeitimai“). Po to atliekama randomizuota lokalioji paieška, t. y. nuosekliai nagrinėjamos atsitiktinai parinktos sprendinio elementų poros, bet elementų sukeitimai atliekami tik tuo atveju, jeigu po sukeitimo gaunamas geresnis sprendinys (tikslo funkcijos reikšmė sumažėja). Ši ir kitos toliau aprašomos mutavimo procedūros jau nėra tokios universalios (nepriklausančios nuo sprendžiamo uždavinio), kaip anksčiau aprašytos, nes turi būti įvertinama ir tikslo funkcija bei specifinės konkretaus sprendžiamo uždavinio savybės.
Randomizuotos dalinės lokalios paieškos mutavimas
Šioje procedūroje iš pradžių taip pat vykdomi atsitiktiniai elementų sukeitimai. Po to atliekama dalinė randomizuota lokalioji paieška. Šiuo atveju visiškai išnagrinėjama atsitiktiniu būdu sukonstruota, nedidelės apimties sprendinių aplinka. Vykdant paiešką šioje aplinkoje, vėlgi atliekami tik tie perėjimai tarp sprendinių, kurie pagerina tikslo funkcijos reikšmę.
Godžios adaptyvios paieškos mutavimas
Šios mutavimo procedūros principas yra kiek kitoks negu
prieš tai nagrinėtų. Ypatumas yra tas, jog iš pradžių sprendinys savotiškai
„dezintegruojamas“, po to rekonstruojamas. Sprendinio dezintegravimas
reiškia, jog yra anuliuojama (pašalinama) dalis atsitiktinai parinktų
sprendinio elementų, sprendinys tampa dalinis, po to bandoma dalinį
sprendinį rekonstruoti į pilnąjį sprendinį ir taip, kad gautas sprendinys
būtų su kuo mažesne tikslo funkcijos reikšme. Taigi, mutavimą sudaro dvi
fazės: 1) sprendinio dezintegravimas, kuris yra atsitiktinis; 2) sprendinio
rekonstravimas, kuris yra determinuotas (nes siekiama minimizuoti tikslo
funkciją). Mūsų procedūroje pirmos fazės metu yra anuliuojama elementų, t. y.
tiek, koks yra mutavimo laipsnis. Antroje fazėje taikomas godusis
konstravimo algoritmas. Šis algoritmas iš visų galimų
variantų atrenka
tą, kuriam apskaičiuotas tikslo funkcijos įvertinimas (tam tikra tikslo
funkcijos ribos reikšmė) yra minimalus. Mutavimo laipsnio
dydis yra
apribotas (
,
), kad labai neišaugtų mutavimo procedūros atlikimo
laikas.
Godžios randomizuotos adaptyvios paieškos mutavimas
Ši mutavimo procedūra primena prieš tai aprašytąją. Skirtumas yra tas, jog dalinio sprendinio rekonstravimo fazėje yra naudojamas godžios randomizuotos adaptyvios paieškos algoritmas (angl. greedy randomized adaptive search procedure – GRASP) (Li ir kt., 1994), norint gauti pagerintą sprendinį.
Išsklaidytas (išsklaidytos tabu paieškos) mutavimas
Šiuo atveju atliekant mutavimo procedūrą yra
tiesiog pertvarkytas tabu paieškos algoritmas, kuriame atliekami tik
perėjimai tarp „antrųjų“ sprendinių. Atliekamas ribotas TP vykdymo iteracijų
skaičius ( iteracijų). Taigi, mutavimas tampa ne tiek atsitiktinis, kiek
godus (kvazideterminuotas).
Pastebėtina, kad, atliekant visas mutavimo
procedūras, pasikeičia sprendinio TF reikšmė, taigi yra labai svarbu
efektyviai perskaičiuoti TF reikšmių pokyčius. Kaip žinoma, TF pokyčiai,
sukeitus du elementus, apskaičiuojami panaudojant operacijų. Kadangi visos
aprašytos mutavimo procedūros atlieka apytikriai
ar panašų (proporcingą)
skaičių elementų sukeitimų, tai visų mūsų mutavimo procedūrų sudėtingumas
yra proporcingas
.
Mutavimo laipsnis atlieka svarbų vaidmenį
mutavimo procedūroje, o kartu ir ją naudojančiame iteraciniame tabu paieškos
algoritme. Turi būti pasirenkamas tam tikras kompromisinis variantas tarp
dviejų ekstremalių situacijų: 1) reikšmė
yra (labai) maža; 2) reikšmė
yra
(labai) didelė (pvz., artima
). Pirmuoju atveju mutavimas
negarantuotų pakankamai „nutolusio“ (nuo duotojo) sprendinio generavimo, o
tai lemtų grįžimą atgal į ankstesnįjį lokalųjį optimumą po tabu paieškos
etapo. Antruoju atveju paieška taptų labai panaši į daugkartinę paiešką,
startuojant kiekvieną kartą tiesiog nuo atsitiktinių sprendinių ir
prarandant paieškos metu lokaliai optimaliuose sprendiniuose sukauptą
naudingą informaciją.
Kompiuteriniai eksperimentai
Buvo atlikti praktiniai kompiuteriniai-eksperimentiniai tyrimai, kurių tikslas – pademonstruoti aprašyto ITP algoritmo tinkamumą ir nustatyti galimai efektyviausias mutavimo procedūras, kaip vienus iš esminių ITP algoritmo sudedamųjų komponentų. Vykdant eksperimentinius tyrimus su ITP algoritmu ir mutavimo procedūromis, buvo pasinaudota kvadratinio paskirstymo uždavinio standartinių testavimo duomenų pavyzdžiais iš viešosios elektroninės KP uždavinio testavimo duomenų bibliotekos QAPLIB (Burkard ir kt., 1997). Eksperimentuose naudotas 3 GHz taktinio dažnio stacionarus asmeninis kompiuteris. Buvo naudota A. Misevičiaus ir D. Kuznecovaitės sudaryto iteracinio tabu paieškos algoritmo programinė realizacija C# programavimo kalba. ITP algoritmo ir visų mutavimo procedūrų programų tekstus galima rasti internete adresu: https://www.personalas.ktu.lt/~alfmise/.
Atliekant eksperimentus, ITP
algoritmo bei kartu mutavimo procedūrų veikimo efektyvumo įvertinimo ir
palyginimo kriterijus yra gaunamų sprendinių kokybės vidutinis santykinis
procentinis nuokrypis nuo geriausios žinomos tikslo funkcijos reikšmės (GŽR)
(angl. best known value). Vidutinis santykinis procentinis nuokrypis
()
apskaičiuojamas pagal formulę:
, čia
yra vidutinė
tikslo funkcijos reikšmė, gauta atlikus
pakartotinių algoritmo
vykdymų,
žymi geriausią žinomą tikslo funkcijos reikšmę, atitinkančią
(pseudo)optimalų sprendinį iš bibliotekos QAPLIB.
Kompiuteriniuose
eksperimentuose panaudoti šie bibliotekoje QAPLIB esantys testavimo duomenų
pavyzdžiai: tai10a, tai12a, tai15a, tai17a, tai20a, tai25a, tai30a, tai35a, tai40a, tai50a. Šie testavimo duomenys yra
sugeneruoti atsitiktiniu būdu ir laikytini sunkiausiai sprendžiamais
pavyzdžiais (Taillard, 1991). Eksperimentuota su trimis skirtingomis
mutavimo laipsnio reikšmėmis: ,
,
.
Eksperimentuose buvo tirtos anksčiau aprašytos mutavimo procedūros:
1) atsitiktinių porinių elementų sukeitimų mutavimas – M1;
2) atsitiktinio rakto mutavimas – M2;
3) priešinių reikšmių mutavimas – M3;
4) maksimalaus atstumo mutavimas – M4;
5) modifikuotas atsitiktinių sukeitimų mutavimas (I) – M5;
6) modifikuotas atsitiktinių sukeitimų mutavimas (II) – M6;
7) kombinuotas mutavimas – M7;
8) randomizuotos lokalios paieškos mutavimas – M8;
9) randomizuotos dalinės lokalios paieškos mutavimas – M9;
10) godžios adaptyvios paieškos mutavimas – M10;
11) godžios randomizuotos adaptyvios paieškos mutavimas – M11;
12) išsklaidytas mutavimas – M12.
Atliktų eksperimentų rezultatai pateikti 1-5 lentelėse. Lentelėse
parodytos gautų sprendinių vidutinių nuokrypių nuo (pseudo)optimalių
sprendinių reikšmės () visoms mutavimo procedūroms.
Testavimo duomenų pavyzdžiams tai10a, tai12a, tai15a visos mutavimo procedūros
įgalino pasiekti (pseudo)optimalius arba jiems labai artimus sprendinius.
Testavimo duomenims tai10a,
tai12a, tai15a, tai17a, tai20a vidutinis nuokrypis neviršija
,
visiems duomenims –
,9 proc. Visa tai liudija
pakankamai aukštą ITP algoritmo ir mutavimo procedūrų efektyvumo
laipsnį.
1 lentelė. Mutavimo procedūrų palyginimo rezultatai testavimo duomenų pavyzdžiams tai10a, tai12a
tai10a |
tai12a |
|||||
μ = 5 |
μ = 6 |
μ = 7 |
μ = 5 |
μ = 6 |
μ = 7 |
|
M1 |
0,000 |
0,000 |
0,000 |
0,000 |
0,000 |
0,000 |
M2 |
0,000 |
0,000 |
0,000 |
0,000 |
0,000 |
0,000 |
M3 |
0,000 |
0,000 |
0,000 |
0,000 |
0,000 |
0,000 |
M4 |
0,000 |
0,000 |
0,000 |
0,000 |
0,000 |
0,000 |
M5 |
0,000 |
0,000 |
0,000 |
0,000 |
0,000 |
0,000 |
M6 |
0,000 |
0,000 |
0,000 |
0,000 |
0,000 |
0,000 |
M7 |
0,000 |
0,000 |
0,000 |
0,000 |
0,000 |
0,000 |
M8 |
0,000 |
0,000 |
0,000 |
0,000 |
0,000 |
0,000 |
M9 |
0,000 |
0,000 |
0,000 |
0,000 |
0,000 |
0,000 |
M10 |
0,000 |
0,000 |
0,000 |
0,000 |
0,000 |
0,000 |
M11 |
0,000 |
0,000 |
0,000 |
0,000 |
0,000 |
0,000 |
M12 |
0,000 |
0,000 |
0,000 |
0,000 |
0,000 |
0,000 |
2 lentelė. Mutavimo procedūrų palyginimo rezultatai testavimo duomenų pavyzdžiams tai15a, tai17a
tai15a |
tai17a |
|||||
μ = 5 |
μ = 6 |
μ = 7 |
μ = 5 |
μ = 6 |
μ = 7 |
|
M1 |
0,000 |
0,000 |
0,000 |
0,708 |
0,273 |
0,075 |
M2 |
0,020 |
0,002 |
0,000 |
0,590 |
0,311 |
0,056 |
M3 |
0,159 |
0,135 |
0,080 |
0,355 |
0,324 |
0,129 |
M4 |
0,100 |
0,020 |
0,000 |
0,346 |
0,286 |
0,038 |
M5 |
0,040 |
0,000 |
0,020 |
0,456 |
0,165 |
0,188 |
M6 |
0,021 |
0,021 |
0,020 |
0,220 |
0,259 |
0,150 |
M7 |
0,100 |
0,021 |
0,200 |
0,465 |
0,534 |
0,339 |
M8 |
0,000 |
0,000 |
0,000 |
0,490 |
0,150 |
0,113 |
M9 |
0,000 |
0,000 |
0,000 |
0,268 |
0,113 |
0,093 |
M10 |
0,080 |
0,001 |
0,200 |
0,684 |
0,292 |
0,167 |
M11 |
0,080 |
0,020 |
0,042 |
0,695 |
0,688 |
0,449 |
M12 |
0,159 |
0,110 |
0,250 |
0,383 |
0,642 |
0,621 |
3 lentelė. Mutavimo procedūrų palyginimo rezultatai testavimo duomenų pavyzdžiams tai20a, tai25a
tai20a |
tai25a |
|||||
μ = 5 |
μ = 6 |
μ = 7 |
μ = 5 |
μ = 6 |
μ = 7 |
|
M1 |
0,522 |
0,624 |
0,566 |
1,045 |
0,.973 |
0,753 |
M2 |
0,505 |
0,272 |
0,648 |
0,857 |
0,883 |
0,899 |
M3 |
0,794 |
0,823 |
0,578 |
0,885 |
1,123 |
1,190 |
M4 |
0,605 |
0,685 |
0,441 |
1,006 |
0,849 |
0,722 |
M5 |
0,536 |
0,563 |
0,502 |
1,015 |
0,936 |
0,957 |
M6 |
0,689 |
0,627 |
0,509 |
1,097 |
1,092 |
0,688 |
M7 |
0,475 |
0,520 |
0,757 |
1,129 |
1,484 |
1,034 |
M8 |
0,569 |
0,373 |
0,345 |
1,067 |
0,843 |
0,718 |
M9 |
0,554 |
0,360 |
0,433 |
0,727 |
0,769 |
0,685 |
M10 |
0,659 |
0,441 |
0,506 |
1,122 |
1,151 |
1,049 |
M11 |
0,646 |
0,537 |
0,722 |
0,970 |
1,005 |
1,180 |
M12 |
0,567 |
0,835 |
0,773 |
1,216 |
1,329 |
1,160 |
4 lentelė. Mutavimo procedūrų palyginimo rezultatai testavimo duomenų pavyzdžiams tai30a, tai35a
tai30a |
tai35a |
|||||
μ = 5 |
μ = 6 |
μ = 7 |
μ = 5 |
μ = 6 |
μ = 7 |
|
M1 |
1,086 |
1,043 |
0,904 |
1,279 |
1,296 |
1,052 |
M2 |
1,362 |
0,891 |
0,892 |
1,278 |
1,195 |
1,158 |
M3 |
1,457 |
1,105 |
1,237 |
1,483 |
1,542 |
1,360 |
M4 |
1,239 |
1,118 |
0,984 |
1,465 |
1,159 |
1,031 |
M5 |
1,235 |
1,006 |
0,872 |
1,300 |
1,150 |
1,197 |
M6 |
1,200 |
0,964 |
0,938 |
1,072 |
1,204 |
1,024 |
M7 |
1,257 |
1,170 |
1,181 |
1,270 |
1,109 |
0,959 |
M8 |
1,091 |
0,927 |
0,980 |
1,234 |
1,152 |
1,194 |
M9 |
1,040 |
0,800 |
0,795 |
1,133 |
1,261 |
1,095 |
M10 |
1,202 |
1,002 |
1,089 |
1,151 |
1,260 |
1,275 |
M11 |
1,272 |
1,242 |
1,307 |
1,387 |
1,389 |
1,240 |
M12 |
0,763 |
1,119 |
1,220 |
1,243 |
1,216 |
1,221 |
5 lentelė. Mutavimo procedūrų palyginimo rezultatai testavimo duomenų pavyzdžiams tai40a, tai50a
tai40a |
tai50a |
|||||
μ = 5 |
μ = 6 |
μ = 7 |
μ = 5 |
μ = 6 |
μ = 7 |
|
M1 |
1,444 |
1,259 |
1,160 |
1,691 |
1,701 |
1,391 |
M2 |
1,315 |
1,468 |
1,417 |
1,525 |
1,550 |
1,687 |
M3 |
1,595 |
1,409 |
1,549 |
1,653 |
1,725 |
1,849 |
M4 |
1,485 |
1,323 |
1,227 |
1,574 |
1,732 |
1,704 |
M5 |
1,259 |
1,364 |
1,343 |
1,626 |
1,761 |
1,598 |
M6 |
1,312 |
1,475 |
1,170 |
1,614 |
1,765 |
1,427 |
M7 |
1,548 |
1,529 |
1,542 |
1,755 |
1,817 |
1,889 |
M8 |
1,247 |
1,355 |
1,256 |
1,828 |
1,634 |
1,526 |
M9 |
1,179 |
1,268 |
1,024 |
1,635 |
1,672 |
1,439 |
M10 |
1,419 |
1,406 |
1,393 |
1,735 |
1,563 |
1,697 |
M11 |
1,451 |
1,389 |
1,500 |
1,713 |
1,638 |
1,713 |
M12 |
1,298 |
1,273 |
1,477 |
1,387 |
1,673 |
1,770 |
Iš pateiktų palyginimo rezultatų matyti, jog randomizuotos dalinės lokalios paieškos mutavimo (M9) ir randomizuotos lokalios paieškos mutavimo (M8) panaudojimas leidžia pasiekti geresnius iteracinio tabu paieškos algoritmo rezultatus, palyginti su likusiomis kitomis mutavimo procedūromis. Pažymėtina, jog ir paprasta mutavimo procedūra (M1), besiremianti tik atsitiktiniais poriniais elementų sukeitimais, įgalina gauti geros kokybės sprendinius. Be to, M1 reikalauja, ko gero, mažiausiai centrinio procesoriaus laiko.
Matyti, kad mutavimo laipsnio reikšmės
padidinimas nebūtinai pagerina gaunamų sprendinių kokybę. Gali būti, jog ši
reikšmė yra susijusi su sprendžiamų pavyzdžių dydžiu
. Šiai
priklausomybei nustatyti reikalingi papildomi eksperimentiniai
tyrimai.
Baigiamosios pastabos
Šiame straipsnyje aprašytas dviejų lygių iteracinis tabu paieškos (ITP) algoritmas kvadratinio paskirstymo uždavinio sprendimui. Pagrindinis dėmesys skirtas į ITP algoritmą integruotoms mutavimo procedūroms, kurių esminė paskirtis yra diversifikuoti sprendinius, gaunamus vykdant tabu paiešką, ir taip pagerinti paieškos efektyvumą, lyginant su tradiciniais TP algoritmais, nenaudojančiais mutavimo.
Atlikti kompiuteriniai eksperimentai su dvylika pasiūlytų įvairių tipų mutavimo procedūrų, pradedant universalizuotu, grynai atsitiktiniu mutavimu ir baigiant kombinuotomis (kvazideterminuotomis) mutavimo procedūromis, kurios yra gana specializuotos ir orientuotos į konkretų sprendžiamą KP uždavinį. Sudarytos mutavimo procedūros pasižymi lankstumu, mutavimo stiprumą galima valdyti pagal vartotojo (tyrėjo) poreikius. Atlikti eksperimentiniai tyrimai, panaudojant KP uždavinio testavimo pavyzdžius iš bibliotekos QAPLIB, rodo, kad dviejų lygių ITP algoritmas leidžia gauti aukštos kokybės sprendinius. Palyginus įvairių mutavimo procedūrų efektyvumo rezultatus, galima daryti išvadą, jog mutavimo procedūros, kuriose įvertinamos tikslo funkcijos reikšmės ir kuriose yra integruotos papildomos priemonės sprendiniui dalinai pagerinti, yra galimai pranašesnės už tas procedūros, kurios neatsižvelgia į konkretaus uždavinio specifiką.
Ateityje dviejų lygių iteracinis tabu paieškos algoritmas galėtų būti toliau tobulinamas, integruojant į jį ištirtas efektyviausias mutavimo procedūras.
Literatūra
ABDEL-BASSET, Mohamed; MANOGARAN, Gunsekaran; EL-SHAHAT, Doaa; MIRJALILI, Seyedali (2018). Integrating the Whale Algorithm with Tabu Search for Quadratic Assignment Prob- lem: a New Approach for Locating Hospital Departments. Applied Soft Computing, vol. 73, p. 530–546. Prieiga per internetą: < https://doi.org/10.1016/j.asoc.2018.08.047>.
AHMED, Zakir H. (2015). A Multi-Parent Genetic Algorithm for the Quadratic Assignment Problem. OPSEARCH, vol. 52, p. 714–732. Prieiga per internetą: <https://doi.org/10.1007/s12597-015-0208-7>.
AKSAN, Yagmur; DOKEROGLU, Tansel; COSAR, Ahmet (2017). A Stagnation-aware Cooperative Parallel Breakout Local Search Algorithm for the Quadratic Assignment Problem. Computers & Industrial Engineering, vol. 103, p. 105–115. Prieiga per internetą: <https://doi.org/10.1016/j. cie.2016.11.023>.
BENLIC, Una; HAO, Jin-Kao (2013). Breakout Local Search for the Quadratic Assignment Prob- lem. Applied Mathematics and Computation, vol. 219, p. 4800–4815. Prieiga per internetą: < https://doi.org/10.1016/j.amc.2012.10.106 >.
BENLIC, Una; HAO, Jin-Kao (2015). Memetic Search for the Quadratic Assignment Problem. Expert Systems with Applications, vol. 42, p. 584–595. Prieiga per internetą: <https://doi.org/10.1016/j. eswa.2014.08.011>.
BURKARD, Rainer E.; KARISCH, Stefan E.; RENDL, Franz (1997). QAPLIB – a Quadratic Assignment Problem Library. Journal of Global Optimization, vol. 10, p. 391–403. Prieiga per internetą: <https://doi.org/10.1023/A:1008293323270> [žr. taip pat prieigą per internetą: < http://anjos.mgi.polymtl.ca/qaplib/>].
ÇELA, Eranda (1998). The Quadratic Assignment Problem: Theory and Algorithms. Dordrecht: Kluwer. 304 p.
CHMIEL, Wojciech (2019). Evolutionary Algorithm Using Conditional Expectation Value for Quadratic Assignment Problem. Swarm and Evolutionary Computation, vol. 46, p. 1–27. Prieiga per internetą: <https://doi.org/10.1016/j.swevo.2019.01.004>.
CHMIEL, Wojciech; KWIECIEŃ, Joanna (2018). Quantum-inspired Evolutionary Approach for the Quadratic Assignment Problem. Entropy, vol. 20, p. 781. Prieiga per internetą: <https://doi.org/10.3390/e20100781>.
DELL’AMICO, Mauro; TRUBIAN, Marco (1998). Solution of Large Weighted Equicut Problems. European Journal of Operational Research, vol. 106, p. 500–521.
DOKEROGLU, Tansel; SEVINÇ, Ender; COSAR, Ahmet (2019). Artificial Bee Colony Optimiza- tion for the Quadratic Assignment Problem. Applied Soft Computing, vol. 76, p. 595–606. Prieiga per internetą: <https://doi.org/10.1016/j.asoc.2019.01.001>.
DREZNER, Zvi (2003). A New Genetic Algorithm for the Quadratic Assignment Problem. IN- FORMS Journal on Computing, vol. 15, p. 320–330.
EDELKAMP, Stefan; SCHRÖDL, Stefan (2012). Heuristic Search. Theory and Applications. Waltham: Morgan Kaufmann Publishers. 712 p.
GAMBARDELLA, Luca M.; TAILLARD, Éric D.; DORIGO, Marco (1999). Ant Colonies for the Quadratic Assignment Problem. Journal of the Operational Research Society, vol. 50, p. 167–176.
GLOVER, Fred; LAGUNA, Manuel (1997). Tabu Search. Dordrecht: Kluwer. 382 p.
HAFIZ, Faizal M. F.; ABDENNOUR, Adel (2016). Particle Swarm Algorithm Variants for the Qua- dratic Assignment Problems - a Probabilistic Learning Approach. Expert Systems with Applications, vol. 44, p. 413–431. Prieiga per internetą: <https://doi.org/10.1016/j.eswa.2015.09.032>.
HANAN, Maurice; KURTZBERG, Jerome M. (1972). Placement Techniques. In Breuer, M. A. (ed.). Design Automation of Digital Systems: Theory and Techniques, vol. 1, Englwood Cliffs: Prentice- Hall, p. 213–282.
KOOPMANS, Tjalling C.; BECKMANN, Martin (1957). Assignment Problems and the Location of Economic Activities. Econometrica, vol. 25, p. 53–76.
LI, Yong; PARDALOS, Panos M.; RESENDE, Mauricio G. C. (1994). A Greedy Randomized Adaptive Search Procedure for the Quadratic Assignment Problem. In Pardalos, P. M.; Wolkowicz, H. (eds.). Quadratic Assignment and Related Problems. DIMACS Series in Discrete Mathematics and Theoretical Computer Science, vol. 16, Providence: AMS, p. 237–261.
LOURENCO, Helena R.; MARTIN, Olivier C.; STÜTZLE, Thomas (2002). Iterated Local Search. In Glover, F.; Kochenberger, G. (eds.). Handbook of Metaheuristics. Norwell: Kluwer, p. 321–353.
MERZ, Peter; FREISLEBEN, Bernd (2000). Fitness Landscape Analysis and Memetic Algorithms for the Quadratic Assignment Problem. IEEE Transactions on Evolutionary Computation, vol. 4, p. 337–352.
MICHALEWICZ, Zbigniew; FOGEL, David B. (2000). How to Solve It: Modern Heuristics. Berlin-Heidelberg: Springer. 467 p.
MISEVIČIUS, Alfonsas (2003). A Modified Simulated Annealing Algorithm for the Quadratic Assignment Problem. Informatica, vol. 14, p. 497–514.
MISEVICIUS, Alfonsas (2004). An Improved Hybrid Genetic Algorithm: New Results for the Quadratic Assignment Problem. Knowledge-Based Systems, vol. 17, p. 65–73.
MISEVICIUS, Alfonsas (2005). A Tabu Search Algorithm for the Quadratic Assignment Problem. Computational Optimization and Applications, vol. 30, p. 95–111.
SAHNI, Sartaj; GONZALEZ, Teofilo (1976). P-complete Approximation Problems. Journal of ACM, vol. 23, p. 555–565.
SHYLO, Volodymyr P. (2017). Solving the Quadratic Assignment Problem by the Repeated Iterated Tabu Search Method. Cybernetics and Systems Analysis, vol. 53, p. 308–311. Prieiga per internetą: <https://doi.org/10.1007/s10559-017-9930-x>.
SIARRY, Patrick (ed.). (2016). Metaheuristics. Cham: Springer. 489 p.
STÜTZLE, Thomas (2006). Iterated Local Search for the Quadratic Assignment Problem. Euro- pean Journal of Operational Research, vol. 174, p. 1519–1539. Prieiga per internetą: <https://doi. org/10.1016/j.ejor.2005.01.066>.
TAILLARD, Éric D. (1991). Robust Taboo Search for the QAP. Parallel Computing, vol. 17, p. 443–455.
TANG, Jing; LIM, Meng-Hiot; ONG, Yew S.; ER, Meng J. (2006). Parallel Memetic Algorithm with Selective Local Search for Large Scale Quadratic Assignment Problems. International Journal of Innovative Computing, Information and Control, vol. 2, p. 1399–1416.
YANG, Xin-She (2010). Nature-Inspired Metaheuristic Algorithms. Frome: Luniver Press. 160 p.
[1] Priminsime, jog
perstatymą formaliai galima nusakyti rinkiniu
;
;
;
, kai
;
.
[2]Panašus patobulinimas yra sukurtas ir klasikiniams lokaliosios paieškos algoritmams. Patobulinimas žinomas kaip iteratyvioji lokalioji paieška (angl. iterated local search) (Lourenco ir kt., 2002).