Metaheurísticas com RKO

O que é o RKO

O Random-Key Optimizer (RKO) é um pacote Python, rko, que já vem instalado em todo kernel de computação da Harumi. Ele não exige licença.

O RKO busca em um vetor de números aleatórios entre 0 e 1. Você não escreve um algoritmo de busca. Você escreve duas funções:

• um decoder que transforma esses números em uma solução do seu problema (por exemplo, ordenando-os para obter uma ordem de tarefas);
• um custo que avalia essa solução. O RKO o minimiza, então devolva o valor negativo se quiser maximizar.

Em seguida, o RKO executa até oito metaheurísticas ao mesmo tempo (BRKGA, multi-start, simulated annealing, VNS, ILS, LNS, PSO e GA), em paralelo, compartilhando suas melhores soluções.

Quando usar

O RKO é indicado quando:

• o problema é combinatório e grande (centenas a milhares de itens), e um modelo exato no Gurobi ou no OR-Tools demora demais ou não tem uma formulação justa;
• uma solução é naturalmente uma ordem, uma lista de prioridades ou um conjunto de pontuações (sequenciamento, empacotamento, roteirização, atribuição por prioridade);
• o objetivo só pode ser calculado simulando a solução.

Ele não é indicado quando você precisa de uma solução ótima comprovada ou de um gap de otimalidade. O RKO não dá nenhum dos dois: seu resultado é sempre heurístico. Se um solver exato consegue terminar o problema, use o solver exato.

Execute em um projeto

[run]
command = "python main.py"
kernel = "or_python_medium"

import json
import os

import numpy as np
from rko import RKO


class SequencingEnv:
    """Ordena tarefas em uma máquina para minimizar o atraso total."""

    def __init__(self, durations, due_dates):
        self.durations = np.asarray(durations, dtype=float)
        self.due_dates = np.asarray(due_dates, dtype=float)

        # Atributos obrigatórios
        self.tam_solution = len(self.durations)  # uma chave aleatória por tarefa
        self.LS_type = "Best"
        self.dict_best = {}
        self.instance_name = "sequencing"

        # Parâmetros de busca (o RKO escolhe entre os valores listados)
        self.BRKGA_parameters = {"p": [200], "pe": [0.2], "pm": [0.05], "rhoe": [0.7]}
        self.SA_parameters = {"SAmax": [100], "alphaSA": [0.9], "betaMin": [0.01],
                              "betaMax": [0.05], "T0": [1000]}
        self.ILS_parameters = {"betaMin": [0.1], "betaMax": [0.2]}
        self.VNS_parameters = {"kMax": [5], "betaMin": [0.05]}
        self.LNS_parameters = {"betaMin": [0.1], "betaMax": [0.3], "TO": [100],
                               "alphaLNS": [0.9]}
        self.PSO_parameters = {"PSize": [100], "c1": [2.05], "c2": [2.05], "w": [0.73]}
        self.GA_parameters = {"sizePop": [100], "probCros": [0.98], "probMut": [0.005]}

    def decoder(self, keys):
        return np.argsort(keys)  # ordem das tarefas: menor chave primeiro

    def cost(self, solution, final_solution=False):
        finish = np.cumsum(self.durations[solution])
        late = np.maximum(finish - self.due_dates[solution], 0.0)
        return float(late.sum())  # o RKO minimiza este valor


if __name__ == "__main__":
    rng = np.random.default_rng(0)
    env = SequencingEnv(rng.integers(1, 20, 80), rng.integers(50, 600, 80))

    solver = RKO(env, logger="none")
    cost, keys, seconds_to_best = solver.solve(time_total=20, brkga=1, sa=1)

    order = env.decoder(keys)  # solve() devolve as chaves, não a solução
    os.makedirs("output", exist_ok=True)
    with open("output/output.json", "w") as f:
        json.dump(
            {
                "objective": cost,
                "rows": [{"name": f"Job {int(j)}", "value": int(env.durations[j])}
                         for j in order[:10]],
            },
            f,
        )
    print(f"atraso total {cost:.1f}, melhor solução após {seconds_to_best:.1f}s")

Ajuste os workers ao kernel

Em solve(), cada um de brkga, ms, sa, vns, ils, lns, pso e ga é o número de processos de trabalho daquele método. Mantenha a soma igual ou menor que as CPUs do kernel. Mais workers do que CPUs só faz com que um atrapalhe o outro.

Não calcule a combinação a partir de os.cpu_count(). Em um contêiner com limite de CPU, ele pode informar os núcleos do host em vez dos do seu kernel.

Algumas outras configurações importam:

Deixe o Chat de IA da Harumi fazer isso

O Chat de IA da Harumi sabe que o RKO está disponível e, em um projeto, vai considerá-lo para problemas combinatórios grandes que um modelo exato não resolve a tempo. Para melhores resultados, instale a habilidade RKO modeling no projeto:

1. Abra Memórias & Habilidades na barra lateral do projeto e vá para a aba Biblioteca.
2. Encontre RKO modeling (busque por "RKO", ou filtre pela categoria Tipo de problema).
3. Clique em Instalar.

A instalação copia a habilidade para o repositório do projeto como skills/rko-modeling/SKILL.md, onde você pode editá-la como qualquer outra habilidade. Veja Memórias & Habilidades para saber como as habilidades funcionam.

Leia o resultado como heurístico

Seja qual for o custo, o RKO não tem prova de que não existe uma solução melhor. Antes de confiar em um resultado:

• decodifique as chaves finais e verifique a solução de forma independente (cada item alocado uma vez, capacidades e prazos respeitados), porque uma penalidade ausente no custo pode fazer uma solução inviável parecer barata;
• compare com uma referência simples, como uma regra gulosa ou a solução exata de uma instância pequena;
• execute duas vezes. O RKO não tem configuração de semente, então cada execução é uma busca aleatória nova, e uma grande diferença entre execuções significa que o tempo está curto demais.