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
idevalor, 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.
Top comments (0)