Генетычныя алгарытмы

Генетычныя алгарытмы ўяўляюць сабой эўрыстычныя, стахастычныя метады аптымізацыі, якія былі прапанаваны ўпершыню ў 1975 годзе Холанд. У іх аснову пакладзена ідэя эвалюцыі з натуральным адборам, якая прапаноўвалася яшчэ Дарвінам.

Генетычныя алгарытмы працуюць з мноствам асобін, то ёсць папуляцыяй, дзе кожная асобіна можа паслужыць рашэннем нейкай пэўнай праблемы. Кожную асобіну даводзіцца ацэньваць на ступень яе прыстасаванасці ў залежнасці ад таго, наколькі добрым з'яўляецца рашэнне задачы, адпаведнае ёй. Калі разглядаць гэта ў суадносінах з прыродай, то там ацэньваецца ступень эфектыўнасці арганізма пры канкурэнтнай барацьбе за рэсурсы. Асобіны, якія прыкметна мацней прыстасаваныя, могуць прайграваць нашчадства пры дапамозе перакрыжаванага скрыжавання з іншымі прадстаўнікамі папуляцыі. Гэта становіцца прычынай з'яўлення новых асобін, у якіх спалучаюцца некаторыя характарыстыкі, якія перадаюцца ў спадчыну ад бацькоў.

Менш прыстасаваныя асобіны змогуць прайграць нашчадства з меншай верагоднасцю, так што ўласцівасці, якімі яны валодаюць, будуць паступова знікаць ў працэсе эвалюцыі з усёй папуляцыі. Часам здараюцца спантаныя змены ў генах, або мутацыі. Атрымліваецца, што добрыя характарыстыкі з пакалення ў пакаленне будуць распаўсюджаныя па ўсёй папуляцыі. Скрыжаванне асобін, якія з'яўляюцца найбольш прыстасаванымі, прыводзіць да таго, што даследуюцца ўчасткі пошуку, якія прадстаўляюць найбольшую перспектыву. У канчатковым выніку знаходзіцца вырашэнне задачы. Генетычныя алгарытмы валодаюць перавагай, якія заключаюцца ў тым, што ён знаходзіць за адносна непрацяглы прамежак часу прыблізныя рашэння, якія ўяўляюць сабой аптымальныя. Варта разгледзець дадзенае пытанне датычна праграмавання.

Генетычныя алгарытмы складаюцца з наступных кампанентаў:

- храмасома, якая ўяўляе сабой рашэнне разгляданай праблемы, складаецца з генаў. Гэтая папуляцыя храмасом лічыцца пачатковай;

- набор аператараў (прызначаецца для генерацыі новых рашэнняў на аснове новых папуляцый);

- мэтавая функцыя (прызначана для таго, каб ацэньваць прыстасаванасць рашэнняў).

Для генетычных алгарытмаў існуе стандартны набор аператараў: селекцыя, мутацыя і скрыжаванне. Можна разгледзець прымяненне генетычных алгарытмаў пры дапамозе ўдакладнення таго, для чаго прызначаны кожны канкрэтны аператар. Аператар селекцыі вырабляе адбор храмасом у адпаведнасці з тым, якія значэнні іх функцый прыстасаванасці. Тут прадстаўлены як мінімум два найбольш папулярных аператара: турнір і рулетка. Метад рулеткі мяркуе ажыццяўленне адбору асобін з дапамогай n запускаў. Для кожнага члена выкарыстоўванай папуляцыі ў коле рулеткі ўтрымліваецца па адным сектару неабходнай велічыні. Члены папуляцыі з прыкметна больш высокім паказьнікам прыстасаванасці пры такім адборы будуць часцей выбірацца, чым прадстаўнікі, якія маюць нізкую прыстасаванасць. Пры турнірнай метадзе рэалізуецца n турніраў, якія дазваляюць выбраць n асобін. У аснову кожнага турніру закладзена выбарка k элементаў з папуляцыі, пры гэтым сярод іх павінна быць абраная лепшая асобіну.

Калі і далей разглядаць алгарытмы праграмавання, то варта сказаць пра метад, званым скрыжаванне. Аператарам скрыжавання ажыццяўляецца абмен часткамі храмасом паміж парай або храмасомамі ў адной папуляцыі.

Апошні аператар - мутацыі - стахастычнага змена часткі храмасом.

Канкрэтнае разгляд прымянення генетычных алгарытмаў ўяўляе сабой больш аб'ёмны матэрыял, чым можа змясціцца ў артыкуле, таму яго варта разглядаць асобна.