Разработка и исследование вероятностных эволюционных алгоритмов для моделирования и оптимизации сложных систем



Рис. 7. Пример усреднения компонент вектора вероятностей в алгоритме прогноза

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

Предложенный алгоритм прогноза сходимости вероятностного ГА был апробирован на тестовых задачах и показал достаточно высокую надежность при заданных вычислительных ресурсах [23, 28]. Алгоритм прогноза может быть использован для стандартного ГА, вероятностного ГА и других стохастических алгоритмов псебдобулевой оптимизации.

1.6 Выводы

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

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

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

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

Глава II. Разработка и исследование метода вероятностного генетического программирования для моделирования сложных систем

2.1 Методы решения задач аппроксимации в моделировании сложных систем

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

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

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

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

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

Непараметрические методы не требуют дополнительной информации о структуре (параметрической) моделируемого объекта. Задача регрессии решается путем восстановления плотности вероятности [9, 17]:

,

,

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

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

.

Функция активации нейрона - некоторое нелинейное преобразование взвешенной суммы входных переменных. Задавая различные архитектуры сетей, состоящие из множества нейронов можно описывать сложные нелинейные зависимости [7, 30].

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

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

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

2.2 Обычный метод генетического программирования для решения задачи символьной регрессии и его исследование

Для решения многих практических задач наиболее естественным представлением решений являются компьютерные программы. Обычно компьютерные программы - иерархические композиции процедур и входных данных, отражающих состояние системы. Одна из центральных задач теории вычислительных систем (computer science) - научить компьютер решать поставленную задачу, не объясняя ему как это делать. Генетическое программирование позволяет сделать это путем создания работающих компьютерных программ исходя из высокоуровневой постановки задачи. Генетическое программирование достигает поставленной цели автоматического программирования или программного синтеза (automatic programming, program synthesis) путем выращивания популяций компьютерных программ, используя принцип естественного отбора Дарвина, и основанные на генетических принципах операторы, которые могут включать репродукцию, скрещивание и мутацию [48].

Каким образом генетические алгоритмы могут быть использованы для автоматического программирования?

В 1975 году Джон Холланд предложил некую модификацию генетического алгоритма известную как классификатор (classifier system), состоящий из IF…THEN правил. Например, бит равный 1 означает выполнение условия IF, бит равный 0 - не выполнение, последующие биты определяют действие при выполнении (невыполнении) условий [45].

В 1985 году Н. Крамер предложил вычислять непосредственно код компьютерных программ и продемонстрировал эволюцию простых арифметических выражений. Он также предложил представление решений в виде деревьев [40].

Джон Коза (John R. Koza) в 1987 продемонстрировал эволюцию выражений языка программирования LISP (LISP S-expression), которые по сути являются компьютерными программами. Он впервые использовал термин «генетическое программирование». В 1989 году Коза показал применение генетического программирования для решения различных задач [49].

Настоящее развитие генетическое программирование получило после выхода в 1992 году книги Джона Козы «Genetic Programming: On the Programming of Computers by Means of Natural Selection & Genetics», в которой он продемонстрировал области применения метода, а также численные результаты экспериментов и некоторые практические рекомендации [50].

2.2.1 Представление решений в методе генетического программирования

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

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

Множество всех возможных внутренних вершин дерева называется функциональным множеством .

Множество всех возможных внешних вершин дерева называется терминальным множеством .

Элементы функционального множества обычно являются рабочими блоками программы (процедурами, функциями), элементы терминального множества - входными данными (переменными и константами). Пример дерева в методе ГП представлен на рис. 8.

Рис. 8. Пример решения в методе ГП.

Объединение функционального и терминального множеств назовем универсальным множеством .

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

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

Например, множество не является замкнутым, так может привести к делению на нуль.

Достаточность. Для обеспечения достаточности элементы множества должны быть выбраны таким образом, чтобы можно было бы решить поставленную задачу.

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

2.2.2 Общая схема метода генетического программирования, применение основных генетических операторов

Общая схема метода генетического программирования представлена ниже:

1. Генерируем начальную популяцию одним из методов выращивания, использую элементы множеств и .

2. На шаге вычисляем пригодность решений в популяции .

3. Применяем операторы селекции, клонирования, скрещивания и мутации к поколению и формируем новую популяцию .

