Planning a Ring-Tree Network to provide Telecommunication Services at Centres of Rural Population

WSEAS TRANS. on INFORMATION SCIENCE & APPLICATIONS Issue 4. Volume 3 Ap il 2006 ISSN: 1790-0832 737 Planning a Ring-T ee Ne wo k o p o ide Telecommunica ion Se ices a Cen es o Ru al Popula ion PABLO CORTES*, JESUS MUNUZURI, JOSE GUADIX, NICOLAS IBANEZ Depa men Ingenie ia de O ganizaci6n Uni e si y o Se ille c/ Camino de los Descub imien os sin, 41092 -Se ille SPAIN *[email p o ec ed] h p://io.us.es/Componen es/P.Co es/ Abs ac : -Nowadays ce ain cen es o u al popula ion a e expe imen ing di icul ies o access high-speed elecommunica ion ne wo ks. This phenomenon a oids he possibili y o accessing o he digi al e olu ion o such a eas. The p i a e companies a e ocusing hei in es men e o s in o he mo e p o i able a eas. In such condi ions, he go e nmen s ha e o p omo e al e na i es o b idge he digi al di ide be ween u al and u ban a eas. We p esen how ing- ee opologies can be used as an adequa e a chi ec u e o inco po a e such less a ou ed a eas in he In o ma ion Socie y. We p esen a case s udy o Andalucia (a wide egion in he sou h o Spain) whe e a decision suppo sys em based on a gene ic algo i hm is implemen ed p o iding cos e ec i e solu ions. We make use o eal li e da a om he elecommunica ion indus y and p esen di e en solu ions sepa a ed by co e age as well as a sensi i i y analysis based on he main ac o s o he cos unc ion. Key-Wo ds: - ing- ee ne wo k, digi al di ide, u al pop ila ion, gene ic algo i hms, ibe op ic, case s udy 1 In oduc ion Nowadays ce ain cen es o u al popula ion a e expe imen ing di icul ies o access high-speed elecommunica ion ne wo ks. I supposes a g ea ba ie o i s de elopmen embedded in o he modem digi al socie y. Ce ainly, he access o in o ma ion and communica ion echnologies can . launch small and medium-sized inns di ec ly in o he hea o egional, na ional and global ma ke s. Also, elemedicine can p o ide access o up- o da e heal h and medical in o ma ion o e en he mos emo e communi ies. These echnologies will acili a e low-cos dis ance lea ning. And hey can empowe ci il socie y, s eng hen democ a ic ins i u ions and make go e nmen s mo e anspa en and accoun able, [lJ. The e a e no many scien i ic e e ences dealing wi h his p oblem. Al hough, [2] shows how he use o new in o ma ion echnologies can imp o e he compe i i eness in u al small businesses. Howe e he p oposals a e in e ms o business solu ions, bu no in e ms o communica ion in as uc u e. Un o una ely, hose communi ies ha mos need he boos ha he echnologies o he in o ma ion and communica ion can p o ide a e leas able o ake ad an age o i . Because, he In o ma ion Socie y e olu ion is suppo ed h ough he elecommunica ion ne wo ks deploymen . The high cos o such in as uc u es o ces he companies o ocus hei e o s in he p o i able communi ies. To gi e a solu ion o i , he go e nmen s ha e o p omo e al e na i es o b idge he digi al di ide be ween u al and u ban a eas. And in many cases hese ac ions mus include he unding o new elecommunica ion in as uc u es. As in o he pa s o he wo ld, in Spain, he p i a e companies ha e ocused hei ne wo k ex ension and mode nisa ion s a egic plans on he mo e p o i able communi ies. I is he case o he big ci ies o he coun y. Recen ly, he Andalusian Regional Go e nmen has been leading a se ies o ini ia i es aimed a p omo ing he de elopmen o ibe op ic ne wo ks a ound he egion. And i s plan ies o p omo e he de elopmen o such ne wo ks, especially, o he less a ou ed a eas. This objec i e is he s a ing poin o ou wo k. The Gene al Di ec o a e o he In o ma ion Socie y o he Jun a de Andalucia asked us o a ool capable o e alua ing he in es men olume equi ed o se up a ibe op ic ne wo k. This ne wo k would ha e o a i e up o he less a ou ed a eas o Andalucia and o connec hem o he bigge ci ies. So ou objec i e was he gene a ion o a ool capable o designing a cos - 738 WSEAS TRANS. on INFORMATION SCIENCE & APPLICATIONS Issue 4, Volume 3, Ap il 2006 ISSN: 1790-0832 e icien backbone ne wo k allowing b idging he digi al di ide and ge ing access o he less a ou ed u al zones. The es o his pape deals wi h he iden i ica ion o he digi al di ide in Andalucia, and he desc ip ion o he echnological backg ound ( espec i ely in sec ion 2 and 3). Subsequen ly, we p esen he model conside ed o design he ne wo k in sec ion 4, and he decision suppo sys em based on a gene ic algo i hm in sec ion 5. The main esul s a e showed in sec ion 6. Finally we inish ou pape wi h he mo e ele an conclusions. 2 The digi al di ide in Andalu�ia In Eu ope, he digi al di ide is a phenomenon ha is p oduced due o he disconnec ion be ween he u al and u ban communi ies. I is because he u al a eas and i s municipali ies end o be non p o i able o he p i a e companies. So he elecommunica ion ne wo ks do no each hose zones. Recen ly, he EU Conunission S a wo king pape , [3], has s a ed he guidelines on c i e ia and modali ies o implemen a ion o s uc u al unds in suppo o elec onic communica ions. The wo king pape shows how he demand agg ega ion o b oadband se ices should be encou aged in o de o ensu e c i ical mass o use s in public adminis a ions whils a oiding dependence on one single ope a o . Fu he mo e he s imula ion o demand o ypes o 'clus e s' o SMEs allows inc easing awa eness and use o JCT. The ac ua ions ha he wo king pape s a es, mus be use ul o inance con en , including e go e nmen , in pa icula local and egional se ices in o de o boos demand o b oadband on a su icien ly ocused basis o de elop supply. Also he Commission s a es ha he Public au ho i ies, and pa icula ly he Regional au ho i ies (as he case o he Jun a de Andalucia is) and local au ho i ies, ha e a key ole o play in he de elopmen o he in o ma ion socie y by (1) using in o ma ion socie y applica ions and se ices in he p ocess o mode nisa ion o se ices p o ided o ci izens and companies, (2) p omo ing he in o ma ion socie y in he egion and (3) moni o ing he e olu ion o he communica ions ne wo ks and se ices p o ision on he egion in o de o a oid exclusion and con ibu e o he balanced de elopmen o egional ac i i ies. In o de o a end o hese guidelines, we di ided Andalucia in h ee se s. Fi s ly, we conside as ype A municipali ies hose whe e exis al e na i e in as uc u e. So, hey a e ci ies whe e a comme cial compe i ion is p oduced (basically be ween ADSL and coaxial cable). Secondly, we s a e ype B municipali ies as hose whe e only exis ADSL bu hey could ha e enough se ice demand o suppo ano he elecommunica ion ope a o . Finally, ype C municipali ies a e hose which has no ADSL in as uc u e due o a s ong lack o demand. 2.1 Classi ica ion o municipali ies The e a e 18 ype A municipali ies: Alme ia, Algeci as, Cadiz, Chiclana de la F on e a, Je ez de la F on e a, La Linea de la Concepcion, El Pue o de San a Ma ia, Ro a, San Fe nando, Sanluca de Ba ameda, Co doba, G anada, Huel a, Jaen, Malaga, Alcala de Guadai a, Dos He manas and Se ille. I supposes 43% o he Andalucia en i e popula ion (3,164,329 inhabi an s). The popula ion li ing in ype B municipali ies is equal o 45% (3,292,609 inhabi an s). The e a e 262 ype B municipali ies. Fu he mo e, we di ide he ype B municipali ies be ween B 1 and B2. Type BI municipali ies a e hose whe e he exis ence o ano he elecommunica ion ope a o would be p o i able; and B2 municipali ies hose non-p o i able. The sepa a ion be ween B 1 and B2 was done conside ing he expec ed Payback pe iod, he Ne P esen Value (NPV) and he In e nal Ra e o Re u n (IRR) o each ype B municipali y. See [4] o an in dep h discussion. In o de o ealize he analysis we conside ed he ini ial in es men as a unc ion o he municipali y size. Basically, we conside ed he DSLAM cos (including a ixed pa and ano he a iable depending on he numbe o use s). As incomes, Cl ENCE & APPLJCATIO S Issue 4, Volume 3. Ap il 2006 ISS 1790-0832 739 we conside ed he mon hly a i mul iplied by he expec ed demand. The demand was calcula ed by using di e en s a is ical app oxima ion me hods (mo ing a e age, exponen ial smoo hing, Hol , linea eg ession and quad a ic eg ession) and minimising he his o ical e o obse ed by a pa ame ic composi ion o hem. [ 4] discusses in dep h abou he demand es ima ion. As cos s, we conside ed he ope a ion and main enance cos s as a 10% o he incomes ( ollowing habi ual alues om he Indus y). He e he possible enla gemen o he DSLAM capaci ies was also included. Finally, o di e ence be ween ype B 1 and ype B2 we selec ed an IRR uppe han 120% and a NPV uppe han 3 millions o eu os o a 10 yea s ho izon. The esul was 43 ype B 1 municipali ies and 219 ype B2. The analysis leads o a s anda d Bl own wi h 32,500 inhabi an s and a s anda d B2 own wi h 8,600 inhabi an s. The es o he owns we e conside ed ype C. So we manage 490 municipali ies ha ep esen he 12% o he en i e popula ion o Andalucia, i.e. 883,637 inhabi an s. Figu e 1 ep esen s he main cha ac e is ics o he municipali ies ( he demand is exp essed as he expec ed numbe o "equi alen ADSL lines" o he inal pe iod o he ho izon). Each "equi alen ADSL line" is conside ed wi h a capaci y o 256 Kb/s. So, inal use s wi h capaci ies uppe han 256 Kb/s a e con e ed in he co esponden numbe o "equi alen ADSL lines". Amoun o Popula ion Numbe o munlclpall les Demand olume Figu e 1. Municipali y classi ica ion The numbe o municipali ies in he bad pa o he digi al di ide is 709. I is a popula ion equal o 2,780,327 inhabi an s, and mos o hem a e li ing in u al a eas. I ep esen s a g ea olume o he Andalusian popula ion ha will su e s ong di icul ies o access o he In o ma ion Socie y and i s bene i s. Figu e 2 de ails he main cha ac e is ics o he digi al di ide. Numbe o munlclpall les C .... Popula ion (.,,. .MI.HO·, .. � Nl.1)1: 12� Demand and Popula ion Figu e 2. Main cha ac e is ics o he digi al di ide 3 Technological backg ound The e a e a wide ange o echnological al e na i es o allow he deploymen o high-speed elecommunica ion ne wo ks. The i s di ision ha we ha e o unde ake is be ween he access ne wo k (u ban ne wo k) and he backbone ne wo k (in e -u ban ne wo k). Nex igu e 3 depic s he di e en al e na i es o be conside ed. ,....,., , . ., '•C Topological { : ���,��!,101 al e na i es � R,ng. Mul iple S o •Ring· R:ing Backbone Access Ne wo k . :� !i ;� .::; ·, -�· )' ./� ' lechnological al e na i es { • Swi ched ne wo,k· PSTH l0SN, x0Sl) • Coble; HFC • Fixed eellulo : Wll·LMOS • MobMa ce l kl · GSM. UMTS • So ellil•. DVB Figu e 3. Access ne wo k and backbone The mos signi ican cos in he access ne wo k is he local loop. The access ne wo k p esen s a g ea echnological he e ogenei y. The physical media can be ibe op ic, coaxial cables, coppe cables cellula adio o e en sa elli e. And he echnology can include adi ional public swi ched elephone ne wo ks, PSTN, IDSN o xDSL, as well as cable elecommunica ion ne wo ks (HFC), ixed cellula ne wo ks (WLL-LMDS) o mobile ne wo ks (GSM, UMTS) in addi ion o he sa elli e mul icas (DVB). Figu e 4 shows se e al o hese al e na i es. I :::· · .. 1111 =-�� Figu e 4. Technological al e na i es o access ne wo ks ISS 1790-0832 Bu he mos impo an pa o he deploymen cos o a uni e sal elecommunica ion ne wo ks is he cos o he backbone ne wo k. The backbone p esen s ce ain homogenei y due o he eno mous ad an ages o he ibe op ic (using SDH o WDM s anda ds). Se e al al e na i es can be used o he ex ension o unk links in he backbone. They depend on he ansmission capaci y and he leng h o he link: •Fibe op ic o high quali y wi hou egene a o s. They achie e op ical ampli ica ion each 100 kilome es. High quali y monomode ibe is necessa y, as well as e bium-doped ibe ampli ie s. This sys em need no elec o-op ic con e sion, and when i 1s combined wi h wa eleng h di ision mul iplexe (WDM/DWDM) can each capaci ies up o 100 Gb/s. •Fibe op ic wi h egene a o s. This op ion does no equi e so e icien and also expensi e equipmen . Lowe quali y ibe can be used bu i equi es he ins alla ion o egene a o s each ce ain dis ance ( ypically 40-50 kilome es). I is adequa e o capaci ies up o 2.4 Gb/s and dis ances sho e han 150 kilome es. •Digi al adio communica ion. I is limi ed o capaci ies up o 34 Mb/s. Fu he mo e he land o og aphy mus be aken in o accoun . Nex sec ion 4 p esen s he design model. In i , we ocus he p oblem in he backbone design, bu conside ing he necessa y e minal in es men ( he local loop). So he las mile co esponding o he selec ion among he echnological al e na i es is no conside ed he e and i will depend on he inal decision o he p i a e company. The objec i e o he wo k is o se up an exis ing in as uc u e capable o eaching he non p o i able poin s o he u al Andalusian egion. In o de o concep ualise he p oblem we make use o G aph Theo y oge he wi h bio-inspi ed algo i hms o sol e i . The p ocess desc ibed in his pape shows he concep ualisa ion o a model ha ep esen s easonably a elecommunica ion ne wo k, as well as he p ocess ollowed in o de o achie e a cos -e ec i e ne wo k deploymen o a egional-size geog aphic a ea. 4 Model The Theo y o G aph de ines a g aph gi en by a se o nodes and a cs: G=(N,A). The nodes can ep esen municipali ies (M) o simple in e sec ions (S) in he unde lying anspo ne wo k whe e he elecommunica ions ne wo k is o be placed. So, hey will be ac i e nodes (municipali ies) o passi e ones ( ypically in e sec ions o he g aph no supplying o ecei ing in o ma ion). A cs ep esen oads linking wo di e en nodes. We used he oad ne wo k o Andalucia ha allows he deploymen o ibe op ic cables. This ini ial g aph was supplied by he Ins i u o de Ca og a ia de Andalucia (ICA) in A c/In o o ma . The g aph is shown in igu e 5. Figu e 5. Ini ial g aph 4.1 P e ious hypo hesis P e iously o he design o he ne wo k, he Jun a de Andalucia s a ed some s a egic decisions ha had o be aken: 1. The ansmission media would be ibe op ic. Tha allows o ensu e a ansmission wi h quali y and capaci y (speed in he o de o hund ed o Gbi /s). 2. The opology should pe mi he e ou ing o he lows among he main municipali ies in case o ails. So, he selec ion o a ing- ee opology was selec ed because i allowed his conce n. The ing o such ne wo k would include all he ype A mu ucipali ies. Ce ainly, he bi-di ec ional sel -healing ing has been he mos used opology in he case o 74 1 adi ional public ope a o s due o i s e ilien wide co e age. 3. The ing should ollow al e na i e ibe op ic ings being cu en ly p ope y o ope a o s di e en om he dominan ope a o . Thi is he case o he a ailable ibe op ic in he ailway and elec ical ne wo ks. This decision will make possible a as e deploymen o he ne wo k in he less a ou ed a eas ca ying ou he ing deploymen in he las s age. Thi decision ixes he ing opology o he igu e 6 case. , .. . .. ·. ·. ·" Figu e 6. Resilien sel -healing ing in he backbone The ing has wo special cha ac e is ics. One o hem is he di ec connec ion be ween Se ille and Huel a. This is o a oid he Do iana Na u al Pa k, one o he la ges p o ec ed biosphe e ese es in Eu ope. The o he one is he di ec connec ion O gi a-Alme ia. This is due o special di icul ies in he oad ne wo k. Bo h p oblems a e sol ed by deploying a pa allel double ibe op ic cable. 4. The ing conside s he da a accumula ion nodes o In e ne connec ion loca ed in Se ille and Malaga. 4.2 Cos model The in as uc u e cos s a e classi ied n ou ca ego ies: 1. Node cos s: a. Fixed cos associa ed o he exjs ence o he node, F; Vi EM. I co esponds o he e minal cable oom adap a ion 742 WSEAS TRANS. on INFORMATION SCIENCE & APPLICATIONS Issue 4 Volume 3 Ap il 2006 ISSN: 1790-0832 o connec he ibe s in o he DSLAM. b. Cos depending on he capaci y managed by he node. G;(C;), ' lieM. I co esponds o he modula equipmen , whe e he ansmi e s and ecei e s a e placed. 2. A c cos s: a. Cos depending on he a c leng h, L;/Di ), l(iJ)eA. I co esponds o he di ches and condui s. b. Cos depending on he a c leng h and i s suppo ed capaci y, C/DiJ,Cmax), V(i,j)eA. I co esponds o he ibe op ic links including ansmi e s, ecei e s and egene a o s o op ical ampli ie s when needed. The node cos s (pa 1 ), as well as he a c cos s depending only on he leng h (pa 2.a) a e de ailed in appendix 1. On he o he hand, wo di e en echnological al e na i es a e conside ed o calcula e he 2.b cos pa . The i s op ion co esponds o high quali y ibe op ic link (wi hou egene a o s). I can be es ima ed as ( 1). (1) The second op ion co esponds o lowe quali y ibe op ic link (wi h egene a o s) ha can be es ima ed as (2). C (D C )= /'SDH,i + l'soHd +P ·D +C - 11+2C ·lc-J u IJ' .... n� n, > J .., D.,.. DWDl>I c,OGb Whe e: (2) • PsDHo and PsDHd a e he o igin and des ina ion SDH mul iplexe cos s. •n0 and nd a e he numbe o links in he SDH equipmen placed in node. Each SDH mul iplexe can se e di e se digi al links. •D/G is he a c dis ance. I is co e ed wi hou egene a o s. •D,i is he a c dis ance. I can be co e ed wi h egene a o s. •P1 /G is he linea cos o a high quali y cable o 24 monomode ibe s plus he cos o connec ing i . •P1 0 is he linea cos o a s anda d cable o 24 monomode ibe s plus he cos o connec ing i . •Coam is he cos o an op ical ampli ica ion sys em. •C eg is he cos o a egene a o . •Dmax is he ampli ica ion maximum dis ance. Typically 140 kilome es o op ion 1 and 40 kilome es o op ion 2. •C, is he cos o DWDM in e ace ca d ( ansmi e / ecei e ) wi h capaci y up o 10 Gb/s. •Cmax is he capaci y ha mus be equipped. Appendix I de ails he nume ical alues o bo h op ions. 4.3 Topological model As sec ion 4.1 s a ed a ing- ee opology was selec ed. This opology consis s o a hie a chical s uc u e gi en by nodes o le el I and nodes o le el 2. Th goal o such a chi ec u e is o simpli y he subsequen ne wo k managemen . The le el 1 nodes a e he en la ge ci ies o Andalusia: Alme ia, Algeci as, Cadiz, Je ez de la F on e a, Co doba, G anada, Huel a, Jaen, Malaga and Se ille plus O gi a (a small municipali y selec ed as pa o he ing due o i s s a egic geog aphic loca ion) .. These nodes depic he ing o he backbone ( igu e 6). The es o nodes a e connec ed a one o hese le el 1 nodes by a ee s uc u e. Howe e he es o nodes could be loca ed in o he ing s uc u e o ou o he ing. In he i s case, he basic in as uc u e has no o be cons uc ed. The e al eady exis he di ch and condui , so we only ha e o conside he cos 2.b. In he o he case ( ou o he ing) we would ha e o conside he cos s o ci il · in as uc u e (2.a) and ansmission link (2.b). See igu e 7. WSEAS TRA S. on JNFORMATIO all Nodes o ln•I 1 eHodes o le¥el 2 in IM ,ng QNodu o lenl 2 ou o he ing Flows be wHn nodu -- Di ec link be wHn nodes o le el 1 ( ing) Supa •b anch. Link be wHn nodH o -- le el 1 and l el 2 h ough lhe ing B anch. L.ink b wHn nodes o le el 2 and le el 2 ou o he ing 0 ln u n,c u e. Condui and di ch 0 0 Figu e 7. Topological s uc u e 5 Decision Suppo Sys em based on a gene ic algo i hm The decision suppo sys em (DSS) is based on a gene ic algo i hm engine. Gene ic algo i hms ha e ecen ly been conside ed o deal wi h di e en kinds o elecommunica ion p oblems. Mos o hem a e in he scope o heo e ical applica ions. A wide-scope on gene ic algo i hm was p esen ed by [5] o design ne wo k ings, and mo e ecen ly [6] and [7]. [8] p esen ed Gen0Sys ha is a opology planning ool based on a gene ic algo i hm o design ee ne wo k in as uc u es. In his scope, [9] de eloped a gene ic algo i hm o he design o opologies in op ical ne wo ks. I is case simila o [ 1 O]. Also, gene ic algo i hms ha e been used o dynamic packing, [11]. Finally, a eal li e implemen a ion can be ound a [ 12]. 5.1 Decision suppo sys em s uc u e The DSS inpu s a e he ca og aphy supplied by he ICA and he socio economic da a wa ehouse da abase p o ided by he Ins i u e Es adis ico de Andalucia (IEA). A e p ocessing he ca og aphy and conside ing he echnological model and he s a egic decisions, we ge he opological model, in e ms o a g aph. The esul was a g aph wi h Issue 4. Volume 3. Ap il 2006 IS N 1790-0832 743 2 796 a cs and 1 920 nodes. 770 o hose nodes ' ' a e municipali ies, he es a e simple in e sec ions. Jn he o he side, he socio economic da a o he municipali ies o Andalusia plus he his o ical demand da a a e used o es ima e he elecommunica ion demand o each o he municipali ies. The demand alues plus he inancial analysis o each u ban node allows us o classi y he municipali ies be ween p o i able and non-p o i able. This allows iden i ying he digi al di ide. These h ee componen s ( he opological model he cos model and he classi ica ion o ' municipali ies) a e in oduced in he algo i hm ha p o ides he solu ion. See igu e 8. � IEA(SIMA} � Sooo--eoonom,c da abNe Digi al di ide lden l l�a lon n ��� ymg anspo ne wo < A c/In o co e ages EJ n !T� modol !llmagic -1.lona Figu e 8. Decision Suppo Sys em s uc u e 5.2 The gene ic algo i hm The dimensioning o he ne wo k, as well as he mul iple opological al e na i es o deploy such ne wo k makes he compu a ionally complex p oblem. In ac , he p oblem can be p o ed as NP-Ha d by simple educ ion o he S eine p oblem. Fu he mo e, gi en a easible solu ion is easy o compu e i s e alua ion (i can be done in polynomial ime), so he p oblem is NP-Comple e oo. Fo his ype o p oblems me aheu is ics app oaches ha e been p o ed o be sui able. And ou p oposal is based on a gene ic algo i hm. The u iliza ion o gene ic algo i hms allows ob aining good solu ions in p oblems wi h a high 744 WSEAS TRANS. on INFORMATION SCIENCE & APPLICATIONS Issue 4, Volume 3, Ap il 2006 ISSN: 1790-0832 numbe o complex cons ain s wi h a di icul ma hema ical o mula ion, as his one is. The s a egy consis s o gene a ing di e se easible solu ions (wi h easy e alua ion) and ecombining hem wi hou losing easibili y. No e how each easible solu ion o ou p oblem mus include he p ede ined ing plus he ee (supe  b anches and b anches, see igu e 7). The p ocedu e ollows he nex h ee s eps: 1. Cons uc ing a sup a-node co esponding o he ing. The ing is concep ualised in one only node composed by all he nodes in he ing (including municipali ies and passi e nodes) and wi h so many inciden a cs as each node o he ing has. 2. Cons uc ing a ee ha con ains he sup a node and all he municipali ies. The passi e nodes (in e sec ion o he anspo ne wo k) can be con enien ly used i necessa y. The gene ic algo i hm gene a es he ne wo k p oposal. 3. Dimensioning he capaci y o he ing. 5.2.1 Cha ac e is ics o he gene ic algo i hm We p oposed a gene ic algo i hm wi h an encoding o he indi iduals genome as shown in igu e 9. The encoding consis s o an a ay wi h so many egis e s as a cs exis in he g aph. I he egis e is se o one hen he a c will be included in he solu ion, o he wise he a c will no be in he solu ion. Addi ionally, he genome mus ensu e he easibili y o he solu ion. So non- easible solu ions a e no accep ed. A e es ing wi h di e en sizes, we ha e conside ed an ini ial popula ion o 20 indi iduals. To gene a e hem we ha e use he K uskal algo i hm o sol e he minimum spanning ee p oblem -MST. No e ha we a e conside ing he ing as a sup a-node. So, gi en 20 di e en se s wi h a c ic i ious cos , we can sol e he co esponden MSTs and a e wa ds he solu ions a e cleaned by e asing he passi e nodes loca ed in a e minal posi ion. The popula ion size is a majo ac o in he e ec i eness o gene ic algo i hms. I has been p o ed ha ela i ely small popula ions allow eaching success ul solu ions wi h li le compu a ion e o , [13]. Ou expe imen s show ha inc easing he popula ion size beyond 20, al hough inc easing he compu a ional e o , is no ewa ded by a co esponding inc ease o pe o mance. We ha e implemen ed wo di e en gene ic ope a o s (see igu e 9): c osso e and mu a ion ope a o s. The pa en selec ion mechanism is andom in o de o en ich he gene ic a ie y. I includes a mechanism o inces p e en ion o a oid he c osso e o gene ically simila pa en s. •Un i o m c osso e ope a o . I he genome o bo h pa en s includes he a c in hei solu ion (i.e. i has he same egis e se o 1, o se o 0), hen he a c is main ained in he o sp ing. O he wise (only one pa en has he a c) he a c is main ained wi h a p obabili y equal o 0.5. •Mu a ion ope a o . The ope a o changes a egis e om 1 o 0, o ice e sa. Tha is, once one egis e has been andomly selec ed, i he a c belongs o he solu ion, hen he a c is e ased. O he wise, i he a c does no belong o he solu ion, hen he a c is included. The applica ion o he gene ic ope a o s can lead o un easible solu ions. The possible in easibili ies a e he ollowing: •A e applying a c osso e ope a o wo ees a e connec ed. This si ua ion gene a es a new g aph and cycles appea . The cycles a e b oken by e asing a andomly selec ed a c o . each cycle. •A e applying a mu a ion ope a o wo si ua ions can appea : oI an a c is included in he solu ion, a cycle can appea . Then, he cycle is b oken by e asing a andomly selec ed a c o he cycle. oI an a c is e ased in he solu ion, he ee is disconnec ed. Then, he ee is econnec ed by means o he sho es pa h algo i hm. W EAS TRANS. on INFORMATION SCIENCE & APPLICATIONS Issue 4, Volume 3, Ap il 2006 ISSN 1790-0832 745 Genome encoding l1lol1!olojol1joj1j1j A, A1 A, A,. A.,. C osso e ope a o Pa en 1 Mu a ion ope a o Figu e 9. Genome encoding and gene ic ope a o s Tes s we e ca ied ou wi h di e en p obabili ies o c osso e and mu a ion ope a o s. Va ying he c osso e p obabili y om 50% o 100% had li le e ec on pe o mance, wi h a alue o 80-90% being ma ginally op imal o he es s ca ied ou . A alue o 80% is used in he main uns. Fo mu a ion, alues be ween 5% and 20% we e seen o be gi ing be e esul s han ypically smalle alues. A alue o 20% is used in he main uns in o de o en ich he gene ic a ie y o he popula ion. Howe e , i is o be no ed ha he gene ic algo i hm is obus . Tha is, he es p oblems' solu ions we e achie ed on he whole wi h a wide ange o pa ame e alues, and wi h no ine- uning equi ed o achie e e iciency. The subs i u ion o new indi iduals (o sp ing) by he old indi iduals (in p e ious popula ion) is made by a anking based eplacemen . We p opose he use o hype geome ic unc ions allowing mo e p obabili y o eplacemen o indi iduals wi h wo se i ness and less p obabili y o eplacemen o indi iduals wi h be e i ness. So he indi idual in anking posi ion-i, ha e a e�lacemen p obabili y equal o q•( 1-q i, whe e q is he eplacemen p obabili y o he wo s indi idual. The alue o he pa ame e q is p og essi e. I s a s wi h a low alue o q in o de o explo e he easibili y egion and hen he alue is p og essi ely inc eased o exploi he niche quali y. Addi ionally, we inco po a ed an indi idual duplici y con ol in he popula ion gene a ion. The numbe o gene a ions o he gene ic algo i hm can be a c i ical pa ame e when we y o each e iciency o he solu ion and sho ime execu ion. Gene ic algo i hms a e i e a i e, and, he e o e, hey can ake e y much ime o execu ion. Howe e he ad an age o gene ic algo i hms is ha hey can be s opped a any ime ha ing he be e solu ion a he momen . A e se e al es s, we selec ed a numbe o 50 i e a ions. The lea ning cu e o he algo i hm is depic ed in igu e 10. 400,00 -1I I 295,00 ,h---���---.--,-----.-..-----.-------� � � m � � N � � � � ; � � I e a ion Figu e 10. Leaming cu e I Nex Table 1 summa izes he alue o pa ame e s selec ed. Table 1. Gene ic al o i hm a ame e s Po ula ion size, N 20 C osso e ope a o p obabili y (mu a ion 0,8 (0,2) 0,2/0,4/0,6/0,8a a P og essi e inc ease o q each en gene a ions. The algo i hm pseudocode is desc ibed in he appendix 2. 5.2.2 Final dimensioning o he ing capaci y We p oposed a bi-di ec ional sel -healing ing. This allows e ou ing he demand lows in case o ail. The p oblem is o de e mine he capaci y o he ing ha allows e ou ing all he lows in case o ail. As he ing capaci y is di ec ly ela ed o he ing cos , we minimize he capaci y capable o gua an eeing he demand lows.