На правах рекламы:
ISSN 0236-235X (P)
ISSN 2311-2735 (E)

Авторитетность издания

ВАК - К1
RSCI, ядро РИНЦ

Добавить в закладки

Следующий номер на сайте

4
Ожидается:
09 Декабря 2024

Разработка и исследование гибридного метода генетического программирования

Implementation and investigation of hybryd genetic programming method
Статья опубликована в выпуске журнала № 3 за 2010 год.
Аннотация:Предложен новый подход к решению задач символьной регрессии, включающий в себя стандартный метод генетического программирования и разработанную процедуру локального поиска на структуре решения. Приведены результаты исследования рассматриваемого подхода на наборе тестовых функций. Изложены результаты апробации подхода на реальной задаче моделирования процесса рудно-термической плавки.
Abstract:A new approach for solving symbolic regression problems is proposed. It consists of standard method of genetic programming and developed procedure of local search on the structure of the solution. The results of investigation of this approach on a set of test functions are presented. The results of testing the approach on the real problem of ore-thermal melting process modeling are also presented in the article.
Авторы: Бухтояров В.В. (vladber@list.ru) - Сибирский государственный аэрокосмический университет им. академика М.Ф. Решетнева, г. Красноярск, Красноярск, Россия, кандидат технических наук, Семенкин Е.С. (styugin@rambler.ru) - Сибирский государственный аэрокосмический университет им. академика М.Ф. Решетнева, г. Красноярск, Россия
Ключевые слова: рудно-термическая плавка, локальный поиск, генетическое программирование, эволюционные алгоритмы, моделирование
Keywords: ore-thermal melting, local search, genetic programming, evolutionary algorithms, modeling
Количество просмотров: 18050
Версия для печати
Выпуск в формате PDF (5.84Мб)
Скачать обложку в формате PDF (1.43Мб)

Размер шрифта:       Шрифт:

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

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

В большинстве численных методов идентификации (регрессионный анализ, непараметрические и нейросетевые методы) для построения зависимостей, аппроксимирующих экспериментальные данные, используют регрессионные модели. Одним из недостатков упомянутых численных методов является то, что построенная при их помощи модель по сути является моделью черного ящика. Преодолеть этот недостаток можно за счет сведения исходной задачи к задаче символьной регрессии и последующего ее решения подходящими методами. Задача символьной регрессии заключается в нахождении в символьной форме математического выражения, аппроксимирующего зависимость между входными и соответствующими им выходными переменными исследуемого процесса или системы. Полезным свойством решения задачи символьной регрессии представляется то, что полученное решение, помимо собственно вычислительной процедуры, является символьным математическим выражением – формулой, которая может быть подвергнута содержательному анализу, а затем упрощена либо уточнена. На современном этапе методы решения задачи символьной регрессии не разработаны достаточно хорошо. Метод генетического программирования – один из самых многообещающих подходов в данном направлении [1].

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

Рассмотрим постановку задачи символьной регрессии. Пусть имеются наблюдения входных и выходных переменных исследуемого процесса V=(xi, yi), , n – объем выборки наблюдений. Известно, что существует зависимость y=f(x), связывающая входные и выходные переменные исследуемого процесса, однако вид и структура зависимости неизвестны.

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

В качестве критерия оптимальности построенной регрессионной модели может использоваться, например, величина относительной средней ошибки моделирования по выборке:

,                (1)

где i – номер наблюдения в выборке, ; ymax и ymin – максимальное и минимальное значения выходного параметра.

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

С этой целью была разработана специальная процедура локального поиска на структуре решения [5]. Опишем ее подробнее.

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

2.   Применение к отобранным индивидам процедуры локального поиска. Локальный поиск осуществляется на заданном числе r вершин дерева, которыми представлено исходное решение. Вершины дерева выбираются случайно с равной вероятностью , где i – номер вершины, ; s – число вершин в дереве.

Поиск осуществляется следующим образом:

-    значение в выбранной вершине дерева заменяется новым в соответствии с правилами для локального поиска в генетическом программировании [5];

-    вычисляется значение функции пригодности индивида, измененного на предыдущем шаге;

-    если пригодность измененного индивида выше пригодности исходного индивида, то шаг поиска считается успешным, новое содержание вершины дерева фиксируется; иначе шаг поиска считается неудачным, вершине возвращается исходное значение;

-    переходим к новому шагу локального поиска (к началу п. 2), если число шагов не превышает r, иначе поиск останавливается.

3.   Возвращение индивидов в исходную популяцию для применения к ним операторов стандартного метода генетического программирования. Индивид возвращается в популяцию таким, каким он стал после применения локального поиска, и с новым значением функции пригодности.

Операторы селекции, скрещивания и мутации в гибридном алгоритме генетического программирования применяются аналогично соответствующим операторам стандартного метода генетического программирования.

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

Подпись:  
Рис. 1. Блок-схема гибридного алгоритма
 генетического программированияОбщая схема гибридного алгоритма генети- ческого программирования представлена на рисунке 1.

Для оценки эффективности предлагаемого метода гибридного генетического программирования был проведен ряд численных экспериментов. В качестве конкурирующих подходов в исследования включен стандартный метод генетического программирования (далее на рисунках и в таблицах он обозначен как Стандартный МГП).

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

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