4. Стоп, если допустимое решение найдено, иначе и переходим к шагу 2.

Рассмотрим шаги алгоритма подробней.

Для инициализации популяции используются следующие методы выращивания деревьев (решений в пространстве поиска):

Полный метод (full method).

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

Метод выращивания (grow method).

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

Комбинированный метод (ramped half and half).

Часть популяции выращивается полным методом, другая - методом
роста [51].

Функция пригодности (fitness function) является оценкой приспособленности индивида к окружающей среде. Пригодность является движущей силой в естественном отборе Дарвина. Аналогично, функция пригодности в генетическом программировании является основанием для создания следующих поколений решений. Более приспособленные решения должны иметь большее значение функции пригодности, менее приспособленные - меньшее значение. Обычно функция пригодности принимает положительные значения.

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

Существует две схемы скрещивания в методе генетического программирования: стандартное скрещивание (standard crossover) и одноточечное скрещивание (one-point crossover).

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

Пример стандартного скрещивания (рис. 9):

Рис. 9. Пример стандартного скрещивания в методе генетического программирования.

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

Пример одноточечного скрещивания (рис. 10). Жирной линией отмечены связи, которые могут быть выбраны в качестве общей точки скрещивания:

Рис. 10. Пример одноточечного скрещивания в методе генетического программирования.

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

Существует две схемы применения оператора мутации в генетическом программировании.

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

Рис. 11. Пример мутации по схеме 1

При использовании второй схемы, выбранное поддерево заменяется поддеревом, выращенным методом роста, новое поддерево имеет глубину не больше, чем глубина выбранного поддерева (рис. 12).

Рис. 12. Пример мутации по схеме 2

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

2.2.3 Решение задачи символьной регрессии с помощью метода генетического программирования

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

1. терминальное множество,

2. функциональное множество,

3. функцию пригодности,

4. параметры, контролирующие работу алгоритма,

5. критерий остановки.

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

.

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

- арифметические операции (),

- математические функции (и т.д.),

- булевы операции (),

- специальные предопределенные функции (Automatically Defined Functions - ADFs).

Необходимо помнить, что заданное универсальное множество должно удовлетворять условию замкнутости. Например, для исключения деления на нуль вводят «защищенное деление», которое возвращает единицу, когда знаменатель равен нулю.

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

(7)

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

Параметры, контролирующие работу алгоритма обычно включают:

- размер популяции,

- метод роста,

- максимальную начальную глубину деревьев,

- метод селекции и его параметры (например, размер турнира для турнирной селекции),

- вероятность и тип мутации.

В качестве критерия остановки работы алгоритма можно выбрать один из следующих:

- достигнуто заданное число поколений (итераций),

- достигнута заданная точность аппроксимации,

- относительное изменение средней пригодности не превышает заданной величины.

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

1. Инициализировать популяцию случайным образом одним из методов роста.

2. Оценить популяцию, используя критерий (7).

3. Если выполняется критерий остановки, то КОНЕЦ, иначе шаг 4.

4. На итерации произвести селекцию одним из предложенных методов для поколения .

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

6. В поколение попадает часть особей из популяции и часть из промежуточной популяции.

7. Переход к шагу 2.

2.2.4 Исследование работоспособности на тестовых задачах

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

1. Функция: , . Выборка: случайная, объем - 200 точек. Условие достаточности не выполняется, т.е. функциональное множество не содержит тригонометрических функций.

Терминальное множество: , где .

Функциональное множество: .

Размер популяции: 100. Метод роста: полный. Начальная глубина деревьев: 9. Селекция: ранговая. Вероятность мутации: 0.001.

«Идеальным» решением было бы выражение, соответствующее разложению функции в ряд. Для отрезка разложение выглядит следующим образом

Найденное выражение:

.

Поколение: 3050.

Сложность дерева (число вершин): 197.

Ошибка аппроксимации (квадратичный критерий): 0.00505.

После упрощения полученного выражения получим:

Т.о. алгоритм смог восстановить первых 2 члена с точностью до знака и коэффициента.

2. Функция: . Выборка: случайная, объем - 2000 точек.

Терминальное множество: , где .

Функциональное множество: .

