Genetik algoritmlarda xromosomalar optimallashtirish muammosining potentsial yechimlarini ifodalash uchun ishlatiladi. Har bir xromosoma genlar vektori bo'lib, har bir gen muammoda qaror o'zgaruvchisini ifodalaydi

O’ZBEKISTON RESPUBLIKASI AXBOROT TEXNOLOGIYALARI VA KOMMUNIKATSIYALARINI RIVOJLANTIRISH VAZIRLIGI
MUHAMMAD AL-XORAZMIY NOMIDAGI TOSHKENT AXBOROT TEXNOLOGIYALARI UNIVERSITETI QARSHI FILIALI

“ KOMPYUTER INJINERINGI ” FAKULTETI
4 – BOSQICH DI-13-19 GURUH TALABASINING
“Evolutsion algoritmlar”
FANIDAN TAYYORLAGAN

Amaliy ish №5


Bajardi: AXMEDOV I
Qabul qildi: Abdullayev R


QARSHI 2023

Genetik algoritmlarda xromosomalar optimallashtirish muammosining potentsial yechimlarini ifodalash uchun ishlatiladi. Har bir xromosoma genlar vektori bo'lib, har bir gen muammoda qaror o'zgaruvchisini ifodalaydi. Misol uchun, agar biz ikkita kirish o'zgaruvchisi bo'lgan funksiyani optimallashtirishga harakat qilsak, har bir potentsial yechimni ikkita genga ega xromosoma sifatida ko'rsatishimiz mumkin, bu erda har bir gen kirish o'zgaruvchilardan birining qiymatini ifodalaydi.

Genetik operatorlar yangi potentsial echimlarni yaratish uchun genetik algoritmda xromosomalarni manipulyatsiya qilish uchun ishlatiladi. Ikkita asosiy genetik operator mavjud: mutatsiya va krossover. Mutatsiya xromosomadagi bir yoki bir nechta genni tasodifiy o'zgartirishni o'z ichiga oladi, krossover esa ikkita ota-ona xromosomasini birlashtirib, yangi nasl xromosomasini yaratadi.

Eggholder funksiyasi optimallashtirish algoritmlari uchun tez-tez ishlatiladigan test funktsiyasidir. Bu bir nechta mahalliy minimal va maksimallarga ega bo'lmagan qavariq funksiya bo'lib, uni optimallashtirishni qiyinlashtiradi. Funktsiya ikkita kirish o'zgaruvchisi x va y uchun aniqlanadi va uning qiymati quyidagicha ifodalanadi:

f(x,y) = -(y + 47) * sin(sqrt(abs(x/2 + (y + 47))))) - x * sin(sqrt(abs(x - (y + 47)) )

Haqiqiy raqamlar muammolari uchun genetik algoritm yordamida ushbu funktsiyani optimallashtirish uchun biz birinchi navbatda potentsial echimlarni haqiqiy sonlarning xromosomalari sifatida kodlashimiz kerak. Buning usullaridan biri har bir kirish o'zgaruvchisini pastki va yuqori chegara orasidagi haqiqiy son sifatida ko'rsatish va har bir raqamni ifodalash uchun belgilangan bitlar sonini ishlatishdir.

Keyinchalik, har bir potentsial yechim qanchalik yaxshi ekanligini o'lchaydigan genetik algoritm uchun fitnes funktsiyasini aniqlashimiz kerak. Eggholder funksiyasi bo'lsa, fitnes funktsiyasi funktsiya qiymatining manfiy qiymati bo'ladi, chunki biz funktsiyani minimallashtirishni xohlaymiz.

Potentsial yechimlarni kodlab, fitnes funksiyasini aniqlaganimizdan so‘ng, yangi potentsial yechimlarni yaratish uchun genetik operatorlarni qo‘llashimiz mumkin. Masalan, xromosomadagi bir yoki bir nechta genlarning qiymatini tasodifiy o'zgartirish uchun mutatsiyadan foydalanishimiz va yangi nasl xromosomasini yaratish uchun ikkita ota-ona xromosomasini birlashtirish uchun krossoverdan foydalanishimiz mumkin.

Biz maksimal takrorlashlar soni yoki fitnes funksiyasini yaxshilashning minimal darajasi kabi tugatish shartiga erishmagunimizcha, yangi potentsial yechimlarni yaratish uchun ushbu genetik operatorlardan foydalanishni davom ettirishimiz mumkin. Shu nuqtada biz optimallashtirish muammosining optimal yechimi sifatida eng yaxshi potentsial yechimni tanlashimiz mumkin.
Genetik algoritmlarda tanlash jarayoni algoritmning muhim qismi hisoblanadi. Tanlashning maqsadi yangi nasl xromosomalarini yaratish uchun ota-onalar sifatida qanday potentsial echimlardan foydalanishni tanlashdir. Ruletka g'ildiragini tanlash, turnir tanlash va daraja tanlash kabi bir nechta tanlov usullari mavjud.

Ruletka g'ildiragini tanlashda potentsial echimlar ularning fitnes qiymatiga proportsional ehtimollik bilan tanlanadi. Boshqacha qilib aytganda, fitnes qiymati yuqori bo'lgan echimlar ota-ona sifatida tanlanish ehtimoli yuqori.

Turnirni tanlashda potentsial echimlarning tasodifiy kichik to'plami tanlanadi va eng yuqori fitnes qiymatiga ega bo'lgan yechim ota-ona sifatida tanlanadi. Bu jarayon ikkinchi ota-onani tanlash uchun takrorlanadi.

Darajani tanlashda potentsial yechimlar ularning yaroqlilik qiymatiga qarab tartiblanadi va keyin ularning darajasiga proportsional ehtimollik bilan tanlanadi. Bu usul ruletka g'ildiragini tanlashga o'xshaydi, lekin u barcha potentsial echimlarning, hatto ularning fitnes qiymati nisbatan past bo'lsa ham, nolga teng bo'lmagan tanlanish ehtimoliga ega bo'lishini ta'minlaydi.

Ushbu tanlash usullaridan tashqari, genetik algoritmlarning ishlashini yaxshilash uchun ishlatilishi mumkin bo'lgan ko'plab boshqa usullar ham mavjud. Misol uchun, elitizm hozirgacha topilgan eng yaxshi yechim har doim potentsial yechimlarning keyingi avlodiga kiritilishini ta'minlash uchun ishlatilishi mumkin. Moslashuvchan mutatsiya va krossover stavkalari algoritmning ishlashi asosida ushbu operatorlarning ehtimolini sozlash uchun ishlatilishi mumkin. Nihoyat, parallelizatsiya genetik algoritmning bir nechta nusxalarini bir vaqtning o'zida turli protsessorlar yoki kompyuterlarda ishga tushirish orqali optimallashtirish jarayonini tezlashtirish uchun ishlatilishi mumkin.

Umuman olganda, genetik algoritmlar optimallashtirishning keng doiradagi muammolarini, shu jumladan qavariq bo'lmagan va ko'p modal maqsad funktsiyalariga ega bo'lgan muammolarni hal qilish uchun ishlatilishi mumkin bo'lgan kuchli optimallash usulidir. Genetik operatorlar va tanlash usullarining kombinatsiyasidan foydalangan holda, genetik algoritmlar qidiruv maydonini samarali o'rganishga va murakkab optimallashtirish muammolariga optimal echimlarni topishga qodir.

Genetik algoritmlarning afzalliklaridan biri ularning bir vaqtning o'zida bir nechta maqsadlarni bajarish qobiliyatidir, bu ko'p maqsadli optimallashtirish deb nomlanadi. Ko'p maqsadli optimallashtirishda bir vaqtning o'zida optimallashtirish kerak bo'lgan bir nechta qarama-qarshi maqsadlar mavjud bo'lib, ular an'anaviy optimallashtirish usullaridan foydalangan holda qiyin bo'lishi mumkin. Genetik algoritmlar Pareto-optimal to'plam deb nomlanuvchi bir nechta maqsadlarga nisbatan optimal bo'lgan echimlar to'plamini topish uchun ishlatilishi mumkin.

Genetik algoritmlarni ko'p maqsadli optimallashtirish masalalariga qo'llash uchun asosiy algoritmga o'zgartirishlar kiritilishi kerak. Ommabop yondashuvlardan biri NSGA-II (Dominated Sorting Genetic Algoritm II) deb nomlanadi. Ushbu algoritm potentsial echimlarni hukmronlik munosabatlariga qarab bir nechta jabhalarga ajratadi. Yechim hech bo'lmaganda bitta maqsadda boshqa yechimdan yaxshiroq bo'lsa va boshqa hech qanday maqsadda yomon bo'lmasa, boshqa yechim ustunlik qiladi. Jabhalar shunday tartiblanganki, birinchi jabhadagi yechimlarda boshqa yechimlar, ikkinchi jabhadagi yechimlar birinchi jabhadagi yechimlar ustunlik qilmaydi va hokazo.

Keyin NSGA-II birinchi jabhadan aholi soniga yetguncha potentsial echimlarni tanlaydi. Agar birinchi jabha populyatsiyani to'ldirish uchun etarlicha katta bo'lmasa, ikkinchi frontdan echimlar ham tanlanadi va to populyatsiya to'lguncha davom etadi. Keyin tanlangan yechimlar krossover va mutatsiya operatorlari yordamida yangi nasl xromosomalarini yaratish uchun ota-ona sifatida ishlatiladi.

Yangi nasl tug'ilgandan so'ng, NSGA-II ota-onalar va nasllarning umumiy populyatsiyasini yana jabhalarga ajratadi va jarayon to'xtash sharti bajarilmaguncha takrorlanadi. Olingan yechimlarning yakuniy to'plami Pareto-optimal to'plam bo'lib, u qarama-qarshi maqsadlar o'rtasidagi eng yaxshi kelishuvni ifodalaydi.

Ko'p maqsadli optimallashtirishdan tashqari, genetik algoritmlarni optimallashtirish muammolaridagi cheklovlarni hal qilish uchun ham kengaytirish mumkin. Mashhur yondashuvlardan biri penalty funktsiyasi usuli sifatida tanilgan, bunda har bir buzilgan cheklov uchun fitnes funksiyasiga jazo qo'shiladi. Bu genetik algoritmni cheklovlarni qondiradigan echimlarni topishga undaydi va shu bilan birga maqsad funktsiyasini optimallashtiradi. Yana bir yondashuv cheklovlarni boshqarish texnikasi sifatida tanilgan bo'lib, cheklovlarni buzadigan potentsial echimlar ota-onalar sifatida tanlanmasligini ta'minlash uchun tanlov jarayonini moslashtiradi.