Equipe do Programa de Pós-graduação em Ciência da Computação da UFOP vence competição internacional

Equipe do Programa de Pós-graduação em Ciência da Computação da UFOP vence competição internacional de otimização

Pesquisadores do Programa de Pós-Graduação em Ciência da Computação (PPGCC) do Departamento de Computação (DECOM) da Universidade Federal de Ouro Preto (UFOP) participaram da competição Bi-objective Traveling Thief Problem (Bi-TTP), promovida pela 10th International Conference on Evolutionary Multi-Criterion Optimization (https://www.emo2019.org/). A equipe JoMar formada pelo doutorando Jonatas Batista Costa das Chagas e por seu orientador, professor Marcone Jamilson Freitas Souza, ficou em primeiro lugar dentre seis equipes de várias nacionalidades.

O Bi-TTP é um problema de alta complexidade, pois ele combina dois problemas clássicos de otimização, de natureza combinatória: o Problema do Caixeiro Viajante (TSP, Traveling Salesman Problem) e o Problema da Mochila (KP, Knapsack Problem).

Basicamente, no Bi-TTP, há um conjunto de cidades, sendo que em cada uma delas há um conjunto de itens valiosos e pesados. Partindo de um depósito, o mochileiro (ou ladrão, no modo cômico de apresentar o problema) deve visitar cada cidade exatamente uma vez e, ao fim, retornar ao depósito. Ao longo da rota, o mochileiro pode escolher itens para carregar, desde que o peso total deles não exceda a capacidade de carga da mochila, pois ele a usa para carregá-los. O mochileiro sai do depósito com a sua mochila completamente vazia e no início do percurso ele consegue se locomover com a sua velocidade máxima. No entanto, à medida que os itens escolhidos são colocados na mochila, o peso da mochila aumenta e a velocidade do mochileiro diminui, visto a dificuldade de carregar os itens consigo. O Bi-TTP tem dois objetivos: maximizar o valor total dos itens carregados na mochila (componente KP) e minimizar o tempo total gasto para visitar todas as cidades (componente TSP). Tais objetivos são conflitantes, uma vez que a otimização de um deles não implica na otimização do outro, pelo contrário.

Embora o Bi-TTP seja descrito e conhecido de uma forma um pouco cômica, as suas características são encontradas em situações reais, práticas (e lícitas!), principalmente em problemas de logística de transporte.

Cada equipe participante deveria apresentar soluções para um conjunto de problemas-teste do Bi-TTP. Os problemas-teste disponibilizados pela competição envolviam de 280 a 33810 cidades e de 279 a 338090 itens. Para cada problema-teste eram distribuídos pontos aos três primeiros colocados, sendo que o primeiro colocado recebia 3 pontos, o segundo 2 pontos e o terceiro, 1 ponto. A equipe vencedora seria aquela que conseguisse o maior número de pontos.

A equipe JoMar desenvolveu um algoritmo heurístico baseado no Biased Random-Key Genetic Algorithm (BRKGA) e no Non-Dominated Sorting Genetic Algorithm II (NSGA-II) para resolver o Bi-TTP. A equipe JoMar, do PPGCC/UFOP, ficou em primeiro lugar ao conquistar 25 dos 27 pontos possíveis. As equipes que ocuparam a segunda, terceira e quarta posição somaram, respectivamente, 19, 8 e 2 pontos.

Em 2017, Jonatas e seu coorientador, professor André Gustavo dos Santos, da Universidade Federal de Viçosa, já haviam conquistado o primeiro lugar na competição Optimisation of Problems with Multiple Interdependent Components, que fez parte do Genetic and Evolutionary Computation Conference 2017 (GECCO 2017), e também abordava o Traveling Thief Problem, porém em sua versão mono-objetivo. Acesse https://bit.ly/2FgTv6u para mais detalhes.

Detalhes técnicos do Bi-TTP e da competição, bem como uma análise detalhada dos resultados de todas as equipes participantes, podem ser acessados por meio do link: https://www.egr.msu.edu/coinlab/blankjul/emo19-thief/

PPGCC - Programa de Pós-Graduação em Ciência da Computação

Departamento de Computação  |  ICEB  |  Universidade Federal de Ouro Preto
Campus Universitário Morro do Cruzeiro  |  CEP 35400-000  |  Ouro Preto - MG, Brasil
Telefone: +55 31 3559-1692  |  secretaria.ppgcc@ufop.edu.br