Постановка
задачи (одной из…).Предположим,
что некоторая переменная Y зависит от множества значений других переменных X=(X1, X2
,.., Xn). Имеется статистическая таблица исходных данных:
X1 |
X2 |
X3 |
Y |
5 |
6 |
8 |
10 |
13 |
4 |
6 |
17 |
………. |
……….. |
…………. |
…………. |
10 |
5 |
4 |
13 |
Рассмотрим случай, когда зависимость Y=f(X1,
X2 ,.., Xn) достаточно сложная и нелинейная. Примечание: проблемы
подобного рода сплошь и рядом. Сделаем допущение просто мало вероятное (об этом позже): зависимость
f установлена и она имеет, например, такой вид:
Y=4,5+sin(X1X2)-X34+Ln(X1/X3)EXP(13,4*(X2X32)).
То, что получено такое выражение означает
решение задачи структурной и параметрической идентификации. Структурной потому,
что определен вид зависимости, а параметрической потому. что определены значения параметров
(4,5 и 13,4). Имея такую зависимость трудно установить, какой из факторов X1,
X2 ,.., Xn, будем их так называть, оказывает наибольшее и наименьшее,
положительное и отрицательное влияние на результирующий показатель Y.
Предположим, что какая то часть факторов
является управляемой, то есть их значения могут быть определены в некоторых пределах заинтересованным
лицом с целью минимизации или максимизации Y. Без ограничения общности будем считать все
факторы управляемыми, а также известными пределы их изменения, т.е. интервалы (ai, bi),
i={1,2,..,n}. Если эти условия не выполнены, то задача будет иметь другой вид (об этом позже).
В нашем случае задача заключается в нахождении максимума функции f с точностью e
, при известных предположениях об управляемости факторов и известности интервалов их значений.
То, что указана точность решения свидетельствует
об априорном допущении о том, что полученное решение будет отличаться от точного на величину e
и это не противоречит нашим желаниям. Указанную задачу можно решить и методом полного перебора,
но комбинаторная сложность такого подхода зачастую делает его неприменимым из-за времени расчета
сравнимого с временем существования человечества или Вселенной. Поэтому предложим более компактный
метод решения на базе ГА.
Начнем с задачи удовлетворения требованию
точности. Понятно, что все интервалы (ai, bi), i={1,2,..,n}, в общем
случае, разные. Возможны два приема:
1. Выбираем такой интервал, для которого
справедливо ъ bi-aiъ =maxъ bi-aiъ . Пусть его
длина m. Тогда для того, чтобы точность решения была e , необходимо разбить этот интервал
и все остальные на k-1=m/e отрезков. Длина каждого отрезка и будет e , что при попадании
решения на некоторый отрезок и будет гарантировать требуемую точность решения.
2. Во втором случае будем нормировать все
факторы и результирующий показатель. Для этого можно использовать, например, такие выражения:
x'=(x-xmin)/(xmax-xmin),
x'=(x-xсреднее)/s , x'=1/(1+exp(+-x), где s - выборочное среднее
квадратическое отклонение (см. в книжке по теории вероятностей и математической статистике). У
каждого вида нормировки есть свои преимущества и недостатки. Желающие могут потренироваться
в определении e ', поскольку точность тоже изменится. Показатель Y после
получения оптимального решения тоже необходимо пересчитать.
Мне импонирует второй прием, но рассмотрим
первый. Пусть, например, a=0, b=8,m=8, e=0.4, тогда k=21. В результате разбиения
получим такие точки отрезка [0,8]: {0; 0,4; 0.8;…;8}. Такое множество возможных значений
называется фенотипом. Поставим в соответствие фенотипу его целочисленный аналог следующим
образом: {0; 0,4; 0.8;…;8}® {0; 1; 2;…; 21}. Целочисленному аналогу надо сопоставить
его двоичный генотип. Для этого предварительно необходимо определить количество разрядов двоичного
представления, поскольку все элементы бинарного представления для корректной работы ГА должны
иметь одинаковую длину, например, p=[log2k]+1. Неизбежно возникает избыточность,
поскольку генотипов будет больше чем фенотипов. Некоторые авторы предлагают считать значение функции
f в таких точках равным нулю. Тогда возникают дополнительные шаги ГА и время вычислений растет.
Мы предлагаем [6] разбивать исходный интервал на 2p+1 интервалов, тем
самым увеличивая точность. В результате всех этих манипуляций мы получим наборы фенотипов, целочисленных
аналогов и генотипов. Все подготовительные операции для ГА закончены.
Далее приведены две процедуры: первая - для
преобразования генотипа в виде строчной переменной ss в целочисленный десятичный аналог s, kk
- число бинарных разрядов.
Procedure Tgenetic.Str_bin_to_dec(var
ss:string;var s:integer;var kk:byte);
var s1:string; k,c1,l,i,p:integer;
begin
s:=0;p:=1;
for i:=0 to kk-1 do begin
s1:=copy(ss,kk-i,1);
val(s1,c1,k);
s:=s+c1*p;
p:=p*2;
end; end;
вторая - преобразование целого положительного
числа a в бинарную строковую форму, l - длина строки.
procedure Tgenetic.Dec_to_bin_str(var a:integer;var
b:string;var l:byte);
var c,v:string; i,d:byte;aa:integer;
begin
b:='';aa:=a;
while aa>1 do begin
d:=aa mod 2; aa:=aa div 2;
str(d,c);
b:=concat(c,b);
end;
str(aa,c);
b:=concat(c,b);
if length(b)<l then
for i:=1 to l-length(b) do
b:=concat('0',b);
end;