Algoritmy pro optimalizaci nehierarchické telekomunikační sítě

Autor: O. Hudousek <hudouso(at)fel.cvut.cz>, Pracoviště: České vysoké učení technické v Praze, FEL, Téma: Optimalizace, Vydáno dne: 07. 01. 2005

Příspěvek navazuje na článek "Optimalizace nehierarchické telekomunikační sítě" a obsahuje návrhy algoritmů pro řešení daného problému.

(Text článku ve formátu pdf je k dispozici na adrese http://k332.feld.cvut.cz/hudousek/data/access-optim/optim.pdf.)


Možné přístupy k řešení problému optimalizace sítě

Vzhledem k tomu, že daný problém patří do třídy NP-úplných úloh, není známý (a velmi pravděpodobně ani neexistuje) algoritmus, který by řešil úlohu, se složitostí O(p(n)), kde p(n) je polynom. Lze tedy očekávat, že algoritmy, kterými lze nalézt optimální řešení problému, budou použitelné pouze pro malé velikosti zadání. Přesto budou možné přístupy k hledání optimálního řešení dále rozebrány, neboť výsledky získané těmito algoritmy, byť jen pro malé počty uzlů, budou použity pro posouzení kvality výstupu druhé kategorie algoritmů. Rezignujeme-li totiž na nalezení optimálního řešení a budeme-li považovat za dostačující nalezení řešení, které se, s danou mírou jistoty, bude lišit od optimálního pouze o předem daný malý rozdíl, pak mohou být do zkoumání zahrnuty i nejrůznější aproximace. U řady z nich se ovšem nevylučuje nalezení optimálního řešení ve většině případů. Uvedený problém spadá do skupiny kombinatorických optimalizačních problémů (angl. combinatorial optimization problems), pro jejichž řešení byla již navržena celá řada obecných postupů. Některé z nich jsou v této práci blíže rozebrány a přizpůsobeny k řešení daného problému. Pro ověření správnosti a kvality aproximačních algoritmů je nutné znát, alespoň v některých případech, optimální řešení úlohy. To je možné s jistotou zjistit prozkoumáním všech možných řešení konkrétní úlohy. Pro kombinatorické úlohy lze pak toto úplné prohledávání jistým způsobem zjednodušit. Algoritmy pro hledání optimálního řešení v této práci jsou

Pro nalezení co nejlepšího přípustného řešení byly uvažovány následující aproximace:

Horolezecký algoritmus byl zařazen pro ověření, zda mají typická zadání úlohy lokální minima kriteriální funkce.

Metoda totálních zkoušek, algoritmus větvení a mezí

Metoda totálních zkoušek spočívá v postupném procházení všech možných řešení. To je samozřejmě i při relativně malém počtu řešení značně náročný postup. Jedno řešení je možné chápat jako vektor a=(a1,a2,...ak), kde k je počet dvojic uzlů v grafu. Prohledávání obvykle probíhá systematicky, např. zvolí se jedna z možných hodnot prvku a1 (reprezentující konkrétní cestu mezi jednou z dvojic uzlů) a postoupí se k prvku a2, pro něj se opět zvolí konkr. hodnota a tak se postupuje až k an. Pro takto navržené řešení se vypočte hodnota kriteriální funkce a pokud je lepší než nejlepší dosud známá, uloží se. V následujícím kroku se zvolí další hodnota an. Pokud byly takto vyčerpány již všechny možné hodnoty an, zvolí se další hodnota prvku an-1 a volí se postupně všechny možné hodnoty an. Obdobně se postup opakuje až do prozkoumání všech možných kombinací hodnot vektoru a.
Pokud se ovšem hodnota kriteriální funkce může přidáním dalších částí řešení (cest) pouze zvýšit nebo zůstat stejná, je možné provádět její výpočet už pro částečná řešení tvořená hodnotami několika prvních prvků vektoru a. Pokud bude hodnota kriteriální funkce pro toto částečné řešení horší než nejlepší dosud známá hodnota kriteriální funkce, pak již není nutné zkoumat řešení, jejichž součástí jsou prvky s těmito hodnotami. Žádné z nich totiž jistě nebude lepší než nejlepší dosud nalezené řešení. Tímto způsobem lze zrychlit proces hledání optimálního řešení a to tím lépe, čím větší jsou rozdíly v hodnotách kriteriální funkce jednotlivých řešení. Předpokládejme, že časově nejnáročnější operací je právě výpočet kriteriální funkce. V krajním případě se jednotlivá řešení mohou navzájem lišit tak málo, že hodnota kriteriální funkce pro každé částečné řešení by byla menší než hodnota k.f. optimálního řešení. Pak by ovšem hledání pomocí metody větvení a mezí bylo pomalejší než metoda totálních zkoušek. Pokud se ovšem ve smyslu četnosti výskytu různých zadání nejedná o ojedinělý případ, dá se často výpočet k.f. uzpůsobit tak, aby se pro účely algoritmu větvení a mezí vypočítávala transformovaná k.f. taková, že její rozdíly pro jednotlivá řešení by umožňovaly identifikovat částečná řešení, která nejsou součástí optimálního, dříve.

Metoda větvení a mezí je demonstrována na následujícím příkladu. Předpokládejme optimalizační problém, jehož řešení je popsáno vektorem a=(a1,a2), přičemž a1 je z {7, 2, 5, 1}, a2 je z {3, 4, 1}. Hodnota kriteriální funkce je dána vztahem f = a1 + a2. Průběh algoritmu je ilustrován následující tabulkou a obrázkem 1. Nejlepší dosud nalezená hodnota f je zde označována fb.

Krok a f fb pozn.
1 (7,3) 10 10
2 (7,1) 8 8
3 (7,4) 11 8
4 (2,x) 2+x 8   f < fb, pokračuje se
5 (2,3) 5 5
6 (2,1) 3 3
7 (2,4) 6 3
8 (5,x) 5+x 3   f > fb, nepokračuje se
9 (1,x) 1+x 3   f < fb, pokračuje se
10 (1,3) 4 3
11 (1,4) 5 3
12 (1,1) 2 2




optim14x

Obrázek 1: K průběhu algoritmu větvení a mezí.

Horolezecký algoritmus

Horolezecký algoritmus patří do skupiny tzv. gradientních algoritmů. Uvažujme opět řešení ve tvaru vektoru a=(a1,a2,..,an) a kriteriální funkci f = f(a). V každém kroku algoritmu se prohledávají sousední řešení stávajícího řešení a vybírá se takové, jehož hodnota kriteriální funkce je nejlepší. To se pak v dalším kroku stává aktuálním řešením. Tento postup se opakuje až do kroku, kdy žádné ze sousedních řešení nemá lepší hodnotu f. Tento algoritmus je ovšem použitelný pouze pro takové f, které nemají lokální extrém1. Pokud má f lokální extrémy, pak, v závislosti na volbě počátečního řešení, může dojít k uvíznutí algoritmu v lokálním minimu resp. maximu. Proto se v této podobě používá spíše pro lokální optimalizaci - rychlé nalezení nejbližšího extrému. V této práci byl horolezecký algoritmus použit pouze pro ověření zda kriteriální funkce má pro danou úlohu a obvyklá zadání lokální minima. Ukázalo se, že předpoklad byl správný a f má obvykle řadu lokálních minim, a proto bylo zkoumáno nedeterministické rozšíření horolezeckého algoritmu - simulované žíhání.

Simulované žíhání

Aby se omezila možnost uvíznutí gradientního algoritmu v lokálním extrému, byl navržen tzv. algoritmus simulovaného žíhání (simulated anealing, SA), viz [9]. Původní inspirací pro něj byl fyzikální proces - průběh ochlazování látky a její krystalizace. Horolezecký algoritmus popsaný v předcházejícím odstavci často skončí svou činnost nalezením lokálního minima kriteriální funkce. Tomu se lze vyhnout tím, že v některých případech přijmeme jako následující i řešení s horší hodnotou kriteriální funkce, než je její současná hodnota. Tento krok se provede s jistou nenulovou pravděpodobností, která v průběhu algoritmu klesá a je navíc závislá na rozdílu hodnot f současného a následujícího řešení. Tato pravděpodobnost je popsána tzv. přijímací funkcí (acceptance function), což je komplementární distribuční funkce exponenciálního rozložení:

optim16x
(23)

kde Df je rozdíl hodnot kriteriální funkce pro stávající a potenciální následující řešení,
TA řídící parametr.

Parametr TA odpovídá teplotě ve fyzikálním procesu ochlazování, na počátku vykonávání algoritmu je nastaven na předem danou hodnotu T0 a jeho hodnota je postupně snižována. V závislosti na tom, zda probíhá snižování v každém kroku nebo jednou za L kroků, dělíme algoritmy simulovaného žíhání na

Průběh algoritmu můžeme tedy zapsat v pseudo-jazyce např. následujícím způsobem:

              Inicializuj(a,K,TA,L);
              i:=0;
              repeat
                for j:=1 to L do
                begin
                  Najdi následující řešení (a -> b);
                  Vypočti Df = f(a) - f(b);
                  if Df (= 0 then a:=b
                  else
                    if Exp(-Df/TA) ) Random(0,1) then a:=b;
                end;
                Aktualizuj(TA);
                i:=i+1;
              until i=K

Význam použitých konstant a proměnných je následující:
a,b jsou řešení získaná v průběhu algoritmu,
K je celkový počet opakování,
T řídící parametr (teplota),
L počet kroků algoritmu, v nichž se T nemění.

Možnou variantou algoritmu je změna parametru L v každém opakovaní (pro každé i).

Při implementování naznačeného algoritmu je nutné volit řadu parametrů. Některé z nich jsou stejné pro všechny SA algoritmy a tvoří skupinu obecných parametrů (cooling scheme, cooling schedule). Jsou to

Vedle toho je nutné stanovit ještě parametry specifické pro danou úlohu:

Stanovení těchto parametrů a dalšími aspekty implementace jsou rozebrány dále.

Algoritmus patří do skupiny pravděpodobnostních algoritmů, tj. jeho průběh je ovlivněn náhodnou veličinou (v praktické implementaci pseudonáhodně generovanými čísly), takže není zaručen, podobně jako u simulací, stejný výstup algoritmu při každém běhu. Pro zkoumání jeho vlastností je tedy nutné výsledky podrobit příslušné statistické analýze. V této práci bylo zpracování omezeno na nalezení příslušných konfidenčních intervalů.

Genetický algoritmus

Další optimalizační technikou, která zahrnuje řadu algoritmů jsou tzv. evoluční výpočetní techniky. Jedná se o postupy inspirované teoriemi přirozeného výběru a vývoje živých organismů. Jedním z možných přístupů jsou genetické algoritmy (genetic algorithms, GA). Narozdíl od dříve zmíněných optimalizačních metod, jež pracovaly s jedním řešením, které se snažily postupně vylepšovat, pracují GA v jednom kroku se skupinou řešení. Ta je v souladu s uvedenou analogií nazývána populace, jednotlivé její prvky jsou označovány jako jedinci (též individua). Jednotlivá řešení jsou reprezentována datovou strukturou zvanou chromozom, v nejjednoduším případě jde o řetězec dvouhodnotových symbolů (0 nebo 1) pevné délky. Jednotlivé kroky algoritmu, v nichž jsou vytvářeny nové populace, jsou označovány jako generace. Vedle toho, že každý jedinec stejným typem datové struktury - genomem, popisuje nějaké řešení, je také každý ohodnocen mírou kvality (fitness). Způsob jakým se tak děje závisí na konkrétní úloze, k níže je GA využit. Pro běh samotného algoritmu je obecně postačující, aby takové ohodnocení existovalo a aby se na jeho základě dali jedinci navzájem porovnat.

GA existuje značné množství, všechny však vznikly úpravami (někdy ovšem poměrně zásadními) a vylepšením původního, tzv. standardního genetického algoritmu (SGA). Jeho funkce je popsána v této části. SGA probíhá, obdobně jako předchozí algoritmy, v krocích. Součástí jednoho kroku jsou operace selekce jedinců ze stávající populace do následující a operace změn jedinců. Selekce, stejně jako v Darwinově přirozeném výběru, zajišťuje výběr jedinců do další generace s ohledem na jejich kvalitu (zde jednoznačně určenou). Obvykle užívaným algoritmem pro tuto fázi je ruletová selekce. Předpokládá se ohodnocení i-tého jedince reálným číslem fi a pro populaci o K jedincích se generuje K-krát náhodné číslo r z intervalu <0..1). i-tý jedinec je zařazen do následující generace, pokud platí:

