Quick start (Continued)

We expand the knowledge from Quick Start where the user has learned how to Install OptFrame, and how to compile and test a Simulated Annealing metaheuristic for the classic 0-1 Knapsack Problem (01KP).

We demonstrate how to update this code for other metaheuristics, for the classic Traveling Salesman Problem (TSP).

Second example: Traveling Salesman Problem, Local Search and Random Keys Genetic Algorithm

At this point, we assume the reader is familiarized with the Traveling Salesman Problem… we intend to expand this section in the future with figures and more motivation (for now, sorry, and let’s move on).

TSP Solution definition

We define a TSP solution as a permutations of $N$ cities being visited by a Traveling Salesman. In this representation, each city is represented as a number $0..N-1$, being a solution a vector of N integers (example: [0,2,3,1] means that solution starts from city 0, then follows to city 2, then city 3, then city 1, and finally comes back to city 0). Objective is to find a route that minimizes distance between the $N$ visited cities.

We may define SolutionTSP and its objective value (double by default on API1d, or int on API1i32).

 1
 2class SolutionTSP(object):
 3    def __init__(self):
 4        # number of cities in solution
 5        self.n : int = 0
 6        # visited cities as a list
 7        self.cities : List[int] = []
 8
 9    # MUST provide some printing mechanism
10    def __str__(self):
11        return f"SolutionTSP(n={self.n};cities={self.cities})"
12

Problem Data

We read a matrix of distances between pairs of cities (considering Euclidean distance), and store in a structure named ProblemContextTSP. Note that we round the result to int, just to allow precise value calculation (but one may use float or double, and then manage the floating-point errors). Other option would be to adopt a strict int API1i32.

 1
 2class ProblemContextTSP(object):
 3    def __init__(self):
 4        # float engine for OptFrame
 5        self.engine = Engine(APILevel.API1d)
 6        # number of cities
 7        self.n = 0
 8        # x coordinates
 9        self.vx = []
10        # y coordinates
11        self.vy = []
12        # distance matrix
13        self.dist = []
14        
15   # Example: "3\n1 10 10\n2 20 20\n3 30 30\n"
16
17    def load(self, filename: str):
18        with open(filename, 'r') as f:
19            lines = f.readlines()
20            self.n = int(lines[0])
21            for i in range(self.n):
22               id_x_y = lines[i+1].split()
23               # ignore id_x_y[0]
24               self.vx.append(int(id_x_y[1]))
25               self.vy.append(int(id_x_y[2]))
26            #
27            self.dist = [[0 for col in range(self.n)] for row in range(self.n)]
28            for i in range(self.n):
29               for j in range(self.n):
30                  self.dist[i][j] = round(self.euclidean(self.vx[i], self.vy[i], self.vx[j], self.vy[j]))
31
32    def euclidean(self, x1, y1, x2, y2):
33        import math
34        return math.sqrt((x1 - x2) * (x1 - x2) + (y1 - y2) * (y1 - y2))
35
36    def __str__(self):
37        return f"ProblemContextTSP(n={self.n};vx={self.vx};vy={self.vy};dist={self.dist})"

Finally, we created a function load() to manage de input of data.

Evaluation

Objective calculation can be done by using an evaluator callback, which is compatible to OptFrame Core Evaluator (for single objectives) and GeneralEvaluator (for single and multiple objectives).

 1# continuation of ProblemContextTSP class...
 2    @staticmethod
 3    def minimize(pTSP: 'ProblemContextTSP', s: SolutionTSP) -> float:
 4        assert (s.n == pTSP.n)
 5        assert (len(s.cities) == s.n)
 6        # remember this is an API1d method
 7        f = 0.0
 8        for i in range(pTSP.n-1):
 9          f += pTSP.dist[s.cities[i]][s.cities[i + 1]];
10        f += pTSP.dist[s.cities[int(pTSP.n) - 1]][s.cities[0]];
11        return f

Search methods based on neighborhoods

The next components will depend on the type of search method used, we start with neighborhood-based search techniques.

Random constructive

In a similar manner with Knapsack example (on Quickstart part 1), we define a random solution generator.

 1# continuation of ProblemContextTSP class...
 2    @staticmethod
 3    def generateSolution(problemCtx: 'ProblemContextTSP') -> SolutionTSP:
 4        sol = SolutionTSP()
 5        for i in range(problemCtx.n):
 6            sol.cities.append(i)
 7        random.shuffle(sol.cities)
 8        sol.n = problemCtx.n
 9        return sol
10
11# optional tests...
12assert isinstance(SolutionTSP, XSolution)            # composition tests 
13assert isinstance(ProblemContextTSP,  XProblem)      # composition tests 
14assert isinstance(ProblemContextTSP,  XConstructive) # composition tests    
15assert isinstance(ProblemContextTSP,  XMinimize)     # composition tests

First move operator: Swap

We start with a Move operator capable of exchanging two elements from a given TSP solution.

 1
 2from optframe.components import Move
 3
 4class MoveSwapClass(Move):
 5    def __init__(self, _i: int = 0, _j: int = 0):
 6        self.i = _i
 7        self.j = _j
 8    def __str__(self):
 9        return "MoveSwapClass(i="+str(self.i)+";j="+str(self.j)+")"
10    def apply(self, problemCtx, sol: SolutionTSP) -> 'MoveSwapClass':
11        aux = sol.cities[self.j]
12        sol.cities[self.j] = sol.cities[self.i]
13        sol.cities[self.i] = aux
14        # must create reverse move (j,i)
15        return MoveSwapClass(self.j, self.i)
16    def canBeApplied(self, problemCtx, sol: SolutionTSP) -> bool:
17        return True
18    def eq(self, problemCtx, m2: 'MoveSwapClass') -> bool:
19        return (self.i == m2.i) and (self.j == m2.j)
20
21assert isinstance(MoveSwapClass, XMove)       # composition tests
22assert MoveSwapClass in Move.__subclasses__() # classmethod style

We have four types of neighborhood definitions in OptFrame (NS, NSFind, NSSeq and NSEnum), but two major are NS and NSSeq.

