\section{Úvod do optimalizace}

Optimalizace je obecně vazto proces úpravy stávajícího řešení
nějakého problému za účelem zlepšení jeho vlastností. Při
optimalizaci zkoušíme různé varianty řešení a znalostí, kterých
během toho nabýváme, se snažíme využívat tak, abychom postupně
získávali stále lepší a lepší řešení
\cite{HAUPT04}.
Pojmy ,,problém`` a ,,řešení`` v tomto případě chápejme pouze v co
nejširším možném slova smyslu.

\begin{definition}
Uvažujme nyní následující definici problému: nechť
$X = \{x_1, x_2, ... , x_n\}$
je množina
\emph{vstupních proměnných problému P},
$Y = \{y_1, y_2, ... , y_m\}$
je množina
\emph{konfiguračních proměnných problému P} a
$Z = \{z_1, z_2, ... , z_p\}$
je množina
\emph{výstupních proměnných problému P}.
Dále nechť
$C(I, Y)$
je
\emph{omezující podmínka problému P} a
$W(I, Y)$
je
\emph{optimalizační kritérium problému P},
kde
$I$
je
\emph{instance problému P}
daná ohodnocením vstupních proměnných tohoto problému. Pak
\emph{problém P}
definujeme jako
$P = \{X, Y, Z, C(I, Y), W(I, Y)\}$
\cite{PAA_WEB}.
\end{definition}

\begin{definition}
Dále platí, že
\emph{konfigurace Y instance I problému P}
je ohodnocení konfiguračních proměnných tohoto problému a
\emph{řešení Y instance I problému P}
je přípustná konfigurace
$Y$,
tj. platí
$C(I, Y)$.
Za
\emph{optimální řešení Y instance I problému P}
budeme považovat takové řešení
$Y$,
které bude mít ze všech možných řešení nejvyšší hodnotu
optimalizačního kritéria.
\emph{Suboptimální řešení Y instance I problému P} je pak takové
řešení
$Y$,
jehož hodnota optimalizačního kritéria je hlediska aplikace stále
ještě přijatelná
\cite{PAA_WEB}.
\end{definition}

Množina vstupních proměnných určuje konkrétní instanci problému,
dále jen instanci, a upřesňuje tak jeho zadání. Konfigurační
proměnné popisují potenciální řešení instance a platnost takto
popsaného řešení nám udává omezující podmínka. Množina výstupních
proměnných pak popisuje samotný výstup instance. Z výše uvedeného je
zřejmé, že množina výstupních proměnných je často podmnožinou
množiny konfiguračních proměnných a v řadě případů jsou obě množiny
totožné. Pokud tomu tak není, je třeba důsledně rozlišovat mezi
\emph{výstupem instance}
a řešením instance. Poslední prvek definice, optimalizační
kritérium, určuje
\emph{kvalitu řešení}
instance v kontextu zadání celého problému. Pro nás budou dále
nejdůležitější konfigurační proměnné, protože jsou to právě ony,
které podrobíme optimalizaci.

Pozorný čtenář si jistě všimne toho, že takováto definice problému
je velice blízká definci
\emph{problému kombinatorického}.
Liší se od ní v podstatě jen tím, že kombinatorický problém je
popsán s pomocí proměnných, které mají diskrétní obor hodnot.
Kombinatorický problém je tak vlastně jen speciálním případem
výše popsaného problému. K tomu se však ještě dále v textu vrátíme.

\begin{definition}
Uvažujme nyní
\emph{algoritmus A řešící problém P},
který během výpočtu používá kromě konfiguračních proměnných problému
$P$,
$X = \{x_1, x_2, ... , x_n\}$ i
\emph{pracovní proměnné},
$V = \{v_1, v_2, ... , v_q\}$
a nazvěme sjednocení obou množin proměnných
\emph{vnitřími proměnnými},
$U = X \cup V$.
\emph{Stavem s algoritmu A řešícího problém P}
budeme potom rozumět jakékoliv ohodnocení vnitřních proměnných
algoritmu
\cite{PAA_WEB}.
\end{definition}

\begin{definition}
Nechť
$S$
je množina všech stavů algoritmu
$A$
řešícího problém
$P$
a nechť
$Q = \{q_1, q_2, ... , q_r\}$
je množina operací
$S \rightarrow S$
takových, že
$q(s) \neq s$
pro žádné
$s \in S$.
Pak
\emph{stavový prostor algoritmu A řešícího problém P}
je dvojice
$(S, Q)$
\cite{PAA_WEB}.
\end{definition}

