Зертханалық жұмыс

«Мақсаттық функцияның экстремумын іздеудің генетикалық

алгоритімін зерттеу»

Генетикалық алгоритм - компьютерлік бағдарлама ретінде іске асқан табиғаттағы эволюцияның қарапайым моделі. Онда генетикалық мұрагерлікте аналогты механикамен қатар, табиғи сұрыптаудың аналогы да қолданылады. Оған қарамастан қарапайым түрде биологиялық терминологиясы сақталады.

1 кесте. Генетикалық мұрагерліктің моделденуі.

Хромосома	Нөл мен бірліктерден құралған вектор әрбір орын жайлы ген деп аталады.
Индивидуум = генетикалық код	Хромосомалар жиыны = есептің шешілу нұсқасы.
Кроссовер	Екі хромосома бір бірінен, өздерінің бөлшектерімен алмасатын амалдар.
Мутация	Хромосомада кездейсоқ жағдайда бір немесе бірнеше позициялық өзгеруі.

Эволюциялық үрдісті моделдеу үшін, алдымен кездейсоқ популяцияны генерациялайық - кездейсоқ хромосомалары (сандық векторлы) бар бірнеше индивидуумдар. Генетикалық алгоритм бұл популяцияның эволюциясын индивидуумдардың қиылысқан циклдық үрдіс ретінде және ұрпақтың өзгеруін жалған түрінде көрсетеді.

15.1 сурет. Генетикалық алгоритм құрудың қағидасы.

Популяцияның өмірлік циклы - бұл бірнеше кездейсоқ будандасу (кроссовер арқылы) және мутациялар, осының нәтижесінде популяцияға жаңадан бірнеше көлемде индивидуумдар қосылады. Генетикалық алгоримде сұрыптау - бұл ескі популяциядан жаңа популяция құру үрдісі,Содан кейін ескі популяция өмір сүруін тоқтатады. Сұрыптаудан кейін жаңа популяцияға тағы да кроссовер мен мутация амалдары қолданылады, содан тағы да сұрыптау болады, осылайша кете береді.

1 кесте. Сұрыптаудың генетикалық алгоритмде және табиғаттағы байланысы.

Индивидуумдардың бейімделуі	Бұл индивидуумда мақсаттық функ-ң мағынасы.
Жаксы бейімделгендердің өмірге деген күресі	Келесі ұрпақтың популяциясы мақсаттық функ-ға байл-ты құрылады. Индивидуум неғұрлым бейімделген болса, онда оның соғұрлым кроссоверде, яғни көбеюде қатысуы қатысу ықтималдылығы көп.

Генетикалық алгоритмдер (ГА) - іздеудің үйренген әдісі, ол қазіргі уақытта функционалды тиімділеудің есептерін шешуде жиі қолданылады. Олар биологиялық организмдердің генетикалық үрдістеріне негізделген: биологиялық популяция бірнеше ұрпақтардан кейін ғана жетіледі, табиғи сұрыптау заңына және Ч.Дарвинмен ашылған “жақсы бейімделген ғана тірі қалады” деген қағидаға бағынады. Осы үрдісті ұқсатып қайталасақ генетикалық алгоритмдер нағыз есептерді шешуді жетілдіреді, егер де олар сәйкесінше кодталған болса. Мысалы, ГА көпір құрылысын проекциялау үшін, беріктіктің/салмаққа деген қатынасын табу үшін немесе матадан формаларды қиюдан ең аз шашырап орналастырылғанын табуға үшін қолдануға болады. Олар тағы да үрдісті антерактивті басқаруда қолданылуы мүмкін, мысалы химиялық заводта немесе көпүрдіссорлы компьютерде теңгеріліп салу кезінде қолданылуы мүмкін.

Табиғатта жекеленген түрлер популяция кезінде бір бірімен түрлі ресурстар үшін бәсекелеске түседі, олар, мысалыға тамақ немесе су сияқтылар. Одан басқа, бір популяция түрінің мүшесі неке серіктестігін қарату үшін жиі бәсекелестікке түседі. Қоршаған ортаның жағдацына ең жақсы икемделген жеке түрлер артынан көп ұрпақ өкелуге көптеген мүмкіндігі бар. Аз икемделгендер болса, артынан ұрпақ қалдырмау мүмкін немесе ол аз мөлшерде ғана болады. Бұл дегеніміз, үйренген гендер немесе икемделген жеке түрлер әрбір келесі ұрпақтарда көп мөлшерде артынан ұрпақ қалдырады. Түрлі ата- анадан жақсы сипаттамадағы комбинациядан кейде “суперикемделген” ұрпақ пайда болады. Мүмкін оның икемділігі ата-анасына қарағанда да күшті. Осылайша, ол жақсы көбейеді және өмір сүру ортасына икемділігі жаксы.

