Prohledávání pomocí harmonií

Prohledávání pomocí harmonií (anglicky 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. 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é. 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.
  • 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

Ostatní související algoritmy

• Genetický algoritmus
• Optimalizace hejnem částic (particle swarm optimization)