optim16x
(24)

Jedinci jsou tedy vybíráni s pravděpodobností úměrnou jejich ohodnocení. Pokud by GA obsahoval pouze fázi selekce, pak by populace po několika generacích obsahovala jen identické, nejkvalitnější jedince z první generace. Proto je nutné, aby se složení populace obměňovalo. Prvním způsobem změn je reprodukce, kdy se s určitou pravděpodobností Pcdvojice jedinců, rodičů, nahradí jinou dvojicí jedinců, potomků. V případě SGA se postupuje tak, že se nejprve náhodně vybere pořadí rg genu v chromozomu (pořadí znaku v řetězci, který popisuje jedno z možných řešení). Chromozom prvního z nových jedinců je pak tvořen rg geny z počátku chromozomu prvního z rodičů a Ngen - rg geny od konce chromozomu druhého z rodičů. Chromozom druhého z potomků je tvořen zbývajícími nevyužitými geny, viz obr. 3. Tímto způsobem se kombinují vlastnosti stávajících jedinců a potenciálně mohou vzniknout kvalitnější řešení. Pokud by však součástí chromozomu, který by popisoval optimální řešení úlohy, byl gen, který se nikde v populaci nevyskytuje, pak by se optimálního řešení nedalo kombinací selekce a reprodukce dosáhnout (např. chromozom popisující optimální řešení byl měl na pátém místě znak 0, ale všichni jedinci v populaci by na pátém místě měli znak 1). Z tohoto důvodu se zavádí další operace - mutace. S jistou pravděpodobností, obvykle Pm = 0,01, se jedinci změní náhodně některý gen v chromozomu. Snahou tohoto kroku je vnést do populace nové kombinace genů.

