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 ESolutionTSP as a pair, containing a solution and its objective value (double).
1#pragma once
2
3// C++
4#include <algorithm>
5#include <functional>
6#include <iostream>
7#include <vector>
8//
9#include <OptFCore/FCore.hpp>
10#include <OptFrame/Core.hpp>
11#include <OptFrame/Heuristics/Heuristics.hpp> // many metaheuristics here...
12#include <OptFrame/Scanner++/Scanner.hpp>
13#include <OptFrame/Util/Matrix.hpp>
14#include <OptFrame/printable/printable.hpp>
15
16using namespace std; // NOLINT
17using namespace optframe; // NOLINT
18using namespace scannerpp; // NOLINT
19
20// define TSP solution type as 'vector<int>', using 'double' as evaluation type
21using ESolutionTSP =
22 std::pair<std::vector<int>, // first part of search space element: solution
23 // (representation)
24 Evaluation<int> // second part of search space element:
25 // evaluation (objective value)
26 >;
Problem Data
We read a matrix of distances between pairs of cities (considering Euclidean distance), and store in a structure named ProblemContext. 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). Do not forget to #include helpers from optframe namespace, such as Matrix and Scanner.
1// TSP problem context and data reads
2class ProblemContext {
3 public:
4 int n{0}; // number of clients
5 Matrix<int> dist; // distance matrix (Euclidean)
6 // load data from Scanner
7 void load(Scanner& scanner) {
8 n = *scanner.nextInt(); // reads number of clients
9 dist = Matrix<int>(n, n); // initializes n x n matrix
10 //
11 vector<double> xvalues(n);
12 vector<double> yvalues(n);
13 //
14 for (int i = 0; i < n; i++) {
15 scanner.next();
16 xvalues[i] = *scanner.nextDouble(); // reads x
17 yvalues[i] = *scanner.nextDouble(); // reads y
18 }
19 // calculate distance values, for every client pair (i,j)
20 for (int i = 0; i < n; i++)
21 for (int j = 0; j < n; j++)
22 dist(i, j) = (int)::round(distance(xvalues.at(i), yvalues.at(i),
23 xvalues.at(j), yvalues.at(j)));
24 }
25 // euclidean distance (double as return)
26 double distance(double x1, double y1, double x2, double y2) {
27 return sqrt((x1 - x2) * (x1 - x2) + (y1 - y2) * (y1 - y2));
28 }
29};
30// Create TSP Problem Context
31// ProblemContext pTSP;
Finally, we declare a global object ProblemContext pTSP (for simplicity), that includes all data.
Evaluation
Objective calculation can be done by using Functional Core class FEvaluator, which is a huge simplification from OptFrame Core components Evaluator (for single objectives) and GeneralEvaluator (for single and multiple objectives).
1Evaluation<int> fevaluate(sref<ProblemContext> pTSP,
2 const std::vector<int>& s) {
3 int f = 0;
4 for (int i = 0; i < int(pTSP->n) - 1; i++) f += pTSP->dist(s[i], s[i + 1]);
5 f += pTSP->dist(s[int(pTSP->n) - 1], s[0]);
6 return Evaluation<int>{f};
7}
8
9// Evaluate
10// FEvaluator<ESolutionTSP, MinOrMax::MINIMIZE> eval{fevaluate};
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.
1std::vector<int> frandom(sref<ProblemContext> pTSP) {
2 vector<int> v(pTSP->n, -1); // get information from context
3 for (int i = 0; i < (int)v.size(); i++) v[i] = i;
4 std::random_shuffle(v.begin(), v.end());
5 return v;
6}
7
8// Generate random solution
9// FConstructive<std::vector<int>, ProblemContext> crand{frandom};
First move operator: Swap
We start with a Move operator capable of exchanging two elements from a given TSP solution.
1std::pair<int, int> fApplySwap(sref<ProblemContext>,
2 const std::pair<int, int>& moveData,
3 ESolutionTSP& se) {
4 int i = moveData.first;
5 int j = moveData.second;
6 // perform swap of clients i and j
7 int aux = se.first[j];
8 se.first[j] = se.first[i];
9 se.first[i] = aux;
10 return std::pair<int, int>(j, i); // return a reverse move ('undo' move)s
11}
12
13// Swap move
14using MoveSwap = FMoveP<std::pair<int, int>, ESolutionTSP, ProblemContext>;
15
16uptr<Move<ESolutionTSP>> makeMoveSwap(sref<ProblemContext> p, int i, int j) {
17 return uptr<Move<ESolutionTSP>>(new MoveSwap{p, make_pair(i, j), fApplySwap});
18}
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.
1uptr<Move<ESolutionTSP>> fRandomSwap(sref<ProblemContext> pTSP,
2 const ESolutionTSP& se) {
3 int i = rand() % pTSP->n;
4 int j = i;
5 while (j <= i) {
6 i = rand() % pTSP->n;
7 j = rand() % pTSP->n;
8 }
9 return uptr<Move<ESolutionTSP>>(makeMoveSwap(pTSP, i, j));
10}
11
12// Swap move (NS)
13// FNS<ESolutionTSP> nsswap{fRandomSwap};
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).
1auto make_nsseq(sref<ProblemContext> p) {
2 sref<FNSSeq<std::pair<int, int>, ESolutionTSP, ProblemContext>> nsseq2{
3 new FNSSeq<std::pair<int, int>, ESolutionTSP, ProblemContext>{
4 p,
5 [](sref<ProblemContext> pTSP,
6 const ESolutionTSP& se) -> uptr<Move<ESolutionTSP>> {
7 int i = rand() % pTSP->n;
8 int j = i;
9 while (j <= i) {
10 i = rand() % pTSP->n;
11 j = rand() % pTSP->n;
12 }
13 return uptr<Move<ESolutionTSP>>(makeMoveSwap(pTSP, i, j));
14 },
15 // iterator initialization (fGenerator)
16 [](sref<ProblemContext> pTSP, const ESolutionTSP& se)
17 -> std::pair<int, int> { return make_pair(-1, -1); },
18 [](sref<ProblemContext> pTSP, std::pair<int, int>& p) -> void {
19 // void (*fFirst)(IMS&), // iterator.first()
20 p.first = 0;
21 p.second = 1;
22 },
23 [](sref<ProblemContext> pTSP, std::pair<int, int>& p) -> void {
24 // void (*fNext)(IMS&), // iterator.next()
25 if (p.second < (pTSP->n - 1))
26 p.second++;
27 else {
28 p.first++;
29 p.second = p.first + 1;
30 }
31 },
32 [](sref<ProblemContext> pTSP, std::pair<int, int>& p) -> bool {
33 // bool (*fIsDone)(IMS&), //
34 // iterator.isDone()
35 return p.first >= pTSP->n - 1;
36 },
37 [](sref<ProblemContext> pTSP,
38 std::pair<int, int>& p) -> uptr<Move<ESolutionTSP>> {
39 // uptr<Move<XES>> (*fCurrent)(IMS&) //
40 // iterator.current()
41 return uptr<Move<ESolutionTSP>>(
42 makeMoveSwap(pTSP, p.first, p.second));
43 } // FNSSeq
44 }};
45 return nsseq2;
46}
47
48class OptFrameDemoTSP {
49 public:
50 sref<ProblemContext> pTSP;
51 sref<FConstructive<std::vector<int>, ProblemContext>> randomConstructive;
52 sref<FEvaluator<ESolutionTSP, MINIMIZE, ProblemContext>> eval;
53 sref<FNS<ESolutionTSP, ProblemContext>> nsSwap;
54 sref<FNSSeq<std::pair<int, int>, ESolutionTSP, ProblemContext>> nsseqSwap;
55 sptr<DecoderRandomKeys<ESolutionTSP, double>> decoder;
56
57 explicit OptFrameDemoTSP(sref<ProblemContext> p)
58 : pTSP{p},
59 randomConstructive{
60 new FConstructive<std::vector<int>, ProblemContext>{p, frandom}},
61 eval{new FEvaluator<ESolutionTSP, MINIMIZE, ProblemContext>{p,
62 fevaluate}},
63 nsSwap{new FNS<ESolutionTSP, ProblemContext>{p, fRandomSwap}},
64 nsseqSwap{make_nsseq(p)}
65
66 {}
67};
68
69//
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.
At this point, we quickly demonstrate how novel C++20 features, such as Coroutines, have improved OptFrame in latest versions (named FxCore library). We note that all four iterator operations (first, next, current and isDone) are made available quite naturally with a single coroutine generator that executes co_yield for each available move.
1// THIS IS ONLY AVAILABLE WITH OptFrame FxCore and C++20 -fcoroutines
2// Swap move (NSSeq) - with "Fancy" iterator (coroutines)
3using NSSeqSwapFancy = FxNSSeqFancy<
4 ESolutionTSP,
5 [](const ESolutionTSP& se) -> uptr<Move<ESolutionTSP>> {
6 int i = rand() % pTSP.n;
7 int j = i;
8 while (j <= i) {
9 i = rand() % pTSP.n;
10 j = rand() % pTSP.n;
11 }
12 return uptr<Move<ESolutionTSP>>(new MoveSwap{ make_pair(i, j) });
13 },
14 [](const ESolutionTSP& se) -> Generator<Move<ESolutionTSP>*> {
15 for (int i = 0; i < int(pTSP.n) - 1; i++)
16 for (int j = i + 1; j < pTSP.n; j++)
17 co_yield new MoveSwap{ make_pair(i, j) }; // implicit unique_ptr requirements
18 }>;
We will explore more of these bleeding-edge tools in an advanced topic.
Complete Example for TSP Components
For simplicity, we separate the main TSP components in a file named TSP-fcore.hpp.
Hint
This example could be made in a single file, to be even simpler. However, we recommend users to have
a clear separation for the header declaration of FCore components (on TSP-fcore.hpp)
from the main() entrypoint depending on method used, e.g., mainTSP-fcore-ils.cpp or mainTSP-fcore-brkga.cpp.
TSP-fcore.hpp
File 'TSP-fcore.hpp' located in 'demo/03_QuickstartTSP_VNS_BRKGA/'
1#pragma once
2
3// C++
4#include <algorithm>
5#include <functional>
6#include <iostream>
7#include <vector>
8//
9#include <OptFCore/FCore.hpp>
10#include <OptFrame/Core.hpp>
11#include <OptFrame/Heuristics/Heuristics.hpp> // many metaheuristics here...
12#include <OptFrame/Scanner++/Scanner.hpp>
13#include <OptFrame/Util/Matrix.hpp>
14#include <OptFrame/printable/printable.hpp>
15
16using namespace std; // NOLINT
17using namespace optframe; // NOLINT
18using namespace scannerpp; // NOLINT
19
20// define TSP solution type as 'vector<int>', using 'double' as evaluation type
21using ESolutionTSP =
22 std::pair<std::vector<int>, // first part of search space element: solution
23 // (representation)
24 Evaluation<int> // second part of search space element:
25 // evaluation (objective value)
26 >;
27
28// TSP problem context and data reads
29class ProblemContext {
30 public:
31 int n{0}; // number of clients
32 Matrix<int> dist; // distance matrix (Euclidean)
33 // load data from Scanner
34 void load(Scanner& scanner) {
35 n = *scanner.nextInt(); // reads number of clients
36 dist = Matrix<int>(n, n); // initializes n x n matrix
37 //
38 vector<double> xvalues(n);
39 vector<double> yvalues(n);
40 //
41 for (int i = 0; i < n; i++) {
42 scanner.next();
43 xvalues[i] = *scanner.nextDouble(); // reads x
44 yvalues[i] = *scanner.nextDouble(); // reads y
45 }
46 // calculate distance values, for every client pair (i,j)
47 for (int i = 0; i < n; i++)
48 for (int j = 0; j < n; j++)
49 dist(i, j) = (int)::round(distance(xvalues.at(i), yvalues.at(i),
50 xvalues.at(j), yvalues.at(j)));
51 }
52 // euclidean distance (double as return)
53 double distance(double x1, double y1, double x2, double y2) {
54 return sqrt((x1 - x2) * (x1 - x2) + (y1 - y2) * (y1 - y2));
55 }
56};
57// Create TSP Problem Context
58// ProblemContext pTSP;
59
60Evaluation<int> fevaluate(sref<ProblemContext> pTSP,
61 const std::vector<int>& s) {
62 int f = 0;
63 for (int i = 0; i < int(pTSP->n) - 1; i++) f += pTSP->dist(s[i], s[i + 1]);
64 f += pTSP->dist(s[int(pTSP->n) - 1], s[0]);
65 return Evaluation<int>{f};
66}
67
68// Evaluate
69// FEvaluator<ESolutionTSP, MinOrMax::MINIMIZE> eval{fevaluate};
70std::vector<int> frandom(sref<ProblemContext> pTSP) {
71 vector<int> v(pTSP->n, -1); // get information from context
72 for (int i = 0; i < (int)v.size(); i++) v[i] = i;
73 std::random_shuffle(v.begin(), v.end());
74 return v;
75}
76
77// Generate random solution
78// FConstructive<std::vector<int>, ProblemContext> crand{frandom};
79
80std::pair<int, int> fApplySwap(sref<ProblemContext>,
81 const std::pair<int, int>& moveData,
82 ESolutionTSP& se) {
83 int i = moveData.first;
84 int j = moveData.second;
85 // perform swap of clients i and j
86 int aux = se.first[j];
87 se.first[j] = se.first[i];
88 se.first[i] = aux;
89 return std::pair<int, int>(j, i); // return a reverse move ('undo' move)s
90}
91
92// Swap move
93using MoveSwap = FMoveP<std::pair<int, int>, ESolutionTSP, ProblemContext>;
94
95uptr<Move<ESolutionTSP>> makeMoveSwap(sref<ProblemContext> p, int i, int j) {
96 return uptr<Move<ESolutionTSP>>(new MoveSwap{p, make_pair(i, j), fApplySwap});
97}
98uptr<Move<ESolutionTSP>> fRandomSwap(sref<ProblemContext> pTSP,
99 const ESolutionTSP& se) {
100 int i = rand() % pTSP->n;
101 int j = i;
102 while (j <= i) {
103 i = rand() % pTSP->n;
104 j = rand() % pTSP->n;
105 }
106 return uptr<Move<ESolutionTSP>>(makeMoveSwap(pTSP, i, j));
107}
108
109// Swap move (NS)
110// FNS<ESolutionTSP> nsswap{fRandomSwap};
111
112auto make_nsseq(sref<ProblemContext> p) {
113 sref<FNSSeq<std::pair<int, int>, ESolutionTSP, ProblemContext>> nsseq2{
114 new FNSSeq<std::pair<int, int>, ESolutionTSP, ProblemContext>{
115 p,
116 [](sref<ProblemContext> pTSP,
117 const ESolutionTSP& se) -> uptr<Move<ESolutionTSP>> {
118 int i = rand() % pTSP->n;
119 int j = i;
120 while (j <= i) {
121 i = rand() % pTSP->n;
122 j = rand() % pTSP->n;
123 }
124 return uptr<Move<ESolutionTSP>>(makeMoveSwap(pTSP, i, j));
125 },
126 // iterator initialization (fGenerator)
127 [](sref<ProblemContext> pTSP, const ESolutionTSP& se)
128 -> std::pair<int, int> { return make_pair(-1, -1); },
129 [](sref<ProblemContext> pTSP, std::pair<int, int>& p) -> void {
130 // void (*fFirst)(IMS&), // iterator.first()
131 p.first = 0;
132 p.second = 1;
133 },
134 [](sref<ProblemContext> pTSP, std::pair<int, int>& p) -> void {
135 // void (*fNext)(IMS&), // iterator.next()
136 if (p.second < (pTSP->n - 1))
137 p.second++;
138 else {
139 p.first++;
140 p.second = p.first + 1;
141 }
142 },
143 [](sref<ProblemContext> pTSP, std::pair<int, int>& p) -> bool {
144 // bool (*fIsDone)(IMS&), //
145 // iterator.isDone()
146 return p.first >= pTSP->n - 1;
147 },
148 [](sref<ProblemContext> pTSP,
149 std::pair<int, int>& p) -> uptr<Move<ESolutionTSP>> {
150 // uptr<Move<XES>> (*fCurrent)(IMS&) //
151 // iterator.current()
152 return uptr<Move<ESolutionTSP>>(
153 makeMoveSwap(pTSP, p.first, p.second));
154 } // FNSSeq
155 }};
156 return nsseq2;
157}
158
159class OptFrameDemoTSP {
160 public:
161 sref<ProblemContext> pTSP;
162 sref<FConstructive<std::vector<int>, ProblemContext>> randomConstructive;
163 sref<FEvaluator<ESolutionTSP, MINIMIZE, ProblemContext>> eval;
164 sref<FNS<ESolutionTSP, ProblemContext>> nsSwap;
165 sref<FNSSeq<std::pair<int, int>, ESolutionTSP, ProblemContext>> nsseqSwap;
166 sptr<DecoderRandomKeys<ESolutionTSP, double>> decoder;
167
168 explicit OptFrameDemoTSP(sref<ProblemContext> p)
169 : pTSP{p},
170 randomConstructive{
171 new FConstructive<std::vector<int>, ProblemContext>{p, frandom}},
172 eval{new FEvaluator<ESolutionTSP, MINIMIZE, ProblemContext>{p,
173 fevaluate}},
174 nsSwap{new FNS<ESolutionTSP, ProblemContext>{p, fRandomSwap}},
175 nsseqSwap{make_nsseq(p)}
176
177 {}
178};
179
180//
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).
1int main() {
2 srand(0); // using system random (weak... just an example!)
3
4 // load data into problem context 'pTSP'
5 Scanner scanner{"5\n1 10 10\n2 20 20\n3 30 30\n4 40 40\n5 50 50\n"};
6 sref<ProblemContext> pTSP{new ProblemContext{}};
7 pTSP->load(scanner);
8 std::cout << pTSP->dist << std::endl;
9
10 OptFrameDemoTSP demo{pTSP};
11
12 // evaluator
13 // TSPEval ev;
14 //
15 // create simple solution
16 // TSPRandom crand;
17 //
18 std::vector<int> sol = *demo.randomConstructive->generateSolution(0);
19 std::cout << sol << std::endl;
20
21 // evaluation value and store on ESolution pair
22 ESolutionTSP esol(sol, demo.eval->evaluate(sol));
23 esol.second.print(); // print evaluation
24
25 // swap 0 with 1
26 MoveSwap move{demo.pTSP, make_pair(0, 1), fApplySwap};
27 move.print();
28
29 // NSSwap nsswap;
30 // move for solution 'esol'
31 auto m1 = demo.nsSwap->randomMove(esol);
32 m1->print();
33
34 std::cout << std::endl;
35 std::cout << "begin listing NSSeqSwapFancy" << std::endl;
36 //
37 auto it1 = demo.nsseqSwap->getIterator(esol);
38 for (it1->first(); !it1->isDone(); it1->next()) it1->current()->print();
39 std::cout << "end listing NSSeqSwapFancy" << std::endl;
40
41 // Random number generator
42 RandGen rg; // stack version
43 sref<RandGen> rg2{new RandGen}; // heap version (safely shared)
44 // testing simulated annealing
45 BasicInitialSearch<ESolutionTSP> initRand(demo.randomConstructive, demo.eval);
46
47 vsref<LocalSearch<ESolutionTSP>> ns_list;
48 Evaluator<ESolutionTSP::first_type, ESolutionTSP::second_type>* ev2 =
49 new FEvaluator<ESolutionTSP, MinOrMax::MINIMIZE, ProblemContext>{
50 pTSP, fevaluate};
51 GeneralEvaluator<ESolutionTSP>* gev2 = (GeneralEvaluator<ESolutionTSP>*)ev2;
52 sref<GeneralEvaluator<ESolutionTSP>> eval2(gev2);
53 ns_list.push_back(new BestImprovement<ESolutionTSP>(eval2, demo.nsseqSwap));
54
55 VariableNeighborhoodDescent<ESolutionTSP> VND(demo.eval, ns_list);
56 // VND.setVerbose();
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//
2ILSLPerturbationLPlus2<ESolutionTSP> pert(demo.eval, demo.nsSwap, rg2);
3
4IteratedLocalSearchLevels<ESolutionTSP> ils(demo.eval, initRand, VND, pert, 10,
5 5);
6// ils.setVerbose();
7
8std::cout << "will start ILS for 3 seconds" << std::endl;
9
10auto status = ils.search(
11 StopCriteria<ESolutionTSP::second_type>{3.0}); // 3.0 seconds max
12ESolutionTSP best = *status.best;
13// best solution value
14best.second.print();
15std::cout << "solution: " << best.first << std::endl;
16
17std::cout << "FINISHED" << std::endl;
18return 0;
19}
Complete Example for ILS
We provide the main file for TSP ILS mainTSP-fcore-ils.cpp.
mainTSP-fcore-ils.cpp
File 'mainTSP-fcore-ils.cpp' located in 'demo/03_QuickstartTSP_VNS_BRKGA/'
1// SPDX-License-Identifier: MIT OR LGPL-3.0-or-later
2// Copyright (C) 2007-2022 - OptFrame developers
3// https://github.com/optframe/optframe
4
5// OptFrame Demo TSP - Iterated Local Search
6
7// C++
8#include <iostream>
9//
10#include "TSP-fcore.hpp"
11// implementation of TSP
12
13#include <OptFrame/Core.hpp>
14#include <OptFrame/Heuristics/Heuristics.hpp> // many metaheuristics here...
15#include <OptFrame/Heuristics/ILS/IteratedLocalSearchLevels.hpp>
16#include <OptFrame/Heuristics/LocalSearches/BestImprovement.hpp>
17#include <OptFrame/Heuristics/LocalSearches/VariableNeighborhoodDescent.hpp>
18#include <OptFrame/LocalSearch.hpp>
19
20// import everything on main()
21using namespace std; // NOLINT
22using namespace optframe; // NOLINT
23using namespace scannerpp; // NOLINT
24// using namespace TSP_fcore;
25int main() {
26 srand(0); // using system random (weak... just an example!)
27
28 // load data into problem context 'pTSP'
29 Scanner scanner{"5\n1 10 10\n2 20 20\n3 30 30\n4 40 40\n5 50 50\n"};
30 sref<ProblemContext> pTSP{new ProblemContext{}};
31 pTSP->load(scanner);
32 std::cout << pTSP->dist << std::endl;
33
34 OptFrameDemoTSP demo{pTSP};
35
36 // evaluator
37 // TSPEval ev;
38 //
39 // create simple solution
40 // TSPRandom crand;
41 //
42 std::vector<int> sol = *demo.randomConstructive->generateSolution(0);
43 std::cout << sol << std::endl;
44
45 // evaluation value and store on ESolution pair
46 ESolutionTSP esol(sol, demo.eval->evaluate(sol));
47 esol.second.print(); // print evaluation
48
49 // swap 0 with 1
50 MoveSwap move{demo.pTSP, make_pair(0, 1), fApplySwap};
51 move.print();
52
53 // NSSwap nsswap;
54 // move for solution 'esol'
55 auto m1 = demo.nsSwap->randomMove(esol);
56 m1->print();
57
58 std::cout << std::endl;
59 std::cout << "begin listing NSSeqSwapFancy" << std::endl;
60 //
61 auto it1 = demo.nsseqSwap->getIterator(esol);
62 for (it1->first(); !it1->isDone(); it1->next()) it1->current()->print();
63 std::cout << "end listing NSSeqSwapFancy" << std::endl;
64
65 // Random number generator
66 RandGen rg; // stack version
67 sref<RandGen> rg2{new RandGen}; // heap version (safely shared)
68 // testing simulated annealing
69 BasicInitialSearch<ESolutionTSP> initRand(demo.randomConstructive, demo.eval);
70
71 vsref<LocalSearch<ESolutionTSP>> ns_list;
72 Evaluator<ESolutionTSP::first_type, ESolutionTSP::second_type>* ev2 =
73 new FEvaluator<ESolutionTSP, MinOrMax::MINIMIZE, ProblemContext>{
74 pTSP, fevaluate};
75 GeneralEvaluator<ESolutionTSP>* gev2 = (GeneralEvaluator<ESolutionTSP>*)ev2;
76 sref<GeneralEvaluator<ESolutionTSP>> eval2(gev2);
77 ns_list.push_back(new BestImprovement<ESolutionTSP>(eval2, demo.nsseqSwap));
78
79 VariableNeighborhoodDescent<ESolutionTSP> VND(demo.eval, ns_list);
80 // VND.setVerbose();//
81ILSLPerturbationLPlus2<ESolutionTSP> pert(demo.eval, demo.nsSwap, rg2);
82
83IteratedLocalSearchLevels<ESolutionTSP> ils(demo.eval, initRand, VND, pert, 10,
84 5);
85// ils.setVerbose();
86
87std::cout << "will start ILS for 3 seconds" << std::endl;
88
89auto status = ils.search(
90 StopCriteria<ESolutionTSP::second_type>{3.0}); // 3.0 seconds max
91ESolutionTSP best = *status.best;
92// best solution value
93best.second.print();
94std::cout << "solution: " << best.first << std::endl;
95
96std::cout << "FINISHED" << std::endl;
97return 0;
98}
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.
1class MyRandomKeysInitEPop
2 : public InitialEPopulation<
3 std::pair<std::vector<double>, Evaluation<int>>> {
4 using RSK = std::vector<double>;
5
6 private:
7 int sz;
8 sref<RandGen> rg;
9
10 public:
11 explicit MyRandomKeysInitEPop(int size, sref<RandGen> _rg = new RandGen)
12 : sz{size}, rg{_rg} {}
13
14 // copy constructor
15 // MyRandomKeysInitEPop(const MyRandomKeysInitEPop& self)
16 // : sz{self.sz}, rg{self.rg} {}
17
18 // this generator cannot evaluate solutions
19 bool canEvaluate() const override { return false; }
20
21 VEPopulation<std::pair<RSK, Evaluation<int>>> generateEPopulation(
22 unsigned populationSize, double timelimit) override {
23 VEPopulation<std::pair<RSK, Evaluation<int>>> pop;
24
25 for (unsigned i = 0; i < populationSize; i++) {
26 vector<double> vd(sz);
27 for (int j = 0; j < sz; j++) vd[j] = (rg->rand() % 100000) / 100000.0;
28 // assert(!this->canEvaluate());
29 std::pair<RSK, Evaluation<int>> ind{vd, Evaluation<int>{}};
30 pop.push_back(ind);
31 }
32
33 return pop;
34 }
35};
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.
1pair<Evaluation<int>, vector<int>> fDecodeEval(
2 sref<Evaluator<typename ESolutionTSP::first_type,
3 typename ESolutionTSP::second_type, ESolutionTSP>>
4 eval,
5 const vector<double>& rk) {
6 vector<pair<double, int>> v(rk.size());
7 //
8 for (unsigned i = 0; i < v.size(); i++) v[i] = pair<double, int>(rk[i], i);
9
10 sort(v.begin(), v.end(),
11 [](const pair<double, int>& i, const pair<double, int>& j) -> bool {
12 return i.first < j.first;
13 });
14
15 // R = vector<int>
16 vector<int> p(v.size());
17 for (unsigned i = 0; i < v.size(); i++) p[i] = v[i].second;
18
19 /*
20 // ========== CHECKER ========
21 vector<bool> vb(v.size(), false);
22 for (unsigned i = 0; i < p.size(); i++)
23 vb[p[i]] = true;
24 for (unsigned i = 0; i < vb.size(); i++) {
25 if (!vb[i]) {
26 std::cout << "ERROR rk:" << rk << std::endl;
27 std::cout << "ERROR v:" << v << std::endl;
28 std::cout << "ERROR p:" << p << std::endl;
29 std::cout << "ERROR vb:" << vb << std::endl;
30 }
31 assert(vb[i]);
32 }
33 // ===== end CHECKER =====
34*/
35
36 Evaluation<int> e = eval->evaluate(p);
37 return make_pair(e, p);
38}
39
40// evaluator random keys (for TSP)
41// FDecoderEvalRK<std::pair<std::vector<int>, Evaluation<int>>, double>
42// decoder{fDecode};
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.
1int main() {
2 sref<RandGen> rg = new RandGen; // avoids weird windows OS interactions
3
4 // load data into problem context 'pTSP'
5 Scanner scanner{"5\n1 10 10\n2 20 20\n3 30 30\n4 40 40\n5 50 50\n"};
6 sref<ProblemContext> pTSP{new ProblemContext{}};
7 pTSP->load(scanner);
8 std::cout << pTSP->dist << std::endl;
9
10 OptFrameDemoTSP demo{pTSP};
11 // setup decoder function
12 demo.decoder = sptr<DecoderRandomKeys<ESolutionTSP, double>>{
13 new FDecoderEvalRK<std::pair<std::vector<int>, Evaluation<int>>, double>{
14 demo.eval, fDecodeEval}};
15
16 // Parameters BRKGA
17 // (C1): Evaluator<S, XEv>& _evaluator, int key_size, unsigned numGen,
18 // unsigned _popSize, double fracTOP, double fracBOT, double _probElitism) :
19
20 sref<DecoderRandomKeys<ESolutionTSP, double>> _decoder = demo.decoder;
21 sref<InitialEPopulation<std::pair<vector<double>, ESolutionTSP::second_type>>>
22 _initPop = new MyRandomKeysInitEPop(pTSP->n); // passing key_size
23
24 // eprk, pTSP.n, 1000, 30, 0.4, 0.3, 0.6
25 BRKGA<ESolutionTSP, double> brkga(
26 _decoder, MyRandomKeysInitEPop(pTSP->n, rg), // key_size = pTSP.n
27 30, 1000, 0.4, 0.3, 0.6, rg);
28
29 auto searchOut = brkga.search(3.0); // 3.0 seconds max
30 ESolutionTSP best = *searchOut.best;
31 // best solution value
32 best.second.print();
33 std::cout << "solution: " << best.first << std::endl;
34
35 std::cout << "FINISHED" << std::endl;
36 return 0;
37}
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.cpp.
mainTSP-fcore-brkga.cpp
File 'mainTSP-fcore-brkga.cpp' located in 'demo/03_QuickstartTSP_VNS_BRKGA/'
1// SPDX-License-Identifier: MIT OR LGPL-3.0-or-later
2// Copyright (C) 2007-2022 - OptFrame developers
3// https://github.com/optframe/optframe
4
5// OptFrame Demo TSP - BRKGA
6
7// C++
8#include <iostream>
9//
10#include "TSP-fcore.hpp"
11// implementation of TSP
12//
13#include <OptFrame/Core.hpp>
14#include <OptFrame/Heuristics/EA/RK/BRKGA.hpp>
15#include <OptFrame/Heuristics/Heuristics.hpp> // many metaheuristics here...
16#include <OptFrame/InitialPopulation.hpp>
17#include <OptFrame/LocalSearch.hpp>
18
19// import everything on main()
20using namespace std; // NOLINT
21using namespace optframe; // NOLINT
22using namespace scannerpp; // NOLINT
23// using namespace TSP_fcore;
24
25class MyRandomKeysInitEPop
26 : public InitialEPopulation<
27 std::pair<std::vector<double>, Evaluation<int>>> {
28 using RSK = std::vector<double>;
29
30 private:
31 int sz;
32 sref<RandGen> rg;
33
34 public:
35 explicit MyRandomKeysInitEPop(int size, sref<RandGen> _rg = new RandGen)
36 : sz{size}, rg{_rg} {}
37
38 // copy constructor
39 // MyRandomKeysInitEPop(const MyRandomKeysInitEPop& self)
40 // : sz{self.sz}, rg{self.rg} {}
41
42 // this generator cannot evaluate solutions
43 bool canEvaluate() const override { return false; }
44
45 VEPopulation<std::pair<RSK, Evaluation<int>>> generateEPopulation(
46 unsigned populationSize, double timelimit) override {
47 VEPopulation<std::pair<RSK, Evaluation<int>>> pop;
48
49 for (unsigned i = 0; i < populationSize; i++) {
50 vector<double> vd(sz);
51 for (int j = 0; j < sz; j++) vd[j] = (rg->rand() % 100000) / 100000.0;
52 // assert(!this->canEvaluate());
53 std::pair<RSK, Evaluation<int>> ind{vd, Evaluation<int>{}};
54 pop.push_back(ind);
55 }
56
57 return pop;
58 }
59};
60
61
62pair<Evaluation<int>, vector<int>> fDecodeEval(
63 sref<Evaluator<typename ESolutionTSP::first_type,
64 typename ESolutionTSP::second_type, ESolutionTSP>>
65 eval,
66 const vector<double>& rk) {
67 vector<pair<double, int>> v(rk.size());
68 //
69 for (unsigned i = 0; i < v.size(); i++) v[i] = pair<double, int>(rk[i], i);
70
71 sort(v.begin(), v.end(),
72 [](const pair<double, int>& i, const pair<double, int>& j) -> bool {
73 return i.first < j.first;
74 });
75
76 // R = vector<int>
77 vector<int> p(v.size());
78 for (unsigned i = 0; i < v.size(); i++) p[i] = v[i].second;
79
80 /*
81 // ========== CHECKER ========
82 vector<bool> vb(v.size(), false);
83 for (unsigned i = 0; i < p.size(); i++)
84 vb[p[i]] = true;
85 for (unsigned i = 0; i < vb.size(); i++) {
86 if (!vb[i]) {
87 std::cout << "ERROR rk:" << rk << std::endl;
88 std::cout << "ERROR v:" << v << std::endl;
89 std::cout << "ERROR p:" << p << std::endl;
90 std::cout << "ERROR vb:" << vb << std::endl;
91 }
92 assert(vb[i]);
93 }
94 // ===== end CHECKER =====
95*/
96
97 Evaluation<int> e = eval->evaluate(p);
98 return make_pair(e, p);
99}
100
101// evaluator random keys (for TSP)
102// FDecoderEvalRK<std::pair<std::vector<int>, Evaluation<int>>, double>
103// decoder{fDecode};
104int main() {
105 sref<RandGen> rg = new RandGen; // avoids weird windows OS interactions
106
107 // load data into problem context 'pTSP'
108 Scanner scanner{"5\n1 10 10\n2 20 20\n3 30 30\n4 40 40\n5 50 50\n"};
109 sref<ProblemContext> pTSP{new ProblemContext{}};
110 pTSP->load(scanner);
111 std::cout << pTSP->dist << std::endl;
112
113 OptFrameDemoTSP demo{pTSP};
114 // setup decoder function
115 demo.decoder = sptr<DecoderRandomKeys<ESolutionTSP, double>>{
116 new FDecoderEvalRK<std::pair<std::vector<int>, Evaluation<int>>, double>{
117 demo.eval, fDecodeEval}};
118
119 // Parameters BRKGA
120 // (C1): Evaluator<S, XEv>& _evaluator, int key_size, unsigned numGen,
121 // unsigned _popSize, double fracTOP, double fracBOT, double _probElitism) :
122
123 sref<DecoderRandomKeys<ESolutionTSP, double>> _decoder = demo.decoder;
124 sref<InitialEPopulation<std::pair<vector<double>, ESolutionTSP::second_type>>>
125 _initPop = new MyRandomKeysInitEPop(pTSP->n); // passing key_size
126
127 // eprk, pTSP.n, 1000, 30, 0.4, 0.3, 0.6
128 BRKGA<ESolutionTSP, double> brkga(
129 _decoder, MyRandomKeysInitEPop(pTSP->n, rg), // key_size = pTSP.n
130 30, 1000, 0.4, 0.3, 0.6, rg);
131
132 auto searchOut = brkga.search(3.0); // 3.0 seconds max
133 ESolutionTSP best = *searchOut.best;
134 // best solution value
135 best.second.print();
136 std::cout << "solution: " << best.first << std::endl;
137
138 std::cout << "FINISHED" << std::endl;
139 return 0;
140}
More Examples
For a other examples, see folder Examples/FCore-BRKGA and execute bazel build ...
Warning
Feel free to check folder OptFrame/Examples for other examples on FCore and OptFrame Classic.