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

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

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

1. Инициировать начальный момент времени t=0. Случайным образом сформировать начальную популяцию, состоящую из k особей. B₀ = {A₁,A₂,…,A_k)
2. Вычислить приспособленность каждой особи F_Ai = fit(A_i) , i=1…k и популяции в целом F_t = fit(B_t) (также иногда называемую термином фиттнес). Значение этой функции определяет насколько  хорошо подходит особь, описанная данной хромосомой, для решения задачи.
3. Выбрать особь A_c из популяции. A_c = Get(B_t)
4. С определенной вероятностью (вероятностью кроссовера P_c) выбрать вторую особь из популяции А_c1 = Get(B_t) и произвести оператор кроссовера A_c = Crossing(A_c,A_c1).
5. С определенной вероятностью (вероятностью мутации P_m) выполнить оператор мутации. A_c = mutation(A_c).
6. С определенной вероятностью (вероятностью инверсии P_i) выполнить оператор инверсии A_c = inversion(A_c).
7. Поместить полученную хромосому в новую популяцию insert(B_t+1,A_c).
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).       Продолжение в следующем выпуске.