MildFAQ: 4
- From
- Yuri Burger ()
- To
- All
- Date
- 2002-12-06T12:42:49Z
- Area
- RU.ALGORITHMS
From: "Yuri Burger" <kruger@selena.net.ua>
Hello, All!
****************************************************************************
**
>Что такое инбридинг, оутбридинг, селективный выбор, панмиксия?
>(источник не известен)
Существует несколько подходов к выбору родительской пары.
Наиболее
простой из них - панмиксия. Этот подход предполагает случайный
выбор
родительской пары, когда обе особи, которые составят родительскую
пару,
случайным образом выбираются из всей популяции. В этом случае любая
особь
может стать членом нескольких пар. Несмотря на простоту, такой
подход
универсален для решения различных классов задач. Однако он достаточно
критичен
к численности популяции, поскольку эффективность алгоритма, реализующего
такой
подход, снижается с ростом численности популяции.
Селективный способ выбора особей в родительскую пару состоит в том,
что
"родителями" могут стать только те особи, значение приспособленности
которых
не меньше среднего значения приспособленности по популяции, при
равной
вероятности таких кандидатов составить брачную пару.
Такой подход обеспечивает более быструю сходимость алгоритма.
Однако
из-за быстрой сходимости селективный выбор родительской пары не
подходит
тогда, когда ставиться задача определения нескольких экстремумов,
поскольку
для таких задач алгоритм, как правило, быстро сходится к одному из
решений.
Кроме того, для некоторого класса задач со сложным
ландшафтом
приспособленности быстрая сходимость может превратиться в
преждевременную
сходимость к квазиоптимальному решению. Этот недостаток может быть
отчасти
компенсирован использованием подходящего механизма отбора, который
бы
"тормозил" слишком быструю сходимость алгоритма.
Инбридинг представляет собой такой метод, когда первый член
пары
выбирается случайно, а вторым с большей вероятностью будет максимально
близкая
к нему особь.
Пример определения родства хромосом при выборе родительской пары
для
хромосомы 1010001:
Хромосомы популяции Количество отличающихся локусов
1000000 2
1010101 1
0011100 4
0000001 2
0110011 3
0100011 4
1111111 4
0000000 3
При аутбридинге также используют понятие схожести особей. Однако
теперь
брачные пары формируют из максимально далеких особей.
Последние два способа поразному влияют на поведение
генетического
алгоритма. Так инбридинг можно охарактеризовать свойством концентрации
поиска
в локальных узлах, что фактически приводит к разбиению популяции на
отдельные
локальные группы вокруг подозрительных на экстремум участков
ландшафта.
Аутбридинг же направлен на предупреждение сходимости алгоритма к уже
найденным
решениям, заставляя алгоритм просматривать новые, неисследованные области.
>Alexander Pavlov [2:5030/399.11]
По поводу источника. Начало, по кpайней меpе, с www.algo.4u.ru,
статья
Д.И. Батищева, С.А. Исаева "Оптимизация многоэкстpемальных функций с
помощью
генетических алгоpитмов" (опубликовано в сбоpнике статей, издаваемом
ВГТУ,
осень 1997).
****************************************************************************
**
>Динамическая самоорганизация параметров ГА.
>Yuri Burger [2:468/85.3]
Зачастую, выбор параметров генетического алгоритма и
конкретных
генетических операторов производится на интуитивном уровне, так как пока
не
существует объективных доказательств преимущества тех или иных настроек
и
операторов. Однако, не нужно забывать, что сама суть ГА заключается в
динамике
и "мягкости" алгоритма и производимых вычислений. Тогда почему бы не
позволить
алгоритму самому настраиваться во время решения задачи и адаптироваться к
ней?
Наиболее просто организовать адаптацию применяемых операторов. Для
этого
встроем в алгоритм несколько (чем больше тем лучше) различных
операторов
выборки (элитная, случайная, рулеточная,..), кроссинговера
(одноточечный,
двуточечный, унифицированный,..) и мутации (случайная
одноэлементная,
абсолютная,..). Установим для каждого оператора равные вероятности
применения.
Далее, на каждом цикле алгоритма будем выберать один из операторов
каждой
группы (выбор, кроссинговер, мутация) соответственно
вероятносному
распределению. Причем, в полученной при помощи этих операторов особи
отметим,
какими именно операторами она была получена. Тогда, если новое
распределение
вероятностей мы вычислим исходя из информации, содержащейся в
популяции
(вероятность применения оператора пропорциональна числу особей в
популяции,
полученных при помощи этого оператора), то генетический алгоритм
получит
механизм динамической самоадаптации.
Такой подход дает еще одно преимущество - теперь не нужно беспокоиться
о
применяемом генераторе случайных чисел (линейный, экспоненциальный и
т.д.),
так как алгоритм динамически изменяет характер распределения.
****************************************************************************
**
>Метод миграции и искусственной селекции.
>В.В Курейчик, статья
В отличие от обыкновенных ГА выполняется макроэволюция, т.е. создается
не
одна популяция, а некоторое множество популяций. Генетический поиск
здесь
осуществляется путем объединения родителей из различных популяций.
****************************************************************************
**
>Метод прерывистого равновесия.
>В.В Курейчик, статья
Метод основан на палеонтологической теории прерывистого
равновесия,
которая описывает быструю эволюцию за счет вулканических и других
изменений
земной коры. Для применения данного метода в технических задачах
предлагается
после каждой генерации случайным образом перемешивать индивидуальности
в
популяции, а затем формировать новые текущие генерации. Здесь
можно
предложить, как аналог из живой природы, бессознательный отбор
родительских
пар и синтетический отбор лучших родительских пар. Далее случайным
образом
смешать результаты обоих отборов и не оставлять размер популяции постоянным,
а
управлять им в зависимости от наличия лучших индивидуальностей.
Такая
модификация метода прерывистого равновесия может позволить
сократить
неперспективные популяции и расширить популяции, в которых находятся
лучшие
индивидуальности.
Метод прерывистого равновесия - это мощный стрессовый метод
изменения
окружающей среды, который используется для эффективного выхода из
локальных
ям.
****************************************************************************
**
>Почему у меня популяция пpи малых размерах вообще не сходится?
>Yuri Burger [2:468/85.3]
В популяциях с малым размером гены распространяются слишком быстро.
Все
особи становятся похожими (популяция сошлась) еще до того, как найдено
решение
задачи. Получается так, что новый генотип с лучшей оценкой быстро
вытесняет
менее хорошие комбинации ген, исключая таким образом возможность
получения
более хорошего решения на их базе.
Вторая проблема заключается в том, что потомки, получаемые в
большей
популяции, скорее всего будут разнообразнее, чем потомки из меньшей
популяции.
С одной стороны, при малых популяциях внимание алгоритма
будет
сконцентрировано на некоторых направлениях, тоесть, эти направления
будут
изучены быстрей. Но если направление изначально было ошибочным
(ложный
оптимум) то алгоритм имеет все шансы застрять.
Выходом может быть увеличение популяции, при условии что время
работы
алгоритма не критично.
Также, может помоч самоадаптация алгоритма при выборе операторов
(в
тупиковых ситуациях увеличить вероятность применения случайного
генератора
особей).
Еще можно попытаться складировать отдельно особи, генотип которых
был
утерян популяцией, и временами добавлять эти особи (случай
удачного
кровосмешения в племенных формациях).
****************************************************************************
**
>Разное.
>vitalie vrabie [2:469/303]
ГА, однородный побитовый recombination, elitistic selection, все
вектора
одинакового размера.
Ввёл такое понятие: "однородность" (степень однородности)
популяции.
Определяется отношением количества одинаковых битов к общему их числу
в
векторе.
Поясню на примере. Скажем, вектор из 10 бит. При следующей популяции:
0101011100
1100010100
0101011110
^^ ^^ ^ ^
Имеем "однородность" равную 6/10 (шесть из десяти битов у всех
одинаковые
- в помеченных позициях).
"Однородность" вычисляю перед каждой итерацией и использую как
вероятность
мутации. Тоесть, чем однороднее (скуднее) генофонд, тем выше
вероятность
мутаций.
****************************************************************************
**
>ГА не рекомендуется, если нужно найти точный глобальный экстремум. Почему?
>Yuri Burger [2:468/85.3]
Это не совсем так... Тоесть, это не значит что ГА не сможет найти
его,
совсем нет... Просто ГА не может определить когда он нашел точное
глобальное
решение.. Часто используют эффект сходимостит популяции (когда
особи
становятся одинаковыми), это позволяет организовать остановку алгоритма, но
не
гарантирует глобальность решения.
****************************************************************************
**
>На каких функциях проверить мой генетический алгоритм?
>Yuri Burger [2:468/85.3]
Первую проверку можно сделать на простых функциях с известным
птимумом -
на пример синус, косинус и т.д. Это чтоб проверить
принципиальную
роботоспособность своей реализации. Следующий шаг - проверка на
сложных
функциях с известным оптимумом. При этом не нужно ожидать точного их
решения,
т.к. они действительно сложные. Нас в этом случае интерисуют такие
параметры,
как время поиска и качество поиска - они обычно используются для
выявления
наилучшей конфигурации алгоритма или для его сравнения с другими
алгоритмами.
Вот известные функции:
Функция Растригина. Число переменных 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
With best regards, Yuri Burger. E-mail: kruger@selena.net.ua
--- ifmail v.2.15dev5
* Origin: Unknown (2:5020/400)