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

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

Рассылка закрыта

При закрытии подписчики были переданы в рассылку "Технологии анализа данных" на которую и рекомендуем вам подписаться.

Вы можете найти рассылки сходной тематики в Каталоге рассылок.

←   Апрель 2002   →
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
Автор
basegrouplabs

Статистика

2.348 подписчиков
-1 за неделю
←   Все выпуски   →

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


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

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

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

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

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

Историческая справка. Одним из методов нахождения экстремумов сложных функций сегодня есть генетические алгоритмы (ГА). ГА есть одной из составляющих эволюционного моделирования как научного направления, базирующегося на принципах природного отбора по Ч. Дарвину (см. напр. [1,2]). Генетический алгоритм впервые был предложен в 1975 году в Мичиганском университете John Holland [3] (Джоном Холландом). Он получил название репродуктивный план Холланда и в дальнейшем активно использовался в качестве базового алгоритма в эволюционных вычислениях. Дальнейшее развитие ГА, как собственно и свое название, получили в работах Goldberg D.E. (Гольдберга) в лаборатории ГА Иллинойса, De Jong K.A. (Кеннет Де Йонг) в университете Джорджа Мейсона, Вирджиния и их учеников. Ссылки на их работы, а также работы других ученых приведены здесь.

Базовый алгоритм. Рассмотрим базовый ГА [3,4]. Я переписал его с сайта лаборатории BaseGroup. Адрес здесь.

  1. Инициировать начальный момент времени t=0. Случайным образом сформировать начальную популяцию, состоящую из k особей. B0 = {A1,A2,…,Ak)
  2. Вычислить приспособленность каждой особи FAi = fit(Ai) , i=1…k и популяции в целом Ft = fit(Bt) (также иногда называемую термином фиттнес). Значение этой функции определяет насколько  хорошо подходит особь, описанная данной хромосомой, для решения задачи.
  3. Выбрать особь Ac из популяции. Ac = Get(Bt)
  4. С определенной вероятностью (вероятностью кроссовера Pc) выбрать вторую особь из популяции Аc1 = Get(Bt) и произвести оператор кроссовера Ac = Crossing(Ac,Ac1).
  5. С определенной вероятностью (вероятностью мутации Pm) выполнить оператор мутации. Ac = mutation(Ac).
  6. С определенной вероятностью (вероятностью инверсии Pi) выполнить оператор инверсии Ac = inversion(Ac).
  7. Поместить полученную хромосому в новую популяцию insert(Bt+1,Ac).
  8. Выполнить операции, начиная с пункта 3, k раз.
  9. Увеличить номер текущей эпохи t=t+1.
  10. .  Если выполнилось условие останова, то завершить работу, иначе переход на шаг 2.

Для того,  кому этот алгоритм знаком, он полностью прозрачен. Для того, кто видит его впервые, я приведу основные понятия и постановку задачи, для решения которой он может быть использован.

Пусть S - некоторая система или процесс. Ее атрибутами есть  X - вектор входных и внутренных параметров, Y - вектор  выходных переменных. Пусть закон Y=f(X) идентифицирован (об этом мы поговорим позже) и зависимость f   достаточно сложная. Известны также пределы возможных изменений составляющих вектора X. Необходимо найти такие значения вектора X, чтобы значение Y было оптимальным.

Я не хочу сказать, что такая задача неразрешима другими методами, но в случае достаточно сложной, возможно разрывной,   полиэкстремальной функции f  думаю, что сделать это очень и очень сложно. Впрочем, можно обсуждать.

Как решается задача с использованием ГА? Функция f называется фитнесс-функцией. Возможные значения элемента вектора X есть его фенотипом. Двоичное представление фенотипа есть генотип (напр. 12,345->100011). Генотип имеет определенное количество элементов (об этом позже). Один или несколько генотипов (по количеству элементов X) представляют хромосому. Кроссовером называют деление двух хромосом и обмен частями (напр. 1100 и 1010 ->1110 и 1000). Мутация - инвертирование одного из элементов хромосомы (напр. 0000->0100). Инверсия - изменение порядка следования частей хромосомы (напр. 1100->0011).       Продолжение в следующем выпуске.

Анонс следующих выпусков.

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

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

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