Символьная регрессия - краткий обзор

Зелинка Иван

Университет Tomas Bata Zlin, Факультет Информационных Технологий Технологического Института, Чешская республика

Источник:http://www.mafy.lut.fi/EcmiNL/ecmi35/node70.html

Автор перевода: Ярошенко Е.А.

Введение

Термин "символьная регрессия" представляет собой процесс, во время которого полученные данные (статистика) аппроксимируются подходящей математической формулой, например, " ", и т.д. Этот процесс весьма известен среди математиков и используется, когда получены данные неизвестного процесса. В течение долгого времени символьная регрессия была областью работы только людей, но за несколько последних десятилетий она стала также областью работы компьютеров. Идея, как решить различные проблемы с помощью символьной регресии посредством эволюционных алгоритмов (ЭА), пришла от Джона Козы, который использовал генетический алгоритм (ГА) в так называемом генетическом программировании (ГП) [1], [2]. Генетическое программирование является в основном символьной регрессией, которая выполняется эволюционными алгоритмами вместо людей. Способность решать действительно сложные задачи была доказана много раз, и сегодня ГП находится на таком уровне работы, что в состоянии синтезировать (например) чрезвычайно сложные электронные цепи [3]. Ясно, что важность символьной регрессии увеличится из-за растущей сложности решаемых задач в науке и промышленности.

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

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

Символьная регрессия и эволюционные алгоритмы - главные идеи

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

Символьная регрессия основана на эволюционных алгоритмах, и её главная цель – «ссинтезировать» эволюционным способом такую "программу" (математические формулы, компьютерные программы, логические выражения, и т.д...), которая решит определенную задачу пользователя наилучшим возможным образом. В то время, как область ЭА имеет числовую природу (вещественные, комплексные, целые, дискретные), область символьной регрессии имеет функциональную природу, т.е. она состоит из набора функции как ( sin(), cos(), gamma(), MyFunction ()...) и так называемого терминального набора (t, x, p...). Из соединения обоих наборов формируется окончательная программа, которая может быть весьма сложна с точки зрения её структуры.

В в настоящее время есть три метода, позволяющие сделать это: генетическое программирование, грамматическая эволюция и аналитическое программирование.

Генетическое программирование

Генетическое программирование [1], [2] является самым старым методом автоматического создания программы посредством генетического алгоритма, который был развит американским информатиком Дж. Koзa (см. также www.genetic-programming.org). Этот метод основан на компьютерном языке Lisp, который в состоянии управлять символьными выражениями. За время существования ГП было решено многочисленное количество задач, таких как настройка данных, логический синтез выражений, оптимизация траектории робота, синтез программы для искусственного движения муравья, идентификации системы, и т.д. Главный принцип ГП таков, что программы представляются в хромосомах в виде синтаксических деревьев. Деревья, основанные на принципах ГА, режутся оператором кроссинговер, и поддеревья обмениваются между собой.

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

Генетическое программирование также использует новые технологии, такие как автоматически определяемые функции (АОФ), которая может быть определена как автоматически определяемые итерации (AОИ), автоматически определяемые циклы (AОЦ), автоматически определяемые рекурсии (AОР), и т.д. Термин "автоматический, означает, что некоторые функции, созданные за время эволюции, автоматически включаются в основной набор функций.

Грамматическая эволюция

Грамматическая эволюция - второй метод для выполнения символьной регрессии, который во многом происходит от ГП. Согласно автору (C. Ryan, www.gramatical-evolution.org) ГЭ является символьной регрессией, которая может быть осуществлена посредством произвольного языка программирования, например, Lisp, C ++, Java, XML, Perl, Fortran и т.д. В отличие от ГП грамматическая эволюция - в основном является его расширением, которое не использует прямое символьное представление в Lisp, но использует так называемую форму записи Бэкуса - Наура (BNF). Основанная на BNF ГЭ, способна выполнить символьную регрессию вне зависимости от компьютерног языка.

На протяжении существования ГЭ были сделаны некоторые сравнительные процессы моделирования, основанные на проблемах, решенных Koza в ГП. Полные тексты пожалуйста см. www.gramatical-evolution.org.

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

Аналитическое программирование (И. Зелинка, www.ft.utb.cz/people/zelinka/soma), было вдохновлено двумя существующими методами: Хилбертовы пространства и ГП. Принципы и общая философия аналитического программирования (AП) происходит от этих двух методов. В AП идея об эволюционном создании символьных решений взята из ГП, в то время как от Хилбертовых пространств взята идея функционального пространства и построения результирующей функции посредством процесса поиска. Этот процесс обычно выполняется числовыми методами, такими как метод Ритц или метод Галеркина [4]. Ядро AП основано на наборе функций, операторов и так называемых терминалов, которые обычно являются константами или независимыми переменными так же как в ГП и ГЭ. Главная цель AП состоит в том, чтобы сформировать подходящую программу (математические формулы, например см. результаты AП (1) - (4)), которая соответствовала бы статистическим данным как можно лучше. По этой причине дискретный набор и был принят в AП.

