Método descobre soluções em várias áreas, das telecomunicações à economia
Mecanismos que atuam na evolução por seleção natural dos seres vivos podem ajudar a descobrir soluções para problemas de diversos tipos, incluindo questões sobre a estrutura de redes de telecomunicação e, até, um problema eminentemente econômico: como otimizar o resultado de um leilão de concessão pública. É o que mostra a tese de doutorado “Algoritmos evolutivos para alguns problemas em telecomunicações”, defendida por Carlos Eduardo de Andrade no Instituto de Computação (IC) da Unicamp, e orientada pelo professor Flávio Keidi Miyazawa, do mesmo instituto, e Mauricio G. C. Resende, do Departamento de Planejamento e Otimização Matemática, da Amazon.com, nos Estados Unidos.
“Um algoritmo evolutivo é um método de resolução de problemas inspirado nos princípios darwinianos de evolução”, disse Andrade. “Em geral, um algoritmo evolutivo utiliza, como metáforas, os mecanismos biológicos de reprodução, mutação, recombinação e seleção natural através da aptidão. Tais mecanismos são simulados pelo algoritmo evolutivo, com o objetivo de resolver um problema específico. Existem diversas variações desses algoritmos, e nem sempre todos mecanismos evolutivos são usados. Algoritmos genéticos, em geral, fazem o uso completo das metáforas”.
A tese explica como possíveis soluções para um problema podem ser codificadas em “cromossomos” virtuais, cada um deles dotado de uma função de aptidão, uma medida de sua qualidade em relação ao problema tratado – por exemplo, qual a forma mais eficiente de conectar uma série de pontos numa rede. Assim como os cromossomos dos seres vivos, os virtuais contêm “alelos”, isto é, diferentes versões de um mesmo gene – ou, no caso, de uma mesma parte da solução.
“O passo evolutivo consiste em construir uma nova população, combinando os indivíduos da população atual, selecionando alelos deles para criar prole”, escreve Andrade em seu trabalho. “Um passo adicional, chamado ‘mutação’, é aplicado com baixa probabilidade, quando um alelo é escolhido e modificado ao acaso. A grande vantagem do algoritmo genético é combinar duas ou mais diferentes soluções”. Mais adiante, acrescenta: “Usando o conceito de operadores genéticos e hereditariedade, algoritmos genéticos são capazes de combinar partes de boas soluções mantê-las ‘vivas’”.
Em sua tese, o pesquisador aplica a técnica a cinco problemas. Quatro deles buscam a determinação de uma melhor forma de montar e organizar redes de telecomunicações, envolvendo de fibras ópticas a conexões de rede sem fio como wi-fi e LTE, e dentro de diversos tipos de demandas e restrições. Um desses quatro tinha a mesma estrutura de uma questão clássica na história da Matemática, o Problema do Caixeiro Viajante.
Melhor rota
“No problema clássico do caixeiro viajante, temos um conjunto de cidades onde queremos encontrar uma rota de menor custo (seja distância, tempo de viagem, ou ainda consumo de combustível) tal que um representante comercial possa visitar todas cidades sem, entretanto, visitar a mesma cidade duas ou mais vezes”, descreve Andrade. “Este problema é abstraído em uma estrutura matemática chamada grafo, onde os vértices do grafo representam as cidades e as arestas, as rodovias entre as cidades, formando um tipo de rede se o visualizarmos. Este é um problema de otimização combinatória clássico considerado NP-difícil”.
O pesquisador explica que, para a classe dos problemas NP-difíceis, o tempo necessário, ou o número de etapas necessárias para se chegar a uma solução é, em geral, uma função exponencial do tamanho do problema. “Por exemplo, suponhamos que no problema do caixeiro viajante temos que visitar 50 cidades. O número de passos necessários para resolver este problema é proporcional a 50! (fatorial de 50), que é um número de mais de 60 dígitos, se tivermos que testar todas as opções. Este imenso número é muito maior que o número de átomos do universo! Embora existam heurísticas que possam encontrar a melhor solução em um tempo razoável, testar todas opções é simplesmente inviável”.
“O problema do caixeiro viajante liga-se intimamente a vários problemas no projeto de redes de telecomunicação”, prossegue Andrade. “Talvez o mais próximo seja o de projetar uma rede de telecomunicações tal que grupos de equipamentos devam ser ligados em forma de anéis, para aumentar a resiliência da rede. Assim, se um equipamento ou conexão falhar, é possível encontrar outros caminhos entre dois equipamentos”.
Em um dos problemas contemplados na tese, o objetivo é construir vários anéis de telecomunicação interligando terminais, de forma a manter um grau de resiliência e minimizar o custo de implantação. “Podemos entender que, neste problema, precisamos resolver vários subproblemas do caixeiro viajante, combinando-os em uma solução final. Este problema é usado para planejamento de redes que podem conter, na prática, centenas de milhares de equipamentos. Portanto, simplesmente enumerar todas possíveis soluções e buscar pela melhor é impraticável. Assim, utilizamos várias abordagens algorítmicas, com os algoritmos evolutivos”.
Metáforas
“Do ponto de vista técnico, um algoritmo evolutivo é um simulador: uma solução ou uma estrutura de um problema é modelada como um indivíduo em uma população. Os indivíduos dessa população são combinados (‘reprodução’) ou modificados (‘mutação’), visando à melhoria da qualidade da solução ou estrutura. Em termos de código, um algoritmo evolutivo se apresenta como outro algoritmo qualquer: ele representa uma abstração da simulação da evolução”, disse o pesquisador.
A questão de até que ponto um algoritmo evolutivo segue de perto o mecanismo natural da evolução por seleção natural, e até que ponto ele apenas se inspira nesse mecanismo como metáfora, é algo “que permeia a comunidade de algoritmos evolutivos por décadas, desde seus anos de infância, nos meados dos anos 70”, disse ele. “Existem duas linhas de trabalho. A primeira utiliza a evolução como metáfora para resolução de problemas práticos. Este é o caso da grande maioria da aplicação de algoritmos evolutivos. A segunda linha tenta avaliar a eficácia das metáforas aplicadas, e mesmo desenvolver novas metáforas”.
No quesito de “novas metáforas”, Andrade cita um caso, apresentado na tese, em que se definiu que os cromossomos – as soluções postas a evoluir – teriam “gêneros” opostos. “Na produção de um novo indivíduo/solução, nós apenas combinamos cromossomos/soluções de gênero oposto. Desta maneira, nós usamos a teoria da heterossexualidade da maioria das espécies como metáfora”.
Em outra estratégia, relata o pesquisador, a produção de um novo indivíduo/solução é feita pela combinação de vários indivíduos, e de diversas maneiras.
Otimização
Os problemas tratados na tese não problemas de otimização – buscas pela melhor solução disponível dentro de um conjunto pré-estabelecido de soluções possíveis. Algoritmos evolutivos apresentam vantagens para o tratamento desse tipo de questão, disse Andrade.
“A grande maioria de problemas de otimização é de natureza não-linear e não-contínua. Muitos deles apresentam vales e picos locais onde residem solução sub-ótimas. Métodos determinísticos em geral são incapazes de escapar de tais regiões quando as atingem”, explicou. A introdução de elementos aleatórios (por exemplo, por meio das mutações) pode ajudar a busca a fugir dessas armadilhas.
“A segunda vantagem dos algoritmos evolutivos é que, em geral, eles trabalham com uma população de soluções”, prossegue. “Em vez de massagear uma certa solução em uma região particular do espaço de busca, os algoritmos evolutivos contêm soluções que, provavelmente, estão espalhadas por todo espaço de busca. Do ponto de vista algorítmico, esta característica ajuda na exploração e aumenta a probabilidade de encontrarmos uma solução ótima. Do ponto de vista prático, várias soluções podem ser facilmente apresentadas”.
O pesquisador cita trabalho de Christos Papadimitriou, professor do departamento de Engenharia Elétrica e Ciência da Computação da Universidade da Califórnia em Berkeley, e um dos mais conceituados cientistas da computação da atualidade, que escreveu recentemente no periódico Communications of the ACM: “Existe uma confusão entre heurísticas comuns e algoritmos evolutivos. Heurísticas devem criar populações que contenham excelentes indivíduos. Evolução parece ser muito boa em algo muito diferente: criar uma boa população”.
Andrade aponta que esta última característica é muito importante do ponto de vista industrial: “Por mais que nos esforcemos, alguns modelos não podem capturar todos os detalhes do problema real. Assim, certas soluções, embora estejam corretas conforme o modelo, podem não ser desejáveis para o usuário, na prática”. Desse modo, explica o pesquisador, a possibilidade de apresentar várias soluções de boa qualidade é essencial para que o usuário possa tomar sua decisão.
“Podemos traçar uma comparação entre algoritmos exatos e algoritmos evolutivos. Os exatos são capazes de retornar, com certeza teórica, soluções ótimas. Mas, em muitos casos, o tempo necessário é demasiado e não é viável na prática, principalmente para operações sensíveis ao tempo, como reescalonamento de pessoal em casos de acidentes. Os algoritmos evolutivos podem retornar soluções de boa qualidade em tempo razoável, embora, em geral, seu caráter ótimo não possa ser provado”.
Genéticos na prática
Os algoritmos propostos na tese de Andrade têm sido utilizados na prática pela AT&T, uma das maiores empresas de telecomunicações do mundo, para planejamento e execução de redes de telecomunicação e outros problemas práticos de otimização.
“No momento, além de projeto de redes, temos usado algoritmos genéticos e outras heurísticas híbridas para resolver problemas de otimização no contexto de rede definidas por software (SDNs), e no contexto de internet das coisas. No último caso, heurísticas são muito importantes, pois o número de elementos nos problemas associados ultrapassa a casa de milhões de dispositivos”, disse ele.
Referências da tese
M.C. Lopes, C.E. Andrade, T.A. Queiroz, M.G.C. Resende, F.K. Miyazawa. Heuristics for a Hub Location-Routing Problem. Networks, volume 68, number 1, pages 54–90, 2016. http://onlinelibrary.wiley.com/doi/10.1002/net.21685/abstract
C.E. Andrade, M.C.G. Resende, W. Zhang, R.C. Sinha, K.C. Reichmann, R.D. Doverspike, F.K. Miyazawa. A Biased Random-key Genetic Algorithm for Wireless Backhaul Network Design. Applied Soft Computing, volume 33, páginas 150-169, 2015. http://www.sciencedirect.com/science/article/pii/S1568494615002410
C.E. Andrade, F.K. Miyazawa, M.C.G Resende, R.F. Toso. Biased Random-Key Genetic Algorithms for the Winner Determination Problem in Combinatorial Auctions. Evolutionary Computation , volume 23, número 2, pages 279-307, 2015. http://www.mitpressjournals.org/doi/10.1162/EVCO_a_00138
C.E. Andrade, M.C.G Resende. H.J. Karloff, F.K. Miyazawa. Evolutionary Algorithms for Overlapping Correlation Clustering. Proceedings of the Sixteen International Conference on Genetic and Evolutionary Computation (GECCO 2014). Páginas 405-412, 2014. http://dl.acm.org/citation.cfm?id=2598284&CFID=599363338&CFTOKEN=96067408
M.L. Lucena, C.E. Andrade, M.G.C. Resende, and F.K. Miyazawa. Some extensions of biased random-key genetic algorithms. Anais do 46o Simpósio Brasileiro de Pesquisa Operacional (SBPO’14). Páginas 1–12, 2014. http://www.research.att.com/people/De_Andrade_Carlos_Eduardo/more_about_carlos/publications/lucena2015
_extensions_of_brkga.pdf
C.E. Andrade, F.K. Miyazawa, M.C.G Resende. Evolutionary Algorithm for the k-Interconnected Multi-Depot Multi-Traveling Salesmen Problem. Proceedings of the Fifteen International Conference on Genetic and Evolutionary Computation (GECCO’ 13). Páginas 463-470, 2013. http://dl.acm.org/citation.cfm?id=2463434&CFID=599363338&CFTOKEN=96067408
Publicação
Tese: “Algoritmos evolutivos para alguns problemas em telecomunicações”
Autor: Carlos Eduardo de Andrade
Orientador: Flávio Keidi Miyazawa
Coorientador: Mauricio G. C. Resende
Unidade: Instituto de Computação (IC)