1//! @file optimal.hpp
2//! @author ryftchen
3//! @brief The declarations (optimal) in the algorithm module.
4//! @version 0.1.0
5//! @copyright Copyright (c) 2022-2025 ryftchen. All rights reserved.
6
7#pragma once
8
9#include <functional>
10#include <optional>
11#include <random>
12#include <unordered_set>
13
14//! @brief The algorithm module.
15namespace algorithm // NOLINT(modernize-concat-nested-namespaces)
16{
17//! @brief Optimal-related functions in the algorithm module.
18namespace optimal
19{
20//! @brief Brief function description.
21//! @return function description (module_function)
22inline static const char* description() noexcept
23{
24 return "ALGO_OPTIMAL";
25}
26extern const char* version() noexcept;
27
28//! @brief Target functions.
29using Function = std::function<double(const double)>;
30//! @brief The precision of calculation.
31inline constexpr double epsilon = 1e-5;
32
33//! @brief Optimal methods.
34class Optimal
35{
36public:
37 //! @brief Construct a new Optimal object.
38 Optimal() = default;
39 //! @brief Destroy the Optimal object.
40 virtual ~Optimal() = default;
41 //! @brief Construct a new Optimal object.
42 Optimal(const Optimal&) = default;
43 //! @brief Construct a new Optimal object.
44 Optimal(Optimal&&) noexcept = default;
45 //! @brief The operator (=) overloading of Optimal class.
46 //! @return reference of the Optimal object
47 Optimal& operator=(const Optimal&) = default;
48 //! @brief The operator (=) overloading of Optimal class.
49 //! @return reference of the Optimal object
50 Optimal& operator=(Optimal&&) noexcept = default;
51
52 //! @brief The operator (()) overloading of Optimal class.
53 //! @param left - left endpoint
54 //! @param right - right endpoint
55 //! @param eps - precision of calculation
56 //! @return result of optimal
57 virtual std::optional<std::tuple<double, double>> operator()(
58 const double left, const double right, const double eps) = 0;
59};
60
61//! @brief Gradient descent (GD).
62class Gradient : public Optimal
63{
64public:
65 //! @brief Construct a new Gradient object.
66 //! @param func - target function
67 //! @param initialLR - predefined initial learning rate
68 //! @param decay - predefined decay
69 //! @param loopTime - predefined loop time
70 explicit Gradient(
71 Function func, const double initialLR = 0.01, const double decay = 0.1, const std::uint32_t loopTime = 500) :
72 func{std::move(func)}, initialLR{initialLR}, decay{decay}, loopTime{loopTime}
73 {
74 }
75
76 //! @brief The operator (()) overloading of Gradient class.
77 //! @param left - left endpoint
78 //! @param right - right endpoint
79 //! @param eps - precision of calculation
80 //! @return result of optimal
81 std::optional<std::tuple<double, double>> operator()(
82 const double left, const double right, const double eps) override;
83
84private:
85 //! @brief Target function.
86 const Function func;
87 //! @brief Initial learning rate.
88 const double initialLR{0.01};
89 //! @brief Decay.
90 const double decay{0.1};
91 //! @brief Loop time.
92 const std::uint32_t loopTime{500};
93
94 //! @brief Create climbers.
95 //! @param left - left endpoint
96 //! @param right - right endpoint
97 //! @return collection of climbers
98 [[nodiscard]] std::unordered_multiset<double> createClimbers(const double left, const double right) const;
99 //! @brief Calculate the first derivative.
100 //! @param x - independent variable
101 //! @param eps - precision of calculation
102 //! @return value of the first derivative
103 [[nodiscard]] double calculateFirstDerivative(const double x, const double eps) const;
104};
105
106//! @brief Tabu search (TS).
107class Tabu : public Optimal
108{
109public:
110 //! @brief Construct a new Tabu object.
111 //! @param func - target function
112 //! @param tabuTenure - predefined tabu tenure
113 //! @param initialStep - predefined initial step length
114 //! @param expDecay - predefined exponential decay of step length
115 //! @param neighborSize - predefined neighborhood size
116 //! @param maxIterations - predefined maximum number of iterations
117 explicit Tabu(
118 Function func,
119 const std::uint32_t tabuTenure = 50,
120 const double initialStep = 1.0,
121 const double expDecay = 0.95,
122 const std::uint32_t neighborSize = 100,
123 const std::uint32_t maxIterations = 500) :
124 func{std::move(func)},
125 tabuTenure{tabuTenure},
126 initialStep{initialStep},
127 expDecay{expDecay},
128 neighborSize{neighborSize},
129 maxIterations{maxIterations}
130 {
131 }
132
133 //! @brief The operator (()) overloading of Tabu class.
134 //! @param left - left endpoint
135 //! @param right - right endpoint
136 //! @param eps - precision of calculation
137 //! @return result of optimal
138 std::optional<std::tuple<double, double>> operator()(
139 const double left, const double right, const double eps) override;
140
141private:
142 //! @brief Target function.
143 const Function func;
144 //! @brief Tabu tenure.
145 const std::uint32_t tabuTenure{50};
146 //! @brief Initial step length.
147 const double initialStep{1.0};
148 //! @brief Exponential decay of step length.
149 const double expDecay{0.95};
150 //! @brief Neighborhood size.
151 const std::uint32_t neighborSize{100};
152 //! @brief Maximum number of iterations.
153 const std::uint32_t maxIterations{500};
154
155 //! @brief Update the neighborhood.
156 //! @param neighborhood - neighborhood of solution
157 //! @param solution - current solution
158 //! @param stepLen - step length
159 //! @param left - left endpoint
160 //! @param right - right endpoint
161 void updateNeighborhood(
162 std::vector<double>& neighborhood,
163 const double solution,
164 const double stepLen,
165 const double left,
166 const double right) const;
167 //! @brief Neighborhood search.
168 //! @param neighborhood - neighborhood of solution
169 //! @param solution - current solution
170 //! @param tabuList - tabu list
171 //! @return best fitness and solution
172 std::tuple<double, double> neighborhoodSearch(
173 const std::vector<double>& neighborhood, const double solution, const std::vector<double>& tabuList);
174};
175
176//! @brief Simulated annealing (SA).
177class Annealing : public Optimal
178{
179public:
180 //! @brief Construct a new Annealing object.
181 //! @param func - target function
182 //! @param initialT - predefined initial temperature
183 //! @param minimalT - predefined minimal temperature
184 //! @param coolingRate - predefined cooling rate
185 //! @param markovChainLen - predefined length of Markov chain
186 explicit Annealing(
187 Function func,
188 const double initialT = 100.0,
189 const double minimalT = 0.01,
190 const double coolingRate = 0.99,
191 const std::uint32_t markovChainLen = 100) :
192 func{std::move(func)},
193 initialT{initialT},
194 minimalT{minimalT},
195 coolingRate{coolingRate},
196 markovChainLen{markovChainLen}
197 {
198 }
199
200 //! @brief The operator (()) overloading of Annealing class.
201 //! @param left - left endpoint
202 //! @param right - right endpoint
203 //! @param eps - precision of calculation
204 //! @return result of optimal
205 std::optional<std::tuple<double, double>> operator()(
206 const double left, const double right, const double eps) override;
207
208private:
209 //! @brief Target function.
210 const Function func;
211 //! @brief Initial temperature.
212 const double initialT{100.0};
213 //! @brief Minimal temperature.
214 const double minimalT{0.01};
215 //! @brief Cooling rate.
216 const double coolingRate{0.99};
217 //! @brief Length of Markov chain.
218 const std::uint32_t markovChainLen{100};
219
220 //! @brief Temperature-dependent Cauchy-like distribution.
221 //! @param prev - current model
222 //! @param min - minimum of model
223 //! @param max - maximum of model
224 //! @param temp - current temperature
225 //! @param xi - random number in the interval [0, 1]
226 //! @return new model
227 static double cauchyLikeDistribution(
228 const double prev, const double min, const double max, const double temp, const double xi);
229 //! @brief Metropolis acceptance criterion which based on the Metropolis-Hastings algorithm.
230 //! @param deltaE - energy difference
231 //! @param temp - current temperature
232 //! @param xi - random number in the interval [0, 1]
233 //! @return accept or not
234 static bool metropolisAcceptanceCriterion(const double deltaE, const double temp, const double xi);
235};
236
237//! @brief Particle swarm optimization (PSO).
238class Particle : public Optimal
239{
240public:
241 //! @brief Construct a new Particle object.
242 //! @param func - target function
243 //! @param c1 - predefined cognitive coefficient
244 //! @param c2 - predefined social coefficient
245 //! @param wBegin - predefined inertia weight beginning value
246 //! @param wEnd - predefined inertia weight ending value
247 //! @param vMax - predefined maximum velocity
248 //! @param vMin - predefined minimum velocity
249 //! @param swarmSize - predefined swarm size
250 //! @param maxIterations - predefined maximum number of iterations
251 explicit Particle(
252 Function func,
253 const double c1 = 1.5,
254 const double c2 = 1.5,
255 const double wBegin = 0.85,
256 const double wEnd = 0.35,
257 const double vMax = 0.5,
258 const double vMin = -0.5,
259 const std::uint32_t swarmSize = 100,
260 const std::uint32_t maxIterations = 100) :
261 func{std::move(func)},
262 c1{c1},
263 c2{c2},
264 wBegin{wBegin},
265 wEnd{wEnd},
266 vMax{vMax},
267 vMin{vMin},
268 swarmSize{swarmSize},
269 maxIterations{maxIterations}
270 {
271 }
272
273 //! @brief The operator (()) overloading of Particle class.
274 //! @param left - left endpoint
275 //! @param right - right endpoint
276 //! @param eps - precision of calculation
277 //! @return result of optimal
278 std::optional<std::tuple<double, double>> operator()(
279 const double left, const double right, const double eps) override;
280
281private:
282 //! @brief Target function.
283 const Function func;
284 //! @brief Cognitive coefficient.
285 const double c1{1.5};
286 //! @brief Social coefficient.
287 const double c2{1.5};
288 //! @brief Inertia weight beginning value.
289 const double wBegin{0.85};
290 //! @brief Inertia weight ending value.
291 const double wEnd{0.35};
292 //! @brief Maximum velocity.
293 const double vMax{0.5};
294 //! @brief Minimum velocity.
295 const double vMin{-0.5};
296 //! @brief Swarm size.
297 const std::uint32_t swarmSize{100};
298 //! @brief Maximum number of iterations.
299 const std::uint32_t maxIterations{100};
300 //! @brief Random engine.
301 std::mt19937_64 engine{std::random_device{}()};
302 //! @brief The perturbation for the coefficient (from 0 to 1).
303 std::uniform_real_distribution<double> perturbation{0.0, 1.0};
304
305 //! @brief Individual information in the swarm.
306 struct Individual
307 {
308 //! @brief Position vector.
309 double x{0.0};
310 //! @brief Velocity vector.
311 double v{0.0};
312 //! @brief Personal best position.
313 double persBest{0.0};
314 //! @brief Fitness of the position vector.
315 double fitness{0.0};
316 //! @brief Fitness of the personal best position.
317 double persBestFitness{0.0};
318 };
319 //! @brief Alias for the swarm information.
320 using Swarm = std::vector<Individual>;
321 //! @brief Initialize the swarm.
322 //! @param left - left endpoint
323 //! @param right - right endpoint
324 //! @return initial swarm
325 Swarm swarmInit(const double left, const double right);
326 //! @brief Update the velocity and position of each particle in the swarm.
327 //! @param swarm - particle swarm
328 //! @param iteration - current number of iterations
329 //! @param gloBest - global best position
330 //! @param left - left endpoint
331 //! @param right - right endpoint
332 //! @param eps - precision of calculation
333 void updateParticles(
334 Swarm& swarm,
335 const std::uint32_t iteration,
336 const double gloBest,
337 const double left,
338 const double right,
339 const double eps);
340 //! @brief Non-linear decreasing weight.
341 //! @param iteration - current number of iterations
342 //! @return inertia weight
343 [[nodiscard]] double nonlinearDecreasingWeight(const std::uint32_t iteration) const;
344 //! @brief Update the personal best position of each particle in the swarm and the global best position.
345 //! @param swarm - particle swarm
346 //! @param gloBest - global best position
347 //! @param gloBestFitness - fitness of the global best position
348 static void updateBests(Swarm& swarm, double& gloBest, double& gloBestFitness);
349};
350
351//! @brief Ant colony optimization (ACO).
352class Ant : public Optimal
353{
354public:
355 //! @brief Construct a new Ant object.
356 //! @param func - target function
357 //! @param rho - predefined pheromone evaporation rate
358 //! @param p0 - predefined exploration probability
359 //! @param initialStep - predefined initial step length
360 //! @param numOfAnts - predefined number of ants
361 //! @param maxIterations - predefined maximum number of iterations
362 explicit Ant(
363 Function func,
364 const double rho = 0.9,
365 const double p0 = 0.2,
366 const double initialStep = 1.0,
367 const std::uint32_t numOfAnts = 500,
368 const std::uint32_t maxIterations = 100) :
369 func{std::move(func)},
370 rho{rho},
371 p0{p0},
372 initialStep{initialStep},
373 numOfAnts{numOfAnts},
374 maxIterations{maxIterations}
375 {
376 }
377
378 //! @brief The operator (()) overloading of Ant class.
379 //! @param left - left endpoint
380 //! @param right - right endpoint
381 //! @param eps - precision of calculation
382 //! @return result of optimal
383 std::optional<std::tuple<double, double>> operator()(
384 const double left, const double right, const double eps) override;
385
386private:
387 //! @brief Target function.
388 const Function func;
389 //! @brief Pheromone evaporation rate.
390 const double rho{0.9};
391 //! @brief Exploration probability.
392 const double p0{0.2};
393 //! @brief Initial step length.
394 const double initialStep{1.0};
395 //! @brief Number of ants.
396 const std::uint32_t numOfAnts{500};
397 //! @brief Maximum number of iterations.
398 const std::uint32_t maxIterations{100};
399 //! @brief Random engine.
400 std::mt19937_64 engine{std::random_device{}()};
401 //! @brief Coefficient of the step length for the local search.
402 std::uniform_real_distribution<double> localCoeff{-1.0, 1.0};
403 //! @brief Coefficient of the range for the global search.
404 std::uniform_real_distribution<double> globalCoeff{-0.5, 0.5};
405
406 //! @brief State of the ant in the colony.
407 struct State
408 {
409 //! @brief Position coordinate.
410 double position{0.0};
411 //! @brief Pheromone intensity level.
412 double pheromone{0.0};
413 //! @brief Transition probability.
414 double transPr{0.0};
415 };
416 //! @brief Alias for the colony information.
417 using Colony = std::vector<State>;
418 //! @brief Initialize the colony.
419 //! @param left - left endpoint
420 //! @param right - right endpoint
421 //! @return initial colony
422 Colony colonyInit(const double left, const double right);
423 //! @brief Perform the state transition for each ant in the colony.
424 //! @param colony - ant colony
425 //! @param eps - precision of calculation
426 static void stateTransition(Colony& colony, const double eps);
427 //! @brief Construct the paths of the ants in the search space.
428 //! @param colony - ant colony
429 //! @param stepLen - step length
430 //! @param left - left endpoint
431 //! @param right - right endpoint
432 void pathConstruction(Colony& colony, const double stepLen, const double left, const double right);
433 //! @brief Update the pheromone intensity levels.
434 //! @param colony - ant colony
435 void updatePheromones(Colony& colony);
436};
437
438//! @brief Genetic algorithm (GA).
439class Genetic : public Optimal
440{
441public:
442 //! @brief Construct a new Genetic object.
443 //! @param func - target function
444 //! @param crossPr - predefined crossover probability
445 //! @param mutatePr - predefined mutation probability
446 //! @param popSize - predefined population size
447 //! @param numOfGenerations - predefined number of generations
448 explicit Genetic(
449 Function func,
450 const double crossPr = 0.7,
451 const double mutatePr = 0.001,
452 const std::uint32_t popSize = 500,
453 const std::uint32_t numOfGenerations = 10) :
454 func{std::move(func)},
455 crossPr{crossPr},
456 mutatePr{mutatePr},
457 popSize{popSize},
458 numOfGenerations{numOfGenerations}
459 {
460 }
461
462 //! @brief The operator (()) overloading of Genetic class.
463 //! @param left - left endpoint
464 //! @param right - right endpoint
465 //! @param eps - precision of calculation
466 //! @return result of optimal
467 std::optional<std::tuple<double, double>> operator()(
468 const double left, const double right, const double eps) override;
469
470private:
471 //! @brief Target function.
472 const Function func;
473 //! @brief Crossover probability.
474 const double crossPr{0.7};
475 //! @brief Mutation probability.
476 const double mutatePr{0.001};
477 //! @brief Population size.
478 const std::uint32_t popSize{500};
479 //! @brief Number of generations.
480 const std::uint32_t numOfGenerations{10};
481 //! @brief Random engine.
482 std::mt19937_64 engine{std::random_device{}()};
483 //! @brief The probability of a possible event (from 0 to 1).
484 std::uniform_real_distribution<double> probability{0.0, 1.0};
485 //! @brief The linear scaling coefficient.
486 static constexpr double cMult{1.01};
487 //! @brief Minimum length of chromosome.
488 static constexpr std::uint32_t minChrLen{2};
489 //! @brief Length of chromosome.
490 std::uint32_t chromosomeLen{0};
491 //! @brief Properties of species.
492 struct Property
493 {
494 //! @brief Left endpoint.
495 double lower{0.0};
496 //! @brief Right endpoint.
497 double upper{0.0};
498 //! @brief The precision of calculation.
499 double prec{0.0};
500 } /** @brief A Property object for storing properties of species. */ property{};
501
502 //! @brief Update species.
503 //! @param left - left endpoint
504 //! @param right - right endpoint
505 //! @param eps - precision of calculation
506 //! @return success or failure
507 bool updateSpecies(const double left, const double right, const double eps);
508 //! @brief Alias for the individual's chromosome in species.
509 using Chromosome = std::vector<std::uint8_t>;
510 //! @brief Alias for the population in species.
511 using Population = std::vector<Chromosome>;
512 //! @brief The genetic decode.
513 //! @param chr - individual's chromosome
514 //! @return decoded value
515 [[nodiscard]] double geneticDecode(const Chromosome& chr) const;
516 //! @brief Initialize the population with binary.
517 //! @return initial population
518 Population populationInit();
519 //! @brief The genetic cross.
520 //! @param chr1 - chromosome from one of the parents
521 //! @param chr2 - chromosome from one of the parents
522 void geneticCross(Chromosome& chr1, Chromosome& chr2);
523 //! @brief Chromosomal crossover in the population.
524 //! @param pop - whole population
525 void crossover(Population& pop);
526 //! @brief The genetic mutation.
527 //! @param chr - individual's chromosome
528 void geneticMutation(Chromosome& chr);
529 //! @brief Chromosomal mutation in the population.
530 //! @param pop - whole population
531 void mutate(Population& pop);
532 //! @brief Calculate the fitness of the individual.
533 //! @param chr - individual's chromosome
534 //! @return fitness of the individual
535 double calculateFitness(const Chromosome& chr);
536 //! @brief The Goldberg linear scaling.
537 //! @param fitness - original fitness
538 //! @param eps - precision of calculation
539 //! @return coefficient of the linear transformation
540 static std::optional<std::pair<double, double>> goldbergLinearScaling(
541 const std::vector<double>& fitness, const double eps);
542 //! @brief The roulette wheel selection.
543 //! @param pop - whole population
544 //! @param cumFitness - cumulative fitness
545 //! @return selected competitor
546 auto rouletteWheelSelection(const Population& pop, const std::vector<double>& cumFitness);
547 //! @brief The stochastic tournament selection.
548 //! @param pop - whole population
549 //! @param cumFitness - cumulative fitness
550 void stochasticTournamentSelection(Population& pop, const std::vector<double>& cumFitness);
551 //! @brief The genetic selection.
552 //! @param pop - whole population
553 void select(Population& pop);
554 //! @brief Get the best individual.
555 //! @param pop - whole population
556 //! @return the best individual's chromosome
557 Chromosome getBestIndividual(const Population& pop);
558};
559} // namespace optimal
560} // namespace algorithm
561