A Study of Geometric Semantic Genetic Programming with Linear Scaling

MMAA Mes ado em Mé odos Analí icos A ançados Mas e P og am in Ad anced Analy ics NOVA In o ma ion Managemen School Ins i u o Supe io de Es a ís ica e Ges ão da In o mação Uni e sidade No a de Lisboa A STUDY OF GEOMETRIC SEMANTIC GENETIC PROGRAMMING WITH LINEAR SCALING Be in Sakallioglu Disse a ion p esen ed as pa ial equi emen o ob aining he Mas e ’s deg ee in Da a Science and Ad anced Analy ics, wi h a specializa ion in Da a Science NOVA In o ma ion Managemen School Ins i u o Supe io de Es a ís ica e Ges ão de In o mação Uni e sidade NOVA de Lisboa A STUDY OF GEOMETRIC SEMANTIC GENETIC PROGRAMMING WITH LINEAR SCALING by Be in Sakallioglu Disse a ion p esen ed as pa ial equi emen o ob aining he Mas e ’s deg ee in Da a Science and Ad anced Analy ics, wi h a specializa ion in Da a Science Ad ise : P o . D . Leona do Vanneschi Feb ua y, 2023 Ad iso : A S udy o Geome ic Seman ic Gene ic P og amming wi h Linea Scaling Copy igh ©Be in Sakallioglu, NOVA In o ma ion Managemen School, NOVA Uni- e si y Lisbon. The NOVA In o ma ion Managemen School and he NOVA Uni e si y Lisbon ha e he igh , pe pe ual and wi hou geog aphical bounda ies, o ile and publish his disse a ion h ough p in ed copies ep oduced on pape o on digi al o m, o by any o he means known o ha may be in en ed, and o dissemina e h ough scien i ic eposi o ies and admi i s copying and dis ibu ion o non-comme cial, educa ional o esea ch pu poses, as long as c edi is gi en o he au ho and edi o . This documen was c ea ed wi h he (pd /Xe/Lua)L A T EX p ocesso and he NOVA hesis empla e ( 6.10.12) [1]. To Anka a. Acknowledgemen s I would like o exp ess my deepes g a i ude o my es eemed p o esso , Leona do Vanneschi, o his excep ional men o ship and cons uc i e eedback h oughou my academic jou ney. His ema kable in ellec and dedica ion o he pu sui o knowledge ha e been a sou ce o inspi a ion. I am deeply indeb ed o him o his pa ience, unde s anding, and kindness. His unwa e ing suppo and us ha e gi en me s eng h o o e come challanges. My hea el app ecia ion goes o e e y pe son in my beau i ul big amily wi h special hanks o my mom, dad and wonde ul b o he , U ku. Thank you o gi ing me li e, you uncondi ional lo e, suppo , and you exis ence. I am lucky o ha e all o you. And all he amazing people in my li e, my iends, my people in Anka a, I am glad ha I g ew up wi h all o you. You ha e all played a signi ican ole in shaping me. And o Lisbon, and he people who emb aced and lo ed me in his ci y. Thank you o being a amily o me in a place so a away om my home. To all hese people and e e yone who di ec ly o indi ec ly helped me wi h my hesis pe iod, I am deeply g ea ul, his would ha e been impossible wi hou you. And inally, he cumula i e knowledge o humani y, hank you. Despi e e e y hing, ending up on his plane has been g ea ! ii Con en s Lis o Figu es x ii Lis o Tables xix 1 In oduc ion 1 2 Theo e ical Backg ound 3 2.1 Machine Lea ning .............................. 3 2.1.1 Da a ................................. 4 2.1.2 Lea ning ............................... 4 2.2 Op imiza ion ................................. 6 2.2.1 Fi ness Landscapes ......................... 7 2.3 BioInspi ed and E olu iona y Algo i hms ................ 7 2.3.1 Gene ic P og amming ....................... 8 2.3.2 Geome ic Seman ic Gene ic P og amming ........... 12 2.3.3 GSGP Implemen a ion ....................... 16 2.4 Linea Scaling ................................ 17 3 Li e a u e Re iew 19 3.1 Seman ics in GP ............................... 19 3.2 LS in GP ................................... 21 4 Me hodology 23 4.1 Gene al O ganiza ion o he GSGP-LS Lib a y ............. 23 4.2 GSGP ..................................... 24 4.3 Popula ion .................................. 25 4.3.1 Ini ializa ion ............................. 25 4.3.2 O sp ing C ea ion ......................... 26 4.3.3 Sco ing a Popula ion ........................ 27 4.4 Indi idual .................................. 29 x 4.4.1 Recons uc ion ........................... 29 4.5 Node ..................................... 29 5 Expe imen al S udy 31 5.1 Expe imen al Se up ............................. 31 5.1.1 Pa ame e Se ings ......................... 31 5.1.2 Case S udies ............................. 33 5.2 Expe imen al Resul s ............................ 44 5.2.1 Reg ession Expe imen s ...................... 44 5.2.2 Syn he ic Da ase Expe imen s .................. 50 5.2.3 Classi ica ion Expe imen s .................... 53 5.3 Discussion on Resul s ............................ 57 6 Conclusions and Fu u e Wo k 61 Bibliog aphy 63 x i Lis o Figu es 2.1 Con usion Ma ixandE o Measu es o Classi ica ion (Rep in ed om [22]) 6 2.2 B ie ly, op imiza ion me hods and he posi ion o EAs in his con ex . . . 8 2.3 A g aphic depic ion o he i e a i e wo k- low o an e olu iona y algo i hm, including GP, ha is d i en by he concep s o Da win’s Theo y o E olu- ion.(Rep in ed om [34]) ........................... 9 2.4 Abs ac syn ax ee ep esen a ion in GP o he unc ion 𝑓(𝑥1, 𝑥2, 𝑥3)=𝑥1−𝑥2+𝑥3∗𝑥1 . (Inspi ed om [38]) ............................... 10 2.5 G ow Algo i hm (Taken om [40]) ...................... 11 2.6 Rela ionship be ween geno ypic and seman ic space. The seman ic space is depic ed in 2D in he igu e, which co esponds o he un ealis ic case in which only wo aining ins ances exis . (Rep in ed om [40]) ...... 13 2.7 A g aphical ep esen a ion o he e ec o geome ic c osso e , in he simple bidimensional case. (Rep in ed om [26]) .................. 14 2.8 A g aphical ep esen a ion o he e ec o geome icmu a ion (box mu a ion), in he simple bi-dimensional case. (Rep in ed om [26]) .......... 14 2.9 T ee ep esen a ion o he GSC o mula. (Inspi ed om [34]) ....... 15 2.10 T ee ep esen a ion o he GSM o mula. (Inspi ed om [34]) ....... 15 2.11 Illus a ion o he example desc ibed abo e. (a) The ini ial popula ion 𝑃 ; (b) The andom ees used by c osso e ; (c) The ep esen a ion in memo y o he new popula ion 𝑃′. (Rep in ed om [45]) ................ 16 5.1 His og am o he a ge columns. ....................... 36 5.2 His og am o he a ge columns. ....................... 38 5.3 His og am o he a ge columns. ....................... 40 5.4 Resul s o he expe imen al compa ison be ween GSGP and GSGP-LS wi h Bos on, Conc e e and Pa kinson da ase s. .................. 46 5.5 E olu ion o 𝑝 - alues esul ing om he compa ison be ween GSGP and GSGP-LS on es da a o Bos on, Conc e e and Pa kinson da ase s. . . . 46 5.6 E olu ion o 𝑝 - alues esul ing om he compa ison be ween GSGP and GSGP-LS on aining da a o Bos on, Conc e e and Pa kinson da ase s. . 47 x ii 5.7 Resul s o he expe imen al compa ison be ween GSGP and GSGP-LS wi h Is anbul, Bioa ailabili y, LD50 da ase s. ................... 47 5.8 E olu ion o 𝑝 - alues esul ing om he compa ison be ween GSGP and GSGP-LS on es da a o Is anbul, Bioa ailabili y, LD50 da ase s. . . . . 48 5.9 E olu ion o 𝑝 - alues esul ing om he compa ison be ween GSGP and GSGP-LS on aining da a o Is anbul, Bioa ailabili y, LD50 da ase s. . . 48 5.10 E olu ion o 𝑝 - alues esul ing om he compa ison be ween GSGP and GSGP-LS on es da a o PPB, Docking and Fluda abine da ase s. . . . . 48 5.11 E olu ion o 𝑝 - alues esul ing om he compa ison be ween GSGP and GSGP-LS on aining da a o PPB, Docking and Fluda abine da ase s. . 49 5.12 Resul s o he expe imen al compa ison be ween GSGP and GSGP-LS wi h PPB, Docking, Fluda abine da ase s. ..................... 49 5.13 E olu ion o 𝑝 - alues esul ing om he compa ison be ween GSGP and GSGP-LS on es da a o p oblem_4, p oblem_5 and p oblem_6 da ase s. 50 5.14 E olu ion o 𝑝 - alues esul ing om he compa ison be ween GSGP and GSGP-LS on aining da a o p oblem_4, p oblem_5 andp oblem_6 da ase s. 51 5.15 Resul s o he expe imen al compa ison be ween GSGP and GSGP-LS wi h p oblem_4, p oblem_5 and p oblem_6 da ase s. .............. 51 5.16 Resul s o he expe imen al compa ison be ween GSGP and GSGP-LS wi h p oblem_7, p oblem_8 and p oblem_9 da ase s. .............. 52 5.17 E olu ion o 𝑝 - alues esul ing om he compa ison be ween GSGP and GSGP-LS on es da a o p oblem_7, p oblem_8 and p oblem_9 da ase s. 52 5.18 E olu ion o 𝑝 - alues esul ing om he compa ison be ween GSGP and GSGP-LS on aining da a o p oblem_7, p oblem_8 andp oblem_9 da ase s. 53 5.19 Con usion Ma ices o he bes indi iduals o Bankno e Au hen ica ion . 54 5.20 Con usion Ma ices o he bes indi iduals o Spo i y Funk Songs . . . . 55 5.21 Con usion Ma ices o he bes indi iduals o B eas Cance Wisconsin . 55 5.22 Resul s o he expe imen al compa ison be ween GSGP and GSGP-LS wi h Bankno e, Spo i y and Wisconsin da ase s. .................. 56 5.23 E olu ion o 𝑝 - alues esul ing om he compa ison be ween GSGP and GSGP-LS on es da a o Bankno e, Spo i y and Wisconsin da ase s. . . . 56 5.24 E olu ion o 𝑝 - alues esul ing om he compa ison be ween GSGP and GSGP-LS on aining da a o Bankno e, Spo i y and Wisconsin da ase s. 57 5.25 Resul s o he expe imen al compa ison be ween GSGP and GSGP-LS wi h p oblem_4 wi h he al e na i e unc ion se . ................. 58 5.26 E olu ion o 𝑝 - alues esul ing om he compa ison be ween GSGP and GSGP-LS on es and aining da a o p oblem_4 wi h he al e na i e unc- ion se . ...................................... 58 x iii Lis o Tables 4.1 GSGP En i ies .................................. 24 4.2 GSGP Pa ame e De ini ions ......................... 24 5.1 Pa ame e se ings. ............................... 32 5.2 Numbe o ins ances and a ibu es o eg ession da ase s. ........ 33 5.3 A ibu es o Bos on Housing. ......................... 35 5.4 A ibu es o Conc e e Comp essi e S eng h. ................ 35 5.5 A ibu es o UPDRS. .............................. 37 5.6 A ibu es o Is anbul S ock Exchange. .................... 38 5.7 Syn he ic da ase se ings. ........................... 41 5.8 Classi ica ion Da ase s. ............................. 41 5.9 A ibu es o Bankno e Au hen ica ion. .................... 42 5.10 Fea u es o Spo i y Funk Songs ........................ 43 5.11 Median Classi ica ion Repo o Bankno e .................. 54 5.12 Median Classi ica ion Repo o Spo i y Funk Songs ............ 54 5.13 Median Classi ica ion Repo o B eas Cance Wisconsin ......... 55 xix 1 In oduc ion Gene ic P og amming (GP) is a gene al-pu pose me hod o au oma ically b eed com- pu e p og ams o sol e a ask [2]. In he las decade, he use o GP [2] o ackle symbolic eg ession p oblems has gained popula i y, possibly because o some quali ies o GP, such as i s abili y o deal wi h p oblems whe e li le o no in o ma ion is known abou he da a, i s abili y o e ol e models ha do no ha e a p e iously ixed ma hema ical shape, and o pe o m au oma ic ea u e selec ion while lea ning he model [3–5]. GP is adi ionally employed o ackle symbolic eg ession p oblems using well-known loss measu es, such as he oo mean squa e e o (RMSE), o quan i y he i ness o he e ol ing solu ions. E en hough his app oach is s ill e y popula , i has a d aw- back: some solu ions may ecei e a bad i ness alue, p omising hough hey migh be. I is he case, o ins ance, o solu ions ha ha e a simila shape o he one o he a ge unc ion, bu wi h di e en slope and/o loca ion in he Ca esian space. Linea scaling (LS) was hus in oduced by Keijze [6] o ackle his issue and imp o e he pe o mance o GP on symbolic eg ession. LS modi ies he i ness unc ion escaling each indi idual by using hei slope and in e cep , wo cons an s ha can be easily calcula ed wi h a cos ha is linea in he size o he aining se . In his way, he bu den o sea ching o hese wo cons an s is emo ed om he e olu ion, lea ing GP wi h he only ask o sea ching o unc ions whose shape is mos simila o ha o he a ge unc ion. Since i s in oduc ion, he bene i o LS was demons a ed on many heo e ical benchma k unc ions [6] and eal-li e applica ions [7–10]. These s udies indica e ha LS does no only imp o e s anda d GP on aining da a, bu can also bes ow on GP a be e gene aliza ion abili y, o en ou pe o ming s anda d GP also on unseen da a. Howe e , Cos elloe and Ryan [11] poin ed ou ha LS may no always imp o e GP’s gene aliza ion abili y. Ten yea s a e he in oduc ion o LS, Mo aglio e al. [12] in oduced Geome ic Seman ic GP (GSGP), a di e en a ian o GP. GSGP uses speci ic gene ic ope a o s, called Geome ic Seman ic Ope a o s (GSOs), ins ead o he adi ional c osso e and mu a ion o GP. Al hough ac ing di ec ly on he syn ax o he GP indi iduals, GSOs ha e an indi ec known e ec on hei seman ics, and ha e he impo an p ope y o 1 CHAPTER 1. INTRODUCTION inducing a unimodal e o su ace o any supe ised lea ning p oblem [12]. Se e al esul s we e p esen ed e ealing he abili y o GSGP o e ec i ely i aining da a [12, 13]. A he same ime, GSGP was also shown o limi o e i ing, o en ou pe o ming s anda d GP on unseen da a o se e al eal-li e symbolic eg ession p oblems [14]. Gi en ha LS wo ks by ede ining he i ness and GSGP wo ks by ede ining he gene ic ope a o s, which a e in gene al wo independen pa s o he GP algo i hm, i is na u al o imagine a sys em ha joins hese wo me hods, possibly cap u ing he ad an ages o bo h GSGP and LS. Following his idea, in 2015 Vanneschi e al. [15] combined GSGP and LS, achie ing ou s anding esul s on a challenging applica ion based on AIS (Au oma ic Iden i ica ion Sys em) o he p edic ion o he posi ions o essels a sea. The success o ha sys em in ha pa icula applica ion domain, oge he wi h he p e ious achie emen s o GSGP and LS used in isola ion, may induce esea che s o hink ha he in eg a ion o GSGP and LS is always bene icial. Howe e , Cos elloe’s and Ryan’s [11] obse a ions made on s anda d GP sound like an impo an wa ning and call o a me hodological s udy aimed a in es iga ing he p os and cons o in eg a ing GSGP and LS. This disse a ion p esen s a GSGP algo i hm and an in es iga ion o a sys em ha employs GSOs o explo e he sea ch space, guided by he LS i ness unc ion, in a manne simila o ha o he app oach p oposed in [15]. The p oposed sys em is e e ed o as GSGP-LS. Fu he mo e, his wo k employs he GSGP and LS me hods o add ess classi ica ion p oblems whe e no p io u iliza ion has been implemen ed. The documen is s uc u ed as ollows. Chap e 2, Theo e ical Backg ound, p o ides he eade wi h su icien knowledge o comp ehend he p esen ed wo k, including a gene al unde s anding o Machine Lea ning (ML), op imiza ion, bioinspi ed and E olu iona y Algo i hms (EAs), as well as LS. Chap e 3, Li e a u e Re iew, b ie ly e iews p e ious wo ks ele an o his s udy, including bo h seman ics in GP and LS in GP. Chap e 4, Me hodology, p esen s a de ailed desc ip ion o he GSGP-LS algo i hm de eloped o his wo k. A discussion o he so wa e implemen ing GSGP-LS has been o ganized and de eloped. In Chap e 5, he expe imen al se up is desc ibed, s a ing wi h he pa ame e se ings, ollowed by p esen a ion o he case s udies, he ob ained expe imen al esul s and a discussion o he esul s. Finally, Chap e 6concludes he wo k wi h an o e iew con aining he esul s o he wo k, limi a ions, and ideas o u u e esea ch. 2 2.3. BIOINSPIRED AND EVOLUTIONARY ALGORITHMS o e ol e in o de o ind he mos success ul among hem o sol e a p oblem a hand. Wi h sexual ecombina ion (c osso e ) o he pa en al compu e p og ams, GP gene a es a new popula ion o o sp ing [2]. Because pa en al p og ams a e chosen in p opo ion o hei i ness measu es, he Da winian p inciple o su i al o he i es is applied. The goal o using na u al selec ion and gene ic ope a o s o c ea e a compu e p og am ha sol es o app oxima es a gi en p oblem is, in ac , he de ini ion o op imiza ion. The concep s iden i ying na u al selec ion a e ep oduc ion,abili y o adap a ion o he en i onmen ,he edi a iness, a ia ion and compe i ion. These a e duplica ed o an ex en in he algo i hm [26]. O e many gene a ions, GP algo i hms may exhibi inc easing a e age i ness and e ec i ely adap o en i onmen al changes [2]. Figu e 2.3: A g aphic depic ion o he i e a i e wo k- low o an e olu iona y algo i hm, including GP, ha is d i en by he concep s o Da win’s Theo y o E olu ion.(Rep in ed om [34]) A his poin i is impo an o s a e ha GP o igina ed om Gene ic Algo i hms (GA) in oduced by Holland in 1975 [35] and Goldbe g in 1989 [36]. Jus like GP, GAs a e algo i hms based on he mechanisms o na u al selec ion and gene ics. GAs a e used o pe o m op imiza ion by mimicking he biological sys ems’ obus ness, e iciency and lexibili y [36]. Despi e he ac ha he e olu iona y p ocess is e y simila o ha o GPs, he e is a c i ical di e ence be ween GAs and GPs, which is ep esen a ion. Indi iduals in GAs a e no compu e p og ams, bu a he ixed-leng h cha ac e s ings ha co espond o ch omosomes in na u e [36]. This ep esen a ion, when used wi h GPs, limi s he in e nal s a es o he sys em due o i s ixed-leng h and canno keep up wi h dynamically a ying p og ams [2]. 9 CHAPTER 2. THEORETICAL BACKGROUND 2.3.1.1 Rep esen a ion o he GP Indi iduals Abs ac syn ax ee ep esen a ion is widely used wi h GP whe e a ee ep esen s a compu e p og am, a unc ion ha sol es he gi en p oblem. The ee is cons uc ed using nodes. The node alues can be ei he unc ions o e minals. The e minals a e speci ied as a cons an alue om a p ede ined se [37]. Node alues a e selec ed om wo se s: Func ion Se ( 𝐹 ) and Te minal Se ( 𝑇 ). The ypes o unc ions may a y, bu o he pu poses o his hesis, examples o bina y ope a ions such as addi ion, sub ac ion, mul iplica ion, and di ision would su ice, as would examples o una y ope a ions such as 𝑠𝑖𝑛 , 𝑐𝑜𝑠 , and 𝑙𝑜𝑔 . Because i co esponds o he s uc u e o he ee, he ep esen a ion is conside ed he geno ype o an indi idual. The i ness o indi iduals is e e ed o as he pheno ype o an indi idual. Ha ing a ee-based ep esen a ion may appea as ha ing an in ini e sea ch space bu he ees a e limi ed by es ic ing hei dep h. In con as o he ixed-leng h ep esen a ion o GAs, ee ep esen a ion o GP allows ees o g ow. This may inc ease he gene aliza ion and solu ion capaci y o GP compa ed o GAs. Figu e 2.4: Abs ac syn ax ee ep esen a ion in GP o he unc ion 𝑓(𝑥1, 𝑥2, 𝑥3)=𝑥1−𝑥2+𝑥3∗𝑥1. (Inspi ed om [38]) 2.3.1.2 Ini ializa ion Ini ializa ion is he p ocess o c ea ing he ees o he i s popula ion. This is he i s s ep o GP as i is o any e olu iona y algo i hm. The mechanisms o na u al selec ion depend hea ily on di e si y. In GP, his e e s o he a ia ion in he geno ype ( ep esen a ion) o pheno ype ( i ness) o he indi iduals wi hin a popula ion. Gene ic sea ch will o en be mo e obus i he popula ion is made up o a wide a ie y o indi iduals since i will encou age he explo a o y s age o he sea ch [39]. A his wo k, h ee majo ini ializa ion me hods is implemen ed. G ow: The g ow algo i hm begins by c ea ing he oo o he ee. A andom symbol om he Func ion Se ( 𝐹 ) is chosen wi h uni o m p obabili y, and he ope and 10 2.3. BIOINSPIRED AND EVOLUTIONARY ALGORITHMS is chosen om he combina ion se o 𝐹 and Te minal Se ( 𝑇 ). I he node alue is a e minal, he node is a lea , indica ing ha he b anch s opped g owing. This p ocess is epea ed un il ei he he maximum dep h is eached o all o he nodes a dep h 𝑑 ha e e minal alues [40]. A pseudocode o he algo i hm is below. Figu e 2.5: G ow Algo i hm (Taken om [40]) Full: Full ini ializa ion begins in he same way ha g ow does. I chooses a andom symbol om 𝐹 o become he oo o he ee. Howe e , nodes om dep h 2 o 𝑑− 1 a e only chosen using he unc ion se 𝐹 , and nodes a he maximum dep h a e chosen om he e minal se 𝑇 . Thus, ull di e en ia es om g ow only in he line ma ked wi h ◦. I ne e selec s a e minal a ha s age, only a unc ion [40]. The di e ence be ween hese me hods is ha ees c ea ed wi h ull ini ializa ion ha e all o hei b anches he same leng h, whe eas ees c ea ed wi h g ow ini ializa ion ha e b anches wi h i egula shapes. Ramped Hal -and-Hal : The mos common and adi ional me hod, and he one used in his wo k, is he Ramped Hal -And-Hal (RHH) me hod de ined by Koza [2]. I makes use o he ull algo i hm oge he wi h he g ow algo i hm. This me hod is ad an ageous because i allows ees wi h a wide ange o sizes and shapes o be gene a ed. When used independen ly, ull ini ializa ion and g ow ini ializa ion p oduce less di e se popula ions since he gene a ed ees may be oo simila o one ano he . RHH is used o inc ease he ini ial di e si y o he popula ion di e si y. The RHH me hod gene a es wo g oups o ees wi h dep hs anging om 2 o 𝑑 . As i s a ed in i s name, 50% o he ees a e gene a ed by ull and 50% is gene a ed by g ow. 2.3.1.3 Fi ness E alua ion The success o indi iduals is measu ed by calcula ing hei i ness. Du ing he e o- lu iona y p ocess, indi iduals wi h be e i ness a e mo e likely o be able o pass on hei genes o he u u e gene a ions ollowing he Da winian p inciple [31]. This phenomenon is ensu ed by he selec ion p ocess. 11 CHAPTER 2. THEORETICAL BACKGROUND 2.3.1.4 Selec ion Selec ion de ines he p ocedu e o selec pa en s om an exis ing popula ion o p oduce o sp ing ha will o m he new gene a ions o e olu ion p ocess. E en hough di e en selec ion me hods such as i ness p opo iona e selec ion ( oule e wheel) [35], anking selec ion [41] and ou namen selec ion [42] can be used o he implemen a ion o GP, ou namen selec ion is op ed o his wo k. This choice is mo i a ed in Chap e 5. Tou namen selec ion is a selec ion algo i hm wi h wo agmen s, he i s o which is andom and he second o which is de e minis ic. Wi h a p e-de ined ou namen size 𝑘 , o selec one o he pa en s om a popula ion, a subse o he popula ion wi h size 𝑘 is c ea ed andomly [43]. Ou o his smalle se , he i ness o e e y indi idual is compa ed and he bes one is chosen o become a pa en . This s ep is en i ely de e minis ic. The ou namen size es ablishes a a iable called selec ion p essu e. Lowe ou namen sizes indica e a low selec ion p essu e, while highe alues indica e a high selec ion p essu e, which co esponds o how likely he bes indi iduals a e o su i e [26]. Always selec ing he bes indi idual o he whole popula ion migh sound like a good idea a i s bu main aining di e si y is c ucial. By keeping he ou namen size small, he selec ion p essu e is educed, and i is ensu ed ha indi iduals wi h lowe i ness a e occasionally chosen o main ain di e si y. 2.3.1.5 Gene ic Ope a o s The e a e mainly wo ypes o gene ic ope a o s. Ope a o s used in GP will be p esen ed wi hou de ails since i di e s om GSGP. Bu i is essen ial o comp ehend he pu pose o hese ope a o s which a e in ac analogous hei biological de ini ions. They in oduce a ia ion in o he e olu iona y p ocess o he indi idual. C osso e : This sexual ecombina ion ope a ion is ca ied ou be ween wo pa en s o p oduce wo o sp ing. Each o sp ing inhe i s a po ion o he ep esen a ion o one pa en and a po ion o he ep esen a ion o he o he pa en , jus as he ch omosomes o li ing beings [2]. Mu a ion: Unlike c osso e , o pe o m his ope a ion, only one indi idual is equi ed. Mu a ion can occu by al e ing a pa o a ee ep esen a ion. This ope a ion also in oduces di e si y and has he po en ial o p oduce bene icial esul s [2]. 2.3.2 Geome ic Seman ic Gene ic P og amming The poin o ocus o his hesis is GSGP, a GP modi ica ion. I is dis inc om he GP due o i s no el gene ic ope a o s. T adi ional c osso e and mu a ion algo i hms a e eplaced wi h special ope a o s, which dis inguishes his me hod om GP. In GSGP, seman ics is exploi ed by he gene ic ope a o s. Seman ics is de ined as he ec o o he ou pu alues o an indi idual on he inpu da a [26]. T adi ional GP, acco ding o Mo aglio, igno es he "meaning" o he p oblems du ing he sea ch p ocess [12]. Fo 12 2.3. BIOINSPIRED AND EVOLUTIONARY ALGORITHMS example, in GP, he c osso e is pe o med by swapping a sub ee o pa en s wi hou aking in o accoun he e ec on seman ics, making his p ocedu e blind. Since he success o he indi iduals is measu ed by i ness, i is cohe en o conside he meaning, he seman ics o he indi iduals du ing e olu iona y p ocess. Geome ic ope a o s which a e used in GSGP a e ocalize on his meaning. 2.3.2.1 Seman ics and Fi ness Landscape Fo a be e unde s anding o GSGP, i is impo an o e u n o he con ex o op imiza- ion p oblems. A popula ion o he ee-based ep esen a ions o indi iduals can be de ined as a geno ypic space o syn ac ic space since his space con ains he s uc u es [26]. Since e e y indi idual has a seman ic, i is also possible o de ine a space wi h seman- ics. Indi iduals in seman ic space a e ep esen ed by hei seman ics a he han ee s uc u es. Due o he ac o seman ics being a ec o , his makes i possible o he indi iduals o be ep esen ed by a poin in his seman ic space [12]. In supe ised lea ning, i is also possible o indica e he a ge , he global op imum in his space. Since he objec i e o op imiza ion is o ind an indi idual wi h bes i ness o a leas o ha e an app oxima ed solu ion, i ness can be calcula ed as, using any me ic, dis ance (e.g. Euclidean dis ance) be ween seman ics and he a ge . Figu e 2.6: Rela ionship be ween geno ypic and seman ic space. The seman ic space is depic ed in 2D in he igu e, which co esponds o he un ealis ic case in which only wo aining ins ances exis . (Rep in ed om [40]) 2.3.2.2 Ope a o s in Seman ic Space I was sugges ed in he li e a u e in 1950 ha when using e olu ion, i is impo an o ind a me hod o p e en comple ely andom mu a ions and o pe o m his ope a ion in a way ha has he po en ial o imp o e he success o an indi idual [16]. Two ope - a o s, geome ic c osso e and geome ic mu a ion we e in oduced by Mo aglio and Poli in 2004 [44]. As p e iously s a ed, he adi ional c osso e and mu a ion ope a o s unc ion on he geno ypic (syn ac ic) ep esen a ions o indi iduals. They p oposed 13 CHAPTER 2. THEORETICAL BACKGROUND a amewo k o c osso e and mu a ion ope a o s based on landscape opology and geome y, which is associa ed wi h seman ic space. This amewo k ensu ed an au o- ma ic me hod o de i ing mu a ion and c osso e om he neighbo hood s uc u e o a landscape. This cla i ied he connec ion be ween ep esen a ion, gene ic ope a o s, neighbo hood s uc u e and dis ance in he landscape [44]. Geome ic c osso e is pe o med wi h wo pa en s o ob ain a single o sp ing loca ed be ween i s pa en s in space. I should be no ed ha his ope a ion only c ea es one o sp ing. Figu e 2.7: A g aphical ep esen a ion o he e ec o geome ic c osso e , in he simple bidimensional case. (Rep in ed om [26]) Geome ic mu a ion, also known as box mu a ion, mu a es an indi idual by an- domly pe u bing i s coo dina es wi hin a ce ain ange (box). Figu e 2.8: A g aphical ep esen a ion o he e ec o geome ic mu a ion (box mu a ion), in he simple bi-dimensional case. (Rep in ed om [26]) 2.3.2.3 Geome ic Seman ic C osso e (GSC) When an o sp ing is c ea ed wi h geome ic c osso e in seman ic space, whe e i ness is calcula ed as he dis ance o an indi idual o he global op imum, i will be loca ed on a linea line be ween he pa en s. The be weenness p ope y o geome ic c osso e ensu es ha o sp ing do no de ia e u he om he global op imum han he wo s pa en al eady is. This ensu es ha he i ness o he o sp ing is ne e wo se han he i ness o he wo s pa en . Mo aglio de ined he GSC ope a o , which co esponds o geome ic c osso e on he seman ic space [12,26]. 14 2.3. BIOINSPIRED AND EVOLUTIONARY ALGORITHMS Geome ic Seman ic C osso e . Gi en wo pa en unc ions 𝑇1, 𝑇2:R𝑛→R , GSC e u ns he eal unc ion 𝑇𝑋𝑂 =(𝑇1·𝑇𝑅)+((1−𝑇𝑅)·𝑇2) , whe e 𝑇𝑅 is a andom eal unc ion whose ou pu alues ange in he in e al [0,1]. Figu e 2.9: T ee ep esen a ion o he GSC o mula. (Inspi ed om [34]) 2.3.2.4 Geome ic Seman ic Mu a ion (GSM). Simila ly, in seman ic space, when an indi idual is mu a ed wi h geome ic mu a ion, mu a ion can always imp o e i ness by allowing he poin o mo e close o he global op imum. Mo aglio also de ined he GSM ope a o , which co esponds o geome ic mu a ion (box mu a ion) on he seman ic space [12,26] Geome ic Seman ic Mu a ion (GSM). Gi en a pa en unc ion 𝑇:R𝑛→R , GSM wi h mu a ion s ep 𝑚𝑠 e u ns he eal unc ion 𝑇𝑀=𝑇+𝑚𝑠 ·(𝑇𝑅1−𝑇𝑅2) , whe e 𝑇𝑅1 and 𝑇𝑅2a e andom eal unc ions. The ms is used o une he p opo ion o he pe u ba ion (i.e., he limi s o he box). O e all, GSGP ha e he abili y o in oduce a unimodal i ness landscape on he aining se since gene ic ope a ions can always p oduce o sp ing ha a e close o he a ge . This is phenomenon ende s eg ession and classi ica ion p oblems easy o sol e on aining se . Figu e 2.10: T ee ep esen a ion o he GSM o mula. (Inspi ed om [34]) 15 CHAPTER 2. THEORETICAL BACKGROUND 2.3.2.5 Real-Li e Applica ions o GSGP GSOs, in addi ion o p esen ing a unimodal i ness landscape, had some limi a ions ha ende ed hem useless in p ac ice when hey we e i s in oduced. By hei de ini ions, GSOs we e causing he ep esen a ion o he o sp ing o become la ge o e e y gene a ion. Fo u u e wo ks, Mo aglio sugges ed simpli ying he syn ax o he indi iduals o ob ain a simple geno ype while p ese ing hei seman ics. Vanneschi e al. and Cas elli e al. p esen ed a no el implemen a ion ha made GSGP u ilizable o complex eal-li e applica ions, o he i s ime [13,45]. 2.3.3 GSGP Implemen a ion This no el implemen a ion o Vanneschi e al. [45] is based on sa ing new gene a ion eco ds ha include ope a o s and pa en s. As in s anda d GP, i begins by gene a ing a andom ini ial popula ion. The indi iduals’ ep esen a ions and seman ics a e hen s o ed in wo ables. A new able is c ea ed o each new gene a ion o indi iduals 𝑇 . The able con ains in o ma ion abou he ope a o wi h which he indi idual was c ea ed (c osso e o mu a ion), as well as he ID. The ID is a memo y poin e ( e e ence) o he pa en s and hei seman ics, which we e calcula ed using geome ic seman ic ope a o s. Indi iduals om he new popula ion a e also sa ed in his manne . An indi idual c ea ed by a c osso e be ween pa en s 𝑇1 and 𝑇2 is ep esen ed by he iple 𝑇=<𝐼𝐷(𝑇1), 𝐼𝐷(𝑇2), 𝐼𝐷(𝑅)> , whe e R is he andom ee used by he c osso e . Wi h he same o m, an indi idual c ea ed by a mu a ion ope a o on 𝑇2 is ep esen ed as 𝑇=<𝐼𝐷(𝑇2), 𝐼𝐷(𝑅1), 𝐼𝐷(𝑅2)> whe e 𝑅1 and 𝑅2 a e andom ees. Random ees, along wi h hei ep esen a ions and seman ics, mus also be s o ed on a able. Figu e 2.11: Illus a ion o he example desc ibed abo e. (a) The ini ial popula ion 𝑃 ; (b) The andom ees used by c osso e ; (c) The ep esen a ion in memo y o he new popula ion 𝑃′. (Rep in ed om [45]) Since he ees a e s o ed wi h hei seman ics (e alua ions), he e is no need o explici ly build he ee and e alua e he en i e ee a e he c ea ion o an o sp ing. Due o memo y cons ain s, indi iduals ha a e no used o he c ea ion o any o sp ing a e dele ed om he memo y be o e passing on o he nex gene a ion because hey will ne e be used again. 16 2.4. LINEAR SCALING In e ms o ime complexi y, his me hod is linea wi h espec o popula ion size and he numbe o gene a ions since i equi es 𝑂(𝑛) space o s o e he indi iduals o g numbe o gene a ions ( 𝑂(𝑛𝑔) ). A he end, i is su icien o econs uc he bes indi idual making econs uc ion a one- ime p ocess and i can be done o line om he algo i hm. O e all, his no el implemen a ion ensu es GSGP o be applied e icien ly on eal-li e da a wi h high success a es. 2.4 Linea Scaling While pe o ming eg ession wi h GP, in cases whe e indi iduals ha ha e a shape which is e y simila o he one o he a ge unc ions, many solu ions may ecei e a bad i ness alue due o ha ing di e en slope and/o being loca ed in a dis an posi ion o he Ca esian space. LS was in oduced by Keijze o ackle his issue and imp o e he pe o mance o GP on symbolic eg ession [6]. I is a me hod in oduced o acili a e he ask o GP o sea ching o he bes unc ion ma ching a se o known da a. LS modi ies he i ness unc ion in a e y simple way, escaling each indi idual by using hei slope and in e cep , wo cons an s ha can be easily calcula ed wi h a cos ha is linea in he size o he aining se . Le 𝑃(𝑥𝑖) be he ou pu o GP indi idual 𝑃 on he 𝑖 h obse a ion o he aining se . A linea eg ession on he a ge alues 𝑡 can be pe o med using he equa ions: 𝑏= 𝑛 Õ 𝑖=1h𝑡𝑖−𝑡𝑃(𝑥𝑖)−𝑃i 𝑛 Õ 𝑖=1𝑃(𝑥𝑖)−𝑃2 𝑎=𝑡−𝑏 𝑃 (2.1) whe e 𝑛 is he numbe o aining obse a ions ( i ness cases) and 𝑃 and 𝑡 deno e he a e age ou pu and he a e age a ge alue espec i ely. Values 𝑏 and 𝑎 espec i ely calcula e he slope and in e cep o he se o ou pu s 𝑃(𝑥𝑖) , such ha he sum o he squa ed e o s be ween 𝑡 and 𝑎+𝑏𝑃 is minimized. A e his, any e o measu e can be calcula ed on he scaled o mula 𝑎+𝑏𝑃, o ins ance he RMSE: RMSE(𝑡, 𝑎 +𝑏 𝑃)= u u u u 𝑛 Õ 𝑖=1(𝑎+𝑏 𝑃(𝑥𝑖)−𝑡𝑖)2 𝑛(2.2) 17 CHAPTER 2. THEORETICAL BACKGROUND I a is di e en om 0 and b is di e en om 1, he p ocedu e ou lined abo e is gua an eed o educe he RMSE o any o mula [6]. By e icien ly calcula ing he slope and in e cep o each indi idual, he bu den o sea ching o hese wo cons an s is hus emo ed om he e olu ion. GP is hen ee o sea ch o he exp ession whose shape is mos simila o ha o he a ge unc ion. 18 4 Me hodology This chap e ou lines he me hodology employed in his s udy, which seeks o in- es iga e a sys em ha combines he a o emen ioned bene i s o bo h GSGP and LS. Speci ically, he sys em u ilizes GSOs o explo e he sea ch space, while guided by he LS i ness unc ion. The sys em is e e ed o as GSGP-LS. The gene al layou o he lib a y is explained in Sec ion 4.1, ollowed by a de ailed discussion o he lib a y’s a ious classes. The chap e ollows by de ining he mos comp ehensi e class, GSGP, in Sec ion 4.2. The Popula ion class is discussed in Sec ion 4.3, which includes el- e an p ocesses such as ini ializa ion, o sp ing c ea ion, and popula ion sco ing in Subsec ions 4.3.1,4.3.2, and 4.3.3, espec i ely. The Indi idual class is discussed in Sec ion 4.4, which includes a subsec ion on econs uc ion in Subsec ion 4.4.1. The chap e concludes wi h he p esen a ion o he Node class in Sec ion 4.5. 4.1 Gene al O ganiza ion o he GSGP-LS Lib a y A GSGP algo i hm is de eloped wi h he ollowing sys em equi emen s: •LS can be implemen ed. •I is possible o sol e bo h eg ession and classi ica ion p oblems. •Hype pa ame e s a e easily changeable o di e en da ase s. •Visualiza ion o expe imen esul s can be d awn. •An accep able un ime is ensu ed. The ex ensibili y o he lib a y was a conside a ion du ing i s design, wi h he in en ion o acili a ing u u e esea ch and de elopmen . The ollowing subsec ions will elabo a e on he lib a y’s a chi ec u e and en i ies. The lib a y was cons uc ed based on he heo e ical knowledge ha was p e iously p esen ed. I can pe o m aining o GSGP models, econs uc ing he ep esen a ion o he bes indi idual, unning ained models o p edic ing, ob aining s a is ical esul s and isualiza ions. The code is w i en in Py hon p og amming language. Py hon has an ac i e usage among he da a science communi y. I con ains lib a ies o easy da a eading as well 23 CHAPTER 4. METHODOLOGY as common s a is ical analysis ools. I also has a high p o o yping speed, all in all p o iding ease o de elopmen . The lib a y comp ises a di e se se o classes and unc ions pe aining o he GSGP algo i hm. Mo eo e , i inco po a es unc ions and helpe classes ha enable he handling o da ase eading, basic s a is ical ope a ions, g aphing ela ed code, mul ip ocessing suppo , and o he u ili y unc ionali y ha lacks scien i ic ele ance. The lib a y’s design embodies an en i y-based objec -o ien ed app oach, whe eby se e al modules lis ed he ein implemen a singula heo e ical concep . The ele ance be ween he en i ies and he heo e ical concep s is shown in he able p esen ed below. Commencing wi h he mos comp ehensi e en i y, he GSGP, he subsequen subsec ions in oduce he Popula ion, Indi idual, and Node. Table 4.1: GSGP En i ies Theo y Lib a y An Op imiza ion P oblem GSGP A Tiny Sample o he Solu ion Space Popula ion A Single Solu ion Indi idual T ee Rep esen a ion Node 4.2 GSGP A GSGP p oblem is ep esen ed h ough he GSGP class, which encompasses he aining and p edic ion p ocedu es and ea u es eal- ime epo ing du ing he aining p ocess. The use -de ined hype pa ame e s ha a e in insic o he GSGP algo i hm a e inco po a ed in his class. The hype pa ame e s, hei espec i e de ini ions, and he anges wi hin which hey a e de ined a e comp ehensi ely lis ed below. The ollowing chap e will p esen he speci ic alues ha ha e been selec ed o hese hype pa ame e s along wi h hei co esponding jus i ica ions. Table 4.2: GSGP Pa ame e De ini ions Pa ame e De ini ion Da a Type and Range max_i e Numbe o gene a ions in ege pop_size Popula ion size in ege _selec ion Selec ion me hod s ing (’ ou namen ’) ou namen .size: in ege eli ism_size Numbe o eli es in ege _ i ness Fi ness unc ion s ing (’ mse’ o ’ sco e’) p ob_xo C osso e p obabili y loa [0,1] p ob_mu Mu a ion p obabili y loa [0,1] mu a ion_s ep Mu a ion s ep loa o andom_mu a ion_s ep: lowe _ ange, uppe _ ange: loa 24 4.3. POPULATION To ain he GSGP model, his class in okes he ope a ion o ini ialize a popula ion, hen con inues he p ocess by eco ding s a is ical in o ma ion such as he aining i ness and es i ness o each gene a ion ( i ness o e ime) as well as p edic ions made wi h he bes indi idual. The gene al p ocess di e s depending on whe he he p oblem ype is eg ession o classi ica ion. The ollowing sec ions will explo e hese di e ences in de ail. The GSGP class uses he ollowing modules o es and ain he GSGP model. 4.3 Popula ion Popula ion class ep esen s a g oup o indi iduals, and i manages ope a ions asso- cia ed wi h he c ea ion o ini ial and new gene a ions. I in okes he ini ializa ion unc ion, pe o ms he p ocedu e o e ol ing a popula ion by c ea ing a new gene a- ion. Fu he mo e, he class sco es a popula ion by calcula ing i s a e age i ness, also keeping he eco d o he popula ion’s i es indi idual. Since he p edic ion equi es knowledge o he bes indi idual in any gi en gene a ion, use calls ia GSGP a e ou ed o his class, which hen compu es he necessa y p edic ions. I is c ucial o no e a dis inc ion be ween eg ession and classi ica ion p oblems in his s ep. In classi ica ion p oblems, p edic ions a e no malized using a sigmoid unc ion, which con ines he p edic ions o a ange o 0 o 1. A e no maliza ion, a h eshold alue o 0.5 is u ilized o classi y he p edic ions, wi h hose abo e 0.5 assigned o a ge class 1 and hose below 0.5 assigned o a ge class 0. 4.3.1 Ini ializa ion Ini ializa ion o a new popula ion is pe o med by c ea ing an ini ial popula ion ( ep- esen ed as T popula ion) wi h a gi en size o a popula ion, pop_size. A simple pool o andom ees ( ep esen ed as R popula ion) o he same size is also c ea ed a his class. The pseudo-code o ini ializa ion algo i hm is p esen ed below. Algo i hm 1 Ini ialize a new popula ion 1: unc ion hh(𝑔𝑟𝑜𝑢𝑝_𝑠𝑖𝑧𝑒,𝑡𝑟𝑒𝑒_𝑑𝑒𝑝𝑡ℎ𝑠) 2: o all 𝑑𝑒𝑝𝑡ℎ𝑠 in 𝑡𝑟𝑒𝑒_𝑑𝑒𝑝𝑡ℎ𝑠 do 3: 𝑖←0 4: while 𝑖≤𝑔𝑟𝑜𝑢𝑝_𝑠𝑖𝑧𝑒 do 5: Append he popula ion wi h an indi idual ini ialized wi h g ow me hod 6: and ha ing a cu en dep h equals o 𝑑𝑒𝑝𝑡ℎ𝑠 7: Append he popula ion wi h an indi idual ini ialized wi h ull me hod 8: and ha ing a cu en dep h equals o 𝑑𝑒𝑝𝑡ℎ𝑠 9: 𝑖+=2 10: end while 11: end o 12: end unc ion 25 CHAPTER 4. METHODOLOGY 1: unc ion Ini ialize Fi s Gene a ion(𝑝𝑜𝑝𝑢𝑙𝑎𝑡𝑖𝑜𝑛, 𝑑𝑎𝑡𝑎) 2: C ea e an emp y 𝑡_𝑝𝑜𝑝𝑢𝑙𝑎𝑡𝑖𝑜𝑛 3: C ea e an emp y 𝑟_𝑝𝑜𝑝𝑢𝑙𝑎𝑡𝑖𝑜𝑛 4: 𝑡𝑟𝑒𝑒_𝑑𝑒𝑝𝑡ℎ𝑠 ← [2,3,4,5,6] 5: 𝑔𝑟𝑜𝑢𝑝_𝑠𝑖𝑧𝑒_𝑜 𝑓 _𝑡_𝑝𝑜𝑝𝑢𝑙𝑎𝑡𝑖𝑜𝑛 ← Hal o he _popula ion_size di ided by he 6: numbe o 𝑡𝑟𝑒𝑒_𝑑𝑒𝑝𝑡ℎ𝑠 7: 𝑔𝑟𝑜𝑢𝑝_𝑠𝑖𝑧𝑒_𝑜 𝑓 _𝑟_𝑝𝑜𝑝𝑢𝑙𝑎𝑡𝑖𝑜𝑛 ← Hal o he _popula ion_size di ided by he 8: numbe o 𝑡𝑟𝑒𝑒_𝑑𝑒𝑝𝑡ℎ𝑠 9: Append 𝑡_𝑝𝑜𝑝𝑢𝑙𝑎𝑡𝑖𝑜𝑛 wi h 𝑅𝐻𝐻(𝑔𝑟𝑜𝑢𝑝_𝑠𝑖𝑧𝑒_𝑜 𝑓 _𝑡_𝑝𝑜𝑝𝑢𝑙𝑎𝑡𝑖𝑜𝑛, 𝑡𝑟𝑒𝑒_𝑑𝑒𝑝𝑡ℎ𝑠) 10: Append 𝑟_𝑝𝑜𝑝𝑢𝑙𝑎𝑡𝑖𝑜𝑛 wi h 𝑅𝐻𝐻(𝑔𝑟𝑜𝑢𝑝_𝑠𝑖𝑧𝑒_𝑜 𝑓 _𝑟_𝑝𝑜𝑝𝑢𝑙𝑎𝑡𝑖𝑜𝑛, 𝑡𝑟𝑒𝑒_𝑑𝑒𝑝𝑡ℎ𝑠) 11: o all indi iduals in 𝑡_𝑝𝑜𝑝𝑢𝑙𝑎𝑡𝑖𝑜𝑛 do 12: Calcula e ini ial seman ics 13: end o 14: o all indi iduals in 𝑟_𝑝𝑜𝑝𝑢𝑙𝑎𝑡𝑖𝑜𝑛 do 15: Calcula e ini ial seman ics 16: end o 17: end unc ion 4.3.2 O sp ing C ea ion Du ing he o sp ing c ea ion p ocess, he Popula ion class also pe o ms he calcula- ion o he seman ics o he T popula ion and R popula ion, which a e hen s o ed in indi iduals. As shown in he pseudo-code o he e olu ion p ocess below, he p ocess s a s wi h he selec ion o wo pa en s using a gi en selec ion me hod, _selec ion. Subsequen ly, a new indi idual is c ea ed p obabilis ically using one o h ee di e - en me hods - mu a ion, c osso e , o eplica ion - based on an independen andom a iable, wi h he p obabili ies de e mined by p ob_xo and p ob_mu . Finally, he seman ics o he o sp ing a e compu ed using hose o i s pa en s. 26 4.3. POPULATION Algo i hm 2 Gene a ion o a new gene a ion 1: unc ion C ea e New Gene a ion(popula ion) 2: C ea e an emp y lis 𝑛𝑒𝑤_𝑔𝑒𝑛𝑒𝑟𝑎𝑡𝑖𝑜𝑛 3: 𝑛𝑢𝑚𝑏𝑒𝑟_𝑜 𝑓 _𝑖𝑛𝑑𝑖𝑣𝑖𝑑𝑢𝑎𝑙𝑠_𝑡𝑜_𝑐𝑟𝑒𝑎𝑡𝑒 ←𝑔𝑒𝑡_𝑝𝑜𝑝_𝑠𝑖𝑧𝑒(𝑝𝑜𝑝𝑢𝑙𝑎𝑡𝑖𝑜𝑛) 4: 𝑛𝑢𝑚𝑏𝑒𝑟_𝑜 𝑓 _𝑒𝑙𝑖𝑡𝑒𝑠 ←𝑔𝑒𝑡_𝑛𝑢𝑚𝑏𝑒𝑟_𝑜 𝑓 _𝑒𝑙𝑖𝑡𝑒𝑠(𝑝𝑜𝑝𝑢𝑙𝑎𝑡𝑖𝑜𝑛) 5: i 𝑛𝑢𝑚𝑏𝑒𝑟_𝑜 𝑓 _𝑒𝑙𝑖𝑡𝑒𝑠 ≥1 hen 6: 𝑛𝑢𝑚𝑏𝑒𝑟_𝑜 𝑓 _𝑖𝑛𝑑𝑖𝑣𝑖𝑑𝑢𝑎𝑙𝑠_𝑡𝑜_𝑐𝑟𝑒𝑎𝑡𝑒−=𝑛𝑢𝑚𝑏𝑒𝑟_𝑜 𝑓 _𝑒𝑙𝑖𝑡𝑒𝑠 7: Copy eli es o he 𝑛𝑒𝑤_𝑔𝑒𝑛𝑒𝑟𝑎𝑡𝑖𝑜𝑛 8: end i 9: o iin [0...numbe _o _indi iduals_ o_c ea e] do 10: Selec pa en s 𝑇1and 𝑇2 om 𝑝𝑜𝑝𝑢𝑙𝑎𝑡𝑖𝑜𝑛 11: 𝑖𝑛𝑑𝑒𝑝𝑒𝑛𝑑𝑒𝑛𝑡_𝑣𝑎𝑟𝑖𝑎𝑏𝑙𝑒 ←𝑟𝑎𝑛𝑑𝑜𝑚_𝑢𝑛𝑖 𝑓 𝑜𝑟𝑚(0,1) 12: i 𝑖𝑛𝑑𝑒𝑝𝑒𝑛𝑑𝑒𝑛𝑡_𝑣𝑎𝑟𝑖𝑎𝑏𝑙𝑒 ≤𝑔𝑒𝑡_𝑥𝑜_𝑝𝑟𝑜𝑏𝑎𝑏𝑖𝑙𝑖𝑡𝑦(𝑝𝑜𝑝𝑢𝑙𝑎𝑡𝑖𝑜𝑛) hen 13: Ge a andom indi idual 𝑅 om 𝑟_𝑝𝑜𝑝𝑢𝑙𝑎𝑡𝑖𝑜𝑛 14: 𝑛𝑒𝑤_𝑖𝑛𝑑𝑖𝑣𝑖𝑑𝑢𝑎𝑙 ←𝑥𝑜(𝑇1, 𝑇2, 𝑅) 15: else i 𝑖𝑛𝑑𝑒𝑝𝑒𝑛𝑑𝑒𝑛𝑡_𝑣𝑎𝑟𝑖𝑎𝑏𝑙𝑒 ≤𝑔𝑒𝑡_𝑥𝑜_𝑝𝑟𝑜𝑏𝑎𝑏𝑖𝑙𝑖𝑡𝑦(𝑝𝑜𝑝𝑢𝑙𝑎𝑡𝑖𝑜𝑛) + 𝑔𝑒𝑡_𝑚𝑢𝑡_𝑝𝑟𝑜𝑏𝑎𝑏𝑖𝑙𝑖𝑡𝑦(𝑝𝑜𝑝𝑢𝑙𝑎𝑡𝑖𝑜𝑛) hen 16: Ge andom indi iduals 𝑅1and 𝑅2 om 𝑟_𝑝𝑜𝑝𝑢𝑙𝑎𝑡𝑖𝑜𝑛 17: 𝑛𝑒𝑤_𝑖𝑛𝑑𝑖𝑣𝑖𝑑𝑢𝑎𝑙 ←𝑚𝑢𝑡𝑎𝑡𝑖𝑜𝑛(𝑅1, 𝑅2, 𝑇1) 18: else 19: 𝑛𝑒𝑤_𝑖𝑛𝑑𝑖𝑣𝑖𝑑𝑢𝑎𝑙 ←𝑇1 20: end i 21: Append 𝑛𝑒𝑤_𝑔𝑒𝑛𝑒𝑟𝑎𝑡𝑖𝑜𝑛 wi h 𝑛𝑒𝑤_𝑖𝑛𝑑𝑖𝑣𝑖𝑑𝑢𝑎𝑙 22: end o 23: e u n 𝑛𝑒𝑤_𝑔𝑒𝑛𝑒𝑟𝑎𝑡𝑖𝑜𝑛 24: end unc ion 4.3.3 Sco ing a Popula ion As he Popula ion class is esponsible o all indi iduals in he sys em, i also sco es he cu en gene a ion. The o de ing o indi iduals a ies based on he i ness unc ion being u ilized. Values close o 1 indica e supe io i ness o F1 sco e, while alues close o 0 indica e supe io i ness o RMSE. To ensu e ha he lib a y emains ex ensible, he i ness unc ions class mus con o m o he p o ocol o he i ness unc ion. This is accomplished by sub-classing he abs ac class o i ness unc ions and implemen ing he equisi e me hods. Any i ness unc ion ha adhe es o his p o ocol can be u ilized 27 CHAPTER 4. METHODOLOGY o gene a e sco ing, as shown in he pseudo-code below. I he cu en indi idual is e y decisi e on a pa icula ou pu , a bad i ness ( e y low o e y high depending on he i ness unc ion) sco e is assigned o ha indi idual, as in Keijze ’s pape [6]. The lib a y is designed o ope a e wi ho wi hou LS o compa abili y. As p esen ed in he pseudocode, i he LS op ion is selec ed, a and b a e calcula ed and he esul s a e scaled acco ding o he me hod ou lined in Chap e 2, Theo e ical Backg ound. Algo i hm 3 Fi ness calcula ion 1: unc ion Sco e Cu en Gene a ion(𝑝𝑜𝑝𝑢𝑙𝑎𝑡𝑖𝑜𝑛,𝑑𝑎𝑡𝑎) 2: o all indi iduals in popula ion do 3: o all ows in da a do 4: Ge a ge alue 5: Ge e alua ion using seman ics 6: 𝑟𝑜𝑤_𝑟𝑒𝑠𝑢𝑙𝑡𝑠 ←𝑡𝑢𝑝𝑙𝑒(𝑡𝑎𝑟𝑔𝑒𝑡, 𝑒𝑣𝑎𝑙𝑢𝑎𝑡𝑖𝑜𝑛) 7: end o 8: 𝑣𝑎𝑟𝑖𝑎𝑛𝑐𝑒 ←𝑐𝑎𝑙𝑐𝑢𝑙𝑎𝑡𝑒_𝑣𝑎𝑟𝑖𝑎𝑛𝑐𝑒(𝑟𝑜𝑤_𝑟𝑒𝑠𝑢𝑙𝑡𝑠) 9: i 𝑣𝑎𝑟𝑖𝑎𝑛𝑐𝑒 ≥107o 𝑣𝑎𝑟𝑖𝑎𝑛𝑐𝑒 ≤10−7 hen 10: Assign a bad i ness alue 11: else 12: i 𝐿𝑖𝑛𝑒𝑎𝑟 𝑆𝑐𝑎𝑙𝑖𝑛𝑔 hen 13: 𝑎, 𝑏 ←𝑐𝑎𝑙𝑐𝑢𝑙𝑎𝑡𝑒_𝑙𝑖𝑛𝑒𝑎𝑟_𝑠𝑐𝑎𝑙𝑖𝑛𝑔_𝑐𝑜𝑛𝑠𝑡𝑎𝑛𝑡𝑠(𝑟𝑜𝑤_𝑟𝑒𝑠𝑢𝑙𝑡𝑠) 14: 𝑟𝑜𝑤_𝑟𝑒𝑠𝑢𝑙𝑡𝑠 ←Scaled esul s 15: end i 16: Calcula e a e age i ness 17: end i 18: Assign he i ness alue o he indi idual 19: end o 20: So popula ion wi h espec o he i ness alues 21: e u n Indi idual wi h he bes i ness 22: end unc ion 28 4.4. INDIVIDUAL 4.4 Indi idual Indi idual class ep esen s an indi idual (i.e., a single solu ion o he p oblem). The class pe o ms he mu a ion and c osso e by aking an ins ance o an indi idual and e u ning he mu a ed indi idual o an o sp ing. GSC and GSM o mulas used in his class a e consis en wi h hose ou lined in he li e a u e [12]. 4.4.1 Recons uc ion I should be no ed ha a modi ied echnique, dis inc om he one p esen ed in Chap e 2, has been s udied o ensu e he econs uc ion capabili y. This echnique le e ages Py hon’s ga bage collec ion mechanism, which unc ions by keeping ack o e e ence coun - a coun e ha holds he numbe o e e ences made o an objec . Essen ially, a Py hon a iable is a e e ence o an objec s o ed in memo y. When he e e ence coun o an objec eaches ze o, indica ing ha he objec is no longe e e ed o by any a iable, he ga bage collec o p omp ly emo es i . In his algo i hm, each indi idual is ep esen ed by a ee s uc u e. When an o sp ing is c ea ed in he Indi idual class, he c osso e o mu a ion ope a ion is pe o med wi h he pa en ’s o a andom ee’s ep esen a ion. Consequen ly, he ee ep esen a ion o he o sp ing only con ains e e ences o he pa en o he andom ee, a he han he en i e ee s uc u e. Py hon’s e e ence coun ing and ga bage collec ion mechanism ensu e ha memo y is pe iodically cleaned up, and any unused ep esen a ions a e e ased om memo y. In he c ea ion o a new popula ion, any indi iduals ha we e no used a e e ased. As he ee g ows, each node con ains a ecu si e me hod, which can make he ecu sion memo y-in ensi e, esul ing in slowe pe o mance and limi a ions in e ms o he numbe o nodes. This app oach was implemen ed o in es iga e i s po en ial, bu i has i s limi a ions. Howe e , since he ocus o his s udy is no on econs uc ion, and his me hod is no equi ed o expe imen al pu poses, explo ing ways o add ess hese limi a ions is in iguing o u u e esea ch. 4.5 Node Node holds he da a s uc u e ha objec i ies a node in a ee ep esen a ion. As ou lined in he heo y, each ee is cons uc ed by combining indi idual nodes, and he Node s uc u e is used o ins an ia e each node. To compu e ini ial seman ics o a ee, he e alua e unc ion is called on his da a s uc u e. Al hough he seman ics o a node can s ill be calcula ed wi h he e alua e unc ion as he ee and da a s uc u e g ow, i is p e e able o compu a ion ime easons o use he seman ics o he pa en s wi hou ee alua ing hem. Values o he nodes a e selec ed om a unc ion se and a e minal se . The unc ion se comp ises ou bina y ope a ions: addi ion, sub ac ion, mul iplica ion, 29 CHAPTER 4. METHODOLOGY and di ision, implemen ed in Node. Di ision is de ined as a p o ec ed di ision o a oid di ision by ze o scena ios. Speci ically, he di ision ope a ion is pe o med only i he denomina o is no ze o; o he wise, he esul is 1.To in oduce non-linea i y o he unc ion se , se e al addi ional ope a ions ha e been de ined, including squa e oo , nega i e x, sine, cosine, absolu e alue, ecip ocal (1/x), exponen ial, and loga i hm. These ope a ions can be selec ed o use i needed. Te minal nodes a e andomly selec ed om he a ailable columns in he da ase ’s ea u es. Addi ionally, e minal nodes can be expanded o include andom numbe s i desi ed by he use . In acco dance wi h he heo e ical de ails, he RHH ini ializa ion me hod is also implemen ed in his sec ion. The ini ializa ion p ocess can be pe o med by RHH, ull, o g ow me hods. 30 5 Expe imen al S udy This chap e p esen s he indings o he applica ion o he me hodology in oduced in he p e ious chap e , along wi h accompanying expe imen al s udies. To acili- a e ep oducibili y, he expe imen al se up is ou lined in Sec ion 5.1. Subsec ion 5.1.1 includes pa ame e se ing and Subsec ion 5.1.2 ou lines case s udies on eg ession, syn- he ic and classi ica ion da ase s. The associa ed expe imen al esul s o all p oblems a e gi en in 5.2 wi h sepa a e subsec ions o eg ession expe imen s 5.2.1, syn he ic da ase expe imen s 5.2.2 and classi ica ion expe imen s 5.2.3. Ul ima ely, he esul s a e discussed in Sec ion 5.3. 5.1 Expe imen al Se up The objec i e o his wo k is o assess he e ec i eness o in eg a ing he LS echnique wi h he GSGP algo i hm. To his end, mul iple expe imen s we e conduc ed using bo h eg ession and classi ica ion p oblems. Fo each p oblem, he expe imen s we e epea ed using he GSGP alone and in combina ion wi h LS. Each con igu a ion was implemen ed using he lib a y p esen ed in he Chap e 4. Gi en he non-de e minis ic na u e o he GSGP algo i hm, wi h elemen s o an- domness p esen in he ini ializa ion, e olu ion, mu a ion, c osso e , and pa en se- lec ion s eps, he ou come o a single un is no conside ed eliable o compa ison pu poses. To ob ain mo e accu a e esul s, mul iple independen uns o he algo i hm we e pe o med. 60 independen uns we e conduc ed o each con igu a ion, wi h he da ase andomly pa i ioned in o 70% aining and 30% es se s o each un. 5.1.1 Pa ame e Se ings I is wo h no ing ha he p ima y ocus o his wo k was no on op imizing hype - pa ame e s bu a he on making a ai compa ison be ween he wo app oaches. In addi ion, op imizing hype pa ame e s would p obably gi e o igin o a di e en hype - pa ame e se o e e y case, hus gene a ing a diso de . As such, he hype pa ame e s 31 CHAPTER 5. EXPERIMENTAL STUDY •EM: MSCI eme ging ma ke s index. •TL BASED ISE: Is anbul s ock exchange na ional 100 index. Table 5.6: A ibu es o Is anbul S ock Exchange. Type Min. Max. A g. Med. SD SP loa -0.054 0.068 0.001 0.001 0.014 DAX loa -0.052 0.059 0.001 0.001 0.015 FTSE loa -0.055 0.05 0.001 0.0 0.013 NIKKEI loa -0.05 0.061 0.0 0.0 0.015 BOVESPA loa -0.054 0.064 0.001 0.0 0.016 EU loa -0.049 0.067 0.0 0.0 0.013 EM loa -0.039 0.048 0.001 0.001 0.011 TL BASED ISE loa -0.062 0.069 0.002 0.002 0.016 Human O al Bioa ailabili y The da ase se es as a complex, eal-wo ld applica ion in he ield o pha macoki- ne ics. I in ol es o ecas ing he human o al bioa ailabili y o a se o po en ial new d ug compounds based on a se o molecula desc ip o s [88]. Human o al bioa ailabili y, indica ed by %F, is he pa ame e ha measu es he pe - cen age o he ini ial o ally adminis e ed d ug dose ha e ec i ely eaches sys emic blood ci cula ion a e passing h ough he li e . Each ins ance is a ec o o molecula desc ip o alues iden i ying a candida e new d ug and each column ep esen s a molecula desc ip o . The a ge is he human o al bioa ailabili y, %F. The dis ibu ion o %F is plo ed in Figu e 5.2b. The a ibu es ha e no been de ailed because o he la ge quan i y and his will emain he same o he subsequen eg ession da ase s. (a) Is anbul S ock Exchange (b) Human O al Bioa ailabili y (c) LD50 Figu e 5.2: His og am o he a ge columns. 38 5.1. EXPERIMENTAL SETUP Median O al Le hal Dose: LD50 The da ase being s udied, which is d awn om he ield o pha macokine ics, conce ns he p edic ion o he median le hal dose o a molecula compound [7]. This is a widely used me ic o e alua ing he oxici y o d ugs. The ac onym LD s ands o Le hal Dose, and he e m LD50 e e s o he amoun o a subs ance, adminis e ed in one dose, ha esul s in he dea h o 50% o a g oup o es animals. Each da a poin consis s o a ec o ep esen ing a molecula compound, wi h he co esponding a ge being he LD50 alue. The dis ibu ion is depic ed in Figu e 5.2c Plasma P o ein Binding Le els: PPB This da ase , om he ield o pha macokine ics, aims o p edic he pe cen age o he ini ial d ug dose ha binds o plasma p o eins [7]. This measu e is o pa amoun impo ance as i ela es o he dis ibu ion o d ugs wi hin he body and hei abili y o each hei in ended a ge . The ins ances consis o ec o s ep esen ing molecula compounds, wi h he co esponding PPB alue se ing as he a ge . The dis ibu ion o hese alues is plo ed in Figu e 5.3a. Docking Ene gy The da ase in ques ion, belonging o he ield o d ug disco e y and design, aims o p edic he in e ac ion ene gy be ween a candida e d ug and i s a ge issue [83]. This me ic, known as docking ene gy, quan i ies he s eng h o binding be ween he molecules o he d ug and hose o he a ge . Each da a poin consis s o a ec o ep esen ing a molecula compound, wi h he co esponding a ge being he docking ene gy and he dis ibu ion is shown in Figu e 5.3b. Fluda abine The da ase is used o p edic he esponse o a se o cance pa ien s o he pha ma- cologic o he Fluda abine d ug [89]. I was buil looking o a unc ional ela ionship be ween gene exp essions and esponses o he Fluda abine. Each ins ance ep esen s a gene exp ession and he ea u es a e he exp ession le el o one pa icula gene. Ta ge is he he apeu ic esponse o he d ug. The dis ibu ion o i s alues is illus a ed in Figu e 5.3c. 39 CHAPTER 5. EXPERIMENTAL STUDY (a) PPB (b) Docking Ene gy (c) Fluda abine Figu e 5.3: His og am o he a ge columns. 5.1.2.2 Syn he ic Da ase s As p e iously s a ed in Chap e 3, Keijze demons a ed a signi ican enhancemen in he pe o mance o GP in symbolic eg ession h ough he in eg a ion o LS, as p esen ed in his pape [6]. He ca ied ou a se o expe imen s o illus a e he p ac ical bene i s o u ilizing LS. In o de o elimina e any biases ha may a ise om an a bi a y de ini ion o es ing unc ions, he used p oblems ha ha e been sou ced om p e ious esea ch ha a e ele an o he applica ion and enhancemen o symbolic eg ession. Besides being a good scien i ic p ac ice o es a me hod (in his s udy, LS) on he same case s udies ha we e used in he wo k ha in oduced ha me hod, mo i a ions o choosing hese benchma ks a e he same as in [6], i.e.: “many o he p oblems abo e mix igonome y wi h polynomials, o make he p oblems in o he ways highly non-linea ”. Also, i is ele an o poin ou ha , as s a ed in [6], “being o low dimensionali y does no make he p oblems easy howe e ”. The speci ics ega ding he sampling app oach and o he p oblem-speci ic de ails a e p esen ed in Table 5.7. The p oblem names a e kep he same as he pape . The da ase s we e hand- ailo ed acco ding o hese speci ics. The aining and es ing in e als a e indica ed using he [s a :s ep:s op] no a ion when he se is cons uc ed wi h sys ema ic in e als. The nd(min,max) no a ion symbolizes andom sampling wi hin a speci ied ange, while he mesh ([s a :s ep:s op]) no a ion signi ies egula sampling in wo-dimensional space. 40 5.1. EXPERIMENTAL SETUP Table 5.7: Syn he ic da ase se ings. P oblem Equa ion ange ( ain) ange ( es ) 4𝑓(𝑥)=𝑥3𝑒𝑥𝑝−1𝑐𝑜𝑠(𝑥)𝑠𝑖𝑛(𝑥)(𝑠𝑖𝑛2(𝑥)∗ 𝑐𝑜𝑠(𝑥)−1)[0:0.05:10] [0.05:0.05:10.05] 5𝑓(𝑥, 𝑦, 𝑧)=30𝑥𝑧 (𝑥−10)𝑦2x,z = nd(-1,1) [0:0.05:10] y = nd(1,2) [0:0.05:10] 6𝑓(𝑥)=Í𝑥 𝑖1/𝑖[1:1:50] [1:1:120] 7𝑓(𝑥)=𝑙𝑜𝑔𝑥 [1:1:100] [1:0.1:100] 8𝑓(𝑥)=√𝑥[0:1:100] [0:0.1:100] 9𝑓(𝑥)=𝑎𝑟𝑐𝑠𝑖𝑛ℎ(𝑥)[0:1:100] [0:0.1:100] 5.1.2.3 Classi ica ion Da ase s Fo his sec ion o he s udy, h ee di e en classi ica ion p oblems we e conside ed. Table 5.8 p o ides he numbe o ins ances and a ibu es o each da ase as well as he a io o a ge classes. The Bankno e Au hen ica ion Da ase , c ea ed wi h au hen ic and o ged bankno e images, was chosen o i s widesp ead use in bina y classi ica ion analysis in he da a science communi y. The Spo i y Funk Songs da ase is a da ase ha was es ablished wi h colleagues se e al yea s ago, in ol ing songs ex ac ed om se e al playlis . Finally, B eas Cance Wisconsin (Diagnos ic) da ase con ains p edic ions on b eas mass images. I is widely u ilized in nume ous ML and GP s udies. Table 5.8: Classi ica ion Da ase s. Ins ances Class Ra io A ibu es (class -1: class 1) Bankno e Au hen ica ion 1372 762 : 610 5 Spo i y Funk Songs 985 711 : 274 14 B eas Cance Wisconsin (Diagnos ic) 569 357 : 212 31 Bankno e Au hen ica ion This da ase is used o di e en ia e be ween au hen ic and o ged bankno es. The da ase was sou ced om he UCI ML eposi o y and is c edi ed o Volke Lohweg o he Uni e si y o Applied Sciences as he owne , wi h Helene Da ksen also o he Uni e si y o Applied Sciences c edi ed as he dono [90]. Images acqui ed om au hen ic and o ged bankno e-like specimens we e used o ex ac da a. An indus ial came a is used o digi iza ion. To ex ac ea u es om images, Wa ele T ans o m ool we e used. A Wa ele T ans o m can be used o ep esen he image as a sum o di e en equency sub-bands which is use ul o ea u e ex ac ion. The esul ing image is a se o coe icien s ha ep esen he di e en equency componen s o he image. The ea u es a e he a iance, skewness, cu osis o he Wa ele T ans o med image and he en opy o he image. Thei cha ac e is ics a e summa ized in Table 5.9. The a ge alue is -1 o au hen ic bankno es and 1 o he o ged bankno es. 41 CHAPTER 5. EXPERIMENTAL STUDY Table 5.9: A ibu es o Bankno e Au hen ica ion. Type Min. Max. A g. Med. SD a iance loa -7.0 6.8 0.4 0.5 2.8 skewness loa -13.8 13.0 1.9 2.3 5.9 cu osis loa -5.3 17.9 1.4 0.6 4.3 en opy loa -8.5 2.4 -1.2 -0.6 2.1 class in -1.0 1.0 -0.1 -1.0 1.0 Spo i y Funk Songs The da ase comp ises songs om i een dis inc playlis s ea u ing a ious gen es on Spo i y, one o he la ges audio s eaming se ice p o ide s. The playlis s encompass di e se hemes such as unky jams, hea y me al, oman ic ballads, and elaxing piano. The pla o m, named Spo i y Fo De elope s, enables de elope s o ex ac de ailed in o ma ion abou albums, acks, and playlis s. The da ase was es ablished by me and my colleagues o an ML p ojec aimed a p edic ing sui able songs o a unk band [91]. The a ibu es o he da ase a e elabo a ed below and a s a is ical summa y has been p o ided in Table 5.10. The songs can be classi ied acco ding o he a ge column, which is bina y in na u e. I he song belongs o a playlis ela ed o he unk gen e, i is labeled as 1, and -1 o he wise. •danceabili y: How sui able a ack is o dancing. •ene gy: Rep esen s a pe cep ual measu e o in ensi y and ac i i y. •key: The es ima ed o e all key o he ack. •loudness: The o e all loudness o a ack in decibels. •mode: Modali y (majo o mino ) o he ack. •speechness: P esence o spoken wo ds in a ack. •acous icness: A measu e indica ing he le el o acous icness. •ins umen alness: Measu es he le el o ins umen alness (no ocals). •li eness: De ec s he p esence o an audience in he eco ding. • alence: Desc ibes he musical posi i eness con eyed by a ack. • empo: The o e all es ima ed empo o a ack in bea s pe minu e (BPM). •du a ion_ms: The du a ion o he ack in milliseconds. • ime_signa u e: An es ima ed o e all ime signa u e (bea s pe measu e) o a ack. 42 5.1. EXPERIMENTAL SETUP Table 5.10: Fea u es o Spo i y Funk Songs Type Min. Max. A g. Med. SD danceabili y loa 0.0 0.9 0.5 0.5 0.2 ene gy loa 0.0 1.0 0.5 0.4 0.3 key in 0.0 11.0 5.2 5.0 3.6 loudness loa -43.9 -1.9 -14.2 -11.6 8.6 mode in 0.0 1.0 0.7 1.0 0.5 speechiness loa 0.0 0.8 0.1 0.0 0.1 acous icness loa 0.0 1.0 0.5 0.5 0.4 ins umen alness loa 0.0 1.0 0.4 0.1 0.4 li eness loa 0.0 1.0 0.2 0.1 0.1 alence loa 0.0 1.0 0.4 0.3 0.3 empo loa 0.0 211.3 116.1 112.8 31.6 du a ion_ms in 62693.0 1215573.0 253833.2 229360.0 125928.2 ime_signa u e in 0.0 5.0 3.8 4.0 0.5 a ge in -1.0 1.0 -0.4 -1.0 0.9 B eas Cance Wisconsin (Diagnos ic) The da ase comp ises ins ances o digi al images o ine needle aspi a es (FNA) o b eas masses [92]. Fine-needle aspi a ion is a diagnos ic p ocedu e employed o in es iga e lumps o masses. This echnique in ol es he inse ion o a hin, hollow needle in o he mass o ob ain a sample o cells, which, upon being s ained, a e subsequen ly examined unde a mic oscope. The ea u es o he da ase desc ibe he cha ac e is ics o he cell nuclei p esen in he images. Fo each cell nucleus, he e a e 10 ea u es wi h loa da a ype: • adius (mean o dis ances om cen e o poin s on he pe ime e ) • ex u e (s anda d de ia ion o g ay-scale alues) •pe ime e •a ea •smoo hness (local a ia ion in adius leng hs) •compac ness (𝑝𝑒𝑟𝑖𝑚𝑒𝑡𝑒𝑟2/𝑎𝑟𝑒𝑎 −1.0) •conca i y (se e i y o conca e po ions o he con ou ) •conca e poin s (numbe o conca e po ions o he con ou ) •symme y • ac al dimension ("coas line app oxima ion" - 1) The mean, s anda d e o , and "wo s " o la ges (mean o he h ee la ges alues) o hese ea u es we e compu ed o each image, esul ing in 31 a ibu es in o al wi h he a ge . The ex ensi e numbe o a ibu es has led o he decision o no display he s a is ical summa y o each one. The a ge is he diagnosis which is classi ied as -1 o benign cases and 1 o malignan cases. 43 CHAPTER 5. EXPERIMENTAL STUDY 5.2 Expe imen al Resul s 5.2.1 Reg ession Expe imen s The ollowing igu es om 5.4 o 5.18 display he pe o mance o he GSGP and GSGP- LS algo i hms on bo h he aining and es se s o he nine conside ed eg ession da ase s. The median i ness, measu ed in e ms o RMSE, o he bes indi idual is plo ed agains he gene a ion numbe o each con igu a ion, based on he esul s o 60 independen uns. The median was chosen o e he mean as i is mo e obus o ou lie s, p o iding a mo e eliable ep esen a ion o he da a. F om he Figu es 5.4,5.7,5.12, i can be deduced ha GSGP-LS consis en ly ou pe - o ms GSGP on he aining se o all conside ed p oblems. Conce ning he esul s on he es se , i can be no iced om he Figu e 5.4 ha GSGP-LS ou pe o ms GSGP on h ee o he conside ed p oblems: •Bos on Housing (Bos on) •Conc e e Comp essi e S eng h (Conc e e) •Uni ied Pa kinson’s Disease Ra ing Scale (Pa kinson) Ne e heless, as i can be obse ed in Figu es 5.7 and 5.12, GSGP-LS su e s om o e i ing issues on six o he conside ed p oblems: •Is anbul S ock Exchange (Is anbul) •Human O al Bioa ailabili y (Bioa ailabili y) •Median O al Le hal Dose: LD50 (LD50) •Plasma P o ein Binding Le els: PPB (PPB) •Docking Ene gy (Docking) •Fluda abine (Fluda abine) To assess he s a is ical signi icance o hese esul s Mann-Whi ney U es wi h s a is ical signi icance a 𝛼= 0 . 05 was pe o med o bo h aining and es se s, o each p oblem, a each gene a ion, wi h he null hypo hesis ha he dis ibu ion o he RMSE o he bes indi idual o igina ed om he 60 uns is he same o GSGP and GSGP-LS. The esul s o compa ing he wo algo i hms on he aining se a e deemed s a is ically signi ican , as indica ed by consis en ly low 𝑝 - alues o app oxima ely 10 −12 . The 𝑝 - alues a e epo ed in Figu es 5.6,5.9,5.11. The e olu ion o he 𝑝 - alue esul ing om he compa ison o he wo algo i hms on he es se is epo ed in Figu es 5.5, 5.8,5.10. The signi icance h eshold in each plo is also shown by ed ho izon al line a 0.05. The esul s o he es se o he Bos on, Conc e e, and Pa kinson da ase s, as illus a ed in Figu e 5.4, p o ide obus e idence o he supe io i y o GSGP-LS o e GSGP. The decline in he RMSE is no signi ican o GSGP-LS, as i commences om a 44 5.2. EXPERIMENTAL RESULTS much lowe RMSE alue. I is no ewo hy o conside ha hese da ase s possess a high a io o ins ances o a ibu es and ha e been ex ensi ely s udied, wi hou any epo ed endency o o e i . The 𝑝 - alue plo s in Figu es 5.5,5.6 consis en ly demons a e a alue nea ze o, suppo ing he a o emen ioned obse a ion. Figu es 5.7,5.12 demons a e clea o e i ing o all da ase s i demons a es. The Bioa ailabili y and PPB da ase s sha e a cha ac e is ic on he es se : despi e GSGP- LS s a ing om a lowe alue, i begins o inc ease and esul s in a poo e model, whe eas his end is no obse ed o he GSGP algo i hm. The inc ease is mo e sub le in he case o Bioa ailabili y and mo e p onounced in PPB. The possible causes a e discussed in Subsec ion 5.3. E en hough he 𝑝 - alues in Figu e 5.8,5.10 being below he h eshold, his is due o he lines no ha ing con e ged ye . PPB is no he only da ase exhibi ing a no iceable inc ease in RMSE. The LD50 and Fluda abine da ase s also demons a e simila cha ac e is ics, s a ing om a low RMSE and hen inc easing o a le el e en highe han ha o GSGP. As a esul , hei 𝑝 - alues a e ini ially close o ze o bu e en ually exceed he h eshold. While his does no di ec ly cause o e i ing, i is wo h no ing ha hese h ee da ase s sha e a c i ical aspec : hey all ha e a e y low a io o ins ances o a ibu es. Is anbul and Docking does no su e om low ins ance o a ibu e a io bu i can be obse ed ha GSGP-LS canno show a supe io pe o mance. I con e ges wi h GSGP and emains s agnan o many gene a ions wi h Docking. Al hough i ini ially begins wi h a lowe RMSE, he wo me hods ha e a compa able pe o mance wi h Is anbul. Fo bo h, he 𝑝 - alue s a s om a alue close o ze o, hen g adually inc eases as he wo me hods s a o ha e compa able pe o mance and e en ually he 𝑝 - alue s a s o decline a e abou 400-450 gene a ions. Then, GSGP s a s pe o ming be e and RMSE s a s inc easing wi h GSGP-LS algo i hm. The ac ha he GSGP-LS e o cu es on he es se o Bioa ailabili y, LD50, PPB and Fluda abine a e inc easing since he e y i s gene a ions should also be no iced. The analysis and discussion on he ma e is deepened in Subsec ion 5.3. Las ly, i is in e es ing o no ice ha , o bo h aining and es se s, he ini ial RMSE o GSGP-LS is al eady lowe han ha a he end o e olu ion o s anda d GSGP. On he aining se , his ou come was expec ed, gi en he known bene i s o LS on he ini ial popula ion [6]. 45 CHAPTER 5. EXPERIMENTAL STUDY Figu e 5.4: Resul s o he expe imen al compa ison be ween GSGP and GSGP-LS wi h Bos on, Conc e e and Pa kinson da ase s. Figu e 5.5: E olu ion o 𝑝 - alues esul ing om he compa ison be ween GSGP and GSGP-LS on es da a o Bos on, Conc e e and Pa kinson da ase s. 46 5.2. EXPERIMENTAL RESULTS Figu e 5.6: E olu ion o 𝑝 - alues esul ing om he compa ison be ween GSGP and GSGP-LS on aining da a o Bos on, Conc e e and Pa kinson da ase s. Figu e 5.7: Resul s o he expe imen al compa ison be ween GSGP and GSGP-LS wi h Is anbul, Bioa ailabili y, LD50 da ase s. 47 CHAPTER 5. EXPERIMENTAL STUDY Table 5.11: Median Classi ica ion Repo o Bankno e GSGP P ecision Recall F1 Sco e Suppo -1 0.948 0.943 0.932 225 1 0.929 0.932 0.915 187 Accu acy 0.925 GSGP-LS P ecision Recall F1 Sco e Suppo -1 0.97 0.996 0.983 225 1 0.995 0.963 0.98 187 Accu acy 0.982 (a) GSGP (b) GSGP-LS Figu e 5.19: Con usion Ma ices o he bes indi iduals o Bankno e Au hen ica ion Table 5.12: Median Classi ica ion Repo o Spo i y Funk Songs GSGP P ecision Recall F1 Sco e Suppo -1 0.925 0.95 0.933 204 1 0.88 0.821 0.835 92 Accu acy 0.904 GSGP-LS P ecision Recall F1 Sco e Suppo -1 0.949 0.94 0.944 213.5 1 0.845 0.867 0.856 82.5 Accu acy 0.919 54 5.2. EXPERIMENTAL RESULTS (a) GSGP (b) GSGP-LS Figu e 5.20: Con usion Ma ices o he bes indi iduals o Spo i y Funk Songs Table 5.13: Median Classi ica ion Repo o B eas Cance Wisconsin GSGP P ecision Recall F1 Sco e Suppo -1 0.944 0.961 0.948 105.5 1 0.936 0.899 0.915 65.5 Accu acy 0.936 GSGP-LS P ecision Recall F1 Sco e Suppo -1 0.977 0.947 0.963 111 1 0.905 0.959 0.932 60 Accu acy 0.953 (a) GSGP (b) GSGP-LS Figu e 5.21: Con usion Ma ices o he bes indi iduals o B eas Cance Wisconsin 55 CHAPTER 5. EXPERIMENTAL STUDY Figu e 5.22: Resul s o he expe imen al compa ison be ween GSGP and GSGP-LS wi h Bankno e, Spo i y and Wisconsin da ase s. Figu e 5.23: E olu ion o 𝑝 - alues esul ing om he compa ison be ween GSGP and GSGP-LS on es da a o Bankno e, Spo i y and Wisconsin da ase s. 56 5.3. DISCUSSION ON RESULTS Figu e 5.24: E olu ion o 𝑝 - alues esul ing om he compa ison be ween GSGP and GSGP-LS on aining da a o Bankno e, Spo i y and Wisconsin da ase s. 5.3 Discussion on Resul s E en hough he esul s ob ained wi h GSGP-LS appea gene ally p omising, some o e i ing issues we e encoun e ed in eal-li e p oblems and heo e ical benchma k p oblems. Fo eal-li e p oblems, i can be obse ed ha LS wo sens he o e i ing issues on he Bioa ailabili y, LD50, PPB, Docking and Fluda abine da ase s. Thus, i can be concluded ha LS can induce o wo sen o e i ing on some p oblems on GSGP. Taking a close look a hese "p oblema ic" da ase s, i can be no iced ha hey sha e wo aspec s which make hem pa icula ly di icul o he eg ession ask, and ha e e en al eady caused some o hem o be c i icised in he li e a u e [93]. Fi s , hey ha e a la ge amoun o ea u es compa ed o he amoun o ins ances a ailable (i.e., he e a e many mo e ows han columns in he da ase ). And second, he e a e simila obse a ions which map o di e en a ge alues. Fo hese easons, hese da ase s a e ela i ely p one o o e i ing. The syn he ic da ase s ha e e ealed o e i ing issues on p oblems 4 and 5. The unc ion o he p oblem 4 includes exponen ial, sine, and cosine unc ions, hus i is easonable o su mise ha he LS is s uggling o accu a ely i he shape o he p oblem. To add ess his issue, he expe imen was epea ed using a unc ion se . To add non-linea i y o he unc ion se , he ollowing unc ions we e included: addi ion, mul iplica ion, ecip ocal, nega ion, squa e oo , and sine ( {+,∗, 1 /𝑥, −𝑥, √𝑥, 𝑠𝑖𝑛(𝑥)} ). RMSE plo s o he p oblem 4 wi h new unc ion se can be obse ed in Figu e 5.25. Addi ionally, 𝑝 - alues o he es se is plo ed in Figu e 5.26. Examining he esul s, i can be concluded ha i is wo h in es iga ing he impac o he unc ion se . Going back o he esul s o eg ession p oblems, addi ional insigh s can be gained on possible ways o o e come he o e i ing issue. Since he es e o s a s wi h a easonable alue and only signi ican ly inc eases a e some gene a ions, as pe de ini ion o o e i ing, he mos i ial solu ion would be o s op he e olu ion ea lie . Howe e , deciding a p ope s opping condi ion o ackle he p oblem is no 57 CHAPTER 5. EXPERIMENTAL STUDY Figu e 5.25: Resul s o he expe imen al compa ison be ween GSGP and GSGP-LS wi h p oblem_4 wi h he al e na i e unc ion se . (a) Tes Se (b) T aining Se Figu e 5.26: E olu ion o 𝑝 - alues esul ing om he compa ison be ween GSGP and GSGP-LS on es and aining da a o p oblem_4 wi h he al e na i e unc ion se . s aigh o wa d. The simples solu ion in ha sense would be o in oduce a alida ion se o simula e he e o on unseen da a along e olu ion, o de ec immedia ely i he solu ion is s a ing o o e i . Howe e , his s a egy is only iable wi h la ge enough da ase s, since i implies spli ing he da ase in mo e pa s, hence educing he amoun o obse a ions in each. In ac , i e da ase s whe e we obse ed o e i ing su e om lack o ins ances, hus becoming no ideal candida es o his solu ion. A mo e sophis ica ed ea ly s opping c i e ion, which seems mo e sui able o he da ase s a hand, has been p oposed in [94] o le e age he seman ic in o ma ion a ailable in GSGP o deciding when o end he e olu iona y op imiza ion. No ably, such a c i e ion would also yield he posi i e side e ec o imp o ing he o e all compu a ion e iciency o he p ocess. Howe e , bo h he cu es o he es se i ness o GSGP-LS a e inc easing since he e y beginning o he un on LD50, PPB and 58 5.3. DISCUSSION ON RESULTS Fluda abine. This induces a hough : al hough wo h in es iga ion, ea ly s opping may no be enough o gene a e eliable models in hose cases. Fo his eason, in he Chap e 6, o he s a egies ha should be explo ed in he u u e o limi o e i ing a e p oposed. In he case o p oblem 5, a pla eau in RMSE alues was no ed ea ly on in he gene a ions. This could be a ibu ed o he di ision in he de ini ion o p oblem 5. The di ision was de ined in he unc ion se as a p o ec ed di ision, which e u ned a cons an alue o 1 o cases whe e he denomina o was 0. This could esul in a cons an beha io o he model. The o e i ing in his scena io is no due o he p oblem i sel , bu a he o he choice o p o ec ed di ision. The algo i hm app oxima es he di ision wi h a alue ha is no he ac ual esul o he di ision, which causes in a de ia ion om he da a. As a esul , he algo i hm disca ds he good esul s and is unable o imp o e i s pe o mance. Du ing he classi ica ion expe imen s, no o e i ing was obse ed. Howe e , an impo an aspec was no ed ega ding he use o classi ica ion and LS: he class alues assigned o he a ge s play a c ucial ole in ensu ing he p ope unc ioning o he LS me hod. When he model used 0 and 1 as labels, i ailed o co ec ly p edic mo e han hal o he ins ances o class 1, esul ing in subpa pe o mance. To comp ehend he easoning behind his, i is impe a i e o ecall he linea scaling equa ions 5.1. 𝑏= 𝑛 Õ 𝑖=1h𝑡𝑖−𝑡𝑃(𝑥𝑖)−𝑃i 𝑛 Õ 𝑖=1𝑃(𝑥𝑖)−𝑃2 𝑎=𝑡−𝑏 𝑃 (5.1) whe e 𝑃 is a GSGP indi idual, 𝑃(𝑥𝑖) is he ou pu o he indi idual calcula ed on obse a ion 𝑥𝑖 , 𝑃 is he a e age ou pu , 𝑡 is a ge alues, 𝑡 is he a e age a ge alues, 𝑎 and 𝑏 a e LS cons an s. A e calcula ing 𝑎 and 𝑏 , indi idual 𝑃 is e alua ed by calcula ing he e o o 𝑎+𝑏𝑃. The p oblem occu s due o he u iliza ion o he labels 0 o he a ge s. Since 0 is always he mino i y class in he da ase s used in his s udy, he mean o he labels, 𝑡 , will always be sligh ly smalle han 0.5: 𝑡+𝜖=0.5, whe e 𝜖 > 0 This leads o a si ua ion whe e he sub ac ion o 𝑡𝑖 and 𝑡 will esul in a alue sligh ly highe han 0.5, leading o an app oxima ion o 0 o 𝑏when he label is 1: 𝑡𝑖−𝑡−𝜖=0.5, whe e 𝜖 > 0 𝑏≈0 as 𝑎and 𝑃𝑠𝑐𝑎𝑙𝑒𝑑 a e de ined as: 59 CHAPTER 5. EXPERIMENTAL STUDY 𝑎=𝑡−𝑏𝑃, 𝑃𝑠𝑐𝑎𝑙𝑒𝑑 =𝑎+𝑏𝑃 a dec eases o a sligh ly lesse alue han 𝑡 and 𝑃𝑠𝑐𝑎𝑙𝑒𝑑 becomes sligh ly smalle han a: 𝑎+𝜖=𝑡, 𝑃𝑠𝑐𝑎𝑙𝑒𝑑 +𝜖=𝑎, whe e 𝜖 > 0 causing he mos o he p edic ions o class 1 o be conside ed as 0. In his scena io, he use o 0 as label in he equa ion esul s in an app oxima ely cons an ou pu . The p edic ions a e no based on he class, bu ins ead, a ise om he inhe en p ope ies o 0 as he iden i y elemen o mul iplica ion. To esol e his issue, he class labels we e al e ed o -1 and 1, and subsequen expe imen a ion e ealed ha he oo cause was he use o 0 in he equa ions. 60 6 Conclusions and Fu u e Wo k This inal chap e o he disse a ion p esen s a b ie o e iew o he p oposed wo k and summa izes he main conclusions ela ed o Geome ic Seman ic Gene ic P og am- ming (GSGP) wi h Linea Scaling (LS). Addi ionally, sugges ions o u he esea ch a e pu o wa d. The p esen ed echnique, e e ed o as GSGP, is g ounded in a heo e ical ame- wo k ha has been ho oughly elucida ed. GSGP is a a ia ion o Gene ic P og amming (GP) ha employs wo inno a i e gene ic ope a o s, Geome ic Seman ic Ope a o s (GSO), in lieu o he con en ional c osso e and mu a ion ope a o s. Ano he echnique, LS, ocuses on al e ing he i ness o solu ions wi hou modi ying he gene ic ope a o s hemsel es. The heo e ical unde pinnings o bo h GSGP and LS a e delinea ed in he backg ound sec ion, and a de ailed desc ip ion o he implemen a ion o bo h ech- niques is p esen ed in he me hodology. The e ec s o augmen ing GSGP wi h LS was explo ed in his wo k. In pa icula , encou aged by he success ha was ob ained in [15], he wo k aimed a in es iga ing he combina ion o he bene icial ai s o hese wo me hods, which can bo h ou pe o m s anda d GP, by imp o ing he gene ic ope a o s – o GSGP – and he i ness – o LS. The analysis in ol ed a ho ough expe imen al e alua ion on he ask o symbolic eg ession o six heo e ical benchma ks and nine eal-li e p oblems o a ious di icul- ies besides h ee eal-li e p oblems om di e en ields o classi ica ion ask. GSGP was compa ed agains GSGP wi h LS (GSGP-LS), bo h in e ms o e iciency, i.e., how as e olu ion is able o achie e he desi ed goal, and in e ms o gene aliza ion, i.e., how well he induced model is able o gene alize o unseen da a. The indings demons a e subs an ial enhancemen s in mos ins ances, bo h in he aining and es ing se s, when compa ed o he s anda d GSGP app oach. Mo eo e , he esul s indica e ha LS accele a es he e olu iona y sea ch p ocess compa ed o GSGP. These conclusions hold o bo h eg ession and classi ica ion p oblems. No ably, in he classi ica ion p oblems, no ins ances o o e i ing we e de ec ed, and he da ase s unde examina ion had no p e iously been lagged as p one o o e i ing. 61 CHAPTER 6. CONCLUSIONS AND FUTURE WORK Howe e , i was obse ed ha he in eg a ion wi h LS makes GSGP mo e p one o o e i ing when he add essed p oblem is cha ac e ized by pa icula ly di icul da a which was obse ed wi h eg ession p oblems. None heless, om he beha io o LS du ing he e olu ion, i was concluded ha sea ch p ocess could be s opped ea lie o achie e compa able o be e esul s han wi hou LS, o bo h GP and GSGP, wi h he desi able side e ec o sa ing compu a ion ime. Fo GSGP, he app oach o ea ly s opping based on seman ic neighbou hood p esen ed in [94] can be conside ed pa icula ly p omising. Besides ea ly s opping, o he me hods ha e ecen ly demons a ed hei e ec i eness in con olling o e i ing. Fo ins ance, one may imagine o de elop a sys em in which LS is u ned on and o dynamically du ing he e olu ion. A simila app oach has been ecen ly p esen ed o a sui able use o local sea ch inside GSGP [95]. In ha con ibu ion, GSGP was enhanced wi h local sea ch a he beginning o he un, bu local sea ch was la e disabled, o an app op ia e con ol o o e i ing. A simila idea may le GSGP-LS o exploi he ad an ages o LS in he ini ial gene a ions, and la e he e olu ion could con inue using GSGP wi hou LS o con ol o e i ing. O he me hods ha ha e been de ined o con ol o e i ing o GSGP and GP a e he dynamic in e lea ing o aining ins ances [96] and so a ge egula iza ion [97]. These me hods look p omising o GSGP-LS. Las bu no leas , he use o an explici ea u e selec ion in a p ep ocessing phase [98], o in eg a e he implici ea u e selec ion al eady pe o med by GP du ing he lea ning, like o ins ance he app oach p oposed in [99], should be in es iga ed. Fu he mo e, u u e s udies and expe imen s ocusing on GSGP-LS and classi ica ion should be conduc ed using la ge and mo e complex da ase s. 62 BIBLIOGRAPHY [54] L. Beadle and C. Johnson. “Seman ic analysis o p og am ini ialisa ion in gene ic p og amming”. In: Gene ic P og amming and E ol able Machines 10 (2009-09), pp. 307–337. doi:10.1007/s10710-009-9082-5 (ci . on p. 19). [55] D. Jackson. “Pheno ypic Di e si y in Ini ial Gene ic P og amming Popula ions”. In: ol. 6021. 2010-04, pp. 98–109. isbn: 978-3-642-12147-0. doi: 10.1007/978-3 -642-12148-7_9 (ci . on p. 19). [56] K. K awiec and P. Lichocki. “App oxima ing geome ic c osso e in seman ic space”. In: 2009-01, pp. 987–994. doi:10.1145/1569901.1570036 (ci . on p. 19). [57] K. K awiec and B. Wieloch. “Analysis o Seman ic Modula i y o Gene ic P og amming”. In: Founda ions o Compu ing and Decision Sciences 34 (2009-01), pp. 265–285 (ci . on p. 19). [58] Q. U. Nguyen, N. Hoai, and M. O’Neill. “Seman ic Awa e C osso e o Gene ic P og amming: The Case o Real-Valued Func ion Reg ession”. In: 2009-04, pp. 292–302. isbn: 978-3-642-01180-1. doi: 10.1007/978-3-642-01181-8_25 (ci . on p. 19). [59] Q. U. Nguyen e al. “Seman ically-based c osso e in gene ic p og amming: Applica ion o eal- alued symbolic eg ession”. In: Gene ic P og amming and E ol able Machines 12 (2011-06), pp. 91–119. doi: 10.1007/s10710-010-9121-2 (ci . on p. 20). [60] M. Cas elli, L. Vanneschi, and S. Sil a. “P edic ion o high pe o mance conc e e s eng h using Gene ic P og amming wi h geome ic seman ic gene ic ope a o s”. In: Expe Sys ems wi h Applica ions: An In e na ional Jou nal 40 (2013-12), pp. 6856– 6862. doi:10.1016/j.eswa.2013.06.037 (ci . on pp. 20,35). [61] M. Cas elli, L. Vanneschi, and S. Sil a. “P edic ion o he Uni ied Pa kinson’s Disease Ra ing Scale assessmen using a gene ic p og amming sys em wi h geome ic seman ic gene ic ope a o s”. In: Expe Sys ems wi h Applica ions 41 (2014-08), 4608–4616. doi:10.1016/j.eswa.2014.01.018 (ci . on pp. 20,36). [62] M. Cas elli, L. Manzoni, and L. Vanneschi. “An E icien Gene ic P og amming Sys em wi h Geome ic Seman ic Ope a o s and i s Applica ion o Human O al Bioa ailabili y P edic ion”. In: (2012-08) (ci . on p. 20). [63] I. Baku o e al. “Gene al Pu pose Op imiza ion Lib a y (GPOL): A Flexible and E icien Mul i-Pu pose Op imiza ion Lib a y in Py hon”. In: Applied Sciences 11 (2021-05). doi:10.3390/app11114774 (ci . on p. 20). [64] H. Iba, T. Sa o, and H. de Ga is. “Sys em iden i ica ion app oach o gene ic p og amming”. In: P oceedings o he Fi s IEEE Con e ence on E olu iona y Com- pu a ion. IEEE Wo ld Cong ess on Compu a ional In elligence. 1994, 401–406 ol.1. doi:10.1109/ICEC.1994.349917 (ci . on p. 21). 68 BIBLIOGRAPHY [65] H. Iba and N. Nikolae . “Gene ic p og amming polynomial models o inancial da a se ies”. In: P oceedings o he 2000 Cong ess on E olu iona y Compu a ion. CEC00 (Ca . No.00TH8512). Vol. 2. 2000, 1459–1466 ol.2. doi: 10.1109/CEC.20 00.870826 (ci . on p. 21). [66] N. Nikolae and H. Iba. “Regula iza ion app oach o induc i e gene ic p og am- ming”. In: IEEE T ansac ions on E olu iona y Compu a ion 5.4 (2001), pp. 359–375. doi:10.1109/4235.942530 (ci . on p. 21). [67] H. G. Hiden. “Da a-based modelling using gene ic p og amming.” PhD hesis. Uni e si y o Newcas le upon Tyne, 1998 (ci . on p. 21). [68] M. - J. Willis e al. “Gene ic p og amming: An in oduc ion and su ey o ap- plica ions”. In: Second in e na ional con e ence on gene ic algo i hms in enginee ing sys ems: inno a ions and applica ions. IET. 1997, pp. 314–319 (ci . on p. 21). [69] B. McKay e al. “Non-linea con inuum eg ession using gene ic p og amming”. In: P oceedings o he 1s Annual Con e ence on Gene ic and E olu iona y Compu a ion- Volume 2. 1999, pp. 1106–1111 (ci . on p. 21). [70] M. Keijze . “Scaled Symbolic Reg ession”. In: Gene ic P og amming and E ol able Machines 5.3 (2004), 259–269. issn: 1389-2576. doi: 10.1023/B:GENP.000003019 5.77571. 9 (ci . on p. 21). [71] F. A che i, I. Gio dani, and L. Vanneschi. “Gene ic p og amming o an icance he apeu ic esponse p edic ion using he NCI-60 da ase ”. In: Compu e s & Ope a ions Resea ch 37 (2010-08), pp. 1395–1405. doi: 10.1016/j.co .2009.02 .015 (ci . on p. 21). [72] C. Pennachin, M. Looks, and J. A. de Vasconcelos. “Robus Symbolic Reg ession wi h A ine A i hme ic”. In: Gene ic and E olu iona y Compu a ion COn e ence (GECCO). 2010 (ci . on p. 21). [73] R. M. A. Azad and C. Ryan. “A Simple App oach o Li e ime Lea ning in Gene ic P og amming-Based Symbolic Reg ession”. In: E olu iona y Compu a ion 22.2 (2014-06), pp. 287–317. issn: 1063-6560. doi: 10.1162/EVCO_ a_00111 . ep in : h ps://di ec .mi .edu/e co/a icle- pd /22/2/287/1509584 /e co _a _00111.pd (ci . on p. 21). [74] M. Vi golin, T. Alde lies en, and P. A. N. Bosman. “Linea Scaling wi h and wi hin Seman ic Backp opaga ion-Based Gene ic P og amming o Symbolic Reg ession”. In: P oceedings o he Gene ic and E olu iona y Compu a ion Con e ence. GECCO ’19. P ague, Czech Republic: Associa ion o Compu ing Machine y, 2019, 1084–1092. isbn: 9781450361118. doi: 10.1145/3321707.3321758 (ci . on p. 22). 69 BIBLIOGRAPHY [75] S. Rube o, V. Te agni, and J. Moo e. “A seman ic gene ic p og amming ame- wo k based on dynamic a ge s”. In: Gene ic P og amming and E ol able Machines 22 (2021-12), pp. 1–31. doi:10.1007/s10710-021-09419-3 (ci . on p. 22). [76] S. Rube o, V. Te agni, and J. H. Moo e. “Towa ds E ec i e GP Mul i-Class Classi ica ion Based on Dynamic Ta ge s”. In: P oceedings o he Gene ic and E olu iona y Compu a ion Con e ence. GECCO ’21. Lille, F ance: Associa ion o Compu ing Machine y, 2021, 812–821. isbn: 9781450383509. doi: 10.1145/344 9639.3459324 (ci . on p. 22). [77] D. Mede nach e al. “A New Wa e: A Dynamic App oach o Gene ic P og am- ming”. In: P oceedings o he Gene ic and E olu iona y Compu a ion Con e ence 2016. GECCO ’16. Den e , Colo ado, USA: Associa ion o Compu ing Machine y, 2016, 757–764. isbn: 9781450342063. doi: 10.1145/2908812.2908857 .u l: h ps://doi.o g/10.1145/2908812.2908857 (ci . on p. 22). [78] A. S. Sambo e al. “Fea u e Enginee ing o Imp o ing Robus ness o C osso e in Symbolic Reg ession”. In: P oceedings o he 2020 Gene ic and E olu iona y Compu a ion Con e ence Companion. GECCO ’20. Cancún, Mexico: Associa ion o Compu ing Machine y, 2020, 249–250. isbn: 9781450371278. doi: 10.1145 /3377929.3390078 .u l: h ps://doi.o g/10.1145/3377929.3390078 (ci . on p. 22). [79] M. Cas elli e al. “The in luence o popula ion size in geome ic seman ic GP”. In: Swa m and E olu iona y Compu a ion 32 (2017), pp. 110–120. issn: 2210-6502. doi:h ps://doi.o g/10.1016/j.swe o.2016.05.004 (ci . on p. 32). [80] L. Vanneschi, I. Baku o , and M. Cas elli. “An ini ializa ion echnique o geome ic seman ic GP based on demes e olu ion and despecia ion”. In: 2017-06, pp. 113–120. doi:10.1109/CEC.2017.7969303 (ci . on p. 32). [81] M. Cas elli e al. “Geome ic Seman ic Gene ic P og amming wi h Local Sea ch”. In: 2015-07. doi:10.1145/2739480.2754795 (ci . on p. 32). [82] L. Vanneschi e al. “Alignmen -based gene ic p og amming o eal li e appli- ca ions”. In: Swa m and E olu iona y Compu a ion 44 (2018-09). doi: 10.1016 /j.swe o.2018.09.006 (ci . on p. 32). [83] F. A che i, I. Gio dani, and L. Vanneschi. “Gene ic p og amming o QSAR in es iga ion o docking ene gy”. In: Applied So Compu ing 10.1 (2010), pp. 170– 182. issn: 1568-4946. doi: h ps://doi.o g/10.1016/j.asoc.2009.06.013 . u l: h ps://www.sciencedi ec .com/science/a icle/pii/S15684946090 00787 (ci . on pp. 33,39). [84] D. Ha ison and D. L. Rubin eld. “Hedonic housing p ices and he demand o clean ai ”. In: Jou nal o En i onmen al Economics and Managemen 5.1 (1978), pp. 81–102. issn: 0095-0696. doi: h ps://doi.o g/10.1016/0095-0696(78)9 0006-2 (ci . on p. 34). 70 BIBLIOGRAPHY [85] I. - C. Yeh. “Modeling o s eng h o high-pe o mance conc e e using a i icial neu al ne wo ks”. In: Cemen and Conc e e Resea ch 28.12 (1998), pp. 1797–1808. issn: 0008-8846. doi: h ps://doi.o g/10.1016/S0008-8846(98)00165-3 (ci . on p. 35). [86] M. A. Li le e al. “Exploi ing Nonlinea Recu ence and F ac al Scaling P ope ies o Voice Diso de De ec ion”. In: BioMedical Enginee ing OnLine 6.1 (2007), p. 23. issn: 1475-925X. doi:10.1186/1475-925X-6-23 (ci . on p. 36). [87] O. Akbilgic e al. “A no el Hyb id RBF Neu al Ne wo ks model as a o ecas e ”. In: S a is ics and Compu ing 24 (2013-05). doi: 10.1007/s11222-013-9375-7 (ci . on p. 37). [88] F. A che i e al. “Gene ic P og amming o Human O al Bioa ailabili y o D ugs”. In: P oceedings o he 8 h Annual Con e ence on Gene ic and E olu iona y Compu a ion. GECCO ’06. Sea le, Washing on, USA: Associa ion o Compu ing Machine y, 2006, 255–262. isbn: 1595931864. doi: 10.1145/1143997.1144042 . u l:h ps://doi.o g/10.1145/1143997.1144042 (ci . on p. 38). [89] L. Vanneschi, D. Codecasa, and G. Mau i. “A Compa a i e S udy o Fou Pa allel and Dis ibu ed PSO Me hods”. In: New Gene a ion Compu . 29 (2011-04), pp. 129– 161. doi:10.1007/s00354-010-0102-z (ci . on p. 39). [90] Volke Lohweg, Helene Doe ksen. Bankno e Au hen ica ion Da a Se . The UCI Machine Lea ning Reposi o y. Accessed: 2023-27-02. 2012. u l: h ps:// a chi e.ics.uci.edu/ml/da ase s/bankno e+au hen ica ion (ci . on p. 41). [91] Bu ak Ka acayi , Be in Sakallioglu, F. Zulal Ki az. Song P edic ion o a Funk Band using Machine Lea ning Algo i hms. ML P ojec . 2020 (ci . on p. 42). [92] N. S ee , W. Wolbe g, and O Mangasa ian. “Nuclea Fea u e Ex ac ion Fo B eas Tumo Diagnosis”. In: P oc. Soc. Pho o-Op . Ins . Eng. 1993 (1999-01). doi: 10.1117/12.148698 (ci . on p. 43). [93] G. Dick, A. P. Rimoni, and P. A. Whigham. “A e-examina ion o he use o gene ic p og amming on he o al bioa ailabili y p oblem”. In: P oceedings o he 2015 Annual Con e ence on Gene ic and E olu iona y Compu a ion. 2015, pp. 1015–1022 (ci . on p. 57). [94] I. Gonçal es e al. “Unsu e when o s op? ask you seman ic neighbo s”. In: P oceedings o he Gene ic and E olu iona y Compu a ion Con e ence. 2017, pp. 929– 936 (ci . on pp. 58,62). [95] M. Cas elli e al. “Geome ic Seman ic Gene ic P og amming wi h Local Sea ch”. In: P oceedings o he 2015 Annual Con e ence on Gene ic and E olu iona y Compu a- ion. GECCO ’15. Mad id, Spain: Associa ion o Compu ing Machine y, 2015, 999–1006. isbn: 9781450334723. doi:10.1145/2739480.2754795 (ci . on p. 62). 71 BIBLIOGRAPHY [96] I. Gonçal es and S. Sil a. “Balancing Lea ning and O e i ing in Gene ic P o- g amming wi h In e lea ed Sampling o T aining Da a”. In: Gene ic P og amming. Ed. by K. K awiec e al. Be lin, Heidelbe g: Sp inge Be lin Heidelbe g, 2013, pp. 73–84. isbn: 978-3-642-37207-0 (ci . on p. 62). [97] L. Vanneschi and M. Cas elli. “So a ge and unc ional complexi y educ ion: A hyb id egula iza ion me hod o gene ic p og amming”. In: Expe Sys ems wi h Applica ions 177 (2021), p. 114929. issn: 0957-4174. doi: h ps://doi.o g/10.1 016/j.eswa.2021.114929 (ci . on p. 62). [98] I. Guyon and A. Elissee . “An In oduc ion o Va iable and Fea u e Selec ion”. In: J. Mach. Lea n. Res. 3.null (2003), 1157–1182. issn: 1532-4435 (ci . on p. 62). [99] N. M. Rod igues e al. “SLUG: Fea u e Selec ion Using Gene ic Algo i hms and Gene ic P og amming”. In: Gene ic P og amming. Ed. by E. Med e , G. Pappa, and B. Xue. Cham: Sp inge In e na ional Publishing, 2022, pp. 68–84. isbn: 978-3-031-02056-8 (ci . on p. 62). Thisdocumen wasc ea edwi h he(pd /Xe/Lua)L ATE Xp ocesso and heNOVA hesis empla e( 6.10.12)[0].12cc90221730b8ba41bb3b1 8b517acd [0] J.M.Lou enço.TheNOVA hesisL A T EXTempla eUse ’sManual.NOVAUni e si yLisbon.2021.URL:h ps://gi hub.com/joaomlou enco/no a hesis/ aw/mas e / empla e.pd (ci .onp.72). 72 Be in Sakallioglu A S udy o Geome ic Seman ic Gene ic P og amming wi h Linea Scaling 2023 STATEMENT OF INTEGRITY I he eby decla e ha ing conduc ed his academic wo k wi h in eg i y. I con i m ha I ha e no used plagia ism o any o m o undue use o in o ma ion o alsi ica ion o esul s along he p ocess leading o i s elabo a ion. I u he decla e ha I ha e ully acknowledge he Rules o Conduc and Code o Hono om he NOVA In o ma ion Managemen School. Lisbon, Feb ua y 2023