Генетические алгоритмы в Mathematica (1)

Никогда раньше блог не вела. Так что не судите строго и все комментарии приветствуются. Буду рада вашим вопросам и пожеланиями. 

Верите вы или нет в эволюционное развитие жизни на этой планете, но теория естественного отбора предлагает некоторые убедительные аргументы. Так люди с определенными характеристиками в большей степени способны выжить и передать эти характеристики их потомству. Мы все знаем о естественном отборе, как о способе природы выбирать лучшие организмы. Генетический алгоритм (ГА) – это общая процедура поиска на основе идей генетики и естественного отбора.

Решение методологии ГА напоминает половое размножение, в котором гены двух родителей объединяются, дабы сформировать детей. Будем основываться на том, что мы можем создать популяцию особей, которая каким-то образом предоставляет возможность решения поставленной нами задачи. Эти особи имеют определенные характеристики, которые делают их более или менее подходящими в качестве членов популяции, и мы связываем это с вероятностью пригодности к деторождению (спаривания). Наиболее подходящие особи будут иметь высокую вероятность спаривания, чем менее приспособленные особи. Эффективность ГА заключается в том, что при скрещивании особей популяции, производится потомство, у которых есть значительный шанс сохранить желаемые характеристики своих родителей, возможно, даже сочетающий лучшие характеристики обоих родителей. Таким образом, общая приспособленность популяции потенциально может увеличиться с поколением, так мы получаем лучшее решение нашей задачи.

Рассмотрим следующий пример.

Десять обезьянок печатают на десяти пишущих машинках. Им позволяют набрать 13 строчных букв. Будем называть этот набор фраз поколением. Если ни одна из обезьянок не набрала фразу «tobeornottobe», тогда начинаем снова с чистого листа для каждой обезьянки. Давайте смоделируем эксперимент с помощью Mathematica нескольких поколений прозы обезьянок. Функция FromCharacterCode в Mathematica преобразует ASCII код элемента списка в их соответствующие символы. Будем использовать функцию для создания текста из случайно сгенерированного списка кодов символов.   

generate[]:=
TableForm[Map[FromCharacterCode,Table[Random[Integer,{97,122}],{i,1,10},{j,1,13}]]]

Результат выполнения данной функции: 

generate[]

sgpufsegstpmn
aaultfgvfhrhu
jjdrerdlzjvav
hcomzqsavxfgs
ygduziuqotcxf
wzzoxkpkoqehg
pyefezculgnzk
svvaeqsznwizc
lhbtszewymxij
ivklrlfjyrzoa

generate[]

lakkmpfiyiugh
rgfxptiovbjyw
bgukgvvpwtauh
seltknwmxpirs
irzbhebsxevfi
llmmzuhjbubui
hxleqlfwowlmd
ohbpbpbdawlar
piwbydpislwaw
zkucmbapjaxsk

generate[]

sabtqcemmtfqs
wrgrdpjascixj
ytfcxgvkgrysl
vjzsttxesonay
qrmkchukzieim
qxsdftjkzehgk
rpwswkilzuvvw
hitoxrddhruvb
yblucnustugeu
dkhxjmfgiwobp

Можно продолжить, но вы видимо заметили, что ни одна строка не имеет сходства с нашей, которую мы хотим получить (напоминаю «tobeornottobe»). Иногда соответствующая буква появляется в нужном месте в одной из строк. Но это, вероятно, займет очень много времени, прежде чем наши псевдообезьянки сгенерируют правильную последовательность чисто случайно. Поскольку существует 26 возможных букв для каждой позиции (у нас 13 позиций) в строке, вероятность того, что одна обезьянка введет правильную фразу:

(1./26)^13

4.03038*10^-19

Что составляет примерно два шанса из миллиарда миллиардов. Согласитесь, что поэтому чистая случайность вероятно не достаточна для управления эволюционного изменения. 

Давайте немного изменим процесс генерации. Сначала создадим 10 последовательностей наугад, как и раньше. Однако, для последующих поколений, мы опираемся на поколение строки, которая незначительно, но наиболее соответствует желаемой строки. Позволим им менять каждую букву с фиксированной вероятностью. Из полученного поколения, мы выбираем наиболее близко соответствующие строки, чтобы сформировать новое поколение, и так далее.

Начнем с объявления фразы как текстовой строки.

tobe="tobeornottobe"

tobeornottobe

Конвертируем строку в переменную keyPhrase.

keyPhrase=ToCharacterCode[tobe]

{116,111,98,101,111,114,110,111,116,116,111,98,101}

Сгенерируем начальную популяцию из 10 случайных фраз, но оставляя их в ASCII коде для дальнейшего использования. 

initialPop=Table[Random[Integer,{97,122}],{i,1,10},{j,1,13}]

{{97,116,103,104,108,117,122,112,105,106,110,120,103},{107,109,107,105,109,101,113,97,118,114,122,103,99},{107,105,117,110,102,118,106,106,108,103,119,116,114},{104,118,109,118,111,99,102,116,108,111,108,98,102},{112,105,107,116,105,103,108,121,101,105,106,121,99},{113,97,109,119,116,112,122,115,114,121,113,118,106},{119,121,103,117,104,119,111,120,108,118,109,109,115},{103,112,97,122,101,121,112,98,106,105,100,112,112},{104,113,99,104,106,118,108,114,120,117,103,98,105},{113,100,101,97,121,107,112,121,114,118,99,117,99}}

