Секция 1 из 3 - Предыдущая - Следующая
Все секции
- 1
- 2
- 3
From: Yuri Burger <Yuri.Burger@p3.f85.n468.z2.fidonet.org>
Date: Sun, 18 Nov 2001 09:55:44 +0300
Subj: MildFAQ
+====================+
+-Мягкие вычисления-+
+=====18-11-2001=====+
Составитель: Yuri Burger [2:468/85.3]
Данный документ может свободно распространяться и использоваться при
выполнении следующих условий:
- использование документа не носит коммерческий характер
- при использовании документа целиком сохранены все копирайты
- при использовании отдельных частей документа указаны ссылки на автора
используемой части или на данный документ вцелом
Любые притензии по поводу содержимого рассматриваются составителем, но не
обязательно удовлетворяются ;)
******************************************************************************
Что такое мягкие вычисления?
Постановка задачи оптимизации, теорема Вейерштрасса, понятие минимума.
ГЕНЕТИЧЕСКИЙ АЛГОРИТМ
- Что такое генетический алгоритм?
- Кто придумал генетический алгоритм?
- Преимущества генетических алгоритмов?
- Недостатки генетических алгоритмов?
- Что такое простейший генетический алгоритм, схема, теорема Холланда?
- А на исходник простого ГА посмотреть можно?
- В приведенном сырце ПГА не ясна роль "не элитных" особей.
- Классический (одноточечный) кроссинговер.
- Двуточечный кроссинговер.
- Унифицированный (однородный) кроссинговер.
- Дифференциальное скрещивание.
- Исходники некоторых кроссинговеров.
- Что такое инверсия и переупорядочение?
- Что такое эпистаз?
- Что такое ложный оптимум?
- Что такое инбридинг, оутбридинг, селективный выбор, панмиксия?
- Динамическая самоорганизация параметров ГА.
- Метод миграции и искусственной селекции.
- Метод прерывистого равновесия.
- Почему у меня популяция пpи малых размерах вообще не сходится?
- Разное.
- ГА не рекомендуется, если нужно найти точный глобальный экстремум. Почему?
ГЕНЕТИЧЕСКОЕ ПРОГРАММИРОВАНИЕ
- Что такое генетическое программирование?
- Деревья поколений.
- Терминальный алфавит, функциональный базис и их свойства.
НЕЙРОННЫЕ СЕТИ
- Математическая модель нейрона.
- Применение генетического подхода в обучении нейронной сети.
НЕЧЕТКИЕ МНОЖЕСТВА
- Что такое нечеткое множество, нечеткая и лингвистическая переменная?
- Базовые операции над нечеткими множествами.
- Библиотека операций над нечеткими множествами.
Словарь
Где искать информацию
******************************************************************************
>Что такое мягкие вычисления?
>(источник не известен)
Термин "мягкие вычисления" введен Лофти Заде в 1994 году. Это понятие
объединяет такие области как: нечеткая логика, нейронные сети, вероятностные
рассуждения, сети доверия и эволюционные алгоритмы; которые дополняют друг
друга и используются в различных комбинациях или самостоятельно для создания
гибридных интеллектуальных систем. Поэтому создание систем работающих с
неопределенностью, надо понимать как составную часть "мягких" вычислений.
По существу в 1970 году Л.Заде был создан новый метод вычислительной
математики, который был поддержан аппаратными средствами (нечеткими
процессорами) который в ряде проблемных областей стал более эффективным, чем
классические методы. Первоначально эти области входили в проблематику
искусственного интеллекта. Постепенно круг этих областей существенно
расширился и сформировалось направление "вычислительного интеллекта". В это
направление в настоящее время входят:
- нечеткая логика и теория множеств;
- нечеткие экспертные системы;
- системы приближенных вычислений;
- теория хаоса;
- фрактальный анализ;
- нелинейные динамические системы;
- гибридные системы (нейронечеткие или нейрологические, генетиконейронные,
нечеткогенетические или логикогенетические системы);
- системы, управляемые данными (нейронные сети, эволюционное вычисление).
******************************************************************************
>Постановка задачи оптимизации, теорема Вейерштрасса, понятие минимума.
>Yuri Burger [2:468/85.3]
Пусть задана функция q(x), определенная во всех значениях x
принадлежащих X. В общем случае x может быть вектором значений
многопараметрической функции q(x).
Тогда, в общей задаче оптимизации требуется найти вектор x=(x1,x2,
....,xn) из допустимой области X, который обращает в минимум целевую функцию
q(x). Если необходимо найти максимум функции, то в качестве целевой берут
обратную функцию -q(x).
Теорема Вейерштрасса. Непрерывная функция, определенная на непустом
замкнутом ограниченном множестве, достигает своего минимума (максимума) по
крайней мере в одной из точек этого множества.
В общем случае глобальный минимум в точке 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)
******************************************************************************
> ГЕНЕТИЧЕСКИЙ АЛГОРИТМ
******************************************************************************
>Что такое генетический алгоритм?
>(источник не известен)
Генетические алгоритмы (ГА) представляют собой методы оптимизации,
основанные на концепциях естественного отбора и генетики. В этом подходе,
переменные представлены как гены на хромосоме. ГА показывают группу вариантов
решения (популяции) на поверхности ответа. Через естественный отбор и
генетические операторы, мутацию и рекомбинацию, отбираются хромосомы с лучшей
пригодностью. Естественный отбор гарантирует, что хромосомы с лучшей
пригодностью будут размножаться в будущих популяциях. Используя оператор
рекомбинации, ГА объединяет гены родительских хромосом, чтобы сформировать
новые хромосомы (детей), которые имеют высокую вероятность наличия лучшей
пригодности, чем у их родителей. Мутация позволяет исследовать новые области
поверхности.
>Yuri Burger [2:468/85.3]
Идею ГА подсказала сама природа и работы Дарвина. Делается предположение,
что если взять 2 вполне хороших решения задачи и каким-либо образом получить
из них новое решение, то будет высокая вероятность того, что новое решение
получится хорошим или даже более лучшим.
Для реализации этого используют моделирование эволюции (естественного
отбора) или если проще - борьбы за выживание. В природе, по упрощенной схеме,
каждое животное стремится выжить, что-бы оставить после себя как можно больше
потомства. Выжить в таких условиях могут лишь сильнейшие.
Тогда нам остается организовать некоторую среду - популяцию, населить её
решениями - особями, и устроить им борьбу. Для этого нужно определить функцию,
по которой будет определяться сила особи - качество предложенного ею решения.
Основываясь на этом параметре можно определить каждой особи количество
оставляемых ею потомков, или вероятность того, что эта особь оставит потомка.
Причем, не исключен вариант, когда особь со слишком низким значением этого
параметра умрёт.
Допустим нам нужно оптимизировать некоторую функцию F(X1,X2,..,Xn). Пусть
мы ищем её глобальный максимум. Тогда, для реализации ГА нам нужно придумать,
как мы будем хранить решения. По сути, нам нужно поместить все X1-Xn в
некоторый вектор, который будет играть роль хромосомы. Один из наиболее
распространенных способов - кодировать значения переменных в битовом векторе.
Например, выделим каждому иксу по 8 бит. Тогда наш вектор будет длины L=8*n.
Для простоты будем считать, что биты лежат в массиве X[0..L-1].
Пусть каждая особь состоит из массива X и значения функции F на
переменных, извлеченных из этого массива.
Тогда ГА будет состоять из следующих шагов:
1. Генерация начальной популяции - заполнение популяции особями, в которых
элементы массива X (биты) заполнены случайным образом.
2. Выбор родительской пары - я всегда использую элитный отбор, тоесть
берем K особей с максимальными значениями функции F и составляю из них все
возможные пары (K*(K-1)/2).
3. Кроссинговер - берем случайную точку t на массиве X (0..L-1). Теперь,
все элементы массива с индексами 0-t новой особи (потомка) заполняем
элементами с теми-же индексами, но из массива X первой родительской особи.
Остальные элементы заполняются из массива второй родительской особи. Для
второго потомка делается наоборот - элементы 0-t берут от второго потомка, а
остальные - от первого.
4. Новые особи с некоторой вероятностью мутируют - инвертируется случайный
бит массива X этой особи. Вероятность мутации обычно полагают порядка 1%.
5. Полученные особи-потомки добавляются в популяцию после переоценки.
Обычно новую особь добавляют взамен самой плохой старой особи, при условии что
значение функции на новой особи выше значения функции на старой-плохой особи.
6. Если самое лучшее решение в популяции нас не удовлетворяет, то переход
на шаг 2. Хотя, чаще всего этого условия нет, а итерации ГА выполняются
бесконечно.
Вообще, если строго придерживаться правилам, то ГА должен содержать еще
такие шаги как отбор особей для размножения и генерация пар из отобранных
особей. При этом каждая особь может быть задействована в одной и более паре, в
зависимости от используемого алгоритма.
Однако я предпочитаю эти два шага совмещать, используя построение пар "все
на все" в элитной выборке. Имхо, так проще.
******************************************************************************
>Кто придумал генетический алгоритм?
>(источник не известен)
В 1966 г. Л.Дж.Фогель, А.Дж. Оуэнс, М.Дж.Волш предложили и исследовали
эволюцию простых автоматов, предсказывающих символы в цифровых
последовательностях. В 1975г. Д.Х.Холланд предложил схему генетического
алгоритма. Эти работы легли в основу главных направлений разработки
эволюционных алгоритмов.
Простой генетический алгоритм был впервые описан Гольдбергом на основе
работ Холланда.
******************************************************************************
>Преимущества генетических алгоритмов?
>(источник не известен)
- Они не требуют никакой информации о поверхности ответа;
- Разрывы, существующие на поверхности ответа имеют незначительный эффект
на полную эффективность оптимизации;
- Они стойки к попаданию в локальные оптимумы;
- Они хороше работают при решении крупномасштабных проблем оптимизации;
- Могут быть использованы для широкого класса задач;
- Просты и прозрачны в реализации;
- Могут быть использованы в задачах с изменяющейся средой.
******************************************************************************
>Недостатки генетических алгоритмов?
>(источник не известен)
Не желательно и проблематично использовать ГА:
- В случае когда необходимо найти точный глобальный оптимум;
- Время исполнения функции оценки велико;
- Необходимо найти все решения задачи, а не одно из них;
- Конфигурация является не простой (кодирование решения).
>Alexander Pavlov [2:5030/399.11]
Необходимость поиска всех решений не является помехой. Исаев (статьи на
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 операторов: репродукция, кроссинговер, мутация.
Репродукция - процесс, в котором хромосомы копируются согласно их целевой
функции (ЦФ). Копирование хромосом с "лучшим" значением ЦФ имеет большую
вероятность для их попадания в следующую генерацию. Оператор репродукции (ОР),
является искусственной версией натуральной селекции, "выживания сильнейших" по
Дарвину.
После выполнения ОР оператор кроссинговера (ОК) может выполниться в
несколько шагов На первом шаге выбираются члены нового репродуцированного
множества хромосом. Далее каждая пара хромосом (стрингов) пересекается по
следующему правилу: целая позиция 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)
Некоторые исследователи считают, что репродукция может привести к
экспоненциальному уменьшению или увеличению схем, особенно если выполнять
генерации параллельно.
Отметим, что если мы только копируем старые структуры без обмена,
поисковое пространство не увеличивается и процесс затухает. Потому и
используется ОК. Он создает новые структуры и увеличивает или уменьшает число
схем в популяции.
Очевидно, что нижняя граница вероятности выживания схемы после применения
ОК может быть вычислена для любой схемы. Так как схема выживает, когда точка
ОК попадает вне "определенной длины", то вероятность выживания для простого ОК
запишется
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 [2:468/85.3]
Вот. Собирал на Watcom C. Расчитано на 2 переменные. Кроссовер -
классический, отбор - элитарный.
// (c) BSM Group, Burger Y.A. (Kruger)
// x = 0..XMaxValue
// y = 0..YMaxValue
#include <stdio.h>
#include <stdlib.h>
#include "math.h"
#define PI 3.14159265358979323846
#define MaxGenNum 256
#define MaxPopulationLeng 65536
long XMaxValue=1024;
long YMaxValue=1024;
double LastX,LastY,LastZ;
char BestIsIn=0;
double BestX,BestY,BestZ;
double NumOfHromosoms;
long PBestLeng=16; // длина лучшей выборки
long PMaxLeng=128; // максимальная длина популяции
long PLeng=0; // текущая длина популяции
long HLeng=32; // количество ген в хромосоме
double MutateHPercent=8;// процент мутаций в популяции
double MutateGPercent=8;// процент мутаций в хромосоме
typedef struct
{
char G[MaxGenNum]; // набор ген
double V; // значение оценки
}HROMOSOM;
HROMOSOM *P[MaxPopulationLeng]; // популяция
HROMOSOM *B[MaxPopulationLeng]; // для селекции
void PrintInfo(void)
{
printf("X=%g ",BestX);
printf("Y=%g ",BestY);
printf("Z(X,Y)=%g\n",BestZ);
}
double CalcZ(double X,double Y)
{
double z;
double sx=X*PI/XMaxValue;
double sy=Y*PI/YMaxValue;
z=fabs(127+200*(cos(sx*sx+sy*sy)*cos(sy*sx))*sqrt(sin(sx)*sin(sy)));
return z;
}
void SortPopulation(long l,long r)
{
long i=l,j=r;
double x=P[(r+l)/2]->V;
HROMOSOM *y;
do
{
while (P[i]->V > x) i++;
while (x > P[j]->V) j--;
if (i<=j)
{
y=P[i];P[i]=P[j];P[j]=y;
i++;j--;
};
}while(i<j);
if (l<j) SortPopulation(l,j);
if (i<r) SortPopulation(i,r);
}
double GetX(HROMOSOM *h)
{
long t;
double d=0;
for(t=0;t<HLeng;t++)
{
d+=(double)h->G[t]*pow(2,t-0);
}
d=XMaxValue*d/(pow(2,HLeng)-1);
return d;
}
double GetY(HROMOSOM *h)
{
long t;
double d=0;
for(t=HLeng;t<HLeng*2;t++)
{
d+=(double)h->G[t]*pow(2,t-HLeng);
}
d=XMaxValue*d/(pow(2,HLeng)-1);
return d;
}
double MiFunction(HROMOSOM *h)
{
double X,Y,Z;
X=GetX(h);
Y=GetY(h);
Z=CalcZ(X,Y);
LastX=X;
LastY=Y;
LastZ=Z;
return Z;
}
HROMOSOM *NewHromosom(void)
{
HROMOSOM *t;
t=(HROMOSOM *)calloc(1,sizeof(HROMOSOM));
NumOfHromosoms++;
return t;
}
void KillHromosom(HROMOSOM *h)
{
free(h);
}
int AddHromosom(HROMOSOM *h)
{
long mh=0;
long t;
if(PLeng<PMaxLeng)
{
P[PLeng]=h;
PLeng++;
return 0;
}
else
{
for(t=0;t<PLeng;t++)
if(P[t]->V < P[mh]->V)mh=t;
if(h->V > P[mh]->V)// >= ?
{
KillHromosom(P[mh]);
P[mh]=h;
}
else return -1;
return 0;
}
}
void RandomFillHromosom(HROMOSOM *h)
{
long t;
for(t=0;t<HLeng*2;t++)
{
if(rand()<RAND_MAX/2) h->G[t]=0;
else h->G[t]=1;
}
h->V=MiFunction(h);
}
void GenerateHromosom(HROMOSOM *h1,HROMOSOM *h2,HROMOSOM *s1,HROMOSOM *s2)
{
long t;
long l=rand()*HLeng*2/RAND_MAX;
for(t=0;t<l;t++)
{
h1->G[t]=s1->G[t];
h2->G[t]=s2->G[t];
}
for(t=l;t<HLeng*2;t++)
{
h1->G[t]=s2->G[t];
h2->G[t]=s1->G[t];
}
h1->V=MiFunction(h1);
h2->V=MiFunction(h2);
}
void MutateHromosom(HROMOSOM *h)
{
double l1,l2;
long g;
l1=MutateHPercent*RAND_MAX/100;
l2=MutateGPercent*RAND_MAX/100;
if(rand()<l1)
{
for(g=0;g<HLeng*2;g++)
{
if(rand()<l2)
{
h->G[g]^=1;
}
}
}
h->V=MiFunction(h);
}
void GA()
{
HROMOSOM *h,*h1,*h2;
long x,y,z,mx,my;
long c=0;
long t;
for(t=0;t<PMaxLeng;t++)
{
h=NewHromosom();
RandomFillHromosom(h);
if(AddHromosom(h)==-1)KillHromosom(h);
}
if(PLeng>0)SortPopulation(0,PLeng-1);
Loop:
if(kbhit()){getch();goto Exit;}
for(t=0;t<PBestLeng;t++)B[t]=P[t];
for(my=0;my<PBestLeng;my++)
{
for(mx=my+1;mx<PBestLeng;mx++)
{
c++;
h1=NewHromosom();
h2=NewHromosom();
GenerateHromosom(h1,h2,B[my],B[mx]);
MutateHromosom(h1);
if(AddHromosom(h1)==-1)KillHromosom(h1);
MutateHromosom(h2);
if(AddHromosom(h2)==-1)KillHromosom(h2);
}
}
if(PLeng>0)SortPopulation(0,PLeng-1);
if(BestIsIn==0||P[0]->V>BestZ)
{
BestIsIn=1;
BestX=GetX(P[0]);
BestY=GetY(P[0]);
BestZ=P[0]->V;
PrintInfo();
}
goto Loop;
Exit:
for(x=0;x<PLeng;x++)KillHromosom(P[x]);
return;
}
int main(void)
{
GA();
return 0;
}
******************************************************************************
>В приведенном сырце ПГА не ясна роль "не элитных" особей.
>Yuri Burger [2:468/85.3]
Честно говоря, этот вопрос меня самого поставил в тупик. Прикинул так и
этак - выходит что не нужны они.. Однако нельзя торопиться с выводами.
Вопервых, многое зависит от процедуры добавления особей в популяцию. В
зависимости от неё, неэлитные особи могут терять и преобретать значимость.
И есть еще одно применение им. Если функция оценки особей (фитнес) будет
давольно медленной, то эти особи можно использовать в качестве кэша. Всилу
особенностей работы ГА, будет весьма высокая вероятность появления решений из
окресности текущего оптимума, а значит можно ожидать повторения особей.
******************************************************************************
>Классический (одноточечный) кроссинговер.
>Дэвид Бисслей, статья
"Традиционный" генетический алгоритм использует одноточечный кроссинговер,
в котором две скрещивающиеся хромосомы разрезаются один раз в соответствующей
точке и производится обмен полученными частями. Однако было изобретено много
других различных алгоритмов с иными видами кроссинговера, часто включающих
больше чем одну точку разреза. 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, то ген
копируется от второго родителя. Процесс повторяется с обмененными родителями
для создания второго потомства. Новая маска кроссинговера случайно
генерируется для каждой пары родителей.
******************************************************************************
>Дифференциальное скрещивание.
>Ilya S. Potrepalov [ispotrepalov@asu.tnk.ru]
Существуют и другие методы скрещивания, а не только crossover. Например,
для поиска минимума/максимума функции многих вещественных переменных наиболее
удачным является "дифференциальное скрещивание". А именно, пусть a и b -- это
два индивидума в популяции, т.е. вещественные вектора от которых наша функция
зависит. Тогда потомок c вычисляется по формуле с=a+k*(a-b), где k -- это
некоторый вещественный коэффициент (который может зависить от ||a-b||
--растояния между векторами).
В этой модели мутация -- это добавление к индивидуму случайного вектора
малой длины. Если исходная функия непрерывна, то эта модель работает хорошо. А
если она еще и гладкая, то -- превосходно.
******************************************************************************
>Исходники некоторых кроссинговеров.
>Yuri Burger [2:468/85.3]
Вот вырезки из моих прог. Вполне можно прикрутить куда нужно :)
Пояснения:
EBitSize - количество бит на одну переменную
Сырци вырезаны из задачи с 4-мя переменными.
Процедуры GetBit, SetBit и InvertBit - соответственно читают,
устанавливают и инвертируют указанный бит в векторе (хромосоме). Если Вы
храните каждый бит в byte и хромосома соответственно представленна массивом
этих byte, процедурки можна сразу сменить на обращение к массиву :)
v1, v2 - указатели на родительские особи.
c1, c2 - потомки.
// классический кроссинговер
q=rand()*(EBitSize*4-1)/RAND_MAX;
for(t=0;t<q;t++)
{
SetBit(c1->r,t,GetBit(v1->r,t));
SetBit(c2->r,t,GetBit(v2->r,t));
}
for(t=q;t<EBitSize*4;t++)
{
SetBit(c1->r,t,GetBit(v2->r,t));
Секция 1 из 3 - Предыдущая - Следующая
© faqs.org.ru
