Vítejte u čvrtého (a určitě nikoliv posledního 😉 ) dílu seriálu věnovaného losování soutěží (1. díl, 2. díl, 3. díl). V tomto komentáři nám dal Tomáš Chalupník na vědomí, že se k nalezení optimálního řešení hodí metaheuristika a uvedl i optimální nalosování. Nějak jsem se domníval, že se Tomáš spojí s Alešem a že nový SORG bude mít supr-dupr startovací matice. Losování jsem pustil z hlavy, ale nedávno jsem v práci opět narazil na pojem metaheuristika a vzpomněl si, že sám pro sebe jsem si problém vlastně nevyřešil. Prázdniny se ovšem k podobným podnikům výborně hodí.

Nejprve „disclaimer“ – baví mě matematika a „losoval“ jsem pro vlastní potěšení z bádání. Osobně si myslím, že na nalosování nezáleží, dokonce v zájmu „koukatelnosti“ soutěže podporuji sestavování skupin z pilotů stejné nebo podobné výkonnosti.

Dodatečná vsuvka: Obvykle po mě žena kontroluje vše, co napíšu. Tentokrát se dostala jen ke 3. odstavci a udělalo se jí špatně, má „pouze“ humanitní vzdělání 🙂 . Abyste neříkali, že jsem vás nevaroval 😀 .

Shrnutí předchozích dílů
Dále zopakuji, co jsem zjistil v předchozích dílech. Vše budu popisovat na příkladu soutěže s 18 piloty rozdělenými po šesti do tří skupin, létá se šest kol (což dále označuji kódem startoviště – skupiny – kola = 6-3-6). Pro rozdělení pilotů do skupin se určí vzájemné počty letů, vzájemné počty letů se vynásobí váhami a vypočte se celkové skóre.

Na tomto obrázku je ukázána startovací matice (sloupec L je startoviště, řádek K-S je kolo-skupina). Vzájemné počty letů jsou nalevo od matice, tj. v tabulce vzájemných letů je 10 nul, 63 jedniček, 44 dvojek, 26 trojek, 9 čtyřek a 1 pětka. Modrá čísla nalevo jsou váhy, které jsou třetí mocninou počtu vzájemných letů. V uvedeném příkladu tedy skóre nalosování 10*0+63*1+44*8+26*27+9*64+1*125 = 1818.

Jak ukazuje tento obrázek (převzatý z 1. dílu), náhodné losování mívá skóre mezi 1500 až 2500, většina náhodných výběrů ale spadne mezi 1900 a 2100 (četnosti jsou pro 1000 náhodných losování). Jak napsal Tomáš, nejmenší skóre uspořádání 6-3-6 je 1080.

První pokus o vylepšení náhodného losování spočíval v tzv. hladovém algoritmu (podrobněji popsáno ve 2. a 3. dílu – hladový se jmenuje proto, že „sežere tady a teď to nejlepší bez ohledu na to, co ho čeká o kousek dále“). Piloti se do skupin přiřazují tak, aby v daném okamžiku bylo skóre minimální. Výsledné skóre okolo 1398 je lepší než při losování náhodném, náhodným losováním v podstatě nedosažitelné, ale pořád ještě moc vysoké.

Optimalizační algoritmus
Můj nejnovější postup nalezení optimální startovací matice je následující:

