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

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

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

• metoda totálních zkoušek,
  
• algoritmus větvení a mezí (branch and bound alg.).

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

• horolezecký algoritmus (hill climbing alg.),
  
• simulované žíhání (simulated anealing),
  
• genetický algoritmus (genetic algorithm).

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 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=(a₁,a₂,...a_k), 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 a₁ (reprezentující konkrétní cestu mezi jednou z dvojic uzlů) a postoupí se k prvku a₂, pro něj se opět zvolí konkr. hodnota a tak se postupuje až k a_n. 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 a_n. Pokud byly takto vyčerpány již všechny možné hodnoty a_n, zvolí se další hodnota prvku a_n-1 a volí se postupně všechny možné hodnoty a_n. 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=(a₁,a₂), přičemž a₁ je z {7, 2, 5, 1}, a₂ je z {3, 4, 1}. Hodnota kriteriální funkce je dána vztahem f = a₁ + a₂. 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 f_b.

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

Horolezecký algoritmus patří do skupiny tzv. gradientních algoritmů. Uvažujme opět řešení ve tvaru vektoru a=(a₁,a₂,..,a_n) 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ém¹. 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í.

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í:

(23)

Parametr T_A odpovídá teplotě ve fyzikálním procesu ochlazování, na počátku vykonávání algoritmu je nastaven na předem danou hodnotu T₀ 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

• nehomogenní, v nichž je parametr T_A zmenšován v každém kroku a
  
• homogenní, v nichž je parametr T_A zmenšován jednou za L kroků.

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

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

• T₀ - počáteční hodnota T_A,
• L - počet kroků pro stejnou hodnotu T_A (může se měnit i v průběhu),
• způsob aktualizace T_A - parametr T_A může být např. zmenšován o předem danou konstatní hodnotu po každých L krocích,
• K - celkový počet opakování nebo jiná podmínka ukočení algoritmu.

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

• a₀ - počáteční řešení,
• způsob hledání sousedního řešení,
• způsob výpočtu Df.

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ů.

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 f_i 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í:

(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í P_cdvojice jedinců, rodičů, nahradí jinou dvojicí jedinců, potomků. V případě SGA se postupuje tak, že se nejprve náhodně vybere pořadí r_g 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 r_g geny z počátku chromozomu prvního z rodičů a N_gen - r_g 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 P_m = 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

• S_max - počet generací (kroků algoritmu),
• N_pop - počet jedinců v populaci,
• P_c - pravděpodobnost reprodukce,
• P_m - pravděpodobnost mutace.

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ší.

              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:

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).

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í.

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

(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.

Algoritmus SA byl implementován v základní podobě bez zásadních úprav. Všechny obecné parametry, tj. T₀, L a počet opakování K jsou volitelné uživatelem, parametr T_A je snižován každých L kroků o volitelnou hodnotu DT_A. Počáteční řešení a₀ 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.

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 N_pop. Pravděpodobnost výběru jedince i do další generace je

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

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 r_m je z <0, 1). Pokud je menší než uživatelem zvolená pravděpodobnost mutace P_m (obvykle P_m = 0,01), pak se náhodně² 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 P_m 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í.

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í interval³. Následující tabulka uvádí srovnání řešení jednotlivých úloh oběma algoritmy (SA i GA)

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

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

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é.

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ů.

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.

¹ 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.

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

³Konfidenč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í.