Genetik algoritmlar

GENETIK ALGORITMLAR.


REJA:
1.Genetik algoritmning asosiy tushunchalari.
2. Genetik algoritm
3. Krossover

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. 6 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. Ota-onalarning xromosomalari Avlodlarning xromosomalari 7 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. Ota-ona xromosomasi Avlod xromosomasi Ota-ona xromosomasi Avlod xromosomasi 8 GAning asosiy xususiyatlari quyidagilardan iborat:
1. Sonli ko`rinishda emas, balki kodlashgan shaklda ifodalangan parametrlarni qayta ishlash.
2. Optimal yechimni masala parametrlarining birdan-bir nutqasidan emas, balki nutqalarning majmuisidan(ya’ni qandaydir populyatsiyadan) qidirish.
3. Optimal yechimni qidirish jarayonida faqat maqsadli funksiyadan foydalanish (uning hosila yoki biror boshqa axborotlaridan emas).
4. Optimal yechimni qidirishda deterministik qoidalardan foydalanmasdan faqat ehtimollik qoidalaridan foydalanish. Mazkur protseduralar GAning ko`p ekstremalli masalalarida global optimumini qidirishda barqarorlik va yuqori samaradorlikni ta’minlaydi.
Sodda GA mexanizmi quyidagi protseduralarni o`z ichiga oladi:
a) tasodifiy ravishda dastlabki xromosomalar (parametrlarni bit satrlar, stringxromosomlar, xromosomalar)ning ketma-ketliklar populyatsiyasini shakllantirish;
b) olingan dastlabki populyatsiyaga seleksiya, mutatsiyalash va chatishtiruv operatsiyalarni qo`llash;
v) ushbu operatsiyalarning bajarilishi natijasida xromosomalarning yangi populyatsiyalarini shakllantirish;
g) yangi populyatsiyaning moslashuvchanlik darajasini baholash (tanlangan mezon asosida) va moslashuvchanlik bahosi qoniqarli bo`lgan populyatsiyani yangi dastlabki populyatsiya sifatida saqlab qolish, aksincha - yo`qotish (yaroqsiz deb topish). Oxirgi holatda avvalgi dastlabki populyatsiyaga qaytiladi va seleksiyalash, mutatsiyalash hamda chatishtiruv operatsiyalari yangi parametrlar bilan barcha protseduralar takrorlanadi. GAlarning qo’llanilish sohalari. GAlar dasturiy ta'minotni ishlab chiqishda, sun'iy intellekt tizimlarida, optimallashtirishda, sun'iy neyron tarmoqlarida va boshqa bilim sohalarida qo'llaniladi. GAlar ko'pincha neyron tarmoqlari bilan birgalikda qo'llaniladi. Ular neyron tarmoqlarni qo'llab-quvvatlashi mumkin, yoki aksincha, yoki har ikkala usul ham muayyan masalani echish uchun gibrid tizim doidasida o'zaro birgalikda qo’llaniladi. GAlar noravshan tizimlar bilan birgalikda ham qo'llaniladi [17]. GAlar quyidagi masalalarni echishda qo’llaniladii:  Graflardagi turli masalalarni (kommivoyajer masalasi, eng qisqa yo'l masalasi, rang berish, mosliklarni topish);  joylashtirish vazifalari;  jadvallarni tuzish;  funksiyalarni approksimatsiyalash;  ma'lumotlarni tanlash (filtrlash);  sun'iy neyron tarmog'ini moslashtirish va o'qitish;  sun'iy hayot;  bioinformatika;  o'yin strategiyalari;  sonli optimallashtirish masalalari;  ma'lumotlar bazalarida so'rovlarni optimallashtirish; 9  nochiziqli filtrlash;  rivojlanayotgan agentlar / mashinalar. GAlarni tez-tez ishlatib turadigan ba'zi sohalarni ham keltirib o'tamiz:
• optimallashtirishda - ma'lum cheklovlar to'plami ostida maqsad funksiyasining berilgan qiymatini maksimal darajaga ko'tarish yoki kamaytirishdan iborat;
• iqtisodiyotda - veb-model, o'yinlar nazariyasidagi muvozanatni aniqlash, mahsulotlar narxlari va boshqalar kabi turli xil iqtisodiy modellarni tavsiflash uchun ham ishlatiladi;
• neyron tarmoqlarida - neyron tarmoqlarni, ayniqsa takrorlanuvchi neyron tarmoqlarni o'rgatishda qo’llaniladi;
• parallellel hisoblashda - GA shuningdek juda yaxshi bir vaqtda ishlash qobiliyatiga ega va muayyan muammolarni hal qilishda juda samarali vosita bo'lib, tadqiqot uchun yaxshi maydon yaratadi.
• tasvirlarni qayta ishlashda - turli xil raqamli tasvirlarni qayta ishlashda foydalaniladi hamda piksellarni zichli taqqoslashda ishlatiladi.
• avtotransport yo'nalishidagi muammolarda - bir nechta yumshoq vaqt oynalari, bir nechta omborlar va turli tipdagi parklar orasidagi marshrutlarni aniqlashda qo’llaniladi;
• rejalashtirish ilovalarida - turli xil rejalashtirish masalalarida, xususan vaqtni aniqlash masalalarida ishlatiladi;
• robot yo'lini generatsiya qilishda - robotning qo'li bir nuqtadan ikkinchisiga o'tishda harakatlanadigan yo'lni rejalashtirish uchun ishlatiladi;
• samolyotlarni parametrik loyixalashda - parametrlarini o'zgartirish va yaxshi echimlarni ishlab chiqish uchun samolyotlarni loyihalashda foydalaniladi;
• DNK tahlilida - namunadagi spektrometrik ma'lumotlar yordamida DNKning tuzilishini aniqlash uchun foydalaniladi;
• multimodal optimallashtirishda - bir nechta optimal echimlarni topish kerak bo'lganda multimodal optimallashtirishda ishlatiladi. GAlarning an'anaviy qidiruv usullaridan farqlari. Farqlari quyidagilardan iborat:
• GAlar optimal echimni topish uchun an'anaviy usullarda bo'lgani kabi bir nuqtadan boshqa nuqtaga o'tishdan ko'ra, bir vaqtning o'zida bir nechta nuqtalardan foydalanadilar. Bu maqsad funksiyasining lokal ekstremumiga tushish xavfini oldini oladi, agarda u unimodal bo'lmasa, ya'ni bir nechta ekstremumga ega bo’lsa. Bir vaqtning o'zida bir nechta nuqtalardan foydalanish bu imkoniyatni sezilarli darajada kamaytiradi;
• GAlar ishlash jarayonida hech qanday qo'shimcha ma'lumotlarni talab qilmaydi va bu algoritmning ishlash tezligini oshirishga olib keladi. GAlarda yagona ma'lumot: qabul qilinadigan qiymatlar diapazoni va muayyan nuqtalarda MFni hisoblashdan foyfalaniladi;
• GAlar bir nuqtadan ikkinchisiga o'tish uchun deterministik qoidalardan va yangi tahlil nuqtalarini yaratish uchun ehtimollik qoidalaridan foydalanadilar;
10 • GAlar maqsad funksiyasi argumentlariga bog'liq bo'lgan parametrlar to'plamini ifodalovchi kodlar bilan ishlaydi. Ushbu kodlarning talqini faqat algoritm boshlanishidan oldin va natijani olish uchun uning ishi tugagandan so'ng sodir bo'ladi. Ish jarayonida kodlar bilan manipulyatsiya ularning izohlanishidan butunlay mustaqil ravishda sodir bo'ladi va kod oddiygina bitli satr sifatida qaraladi. GA ning afzalliklari. GA ularni juda mashhur qilgan turli xil afzalliklarga ega. Bunga quyidagilar kiradi:
• hech qanday yasama ma'lumotlarini talab qilmaydi (ular haqiqiy hayotdagi ko'plab muammolar uchun mavjud bo'lmasligi mumkin);
• bu an'anaviy usullarga qaraganda tezroq va samaraliroq ishlaydi;
• juda yaxshi parallel ishlash imkoniyatlarga ega;
• uzluksiz va diskret funksiyalarni hamda ko'p maqsadli masalalarni optimallashtiradi;
• bitta yechim emas, balki "yaxshi" echimlar ro'yxatini taqdim etadi; • vaqt o'tishi bilan yaxshilanadigan muammoga doimo javob oladi;
• qidiruv fazosi juda katta bo'lganida va ko'plab parametrlar mavjud bo'lganda foydalanish qulay. Adabiyotlarda tasvirlangan tajribalar shuni ko'rsatadiki, GAlar adaptiv releflarning global minimalarini topishda juda samarali, chunki ular neyron tarmoqlari parametrlarining qabul qilinadigan qiymatlarining katta diapazonlarini o'rganishadi. (Gradient algoritmlari faqat lokal minimumlarni topishga imkon beradi.) GAlar neyron tarmoqlari parametrlarining diskret qiymatlari bilan ishlashga imkon beradi. Bu neyron tarmoqlarning raqamli apparat dasturlarini ishlab chiqishni soddalashtiradi. Uskunani amalga oshirishga yo'naltirilmagan kompyuterda neyron tarmoqlarni o'rgatish paytida ba'zi holatlarda parametrlarning alohida qiymatlarini ishlatish imkoniyati o'qitish (o’rgatish) vaqtining qisqarishiga olib kelishi mumkin. GA ning cheklovlari va kamchiliklari. Har qanday texnikada bo'lgani kabi GA ham bir nechta cheklovlardan holi emas. Bunga quyidagilar kiradi:
• GA barcha muammolarga mos kelmaydi, ayniqsa, sodda va ular uchun ma'lumot mavjud bo'lgan muammolar uchun;
• MF qiymati maslani echishda bir necha bor hisoblab chiqiladi, bu esa ba'zi masalalarni echishda hisoblashlar hajmining oshishiga olib keladi; • stoxastik bo'lganligi sababli echimning optimalligi yoki sifatiga hech qanday kafolat mavjud emasligi;
• agar GA to'g'ri bajarilmasa u optimal echimga yaqinlashmasligi mumkin. Genetik algoritmlari yordamida o’qitishni tushunish va uni dasturiy ta’minot sifatida amalga oshirish murakkab hisoblanadi. GAlardan foydalanib masalalarni echishda quyidagi muammoli holatlar paydo bo’lishi mumkin: aniq global optimallashtirish kerak bo'lganda; funksiyani baholashni bajarish vaqti uzoq bo’lganda; masalaning birortasini emas, balki barcha echimlarini topish kerak bo’lganda; echimlarni kodlash oddiy bo’lmaganda.