Численные эксперименты проводились с помощью разработанной программной системы «Моделирование: гибридный метод генетического программирования», в которой реализованы исследуемые методы [6].

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

Эффективность методов оценивалась по критерию надежности, который определялся как отношение числа запусков, в которых была достигнута заданная точность аппроксимации исходных данных, к общему числу запусков. При этом максимальное число вычислений функции пригодности не должно превышать заданное в критерии останова. Статистика для получения оценок надежности набиралась по 50 запускам каждого из рассмотренных методов. Значимость в различиях результатов алгоритмов проверялась методами ANOVA. Проверка выполнялась при уровне значимости α=0,05.

Подпись: Таблица 1 Тестовые задачи№ задачи	Моделируемая функция	Интервал варьирования переменных	Функциональ-ное множество	Объем выборки1	   1002	   1003	   2004	Функция Растригина:   2005	   2006	Функция Розенброка:   2007	   300Описание тестовых задач приведено в таблице 1. В таблице 2 представлены результаты сравнительного исследования эффективности, полученные для рассматриваемых модификаций метода генетического программирования на тестовых задачах. Жирным шрифтом выделен метод, победивший на тестовой задаче, то есть статистически значимо превосходящий по надежности конкурирующий метод.

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

Одной из практических задач, на которой апробировались разработанные методы и оценивалась их эффективность, являлась задача моделирования процесса рудно-термической плавки (РТП) [7].

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

Таблица 2

Результаты тестирования

Тестовая задача

Стандартный МГП

Гибридный МГП

1

0,6

0,95

2

0,9

1

3

0,5

0,9

4

0,45

0,95

5

0,95

1

6

0,6

0,95

7

0,45

0,85

Известно, что существует зависимость, связывающая входные и выходные параметры процесса РТП:

.                                            (2)

Однако вид и структура этой зависимости неизвестны. Необходимо по имеющимся выборкам наблюдений восстановить в символьном виде функциональную зависимость, характеризующую процесс РТП:

.                                            (3)

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

.                                                       (4)

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

Выборка наблюдений за процессом РТП состоит из 47 элементов. При решении задачи выборка была разбита случайным образом на две части: на обучающую выборку, включающую в себя 37 элементов, и на экзаменующую, состоящую из 10 элементов.

Лучшее решение, найденное с помощью разработанного подхода, имеет следующий вид:

.

Для обучающей выборки относительная ошибка оценивания составила 8,8 %, а для экзаменующей выборки относительная ошибка прогнозирования составила 10,2 %. Результаты моделирования предложенным алгоритмом генетического программирования сопоставимы с результатами нейросетевого моделирования, полученными группой аналитиков [7].

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

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

Подпись:  Рис. 2. График прогнозируемой концентрации никеля и реальных данных в точках обучающей выборки  Рис. 3. График прогнозируемой концентрации никеля и реальных данных в точках экзаменующей выборкиПолученные результаты решения задачи моделирования процесса РТП можно считать вполне удовлетворительными. Достигнутое значение относительной ошибки прогноза концентрации никеля в отработанном шлаке равно 10 %, что является достаточно хорошим показателем ввиду чрезвычайной ограниченности объема выборок наблюдений, отсутствия какой-либо априорной информации о структуре модели исследуемого процесса, о законах распределения помех. Все это, безусловно, затрудняет процесс построения модели РТП. Тем не менее, разработанный гибридный алгоритм генетического программирования доказал свою работоспособность в условиях ограниченности вычислительных ресурсов и может использоваться при необходимости быстро получить с приемлемой точностью аналитический вид зависимости, связывающей входные и выходные переменные, и построить прогноз состояния исследуемого процесса, значений его выходных переменных.

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

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

Литература

1.   Koza John R. The Genetic Programming Paradigm: Genetically Breeding Populations of Computer Programs to Solve Problems. Cambridge, MA: MIT Press, 1992.

2.   Holland J.H. Adaptation in natural and artificial systems. Ann Arbor. MI: University of Michigan Press, 1975.

3.   Goldberg D.E. Genetic algorithms in search, optimization and machine learning. Reading, MA: Addison-Wesley, 1989.

4.   Бежитский С.С., Семенкин Е.С., Семенкина О.Э. Гибридный эволюционный алгоритм для задач выбора эффективных вариантов систем управления // Автоматизация и современные технологии. 2005. № 11. С. 24–31.

5.   Бухтояров В.В. Разработка гибридного метода генетического программирования // Решетневские чтения: матер. XII Междунар. науч. конф., посвященной памяти генерального конструктора ракетно-космических систем акад. М.Ф. Решетнева (ноябрь 2008 г., Красноярск). Красноярск: РИО СибГАУ, 2008.

6.   Бухтояров В.В. Моделирование: гибридный алгоритм генетического программирования // Свид. о гос. рег. № 2010613317. М.: ФИПС, 2010.

7.   Гонебная О.Е. Экспертная система рудно-термической плавки: дис. … канд. техн. наук. Красноярск: ГУЦМиЗ, 2004. 136 с.


Постоянный адрес статьи:
http://swsys.ru/index.php?page=article&id=2554&lang=&lang=&like=1
Версия для печати
Выпуск в формате PDF (5.84Мб)
Скачать обложку в формате PDF (1.43Мб)
Статья опубликована в выпуске журнала № 3 за 2010 год.

Возможно, Вас заинтересуют следующие статьи схожих тематик: