Algoritmo de otimização bayesiano com detecção de comunidades Marcio Kassouf Crocomo SERVIÇO DE PÓS-GRADUAÇÃO DO ICMC-USP Data de Depósito: Assinatura:________________________ Algoritmo de otimização bayesiano com detecção de comunidades Marcio Kassouf Crocomo Orientador: Prof. Dr. Alexandre Cláudio Botazzo Delbem Tese apresentada ao Instituto de Ciências Matemáticas e de Computação - ICMC-USP, como parte dos requisitos para obtenção do título de Doutor em Ciências - Ciências de Computação e Matemática Computacional. VERSÃO REVISADA USP – São Carlos Novembro de 2012 Ficha catalográfica elaborada pela Biblioteca Prof. Achille Bassi e Seção Técnica de Informática, ICMC/USP, com os dados fornecidos pelo(a) autor(a) Crocomo, Marcio Kassouf C937a Algoritmo de otimização bayesiano com detecção de comunidades / Marcio Kassouf Crocomo; orientador Alexandre Cláudio Botazzo Delbem. -- São Carlos, 2012. 148 p. Tese (Doutorado - Programa de Pós-Graduação em Ciências de Computação e Matemática Computacional) -- Instituto de Ciências Matemáticas e de Computação, Universidade de São Paulo, 2012. 1. Algoritmos de Estimação de Distribuição. 2. Computação Evolutiva. 3. Algoritmo de Otimização Bayesiano. I. Delbem, Alexandre Cláudio Botazzo, orient. II. Título. Àminhafamília,semprepresente. Agradecimentos AFrancisco,Faridi,LucaseLuziana,pelocarinhoeapoiosempredisponíveis. Ao Prof. Dr. Eduardo do Valle Simões, por ter me incentivado a ingressar no doutorado e, assim,seguirnocaminhoacadêmico. Ao Prof. Dr. Zhao Liang pelas aulas sobre Redes Complexas que muito contribuíram para asideiasdesenvolvidasduranteoprojeto. Ao Programa de Pós-graduação de Ciências de Computação e Matemática Computacional (PG-CCMC) do Instituto de Ciências Matemáticas e de Computação (ICMC), pela oportu- nidade e pela estrutura oferecida para a realização do curso de doutorado. Agradeço aos pro- fessoresefuncionários,dentreosquaisdestacoAnaPaulaSampaioFregona,daSeçãoTécnico Acadêmica,eDiegoJesusTalaricoFerreira,doServiçodeConvênios,BolsaseAuxílios. Ao Prof. Dr. Cláudio Fabiano Motta Toledo e aos professores que participaram de minha banca de qualificação: Prof. Dr. Renato Tinós, Prof. Dr. Dorival Leão Pinto Junior e Prof. Dr. Leandro Nunes de Castro Silva, agradeço pelas importantes orientações e discussões sobre o trabalhoquemuitoauxiliaramparaaqualidadefinaldomesmo. A todos os colegas do laboratório LCR pela companhia nestes últimos anos, pelas produti- vas conversas sobre os tópicos da tese, e com os quais tive o prazer de trabalhar, em especial Jean Paulo Martins, Danilo Vasconcellos Vargas, Marcilyanne Moreira Gois, Antonio Helson MineiroSoares,DanielRodrigoFerrazBonettieProf. Dr. ViníciusVelosodeMelo. Ao grande amigo Paulo Henrique Ribeiro Gabriel, por sua companhia, pelas interessantes conversas sobre assuntos relacionados ao trabalho, recomendações importantes sobre as refe- rênciasbibliográficasepelaimprescindívelajudanautilizaçãodoprogramaLATEX utilizadona escritadatese. AotambémamigoEduardoAlvesdaSilvaTicianelli,pelacompanhiaepresença deespíritonashorasnecessárias. Ao meu orientador Prof. Dr. Alexandre Cláudio Botazzo Delbem, com quem tive o prazer de trabalhar nestes últimos anos. Agradeço a confiança em mim depositada e toda atenção despendida a este projeto. Agradeço também pelos valiosos ensinamentos e pelas longas e produtivas conversas e planejamentos que conduziram aos resultados aqui apresentados. Por suaamizadeededicação,muitoobrigado. Aos meus tios Sylvio e Emelie e à minha prima Julia, pela ajuda com as revisões de textos em inglês, resultantes deste trabalho. Agradeço também, pelo mesmo motivo, a Profa. Angela CristinaPregnolatoGiampedro,doCentroCulturaldaUSPemSãoCarlos. À Fundação de Amparo à Pesquisa do Estado de São Paulo (FAPESP), pela concessão da bolsa de doutorado e pelo apoio financeiro para a realização desta pesquisa (Processo número 2010/01634-5), e também à Coordenação de Aperfeiçoamento de Pessoal de Nível Superior (CAPES)pelaconcessãodabolsaduranteos10mesesanterioresàbolsaFAPESP. iii Resumo ALGORITMOS de Estimação de Distribuição (EDAs) compõem uma frente de pesquisa em Computação Evolutiva que tem apresentado resultadospromissoresparalidarcomproblemascomplexosdelarga escala. Nesse contexto, destaca-se o Algoritmo de Otimização Bayesiano (BOA)queusaummodeloprobabilísticomultivariado(representadoporuma rede Bayesiana) para gerar novas soluções a cada iteração. Baseado no BOA e na investigação de algoritmos de detecção de estrutura de comunidades (para melhorar os modelos multivariados construídos), propõe-se dois novos algoritmos denominados CD-BOA e StrOp. Mostra-se que ambos apresen- tamvantagenssignificativasemrelaçãoaoBOA.OCD-BOAmostra-semais flexívelqueoBOA,aoapresentarumamaiorrobustezavariaçõesdosvalores de parâmetros de entrada, facilitando o tratamento de uma maior diversidade de problemas do mundo real. Diferentemente do CD-BOA e BOA, o StrOp mostra que a detecção de comunidades a partir de uma rede Bayesiana pode modelar mais adequadamente problemas decomponíveis, reestruturando-os em subproblemas mais simples, que podem ser resolvidos por uma busca gulosa, resultando em uma solução para o problema original que pode ser ótima no caso de problemas perfeitamente decomponíveis, ou uma aproxi- mação, caso contrário. Também é proposta uma nova técnica de reamostra- gens para EDAs (denominada REDA). Essa técnica possibilita a obtenção de modelosprobabilísticosmaisrepresentativos,aumentandosignificativamente odesempenhodoCD-BOAeStrOp. Deumaformageral,édemonstradoque, para os casos testados, CD-BOA e StrOp necessitam de um menor tempo de execução do que o BOA. Tal comprovação é feita tanto experimentalmente quantoporanálisedascomplexidadesdosalgoritmos. Ascaracterísticasprin- cipais desses algoritmos são avaliadas para a resolução de diferentes proble- mas, mapeando assim suas contribuições para a área de Computação Evolu- tiva. v