12. Codes

Code 12.1 random_generators.py Implementation of a pseudo-random generator due to l’Ecuyer [1] as well as utility functions to generate integers between two bounds, random permutations and random symmetric matrices

Code 12.2 tsp_utilities.py Utility functions for the traveling salesman: computation of the length of a tour when a solution is provided in the form of an array giving the order in which the cities are visited; transformation of a solution from one form to another (order, successors, predecessors); comparison of tours

Code 12.3 tsp_ LK.pyEjection chain for the TSP

Code 12.4 kd_tree_add_scan.pyCodes to define the general structure of the nodes of a KD-tree, to add an element to a KD-tree, and to inspect the whole tree. The inspection procedure just prints out the elements

Code 12.5 kd_tree_delete.pyCode for removing a node in a KD-tree

Code 12.6 kd_tree_update_pareto.pyCode for updating a Pareto set represented by a KD-tree

Code 12.7 test_tsp_2_and_3opt.pyThis code first generates a symmetric matrix with random distances and starts with a random solution. The latter is improved with a local search applying the first-move improving policy with the 2-opt neighborhood. This method is relatively rapid for instances with up to a few thousand cities. Then, all sub-paths of 100 successive cities in this solution are improved with a 3-opt neighborhood. This method runs in almost linear time, but only produces good solutions if the starting solution is adequate. The solution is then improved with a full 3-opt neighborhood. Its complexity is considerably higher; the computational time becomes significant beyond a few hundred cities. Ultimately, the solution is improved with the 2-opt neighborhood, but applying the best move policy at each iteration

Code 12.8 test_tsp_3opt_pareto.py A program for testing a local Pareto search for a TSP with a randomly generated distance matrix. For a 20-city and 3-objective instance, this program generates an approximation to the Pareto set with more than 3000 solutions. Since the implementation is highly recursive, the recursion stack and console user limits must be appropriately resized

Code 12.9 test_tsp_FANT.pyProgram to test a method inspired by artificial ant colonies

Code 12.10 test_tsp_TS.pyA taboo search test program for a TSP with a randomly generated symmetric distance matrix

Code 12.11 test_tsp_GA.pyA memetic algorithm test program for a TSP with a randomly generated symmetric distance matrix

Code 12.12 test_tsp_GRASP_PR.pyA GRASP with path relinking test program. This method uses GRASP which calls for a local search based on ejection chains, as well as other utility functions