NS works well for random neighborhoods, with no intent of explicitly visiting all possible neighbors (also useful for continuous or infinite neighborhoods). Swap move and NS definition can be seen below.

 1
 2#from optframe.components import NS
 3
 4class NSSwap(object):
 5    @staticmethod
 6    def randomMove(pTSP, sol: SolutionTSP) -> MoveSwapClass:
 7        import random
 8        n = sol.n
 9        i = random.randint(0, n - 1)
10        j = i
11        while  j <= i:
12            i = random.randint(0, n - 1)
13            j = random.randint(0, n - 1)
14        # return MoveSwap(i, j)
15        return MoveSwapClass(i, j)
16    
17#assert NSSwap in NS.__subclasses__()   # optional test

We now define the NSSeq neighborhood with a explicit iterator definition, that requires four operations: first (initializes first valid move), next (skips to next valid move), current (returns current move) and isDone (indicates if no move exists).

 1
 2#from optframe.components import NSSeq
 3from optframe.components import NSIterator
 4
 5# For NSSeq, one must provide a Move Iterator
 6# A Move Iterator has five actions: Init, First, Next, IsDone and Current
 7
 8class IteratorSwap(NSIterator):
 9    def __init__(self, _i: int, _j: int):
10        self.i = _i
11        self.j = _j
12    def first(self, pTSP: ProblemContextTSP):
13        self.i = 0
14        self.j = 1
15    def next(self, pTSP: ProblemContextTSP):
16        if self.j < pTSP.n - 1:
17            self.j = self.j+1
18        else:
19            self.i = self.i + 1
20            self.j = self.i + 1
21    def isDone(self, pTSP: ProblemContextTSP):
22        return self.i >= pTSP.n - 1
23    def current(self, pTSP: ProblemContextTSP):
24        return MoveSwapClass(self.i, self.j)
25    
26assert IteratorSwap in NSIterator.__subclasses__()   # optional test
27    
28class NSSeqSwap(object):
29    @staticmethod
30    def randomMove(pTSP: ProblemContextTSP, sol: SolutionTSP) -> MoveSwapClass:
31        return NSSwap.randomMove(pTSP, sol)  # composition
32    
33    @staticmethod
34    def getIterator(pTSP: ProblemContextTSP, sol: SolutionTSP) -> IteratorSwap:
35        return IteratorSwap(-1, -1)
36
37#assert NSSeqSwap in NSSeq.__subclasses__()   # optional test

Hint

According to groundbreaking ideas from Variable Neighborhood Search community, the user should create multiple neighborhoods, with different ideas in each one, in order to better explore the solution space.

Complete Example for TSP Components

For simplicity, we separate the main TSP components in a file named TSP-fcore.py.

Hint

This example could be made in a multiple files as a package, for the separation of FCore components (on TSP-fcore.py) and the main() entrypoint depending on method used. However, we just merge them into a single file on each application, for simplicity, e.g., mainTSP-fcore-ils.py or mainTSP-fcore-brkga.py.

TSP-fcore.py

File 'TSP-fcore.py' located in 'demo/03_QuickstartTSP_VNS_BRKGA/'

  1# OptFrame Python Demo TSP - Traveling Salesman Problem
  2
  3from typing import List
  4import random
  5
  6from optframe import *
  7from optframe.protocols import *
  8
  9
 10class SolutionTSP(object):
 11    def __init__(self):
 12        # number of cities in solution
 13        self.n : int = 0
 14        # visited cities as a list
 15        self.cities : List[int] = []
 16
 17    # MUST provide some printing mechanism
 18    def __str__(self):
 19        return f"SolutionTSP(n={self.n};cities={self.cities})"
 20    
 21class ProblemContextTSP(object):
 22    def __init__(self):
 23        # float engine for OptFrame
 24        self.engine = Engine(APILevel.API1d)
 25        # number of cities
 26        self.n = 0
 27        # x coordinates
 28        self.vx = []
 29        # y coordinates
 30        self.vy = []
 31        # distance matrix
 32        self.dist = []
 33        
 34   # Example: "3\n1 10 10\n2 20 20\n3 30 30\n"
 35
 36    def load(self, filename: str):
 37        with open(filename, 'r') as f:
 38            lines = f.readlines()
 39            self.n = int(lines[0])
 40            for i in range(self.n):
 41               id_x_y = lines[i+1].split()
 42               # ignore id_x_y[0]
 43               self.vx.append(int(id_x_y[1]))
 44               self.vy.append(int(id_x_y[2]))
 45            #
 46            self.dist = [[0 for col in range(self.n)] for row in range(self.n)]
 47            for i in range(self.n):
 48               for j in range(self.n):
 49                  self.dist[i][j] = round(self.euclidean(self.vx[i], self.vy[i], self.vx[j], self.vy[j]))
 50
 51    def euclidean(self, x1, y1, x2, y2):
 52        import math
 53        return math.sqrt((x1 - x2) * (x1 - x2) + (y1 - y2) * (y1 - y2))
 54
 55    def __str__(self):
 56        return f"ProblemContextTSP(n={self.n};vx={self.vx};vy={self.vy};dist={self.dist})"
 57# continuation of ProblemContextTSP class...
 58    @staticmethod
 59    def minimize(pTSP: 'ProblemContextTSP', s: SolutionTSP) -> float:
 60        assert (s.n == pTSP.n)
 61        assert (len(s.cities) == s.n)
 62        # remember this is an API1d method
 63        f = 0.0
 64        for i in range(pTSP.n-1):
 65          f += pTSP.dist[s.cities[i]][s.cities[i + 1]];
 66        f += pTSP.dist[s.cities[int(pTSP.n) - 1]][s.cities[0]];
 67        return f
 68# continuation of ProblemContextTSP class...
 69    @staticmethod
 70    def generateSolution(problemCtx: 'ProblemContextTSP') -> SolutionTSP:
 71        sol = SolutionTSP()
 72        for i in range(problemCtx.n):
 73            sol.cities.append(i)
 74        random.shuffle(sol.cities)
 75        sol.n = problemCtx.n
 76        return sol
 77
 78# optional tests...
 79assert isinstance(SolutionTSP, XSolution)            # composition tests 
 80assert isinstance(ProblemContextTSP,  XProblem)      # composition tests 
 81assert isinstance(ProblemContextTSP,  XConstructive) # composition tests    
 82assert isinstance(ProblemContextTSP,  XMinimize)     # composition tests
 83
 84from optframe.components import Move
 85
 86class MoveSwapClass(Move):
 87    def __init__(self, _i: int = 0, _j: int = 0):
 88        self.i = _i
 89        self.j = _j
 90    def __str__(self):
 91        return "MoveSwapClass(i="+str(self.i)+";j="+str(self.j)+")"
 92    def apply(self, problemCtx, sol: SolutionTSP) -> 'MoveSwapClass':
 93        aux = sol.cities[self.j]
 94        sol.cities[self.j] = sol.cities[self.i]
 95        sol.cities[self.i] = aux
 96        # must create reverse move (j,i)
 97        return MoveSwapClass(self.j, self.i)
 98    def canBeApplied(self, problemCtx, sol: SolutionTSP) -> bool:
 99        return True
