Genetik algoritm (GA) bu izlash va optimallashtirish algoritmi, bu algoritmning proobrazi boʻlib tabiiy tanlovning biologik prinsipi hisoblanadi [13-17]


Download 64.78 Kb.
Sana17.06.2023
Hajmi64.78 Kb.
#1534193
Bog'liq
путуешлф 3


1.3. Sun'iy intellekt. Genetik algoritm
Genetik algoritm: tabiiy tanlashga asoslangan sun'iy intellekt instrumenti sifatida. Bilamizki, evolyasiyaning asosiy postuloti irsiy oʻzgaruvchanlikdir, uning harakatlantiruvchi kuchi esa yashash uchun kurash va tabiiy tanlash hisoblanadi.
- 18-
Genetik algoritm (GA) - bu izlash va optimallashtirish algoritmi, bu algoritmning proobrazi boʻlib tabiiy tanlovning biologik prinsipi hisoblanadi [13-17].
Genetik algoritmning ishlash prinsipi [18] (1.2-rasm). Birinchi bosqich - ko'payishni tashkil qilish. Mazkur holatda populyasiya bu biologik, zotlar majmuasi emas, balki muammoning yechimini mumkin boʻlgan to'plamlari boʻlib, izlash fazosini tashkil qiladi (space search).
Ikkinchi bosqich yaroqlilik funksiyasini hisoblaydi (moslashuvchanlik, fitness function). Mazkur funksiya kirishda muammoning potensial yechimini qabul qiladi(candidate solution), keyin esa uning yaroqliligini baholaydi va qiymatini beradi. Klassik genetik algoritm holatida maqsad funksiyasi va yaroqlilik funksiyasi bitta ma'noga ega. Algoritm o'z ishini yakunlaydi, agar kutilayotgan optimal yechimga erishilgan bo'lsa, agar olingan qiymatni yanada yaxshilashni imkoni bo'lmasa yoki belgilangan vaqt ichida (iteratsiyalar soni) erishilmasa. Toʻxtagandan keyin oʻzi moslashgan xromosomani tanlash amalga oshiriladi. Agar algoritmni to'tash sharti bajarilmasa, u holda tabiiy tanlash natijasida nasl qoldirish uchun xromosomalar seleksiyasi ishlab chiqariladi.
Uchinchi bosqich - chatishtirish («krossingover») va mutatsiya. Chatishtirish, mutatsiya va seleksiya bular genetik operatorlar. Xuddi tabiatdagiday, chatishtirish ehtimolligi mutatsiya ehtimoligiga qaraganda bir qancha darajaga yuqoriroqdir. Populyasiyada chatishtirish cheksiz ko'p holatlarni qo'llab- quvvatlaydi, bu ota-onaning genetik materialini qayta taqsimlashdir, natijada nasllarda genlarning yangicha birlashmalari paydo bo'ladi. Genetik algoritmda "xromosoma" - parametrlar to`plami, mumkin boʻlgan yechimlarni aniqlaydigan, "gen" esa bu "xromosoma" satrida bitta “harf”, qoidaga binoan ikkilik qiymatga ega boʻlgan (0) yoki 1).
Mavzuni kengroq oʻrganuvchilar uchun F.Herrera, M.Losano, A.M.Sanches Hybrid Crossover Operators for Real-Coded Genetic Algorithms: An Experimental Study [16] maqolasini tavsiya qilamiz.
Mutatsiya genetik operator, u birorta ehtimollik bilan <ning tasodifiy pozitsiyalaridagi bitta yoki bir qancha "genlar"ni oʻzgartiradi. Mutatsiya bu genetik koddagi
oʻzgarishlar. Mutatsiya tabiatda mavjud, ular nasllarni yaxshi yashab ketishiga imkoniyat yaratadimi? Bu maqola genetika toʻgʻrisida emas, esdan chiqarmaslik kerakki, aynan shu maqola genetik algoritmni yaratuvchi olim Xolland (1975) uchun ijod manbai boʻldi. Genetik operatorlar ta'siriga uchragan nasllar yangi populyasiyani hosil qiladi – bunda yana navbatdagi GA iteratsiyasi boshlanadi.

Yangitdan yaroqlilik funksiyasini qiymati hisoblanadi, tabiiy tanlov amalga oshiriladi, undan keyin esa agar belgilangan shart
bajarilgan boʻlsa, toʻxtatiladi, yoki yana yangi seleksiyaga oʻtiladi. Genetik algoritmni qiziqarli tadbiqlaridan kommivoyajer - dayti savdogar (travelling salesman problem) masalasi, hamda ryukzakga narsalarni joylash (knapsack problem) masalasini keltirish mumkin. Bu ikkala masala asosan kombinatorika masalasi hisoblanadi.Biz oxir oqibatda optimal variantni izlaymiz. GA metodni ijobiy va salbiy tomonlarini keltiramiz.
GA ning ijobiy tomonlari. Bu algoritmning kuchli tomonlari mavjud:
⚫ bitta yechimni emas, balki bir qancha yechimlarni tanlashni
taklif qiladi; .birdaniga bir qancha nuqtalarni oʻrganadi, shu boisdan ham maqsad funksiyasi lokal ekstremumga yopishib qolmaydi;
⚫ muhitning shart-sharoitlarini o'zgarishi mobaynida optimizatsiya to'xtovsiz amalga oshiriladi, populyasiya esa moslashishga harakat qiladi;
.NP-hard muammo uchun qoniqarli yechimni taklif qilishi mumkin;
• parallel hisoblashlarni amalga oshiradi;
⚫ turli xil parametrli masalalarni yechish uchun yaroqli (asosiysi - mos keluvchi yaroqlilik funksiyasini berish).
GA ning salbiy jihatlari:
• "oddiy yaxshi yechim" - bu ayrim hollarda kamchilik; .izlash fazosida juda ko'p nuqtalar bu ham ayrim hollarda kamchilik;
. Masalani gen va xromosoma terminlarida qoʻyish ko'pchilik hollarda qulay emas.
GA qoʻllab yechiladigan masalalar bir butun spektr: NASA ni antennasini yaratishdan tortib to beloklarning strukturasini anglab yetadigan programmalarni ishlab chiqish.
GA moliyaviy ishlarda iqtisodiy agentlarni modellashtirish uchun samarali qoʻllanilmoqda. Qiziqarli masalalardan bittasi – moliyaviy portfelni optimallash (portfolio optimization). O'yinlar nazariyasida optimal strategiyani aniqlash uchun. Robototexnikada insonga o'xshagan robotlarni boshqarish uchun qoʻllanilmoqda, marshrutni rejalashtirishni optimallashtirish (routing) masalalarida. Samolyotsozlikda: General Electric va Rensselerovskiy politexnika
instituti olimlari GA ni zamonaviy avialaynerlarida qoʻllaniladigan reaktiv dvigatelning turbinasini konstruksiyasini ishlab chiqishga tadbiq etishdi. Ishlab chiqarish sohasida ishlab chiqarishni rejalashtirish jadvalini tuzishda, yirik ta'lim muasasalarida oʻquv jarayonini rejalashtirishda. GA ning imkoniyatlari ijodiy ishlar uchun cheki yo'q.
Download 64.78 Kb.

Do'stlaringiz bilan baham:




Ma'lumotlar bazasi mualliflik huquqi bilan himoyalangan ©fayllar.org 2024
ma'muriyatiga murojaat qiling