Struktura SGA je shrnuta následujícím zápisem v pseudo-kódu:

              i:=0;
              Inicializuj(G(i)); 
              Vyhodnoť(G(i));
              while not podmínka_ukončení do 
              begin 
                i:=i+1; 
                G(i):=Proveď_selekci(G(i-1)); 
                Proveď_reprodukce(G(i)); 
                Proveď_mutace(G(i));
                Vyhodnoť(G(i)); 
              end;

Stejně jako v případě SA je před vykonáváním algoritmu nutné zvolit řadu parametrů. Obecné parametry, stejné pro všechny SGA jsou

Dále je nutné zvolit některé parametry a navrhnout části algoritmu specifické pro danou úlohu, např. způsob volby počáteční populace, konkrétní realizace křížení a mutace, způsob výpočtu hodnoty kriteriální funkce a další.


Implementace

V předchozím textu byly navrženy dva způsoby reprezentace řešení. V této práci je použita reprezentace pomocí odkazů do úplného seznamu všech přípustných cest. Praktická použitelnost tohoto přístupu je sice omezená paměťovou náročností, jeho výhodou je ovšem jednoduché hledání sousedních řešení, tj. řešení, která se od sebe příliš neliší. Před jeho použitím je ovšem nutné zkonstruovat seznam všech cest mezi každou dvojicí uzlů, mezi nimž existuje nenulová nabídka. Tento problém je možné vyřešit jednoduchou aplikací algoritmu prohledávání do hloubky. V přípravném kroku je pro zjednodušení pro každý uzel připraven seznam jeho sousedních uzlů, tj. těch s nimiž jej spojuje hrana. Tento seznam je reprezentován dvourozměrným polem S s prvky S[i][j]. V poli S[i], jsou uloženy sousední uzly uzlu i. Průběh algoritmu pro jednu dvojici uzlů je pak možné popsat pomocí pseudo-kódu následujícím rekurzivním způsobem, v poli P je uložen seznam uzlů právě konstruované cesty:



              procedure Hledej(u:číslo_uzlu;P:seznam_uzlů);
              begin
                for i:=0 to Délka_pole(S[u]) do
                begin
                  if S[u][i]=konečný_uzel then
                  begin
                    Přidej_do_P(S[u][i]);
                    Ulož_do_seznamu_všech_cest(P);
                  end
                  else
                    if Uzel_S[u][i]_není_obsažen_v_poli_P then
                    begin
                      Přidej_do_P(S[u][i]);
                      Hledej(S[u][i]);
                    end;
                end; 
              end;

