13-ma'ruza. Genetik algoritmlar

^13-ma'ruza. Genetik algoritmlar

Reja

1. 
   Kirish.
   
2. 
   Genetik algoritm va uning asosiy tushunchalari.
   
3. 
   Genetik algoritmlarda kodlash.
   
4. 
   Klassik genetik algoritm va uning asosiy bosqichlari.
   
5. 
   Genetik algoritmlar va an'anaviy optimallashtirish usullari.
   
6. 
   Klassik genetik algoritmning bajarilishini tasvirlash.
   
7. 
   Genetik algoritmlar haqidagi asosiy teorema.
   

Kalit so'zlar. Genetik algoritm (Genetic algorithm), ko'payish (reproduction), xromosoma (chromosome), rekombinatsiya (recombination), populyatsiya (population), allel (allele), genotip (genotype), fenotip (phenotype), gen (gene), lokus (lokus), moslanuvchanlik funksiyasi (fitness function), moslanuvchanlik darajasi (degree of fitness), avlod (generation), naslning avlodi (generation of offspring), xromosomalarning populyatsiyasi (population of chromosome), klassik genetik algoritm (classical genetic algorithm), xromosoma populyatsiyalari (chromosome populations), xromosomalarni tanlash (chromosome selection), initsializatsiyalash (initialization), xromosomalarni tanlash ehtimoli (chromosome selection probability), rulet g'ildiraklari (roulette wheels), ruletka g’ildiragi aylanasi (roulette wheel circumference), ota-ona populyatsiyasi (parent population), chatishtiruv (crossover), chatishtiruv operatori (crossover operator), mutatsiyalash (mutation), mutatsiyalash operatori (mutation operator), kodlash (coding), ikkilik kodlash (binary coding), sxemaning yo'q bo’lish ehtimoli (scheme destruction probability), sxemaning omon qolish ehtimoli (scheme survival probability), qamrab olish (defining length).

1. Kirish

Tabiiy tizimlarning rivojlanishi ko'p asrlar davomida olimlarning e'tiborini tortib kelgan. Tirik tabiatda yuz beradigan o'zgarishlar asosida yotgan asosiy prinsiplar va mexanizmlarni aniqlash va tushunishga bir necha bor urinishlar qilingan. Charlz Darvin 1858 yilda mashhur "Turlarning kelib chiqishi" ni nashr etgunga qadar juda ko'p turli xil tushunchalar taklif qilingan edi, unda irsiyat, o'zgaruvchanlik va tabiiy tanlanish tamoyillari e'lon qilingan. Biroq, deyarli 100 yil davomida organizmlarning irsiy va o'zgaruvchanligi uchun javobgar mexanizmlar noaniq bo'lib qoldi. 1944 yilda Eyveri, Makleod va Makkarti "dezoksiriboza tipidagi kislota" irsiy jarayonlar uchun mas'ul ekanligini isbotlovchi tadqiqotlar natijalarini nashr etishdi. Ushbu kashfiyot dunyo bo'ylab ko'plab tadqiqotlarni keltirib chiqardi va 1953 yil 27-aprelda Uotson va Kriklarning “Nature” jurnalida ikkizanjirli DNK spirali modelini tavsiflovchi maqola chop etishdi.

Irsiyatning evolyutsion tamoyillari va genetik asoslarini bilish molekulyar

