ISSN 1991-3087
Рейтинг@Mail.ru Rambler's Top100
Яндекс.Метрика

НА ГЛАВНУЮ

Синтез алгоритмов на основе эволюционного программирования

 

Мусман Александр Эдуардович,

магистрант Волгоградского государственного технического университета.

 

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

 

Модель представления класса алгоритмов

 

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

 

Метод эволюционного программирования

 

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

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

 

Эволюционные операторы, определенные для предложенной модели

 

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

Особями являются варианты алгоритма – решения на дереве вариантов алгоритма. Для применения метода эволюционного программирования требуется определить операции репродукции, мутации и скрещивания на множестве вариантов алгоритма. Предлагается следующее определение этих операций:

-                   Мутация. Производится случайный выбор некоторой ИЛИ-вершины либо параметрической вершины. Для ИЛИ-вершины происходит случайный выбор другой И-вершины из дочерних вершин, а для параметрической вершины – мутация внутреннего представления параметра.

-                   Кроссинговер. Случайно выбирается некоторая вершина и две родительские особи, содержащие данную вершину, после чего, если выбрана ИЛИ-вершина, то производится обмен поддеревьев у выбранных вершин, а если параметрическая вершина – то производится кроссинговер внутренних представлений соответствующих параметров.

-                   Репродукция. Выбираемый способ репродукции зависит от класса алгоритмов, к которому применяется данный метод.

 

Основные особенности предлагаемого метода

 

Отметим следующие преимущества предлагаемого метода синтеза алгоритмов:

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

2)                 простота представления класса алгоритмов в виде дерева вариантов алгоритма;

Также можно отметить следующие особенности, которые необходимо учесть при применении данного метода:

1)                 требуется обеспечить эквивалентность результатов, получаемых при выполнении фрагментов кода, соответствующих И-узлам, являющихся дочерними узлами одного ИЛИ-узла. Это может быть обеспечено, например, путем активного применения модульного тестирования получаемых вариантов;

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

 

Программная реализация

 

Разработана тестовая версия программной системы, в которой вершинам дерева вариантов алгоритма соответствуют текстовые фрагменты исходного кода программы-реализации алгоритма. В исходном коде программы на языке C++ текстовые фрагменты выделяются специальными метками:

- начало ИЛИ-узла, внутри которого происходит подстановка И-узла, выбранного в соответствующем варианте алгоритма;

- начало И-узла, рекурсивно вычисленный текст которого подставляется в родительский ИЛИ-узел, если данный И-узел выбран в нем в соответствующем варианте алгоритма;

- окончание узла;

- параметрический узел – метка данного типа узлов находится в исходном тексте справа от некоторой численной константы (имеющей целочисленный тип или тип числа с плавающей запятой). Метка параметрического узла определяет также интервал и шаг варьирования соответствующего параметра.

 

Заключение

 

В результате проделанной работы получены следующие основные результаты:

- разработана модель представления класса алгоритмов, позволяющая проводить эволюцию вариантов алгоритма;

- с целью применения метода эволюционного программирования для синтеза алгоритмов на основе данной модели определены операции мутации и скрещивания вариантов алгоритма;

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

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

 

Литература

 

1. Божко А. Н., Толпаров А.Ч. Структурный синтез на элементах с ограниченной сочетаемостью. - Электронный журнал «Наука и образование», 2004.

2. Дворянкин А.М., Половинкин А.И., Соболев А.Н. Методы синтеза технических решений.– М.: Наука. – 1977.

3. Емельянов В. В., Курейчик В. В., Курейчик В. М. Теория и практика эволюционного моделирования.- М.: ФИЗМАТЛИТ, 2003.

 

Поступилав редакцию 17.05.2010 г.

 

2006-2019 © Журнал научных публикаций аспирантов и докторантов.
Все материалы, размещенные на данном сайте, охраняются авторским правом. При использовании материалов сайта активная ссылка на первоисточник обязательна.