13-ma'ruza. Genetik algoritmlar

Genetik ma'lumotlar. DNK va xromosomalar. Tirik organizmning har bir hujayrasida u haqida kodlangan ma'lumotlar mavjud bo’ladi. Irsiy material "gen" deb nomlanadi. Genlarning katta qismi, shu jumladan inson genini DNK (Dezoksiribonuklein kislotasi) tashkil etadi va bir qator viruslarda gen RNK(Ribonuklein kislotasi)dan hosil bo'ladi.
Genomning genetik ma'lumotlari genlardan yig'iladi. Gen - bu irsiy ma'lumotni uzatish birligi va organizmning ma'lum bir xususiyatiga ta'sir qiladigan DNK hisoblanadi. Genlar to'plami genotip deb nomlanadi.
Kimyoviy nuqtai nazardan DNK- bu to'rt blokli nukleotidlarning turli xil
birikmalaridan tashkil topgan uzun, juft spiralli polimer molekulasi hisoblanadi (13.2-rasm). Har bir nukleotidga lotin harfi nomi berilgan: A, G, T, C. Genetik ma'lumot uchun DNKdagi nukleotidlarning, ya’ni genetik kodining almashinuv ketma-ketligini kelish tartibi bilan belgilanadi.

13.2-rasm. DNKning turli shakllari.

