|
ru.algorithms
- RU.ALGORITHMS ----------------------------------------------------------------
From : Yuri Burger 2:5020/400 19 Feb 2003 10:18:38
To : All
Subject : GA FAQ
--------------------------------------------------------------------------------
Hello, All!
> ПОЗИЦИО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овое
решение он получает комбинируя части готовых решений. Тоесть, кроссинговер
суть есть комбинирующий механизм. Исходным материалом для него служат генотипы
имеющихся решений. Это означает, что число различных решений, которые могут
быть получены кроссинговером при использовании одной и той же пары готовых
решений, ограничено. Соответственно, пространство, которое ГА может покрыть
используя лишь кроссинговер, жестко зависит от генофонда популяции. Чем
разнообразнее генотипы решений популяции, тем больше пространство покрытия.
Теперь, если вспомнить что при обнаружении локального оптимума,
соответствующий ему генотип стремится занять все позиции в популяции,
становится понятным почему ГА "сходится", тоесть перестает генерировать новые
решения.
******************************************************************************
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 |
Yuri Burger |
19 Feb 2003 10:18:38 |
|
|