100    def eq(self, problemCtx, m2: 'MoveSwapClass') -> bool:
101        return (self.i == m2.i) and (self.j == m2.j)
102
103assert isinstance(MoveSwapClass, XMove)       # composition tests
104assert MoveSwapClass in Move.__subclasses__() # classmethod style
105
106#from optframe.components import NS
107
108class NSSwap(object):
109    @staticmethod
110    def randomMove(pTSP, sol: SolutionTSP) -> MoveSwapClass:
111        import random
112        n = sol.n
113        i = random.randint(0, n - 1)
114        j = i
115        while  j <= i:
116            i = random.randint(0, n - 1)
117            j = random.randint(0, n - 1)
118        # return MoveSwap(i, j)
119        return MoveSwapClass(i, j)
120    
121#assert NSSwap in NS.__subclasses__()   # optional test
122
123#from optframe.components import NSSeq
124from optframe.components import NSIterator
125
126# For NSSeq, one must provide a Move Iterator
127# A Move Iterator has five actions: Init, First, Next, IsDone and Current
128
129class IteratorSwap(NSIterator):
130    def __init__(self, _i: int, _j: int):
131        self.i = _i
132        self.j = _j
133    def first(self, pTSP: ProblemContextTSP):
134        self.i = 0
135        self.j = 1
136    def next(self, pTSP: ProblemContextTSP):
137        if self.j < pTSP.n - 1:
138            self.j = self.j+1
139        else:
140            self.i = self.i + 1
141            self.j = self.i + 1
142    def isDone(self, pTSP: ProblemContextTSP):
143        return self.i >= pTSP.n - 1
144    def current(self, pTSP: ProblemContextTSP):
145        return MoveSwapClass(self.i, self.j)
146    
147assert IteratorSwap in NSIterator.__subclasses__()   # optional test
148    
149class NSSeqSwap(object):
150    @staticmethod
151    def randomMove(pTSP: ProblemContextTSP, sol: SolutionTSP) -> MoveSwapClass:
152        return NSSwap.randomMove(pTSP, sol)  # composition
153    
154    @staticmethod
155    def getIterator(pTSP: ProblemContextTSP, sol: SolutionTSP) -> IteratorSwap:
156        return IteratorSwap(-1, -1)
157
158#assert NSSeqSwap in NSSeq.__subclasses__()   # optional test

Exploring with neighborhood exploration

OptFrame supports several strategies for neighborhood exploration, such as: First Improvement, Best Improvement, Random Selection and Multi Improvement. We can also combine several local search strategies in a multiple strategy called Variable Neighborhood Descent (VND).

Hint

Note that we will use OptFrame Component Builder syntax, to automatically generate a native C++ Component based on a build string. For more details, see the (TODO) Component Builder list on OptFrame C++ ReadTheDocs (TODO).

File 'mainTSP-fcore-ils-part2.py' located in 'demo/03_QuickstartTSP_VNS_BRKGA/'

 1
 2# set random seed for system
 3random.seed(0) # bad generator, just an example..
 4
 5# loads problem from filesystem
 6pTSP = ProblemContextTSP()
 7pTSP.load('tsp-example.txt')
 8print(pTSP)
 9
10# Register Basic Components
11comp_list = pTSP.engine.setup(pTSP)
12print(comp_list)
13
14# get index of new NS
15ns_idx = pTSP.engine.add_ns_class(pTSP, NSSwap)
16print("ns_idx=", ns_idx)
17
18# get index of new NSSeq
19nsseq_idx = pTSP.engine.add_nsseq_class(pTSP, NSSeqSwap)
20print("nsseq_idx=", nsseq_idx)
21
22# ========= play a little bit =========
23
24gev_idx = comp_list[0] # GeneralEvaluator
25ev_idx  = comp_list[1] # Evaluator
26print("evaluator id:", ev_idx)
27
28c_idx = comp_list[2]
29print("c_idx=", c_idx)
30
31is_idx = IdInitialSearch(0)
32print("is_idx=", is_idx)
33
34# test each component
35
36fev = pTSP.engine.get_evaluator(ev_idx)
37pTSP.engine.print_component(fev)
38
39fc = pTSP.engine.get_constructive(c_idx)
40pTSP.engine.print_component(fc)
41
42solxx = pTSP.engine.fconstructive_gensolution(fc)
43print("test solution:", solxx)
44
45z1 = pTSP.engine.fevaluator_evaluate(fev, True, solxx)
46print("test evaluation:", z1)
47
48# some basic tests with moves and iterator
49move = MoveSwapClass(0,1) # swap 0 with 1
50print("move=",move)
51m1 = NSSwap.randomMove(pTSP, solxx)
52print(m1)
53
54print("begin test with iterator")
55it = NSSeqSwap.getIterator(pTSP, solxx)
56it.first(pTSP)
57while not it.isDone(pTSP):
58    m = it.current(pTSP)
59    print(m)
60    it.next(pTSP)
61print("end test with iterator")
62
63# ======== end playing ========
64
65# pack NS into a NS list
66list_idx = pTSP.engine.create_component_list(
67    "[ OptFrame:NS 0 ]", "OptFrame:NS[]")
68print("list_idx=", list_idx)
69
70# print("Listing registered components:")
71# pTSP.engine.list_components("OptFrame:")
72
73# list the required parameters for OptFrame ComponentBuilder
74# print("engine will list builders for OptFrame: ")
75# print(pTSP.engine.list_builders("OptFrame:"))
76# print()
77
78# make next local search component silent (loglevel 0)
79pTSP.engine.experimental_set_parameter("COMPONENT_LOG_LEVEL", "0")
80
81print("building 'BI' neighborhood exploration as local search", flush=True)
82bi = BestImprovement(pTSP.engine, 0, 0)
83ls_idx = bi.get_id()
84print("ls_idx=", ls_idx, flush=True)
85
86print("creating local search list", flush=True)
87list_vnd_idx = pTSP.engine.create_component_list(
88    "[ OptFrame:LocalSearch 0 ]", "OptFrame:LocalSearch[]")
89print("list_vnd_idx=", list_vnd_idx)
90
91
92print("building 'VND' local search")
93vnd = VariableNeighborhoodDescent(pTSP.engine, 0, 0)
94vnd_idx = vnd.get_id()
95print("vnd_idx=", vnd_idx)

