Mavzu: Genetik algoritmning bazaviy tuzilishi. Genetik algoritmlar yordamida masalalarni yechish reja

Gradientga asoslangan usullarning muvaffaqiyatsizligi
An'anaviy hisob-kitoblarga asoslangan usullar tasodifiy nuqtadan boshlab va tepalikning tepasiga etgunimizcha gradient yo'nalishi bo'yicha harakat qilish orqali ishlaydi. Ushbu uslub samarali va chiziqli regressiyadagi xarajat funksiyasi kabi bir darajali maqsad funktsiyalari uchun juda yaxshi ishlaydi. Ammo, ko'pgina real vaziyatlarda bizda ko'plab cho'qqilar va ko'plab vodiylardan tashkil topgan landshaftlar deb ataladigan juda murakkab muammo bor, bu esa bunday usullarning muvaffaqiyatsiz bo'lishiga olib keladi, chunki ular mahalliy optimaga yopishib qolish tendentsiyasidan aziyat chekadi. quyidagi rasmda ko'rsatilganidek.

Tezda yaxshi yechim topish
Sayohatchi sotuvchi muammosi (TSP) kabi ba'zi qiyin muammolar yo'l topish va VLSI dizayni kabi haqiqiy ilovalarga ega. Endi tasavvur qiling-a, siz GPS navigatsiya tizimidan foydalanmoqdasiz va manbadan manzilgacha bo'lgan "optimal" yo'lni hisoblash uchun bir necha daqiqa (hatto bir necha soat) kerak bo'ladi. Bunday real dunyo ilovalarida kechikish qabul qilinishi mumkin emas va shuning uchun "tezkor" yetkazib beriladigan "etarli darajada yaxshi" yechim talab qilinadi.


Genetik algoritmlar - asoslar
Ushbu bo'lim GAni tushunish uchun zarur bo'lgan asosiy terminologiya bilan tanishadi. Shuningdek, GA ning umumiy tuzilishi ham soxta kod, ham grafik shakllarda taqdim etilgan. O'quvchiga ushbu bo'limda keltirilgan barcha tushunchalarni to'g'ri tushunish va ushbu qo'llanmaning boshqa bo'limlarini o'qiyotganda ularni yodda tutish tavsiya etiladi.


Asosiy terminologiya
Genetik algoritmlar bo'yicha munozarani boshlashdan oldin, ushbu qo'llanma davomida qo'llaniladigan ba'zi bir asosiy terminologiya bilan tanishish kerak.

• 
  Populyatsiya - bu berilgan muammoning barcha mumkin bo'lgan (kodlangan) echimlarining kichik to'plami. GA uchun populyatsiya odamlar uchun populyatsiyaga o'xshaydi, bundan tashqari bizda odamlar o'rniga odamlarni ifodalovchi nomzodlik echimlari mavjud.
  

• 
  Xromosomalar - Xromosoma berilgan muammoning shunday yechimidir.
  

• 
  Gen - gen xromosomaning bir element pozitsiyasidir.
  

• 
  Allel - bu genning ma'lum bir xromosoma uchun oladigan qiymati.
  

• 
  Genotip - Genotip - hisoblash maydonidagi populyatsiya. Hisoblash maydonida echimlar hisoblash tizimi yordamida oson tushuniladigan va boshqarilishi mumkin bo'lgan tarzda taqdim etiladi.
  

• 
  Fenotip - Fenotip - bu haqiqiy dunyodagi echimlar makonidagi populyatsiya bo'lib, unda echimlar haqiqiy dunyo vaziyatlarida aks ettirilgan tarzda taqdim etiladi.
  

• 
  Dekodlash va kodlash - Oddiy muammolar uchun fenotip va genotip bo'shliqlari bir xil. Biroq, aksariyat hollarda fenotip va genotip bo'shliqlari boshqacha. Dekodlash eritmani genotipdan fenotip fazosiga aylantirish jarayonidir, kodlash esa fenotipdan genotip fazosiga o'tish jarayonidir. Dekodlash tez bo'lishi kerak, chunki u fitnes qiymatini hisoblash paytida GAda qayta-qayta amalga oshiriladi.
  

Masalan, 0/1 sumka muammosini ko'rib chiqing. Fenotip maydoni faqat tanlanishi kerak bo'lgan elementlarning raqamlarini o'z ichiga olgan echimlardan iborat.

Biroq, genotip fazosida u n uzunlikdagi ikkilik qator sifatida ifodalanishi mumkin (bu erda n - elementlarning soni). X pozitsiyasidagi 0 x-band tanlanganligini, 1 esa teskarisini bildiradi. Bu genotip va fenotip bo'shliqlari har xil bo'lgan holat.

• 
  Fitness funktsiyasi - Oddiygina aniqlangan fitnes funksiyasi yechimni kirish sifatida qabul qiladigan va chiqish sifatida yechimning mosligini ishlab chiqaradigan funktsiyadir. Ba'zi hollarda fitnes funktsiyasi va maqsad funktsiyasi bir xil bo'lishi mumkin, boshqalarida esa muammoga qarab farq qilishi mumkin.
  

• 
  Genetik operatorlar - bu naslning genetik tarkibini o'zgartiradi. Bularga krossover, mutatsiya, seleksiya va boshqalar kiradi.