Písmenem i je výše označena lokální proměnná, v níž je uloženo aktuální pořadí v prohledávání seznamu sousedních uzlů. Rekurzivní podoba je uvedena pouze pro přehlednost, ve skutečnosti je algoritmus implementován jako nerekurzivní, což ovšem vyžaduje navíc ukládat stav prohledávání pro všechny stavy odpovídající úrovním vnoření při použití rekurzivní verze. Příklad průběhu prohledávání grafu pro dvojici uzlů (0,3) a odpovídající obsah pole P jsou znázorněny na následujícím obrázku:


optim17x

Obrázek 2: Průběh hledání všech cest mezi uzly (0,3).

V programu, kde byly všechny uvedené algoritmy implementovány, byla uvažována telefonní síť popsaná jako soustava obsluhových systémů M/M/N/0 Kendallovy klasifikace. Při použití nástrojů pro sledování času stráveného vykonáváním jednotlivých procedur (tzv. profiler) na prvotní verzi programu bylo zjištěno, že většina času je věnována výpočtu první Erlangovy funkce realizovaného pomocí rekurentního vztahu. Proto byla pozornost věnována zrychlení vyčíslení této funkce. Výsledky byly shrnuty v [1] a [2].

Pro všechny následující algoritmy je zapotřebí provádět výpočet hodnoty kriteriální funkce. Použitý postup platí opět pro OS typu M/M/N/0. Každému svazku, který odpovídá hraně e je z E, je nabízeno provozní zatížení tvořené součtem provozních zatížení, která jsou odbavována po cestách, jejichž součástí je hrana e (rce. 3). Je tedy nutné ke každé cestě najít hrany, z nichž se skládá, a do pomocného pole postupně nasčítat všechny příspěvky provozního zatížení. V dalším kroku se pak pro každou hranu provede dimenzování pomocí prvního Erlangova vztahu a spočítá se odpovídající cena. Hodnota kriteriální funkce je pak rovna součtu cen všech svazků v síti (rce. 1).


