Գենետիկական ծրագրավորում

Վիքիպեդիայից՝ ազատ հանրագիտարանից
Jump to navigation Jump to search

Արհեստական բանականության մեջ գենետիկական ծրագրավորումը (անգլ.՝ genetic programming) ծրագրերի ավտոմատ ստեղծումը կամ փոփոխումն է՝ գենետիկական ալգորիթմների օգնությամբ։ Այս մեթոդաբանության շնորհիվ ծրագրերը «աճում են», որոնք ավելի և ավելի լավ են (ըստ քրոմոսոմ խնդրի համար հատուկ գործառույթով) լուծում հաշվողական խնդիր:Այն, ըստ էության, հեուրիստական ​​որոնման տեխնիկա է, որը հաճախ նկարագրվում է որպես «բլուր բարձրանալ», այսինքն բոլոր ծրագրերի տարածության մեջ օպտիմալ կամ գոնե հարմար ծրագրի որոնում:

Գործողությունները հետևյալն են.

Քրոսովերի գործողությունը ներառում է ընտրված զույգերի (ծնողների) պատահական մասերի փոխանակում ՝ նոր և տարբեր սերունդներ արտադրելու համար, որոնք ծրագրերի նոր սերնդի մաս են դառնում: Փոփոխությունը ենթադրում է ծրագրի որոշ պատահական մասի փոխարինում ծրագրի որոշ այլ պատահական մասի հետ: - Վերարտադրության համար չընտրված որոշ ծրագրեր ընդօրինակվում են ներկայիս սերնդից նոր սերնդի համար: Այնուհետև ընտրությունը և այլ գործողություններ հետադարձաբար կիրառվում են նոր սերնդի ծրագրերի վրա: Սովորաբար, յուրաքանչյուր նոր սերնդի ծրագրեր միջին հաշվով ավելի հարմար են, քան նախորդ սերնդի ծրագրերը, իսկ սերնդի լավագույն ծրագիրը հաճախ ավելի լավն է, քան նախորդ սերունդների լավագույն ծրագրերը:

Պատմություն[խմբագրել | խմբագրել կոդը]

Ծրագրերը զարգացնելու առաջարկի առաջին գրառումը, հավանաբար, Alan Turing- ի գրառումն էր 1950 թ-ին[1]: Կար մի բացթողում 25 տարի առաջ մինչև Ջոն Հոլլանդի «Ադապտացիան բնական և արհեստական ​​համակարգերում » հրապարակումը նախանշեց գիտության տեսական և էմպիրիկ հիմքերը: 1981 թ.-ին Ռիչարդ Ֆորսիթը ցույց տվեց փոքր ծրագրերի հաջող զարգացումը, որոնք ներկայացված են որպես ծառեր ՝ կատարելու հանցագործությունների տեսարանների ապացույցների դասակարգումը՝ Միացյալ Թագավորության Ներքին գործերի գրասենյակի համար:

Չնայած զարգացող ծրագրերի գաղափարը (սկզբում համակարգչային լեզվով Lisp ) առկա էր Ջոն Հոլլանդի ուսանողների մեջ, դա այդպես չէր մինչ այն ժամանակ, երբ Փիթսբուրգում կազմակերպվեց գենետիկական ալգորիթմների առաջին գիտաժողովը, որի ընթացքում Michael Cramer- ը  հրապարակեց զարգացած ծրագրերի երկու հատուկ մշակված լեզուներ: 1988-ին Կոզան ( Հոլլանդի ասպիրանտ) արտոնագրեց իր գիտնականի գյուտը ծրագրի զարգացման համար: Դրան հաջորդեց «Արհեստական ​​ինտելեկտի միջազգային IJCAI-89» հրապարակումը միջազգային համատեղ համաժողովում [2]:

Կոզան հետևեց դրան «Գենետիկ ծրագրավորում» (GP)-ի 205 հրապարակումներով։ Այնուամենայնիվ, դա Կոզայի 4 գրքերի շարքն է ՝ 1992 թվականից  սկսած ուղեկցող տեսանյութերով,  որոնք իսկապես ստեղծեցին GP- ն: Դրանից հետո տեղի ունեցավ գենետիկական ծրագրավորման մատենագրության հետ հրատարակությունների քանակի ահռելի ընդլայնում ՝ գերազանցելով 10,000 գրառում:  2010 թվականին Կոզան  թվարկեց 77 արդյունք, որտեղ գենետիկական ծրագրավորումը մարդկային մրցակցություն էր[3]:

