Введение
Актуальной проблемой в области разработки программного обеспечения является повышение его экономической эффективности с помощью более совершенных инструментов. Предлагаемый в работе подход позволит повысить эффективность синтеза алгоритмов и автоматизировать процесс выбора алгоритма решения задачи на этапе разработки технического проекта. Под синтезом, следуя [1], мы понимаем проектную процедуру, целью которой является соединение различных элементов, свойств, сторон и т. п. объекта в единое целое, систему.
Представление класса алгоритмов
Предлагается представлять класс алгоритмов в виде дерева вариантов алгоритма (ДВА) – И-ИЛИ дерева [2,4] с дополнительными вершинами, представляющими собой некоторые параметры, используемые в алгоритме. Решение на ДВА соответствует некоторому алгоритму из этого класса и представляет собой такое поддерево, в котором в каждом ИЛИ-узле выбран ровно один дочерний И-узел, а в каждом параметрическом узле – определено значение параметра. Для множества алгоритмов, заданных таким образом, требуется задать также функцию оценки приспособленности алгоритма. Для поиска оптимального варианта алгоритма необходимо найти такой вариант алгоритма, который обеспечивает глобальный экстремум целевой функции.
Эволюционное программирование на основе ДВА
Для поиска наиболее подходящего варианта алгоритма на ДВА предлагается использовать метод эволюционного программирования (ЭП), который основан на аналогии с естественными процессами селекции и генетическими преобразованиями, протекающими в природе.
Простой генетический алгоритм [3], реализующий ЭП, предварительно генерирует популяцию особей (хромосом), а затем применяет множество простых операций к популяции и генерирует новые популяции. Основные операторы, используемые в данном алгоритме – репродукция, кроссинговер, мутация.
Успех применения метода ЭП во многом зависит от того, насколько хорошо взаимодействуют между собой схема представления, операторы изменений особей и способ определения целевой функции. [3] Поэтому для данной задачи целесообразно использовать специальные определенные для этих задач операторы.
Особями являются варианты алгоритма – решения на ДВА. Для применения метода ЭП требуется определить операции репродукции, мутации и скрещивания на множестве вариантов алгоритма. Предлагается следующее определение этих операций:
Мутация. Производится случайный выбор некоторой ИЛИ-вершины либо параметрической вершины. Для ИЛИ-вершины происходит случайный выбор другой И-вершины из дочерних вершин, а для параметрической вершины – мутация внутреннего представления параметра.
Кроссинговер. Случайно выбирается некоторая вершина и две родительские особи, содержащие данную вершину, после чего, если выбрана ИЛИ-вершина, то производится обмен поддеревьев у выбранных вершин, а если параметрическая вершина – то производится кроссинговер внутренних представлений соответствующих параметров.
Репродукция. Выбираемый способ репродукции зависит от класса алгоритмов, к которому применяется данный метод.
Автоматизированная система синтеза вариантов алгоритма
Для реализации предложенного подхода разработана тестовая версия программной системы, диаграмма классов которой в нотации UML представлена на рисунке 1.
Рисунок 1 – Диаграмма классов «Автоматизированной системы синтеза вариантов алгоритма»
Модуль UI реализует графический интерфейс пользователя и разработан на основе библиотеки wxPython. Данное решение обусловлено переносимостью и гибкостью выбранной библиотеки.
Модуль Domain включает в себя основные классы, реализующие описанную модель представления класса алгоритмов в виде ДВА.
Модуль Infrastructure содержит классы, используемые для ввода-вывода данных:
- сохранение и загрузка проекта,
- считывание ДВА из исходного кода программы, описывающей дерево вариантов,
- запись исходных кодов вариантов.
Модуль Evolution включает в себя реализацию алгоритма ЭП и основан на использовании библиотеки pyevolve. Для реализации метода ЭП в этом модуле реализованы операции мутации и скрещивания, определенные ранее.
Рисунок 2 – Экранная форма главного окна «Автоматизированной системы синтеза вариантов алгоритма»
При работе с системой пользователю необходимо создать проект, в котором задать следующие входные данные:
- файлы, содержащие исходные коды программной реализации алгоритмов;
- скрипт, производящий сборку программы по заданных файлам исходных кодов;
- настройки проекта (такие, как численность особей, путь к корневому каталогу проекта и т.п.)
Результатом работы системы являются особи – варианты алгоритма и соответствующие им оценки. Также в процессе работы с системой могут быть получены промежуточные результаты – графики, представляющие оценку приспособленности особей, гистограммы распределения приспособленности особей и др. графики, для построения которых используется библиотека mathplotlib.
Расчет оценок пригодности программ особей может осуществляться разными способами. Наиболее простой способ – программа особи выводит на поток стандартного вывода некоторое число, которое считается оценкой её пригодности. Возможна реализация других способов оценки, для чего необходимо, в соответствии с рисунком 1, реализовать интерфейс Evaluator.
В процессе работы с системой пользователь может запускать заданное количество итераций эволюционного процесса, а также редактировать особи вручную при помощи разработанных элементов управления. Таким образом, в разработанной системе реализуется предложенный подход к синтезу алгоритмов.
Заключение.
В результате проделанной работы получены следующие основные результаты:
- разработана модель представления класса алгоритмов, позволяющая проводить эволюцию вариантов алгоритма;
- с целью применения метода эволюционного программирования для синтеза алгоритмов на основе данной модели определены операции мутации и скрещивания вариантов алгоритма;
- разработана тестовая версия программной системы, реализующей эволюцию вариантов алгоритма и использующей предложенные методы.
В дальнейшем предполагается проведение экспериментов на различных классах алгоритмов.
Литература
1. Божко А. Н., Толпаров А.Ч. Структурный синтез на элементах с ограниченной сочетаемостью. - Электронный журнал «Наука и образование», 2004
2. Дворянкин А.М., Половинкин А.И., Соболев А.Н. Методы синтеза технических решений.– М.: Наука. – 1977
3. Емельянов В. В., Курейчик В. В., Курейчик В. М. Теория и практика эволюционного моделирования.- М.: ФИЗМАТЛИТ, 2003
4. Половинкин А.И., Бобков Н.К., Буш Г.Я., Грудачев В.Г., Дворянкин А.М. и др. Автоматизация поискового конструирования (искусственный интеллект в машинном проектировании).– М.: Радио и связь. – 1981