Jedná se tedy o množinu všech stavů algoritmu dovybavenou o množinu
operací, které umožňují přechod mezi různými stavy algoritmu a tedy
i pohyb jeho stavovým prostorem.

K výše uvedené definici je třeba poznamenat, že pracovní proměnné
nesou často informaci o tom, zda je ta či ona konfigurační proměnná
platná, a tedy zda-li už byla ohodnocena. V takovém případě se
rozlišuje stavový prostor daný pouze konfiguračními proměnnými
problému od
\emph{prostoru hledání}
odpovídajícímu shora uvedené definici. V dalším textu budeme
pracovat se stavovým prostorem ve smyslu znění tohoto odstavce.

\subsection{Základní přístupy k optimalizaci}

Teď, když jsme si zavedli pojem ,,problém`` a pojmy s ním
související, můžeme přikročit k dalším výkladu o optimalizaci.

Přístupy k optimalizaci můžeme podle jejich různých aspektů rozdělit
celkem do šesti základních kategorií
\cite{HAUPT04}.
Jejich hranice jsou však vytýčeny jen přibližně a kategorie se tak
v mnoha případech vzájemně překrývají:

\begin{enumerate}
\item {
V první kategorii rozlišujeme přístup
\emph{metodou pokus-omyl} a
\emph{funkční optimalizaci}.

\begin{itemize}
\item{
Metoda pokus-omyl se při zkoumání kvality různých řešení z velké
části spoléhá na intuitivní volbu řešení. Činíme tak, aniž bychom
blíže znali optimalizační kritérium, což se v praxi stává velice
často.
}

\item{
Naproti tomu, při funkční optimalizaci dokážeme optimalizační
kritérium vyjádřit pomocí matematické funkce a optimalizace spočívá
v hledání
\emph{extrémů této funkce}
buď pomocí příslušného matematického aparátu nebo numericky.
}
\end{itemize}
}

\item{
Na
\emph{počet dimenzí}
optimalizovaného problému klademe důraz v druhé kategorii.

Je zřejmé, že s růstem počtu dimenzí prudce stoupá i složitost
optimalizace. Nárůst složitosti je zpravidla exponenciálního
charakteru.
}

\item{
Do třetí kategorie pak spadá
\emph{statická} a
\emph{dynamická optimalizace}.

Při dynamické optimalizaci, na rozdíl od optimalizace statické,
uvažujeme i čas. Tím nám přibyde jedna dimenze a složitost
optimalizace se tak podstatně zvýší. Velké množství problémů
z reálného světa vede právě na tento typ optimalizace. Otázkou
zůstává, jakým způsobem budeme při optimalizaci s časem pracovat.
}

\item{
Nejen tím se zabývá čtvrtá kategorie, která rozlišuje optimalizaci
z hlediska použití proměnných s
\emph{diskrétním}
nebo
\emph{spojitým oborem hodnot}.

\begin{itemize}
\item{
V případě diskrétních proměnných mluvíme o optimalizaci
kombinatorických problémů. Tato třída problémů má konečně mnoho
diskrétních řešení, která je možné všechna prozkoumat s použitím
hrubé síly. Díky tomu je vhodná pro řešení s pomocí prostředků
výpočetní techniky.
}

\item{
Pokud však hledáme extrém matematické funkce, jedná se zpravidla
o optimalizaci spojitou.
}
\end{itemize}
}

\item{
Pátá kategorie řeší, zda použít proměnné s
\emph{omezeným} či
\emph{neomezeným oborem hodnot}.

V případě proměnných s omezeným oborem hodnot to znamená, že
optimalizační kritérium svážeme podmínkami, typicky ve formě rovnic.
To nám samozřejmě celý proces zkomplikuje a proto se v případě, že
je takovýto postup nezbytný, snažíme transformací optimalizačního
kritéria podmínek zbavit.

Pokud například budeme optimalizovat funkci
$f(x)$
na intervalu
$-1 \le x \le 1$,
bude pro nás výhodné zavést substituci
$x = sin(u)$
a dále optimalizovat funkci
$f(sin(u))$
\cite{HAUPT04}.
}

