Mövzu 11: evolyusion hesablamalar
Yüklə 30,15 Kb.
|
- Bu səhifədəki naviqasiya:
- 2. Evolyusion strategiyalar
- 3. Evolyusion proqramlaşmanın tətbiqi aspektləri
|
MÖVZU 11: EVOLYUSİON HESABLAMALAR Plan 1. Abstrakt evolusion alqoritm 2. Evolusion strategiyalar 3. Evolusion proqramlaşmanın tətbqi aspektləri 1. Abstrakt evolusion alqoritm Evolyuion hesablamalar süni intellektin çətinliklə formalizə olan məsələlərindən başqa (surətlərin tanınması, klasterizasiya) optimallaşdırmanın, approksimasiyanın, verilənlərin intellektual işləniməsi məsələlərində öz səmərəliliyini sübut etmişdir. Evolusion hesablamaların üstünlüklərinə adaptivlik, öyrənməyə qabiliyyət, parallelizm, hibrid intellektual sistemlərin qurulması imkanı aiddir. Nəzərə alaraq ki, evolyusion hesablamalar konsepsiyası təbii ebolyusiya prosesinin bəzi formalizə edilmiş prinsipləri üzərində qurulmalıdır, evolyusion modelləşdirmənin əsas formalarının metodoloji fərqləri və tətbiq sferaları haqqında suallar meydana gəlir. Evolyusion alqoritmələrin məlum formalarının müqayisə təhlilinin nəticələri onlar arasında müəyən metodoloji fərqlər göstərdi. Bu fərqlər məqsədi funksiya və alternativ həllərin təqdimat formalarına, rekombinasiya, mutasiya operatorları və onların istifadə ehtimallarına, selektiv seçim strategiyalarına aiddir. Lakin evolyusiya hesablamalarının müxtəlif formaları arasında metodoloji fərqlər baza postulatları – universallıq və fundamentallıq – haqqında danışmağa imkan verir. Göstərilən ümumilik abstrakt evolyusion alqoritmin bu sxemi ilə ifadə oluna bilər: 1. Evolyusiyanın prametrlərinin qeydi; 2.P(0) ilkin populyasiyanın qeydi; 3. t:=0;
4. Populyasiyaya daxil olan həllərin qiymətlənməsi; 5. t:=t+1; 6. Seleksiya; 7. Replikasiya (təkrar, kopyalama); 8. Variasiya; 9. Varis həllərin qiymətlənməsi; 10. P(t) yeni populyasiyan ın təşkili; 11. t parametrin tmax verilmiş qiymətinə çatmasına qədər alqoritmin yerinə yetirilməsi; 12. Nəticələr. Evolyusion alqoritmin praktiki əhəmiyyəti vənəticəviliyinin həlledici göstəricisi kimi surət və axtarışın davamlılığıdır. Evolyusion alqoritmlərinin üsnünlükləri və çatışmazlıqları. Üsnünlükləri:
Çatışmazlıqlar:
Beləliklə, təhlil göstərir ki, evolyusion hesablamalar aşağıdakı məsələlər üçün yararlı deyil: qlobal optimumun tapılması məsələsi; müstəqil dəyişənlərdən asılı olan həll; epistaziyanın (bir dəyişən digərini üstünləyir) yüksək dərəcəsi; optimumun istisna olunması ilə məqsəd funksiyasının bütün nöqtələrdə qiymətlərinin nisbətən eyni olması. Yararlı hesab edilən aşağıdakı məsələlərdir: multimodal məqsəd funsiyaları ilə çoxölçülü optimallaşdırma məsələləri; stoxastik və dinamik məsələlər; kombinator optimallaşdırma məsələləri; proqnozlaşdırma və tanıma məsələləri. 2. Evolyusion strategiyalar Evolyusion hesablamalarda elitizm, müxtəliflik, “təzə qan”, populyasiyanın ölçüsünün dəyişdirilməsi, parallel evolyusiya (miqrasiya, turnir) strategiyalarını seçmək olar. Daha çox yayımlanan və istifadə edilən – elitizm strategiyasıdır. Onun məğzi evolusion prosesin bütün mərhələlərində populyasiyanın ən yaxşı nümayəndələr təbəqəsinin saxlanılmasıdır. Hesab edilir ki, nümayəndə nə qədər yaxşı olsa, o qədər onun faydalı genetik materialı daşımasının ehtimalı optimumun tapılması üçün yüksək olar. Beləliklə, elitizm strategiyasının istifadəsi yeni nəsilin formalaşması zamanı populyasiyadan ən yaxşı nümayəndələrin silinməsi imkanını istisna edir. Elit qrupun ölçüsü, qayda olaraq, populyasiyanın ümumi sayından asılıdır. Alqoritmin işi prosesində qeyd etmək lazımdır ki, elit qrupun nümayəndələri eyni və ya oxşar genotiplərə не вырождались. Bu problemin həllinə evolyusion alqorimlərdə populyasiyanın müxtəliflik strategiyasından istifadə dəstəklənir. Bunun zəruriyyəti evolyusion operatorlarının tətbiqi zamanı bir neçə oxşar və ya identik nümayəndələrin alınması imkanı ilə şərtlənib. Bu isə öz növbəsində belə nümayəndələrin genetik informasiyanın mənbələri olmasına gətirib çıxarır ki, bununla həll sahəsi daralır. Texniki olaraq bu strategiya evolyusiya prosesinin hər mərhələsində və ya hansısa verilmiş dövrlə Hemminq məsafəsi əsasında populyasiyanın bütün nümayəndələrinin yaxınlıq qiymətinin verilməsi ilə realizə edilir. Verilmiş müəyyən sərhəd qiymətindən aşağı qiymətləndirilən bir neçə nümayəndə arasında oxşarlığın mövcudluğunda onların arasında yalnızı biri - ən yaxşısı- qalır. Vakant yerlər evolyusiyanın cari mərhələsində tətbiq edilən nəticə əsasında və ya zəruriyyət olarsa təsadüfi həllərlə alınan varislərlə doldurulur. Müxtəliflik strategiyasının istifadəsi populyasiyada oxşar və ya eyni nümayəndələrin əmələ gəlməsi problemini həll edir, lakin yenə də elə situasiya yarana bilər ki, cari nəsilin bütün nümayəndələri həll fəzasının kifyət qədər dar çərçivəsində olacaq, bu da yeni nəsilin nümayəndələrinin bu fəzaya mənsubiyyətinə gətirib çıxaracaq. Bununla bağlı “yeni qan” srategiyası daha böyük səmərə verir. Bu strategiya populyasiyanın yeni nəsilinə valideyn qrupunun yerinə yeni, təsadüfən seçilmiş nümayəndələrin daxilindən ibarətdir. Prosedur nəsillər arasında verilmiş intervalla sistematik və ya evolyusiyanın istənilən mərhələsində müəyyən kiçik ehtimalla yerinə yetirilə bilər. “Yeni qan” strategiyasının elitizm strategiyası arasında ziddiyyət olmamalıdır, bunun üçün istisna edilən valideyn nümayəndələrinin arasında elitar olanlarının yeri yoxdur. Populyasiyanın ölçüsünün dəyişilməsi strategiyası evolyusiyanın hər mərhələsində iştirak edən nümayəndələrin sayının qeyri-sabit olmasını nəzərə alır. Nümayəndələrin sayı populyasiyanın ümumilkdə xarakteristikalarının keyfiyyətindən asılı olaraq dəyişə bilər. Belə xarakterstikalar qismində populyasiyanın orta uyğunluğu və ya evolyusiya mərhələlərinin nisbətən az sayı zamanı onun dəyişilməsi çıxış edə bilər. Populyasiyanın alt və üst sərhədləri və nümayəndələrin ilkin sayı qeyd olunmalıdır. Parallel evolyusiyalar strategiyaları qrupu canlı təbiətdə və ya ictimai həyatda yer tutan analogiyaların realizasiyasına yənəldilib. Belə strategiyaların ümumi prinsipi – müstəqil və ya bir-birindən az asılıolan birliklərin seçilməsidir. Sonradan bir qrupdan digərinə informasiyanın ötürülməsi və ya onların birləşmələri yerinə yetirilir. Bu qrupa miqrasiya və ya turnir strategiyaları aiddir. Miqrasiya strategiyasının realizasiyası zamanı bütün populyasiya müxtəlif saylı birliklərə bölünür. Krossover operatorları yalnız öz birliklərindən seçilmiş nümayəndələrə tətbiq olunur. Ayrı-ayrı nümayəndələrə mutasiya və inversiya operatorlarıda tətbiq olunur. Əsas kütlədə evolyusiyalar birlik çərçivəsində baş verir. Yalnız bəzi təsadüflərdə və kiçik ehtimalla birliklər arası ayrı-ayrı nümayəndələrin genetik material mübadiləsi baş verir. Evolyusiya dövrü ən yaxşı həllər bankı yığılır ki, onlar sonra vahid populyasiyaya birləşir. Turnir strategiyası bir neçə qrupda tam müstəqil və sona qədər yetirilmiş evolyusiya proseslərinin keçirilməsinin və hər qrupda ən yaxşı həllərin birlşməsinin aparılmasını nəzərdə tutur. Mərhələlərin sayı ümumi halda ixtiyari ola bilər və yalnız zaman tələbləri və tədqiqatçının hesablama imkanları ilə məhdudlaşır. Təbiidirki, mərhələlər nə qədər çox olarsa qlobal optimumun tapılması ehtimalı da çox olar.
İdiyəkimi biz nəzərdə tutmuşduq ki, μ valideynlərdən ibarət olan populyasiya μ varis yaradır, bu da optimizasiyanın unimodal funksiyalarında EP-nın surətinə müsbət təsir göstərir. Lakin bir çox praktiki məsələlər kombinatpr təbiətlidir, məqsəd funksiyanın dəyişənləri isə diskretdir. Onlar üçün mutasiya proseduru tətbiq olunmazdır. Xüsusi olaraq, NP-tam kombinator problemləri üçün EA-in testdən keçirilmənin obyektiv vasitələrindən biri kommivoyajor haqqında məsələdir ki, 100 şəhənin nəzərdən keçirilməsini nəzərdə tutur. Həllər populyasiyasında hər bir nümayəndə şəhərin nömrəsini təyin edən 1-dən 100-ə kimi yer dəyişməni kodlaşdırılır. İlkin populyasiya təsadüfi seçilən 50 yer dəyişmədən ibarətdir. Müvafiqlik funksiyası kommivoyajor tərəfindən bütün şəhərlərin nəzərdən keçirilmənizamı ilə verilən dövrün uzunluğu kimi təyin edilir. Mutasiya operatoru iki şəhərin yer dəyişməsini təsadüfi nəzərdə tutur. Belə yolla alınan 50 varis və 50 valideyn 5 təsadüfən seçilmiş kontragentlə yarışır. Aydındır ki, belə yarışmada hər bir nümayəndə maksimum 5 qələbə əldə edə bilər, və hətta ən zəif nümayəndənin də qələbə əldə etmək imkanı var. EP-nın agentlərin intellektual davranışlarının modelləşdirilməsində də uğurludur. EA-rın bu cür problemlərinin obyektiv test vasitəsi kimi oyunlar nəzəriyyəsinin “məhbuslar dilemması” adlanan klassik məsələsi çıxış edir. Bu məsələ konflikt situasiyanın yaxşı modelidir ki, burada oyunçuların maraqları müxtəlif olsa da antaqonistik deyildir. Oyunçular qismində cinayətin törənməsində ittiham olunan iki məhbusdur. Bilavasitə dəlil olmadıqda onların məhkumiyyət imkanı əhəmiyyətli dərəcədə onların susmaq və ya danışmaqlarından asılıdır. Əgər hər ikisi danışacaqsa hər ikisinin cəzası 1 il təşkil edəcək. Əgər hər ikisi etiraf edəcəksə cəza 3 il təşkil edəcək (etiraf yüngülləşdirici şərt kimi hesab olunacaq). Əgər məhbuslardan yalnız biri danışacaqsa, o azad olunacaq, susan isə maksimal cəza – 5 il – alacaq. Bu konflikt situasiya belə bir oyuna gətirir ki, burada oyunçuların hər birinin iki strategiyası var – susmaq (S) və ya danışmaq (D). Oyunçuların itkiləri aşağıdakı görkımdə matrislə təsvir edilir:
Aydındır ki, ən sərfəlisi susmaqdır. Lakin sadə mülahizə onu göstərir ki, aralarında heç bir kontakt olmadıqda və bir-birlərinə etibar etmədikdə hir bir məhbus fikirləşdikdən sonra etiraf etmək nəticəsinə gələcək. EP-nən vəzifəsi elə oyun strategiyasının axtarışıdır ki, oyun situasiyanın bir neçə təkrarından sonra orta itirimlərin minimallaşdırma imkanı əldə edilsin. Yüklə 30,15 Kb. Dostları ilə paylaş:
|