Genetik algoritm tabiiy tanlanish jarayonlari (mutatsiya, kesishish, tanlash) asosida

Genetik algoritm tabiiy tanlanish jarayonlari (mutatsiya, kesishish, tanlash) asosida optimallashtirish muammolarini hal qilish usuli bo'lib , sun'iy intellektning kengroq sohasi - evolyutsion hisoblashning bir qismidir .
Genetik algoritmda optimallashtirish muammosining har bir mumkin bo'lgan yechimi individual deb ataladi. Individuallar populyatsiyani tashkil qiladi. Vazifa evolyutsiya jarayonida shaxslarning har bir yangi avlodi (ya'ni, optimallashtirish muammosining echimlari) yanada mukammal bo'lishini ta'minlashdir.
Har bir shaxs o'zgarishi mumkin bo'lgan xususiyatlar to'plamiga (xromosomalar) ega. An'anaga ko'ra, echimlar ikkilik shaklda (0 va 1 qatorlar sifatida) taqdim etiladi, ammo boshqa kodlashlar ham mumkin.
Evolyutsiya tasodifiy yaratilgan shaxslar populyatsiyasidan boshlanadi va iterativ jarayon bo'lib, har bir iteratsiyada populyatsiya avlod deb ataladi. Har bir avlodda populyatsiyadagi har bir individning yaroqliligi baholanadi.
Fitness - hal qilinayotgan optimallashtirish masalasidagi maqsad funksiyasining qiymati . Joriy populyatsiyadan ko'proq "mos" shaxslar tanlanadi, ularning xromosomalari yangi avlodni shakllantirish uchun o'zgartiriladi (tasodifiy mutatsiyaga uchraydi), keyinchalik algoritmning keyingi iteratsiyasida foydalaniladi. Odatda, algoritm oldindan belgilangan takrorlash soniga erishilganda yoki populyatsiya qoniqarli "fitness" darajasiga yetganda tugaydi.
Algoritmni boshlashdan oldin fitnes funksiyasini (fitness funktsiyasi) aniqlash va mumkin bo'lgan echimlarni (individuallarni) ikkilik massivlar shaklida ko'rsatish kerak. Keyin algoritm quyidagilarni bajaradi:

• 
  Initializatsiya - boshlang'ich populyatsiyaning tasodifiy shakllanishi, individlar soni bir necha yuzdan bir necha minggacha.
  
• 
  Tanlash (tanlash) - har bir iteratsiyada keyingi avlodni shakllantirish uchun joriy populyatsiyaning bir qismi tanlanadi. Fitnes funktsiyasining qiymati etarlicha yuqori bo'lgan shaxslar tanlanadi.
  
• 
  Genetik operatorlarni qo'llash - Krossover va mutatsiya operatorlari oldingi bosqichda tanlangan shaxslarga qo'llaniladi. Har bir yangi shaxsni shakllantirish uchun ikkita ota-ona tanlanadi, ular ota-onasining xususiyatlarini meros qilib olgan yangi shaxsni yaratadi. Ikki ota-onadan foydalanishga asoslangan ko'payish usullari usulning biologik asosiga ko'proq mos keladigan bo'lsa-da, tadqiqotlar shuni ko'rsatdiki, uch yoki undan ortiq ota-onadan foydalanish yuqori sifatli nasl beradi. Natijada aholining o'rtacha jismoniy tayyorgarlik darajasi oshadi.
  
• 
  Tugatish - algoritm tugatish shartlaridan biri bajarilmaguncha ishlashni davom ettiradi:
  
  • 
    fitnes funksiyasining ma'lum minimumini qanoatlantiradigan yechim topiladi;
    
  • 
    belgilangan takrorlash soniga erishildi;
    
  • 
    yangi shaxslar uchun fitnes funksiyasining qiymati o'sishni to'xtatdi.
    

Genetik algoritmlarning kamchiliklari:

• 
  ölçeklenebilirlik yo'qligi ;
  
• 
  usulning evristik tabiati;
  
• 
  algoritmni mahalliy minimumga yaqinlashtirish imkoniyati .
  

Genetik algoritmlar 1960 yilda Jon Gollandiya tomonidan taklif qilingan.
Genetik algoritmlar va ulardan foydalanish tamoyillari haqida ko'proq maqolada o'qing "Genetik algoritmlar - matematik apparatlar" .

