2 Biologik talqin

Asosiy ta'riflar va xususiyatlar
Tasodifiylik elementlariga ega qidiruv usullarining bir turi bo'lgan genetik algoritmlar muammoning optimal yechimini emas, balki mavjud bo'lganiga nisbatan eng yaxshi yechimni topishga qaratilgan. Buning sababi shundaki, murakkab tizim uchun ko'pincha hech bo'lmaganda qoniqarli yechimni topish talab qilinadi va optimalga erishish muammosi orqa fonda qoladi. Shu bilan birga, muammoning o'ta murakkabligi tufayli aniq optimal yechimni 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.
1. 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.
2. 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.
3. 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.
4. 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.
Shunday qilib, biz genetik algoritmlar sohasida qo'llaniladigan asosiy tushunchalar va atamalarni sanab o'tishimiz mumkin:
genotip va fenotip;
shaxs va shaxsning sifati;
aholi va aholi soni;
avlod;
ota-onalar va avlodlar.
Genetik algoritmning xususiyatlari quyidagilardan iborat:
aholi soni;
kesishuvchi operator va undan foydalanish ehtimoli;
mutatsiya operatori va mutatsiya ehtimoli;
tanlash operatori;
qisqartirish operatori;
to'xtatish mezoni.
Seleksiya, krossover, mutatsiya va qaytarilish operatorlari genetik operatorlar deb ham ataladi.
Genetik algoritmning ishlashini to'xtatish mezoni uchta hodisadan biri bo'lishi mumkin:
Foydalanuvchi tomonidan belgilangan avlodlar soni yaratildi.
Populyatsiya foydalanuvchi tomonidan belgilangan sifatga erishdi (masalan, barcha shaxslarning sifat qiymati belgilangan chegaradan oshib ketdi).
Muayyan darajadagi yaqinlashuvga erishildi. Ya'ni, populyatsiyadagi individlar shu qadar o'xshash bo'lib qolganki, ularning keyingi yaxshilanishi nihoyatda sekin kechadi.
Genetik algoritmning xarakteristikalari shunday tanlanadiki, bir tomondan qisqa ishlash muddati, ikkinchi tomondan esa eng yaxshi yyechim izlanishi ta'minlanadi.