Posted on May 30

Como uma conversa no bilhar 🎱 me ensinou a montar agendas com algoritmos genéticos 🧬 em PHP

#php #inteligenciaartificial #algoritmogenetico #programacao

Esses dias saí pra descontrair e jogar um bilhar com meu amigo Romane.

No meio do jogo, ele soltou:

“Eu que estava me achando porque fiz uma função de busca genética!”

Achei que ele estava brincando... até me contar que criou uma função chamada buscaGenetica() que ajudava a resolver um problema real: pagar boletos com um valor limitado.

💸 O problema dos boletos

“Imagine que o usuário informa um array de boletos, cada um com id e valor, e diz que possui R\$1.000 para pagar o maior número possível deles.”

Ele usava algoritmos genéticos para encontrar a melhor combinação possível respeitando esse limite.

🧬 Como funciona essa tal de busca genética?

A explicação dele foi tão lúdica que parecia até um roteiro de ficção científica:

💑 Os boletos “casavam” entre si e geravam novas combinações.
🧟 Algumas gerações vinham com mutações, tipo boletos trocados por outros — o que ele chamava carinhosamente de “anomalias genéticas” (ou "cânceres" 😅).
👑 Boas combinações sobreviviam direto para a próxima geração.
🧠 E tudo isso se repetia por 100 gerações, até encontrar a solução ideal: o maior número de boletos pagos com até R\$1.000.

Fiquei vidrado. A ideia era poderosa.

⏰ O meu problema real: disponibilidade de horários

Na volta pra casa, a conversa não saía da minha cabeça.

Eu estava justamente quebrando a cabeça com um problema no meu sistema:

Tenho vários profissionais, com diferentes habilidades (banho, tosa, trimming), e preciso preencher os horários da agenda com os melhores profissionais, sem sobreposição.

E aí veio o clique:

E se eu aplicasse o algoritmo genético do Romane para montar essa agenda?

Transformei a lógica dele em um serviço PHP chamado GeneticAlgorithmService.

💻 A implementação com PHP

A classe GeneticAlgorithmService é genérica e recebe um objeto de configuração. Ela cuida de toda a evolução genética por trás da solução:

use App\Services\GeneticAlgorithmService; $config = [ "items" => [ ["id" => 1, "peso" => 10, "altura" => 50, "valor" => 60], ["id" => 2, "peso" => 20, "altura" => 60, "valor" => 100], ["id" => 3, "peso" => 30, "altura" => 70, "valor" => 120], ], "constraints" => [ ["attribute" => "peso", "max" => 50], ["attribute" => "altura", "max" => 110], ], "objective" => ["attribute" => "valor", "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 "Melhor combinação encontrada:\n"; print_r($result);

📥 Entrada (configuração)

Você define:

items: conjunto de dados (horários, boletos, tarefas, etc)
constraints: restrições (ex: peso máximo, limite de tempo, altura)
objective: qual atributo será maximizado ou minimizado
Parâmetros genéticos: tamanho da população, número de gerações, taxa de mutação e taxa de elite

📤 Saída

A função run() retorna, por exemplo:

[ ['id' => 2, 'peso' => 20, 'altura' => 60, 'valor' => 100], ['id' => 1, 'peso' => 10, 'altura' => 50, 'valor' => 60] ]

Ou seja, a melhor combinação possível segundo os critérios definidos.

⚙️ O que o algoritmo faz por trás

Internamente, o GeneticAlgorithmService executa:

Geração da população inicial (combinações aleatórias de itens)
Avaliação de "fitness" (quão boa é cada combinação)
Seleção dos melhores indivíduos (elitismo)
Cruzamento entre candidatos (reprodução)
Mutação aleatória em descendentes
Repetição por várias gerações

✅ Por que isso funciona tão bem?

Porque é flexível. Com esse padrão, você pode resolver:

Agendas de atendimento
Seleção de tarefas com prioridades
Escalonamento de recursos
Qualquer problema de otimização combinatória

⚙️ O algoritmo completo

Abaixo está o código completo da classe GeneticAlgorithmService:

 use Illuminate\Support\Collection; 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; } }

🤖 Feito em PHP. Mas a inteligência é universal.

Embora eu tenha feito tudo isso com PHP, a lógica do algoritmo genético é agnóstica.

Se quiser usar JavaScript, Python, Go, Rust ou qualquer outra linguagem, você pode traduzir o código manualmente ou usar uma IA como o ChatGPT para converter tudo.

A inteligência está na ideia. A linguagem é só o meio. 😉

🧠 Pronto para evoluir?

Se você já precisou montar uma escala, agenda ou lista de prioridades com muitas variáveis cruzadas, sabe que usar força bruta é lento ou inviável. Algoritmos genéticos simulam a evolução natural para encontrar soluções surpreendentemente boas.

E o melhor: com PHP puro, de forma testável, limpa e extensível.

DEV Community