Metoda totálních zkoušek

Jak bylo dříve uvedeno, metoda totálních zkoušek spočívá v prozkoumání všech možných řešení. Jedno řešení je reprezentováno polem R, kde každý prvek odpovídá jedné dvojici uzlů. Obsahem prvku je přímo index cesty v poli všech cest mezi dvojicí uzlů a průběh algoritmu pak spočívá pouze v prozkoumání všech kombinací možných hodnot prvků pole R. Metoda totálních zkoušek byla implementována proto, aby bylo alespoň u úloh s omezenou velikostí zadání možné zjistit přesné řešení a ověřit následně schopnost nedeterministických algoritmů hledat řešení blízká optimálnímu. Algoritmus větvení a mezí nebyl implementován, neboť pro praktické použití je jeho časová složitost příliš vysoká a pro ověření funkce dalších algoritmů byl již k dispozici program prověřující všechna možná řešení.


Horolezecký algoritmus

V každém kroku se prozkoumají sousední řešení b současného řešení a, tj. takové řešení, pro které platí:

optim18x
(25)

Pro aktuálně zkoumané řešení reprezentované polem R a pomocné pole S může být průběh algoritmu naznačen následujícím zápisem:

              Opakuj dokud se R mění
              begin
                for i:=0 to Délka_pole(R)-1 do
                begin 
                  S:=R; 
                  S[i]:=(S[i]+1) modulo Délka_pole(P[i]); 
                  if Vypočti_f(S) ( Nejlepší_sousední_řešení then
                    Nejlepší_sousední_řešení:=S
                  S[i]:=(S[i]-2) modulo Délka_pole(P[i]);
                  if Vypočti_f(S) ( Nejlepší_sousední_řešení then
                    Nejlepší_sousední_řešení:=S
                end;  
                R:=Nejlepší_sousední_řešení;
              end;

P je pole, stejně jako v předchozích odstavcích, všech cest mezi každou dvojicí uzlů. Počáteční řešení se volí ve tvaru a = (0, 0, 0, ..., 0), mohlo by ovšem být voleno i jiným způsobem. Zde bylo však cílem pouze ověřit, zda má kriteriální funkce f lokální minima, což se pro několik náhodně zvolených zadání potvrdilo.

Simulované žíhání

Algoritmus SA byl implementován v základní podobě bez zásadních úprav. Všechny obecné parametry, tj. T0, L a počet opakování K jsou volitelné uživatelem, parametr TA je snižován každých L kroků o volitelnou hodnotu DTA. Počáteční řešení a0 je voleno pseudonáhodně, pravděpodobnost volby kteréhokoliv řešení je stejná. Sousední řešení k současnému řešení R je konstruováno tak, že pro jeden náhodně vybraný prvek R[i] je náhodně vybrána nová hodnota. Nové řešení obsahuje tedy až na jednu všechny cesty z původního řešení. Nahrazovaná cesta je volena náhodně. Hodnota kriteriální funkce f je vyčíslována stejně jako v předchozích případech.

Genetický algoritmus

V předchozím textu byly vyčleněny tři fáze běhu GA, z nichž první je selekce. K její realizaci slouží pole PR, která má stejný počet prvků, jako je jedinců v populaci Npop. Pravděpodobnost výběru jedince i do další generace je

optime1

Jednotlivým prvkům pole PR jsou přiřazeny hodnoty tzv. kumulativní pravděpodobnosti

optime2

Následně se vygeneruje pseudonáhodné číslo rs je z <0, 1) a najde se největší prvek i, pro který platí qi < rs. Jedinec i je pak zařazen do pomocné populace Ip. Další fází je reprodukce, pro jejíž realizaci byly testovány dva přístupy. Obecně se postupně náhodně a bez opakování vybírají dvojice jedinců a,b. S pravděpodobností Pr, kterou může uživatel volit (typicky Pr = 0, 7 ~ 0, 8), je pak s dvojicí provedena operace křížení, jinak přecházejí oba jedinci do další generace v nezměněné podobě. Při první, jednodušší variantě křížení se vygeneruje náhodné číslo

optime3

kde Ngen je počet genů jedince, tj. počet různých dvojic uzlů. První potomek pak má prvních rk genů od rodiče a a zbylých Ngen-rk genů od rodiče b. Druhý potomek získá naopak prvních rk genů od rodiče b a zbytek od a. Pro rk = 3, a = (14, 3, 7, 11, 8) a b = (1, 3, 19, 2, 4) je příklad prvního typu křížení na obrázku 3. Tento typ křížení má ovšem nevýhodu v případě, že v prvotní populaci nejsou obsaženy všechny možné geny pro každé místo v genotypu jedince. Například, pokud by existovala cesta kódovaná číslem 5 v třetím genu (na třetím místě v poli reprezentujícím jedno řešení - jedince), ale žádný jedinec v populaci by takovou hodnotu třetího genu neměl, pak by se ani nikdy v budoucnu nemohl takový gen objevit, ačkoliv potenciálně může být součástí kvalitního řešení. Stejný případ by nastal, pokud by všichni nositelé takového genu vymřeli. Tento problém ovšem může být překonán pomocí operace mutace.


optim19x

Obrázek 3: Příklad prvního typu křížení (rk = 3).

Přesto byl navržen druhý typ křížení, který umožňuje, aby nově vzniklí jedinci neměli genom zcela totožný se svými rodiči. Postupuje se obdobně jako v předchozím případě. Vygeneruje se náhodné číslo

optime4

Prvních rl-1 prvků jedince a je přavzato do prvního z potomků, stejně tak je do něj převzato posledních Ngen-rl prvků. Obdobně se postupuje s druhým potomkem. Jediná odlišnost od předchozího typu křížení je v postupu pro rl-tý prvek. Jeho nová hodnota se pro potomky c a d vypočítá (pro brl > arl) následujícím způsobem:



optim20x

arl a brl jsou hodnoty rl-tého genu jedinců a a b. Nrl je počet možných cest mezi dvojicí uzlů odpovídající indexu rl v řešení. Pro rl = 3, Nrl = 30, a = (14, 3, 7, 11, 8) a b = (1, 3, 19, 2, 4) je příklad druhého typu křížení uveden na obrázku 4. Přesto, že byl očekáván pozitivní přínos druhého typu křížení, jeho použití prakticky bez vyjímky kvalitu výsledného řešení snížilo. Proto bylo nakonec, v průběhu fáze testování a porovnávání algoritmů, od jeho používání upuštěno.

optim21x

Obrázek 4: Příklad druhého typu křížení (rl = 3).

Poslední operací je mutace. Pro každý prvek se vygeneruje pseudonáhodné číslo rm je z <0, 1). Pokud je menší než uživatelem zvolená pravděpodobnost mutace Pm (obvykle Pm = 0,01), pak se náhodně2 zvolí jeden z genů (každý se stejnou pravděpodobností). Jeho hodnota se, opět náhodně, změní. Touto operací se vnášejí do populace zcela nové geny, což zvyšuje různorodost populace a tím potenciálně zvyšuje pravděpodobnost nalezení kvalitního řešení. Na druhou stranu pravděpodobnost Pm nesmí být příliš velká, neboť, pak by se nalezená řešení příliš často měnila. Hledání řešení s využitím znalostí kvality předcházejících řešení by se pak změnilo na náhodné prohledávání možných řešení.