ГА-ды осындай механизмде тура аналогия ретінде қолданады. Олар, түрлердің жиынтығымен - популяциямен жұмыс істейді, олардың әр біреуі берілген қиындықтан мүмкін болатын шешімін береді. Әрбір түр оның сәйкес “икемділігіне” қарай бағаланады, оған есептің шешімі қаншалықты “жақсы” сәйкес екеніне қарайды. Мысалы, берілген көпірдің жобасына икемделу шамасы болып күштің/салмаққа қатынасы болар еді. Жақсы икемделген түрлер ұрпақты көбейтуді “қиылысып будандасу” арқылы популяцияның басқа түрімен іске асырады. Бұл жаңа түрдің пайда болуына әкеліп соқтырады, оларда ата-анасына ұқсас сипаттары да байқалады. Аз икемделген жеке түрлердің артынан ұрпақ қалдыру ықтималдылығы өте аз, өйткені олардың бар қасиеттері өрістеу кезінде популяциядан аз-аздап кете береді.

Шешілетін есептің барлық жаңа популяциясы осылайша іске асады, алдынғы ұрпақтан ең жақсы дегенді таңдап, будандастырып, соның арқасында көптеген жаңа түрлерді алу. Бұл жаңа ұрпақ алдынғы ұрпақтардан алған жақсы сипаттамаға ие. Осылайша, ұрпақтан-ұрпаққа жақсы сипаттамалар бүкіл ұрпақ бойынша тарайды. Жақсы икемделген түрлердің будандасуы арқасында, іздеудің кеңістікте перспективті бөлігін зерттеуге әкеледі. Соңында, популяция тиімді шешімге келеді.

Мақсаты: Генетикалық бағдарламаны қолданып, түрлі функцияға арналған нақты іздеуді және оның жылдамдығын зерттеу.

Генетикалық алгоритм көмегімен мақсаттық функцияның экстремумын табудың алгоритмі.

Бастапқы мәліметтер енгізіледі, X(i) кіріс айнымалысының саны X(i)-к, h - қадам шамасы, іздеудің берілген дәлдігі - E, бірінші ретті туындысын тапқанда аргумен ттің өзгеру шамасы dX, бастапқы сәтте қадамның счетчигі 1-ге тең болу керек (n=1), өйткені итерациалыәдістер басталмас бұрын бір рет мақсаттық функцияны есептеу керек F_ц0=G_Znкр

ГА-ді зерттегенге ыңғайлы және бағдарламаны қайтадан құрмау үшін функцияны өзгертпейтіндей программа құру керек. Бұл бағдарлама әмбебап болу керек, өйткені оның пайда болуына ең қарапайым мысал алынған және оның негізінде экстремумды табудың басқа бағдарламасының салыстырмалы анализі алынған, және де басқа есептерге арналған генетикалық алгоритмді зерттеу, экстремумды табудың классикалық әдісіне қарағанда өте қиын болып келеді. Төменде келтірілген программада кейбір аумақ алынган, бұл аумақта бес нүктеден құралған бастапқы популяцияны алған, олардан үшеуін экстремумға жақын нүкте ретінде анықтады, бұл нүктенің ұрпақтарын анықтады, содан бұл нүктенің мутациясын жасады, бірнеше түрдің мутациясы. өйткені экстремум нүктесін табудың негізгі факторы болып ұрпақтың мутациясы болу керек. Мутация түрлері:

1. ұрпақтың координатасының 2-ге көбейтілуі;

2. ұрпақтың абцисса осінің координатасын ордината осіне ауыстыру;

3. ұрпақ коодинатасын теріс санға көбейту;

4. кездейсоқ сандар генераторынан алынған санға ұрпақ координатасының

көбейтілуі.

Берілген алгоритм координатасы 5 нүктеге алынған, олар келесі мәндерге ие (7;8);

(2,5;7); (-3;-5); (-2;-1); (3,5;-1,5). Мәндер матрица түрінде берілген

Тапсырма:

1. Мақсаттық функцияны Овраг Розенброк функциясына өзгерту

2. 5 нүктеге координаталар мәндерін және де коэффициенттер мәнінде ауыстыру;

3. Итерация санын ұлғайту немесе кеміту;

4. Берілген алгоритм мен өзгертілген алгоритм арасында жүргізу.