Մասնակից:Ero Hovasyan

Գենետիկական Ալգորիթմ

Գենետիկական Ալգորիթմ- (ENG.genetic algorithm)--դա էվրիստիկ որոնման ալգորիթմ է, որն օգտագործվում է օպտիմալացման և մոդելավորման խնդիրները լուծելու համար՝ պատահական ընտրությամբ, ցանկալի պարամետրերի համակցմամբ և փոփոխությամբ՝ օգտագործելով բնական ընտրությանը նման մեխանիզմներ: Այն էվոլյուցիոն հաշվարկների մի տեսակ է, որը լուծում է օպտիմալացման խնդիրները՝ օգտագործելով բնական էվոլյուցիայի մեթոդները, ինչպիսիք են ժառանգությունը, մուտացիան, ընտրությունը և հատումը: Գենետիկական ալգորիթմի տարբերակիչ առանձնահատկությունն այն է, որ շեշտը դրվում է «խաչման» օպերատորի օգտագործման վրա, որն իրականացնում է թեկնածու լուծումների վերահամակցման գործողությունը, որի դերը նման է վայրի բնության մեջ անցման դերին:

Պատմություն

Էվոլյուցիայի մոդելավորման առաջին աշխատանքը կատարվել է 1954 թվականին Նիլս Բարիչելլիի կողմից՝ Փրինսթոնի համալսարանի առաջադեմ ուսումնասիրությունների ինստիտուտում տեղադրված համակարգչի վրա ։ Նրա աշխատանքը, որը հրատարակվել է նույն թվականին, գրավել է հանրության լայն ուշադրությունը։ 1957 թվականից ի վեր ավստրալացի գենետիկ Ալեքս Ֆրեյզերը հրապարակել է մի շարք հոդվածներ, որոնք վերաբերում են օրգանիզմների արհեստական ընտրության մոդելավորմանը, որոնք ունեն չափելի բնութագրերի բազմաթիվ վերահսկում: Այս սկիզբը թույլ տվեց էվոլյուցիոն գործընթացների և մեթոդների համակարգչային մոդելավորումը, որոնք նկարագրված են Ֆրեյզերի և Բարնելի (1970) և Քրոսբիի (1973) գրքերում, սկսած 1960-ականներից, դառնալ ավելի տարածված կենսաբանների շրջանում:Ֆրեյզերի սիմուլյացիան ներառում էր ժամանակակից գենետիկական ալգորիթմների բոլոր էական տարրերը։ Ի հավելումն դրան, Հանս-Յոահիմ Բրեմերմանը 1960-ականներին հրատարակեց մի շարք հոդվածներ, որոնք նույնպես որդեգրեցին օպտիմալացման խնդիրներում վերահամակցման, մուտացիայի և ընտրության ենթարկվող լուծումների պոպուլյացիայի օգտագործման մոտեցումը: Բրեմերմանի հետազոտությունը ներառում էր նաև ժամանակակից գենետիկական ալգորիթմների տարրեր։ Մյուս ռահվիրաներից են Ռիչարդ Ֆրիդբերգը, Ջորջ Ֆրիդմանը և Մայքլ Կոնրադը։ Շատ վաղ գործեր վերահրատարակվել են Դեյվիդ Բ. Ֆոգելի կողմից (1998)