Размер популяции: 100. Метод роста: полный. Начальная глубина деревьев: 6. Селекция: ранговая. Вероятность мутации: 0.001.

Найдено точное решение: .

Поколение: 13.

Сложность дерева (число вершин): 7.

3. Функция Растригина: . Выборка: случайная, объем - 4000 точек.

Терминальное множество: , где .

Функциональное множество: .

Размер популяции: 100. Метод роста: полный. Начальная глубина деревьев: 6. Селекция: ранговая. Вероятность мутации: 0.05.

Найдено точное решение: .

Поколение: 178.

Сложность дерева (число вершин): 13.

4. Функция: . Выборка: случайная, объем - 2000 точек.

Терминальное множество: , где .

Функциональное множество: .

Размер популяции: 100. Метод роста: полный. Начальная глубина деревьев: 5. Селекция: ранговая. Вероятность мутации: 0.01.

Найдено точное решение:

.

Поколение: 72.

Сложность дерева (число вершин): 18.

5. Функция: . Выборка: случайная, объем - 3000 точек.

Терминальное множество: , где .

Функциональное множество: .

Размер популяции: 100. Метод роста: полный. Начальная глубина деревьев: 7. Селекция: ранговая. Вероятность мутации: 0.001.

Найдено решение:

.

Поколение: 42.

Сложность дерева (число вершин): 43.

Ошибка аппроксимации (квадратичный критерий): 0.036.

6. Функция: . Выборка: случайная, объем - 5000 точек.

Терминальное множество: , где .

Функциональное множество: .

Размер популяции: 100. Метод роста: полный. Начальная глубина деревьев: 7. Селекция: ранговая. Вероятность мутации: 0.001.

Найдено точное решение:

.

Поколение: 26.

Сложность дерева (число вершин): 21.

7. Функция Растригина: . Выборка: случайная, объем - 5000 точек.

Терминальное множество: , где .

Функциональное множество: .

Размер популяции: 100. Метод роста: полный. Начальная глубина деревьев: 9. Селекция: ранговая. Вероятность мутации: 0.01.

Найдено решение:

.

Поколение: 1500.

Сложность дерева (число вершин): 65.

Ошибка аппроксимации (квадратичный критерий): 2.986.

2.3 Основные идеи вероятностного генетического программирования и его исследование

Как упоминалось ранее, в основе метода ГП лежит генетический алгоритм предложенный Холландом [45]. Попробуем вместо стандартного ГА использовать вероятностный ГА, который активнее использует статистическую информацию о пространстве поиска.

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

Рис. 13. Пример полного дерева глубины 3.

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

, где

Рис. 14. Нумерация вершин полного дерева.

При вычислении выражения полного дерева, построенного из бинарной строки, может оказаться, что в какой-то из вершин появится функция одного аргумента (рис. 15). Тогда при интерпретации символьного выражения будем учитывать только левое поддерево данной вершины. При таком способе вычисления решения функция пригодности будет определена однозначно, однако в пространстве поиска будет появляться множества постоянства. Как показывают численные эксперименты, ВГА эффективно решает задачи содержащие множества постоянства (Ф7, Ф8, Ф14).



Рис. 15. Вычисление символьного выражения дерева, содержащего унарные функции

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

Рис. 16. Пример использования функции ADF1.

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

Рис. 17. Пример использования функции ADF2.

В случае, когда предопределенные функции ADF1 и ADF2 не используются, точное решение все равно может быть найдено. Это возможно за счет появления в деревьях так называемого неэффективного кода (non-effective code) - поддеревьев не несущих никакой информации (например, и др.). В [38] показано, что неэффективные коды защищают решения от разрушительного скрещивания (destructive crossover) - скрещивания, которое дает потомков с пригодностью ниже, чем у родителей.

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

1. Задать небольшую начальную глубину деревьев.

2. Запустить метод ГП.

3. Если в результате длительного времени приемлемое решение не найдено, и весь код деревьев эффективный, то увеличить глубину деревьев на 1. Исходные деревья становятся левыми поддеревьями корня.

4. Если приемлемое решение найдено, то СТОП, иначе повторить
шаги 2 - 4.

Рис. 18. Пример наращивания деревьев.

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

2.3.1 Общая схема метода вероятностного генетического программирования