DNKning har bir molekulasi xromosomalar bilan o'ralgan va hujayra yadrosida joylashgan bo’ladi. Genetik ma'lumotlarning yaxlitligini saqlab qolish uchun yadrodagi xromosomalar bir-biridan ajralib turadi.
Inson genomi 23 juft xromosomadan va bitta alohida DNKdan iborat bo’lib, ular tarkibida 28 mingta genlar mavjud.
Genetik algoritmning asosiy tushunchalari. GAlarda genetikadan olingan bir qator atamalar, birinchi navbatda genlar va xromosomalar, shuningdek populyatsiya, individual, allel, genotip, fenotip kabilar ishlatiladi. Shuningdek, ushbu atamalarga mos keladigan texnik leksikadagi tushunchalar, xususan, zanjir, ikkilik ketma-ketlik, tuzilma kabilardan ham foydalaniladi [17].
Populyatsiya - bu cheklangan xromosoma (zot)lar to'plami. GAlarda populyatsiyaga kiritilgan xromosomalar ular ichida kodlangan muammoli parametrlar to'plami bo'lgan xromosomalar bilan ifodalanadi, ya'ni, echimlar, boshqacha qilib aytganda qidiruv fazosidagi nuqtalar (qidiruv nuqtalari) deb ataladi. Ba'zi bir ilmiy ishlarda xromosomalar organizmlar deb ham ataladi.
Xromosoma - bu irsiy ma'lumotlarning tashuvchisi. Xromosomalar to'plami individni xarakterlaydi. Xromosoma genlardan tashkil topgan. Xromosomalar (qatorlar yoki kodlar ketma-ketligi deb ham ataladi) - bu genlarning tartiblangan ketma-ketliklari hisoblanadi.
Gen (xususiyat, belgi yoki detektor deb ham ataladi) - bu genotipning atomar elementi, xususan xromosomalar hisoblanadi. Genlar - irsiy axborotni kodlash elementlari. Axborotni bitli kodlash ko'pincha genlar vazifasini bajaradi.
Genetik operator - bu avlodni olish uchun zarur bo'lgan bir yoki bir nechta ota-onalarga nisbatan tartiblangan harakatlar ketma-ketligi.
Individ (zot, organizm) - xromosomalar to'plami.
Individual moslanuvchanlik - kerakli parametrga nisbatan berilgan parametrlar to'plami uchun maqsad funksiyasining qiymati.
Genotip yoki tuzilma - bu ma'lum bir individning xromosomalar to'plami hisoblanadi. Binobarin, populyatsiyaning individual a'zolari genotiplar yoki bitta xromosomalar bo'lishi mumkin (keng tarqalgan holatda siftida genotip bitta xromosomadan iborat bo'lgan holar qaraladimasala
Fenotip - bu ma'lum bir genotipga mos keladigan qiymatlar to'plami, ya'ni. masala parametrlarining dekodlangan tuzilmasi yoki to'plami (echimi, qidiruv fazosining nuqtasi).
Allel - bu ma'lum bir genning qiymati, shuningdek xususyatning qiymati yoki xususiyatning bir varianti sifatida aniqlanadi.
Lokus yoki joy - bu ma'lum bir genning xromosoma(zanjir)da joylashgan joyini ko’rsatadi. Genlar joylarining to’plami loklar deb ataladi.
Moslanuvchanlik funksiyasi (MF) - bu genetikaga xos bo’lib, u populyatsiyadagi muayyan individlarning jismoniy tayyorgarligini baholash va eng munosiblarini tirik qolish evolyutsion prinsipiga muvofiq ular orasida eng munosibini (ya'ni MFning maksimal qiymatlariga ega bo’lganini) tanlashga imkon beradi. Bu maqsad funksiyalarning alohida xususiy hollaridan biri hisoblanadi. Shuningdek, MF (baholash funksiyasi) genetikada ma'lum bir shaxsning populyatsiyaga mosligini o'lchaydigan o'lchovni aks ettiradi. Optimallashtirish masalalarida MF odatda optimallashtiriladi (aniqrog'i, maksimal darajaga ko'tariladi) va madsa funksiya deb ataladi. Minimallashtirish masalalarida maqsad funksiya o'zgartiriladi va muammo maksimallashtirishga keltiriladi. Boshqarish nazariyasida MF xatolik funksiyasi shaklida, o'yinlar nazariyasida xarajatlar funksiyasi shaklida bo'lishi mumkin. Genetika algoritmining har bir takrorlanishida ma'lum bir populyatsiyaning har bir individini jismoniy tayyorgarligi MFdan foydalangan holda baholanadi va shu asosda muammoning potentsial echimlari to'plamini tashkil etadigan jismoniy individlarning navbatdagi populyatsiyasi yaratiladi, misol sifatida optimallashtirish masalasini keltirish mumkin.
Xromosomalarning boshlang'ich populyatsiyasini yaratish - bu MF parametrlarining qiymatlari tasodifiy tanlangan va ushbu parametr qiymatlari uchun MF qiymati topilgan holat.
Seleksiyalash (tanlash) - ko'payish uchun eng yaxshi moslashuvchanligi bo'lgan xromosomalarni seleksiyalash (moslanuvchanlik (maqsad) funksiyasi qiymati bo'yicha saralash). Xromosomaning moslanuvchanlik tayyorgarligi qanchalik yaxshi bo'lsa, kelajak avlodga uning genlarini chatishtirish va meros qilib olish imkoniyati shunchalik yuqori bo'ladi.
Chatishtiruv - bunda tasodifiy ravishda xromosomalar qatoridagi qo’shni bitlar orasida uzilish nuqtasi tanlanadi. Ikkala ota-ona xromosomalari ham shu vaqtda ikkita segmentga bo'linadi. Keyin, turli xil ota-onalarning tegishli segmentlari biriktiriladi va naslning ikkita genotipi olinadi (13.3-rasm).

13.3-rasm. Xromosomalarni chatishtiruv jarayoni.
Mutatsiyalash - bu genlarning tasodifiy o'zgarishi. Tasodifiy tanlangan gen qandaydir ehtimollik bilan bosqasiga o'zgaradi (13.4-rasm).

13.4-rasm. Xromosomani mutatsiyalash jarayoni.
Inversiyalash - xromosoma kodi qismlarini kelish tartibini o'zgartirish bo’lib, bunda tasodifiy ravishda xromosoma kodidagi qo’shni bitlar orasida uzilish nuqtasi tanlanadi (13.5-rasm). Uzilish nuqtasi bo’yicha ota-ona xromosoma kodidagi qismlar joulari almashtiriladi va undan keyin birlashtiriladi.

13.5-rasm. Xromosomani inversiyalash jarayoni.
GAdagi navbatdagi populyatsiya avlod deb ataladi va "yangi avlod" yoki "nasllar avlodi" atamasi xromosomalarning yangi yaratilgan populyatsiyasiga nisbatan qo'llaniladi.
Ikkilik kodlash - bu xromosomaning genotipini nol va birdan iborat raqamli ketma-ketlik sifatida aks ettirish usuli.
Haqiqiy kodlash - bu xromosomaning genotipini haqiqiy sonlar to'plami sifatida aks ettirish usuli.
J. Xolland [4] tabiiy evolyutsiya jarayonlarining xususiyatlari (shu jumladan, tirik mavjudotlarning o'zi emas, balki xromosomalar rivojlanib borishi) bilan qiziqdi. Xolland murakkab muammolarni tabiat evolyutsiyasi yo'li bilan hal qiladigan algoritmni kompyuter dasturi shaklida tuzish va amalga oshirish imkoniyatiga ishongan. Shuning uchun u xromosomalar deb nomlangan ikkilik raqamlarning (birlar va nollar) ketma-ketliklari ustida ishlaydigan algoritmlar ustida ishlashni boshladi. Ushbu algoritmlar bunday xromosomalarning avlodlaridagi evolyutsion jarayonlarni taqlid qildi. Tabiiy evolyutsiyada ishlatilgandek, seleksiyalash (tanlash) va ko'payish (reproduksiya) mexanizmlari ularda amalga oshirildi. Xuddi tabiatda bo'lgani kabi, GAlar ham echilayotgan masalaning mohiyati to'g'risida hech qanday ma'lumot ishlatmasdan "yaxshi" xromosomalarni izlashni amalga oshirdi. Faqatgina har bir xromosomani uning jismoniy holatini aks ettiruvchi moslanuvchanlik darajasini belgilaydigan baholashlar aniqlandi. Seleksiyalash mexanizmi eng katta moslanuvchanlik darajasiga ega bo`lgan xromosomalarni ajratib olishdan iborat. Bunday xromosomalar pastroq moslanuvchanlik xromosomalarga ko`ra ko`proq urchishadilar. Urchish  ota-ona xromosomalari genlarinining rekombinatsiyalash(aralashmasi) natijasida yangi xromosomalarni yaratishni anglatadi. Rekombinatsiyalash - bu genlarning yangi kombinatsiyalarini paydo bo`lishiga olib keladigan jarayondir. Buning uchun ikki: chatishtiruv va mutatsiyalash amallari bajariladi. Chatishtiruv amali ota-ona xromosoma juftlari genlarini qayta kombinatsiyalash yo`li bilan avlodlarning mutlaqo yangi xromosomalarini yaratishga imkoniyat beradi. Mutatsiyalash amali ayrim xromosomalar tuzilmalarida tegishli o`zgarishlarni yuzaga keltirishi mumkin.