ࡱ> *,)bjbjUU :?? KKKKK____ k _wwwwwwww4JKwwwwwKKwwwwwwKwKwwwwwww4N_ww0w~w~w~Kw wwwwwwwwwwwwwwww~wwwwwwwww :RESUMO O problema da rvore geradora mnima generalizado com coleta de prmios (PAGMG-CP) uma extenso do problema da rvore geradora mnima generalizado (PAGMG). Este problema NP-difcil e neste trabalho descrevem-se vrios algoritmos baseados em duas metaheursticas: BRKGA (Biased Random-Key Genetic Algorithm) e GRASP (Greedy Randomized Adaptive Search Procedure). Os principais parmetros de ambas as metaheursticas foram ajustados com o uso do programa IRACE (Iterated Race for Automatic Algorithm Configuration). A condio de parada para todas as heursticas foi o tempo de execuo de cada instncia de uma heurstica GRASP simples com 200 iteraes internas. Todas as variantes de cada metaheurstica foram comparadas entre si e foram ordenadas decrescentemente de acordo com o desempenho. O estudo computacional indicou que as heursticas desenvolvidas encontram rapidamente solues prximas do timo para todas as instncias de teste com at 439 ns e que as variantes GRASP apresentaram melhor desempenho em geral. Alm disso, na maioria dos casos, os algoritmos com reconexo por caminhos e com reinicializao superam suas verses sem essas estratgias. Palavras-chave: Metaheursticas. rvore geradora mnima generalizada. Coleta de prmios. BRKGA. GRASP. IRACE. ABSTRACT The prize-collecting generalized minimum spanning tree problem (PC-GMSTP) is an extension of the generalized minimum spanning tree problem (GMSTP). This problem is NP-hard and in this work are described several algorithms based on two metaheuristics: BRKGA (Biased Random-Key Genetic Algorithm) and GRASP (Greedy Randomized Adaptive Search Procedure). The main parameters of both metaheuristics were adjusted using the program IRACE (Iterated Race for Automatic Algorithm Configuration). The stop condition for all heuristics was the execution time for each instance of a simple GRASP heuristic with 200 internal iterations. All variants of each metaheuristic were compared to each other and were ordered decreasingly according to their performance. The computational study indicated that the developed heuristics rapidly find near-optimal solutions for all of the test instances with up to 439 nodes and that the GRASP variants presented better overall performance. Furthermore, in most cases, the algorithms with path-relinking and restarts outperformed their versions without these strategies. Keywords: Metaheuristics. Generalized minimum spanning tree. Prize-collecting. BRKGA. GRASP. IRACE.  < G r    YZb hW5\ hW6]hW hW^JhW5CJ\aJ    YZ$dha$ $dh`a$ $$dha$ 8P:pW. A!n"n#n$n% Dp^ 666666666vvvvvvvvv66666686666666666666666666666666666666666666666666666666hH6666666666666666666666666666666666666666666666666666666666666666662 0@P`p2( 0@P`p 0@P`p 0@P`p 0@P`p 0@P`p 0@P`p8XV~_HmHnHsHtHX`X Normal*$,CJKHOJQJ^J_HaJmHnHsHtHDA D 0Default Paragraph FontRiR 0 Table Normal4 l4a (k ( 0No List PP 0 Encabezado $xCJOJQJ^JaJ8B8 0 Body Text d T/T G0Body Text Char CJKHOJQJ^JaJnHtH$/"$ 0List<"2< 0Caption  $xx6],B, 0ndice $PK![Content_Types].xmlj0Eжr(΢Iw},-j4 wP-t#bΙ{UTU^hd}㨫)*1P' ^W0)T9<l#$yi};~@(Hu* Dנz/0ǰ $ X3aZ,D0j~3߶b~i>3\`?/[G\!-Rk.sԻ..a濭?PK!֧6 _rels/.relsj0 }Q%v/C/}(h"O = C?hv=Ʌ%[xp{۵_Pѣ<1H0ORBdJE4b$q_6LR7`0̞O,En7Lib/SeеPK!kytheme/theme/themeManager.xml M @}w7c(EbˮCAǠҟ7՛K Y, e.|,H,lxɴIsQ}#Ր ֵ+!,^$j=GW)E+& 8PK!Ptheme/theme/theme1.xmlYOo6w toc'vuر-MniP@I}úama[إ4:lЯGRX^6؊>$ !)O^rC$y@/yH*񄴽)޵߻UDb`}"qۋJחX^)I`nEp)liV[]1M<OP6r=zgbIguSebORD۫qu gZo~ٺlAplxpT0+[}`jzAV2Fi@qv֬5\|ʜ̭NleXdsjcs7f W+Ն7`g ȘJj|h(KD- dXiJ؇(x$( :;˹! I_TS 1?E??ZBΪmU/?~xY'y5g&΋/ɋ>GMGeD3Vq%'#q$8K)fw9:ĵ x}rxwr:\TZaG*y8IjbRc|XŻǿI u3KGnD1NIBs RuK>V.EL+M2#'fi ~V vl{u8zH *:(W☕ ~JTe\O*tHGHY}KNP*ݾ˦TѼ9/#A7qZ$*c?qUnwN%Oi4 =3ڗP 1Pm \\9Mؓ2aD];Yt\[x]}Wr|]g- eW )6-rCSj id DЇAΜIqbJ#x꺃 6k#ASh&ʌt(Q%p%m&]caSl=X\P1Mh9MVdDAaVB[݈fJíP|8 քAV^f Hn- "d>znNJ ة>b&2vKyϼD:,AGm\nziÙ.uχYC6OMf3or$5NHT[XF64T,ќM0E)`#5XY`פ;%1U٥m;R>QD DcpU'&LE/pm%]8firS4d 7y\`JnίI R3U~7+׸#m qBiDi*L69mY&iHE=(K&N!V.KeLDĕ{D vEꦚdeNƟe(MN9ߜR6&3(a/DUz<{ˊYȳV)9Z[4^n5!J?Q3eBoCM m<.vpIYfZY_p[=al-Y}Nc͙ŋ4vfavl'SA8|*u{-ߟ0%M07%<ҍPK! ѐ'theme/theme/_rels/themeManager.xml.relsM 0wooӺ&݈Э5 6?$Q ,.aic21h:qm@RN;d`o7gK(M&$R(.1r'JЊT8V"AȻHu}|$b{P8g/]QAsم(#L[PK-![Content_Types].xmlPK-!֧6 +_rels/.relsPK-!kytheme/theme/themeManager.xmlPK-!Ptheme/theme/theme1.xmlPK-! ѐ' theme/theme/_rels/themeManager.xml.relsPK]   4W @ @@UnknownG*Ax Times New Roman5Symbol3" ArialI xP!Liberation SerifG& xP!Liberation SansACambria Math" dGdG9! 0 $P 4!xxRESUMOHelioHelioOh+'0x  4 @ LX`hpRESUMOHelioNormal_WordconvHelio2Microsoft Office Outlook@F#@ni N@ni N9՜.+,0 hp|   RESUMO Title  "#$%&'(+Root Entry FN-1Table ~WordDocument:SummaryInformation(DocumentSummaryInformation8!CompObjy  F'Microsoft Office Word 97-2003 Document MSWordDocWord.Document.89q  F#Documento do Microsoft Office Word MSWordDocWord.Document.89q