На основе предложенного выше способа кодирования и интерпретации полных деревьев построена схема метода ГП, основанная на механизме ВГП. Такая схема получила название вероятностное генетическое программирование (ВГП):

1. Случайным образом формируются векторов . Вычисляется распределение , .

2. На k-м шаге в соответствии с распределением формируются векторов .

3. Случайным образом формируются новые решения: с вероятностью компоненты векторов меняются на противоположные.

4. На основе векторов формируются полные деревья решений, интерпретируются решения, решения оцениваются.

5. Выбираются векторов из в соответствии с конкретным правилом отбора.

6. Пересчитывается распределение единичных компонент .

7. Если не выполняется условие остановки, то , , повторить
шаги 2 - 6.

Оценивание деревьев в п. 4 происходит по критерию (7), аналогично обычному ГП.

2.3.2 Исследование работоспособности на тестовых задачах

1. Функция: . Выборка: случайная, объем - 1000 точек.

Терминальное множество: , где .

Функциональное множество: .

Размер популяции: 100. Глубина деревьев: 5. Селекция: ранговая. Вероятность мутации: 0.01.

Найдено точное решение: .

Поколение: 89.

2. Функция Растригина: . Выборка: случайная, объем - 1000 точек.

Терминальное множество: , где .

Функциональное множество: .

Размер популяции: 100. Глубина деревьев: 5. Селекция: ранговая. Вероятность мутации: 0.01.

Найдено решение: .

Ошибка (квадратичный критерий): 2.28.

Поколение: 1000.

3. Функция: . Выборка: случайная, объем - 100 точек.

Терминальное множество: , где .

Функциональное множество: .

Размер популяции: 100. Глубина деревьев: 5. Селекция: ранговая. Вероятность мутации: 0.01.

Найдено решение: .

Ошибка (квадратичный критерий): 1.15.

Поколение: 180.

2.4 Выводы

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

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

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

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

Глава III. Практическая реализация разработанных алгоритмов

3.1 Программная реализация обыкновенного и вероятностного генетического алгоритмов

На основе рассмотренного в п. 1.2. стандартного ГА и предложенного ВГА разработаны программные системы: «GA lab» и «ProbGA lab».

В качестве рабочей операционной системы (ОС) был выбрана Microsoft Windows, поскольку она является наиболее распространенной ОС, 32 битные приложения одинаково эффективно работают в различных версиях Windows: 9x, ME, 2000, NT, XP, ОС Windows обладает удобным и очень гибким интерфейсом [32].

В качестве среды программирования был выбран Borland C++ Builder, т.к. он обладает следующими свойствами:

- Язык C++ объектно-ориентированный, обеспечивает наследование, полиморфизм, абстракцию данных.

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

- Инкрементальный линкер осуществляет быструю и надежную сборку приложений в формате ЕХЕ файлов сравнительно меньшего размера [2, 31].

- Чистый и доступный код приложений, которые C++ Builder строит на основе предоставляемых разработчику компонентных свойств, событий и методов, исключает скрытые и трудные в отладке макросы.

- Создание DLL, LIB, и ЕХЕ файлов предоставляет свободу выбора формата целевого приложения в соответствии с требованиями конкретного проекта.

- Прямое обращение к системным функциям Windows 9x и NT дает возможность программистам, работающим в среде C++ Builder при необходимости воспользоваться всеми возможностями современных операционных систем [33].

3.1.1 Программная система «GA lab»

Программная система «GA lab», реализует работу стандартного ГА с возможностью выбора различных параметров алгоритма. В качестве тестовых задач использованы функции, описанные в п.1.1. (см. приложение 1).

Приложение имеет следующие опции:

- Выбор одинарного прогона или набора статистики;

- Стандартное бинарное кодирование или рефлексивный код Грея с возможностью выбора точности кодирования (шага дискретизации);

- Вероятность мутации: высокая, равномерная, низкая или отсутствует;

- Селекция: турнирная, пропорциональная или ранговая;

- 15 тестовых задач;

- Визуализация изменения пригодности: средней по популяции, лучшего и худшего индивидов;

Приложение разработано в среде визуального программирования Borland Builder C++ 5.0. Системные требования: IBM PC Pentium совместимый, 1Мб дискового пространства, 32 Мб ОЗУ, ОС Windows 9x, Me, 2000, NT, XP.

