[TSP] Assignment / Úkol
Požadavky na absolvování
Otevřené: pondělí, 27. listopadu 2023, 00.00
Termín: neděle, 7. ledna 2024, 23.55
[EN]
Part 1
- (5 points) Experiment with the traveling salesman problem and let me know, what you tried and what was the results. Implement at least one of the "non-informed" operators. You have a few possibilities.
- Try to create another crossover and compare it to the default version.
- Try to make another mutation.
- Try to change the fitness function, 1/
path length
may not be the best one (it does not matter if you use the tournament selection)
Part 2
- (5 points) Try to use some of the informed operators and improve your solution from the first part, 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.in
find 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.in
find 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. Implmentujte alespoň jeden neinformovaný operátor. Máte zase několik možností, co zkusit.
- Napište nějaký nový operátor křížení a zkuste, jestli to zlepší řešení.
- Napište nějakou jinou mutaci.
- Zkuste upravit fitness, 1/délka cesty nemusí být nejlepší (jestli používáte turnaj, tak je to jedno).
Druhá část
- (5 bodů) Zkuste použít některý z "chytrých" (informovaných) operátorů a zlepšit svoje řešení, pošlete mi ř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.in
cestu 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.