\item{
Poslední úhel pohledu na optimalizaci představuje šestá kategorie,
ve které rozlišujeme mezi optimalizací
\emph{deterministickou} a
\emph{nedeterministickou}.

\begin{itemize}
\item{
Řada optimalizačních algoritmů pro různé problémy vychází z pevně
dané sady počátečních řešení těchto problémů, kterou pak tyto
algoritmy transformují deterministickou posloupností operací. Díky
tomu jsou zpravidla při procházení stavového prostoru velice rychlé,
ale mají sklon k uváznutí v lokálních extrémech.
}

\item{
Algoritmy, které naproti tomu nejprve navzorkují stavový prostor
z velké části náhodným způsobem a dále jej pak procházejí
nedeterministicky, tj. jejich přechodová funkce se řídí určitým
rozdělením pravděpodobnosti, ve výsledku sice pomaleji konvergují
k optimálním řešením, ale mají zato mnohem vyšší pravděpodobnost
nalezení globálního optima. To je dáno především jejich výrazně
vyšší odolností vůči uváznutí v lokálních extrémech ve srovnání
se třídou algoritmů popsaných v předchozím odstavci.
}
\end{itemize}
}
\end{enumerate}

Všechny výše popsané přístupy k optimalizaci mají však jedno
společné: hledají pomocí vhodného algoritmu optimální řešení
zadaného problému. Pokud takové řešení nedokážeme dopředu
specifikovat, tj. neznáme horní nebo spodní mez optimalizačního
kritéria, nebo je jeho hledání příliš zdlouhavé, je cílem
optimalizace nalézt alespoň suboptimální řešení, které by vyhovovalo
potřebám dané aplikace.

\subsection{Minimum-seeking algoritmy}

Tato třída algoritmů má společný základ, kterým je více či méně
systematické prohledávání stavového prostoru algoritmu s ohledem na
extrémy optimalizačního kritéria. Existuje mnoho různých způsobů,
jakými se lze ve stavovém prostoru pohybovat a hledat tyto extrémy,
ať už se jedná o minimální či maximální hodnoty optimalizačního
kritéria. Ve většině případů však zpravidla nejsme schopni určit,
zda-li je nalezený extrém lokálního nebo globálního charakteru.
Nalezení globálního extrému je pro algoritmy tohoto typu obecně
velice obtížný úkol, s vyjímkou situací, kdy má
\emph{povrch stavového prostoru}
jednoduchý tvar. Povrchem stavového prostoru je zde myšlena plocha
definovaná optimalizačním kritériem.

Typickým příkladem algoritmu tohoto typu je algoritmus
\emph{úplného prohledávání stavového prostoru}.
Ten při hledání globálního optima ve formě extrému optimalizačního
kritéria postupuje zhruba následujícím způsobem:

\begin{enumerate}
\item{
Nejprve provede dostatečně jemné vzorkování stavového prostoru,
které obnáší vyhodnocení optimalizačního kritéria v jeho zvolených
bodech. Pokud se jedná o diskrétní stavový prostor, jako je tomu
v případě kombinatorických problémů, zvolené body odpovídají přímo
množině všech stavů tvořících tento prostor.
}

\item{
Poté projde algoritmus takto získanou množinu vzorků hrubou silou,
tj. postupně zkoumá jeden vzorek za druhým. Za globální optimum
pak zvolí takový bod stavového prostoru, který odpovídá vzorku
s nejnižší či, podle zadání problému, naopak nejvyšší hodnotou.
}
\end{enumerate}

Z výše uvedeného je zřejmé, že pokud je počet takto zkoumaných
vzorků vzhledem ke složitosti stavového prostoru příliš malý,
globální optimum nám v případě spojitého prostoru s vysokou
pravděpodobností proklouzne sítem výběru, a my tak v nejlepším
případě získáme suboptimální řešení daného problému. Pokud uvažujeme
diskrétní prostor, tak máme nalezení globálního optima vždy
zaručeno.

Jiným příkladem je už dříve zmíněná
\emph{funkční či analytická optimalizace},
která se od úplného prohledávání stavového prostoru liší především
způsobem výběru vzorků:

\begin{enumerate}
\item{
Tento přístup nahrazuje první krok úplného prohledávání stavového
prostoru, vzorkování samotného prostoru, analytickým nebo numerickým
určením extrémů optimalizačního kritéria. Dále pak pokračuje
obdobným způsobem.
}