Работа начинается с окна выбора режима работы: одинарный прогон ГА или набор статистики (рис. 19). В обоих режимах предоставляется одинаковый выбор параметров за исключением выбора количества прогонов в режиме статистики.



Рис. 19. Стартовый диалог в приложении «GA lab».

Далее появляется окно, содержащее настройки алгоритма, органы управления и слежения за динамикой алгоритма (рис. 20).

Рис. 20. Главное окно приложения «GA lab».

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

3.1.2 Программная система «ProbGA lab»

Программная система «ProbGA lab» реализует работу вероятностного ГА с возможностью выбора различных параметров алгоритма. В качестве тестовых задач использованы функции, представленные в приложении 1.

Приложение имеет следующие опции:

- Выбор одинарного прогона или набора статистики;

- Стандартное бинарное кодирование или рефлексивный код Грея с возможностью выбора точности кодирования (шага дискретизации);

- Вероятность мутации: высокая, равномерная, низкая или отсутствует;

- Тип мутации: новая популяция, старая популяция или обе популяции;

- Селекция: пропорциональная, элитарная, ранговая или турнирная с выбором размера турнира;

- Схема формирования новой популяции: из объединения новой и старой, 50% из новой и 50% из старой;

- 15 тестовых задач;

- Слежение за динамикой алгоритма: размерность бинарного вектора, текущий вектор вероятностей, текущее лучшее решение.

Приложение разработано в среде визуального программирования Borland Builder C++ 5.0. Системные требования: IBM PC Pentium совместимый, 1Мб дискового пространства, 32 Мб ОЗУ, ОС Windows 9x, Me, 2000, NT, XP.

Работа приложения начинается с окна выбора режима работы: одинарный прогон или набор статистики (рис. 21):



Рис. 21. Стартовый диалог в приложении «ProbGA lab».

Главное окно приложения содержит настройки алгоритма, органы управления и слежения за динамикой алгоритма (рис. 22).

Рис. 22. Главное окно приложения «ProbGA lab».

После завершения одинарного прогона в поле «Результат» выводится лучшее решение, значение выбранной функции в этой точке и номер итерации, когда было найдено решение (рис. 23). В режиме набора статистики после выполнения заданного числа прогонов выводится оценка надежности и среднего числа итерации.



Рис. 23. Вывод результатов в приложении «ProbGA lab».

3.2 Программная реализация методов обыкновенного и вероятностного генетического программирования

Рабочим языком программирования был выбран Borland C++, поскольку он предоставляет возможности гибкого объектно-ориентированного программирования, а также является мощнейшим инструментом для реализации программ под Win32.

Для представления деревьев решений в памяти компьютера был выбран связанный список классов, описывающих вершины дерева (рис. 24):

Рис. 24. Пример представления дерева в памяти компьютера.

3.2.1 Программная система «GP: Symbolic Regression»

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

Приложение разработано в среде визуального программирования Borland Builder C++ 5.0. Системные требования: IBM PC Pentium совместимый, 1Мб дискового пространства, 32 Мб ОЗУ, ОС Windows 9x, Me, 2000, NT, XP Среднее время вычислений (зависит от сложности структур деревьев, от размера популяции и объема выборки): до 100 поколений в минуту.

Ниже представлено главное окно приложения:

Рис. 25. Рабочее окно приложения «GP: Symbolic Regression».

Меню 1 состоит из элементов File , Options, Help. При входе в меню Options появляется окно настроек (рис. 26), в котором задается размер популяции, максимальная начальная глубина деревьев, метод выращивания, вероятность мутации, тип селекции и параметры. При выборе пункта Help появляется окно с информацией о данном программном продукте (рис. 27).

Рис. 26. Окно настроек.

Рис. 27. Окно Help.

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

Текущие настройки параметров алгоритма 3 отражают текущие настройки (также сохраняются в файле «GP.ini»).

Кнопки управления работой приложения 4 включают Start, Stop, Exit.

Параметры, контролирующие работу алгоритма 5, включают номер текущего поколения, сложность лучшего решения и его ошибку.

При достижении заданной точности (по умолчанию равной 0.001) программа выдает сообщение (рис. 28) и продолжает работу. При равенстве ошибки нулю во всех точках выборки программа выдает сообщение в окне 2 и прекращает работу.

