[ссылки] [литература] [проекты] [программы] [методические указания] [монографии и статьи] [вопросы и ответы] [школы] [учебники] [новости]
ENG  |   Карта сайта
Информация
Проект преследует цель популяризации идей применения природных механизмов функционирования для решения задач прогнозирования, оптимизации и поддержки принятия решений

Cписок рассылки
Открыть в новом окне

  1. Введение
  2. Генетические алгоритмы (1)
  3. Генетические алгоритмы (2)
  4. Генетические алгоритмы (3)
  5. Тренды
  6. Полиномиальные тренды
  7. Тригонометрические тренды
  8. Нейронные сети
  9. Метод наименьших квадратов
  10. Метод обратного распространения ошибки
  11. Множественная линейная модель
  12. Нестандартный выпуск. Анкета
  13. МЛМ. Пример расчета
  14. RBF-сеть
  15. Сеть встречного распространения
  16. Первая интерполяционная формула Ньютона
  17. МГУА (1)
  18. Вторая интерполяционная формула Ньютона
  19. Метод Брандона
  20. МГУА (2)
  21. Интерполяционные формулы Гаусса
  22. Интерполяционные формулы Стирлинга и Лагранжа
  23. МГУА (3)
  24. МГУА (4)
  25. Предварительная обработка данных (1)
  26. Предварительная обработка данных (2)
  27. Предварительная обработка данных (3)
  28. Box-counting
  29. Гетероскедастичность
  30. Введение в нечеткую логику
  31. Обобщённый метод наименьших квадратов
  32. Прогнозирование с помощью функций с гибкой структурой
  33. Автокорреляция
  34. Дистрибутивно-лаговые модели (1)
  35. Дистрибутивно-лаговые модели (2)
  36. Дистрибутивно-лаговые модели (3)
  37. Моделирование данных при помощи кривых для восстановления пробелов в таблицах (1)
  38. Нестандартный выпуск. Анонс книги Цейтлина Н.А."Опыт аналитического статистика"
  39. Алгоритм ZET
  40. Алгоритм ZetBraid
  41. Метод эволюционной кластеризации
  42. Эволюционный метод восстановления пропусков в данных
  43. Алгоритмы кластеризации класса FOREL
Выпуск 3. Генетические алгоритмы (Часть 2)
Постановка задачи (одной из…).Предположим, что некоторая переменная 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;

ГГНИ и История
Сайт создан в системе uCoz