Назначение и общее описание
Программа моделирует выход относительно входа, используя и подбирая для этого аналитические формулы. Для обучения применяется комплексный подход: сами формулы подбираются с использованием генетического алгоритма, при этом значения параметров подбираются с помощью оптимизатора (градиентный спуск).
Например, есть формула: w[0] * sin(x[0]) + w[1].
Этой формуле соответствует дерево:
В ходе обучения узлы дерева меняются/добавляются новые, а весовые коэффициенты (в этом примере w[0] и w[1]) подбираются оптимальным образом.
Характеристика и структура программы:
-
Для нахождения формул используется генетический алгоритм (набор особей).
-
Каждая особь – это дерево вычислений для соответствующей аналитической формулы. Т.е. дерево м.б. представлено аналитической формулой и наоборот.
-
Дерево состоит из вершин. Каждая вершина хранит информацию: о связях с другими вершинами, вычисляемой операции (функции), индексе данных и типе вершины. Типы вершин могут быть следующими:
-
[o = ] Операция (вычисляемая функция)
-
[x = ] Значение входного вектора
-
[w = ] Значение веса
-
[c = ] Константа.
-
-
Операции дерева подбираются с помощью генетических операторов.
-
Веса дерева обучаются с помощью оптимизатора scipy.optimize.
-
Константы дерева не могут быть обучены, но могут подбираться из установленного списка значений генетическим алгоритмом.
-
Для дерева можно использовать типовой набор операций: сложение, вычитание, умножение, деление, синус (sin), косинус (cos), тангенс (tanh), арктангенс (arctg), кардинальный синус (sinc), функция Гаусса. Этот набор можно расширить своими (пользовательскими) операциями.
-
У операции предусмотрено использование любого количества аргументов. У каждой операции количество аргументов необходимо указывать явно. Особо выделены следующие типы операций:
-
1 аргумент – унарные операции (функции, например, тангенс)
-
2 аргумента – бинарные операции (например, арифметические операции)
-
3 аргумента – тернарные операции (например, операции сравнения)
-
-
По умолчанию предусмотрен следующий список констант: -1, 0, 1, 1.41421356237 (
), 2, 2.7182818284 ([e]), 3, 3.1415926535 (π). Можно использовать свой (пользовательский) набор констант, но в них в обязательном порядке д.б. следующие значения (опорный вектор значений): 0, 1, 2, -1.
Генетический алгоритм
Процедура (метод FormulaPopulation.recombine):
-
Подсчитать ранг и сортировать всех особей по рангу
-
Исключить более низкий процент особей из племенного пула
-
Передать верхний процент особей в дочернюю популяцию без изменений
-
Выбор особей турнирным методом
-
Создание новой популяции через кроссовер и мутацию.
Метрики оценки популяции
Для оценки популяции используются следующие метрики:
-
Сложность (complexity_target) – вычисляется на основе сложности операций, составляющих дерево вычислений.
-
Средняя среднеквадратичная оценка MSE (ftarget) = min(MSE)
-
Минимальная среднеквадратичная оценка MSE (ftarget_min) = mean(MSE)
Затем в популяции проводится ранжирование по доминированию Парето. Выбор пар метрик вероятностно регулируется параметром FormulaPopulation.alg_probMoo (=0,8):
-
Тип: mean-complexity. Средняя среднеквадратичная оценка – Сложность. Выбирается с вероятностью alg_probMoo.
-
Тип: mean-min. Средняя среднеквадратичная оценка – Минимальная среднеквадратичная оценка. Выбирается с вероятностью (1 - alg_probMoo).
Правила сокращения
Опционально при подборе формулы можно использовать сокращение размера дерева вычислений. Для сокращения размера формул (reduction) используются следующие правила:
-
Сложение одинаковых весов, констант, входных переменных: x + x → 2 * x
-
Вычитание одинаковых весов, констант, входных переменных: x - x → 0
-
Деление одинаковых весов, констант, входных переменных: x / x → 1
-
Сложение с нулём: x + 0 → x
-
Вычитание из нуля: 0 - x → -1 * x
-
Вычитание нуля: x - 0 → x
-
Умножение на единицу: 1 * x → x
-
Деление на единицу: x / 1 → x
Конвертация и строковое представление
Дерево вычислений м.б. преобразовано в строку несколькими способами:
-
Преобразование дерева в строку с заменой констант на числа (to_strw)
-
Преобразование дерева в строку с заменой весов и констант на числа (to_str).
Пример использования
Код для обучения популяции на входных данных inp, чтобы смоделировать выходные данные targ. 100 итераций эволюционного алгоритма, в каждой итерации используется оптимизация весов (20 итераций). В конце применяется оптимизация весов – 100 итераций.
import numpy as np
my_prob = np.ones(len(FUNC_OPERATIONS), dtype=int)
fp = FormulaPopulation(input_num=1, weights_num=2, my_func=FUNC_OPERATIONS, my_prob=my_prob)
fp.start_popul(30)
fp.runfit(inp, targ, iterfit=20, iter=100)
fp.runfit(inp, targ, iterfit=100)
Код для предсказания значений популяцией.
pred = fp.predict(inp)
Классы и методы
FormulaVertex - Класс вершины дерева операций. Хранит информацию: о связях с другими вершинами, вычисляемой функции, индексе данных и типе вершины.
Аргументы класса:
-
func - (function) - Вычисляемая функция.
-
typeval - (Str) - Тип вершины:
-
x - значение входного вектора
-
w - значение веса
-
с - константное значение
-
o - выполнение операции.
-
-
indexval - (int) - Индекс значения: либо входного вектора, либо вектора весов, либо вектора констант.
-
rel1, rel2, rel3 - (FormulaVertex) - Связи с другими вершинами.
Методы класса:
-
del_relations - Удалить связи
-
add_relation - Вставить новую связь
-
add - Добавить связь в конец
-
vertex_index - Найти смежную вершину
-
update_relation_num - Обновить используемое количество связей
-
calc - Расчёт дерева операций
-
complexity - Вычисление сложности дерева операций
-
update_oper - Обновление индекса операций
-
update_connect - Обновление индекса связей
-
get_ids - Вернуть ID
-
reduction_req - Рекурсивное сокращение операций
-
reduction - Сокращение операций
-
set_func - Установить функцию
-
del_vertex - Удалить текущую вершину
-
set_const - Установить константу
-
eq_two - Проверка на одинаковые значения бинарных операций
-
eq_const - Проверка значения константы
-
str_one - Преобразование унарных (и префиксных) операций в строку
-
str_two - Преобразование бинарной операции в строку
-
str_three - Преобразование тернарной операции в строку
-
str_vertex - Вывод только текущей вершины
FormulaTree - Дерево операций, состоящие из вершин FormulaVertex.
Аргументы класса:
-
base - (FormulaVertex) - Корень дерева.
-
weights - (ndarray) - Вектор весов.
-
weights_num - (int) - Если вектор весов не задан, инициализирует нулевой вектор весов.
-
input_num - (int) - Количество входов.
-
constants - (list) - Список констант. Если не задан, по умолчанию берутся константы CONSTANTS_OPERATIONS.
Методы класса:
-
get_rand_weight (staticmethod) - Вернуть случайный вес от -2 до +2
-
set_data - Задать данные для расчётов
-
init_weight - Инициализация дерева одним общим весом
-
init_weights - Инициализация весов дерева
-
predict - Расчёт дерева операций
-
targetfun - Целевая функция
-
targetfun_opt - Целевая функция для оптимизации
-
target_mse - Метрика MSE
-
target_rmse - Метрика RMSE
-
complexity - Вычисление сложности дерева операций
-
total_target - Целевая функция, учитывающая сложность
-
fit - Обучение весов дерева
-
update_oper - Обновление индекса операций
-
update_connect - Обновление индекса связей
-
update_index - Обновление всех индексов
-
clear_index - Очистить индекс
-
check_index - Проверка индексов
-
get_ids - Массив идентификаторов
-
reduction - Сокращение операций
-
to_str_oper - Вывод индексов операций
-
to_str_connect - Вывод индексов соединений
-
to_strw - Преобразование дерева в строку
-
to_str - Преобразование дерева в строку с заменой весов на числа
FormulaTreePopul - Дерево-особь для использования в генетическом алгоритме. Наследует класс FormulaTree.
Аргументы класса:
-
my_func - (list) - Список допустимых функций.
-
my_args - (list) - Количество аргументов у соответствующих функций.
-
my_prob - (list) - Задаёт важность использования соответствующих функций (в условных единицах).
-
input_num - (int) - Количество входов.
-
weights_num - (int) - Задаёт вектор весов.
-
constants - (list) - Список констант. Если не задан, по умолчанию берутся константы CONSTANTS_OPERATIONS.
Методы класса:
-
init_popul - Инициализация дерева
-
start_popul - Создание стартовой популяции
-
rand_func - Случайная функция из предложенного массива
-
rand_change_oper - Изменение случайной операции дерева
-
new_relation - Создание новой связи
-
new_vertex - Новая вершина
-
add_vertex - Добавление новой вершины в дерево
-
rand_add_vertex - Добавление случайной вершины
FormulaPopulation- Популяция особей: оптимизация весов, генетический алгоритм, обучение и предсказание.
Аргументы класса:
-
input_num - (int) - Количество входов.
-
weights_num - (int) - Задаёт вектор весов.
-
constants - (list) - Список констант. Если не задан, по умолчанию берутся константы CONSTANTS_OPERATIONS.
-
my_func - (list) - Список допустимых функций. Если не задан, по умолчанию берутся функции FUNC_OPERATIONS.
-
my_prob - (list) - Задаёт важность использования соответствующих функций (в условных единицах). Если не задан, по умолчанию важность одинакова (1/len(my_func)).
-
weights_popul - (int) - Количество испытаний, проведённых с одной особью.
-
prob_func - (float) - Вероятность изменения операции дерева в особи.
-
prob_vertex - (float) - Вероятность добавления новой вершины в особь.
-
prob_crossover - (float) - Вероятность применения кроссовера к особи.
-
cull_ratio - (float) - Отбор - устранение худших особей из племенного пула.
-
elite_ratio - (float) - Элитарность - сохранить лучших особей без изменений.
-
alg_probMoo - (float) - Методика ранжирования по Парето: mean-complexity или mean-min.
-
prob_reduction - (float) - Вероятность сокращения операций в особи.
-
lmd - (float) - Коэффициент общей целевой функции.
Методы класса:
-
init_popul - Инициализация популяции
-
start_popul - Создание стартовой популяции
-
start_popul_func - Создание стартовой популяции по функции
-
check_index - Проверка индексов
-
crossover (staticmethod) - Кроссовер
-
multi_targetfun - Оценка популяции по разным весам
-
targetfit - Обучение популяции
-
probMoo - Ранжирование
-
rank_sort - Сортировка всех особей по рангу
-
tournament - Выбор особей турнирным метогдом
-
cull_elite - Исключение низших особей и передача высших без изменений
-
recombine - Следующее поколение особей
-
reduction - Сокращение операций
-
ask - Этап эволюции особей
-
askfit - Этап эволюции особей
-
sort - Последнее ранжирование популяции
-
run - Запуск оптимизации
-
runfit - Запуск оптимизации
-
fit - Обучение весов дерева
-
predict - Предсказание
-
support - Нахождение опорных значений
-
get_weights - Все веса популяции
-
print_iter - Информация про выполнение итерации
-
check_set - Проверка пересечений
-
to_str - Преобразование популяции в строку с заменой весов на числа
Доступные по умолчанию функции дерева операций
-
fsum - Сложение
-
fsub - Вычитание
-
fmul - Умножение
-
fdev - Деление
-
fsin - Синус
-
fcos - Косинус
-
ftanh - Тангенс
-
farctan - Арктангенс
-
fsinc - Кардинальный синус
-
fgauss - Функция Гаусса
Глобальные константы
-
FUNC_OPERATIONS - Список используемых по умолчанию операций дерева (все функции)
-
ARGS_OPERATIONS - Количество аргументов для соответствующих операций
-
STR_OPERATIONS - Строковое обозначение для соответствующих операций
-
COMPL_OPERATIONS - Значение сложности для соответствующих операций
-
TWO_OPERATIONS - Бинарные операции
-
THREE_OPERATIONS - Тернарные операции
-
CONSTANTS_OPERATIONS - Список используемых по умолчанию констант.