Отправляет email-рассылки с помощью сервиса Sendsay
  Все выпуски  

Технологии обработки данных в прогнозировании


Служба Рассылок Subscribe.Ru

rass_4

Выпуск 3.   Генетические алгоритмы (Часть 2)

  В рассылке представлены аналитические материалы как лично мои так и те, которые будут присылаться, а также информация, полученная  из других источников. Будут указаны ссылки на литературу. Список литературных и электронных источников  находится на сайте (здесь).  При возможности там же будут указаны и адреса. На вопросы буду отвечать лично, или включать их в рассылку, или помещать в форум на сайте. Разные рассылки будут ориентированы на разный уровень читателей. Так что не огорчайтесь, если текст для Вас слишком легкий, или совсем непонятный. Возможно cледующий материал будет специально для Вас. Ну вот и все. Приступаем!

Предыдущие выпуски

                                                           Здравствуйте!                                                             

     

Постановка задачи (одной из…). Предположим, что некоторая переменная 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-a=maxъ bi-a. Пусть его длина 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;

 

        
                                                       

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

                                 Написать автору рассылки

 


http://subscribe.ru/
E-mail: ask@subscribe.ru
Отписаться
Убрать рекламу

В избранное