Code Coverage
 
Lines
Functions and Methods
Classes and Traits
Total
0.00% covered (danger)
0.00%
0 / 30
0.00% covered (danger)
0.00%
0 / 1
 CRAP
0.00% covered (danger)
0.00%
0 / 1
GeneticOptimization
0.00% covered (danger)
0.00%
0 / 30
0.00% covered (danger)
0.00%
0 / 1
 90
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 / 30
0.00% covered (danger)
0.00%
0 / 1
 72
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 genetic algorithm (GA).
19 *
20 * @package phpOMS\Algorithm\Optimization
21 * @license OMS License 2.0
22 * @link    https://jingga.app
23 * @since   1.0.0
24 */
25class GeneticOptimization
26{
27    /**
28     * Constructor
29     *
30     * @since 1.0.0
31     * @codeCoverageIgnore
32     */
33    private function __construct()
34    {
35    }
36
37    /*
38    // Fitness function (may require to pass solution space as \Closure variable)
39    // E.g.
40    // highest value of some sorts (e.g. profit)
41    // most elements (e.g. jobs)
42    // lowest costs
43    // combination of criteria = points (where some criteria are mandatory/optional)
44    public static function fitness($x)
45    {
46        return $x;
47    }
48
49    public static function mutate($parameters, $mutationRate)
50    {
51        for ($i = 0; $i < \count($parameters); $i++) {
52            if (\mt_rand(0, 1000) / 1000 < $mutationRate) {
53                $parameters[$i] = 1 - $parameters[$i];
54            }
55        }
56
57        return $parameters;
58    }
59
60    public static function crossover($parent1, $parent2, $parameterCount)
61    {
62        $crossoverPoint = \mt_rand(1, $parameterCount - 1);
63
64        $child1 = \array_merge(
65            \array_slice($parent1, 0, $crossoverPoint),
66            \array_slice($parent2, $crossoverPoint)
67        );
68
69        $child2 = \array_merge(
70            \array_slice($parent2, 0, $crossoverPoint),
71            \array_slice($parent1, $crossoverPoint)
72        );
73
74        return [$child1, $child2];
75    }
76    */
77
78    /**
79     * Perform optimization
80     *
81     * @example See unit test for example use case
82     *
83     * @param array<array> $population   List of all elements with ther parameters (i.e. list of "objects" as arrays).
84     *                                   The constraints are defined as array values.
85     * @param \Closure     $fitness      Fitness function calculates score/feasability of solution
86     * @param \Closure     $mutate       Mutation function to change the parameters of an "object"
87     * @param \Closure     $crossover    Crossover function to exchange parameter values between "objects".
88     *                                   Sometimes single parameters can be exchanged but sometimes interdependencies exist between parameters which is why this function is required.
89     * @param int          $generations  Number of generations to create
90     * @param float        $mutationRate Rate at which parameters are changed.
91     *                                   How this is used depends on the mutate function.
92     *
93     * @return array{solutions:array, fitnesses:float[]}
94     *
95     * @since 1.0.0
96     */
97    public static function optimize(
98        array $population,
99        \Closure $fitness,
100        \Closure $mutate,
101        \Closure $crossover,
102        int $generations = 500,
103        float $mutationRate = 0.1
104    ) : array
105    {
106        $populationSize = \count($population);
107        $parameterCount = $populationSize === 0 ? 0 : \count(\reset($population));
108
109        // Genetic Algorithm Loop
110        for ($generation = 0; $generation < $generations; ++$generation) {
111            $fitnessScores = [];
112            foreach ($population as $parameters) {
113                $fitnessScores[] = ($fitness)($parameters);
114            }
115
116            // Select parents for crossover based on fitness scores
117            $parents = [];
118            for ($i = 0; $i < $populationSize; ++$i) {
119                do {
120                    $parentIndex1 = \array_rand($population);
121                    $parentIndex2 = \array_rand($population);
122                } while ($parentIndex1 === $parentIndex2);
123
124                $parents[] = $fitnessScores[$parentIndex1] > $fitnessScores[$parentIndex2]
125                    ? $population[$parentIndex1]
126                    : $population[$parentIndex2];
127            }
128
129            // Crossover and mutation to create next generation
130            $newPopulation = [];
131            for ($i = 0; $i < $populationSize; $i += 2) {
132                $crossover = ($crossover)($parents[$i], $parents[$i + 1], $parameterCount);
133
134                $child1 = ($mutate)($crossover[0], $mutationRate);
135                $child2 = ($mutate)($crossover[1], $mutationRate);
136
137                $newPopulation[] = $child1;
138                $newPopulation[] = $child2;
139            }
140
141            $population = $newPopulation;
142        }
143
144        $fitnesses = [];
145
146        foreach ($population as $key => $parameters) {
147            $fitnesses[$key] = ($fitness)($parameters);
148        }
149
150        \asort($fitnesses);
151
152        return [
153            'solutions' => $population,
154            'fitnesses' => $fitnesses,
155        ];
156    }
157}