Из любопытства преобразуем популяции в строку, дабы увидеть, как они выглядят.

TableForm[Map[FromCharacterCode,initialPop]]

atghluzpijnxg

kmkimeqavrzgc

kiunfvjjlgwtr

hvmvocftlolbf

piktiglyeijyc

qamwtpzsryqvj

wyguhwoxlvmms

gpazeypbjidpp

hqchjvlrxugbi

qdeaykpyrvcuc

Нам понадобиться еще несколько функций для реализации этой демонстрации. Для начала, функция flip[prob], реализующая предвзятую жеребьёвку. Т.е. при случаи подбрасывании монеты, вероятность выпадения орла будет prob, а не 50-50.

flip[x_]:=If[Random[]<=x,True,False]

Функция mutateLetter будет изменять данную букву с вероятностью pmute

mutateLetter[pmute_,letter_]:=If[flip[pmute],Random[Integer,{97,122}],letter]

newGenerate – главная функция, которая создает группу новых фраз. 

newGenerate[pmutate_,keyPhrase_,pop_,numGens_]:=

Module[{i,newPop,parent,diff,matches,index,fitness},

newPop=pop;

For[i=1,i<= numGens,i++,diff=Map[(keyPhrase-#)&,newPop];

matches=Map[Count[#,0]&,diff];

fitness=Max[matches];

index=Position[matches,fitness];

parent=newPop[[First[Flatten[index]]]];

Print["Generation",i,": ",

FromCharacterCode[parent],"  Fitness = ",fitness];

newPop=Table[Map[mutateLetter[pmutate,#]&,parent],{100}];

];

];

Давайте произведем 50 новых поколений, чтобы увидеть, насколько хорошо эта схема работает.

newGenerate[0.1,keyPhrase,initialPop,50]

Generation1: hvmvocftlolbf  Fitness = 2

Generation2: hvmvocftrolbi  Fitness = 2

Generation3: tvmvorftfolbi  Fitness = 4

Generation4: tvmvorftfolbe  Fitness = 5

Generation5: tvmvorftfolbe  Fitness = 5

Generation6: tvmvorftftlbe  Fitness = 6

Generation7: tvmvorftftobe  Fitness = 7

Generation8: tvmvorntftobe  Fitness = 8

Generation9: tvmvorntftobe  Fitness = 8

Generation10: tvmvorntftobe  Fitness = 8

Generation11: tvmvornwftobe  Fitness = 8

Generation12: tvmeornwftobe  Fitness = 9

Generation13: tvmeornoftobe  Fitness = 10

Generation14: tvmeornoftobe  Fitness = 10

Generation15: tomeornoftobe  Fitness = 11

Generation16: tobeornoftobe  Fitness = 12

Generation17: tobeornovtobe  Fitness = 12

Generation18: tobeornovtobe  Fitness = 12

Generation19: tobeornovtobe  Fitness = 12

Generation20: tobeornottobe  Fitness = 13

Generation21: tobeornottobe  Fitness = 13

Generation22: tobeornottobe  Fitness = 13

Generation23: tobeornottobe  Fitness = 13

Generation24: tobeornottobe  Fitness = 13

Generation25: tobeornottobe  Fitness = 13

Generation26: tobeornottobe  Fitness = 13

Generation27: tobeornottobe  Fitness = 13

Generation28: tobeornottobe  Fitness = 13

Generation29: tobeornottobe  Fitness = 13

Generation30: tobeornottobe  Fitness = 13

Generation31: tobeornottobe  Fitness = 13

Generation32: tobeornottobe  Fitness = 13

Generation33: tobeornottobe  Fitness = 13

Generation34: tobeornottobe  Fitness = 13

Generation35: tobeornottobe  Fitness = 13

Generation36: tobeornottobe  Fitness = 13

Generation37: tobeornottobe  Fitness = 13

Generation38: tobeornottobe  Fitness = 13

Generation39: tobeornottobe  Fitness = 13

Generation40: tobeornottobe  Fitness = 13

Generation41: tobeornottobe  Fitness = 13

Generation42: tobeornottobe  Fitness = 13

Generation43: tobeornottobe  Fitness = 13

Generation44: tobeornottobe  Fitness = 13

Generation45: tobeornottobe  Fitness = 13

Generation46: tobeornottobe  Fitness = 13

Generation47: tobeornottobe  Fitness = 13

Generation48: tobeornottobe  Fitness = 13

Generation49: tobeornottobe  Fitness = 13

Generation50: tobeornottobe  Fitness = 13

И как видно, уже после 20 поколения популяция произвела нужную фразу. Хочу вас предупредить, что если вы запустите выполнять newGenerate еще раз, то у вас может получится немного разный результат. Т.е. на каком поколение будет получена требуемая фраза.

Мы увидели, что добавлении вероятности в естественном отборе не ведет к хаосу, а наоборот, ведет к порядку и смыслу. Но мы в этом примере еще не использовали спаривание и воспроизведение потомства.

Продолжение следует.  

Всего доброго!