|
§2.1 Genetik algoritmni kriptotahlilda umumiy qo‘llanilishi
Evolyutsion algoritmlarning ishlashining asosiy printsipi o‘zgaruvchanlik, merosxo‘rlik va eng munosib shaxslarni tanlash omillarini hisobga olgan holda, evolyutsion jarayonni kompyuterda modellashtirishga asoslangan. Optimallashtirish masalasini yechishda eng yaxshi yechimni topish uchun tasodifiy transformatsiyalar amalga oshiriladigan yechimlar to‘plami (populyatsiyasi) tuziladi. Populyatsiya selektsiya operatoridan foydalangan holda ota-onalarning shaxslarini tanlash va ularga gen mutatsiyasini va ota-ona genotiplarining rekombinatsiyasini taqlid qiluvchi tasodifiy operatorlarni qo‘llash (kesishish) orqali rivojlanadi. Maqsad funksiyasi (fitness funksiyasi) yoki fitness funksiyasi bilan belgilanadigan katta fitnes qiymatiga ega bo‘lgan shaxslar keyingi avlodda ko‘proq avlod olishadi. Kriptotahlil algoritmidan foydalanilgan holda, shaxs kalit uzunligiga teng uzunlikdagi ikkilik qator shaklida kalit hisoblanadi.
Qidiruv algoritm protsedurasini initsializatsiya qilish mumkin bo‘lgan yechimlar populyatsiyasini yaratishdir. Genetik algoritmning klassik versiyasi uchta asosiy bosqichdan iborat: tanlash, kesishish (o‘zaro faoliyat) va mutatsiyadan iborat. Keyingi avlodni, ya’ni naslni olish uchun eng yaxshi shaxslar tanlanganligi sababli, keyingi avlod oldingisiga qaraganda yaxshiroqdir. Mahalliy ekstremadan qochish uchun mutatsiya zarur. Algoritmning ishlashi natijasida fizikaviy funksiyalarning mumkin bo‘lgan yechimlarning diskret to‘plamida berilgan ekstremumi aniqlanadi.
Mumkin yechimlarni topish muammosida genetik algoritmdan foydalanish uchun, kriptotahlilda - shifr kaliti uchun, amalga oshiriladigan yechimlarni kodlash usulini, o‘tish va mutatsiyani o‘tkazish qoidalarini, selektsiya strategiyalarini tanlash, shuningdek fitness funksiyasi, global maksimal yoki minimal nuqtasi shifr kalitining kerakli qiymati bo‘ladi.
Genetik algoritm quyidagicha tuzilgan:
Dastlabki populyatsiyani initsializatsiya qilish (umumiy holda, uni ikkilik qatorlardan tasodifiy hosil qilish mumkin).
Chatishtirish. Amaldagi aholi vakillari, tanlov strategiyasiga muvofiq, juftlarni shakllantiradi va keyin kesib o‘tadi, ya’ni krossover operatori qo‘llaniladi. Klassik versiyada krossover bitta nuqtadan iborat. Ikkilik qatorlarning bo‘linish nuqtasi tanlanadi, avlodlar segmentlarni almashtirish orqali olinadi.
Yangi avlod shaxslarida ayrim genlarning mutatsiyasiga (inversiyasiga) ba’zi ehtimoli bor. Inversiya ehtimoli algoritm parametrlaridan biridir.
2-3 bosqichlar avlodlar sonining belgilangan parametriga yoki populyatsiya yaqinlashishiga qadar takrorlanadi, ya’ni populyatsiyaning barcha qatorlari ekstremum mintaqasida joylashgan va deyarli bir xil, ya’ni, o‘tish deyarli aholi sonini o‘zgartirmaydi va mutatsiyaga uchragan qatorlar keyingi avlodga kiritilmaydi, chunki ular unchalik moslashgan emas. Yakuniy qaror so‘nggi avlodning eng yaxshi satrlari bo‘ladi.
Fitnes funksiyasini tanlash usuli hal qilinayotgan muammoga bog‘liq. Masalan, Чернышев Ю.О., Сергеев А.С., Рязанов А.Н. kabi kriptotahlil olimlar o‘zlarining ilmiy ishlarida Vigenere almashtirish shifrining kriptotahlili uchun fitnes funksiyasi sifatida foydalangan[6][7]:
,
bu erda - faraz qilingan kalit yordamida shifrlanganidan so‘ng olingan matnda ikki harfli so‘zning ("bigram") paydo bo‘lish chastotasi; - bigramning o‘rtacha statistik mazmunli matnda paydo bo‘lish chastotasi, ular oldindan ma’lum yoki matnlarning statistik tahlili asosida hisoblanishi mumkin.
Boshqa vazifalarda, asl shifrlangan matndagi va tekshirilayotgan kalit bilan shifrlangan matndagi turli xil bitlarning soni fitness funksiyasi sifatida ishlatilishi mumkin.
Genetik algoritmning kamchiligi - bu monoton bo‘lmagan funksiya ekstremalini topish muammosi, ya’ni har bir nuqtada funksiya qiymati aslida tasodifiy o‘zgaruvchidir va unga yondashish haqida ma’lumot olish mumkin bo‘lmagan global ekstremum muammosidir.
Do'stlaringiz bilan baham: |