Թեև Բարիչելլին իր 1963 թվականի աշխատանքում մոդելավորել է պարզ խաղ խաղալու մեքենայի կարողությունը, սակայն արհեստական էվոլյուցիան դարձավ հաստատված օպտիմալացման տեխնիկա 1960-ականներին և 1970-ականների սկզբին Ինգո Ռեխենբերգի և Հանս-Պոլ Շվեֆելի աշխատանքից հետո. ունակ է լուծել բարդ ինժեներական խնդիրներ՝ ըստ էվոլյուցիոն ռազմավարությունների ։ Մյուս մոտեցումը Լոուրենս Ջ. Ֆոգելի էվոլյուցիոն ծրագրավորման տեխնիկան էր, որն առաջարկվել էր արհեստական ինտելեկտ ստեղծելու համար։ Էվոլյուցիոն ծրագրավորումն ի սկզբանե օգտագործել է վերջավոր վիճակի մեքենաներ՝ հանգամանքները կանխատեսելու համար, իսկ բազմազանությունն ու ընտրությունը՝ կանխատեսող տրամաբանությունը օպտիմալացնելու համար։Գենետիկական ալգորիթմները հատկապես հայտնի դարձան Ջոն Հոլանդի աշխատանքի շնորհիվ 70-ականների սկզբին և նրա «Ադապտացիան բնական և արհեստական համակարգերում» (1975) գրքի շնորհիվ։ Նրա հետազոտությունը հիմնված էր Հոլանդի կողմից իրականացված բջջային ավտոմատների հետ փորձերի և Միչիգանի համալսարանում գրված նրա գրվածքների վրա: Հոլանդը ներկայացրեց հաջորդ սերնդի որակի կանխատեսման պաշտոնական մոտեցում, որը հայտնի է որպես սխեմայի թեորեմ: Գենետիկական ալգորիթմների վերաբերյալ հետազոտությունները հիմնականում տեսական մնացին մինչև 1980-ականների կեսերը, երբ վերջապես տեղի ունեցավ Գենետիկական ալգորիթմների վերաբերյալ առաջին միջազգային համաժողովը Փենսիլվանիա նահանգի Պիտսբուրգ քաղաքում (ԱՄՆ):

Զգալիորեն աճել է նաև աշխատասեղանի համակարգիչների հաշվողական հզորությունը, ինչը հնարավորություն է տվել գործնականում կիրառել նոր հաշվողական տեխնոլոգիա: 1980-ականների վերջին General Electric-ը սկսեց վաճառել աշխարհում առաջին արտադրանքը՝ օգտագործելով գենետիկական ալգորիթմ: Դա արդյունաբերական հաշվողական գործիքների հավաքածու էր։ 1989 թվականին մեկ այլ ընկերություն Axcelis, Inc. թողարկեց Evolver-ը՝ աշխարհում առաջին կոմերցիոն գենետիկ ալգորիթմի արտադրանքը սեղանադիր համակարգիչների համար: The New York Times-ի տեխնոլոգիական լրագրող Ջոն Մարքոֆը գրել է Evolver-ի մասին 1990 թվականին։

Ալգորիթմի նկարագրություն

Խնդիրը ձևակերպված է այնպես, որ դրա լուծումը կարող է կոդավորվել գեների վեկտորի («գենոտիպի») տեսքով, որտեղ յուրաքանչյուր գեն կարող է լինել մի բիթ, թիվ կամ որևէ այլ առարկա։ Գենետիկական ալգորիթմի (GA) դասական իրականացումներում ենթադրվում է, որ գենոտիպն ունի ֆիքսված երկարություն։ Այնուամենայնիվ, կան GA-ի տարբերակներ, որոնք զերծ են այս սահմանափակումից:

Ոմանք, սովորաբար պատահականորեն, ստեղծում են սկզբնական պոպուլյացիայի բազմաթիվ գենոտիպեր: Դրանք գնահատվում են օգտագործելով «fitness ֆունկցիան», որի արդյունքում յուրաքանչյուր գենոտիպի հետ կապված է որոշակի արժեք («fitness»), որը որոշում է, թե որքանով է իր կողմից նկարագրված ֆենոտիպը լուծում առաջադրանքը։

«Ֆիթնես ֆունկցիա» (կամ ֆիթնես ֆունկցիա անգլերեն լեզվի գրականության մեջ) ընտրելիս կարևոր է ապահովել, որ դրա «թեթևացումը» լինի «հարթ»:

Ստացված լուծումների շարքից («սերունդներ»), հաշվի առնելով «պիտանիության» արժեքը, ընտրվում են որոշումներ (սովորաբար լավագույն անհատները ընտրվելու մեծ հավանականություն ունեն), որոնց նկատմամբ կիրառվում են «գենետիկական օպերատորներ» (մեծ մասում. դեպքերում, «խաչելը» խաչմերուկ է, իսկ «մուտացիան»՝ ), ինչը հանգեցնում է նոր լուծումների ստացմանը: Նրանց համար հաշվարկվում է նաև ֆիթնես արժեքը, իսկ հետո կատարվում է հաջորդ սերնդի լավագույն լուծումների ընտրությունը։

Գործողությունների այս շարքը կրկնվում է կրկնվող, այսպես է մոդելավորվում «էվոլյուցիոն գործընթացը», որը շարունակվում է մի քանի կյանքի ցիկլեր (սերունդներ) մինչև ալգորիթմի դադարեցման չափանիշը բավարարվի։ Այս չափանիշը կարող է լինել:

●գտնել գլոբալ կամ ոչ օպտիմալ լուծում.

●էվոլյուցիայի համար առանձնացված սերունդների քանակի սպառում.

●էվոլյուցիայի համար հատկացված ժամանակի սպառում.

Գենետիկական ալգորիթմները հիմնականում օգտագործվում են բազմաչափ որոնման տարածքներում լուծումներ գտնելու համար:

Այսպիսով, կարելի է առանձնացնել գենետիկական ալգորիթմի հետևյալ փուլերը.

1.Սահմանեք թիրախային գործառույթը (պիտանիությունը) բնակչության անհատների համար

2.Ստեղծեք սկզբնական բնակչություն

●(Ցիկլի սկիզբ)

1.Վերարտադրում (խաչում)

2.Մուտացիա

3.Հաշվեք օբյեկտիվ ֆունկցիայի արժեքը բոլոր անհատների համար

4.Նոր սերնդի ձևավորում (ընտրություն)

5.Եթե կանգառի պայմանները բավարարված են, ապա (ցիկլի ավարտ), հակառակ դեպքում (ցիկլի սկիզբ)

Նախնական բնակչության ստեղծում

Նախքան առաջին քայլը, դուք պետք է պատահականորեն ստեղծեք նախնական բնակչություն. նույնիսկ եթե պարզվի, որ այն լիովին անմրցունակ է, հավանական է, որ գենետիկական ալգորիթմը դեռ արագ կփոխանցի այն կենսունակ բնակչության մեջ: Այսպիսով, առաջին քայլում չի կարելի հատկապես փորձել անհատներին չափից դուրս պիտանի դարձնել, բավական է, որ նրանք համապատասխանեն բնակչության անհատների ձևաչափին, և նրանց վրա կարելի է հաշվարկել ֆիթնեսի ֆունկցիան։ Առաջին քայլի արդյունքը H պոպուլյացիան է՝ բաղկացած N անհատներից։

Ծնողների ընտրություն

Գենետիկական ալգորիթմներում վերարտադրումը պահանջում է մի քանի ծնող, սովորաբար երկու, սերունդ առաջացնելու համար:

Ծնողների ընտրության մի քանի օպերատորներ կան

1.Պանմիքսիա - երկու ծնողներն էլ ընտրվում են պատահականության սկզբունքով, բնակչության յուրաքանչյուր անհատ ընտրվելու հավասար հնարավորություն ունի

2.Ինբրեդինգ - առաջին ծնողը ընտրվում է պատահականության սկզբունքով, իսկ երկրորդը ընտրվում է այն մեկը, որն առավել շատ նման է առաջին ծնողին

3.Բազմացում - առաջին ծնողը ընտրվում է պատահականության սկզբունքով, իսկ երկրորդը ընտրվում է նա, որն ամենաքիչ նման է առաջին ծնողին

Ինբրեդինգը և բուծումը լինում են երկու ձևով՝ ֆենոտիպային և գենոտիպային: Ֆենոտիպային ձևի դեպքում նմանությունը չափվում է կախված ֆիթնես ֆունկցիայի արժեքից (որքան մոտ են օբյեկտիվ ֆունկցիայի արժեքները, այնքան ավելի նման են անհատները), իսկ գենոտիպային ձևի դեպքում՝ նմանությունը չափվում է կախված գենոտիպի ներկայացումից (որքան քիչ են տարբերությունները անհատների գենոտիպերի միջև, անհատները նման են):