If one wants to build a complete metaheuristic, the Iterated Local Search (ILS) or a Variable Neighborhood Search (VNS). The ILS is based on general perturbation concept, so we will use the concept of Levels of Perturbation, that are increased when stuck in a poor quality local optimum. We adopt a perturbation strategy that tries to escape at level p by applying p+2 random moves, e.g., at level 0, 2 random moves are applied, and so on.

 1
 2
 3#####
 4#pTSP.engine.list_components("OptFrame:")
 5
 6ilsl_pert = ILSLevelPertLPlus2(pTSP.engine, 0, 0)
 7pert_idx = ilsl_pert.get_id()
 8print("pert_idx=", pert_idx)
 9
10# pTSP.engine.list_components("OptFrame:")
11
12# make next global search component info (loglevel 3)
13pTSP.engine.experimental_set_parameter("COMPONENT_LOG_LEVEL", "3")
14
15# build Iterated Local Search (ILS) Levels with iterMax=10 maxPert=5
16ilsl = ILSLevels(pTSP.engine, 0, 0, 1, 0, 10, 5)
17print("will start ILS for 3 seconds")
18lout = ilsl.search(3.0)
19print("Best solution: ",   lout.best_s)
20print("Best evaluation: ", lout.best_e)
21
22print("FINISHED")

Complete Example for ILS

We provide the main file for TSP ILS mainTSP-fcore-ils.py.

mainTSP-fcore-ils.py

File 'mainTSP-fcore-ils.py' located in 'demo/03_QuickstartTSP_VNS_BRKGA/'

  1# OptFrame Python Demo TSP - Traveling Salesman Problem
  2
  3from typing import List
  4import random
  5
  6from optframe import *
  7from optframe.protocols import *
  8
  9
 10class SolutionTSP(object):
 11    def __init__(self):
 12        # number of cities in solution
 13        self.n : int = 0
 14        # visited cities as a list
 15        self.cities : List[int] = []
 16
 17    # MUST provide some printing mechanism
 18    def __str__(self):
 19        return f"SolutionTSP(n={self.n};cities={self.cities})"
 20    
 21class ProblemContextTSP(object):
 22    def __init__(self):
 23        # float engine for OptFrame
 24        self.engine = Engine(APILevel.API1d)
 25        # number of cities
 26        self.n = 0
 27        # x coordinates
 28        self.vx = []
 29        # y coordinates
 30        self.vy = []
 31        # distance matrix
 32        self.dist = []
 33        
 34   # Example: "3\n1 10 10\n2 20 20\n3 30 30\n"
 35
 36    def load(self, filename: str):
 37        with open(filename, 'r') as f:
 38            lines = f.readlines()
 39            self.n = int(lines[0])
 40            for i in range(self.n):
 41               id_x_y = lines[i+1].split()
 42               # ignore id_x_y[0]
 43               self.vx.append(int(id_x_y[1]))
 44               self.vy.append(int(id_x_y[2]))
 45            #
 46            self.dist = [[0 for col in range(self.n)] for row in range(self.n)]
 47            for i in range(self.n):
 48               for j in range(self.n):
 49                  self.dist[i][j] = round(self.euclidean(self.vx[i], self.vy[i], self.vx[j], self.vy[j]))
 50
 51    def euclidean(self, x1, y1, x2, y2):
 52        import math
 53        return math.sqrt((x1 - x2) * (x1 - x2) + (y1 - y2) * (y1 - y2))
 54
 55    def __str__(self):
 56        return f"ProblemContextTSP(n={self.n};vx={self.vx};vy={self.vy};dist={self.dist})"
 57# continuation of ProblemContextTSP class...
 58    @staticmethod
 59    def minimize(pTSP: 'ProblemContextTSP', s: SolutionTSP) -> float:
 60        assert (s.n == pTSP.n)
 61        assert (len(s.cities) == s.n)
 62        # remember this is an API1d method
 63        f = 0.0
 64        for i in range(pTSP.n-1):
 65          f += pTSP.dist[s.cities[i]][s.cities[i + 1]];
 66        f += pTSP.dist[s.cities[int(pTSP.n) - 1]][s.cities[0]];
 67        return f
 68# continuation of ProblemContextTSP class...
 69    @staticmethod
 70    def generateSolution(problemCtx: 'ProblemContextTSP') -> SolutionTSP:
 71        sol = SolutionTSP()
 72        for i in range(problemCtx.n):
 73            sol.cities.append(i)
 74        random.shuffle(sol.cities)
 75        sol.n = problemCtx.n
 76        return sol
 77
 78# optional tests...
 79assert isinstance(SolutionTSP, XSolution)            # composition tests 
 80assert isinstance(ProblemContextTSP,  XProblem)      # composition tests 
 81assert isinstance(ProblemContextTSP,  XConstructive) # composition tests    
 82assert isinstance(ProblemContextTSP,  XMinimize)     # composition tests
 83
 84from optframe.components import Move
 85
 86class MoveSwapClass(Move):
 87    def __init__(self, _i: int = 0, _j: int = 0):
 88        self.i = _i
 89        self.j = _j
 90    def __str__(self):
 91        return "MoveSwapClass(i="+str(self.i)+";j="+str(self.j)+")"
 92    def apply(self, problemCtx, sol: SolutionTSP) -> 'MoveSwapClass':
 93        aux = sol.cities[self.j]
 94        sol.cities[self.j] = sol.cities[self.i]
 95        sol.cities[self.i] = aux
 96        # must create reverse move (j,i)
 97        return MoveSwapClass(self.j, self.i)
 98    def canBeApplied(self, problemCtx, sol: SolutionTSP) -> bool:
 99        return True
