Problemas de otimização combinatória com múltiplos objetivos são extensões naturais dos problemas com objetivo único. Embora esses últimos sirvam de modelo para diversas aplicações, em algumas situações podem ser representações bastante simplistas, por não considerarem pontos conflitantes equivalentes aos múltiplos objetivos de problemas reais. Um problema quanto à consideração de modelos que melhor representem a realidade, no caso com múltiplos objetivos, é que os problemas com único objetivo frequentemente têm sua complexidade aumentada quando considerados em suas versões multi-objetivo. Devido aos algoritmos exatos serem capazes de resolver apenas instâncias de pequeno porte em um tempo computacional razoável, os algoritmos aproximativos baseados em técnicas metaheurísticas são bastante utilizados. Os Algoritmos Meméticos são algoritmos evolucionários que unem a potencialidade de diversificação dos Algoritmos Genéticos a métodos que produzam intensificação da busca em determinadas partes do espaço de solução. Uma árvore geradora de um grafo conexo G=(V,E) é um subgrafo de G , conexo, com n vértices e n-1 arestas, onde n = |V|. Se G é um grafo ponderado em arestas, então a árvore geradora mínima de G é a árvore geradora cuja soma dos pesos de suas arestas é mínima sobre todas as árvores geradoras de G. O problema da AGM-MO é o de encontrar o conjunto de soluções S que não possua soluções claramente piores, ou seja, encontrar o conjunto de todas as soluções não-dominadas.

O algoritmo proposto para o problema é um algoritmo genético hibridizado com um procedimento de busca tabu. A primeira parcela da população inicial é gerada através de uma versão aleatória do algoritmo de Kruskal, modificado para lidar com o problema com dois objetivos, enquanto a outra parcela da população é inicializada de maneira aleatória. Os indivíduos da população do algoritmo memético são codificados de forma direta seguindo a representação Edge-Set, proposta por Raidl. Um número fixo de gerações, denotado por #max¬_gerações, é realizado pelo algoritmo genético. No início de cada geração, todos os membros da população são otimizados através de um procedimento de busca tabu. Para cada filho os pais são selecionados através de um método de Torneio Binário determinístico (com a observação de um dos objetivos). No algoritmo de Busca Tabu inserido em Mem-MC-MST, uma solução s’ é vizinha de uma solução s, se s’ é gerada a partir de s pela remoção de duas arestas (vi,vj) e (vk,vl), e os vértices terminais dessas arestas são religados da única maneira possível. A solução gerada substitui a original caso a domine ou esteja melhor distribuída no espaço de soluções encontradas. No caso da solução corrente ter sido modificada, então a lista tabu é atualizada com as arestas que deixaram à solução, as quais ficam proibidas de voltarem à solução por #tabutenure iterações.

Os algoritmos foram testados em 39 diferentes instâncias. Foram geradas, respectivamente, 13 instâncias de cada uma das classes “correlated”, “anti-correlated” e “concave” descritas. Para cada uma das classes foram geradas instâncias de tamanho 10, 25, 50, além de duas instâncias de tamanho 100, 200, 300, 400 e 500 nós. As comparações foram feitas entre o algoritmo memético proposto, denominado Mem-MC-MST, e o algoritmo AESSEA+Direct/RPM. A comparação entre os conjuntos de soluções encontrados pelos algoritmos foi feita utilizando indicadores binários. Foi escolhido o indicador épsilon-aditivo, cuja função de interpretação I(A,B) < 0 mostra que o conjunto obtido pelo algoritmo A domina estritamente o conjunto obtido pelo algoritmo B. Uma característica dessa função é que não assume nada sobre as preferências do tomador de decisão. Pode-se observar que os resultados mostram que o algoritmo Mem-MC-MST domina estritamente o algoritmo AESSEA em 25 das 39 instâncias testadas, sendo que quanto maior as instâncias, mais a diferença se acentua: o algoritmo foi melhor em 25 das 30 instâncias de tamanho maior ou igual a 100 nós. O algoritmo AESSEA não dominou estritamente o algoritmo Mem-MC-MST em nenhuma das instâncias.

Neste trabalho foi apresentado um novo algoritmo memético para o problema da árvore geradora mínima bi-objetivo. Os resultados do método proposto são comparados com o algoritmo AESSEA. Os resultados mostram que o algoritmo proposto encontra melhores soluções que o algoritmo de comparação em 25 das 39 instâncias de teste e o inverso não acontece em nenhuma das instâncias. Além disso, o algoritmo proposto, em geral, tem um tempo de execução cerca de dez vezes menor e encontra duas vezes mais soluções. Como trabalhos futuros, pode-se citar o estudo de novas vizinhanças para a busca local, a implementação de novas estruturas de dados para o arquivo de soluções Pareto e para a busca local.

Instituição de fomento: CNPQ

Trabalho de Iniciação Científica