Рис. 28. Сообщение

По окончании работы алгоритма, программа создает (либо переписывает) файлы «Fitness.dat», содержащий изменение значений функции пригодности и «GentnBest.dat», содержащий решения последнего поколения и их пригодности.

3.2.2 Программная система «ProbGP: Symbolic Regression»

Программная система «ProbGP: Symbolic Regression» реализует работу алгоритма решения задачи символьной регрессии с использованием метода вероятностного ГП.

Приложение разработано в среде визуального программирования Borland Builder C++ 5.0. Системные требования: IBM PC Pentium совместимый, 1Мб дискового пространства, 32 Мб ОЗУ, ОС Windows 9x, Me, 2000, NT, XP.

Главное окно приложения показано на рис. 29:



Рис. 29. Главное окно приложения «ProbGP: Symbolic Regression».

В окне отображаются: лучшее решение на текущей итерации (рис. 30), график найденного решения для функции одной переменной (рис. 31) и график изменения пригодности (рис. 32).

Рис. 30. Просмотр текущего лучшего решения.



Рис. 31. График лучшего решения.

Рис. 32. График изменения пригодности.

В меню настроек алгоритма (рис. 33) имеется возможность выбора следующих параметров:

- Размер популяции;

- Глубина полного дерева;

- Схема селекции: ранговая, пропорциональная, элитарная, турнирная с выбором размера турнира;

- Вероятность мутации: низкая, равномерная, высокая или задается в ручную;

- Схема мутации: новая, старая или новая и старая популяции;

- Схема формирования новой популяции: селекция по объединению новой и старой популяции, 50% из старой и 50% из новой;

- Стандартное бинарное кодирование или код Грея;

- Критерий остановки: вручную, заданное число итераций.



Рис. 33. Окно настроек алгоритма.

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

- Арифметические операции: сложение, вычитание, умножение и защищенное деление (возвращает 1, если знаменатель равен нулю);

- Математические функции: , , (модуль), , , ;

- Переменные: , константы: 0.1, 0.2, …, 0.9, 1.0;

- Предопределенные функции: функция, обнуляющая поддерево, вершиной которого она является.

Рис. 34. Окно выбора функций и термов.

3.3 Постановка задачи оптимизации работы электростанции на топливных элементах в стационарном режиме

Эффект Fuel Cell (топливный элемент) был открыт в 1839 году Уильямом Грувом. Топливные элементы относятся к химическим источникам тока. Они осуществляют прямое превращение энергии топлива в электричество, минуя малоэффективные, идущие с большими потерями, процессы горения. Это электрохимическое устройство в результате высокоэффективного окисления топлива непосредственно вырабатывает электроэнергию.

Топливные элементы являются наиболее перспективным источником электрической энергии. Их преимущества:

- Топливные элементы имеют высокий КПД при очень низких температурах, достигающий 80% (у обычных энергоустановок - 35%);

- Цена одного киловатта энергии, вырабатываемой одним топливным элементом, ниже, чем у его конкурентов;

- Энергия вырабатывается непрерывно при наличии в элементе топлива (в отличие от аккумуляторов, которые требуют периодической замены электролита);

- Топливный элемент и продукты его работы экологически чисты;

- Топливный элемент работает бесшумно;

- Топливный элемент практически “всеяден”, т.е. в качестве топлива может использоваться практически любое водородосодержащее топливо;

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

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

3.3.1 Водородные топливные элементы - основные принципы

Конструктивно топливный элемент состоит из двух электродов - анода и катода - и разделяющего их электролита (рис. 35). На аноде окисляется, т.е. отдает электроны, восстановитель (топливо или ), свободные электроны с анода поступают во внешнюю цепь, а положительные ионы удерживаются на границе анод-электролит (,). С другого конца цепи электроны подходят к катоду, на котором идет реакция восстановления (присоединение электронов окислителем ). Затем ионы окислителя переносятся электролитом к катоду (рис. 36) [55].

Рис. 35. Простейшая конструкция топливного элемента.



Рис. 36. Схема реакций в топливном элементе.

Для повышения выходного напряжения топливные элементы объединяются в группы - стеки (рис. 37).

Рис. 37. Пример объединения 3х топливных элементов.

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

