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

A Basic Genetic Algorithm 2.1

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

Описание настоящих BGA требует только несколько утверждений.

1.       Начинается со случайного генерирования популяции особей.

2.       Определяется приспособленность каждой особи в текущей популяции.

3.       Выбор родителей для следующего размножения (потомства) с равно вероятностной приспособленностью.

4.       Спаривание выбранных родителей для воспроизводства популяции нового поколения.

5.       Повтор пунктов 2-4.

The Fitness Function

Давайте начнем наш пример с определения величины, определяющей приспособленность особи. Рассмотрим функцию

f[x_]:=1+Cos[x]/(1+0.01 x^2)

Мы предполагаем, что это функция есть измерение приспособленности индивидуального фенотипа, x. Фенотип, x, это численная величина, которая декодируется из хромосомы. Давайте рассмотрим поведение функции приспособленности.

Plot[f[x],{x,-45,45}, PlotPoints-> 200]

Обратим внимание, что оптимальное значение функции в точке x=0 , но заметим также, что существует много локальных максимумов, которые субоптимальны. Традиционный метод спуска, если бы он случайно начался где-то на центральном пике, то быстро бы добрался до одного из субоптимального пика и застрял бы там.

Chromosome Representation

Каждый фенотип – это значение, декодированное из хромосомы. Будем использовать хромосомы с бинарными аллелями для примера. Мы решили представить хромосому как десятизначную бинарную строку и ограничим фенотип в пределах от -40 до 40. Поэтому хромосома {0,0,0,0,0,0,0,0,0,0} должна декодироваться в значение -40, а хромосома {1,1,1,1,1,1,1,1,1,1} в 40.

Двоичное число 1111111111 равно десятичному числу 1023. Если мы умножим это число как 80/1023

N[80/1023,20]

0.078201368523949169110

вычтем 40 и получим 40

1023 (80.0/1023)-40

40.

Аналогично получаем, что 0000000000 есть -40

0 (80.0/1023)-40

-40.

Функция decodeBGA олицетворяет процедуру перекодировки. Функция перевода  из двоичного числа в десятичное следующая, используем 1010101010 для примера. Для начала, определим местоположение единиц в строке.

pList=Flatten[Position[{1,0,1,0,1,0,1,0,1,0},1]]

{1,3,5,7,9}

Теперь вычислим 2 в степени местоположения для каждой единицы.

values=Map[2^(10-#)&,pList]

{512,128,32,8,2}

Сложим эти величины

decimal=Apply[Plus,values]

682

Между прочим, существует весьма элегантный способ перевода двоичного числа в десятичное, используя схему Горнера, который воплощен в следующей функции

Horner[u_List,base_:2]:=Fold[base #1+#2&,0,u]

Проверим эту функцию на том же числе

Horner[{1,0,1,0,1,0,1,0,1,0}]

682

Наконец-то, конвертируем число в промежутке от -40 до 40

phenotype=decimal (0.078201368523949169)-40

13.3333

decodeBGA[chromosome_]:=
Module[{plist, lchrom,values,phenotype},
lchrom=Length[chromosome];
pList=Flatten[Position[chromosome,1]];
values=Map[2^(lchrom-#)&,pList];
decimal=Apply[Plus,values];
phenotype=decimal (0.07820136852394)-40;
Return[phenotype];
];

Наибольший отрицательный фенотип у хромосомы {0,1,1,1,1,1,1,1,1,1}

decodeBGA[{0,1,1,1,1,1,1,1,1,1}]

-0.0391007

Наименьший положительный фенотип у хромосомы {1,0,0,0,0,0,0,0,0,0}

decodeBGA[{1,0,0,0,0,0,0,0,0,0}]

0.0391007

Функция f[x] определяет приспособленность отдельного фенотипа.

f[-0.0391007]

1.99922

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

Аппроксимация. Интерполирование. Экстраполяция.

Как известно, есть 3 способа задания функции:

1) аналитический

2) графический

3) табличный

Табличный способ обычно возникает в результате эксперимент. Недостаток табличного
задания функции заключается в том, что найдутся значения переменных, которые 
неопределенны таблицей. Тут нам и понадобится это загадочная аппроксимация. 

 Итак 

Аппроксимация, или приближение — научный метод, состоящий в замене одних объектов другими, в том или ином смысле близкими к исходным, но более простыми.

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

 Обычно на практике используют классы самых простейших функций:

·        линейные комбинации функций 1,x,x^2,…,x^n, т.е. функции из класса полиномов степени не выше n (аппроксимация алгебраическим многочленом заданной 
степени);

·        линейные комбинации функций Sin(akx) и Cos(akx) (аппроксимация 
тригонометрическим многочленом, или отрезком ряда Фурье);

·        комбинации экспоненциальных функций Exp(Λkx) c вышеуказанными и 
некоторые другие.

В качестве критерия согласия используют три условия:

1. точное совпадение значений искомой функции с “экспериментом” - со значениями в узлах таблицы (критерий интерполяции);

2. сумма квадратов отклонений значений искомой и табличной функций минимальна 
(критерий среднеквадратической аппроксимации);

3. максимальное по абсолютной величине из отклонений значений искомой и 
табличной функций минимально (критерий равномерной аппроксимации).

Типичной задачей аппроксимации функций является задача интерполяции.

Простейшая  задача  интерполяции  заключается  в  следующем.  

На  отрезке [a, b]  заданы  n + 1  точки 

xi = х0, х1, . . ., хn,

которые называются узлами интерполяции, и значения некоторой функции f(x)  в этих 
точках 

f(x0) = y0,  f(x1) =  y1,  . . ., f(xn) = yn. (1) 

Требуется  построить  функцию  Φ(х) (интерполяционная  функция),  принадлежащую  
известному  классу  и принимающую в узлах интерполяции те же значения, что и f(x), т. е. 
такую, что 

Ф(x0) = y0, Ф(x1) =  y1,  . . ., Ф(xn) = yn.  (2) 

Геометрически это означает, что нужно найти кривую y = Φ(х) некоторого определенного типа, проходящую через заданную систему точек M(xi, yi) (i = 0, 1, ..., n) (Рисунок 1).

В такой общей постановке задача может иметь бесконечное множество решений или совсем не иметь решений.

Однако эта задача становится однозначной, если вместо произвольной функции

 Φ(х) искать полином ϕ(х) (интерполяционный полином) степени не выше n, 
удовлетворяющий условиям (2), т. е. такой, что 

ϕ (x0) = y0, ϕ (x1) =  y1,  . . ., ϕ (xn) = yn.  (3) 

Полученную интерполяционную формулу 

ϕ (x0)=anx^n+an-1x^(n-1)+...+a1x+a0

обычно используют для приближенного вычисления значений данной функции ƒ(х) для 

значений аргумента х, отличных от узлов интерполяции. Такая операция называется 
интерполяцией функций. 

Различают два вида интерполяции: 

1)  глобальная - соединение  всех точек ƒ(х) единым интерполяционным полиномом; 

2)  локальная - соединение точек  отрезками прямой (по двум точкам), отрезками 
параболы (по трем точкам).

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

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

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

Генетические алгоритмы в 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 еще раз, то у вас может получится немного разный результат. Т.е. на каком поколение будет получена требуемая фраза.

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

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

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