Code Coverage |
||||||||||
Lines |
Functions and Methods |
Classes and Traits |
||||||||
| Total | |
0.00% |
0 / 15 |
|
0.00% |
0 / 1 |
CRAP | |
0.00% |
0 / 1 |
| SimulatedAnnealing | |
0.00% |
0 / 15 |
|
0.00% |
0 / 1 |
30 | |
0.00% |
0 / 1 |
| __construct | n/a |
0 / 0 |
n/a |
0 / 0 |
1 | |||||
| optimize | |
0.00% |
0 / 15 |
|
0.00% |
0 / 1 |
20 | |||
| 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 | */ |
| 13 | declare(strict_types=1); |
| 14 | |
| 15 | namespace phpOMS\Algorithm\Optimization; |
| 16 | |
| 17 | /** |
| 18 | * Perform simulated annealing (SA). |
| 19 | * |
| 20 | * @package phpOMS\Algorithm\Optimization |
| 21 | * @license OMS License 2.0 |
| 22 | * @link https://jingga.app |
| 23 | * @since 1.0.0 |
| 24 | */ |
| 25 | class SimulatedAnnealing |
| 26 | { |
| 27 | /** |
| 28 | * Constructor |
| 29 | * |
| 30 | * @since 1.0.0 |
| 31 | * @codeCoverageIgnore |
| 32 | */ |
| 33 | private function __construct() |
| 34 | { |
| 35 | } |
| 36 | |
| 37 | /* |
| 38 | public static function costFunction($x) |
| 39 | { |
| 40 | return $x; |
| 41 | } |
| 42 | |
| 43 | // can be many things, e.g. swapping parameters, increasing/decrising, random generation |
| 44 | public static function neighbor(array $generation, $parameterCount) |
| 45 | { |
| 46 | $newGeneration = $generation; |
| 47 | $randomIndex1 = \mt_rand(0, $parameterCount - 1); |
| 48 | $randomIndex2 = \mt_rand(0, $parameterCount - 1); |
| 49 | |
| 50 | // Swap two cities in the route |
| 51 | $temp = $newGeneration[$randomIndex1]; |
| 52 | $newGeneration[$randomIndex1] = $newGeneration[$randomIndex2]; |
| 53 | $newGeneration[$randomIndex2] = $temp; |
| 54 | |
| 55 | return $newGeneration; |
| 56 | } |
| 57 | */ |
| 58 | |
| 59 | // Simulated Annealing algorithm |
| 60 | // @todo allow to create a solution space (currently all soluctions need to be in space) |
| 61 | // @todo: currently only replacing generations, not altering them |
| 62 | /** |
| 63 | * Perform optimization |
| 64 | * |
| 65 | * @example See unit test for example use case |
| 66 | * |
| 67 | * @param array $space List of all elements with ther parameters (i.e. list of "objects" as arrays). |
| 68 | * The constraints are defined as array values. |
| 69 | * @param int $initialTemperature Starting temperature |
| 70 | * @param \Closure $costFunction Fitness function calculates score/feasability of solution |
| 71 | * @param \Closure $neighbor Neighbor function to find a new solution/neighbor |
| 72 | * @param float $coolingRate Rate at which cooling takes place |
| 73 | * @param int $iterations Number of iterations |
| 74 | * |
| 75 | * @return array{solutions:array, costs:float[]} |
| 76 | * |
| 77 | * @since 1.0.0 |
| 78 | */ |
| 79 | public function optimize( |
| 80 | array $space, |
| 81 | int $initialTemperature, |
| 82 | \Closure $costFunction, |
| 83 | \Closure $neighbor, |
| 84 | float $coolingRate = 0.98, |
| 85 | int $iterations = 1000 |
| 86 | ) : array |
| 87 | { |
| 88 | $parameterCount = \count($space); |
| 89 | $currentGeneration = \reset($space); |
| 90 | |
| 91 | $currentCost = ($costFunction)($currentGeneration); |
| 92 | |
| 93 | for ($i = 0; $i < $iterations; ++$i) { |
| 94 | $newGeneration = ($neighbor)($currentGeneration, $parameterCount); |
| 95 | |
| 96 | $newCost = ($costFunction)($newGeneration); |
| 97 | |
| 98 | $temperature = $initialTemperature * \pow($coolingRate, $i); |
| 99 | |
| 100 | if ($newCost < $currentCost |
| 101 | || \mt_rand() / \mt_getrandmax() < \exp(($currentCost - $newCost) / $temperature) |
| 102 | ) { |
| 103 | $currentGeneration = $newGeneration; |
| 104 | $currentCost = $newCost; |
| 105 | } |
| 106 | } |
| 107 | |
| 108 | return [ |
| 109 | 'solutions' => $currentGeneration, |
| 110 | 'costs' => $currentCost, |
| 111 | ]; |
| 112 | } |
| 113 | } |