TTTC6544 · L6 · Hands-onAmali
Emulation ArenaArena Emulasi
Pick a problem, run hill climbing, Simulated Annealing and the Great Deluge on equal budgets over many seeds, then break them with the challenges and repair them with the suggested fixes. Everything runs in your browser.Pilih masalah, jalankan pendakian bukit, Penyepuhlindapan Simulasi dan Banjir Besar dengan bajet sama atas banyak benih, kemudian rosakkan dengan cabaran dan baiki dengan pembaikan yang dicadangkan. Semuanya berjalan dalam pelayar anda.
Emulation ArenaArena Emulasi
HC · SA · GD
Challenges:Cabaran:
Convergence: median best-so-far (band = min–max over seeds)Penumpuan: median terbaik setakat ini (jalur = min–maks atas benih)
Share of worse moves accepted (per 2% of budget)Peratus langkah buruk diterima (setiap 2% bajet)
HCSAGDbest knownterbaik diketahui
| AlgorithmAlgoritma | Mean ± sdPurata ± sp | BestTerbaik | WorstTerburuk | Worse moves acceptedLangkah buruk diterima |
|---|
SA diagnosisDiagnosis SA
GD diagnosisDiagnosis GD
Tasks with expected observations (10 seeds)Tugasan dengan pemerhatian dijangka (10 benih)
- Basic · Route, out of the box. Expected means: HC ≈ 243, SA ≈ 236, GD ≈ 242 km. Which curve drops fastest in the first 10% of the budget, and which finishes lowest?
- Asas · Laluan, tetapan asal. Purata dijangka: HC ≈ 243, SA ≈ 236, GD ≈ 242 km. Lengkung mana yang turun paling cepat dalam 10% pertama bajet, dan yang mana berakhir paling rendah?
- Basic · Break SA. Press Overheat SA on the route: SA ends near 330 km, worse than hill climbing, and its acceptance curve never falls. Then press Quench SA: SA ≈ 243, the same as HC. Explain both with the acceptance chart.
- Asas · Rosakkan SA. Tekan SA terlampau panas pada laluan: SA berakhir hampir 330 km, lebih buruk daripada pendakian bukit, dan lengkung penerimaannya tidak pernah turun. Kemudian tekan Lindap kejut SA: SA ≈ 243, sama seperti HC. Terangkan kedua-duanya dengan carta penerimaan.
- Intermediate · Exam timetable, out of the box. Both metaheuristics lose to plain hill climbing (HC ≈ 1,500; SA ≈ 3,300; GD ≈ 5,900). Read the diagnosis: SA's automatic T₀ is fooled by the 1000-point clash penalty, and linear GD wastes its budget far above good solutions. Apply the suggested fixes one at a time. With Apply both fixes, SA ≈ 1,100 and GD ≈ 2,000.
- Pertengahan · Jadual peperiksaan, tetapan asal. Kedua-dua metaheuristik kalah kepada pendakian bukit biasa (HC ≈ 1,500; SA ≈ 3,300; GD ≈ 5,900). Baca diagnosis: T₀ automatik SA tertipu oleh penalti pertindihan 1000 mata, dan GD linear membazir bajet jauh di atas penyelesaian baik. Gunakan pembaikan yang dicadangkan satu demi satu. Dengan Guna kedua-dua pembaikan, SA ≈ 1,100 dan GD ≈ 2,000.
- Intermediate · Tiny budget. With N = 2,000 on the route, SA ≈ 249, GD ≈ 249 and HC ≈ 243. Why do both metaheuristics lose when the budget is too small to cool or lower the level properly?
- Pertengahan · Bajet kecil. Dengan N = 2,000 pada laluan, SA ≈ 249, GD ≈ 249 dan HC ≈ 243. Mengapa kedua-dua metaheuristik kalah apabila bajet terlalu kecil untuk menyejuk atau menurunkan paras dengan betul?
- Advanced · Continuous tuning. Out of the box SA ≈ 11 and GD ≈ 15; with fixes SA ≈ 8. Compare Drown GD and Lazy GD here and on the route. Surprisingly, a lazier target helps GD on this problem (≈ 13). Propose an explanation based on how rugged the landscape is.
- Mahir · Penalaan selanjar. Tetapan asal SA ≈ 11 dan GD ≈ 15; dengan pembaikan SA ≈ 8. Bandingkan Tenggelamkan GD dan GD malas di sini dan pada laluan. Mengejutkan, sasaran yang lebih malas membantu GD pada masalah ini (≈ 13). Cadangkan penjelasan berdasarkan kekasaran landskap.
Strengths, weaknesses and potentialKekuatan, kelemahan dan potensi
| Simulated Annealing | Great Deluge | |
|---|---|---|
| Strengths seen in the arenaKekuatan dalam arena | Best final quality on all three problems once tuned; reheating made it reliable on the route (234.5 km in every seed).Kualiti akhir terbaik pada ketiga-tiga masalah selepas ditala; pemanasan semula menjadikannya boleh dipercayai pada laluan (234.5 km pada setiap benih). | Least sensitive to bad settings: its worst setting is far less damaging than SA's worst. With non-linear decay it reaches a good-enough solution sooner.Paling kurang sensitif terhadap tetapan buruk: tetapan terburuknya jauh kurang merosakkan berbanding SA. Dengan susutan tak linear ia mencapai penyelesaian cukup baik lebih awal. |
| Weaknesses seenKelemahan dilihat | Temperature lives in cost units: too hot wanders, too cold freezes; wide cost scales fool automatic calibration.Suhu dalam unit kos: terlalu panas merayau, terlalu sejuk membeku; skala kos yang luas memperdaya penentukuran automatik. | Needs a sensible target; drowns when too optimistic; linear decay wastes budget when costs span orders of magnitude.Perlukan sasaran munasabah; tenggelam apabila terlalu optimis; susutan linear membazir bajet apabila kos merentasi beberapa magnitud. |
| Potential (try in the arena)Potensi (cuba dalam arena) | Reheating; calibrating T near good solutions; adaptive or learned schedules Correia et al. 2023 Qiu & Liang 2025; parallel tempering Earl & Deem 2005.Pemanasan semula; menentukur T hampir penyelesaian baik; jadual adaptif atau dipelajari Correia et al. 2023 Qiu & Liang 2025; pembajaan selari Earl & Deem 2005. | Non-linear decay Landa-Silva & Obit 2008; reheating the level McMullan 2007; GD inside hyper-heuristics Hutama & Muklason 2024; hybrids with exact solvers Baykasoğlu et al. 2026.Susutan tak linear Landa-Silva & Obit 2008; memanaskan semula paras McMullan 2007; GD dalam hiper-heuristik Hutama & Muklason 2024; hibrid dengan penyelesai tepat Baykasoğlu et al. 2026. |
Key sourcesSumber utama
- Dueck, G. (1993). New optimization heuristics: The great deluge algorithm and the record-to-record travel. Journal of Computational Physics, 104(1), 86–92. https://doi.org/10.1006/jcph.1993.1010
- Burke, E. K., Bykov, Y., Newall, J. & Petrovic, S. (2004). A time-predefined local search approach to exam timetabling problems. IIE Transactions, 36(6), 509–528. https://doi.org/10.1080/07408170490438410
- Kirkpatrick, S., Gelatt, C. D. & Vecchi, M. P. (1983). Optimization by simulated annealing. Science, 220(4598), 671–680. https://doi.org/10.1126/science.220.4598.671
- Hajek, B. (1988). Cooling schedules for optimal annealing. Mathematics of Operations Research, 13(2), 311–329. https://doi.org/10.1287/moor.13.2.311
- Landa-Silva, D. & Obit, J. H. (2008). Great deluge with non-linear decay rate for solving course timetabling problems. Proc. 4th International IEEE Conference on Intelligent Systems (IS'08), Varna, 8-11–8-18. https://doi.org/10.1109/IS.2008.4670447
- McMullan, P. (2007). An extended implementation of the great deluge algorithm for course timetabling. In Computational Science – ICCS 2007, LNCS, Springer, 538–545. https://doi.org/10.1007/978-3-540-72584-8_71
- Wolpert, D. H. & Macready, W. G. (1997). No free lunch theorems for optimization. IEEE Transactions on Evolutionary Computation, 1(1), 67–82. https://doi.org/10.1109/4235.585893
- Johnson, D. S., Aragon, C. R., McGeoch, L. A. & Schevon, C. (1989). Optimization by simulated annealing: An experimental evaluation; Part I, graph partitioning. Operations Research, 37(6), 865–892. https://doi.org/10.1287/opre.37.6.865