Таблица 4. Основные типы топливных элементов.

Тип топливного элемента	Мобильный ион	Рабочая температура	Область применения
Щелочной (AFC)		50-200	Аэрокосмическая техника (Аполлон, Шаттл).
Протон-содержащая мембрана (PEMFC)		30-100	Транспортные средства и мобильные установки, а также маломощные электростанции.
Чистый метанол (DMFC)		20-90	Портативные электронные системы с низким потреблением энергии, работающие длительное время.
Фосфорная кислота (PAFC)		~220	~200 кВт электростанции.
Жидкий диоксид углерода (MCFC)		~650	Среднемощные и большие электростанции до МВт.
Твердая окись		500-1000	Электростанции любых масштабов от 2кВт до нескольких МВт.

Рис. 38. Преимущества и области применения различных типов топливных элементов.

3.3.2 Теплоэлектростанции на топливных элементах

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

Основной объект данного исследования - малогабаритная ТЭЦ на топливных элементах для бытового энергообеспечения, исследуемая в институте прикладных исследований при Высшей технической школе города Ульм (рис. 39). ТЭЦ имеет типичную для PEMFC (топливо - природный газ) структуру, основные элементы которой представлены на рисунке 40.

Рис. 39. Малогабаритная ТЭЦ исследуемая в высшей технической школе г. Ульм.

Рис. 40. Основные элементы ТЭЦ.

Вода и пригодный газ поступают в преобразователь (реформер), где образуется водород и одноокись углерода. Далее часть одноокиси углерода преобразуется в двуокись в реакторе высокой температуры (HT shift, 260-320), оставшаяся часть - в реакторе низкой температуры (LT shift, 200-260). Далее газ поступает в реактор-окислитель (PROX - Preferential Oxidation Reactor), увлажняется и подается в топливные элементы (в исследуемой ТЭЦ - 40 ячеек, ~5кВт). Отработавший газ сжигается. Вырабатываемое электричество через преобразователь поступает в электрическую сеть [42, 46].

3.3.3 Математическая модель электростанции на топливных элементах

Ранее для исследуемой электростанции была построена математическая модель, основанная на физико-химической теории процессов, протекающих в топливных элементах, и экспериментальных статистических данных о функционировании подсистем объекта [47]. Библиотека компонентов модели содержит все элементы ТЭЦ. Модель реализует практически все возможные режимы функционирования станции, а также содержит применяемую на электростанции систему управления. Модель была реализована в среде MatLab Simulink (рис. 41). Параметры системы управления и подсистем ТЭЦ выбраны в соответствии с техническими ограничениями.

Рис. 41. Структура Simulink - модели ТЭЦ.

3.3.4 Постановка задачи оптимизации

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

Математически критерий оптимальности выглядит следующим образом:

.

, где - полученная электроэнергия, - суммарное потребление энергии для обеспечения нормального функционирования ТЭЦ.

- подводимая к системе энергия пропорциональная количеству используемого топлива, где - константа, связанная с физикой процесса (теплота сгорания), - интенсивность расхода природного газа. Т.о. критерий оптимальности имеет вид:

.

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

Сложность задачи оптимизации состоит в следующем: априорная информация о пространстве поиска в явном виде отсутствует (является ли функционал непрерывным, выпуклым, квадратичным), зависимость выходных переменных от входных сложная и нелинейная. Возможна многоэкстремальность. Получение оценок производных затруднено. Существуют значения параметров (области в пространстве поиска), где функционал не определен - объект не выходит на стационарный режим работы. Очевидно, что использование стохастических методов прямого поиска в данной задаче более предпочтительно, чем использование классических методов оптимизации. Будем использовать ВГА, предложенный в п. 1.4.

Для взаимодействия с Simulink-моделью, ВГА был реализован на языке программирования Matlab.

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

Для слежения за динамикой работы ВГА изменение пригодности лучшего и среднего по популяции решения выводятся на экран.

Поскольку ГА являются эвристическими методами случайного поиска, строгой теории позволяющей оптимально выбирать параметры алгоритма, нет. Однако многолетний опыт использования ГА дает нам следующие практические советы [41, 57]:

- Соотношение размер популяции - число итераций должно быть примерно равным. Соотношения 100-10 или 10-100 хуже, чем 25-40 или 40-25.

