13-ma'ruza. Genetik algoritmlar

5. Genetik algoritmlar va an'anaviy optimallashtirish usullari

GA - bu muammoni hal qilish usullarining tabiiy evolyutsiyasini va birinchi navbatda optimallashtirish muammolarini aks ettiruvchi usul hisoblanadi. GAlar - bu tabiiy tanlanish va merosxo'rlik mexanizmlariga asoslangan qidiruv protseduralaridan iborat bo’ladi. Ularda eng munosib xromosomalarning omon qolish evolyutsion prinsipidan foydalanadilar. GAlar an'anaviy optimallashtirish usullaridan bir necha asosiy elementlari bilan ajralib turadi. Xususan, GAlar [17]:

1. 
   masala prametrlarining berilgan boshlang’ich qiymatlarini emas, balki ularning kodlashtirilgan qiymatlarini qayta ishlaydi;
   
2. 
   echimni bitta nuqtadan emas, balki ularning ma'lum bir populyatsiyasidan qidirishni amalga oshiradi;
   
3. 
   maqsad funksiyasining hosilalari yoki boshqa qo'shimcha ma'lumotlaridan emas, balki faqat maqsad funksiyasining o’zidan foydalanadi;
   
4. 
   seleksiyada deterministik qoidalarni emas, balki ehtimolli qoidalarni qo’llaydi.
   

Parametrlarni kodlashtirish, populyatsiyalar ustida operatsiyalarni amalga oshirish, masala haqida minimal ma'lumotdan foydalanish va operatsiyalarning tasodifiy shakllanishini amalga oshirishda qatnashadigan to'rt xususiyat GAlarning barqarorligini va ularning keng qo'llaniladigan boshqa texnologiyalardan ustunligini belgilaydi [14].
13.3-misol. Quyidagi
f (x)  2x² 1
funksiya berilgan bo’lib, ^x o’zgaruvchi 0 dan 15 gacha bo'lgan butun sonli
qiymatlarni qabul qilsin. Bu funksiyani optimallashtirish masalasi ^{0, 1,...,15}
qiymatlardan iborat 16 ta nuqtalar fazosi bo’ylab harakat qilish natijasida ushbu funksiya maksimal (yoki minimal) qiymatga erishadigan nuqtani topishdan iborat.
Bu holda masala parametri sifatida ^x o'zgaruvchidan foydalaniladi. ^{0, 1,...,15}
to'plam qidiruv fazosini va shu bilan birga masalaning potentsial echimlari to'plamini tashkil etadi. Ushbu to'plamga tegishli 16 ta raqamning har biri qidiruv fazosining nuqtasi, echimi, parametr qiymati, fenotip deb nomlanadi. Shuni ta'kidlash kerakki funksiyani optimallashtiradigan echim eng yaxshi yoki optimal echim deb nomlanadi. ^x ning 0 dan 15 gacha bo'lgan parametr qiymatlarini
quyidagicha kodlashtirish mumkin:
0000 0001 0010 0011 0100 0101 0110 0111
1000 1001 1010 1011 1100 1101 1110 1111
Bu ikkilik tizimda o'nli raqamlarni yozish bilan bog'liq bo'lgan taniqli ikkilik kodlash uslubi hisoblanadi. Taqdim etilgan kodlar ketma-ketligi zanjirlar yoki xromosomalar deb nomlanadi. Ko'rib chiqilayotgan misolda ular genotip sifatida ham qaraladi. Xromosomalarning har biri 4 gendan iborat (yoki ikkilik ketma- ketliklar 4 bitdan iborat deyish mumkin). Genning ma'lum bir joydagi qiymati allel deb ataladi, bu holda allel 0 yoki 1 qiymatlarni oladi. Populyatsiya shu 16 xromosomalar orasidan tanlangan xromosomalardan iborat bo’ladi. Soni 6 ga teng
bo’lgan populyatsiyaga misoli sifatida, masalan quyidagi 2,5, 7,9,12,14
fenotiplarning kodlangan shakllari bo'lgan 0010, 0101, 0111,1001,1100,1110
xromosomalarning to’plamini qarash mumkin. Ushbu misolda MF (13.3) ifoda bilan berilgan. Populyatsiyadagi alohida xromosomalarning moslanuvchanligi funksiyaning ushbu xromosomalarga mos keladigan ^x qiymatlari bilan, ya'ni ba'zi genotiplarga mos keladigan fenotiplar uchun funksiyaning qiymati aniqlanadi.