|
ru.algorithms
- RU.ALGORITHMS ----------------------------------------------------------------
From : Yuri Burger 2:5020/400 17 Jul 2003 09:46:08
To : All
Subject : GA FAQ 4
--------------------------------------------------------------------------------
Hello, All!
> Терминальный алфавит, функциональный базис и их свойства.
> 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 лицензией.
******************************************************************************
With best regards, Yuri Burger aka J.O. Kruger. E-mail: jo_kruger@mail.ru
--- ifmail v.2.15dev5
* Origin: Unknown (2:5020/400)
Вернуться к списку тем, сортированных по: возрастание даты уменьшение даты тема автор
| Тема: |
Автор: |
Дата: |
|
GA FAQ 4 |
Yuri Burger |
17 Jul 2003 09:46:08 |
|
|
