Ziyosfera

Genetik algoritm

Генетик алгоритм (генетиc алгоритҳм, ГА) - информатика ва операцияларни тадқиқ қилиш соҳаларида табиий танланиш жараёнига асосланган, эволюцион алгоритмлар (ЭА) синфига мансуб бо'лган метаэвристик қидирув алгоритмидир.

2006-йилда учирилган НАСА СТ5 космик кемасининг антеннаси. Ушбу мураккаб шакл эволюцион компютер дизайни дастури томонидан энг яхши нурланиш моделини яратиш учун топилган. Бу эволюцияланган антенна сифатида танилган.

Генетик алгоритмлар одатда оптимизация ва қидирув муаммолари учун юқори сифатли ечимларни топишда танлаш, кроссовер (реккомбинация) ва мутация каби биологик илҳомлантирилган операторлар ёрдамида қо'лланилади.

Ушбу алгоритмлар қарор қабул қилиш дарахтларини оптималлаштириш, Судоку жумбоқларини эчиш, гиперпараметр оптималлаштириш ва кауфал хулосалар чиқариш каби кенг ко'ламли соҳаларда муваффақиятли қо'лланилади. Генетик алгоритмларнинг асосий кучи уларнинг мураккаб, ко'п о'лчовли ва тушунарли математик модели бо'лмаган қидирув майдонларида самарали ишлай олишидадир.

Эволюцион жараён одатда тасодифий ҳосил қилинган шахслар (ечимлар) популяциясидан бошланади ва итератив (такрорланувчи) жараён ҳисобланади. Ҳар бир итерация авлод (генератион) деб аталади. Ҳар бир авлодда популяциядаги ҳар бир шахснинг "яроқлилиги" (фитнесс) баҳоланади; бу қиймат одатда ҳал қилинаётган оптималлаштириш муаммосидаги мақсад функсиясининг қийматига тенг бо'лади.

Методология

Оптимизация муаммолари

Генетик алгоритмда оптималлаштириш муаммосига номзод ечимлар популяцияси (шахслар, жонзотлар ёки фенотиплар деб аталади) яхшироқ ечимлар сари ривожланади. Ҳар бир номзод ечим о'з хусусиятлари то'пламига (унинг хромосомалари ёки генотипи) эга бо'либ, улар мутацияга учраши ва о'згариши мумкин. Ан'анавий равишда ечимлар 0 ва 1 лардан иборат иккилик (бинарй) қаторлар шаклида ифодаланади, аммо бошқа кодлаш усуллари ҳам мавжуд.

Стандарт генетик алгоритм қуйидагиларни талаб қилади:

  1. Ечимлар соҳасининг генетик ифодаси (генетиc репресентатион);
  2. Ечимлар соҳасини баҳолаш учун фитнесс функсияси (фитнесс фунcтион).

Жараён босқичлари

1. Инициализация (Ишга тушириш)

Популяция ҳажми муаммонинг табиатига бог'лиқ, аммо одатда юзлаб ёки минглаб мумкин бо'лган ечимларни о'з ичига олади. Ко'пинча бошланг'ич популяция бутун қидирув майдонини қамраб олиши учун тасодифий тарзда шакллантирилади. Ба'зан ечимлар оптимал натижа топилиши эҳтимоли юқори бо'лган соҳаларга "экилиши" (сеэдинг) мумкин.

2. Танлаш (Селеcтион)

Ҳар бир кейинги авлод давомида мавжуд популяциянинг бир қисми янги авлодни яратиш учун танлаб олинади. Шахсий ечимлар фитнессга асосланган жараён орқали танланади, бунда яроқлилик даражаси юқори бо'лган ечимлар танланиш эҳтимоли ко'проқ бо'лади. Фитнесс функсияси генетик ифода устида аниқланади ва тақдим этилган ечимнинг "сифатини" о'лчайди.

Масалан, Халта муаммосида (кнапсаcк проблем) ма'лум сиг'имга эга халтага жойлаштирилиши мумкин бо'лган буюмларнинг умумий қийматини максималлаштириш керак. Ечимнинг фитнесс қиймати халтадаги барча буюмлар қийматининг йиг'индисига тенг бо'лади (агар умумий ог'ирлик лимитдан ошмаса).

3. Генетик операторлар

Кейинги қадам танланган ечимлардан генетик операторлар: кроссовер (реккомбинация) ва мутация ёрдамида иккинчи авлод популяциясини яратишдир.

  • Кроссовер: Икки "ота-она" ечимнинг хусусиятларини бирлаштириб, янги "фарзанд" ечим яратиш жараёни. Бу янги ечим о'з ота-оналарининг ко'плаб хусусиятларини мерос қилиб олади.
  • Мутация: Генетик хилма-хилликни сақлаб қолиш ва алгоритмнинг локал оптимумга (маҳаллий энг яхши нуқтага) тушиб қолишининг олдини олиш учун ечимнинг айрим қисмларини тасодифий о'згартириш жараёни.

4. Якунлаш (Терминатион)

