Кароткае Ўвядзенне Ў Генетычныя Алгарытмы

2015-11-11 10:34:06 / author: sharkov views 758Total views: 758 / 7Views for 7 days: 7
Thanks to Best cliparts
source article: http://www.cs.bgu.ac.il/~sipper/ga.html

by Moshe Sipper

Ідэя прымянення біялагічных прынцып натуральнай эвалюцыі штучных сістэм, уведзеныя больш чым тры дзесяцігоддзі назад, назіраецца ўражлівы рост у апошнія некалькі гадоў. Звычайна групуюцца пад тэрмінам эвалюцыйных алгарытмаў або эвалюцыйных вылічэнняў, мы знаходзім дамены генетычныя алгарытмы, эвалюцыйныя стратэгіі, эвалюцыйнае праграмаванне і генетычныя праграмавання [Sip02, В96, Mic96, Mit96, Sch95, Fog95, Koz92, Gol89, Hol75]. Эвалюцыйныя алгарытмы з'яўляюцца ўсюдыіснымі цяпер, будучы паспяхова ужыты да шматлікіх праблемах з розных прадметных абласцей, у тым ліку аптымізацыя, аўтаматычнае праграмаванне, машыннае навучанне, эканомікі, даследаванні аперацый, экалогіі, папуляцыйнай генетыкі, даследаванні эвалюцыі і навучання, і сацыяльнай сістэм [Mit96]. Для апошнія агляды бягучага стану мастацтва, чытачу варта звярнуцца да [Tom96, Tom95]. (Снежань 2003-новыя спасылкі: [Sip02, Banzhaf97, Fogel99, Koza99, Vose99].)

Як базавы прыклад штучнай эвалюцыі, мы разгледзім генетычныя алгарытмы [Hol75].

Генетычны алгарытм ўяўляе сабой итерационную працэдуру, якая складаецца з пастаяннай-Памер папуляцыі індывідаў, кожны з якіх прадстаўлены канчатковую радок знакаў, вядомую як геному, кадавальныя магчымае рашэнне ў дадзенай праблеме прасторы. Гэта прастора называецца прастору пошуку, ўключае ў сябе ўсе магчымыя варыянты вырашэння праблемы пад рукой. Наогул кажучы, генетычны алгарытм ўжываецца для памяшканняў, якія занадта вялікія, каб быць вычарпальным чынам абшукалі. Сімвал алфавіту выкарыстоўваецца двайковы часта, хоць іншыя прадстаўлення таксама былі выкарыстаны, у тым ліку на аснове кадовак знакаў, рэчыўных кадовак, і -- асабліва -- дрэва уяўленняў.

