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

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

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

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