1. Vygenerování výchozí startovací matice (nejrychlejší je náhodná, lze použít i hladový algoritmus, ale je to skoro zbytečné).
2. Záměna jednoho pilota z jedné skupiny kola s jiným pilotem z jiné skupiny stejného kola.
3. Výpočet skóre upravené startovací matice; pokud je lepší než stará hodnota skóre, uložení skóre i poloh a jmen vyměněných pilotů.
4. Vrácení vyměněných pilotů do výchozích poloh.
5. Opakování bodů (2) až (4) pro všechny dvojice pilotů.
6. Po vyzkoušení všech dvojic pilotů se provede výměna těch dvou pilotů, kteří minimalizují skóre (jejich jména a polohy byly uloženy v kroku (3).
7. Opakování optimalizačního kroku (2) až (6) po předepsaný počet opakování.

Je to hodně výpočtů, ale od toho máme počítače. Popsaný postup je heuristický a jak jsem zjistil, nefunguje bezchybně, ostatně přesně podle odborné literatury. Algoritmus se snadno dostane na skóre okolo 1200 (pro 6-3-6) a tam začne postup přeskakovat mezi několika řešeními, ze kterých není úniku. K heuristice se musí přidat ono „meta“, tj. zavedení nějaké strategie, co v takové situaci dělat. V našem případě jsem zvolit tu nejjednodušší podmínku – zákaz předchozích pohybů, aby se algoritmus nemohl vracet po svých vlastních stopách k již prozkoumanému řešení. Potřebný počet optimalizačních kroků i délku tzv. tabu seznamu (seznamu zakázaných kroků) je třeba určit zkusmo. Pro vzor 6-3-6 jsem skončil u 50 optimalizačních kroků a zákazu opakování po 25 předchozích kroků.

Skóre v průběhu jednotlivých optimalizačních kroků (iterací) vypadá následovně, tento průběh je dosti typický – v průběhu asi 15-20 kroků skóre poklesne k 1200 a potom už se hledá, jestli tam někde není skulinka umožňující další snížení skóre. Pokud by stačilo „dost dobré řešení“, je možné iteraci ukončit po asi 20 krocích a tak významně zkrátit dobu výpočtu.

Nejlepší optimum nenajde algoritmus vždy. Ze 30 pokusů na náhodně vygenerovaných maticích vrátil program následující skóre:
1080 – 1x
1128 – 16x
1152 – 7x
1164 – 5x
1194 – 1x

Takže globální optimum program našel jen 1x ze 30 pokusů, ale jen o trochu horší skóre ve více než polovině případů.

Zde je snad dobré připomenout, že účelem metaheuristických postupů je nalézt „dost dobré řešení“, ne nezbytně nejlepší. V našem případě lze při použití opakovaného náhodného losování získat skóre okolo 1600, zatímco popisovaný algoritmus dosáhne 1200 již po několika málo optimalizačních krocích. Další zlepšení na 1100 už může být náročné a možná i zbytečné. Převedeno na výpočtový čas, tak vygenerování náhodné matice trvá několik sekund. Optimalizace na skóre 1200 zabere asi 2 minuty (např. 20 kroků po 6 sekundách – vysvětlení níže), pokles na 1128 si vyžádá tak 15 minut (např. 3 úplné výpočty po 50 krocích) a nalezení optima 1080 trvalo asi 3 hodiny počítání (30 úplných výpočtů).

Pro nejlepší skóre 1080 vypadají iterace takto…

… a tabulka výsledků takto. V tabulce vzájemných letů je 18 nul a 135 dvojek, žádní dva piloti proti sobě neletí tři- a vícekrát.

Až sem to vypadá skvěle, ale samozřejmě háček přítomen je – náročnost (a tudíž i doba výpočtu) roste přibližně se 6. mocninou počtu pilotů a se druhou mocninou počtu kol. Program jsem ladil na „dovolenkovém“ Asus Eee PC, který jeden optimalizační krok uspořádání 6-3-6 počítal asi 85 sekund! Výpočet s 50 kroky by tedy zabral hodně přes hodinu, na druhém notebooku s procesorem i7 trval jeden výpočet s 50 kroky asi 5 minut, tj. jeden krok asi 6 sekund, což už se dalo vydržet.

No jo, jenomže na soutěži může přijet i více než 100 pilotů a kol může být 12. Potom by jeden optimalizační krok na mém rychlém počítači trval (pro 18 pilotů a 6 kol zabral jeden optimalizační krok 6 sekund) T = 6*(100/18)^6*(12/6)^2=705600 s = 196 hodin = 8.2 dne. Hmmm, optimalizační algoritmus bude potřebovat optimalizaci 🙂 (pár nápadů už mám, ale náladu a čas asi zase až za pár měsíců).

Zdá se mi, že nalosování do nějakých 20 pilotů lze optimalizovat pomocí tohoto algoritmu přímo na letišti, pro větší počty pilotů bude lepší předem vygenerovaná obecná startovací matice. Ale to je jen doporučení, viz disclaimer nahoře 😉 .

Výpočtový program
Na závěr ještě popíši přiložený program v Excelu. Zde upozorňuji, že program není napsán s úmyslem, aby byl k uživateli přespříliš přátelský. Doufám, že si s ním poradíte.

Program má dva listy – List1 a List2, a řídí se pomocí maker. Zadávané údaje jsou modré.

První list „List1“ je generovací a zadává se počet startovišť, počet skupin, počet kol a také váhový vektor. Procedura vyvolaná Ctrl-Shift-U vymaže list od sloupce 3 napravo, tj. když změníte počty startovišť, skupin a kol, nejprve „Ukliďte“ 🙂 . Procedura vyvolaná Ctrl-Shift-G vyGeneruje matici hladovým algoritmem, procedura Ctrl-Shift-N potom Náhodným losováním. Hladový algoritmus už je jen pozůstatek z minulosti, náhodná matice postačí. Okamžitě po vygenerování matice program sestaví i tabulku vzájemných letů, spočítá počty vzájemných letů a celkové skóre. Příkaz Ctrl-Shift-N tak lze opakovat podle libosti. Ukázaný případ platí pro 12 pilotů ve třech skupinách a 6 letů). Skóre nalosování je 816 a v tabulce vzájemných letů se vyskytuje jedna 5, pět 4 a šest 3.

List „List2“ je optimalizační a zadává se startovací matice a další údaje. V programu je to udělané tak, že se příkazem Ctrl-Shift-I list Inicializuje. Příkaz vymaže všechny staré údaje a do startovací matice dá odkazy na matici z listu „List1“, nikoliv jen hodnoty z vygenerované matice. To je výhodné, neboť pokud se nemění počty startovišť, skupin a kol, lze jednoduše příkazem Ctrl-Shift-N vygenerovat novou náhodnou matici bez opakování inicializace. Pozor na počet průchodů (optimalizačních kroků), začněte s malým číslem, výpočet může trvat hodně dlouho, jak je naznačeno výše. Vlastní Optimalizace se spustí Ctrl-Shift-O.

Po proběhnutí výpočtu program vrátí:

Nejlepší nalezenou matici, včetně počtu vzájemných letů (3x 0, 18x 1 a 45x 2, tj. žádní dva piloti proti sobě neletí 3 a vícekrát) a celkového skóre (378) …

…tabulku vzájemných letů…

… a také optima nalezená v jednotlivých optimalizačních krocích. Například v 50. kroku výpočet trval už 140 sekund a program přehodil pilota P7 z druhého řádku a třetího sloupce s pilotem P6 z třetího řádku a třetího sloupce. Nejlepší skóre v 50. kroku bylo potom 390. Nejlepší skóre bylo nalezeno už 15. kroku, takže těch 50 je pro schéma 4-3-6 zbytečně moc.

Hodně štěstí 🙂 , excelový program v ZIP ke stažení.

Honza
19.7.2020