Genetik algoritm - tabiatda tabiiy tanlanishga o'xshash mexanizmlar yordamida kerakli parametrlarni tasodifiy tanlash, kombinatsiyalash va o'zgartirish yo'li bilan optimallashtirish va modellashtirish masalalarini hal qilish uchun ishlatiladigan evristik qidiruv algoritmi . Bu meros , mutatsiya , tanlash va kesishish kabi tabiiy evolyutsiya usullaridan foydalangan holda optimallashtirish muammolarini hal qiladigan evolyutsion hisoblashning bir turi .. Genetik algoritmning o'ziga xos xususiyati, roli yovvoyi tabiatdagi o'tish roliga o'xshash nomzod echimlarni rekombinatsiya qilish operatsiyasini amalga oshiradigan "o'tish" operatoridan foydalanishga urg'u berishdir.

Evolyutsiyani simulyatsiya qilish bo'yicha birinchi ish 1954 yilda Niels Baricelli tomonidan Prinston universiteti qoshidagi Ilg'or tadqiqotlar institutida o'rnatilgan kompyuterda [1] [2] amalga oshirildi, o'sha yili nashr etilgan ish keng e'tiborni tortdi. 1957 yildan beri [3] avstraliyalik genetik Aleks Freyzer o'lchanadigan xususiyatlar uchun bir nechta nazoratga ega organizmlar o'rtasida sun'iy tanlanishni simulyatsiya qilish bo'yicha bir qator maqolalarni nashr etdi . Qo'yilgan poydevor Freyzer va Barnel (1970) [4] va Krosbi (1973) [5] kitoblarida tasvirlangan usullarga muvofiq evolyutsion jarayonlarning simulyatsiya modellarini amalga oshirishga imkon berdi.. Freyzerning simulyatsiya modellari zamonaviy genetik algoritmlarning barcha muhim elementlarini o'z ichiga olgan. Bunga qo'shimcha ravishda, Hans-Yoaxim Bremermann 1960-yillarda bir qator maqolalarni nashr etdi, ular rekombinatsiya, mutatsiya va tanlovga duchor bo'lgan qarorlar populyatsiyasini optimallashtirish muammolarida qo'llash yondashuvini ham oldi. Bremermanning tadqiqotlari zamonaviy genetik algoritmlar elementlarini ham o'z ichiga olgan [6] . Boshqa dastlabki tadqiqotchilar orasida Richard Fridberg, Jorj Fridman va Maykl Konrad bor. Ko'pgina dastlabki asarlar David Vogel (1998) tomonidan qayta nashr etilgan [7] .

Garchi Baricelli 1963 yilda mashinaning oddiy o'yin o'ynash qobiliyatiga taqlid qilgan bo'lsa-da, [ 8] sun'iy evolyutsiya XX asrning 1960-yillari va 1970-yillari boshlarida Ingo Rechenberg va Hans-Pol Shvefelning ishlaridan so'ng qabul qilingan optimallashtirish usuliga aylandi - Rechenberg guruhi Evolyutsiya strategiyalariga ko'ra murakkab muhandislik muammolarini hal qila oldi . [9] [10] [11] [12] Yana bir yondashuv sun'iy intellekt yaratish uchun taklif qilingan Lorens J. Vogelning evolyutsion dasturlash texnikasi edi. Evolyutsion dasturlash dastlab davlat mashinalaridan foydalanganvaziyatlarni va xilma-xillikni bashorat qilish va bashorat qilish mantiqini optimallashtirish uchun tanlash. Genetik algoritmlar, ayniqsa , Jon Gollandiyaning 70-yillar boshidagi ishi va uning "Tabiiy va sun'iy tizimlarga moslashish" (1975) kitobi tufayli mashhur bo'ldi [13] . Vogelning tadqiqoti Gollandiyaning uyali avtomatlar bilan o'tkazgan tajribalari va uning (Gollandiya) Michigan universitetida yozgan asarlariga asoslangan edi . Gollandiya keyingi avlod sifatini bashorat qilish uchun sxema teoremasi deb nomlanuvchi rasmiylashtirilgan yondashuvni joriy qildi .. Genetik algoritmlar bo'yicha tadqiqotlar 1980-yillarning o'rtalariga qadar, ya'ni Pitsburgda (AQSh) Genetik algoritmlar bo'yicha Birinchi Xalqaro konferentsiya bo'lib o'tgunga qadar asosan nazariy bo'lib qoldi .

