| Выпуск 3. Генетические алгоритмы (Часть 2) | ||||||||||||||||||||
Постановка
задачи (одной из…).Предположим,
что некоторая переменная Y зависит от множества значений других переменных X=(X1, X2
,.., Xn). Имеется статистическая таблица исходных данных:
Рассмотрим случай, когда зависимость 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; |
| РЕКЛАМА: |