Дискретный набор был предложен в [5], [6]. В аналитическом программировании дискретный набор используется, чтобы создать индекс целогг типа, который использовался бы в эволюционном процессе как альтернативная особь, обработываемая в ЭА методом целого числа [5], [6]. Особь создается автоматически в популяции как особь целого числа, диапазон параметров которого не может превысить количество элементов используемого набора функций и терминалов.

Сегодня AП существует в трех версиях. Все три версии нуждаются для синтеза программы в тех же самых наборах функций, терминалов, и т.д как Koza использовал в ГП [1], [2]. Первая основная версия, названная AP_basic, является основной версией AП. Она использует константы из терминального множества для того, чтобы синтезировать программы таким же образом как Koza [1]. Вторая версия – AP_meta – является модификацией в смысле оценки констант. В сравнении с AP_basic в AP_meta есть только одна неспецифицированная константа "K", сгенерированная вместо набора сгенерированных случайным образом констант. Константа "K" после синтеза индексируется так, чтобы K1,K2,...,Knбыли в полученной формуле, и затем чтобы все Kn были оценены различными или тем же самым эволюционным методом. Поскольку ЭА "работает под" ЭА (т.е. EA_master-> программа -> K индексация ->EA_slave -> оценки Kn ),то эта версия называют AП с метаэволюцией – AP_meta . Последняя модификация - AP_nf,которая основана на AP_meta,является таковой, что вместо другого ЭА используется K, оцененная подходящим нелинейным методом настройки.

Чтобы проверить, что AП жизнеспособно, было произведено моделирование - эксперименты, которые были повторены для каждого случая много раз [7], [8] и [9]. Все экспериметны моделирования, особенно последний сравнительный, показал, что AП в состоянии решить те же самые проблемы как и ГП или ГЭ на том же самом уровне качества.

Заключение

Метод символьной регрессии, описанный здесь, имеет три вида. Первый – генетическое программирование – является самым старым видом и может использоваться только генетическими алгоритмами и языком программы Lisp. Второй – грамматическая эволюция – "разворачивается" в отличие от генетического программирования так, что вместо Lisp там могут использоваться различные компьютерные языки программирования. Однако, грамматическая эволюция все еще использует двойное представление особей и операций кроссинговера как генетическое алгоритмы. Третий метод, названный аналитическим программированием, независим от языка программирования и может использоваться любым эволюционным алгоритмом,и не имеет значения, как вычислено новое поколение.

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

Для полной информации обо всех трех методах рекомендуется посмотреть литературу в конце или начальных страницах всех трех методов, то есть для генетического программирования: www.genetic-programming.org, для грамматической эволюции: www.gramatical-evolution.org и для аналитического программирования: www.ft.utb.cz/people/zelinka/soma.

References

1. Koza J.R. Genetic Programming, MIT Press, ISBN 0-262-11189-6, 1998

2. Koza J.R., Bennet F.H., Andre D., Keane M., Genetic Programming III, Morgan Kaufnamm pub., ISBN 1-55860-543-6, 1999

3. J. R. Koza, M. A. Keane, M. J. Streeter, Evolving Inventions, ScientificAmerican, February 2003, p. 40-47, ISSN 0036-8733, see also www.sciam.com

4. Rektorys, Karel, Variational methods in Engineering Problems and Problems of Mathematical Physics. Czech Ed., 1999, ISBN 80-200-0714-8. English edition is also available on the Internet, see www.amazon.com

5. Lampinen Jouni, Zelinka Ivan. New Ideas in Optimization - Mechanical Engineering Design Optimization by Differential Evolution. Volume 1. London : McGraw-Hill, 1999. 20 p. ISBN 007-709506-5.

6. Zelinka, Ivan, Artificial Intelligence in The Problems of Global Optimization (Czech Ed.) BEN, 2002, 190 p. ISBN 80-7300-069-5

7. Zelinka I.: Analytic Programming by Means of Soma Algorithm. Mendel '02, In: Proc. 8th International Conference on Soft Computing Mendel'02, Brno, Czech Republic, 2002, 93-101., ISBN 80-214-2135-5

8. Zelinka I.: Analytic Programming by Means of Soma Algorithm. ICICIS'02, First International Conference on Intelligent Computing and Information Systems, Egypt, Cairo, 2002, ISBN 977-237-172-3

9. Zelinka I., Oplatkova Z.: Analytic Programming - Comparative Study. CIRAS'03, The second International Conference on Computational Intelligence, Robotics, and Autonomous Systems, Singapore, 2003