Prohledávání pomocí harmonií

Technology

12 hours ago

Author

Prohledávání pomocí harmonií ( Harmony search, dále jen HS) je obecný metaheuristický algoritmus pro řešení optimalizačních problémů. HS se používá pro lokalizaci globálního optima nebo jeho dobré aproximaci pro danou cílovou funkci, jejíž definiční obor může být jak spojitý, tak diskrétní.

Jméno a i vlastní algoritmus je inspirovaný improvizací jazzových muzikantů. V HS každá proměnná odpovídá jednomu muzikantovi a její hodnota odpovídá notě, kterou daný muzikant hraje. +more Optimální řešení je takové řešení, které má dohromady nejlepší harmonii (hodnotu cílové funkce).

Hlavní výhody HS: *dokáže uniknout z lokálního optima *může používat jak diskrétní tak spojité domény proměnných *nepotřebuje derivaci cílové funkce *nepotřebuje počáteční inicializaci proměnných

Schéma algoritmu

Popíšeme schéma algoritmu pro diskrétní proměnné.

Zadání

maximalizovat funkci f(\textbf{x})

kde \textbf{x} = (x_1, x_2, \ldots , x_n)

a \forall{i} \; x_i \in dom(x_i) = \{x_i(1), x_i(2), \ldots, x_i(k_i)\}

Tedy každá proměnná x_i má k_i možných hodnot, které může nabývat. Úkolem je nalézt takovou kombinaci hodnot, že f(\textbf{x}) je maximální.

Parametry algoritmu

přirozené číslo HMS (harmony memory size) - velikost paměti jednotlivých muzikantů *reálné číslo HMCR (harmony memory considering rate) v rozmezí 0 až 1 - pravděpodobnost, že muzikant vybere hodnotu ze své paměti *reálné číslo PAR v rozmezí 0 až 1 - pravděpodobnost, že muzikant vybranou hodnotu ze své paměti trochu upraví (doladí) *přirozené číslo MI (maximum improvisation) - maximální počet improvizací neboli maximální počet iterací algoritmu

Hodnoty těchto parametrů jsou typicky konstantní po celou dobu algoritmu, ale jsou i varianty, ve kterých se v průběhu algoritmu mění - například hodnotu PAR postupně lineárně zvětšovat.

Inicializace

Vytvoř HMS náhodných vektorů (\textbf{x}^1, \ldots , \textbf{x}^{HMS}) . Každý z těchto vektorů je dlouhý n a na i-tém místě má náhodnou hodnotu z domény i-té proměnné. +more Tyto vektory budeme označovat paměť.

Je možné vytvořit i více než HMS vektorů a vybrat z nich poté HMS vektorů s nejvyšší cílovou funkcí.

Tyto vektory tvoří paměti jednotlivých muzikantů

Iterace algoritmu

Vytvoř nový vektor {\textbf{x}}^{new} a to tak, že do každé jeho složky {{\textbf{x}}^{new}}_i dosadíš *náhodnou hodnotu z dom(x_i) = \{x_i(1), x_i(2), \ldots, x_i(k_i)\} s pravděpodobností 1 - HMCR *jinak (tedy s pravděpodobností HMCR ) vyber náhodnou hodnotu z \{{\textbf{x}_i}^1, \ldots , {\textbf{x}_i}^{HMS}\}. Tedy z paměti pro i-tou proměnnou. +more **Nechť je tato hodnota vybrána a je rovna x_i(k) (tedy {{\textbf{x}}^{new}}_i = x_i(k)). Tato hodnota je s pravděpodobností PAR doladěna. Do ({{\textbf{x}}^{new}}_i je dosazeno hodnota x_i(k + m) kde m je náhodně zvoleno z množiny \{-1, 1\}.

Pokud hodnota cílové funkce pro {\textbf{x}}^{new} je lepší než pro nejhorší vektor z paměti, tak tento nejhorší vektor z paměti vyhoď a na jeho místo dej {\textbf{x}}^{new}.

Je možné i vzhledem k diverzitě paměti uvažovat o složitějším pravidle vyhazování vektorů - například kombinovat hodnotu cílové funkce s mírou odlišnosti od ostatních vektorů (například vzdáleností od nejbližšího vektoru).

Zastavení a výsledek

Algoritmus provádí iterace tak dlouho, než jejich počet nepřesáhne zadaný počet (parametr MI), nebo není dosaženo dostatečného výsledku (hodnota cílové funkce přesáhne požadovanou mez). Jako výsledek je vrácen vektor z paměti, pro nějž cílová funkce vrací největší hodnotu.

Rozšíření

Algoritmus je možné rozšířit o podmínky, které mají proměnné splňovat. Pokud jsou tyto podmínky porušeny, je buď nově vygenerovaný vektor zahozen, nebo je penalizována hodnota účelové funkce.

Aplikace

Aplikací je celá řada, zde je uvedeno pouze pár příkladů. *automatická kompozice hudby *řešení sudoku *rozvrhování *robotika *predikce struktury RNA *logistika