Amaliy matematika” yo‘nalishi 21. 08-guruh talabasi Mamasodiqova Mubina Sattorali qizining

Genetik algoritmning qo'llaniladigan masalalar.

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 masalalarini 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 Nils Baricelli tomonidan Prinston universitetida malaka oshirish institutida o'rnatilgan kompyuterda amalga oshirilgan.[1][2]. Uning o'sha yili nashr etilgan asari keng jamoatchilik e'tiborini tortdi. 1957 yildan beri [3] avstraliyalik genetik Aleks Freyzer o'lchanadigan xususiyatlar uchun bir nechta nazoratga ega organizmlar o'rtasida sun'iy tanlanishni simulyatsiya qiluvchi bir qator maqolalarni nashr etdi. Ushbu yangilik evolyutsion jarayonlarni kompyuter simulyatsiyasi va Freyzer va Barnel (1970) [4] va Krosbi (1973) [5] kitoblarida tasvirlangan usullarni 1960-yillardan biologlar orasida keng tarqalgan faoliyatga aylantirish imkonini berdi. Freyzerning simulyatsiyalari 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 kashshoflar orasida Richard Fridberg, Jorj Fridman va Maykl Konrad bor. Ko'pgina dastlabki asarlar David B. Vogel tomonidan qayta nashr etilgan (1998).[7]
Garchi Baricelli o'zining 1963 yilgi maqolasida mashinaning oddiy o'yin o'ynash qobiliyatini simulyatsiya qilgan bo'lsa-da,[8] sun'iy evolyutsiya 1960-yillarda va 1970-yillarning boshlarida Ingo Rechenberg va Xans-Pol Shvefel ishlaridan so'ng qabul qilingan optimallashtirish usuliga aylandi. asr - 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 Lourens J. Vogelning evolyutsion dasturlash texnikasi. Evolyutsion dasturlash dastlab vaziyatlarni bashorat qilish uchun chekli avtomatlardan foydalangan va bashorat qilish mantiqini optimallashtirish uchun xilma-xillik va tanlovdan foydalangan. Genetik algoritmlar, ayniqsa, Jon Gollandiyaning 70-yillar boshidagi ishi va uning "Tabiiy va sun'iy tizimlarga moslashish" kitobi (1975) tufayli mashhur bo'ldi [13]. Uning tadqiqoti Gollandiyaning uyali avtomatlar bilan o'tkazgan tajribalari va Michigan universitetidagi yozuvlariga 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 ortishi 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. Nyu-York Tayms texnologiya jurnalisti Jon Markoff 1990 yilda Evolver haqida yozgan [14].

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 genotip qat'iy belgilangan uzunlikka ega deb taxmin qilinadi. Biroq, GA ning ushbu cheklovdan ozod bo'lgan o'zgarishlari mavjud.
Ba'zi, odatda tasodifiy, boshlang'ich populyatsiyaning ko'plab genotiplari yaratiladi. Ular "fitness funktsiyasi" yordamida baholanadi, bunda har bir genotip o'ziga xos qiymat ("fitness") bilan bog'liq bo'lib, u tasvirlagan fenotip vazifani qanchalik yaxshi bajarishini belgilaydi.
"Fitness funktsiyasi" (yoki ingliz adabiyotida fitnes funksiyasi) ni 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 echimlar paydo bo'ladi. Ular uchun fitnes qiymati ham hisoblab chiqiladi, so'ngra keyingi avlod uchun eng yaxshi echimlarni tanlash ("tanlash") amalga oshiriladi.
Bu harakatlar majmui iterativ tarzda takrorlanadi, shu tarzda algoritmning to'xtash mezoni bajarilgunga qadar bir necha hayot davrlari (avlodlar) davom etadigan "evolyutsion jarayon" modellashtiriladi. Bu mezon bo'lishi mumkin:
• global yoki suboptimal yechim topish;
• evolyutsiya uchun chiqarilgan avlodlar sonining tugashi;
• evolyutsiyaga 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 populyatsiyani yarating
• (Tsiklni boshlash)
1. Ko'paytirish (kesish)
2. Mutatsiya
3. Maqsad funksiyasining barcha individlar uchun qiymatini hisoblang
4. Yangi avlodning shakllanishi (seleksiya)
5. Agar to'xtash shartlari bajarilsa, u holda (tsiklning oxiri), aks holda (tsiklning boshlanishi).
Dastlabki populyatsiyani yaratish
Birinchi qadamdan oldin siz tasodifiy boshlang'ich populyatsiyani yaratishingiz kerak; u butunlay raqobatbardosh bo'lib chiqsa ham, genetik algoritm baribir uni tezda hayotiy populyatsiyaga o'tkazishi mumkin. Shunday qilib, birinchi bosqichda, ayniqsa, odamlarni juda mos qilishga urinib bo'lmaydi, ular populyatsiyadagi individlar formatiga mos kelishi kifoya va fitnes funktsiyasini ular bo'yicha hisoblash mumkin. Birinchi bosqichning natijasi N populyatsiyadan iborat H populyatsiyasidir.
Tanlash (tanlash)
Tanlash bosqichida evolyutsiyaning ushbu bosqichida "tirik" qoladigan butun populyatsiyaning ma'lum bir qismini tanlash kerak. Tanlashning turli usullari mavjud. Jismoniy h ning omon qolish ehtimoli Fitness(h) fitnes funktsiyasi qiymatiga bog'liq bo'lishi kerak. Omon qolish darajasi s ning o'zi odatda genetik algoritmning parametri bo'lib, u shunchaki oldindan berilgan. Seleksiya natijasida H populyatsiyasining N individidan sN individlari qolishi kerak, ular yakuniy H' populyatsiyasiga kiritiladi. Qolgan shaxslar vafot etadi.
• Turnir tanlovi - birinchi navbatda, tasodifiy ravishda belgilangan miqdordagi shaxslar tanlanadi (odatda ikkita), so'ngra ular orasidan fitnes funksiyasining eng yaxshi qiymatiga ega bo'lgan shaxs tanlanadi.
• Ruletka usuli - shaxsni tanlash ehtimoli qanchalik ko'p bo'lsa, uning fitnes funksiyasining qiymati shunchalik yaxshi bo'ladi, bu erda - i shaxslarni tanlash ehtimoli, - i shaxslar uchun fitnes funksiyasining qiymati, - jismoniy shaxslar soni. aholi
• Reyting usuli - tanlash ehtimoli fitnes funksiyasining qiymati bo'yicha tartiblangan shaxslar ro'yxatidagi o'rniga bog'liq bo'ladi, bu erda , , jismoniy shaxsning fitnes funksiyasi qiymati bo'yicha tartiblangan shaxslar ro'yxatidagi seriya raqami ( ya'ni fitnes funksiyasining qiymatini minimallashtirsak)
• Yagona reyting — shaxsni tanlash ehtimoli quyidagi ifoda bilan aniqlanadi: , bu erda usul parametri
• Sigma kesish - genetik algoritmning muddatidan oldin yaqinlashishini oldini olish uchun maqsad funktsiyasi qiymatini masshtablash usullari qo'llaniladi. Shaxsni tanlash ehtimoli qanchalik katta bo'lsa, masshtablangan maqsad funktsiyasining qiymati shunchalik optimal bo'ladi, bu erda , butun populyatsiya uchun maqsad funktsiyasining o'rtacha qiymati, s - maqsad funktsiyasi qiymatining standart og'ishi [ 15].
Ota-onalar tanlovi
Genetik algoritmlarda ko'payish nasl berish uchun bir nechta ota-onalarni, odatda ikkitasini talab qiladi.
Bir nechta ota-ona tanlash operatorlari mavjud:
1. Panmiksiya - ikkala ota-ona ham tasodifiy tanlanadi, aholining har bir shaxsi tanlanish uchun teng imkoniyatga ega.
2. Qarindoshlik - birinchi ota-ona tasodifiy tanlanadi, ikkinchisi esa birinchi ota-onaga eng o'xshashi tanlanadi.
3. Outbreeding - birinchi ota-ona tasodifiy tanlanadi, ikkinchisi esa birinchisiga eng kam o'xshashi tanlanadi. ota-ona haqida
Inbreeding va outbreding ikki shaklda bo'ladi: fenotipik va genotipik. Fenotipik shaklda o'xshashlik moslik funktsiyasi qiymatiga qarab o'lchanadi (maqsad funktsiyasi qiymatlari qanchalik yaqin bo'lsa, shaxslar shunchalik o'xshash), genotipik shaklda esa o'xshashlik o'lchanadi. genotipning vakiliga qarab (individlar genotiplari orasidagi farqlar qanchalik kam bo'lsa, individlar shunchalik o'xshash).
Qayta ishlab chiqarish (kesishish) Turli xil algoritmlarda ko'paytirish turlicha aniqlanadi - bu, albatta, ma'lumotlarning taqdimotiga bog'liq. Ko'payishning asosiy talabi - nasl yoki nasl ikkala ota-onaning xususiyatlarini meros qilib olish, ularni qandaydir tarzda "aralashtirish" imkoniyatiga ega bo'lishidir.
Nima uchun ko'payish uchun shaxslar birinchi bosqichda saqlanib qolgan H' elementlaridan emas, balki butun H populyatsiyasidan tanlanadi (garchi oxirgi variant ham mavjud bo'lish huquqiga ega)? Haqiqat shundaki, ko'plab genetik algoritmlarning asosiy kamchiliklari - bu shaxslarda xilma-xillikning yo'qligi. Tezda bitta genotip ajralib turadi, bu mahalliy maksimaldir va keyin populyatsiyaning barcha elementlari unga tanlovni yo'qotadi va butun populyatsiya ushbu shaxsning nusxalari bilan "tiqilib qoladi". Bunday kiruvchi ta'sir bilan kurashishning turli usullari mavjud; ulardan biri eng moslashgan emas, balki umuman barcha shaxslarni ko'paytirish uchun tanlovdir. Biroq, bu yondashuv bizni oldindan mavjud bo'lgan barcha shaxslarni saqlashga majbur qiladi, bu esa muammoning hisoblash murakkabligini oshiradi. Shu sababli, o'tish uchun shaxslarni tanlash usullari ko'pincha shunday qo'llaniladiki, nafaqat eng moslashgan, balki yomon jismoniy holati bo'lgan boshqa shaxslar ham "ko'payadi". Ushbu yondashuv bilan genotipning xilma-xilligi uchun mutatsiyalarning roli ortadi.
Mutatsiyalar
Xuddi shu narsa ko'payish mutatsiyalariga ham taalluqlidir: genetik algoritmning parametri bo'lgan mutantlarning m ning ma'lum bir qismi mavjud va mutatsiya bosqichida siz mN shaxslarni tanlashingiz va keyin ularni oldindan belgilangan mutatsiya operatsiyalariga muvofiq o'zgartirishingiz kerak. .
Tanqid
Boshqa optimallashtirish usullari bilan taqqoslaganda, genetik algoritmdan foydalanishni tanqid qilish uchun bir nechta sabablar mavjud:
• Murakkab masalalar uchun fitnes funksiyasini qayta baholash ko'pincha sun'iy evolyutsiya algoritmlarini qo'llashda cheklovchi omil hisoblanadi. Murakkab yuqori o'lchamli muammoning optimal echimini topish ko'pincha fitnes funktsiyasini juda qimmat baholashni talab qiladi. Haqiqiy muammolarda, masalan, strukturani optimallashtirish muammolarida, bir martalik funktsional baholash uchun zarur hisob-kitoblarni bajarish uchun bir necha soatdan bir necha kungacha kerak bo'ladi. Standart optimallashtirish usullari bunday muammolarni hal qila olmaydi. Bunday holda, aniq hisob-kitobni e'tiborsiz qoldirish va samarali hisoblash mumkin bo'lgan fitnesga yaqinlikdan foydalanish kerak bo'lishi mumkin. Shubhasiz, fitnesga yaqinlashtirishdan foydalanish genetik algoritmlardan foydalangan holda murakkab real hayot muammolarini oqilona hal qilish uchun eng istiqbolli yondashuvlardan biriga aylanishi mumkin.
• Genetik algoritmlar hal qilinayotgan muammoning murakkabligiga nisbatan yomon miqyosda. Bu shuni anglatadiki, agar eritma qidirish maydoni katta bo'lsa, mutatsiyaga duchor bo'lgan elementlarning soni juda katta. Bu dvigatel, uy yoki samolyotni loyihalash kabi muammolarni hal qilish uchun ushbu kompyuter texnologiyasidan foydalanishni juda qiyinlashtiradi. Bunday muammolarni evolyutsion algoritmlarga moslashtirish uchun ularni ushbu muammolarning eng oddiy ko'rinishlariga bo'lish kerak. Shunday qilib, evolyutsion hisob-kitoblar, masalan, butun dvigatel o'rniga pichoqlar shaklini loyihalashda, batafsil konstruktsiya loyihasi o'rniga binoning shakli va butun samolyotning ko'rinishini ishlab chiqish o'rniga fyuzelyaj shaklini loyihalashda qo'llaniladi. . Ikkinchi murakkablik muammosi - yuqori darajada foydalanish mumkin bo'lgan echimlar bilan ishlab chiqilgan qismlarni keyingi halokatli mutatsiyadan qanday himoya qilish kerak, ayniqsa ulardan foydalanish imkoniyatini baholash jarayonida boshqa qismlarga yaxshi mos kelishi kerak bo'lganda. Ba'zi ishlab chiquvchilar tomonidan yechimning yaroqliligiga o'zgaruvchan yondashuv bir qator xavfsizlik muammolarini bartaraf etishi mumkinligi taklif qilingan, ammo bu masala haligacha tadqiqot uchun ochiq.
• Eritma boshqa yechimlarga qaraganda ko'proq mos keladi. Natijada, algoritmning to'xtash sharti har bir masala uchun aniq emas.
• Ko'pgina masalalarda genetik algoritmlar berilgan muammo uchun global optimalga emas, balki mahalliy optimalga yoki hatto ixtiyoriy nuqtaga yaqinlashishga moyildir. Bu shuni anglatadiki, ular uzoq muddatli fitnes uchun qisqa muddatli yuqori jismoniy tayyorgarlikni qanday qurbon qilishni "bilmaydilar". Buning ehtimoli fitnes landshaftining shakliga bog'liq: individual muammolar global minimumga aniq yo'nalishga ega bo'lishi mumkin, qolganlari esa fitnes funktsiyasini mahalliy optimallikka yo'naltirishi mumkin. Bu muammoni boshqa fitnes funksiyasidan foydalangan holda, mutatsiyalar ehtimolini oshirish yoki populyatsiyadagi yechimlarning xilma-xilligini qo'llab-quvvatlovchi tanlash usullaridan foydalanish orqali hal qilish mumkin, garchi Qidiruv va optimallashtirishda bepul tushlik yo'q teoremasi [16] buni isbotlaydi. bu muammoning umumiy yechimi emas. Populyatsiya xilma-xilligini saqlashning keng tarqalgan usuli - yuqori yaqinlikka ega bo'lgan elementlarning soni bo'yicha daraja chegarasini o'rnatish, bu keyingi avlodlarda shunga o'xshash echimlar vakillarining sonini kamaytiradi, populyatsiyada boshqa, kamroq o'xshash elementlarning qolishiga imkon beradi. Biroq, bu usul muayyan muammoli landshaftga qarab muvaffaqiyatli bo'lmasligi mumkin. Yana bir mumkin bo'lgan usul - populyatsiya elementlari bir-biriga juda o'xshash bo'lgan paytda, populyatsiyaning bir qismini tasodifiy yaratilgan elementlar bilan almashtirishdir. Turli xillik genetik algoritmlar (va genetik dasturlash) uchun muhimdir, chunki bir hil populyatsiyadagi genlarning kesishishi yangi echimlarni keltirmaydi. Evolyutsion strategiyalar va evolyutsion dasturlashda xilma-xillik zarurat emas, chunki ularda mutatsiya katta rol o'ynaydi.
Genetik algoritmlardan foydalanishning maqsadga muvofiqligi haqida ko'plab skeptiklar mavjud. Masalan, Stony Bruk universitetining kompyuter injiniringi professori, mashhur algoritm tadqiqotchisi va IEEE instituti mukofoti sovrindori Stiven S. Skiena yozadi[17]:
Shaxsan men hech qachon genetik algoritmlar eng mos vosita bo'lishi mumkin bo'lgan bitta muammoga duch kelmaganman. Bundan tashqari, men hech qachon genetik algoritmlar orqali olingan hisob-kitoblarning menda ijobiy taassurot qoldiradigan natijalarini uchratmaganman.
Genetik algoritmlarni qo'llash
Genetik algoritmlar quyidagi muammolarni hal qilish uchun ishlatiladi:
1. Xususiyatlarni optimallashtirish
2. Ma'lumotlar bazalarida so'rovlarni optimallashtirish
3. Grafiklardagi turli masalalar (sayohatchi sotuvchi muammosi, rang berish, mosliklarni topish)
4. Sun'iy neyron tarmoqni o'rnatish va o'rgatish
5. Vazifalarni tuzish
6. Rejalashtirish
7. O'yin strategiyalari
8. Taxminlash nazariyasi
9 Sun'iy hayot
10. Bioinformatika (oqsillarning buklanishi)
11. Cheklangan avtomatlarning sintezi
12. PID kontrollerlarini sozlash