Advanced - CheckModule
We expand the knowledge from Quick Start where the user has learned how to Install OptFrame, and how to compile and test metaheuristics for classic 0-1 Knapsack Problem (01KP) and Traveling Salesman Problem (TSP).
We now demonstrate how to quickly test the code and provide better move evaluations.
Multiple ways to evaluate a move
Warning
At this point, we assume the reader is familiarized with the Traveling Salesman Problem, and is also familiarized with basic workings of OptFrame and OptFrame Functional Core.
We recall the example for the TSP, where a move operation called MoveSwap is proposed.
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}
Basic move cost calculation (revCost)
Typically, any basic move implementation will require at least one extra evaluation (on objective space) and two move applications (called revCost):
First apply move it to current solution, becoming a neighbor solution (prevent solution copy)
generating an Undo Move
evaluating the cost at the neighbor solution
applying the Undo Move and come back to original solution
update objective value (by numeric copy)
1class MoveSwap : public Move<ESolutionTSP> {
2 public:
3 int i, j;
4
5 MoveSwap(int _i, int _j) : i{_i}, j{_j} {}
6
7 bool canBeApplied(const ESolutionTSP& se) override {
8 return (::abs(i - j) >= 2) && (i >= 1) && (j >= 1);
9 }
10
11 uptr<Move<ESolutionTSP>> apply(ESolutionTSP& se) override {
12 // perform swap of clients i and j
13 int aux = se.first[j];
14 se.first[j] = se.first[i];
15 se.first[i] = aux;
16 return uptr<Move<ESolutionTSP>>(
17 new MoveSwap{j, i}); // return a reverse move ('undo' move)s
18 }
19
20 bool operator==(const Move<ESolutionTSP>& other) const override {
21 auto& fmove = (MoveSwap&)other;
22 return (i == fmove.i) && (j == fmove.j);
23 }
24};
25
26uptr<Move<ESolutionTSP>> makeMoveSwap(int i, int j) {
27 return uptr<Move<ESolutionTSP>>(new MoveSwap{i, j});
28}
Important
We have included the filter canBeApplied to limit the scope of valid moves,
so as an operator== to check for equality between moves.
Faster move cost calculation (fasterCost)
Step 3 from revCost is typically costly, what may be prevented by directly updating objective value at the same time the move is applied to solution.
This can be done by adopting the applyUpdate operation on Move implementation.
Usually, this can be done by either:
Precomputing the cost value before move apply, and then apply it
Apply the move and then directly compute the updated objective value
1class MoveSwap : public Move<ESolutionTSP> {
2 public:
3 sref<ProblemContext> pTSP;
4 int i, j;
5
6 MoveSwap(sref<ProblemContext> _p, int _i, int _j) : pTSP{_p}, i{_i}, j{_j} {}
7
8 bool canBeApplied(const ESolutionTSP& se) override {
9 return (::abs(i - j) >= 2) && (i >= 1) && (j >= 1);
10 }
11
12 uptr<Move<ESolutionTSP>> applyUpdate(ESolutionTSP& se) override {
13 // input cannot be outdated
14 assert(!se.second.isOutdated());
15 auto& s = se.first;
16 int diff =
17 -pTSP->dist(s[i - 1], s[i]) - pTSP->dist(s[i], s[(i + 1) % pTSP->n]) -
18 pTSP->dist(s[j - 1], s[j]) - pTSP->dist(s[j], s[(j + 1) % pTSP->n]);
19 diff += pTSP->dist(s[i - 1], s[j]) +
20 pTSP->dist(s[j], s[(i + 1) % pTSP->n]) +
21 pTSP->dist(s[j - 1], s[i]) + pTSP->dist(s[i], s[(j + 1) % pTSP->n]);
22 // solution swap
23 auto rev = this->apply(se);
24 se.second.setObjFunction(se.second.evaluation() + diff);
25 return rev;
26 }
27
28 uptr<Move<ESolutionTSP>> apply(ESolutionTSP& se) override {
29 // perform swap of clients i and j
30 int aux = se.first[j];
31 se.first[j] = se.first[i];
32 se.first[i] = aux;
33 return uptr<Move<ESolutionTSP>>(
34 new MoveSwap{pTSP, j, i}); // return a reverse move ('undo' move)s
35 }
36
37 bool operator==(const Move<ESolutionTSP>& other) const override {
38 auto& fmove = (MoveSwap&)other;
39 return (i == fmove.i) && (j == fmove.j);
40 }
41};
42
43uptr<Move<ESolutionTSP>> makeMoveSwap(sref<ProblemContext> p, int i, int j) {
44 return uptr<Move<ESolutionTSP>>(new MoveSwap{p, i, j});
45}
Constant cost calculation (cost)
Finally, an even faster approach is not directly compute cost of move, without even applying it to the solution.
The method cost() may optionally return a calculated cost, if user wants to use that.
We observe that it is important to have some precise numerics here, such as Evaluation<int>,
instead of Evaluation<double>. Cost recalculation may impose calculation errors (but if user
wants to do it anyway, OptFrame will not forbid it).
1class MoveSwap : public Move<ESolutionTSP> {
2 public:
3 sref<ProblemContext> pTSP;
4 int i, j;
5
6 MoveSwap(sref<ProblemContext> _p, int _i, int _j) : pTSP{_p}, i{_i}, j{_j} {}
7
8 bool canBeApplied(const ESolutionTSP& se) override {
9 return (::abs(i - j) >= 2) && (i >= 1) && (j >= 1);
10 }
11
12 uptr<Move<ESolutionTSP>> applyUpdate(ESolutionTSP& se) override {
13 // input cannot be outdated
14 assert(!se.second.isOutdated());
15 auto& s = se.first;
16 int diff =
17 -pTSP->dist(s[i - 1], s[i]) - pTSP->dist(s[i], s[(i + 1) % pTSP->n]) -
18 pTSP->dist(s[j - 1], s[j]) - pTSP->dist(s[j], s[(j + 1) % pTSP->n]);
19 diff += pTSP->dist(s[i - 1], s[j]) +
20 pTSP->dist(s[j], s[(i + 1) % pTSP->n]) +
21 pTSP->dist(s[j - 1], s[i]) + pTSP->dist(s[i], s[(j + 1) % pTSP->n]);
22 // solution swap
23 auto rev = this->apply(se);
24 se.second.setObjFunction(se.second.evaluation() + diff);
25 return rev;
26 }
27
28 uptr<Move<ESolutionTSP>> apply(ESolutionTSP& se) override {
29 // perform swap of clients i and j
30 int aux = se.first[j];
31 se.first[j] = se.first[i];
32 se.first[i] = aux;
33 return uptr<Move<ESolutionTSP>>(
34 new MoveSwap{pTSP, j, i}); // return a reverse move ('undo' move)s
35 }
36
37 virtual op<Evaluation<int>> cost(const ESolutionTSP& se,
38 bool allowEstimated) override {
39 assert(!se.second.isOutdated());
40 auto& s = se.first;
41 int diff =
42 -pTSP->dist(s[i - 1], s[i]) - pTSP->dist(s[i], s[(i + 1) % pTSP->n]) -
43 pTSP->dist(s[j - 1], s[j]) - pTSP->dist(s[j], s[(j + 1) % pTSP->n]);
44 diff += pTSP->dist(s[i - 1], s[j]) +
45 pTSP->dist(s[j], s[(i + 1) % pTSP->n]) +
46 pTSP->dist(s[j - 1], s[i]) + pTSP->dist(s[i], s[(j + 1) % pTSP->n]);
47 return std::make_optional(Evaluation<int>(diff));
48 }
49
50 bool operator==(const Move<ESolutionTSP>& other) const override {
51 auto& fmove = (MoveSwap&)other;
52 return (i == fmove.i) && (j == fmove.j);
53 }
54};
55
56uptr<Move<ESolutionTSP>> makeMoveSwap(sref<ProblemContext> p, int i, int j) {
57 return uptr<Move<ESolutionTSP>>(new MoveSwap{p, i, j});
58}
Using the CheckCommand to test structures
One can easily check for the integrity of the structures, by creating an instance of CheckCommand.
First, create it, then add all available components (NS, NSSeq, Evaluator, Constructive, …). Finally, invoke it passing two parameters: randomized pressure and iterative pressure.
1// SPDX-License-Identifier: LGPL-3.0-or-later OR MIT
2// Copyright (C) 2007-2022 - OptFrame - https://github.com/optframe/optframe
3
4#include <iostream>
5//
6#include <OptFrame/Core.hpp>
7#include <OptFrame/Heuristics/Heuristics.hpp> // many metaheuristics here...
8#include <OptFrame/Heuristics/ILS/IteratedLocalSearchLevels.hpp>
9#include <OptFrame/Heuristics/LocalSearches/BestImprovement.hpp>
10#include <OptFrame/Heuristics/LocalSearches/VariableNeighborhoodDescent.hpp>
11#include <OptFrame/LocalSearch.hpp>
12#include <OptFrame/Util/CheckCommand.hpp>
13//
14#include "TSP-fcore.hpp" // NOLINT
15// implementation of TSP
16
17// import everything on main()
18using namespace std;
19using namespace optframe;
20using namespace scannerpp;
21// using namespace TSP_fcore;
22int main() {
23 std::stringstream ss;
24 srand(1000000);
25 int N = 50;
26 ss << N << std::endl;
27 for (unsigned i = 0; i < N; i++)
28 ss << i << "\t" << rand() % 1000 << "\t" << rand() % 1000 << std::endl;
29 // Scanner scanner{ std::string(instance5) };
30 Scanner scanner{ss.str()};
31 sref<ProblemContext> pTSP{new ProblemContext{}};
32 pTSP->load(scanner);
33
34 // REQUIRE(pTSP.n == 5);
35 assert(pTSP->n == 50);
36
37 // set random seed for std::random_shuffle
38 srand(1000000);
39
40 FConstructive<std::vector<int>, ProblemContext> crand{pTSP, frandom};
41 FEvaluator<ESolutionTSP, MinOrMax::MINIMIZE, ProblemContext> eval{pTSP,
42 fevaluate};
43 FNS<ESolutionTSP, ProblemContext> nsswap{pTSP, fRandomSwap};
44 sref<FNSSeq<std::pair<int, int>, ESolutionTSP, ProblemContext>> nsseq2{
45 make_nsseq(pTSP)};
46
47 sref<InitialSearch<ESolutionTSP>> initRand{
48 new BasicInitialSearch<ESolutionTSP>(crand, eval)};
49
50 CheckCommand<ESolutionTSP> check(false); // verbose
51 //
52 check.addEvaluator(eval);
53 check.add(initRand);
54 check.addNS(nsswap); // NS
55 check.addNSSeq(nsseq2); // NSSeq
56
57 // bool run(int iterMax, int nSolNSSeq)
58 check.run(100, 10);
59 //
60 return 0;
61}
An example of output can be seen here:
Note that cost() version is faster than others, for both neighborhoods (NS and NSSeq), as expected.
Error codes on CheckCommand
CheckCommand may launch several errors, according to the table below:
static const int CMERR_EV_BETTERTHAN = 2001;
static const int CMERR_EV_BETTEREQUALS = 2002;
static const int CMERR_MOVE_EQUALS = 3001;
static const int CMERR_MOVE_HASREVERSE = 3002;
static const int CMERR_MOVE_REVREV_VALUE = 3004;
static const int CMERR_MOVE_REVSIMPLE = 3005;
static const int CMERR_MOVE_REVFASTER = 3006;
static const int CMERR_MOVE_REALREVFASTER = 3008;
static const int CMERR_MOVE_COST = 3007;
Feel free to file an Issue on OptFrame Project in order to discuss how to handle them.
In the future, we intend to expand this section.
More Tricks on CheckCommand
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.