مانند مکالمه در استخر 🎱 به من آموخت که چگونه برنامه هایی را با الگوریتم های ژنتیکی تنظیم کنم 🧬 در PHP

namespace App\Services;

class GeneticAlgorithmService
{
    private array $items;
    private array $constraints;
    private string $objectiveAttribute;
    private string $objectiveGoal; // 'maximize' ou 'minimize'
    private int $populationSize;
    private int $generations;
    private float $mutationRate;
    private float $eliteRate;

    private array $population = [];

    public function __construct(object $config)
    {
        $this->items = $config->items;
        $this->constraints = $config->constraints;
        $this->objectiveAttribute = $config->objective->attribute;
        $this->objectiveGoal = $config->objective->goal;
        $this->populationSize = $config->populationSize;
        $this->generations = $config->generations;
        $this->mutationRate = $config->mutationRate;
        $this->eliteRate = $config->eliteRate;
    }

    // Executa o algoritmo e retorna a lista de itens selecionados
    public function run(): array
    {
        $this->initializePopulation();

        for ($gen = 0; $gen < $this->generations; $gen++) {
            $fitnessScores = $this->evaluatePopulation();

            $elite = $this->selectElite($fitnessScores);

            $newPopulation = $elite;

            while (count($newPopulation) < $this->populationSize) {
                $parent1 = $this->tournamentSelection($fitnessScores);
                $parent2 = $this->tournamentSelection($fitnessScores);

                $child = $this->crossover($parent1, $parent2);
                $this->mutate($child);

                if ($this->checkConstraints($child)) {
                    $newPopulation[] = $child;
                }
            }

            $this->population = $newPopulation;
        }

        $finalFitness = $this->evaluatePopulation();
        $bestIndex = $this->getBestIndex($finalFitness);

        return $this->decodeChromosome($this->population[$bestIndex]);
    }

    // Inicializa população com cromossomos aleatórios
    private function initializePopulation(): void
    {
        $this->population = [];
        $numItems = count($this->items);

        for ($i = 0; $i < $this->populationSize; $i++) {
            $chromosome = [];

            for ($j = 0; $j < $numItems; $j++) {
                // 0 ou 1 para representar se o item está selecionado
                $chromosome[] = rand(0, 1);
            }

            // Garante que o cromossomo respeite as restrições
            if ($this->checkConstraints($chromosome)) {
                $this->population[] = $chromosome;
            } else {
                // Caso não respeite, tenta gerar outro até encontrar válido
                $i--;
            }
        }
    }

    // Avalia fitness de cada indivíduo na população
    private function evaluatePopulation(): array
    {
        $fitnessScores = [];

        foreach ($this->population as $chromosome) {
            $fitnessScores[] = $this->fitness($chromosome);
        }

        return $fitnessScores;
    }

    // Função fitness que calcula a pontuação do cromossomo
    private function fitness(array $chromosome): float
    {
        $totalObjective = 0;

        foreach ($chromosome as $index => $gene) {
            if ($gene === 1) {
                $totalObjective += $this->items[$index][$this->objectiveAttribute];
            }
        }

        return $totalObjective;
    }

    // Seleciona os melhores indivíduos (elite) para a próxima geração
    private function selectElite(array $fitnessScores): array
    {
        $numElite = (int) round($this->populationSize * $this->eliteRate);

        // Associa fitness ao índice para ordenar
        $indexedFitness = array_map(fn($score, $i) => ['score' => $score, 'index' => $i], $fitnessScores, array_keys($fitnessScores));

        usort($indexedFitness, function($a, $b) {
            if ($this->objectiveGoal === 'maximize') {
                return $b['score'] <=> $a['score'];
            }
            return $a['score'] <=> $b['score'];
        });

        $elite = [];
        for ($i = 0; $i < $numElite; $i++) {
            $elite[] = $this->population[$indexedFitness[$i]['index']];
        }

        return $elite;
    }

    // Torneio para selecionar um cromossomo (parent)
    private function tournamentSelection(array $fitnessScores): array
    {
        $tournamentSize = 3;
        $candidates = [];

        $populationCount = count($this->population);

        for ($i = 0; $i < $tournamentSize; $i++) {
            $randomIndex = rand(0, $populationCount - 1);
            $candidates[] = ['chromosome' => $this->population[$randomIndex], 'fitness' => $fitnessScores[$randomIndex]];
        }

        usort($candidates, function($a, $b) {
            if ($this->objectiveGoal === 'maximize') {
                return $b['fitness'] <=> $a['fitness'];
            }
            return $a['fitness'] <=> $b['fitness'];
        });

        return $candidates[0]['chromosome'];
    }

    // Crossover simples: um ponto de corte
    private function crossover(array $parent1, array $parent2): array
    {
        $length = count($parent1);
        $cut = rand(1, $length - 2);

        return array_merge(
            array_slice($parent1, 0, $cut),
            array_slice($parent2, $cut)
        );
    }

    // Mutação com probabilidade definida
    private function mutate(array &$chromosome): void
    {
        for ($i = 0; $i < count($chromosome); $i++) {
            if (rand() / getrandmax() < $this->mutationRate) {
                $chromosome[$i] = $chromosome[$i] === 1 ? 0 : 1;
            }
        }
    }

    // Verifica se o cromossomo respeita as restrições
    private function checkConstraints(array $chromosome): bool
    {
        foreach ($this->constraints as $constraint) {
            $attribute = $constraint->attribute;
            $max = $constraint->max;

            $total = 0;
            foreach ($chromosome as $index => $gene) {
                if ($gene === 1) {
                    $total += $this->items[$index][$attribute];
                }
            }

            if ($total > $max) {
                return false;
            }
        }
        return true;
    }

    // Retorna o índice do melhor cromossomo baseado no fitness
    private function getBestIndex(array $fitnessScores): int
    {
        if ($this->objectiveGoal === 'maximize') {
            return array_keys($fitnessScores, max($fitnessScores))[0];
        }
        return array_keys($fitnessScores, min($fitnessScores))[0];
    }

    // Decodifica o cromossomo para retornar os itens selecionados
    private function decodeChromosome(array $chromosome): array
    {
        $selected = [];
        foreach ($chromosome as $index => $gene) {
            if ($gene === 1) {
                $selected[] = $this->items[$index];
            }
        }
        return $selected;
    }
}