Prohledávání pomocí harmonií

Z Wikipedie, otevřené encyklopedie
Skočit na: Navigace, Hledání

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[editovat | editovat zdroj]

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

Zadání[editovat | editovat zdroj]

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_ik_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[editovat | editovat zdroj]

  • 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[editovat | editovat zdroj]

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[editovat | editovat zdroj]

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[editovat | editovat zdroj]

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í[editovat | editovat zdroj]

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[editovat | editovat zdroj]

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[editovat | editovat zdroj]