Tadqiqotga bo'lgan qiziqishning o'sishi bilan stol kompyuterlarining hisoblash quvvati ham sezilarli darajada oshdi, bu esa yangi kompyuter texnologiyalarini amalda qo'llash imkonini berdi. 80-yillarning oxirida General Electric dunyodagi birinchi genetik algoritm mahsulotini sotishni boshladi. Ular sanoat hisoblash asboblari to'plamiga aylandi. 1989 yilda yana bir kompaniya Axcelis, Inc. ish stoli kompyuterlari uchun dunyodagi birinchi tijorat genetik algoritm mahsuloti Evolverni chiqardi . New York Times texnologiya jurnalisti Jon Markoff 1990 yilda Evolver haqida [14] yozgan .
Algoritm tavsifi [ tahrir | kodni tahrirlash ]

Genetik algoritm sxemasi
Muammo shunday rasmiylashtirilganki, uning yechimi genlarning vektori (" genotip ") sifatida kodlanishi mumkin, bunda har bir gen bit , raqam yoki boshqa ob'ekt bo'lishi mumkin. Genetik algoritmning (GA) klassik tatbiqlarida genotipning belgilangan uzunligi bor deb taxmin qilinadi. Biroq, ushbu cheklovdan ozod bo'lgan GA o'zgarishlari mavjud.
Ba'zi, odatda tasodifiy, boshlang'ich populyatsiyaning ko'plab genotiplari yaratiladi. Ular " fitness funktsiyasi " yordamida baholanadi , bunda ma'lum bir qiymat ("fitness") har bir genotip bilan bog'liq bo'lib, u tomonidan tasvirlangan fenotip muammoni qanchalik yaxshi hal qilishini aniqlaydi.
"Fitness funktsiyasi " ni (yoki ingliz adabiyotida fitnes funksiyasini) tanlayotganda , uning "relefi" "silliq" bo'lishini ta'minlash kerak.
Olingan yechimlar to'plamidan ("avlodlar") "fitness" qiymatini hisobga olgan holda, echimlar tanlanadi (odatda eng yaxshi shaxslarni tanlash ehtimoli yuqori), ularga "genetik operatorlar" qo'llaniladi (ko'p hollarda). holatlar, “ krossover ” - krossover va “ mutatsiya ” - mutatsiya), natijada yangi yechimlar paydo bo'ladi. Ular uchun fitnes qiymati ham hisoblab chiqiladi, so'ngra keyingi avlod uchun eng yaxshi echimlarni tanlash ("tanlash") amalga oshiriladi.
Ushbu harakatlar to'plami iterativ ravishda takrorlanadi, shuning uchun algoritmni to'xtatish mezoniga erishilgunga qadar bir necha hayot tsikllari ( avlodlar ) davom etadigan "evolyutsiya jarayoni" modellashtiriladi. Bu mezon bo'lishi mumkin:

• 
  global yoki suboptimal yechim topish;
  
• 
  evolyutsiya uchun chiqarilgan avlodlar sonining tugashi;
  
• 
  evolyutsiya uchun ajratilgan vaqtning tugashi.
  

Genetik algoritmlar asosan ko'p o'lchovli qidiruv maydonlarida echimlarni izlash uchun xizmat qiladi.
Shunday qilib, genetik algoritmning quyidagi bosqichlarini ajratish mumkin:

1. 
   Aholining alohida shaxslari uchun maqsadli funktsiyani (fitness) belgilang
   
2. 
   Dastlabki aholini yarating
   

• 
  (Tsiklning boshlanishi)
  

1. 
   Ko'paytirish (kesish)
   
2. 
   Mutatsiya
   
3. 
   Barcha shaxslar uchun maqsad funktsiyasi qiymatini hisoblang
   
4. 
   Yangi avlodni shakllantirish (seleksiya)
   
5. 
   Agar to'xtash shartlari bajarilgan bo'lsa, u holda (loopning oxiri), aks holda (loopning boshlanishi).