Բազմացում (խաչաձև)

Տարբեր ալգորիթմներում վերարտադրումը տարբեր կերպ է սահմանվում. դա, իհարկե, կախված է տվյալների ներկայացումից: Բազմացման հիմնական պահանջն այն է, որ սերունդը կամ հետնորդները հնարավորություն ունենան ժառանգելու երկու ծնողների գծերը՝ դրանք ինչ-որ կերպ «խառնելով»։

Ինչու՞ են վերարտադրման համար անհատները սովորաբար ընտրվում H ամբողջ պոպուլյացիայից, այլ ոչ թե H' տարրերից, որոնք գոյատևել են առաջին քայլին (չնայած վերջին տարբերակը նույնպես իրավունք ունի գոյություն ունենալ )? Փաստն այն է, որ շատ գենետիկական ալգորիթմների հիմնական թերությունը անհատների բազմազանության բացակայությունն է: Արագորեն հայտնաբերվում է մեկ գենոտիպ, որը տեղական առավելագույնն է, և այնուհետև պոպուլյացիայի բոլոր տարրերը կորցնում են իրենց ընտրությունը, և ամբողջ բնակչությունը «խցանվում» է այս անհատի պատճեններով: Այս անցանկալի ազդեցության դեմ պայքարելու տարբեր եղանակներ կան. դրանցից մեկը ոչ թե առավել հարմարվող, այլ ընդհանրապես բոլոր անհատների վերարտադրության ընտրությունն է:Այնուամենայնիվ, այս մոտեցումը ստիպում է պահպանել բոլոր նախկինում գոյություն ունեցող անհատները, ինչը մեծացնում է խնդրի հաշվողական բարդությունը: Ուստի, խաչմերուկի համար անհատների ընտրության մեթոդները հաճախ օգտագործվում են այնպես, որ «բազմապատկվեն» ոչ միայն առավել հարմարվողները, այլև վատ մարզավիճակ ունեցող անհատները։ Այս մոտեցմամբ մուտացիաների դերը մեծանում է գենոտիպի բազմազանության համար։

Գենետիկական ալգորիթմների կիրառում

Գենետիկական ալգորիթմներն օգտագործվում են հետևյալ խնդիրները լուծելու համար.

1.Գործառույթների օպտիմիզացում

2.Տվյալների բազայի հարցումների օպտիմիզացում

3.Տարբեր գրաֆիկական խնդիրներ (շրջիկ վաճառողի խնդիր, գունավորում, համընկնում գտնել)

4.Արհեստական նեյրոնային ցանցի ստեղծում և ուսուցում

5.Դասավորության առաջադրանքներ

6.Ժամանակացույց

7.Խաղի ռազմավարություններ

8.Մոտավորության տեսություն

9.Արհեստական կյանք

10.Կենսաինֆորմատիկա (սպիտակուցների ծալում)

11.Վերջավոր ավտոմատների սինթեզ

12.PID Կարգավորիչների թյունինգ

Մշակույթում

В фильме 1995 года «Виртуозность» мозг главного злодея выращен генетическим алгоритмом с использованием воспоминаний и поведенческих черт преступников.

Գրքեր

Саймон Д. Алгоритмы эволюционной оптимизации..

S.N. SivanandamS.N. Deepa Introduction to Genetic Algorithms.

Гладков Л. А., Курейчик В. В, Курейчик В. М Биоинспирированные методы в оптимизации: монография.

Lance D. Chambers The Practical Handbook of Genetic Algorithms.

Скобцов Ю. А. Основы эволюционных вычислений.

Արտաքին հղումներ

Introduction to Optimization with Genetic Algorithm.

The Basics of Genetic Algorithms in Machine Learning.

Генетические алгоритмы — математический аппарат.

Что такое генетические алгоритмы.

Introduction to Genetic Algorithm & their application in data science.