13-ma'ruza. Genetik algoritmlar

b c a b c d
13.1-rasm. Matematik ifodalarning daraxtli ko`rinishi.
Hozirgi paytda Stendford Universitetida professor Djon Koza [9] rahbarligida ishlayotgan tadqiqotchilar guruhi genetik dasturlash sohasidagi liderlardan biri hisoblanadi. Genetik dasturlash ro`yxatlarni qayta ishlash va funksional dasturlash uchun yaratilgan va allaqachon unutilgan LISP (List Programming) tiliga yangi hayot bag`ishladi. Aynan shu til AQShda SI masalalari uchun keng tarqalgan dasturlash tillaridan biri bo`lgan va bo`lib qolmoqda.
EH usullari belgilangan me’yorda biologik evolyutsiya va seleksiyalash(tabiiy tanlab olish) jarayonlarini taqlid qiladilar. EH mutatsiyalash
(dastlabki populyatsiyada), chatishtiruv, seleksiyalash (yangi populyatsiyani shakllashtirish) kabi asosiy protseduralardan iborat.
Mazkur usullar optimallashtirish, ayniqsa ko`pmezonli optimallashitirish masalalarini yechish uchun keng qo`llaniladi. Zamonaviy kompyuter va dasturlash texnoglogiyalari imkoniyatlari keskin ravishda oshganligi bilan EHning qo`llanish sohasi ham kengaydi. Bu - murakkab nochiziqli tizimlarni kompyuterli tahlil qilish, operatsiyalarni (noaniqlik, noto`liqlik sharoitlarda) tadqiq qilish, SI, “Yumshoq hisoblashlar” (Soft computing) nazariyasi va texnologiyalari, jonli tabiatni(Artificial life) kompyuterlar yordamida modellash, tasniflash, bashoratlash, tashxislash, ko`pmezonli optimallashtirish (global optimumni topish), noto`liqlik sharoitlarda qarorlarni qabul qilishni qo’llab-quvvatlashni o`rgatish sohalardir. EH usullari ananaviy stoxastik adaptiv usullarga qo`shimcha usullar bo`lib hisoblanadi.

2. Genetik algoritm va uning asosiy tushunchalari

GAlar tirik organizmlar dunyosida yuz beradigan tabiiy jarayonlarni, xususan, evolyutsiyani va tirik mavjudotlar populyatsiyasining shu bilan bog'liq tanlanishini (tabiiy tanlanishini) kuzatish va nusxalashga urinishlar natijasida paydo bo'lgan [6]. Genetik algoritm(GA) - bu tabiatdagi tabiiy seleksiyalashga o'xshash mexanizmlardan foydalanib, kerakli parametrlarni tasodifiy tanlab olish, birlashtirish va o'zgartirish orqali optimallashtirish va modellashtirish muammolarini hal qilish uchun ishlatiladigan evristik qidiruv algoritmi. Bu evolyutsion hisoblashning bir turi bo'lib, evolyutsiya muammolarini tabiiy evolyutsiya usullaridan foydalangan holda, masalan meros, mutatsiyalash, tanlab olish va chatishtirish kabi muammolarni hal qiladi. GAning o'ziga xos xususiyati o'rni yovvoyi tabiatda o'tish roliga o'xshash bo'lgan nomzod echimlarining rekombinatsiyasini amalga oshiruvchi «chatishtirish» operatoridan foydalanishga
qaratiladi.
Yuqorida ta'kidlab o'tilganidek, GAlar o'z ishlarida irsiyat, o'zgaruvchanlik va tabiiy tanlanishning evolyutsion tamoyillaridan foydalanadilar.
GAlar g'oyasi J. Xolland tomonidan XX asrning 60-yillari oxiri 70-yillari boshlarida taklif qilingan va uning birinchi tadqiqotlar natijalari "Tabiiy va sun'iy tizimlarga moslashish" [4] monografiyasida, shuningdek, uning aspiranti Kennet De Yongning dissertatsiyasida [10] umumlashtirilgan. Shuningdek, D. E. Goldberg [16] tomonidan oddiy GA tuzilmasi to`g`risida ilmiy ishlar chop etilgan.