Použite simulované žíhanie s gaussovskou mutáciou so sigmou 0,1 umiestnenia vrcholov na nájdenie rozmiestnenia vrcholov kompletného grafu pre n=4 až n=10 s čo najmenším počtom prekrížení. Počiatočné umiestnenia vrcholov by mali byť v štvorci o jednotkovej hrane, ale mutácie môžu vysunúť vrcholy mimo tohto štvorca. Použite verziu bez a s pokutovou funkciou, penalizujúcou vybočenie vrcholov ďaleko od stredu štvorca. Vypočítajte priemer a smerodajnú odchýlku na počet pokusov k dosiahnutiu cieľa pre každý z grafov.
Riešenie:
Parametre algoritmu:
Energia je počet prekrížení
Teplota klesá každých 250 pokusov
Mutácia je posunutie jedného vrcholu
Pokutová funkcia: čím väčšia vzdialenosť mutovaného vrcholu od stredu štvorca tým väčšia pravdepodobnosť, že túto mutáciu nepoužíjeme.
Výsledok algoritmu:
Celá prezentácia
Zdrojový kód v Scala-e
Žiadne komentáre:
Zverejnenie komentára