3.3. Генетикалық алгоритмдердің қолдану мысалы
Инвестициялық тиімді таралу есебіне орала отырып, генетикалық алгоритімнің іске асу ерекшелігін айқындаймыз. Тұлғалар = есепті шешу нұсқасы = 10 Х, хромосомасынан тұратын жиын, Х хромосомасы = жобаға енгізу көлемі j=16 осы санның еселігінің таңбасы. Енгізу көлемі шектеулі болғандықтан, хромосоманың барлық мәні рұқсат етуге болмайды. Ол популяция генерациясы арқылы анықталады. Инвестицияның жалпы көлемі бекітілген болғандықтан, 9-храмосома нұсқауланады, ал 10 сол арқылы анықталады.
К 24 инвестициясының жалпы көлемнің үш түрлі мәніндей генетикалық алгоритм құрлысының нәтижесі төменде көрсетілген.
3.1 Инвестициялық есептеулер
Берілген жобаға енгізу көлемі шаршымен берілген. К-кіші мәнінде минимал енгізудегі табысты жобалар инвестицияланады. Егер инвестицияның жалпы көлемі үлкейтсе, қымбат тұратын жобаларға де ақша салуға болады. К – өсуіне байланысты табысты жобаларға енгізудің максимал мәніне жетуге болады.
3.4 Генетикалық алгоритімнің ерекшеліктері
Генетикалық алгоритм – тиімділеу есебін шешудің жаңа әдісі. Ерте заманнан бері осындай есепті шешудің екі жолы бар жергілікті градиентті және сұрыптау. Бұл әдістерде өзінің артықшылықтары мен ерекшеліктері бар.
Коммивояжер есебінің классикалық мысалында стандартты және генетикалық әдістердің артықшылығы мен кемшілігі қарастырайық (TSP-travelling salesman problem). Есеп бойынша берілген координат бойынша бірнеше қаланы айналып өтудің қысқа тұйық жолын табу керек. 30 қала үшін тиімді жол табу күрделі есеп болып табылады.
Шешімнің әрбір нұсқасы (30 қала үшін) j-орнын да j- қаланың нөмері тұратын сандық жол. Сол себепті бұл есепте 30 параметр бар.
Сұрыптау әдісі бағдарламауға қарапайым және тривиалды. Тиімді шешім табу үшін барлық мүмкін нүктедегі мақсаттық функциясының мәнін тізбектей табу керек. Бұл есептің шешімі - есептеу құнының жоғары болуы. Коммивояжер – есебінде ұзыңдығы 10-ң 30 дәрежесі жуық жолдың нұсқасын табу керек. Егер нақты уақытта барлық нұсқаны сұрыптауға болса, онда табылған шешім тиімді болады.
Екінші түрі – градиентті түсу әдісі. Бұл кезде кейбір кездейсоқ параметірлер мәні алынып, олар біртіндеп өзгерте отырып, мақсаттық функция жылдамдығын арттырады жергілікті максимумға келген соң, алгоритім тоқтайды. Сондықтан жергілікті тиімді табу үшін қосымша көмек керек.
Градиантты әдіс тез жұмыс істейді, бірақ табылған шешімнің тиімділігіне кепілдік бермейді. Олар мақсаттық функцияның бір ғана жергілікті максимумы болатын есептерге қолдануға келеді. тәжірибелік есеп әдетте мультимодальды және көп өлшемді. Мұндай есептер абсолютті нақты шешімді табатын әмбебап әдісі жоқ. Бірақ сұрыптау және градиентті әдісті қосып, есептеу уақытының өсуіне байланысты нақтылығы өсетін жуық шешімді табуға болады. Генетикалық алгоритм комбинацияланған әдіске ұқсас қиылысу және мутация механизмдері әдістін сұрыптау, ал градиентті түсу тиімді шешімді қамтамассыз етеді.
Суретте осындай комбинациялық кез келген есеп үшін генетикалық іздеудің тиімділігін қамтамассыз ететіні көрсетілген. Егер кейбір жиында бірнеше айнымалыдан тұратын күрделі функция берілсе, онда генетикалық алгоритм нақты уақытта функция мәні максимал мүмкін мәнде болатын нүктені табатын бағдарлама.
Есептеу уақытын дұрыс таңдай отырып, ең тиімді шешімді табуға болады. Басқару жүйелерінде ГА-ді пайдалану – хромосомалардың бинарлы кодтауын қолдануға негізделген, бұл құбылыс ақпаратты өңдеуді қиындатады.
Заттық сандар кеңістігінде тиімді шешімді табу үшін хромосомалар заттық сандар векторы түрінде беріледі. Мұндай кодтау қиылысу мен мутацияның генетикалық амалдарысын табуды талап етеді. Мысалы, хромосомалардың заттық кодтау үшін сызықтық қиылысу амалдарысы енгізіледі, бұнда ұрпақтары жолақ бойында, ал ата-анасы біріктіру нүктелерінде орналасады. Сонымен қатар нормаль таралу заңына сәйкес келетін нормаль-сызықтық қиылысу енгізіледі.
3.2-сурет. Сызықтық қилысудың графикалық бейнелеуі
Заттық хромосомалар жағдайына арналған нормаль заттық мутация құбылысының бинарлы айырмашылығы бар: Онда барлық хромосома өзгереді. Өзгертілген хромосомаға сәйкес нүктенің нақты орны таралудың нормаль заңымен анықталады. Нормаль-сызықтық заттық қиылысу мен нормаль заттық мутацияның генетикалық амалдары заттық сандарды анықтауға мүмкіндік беретін ГА-ны орындауға көмектеседі.