100    def eq(self, problemCtx, m2: 'MoveSwapClass') -> bool:
101        return (self.i == m2.i) and (self.j == m2.j)
102
103assert isinstance(MoveSwapClass, XMove)       # composition tests
104assert MoveSwapClass in Move.__subclasses__() # classmethod style
105
106#from optframe.components import NS
107
108class NSSwap(object):
109    @staticmethod
110    def randomMove(pTSP, sol: SolutionTSP) -> MoveSwapClass:
111        import random
112        n = sol.n
113        i = random.randint(0, n - 1)
114        j = i
115        while  j <= i:
116            i = random.randint(0, n - 1)
117            j = random.randint(0, n - 1)
118        # return MoveSwap(i, j)
119        return MoveSwapClass(i, j)
120    
121#assert NSSwap in NS.__subclasses__()   # optional test
122
123#from optframe.components import NSSeq
124from optframe.components import NSIterator
125
126# For NSSeq, one must provide a Move Iterator
127# A Move Iterator has five actions: Init, First, Next, IsDone and Current
128
129class IteratorSwap(NSIterator):
130    def __init__(self, _i: int, _j: int):
131        self.i = _i
132        self.j = _j
133    def first(self, pTSP: ProblemContextTSP):
134        self.i = 0
135        self.j = 1
136    def next(self, pTSP: ProblemContextTSP):
137        if self.j < pTSP.n - 1:
138            self.j = self.j+1
139        else:
140            self.i = self.i + 1
141            self.j = self.i + 1
142    def isDone(self, pTSP: ProblemContextTSP):
143        return self.i >= pTSP.n - 1
144    def current(self, pTSP: ProblemContextTSP):
145        return MoveSwapClass(self.i, self.j)
146    
147assert IteratorSwap in NSIterator.__subclasses__()   # optional test
148    
149class NSSeqSwap(object):
150    @staticmethod
151    def randomMove(pTSP: ProblemContextTSP, sol: SolutionTSP) -> MoveSwapClass:
152        return NSSwap.randomMove(pTSP, sol)  # composition
153    
154    @staticmethod
155    def getIterator(pTSP: ProblemContextTSP, sol: SolutionTSP) -> IteratorSwap:
156        return IteratorSwap(-1, -1)
157
158#assert NSSeqSwap in NSSeq.__subclasses__()   # optional test
159# ===========================================
160# begins main() python script for TSP ILS/VNS
161# ===========================================
162
163# import ILSLevels and BestImprovement
164from optframe.heuristics import *
165
166# set random seed for system
167random.seed(0) # bad generator, just an example..
168
169# loads problem from filesystem
170pTSP = ProblemContextTSP()
171pTSP.load('tsp-example.txt')
172print(pTSP)
173
174# Register Basic Components
175comp_list = pTSP.engine.setup(pTSP)
176print(comp_list)
177
178# get index of new NS
179ns_idx = pTSP.engine.add_ns_class(pTSP, NSSwap)
180print("ns_idx=", ns_idx)
181
182# get index of new NSSeq
183nsseq_idx = pTSP.engine.add_nsseq_class(pTSP, NSSeqSwap)
184print("nsseq_idx=", nsseq_idx)
185
186# ========= play a little bit =========
187
188gev_idx = comp_list[0] # GeneralEvaluator
189ev_idx  = comp_list[1] # Evaluator
190print("evaluator id:", ev_idx)
191
192c_idx = comp_list[2]
193print("c_idx=", c_idx)
194
195is_idx = IdInitialSearch(0)
196print("is_idx=", is_idx)
197
198# test each component
199
200fev = pTSP.engine.get_evaluator(ev_idx)
201pTSP.engine.print_component(fev)
202
203fc = pTSP.engine.get_constructive(c_idx)
204pTSP.engine.print_component(fc)
205
206solxx = pTSP.engine.fconstructive_gensolution(fc)
207print("test solution:", solxx)
208
209z1 = pTSP.engine.fevaluator_evaluate(fev, True, solxx)
210print("test evaluation:", z1)
211
212# some basic tests with moves and iterator
213move = MoveSwapClass(0,1) # swap 0 with 1
214print("move=",move)
215m1 = NSSwap.randomMove(pTSP, solxx)
216print(m1)
217
218print("begin test with iterator")
219it = NSSeqSwap.getIterator(pTSP, solxx)
220it.first(pTSP)
221while not it.isDone(pTSP):
222    m = it.current(pTSP)
223    print(m)
224    it.next(pTSP)
225print("end test with iterator")
226
227# ======== end playing ========
228
229# pack NS into a NS list
230list_idx = pTSP.engine.create_component_list(
231    "[ OptFrame:NS 0 ]", "OptFrame:NS[]")
232print("list_idx=", list_idx)
233
234# print("Listing registered components:")
235# pTSP.engine.list_components("OptFrame:")
236
237# list the required parameters for OptFrame ComponentBuilder
238# print("engine will list builders for OptFrame: ")
239# print(pTSP.engine.list_builders("OptFrame:"))
240# print()
241
242# make next local search component silent (loglevel 0)
243pTSP.engine.experimental_set_parameter("COMPONENT_LOG_LEVEL", "0")
244
245print("building 'BI' neighborhood exploration as local search", flush=True)
246bi = BestImprovement(pTSP.engine, 0, 0)
247ls_idx = bi.get_id()
248print("ls_idx=", ls_idx, flush=True)
249
250print("creating local search list", flush=True)
251list_vnd_idx = pTSP.engine.create_component_list(
252    "[ OptFrame:LocalSearch 0 ]", "OptFrame:LocalSearch[]")
253print("list_vnd_idx=", list_vnd_idx)
254
255
256print("building 'VND' local search")
257vnd = VariableNeighborhoodDescent(pTSP.engine, 0, 0)
258vnd_idx = vnd.get_id()
259print("vnd_idx=", vnd_idx)
260
261
262#####
263#pTSP.engine.list_components("OptFrame:")
264
265ilsl_pert = ILSLevelPertLPlus2(pTSP.engine, 0, 0)
266pert_idx = ilsl_pert.get_id()
267print("pert_idx=", pert_idx)
268
269# pTSP.engine.list_components("OptFrame:")
270
271# make next global search component info (loglevel 3)
272pTSP.engine.experimental_set_parameter("COMPONENT_LOG_LEVEL", "3")
273
274# build Iterated Local Search (ILS) Levels with iterMax=10 maxPert=5
275ilsl = ILSLevels(pTSP.engine, 0, 0, 1, 0, 10, 5)
276print("will start ILS for 3 seconds")
277lout = ilsl.search(3.0)
278print("Best solution: ",   lout.best_s)
279print("Best evaluation: ", lout.best_e)
280
281print("FINISHED")