Стандартны генетычны алгарытм працягваецца наступным чынам: пачатковая папуляцыя асобін генеруецца выпадкова ці эвристически. Кожны эвалюцыйны крок, вядомы як пакаленне, фізічных асоб у бягучым насельніцтва дэкадуе і ацэненыя ў адпаведнасці з некаторых загадзя вызначаным крытэрам якасці, названыя фітнес, або фітнес-функцыяй. Для фарміравання новай папуляцыі (новага пакалення), асобам, якія выбіраюцца ў залежнасці ад іх падрыхтаванасці. Многія працэдуры адбору выкарыстоўваюцца ў цяперашні час, адным з самых простых будучы Галандыі арыгінальных фітнес-прапарцыйны адбор, дзе людзі адбіраюцца з верагоднасцю, прапарцыйнай іх адноснай прыдатнасці. Гэта гарантуе, што чаканае колькасць разоў індывідуальны выбіраецца прыкладна прапарцыйная яго адноснай прадукцыйнасці ў папуляцыі. Такім чынам, максімум-фітнэс (`добрыя") індывідаў маюць больш шанцаў `прайграваючы", у той час як нізкія-фітнес-тыя з большай верагоднасцю знікне.

Выбар у адзіночку не можа ўводзіць ніякіх новых асобін у папуляцыі, т. е. ен не можа знайсці новых кропак у прасторы пошуку. Яны ствараюцца на аснове генетычна-натхніў аператараў, з якіх найбольш вядомымі з'яўляюцца кросовер і мутацыя. Кросовер выконваецца з верагоднасцю pcross (на `кросовер верагоднасці" або `кросовер стаўка") паміж двух выбраных асоб, названых бацькоў, шляхам абмену часткі іх геномаў (г. зн. кадоўкі) у выглядзе двух новых асобін, называюць нашчадства; у сваей найпростай форме, падрадка абмяняліся пасля выпадкова абранай кропкі красовер. Гэты аператар мае тэндэнцыю ўключыць эвалюцыйны працэс, каб рухацца ў бок `перспектыўных" абласцях прасторы пошуку. Аператар мутацыі ўводзіцца для прадухілення заўчаснай збежнасці да лакальных Оптыма пры выпадковым адборы новых кропак у прасторы пошуку. Гэта ажыццяўляецца шляхам гартаць біты выпадковым чынам, з некаторай (невялікі) верагоднасцю pmut. Генетычныя алгарытмы з'яўляюцца выпадковыя ітэрацыйныя працэсы, якія, як гарантуюць, не сыходзяцца; ўмова завяршэння можа быць вызначаны як некаторы фіксаванае Максімальны лік пакаленняў або як дасягненне прымальнага ўзроўню фізічнай падрыхтоўкі. На малюнку 1 прадстаўлены стандартны генетычны алгарытм ў псеўда-код фармату.

begin GA

g:=0 { generation counter }

Initialize population P(g)

Evaluate population P(g) { i.e., compute fitness values }

while not done do

g:=g+1

Select P(g) from P(g-1)

Crossover P(g)

Mutate P(g)

Evaluate P(g)

end while

end GA

Мал. 1: псеўда-код стандартнага генетычнага алгарытму.

Давайце разгледзім наступны просты прыклад, з-за [Mit96], дэманструюць генетычны алгарытм яго працы. Насельніцтва складаецца з 4 асоб, якія з'яўляюцца двайкова-кадаванай радкі (геномаў) даўжыней 8. Фітнес-значэнне роўна колькасці адзінак у бітавай радку, з pcross=0.7, і pmut=0.001. Больш за тыповыя значэння колькасці і геном даўжыні знаходзяцца ў дыяпазоне 50-1000. Таксама звярніце ўвагу, што фітнес у гэтым выпадку разлік вельмі просты, паколькі няма складаных дэкадавання, ні ацэнкі з'яўляецца неабходным. Пачатковая (генеруецца выпадковым чынам) насельніцтва можа выглядаць наступным чынам:

Label Genome Fitness

A 00000110 2

B 11101110 6

C 00100000 1

D 00110100 3

Выкарыстоўваючы фітнес-прапарцыянальнага адбору мы павінны выбраць 4 чалавека (дзве сям'і), з верагоднасцю, прапарцыйнай іх адноснай прыдатнасці значэння. У нашым прыкладзе, выкажам здагадку, што на двух бацькоўскіх пар {B,D} І {B,C} (звярніце ўвагу, што не атрымліваецца выбірацца, так як наша працэдура носіць імавернасны). Пасля пары бацькоў абраны, кросовер вырабляецца паміж імі з верагоднасцю pcross , атрыманыя ў двух атожылкаў. Калі няма красовер ажыццяўляецца (з верагоднасцю 1-pcross), то ў нашчадства з'яўляюцца дакладнымі копіямі кожнага з бацькоў. Выкажам здагадку, у нашым прыкладзе, што кросовер зойме месца паміж бацькамі, B і D (выпадковым чынам) першай разраднай пазіцыі, фармуючы нашчадства Е=10110100 і F=01101110, а не кросовер вырабляецца паміж бацькамі, B і C, утвараючы атожылкі, якія ўяўляюць сабой дакладныя копіі B і C. далей, кожнае нашчадства падвяргаецца мутацыі, з верагоднасцю pmut у біт. Напрыклад, выкажам здагадку, што Е нашчадства муціруе на шостай пазіцыі ў форме Е'=10110000, Б нашчадства муціруе ў першую бітавую пазіцыю, каб форма B'=01101110, і нашчадкаў F і C з'яўляюцца не відазмяняецца наогул. Наступнае пакаленне папуляцыі, створаныя вышэйназваныя аператары адбору, кросовера і мутацыі, такім чынам:

Label Genome Fitness

E' 10110000 3

F 01101110 5

C 00100000 1

B' 01101110 5

Звярніце ўвагу, што ў новай папуляцыі, хоць лепшыя індывідуальныя з фітнес-6 быў страчаны, сярэдні фітнес-павялічылася. Ітэрацыя гэтай працэдуры генетычнага алгарытму ў канчатковым выніку знайсці ідэальны радкі, г. зн. з максімальным фітнес-значэнне 8.

Рэалізацыя эвалюцыйнага алгарытму, пытанне, які звычайна застаецца ў фонавым рэжыме, даволі дарагім, у многіх выпадках, паколькі папуляцыі рашэнняў ўцягнутыя магчыма, у спалучэнні з рэсурсаемістых вылічэнняў фітнес-ацэнкі. Адно магчымае рашэнне складаецца ў тым, каб распараллелить працэс, ідэя, якая была вывучана ў якой-то ступені ў апошнія гады (гл агляды [Tom96, CP95]). Падчас пазіравання ніякіх сур'езных праблем у прынцыпе, для гэтага можа спатрэбіцца разумнае мадыфікацыі існуючых алгарытмаў або ўвядзенне новых у мэтах задавальнення абмежаванняў дадзенага паралельнай машыны. Наш праект уключае ў сябе клеткавы праграмавання эвалюцыйны алгарытм выкарыстоўваецца, каб развівацца неаднародных клеткавых аўтаматаў. Алгарытм лакальнага характару робіць яго больш згаворлівым для паралельнай рэалізацыі і будаўніцтву `развіваецца харчовы", evolware.

Для спасылкі на дадатковую інфармацыю націсніце тут.

Перайсці да сотавай праграмавання старонкі.

М. Sipper, машына прыроды: будучы стагоддзе Бія-натхніў вылічэнняў, Макгро-Хіл, Нью-Ерк, 2002.

paper4pc
Add a comment:
Sign in

See also

Great Computer Scientists

УТ іх розумы: аб жыцці і адкрыццях вялікіх навукоўцаў 15 кампутар

2015-11-02 16:35:12

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

html markup

Гэта разметка назоўнік або дзеяслоў? Ты разметка дадзеных або дадзеныя абгарнуць у тэгі?

2015-11-02 12:30:51

Пастаноўка Задачы Разгледзім гэтыя дадзеныя: Вось я зрабіў "нешта" у дадзеных: Што з'яўляецца пераважным спосабам выказвання таго, што я зрабіў дадзеныя: Я...

DES Encryption

Шыфравання des

2015-11-02 12:42:27

Гэта JavaScript-рэалізацыя ў DES (Data Encryption Standard - Стандарт шыфравання дадзеных), алгарытм шыфравання, які працуе на біты. Ен падтрымлівае электроннай...

Жолуд Мікракампутар (1979)

Acorn Мікракампутар (1979)

2015-11-02 16:08:51

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

Art for designers dkcoin8.com (DesignerKit)