Memetic algoritmas, skirtas dviejų variantų dviejų etapų paslaugų vietos nustatymo problemai spręsti
|
| Title | Memetic algoritmas, skirtas dviejų variantų dviejų etapų paslaugų vietos nustatymo problemai spręsti |
| Authors | |
| Abstract | Straipsnyje nagrinėjama dviejų etapų paslaugų vietos problema (TSUFLP), kuri turi svarbių telekomunikacijų sistemų projektavimo programų. Atsižvelgiant į reikalavimus ir galimų vietų pirmojo ir antrojo lygmens koncentratorius (perjungiklius, tankintuvus), TSUFLP tikslas - apibrėžti dviejų lygmenų koncentratorių prieigos tinklo struktūrą taip, kad tinklui įrengti išleista bendra išlaidų suma būtų kuo mažesnė. Remiantis literatūra, apžvelgti du TSUFLP variantai ir pasiūlytas veiksmingas memetic algoritmas (MA), remiantis evoliucinio požiūrio ir dviejų vietinės paieškos euristikos mišrinimu. Godi euristika yra įtraukta į MA sistemą siekiant veiksmingai apskaičiuoti treniruoklių funkciją, kuri papildomai sumažina bendrą MA darbo laiką. Aprašytas MA metodas taikomas kaip etalonas vidutinių ir didelių matmenų, remiantis literatūra, pavyzdžiais, kurie yra pritaikyti TSUFLP ir apima 50 500 vartotojų mazgų. Taikant šiuos atvejus, siūlomas MA metodas greitai pasiekia visus žinomus optimalius sprendimus, anksčiau gautus taikant tiesinio programavimo metodą remiantis literatūra arba CPLEX sprendėju. Siekiant patikrinti MA efektyvumą, pakeisti kai kurie didelio masto literatūriniai pavyzdžiai, apimantys 1000 ir 2000 m paklausos taškus, kurie negali būti išspręsti optimaliai. Išsamūs skaičiuojamieji eksperimentai rodo, kad MA pateikia sprendimus naujai sugeneruotam duomenų rinkiniui per palyginti trumpą centrinio procesoriaus darbo laiką. Dėl tiek sprendimo kokybės, tiek ir veikimo laiko daroma išvada, kad siūlomas MA pateikia galingą metaeuristinį metodą TSUFLP ir kitų panašių tinklų projektavimo problemoms spręsti.DOI: http://dx.doi.org/10.5755/j01.itc.42.2.1768 |
| Publisher | Kaunas University of Technology |
| Date | 2013-06-11 |
| Source | Informacinės technologijos ir valdymas Vol 42, No 2 (2013) |
| Rights | Copyright terms are indicated in the Republic of Lithuania Law on Copyright and Related Rights, Articles 4-37. |