Материал: ММвСС. Экзаменационные вопросы и ответы

50. Оптимизация функции нескольких переменных. Невыпуклые функции. Эволюционный метод (генетический алгоритм).

Стохастические методы.

Целью разработки и использования данных методов является оптимизация невыпуклых функций.

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

Оптимизацию невыпуклых функций называют многоэкстремальной оптимизацией. Примеры методов оптимизации:

•Слепой случайный поиск: поиск экстремума в заданной области путем проб в случайных точках области;

•Локальный случайный поиск: поиск экстремума в заданной области путем проб в случайных точках, сосредоточенных вокруг некоторой базисной точки с последующим переходом к другой базисной точке;

•Мультистартовый метод: многократный запуск метода поиска экстремума выпуклой функции из различных стартовых точек;

•Эволюционный метод (генетический алгоритм): метод имитирующий процесс эволюции, происходящий в

живой природе.

Генетический алгоритм (англ. genetic algorithm) — это стохастический эвристический алгоритм поиска, используемый для решения задач оптимизации и моделирования путём последовательного подбора, комбинирования и вариации искомых параметров с использованием механизмов, напоминающих биологическую эволюцию. Является разновидностью эволюционных вычислений (англ. evolutionary computation). Отличительной особенностью генетического алгоритма является акцент на использование оператора «скрещивания», который производит операцию рекомбинации решений-кандидатов, роль которой аналогична роли скрещивания в живой природе.

Предполагает имитацию процесса эволюции (различные реализации могут использовать различные приемы имитирующие этапы эволюционного процесса). Например:

•Значения переменных (точка) – особь.

•Значение функции в точке характеризует приспособленность особи (выживаемость).

Пусть задана выпуклая функция переменных ( ) = (1, 2, … , ).

Данный метод предполагает следующие шаги:

1.Создание начальной популяции – множества особей, численность .

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

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

= ( ) + (1 − ) ( ), где = 0 … 1 – случайное число.

4.Мутация. Случайное изменение наследственных признаков. Например, = , где (дзета) – случайный коэффициент.

5.Селекция. Новая особь помещается в популяцию на место наименее приспособленной особи, которая,

освобождая позицию, погибает.

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

Пример (из лекции)

Функция Экли

( , ) = −20 exp (−0.2√0.5( 2 + 2)) − exp(0.5(cos(2 ) + cos(2 ))) + + 20

Найденное значение:

= (−0.002, −0.014), ( ) = 0.040

Размер популяции 50, число поколений 1000.

Реальный экстремум:

= (0, 0), ( ) = 0

// Мутация популяций void mutate() {

auto minimal_population_x = *std::min(population_x_.begin(), population_x_.end()); auto minimal_population_y = *std::min(population_y_.begin(), population_y_.end());

std::normal_distribution<> normal_dist {0, min(probability_ * 1000, 0.001)}; // нормальное распределение

for (auto &elem : population_x_) {

elem += minimal_population_x * normal_dist(random_gen_);

}

for (auto &elem : population_y_) {

elem += minimal_population_y * normal_dist(random_gen_);

}

}

//Рекомбинация (размножение) void crossover() {

int population_x_length = population_x_.size(); std::uniform_int_distribution<>

uniform_dist(0, population_x_length - 1); // Равномерное дискретное распределение population_x_.resize(number_of_population_members_); // Увеличение population_y_.resize(number_of_population_members_); // Увеличение

for (int i = population_x_length; i < number_of_population_members_; ++i) { population_x_[i] =

( population_x_[uniform_dist(random_gen_)] + population_x_[uniform_dist(random_gen_)] ) / 2.0; population_y_[i] =

( population_y_[uniform_dist(random_gen_)] + population_y_[uniform_dist(random_gen_)] ) / 2.0;

}

}

//Поиск минимума функции (количество итераций в аргументах)

T searchMinimum(int iterations) { generateInitialPopulation();

for (int i = 0; i < iterations; ++i) {

auto temp_population = getBestMembers(); population_x_ = temp_population.first; population_y_ = temp_population.second; crossover();

mutate();

}

auto minimumValueIndex = getMinimalValueIndex();

return function_(population_x_[minimumValueIndex], population_y_[minimumValueIndex]);

}

//Получение индекса элемента с минимальным значением функции f(x, y) int getMinimalValueIndex() {

vector<T> function_values(number_of_population_members_);