ketma-ketliklar o'zgarishi dinamikasini tavsiflaydigan molekulyar evolyutsiyaning modelini [1] hamda ekologiya, tarix va sotsiologiyada organizmlarning ekotizimlari va turkumlarini o'rganish uchun qo'llaniladigan makroevolyutsion modellarni [1, 2] ishlab chiqishga imkon berdi.
Mashinali o’rgatishda evolyutsion tamoyillarni qo'llash g'oyasi A. Turingning "O'ylaydigan" mashinalarni yaratish muammolariga bag'ishlangan ilmiy ishlarida ham qaralgan [11].
Evolyutsiyani simulyatsiya qilish bo'yicha birinchi ish 1954 yilda Niels Baricelli tomonidan Prinston Universitetining ilmiy tadqiqotlar institutida o'rnatilgan kompyuterda amalga oshirilgan [18]. O'sha yili uning kitobi keng jamoatchilik e'tiborini tortdi. 1957 yildan boshlab avstraliyalik genetika bo'yicha mutaxassis Aleks Frazier ko'p o'lchovli xususiyatlarga ega bo'lgan organizmlar o'rtasida sun'iy tanlanishni taqlid qilish bo'yicha bir qator asarlarni nashr etdi. Dastlab evolyutsion jarayonlar Frazer [20] va Baricelli (1970) [18] hamda Krosbi (1973) [19] kitoblarida tasvirlangan usullarni kompyuterda taqlid qilish imkoniyati yaratildi, 60-yillardan boshlab biologlar orasida keng tarqalgan faoliyat turiga aylandi. Frayzerning simulyatsiyasi zamonaviy genetik algoritm(GA)larning barcha zarur elementlarini o'z ichiga oldi. Bundan tashqari, Hans-Yoaxim Bremermann, Richard Fridberg, Jorj Fridman va Maykl Konrad kabi olimlar ham GAlar yo’nalishida ilmiy tadqiqot ishlarini olib borganlar. Bu yo’nalshda chop etilgan ilmiy ishlarning ko'pchiligi Devid B. Fogel tomonidan nashr etilgan (1998) [21].
Garchi Baricelli 1963 yilgi asarida mashinaning oddiy o'yin o'ynash qobiliyatini simulyatsiya qilgan bo'lsa-da, sun'iy evolyutsiya 1960 va 1970-yillar boshlarida Ingo Rechenberg va Hans-Paul Schweffelning ishidan so'ng universal qabul qilingan optimallashtirish usuliga aylanishini Rechenberg guruhi hal qila oldi [22, 23]. Yana bir yondoshuv - bu Lawrence J. Fogelning sun'iy intellektni yaratishda evolyutsion dasturlash uslubini qo’llashdan iborat [21]. Evolyutsion dasturlash dastlab vaziyatlarni bashorat qilishda chekli avyomatlardan foydalangan va mantig'iy bashoratlasni optimallashtirishda foydalangan. Genetika algoritmlari 70-yillarning boshlarida Jon Xollandning ishi va uning "Tabiiy va sun'iy tizimlarda moslashish" (1975) [4] kitobi tufayli ommalashib ketdi. Uning tadqiqotlari Michigan universitetida Xolland tomonidan xujayrali avtomatlar bo'yicha o'tkazilgan tajribalar va uning yozgan asarlari asosida olib borildi. Xolland "Sxemalar teoremasi" deb nomlanuvchi keyingi avlod sifatini bashorat qilish uchun rasmiy yondashuvni taqdim etdi. Genetika algoritmlari sohasidagi tadqiqotlar asosan nazariy bo'lib, ular 80-yillarning o'rtalariga qadar Pittsburg Pensilvaniya shtatida (AQSh) genetika algoritmlari bo'yicha birinchi xalqaro konferentsiya o'tkazilgunga qadar saqlanib qoldi.
Tadqiqotga qiziqishning o'sishi bilan shaxsiy kompyuterlarining hisoblash hajmi va tezligi sezilarli darajada o'sdi, bu esa yangi hisoblash texnologiyalarini amalda qo'llashga imkon berdi. 80-yillarning oxirida General Electric dunyodagi birinchi GAga asoslangan mahsulotni sotishni boshladi. 1989 yilda Axcelis, Inc. kompaniyasi shaxsiy kompyuterlarga mo’ljallangan GAga asoslangan dunyoda birinchi tijorat maxsulotini islab chiqdi.
Evolyutsion printsiplar nafaqat modellashtirish uchun, balki optimallashtirishning amaliy muammolarini hal qilish uchun ham qo'llaniladi. Yechim topishda evolyutsion yondashuvdan foydalanadigan turli xil algoritmlar va usullar evolyutsion hisoblash (EH) yoki evolyutsion algoritm(EA)lar umumiy nomi ostida birlashtirilgan [3]. EHlarning quyidagi asosiy yo'nalishlari mavjud:

• 
  genetik algoritm (GA) [4, 5];
  
• 
  evolyutsion dasturlash (ED) [6];
  
• 
  evolyutsion strategiyalar (ES) [7, 8];
  
• 
  genetik dasturlash (GD) [9].
  

GAlar o'z ishlarida irsiyat, o'zgaruvchanlik va tabiiy tanlanishning evolyutsion tamoyillaridan foydalanadilar [4, 5].
L.Dj. Vogel 1960 yilda EDni birinchi marta evolyutsiyani modellashtirish uchun sun'iy intellektni yaratish maqsadida o'quv jarayoni sifatida taklif etildi [6]. U belgilarni raqamli ketma-ketliklar ko’rinishda ifodalaydigan va ular rivojlanib borgan sari qo'yilgan masalani hal qilishga ko'proq moslashib boradigan chekli avtomatlardan foydalangan,
ESlar - bu moslashish va evolyutsiya g'oyalariga asoslangan optimallashtirish usuli [7, 8]. Bu holda mutatsiyalash darajasi vaqt o'tishi bilan o'zgarib turadi - bu esa o'z-o'zini moslashishga olib keladi.
GD - bu dasturlar populyatsiyasiga evolyutsion yondashuvni qo'llashdan iborat. GD (genetic programming) - turli xil algoritmlarni tavsiflash uchun gen injeneriyasi metaforasidan foydalanishga urinish hisoblanadi. Sun’iy «genetik» tizimlardagi satrlar biologik tizimlardagi xromasomalarga o`xshash. GAlarda fiksirlangan uzunlikdagi satrlar asosiy qurilish bloklari rolini o`ynaydi. Genetik
dasturlashda bu satrlar daraxtga sochib tashlanadi. Masalan, ^{a  b * c} hamda
^{(a  b)*(c  d )} ifodalarni quyidagi ko`rinishlarda ifodalaydi:
+ *

_{a *} + -