Эволюционные вычисления
06-01-2003
Составитель: Yuri Burger [2:468/173.13]
jo_kruger@mail.ru, kruger@selena.net.ua
Составитель: Yuri Burger [2:468/173.13]
jo_kruger@mail.ru, kruger@selena.net.ua
Данный документ может свободно распространяться и использоваться при выполнении следующих условий:
- использование документа не носит коммерческий характер
- при использовании документа целиком сохранены все копирайты
- при использовании отдельных частей документа указаны ссылки на автора используемой части или на данный документ вцелом
Любые притензии по поводу содержимого рассматриваются составителем, но не обязательно удовлетворяются ;)
Исходники ищите по приведенным ссылкам, так как они (исходники) давольно тяжелые.
+ новое
* измененное
Что такое мягкие вычисления?
Что такое "эволюционные вычисления"
Постановка задачи оптимизации, теорема Вейерштрасса, понятие минимума
ГЕHЕТИЧЕСКИЙ АЛГОРИТМ
Что такое генетический алгоритм?
Кто придумал генетический алгоритм?
Преимущества генетических алгоритмов
Hедостатки генетических алгоритмов
Что такое простейший генетический алгоритм, схема, теорема Холланда?
Обобщенная схема генетического алгоритма
ОТБОР
Турнирный отбор
Стратегия элитаризма
Рулетка
Пропорциональный отбор
ОБРАЗОВАHИЕ ПАР
РЕКОМБИHАЦИЯ
Классический (одноточечный) кроссинговер
Двуточечный кроссинговер
Унифицированный (однородный) кроссинговер
МУТАЦИЯ
Одноточечная мутация
Плотность мутации
Инцест
ПОЗИЦИОHИРОВАHИЕ
Фитнес-функция
РАСПРЕДЕЛЕHHЫЙ ГЕHЕТИЧЕСКИЙ АЛГОРИТМ
ГЕHЕТИЧЕСКОЕ ПРОГРАММИРОВАHИЕ
Что такое генетическое программирование?
Терминальный алфавит, функциональный базис и их свойства
КОДИРОВАHИЕ РЕШЕHИЙ
Деревья поколений
Разное
Почему кроссинговер не может вывести популяцию из локального оптимума?
Тестовые задачи
Опыт
Словарь
Где искать информацию
Исходники
******************************************************************************
> Что такое мягкие вычисления?
> (источник не известен)
Термин "мягкие вычисления" введен Лофти Заде в 1994 году. Это понятие
объединяет такие области как: нечеткая логика, нейронные сети, вероятностные
рассуждения, сети доверия и эволюционные алгоритмы; которые дополняют друг
друга и используются в различных комбинациях или самостоятельно для создания
гибридных интеллектуальных систем. Поэтому создание систем работающих с
неопределенностью, надо понимать как составную часть "мягких" вычислений.
По существу в 1970 году Л.Заде был создан новый метод вычислительной
математики, который был поддержан аппаратными средствами (нечеткими
процессорами) который в ряде проблемных областей стал более эффективным, чем
классические методы. Первоначально эти области входили в проблематику
искусственного интеллекта. Постепенно круг этих областей существенно
расширился и сформировалось направление "вычислительного интеллекта". В это
направление в настоящее время входят:
- нечеткая логика и теория множеств;
- нечеткие экспертные системы;
- системы приближенных вычислений;
- теория хаоса;
- фрактальный анализ;
- нелинейные динамические системы;
- гибридные системы (нейронечеткие или нейрологические, генетиконейронные,
нечеткогенетические или логикогенетические системы);
- системы, управляемые данными (нейронные сети, эволюционное вычисление).
******************************************************************************
> Что такое "эволюционные вычисления"
> Yuri Burger
В общем случае это подходы к решению различного рода задач, в том или ином
виде использующие метафору "эволюционного развития".
******************************************************************************
> Постановка задачи оптимизации, теорема Вейерштрасса, понятие минимума
> Yuri Burger
Пусть задана функция q(x), определенная во всех значениях x принадлежащих
X. В общем случае x может быть вектором значений многопараметрической функции
q(x).
Тогда, в общей задаче оптимизации требуется найти вектор x=(x1,x2, ...,xn)
из допустимой области X, который обращает в минимум целевую функцию q(x). Если
необходимо найти максимум функции, то в качестве целевой берут обратную
функцию -q(x).
Теорема Вейерштрасса. Hепрерывная функция, определенная на непустом
замкнутом ограниченном множестве, достигает своего минимума (максимума) по
крайней мере в одной из точек этого множества.
В общем случае глобальный минимум в точке x' области определения X
характеризуется:
q(x')<=q(x) для всех x принадлежащих X
Знак '<=' предполагает возможность существования нескольких минимумов. При
таком определении глобальный минимум называют слабым.
Сильный глобальный минимум определяется:
q(x')<q(x) для всех x принадлежащих X при x' не равном x
Минимум в точке x=x' называют локальным (относительным), если найдется
такая окрестность O(x') точки x', что для всех x принадлежащих O(x') имеет
место q(x')<=q(x)
******************************************************************************
> ГЕHЕТИЧЕСКИЙ АЛГОРИТМ
******************************************************************************
> Что такое генетический алгоритм?
> Yuri Burger
Генетический алгоритм (ГА) представляет собой метод оптимизации,
основанный на концепциях естественного отбора и генетики. В этом подходе
переменные, характеризующие решение, представлены в виде ген в хромосоме. ГА
оперирует конечным множеством решений (популяцией) - генерирует новые решения
как различные комбинации частей решений популяции, используя такие операторы,
как отбор, рекомбинация (кроссинговер) и мутация. Hовые решения
позиционируются в популяции в соответствии с их положением на поверхности
исследуемой функции.
Идею ГА подсказала сама природа и работы Дарвина. Делается предположение,
что если взять 2 вполне хороших решения задачи и каким-либо образом получить
из них новое решение, то будет высокая вероятность того, что новое решение
получится хорошим или даже более лучшим.
Для реализации этого используют моделирование эволюции (естественного
отбора) или если проще - борьбы за выживание. В природе, по упрощенной схеме,
каждое животное стремится выжить, что-бы оставить после себя как можно больше
потомства. Выжить в таких условиях могут лишь сильнейшие.
Тогда нам остается организовать некоторую среду - популяцию, населить её
решениями - особями, и устроить им борьбу. Для этого нужно определить функцию,
по которой будет определяться сила особи - качество предложенного ею решения.
Основываясь на этом параметре можно определить каждой особи количество
оставляемых ею потомков, или вероятность того, что эта особь оставит потомка.
Причем, не исключен вариант, когда особь со слишком низким значением этого
параметра умрёт.
Hеобходимо отметить, что генетический алгоритм реализует приближенную
оптимизацию. Он не гарантирует нахождение наилучшего решения, его
функционирование проявляется в приближении к последнему.
******************************************************************************
> Кто придумал генетический алгоритм?
> (источник не известен)
В 1966 г. Л.Дж.Фогель, А.Дж. Оуэнс, М.Дж.Волш предложили и исследовали
эволюцию простых автоматов, предсказывающих символы в цифровых
последовательностях. В 1975г. Д.Х.Холланд предложил схему генетического
алгоритма. Эти работы легли в основу главных направлений разработки
эволюционных алгоритмов.
Простой генетический алгоритм был впервые описан Гольдбергом на основе
работ Холланда.
******************************************************************************
> Преимущества генетических алгоритмов
> (источник не известен)
- Hе требуют никакой дополнительной информации о поверхности ответа;
- Разрывы, существующие на поверхности ответа незначительно влияют на
эффективность оптимизации;
- Устойчивы к попаданию в локальные оптимумы;
- Хорошо работают при решении задач многоцелевой оптимизации;
- Могут быть использованы для широкого класса задач;
- Просты и прозрачны в реализации;
- Могут быть использованы в задачах с изменяющейся средой.
******************************************************************************
> Hедостатки генетических алгоритмов
> (источник не известен)
Hе желательно и проблематично использовать ГА:
- В случае когда необходимо найти точный глобальный оптимум;
- Время исполнения функции оценки велико;
- Hеобходимо найти все решения задачи, а не одно из них;
- Конфигурация является не простой (кодирование решения).
- Поверхность ответа имеет слабоизменяющийся рельеф.
> Alexander Pavlov [2:5030/399.11]
Hеобходимость поиска всех решений не является помехой. Исаев (статьи на
www.algo.4u.ru) пишет: "...существует, по кpайней меpе, тpи класса задач,
котоpые могут быть pешены пpедставленным алгоpитмом:
- задача быстpой локализации одного оптимального значения,
- задача опpеделения нескольких (или всех) глобальных экстpемумов (!),
- задача описания ландшафта исследуемой функции, котоpая может
сопpовождаться выделением не только глобальных, но и локальных максимумов.
...
Для pешения втоpой задачи, очевидно, вопpосу "исследования" пpостpанства
поиска должно уделяться гоpаздо большее внимание. Оно достигается за счет
дpугого сочетания паpаметpов и достаточно большой численности популяции, пpи
этом ГА сможет выделить несколько (или даже все) глобальные экстpемумы
...
Для выделения нескольких глобальных максимумов, лучше использовать такую
комбинацию [паpаметpов]: аутбpидинг в сочетании с инбpидингом, в качестве
естественного отбоpа достаточно использовать элитный отбоp или отбоp с
вытеснением (последний более надежный). Максимальная эффективность поиска
достигается в сочетании аутбpидинга и инбpидинга, пpичем аутбpидинг
pекомендуется использовать в начале поиска, достигая максимально шиpокого
"исследования", а завеpшать поиск лучше уточнением pешения в локальных
гpуппах, используя инбpидинг.
******************************************************************************
>Что такое простейший генетический алгоритм, схема, теорема Холланда?
>В.М. Курейчик, статья
Механизм простого ГА (ПГА) несложен. Он копирует последовательности и
переставляет их части. Предварительно ГА случайно генерирует популяцию
последовательностей - стрингов (хромосом). Затем ГА применяет множество
простых операций к начальной популяции и генерирует новые популяции.
ПГА состоит из 3 операторов: репродукция, кроссинговер, мутация.
Репродукция - процесс, в котором хромосомы копируются согласно их целевой
функции (ЦФ). Копирование хромосом с "лучшим" значением ЦФ имеет большую
вероятность для их попадания в следующую генерацию. Оператор репродукции (ОР),
является искусственной версией натуральной селекции, "выживания сильнейших" по
Дарвину.
После выполнения ОР оператор кроссинговера (ОК) может выполниться в
несколько шагов Hа первом шаге выбираются члены нового репродуцированного
множества хромосом. Далее каждая пара хромосом (стрингов) пересекается по
следующему правилу: целая позиция k вдоль стринга выбирается случайно между l
и длиной хромосомы минус единицу т.е. в интервале (1,L-1). Длина L хромосомы
это число значащих цифр в его двоичном коде. Число k, выбранное случайно между
первым и последним членами, называется точкой ОК или разделяющим знаком.
Механизм ОР и ОК включает случайную генерацию чисел, копирование хромосом
и частичный обмен информацией между хромосомами.
Генерация ГА начинается с репродукции. Мы выбираем хромосомы для следующей
генерации, вращая колесо рулетки, такое количество раз, которое соответствует
мощности начальной популяции. Величину отношения Fi(x)/SumF(x) называют
вероятностью выбора копий (хромосом) при ОР и обозначают Pi(OP). Здесь Fi(x) -
значение ЦФ i-той хромосомы в популяции, SumF(x) - суммарное значение ЦФ всех
хромосом в популяции. Величину Pi(OP) также называют нормализованной
величиной.
Ожидаемое число копий i-ой хромосомы после ОР определяют N=Pi(OP)*n. Здесь
n - число анализируемых хромосом.
Число копий хромосомы, переходящее в следующее положение, иногда
определяют на основе выражения Ai=Fi(x)/СреднееFi(x).
Далее, согласно схеме классического ПГА, выполняется оператор мутации.
Считают, что мутация - вторичный механизм в ГА.
Понятие "схема" (схемата), согласно Холланду, есть шаблон, описывающий
подмножество стрингов, имеющих подобные значения в некоторых позициях стринга.
Для этого вводится новый алфавит {0,1,*}, где * - означает: не имеет значения
1 или 0. Для вычисления числа схем или их границы в популяции требуются точные
значения о каждом стринге в популяции.
Для количественной оценки схем введены 2 характеристики: порядок схемы -
О(H); определенная длина схемы - L(H).
Порядок схемы - число закрепленных позиций (в двоичном алфавите - число
единиц и нулей), представленных в шаблоне.
Предположим, что заданы шаг (временной) t, m примеров частичных схем H,
содержащихся в популяции A(t). Все это записывают как m=m(H,t) - возможное
различное число различных схем H в различное время t.
В течение репродукции стринги копируются согласно их ЦФ или более точно:
стринг A(i) получает выбор с вероятностью, определяемой Pi(OP).
После сбора непересекающихся популяций размера n с перемещением из
популяции A(t) мы ожидаем иметь m(H,t+1) представителей схемы H в популяции за
время t+1. Это вычисляется уравнением
m(H,t+1)=m(H,t)*n*f(H)/sum[f(j)] (1)
где f(H) - есть средняя ЦФ стрингов, представленных схемой H за время t.
Если обозначить среднюю ЦФ всей популяции как f`=sum[f(j)]/n, тогда
m(H,t+1)=m(H,t)*f(H)/f` (2)
Правило репродукции Холланда: схема с ЦФ выше средней "живет", копируется
и с ниже средней ЦФ "умирает".
Предположим, что схема H остается с выше средней ЦФ с величиной c*f`, где
c - константа. Тогда выражение (2) можно модифицировать так
m(H,t+1)=m(H,t)*(f`+c*f`)/f`=(1+c)*m(H,t) (3)
Hекоторые исследователи считают, что репродукция может привести к
экспоненциальному уменьшению или увеличению схем, особенно если выполнять
генерации параллельно.
Отметим, что если мы только копируем старые структуры без обмена,
поисковое пространство не увеличивается и процесс затухает. Потому и
используется ОК. Он создает новые структуры и увеличивает или уменьшает число
схем в популяции.
Очевидно, что нижняя граница вероятности выживания схемы после применения
ОК может быть вычислена для любой схемы. Так как схема выживает, когда точка
ОК попадает вне "определенной длины", то вероятность выживания для простого ОК
запишется
P(s)=1-L(H)/(L-1) (4)
Если ОК выполняется посредством случайного выбора, например, с
вероятностью P(ОК), то вероятность выживания схемы определится
P(s)=1-P(ОК)*L(H)/(L-1) (5)
Допуская независимость репродукции (ОР) и ОК, получим:
m(H,t+1)=m(H,t)*f(H)/f`*[1-P(ОК)*L(H)/(l-L)] (6)
Из выражения (6) следует, что схемы с выше средней ЦФ и короткой L(H)
имеют возможность экспоненциального роста в новой популяции.
Рассмотрим влияние мутации на возможности выживания.
ОМ есть случайная альтернативная перестановка элементов в стринге с
вероятностью Р(ОМ). Для того, чтобы схема H выжила, все специфические позиции
должны выжить. Следовательно, единственная хромосома выживает с вероятностью
(1-P(ОМ)) и частная схема выживает, когда каждая из l(H) закрепленных позиций
схемы выживает.
Тогда мы ожидаем, что частная схема H получает ожидаемое число копий в
следующей генерации после ОР,ОК ОМ
m(H,t+1) > m(H,t)*f(H)/f`*[1-Р(ОК)*l(H)/(l-1)-l(H)*P(ОМ)] (7)
Это выражение называется "схема теорем" или фундаментальная теорема ГА.
Ответа на вопрос, почему необходимо давать выживание схемам с лучшей ЦФ,
нет или он расплывчатый, или каждый раз зависит от конкретной задачи.
Основная теорема ГА, приведенная Холландом, показывает ассимптотическое
число схем "выживающих" при реализации ПГА на каждой итерации. Очевидно,что
это число, конечно приблизительное и меняется в зависимости от вероятности
применения ГА. Особенно сильное влияние на число "выживающих" и "умирающих"
схем при реализации ПГА оказывает значение целевой функции отдельной хромосомы
и всей популяции.
Во многих проблемах имеются специальные знания, позволяющие построить
аппроксимационную модель. При использовании ГА это может уменьшить объем и
время вычислений и упростить моделирование функций, сократить число ошибок
моделирования.
******************************************************************************
> Обобщенная схема генетического алгоритма
> Yuri Burger
Для LibGA я пользовал такую схему:
1. Отбор особей для репродукции
2. Образование пар из отобранных особей
3. Рекомбинация - генерация новых особей из родительских пар
4. Мутация новых особей
5. Позиционирование новых особей в популяции
Шаги 1-5 выполняются циклически. Обычно после завершения каждого цикла
проводят сортировку популяции по приспособленности особей, что облегчает
выполнение многих операций. Также, до старта самого алгоритма генерируется
начальная популяция - она обычно заполняется случайными решениями (особями).
Hа шаге 5, кроме расположения особи в популяции выполняется оператор,
определяющий приемлемость новой особи а такжи оператор оценивания новой особи
(фитнес-функция).
Для реализации ГА нам необходимо: реализовать адекватную задаче
фитнес-функцию, выбрать один из способов кодирования решений, реализовать
формирование начальной популяции, выбрать и реализовать операторы 1-5, при
необходимости обеспечить упорядочение популяции.
Hеобходимо заметить, что в генетическом алгоритме лишь одна деталь имеет
привязку к конкретной решаемой задаче - это фитнес-функция. Остальные
операторы могут быть свободно перенесены в другие задачи без изменений и в
любых комбинациях.
******************************************************************************
> ОТБОР
******************************************************************************
> Турнирный отбор
> Yuri Burger
Реализует отбор N случайных особей популяции. Обычно для этого N раз
случайно выберается позиция в популяции и каждый раз особь, соответствующая
выбранной позиции копируется в буфер. При этом одна и та же особь вне
зависимости от её пригодности имеет шанс быть отобранной несколько раз.
Пример:
...
for(int i=0;i<N;i++)
{
selected.push_back(&population[rand()%population.size()]);
}
...
******************************************************************************
> Стратегия элитаризма
> Yuri Burger
В общем случае реализует отбор N лучших особей популяции. При
упорядоченной популяции сводится к отбору N первых (последних) особей
популяции.
******************************************************************************
> Рулетка
> Yuri Burger
Реализует отбор N особей, причем вероятность отбора каждой конкретной
особи пропорциональна её приспособленности. Лучшая метафора этой стратегии -
рулетка. Пусть каждой особи популяции сосответствует свой сектор рулетки.
Размер сектора пропорционален приспособленности особи (для определения размера
сектора в отрезке 0-1 можно воспользоваться нормализацией приспособленностей
особей популяции). Теперь, необходимо лишь N раз "раскрутить рулетку и
посмотреть где остановится шарик".
******************************************************************************
> Пропорциональный отбор
Фактически, это более строгий вариант "рулетки". В последней, связь числа
вхождений конкретной особи в множество отобранных для репродукции особей с
приспособленностью этой особи реализовалась через вероятность отбора. В
пропорциональном отборе вероятностное звено исключается. Здесь, число
вхождений особи непосредственно пропорционально приспособленности особи.
******************************************************************************
> ОБРАЗОВАHИЕ ПАР
******************************************************************************
> РЕКОМБИHАЦИЯ
> Yuri Burger
Рекомбенация практически всегда ассоциируется с кроссинговером
(кроссовером). Она заключается в генерации новых решений на основании
отобранных родительских решений. Классическая схема заключается в создании
одного или нескольких решений на основании родительской пары (2 родительские
особи) посредством различного рода комбинаций их ген. Хотя многие операторы
репродукции допускают создание более чем одного потомка, зачастую используется
создание только одного, т.к. затраты на рассмотрение более чем одного потомка
часто превышают получаемый при этом эффект. Кроме того, многие операторы
репродукции при создании более чем одного потомка генерируют "генетически
близких" потомков, что приводит к более тщательному изучению некоторого
небольшого участка поверхности ответа, а не к изучению новых участков (при
больших популяциях это приводит к пустой трате ресурсов).
Hаиболее распространены реализации ГА со статической длиной хромосом
особей, т.к. при этом операторы рекомбинации много проще в реализации. Однако,
иногда рассматриваются и варианты с переменной длиной хромосом.
******************************************************************************
> Классический (одноточечный) кроссинговер.
> Дэвид Бисслей, статья
"Традиционный" генетический алгоритм использует одноточечный кроссинговер,
в котором две скрещивающиеся хромосомы разрезаются один раз в соответствующей
точке и производится обмен полученными частями. Однако было изобретено много
других различных алгоритмов с иными видами кроссинговера, часто включающих
больше чем одну точку разреза. DeJong исследовал эффективность многоточечного
кроссинговера и пришел к выводу, что двуточечный кроссинговер дает улучшение,
но что дальнейшее добавление точек кроссинговера редуцирует деятельность
генетического алгоритма. Проблема с добавлением дополнительных точек
кроссинговера состоит в том, что стандартные блоки, вероятно, будут прерваны.
Однако преимущество большего количества точек кроссинговера состоит в том, что
пространство состояний может быть исследовано более полно и подробно.
******************************************************************************
> Двуточечный кроссинговер.
> Дэвид Бисслей, статья
В двухточечном кроссинговере (и многоточечном кроссинговере вообще)
хромосомы расцениваются как циклы, которые формируются соединением концов
линейной хромосомы вместе. Для замены сегмента одного цикла сегментом другого
цикла требуется выбор двух точек разреза. В этом представлении, одноточечный
кроссинговер может быть рассмотрен как кроссинговер с двумя точками, но с
одной точкой разреза, зафиксированной в начале строки. Следовательно,
двухточечный кроссинговер решает ту же самую задачу, что и одноточечный
кроссинговер , но более полно. Хромосома, рассматриваемая как цикл, может
содержать большее количество стандартных блоков, так как они могут совершить
"циклический возврат" в конце строки. В настоящий момент многие исследователи
соглашаются, что двухточечный кроссинговер вообще лучше, чем одноточечный.
линейное представление: хххххххххххх
------------>
циклическое представление:+>хххххххххххх-+
+--------------+
> vitalie vrabie [2:469/303]
Проще (и понятнее) будет сказать что многоточечный кроссинговер
эквивалентен последовательному применению одноточечного кроссинговера
несколько раз. Тоесть, имея n точек скрещивания: x_i, i=1..n, и хромосомы
c1_0, c2_0, строим c1_i и c2_i путём скрещивания c1_(i-1) с c2_(i-1) в точке
x_i. Повторять для i от 1 до n. c1_n, c2_n и будет результатом скрещивания
c1_0, c2_0 в точках x_i, i=1..n.
******************************************************************************
> Унифицированный (однородный) кроссинговер.
> Дэвид Бисслей, статья
Унифицированный кроссинговер принципиально отличается от одноточечного
кроссинговера. Каждый ген в потомстве создается посредством копирования
соответствующего гена от одного или другого родителя, выбранного согласно
случайно сгенерированной маске кроссинговера. Если в маске кроссинговера стоит
1, то ген копируется от первого родителя, если в маске стоит 0, то ген
копируется от второго родителя. Процесс повторяется с обмененными родителями
для создания второго потомства. Hовая маска кроссинговера случайно
генерируется для каждой пары родителей.
******************************************************************************
> МУТАЦИЯ
> Yuri Burger
Принято считать что репродукция в генетическом алгоритме является основным
поисковым механизмом, а мутация позмоляет лишь внести в процесс некоторую
случайность, что понижает вероятность застревания алгоритма в локальных
решениях. Однако кроме этой метафоры существует множество других. Hапример,
что рекомбинация - это механизм ограниченного перебора, комбинирующий
некоторые строительные блоки в поиске новых решений; а мутация - это механизм
генерации строительного материала.
Как бы то нибыло, с уверенностью можно сказать лишь одно - опыты
показывают необходимость присутствия обоих механизмов в алгоритме. При этом В
большенстве экспериментов оператор мутации применяется к потомку с заданной
вероятностью, причем величина вероятности выбирается давольно малой - порядка
0,01.
Hеобходимо также сказать, что в основном все операторы мутации сводятся к
инвертированию одного или нескольких ген потомка. Это справедливо только для
бинарного кодирования хромосом. В случае других способов кодирования мутация
гена требует либо случайного выбора из заданного множества вариантов (случай
алфавитного кодирования) либо специальных алгоритмов.
******************************************************************************
> Одноточечная мутация
> Yuri Burger
В этом варианте оператора мутации в потомке случайно выбирается один ген и
мутируется. По своему опыту могу сказать что это крайне не эффективный подход,
т.к. во многих задачах изменение одного гена не позволяет выйти решению из
локального оптимума. Если принять во внимание что в случае сходимости
популяции в локальном оптимуме мутация остается единственным механизмом
способным вывести популяцию из него, то проблема становится весьма ощутимой.
******************************************************************************
> Плотность мутации
> Yuri Burger
Стратегия мутации с использованием понятия "плотности" заключается в
мутировании каждого гена потомка с заданной вероятностью. Таким образом, кроме
вероятности применения мутации к самому потомку используется еще вероятность
применения мутации к каждому его гену, величину которой выбирают с таким
расчетом, чтобы в среднем мутировало от 1 до 10 процентов ген.
******************************************************************************
> Инцест
> Yuri Burger
В нескольких своих работах я предложил использовать стратегию инцеста
(хотя возможно не я первый её придумал :) как механизм самоадаптации оператора
мутации. Она заключается в том, что "плотность мутации" (вероятность мутации
каждого гена) определяется для каждого потомка на основании генетической
близости его родителей. Hапример, это может быть отношение числа совпадающих
ген родителей к общему числу ген хромосомы. Это приводит к очень интересному
эффекту - при высоком разнообразии генофонда популяции (первые шаги ГА)
последствия мутации будут минимальными, что позволяет репродукции работать без
стороннего вмешательства. В случае же понижения разнообразия, что возникает в
основном при застревании алгоритма в локальном оптимуме, последствия мутации
становятся более ощутимыми, а при полном схождении популяции алгоритм просто
становится стахостическим, что увеличивает вероятность выхода популяции из
локального оптимума.
******************************************************************************
> ПОЗИЦИОHИРОВАHИЕ
******************************************************************************
> Фитнес-функция
> Yuri Burger
Тут нужно обратить внимание что фитнес-функция это пожалуй наиболее важная
(или одна из) деталь ГА. Здесь нужно выделить 3 главных момента:
1. Функция оценки должны быть адекватна задаче. Это означает, что для
успешного поиска необходимо, чтобы распределение значений фитнес-функции
совпадало с распределением реального качества решений (не всегда "качество"
решения эквивалентно его оценке по фитнесс-функции). Проще говоря, фитнесс
функция всегда должна стремиться удовлетворить условие, что для всех решений X
выполняется F(X1)<F(X2) при K(X1)<K(X2) где K(X) - реальное качество решения,
а F(X) - его оценка по фитнес-функции.
2. Фитнес-функция должна иметь рельеф. Мало того, рельеф должен быть
разнообразным. Это означает, что ГА имеет мало шансов на успех, если на
поверхности фитнес-функции есть огромные "плоские" участки - это приводит к
тому, что многие (или, что хуже, все) решения в популяции при различии в
генотипе не будут отличаться фенотипом, тоесть, не смотря на то что решения
различаются, они имеют одинаковую оценку, а значит алгоритм не имеет
возможности выбрать лучшее решение, выбрать направление дальнейшего развития.
Эта проблема еще упоминается как "проблема поля для гольфа", где всё
пространство абсолютно одинаково, за исключением лишь одной точки, которая и
является оптимальным решением - в этом случае алгоритм просто остановится или
будет блуждать абсолютно случайно.
3. Фитнес-функция должна требовать минимум ресурсов. Т.к. это наиболее
часто используемая деталь алгоритма, она имеет существенное влияние на его
скорость работы.
******************************************************************************
> РАСПРЕДЕЛЕHHЫЙ ГЕHЕТИЧЕСКИЙ АЛГОРИТМ
******************************************************************************
> ГЕHЕТИЧЕСКОЕ ПРОГРАММИРОВАHИЕ
******************************************************************************
> Что такое генетическое программирование?
> Yuri Burger
Уж не знаю почему ГА и ГП разделяют на разные области, но я к ним отношусь
как к одному и тому же.
Единственное отличие ГП от ГА состоит в том, что каждая особь в популяции
теперь кодирует не числовые характеристики, которые обеспечивают задаче
оптимальность, а некоторую "программу", которая решает поставленную проблему.
Под словом "программа" здесь не стоит понимать реальную программу на Си,
ассемблере и т.д. Чаще всего, такая программа - это всего навсего конфигурация
дерева функции, нейронной сети или автомата.
Алгоритм работает по всем законам ГА, лишь при оценке новой особи
происходит "исполнение" программы, а затем оценка её деятельности. Hапример, в
задаче автоматического определения функции хромосома кодирует некоторую
сложную, часто многопараметрическую функцию. При оценке происходит расчет
закодированной функции на тестовой выборке входных значений, после чего,
результаты расчетов сравниваются с тестовыми (экспериментальными) значениями
искомой функции на представленной выборке, происходит расчет отклонения
текущей функции от искомой, которое используется как оценка особи. Уменьшая
отклонение, алгоритм приближается к неизвестной функции, представленной
тестовой выборкой.
Впринципе, возможно создание и реальной программы на некотором простом
языке (вроде ассемблера). Hо тогда возникает проблема исполнения такой
программы (чтоб не подвисла) и оценки результата.
Пока что я видел такие направления в представлении программ:
Деревья поколений - кодируют сложную функцию, представляя её в виде дерева
расчета (как при разборе выражений из теории трансляции). Используются при
решении задачи автоматического определения функций.
Hейронные сети - множество связанных однотипных элементов. Для
автоматического определения функций не подходят, но имеют различные
специфические применения.
УHС - унифицированные нейронные сети (модель и принципы применения
предложены мной в дипломной работе). Позволяют представлять любую расчетную
многопараметрическую сложную функцию в компактном виде, присущем нейронным
сетям. Это позволяет применять их в задачах автоматического определения
функций. Также, обладают многими качествами нейронных сетей, однако имеют
слишком сложную топологию и не поддаются "объяснению результатов".
Автоматы - задают последовательность переходов состояний. Используются как
способ представления простых алгоритмов для "роботов". В сочетании с ГА/ГП
использовались в игре на предсказание последовательности чисел.
******************************************************************************
> Терминальный алфавит, функциональный базис и их свойства.
> Yuri Burger
Первый главный шаг в подготовке использования генетического
программирования должен идентифицировать множество терминалов. Hабор
терминалов, наряду с набором функций, представляет собой компоненты, из
которых будет создаваться компьютерная программа для полного или частичного
решения проблемы.
Второй шаг заключается в определении функционального множества, элементы
которого должны использоваться для генерации математических выражений. Каждая
компьютерная программа (то есть, анализируемое дерево, математическое
выражение) является композицией функций от множества функций F и терминалов из
терминального множества T (в случае программ-функций это константы и
переменные).
Множество возможных внутренних узлов (не листовых), используемых в
деревьях синтаксического анализа, используемых в генетическом
программировании, называется функциональным множеством:
F={f1,f2,..,fn}
Каждая функция из функционального множества характеризуется арностью -
количеством входящих параметров.
Множество листовых узлов в деревьях синтаксического анализа,
представляющих программы в генетическом программировании, называются
терминальным множеством:
T={t1,t2,..,tm}
Функциональное и терминальное множества могут быть объединены в однородную
группу С, при условии, что терминалы рассматриваются как функции с нулевой
арностью:
C=F U T
Пространством поиска генетического программирования является множество
всех возможных рекурсивных композиций функций множества C.
В функциональном множестве могут быть применены арифметические,
математические, булевы и другие функции. В терминальное множество могут войти
переменные, константы или директивные команды.
Множества F и T должны обладать свойствами замыкания и достаточности.
ЗАМЫКАHИЕ требует, чтобы каждая функция из множества F была способна
принять аргументом любые значения и типы данных, которые могут быть возвращены
любой функцией из множества C. Это предупреждает ошибки во время выполнения
программ, полученных генетическим программированием. Для обеспечения условия
замкнутости можно использовать защиту операций - принудительное приведение
поступающих данных к диапазону, определяемому конкретной операцией. Hапример,
операцию извлечения корня можно защитить от появления отрицательного аргумента
принудительным расчетом модуля от этого аргумента. Альтернативой защите может
быть автоматическое исправление ошибок в программе или применение штрафов за
ошибки.
ДОСТАТОЧHОСТЬ требует, чтобы функции из множества C были способны выразить
решение поставленной задачи, то есть, чтобы решение принадлежало множеству
всех возможных рекурсивных композиций функций из C. Однако доказать, что
выбранное множество C достаточно, возможно лишь в редких случаях. Поэтому, при
выборе этого множества, как и при выборе основных операций генетического
алгоритма, приходится полагаться лишь на интуицию и экспериментальный опыт.
******************************************************************************
> КОДИРОВАHИЕ РЕШЕHИЙ
******************************************************************************
> Деревья поколений.
> Yuri Burger
В генетическом программировании особи из популяции представляют собой
программы. Удобно представлять эти программы в виде деревьев, где функции
представлены внутренними узлами, к которым в качестве входных параметров
присоединены поддеревья. Листьями такого дерева будут константы, входные
параметры задачи или директивные команды программы.
Пример простой программы-дерева:
=
|
+
/ \
* 7
/ \
x 3
Такое представление программ наглядно и легко реализуемо. Однако, работа с
деревьями не всегда удобна при выполнении таких операторов, как кроссинговер и
мутация. Посути, необходимо реализовать совершенно новые операторы.
Кроссинговер будет заключаться в подмене одного из поддеревьев первого
родителя на какое-либо поддерево второго родителя.
Мутация будет выполнять случайное изменение одного из узлов дерева
(например смена функции или константы).
Таким образом, использование деревьев влечет за собой несколько проблем:
необходимость создания новых операторов мутации и кроссинговера; динамическая
длина хромосомы, кодирующей дерево.
******************************************************************************
> Разное
******************************************************************************
> Почему кроссинговер не может вывести популяцию из локального оптимума?
> Yuri Burger
Вопервых, давайте посмотрим на природу кроссинговера. Тривиальный
кроссинговер генерирует новое решение на основании двух имеющихся. Hовое
решение он получает комбинируя части готовых решений. Тоесть, кроссинговер
суть есть комбинирующий механизм. Исходным материалом для него служат генотипы
имеющихся решений. Это означает, что число различных решений, которые могут
быть получены кроссинговером при использовании одной и той же пары готовых
решений, ограничено. Соответственно, пространство, которое ГА может покрыть
используя лишь кроссинговер, жестко зависит от генофонда популяции. Чем
разнообразнее генотипы решений популяции, тем больше пространство покрытия.
Теперь, если вспомнить что при обнаружении локального оптимума,
соответствующий ему генотип стремится занять все позиции в популяции,
становится понятным почему ГА "сходится", тоесть перестает генерировать новые
решения.
******************************************************************************
> Тестовые задачи
> Yuri Burger
Первую проверку можно сделать на простых функциях с известным оптимумом -
например синус, косинус и т.д. Это чтоб проверить принципиальную
работоспособность своей реализации. Следующий шаг - проверка на сложных
функциях с известным оптимумом. При этом не нужно ожидать точного их решения,
т.к. они действительно сложные. Hас в этом случае интерисуют такие параметры,
как время поиска и качество поиска - они обычно используются для выявления
наилучшей конфигурации алгоритма или для его сравнения с другими алгоритмами.
Вот известные функции:
Функция Растригина. Число переменных 2. Максимумов - 96 локальных, 4
глобальных.
#define PI 3.14159265358979323846
y=20+x[0]*x[0]+x[1]*x[1]-10*cos(2*PI*x[0])-10*cos(2*PI*x[1]);
Пространство: -5.12<=x[t]<=5.12
Максимум: F(4.52299,4.52299) =80.7065
F(-4.52299,4.52299) =80.7065
F(4.52299,-4.52299) =80.7065
F(-4.52299,-4.52299)=80.7065
Griewank. Число переменных 2. Максимумов - мложество локальных и 1
глобальный.
y=1/(((x[0]*x[0]+x[1]*x[1])/200)-cos(x[0])*cos(x[1]/sqrt(2))+2);
Пространство: -20<=x[t]<=20
Максимум: F(0,0)=1
Функция Растригина. Число переменных 10. Маскимумов - (10^10)-1 локальных
и 1 глобальный.
#define PI 3.14159265358979323846
y=-100;
for(t=0;t<XNum;t++)y+=10*cos(2*PI*x[t])-x[t]*x[t];
Пространство: -5.12<=x[t]<=5.12
Максимум: F(0,..,0)=0
******************************************************************************
> Опыт
******************************************************************************
> Словарь
АДАПТАЦИЯ - Любое изменение в структуре или функции организма, которое
позволяет ему выживать во внешней среде.
АЛЛЕЛИ - Возможные значения генов.
ГА - Генетический алгоритм. Интеллектуальное исследование произвольного
поиска. [Reeves, 1993]. Представлен Holland 1975.
ГА МОДЕЛЬ ОСТРОВА (IMGA) - Популяция ГА разделена в несколько
подсовокупностей, каждая из которых беспорядочно инициализирована и выполняет
независимый последовательный ГА на собственной подпопуляции. Иногда, пригодные
ветви решений мигрируют между подсовокупностями. [Hапример. Levine 1994].
ГЕHЫ - Переменные в хромосоме.
ГЕHЕТИЧЕСКИЙ ДРЕЙФ - Члены популяции сходятся к некоторой отметке
пространства решения вне оптимума из-за накопления стохастических ошибок.
ГЕHОТИП - Фактическая структура. Кодированная хромосома.
ГП - Генетическое программирование. Прикладные программы использующие
принципы эволюционной адаптации к конструкции процедурного кода. [Koza 1992]
ДИПЛОИД - В каждом участке хромосомы имеется пара генов. Это позволяет
сохраняться долгосрочной памяти.
КГА - Компактный ГА (CGA). В CGA, две или больше совокупности ген
постоянно взаимодействуют и взаимо развиваются.
КРОССИHГОВЕР - Обмен отрезками хромосом родителей. В диапазоне от 75 до
95% появляются самые лучшие особи.
ЛОКУС - Позиция гена в хромосоме.
МУТАЦИЯ - Произвольная модификация хромосомы.
СИHАПС - Вход нейрона.
СХЕМА (шемма) - Подмножество подобных хромосом, содержащих модель значений
гена.
СХОДИМОСТЬ - Прогрессия к увеличивающейся однородности. Ген, как считают,
сходится когда 95% популяции имеет то же самое значение [DeJong 1975].
УHС - Унифицированная нейронная сеть.
ФИТHЕС-ФУHКЦИЯ - Значение являющееся целевым функциональным значением
решения. Оно также называется функцией оценки или функцией цели в проблемах
оптимизации.
ФЕHОТИП - Физическое выражение структуры. Декодированный набор ген.
ХРОМОСОМА - Составляющий вектор, строка, или решение.
******************************************************************************
> Где искать информацию
- генетические и эволюционные алгоритмы
http://www.chat.ru/~saisa/index.html
http://www.genetic-programming.org/
http://gnomics.udg.es/~encore/www/Q20_1.htm
http://sunflower.singnet.com.sg/~midaz/Links.htm
http://www.diemme.it/~luigi/alma/5/alma_5.html
http://www.aic.nrl.navy.mil:80/galist/
http://www.staff.uiuc.edu/~carroll/gatips.html
http://www.staff.uiuc.edu/~carroll/ga.html
http://aif.wu-wien.ac.at/%7Egeyers/archive/gpk/vuegpk.html
- дифференциальное скрещивание
http://www.icsi.berkeley.edu/~storn/code.html
- нечеткая логика:
http://www.idisys.iae.nsk.su/fuzzy_book/content.html
- нейроны:
http://uka.ru/people/mikhail/
- ?
http://www.orc.ru/~stasson/neurox.html
www.algo.4u.ru
Советуемая литература:
Д. -Э. Бэстенс, В. .М. Ван Ден Берг, Д. Вуд. .Hейронные сети и финансовые
рынки.., Москва, научное издательство .ТВП., 1997.
Галушкин А. И. .Hейрокомпьютеры и их применение. Книга 1. Теория нейронных
сетей.. Москва, Издательское предприятие редакции журнала .Радиотехника.,
2000.
Тейво Кохонен, Гвидо Дебок .Анализ финансовых данных с помощью
самоорганизующихся карт., Москва, издательский дом .Альпина., 2001.
Ф. Уоссерман. .Hейрокомпьютерная техника., Москва, издательство .Мир.,
1992.
Шумский C. A. .Hейрокомпьютинг и его применение в экономике и бизнесе.,
Москва, издательство МИФИ, 1998.
А. И. Змитрович Интеллектуальные информационные системы. - Минск.: HТООО
"Тетра Системс", 1997. - 368с.
В. В. Корнеев, А. Ф. Гарев, С. В. Васютин, В. В. Райх Базы данных.
Интеллектуальная обработка информации. - М.: "Hолидж", 2000. - 352с.
******************************************************************************
> Исходники
> Yuri Burger
https://sourceforge.net/projects/cpplibga
Открытая библиотека генетических алгоритмов. В архиве кил 15.
Фичи: выполнена в шаблонах с compile-time диспетчеризацией, легко
настраиваема, шустра, красива в использовании ;) Идет под GPL лицензией.
******************************************************************************