1996 թ.-ին Կոզան սկսեց գենետիկական ծրագրավորման ամենամյա գիտաժողովը  , որին հաջորդեց 1998-ին ՝ EuroGP ամենամյա կոնֆերանսը,  և առաջին գիրքը  `Koza- ի խմբագրած GP շարքից: 1998 թվականին լույս տեսավ նաև առաջին GP դասագիրքը:

Հիմնարար աշխատանք ԳՊ-ում[խմբագրել | խմբագրել կոդը]

Վաղ աշխատանքները, որոնք հիմք են հանդիսանում ներկայիս գենետիկական ծրագրավորման հետազոտության թեմաների և կիրառությունների համար, բազմազան են և ներառում են ծրագրային ապահովման սինթեզ և նորոգում, կանխատեսման մոդելավորում, տվյալների հանքարդյունաբերություն, [4]  ֆինանսական մոդելավորում, [5] փափուկ տվիչներ,[6] ձևավորում[7] և պատկերի վերամշակում[8]:  Որոշ ոլորտներում կիրառումները, ինչպիսիք են դիզայնը, հաճախ օգտագործում են միջանկյալ ներկայացուցչություններում,  ինչպիսին է Ֆրեդ Գրուուի բջջային կոդավորումը:  Արդյունաբերական կլանումը նշանակալի է մի քանի ոլորտներում, ներառյալ ֆինանսները, քիմիական արդյունաբերությունը, կենսաֆորմատիկան  և պողպատե արդյունաբերությունը[9]:

Մեթոդներ[խմբագրել | խմբագրել կոդը]

Ընտրություն[խմբագրել | խմբագրել կոդը]

Ընտրությունն այն գործընթացն է, որի միջոցով որոշակի ծրագրեր ընտրվում են ներկայիս սերնդից, որոնք որպես սերունդ ծառայելու են հաջորդ սերնդի համար: ծրագիրները ընտրվում են այն հավանականքւթյամբ, որ ավելի լավ իրենց ներկայացնող ծրագրերը ավելի մեծ հավանականություն ունեն ընտրվելու[10]։ GP- ում ամենատարածված ընտրության մեթոդը մրցաշարի ընտրությունն է , չնայած կան այլ մեթոդներ, ինչպիսիք են ֆիթնես համաչափ ընտրությունը , լեքսեքսազի ընտրությունը,[11]  և այլն, որոնք ցույց են տվել, որ ավելի լավ են լուծում GP- ի շատ խնդիրների համար:

Crossover[խմբագրել | խմբագրել կոդը]

Վերոհիշյալ նկարագրության ընտրության փուլում ընտրված անհատների նկատմամբ կիրառվում են տարբեր գենետիկ օպերատորներ` նոր ծրագրեր ստեղծելու համար։ Այս օպերատորների կիրառման որոշումը կատարում է բնակչության բազմազանությունը:

Մուտացիա[խմբագրել | խմբագրել կոդը]

Վերցնենք նախորդ սերունդից մեկ կամ մի քանի բիթեր `նոր ծրագիր կամ սերունդ ստեղծելու համար[12]:

Ծրագրեր[խմբագրել | խմբագրել կոդը]

GP- ն հաջողությամբ օգտագործվել է որպես ավտոմատ ծրագրավորման գործիք, մեքենայական ուսուցման գործիք և ավտոմատ խնդիրների լուծման շարժիչ:GP- ն հատկապես օգտակար է այն տիրույթներում, որտեղ լուծման ճշգրիտ ձևը նախապես հայտնի չէ կամ մոտավոր լուծումը ընդունելի է (հնարավոր է, որ ճշգրիտ լուծում գտնելը շատ դժվար է): GP- ի որոշ դիմումներից են կորի տեղավորումը, տվյալների մոդելավորումը, խորհրդանշական հետընթացը , հնարավորությունների ընտրությունը , դասակարգումը և այլն: Ռ. Կոզան նշում է 76 դեպքերի մասին, երբ գենետիկ ծրագրավորումը կարողացել է ունենալ այնպիսի արդյունքներ, որոնք մրցակցային են մարդու արտադրած արդյունքների հետ (կոչվում է Մարդ -մրցակցային արդյունքներ): 2004 թվականից ի վեր Գենետիկական և էվոլյուցիոն հաշվարկների ամենամյա գիտաժողովը (GECCO) անցկացնում է Human Competitive Awards մրցույթը,  որտեղ դրամական պարգևները տրվում են մարդկային մրցակցային արդյունքներին, որոնք արտադրվում են գենետիկական և էվոլյուցիոն հաշվարկների ցանկացած ձևով: GP- ն տարիների ընթացքում այս մրցույթում շահել է բազմաթիվ մրցանակներ[13][14]:

Մետա-գենետիկական ծրագրավորում[խմբագրել | խմբագրել կոդը]

Մետա-գենետիկական ծրագրավորումն ինքնին գենետիկ ծրագրավորման համակարգի զարգացման մետա-ուսուցման մեթոդն է: Այն ենթադրում է, որ քրոմոսոմները, խաչաձևությունը և մուտացիան ինքնին զարգացել են, հետևաբար, ինչպես իրենց իրական կյանքի գործընկերները պետք է թույլատրվեն փոխվել ինքնուրույն, այլ ոչ թե որոշվել ծրագրավորողի կողմից[15]:

Այս գաղափարի քննադատողները հաճախ ասում են, որ այս մոտեցումը չափազանց լայն է: Այնուամենայնիվ, հնարավոր է սահմանափակել ֆիթնեսի չափանիշը արդյունքների ընդհանուր դասի վրա և, այդպիսով, ձեռք բերել զարգացած բժիշկ, որն առավել արդյունավետ արդյունք կտա ենթա դասերի համար: Սա կարող է լինել մետա-զարգացած GP- ի ձև `մարդկային քայլելու ալգորիթմների ձևավորման համար, որն այնուհետև կօգտագործվի մարդու վազքի, թռչկոտելու և այլ բաներ զարգացնելու համար[16][17][18]:

