Quick start
OptFrame is a C++ framework to solve challenging optimization problems, specially by means of metaheuristic techniques. It has no external dependencies, except a C++ compiler compatible with C++17 (or C++20).
After installing OptFrame (or just cloning it), user can start building a solution to the problem at hand.
Welcome Message
A useful abstraction was introduced since OptFrame 4.1, called OptFrame Functional Core (FCore). The idea of FCore is to provide a simplified access to OptFrame programming classes, by means of closures and lambdas. This way, a project that typically had 8 to 10 files is reduced to a single file (all included in headers!).
The first test on FCore is to see if it’s correctly compiling. So let’s just include its main header, and print its welcome() message:
File 'mytest.cpp' located in 'demo/01_QuickstartWelcome/'
1// file: 'mytest.cpp'
2#include <OptFCore/FCore.hpp>
3#include <iostream>
4int
5main()
6{
7 std::cout << optframe::FCore::welcome() << std::endl;
8 return 0;
9}
Build with make
One way to compile it locally is just copy src/ folder inside your project and see the results (using GCC C++ compiler):
g++ --std=c++20 mytest.cpp -o fcore_mytest
./fcore_mytest
# Welcome to OptFrame Functional Core (FCore) - version 4.1-dev
If a local copy of OptFrame is being used in other folder (via git clone), one needs to pass its location via flag -I to the compiler (considering relative location of ./optframe/src/):
File 'makefile' located in 'demo/01_QuickstartWelcome/'
1all: demo_quickstart_welcome
2
3demo_quickstart_welcome:
4 g++ --std=c++20 -I../../include mytest.cpp -o demo_welcome
5 # Expects: Welcome to OptFrame Functional Core (FCore) - version 4.1-dev
6 ./demo_welcome
7
8
9build_with_bazel:
10 bazel build ... --cxxopt=-std=c++17
Build with bazel
If one wants to build in Windows or any other system, easiest manner is to use Bazel. Just create a WORKSPACE.bazel file that points to remote OptFrame git repository:
File 'WORKSPACE.bazel' located in 'demo/01_QuickstartWelcome/'
1load('@bazel_tools//tools/build_defs/repo:git.bzl', 'git_repository')
2git_repository(
3 name='OptFrame',
4 remote='https://github.com/optframe/optframe.git',
5 branch='master'
6)
And use the following BUILD.bazel file (with dependency to @OptFrame):
File 'BUILD.bazel' located in 'demo/01_QuickstartWelcome/'
1load("@rules_cc//cc:defs.bzl", "cc_library", "cc_binary")
2cc_binary(
3 name = "demo_welcome",
4 srcs = ["mytest.cpp"],
5 deps=["@OptFrame//include:OptFCore"],
6 copts = select({
7 "@bazel_tools//src/conditions:windows": ["/std:c++17"],
8 "@bazel_tools//src/conditions:darwin": ["--std=c++17"],
9 "//conditions:default": ["--std=c++17"],
10 }),
11)
Just invoke bazel build system (assuming MinGW C/C++ toolchain on Windows or just remove option --compiler
for Linux):
bazel build --compiler=mingw-gcc ...
bazel run :demo_welcome
# Welcome to OptFrame Functional Core (FCore) - version 4.1-dev
A deeper explanation of OptFrame theoretical foundations can be found on Concepts section, so we will move fast here!
First Example: 0-1 Knapsack Problem and Simulated Annealing
Let’s consider a classic problem: the 0-1 Knapsack Problem (KP).
By: Dake CC BY-SA 2.5
Given a set of items \(I\), the KP consists in selecting some items \(S \subseteq I\), such that the sum of weights \(w_i\) (for each selected item) do not exceed knapsack capacity \(Q\), and profit \(p_i\) of the selected items is maximized.
$$maximize\; \sum_{i \in S} p_i$$ $$\sum_{i \in S} w_i \leq Q$$ $$S \subseteq I$$
Solution and Evaluation Types
Users must first define a Representation, which is a data structure that represents
an element in the Solution Space for the KP. A natural candidate here is an array of booleans,
since we need to decide if we are going to carry each item or not. In C++, an interesting
approach is to use stl containers, such as a std::vector<int>
.
User also needs to specify the data type for the Objective Space, in general a numeric type.
In this case, we will simply choose
an Evaluation<int>
(just ignore the Evaluation container for now…).
We declare a XESolution pair that aggregates both spaces as a single
type ESolutionKP
(meaning an evaluated solution for the knapsack problem):
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 0-1 Knapsack Problem + Simulated Annealing
6// File: KP-fcore-ex.hpp
7#pragma once
8
9// C++
10#include <algorithm>
11#include <functional>
12#include <iostream>
13#include <utility>
14#include <vector>
15//
16#include <OptFCore/FCore.hpp>
17#include <OptFrame/Core.hpp>
18#include <OptFrame/Heuristics/Heuristics.hpp> // many metaheuristics here...
19#include <OptFrame/Scanner++/Scanner.hpp>
20#include <OptFrame/Util/Matrix.hpp>
21#include <OptFrame/printable/printable.hpp>
22
23using namespace std; // NOLINT
24using namespace optframe; // NOLINT
25using namespace scannerpp; // NOLINT
26
27// namespace para o problema da mochila
28// namespace KP_fcore {
29
30// Solução para o problema da mochila, e elemento de avaliação
31
32// ================================
33// Definição do 'ESolution'
34// Par: (Representação, Avaliação)
35// ================================
36
37using ESolutionKP = std::pair<std::vector<bool>, // (representation)
38 Evaluation<int> // (objective value)
39 >;
Hint
As long as fields first
and second
are provided on XESolution concept, any class can
be used instead of std::pair
, as demonstrated on Explicit XESolution
section.
Warning
Since OptFrame v4, any data structure can be used as a solution representation, as long as it implements operator<<
.
OptFrame Classic (<= v3) required a templated class named Solution<R,ADS>
, passing both
a representation type R
and auxiliary data structure type ADS
. This is no longer mandatory, but still widely
used on the available examples.
Problem Context
Users will need to store general problem information (such as profits and weights of items), so a ProblemContext can be introduced. For easy interoperability with file and string inputs (on Linux/Windows), we use Scanner class to process problem data (some details of ‘load’ function will only be discussed in a later moment):
1class ProblemContext {
2 public:
3 int n{0}; // numero de itens
4 int Q{-1}; // capacidade máxima da mochila
5 vector<int> p; // lucro 'p' de cada item
6 vector<int> w; // peso 'w' de cada item
7 //
8 // leitor de dados "estilo Java" (Scanner)
9 void load(Scanner& scanner) {
10 n = *scanner.nextInt(); // leitura do numero de itens na mochila
11 Q = *scanner.nextInt(); // leitura da capacidade da mochila
12 p = vector<int>(n); // realoca espaço
13 w = vector<int>(n); // realoca espaço
14 //
15 cout << "n=" << n << " Q=" << Q << endl;
16 //
17 // leitura do lucro do item i
18 for (int i = 0; i < n; i++) {
19 p[i] =
20 *scanner.nextInt(); // '*' é usado pq saída do 'nextInt' é 'optional'
21 cout << "p[" << i << "]=" << p[i] << " ";
22 }
23 cout << endl;
24 //
25 // leitura do peso do item i
26 for (int i = 0; i < n; i++) {
27 w[i] =
28 *scanner.nextInt(); // '*' é usado pq saída do 'nextInt' é 'optional'
29 cout << "w[" << i << "]=" << w[i] << " ";
30 }
31 cout << endl;
32 }
33};
34// Instanciar um problema da mochila pKP
35// ProblemContext pKP; // NOLINT
Hint
ProblemContext is a user-defined class that can have any desired format. A ‘load’ function
is just a suggestion, but not at all necessary. The object pKP
is declared in global scope
just to simplify the example, but it could be embedded in any other component if user desires.
Random Constructive
We need to have some initial solution for the search process, so we just proceed in a random manner. For simplicity, we allow infeasible solutions to be generated (as if capacity was infinite).
1std::vector<bool> frandom(sref<ProblemContext> pKP) {
2 vector<bool> v(pKP->n, false); // começa sem nenhum item escolhido
3 for (unsigned i = 0; i < v.size(); i++)
4 v[i] = rand() % 2; // sorteia se leva item ou não (resultado 0 ou 1)
5 // retorna solução
6 return v;
7}
8
9// Gerador de solução inicial (método construtivo)
10// FConstructive<std::vector<bool>, ProblemContext> randomConstructive{pKP,
11// frandom};
Hint
User can also define many advanced constructive techniques in a similar manner, such as greedy and greedy randomized approaches.
Evaluator
Now it’s time to define an evaluation (or objective) function. According to the goal of maximizing the profits, we iterate over selected items to accumulate profit and weights. As discussed in constructive section, we allow accumulated weight to surpass knapsack capacity, for infeasible configurations. To discourage that, we introduce negative penalization whenever capacity is exceeded (assuming weight -1000000):
1// ===========================
2// Função de avaliação
3// ===========================
4
5// função de avaliação da mochila
6Evaluation<int> fevaluate(sref<ProblemContext> pKP,
7 const std::vector<bool>& s) {
8 int f = 0;
9 int somaPeso = 0;
10 for (int i = 0; i < pKP->n; i++)
11 if (s[i]) // se elemento foi escolhido
12 {
13 f += pKP->p[i]; // acumula lucro do elemento i
14 somaPeso += pKP->w[i]; // acumula peso do elemento i
15 }
16 // verifica capacidade excedida
17 if (somaPeso >= pKP->Q)
18 f -= 1000000 *
19 (somaPeso - pKP->Q); // punição proporcional ao excesso de peso
20 //
21 return Evaluation<int>{f};
22}
23
24// Evaluate (false -> maximização)
25// FEvaluator<ESolutionKP, MAXIMIZE> evalKP{fevaluate};
We have defined fevaluate
function to create an Evaluator
object named evalKP
,
in a MAXIMIZE
direction.
Hint
User can choose MINIMIZE
if dealing with a minimization problem. For multi-objective
problems and Pareto optimization, user should visit Multi-Objective section.
Neighborhood Structure
In order to improve a given solution, several metaheuristics employ Local Search Optimization techniques based on the concept of Neighborhood Structure. Every neighborhood is related to a move operator, which is required (on FCore) to have an undo operation (capable of reverting the effects of the move).
We create a BitFlip
move, that changes the true/false
selection of a given item \(k\).
In this case, the move structure (representation of the move) is just an int
, that represents the flipped item.
Note the makeMoveBitFlip
move generator based on FCore library.
1// MoveBitFlip (moveData = 'int' (k))
2using MoveBitFlip = FMove<int, ESolutionKP>;
3
4// vizinhança: operador de "movimento" que faz "bit flip" (0 -> 1; 1 -> 0) na
5// posição k
6int fApplyFlip(const int& k, ESolutionKP& se) {
7 // se.first[k] = 1 - se.first[k]; // inverte elemento 'k'
8 se.first[k] = !se.first[k]; // inverte elemento 'k'
9 return k; // movimento reverso
10}
11
12uptr<Move<ESolutionKP>> makeMoveBitFlip(int k) {
13 return uptr<Move<ESolutionKP>>(new MoveBitFlip{k, fApplyFlip});
14}
The definition of the move can be done using inheritance, if one finds easier (which is what we will adopt).
1//
2class MoveBitFlip : public Move<ESolutionKP> {
3 public:
4 int k; // MoveBitFlip (moveData = 'int' (k))
5
6 explicit MoveBitFlip(int _k) : k{_k} {}
7
8 uptr<Move<ESolutionKP>> apply(ESolutionKP& se) override {
9 se.first[k] = !se.first[k]; // reverts element 'k'
10 return uptr<Move<ESolutionKP>>(new MoveBitFlip{k}); // returns reverse move
11 }
12};
13
14uptr<Move<ESolutionKP>> makeMoveBitFlip(int k) {
15 return uptr<Move<ESolutionKP>>(new MoveBitFlip{k});
16}
Now, it’s time to define a neighborhood generator for the move.
OptFrame has three main types of neighborhoods: NS
, NSSeq
and NSEnum
.
In this example, we will use NS
, since it only requires the generation of random moves:
1// gerador de movimentos aleatórios do tipo BitFlip
2uptr<Move<ESolutionKP>> fRandomFlip(sref<ProblemContext> pKP,
3 const ESolutionKP& se) {
4 int k = ::rand() % pKP->n; // sorteia um item entre [0..n-1]
5 // cria um "movimento" de flip, na posição k, com operação 'fApplyFlip'
6 return uptr<Move<ESolutionKP>>(makeMoveBitFlip(k));
7}
8
9// Estrutura de Vizinhança para BitFlip (NS)
10// FNS<ESolutionKP> nsFlip{fRandomFlip};
11
12// ================== EVERYTHING TOGETHER ====================
13
14class OptFrameDemoKP {
15 public:
16 FConstructive<std::vector<bool>, ProblemContext> randomConstructive;
17 FEvaluator<ESolutionKP, MAXIMIZE, ProblemContext> evalKP;
18 FNS<ESolutionKP, ProblemContext> nsFlip;
19
20 explicit OptFrameDemoKP(sref<ProblemContext> p)
21 : randomConstructive{p, frandom},
22 evalKP{FEvaluator<ESolutionKP, MAXIMIZE, ProblemContext>{p, fevaluate}},
23 nsFlip{FNS<ESolutionKP, ProblemContext>{p, fRandomFlip}} {}
24};
Hint
It is usually a good idea to start developing over the simplest neighborhood, which is NS
.
Most (non-deterministic) metaheuristics only requires a NS
, as it only requires the generation of random moves.
More advanced neighborhoods based on iterators, such as NSSeq
and NSEnum
are only required for advanced Local Search methods.
Time to Test!
At this point, you can already test many nice metaheuristics and solve your knapsack problem! We use the following code to load a problem instance (see Complete Example after):
1std::cout << "======== Carregando Problema ========" << std::endl;
2// semente pseudo-aleatória fixa em zero
3srand(time(NULL));
4
5std::string sinstance = "knapsack-example.txt";
6File f{sinstance};
7
8if (!f.isOpen()) {
9 std::cerr << "Problema '" << sinstance << "' não encontrado no diretório!"
10 << std::endl;
11 return 1;
12}
13
14Scanner scanner{std::move(f)};
15
16sref<ProblemContext> pKP{new ProblemContext{}};
17pKP->load(scanner);
18std::cout << "número de elementos na mochila:" << pKP->n << std::endl;
19
20OptFrameDemoKP demo{pKP};
Hint
It is useful to test every FCore structure independently, so as to develop unit testing for them.
To test the constructive and evaluator:
1std::cout << "======== Testa Construtivo Aleatório ========" << std::endl;
2// invoca método 'generateSolution' do FCore 'FConstructive' para construtivo
3// aleatório
4std::vector<bool> sol = *demo.randomConstructive.generateSolution(0.0);
5// imprime solução inicial
6std::cout << sol << std::endl;
7//
8std::cout << "======== Testa Avaliador ========" << std::endl;
9// avalia solução inicial e cria um par 'ESolution'
10ESolutionKP esol(sol, demo.evalKP.evaluate(sol));
11// imprime avaliação da solução inicial
12esol.second.print();
Now we give an example with of the most well-known metaheuristics: the Simulated Annealing.
It has few parameters, including: initial temperature T0
, cooling factor alpha
, and iterations per temperature iterT
.
1std::cout << "======== Executa Simulated Annealing ========" << std::endl;
2// Especifica um gerador aleatório para o Simulated Annealing
3RandGen rg;
4//
5// Cria objeto da classe 'InitialSearch' (parecido com 'construtivoAleatório')
6BasicInitialSearch<ESolutionKP> initRand(demo.randomConstructive, demo.evalKP);
7// Instancia um Simulated Annealing com alpha=98%, iterações na temp = 100,
8// temperatura inicial = 99999
9BasicSimulatedAnnealing<ESolutionKP> sa{
10 demo.evalKP, initRand, demo.nsFlip, 0.98, 100, 99999, rg};
11// executa o SA e coleta o 'status' de saída
12// passa um 'Criterio de Parada' por tempo (= 10 segundos)
13auto searchOut = sa.search(
14 StopCriteria<ESolutionKP::second_type>{10.0}); // 10.0 seconds max
15// pega melhor solução do método SA
16ESolutionKP melhor = *searchOut.best; //*sa.getBestSolution();
17std::cout << "======== Imprime melhor solução do SA ========" << std::endl;
18// imprime representação da melhor solução
19cout << melhor.first << endl;
20// imprime avaliação da melhor solução
21melhor.second.print();
Complete Example
Warning
We present a complete example below. Note that some small differences may exist due to updates in tutorial, including language details.
Feel free to check folder OptFrame/Examples
for other examples on FCore and OptFrame Classic.
Example is divided in two files: KP-fcore-ex.hpp
and mainKP-fcore-ex.cpp
.
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 KP-fcore-ex.hpp
)
from the main()
entrypoint (on mainKP-fcore-ex.cpp
), since unit testing is much simpler when these are decoupled.
KP-fcore-ex.hpp
File 'KP-fcore-ex.hpp' located in 'demo/02_QuickstartKP_SA/'
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 0-1 Knapsack Problem + Simulated Annealing
6// File: KP-fcore-ex.hpp
7#pragma once
8
9// C++
10#include <algorithm>
11#include <functional>
12#include <iostream>
13#include <utility>
14#include <vector>
15//
16#include <OptFCore/FCore.hpp>
17#include <OptFrame/Core.hpp>
18#include <OptFrame/Heuristics/Heuristics.hpp> // many metaheuristics here...
19#include <OptFrame/Scanner++/Scanner.hpp>
20#include <OptFrame/Util/Matrix.hpp>
21#include <OptFrame/printable/printable.hpp>
22
23using namespace std; // NOLINT
24using namespace optframe; // NOLINT
25using namespace scannerpp; // NOLINT
26
27// namespace para o problema da mochila
28// namespace KP_fcore {
29
30// Solução para o problema da mochila, e elemento de avaliação
31
32// ================================
33// Definição do 'ESolution'
34// Par: (Representação, Avaliação)
35// ================================
36
37using ESolutionKP = std::pair<std::vector<bool>, // (representation)
38 Evaluation<int> // (objective value)
39 >;
40class ProblemContext {
41 public:
42 int n{0}; // numero de itens
43 int Q{-1}; // capacidade máxima da mochila
44 vector<int> p; // lucro 'p' de cada item
45 vector<int> w; // peso 'w' de cada item
46 //
47 // leitor de dados "estilo Java" (Scanner)
48 void load(Scanner& scanner) {
49 n = *scanner.nextInt(); // leitura do numero de itens na mochila
50 Q = *scanner.nextInt(); // leitura da capacidade da mochila
51 p = vector<int>(n); // realoca espaço
52 w = vector<int>(n); // realoca espaço
53 //
54 cout << "n=" << n << " Q=" << Q << endl;
55 //
56 // leitura do lucro do item i
57 for (int i = 0; i < n; i++) {
58 p[i] =
59 *scanner.nextInt(); // '*' é usado pq saída do 'nextInt' é 'optional'
60 cout << "p[" << i << "]=" << p[i] << " ";
61 }
62 cout << endl;
63 //
64 // leitura do peso do item i
65 for (int i = 0; i < n; i++) {
66 w[i] =
67 *scanner.nextInt(); // '*' é usado pq saída do 'nextInt' é 'optional'
68 cout << "w[" << i << "]=" << w[i] << " ";
69 }
70 cout << endl;
71 }
72};
73// Instanciar um problema da mochila pKP
74// ProblemContext pKP; // NOLINT
75
76std::vector<bool> frandom(sref<ProblemContext> pKP) {
77 vector<bool> v(pKP->n, false); // começa sem nenhum item escolhido
78 for (unsigned i = 0; i < v.size(); i++)
79 v[i] = rand() % 2; // sorteia se leva item ou não (resultado 0 ou 1)
80 // retorna solução
81 return v;
82}
83
84// Gerador de solução inicial (método construtivo)
85// FConstructive<std::vector<bool>, ProblemContext> randomConstructive{pKP,
86// frandom};
87
88// ===========================
89// Função de avaliação
90// ===========================
91
92// função de avaliação da mochila
93Evaluation<int> fevaluate(sref<ProblemContext> pKP,
94 const std::vector<bool>& s) {
95 int f = 0;
96 int somaPeso = 0;
97 for (int i = 0; i < pKP->n; i++)
98 if (s[i]) // se elemento foi escolhido
99 {
100 f += pKP->p[i]; // acumula lucro do elemento i
101 somaPeso += pKP->w[i]; // acumula peso do elemento i
102 }
103 // verifica capacidade excedida
104 if (somaPeso >= pKP->Q)
105 f -= 1000000 *
106 (somaPeso - pKP->Q); // punição proporcional ao excesso de peso
107 //
108 return Evaluation<int>{f};
109}
110
111// Evaluate (false -> maximização)
112// FEvaluator<ESolutionKP, MAXIMIZE> evalKP{fevaluate};
113//
114class MoveBitFlip : public Move<ESolutionKP> {
115 public:
116 int k; // MoveBitFlip (moveData = 'int' (k))
117
118 explicit MoveBitFlip(int _k) : k{_k} {}
119
120 uptr<Move<ESolutionKP>> apply(ESolutionKP& se) override {
121 se.first[k] = !se.first[k]; // reverts element 'k'
122 return uptr<Move<ESolutionKP>>(new MoveBitFlip{k}); // returns reverse move
123 }
124};
125
126uptr<Move<ESolutionKP>> makeMoveBitFlip(int k) {
127 return uptr<Move<ESolutionKP>>(new MoveBitFlip{k});
128}
129// gerador de movimentos aleatórios do tipo BitFlip
130uptr<Move<ESolutionKP>> fRandomFlip(sref<ProblemContext> pKP,
131 const ESolutionKP& se) {
132 int k = ::rand() % pKP->n; // sorteia um item entre [0..n-1]
133 // cria um "movimento" de flip, na posição k, com operação 'fApplyFlip'
134 return uptr<Move<ESolutionKP>>(makeMoveBitFlip(k));
135}
136
137// Estrutura de Vizinhança para BitFlip (NS)
138// FNS<ESolutionKP> nsFlip{fRandomFlip};
139
140// ================== EVERYTHING TOGETHER ====================
141
142class OptFrameDemoKP {
143 public:
144 FConstructive<std::vector<bool>, ProblemContext> randomConstructive;
145 FEvaluator<ESolutionKP, MAXIMIZE, ProblemContext> evalKP;
146 FNS<ESolutionKP, ProblemContext> nsFlip;
147
148 explicit OptFrameDemoKP(sref<ProblemContext> p)
149 : randomConstructive{p, frandom},
150 evalKP{FEvaluator<ESolutionKP, MAXIMIZE, ProblemContext>{p, fevaluate}},
151 nsFlip{FNS<ESolutionKP, ProblemContext>{p, fRandomFlip}} {}
152};
mainKP-fcore-ex.cpp
File 'mainKP-fcore-ex.cpp' located in 'demo/02_QuickstartKP_SA/'
1// mainKP-fcore-ex.cpp
2
3// C++
4#include <iostream>
5
6//
7#include "KP-fcore-ex.hpp" // implementação da mochila
8
9// import everything on main()
10using namespace std; // NOLINT
11using namespace optframe; // NOLINT
12using namespace scannerpp; // NOLINT
13// using namespace KP_fcore;
14
15int main(int argc, char** argv) {std::cout << "======== Carregando Problema ========" << std::endl;
16// semente pseudo-aleatória fixa em zero
17srand(time(NULL));
18
19std::string sinstance = "knapsack-example.txt";
20File f{sinstance};
21
22if (!f.isOpen()) {
23 std::cerr << "Problema '" << sinstance << "' não encontrado no diretório!"
24 << std::endl;
25 return 1;
26}
27
28Scanner scanner{std::move(f)};
29
30sref<ProblemContext> pKP{new ProblemContext{}};
31pKP->load(scanner);
32std::cout << "número de elementos na mochila:" << pKP->n << std::endl;
33
34OptFrameDemoKP demo{pKP};
35std::cout << "======== Testa Construtivo Aleatório ========" << std::endl;
36// invoca método 'generateSolution' do FCore 'FConstructive' para construtivo
37// aleatório
38std::vector<bool> sol = *demo.randomConstructive.generateSolution(0.0);
39// imprime solução inicial
40std::cout << sol << std::endl;
41//
42std::cout << "======== Testa Avaliador ========" << std::endl;
43// avalia solução inicial e cria um par 'ESolution'
44ESolutionKP esol(sol, demo.evalKP.evaluate(sol));
45// imprime avaliação da solução inicial
46esol.second.print();
47
48std::cout << "======== Executa Simulated Annealing ========" << std::endl;
49// Especifica um gerador aleatório para o Simulated Annealing
50RandGen rg;
51//
52// Cria objeto da classe 'InitialSearch' (parecido com 'construtivoAleatório')
53BasicInitialSearch<ESolutionKP> initRand(demo.randomConstructive, demo.evalKP);
54// Instancia um Simulated Annealing com alpha=98%, iterações na temp = 100,
55// temperatura inicial = 99999
56BasicSimulatedAnnealing<ESolutionKP> sa{
57 demo.evalKP, initRand, demo.nsFlip, 0.98, 100, 99999, rg};
58// executa o SA e coleta o 'status' de saída
59// passa um 'Criterio de Parada' por tempo (= 10 segundos)
60auto searchOut = sa.search(
61 StopCriteria<ESolutionKP::second_type>{10.0}); // 10.0 seconds max
62// pega melhor solução do método SA
63ESolutionKP melhor = *searchOut.best; //*sa.getBestSolution();
64std::cout << "======== Imprime melhor solução do SA ========" << std::endl;
65// imprime representação da melhor solução
66cout << melhor.first << endl;
67// imprime avaliação da melhor solução
68melhor.second.print();
69
70
71std::cout << "======== Fim da Execução ========" << std::endl;
72return 0;
73} // main
knapsack-example.txt
File 'knapsack-example.txt' located in 'demo/02_QuickstartKP_SA/'
15
210
31 1 1 5 5
41 2 3 7 8
To compile it (generates binary app_KP):
g++ -g -O3 --std=c++20 -I../../include mainKP-fcore-ex.cpp -o app_KP