О решении проблемы настройки численных коэффициентов при решении задачи символьной регрессии методом генетического программирования

Размещено на http: //www. allbest. ru/

Сибирский государственный аэрокосмический университет им. ак. М.Ф. Решетнева, Красноярск

О решении проблемы настройки численных коэффициентов при решении задачи символьной регрессии методом генетического программирования

В. Г. Жуков (vadimzhukov@mail.ru)

Аннотация

В работе описываются применение генетического алгоритма и предложенных для него модификаций при решении задачи символьной регрессии методом генетического программирования для оптимизации математических моделей сложных систем и процессов.

Введение

Исследование с помощью математических моделей зачастую является единственно возможным способом изучения сложных систем и решения важнейших практических задач управления. Высокие темпы информатизации различных видов деятельности в настоящее время привели к тому, что появилась возможность компьютерного моделирования и проектирования сложных систем, изучения их свойств и управления ими в условиях неполноты информации, ограниченности ресурсов, дефицита времени [Абдеев, 1994]. При этом для исследования характеристик любой системы математическими методами должна быть выполнена формализация, то есть, построена математическая модель.

На практике сложно зафиксировать свойства функциональной зависимости выходных параметров от входных величин, еще сложнее привести аналитическое описание такой зависимости. Одним из способов решения данной проблемы является применение эволюционных алгоритмов путем решения задачи символьной регрессии методом генетического программирования [Koza, 1992]. Символьная регрессия дает математическое выражение в символьной форме, которое можно подвергнуть содержательному анализу, упростить и далее использовать для моделирования или оптимизации.

Однако следует отметить, что при решении задачи символьной регрессии с помощью алгоритма генетического программирования часто возникает следующая проблема: в задачах, где решение имеет сложное выражение, деревья с более простой структурой (как правило, линейные выражения) имеют пригодность выше, чем деревья со сложными структурами, которые, обычно, оказываются более перспективными. В результате простые решения начинают преобладать в популяции, и, поиск замедляется. Это связано с тем, что набор констант во множестве термов фиксирован, и, в удачно выращенных структурах, численные коэффициенты часто подобраны плохо. Таким образом, решение с очень хорошей структурой может иметь ошибку аппроксимации намного больше, чем простая структура, в которой коэффициентов меньше.

Следующий пример наглядно показывает, как плохо подобранные коэффициенты влияют на пригодность решения. Задана функция

.

генетический алгоритм регрессия программирование

Пусть в популяции есть два решения:

и .

Графики этих функций показаны на рис. 1.

Рис 1 Пример решений без подбора численных коэффициентов

Очевидно, что решение , несмотря на то, что оно плохо аппроксимирует функцию , оказывается намного лучше . Однако, если в подобрать численные коэффициенты, то решение

будет иметь меньшую ошибку аппроксимации, и теперь алгоритм отдаст предпочтение этому решению (Рис. 2).

Рис. 2 Пример решений с подбором численных коэффициентов

Алгоритм генетического программирования способен преодолеть данную проблему путем интенсивного применения оператора мутации, но, случайный характер оператора мутации может оказать и негативное воздействие ? могут быть потеряны хорошо подобранные коэффициенты или изменена выращенная структура. Также подстройка коэффициентов возможна за счет появления поддеревьев, содержащих во внешних вершинах только константы. В результате вычисления значения такого поддерева, может появиться численный коэффициент, не включенный во множество термов. Тем не менее, зачастую алгоритм либо плохо справляется с подбором коэффициентов, либо коэффициенты настраиваются очень долго.

Таким образом, необходимо настраивать параметры генерируемых решений, что можно сделать только процедурами прямого поиска. Так как алгоритм генетического программирования является модификацией генетического алгоритма и использует схожие механизмы, то именно его предложено использовать для настройки численных коэффициентов.

1. Модифицированный генетический алгоритм настройки численных коэффициентов моделей

Для решения проблемы подбора численных коэффициентов в модели, найденной с помощью метода генетического программирования, предложена следующая модификация. Будем представлять вектор независимых входных переменных

,

где n - количество переменных, в следующем виде:

.

Таким образом, полученные деревья решений будут представлять не готовые решения, а их структуры (шаблоны, функциональные формы). При оценивании решений численные коэффициенты структур настраиваются с помощью какой-либо внешней оптимизационной процедуры.

При использовании предложенной модификации алгоритм генетического программирования, в случае появления в популяции удачных структур, после подбора численных коэффициентов, отдаст предпочтение именно этим структурам. В результате, при аппроксимации нелинейных зависимостей, алгоритм гораздо быстрее перейдет от линейных (или слабо нелинейных) функций к более сложным.

Очевидно, что количество численных коэффициентов для сложных структур будет велико и при настройке параметров заданной структуры, функция ошибки аппроксимации (критерий оптимизации) будет нелинейной и многоэкстремальной. Как известно, генетический алгоритм достаточно эффективно решает сложные задачи оптимизации, более того он использует тот же механизм, что и алгоритм генетического программирования. Поэтому будем использовать его для настройки численных коэффициентов.

