A GA(TS) hybrid algorithm for scheduling in computational grids

A GA(TS) Hyb id Algo i hm o Scheduling in Compu a ional G ids Fa os Xha a1, Juan A. Gonzalez1, Kesha P. Dahal2, and Aji h Ab aham3 1Depa men o Languages and In o ma ics Sys ems Technical Uni e si y o Ca alonia, Ba celona, Spain [email p o ec ed] 2School o In o ma ics, Uni e si y o B ad o d, UK [email p o ec ed] 3Cen e o Excellence o Quan i iable Quali y o Se ice No wegian Uni e si y o Science and Technology, No way [email p o ec ed] Abs ac . The hyb idiza ion o heu is ics me hods aims a explo ing he syne gies among s and alone heu is ics in o de o achie e be e e- sul s o he op imiza ion p oblem unde s udy. In his pape we p esen a hyb idiza ion o Gene ic Algo i hms (GAs) and Tabu Sea ch (TS) o scheduling in compu a ional g ids. The pu pose in hyb idizing hese heu is ics is o bene i he explo a ion o he solu ion space by a popu- la ion o indi iduals wi h he exploi a ion o solu ions h ough a sma sea ch o he TS. Ou GA(TS) hyb id algo i hm uns he GA as he main algo i hm and calls TS p ocedu e o imp o e indi iduals o he popula ion. We e alua ed he p oposed hyb id algo i hm using di e en G id scena ios gene a ed by a G id simula o . The compu a ional esul s showed ha he hyb id algo i hm ou pe o ms bo h he GA and TS o he makespan alue bu canno ou pe o m hem o he low ime o he scheduling. 1 In oduc ion Me a-heu is ics a e he de ac o app oach o cope in p ac ice wi h he compu a- ionally ha d op imiza ion p oblems. Me a-heu is ics a e in ac hyb id in hei na u e since hey consis o a high le el algo i hm ha guides he sea ch us- ing o he pa icula me hods. Fo ins ance, in popula ion based me a-heu is ics, such as Gene ic Algo i hms, he solu ion space is explo ed h ough a popula ion o indi iduals and he e a e used me hods o gene a ing he ini ial popula ion, compu ing he i ness o indi iduals as well gene ic ope a o s o ansmi he gene ic in o ma ion om pa en s o o sp ings. Besides using me a-heu is ics as s and alone app oaches o sol ing ha d combina o ial op imiza ion p oblems, du ing he las yea s, he a en ion o e- sea che s has shi ed o conside ano he ype o high le el algo i hms, namely hyb id algo i hms. These algo i hms do no ollow any conc e e me a-heu is ic, bu a he hey combine o he me a-heu is ics and/o o he me hods (e.g. exac me hods) yielding hus hyb id me a-heu is ics. Xha a, F., González, J. A., Dahal, K. P., Ab aham, A. A GA(TS) hyb id algo i hm o scheduling in compu a ional g ids. A: In e na ional Con e ence on Hyb id A i icial In elligence Sys ems. "Hyb id A i icial In elligence Sys ems, 4 h In e na ional Con e ence, HAIS 2009: Salamanca, Spain, June 10-12, 2009: p oceedings". Be lín: Sp inge , 2009, p. 285-292. The inal au hen ica ed e sion is a ailable online a h ps://doi.o g/10.1007/978-3-642-02319-4_34 The a ionale behind he hyb idiza ion esides in he “no ee lunch he- o em” [16] s a ing ha “... all algo i hms ha sea ch o an ex emum o a cos unc ion pe o m exac ly he same, when a e aged o e all possible cos unc ions. In pa icula , i algo i hm A ou pe o ms algo i hm B on some cos unc ions, hen loosely speaking he e mus exis exac ly as many o he unc ions whe e B ou pe o ms A.” Essen ially, he heo em s a es ha he e is no any sea ch me hod o op imiza ion which ou pe o ms all o he sea ch me hods. This sugges s ha one can use exis ing algo i hms as componen s o designing new e icien sea ch algo i hms and expec imp o ed pe o mance o he newly ob ained algo i hm o some cos unc ions. The e a e a leas wo majo issues in designing hyb id me a-heu is ics: (a) how o choose he (exis ing) heu is ic me hods o combine, and (b) how o com- bine he chosen heu is ic me hods in o new hyb id app oaches. Un o una ely, he e a e no heo e ical ounda ions o hese issues. Fo he o me , di e en classes o sea ch algo i hms can be conside ed o he pu poses o hyb idiza ion, such as exac me hods, simple heu is ic me hods (ad hoc me hods) and me a- heu is ics. Mo eo e , me a-heu is ics hemsel es a e classi ied in o local sea ch based me hods, popula ion based me hods and o he classes o na u e inspi ed me a-heu is ics. The e o e, in p inciple, one could combine any me hods om he same class o me hods om di e en classes. Rega ding he la e , he e a e some a emp s o axonomies o hyb id me a-heu is ics [8, 5]; in ac , he common ap- p oach is o y ou in sma ways, based on domain knowledge o p oblem a hand and cha ac e is ics o heu is ics me hods, di e en hyb id app oaches and shed ligh on he pe o mance o he hyb id app oach h ough empi ical s udies. F amewo ks ha acili a e he as p o o yping ha e been also p o ided in he me a-heu is ics li e a u e [2, 4]. In his pape , we p esen a hyb id algo i hm o he p oblem o scheduling independen asks in compu a ional g ids. A compu a ional g id is a dis ibu ed in as uc u e o compu a ional esou ces (ha dwa e, so wa e, da a s o ages, e c.) highly he e ogenous, in e connec ed h ough he e ogenous ne wo ks. One key issues in G ids is o design e icien schedule s, which will be used as pa o middlewa e se ices o p o ide e icien planning o use s’ asks o g id nodes. Recen ly, heu is ic app oaches ha e been p esen ed o he p oblem [1, 7, 9, 11, 10, 12], howe e , p ope hyb id app oaches a e lacking. Ou hyb id app oach combines Gene ic Algo i hms (GAs) and Tabu Sea ch (TS) me hods. Roughly, ou hyb id algo i hm uns he GA as he main algo i hm and calls TS p ocedu e o imp o e indi iduals o he popula ion. Ou hyb id algo i hms deals wi h he scheduling p oblem as a bi-objec i e op imiza ion p oblem, in which makespan is conside ed a p ima y objec i e and low ime a seconda y one. Such op imiza ion scheme is usually e e ed o as hie a chic op imiza ion. The p oposed algo i hm has been expe imen ally e alua ed and he esul s a e con as ed agains bo h GAs and TS o he p oblem. The es o he pape is o ganized as ollows. In Sec ion 2, we b ie ly p esen he scheduling o independen asks conside ed as a bi-objec i e op imiza ion p oblem in his wo k. In Sec ion 3, ypes o hyb idiza ions a e p esen ed. The GAs and TS o he p oblem as well as he hyb id app oach a e gi en in Sec ion 4. The expe imen al s udy and some compu a ional esul s a e gi en in Sec ion 5. We conclude in Sec ion 6 wi h some ema ks and indica ions o u u e wo k. 2 Scheduling o independen asks in compu a ional g ids Many applica ions a e being de eloped o be un in compu a ional g ids o ben- e i om he la ge amoun o compu a ional esou ces in such sys ems. In simple G id sys ems such as en ep ise g ids o campus g ids, he use can use queuing sys ems such as Condo o Sun G id Engine; e en, manual selec ion o he ap- p op ia e machines o unning he applica ion is possible in such g ids. In la ge scale and highly he e ogenous g ids, howe e , his edious ask is au oma ically handled by g id schedule s, which a e expec ed o ind planning o use s’ asks and applica ions o mos app op ia e machines. One class o g id schedule s a e ba ch schedule s, ha is, schedule s ha compu e a planning o a se o asks/applica ions al oge he o a se o g id nodes. Me a-heu is ic app oaches a e use ul o he design o such schedule s, since hey usually p o ide quali y solu ions in sho imes. In his wo k we a e in e es ed in scheduling o independen asks o g id esou ces. The o mal de ini ion o he p oblem is based on he de ini ion o he Expec ed Time o Compu e (ETC) ma ix in which ET C[j][m] indica es an es ima ion o how long will i ake o comple e ask jusing esou ce m. Unde he ETC ma ix model, he independen scheduling can be de ined as ollows: –A numbe o independen asks o be alloca ed o g id esou ces. Each ask has o be p ocessed en i ely in a single esou ce and is no p eemp ed (once s a ed, a ask uns un il comple ion). –A numbe o machines candida es o pa icipa e in he alloca ion o asks. –The wo kload (in millions o ins uc ions) o each ask. –The compu ing capaci y o each machine (in Mips). –The eady imes, deno ed eadym, indica ing when machine mwill ha e inished he p e iously assigned asks. A he beginning, usually eady imes a e conside ed equal o ze o (all machines in he machine se a e a ailable o ask alloca ion). –The ET C ma ix o size nb asks ×nb machines, whe e ET C[j][m] is he alue o he expec ed ime o compu e o ask jin machine m. The quali y o a schedule can be measu ed using se e al op imiza ion c i e ia, such as minimizing he makespan ( ha is, he inishing ime o he la es ask), he low ime (i.e., he sum o inaliza ion imes o all he asks), he comple ion ime o asks in e e y machine (closely ela ed o makespan), o maximizing he esou ce u iliza ion. In his wo k we conside ha he mos impo an c i e ion is ha o minimizing he makespan. Addi ionally, we conside he minimiza ion o he low ime o he g id sys em as a seconda y c i e ion. These wo c i e- ia a e o mally de ined as ollows: makespan: minSi∈Sched{maxj∈T asks Fj}and, low ime: minSi∈Sched{Pj∈T asks Fj}, whe e Fjdeno es he ime when ask j inalizes and Sched is he se o all possible schedules. No ice ha by consid- e ing he makespan as he main objec i e o op imize and he low ime as a secunda y goal, we aim a designing a hie a chical algo i hm, in which he alue o makespan can no be wo sened when op imizing he low ime. 3 Hyb idiza ion o me a-heu is ics As men ioned ea lie , he hyb idiza ion s a ed as an app oach ha ies o combine ully o pa ially wo o mo e algo i hms o enhance he pe o mance o s and alone sea ch me hod o op imiza ion p oblems. To achie e such goal, he hyb idiza ion should be able o embed he bes ea u es o he combined algo i hms in o a new high le el algo i hm. Cu en hyb id models ake in o accoun wo main aspec s: (1) Type o me hods o hyb idize, and (2) Le el o hyb idiza ion. The i s e e s o he ype o he me hods o be hyb idized. Essen ially we could conside wo cases: (a) me a-heu is ics + me a-heu is ics and (b) me a-heu is ics + speci ic sea ch me hod. In he i s case he componen s a e me a-heu is ics while in he la e , a me a-heu is ic is combined wi h ano he ype o sea ch me hod, which could be an exac algo i hm, dynamic p og amming, cons ain p og amming o o he AI echniques. In his wo k we a e conside ing he i s case, being he me a- heu is ics he GAs and TS me hod. The le el o hyb idiza ion, on he o he hand, e e s o he deg ee o coupling be ween he me a-heu is ics, he execu ion sequence and he con ol s a egy. Le el o hyb idiza ion. Loosely coupled: in his case he hyb idized me a- heu is ics p ese e hei iden i y, namely, hei low is ully used in he hyb idiza- ion. This case is also e e ed o as high le el o hyb idiza ion.S ongly coupled: in his case, he hyb idized me a-heu is ics in e -change hei inne p ocedu es, esul ing in a low le el o hyb idiza ion. Execu ion sequence. Sequen ial ( he me a-heu is ics lows a e un sequen- ially) o Pa allel ( he me a-heu is ics lows a e un in pa allel.) Con ol s a egy. Coe ci e: he main low is ha o one o he me a-heu is ics, he o he me a-heu is ics low is subo dina ed o he main low. Coope a i e: he me a-heu is ics explo e he solu ion space coope a i ely (e en ually, hey can explo e di e en pa s o he solu ion space.) 4 The p oposed GA(TS) hyb id app oach Fo he design o ou hyb id app oach we conside wo well-known me a-heu is ics: Gene ic Algo i hms (GAs) and Tabu Sea ch (TS). Bo h GAs and TS ha e been de eloped o he independen ask scheduling in Xha a e al. [11] and [12] in sequen ial se ing. We ha e conside ed he S eady-S a e GA in his wo k. The choice o hese wo me a-heu is ics is based on he ollowing obse a ions. Fi s , g id schedule s should be e y as in o de o adap o dynamic na u e o compu- a ional g ids. The e o e, a as con e gence o he main algo i hm is p e e able in his case, which can be achie ed h ough a good adeo be ween explo a ion and exploi a ion o he sea ch. Second, in o de o achie e high quali y planning in a e y sho ime, i is sugges i e o combine he explo a ion o he solu ion space by a popula ion o indi iduals wi h he exploi a ion o neighbo hoods o solu ions h ough local sea ch. In such case, GAs and TS a e among he bes ep esen a i es o popula ion based and local sea ch me hods, espec i ely. We a e hus conside ing he case o hyb idiza ion o wo me a-heu is ics unning in sequen ial en i onmen . We ha e conside ed a low le el hyb idiza ion and he coe ci e con ol s a egy. Roughly, ou hyb id algo i hm uns he GA as he main algo i hm and calls TS o imp o e indi iduals o he popula ion. The hyb idiza ion scheme is shown in Figu e 1. I should be no ed ha in he hyb idiza ion scheme in Figu e 1, ins ead o eplacing he mu a ion p ocedu e o GAs by he TS p ocedu e, we ha e added a new unc ion o he GA Popula ion class (namely apply TabuSea ch) o applying he TS. This new unc ion could be applied o any indi idual o he cu en popula ion, howe e , his is compu- a ionally cos ly. In ou case, gi en ha we wan o un he G id schedule in sho imes, he apply TabuSea ch is applied wi h small p obabili y4. In ac , his pa ame e can well be used o une he con e gence o he GA since TS usually p o ides subs an ial imp o emen s o indi iduals. Fig. 1. The hyb id GA(TS) scheme. We sho ly p esen nex bo h he GA and TS me a-heu is ics o independen ask scheduling in compu a ional g ids ( e e o [11] and [12] o de ails.) 4.1 GAs o he scheduling p oblem in G ids GAs a e a popula ion-based app oaches whe e indi iduals ep esen possible so- lu ions, which a e successi ely e alua ed, selec ed, c ossed, mu a ed and eplaced by simula ing he Da winian e olu ion ound in na u e. We ha e implemen ed he S eady S a e e sion o GAs. In S eady S a e GAs, a ew good indi idu- als o popula ion a e selec ed and c ossed. Then, he wo s indi iduals o he popula ion a e eplaced by he newly gene a ed descendan s; he es o he in- di iduals o he popula ion su i e and pass o he nex gene a ion. The es o gene ic ope a o s and me hods a e as ollows: Ini ializa ion me hods a e MCT and LJFR-SJFR implemen ed in [14, 15]; Selec ion ope a o : Linea anking; 4This is a use inpu pa ame e . Fo he pu poses o his wo k, apply TabuSea ch is applied oughly o 30% o indi iduals Table 1. Simula o s’ con igu a ion. Small Medium La ge Ini ./To al hos s 32 64 128 Mips n(1000, 175) Ini ./To al asks 512 1024 2048 Wo kload n(250000000, 43750000) Hos selec ion All Task selec ion All Local policy SPTF Numbe o uns 30 C osso e ope a o : Cycle C osso e (CX); Mu a ion ope a o : Mu a e Rebal- ancing. The conc e e alues o he es o pa ame e s a e gi en in Sec ion 5. 4.2 Tabu Sea ch o he scheduling p oblem in G ids Tabu Sea ch (TS) has shown i s e ec i eness in a b oad ange o combina o- ial op imiza ion p oblems and dis inguishes o i s lexibili y in exploi ing do- main/p oblem knowledge. The main p ocedu es used in TS a e summa ized nex . The ini ial solu ion is ound using Min-Min me hod [14]. Rega ding his o ical memo y, bo h sho and long e m memo ies ha e been used in TS algo i hm. Fo he ecency memo y, a ma ix T L (nb asks×nb machines) is used o main- ain he abu s a us. In addi ion, a abu hash able (T H) is main ained in o de o u he il e he abu solu ions. The neighbo hood explo a ion is done using a s eepes descen - mildes ascen me hod using wo ypes o mo emen s, namely, ans e (mo es a ask om a machine o ano he one, app op ia ely chosen) and swap ( wo asks assigned o wo di e en machines a e swapped). Fu he , se - e al aspi a ion c i e ia a e used o emo e he abu s a us o mo emen s. They a e de ined using he i ness o solu ions as well as in o ma ion om ecency ma- ix. In ensi ica ion is implemen ed using eli e solu ions while so di e si ica ion uses penal ies o ETC alues, ask dis ibu ion and ask eezing. Finally, s ong di e si ica ion is implemen ed using la ge pe u ba ions o solu ions. The conc e e alues o he es o pa ame e s a e gi en in Sec ion 5. 5 Expe imen al s udy We ha e used a G id simula o [13] o e alua e ou hyb id algo i hm. Simula ion en i onmen se ing. Fo he e alua ion o he GA(TS) hyb id algo- i hm, we ha e used h ee G id scena ios: small, medium and la ge size. They consis , espec i ely, o 32 hos s/521 machines, 64 hos s/1024 machines, and 128 hos s / 2048 machines. Each scena io is gene a ed om he simula o bu he numbe o asks and machines a e kep cons an , ha is, o bo h o hem, espec- i ely, he numbe o ini ial asks equals he o al numbe o asks in he sys em and and he ini ial numbe o machines equals he o al numbe o machines. The con igu a ion o simula o ollows he pa ame e s gi en in Table 1. In he able n(·,·) e e s o no mal dis ibu ion; SPTF s ands o Sho es P ocessing Time Fi s local policy. The pa ame e alues o he GA and TS algo i hms used in he hyb id algo i hm a e gi en in Tables 2 and 3. Table 2. Pa ame e alues o GA. Pa ame e Value e olu ion s eps 20 ·nb asks popula ion size 4 ·(log2(nb asks)−1) in e media e pop. (pop size)/3 c oss p obab. 1.0 mu a ion p obab. 0.4 Table 3. Pa ame e alues o TS. Pa ame e Value #i e a ions nb asks ·nb mach max. abu s a us 1.5·nb mach # epe i ions be o e ac i a ing 4 ∗ln(nb asks)· in ensi ic./di e si ic. ln(nb mach) #i e a ions pe in ensi ic./di e si ic. log2(nb asks) #i e a ions max abu/2− o aspi a ion c i e ia −log2(max abu) Compu a ional esul s and e alua ion. The simula o is un530 imes o each scena io and compu a ional esul s o makespan and low ime a e a e aged. S anda d de ia ion (a 95% con idence in e al) is also epo ed. The esul s o makespan and low ime a e gi en in Table 4 and Table 5, esp. Table 4. Makespan alues. Small Medium La ge GA (hie a chic) 2808662.116 2760024.390 2764455.222 ±1,795% ±1,010% ±0,745% TS (hie a chic) 2805531.301 2752355.018 2748878.934 ±1,829% ±1,056% ±0,669% GA(TS) (hie a chic) 2805519.428 2751989.166 2812776.300 ±1,829% ±1,058% ±1,176% Table 5. Flow ime alues. Small Medium La ge GA (hie a chic) 709845463.699 1405493291.442 2811723598.025 ±1,209% ±0,655% ±0,487% TS (hie a chic) 710189541.278 1408001699.550 2812229021.221 ±1,124% ±0,616% ±0,455% GA(TS) (hie a chic) 711183944.069 1409127007.870 2811605453.116 ±1,174% ±0,604% ±0,465% As can be seen om Table 4, o makespan alue he GA(TS) ou pe o ms bo h GA and TS o small and medium size g id scena ios bu achie es wo se alue o la ge size scena io. On he o he hand, om Table 5, we can see ha GA(TS) pe o ms be e han bo h GA and TS o low ime alue only o la ge size ins ances. So, GA(TS) pe o ms be e o makespan alue, which is consid- e ed p ima y objec i e in hie a chic e sion, han o low ime pa ame e , which is a seconda y objec i e. In ac , close o (sub-)op imal solu ions, makespan and low ime beha e as con adic o y objec i es and hus unde ou hie a chic model, he imp o emen s o low ime a e di icul o happen. 6 Conclusions In his pape we ha e p esen ed a hyb id GA(TS) algo i hm o he p oblem o independen scheduling in compu a ional g ids. The hyb idiza ion ollows a low le el app oach in which GA is he main low and TS is subo dina ed o i . The 5AMD A hlon 64 3200+, 2GB RAM. objec i e unc ion conside ed is ha o bi-objec i e in which makespan is p ima y objec i e and low ime is seconda y. The expe imen al e alua ion showed ha GA(TS) ou pe o ms bo h GA and TS o makespan alues o small and medium size g id scena ios and o low ime alues o la ge size g id scena ios. The GA(TS) hyb idiza ion scheme is e y app op ia e o pa allel implemen- a ion, by unning TS me hod o all indi iduals o GA popula ion in pa allel. Re e ences 1. A. Ab aham, R. Buyya, and B. Na h. Na u e’s heu is ics o scheduling jobs on compu a ional g ids. In The 8 h IEEE In e na ional Con e ence on Ad anced Compu ing and Communica ions, India, 2000. 2. E. Alba, F. Almeida, M. Blesa, C. Co a, M. D´ıaz, I. Do a, J. Gaba ´o, C. Le´on, G. Luque, J. Pe i , C. Rod ´ıguez, A. Rojas, and F. Xha a. E icien pa allel LAN/WAN algo i hms o op imiza ion. The Mallba p ojec . Pa allel Compu - ing, 32(5-6):415–440, 2006. 3. T. B aun, H. Siegel, N. Beck, L. Boloni, M. Maheswa an, A. Reu he , J. Robe son, M. Theys, and B. Yao. A compa ison o ele en s a ic heu is ics o mapping a class o independen asks on o he e ogeneous dis ibu ed compu ing sys ems. Jou nal o Pa allel and Dis ibu ed Compu ing, 61(6):810–837 (2001). 4. S. Cahon, N. Melab and E. Talbi. Building wi h pa adisEO eusable pa allel and dis ibu ed e olu iona y algo i hms. Pa allel Compu ing 30, 5-6, 677-697, 2004. 5. L. Jou dan, M. Basseu and E. Talbi. Hyb idizing Exac Me hod and Me aheu is- ics: A Taxonomy. Eu opean Jou nal o Ope a ional Resea ch, (Online, 2008). 6. H.C. Lau, W.C. Wan, M.K. Lim, and S. Halim. A De elopmen F amewo k o Rapid Me a-Heu is ics Hyb idiza ion. In P oc. o he 28 h Annual In e na ional Compu e So wa e and Applica ions Con e ence, 362-367, 2004. 7. G. Ri chie and J. Le ine. A as , e ec i e local sea ch o scheduling independen jobs in he e ogeneous compu ing en i onmen s. TechRep, Cen e o In elligen Sys ems, Uni e si y o Edinbu gh, 2003. 8. E. Talbi. A Taxonomy o Hyb id Me aheu is ics. J. o Heu . 8(5), 541-564, 2002. 9. F. Xha a. A Hyb id E olu iona y Heu is ic o Job Scheduling in Compu a ional G ids. Sp inge Se ies: S udies in Comp. In ell., Vol. 75, Chap. 10, 2007. 10. F. Xha a, L. Ba olli, and A. Du esi, An Expe imen al S udy on Gene ic Algo- i hms o Resou ce Alloca ion on G id Sys ems, JOIN 8(4), 427 - 443, 2007. 11. F. Xha a, J. Ca e e o, A. Ab aham. Gene ic Algo i hm Based Schedule s o G id Compu ing Sys ems. In e na ional Jou nal o Inno a i e Compu ing, In o ma ion and Con ol, Vol. 3, No.5, pp. 1-19, 2007. 12. F. Xha a, J. Ca e e o, B. Do onso o and E. Alba. Tabu Sea ch Algo i hm o Scheduling Independen Jobs in Compu a ional G ids. Compu e s and In o ma ics, 2009. To appea . 13. F. Xha a, J. Ca e e o, L. Ba olli and A. Du esi. Requi emen s o an E en -Based Simula ion Package o G id Sys ems. JOIN, 8(2):163-178, 2007. 14. F. Xha a, J. Ca e e o, L. Ba olli and A. Du esi. Immedia e Mode Scheduling in G id Sys ems. In . J. o Web and G id Se ices, Vol.3 No.2, 219-236, 2007. 15. F. Xha a, L. Ba olli and A. Du esi. Ba ch Mode Schedule s o G id Sys ems. In e na ional Jou nal o Web and G id Se ices, Vol. 3, No. 1, 19-37, 2007. 16. D.H. Wolpe , W.G. Mac eady. No F ee Lunch Theo ems o Op imiza ion, IEEE T ansac ions on E olu iona y Compu a ion 1(1), 67-82, 1997.