Desenvolvendo rotas inteligentes usando Otimização por Enxame de Partículas
Imagine que você é um carteiro e precisa entregar todas as cartas da sua bolsa até o fim do expediente as 17:00 horas. Você tem 50 ‘destinos’ a percorrer durante o seu dia.
Qual seria a menor rota que ligue todos esses destinos e te faz retornar ao ponto de partida? Ou qual a rota que teria um menor custo para ser percorrida?
Bom, ao se perguntar isso, você acabaria por conhecer involuntariamente o ‘Problema do caixeiro-viajante’, um problema matemático que visa achar a melhor rota possível dentro do seu objetivo.
Antes que você pense: “Ok, sem problemas. Deixo meu computador verificar todas as rotas possíveis dentro desse número de destinos e ele me retornará a melhor delas”. Saiba, que para o nosso exemplo, o número de rotas possíveis é de aproximadamente: 3.0362e+62 !! Ou seja, você precisaria deixar seu computador de lado por dias computando todas esse astronômico número.
Porém, nós estamos somente no começo do dia e precisamos achar uma outra solução para entregar todas essas cartas.
Para nossa sorte, existem diversos métodos matemáticos que nos auxiliam na resolução (ou minimização) do problema em muito menos tempo.
Mostraremos aqui a Otimização por Enxame de Partículas (PSO). Onde Marcel P. Caraciolo explica seu conceito brilhantemente nesse post.
Em resumo, a PSO visa em simular o comportamento de ‘enxame’ encontrado na natureza em certos tipos de espécie animal, onde, ao se deslocarem de um ponto ao outro, sempre há a existência de um ou mais líderes do bando que acabam influenciando no movimento dos demais.
A estratégia aqui é a seguinte: Determinamos um certo número de indivíduos que terão uma rota candidata a solução do problema, cada um. A partir disso, verificaríamos quem seria o ‘líder do bando’ (vamos chamar de gbest), ou seja, aquele indivíduo que tem a melhor rota dentre todos. Sabendo o líder, começamos a ‘cruzar’ (o termo em inglês correto é de ‘crossover’) parte da sua rota com a dos outros indivíduos. Fazendo assim, na teoria, com que todos melhorem sua rota através do líder (melhor indivíduo).
Há também um segundo ‘crossover’ para cada indivíduo. Porém, nesse, nós misturamos a rota atual de cada indivíduo com a melhor rota já obtida pelo mesmo, anteriormente (chamamos de pbest).
Resumo da ópera: A cada iteração…
① Escolhemos o líder, dentre os indivíduos. (O que tem melhor resultado).
② Fazemos um ‘crossover’ de cada indivíduo com seu pbest.
③ Com a rota resultante fazemos um outro crossover, mas com o gbest.
E repetimos o processo na próxima iteração…
Lembrando, que como a grande maioria dos métodos de otimização bioinspirados nós temos um fator aleatório, e ele aparece no operador ‘crossover’. Portanto, depois do ‘crossover’ a rota resultante pode ser melhor ou pior que a anterior.
Achou complicado? Eu te provo que não é!
Vamos adotar um exemplo um pouco mais simples. Vamos supor que o nosso problema seja encontrar o melhor caminho que ligue os pontos abaixo:
Vamos ter 4 indivíduos candidatos a resolução do problema. E simplesmente sorteamos uma rota diferente para cada um deles. Estamos gerando nesse caso, a população inicial.
Vamos então para a 1ª Iteração.
Nós calcularemos a distância total das rotas. Com isso, encontraremos o nosso melhor indivíduo, o gbest.
A = 38m; B = 30m; C = 32m ; D = 29m;
Logo, nosso gbest será o indivíduo ‘D’.
Próximo passo é fazer o crossover.
Como estamos na iteração 1 não temos ainda um pbest (Já que o pbest é o melhor resultado que cada indivíduo ja teve e ainda estamos na primeira iteração). Por isso o crossover na iteração 1 pode ser apenas com o gbest, ou seja com o indivíduo ‘D’.
O crossover como mostrado acima necessita de 2 fatores aleatórios que aqui vamos chamar de ‘R’ e ‘M’. Considere o primeiro como lugar de corte e o segundo como a quantidade de ‘termos’ que serão passados para o indivíduo.
Com o R = 3, contamos 3 termos e fazemos uma marcação. Após isso com o M = 2, contamos mais 2 termos e fazemos outra marcação. Os itens que tiverem entra as marcações serão ‘herdados’ para o indivíduo A.
Esse crossover será feito para todos os indivíduos. Cada um com R e M gerados novamente.
A partir da iteração 2 em diante, nós também faremos um crossover com o pbest de cada indivíduo.
Logo, a sequência do algoritmo fica assim:
Passo 1 — Inicialização: Onde definimos o número de indivíduos da nossa população. Definimos também o número de iterações que julgamos necessário.Passo 2 — Achando o líder: Calcula a distância de todas as rotas para achar o gbest.Passo 3 — Começa as iterações.Passo 4 — Hora da operação de crossover: É executado o crossover de cada indivíduo com seu pbest e gbest.Passo 5 — Atualização dos pbest e gbest: Avaliamos a nova rota de cada indivíduo. Ela é melhor que seu pbest atual? Então ele vira o novo pbest. Avaliamos todos os indivíduos. Qual é a melhor rota dessa iteração? Essa será o novo gbest.Passo 6 — Finalizando as novas rotas: Definimos as rotas resultantes de cada crossover, definindo assim as novas rotas para cada indivíduo.E repete a partir do passo 3, até o resultado for satisfatório.
Entre o passo 5 e o 6 podemos adicionar mais passos com algumas técnicas que pode melhorar a nossa otimização, se tornando variações do PSO clássico. Como Huilian FAN mostra nesse artigo.
Pronto. Agora que sabemos como escrever um algoritmo utilizando PSO para resolver nosso problema de rotas, podemos pegar o nosso problema inicial e gerar algo como isso:
Aposto que hoje chegaremos em casa mais cedo.
Usei aqui uma abordagem da PSO para problemas discretos e especificamente para TSP, por isso deixei de fora alguns termos encontrados na literatura , da PSO clássica como ‘fitness’, ‘equação da velocidades’, ‘posição’ e etc. Para um estudo mais aprofundado no assunto, indico os artigos abaixo:
OTIMIZAÇÃO POR NUVEM DE PARTÍCULAS
Particle swarm optimization-based algorithms for TSP and generalized TSP
Solving City Routing Issue with Particle Swarm Optimization
