Генетические алгоритмы в Mathematica (1)
Никогда раньше блог не вела. Так что не судите строго и все
комментарии приветствуются. Буду рада вашим вопросам и пожеланиями.
Верите вы или нет в эволюционное развитие жизни на этой
планете, но теория естественного отбора предлагает некоторые убедительные
аргументы. Так люди с определенными характеристиками в большей степени способны
выжить и передать эти характеристики их потомству. Мы все знаем о естественном
отборе, как о способе природы выбирать лучшие организмы. Генетический алгоритм (ГА)
– это общая процедура поиска на основе идей генетики и естественного отбора.
Решение методологии ГА напоминает половое размножение, в
котором гены двух родителей объединяются, дабы сформировать детей. Будем
основываться на том, что мы можем создать популяцию особей, которая каким-то
образом предоставляет возможность решения поставленной нами задачи. Эти особи
имеют определенные характеристики, которые делают их более или менее подходящими
в качестве членов популяции, и мы связываем это с вероятностью пригодности к
деторождению (спаривания). Наиболее подходящие особи будут иметь высокую
вероятность спаривания, чем менее приспособленные особи. Эффективность ГА
заключается в том, что при скрещивании особей популяции, производится
потомство, у которых есть значительный шанс сохранить желаемые характеристики
своих родителей, возможно, даже сочетающий лучшие характеристики обоих
родителей. Таким образом, общая приспособленность популяции потенциально может
увеличиться с поколением, так мы получаем лучшее решение нашей задачи.
Рассмотрим следующий пример.
Десять обезьянок печатают на
десяти пишущих машинках. Им позволяют набрать 13 строчных букв. Будем называть
этот набор фраз поколением. Если ни одна из обезьянок не набрала фразу «tobeornottobe», тогда
начинаем снова с чистого листа для каждой обезьянки. Давайте смоделируем
эксперимент с помощью Mathematica
нескольких поколений прозы обезьянок. Функция FromCharacterCode в Mathematica преобразует
ASCII код элемента списка в их соответствующие символы. Будем использовать
функцию для создания текста из случайно сгенерированного списка кодов символов.
generate[]:=
TableForm[Map[FromCharacterCode,Table[Random[Integer,{97,122}],{i,1,10},{j,1,13}]]]
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 еще раз, то у вас может получится
немного разный результат. Т.е. на каком поколение будет получена требуемая фраза.
Мы увидели, что добавлении вероятности в естественном отборе
не ведет к хаосу, а наоборот, ведет к порядку и смыслу. Но мы в этом примере
еще не использовали спаривание и воспроизведение потомства.
Продолжение следует.
Всего доброго!
Использованная литература:
ОтветитьУдалитьSimulating neural network by James a. Freeman
Best Casino in South Africa (2021) - A complete Guide
ОтветитьУдалитьCasinoBonus100 free spins no 숫자 야구 필승법 deposit. 100 Free Spins on 토토 사이트 리스트 Immortal 골인 벳 Romance. 1xbet скачать 100 Free Spins on Immortal Romance ✓ Play on Immortal Romance Slots ✓ Immortal Romance Slot 스 크릴 Machine.