Matematika-informatika fakulteti amaliy matematika va informatika kafedrasi amaliy matematika yo

10.1. Genetik algoritmlarnig qo’llaniladigan masalalari
Genetik algoritmlar Hozirgi vaqtda qidiruv va optimallashtirish muammolarini hal qilish bilan bog'liq intellektual ma'lumotlarni qayta ishlashning istiqbolli va dinamik rivojlanayotgan sohasini ifodalaydi.
Genetik algoritmlarning ko'lami juda keng. Ular biznes va muhandislikni rivojlantirishda bir qator yirik va iqtisodiy ahamiyatga ega vazifalarni hal qilishda muvaffaqiyatli qo'llaniladi. Ularning yordami bilan sanoat dizayn echimlari ishlab chiqildi, bu esa millionlab dollarlarni tejash imkonini berdi. Moliyaviy kompaniyalar qimmatli qog'ozlar paketlarini boshqarishda moliyaviy bozorlarning rivojlanishini bashorat qilish uchun ushbu vositalardan keng foydalanadilar. Evolyutsion hisoblashning boshqa usullari bilan bir qatorda, genetik algoritmlar odatda yuqori o'lchamli modellarning uzluksiz parametrlarining qiymatlarini baholash, kombinatsion muammolarni hal qilish va uzluksiz va diskret parametrlarni o'z ichiga olgan modellarni optimallashtirish uchun ishlatiladi. Qo'llashning yana bir sohasi - yirik ma'lumotlar bazalaridan yangi bilimlarni olish, stokastik tarmoqlarni yaratish va o'qitish, neyron tarmoqlarni o'rgatish, ko'p o'lchovli statistik tahlil muammolarida parametrlarni baholash, boshqa qidiruv va optimallashtirish algoritmlari uchun dastlabki ma'lumotlarni olish tizimlarida foydalanish. .
Asosiy ta'riflar va xususiyatlar
Tasodifiylik elementlariga ega qidiruv usullarining bir turi bo'lgan genetik algoritmlar muammoning optimal echimini emas, balki mavjud bo'lganiga nisbatan eng yaxshi echimni topishga qaratilgan. Buning sababi shundaki, murakkab tizim uchun ko'pincha hech bo'lmaganda qoniqarli echimni topish talab qilinadi va optimalga erishish muammosi orqa fonda qoladi. Shu bilan birga, muammoning o'ta murakkabligi tufayli aniq optimal echimni topishga qaratilgan boshqa usullar umuman qo'llanilmaydi. Bu genetik algoritmlarning paydo bo'lishi, rivojlanishi va mashhurligining o'sishiga sababdir. Garchi, boshqa har qanday qidiruv usuli kabi, bu yondashuv har qanday muammolarni hal qilishning optimal usuli emas. Ushbu algoritmlarning qo'shimcha xususiyati odamning rivojlanayotgan qidiruv jarayoniga aralashmasligi hisoblanadi. Biror kishi ma'lum parametrlarni o'rnatish orqali unga faqat bilvosita ta'sir qilishi mumkin.
Agar an'anaviy usullardan asosiy farqlarini hisobga olsak, genetik algoritmlarning afzalliklari yanada oydinlashadi. To'rtta asosiy farq bor.
Genetik algoritmlar maqsad funksiyasining argumentlariga bevosita bog'liq bo'lgan parametrlar to'plamini ifodalovchi kodlar bilan ishlaydi. Bundan tashqari, ushbu kodlarning talqini faqat algoritm boshlanishidan oldin va natijani olish uchun uni tugatgandan keyin sodir bo'ladi. Ish jarayonida kodlar bilan manipulyatsiyalar ularning talqinidan butunlay mustaqil ravishda amalga oshiriladi, kod oddiygina bit satr sifatida ko'rib chiqiladi.
Qidiruv uchun genetik algoritm bir vaqtning o'zida qidiruv maydonining bir nechta nuqtalarini ishlatadi va an'anaviy usullarda bo'lgani kabi nuqtadan nuqtaga o'tmaydi. Bu ularning kamchiliklaridan birini - agar u unimodal bo'lmasa, ya'ni bir nechta shunday ekstremallarga ega bo'lsa, maqsad funktsiyasining mahalliy ekstremumiga tushib qolish xavfini bartaraf etishga imkon beradi. Bir vaqtning o'zida bir nechta nuqtadan foydalanish bu imkoniyatni sezilarli darajada kamaytiradi.
Genetik algoritmlar ish jarayonida hech qanday qo'shimcha ma'lumotdan foydalanmaydi, bu esa ish tezligini oshiradi. Foydalanadigan yagona ma'lumot parametrlarning maqbul qiymatlari maydoni va ixtiyoriy nuqtadagi maqsad funktsiyasi bo'lishi mumkin.
Genetik algoritm yangi tahlil nuqtalarini yaratish uchun ham ehtimollik qoidalaridan, ham bir nuqtadan ikkinchisiga o'tish uchun deterministik qoidalardan foydalanadi. Yuqorida aytib o'tilganidek, tasodifiylik va determinizm elementlarini bir vaqtda qo'llash alohida foydalanishga qaraganda ancha katta samara beradi.
Genetik algoritmning ishlashini bevosita ko'rib chiqishdan oldin, biz ushbu sohada keng qo'llaniladigan bir qator atamalarni kiritamiz.
Yuqorida genetik algoritm semantik talqinidan qat'iy nazar kodlar bilan ishlashi ko'rsatilgan. Shuning uchun kodning o'zi va uning tuzilishi kontseptsiya bilan tavsiflanadi genotip, va uni hal qilinayotgan muammo nuqtai nazaridan, tushuncha bilan talqin qilish - fenotip. Har bir kod, aslida, qidiruv maydonidagi nuqtani ifodalaydi. Biologik atamalarga imkon qadar yaqinroq bo'lish uchun kodning nusxasi xromosoma, individ yoki individ deb ataladi. Quyida biz asosan " atamasidan foydalanamiz. individual".
Ishning har bir bosqichida genetik algoritm bir vaqtning o'zida bir nechta qidiruv nuqtalaridan foydalanadi. Bu nuqtalar to'plami individlar to'plami bo'lib, u populyatsiya deb ataladi. Populyatsiyadagi individlar soni populyatsiya soni deyiladi; Ushbu bo'limda biz klassik genetik algoritmlarni ko'rib chiqayotganimiz sababli, populyatsiya miqdori qat'iy va genetik algoritmning xususiyatlaridan birini ifodalaydi, deb aytishimiz mumkin. Ishning har bir bosqichida genetik algoritm yangi shaxslarni yaratish va keraksizlarni yo'q qilish orqali populyatsiyani yangilaydi. Har bir bosqichdagi populyatsiyalarni va bosqichlarning o'zlarini farqlash uchun ular avlodlar deb ataladi va odatda raqam bilan belgilanadi. Masalan, algoritmning birinchi bosqichidan keyin dastlabki populyatsiyadan olingan populyatsiya birinchi avlod bo'ladi, keyingi bosqichdan keyin - ikkinchi va hokazo.
Algoritmning ishlashi davomida ko'payish jarayonini simulyatsiya qilish asosida yangi shaxslarning avlodi sodir bo'ladi. Bunda, albatta, tug'diruvchi shaxslar ota-onalar, hosil bo'lganlar esa avlodlar deb ataladi. Ota-ona juftligi odatda bir juft nasl tug'diradi. Ikki tanlanganidan to'g'ridan-to'g'ri yangi kod satrlarini yaratish ish tufayli sodir bo'ladi kesib o'tish operatori, bu ham krossover deb ataladi (ingliz tilidan, krossover). Yangi populyatsiyani yaratishda krossover operatori barcha ota-onalar juftligiga qo'llanilmasligi mumkin. Ushbu juftlarning ba'zilari to'g'ridan-to'g'ri keyingi avlod populyatsiyasiga o'tishi mumkin. Bu holat qanchalik tez-tez sodir bo'lishi genetik algoritmning parametrlaridan biri bo'lgan kesishish operatorini qo'llash ehtimoli qiymatiga bog'liq.
Ish tufayli yangi shaxslarning mutatsiya jarayonini simulyatsiya qilish amalga oshiriladi mutatsiya operatori. Mutatsiya operatorining asosiy parametri ham mutatsiya ehtimoli hisoblanadi.
Populyatsiya soni qat'iy bo'lganligi sababli, naslning paydo bo'lishi boshqa individlarning yo'q qilinishi bilan birga bo'lishi kerak. Nasl etishtirish uchun populyatsiyadan ota-onalarning juftlarini tanlash hosil beradi tanlash operatori, va yo'q qilish uchun shaxslarni tanlash - kamaytirish operatori. Ularning ishining asosiy parametri, qoida tariqasida, ushbu shaxs tomonidan tasvirlangan qidiruv maydonidagi nuqtadagi maqsad funktsiyasining qiymati bilan belgilanadigan shaxsning sifati.


xi-bob. qarorlar daraxtining amaliy tadbiqlari.