[TSP] Assignment / Úkol
Požadavky na absolvování
Termín: neděle, 15. prosince 2024, 23.55
[EN]
Part 1
- (5 points) Experiment with the traveling salesman problem and try implementing some of the crossovers mentioned in the lecture. You can also try to change the mutation to the inverting one, or try changing the fitness function.
Part 2
- (5 points) Try to use some of the informed operators and improve your solution from the first part. You can also try some improved initialization, or other tricks to improve the solutions. Send me a comparison of your solutions from both parts.
Bonus
You can use the informed operators and any other techniques to obtain the bonus.
- [Bonus] (+3 points) On the input
tsp_std.infind a path shorter than 170 000 km (the optimum is around 158 418 km). - [Bonus] (+2 points, in addition to the above bonus) On the input
tsp_std.infind a path shorter than 160 000 km.
[CZ]
První část
- (5 bodů) Pohrajte si s problémem obchodního cestujícího a napište mi, jak to dopadlo. Implementujte některé z křížení zmiňovaných na přednášce. Můžete také zkusit změni mutaci na tu, která otáčí část jedince pozpátku, nebo změnit fitness.
Druhá část
- (5 bodů) Zkuste použít některý z "chytrých" (informovaných) operátorů a zlepšit svoje řešení. Také můžete zkusit lepší inicializaci, nebo jiné triky, které vás napadnou. Pošlete mi porovnání řešení z první a druhé části.
Bonus
Pro získání bonusu můžete používat i chytré operátory a jakékoliv další techniky.
- [Bonus] (+3 body) Najděte na vstupu
tsp_std.incestu kratší než 170 000 km (optimum je kolem 158 418 km) - [Bonus] (+2 body, možno sčítat s předchozím) Najděte na vstupu tsp_std.in cestu kratší než 160 000 km.