Úvod a cíle

U algoritmu v některých mezních případech může dojít k situaci, že na začátku algoritmu budou vygenerovány takové prvky (takové prvky se nazývají počáteční řešení), které jsou nepřípustné. Jedná se zejména o takové prvky, které nevyhovují omezením kladeným na účelovou funkci - to jestli je prvek v množině přípustných řešení se dozvíme až po vypočtení simulačního experimentu.

Pokud bychom taková řešení zamítli (tzv. Trest smrti (Death Penalty)), algoritmus nebude mít žádnou informaci o tom, jakým směrem se má vydat na své cestě za hledáním optimálního prvku. Proto je možné využít další metody práce (zejména penalizační funkce) s různými typy omezení, které jsou zpravidla používány v kontextu s evolučními výpočty (zpravidla i s vícekriteriální optimalizací). Tyto metody lze samozřejmě použít i v optimalizaci jednoúčelové funkce (Single-Objective Optimization). Takovými metodami jsou např.:

1. Trest smrti
2. Penalizační funkce
3. Opravné algoritmy a speciální operátory

1. Trest smrti (Death Penalty)

Trest smrti znamená přímé odmítnutí všech prvků z oblasti nepřípustných řešení. Díky zamítnutí se prvek nezahrnuje do dalších optimalizačních procesů. Toto omezení má opodstatnění v oblastech nepřípustných řešení, které jsou rozlehlé. Bohužel zavržení nepřípustných prvků vede ke ztrátě informací, které mohly být získány a nebudou tak použity během optimalizace. [6]

2. Penalizační funkce (Penalty Function)

Pokud se nahlíží na prohledávaný prostor možných řešení účelové funkce jako na „životní prostředí“ prvků z populace (viz - červené oblasti), pak penalizace má efekt „znepříjemnění“ pobytu prvků v penalizovaných oblastech prostoru řešení. V tomto příkladu je např. hledáno minimum, tudíž abychom znepříjemnily pobyt prvkům v oblastech nepřípustných řešení, je k jejich hodnotě účelové funkce přičtena konstanta. Kvalita prvku, která je posuzována hodnotou účelové funkce, je tímto způsobem degradována.

Z geometrického hlediska si lze toto „znepříjemnění“ představit jako lokální deformaci hyperpochy směrem k opačnému extrému, než je hledán. Jeden z mnoha přístupů při penalizaci. [5]

3. Opravné algoritmy (Repair Algorithms) a speciální operátory

Při použití opravných algoritmů nebo speciálních operátorů pracuje algoritmus pouze nad množinou přípustných řešení a jedině prvky náležící této množině mají příležitost účastnit se optimalizačního procesu. Následně jsou jednotlivá individua ohodnocována přímo použitím účelové funkce, bez nutnosti používat jakoukoliv formu penalizace.

Aby bylo možné tohoto stavu dosáhnout, je nezbytné použít speciální techniky, které zajistí přípustnost všech nově generovaných prvků.

V případu evolučních algoritmů existují v podstatě dva odlišné způsoby, jak dosáhnout stavu, aby prvek (v případě evolučních algoritmů jedinec) náležel množině přípustných řešení.

Jednak lze použít tradiční genetické operátory, které ovšem pracují nad celým prostorem prohledávání, a proto je nutné jakákoliv nepřípustná individua, která nám v procesu rekombinace vzniknou, modifikovat vhodným opravným algoritmem tak, aby výsledné individuum bylo přípustným řešením.

Druhý způsob je založen na myšlence využití speciálních operátorů, u nichž je garantováno, že jejich použitím na přípustné individuum čí více individuí nemůže jako produkt příslušné operace vzniknout individuum nepřípustné. [9]

V případě, kdy vygenerovaný prvek pomocí optimalizačního algoritmu leží mimo povolené meze (mimo definovaných hranic prohledávaného prostoru) je nutné zajistit, aby hodnoty rozhodovacích proměnných prvku po jejich přepočítání ležely uvnitř .

Překročení hranic prohledávaného prostoru je často způsobeno tím, že nové prvky (v grafu účelové funkce body), které jsou zkoumány, jsou generovány za pomoci veličin náhodného rozdělení. Popišme nyní nejvíce používané možnosti generování náhodného čísla v optimalizačních algoritmech.

Poznámka: Text v odstavci uvedený za znakem popisuje metody (funkce, procedury). V jednotlivých algoritmech za znakem // bude uváděn komentář, který se vejde do konce řádky. Pokud se komentář nevejde na jednu řádku, bude komentář vložen do závorek s hvězdičkami tj. (* pro začátek komentáře a *) pro konec komentáře.

Funkce Random_u (např. ) s indexem (Uniform) generuje náhodná čísla na základě rovnoměrného rozdělení na mezích intervalu v oboru reálných čísel, kde dolní mez je zahrnuta do intervalu a horní mez zahrnuta není. Pokud nebudou uvedeny hranice, bude generováno náhodné číslo v intervalu .

