Problema:
Didelių sporto lygų tvarkaraščių sudarymas
Problemos aprašymas:
10 komandų grupės sezonas susidaro iš 90 susitikimų, t.y. 45 susitikimai pirmą sezono pusę ir 45 atsakomieji susitikimai antrąją sezono pusę. Esminė šios problemos savybė skirianti ją nuo tradicinių didelių sporto tvarkaraščių yra nefiksuotas datų, kuriomis žaidžiama, tinklelis. Tai reiškia kad visi tvarkaraščiai yra skirtingi savo datų skaičiumi bei pačiomis datomis. Tvarkaraščiai turėjo būti sugeneruojami iš dalyvių pateiktų duomenų. Kiekviena komanda pateikia datas, kuriomis pageidauja/gali žaisti namie, ir datas, kuriomis negali dalyvauti varžybose.
Tvarkaraštis turi būti sudaromas remiantis šiomis taisyklėmis:
- Žaidimo data privalo būti viena iš namų komandos pageidaujamų datų.
- Žaidimo data negali būti tarp abiejų komandų negalimų datų.
- Komanda negali žaisti dviejų rungtynių tą pačią dieną.
Sprendimas:
Būsena ir energija:
Vienas svarbiausių pasirinkimų naudojant Simulated Annealing algoritmą yra būsenos (state) pasirinkimas. Mūsų atveju tai yra pats tvarkaraštis. Pakeičiant vieną tvarkaraščio datą gaunama nauja tvarkaraščio būsena, o tas pakeitimas vadinamas perėjimu tarp būsenų (transition). Būsenos energija (state energy) randama suskaičiavus visus žaidimus, kurie negali įvykti.
Pavyzdyje parodyta mažesnės grupės dvi tvarkaraščio būsenos. Būsenos A energija yra 3, o B - 2. Algoritmo tikslas - surasti tvarkaraščio būseną su nuline energija.
Perėjimo iš būsenos į būseną tikimybės ir temperatūros funkcija:
Rasti abi šias funkcijas ir parinkti tinkamus parametrus ir yra sunkiausias dalykas naudojant Simulated Annealing algoritmą. Kirkpatrick'as ir kiti rekomenduoja naudoti P=exp((e-e')/T) kaip perėjimo tikimybės funkciją. Čia e yra kol kas geriausios tvarkaraščio būsenos energija, e' - dabartinės sugeneruotos tvarkaraščio būsenos energija, T - dabartinė temperatūra. Ši funkcija ir naudojama mūsų darbe. Tačiau jos tradicinį elgesį ganėtinai keičia mūsų naudojama temperatūros funkcija. Dažnai Simulated Annealing algoritme naudojama temperatūra yra po truputį mažinama tuo pačiu mažu skaičiumi. Mūsų atveju tai nedavė gerų rezultatų, todėl mes naudojame temperatūros funkcija, kuri labiau pritaikoma šios problemos būsenų energijų skirtumams. Taigi, programoje naudojama temperatūros funkcija yra - T = c1 + (c2/(c2+iter_count)), kur c1 ir c2 yra konstantos, o iter_count reiškia iteracijų skaičių. Tokia temperatūros funkcija padaro perėjimo iš būsenos į būseną tikimybės funkciją beveik tiesinę mums reikalingoje srityje.
Rezultatai:
Programa sugeneruoja tvarkaraštį pakankamai greitai (1-2s), tačiau dėl savo tikimybinės prigimties gali užtrukti ir ilgiau.
Duomenys, kurie buvo naudojami programoje, yra realūs.
Egzistuoja komercinis produktas sprendžiantis šią problemą. Jame naudojamas Forarlbergo Taikomųjų mokslų universitete sukurtas algoritmas. Palyginus rezultatus, paaiškėjo, kad Simulated Annealing algoritmas veikia ne taip efektyviai, kaip algoritmas, kurį naudoja komercinis produktas, tačiau geriau nei genetiniai algoritmai.
Programą paleisti galima paspaudus čia.
Source kodas: src.zip.