- Следует использовать высокую мутацию, чтобы избежать захвата локальными оптимумами.

- Следует использовать ранговую или турнирную селекцию, чтобы избежать стагнации.

Были выбраны следующие параметры ВГА:

- Число переменных задачи - 12.

- Интервалы изменения переменных: [0.034,0.3; 3.7,10; 17,50; 1123,1223; 1.2,2; 323,343; 473,723; 413,513; 1.3,4; 0.1,1; 0.1,2.5; 0.1,2.5].

- Точность поиска: [0.01; 0.1; 3; 10; 0.1; 1; 10; 10; 0.1; 0.1; 0.1; 0.1].

- Размерность задачи после бинаризации - 55.

- Размер популяции - 25.

- Селекция - турнирная (размер равен 2).

- Мутация - высокая.

Ниже представлен график изменения пригодности (значения критерия оптимальности) для лучшего решения - сплошная линия и среднего значения по популяции - пунктирная (рис. 42).



Рис. 42. График изменения пригодности.

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

Полученный набор параметров дает значение электрической производительности равное 11.5%. Значение производительности, полученное для известных параметров используемых на исследуемой ТЭЦ - 5.5%. Следовательно, полученное решение позволяет повысить эффективность (на модели) в 2 раза.

3.4.1 Исследование устойчивости решения

Поскольку найденное решение должно быть реализовано на реальной ТЭЦ, необходимо проверить является ли решение устойчивым. Т.е. определить, как меняется значение электрической производительности, при отклонении параметров от оптимального значения.

Каждый параметр варьировался в пределах 20% от его значения при фиксированных значениях остальных параметров. Следующие графики показывают изменения значения критерия (рис. 43 - 54) :



Рис. 43. Расход воздуха в топливном элементе. BZ_np_Luft=0.12839. Допустимый интервал: [0.034, 0.3]. Точность: 0.01.

Рис. 44. Расход воды на реформере газа. PM2_Qsoll =7.3e-07. Допустимый интервал:[3.7e-07, 10e-07]. Точность: 0.1.



Рис. 45. Расход природного газа. Verdichter_f =22. Допустимый интервал: [17, 50]. Точность: 2.2.

Рис. 46. Температура в реформере. T_Ref_Br_soll =1223. Допустимый интервал: [1123, 1223]. Точность: 6,67.



Рис. 47. Давление в топливном элементе. BZ_p_soll =1.4286. Допустимый интервал: [1.2, 2]. Точность = 0.1.

Рис. 48. Температура воды в топливном элементе. st_Tsoll_BZ_Wasser=323. Допустимый интервал: [323, 343]. Точность: 0.65.



Рис. 49. Температура высокотемпературного реактора. st_Tsoll_HT_Kuehlung =522. Допустимый интервал: [473, 723]. Точность: 8.1.

Рис. 50. Температура низкотемпературного реактора. st_Tsoll_NT_Kuehlung=420. Допустимый интервал: [413, 513]. Точность: 6.67.



Рис. 51. Давление газа в реформере. V23.psoll=2.9548. Допустимый интервал: [1.3, 4]. Точность: 0.08.

Рис. 52. Отношение количества воздуха подводимого до/после блока PROX. X_luft=0.16. Допустимый интервал: [0, 1]. Точность: 0.06.



Рис. 53. Расход воды в увлажнителе (блок 1). Bef_A.Q_ein=0.87419e-05. Допустимый интервал: [0, 2.5e-05]. Точность: 0.078.

Рис. 54. Расход воды в увлажнителе (блок 2). Bef_K.Q_ein=1.2613e-05. Допустимый интервал: [0, 2.5e-05]. Точность: 0.078.

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

Из графиков видно, что найденное решение может быть улучшено. После запуска алгоритма покоординатного спуска из найденной точки, было найдено решение, дающее значение производительности - 11.9%.

Найденный с помощью ВГА набор параметров был реализован на реальной ТЭЦ, исследуемой в институте прикладных исследований Высшей Технической школы г. Ульм, Германия. Полученное значение электрической производительности оказалось меньше полученного на модели (предположительно из-за некачественных топливных элементов, используемых на ТЭЦ), но существенно больше, чем значение производительности при ранее известных параметрах.