import random from tsp import TSP random.seed(1) def hill_climb_with_k_opt(tsp, tour, k): fails_before_quit = 1000 fails = 0 sol = tour score = tsp.score(tour) while fails < fails_before_quit: new_sol = tsp.k_opt(sol, k) new_score = tsp.score(new_sol) if new_score < score: sol = new_sol score = new_score fails = 0 else: fails += 1 return sol, score tsp = TSP.from_file("tsp50.txt") best_score = None gen = 0 while True: gen += 1 sol = tsp.random_grasp_tour(0.2) sol, score = hill_climb_with_k_opt(tsp, sol, 2) if best_score is None or score < best_score: best_score = score print(f"Gen {gen} - new best score {best_score}")