IMPLEMENTA˙ˆODEUMALGORITMOGEN(cid:201)TICOUTILIZANDOOMODELO DEILHAS AngeloJosØMoreiraSilva TESE SUBMETIDA AO CORPO DOCENTE DA COORDENA˙ˆO DOS PROGRAMAS DE P(cid:211)S-GRADUA˙ˆO DE ENGENHARIA DA UNIVERSIDADE FEDERAL DO RIO DE JANEIRO COMO PARTE DOS REQUISITOS NECESS`RIOS PARA A OBTEN˙ˆO DO GRAU DE MESTRE EM CI˚NCIAS EMENGENHARIACIVIL Aprovadapor: Prof. NelsonFranciscoFavillaEbecken,D.Sc. Dra. MyrianChristinadeAragªoCosta,D.Sc. Prof. MarioAntonioRibeiroDantas,Ph.D. Prof. BeatrizdeSouzaLeitePiresdeLima. D.Sc. RIODEJANEIRO,RJ-BRASIL AGOSTODE2005 MOREIRASILVA,ANGELOJOS(cid:201) Implementa(cid:231)ªo de um Algoritmo GenØtico utilizando o Modelo de Ilhas [Rio de Janeiro] 2005 XI,73p.29,7cm(COPPE/UFRJ,M.Sc.,En- genhariaCivil,2005) Tese - Universidade Federal do Rio de Janeiro,COPPE 1. algoritmos genØticos, otimiza(cid:231)ªo, progra- ma(cid:231)ªoparalela I.COPPE/UFRJII.T(cid:237)tulo(sØrie) ii Aquelesquesªoiluminadosnuncaparamdeforjarasimesmos. Arealiza(cid:231)ªodetaismestres nªo pode ser expressa em palavras ou por teorias. As mais perfeitas a(cid:231)ıes sªo o eco do modeloencontradonanatureza. (MoriheiUeshiba-AArtedaPaz) iii Agradecimentos Aomeupai,estejaondeDeusocolocou,inspira(cid:231)ªo,carÆterecondutanªosomentepala- vras,masa(cid:231)ıesemtodaasuaexistŒncia. Asminhas(cid:2)lhasPriscillaeGabriellepormeseguraremnasquedasdospioresmomentos epormeaben(cid:231)oaremcomadÆdivadepoderserpai. Aminhamªe,aosmeusirmªoseaClaudiapelocarinhoefor(cid:231)a. Ao professor Nelson pela orienta(cid:231)ªo e pelo est(cid:237)mulo que foi indispensÆvel (cid:224) execu(cid:231)ªo destatese. AprofessoraMyriannªotenhopalavrasquepossamdescreveraimport(cid:226)nciaqueteveao longodetodaestaetapaemminhavida. Asdiscord(cid:226)nciasserviramparaaumentarorespeito, aamizadeeocarinho. AosamigosValeriana,LeonardoePaulapeloajudaquenªohÆcomoserpaga. AoCNPq,queviabilizou arealiza(cid:231)ªodestetrabalho. iv Resumo da Tese apresentada (cid:224) COPPE/UFRJ como parte dos requisitos necessÆrios para a obten(cid:231)ªodograudeMestreemCiŒncias(M.Sc.) IMPLEMENTA˙ˆODEUMALGORITMOGEN(cid:201)TICOUTILIZANDOOMODELO DEILHAS AngeloJosØMoreiraSilva Agosto/2005 Orientadores: NelsonFranciscoFavillaEbecken MyrianChristinadeAragªoCosta Programa: EngenhariaCivil Estadisserta(cid:231)ªoapresentaaimplementa(cid:231)ªodeumalgoritmogenØticoparaleloutilizando omodelodeilhas. Noalgoritmodeilhas,popula(cid:231)ıesaleat(cid:243)riassªogeradasdemaneirainde- pendenteemcadaumadasilhas,que(cid:2)camrestritasaprocessadoresespec(cid:237)(cid:2)cos. Aobten(cid:231)ªo deumamelhoraglobalsedÆcomasevolu(cid:231)ıesindependentesdasilhasecomamigra(cid:231)ªode indiv(cid:237)duos entre as mesmas a partir de critØrios determinados. A troca de informa(cid:231)ıes entre asilhassefazatravØsdabibliotecadetrocademensagensMPI.Diferentestopologiasl(cid:243)gicas estªo sendo analisadas para a fase de de migra(cid:231)ªo de indiv(cid:237)duos entre as ilhas, sendo utili- zada especi(cid:2)camente a topologia em anel. Resultados experimentais foram gerados com a utiliza(cid:231)ªodeexemplosdaliteraturaeanalisadosecomparadoscomoutrasimplementa(cid:231)ªoes. O objetivo dessa disserta(cid:231)ªo Ø a disponibiliza(cid:231)ªo de uma ferramenta paralela de minera(cid:231)ªo dedadosdealtodedesempenhopara,porexemplo,otimizaraarquiteturadeumaredeneural arti(cid:2)cial,gerandoumalgoritmo h(cid:237)brido. v Abstract of Thesis presented to COPPE/UFRJ as a partial ful(cid:2)llment of the requirementsforthedegreeofMasterofScience(M.Sc.) IMPLEMENTATIONOFAGENETICALGORITHMUSINGTHEMODELOFISLAND AngeloJosØMoreiraSilva August/2005 Advisors: NelsonFranciscoFavillaEbecken MyrianChristinadeAragªoCosta Department: CivilEngineering This dissertation presents the parallel genetic algorithm implementation using the island model. In the island algorithm, random populations are generated of independent manner in each of the islands that remain restricted to speci(cid:2)c processors. The optimal solution is obtained with the independent evolution of the islands and the migration of individuals amongthem,usingprede(cid:2)nedcriterials. Communicationsamongislandsisperformedusing the MPI library. Different logical topologies are currently being analyzed for migration phaseamongislands,usingspeci(cid:2)callytheringtopology. Someresultsweregeneratedusing examples from the literature and were compared with other implementations. The objective thisdissertationisdevelopingaparalleltoolforhighperformancedatamining,forexample, this tool will be used to optimize the architecture of a arti(cid:2)cial neural network, generating a hybrid algorithm. vi SumÆrio ListadeFiguras ix ListadeTabelas xi 1 Introdu(cid:231)ªo 1 1.1 Objetivo . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 3 1.2 Otimiza(cid:231)ªodeFun(cid:231)ıeseRedesNeuraisArti(cid:2)ciais . . . . . . . . . . . . . 4 1.3 Apresenta(cid:231)ªodaDisserta(cid:231)ªo . . . . . . . . . . . . . . . . . . . . . . . . . 6 2 AlgoritmosGenØticos 7 2.1 Introdu(cid:231)ªo . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 7 2.2 Codi(cid:2)ca(cid:231)ªo . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 8 2.3 Inicializa(cid:231)ªo . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 10 2.4 Avalia(cid:231)ªo . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 11 2.5 Sele(cid:231)ªo . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 13 2.5.1 Roleta . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 14 2.5.2 Torneio . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 16 2.5.3 Amostragem EstocÆstica . . . . . . . . . . . . . . . . . . . . . . . 16 2.5.4 Classi(cid:2)ca(cid:231)ªo . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 16 2.6 OperadoresGenØticos . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 17 2.6.1 Cruzamento . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 17 2.6.1.1 Blend-(cid:11) . . . . . . . . . . . . . . . . . . . . . . . . . . 18 2.6.2 Muta(cid:231)ªo. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 18 2.6.2.1 Creep . . . . . . . . . . . . . . . . . . . . . . . . . . . . 19 2.7 Par(cid:226)metrosGenØticos . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 19 2.7.1 TamanhodaPopula(cid:231)ªo . . . . . . . . . . . . . . . . . . . . . . . . 20 2.7.2 TaxadeCruzamento . . . . . . . . . . . . . . . . . . . . . . . . . 20 2.7.3 TaxadeMuta(cid:231)ªo . . . . . . . . . . . . . . . . . . . . . . . . . . . 20 2.7.4 TaxadeSubstitui(cid:231)ªo . . . . . . . . . . . . . . . . . . . . . . . . . 20 2.7.5 Condi(cid:231)ªodeParada . . . . . . . . . . . . . . . . . . . . . . . . . . 20 3 AlgoritmosGenØticosParalelos 22 3.1 Introdu(cid:231)ªosobreParalelismo . . . . . . . . . . . . . . . . . . . . . . . . . 22 3.1.1 Tiposdeparalelismo . . . . . . . . . . . . . . . . . . . . . . . . . 23 3.1.1.1 ParalelismodeDados . . . . . . . . . . . . . . . . . . . 23 3.1.1.2 ParalelismoFuncional . . . . . . . . . . . . . . . . . . . 23 vii 3.1.2 AmbienteParalelo . . . . . . . . . . . . . . . . . . . . . . . . . . 24 3.1.3 ObstÆculosnoparalelismo . . . . . . . . . . . . . . . . . . . . . . 25 3.2 MessagePassingInterface . . . . . . . . . . . . . . . . . . . . . . . . . . 26 3.3 ParalelismonosAlgoritmos GenØticos . . . . . . . . . . . . . . . . . . . . 26 3.3.1 ModelosdeAlgoritmos GenØticosParalelos . . . . . . . . . . . . . 27 3.3.1.1 ModeloIlha . . . . . . . . . . . . . . . . . . . . . . . . 30 4 PropostadeFerramentanoModelodeIlhas 35 4.1 Introdu(cid:231)ªo . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 35 4.2 TrabalhosCorrelatos . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 35 4.3 AmbienteExperimental . . . . . . . . . . . . . . . . . . . . . . . . . . . . 36 4.4 Algoritmo BaseadonoModelodeIlhas . . . . . . . . . . . . . . . . . . . 39 4.4.1 Testes . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 47 4.4.1.1 Fun(cid:231)ªoDeJong1 . . . . . . . . . . . . . . . . . . . . . 47 4.4.1.2 Fun(cid:231)ªoDeJong2 . . . . . . . . . . . . . . . . . . . . . 49 4.4.1.3 Fun(cid:231)ªoDeJong3 . . . . . . . . . . . . . . . . . . . . . 50 4.4.1.4 Tanomaru . . . . . . . . . . . . . . . . . . . . . . . . . 52 5 EstudodeCaso 54 5.1 RedesNeuraisArti(cid:2)ciais . . . . . . . . . . . . . . . . . . . . . . . . . . . 54 5.1.1 Introdu(cid:231)ªo . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 55 5.1.2 ProblemasdasRedesNeurais . . . . . . . . . . . . . . . . . . . . 58 5.1.3 Escolhadepar(cid:226)metrosdaRNA . . . . . . . . . . . . . . . . . . . 58 5.2 EstudodeCaso . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 60 6 Conclusıesetrabalhosfuturos 68 ReferŒncias 70 viii Lista de Figuras 2.1 FluxoGeraldeumAlgoritmo GenØtico . . . . . . . . . . . . . . . . . . . 8 2.2 Representa(cid:231)ıesdeCromossomos . . . . . . . . . . . . . . . . . . . . . . . 10 2.3 EsquemadaRoleta . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 15 2.4 EsquemadoTorneio . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 16 3.1 Comunica(cid:231)ªoentreprocessadores . . . . . . . . . . . . . . . . . . . . . . 22 3.2 Processadorexecutandoasmesmasinstru(cid:231)ıessobredadosdiferentes . . . . 23 3.3 Comunica(cid:231)ªoentreprocessadores . . . . . . . . . . . . . . . . . . . . . . 24 3.4 Esquema de um algoritmo genØtico paralelo de granularidade grossa. Cada processo Ø um simples algoritmo genØtico seq(cid:252)Œncial, e hÆ (nªo frequente- mente)comunica(cid:231)ªoentreassubpopula(cid:231)ıes . . . . . . . . . . . . . . . . . 28 3.5 esquema de um algoritmo genØtico paralelo de granularidade (cid:2)na. Esta classedealgoritmo genØticostemumapopula(cid:231)ªodistribu(cid:237)da espacialmente. 29 3.6 Esquema de um algoritmo genØtico paralelo global (master-slave). O pro- cesso mestre armazena a popula(cid:231)ªo, executa opera(cid:231)ıes de um algoritmo ge- nØtico, e distribui indiv(cid:237)duos para os processos escravos. Os processos es- cravossomenteavaliamaaptidªodosindiv(cid:237)duos. . . . . . . . . . . . . . . 30 3.7 Comunica(cid:231)ªoentreprocessosnomodeloilhapara3processadores . . . . . 31 3.8 Migra(cid:231)aodeindiv(cid:237)duospeloprocessom1 nocasode3processadores . . . 32 3.9 ModelosdeGranularidadeGrossa . . . . . . . . . . . . . . . . . . . . . . 34 4.1 Fluxogramadomodelodeilhasparaotimiza(cid:231)ªodeumaRNA . . . . . . . 40 4.2 Fun(cid:231)ªoDeJong1 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 47 4.3 Fun(cid:231)ªoDeJong2 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 49 4.4 Fun(cid:231)ªoDeJong3em3dimensıes . . . . . . . . . . . . . . . . . . . . . . 50 4.5 Fun(cid:231)ªodeTanomaru . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 52 5.1 ArquiteturadeumaRNA . . . . . . . . . . . . . . . . . . . . . . . . . . . 55 5.2 Neur(cid:244)nioarti(cid:2)cial . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 56 5.3 Algoritmo back-propagation . . . . . . . . . . . . . . . . . . . . . . . . . 57 5.4 Representa(cid:231)ªodeumindiv(cid:237)duo . . . . . . . . . . . . . . . . . . . . . . . . 60 5.5 SS1com8ilhas: RMSxGera(cid:231)ªo . . . . . . . . . . . . . . . . . . . . . . 63 5.6 SS2com8ilhas: RMSxGera(cid:231)ªo . . . . . . . . . . . . . . . . . . . . . . 63 5.7 SS1com60gera(cid:231)ıese50Øpocas . . . . . . . . . . . . . . . . . . . . . . 64 5.8 SS2com60gera(cid:231)ıese100Øpocas . . . . . . . . . . . . . . . . . . . . . . 65 5.9 SS1com60gera(cid:231)ıese150Øpocas . . . . . . . . . . . . . . . . . . . . . . 66 ix 5.10 SS2com60gera(cid:231)ıese150Øpocas . . . . . . . . . . . . . . . . . . . . . . 66 x