To run it:

python3 mainTSP-fcore-ils.py

Search methods based on random keys

We finish with the Biased Random Key Genetic Algorithm (BRKGA), a simple metaheuristic inspired by classic Genetic Algorithm, using the solution representation of $n$ Random Keys, which are $[0,1]^n$ float values.

Random key generation

The BRKGA requires an initial solution generator, which is in this case, $n$ random [0,1] floats. This can be done automatically by the method (since its trivial do generate $n$ [0,1] random numbers), but we choose to demonstrate manually (by inheriting from OptFrame Core class Initial Population).

This is good to tune the degree of randomness (number of random digits) and also the random function used.

 1
 2from optframe.protocols import XConstructiveRK
 3from optframe.core import LibArrayDouble
 4
 5#
 6# random constructive: updates parameter ptr_array_double of type (LibArrayDouble*)
 7#
 8class RKConstructiveTSP(object):
 9    @staticmethod
10    def generateRK(problemCtx: ProblemContextTSP, ptr_array_double : LibArrayDouble) -> int:
11        rkeys = []
12        for i in range(problemCtx.n):
13            key = random.random() # [0,1] uniform
14            rkeys.append(key)
15        #
16        ptr_array_double.contents.size = len(rkeys)
17        ptr_array_double.contents.v = engine.callback_adapter_list_to_vecdouble(rkeys)
18        return len(rkeys)
19

BRKGA decoding

BRKGA also requires a decoder function, that maps this array of random keys into a permutation.

This can be easily done with Functional Core class FDecodeRK, and an interesting approach based on sorting the keys, related to a predefined indexing of each key.

 1
 2from optframe.core import LibArrayDouble
 3from typing import Tuple
 4
 5import ctypes
 6
 7#
 8# decoder function: receives a problem instance and an array of random keys (as LibArrayDouble)
 9#
10
11class DecoderTSP(object):
12    @staticmethod
13    def decodeSolution(pTSP: ProblemContextTSP, array_double : LibArrayDouble) -> SolutionTSP:
14        #
15        sol = SolutionTSP()
16        #
17        lpairs = []
18        for i in range(array_double.size):
19            p = [array_double.v[i], i]
20            lpairs.append(p)
21        #
22        #print("lpairs: ", lpairs)
23        sorted_list = sorted(lpairs)
24        #print("sorted_list: ", sorted_list)
25        #
26        sol.n = pTSP.n
27        sol.cities = []
28        for i in range(array_double.size):
29            sol.cities.append(sorted_list[i][1]) # append index of city in order
30        return sol
31
32    @staticmethod
33    def decodeMinimize(pTSP: ProblemContextTSP, array_double : LibArrayDouble, needsSolution: bool) -> Tuple[SolutionTSP|None, float]:
34        #
35        # print("decodeMinimize! needsSolution="+str(needsSolution), flush=True)
36        sol = DecoderTSP.decodeSolution(pTSP, array_double)
37        #
38        # NOW WILL GET EVALUATION VALUE
39        e = ProblemContextTSP.minimize(pTSP, sol)
40        # FINALLY, WILL RETURN WHAT IS REQUIRED
41        if not needsSolution:
42            return (None, e)
43        else:
44            return (sol, e)
45
46

BRKGA with TSP

We are ready to build a TSP instance with 3 cities with coordinates (10,10), (20,20) and (30,30), and invoke a BRKGA to solve it.

The parameters of BRKGA are: decoding function, initial solution generator, population size, number of iterations, also rates for mutation (randomness), elite (best solutions), preference for elite solutions, and finally, a random generation method.

 1
 2
 3# set random seed for system
 4random.seed(0) # bad generator, just an example..
 5
 6# loads problem from filesystem
 7pTSP = ProblemContextTSP()
 8pTSP.load('tsp-example.txt')
 9
10print("problem=",pTSP)
11
12import optframe
13print(str(optframe.__version__))
14pTSP.engine.welcome()
15
16
17# Register Basic Components
18comp_list = pTSP.engine.setup(pTSP)
19print(comp_list)
20#
21ev_idx = comp_list[1]
22print("evaluator id:", ev_idx)
23
24c_rk_idx = pTSP.engine.add_constructive_rk_class(pTSP, RKConstructiveTSP)
25print("c_rk_idx=", c_rk_idx)
26
27print("")
28dec_rk_idx = pTSP.engine.add_decoder_rk_class(pTSP, DecoderTSP)
29print("dec_rk_idx=", dec_rk_idx)
30
31print("")
32print("WILL CREATE DecoderRandomKeys directly with simultaneous evaluation and optional solution!")
33drk_rk_id = pTSP.engine.add_edecoder_op_rk_class(pTSP, DecoderTSP)
34print("drk_rk_id=", drk_rk_id)
35
36pTSP.engine.list_components("OptFrame:")
37
38#print("")
39#print("WILL CREATE DecoderRandomKeys FROM DecoderRandomKeysNoEvaluation!")
40#drk = DecoderRandomKeys(pTSP.engine, ev_idx, dec_rk_idx)
41#drk_rk_id = drk.get_id()
42#print("drk_rk_id=", drk_rk_id)
43
44# =======================
45# pTSP.engine.experimental_set_parameter("ENGINE_LOG_LEVEL", "4")
46print("")
47print("will start BRKGA for 3 seconds")
48brkga = BRKGA(pTSP.engine, drk_rk_id, c_rk_idx, 30, 1000, 0.4, 0.3, 0.6)
49
50pTSP.engine.list_components("OptFrame:")
51
52lout = brkga.search(3.0)
53print("Best solution: ",   lout.best_s)
54print("Best evaluation: ", lout.best_e)
55