auto tempX = population_x_.begin(), tempY = population_y_.begin(); for (auto &k : function_values) {

k = function_(*( tempX++ ), *( tempY++ ));

}

return std::min(function_values.begin(), function_values.end()) - function_values.begin();

}

//Получение X и Y координаты минимума

pair<T, T> getArgumentsOfMinimumValue() {

auto minimum_value_index = getMinimalValueIndex();

return {population_x_[minimum_value_index], population_y_[minimum_value_index]};

}

GeneticAlgorithm(const GeneticAlgorithm &arg) = delete;

GeneticAlgorithm &operator=(const GeneticAlgorithm &arg) = delete;

GeneticAlgorithm &operator=(GeneticAlgorithm &arg) = delete;

GeneticAlgorithm(GeneticAlgorithm &&arg) = delete;

private:

int number_of_population_members_; // Количество популяций

double percent_of_best_ones_to_live_; // Процент выживаемости (лучшие выживают, остальные погибают) pair<T, T> section_; // Ограничения областей определения

std::function<T(T, T)> function_; // Функция, которую необходимо минимизировать double probability_; // Точность

vector<T> population_x_; // Популяция X vector<T> population_y_; // Популяция Y

std::mt19937 random_gen_; // Генератор рандомных чисел

// Итеративная быстрая сортировка Хоара для трехмерного массива по первому вектору functionValues static void Sort(vector<T> &functionValues, vector<T> &populationX, vector<T> &populationY) {

int Left = 0, Right = functionValues.size() - 1, L2, R2; T PivotValue, Temp;

std::stack<T> Lows, Highs;

Lows.push(Left);

Highs.push(Right); while (!Lows.empty()) {

Left = Lows.top(); Lows.pop();

Right = Highs.top(); Highs.pop();

L2 = Left;

R2 = Right;

PivotValue = functionValues[( Left + Right ) / 2]; do {

while (functionValues[L2] < PivotValue) { ++L2; } while (functionValues[R2] > PivotValue) { --R2; } if (L2 <= R2) {

if (functionValues[L2] > functionValues[R2]) { std::swap(functionValues[L2], functionValues[R2]); std::swap(populationX[L2], populationX[R2]); std::swap(populationY[L2], populationY[R2]);

}

++L2;

if (R2 > 0) { --R2;

}

}

} while (L2 <= R2); if (L2 < Right) {

Lows.push(L2); Highs.push(Right);

}

if (R2 > Left) { Lows.push(Left); Highs.push(R2);

}

}

}

};

// Функция Экли

double AckleyFunction(double x, double y) {

return -20 * exp(-0.2 * sqrt(0.5 * ( x * x + y * y ))) - exp(0.5 * ( cos(2 * M_PI * x) + cos(2 * M_PI * y) )) + M_E + 20;

}

// Функция Била

double BealFunction(double x, double y) {

return pow(1.5 - x + x * y, 2) + pow(2.25 - x + x * y * y, 2) + pow(2.625 - x + x * y * y * y, 2);

}

// Функция Изома

double IzomFunction(double x, double y) {

return -cos(x) * cos(y) * exp(-pow(x - M_PI, 2) - pow(y - M_PI, 2));

}

// Функция Розенброка

double RosenbrokFunction(double x, double y) {

return ( 1.0 - x ) * ( 1.0 - x ) + 100.0 * ( y - x * x ) * ( y - x * x );

}

// Функция Шаффера-N2

double ShafferN2Function(double x, double y) {

return 0.5 + (pow(sin(x * x - y * y), 2) - 0.5) / pow(1 + 0.001 * (x * x + y * y), 2);

}

int main() {

cout << setprecision(16); const double EPS = 1e-7;

int numberOfPopulationMembers = 10000; int iterations = 10000;

double percentOfBestOnesToLive = 0.8; pair<double, double> searchingSection = {-1, 4}; GeneticAlgorithm<double>

GA_A(numberOfPopulationMembers, percentOfBestOnesToLive, searchingSection, AckleyFunction, EPS);

{

cout << "Ackley Function" << endl;

auto minimumValue = GA_A.searchMinimum(iterations); auto minimumPoint = GA_A.getArgumentsOfMinimumValue();

cout << "Minimum: f(" << minimumPoint.first << ", " << minimumPoint.second << ") = " << minimumValue << endl;

cout << "Real: f(0, 0) = 0" << endl << endl;