Генетические алгоритмы в 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

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