Разработка и исследование вероятностных эволюционных алгоритмов для моделирования и оптимизации сложных систем
Диссертация - Менеджмент
Другие диссертации по предмету Менеджмент
?етического программирования, где допустимое решение может быть найдено экстенсивным использованием оператора мутации [37].
Существует две схемы применения оператора мутации в генетическом программировании.
При использовании первой схемы (точечная мутация), случайно выбранный узел в дереве меняется на случайно выбранный элемент того же типа. Т.е. выбранный ген заменяется случайно выбранным элементом терминального множества, если этот ген принадлежит терминальному множеству, или элементом функционального, если ген - элемент функционального множества (рис. 11).
Рис. 11. Пример мутации по схеме 1
При использовании второй схемы, выбранное поддерево заменяется поддеревом, выращенным методом роста, новое поддерево имеет глубину не больше, чем глубина выбранного поддерева (рис. 12).
Рис. 12. Пример мутации по схеме 2
программный оптимизация генетический символьный регрессия
2.2.3Решение задачи символьной регрессии с помощью метода генетического программирования
Для решения задачи символьной регрессии с помощью генетического программирования необходимо выполнить следующие подготовительные шаги, а именно определить:
.терминальное множество,
.функциональное множество,
.функцию пригодности,
.параметры, контролирующие работу алгоритма,
.критерий остановки.
Первый этап определяет множество термов, из которых будет строиться решение. В задаче символьной регрессии терминальное множество содержит набор переменных (где - размерность поставленной задачи) и набор констант, т.е.
.
На втором этапе пользователь метода должен определить множество функций, которые будут использованы для построения решений. Пользователь должен априори предполагать некоторую комбинацию функций, которые могли бы содержаться в решении задачи. Функциональное множество может содержать:
арифметические операции (),
математические функции (и т.д.),
булевы операции (),
специальные предопределенные функции (Automatically Defined Functions - ADFs).
Необходимо помнить, что заданное универсальное множество должно удовлетворять условию замкнутости. Например, для исключения деления на нуль вводят защищенное деление, которое возвращает единицу, когда знаменатель равен нулю.
Третий этап - определить функцию пригодности, вычисляемую по заданной обучающей выборке. Для решения задачи символьной регрессии предложена следующая функция пригодности (7)
(7)
где - пригодность решения , - квадратичная ошибка аппроксимации, вычисляемая по всем точкам обучающей выборки, - объем обучающей выборки, - значение полученного выражения в точке , - некоторый штраф на сложность дерева, выраженный в суммарном количестве вершин.
Параметры, контролирующие работу алгоритма обычно включают:
-размер популяции,
-метод роста,
максимальную начальную глубину деревьев,
метод селекции и его параметры (например, размер турнира для турнирной селекции),
вероятность и тип мутации.
В качестве критерия остановки работы алгоритма можно выбрать один из следующих:
-достигнуто заданное число поколений (итераций),
-достигнута заданная точность аппроксимации,
относительное изменение средней пригодности не превышает заданной величины.
Общая схема алгоритма для решения поставленной задачи следующая:
1.Инициализировать популяцию случайным образом одним из методов роста.
.Оценить популяцию, используя критерий (7).
.Если выполняется критерий остановки, то КОНЕЦ, иначе шаг 4.
.На итерации произвести селекцию одним из предложенных методов для поколения .
.Отобранные особи скрещиваются, подвергаются мутации и оцениваются - создают промежуточную популяцию.
.В поколение попадает часть особей из популяции и часть из промежуточной популяции.
.Переход к шагу 2.
2.2.4Исследование работоспособности на тестовых задачах
На основе полученного алгоритма созданы библиотека для реализации метода генетического программирования и программная система, решающая задачу символьной регрессии. Проверена работа алгоритма на тестовых функциях одной и нескольких переменных. При соблюдении условия достаточности на ранних поколениях найдены точные решения. При несоблюдении - аппроксимации, заданной точности.
1.Функция: , . Выборка: случайная, объем - 200 точек. Условие достаточности не выполняется, т.е. функциональное множество не содержит тригонометрических функций.
Терминальное множество: , где .
Функциональное множество: .
Размер популяции: 100. Метод роста: полный. Начальная глубина деревьев: 9. Селекция: ранговая. Вероятность мутации: 0.001.
Идеальным решением было бы выражение, соответствующее разложению функции в ряд. Для отрезка разложение выглядит следующим образом
Найденное выражение:
.
Поколение: 3050.
Сложность дерева (число вершин): 197.
Ошибка аппроксимации (квадратичный критерий): 0.00505.
После упрощения полученного выражения получим:
Т.о. алгоритм смог восстановить первых 2 члена с точностью до знака и коэффициента.
.Функция: . Выборка: случайная, объем - 2000 точек.
Терминальное множество: , где .
Функциональное множество: .
Размер популяции: 100. Метод роста: полный. Начальная глубина деревьев: 6. Селекция: ранговая. Вероятность мутации: 0.001.
Найдено точное решение: .
Поколение: 13.