random_tours.py

import random

import numpy as np
from tqdm import tqdm
from typing import Tuple
from tdp import TravelingDeliverymanProblem
from numpy.typing import NDArray
from visualizer import Visualizer


def random_tours(tdp: TravelingDeliverymanProblem, max_fe: int = 10000, seed = 42, track_tried_tours: bool = False) -> Tuple[NDArray, float]:
    """
    Bruteforce using random unique valid walks.

    :param tdp: TravelingDeliverymanProblem instance
    :param max_fe: Maximum Number of Function Evaluations (full tour evaluations) done for fair comparison
    :param seed: Random seed for reproducibility
    :param track_tried_tours: Whether to track tour that have been tired, but not resulted in an improvement.
    :return: Tuple(best_tour, best_distance)
    """
    random.seed(seed)
    np.random.seed(seed)

    best_tour = None
    best_obj_val = -float('inf')
    seen_tours = set()

    # We use a for loop with tqdm for maximum readability.
    # range(max_fe) provides a clear upper bound for the progress bar.
    for _ in tqdm(range(max_fe), desc=f"Random Search ({max_fe} FE)", unit="FE"):
        if tdp.get_num_fe() >= max_fe:
            break

        tour_list = tdp.get_unique_tours(1, seen_tours=seen_tours)

        if len(tour_list) == 0:
            break # No suitable tour anymore, search space exhausted (or randomizer is not seeded properly)

        tour = tour_list[0]

        tour_tuple = tuple(tour)

        seen_tours.add(tour_tuple)

        # Also checks if tour is feasible, if not, obj value will be punished
        # Objective Function checks feasibility and adds 1 FE if the tour is unfeasible and 2 FE if is feasible
        obj_val = tdp.objective_func(tour)

        if track_tried_tours: tdp.log_tried_tour(tour)

        # 4. Update Global Best
        if obj_val > best_obj_val:
            best_obj_val = obj_val
            best_tour = np.array(tour)

    return best_tour, best_obj_val

if __name__ == "__main__":
    DATASET = "datasets/custom/kochi_small.tdp"
    problem = TravelingDeliverymanProblem(DATASET, "Random Tours (10k)")
    # Run the algorithm
    best_tour, best_obj_val = random_tours(problem)
    visualizer = Visualizer(problem)
    visualizer.show_convergence_plot()
    visualizer.save_convergence_plot()
    visualizer.show_solution_plot()
    visualizer.save_solution_plot()
    print(f"\nBest tour found: {best_tour}")
    print(f"Best fitness: {best_obj_val:.2f}")