\item{
Ve druhém kroce pak algoritmus pracuje s množinou vzorků, která by,
díky způsobu jejich výběru, měla obsahovat i globální optimum. Navíc
má výsledná množina prohledávaných vzorků z principu podstatně
menší mohutnost, než je tomu v případě předchozího algoritmu.
}
\end{enumerate}

Analytická optimalizace je nesporně elegantější než prosté
prohledávání stavového prostoru, nicméně složitost jejího prvního
kroku přímo závisí na dimenzi uvažovaného stavového prostoru a také
na tvaru jeho povrchu.

Pokud obsahuje povrch trhliny a zlomy, vyžaduje tento přístup
úpravu spočívající v použití
\emph{Lagrangeových multiplikátorů},
které umožňují nahradit optimalizační kritérium se všemi jeho
omezeními funkcí, která tato omezení obsahuje inherentně
\cite{HAUPT04}.
Podrobnější popis této techniky však přesahuje rámec tohoto textu.

\subsection{Algoritmy inspirované přírodními procesy}

Zatímco klasické optimalizační algoritmy se spoléhají na
deterministicky řízené prohledávání stavového prostoru,
v osmdesátých letech minulého století se začaly objevovat nové
typy algoritmů, souhrnně nazývané
\emph{evoluční techniky},
jejichž tvůrci čerpali inspiraci ve fungování přírodních procesů.

Mezi tyto algoritmy se řadí například
\cite{WIKI_EC}:
\begin{itemize}
\item{
\emph{genetické algoritmy}
(angl. Genetic Algorithms),
}

\item{
\emph{genetické programování}
(angl. Genetic Programming),
}

\item{
\emph{evoluční programování}
(angl. Evolutionary Programming).
}
\end{itemize}

Mezi jim příbuzné algoritmy pak patří
\begin{itemize}
\item{
\emph{simulované žíhání}
(někdy také uváděné jako
\emph{simulované ochlazování},
angl. Simulated Annealing),
}

\item{
\emph{optimalizace pomocí roje částic}
(angl. Particle Swarm Optimization),
}

\item{
\emph{optimalizace pomocí kolonie mravenců}
(angl. Ant Colony Optimization).
}
\end{itemize}

Všechny výše uvedené algoritmy se při řešení problémů pohybují
stavovým prostorem tak, že počáteční sadu řešení transformují pomocí
specifických operátorů a přesouvají se tak do jiných oblastí
stavového prostoru. Aplikace těchto operátorů se pak řídí různými
statistickými metodami.

Tímto způsobem dokáží efektivně prohledat rozsáhlé stavové prostory
a nevadí jim přitom ani použití diskrétních proměnných ve
specifikaci problému, ani případné nespojitosti optimalizačního
kritéria.

Na přírodu samotnou a procesy, které se v ní odehrávají, je možné
nahlížet jako na obrovský optimalizační algoritmus jehož předmětem
optimalizace jsou celé
\emph{živočišné druhy}.
Kvalita jednotlivých druhů je v něm určena mírou, na kolik se každý
druh dokázal přizpůsobit svému habitatu
\cite{HAUPT04}.

Tato veličina, definovaná na celé
\emph{živočišné populaci},
tak formuje zvlněnou plochu, jejíž míra elevace v jednotlivých
oblastech prostoru této populace odpovídá dříve uvedené míře
adaptace živočišných druhů vyskytujících se v té které oblasti
prostoru.

Jinými slovy si tento prostor můžeme představit jako hornatou
krajinu, jejíž vyvýšené části obývají jednotlivé živočišné druhy.
Rozloha těchto částí pak udává diverzitu populací druhů, které je
obývají. Diverzitou v tomto případě rozumíme podíl
\emph{jedinců}
s unikátními rysy v rámci celé populace daného druhu. Čím je rozloha
takové části menší, tím vyšší je stupeň adaptace vyžadovaný pro
přežití druhu obývajícího tuto část.

V předchozím odstavci jsme narazili na pojem ,,rys jedince'', aniž
bychom jej nějak blíže specifikovali. Rys jedince je možné považovat
za vnější projev
\emph{dědičné informace},
která je v každém jedinci uložena a z větší části se mezi jedinci
předává z generace na generaci. O tom, jakým způsobem je toho
dosaženo, bude pojednávat další část tohoto textu.