Algoritmus generování náhodného čísla v rozsahu dolní a horní meze na základě rovnoměrného rozdělení ve formě kódu v pseudopascalu je popsán v .

Všechna náhodná čísla v tomto intervalu mají stejnou pravděpodobnost, že budou (mohou být) vygenerována. To je patrné z obrázku zachycující hustotu pravděpodobnosti u rovnoměrného rozdělení (viz ).

Druhou možností generování bodů v sousedství je za pomoci normálního rozdělení.

Funkce Random_n (např. ) s indexem n (Normal) generuje náhodná čísla na základě normálního (Gaussova) rozdělení se střední hodnotou a se směrodatnou odchylkou . Pokud nebudou definovány hranice, bude navráceno náhodné číslo v normovaném rozdělení tj. se střední hodnotou a se směrodatnou odchylkou .

Pravděpodobnost vygenerování bodu (viz ) je závislá na střední hodnotě (v našem případě je to hodnota rozhodovací proměnné na jednotlivé ose) a rozptylu (míra šířky rozdělení), který je druhou mocninou směrodatné odchylky. Z grafu vyplývá, že nejvíce se budou generovat body ve střední hodnotě a čím dále budeme od této hodnoty, pravděpodobnost vygenerování bodu je menší.

Prvním přístupem (viz ) pro přepočtení je, že nahradíme nepřípustné souřadnice rozhodovacích proměnných prvku nově vygenerovanými souřadnicemi pomocí funkce New. Tento postup bude prováděn pro všechny souřadnice rozhodovacích proměnných vstupního prvku, které neleží uvnitř prohledávaného intervalu -té rozhodovací proměnné tj. (viz ), řádek 3 - dále bude uváděno jen číslo řádku). Pokud souřadnice neleží uvnitř intervalu, je nahrazena vygenerovaným náhodným číslem na základě rovnoměrného rozdělení v rozsahu mezí jednotlivého prohledávaného intervalu (řádek 4).

V algoritmu je zapotřebí přistupovat k hodnotám souřadnic rozhodovacích proměnných prvku (bodu - vektoru). Protože záleží na pořadí jednotlivých hodnot v prvku, lze prvek vnímat jako seznam. Přístup k jednotlivým prvkům seznamu je pomocí indexu v hranatých závorkách. Položky uvnitř seznamu (hodnoty jednotlivých rozhodovacích proměnných) budeme indexovat od počátečního indexu = 0 až do posledního indexu = počet rozhodovacích proměnných - 1. Tím vytvoříme pořadí hodnot jednotlivých rozhodovacích proměnných (řádek 2).

Dalším způsobem jak „opravit“ souřadnice rozhodovacích proměnných prvků, které jsou mimo prohledávaný interval prohledávaného prostoru je použití opravného algoritmu tzv. zrcadlení - perturbace (Perturbation). [11]

Pojem perturbace je také užíván v algoritmu simulovaného žíhání, kde představuje náhodnou výměnu dvou složek prvku. Pokud prvek obsahuje reálných na sobě nezávislých složek, modifikuje se náhodná složka prvku přičtením nebo odečtením náhodné hodnoty k hodnotě složky. [I8]

Vraťme se ale k prvnímu způsobu perturbace. Souřadnici, která leží mimo prohledávaný interval rozhodovací proměnné, překlopíme dovnitř prohledávaného prostoru kolem příslušné hrany prohledávaného prostoru. Znamená to, že pokud je souřadnice menší než dolní mez prohledávaného intervalu -té rozhodovací proměnné , je tato souřadnice překlopena o vzdálenost této souřadnice k dolní mezi dovnitř prohledávaného prostoru. A naopak - pokud je souřadnice větší než horní mez prohledávaného intervalu -té rozhodovací proměnné , je tato souřadnice překlopena o vzdálenost horní mezi k této souřadnice dovnitř prohledávaného prostoru.

Princip perturbace je patrný z následujícího obrázku (viz ).

Perturbaci popisuje následující algoritmus. V algoritmu je bod vnímám jako vektor souřadnic daného bodu - z pohledu simulační optimalizace jako seznamu nastavených hodnot jednotlivých rozhodovacích proměnných (viz - dále bude uváděno jen číslo řádku).

Princip zrcadlení hodnoty rozhodovací proměnné prvku, tj. zrcadlení hodnoty rozhodovací proměnné kolem dolní meze (řádek 5) nebo kolem horní meze (řádek 7) je uplatňován tak dlouho, dokud hodnota rozhodovací proměnné neleží uvnitř prohledávaného intervalu rozhodovací proměnné (řádek 3).

Funkce Perturbation (např. ) velmi jednoduchým způsob garantující „návrat“ prvku, který tyto hranice překročí, je zachycen pomocí následujícího algoritmu (viz ). [11]