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

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

1. 
   Genetik algoritmlar nima?
   
2. 
   Genetik algoritmlarning afzal tomonlari.
   
3. 
   Genetik algoritmlarning chegaralari.
   
4. 
   Genetik algoritmlarning asoslari.
   
5. 
   Asosiy tuzilmasi.
   

Genetik algoritmlar - Kirish
Genetik algoritm (GA) genetika va tabiiy tanlanish tamoyillariga asoslangan qidiruvga asoslangan optimallashtirish usulidir. U tez-tez hal qilish uchun umr bo'yi kerak bo'lgan qiyin muammolarga optimal yoki deyarli optimal echimlarni topish uchun ishlatiladi. U tez-tez optimallashtirish muammolarini hal qilish, tadqiqot va mashinani o'rganishda qo'llaniladi.

Optimallashtirishga kirish

Optimallashtirish - bu biror narsani yaxshiroq qilish jarayoni. Har qanday jarayonda biz quyidagi rasmda ko'rsatilganidek, kirishlar va chiqishlar to'plamiga egamiz.

Optimallashtirish kirishlar qiymatlarini shunday topishni anglatadiki, biz “eng yaxshi” chiqish qiymatlarini olamiz. "Eng yaxshi" ta'rifi muammodan muammoga farq qiladi, lekin matematik nuqtai nazardan, u kirish parametrlarini o'zgartirish orqali bir yoki bir nechta maqsadli funktsiyalarni maksimallashtirish yoki minimallashtirishni anglatadi.

Kirishlar olishi mumkin bo'lgan barcha mumkin bo'lgan echimlar yoki qiymatlar to'plami qidiruv maydonini tashkil qiladi. Ushbu qidiruv maydonida optimal echimni beradigan nuqta yoki nuqtalar to'plami yotadi. Optimallashtirishning maqsadi qidiruv maydonida ushbu nuqta yoki nuqtalar to'plamini topishdir.

Genetik algoritmlar nima?
Tabiat har doim butun insoniyat uchun ajoyib ilhom manbai bo'lib kelgan. Genetik algoritmlar (GA) tabiiy tanlanish va genetika tushunchalariga asoslangan qidiruvga asoslangan algoritmlardir. GA evolyutsion hisoblash deb nomlanuvchi hisoblashning ancha katta tarmog'ining kichik to'plamidir.

GA Jon Holland va uning talabalari va Michigan universitetidagi hamkasblari, ayniqsa Devid E. Goldberg tomonidan ishlab chiqilgan va shu vaqtdan boshlab turli xil optimallashtirish muammolari ustida yuqori muvaffaqiyat bilan sinab ko'rilgan.

GAlarda bizda berilgan muammoning mumkin bo'lgan yechimlari puli yoki populyatsiyasi mavjud. Keyin bu eritmalar rekombinatsiya va mutatsiyaga uchraydi (tabiiy genetikada bo'lgani kabi), yangi bolalar hosil qiladi va jarayon turli avlodlarda takrorlanadi. Har bir shaxsga (yoki nomzod yechimga) yaroqlilik qiymati (maqsad funksiyasi qiymatidan kelib chiqqan holda) tayinlanadi va mosroq shaxslarga ko'proq moslashish va ko'proq "bardoshli" shaxslarni berish imkoniyati beriladi. Bu Darvinning "Eng kuchlilarning omon qolishi" nazariyasiga mos keladi.

Shunday qilib, biz to'xtatish mezoniga erishgunimizcha, avlodlar davomida yaxshiroq shaxslarni yoki echimlarni "rivojlantiramiz".

Genetik algoritmlar tabiatan etarlicha tasodifiydir, lekin ular tasodifiy mahalliy qidiruvga qaraganda ancha yaxshi ishlaydi (bunda biz har xil tasodifiy echimlarni sinab ko'ramiz, hozirgacha eng yaxshisini kuzatib boramiz), chunki ular tarixiy ma'lumotlardan ham foydalanadilar.