Tím se dostáváme ke způsobu, jakým je v jedinci uložena dědičná
informace a jakým způsobem se tato informace projevuje na
morfologické stavbě jedince, jeho vlastnostech a chování v rámci
okolního prostředí
\cite{WIKI_GENE}:

\begin{itemize}
\item{
Základní jednotkou informace organismu každého jedince je
\emph{gen},
což je segment nukleové kyseliny, který definuje přesnou strukturu
jedné bílkoviny a řídí způsob její produkce a jejího dalšího
metabolismu v organismu. Soubor všech genů v rámci celého organismu
se pak nazývá
\emph{genom}.

Vzhledem k faktu, že sám gen nemá atomickou strukturu a je tvořen
kombinací čtveřice nukleotidů, existuje pro každý gen více možných
kódování--tzv.
\emph{allel}.
Allely jsou tedy různé variace jednoho genu.
}

\item{
Geny jsou seskupeny do
\emph{chromosomu},
kterých se může v jedné buňce organismu vyskytovat větší počet.
V lidském organismu se pak typicky jedná o jeden pár chromosomů do
ktererého přispěl každý z rodičů právě jedním chromosomem. Místu,
které gen v rámci chromosomu obsazuje se říká
\emph{locus}.

Chromosom je tedy tvořen velice dlouhou posloupností genů, která
řídí vlastnosti a funkci celého organismu. Každá buňka organismu
navíc obsahuje kompletní sadu chromosomů a tento fakt je z hlediska
správné funkce organismu nesmírně důležitý, protože umožňuje
decentralizované řízení jeho základní látkové výměny.
}
\end{itemize}

Při
\emph{pohlavním rozmnožování}
jedinců dojde mezi dvěma jedinci k vzájemné výměně genetické
informace. V pohlavních buňkách každého jedince je obsažen pouze
jeden chromosom, ze kterého se při rozmnožování vytvoří identická
kopie. Tyto kopie si pak oba jedinci vymění, takže každý z nich bude
mít dále k dispozici jeden chromosom původní a jeden od svého
protějšku. Nakonec každý jedinec oba chromosomy rekombinuje tak, že
se tyto nejdříve v jednom bodě spojí, vzájemně si prohodí koncové
části a nakonec se od sebe zase oddělí. Této operaci se říká
\emph{operace křížení}.

V celé populaci druhu dochází v průběhu času k rozmnožování jedinců
výše popsaným způsobem. Tento proces však není zcela náhodný, ale
řídí se několika několika základními pravidly, která v polovině
19.\ století postuloval ve své práci nazvané
\emph{,,O původu druhů''}
britský přírodovědec Charles R.\ Darwin.

Tato pravidla se dají shrnout následujícím způsobem:
\begin{enumerate}
\item{
Potomek dědí výraznou část svých vlastností po rodičích. Tím je
zajištěna krátkodobá stabilita populace a výrazná mezigenerační
změna vlastností populace je bez vnějšího zásahu velice
nepravděpodobná.
}

\item{
V populaci pohlavně se rozmnožujících jedinců nejsou žádní dva
jedinci stejní. Dále platí, že většina této rozmanitosti přechází
i do další generace takovéto populace.
}

\item{
Jedinci jsou obecně velice plodní a vyprodukují výrazně větší
množství potomků, než nakonec dosáhne dospělosti a může se začít
rozmnožovat.
}

\item{
Přežití jedince a pravděpodobnost, s jakou dosáhne dospělosti
a začne se rozmnožovat, přímo závisí na vlastnostech tohoto jedince
a na tom, jak dalece se dokázal přizpůsobit danému prostředí.
}
\end{enumerate}

Výše uvedená pravidla ve své podstatě popisují jev, který Darwin
nazval
\emph{přírodním výběrem}
\cite{WIKI_OS}.

Tento jev je charakteristický tím, že jakkoliv drobné variace
v genomu jedince, které mu v daném prostředí poskytnou konkurenční
výhodu před ostatními jedinci, a tudíž i zvýší jeho šanci na
přežití, mají tendenci přecházet na jeho potomky. To má
v dlouhodobém horizontu za následek adaptaci populace druhu jako
celku na prostředí, ve kterém se tato populace vyskytuje.