Գրականություն[խմբագրել | խմբագրել կոդը]

Արդյունաբերությունը Գենետիկ Ալգորիթմներում

Գենետիկ ծրագրավորման թեորեմը և կիրառությունը

Գենետիկական ծրագրավորում և տվյալների կառուցվածքներ

Գենետիկական ծրագրավորման դաշտային ուղեցույց

Գենետիկական Ծրագրավորում

Ծանոթագրություններ[խմբագրել | խմբագրել կոդը]

  1. «COMPUTING MACHINERY AND INTELLIGENCE»։ cogprints.org։ Վերցված է 2019-10-20 
  2. Koza John R. (1989)։ «Hierarchical Genetic Algorithms Operating on Populations of Computer Programs»։ Proceedings of the 11th International Joint Conference on Artificial Intelligence - Volume 1։ IJCAI'89 (San Francisco, CA, USA: Morgan Kaufmann Publishers Inc.): 768–774 
  3. Press The MIT։ «Genetic Programming»։ The MIT Press (անգլերեն)։ Վերցված է 2019-10-20 
  4. Freitas Alex A. (2002)։ Data Mining and Knowledge Discovery with Evolutionary Algorithms։ Natural Computing Series (անգլերեն)։ Berlin Heidelberg: Springer-Verlag։ ISBN 9783540433316 
  5. Tsang Edward P. K., Li Jin, Butler James M. (1998)։ «EDDIE beats the bookies»։ Software: Practice and Experience (անգլերեն) 28 (10): 1033–1043։ ISSN 1097-024X։ doi:10.1002/(SICI)1097-024X(199808)28:103.0.CO;2-1 
  6. Kordon Arthur (2010)։ Applying Computational Intelligence: How to Create Value (անգլերեն)։ Berlin Heidelberg: Springer-Verlag։ ISBN 9783540699101 
  7. «dblp: computer science bibliography»։ dblp.uni-trier.de։ Վերցված է 2019-10-20 
  8. «Discovery of Human-Competitive Image Texture Feature Extraction Programs Using Genetic Programming»։ gpbib.cs.ucl.ac.uk (անգլերեն)։ Վերցված է 2019-10-20 
  9. «Genetic Programming and Jominy Test Modeling»։ gpbib.cs.ucl.ac.uk (անգլերեն)։ Վերցված է 2019-10-20 
  10. Programming A. Field Guide to Genetic։ «A Field Guide to Genetic Programming»։ Վերցված է 2019-10-20 
  11. Spector Lee (2012)։ «Assessment of Problem Modality by Differential Performance of Lexicase Selection in Genetic Programming: A Preliminary Report»։ Proceedings of the 14th Annual Conference Companion on Genetic and Evolutionary Computation։ GECCO '12 (New York, NY, USA: ACM): 401–408։ ISBN 9781450311786։ doi:10.1145/2330784.2330846 
  12. Cartesian genetic programming։ Miller, Julian (Julian F.)։ New York: Springer։ 2011։ ISBN 9783642173103։ OCLC 763154890 
  13. «Human-Competitive Awards 2004 – Present | Human Competitive»։ www.human-competitive.org։ Վերցված է 2019-10-20 
  14. «Semantic Scholar - An academic search engine for scientific articles»։ www.semanticscholar.org (անգլերեն)։ Վերցված է 2019-10-20 
  15. Jr Kenneth L. Kinnear, Kinnear Kenneth E., Angeline Peter J. (1994)։ Advances in Genetic Programming (անգլերեն)։ MIT Press։ ISBN 9780262111881 
  16. Spector Lee, Robinson Alan (2002-03-01)։ «Genetic Programming and Autoconstructive Evolution with the Push Programming Language»։ Genetic Programming and Evolvable Machines (անգլերեն) 3 (1): 7–40։ ISSN 1573-7632։ doi:10.1023/A:1014538503543 
  17. Kinnear Kenneth E., Langdon William B., Spector Lee, Angeline Peter J., O'Reilly Una-May (1994)։ Advances in Genetic Programming (անգլերեն)։ MIT Press։ ISBN 9780262194235 
  18. «The Genetic Programming Bibliography»։ gpbib.cs.ucl.ac.uk։ Վերցված է 2019-10-20 

Արտաքին հղումներ[խմբագրել | խմբագրել կոդը]