Использование стандартного генетического алгоритма для подбора численных коэффициентов позволяет получать хорошие аппроксимации. Но, данный алгоритм имеет следующие недостатки: время работы генетического алгоритма не сопоставимо велико по сравнению со временем работы алгоритма генетического программирования и не учитывается информация, полученная алгоритмом генетического программирования.

Для улучшения эффективности работы генетического алгоритма (применяемого для настройки параметров найденной модели) были предложены следующие модификации [Жуков, 2006]:

переход коэффициентов лучших решений;

использование статистических данных;

увеличение ресурса.

1.1 Переход коэффициентов лучших решений

Если пригодность решения, полученного алгоритмом генетического программирования

, где ,

то при параметрической оптимизации численные коэффициенты данного решения кодируются и включаются в первую популяцию генетического алгоритма. Тем самым учитывается информация, полученная методом генетического программирования, и алгоритм оптимизации начинает свою работу, имея в первой популяции вполне конкретною точку, с пригодностью выше средней. Однако нельзя сказать, что такая модификация в ста процентах случаев приведет к нахождению оптимальных численных коэффициентов, но, оптимизационный алгоритм достаточно быстро улучшит исходные численные коэффициенты и не позволит алгоритму генетического программирования потерять хорошие, с точки зрения пригодности, структуры, которые, как правило, являются нелинейными.

Таким образом, применяя данную модификацию мы помогаем алгоритму генетического программирования гораздо быстрее перейти от линейных (или слабо нелинейных) структур к более сложным за меньшее количество поколений.

1.2 Использование статистических данных

В ходе параметрической оптимизации генетический алгоритм накапливает и обрабатывает некоторую статистическую информацию о пространстве поиска, однако эта статистика в явном виде отсутствует. Для анализа работы генетического алгоритма предложен следующий способ представления накопленной статистики.

На каждом поколении вычисляется средняя пригодность:

,

N - размер популяции,

.

Далее подсчитывается количество единиц в j-ом гене k-ой хромосомы, удовлетворяющей неравенству

.

На основе статистических данных определяются вероятности появления единицы в j-ом гене:

,

где Мi - количество единиц в j-ом гене, а k - количество хромосом с

.

Используя полученные вероятности, формируется индивид по правилу (Рис. 3):

1 - если , где ;

0 - если , где ;

если , то значение гена инициализируется случайным образом.

Рис. 3 Правила формирования индивидов

Например, если вероятности имеют следующие значения:

То, получается хромосома:

Индивид, созданный таким образом, на каждом поколении искусственно вводится в популяцию. В результате исследования было установлено, что в 85% пригодность полученного индивида больше средней на каждом поколении. Таким образом, полученный индивид задает вектор движения алгоритма и ускоряет его работу за счет распространения своих генов на всю популяцию.

1.3 Увеличение ресурса

Если при настройке коэффициентов генетический алгоритм находит решение с пригодностью большей, чем пригодность этого же решения без настройки численных коэффициентов, найденного с помощью метода генетического программирования, то его ресурс (размер популяции и количество поколений) увеличивается вдвое.

2. Результаты

Эффективность модифицированного алгоритма проверена на множестве тестовых функций с усреднением по многим прогонам. Обобщенные результаты исследований работы алгоритма с применением предложенных модификаций представлены в таблице 1.

Результаты сравнительного анализа стандартных и предложенных подходов представлены в таблице 2.

В табл. 1 и 2 приведены фрагменты результатов исследований для тестовой функции Sin(x) (функциональное множество ) и используются следующие обозначения:

N1 - количество прогонов, в которых было получено решение с ошибкой E >5%, в процентах от общего количества прогонов.

N2 - количество прогонов, в которых было получено решение с ошибкой 1% < E < 5%, в процентах от общего количества прогонов.

N3 - количество прогонов, в которых было получено решение с ошибкой E < 1%, в процентах от общего количества прогонов.

Применение модифицированного генетического алгоритма для настройки численных коэффициентов решений, полученных методом генетического программирования, позволило увеличить эффективность работы метода генетического программирования:

по показателю N1 на 20 %.

по показателю N2 на 5 %.

по показателю N3 на 25 %.

Таким образом, использование предложенных модификаций позволяет получать очень хорошие аппроксимации.

Благодарности. Работа поддержана грантом Президента молодым кандидатам наук МК-4294.2008.9.

Список литературы

1. [Абдеев, 1994] Абдеев Р.Ф. Философия информационной цивилизации. - М.: ВЛАДОС, 1994.

2. [Жуков, 2006] Жуков В.Г. Моделирование сложных систем коэволюционным алгоритмом генетического программирования. Дис. канд. тех. наук: 05.13.01/. Жуков В.Г., Красноярск, СибГАУ, 2006.

3. [Koza, 1992] Koza John R. Genetic Programming: On Programming Computer by Means of Natural Selection and Genetics. - Cambridge, MA: The MIT Press, 1992.

Размещено на Allbest.ru