The result from searchOut can be split in two parts, an error code and the returned solution (the same as in Simulated Annealing or any other OptFrame search method).

Complete Example for BRKGA

We provide the main file for TSP BRKGA mainTSP-fcore-brkga.py.

mainTSP-fcore-brkga.cpp

File 'mainTSP-fcore-brkga.py' located in 'demo/03_QuickstartTSP_VNS_BRKGA/'

  1# OptFrame Python Demo TSP - Traveling Salesman Problem
  2
  3from typing import List
  4import random
  5
  6from optframe import *
  7from optframe.protocols import *
  8
  9
 10class SolutionTSP(object):
 11    def __init__(self):
 12        # number of cities in solution
 13        self.n : int = 0
 14        # visited cities as a list
 15        self.cities : List[int] = []
 16
 17    # MUST provide some printing mechanism
 18    def __str__(self):
 19        return f"SolutionTSP(n={self.n};cities={self.cities})"
 20    
 21class ProblemContextTSP(object):
 22    def __init__(self):
 23        # float engine for OptFrame
 24        self.engine = Engine(APILevel.API1d)
 25        # number of cities
 26        self.n = 0
 27        # x coordinates
 28        self.vx = []
 29        # y coordinates
 30        self.vy = []
 31        # distance matrix
 32        self.dist = []
 33        
 34   # Example: "3\n1 10 10\n2 20 20\n3 30 30\n"
 35
 36    def load(self, filename: str):
 37        with open(filename, 'r') as f:
 38            lines = f.readlines()
 39            self.n = int(lines[0])
 40            for i in range(self.n):
 41               id_x_y = lines[i+1].split()
 42               # ignore id_x_y[0]
 43               self.vx.append(int(id_x_y[1]))
 44               self.vy.append(int(id_x_y[2]))
 45            #
 46            self.dist = [[0 for col in range(self.n)] for row in range(self.n)]
 47            for i in range(self.n):
 48               for j in range(self.n):
 49                  self.dist[i][j] = round(self.euclidean(self.vx[i], self.vy[i], self.vx[j], self.vy[j]))
 50
 51    def euclidean(self, x1, y1, x2, y2):
 52        import math
 53        return math.sqrt((x1 - x2) * (x1 - x2) + (y1 - y2) * (y1 - y2))
 54
 55    def __str__(self):
 56        return f"ProblemContextTSP(n={self.n};vx={self.vx};vy={self.vy};dist={self.dist})"
 57# continuation of ProblemContextTSP class...
 58    @staticmethod
 59    def minimize(pTSP: 'ProblemContextTSP', s: SolutionTSP) -> float:
 60        assert (s.n == pTSP.n)
 61        assert (len(s.cities) == s.n)
 62        # remember this is an API1d method
 63        f = 0.0
 64        for i in range(pTSP.n-1):
 65          f += pTSP.dist[s.cities[i]][s.cities[i + 1]];
 66        f += pTSP.dist[s.cities[int(pTSP.n) - 1]][s.cities[0]];
 67        return f
 68# continuation of ProblemContextTSP class...
 69    @staticmethod
 70    def generateSolution(problemCtx: 'ProblemContextTSP') -> SolutionTSP:
 71        sol = SolutionTSP()
 72        for i in range(problemCtx.n):
 73            sol.cities.append(i)
 74        random.shuffle(sol.cities)
 75        sol.n = problemCtx.n
 76        return sol
 77
 78# optional tests...
 79assert isinstance(SolutionTSP, XSolution)            # composition tests 
 80assert isinstance(ProblemContextTSP,  XProblem)      # composition tests 
 81assert isinstance(ProblemContextTSP,  XConstructive) # composition tests    
 82assert isinstance(ProblemContextTSP,  XMinimize)     # composition tests
 83
 84from optframe.components import Move
 85
 86class MoveSwapClass(Move):
 87    def __init__(self, _i: int = 0, _j: int = 0):
 88        self.i = _i
 89        self.j = _j
 90    def __str__(self):
 91        return "MoveSwapClass(i="+str(self.i)+";j="+str(self.j)+")"
 92    def apply(self, problemCtx, sol: SolutionTSP) -> 'MoveSwapClass':
 93        aux = sol.cities[self.j]
 94        sol.cities[self.j] = sol.cities[self.i]
 95        sol.cities[self.i] = aux
 96        # must create reverse move (j,i)
 97        return MoveSwapClass(self.j, self.i)
 98    def canBeApplied(self, problemCtx, sol: SolutionTSP) -> bool:
 99        return True
