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