Code Coverage
 
Lines
Functions and Methods
Classes and Traits
Total
0.00% covered (danger)
0.00%
0 / 25
0.00% covered (danger)
0.00%
0 / 1
 CRAP
0.00% covered (danger)
0.00%
0 / 1
TabuSearch
0.00% covered (danger)
0.00%
0 / 25
0.00% covered (danger)
0.00%
0 / 1
 132
0.00% covered (danger)
0.00%
0 / 1
 __construct
n/a
0 / 0
n/a
0 / 0
 1
 optimize
0.00% covered (danger)
0.00%
0 / 25
0.00% covered (danger)
0.00%
0 / 1
 110
1<?php
2/**
3 * Jingga
4 *
5 * PHP Version 8.1
6 *
7 * @package   phpOMS\Algorithm\Optimization
8 * @copyright Dennis Eichhorn
9 * @license   OMS License 2.0
10 * @version   1.0.0
11 * @link      https://jingga.app
12 */
13declare(strict_types=1);
14
15namespace phpOMS\Algorithm\Optimization;
16
17/**
18 * Perform tabu search.
19 *
20 * @package phpOMS\Algorithm\Optimization
21 * @license OMS License 2.0
22 * @link    https://jingga.app
23 * @since   1.0.0
24 */
25class TabuSearch
26{
27    /**
28     * Constructor
29     *
30     * @since 1.0.0
31     * @codeCoverageIgnore
32     */
33    private function __construct()
34    {
35    }
36
37    /*
38    // Define your fitness function here
39    public static function fitness($solution) {
40        // Calculate and return the fitness of the solution
41        // This function should be tailored to your specific problem
42        return $solution;
43    }
44
45    // Define your neighborhood generation function here
46    public static function generateNeighbor($currentSolution) {
47        // Generate a neighboring solution based on the current solution
48        // This function should be tailored to your specific problem
49        return $currentSolution;
50    }
51    */
52
53    /**
54     * Perform optimization
55     *
56     * @example See unit test for example use case
57     *
58     * @param array    $initialSolution List of all elements with ther parameters (i.e. list of "objects" as arrays).
59     *                                  The constraints are defined as array values.
60     * @param \Closure $fitness         Fitness function calculates score/feasability of solution
61     * @param \Closure $neighbor        Neighbor function to find a new solution/neighbor
62     * @param int      $tabuListSize    ????
63     * @param int      $iterations      Number of iterations
64     *
65     * @return array
66     *
67     * @since 1.0.0
68     */
69    public static function optimize(
70        array $initialSolution,
71        \Closure $fitness,
72        \Closure $neighbor,
73        int $tabuListSize,
74        int $iterations
75    ) : array
76    {
77        $currentSolution = $initialSolution;
78        $bestSolution    = $currentSolution;
79        $bestFitness     = \PHP_FLOAT_MIN;
80        $tabuList        = [];
81
82        for ($i = 0; $i < $iterations; ++$i) {
83            $neighbors = [];
84            for ($j = 0; $j < $tabuListSize; ++$j) {
85                $neighbor    = ($neighbor)($currentSolution);
86                $neighbors[] = $neighbor;
87            }
88
89            $bestNeighbor = null;
90            foreach ($neighbors as $neighbor) {
91                if (!\in_array($neighbor, $tabuList) &&
92                    ($bestNeighbor === null
93                        || ($fitness)($neighbor) > ($fitness)($bestNeighbor))
94                ) {
95                    $bestNeighbor = $neighbor;
96                }
97            }
98
99            if ($bestNeighbor === null) {
100                break;
101            }
102
103            $tabuList[] = $bestNeighbor;
104            if (\count($tabuList) > $tabuListSize) {
105                \array_shift($tabuList);
106            }
107
108            $currentSolution = $bestNeighbor;
109
110            if (($score = ($fitness)($bestNeighbor)) > $bestFitness) {
111                $bestSolution = $bestNeighbor;
112                $bestFitness  = $score;
113            }
114        }
115
116        return $bestSolution;
117    }
118}