100    def eq(self, problemCtx, m2: 'MoveSwapClass') -> bool:
101        return (self.i == m2.i) and (self.j == m2.j)
102
103assert isinstance(MoveSwapClass, XMove)       # composition tests
104assert MoveSwapClass in Move.__subclasses__() # classmethod style
105
106#from optframe.components import NS
107
108class NSSwap(object):
109    @staticmethod
110    def randomMove(pTSP, sol: SolutionTSP) -> MoveSwapClass:
111        import random
112        n = sol.n
113        i = random.randint(0, n - 1)
114        j = i
115        while  j <= i:
116            i = random.randint(0, n - 1)
117            j = random.randint(0, n - 1)
118        # return MoveSwap(i, j)
119        return MoveSwapClass(i, j)
120    
121#assert NSSwap in NS.__subclasses__()   # optional test
122
123#from optframe.components import NSSeq
124from optframe.components import NSIterator
125
126# For NSSeq, one must provide a Move Iterator
127# A Move Iterator has five actions: Init, First, Next, IsDone and Current
128
129class IteratorSwap(NSIterator):
130    def __init__(self, _i: int, _j: int):
131        self.i = _i
132        self.j = _j
133    def first(self, pTSP: ProblemContextTSP):
134        self.i = 0
135        self.j = 1
136    def next(self, pTSP: ProblemContextTSP):
137        if self.j < pTSP.n - 1:
138            self.j = self.j+1
139        else:
140            self.i = self.i + 1
141            self.j = self.i + 1
142    def isDone(self, pTSP: ProblemContextTSP):
143        return self.i >= pTSP.n - 1
144    def current(self, pTSP: ProblemContextTSP):
145        return MoveSwapClass(self.i, self.j)
146    
147assert IteratorSwap in NSIterator.__subclasses__()   # optional test
148    
149class NSSeqSwap(object):
150    @staticmethod
151    def randomMove(pTSP: ProblemContextTSP, sol: SolutionTSP) -> MoveSwapClass:
152        return NSSwap.randomMove(pTSP, sol)  # composition
153    
154    @staticmethod
155    def getIterator(pTSP: ProblemContextTSP, sol: SolutionTSP) -> IteratorSwap:
156        return IteratorSwap(-1, -1)
157
158#assert NSSeqSwap in NSSeq.__subclasses__()   # optional test
159# =========================================
160# begins main() python script for TSP BRKGA
161# =========================================
162from optframe.heuristics import *
163
164from optframe.protocols import XConstructiveRK
165from optframe.core import LibArrayDouble
166
167#
168# random constructive: updates parameter ptr_array_double of type (LibArrayDouble*)
169#
170class RKConstructiveTSP(object):
171    @staticmethod
172    def generateRK(problemCtx: ProblemContextTSP, ptr_array_double : LibArrayDouble) -> int:
173        rkeys = []
174        for i in range(problemCtx.n):
175            key = random.random() # [0,1] uniform
176            rkeys.append(key)
177        #
178        ptr_array_double.contents.size = len(rkeys)
179        ptr_array_double.contents.v = engine.callback_adapter_list_to_vecdouble(rkeys)
180        return len(rkeys)
181
182
183from optframe.core import LibArrayDouble
184from typing import Tuple
185
186import ctypes
187
188#
189# decoder function: receives a problem instance and an array of random keys (as LibArrayDouble)
190#
191
192class DecoderTSP(object):
193    @staticmethod
194    def decodeSolution(pTSP: ProblemContextTSP, array_double : LibArrayDouble) -> SolutionTSP:
195        #
196        sol = SolutionTSP()
197        #
198        lpairs = []
199        for i in range(array_double.size):
200            p = [array_double.v[i], i]
201            lpairs.append(p)
202        #
203        #print("lpairs: ", lpairs)
204        sorted_list = sorted(lpairs)
205        #print("sorted_list: ", sorted_list)
206        #
207        sol.n = pTSP.n
208        sol.cities = []
209        for i in range(array_double.size):
210            sol.cities.append(sorted_list[i][1]) # append index of city in order
211        return sol
212
213    @staticmethod
214    def decodeMinimize(pTSP: ProblemContextTSP, array_double : LibArrayDouble, needsSolution: bool) -> Tuple[SolutionTSP|None, float]:
215        #
216        # print("decodeMinimize! needsSolution="+str(needsSolution), flush=True)
217        sol = DecoderTSP.decodeSolution(pTSP, array_double)
218        #
219        # NOW WILL GET EVALUATION VALUE
220        e = ProblemContextTSP.minimize(pTSP, sol)
221        # FINALLY, WILL RETURN WHAT IS REQUIRED
222        if not needsSolution:
223            return (None, e)
224        else:
225            return (sol, e)
226
227
228
229
230# set random seed for system
231random.seed(0) # bad generator, just an example..
232
233# loads problem from filesystem
234pTSP = ProblemContextTSP()
235pTSP.load('tsp-example.txt')
236
237print("problem=",pTSP)
238
239import optframe
240print(str(optframe.__version__))
241pTSP.engine.welcome()
242
243
244# Register Basic Components
245comp_list = pTSP.engine.setup(pTSP)
246print(comp_list)
247#
248ev_idx = comp_list[1]
249print("evaluator id:", ev_idx)
250
251c_rk_idx = pTSP.engine.add_constructive_rk_class(pTSP, RKConstructiveTSP)
252print("c_rk_idx=", c_rk_idx)
253
254print("")
255dec_rk_idx = pTSP.engine.add_decoder_rk_class(pTSP, DecoderTSP)
256print("dec_rk_idx=", dec_rk_idx)
257
258print("")
259print("WILL CREATE DecoderRandomKeys directly with simultaneous evaluation and optional solution!")
260drk_rk_id = pTSP.engine.add_edecoder_op_rk_class(pTSP, DecoderTSP)
261print("drk_rk_id=", drk_rk_id)
262
263pTSP.engine.list_components("OptFrame:")
264
265#print("")
266#print("WILL CREATE DecoderRandomKeys FROM DecoderRandomKeysNoEvaluation!")
267#drk = DecoderRandomKeys(pTSP.engine, ev_idx, dec_rk_idx)
268#drk_rk_id = drk.get_id()
269#print("drk_rk_id=", drk_rk_id)
270
271# =======================
272# pTSP.engine.experimental_set_parameter("ENGINE_LOG_LEVEL", "4")
273print("")
274print("will start BRKGA for 3 seconds")
275brkga = BRKGA(pTSP.engine, drk_rk_id, c_rk_idx, 30, 1000, 0.4, 0.3, 0.6)
276
277pTSP.engine.list_components("OptFrame:")
278
279lout = brkga.search(3.0)
280print("Best solution: ",   lout.best_s)
281print("Best evaluation: ", lout.best_e)
282

To run it:

python3 mainTSP-fcore-brkga.py

More Examples

For a other examples, see folder Examples/FCore-BRKGA on OptFrame C++ project.

Warning

Feel free to check folder OptFrame/Examples for other examples on FCore and OptFrame C++.