Конференции ИВТ СО РАН

VII Всероссийская конференция молодых ученых по математическому моделированию и информационным технологиям (с участием иностранных ученых)

1-3 ноября 2006 года, Красноярск, Россия

Тезисы докладов

Математическое моделирование

Алгоритм генетического программирования с автоматически определяемыми функциями

Егоров А.С.

Сибирский государственный аэрокосмический университет (Красноярск)

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

Шаблон - это функция с параметрами, вместо которых могут подставляться другие функции.

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

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

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

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

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

Дополнительные материалы: Полный текст доклада
Примечание. Тезисы докладов публикуются в авторской редакции

Ваши комментарии
Обратная связь

[Головная страница]
[Конференции]