Разработка и исследование вероятностных эволюционных алгоритмов для моделирования и оптимизации сложных систем
Диссертация - Менеджмент
Другие диссертации по предмету Менеджмент
Сложность дерева (число вершин): 7.
.Функция Растригина: . Выборка: случайная, объем - 4000 точек.
Терминальное множество: , где .
Функциональное множество: .
Размер популяции: 100. Метод роста: полный. Начальная глубина деревьев: 6. Селекция: ранговая. Вероятность мутации: 0.05.
Найдено точное решение: .
Поколение: 178.
Сложность дерева (число вершин): 13.
.Функция: . Выборка: случайная, объем - 2000 точек.
Терминальное множество: , где .
Функциональное множество: .
Размер популяции: 100. Метод роста: полный. Начальная глубина деревьев: 5. Селекция: ранговая. Вероятность мутации: 0.01.
Найдено точное решение:
.
Поколение: 72.
Сложность дерева (число вершин): 18.
.Функция: . Выборка: случайная, объем - 3000 точек.
Терминальное множество: , где .
Функциональное множество: .
Размер популяции: 100. Метод роста: полный. Начальная глубина деревьев: 7. Селекция: ранговая. Вероятность мутации: 0.001.
Найдено решение:
.
Поколение: 42.
Сложность дерева (число вершин): 43.
Ошибка аппроксимации (квадратичный критерий): 0.036.
.Функция: . Выборка: случайная, объем - 5000 точек.
Терминальное множество: , где .
Функциональное множество: .
Размер популяции: 100. Метод роста: полный. Начальная глубина деревьев: 7. Селекция: ранговая. Вероятность мутации: 0.001.
Найдено точное решение:
.
Поколение: 26.
Сложность дерева (число вершин): 21.
.Функция Растригина: . Выборка: случайная, объем - 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.Запустить метод ГП.
.Если в результате длительно?/p>