Porovnání výsledků

Pro otestování a vzájemné porovnání algoritmů bylo vygenerováno několik testovacích úloh (jsou k dispozici na http://matlab.feld.cvut.cz/Hudousek/zadani.zip). V první fázi testů bylo snahou nalézt v případech, kde to bylo v reálném čase možné, deterministickým algoritmem optimální řešení úloh. Dále byla hledána taková kombinace parametrů nedeterministických algoritmů řešících úlohu, aby odchylka průměrného řešení od optimálního nebyla větší než 1%. Pro zadání s větším počtem uzlů, kde není s jistotou známé optimální řešení byla snaha docílit uvedené odchylky od nejlepšího známého řešení. Aby bylo možné vliv jednotlivých nastavení věrohodně posoudit, bylo vzhledem k (pseudo)náhodné povaze výsledků nutné provést větší počet vykonání programu. Z výsledných hodnot byl spočítán průměr a 95%-ní konfidenční interval3. Následující tabulka uvádí srovnání řešení jednotlivých úloh oběma algoritmy (SA i GA)

Úloha Uzlů OR Copt CSA KISA [%] CGA KIGA [%]
5a1
5b1
6a1
6b1
6c1
7a1
8a1
9a1
51
51
61
61
61
71
81
91
3,6.108
3,6.108
6,1.1030
5,7.1031
6,1.1033
6,9.10157
7,4.10266
5,1.10393
2198,501
3010,841
5131,361
7176,831
9761,121
není známé1
není známé1
není známé1
2201,391
3010,841
5133,111
7177,011
9771,141
4455,121
4237,421
6529,161
0,071
0,011
0,011
0,011
0,021
0,241
0,361
0,501
2201,401
3010,841
5132,141
7176,831
9771,521
4434,791
1
1
0,091
0,011
0,011
0,011
0,031
0,401
1
1


Značení sloupců v tabulce má následující význam:
Copt je hodnota f optimálního řešení,
CSA průměrná hodnota f nalezená pomocí SA,
CGA průměrná hodnota f nalezená pomocí GA,
KISA konfidenční interval CSA,
KIGA konfidenční interval CGA,
OR počet možných řešení.

Nejlepší nalezená nastavení parametrů simulovaného žíhání pro testované úlohy shrnuje následující tabulka:

Úloha Lk Smax T0 DT
5a
5b
6a
6b
6c
7a
8a
9a
100
200
800
200
200
800
12800
12800
1000
1000
2000
1000
1000
128000
2048000
2048000
50
50
20
50
50
100
100
100
5
5
5
5
5
1,25
1,25
1,25

Nejlepší nalezená nastavení parametrů pro genetický algoritmus jsou uvedena v následující tabulce:

Úloha Smax Npop Pc Pm
5a
5b
6a
6b
6c
7a
400
200
200
200
200
4000
200
200
200
200
200
3000
90
90
90
90
90
90
20
20
60
20
20
40

Hledání nastavení parametrů se vzhledem k nutnosti provádět měření opakovaně ukázalo oproti předpokladům jako časově velmi náročné.


Závěr

Tato práce se zabývá optimalizací nehierarchické telekomunikační sítě s přímým, deterministickým směrování provozního zatížení. V první části byl formálně vymezen daný problém, byla odvozena horní hranice počtu řešení úlohy a byla rozebrána problematika vlivu reprezentace, včetně odvození vztahu pro výpočet horní hranice paměťových nároků navržených reprezentací. Další část pak shrnuje vlastnosti a principy některých známých obecných algoritmů použitelných pro řešení optimalizačních úloh. V rámci práce bylo provedeno přizpůsobení algoritmů tak, aby byly použitelné pro řešení dané úlohy a následně byl vytvořen odpovídající program (rozsahem překračující 5500 řádek zdrojového kódu). Byly uvedeny podrobnosti o implementaci a provedených přizpůsobeních. Na závěr byly implementovány algoritmy, testovány na vybraných úlohách a bylo provedeno jejich srovnání. Oba algoritmy se ukázaly jako použitelné pro daný účel, pravděpodobně je zřejmě možné dosáhnout jejich dalšího zrychlení a zkvalitnění aplikovaním některých vylepšení, která byla v jejich obecné podobě již publikována. Jedná se např. u GA o turnajovou selekci, elitářství a další techniky. Tyto možnosti budou využity, neboť se předpokládá další rozvíjení této práce i implementace algoritmů.



Příspěvek vznikl za podpory grantu FRVŠ č.2047/2004.

Reference

[1] Hudousek,O. Evaluation of the Erlang-B formula. RTT 2003 - Proceedings. Bratislava: FEI, Slovak University of Technology, 2003, p.80-83.

[2] Hudousek,O. Precision of the Erlang-B Function Evaluation for noninteger number of service lines. Sborník konference RTT 2004. Praha: FEL, České vysoké učení technické, 2004

[3] Johnson.D.S.; Lenstra.J.K.; Rinnooy Kan.A.H.G. The Complexity of the Network Design Problem. Networks, Vol.8 New York: John Wiley & Sons, Inc., 1978, p.279-285

[4] Mařík.V.; Štěpánková.O.; Lažanský.J. a kol. Umělá inteligence (3). Praha: Academia 2001. 328 s. ISBN 80-200-0472-6.

[5] Papadimitrou.C.H. Computational Complexity. Adison-Wesley Publishing Company 1994. 523 s. ISBN 0-201-53082-1.

[6] Pioro.M. et al. Topological design of telecommunication networks (Nodes and links localization under demand constraints). Teletraffic Engineering in the Internet Era: Proceedings of the International Teletraffic Congress - ITC-17 Salvador Da Bahia, Brasilia: Elsevier Science, 2001, p.629-642. ISBN 0444509119.

[7] Rapp, Yngve. Planning of Junction Network in a Multi-exchange Area. I General Principles. Ericsson Technics, 1964, no.1, p.77-130.

[8] Rapp, Yngve. Planning of Junction Network in a Multi-exchange Area. II Extensions of the Principles and Applications. Ericsson Technics, 1965, no.2, p.187-240.

[9] Vidal.V.V.R. et al. Applied Simulated Anealing. Berlin: Springer-Verlag 1993.




1 Tento text je omezen pouze na intuitivní představu lokálních a globálních extrémů funkce f, neboť přesnější vymezení těchto pojmů závisí na konkrétní podobě funkce.

2Všude v textu, kde se hovoří o náhodné volbě čísla, míní se v implementaci výstup generátoru pseudonáhodných čísel.

3Konfidenční interval byl stanovován za předpokladu normálního rozložení hodnot při jejich neznámém rozptylu. K výpočtu bylo tedy použito Studentova rozložení.