<jupyter_start><jupyter_text>Basic GRASPThe pseudo code for basic GRASP algorithm is outlined below.  Note that the TSP implementation in these notes always results in feasible solutions.  Optionally GRASP may include a **repair** function used to modify infeasible solutions created during the construction phase.```pythondef basic_grasp():    best = []    do         s = greedy_construction()        s = local_search(s)        if cost(s) > cost(best):            best = s        until max_iterations or time_limit        return best```> The way I like to think about basic GRASP that it feeds the local search with a diverse set of high(ish) quality initial solutions. Imports<jupyter_code>import numpy as np
import sys
import time<jupyter_output><empty_output><jupyter_text>`metapy` imports<jupyter_code># install metapy if running in Google Colab
if 'google.colab' in sys.modules:
    !pip install meta-py
from metapy.tsp import tsp_io as io
from metapy.tsp.euclidean import gen_matrix, plot_tour

from metapy.tsp.objective import OptimisedSimpleTSPObjective

from metapy.local_search.hill_climbing import (HillClimber,
                                               TweakTwoOpt, 
                                               SimpleTweak)

from metapy.tsp.grasp import (SemiGreedyConstructor, FixedRCLSizer, 
                              RandomRCLSizer)<jupyter_output><empty_output><jupyter_text>Load problem<jupyter_code>#load file
file_path = 'https://raw.githubusercontent.com/TomMonks/meta-py/main/data/st70.tsp'

#number of rows in the file that are meta_data
md_rows = 6

#read the coordinates
cities = io.read_coordinates(file_path, md_rows)
matrix = gen_matrix(cities, as_integer=True)<jupyter_output><empty_output><jupyter_text>Implementation We will implement the algorithm in a `GRASP` class.  We will set the class up to accept the following parameters:* Logic for the semi-greedy constructor. * The local search algorithm.* Parameters that control the run duration.<jupyter_code>class GRASP:
    '''
    Greedy Randomised Adaptive Search Procedure algorithm
    for the Travelling Salesman Problem.
    
    
    The class has the following properties
    .best: float
        the best cost
        
    .best_solution: np.ndarray
        the best tour found
    
    '''
    def __init__(self, constructor, local_search, max_iter=1000,
                 time_limit=np.inf):
        '''
        Constructor
        
        Parameters:
        ---------
        constructor: object
            semi-greedy construction heuristic
            
        local_search: object
            local search heuristic e.g. `HillClimber`
            
        max_iter: int, optional (default=1000)
            The maximum number of iterations (restarts) of GRASP
            
        time_limit: float64, optional (default=np.inf)
            The maximum allowabl run time.
            
        
        '''
        # semi greedy tour construction method
        self.constructor = constructor
        
        # local search procedure
        self.local_search = local_search
        
        # max runtime budget for GRASP
        self.max_iter = max_iter
        self.time_limit = time_limit
        
        # init solution 
        self.best_solution = None
        self.best = None
    
        
    def solve(self):
        '''
        Run GRASP
        
        Returns:
        -------
        None
        '''
        
        self.best_solution = None
        self.best = -np.inf
        
        i = 0
        start = time.time()
    
        while i < self.max_iter and ((time.time() - start) < self.time_limit):
            
            i += 1
            
            # construction phase
            solution = self.constructor.build()
            
            # Improve solution via local search
            self.local_search.set_init_solution(solution)
            self.local_search.solve()
            
            current_solution = self.local_search.best_solutions[0]
            current = self.local_search.best_cost
            
            # check if better than current solution
            if current > self.best:
                self.best = current
                self.best_solution = current_solution<jupyter_output><empty_output><jupyter_text>Running Basic GRASPThe function `get_grasp` is our recipe to bring together our GRASP ingredients into a the full algorithm.<jupyter_code>def get_grasp(tour, matrix, max_iter=50, rcl_size=5, random_seed=None):
    '''
    Parameterises a basic grasp model
    
    Params:
    ------
    tour: np.array
        cities in tour as vector
        
    matrix: np.array
        matrix of costs
    
    max_iter: int, optional (default=50)
        The number of iterations (restarts) of GRASP
        
    rcl_size: int optional (default=5)
        if int then a FixedRCLSizer is used.  
        
    random_seed: int, optional (default=None)
        control the sampling of the semi-greedy constructor
        
    Returns:
    -------
    GRASP
        
    '''
    # objective function; optimised = numpy
    obj = OptimisedSimpleTSPObjective(-matrix)

    # Two-opt tweaks
    tweaker = TweakTwoOpt()

    # local search = first improvement hill climbing
    ls = HillClimber(obj, tour, tweaker)

    # semi-greedy constructor and RCL sizer
    sizer = FixedRCLSizer(r=rcl_size)
    constructor = SemiGreedyConstructor(sizer, tour, -matrix, random_seed=random_seed)

    # bring ingredients together in the GRASP framework
    solver = GRASP(constructor, ls, max_iter=max_iter)
    
    return solver
tour = np.arange(70)
solver = get_grasp(tour, matrix, max_iter=50, random_seed=101)
print("\nRunning Basic GRASP.")
solver.solve()

print("\n** GRASP OUTPUT ***")
print(f'best cost:\t{solver.best}')
print("best solutions:")
print(solver.best_solution)
fig, ax = plot_tour(solver.best_solution, cities, figsize=(12,9))<jupyter_output>Running Basic GRASP.

** GRASP OUTPUT ***
best cost:	-724.0
best solutions:
[ 0 35 22 15 46 36 57  4 52  5 40 41 17  3  1  6 31  2 43 67 42 16 59 51
  9 49 50 64 63 10 55 66 47 53 61 32 11 20 33  8 39 60 38 44 24 45 26 29
 19 13 27  7 25 48 54 18 23 14 56 65 21 62 58 37 68 30 12 69 34 28]
{'fraction_non_alphanumeric': 0.07431887796227632, 'fraction_numerical': 0.026761244559084314, 'mean_word_length': 2.2532773990561092, 'pattern_counts': {'":': 0, '<': 22, '<?xml version=': 0, '>': 23, 'https://': 1, 'lorem ipsum': 0, 'www.': 0, 'xml': 0}, 'pii_count': 0, 'substrings_counts': 0, 'word_list_counts': {'cursed_substrings.json': 4, 'profanity_word_list.json': 0, 'sexual_word_list.json': 0, 'zh_pornsignals.json': 0}}
{'chain_length': '5', 'dir': 'jupyter-structured-clean-dedup', 'id': '421610', 'license': 'MIT', 'n_tokens_mistral': 1971, 'n_tokens_neox': 1745, 'n_words': 564, 'path': 'content/03_basic_grasp.ipynb', 'repo_name': 'TomMonks/grasp_examples', 'size': '6203'}