Rômulo Mendes Soares Junior

Posted on May 30

How a Pool Game 🎱 Taught Me to Build Smart Schedules Using Genetic Algorithms 🧬 in PHP

#php #ai #geneticalgorithms #optimization

The other day, I went out to relax and play a game of pool with my friend Romane.

In the middle of the game, he said:

“I thought I was clever—I just made a genetic search function!”

I thought he was joking… until he told me he built a function called buscaGenetica() that actually solved a real problem: paying bills with a limited budget.

💸 The Bill-Paying Problem

“Imagine a user provides an array of bills, each with an id and amount, and says they have $1,000 to pay as many as possible.”

He was using genetic algorithms to find the best possible combination under that constraint.

🧬 How Does Genetic Search Work?

His explanation sounded like science fiction:

💑 The bills “mated” with each other to produce new combinations.
🧟 Some generations had mutations, like swapped bills—what he jokingly called “genetic anomalies” (or "cancers" 😅).
👑 The best combinations survived into the next generation.
🧠 And this repeated for 100 generations, until the best solution emerged: the maximum number of bills paid with $1,000.

I was hooked. The concept was brilliant.

⏰ My Real-World Problem: Scheduling Availability

On the way home, I couldn’t stop thinking about it.

I’d been struggling with a problem in my own system:

I have several professionals with different skills (bathing, grooming, trimming), and I need to fill time slots with the best-suited professionals, without overlaps.

Then it clicked:

What if I applied Romane’s genetic algorithm to build that schedule?

I turned his logic into a PHP service called GeneticAlgorithmService.

💻 Implementing It in PHP

The GeneticAlgorithmService class is generic and takes a configuration object. It handles the entire evolution process under the hood:

use App\Services\GeneticAlgorithmService;

$config = [
    "items" => [
        ["id" => 1, "weight" => 10, "height" => 50, "value" => 60],
        ["id" => 2, "weight" => 20, "height" => 60, "value" => 100],
        ["id" => 3, "weight" => 30, "height" => 70, "value" => 120],
    ],
    "constraints" => [
        ["attribute" => "weight", "max" => 50],
        ["attribute" => "height", "max" => 110],
    ],
    "objective" => ["attribute" => "value", "goal" => "maximize"],
    "populationSize" => 50,
    "generations" => 100,
    "mutationRate" => 0.05,
    "eliteRate" => 0.2,
];

$configObject = json_decode(json_encode($config), false);
$service = new GeneticAlgorithmService($configObject);
$result = $service->run();

echo "Best combination found:\n";
print_r($result);

📥 Input (Configuration)

You define:

items: the data set (time slots, bills, tasks, etc.)
constraints: restrictions (e.g. max weight, time, height)
objective: which attribute to maximize or minimize
Genetic parameters: population size, number of generations, mutation rate, elite rate

📤 Output

The run() method returns something like:

[
    ['id' => 2, 'weight' => 20, 'height' => 60, 'value' => 100],
    ['id' => 1, 'weight' => 10, 'height' => 50, 'value' => 60]
]

In other words, the best possible combination based on your rules.

⚙️ What the Algorithm Does Under the Hood

The GeneticAlgorithmService internally runs:

Generates an initial population (random combinations)
Evaluates “fitness” (how good each combination is)
Selects top performers (elitism)
Crosses candidates (reproduction)
Randomly mutates offspring
Repeats this process across generations

✅ Why Does This Work So Well?

Because it’s flexible. With this pattern, you can solve:

Scheduling conflicts
Task prioritization
Resource allocation
Any combinatorial optimization problem

⚙️ The Full Algorithm

The complete source code for GeneticAlgorithmService is available in the full post. Feel free to adapt it to your own needs!

use Illuminate\Support\Collection;

class GeneticAlgorithmService
{
    private array $items;
    private array $constraints;
    private string $objectiveAttribute;
    private string $objectiveGoal; // 'maximize' or '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;
    }

    // Runs the algorithm and returns the selected items
    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]);
    }

    // Initializes the population with random chromosomes
    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 or 1 to represent if the item is selected
                $chromosome[] = rand(0, 1);
            }

            // Ensure the chromosome respects all constraints
            if ($this->checkConstraints($chromosome)) {
                $this->population[] = $chromosome;
            } else {
                // If not, retry until a valid one is generated
                $i--;
            }
        }
    }

    // Evaluates the fitness of each individual in the population
    private function evaluatePopulation(): array
    {
        $fitnessScores = [];

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

        return $fitnessScores;
    }

    // Fitness function to score each chromosome
    private function fitness(array $chromosome): float
    {
        $totalObjective = 0;

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

        return $totalObjective;
    }

    // Selects the best individuals (elite) for the next generation
    private function selectElite(array $fitnessScores): array
    {
        $numElite = (int) round($this->populationSize * $this->eliteRate);

        // Pair each fitness score with its index
        $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;
    }

    // Tournament selection to pick a parent chromosome
    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'];
    }

    // Single-point crossover between two parent chromosomes
    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)
        );
    }

    // Mutation with a defined probability
    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;
            }
        }
    }

    // Checks if a chromosome respects all constraints
    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;
    }

    // Returns the index of the best chromosome based on 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];
    }

    // Decodes a chromosome and returns the selected items
    private function decodeChromosome(array $chromosome): array
    {
        $selected = [];
        foreach ($chromosome as $index => $gene) {
            if ($gene === 1) {
                $selected[] = $this->items[$index];
            }
        }
        return $selected;
    }
}

🤖 Built in PHP, But the Intelligence is Universal

Although I built everything in pure PHP, the genetic algorithm logic is language-agnostic.

Whether you're using JavaScript, Python, Go, Rust, or any other language, you can rewrite the code manually—or let an AI like ChatGPT do the heavy lifting.

The intelligence is in the idea. The language is just the medium. 😉

🧠 Ready to Evolve?

If you’ve ever had to build a schedule, task list, or resource plan with overlapping constraints, you know brute force just doesn’t scale. Genetic algorithms mimic natural evolution to find surprisingly effective solutions.

And the best part? You can do it all in clean, testable, pure PHP.

DEV Community