Ушбу авлодлар алмашинуви жараёни якунлаш шарти бажарилгунга қадар такрорланади. Умумий якунлаш шартлари:

  • Минимал мезонларга жавоб берадиган ечим топилиши;
  • Белгиланган авлодлар сонига етиб борилиши;
  • Ажратилган вақт ёки ҳисоблаш ресурсларининг тугаши;
  • Энг яхши ечимнинг фитнесс даражаси платога (тург'унликка) етиши, я'ни кейинги итерациялар яхшироқ натижа бермай қо'йиши.

Қурилиш блоклари гипотезаси

Генетик алгоритмларни амалга ошириш осон, аммо уларнинг хатти-ҳаракатларини тушуниш мураккаб. Қурилиш блоклари гипотезаси (буилдинг блоcк ҳйпотҳесис, ББҲ) алгоритмларнинг нима учун муваффақиятли эканлигини тушунтиришга ҳаракат қилади. Давид Э. Голдбергнинг фикрича, алгоритм "қурилиш блоклари" деб аталувчи қисқа, паст тартибли ва юқори фитнессли схемаларни аниқлаш ва уларни қайта бирлаштириш орқали мослашишни амалга оширади.

Ҳудди бола оддий ёг'оч блоклардан муҳташам қал'алар қургани каби, генетик алгоритм ҳам қисқа ва самарали қисмларни бирлаштириш орқали оптимал ечимга яқинлашади.

Чекловлар

Генетик алгоритмларнинг амалий қо'лланилишида бир қатор чекловлар мавжуд:

  • Ҳисоблаш ресурслари: Мураккаб муаммолар учун фитнесс функсиясини қайта-қайта баҳолаш жуда ко'п вақт талаб қилиши мумкин. Ба'зан битта симуляция соатлаб ёки кунлаб давом этади.
  • Масштаблашув: Элементлар сони ко'пайган сари қидирув майдони экспоненциал равишда кенгайиб боради (мураккаблик муаммоси).
  • Локал оптимум: Алгоритмлар ко'пинча глобал ечим о'рнига локал оптимумга (яқин атрофдаги яхши нуқтага) яқинлашиб, о'ша ерда "тиқилиб" қолишга мойил бо'лади.
  • Динамик ма'лумотлар: Ма'лумотлар то'плами о'згарувчан бо'лса, алгоритм эски ма'лумотларга мослашиб қолиши мумкин.

Вариантлар ва турлари

Хромосома ифодаланиши

Энг оддий алгоритм ҳар бир хромосомани битлар қатори (0 ва 1) сифатида ифодалайди. Аммо замонавий вариантларда хромосомалар қуйидагича бо'лиши мумкин:

  • Ҳақиқий сонлар массивлари (реал-валуэд репресентатион);
  • Буйруқлар жадвалига индекслар ро'йхати;
  • Бог'ланган ро'йхатлар (линкед лисц) ёки об'эктлар.

Иккилик кодлашда ко'пинча Грей коди (Грай cодинг) қо'лланилади. Бу соннинг кичик о'згариши хромосомада ҳам кичик о'згаришга олиб келишини та'минлайди.

Элитизм (Элитисм)

Янги авлодни яратишда жорий авлоднинг энг яхши вакилларини (ёки вакилини) о'згартиришсиз кейинги авлодга о'тказиш стратегияси. Бу ечим сифатининг авлоддан-авлодга ёмонлашмаслигини кафолатлайди.

Адаптив генетик алгоритмлар (АГА)

Ушбу вариантда кроссовер (пc) ва мутация (пм) эҳтимоллари о'згармас эмас, балки популяциянинг ҳолатига қараб автоматик равишда мослаштирилади. Агар популяция хилма-хиллиги камайса, мутация даражаси оширилади.

Қо'лланилиш соҳалари

Генетик алгоритмлар айниқса қуйидаги соҳаларда самарали:

  • Жадвалларни тузиш: Дарс жадваллари, навбатчилик графиклари ва ишлаб чиқариш режалари.
  • Муҳандислик дизайни: Аэродинамик шаклларни оптималлаштириш, ко'приклар дизайни.
  • Космик технологиялар: НАСА антенналари ва космик аппаратлар траекториясини ҳисоблаш.
  • Иқтисодиёт: Портфелни оптималлаштириш ва савдо стратегияларини ишлаб чиқиш.
  • О'йинлар ва робототехника: Компютер персонажларининг юриш усулларини ва ҳаракат логикасини о'ргатиш.

Тарих

Генетик алгоритмларнинг ривожланиш тарихи бир неча муҳим босқичларни босиб о'тган:

  • 1950-йил: Алан Туринг эволюция тамойилларига асосланган "о'рганувчи машина" г'оясини таклиф қилди.
  • 1954-йил: Нилс Аалл Барриcелли Принстонда биринчи эволюцион симуляцияларни о'тказди.
  • 1960-йиллар: Инго Реченберг ва Ҳанс-Паул Счwефел эволюцион стратегиялар ёрдамида мураккаб муҳандислик муаммоларини ҳал қилишди.
  • 1975-йил: Жоҳн Ҳенрй Ҳолланд о'зининг "Адаптатион ин Натурал анд Артифиcиал Сйстемс" китобини нашр этди ва генетик алгоритмларнинг назарий асосларини шакллантирди.
  • 1980-йиллар охири: Генерал Элеcтриc дунёдаги биринчи саноат генетик алгоритм маҳсулотини сотувга чиқарди.

О'хшаш техникалар

Генетик алгоритмлар қуйидаги кенгроқ соҳаларнинг бир қисмидир:

Яна қаранг

Манбалар

Қо'шимча адабиётлар

  • Голдберг, Давид (1989). Генетиc Алгоритҳмс ин Сеарч, Оптимизатион анд Мачине Леарнинг. Аддисон-Wеслей Профессионал. ИСБН 978-0201157673.
  • Митчелл, Меланиэ (1996). Ан Интродуcтион то Генетиc Алгоритҳмс. МИТ Пресс. ИСБН 9780585030944.
  • Ҳолланд, Жоҳн (1992). Адаптатион ин Натурал анд Артифиcиал Сйстемс. МИТ Пресс. ИСБН 978-0262581110.

Ташқи ҳаволалар

"https://new.ziyosfera.uz/ziyo/19914441" dan olindi