Вступление
Стохастическая оптимизация относится к категории алгоритмов оптимизации, которые генерируют и используют случайные точки данных для поиска приближенного решения.
Хотя алгоритмы грубой силы действительно предоставляют нам лучшее решение, они ужасно неэффективны. Это не проблема с меньшими наборами данных, но для большинства реальных проблем и пространств поиска требуются такие огромные вычислительные возможности, которые должны быть решены в разумные сроки, что такие компьютеры, вероятно, будут существовать за пределами предсказуемого будущего.
В таких случаях необходимо использовать новый подход, и вместо того, чтобы искать действительно лучшее решение, мы соглашаемся на приблизительное решение, которое будет работать для нас достаточно хорошо.
Существует множество методов оптимизации, и каждый из них может быть реализован с помощью множества различных алгоритмов. Мы начнем с реализации наименее эффективного и наиболее интуитивно понятного алгоритма стохастического поиска - случайного поиска .
В погоне за эффективностью над абсолютной правильностью было разработано множество случайных алгоритмов, кульминацией которых стали эволюционные алгоритмы, такие как генетические алгоритмы .
Случайный поиск
Случайный поиск - это простейший алгоритм стохастического поиска, который очень интуитивно понятен. Например, предположим, что мы ищем максимум функции. Вместо того, чтобы подбирать решение, он генерирует случайные точки в одном измерении пространства поиска.
Затем он переходит к проверке каждой из этих точек, сравнивая текущее значение f ~max~ со значением точки, в которой она находится, и при необходимости присваивает ей новое значение. После прохождения всех сгенерированных точек он возвращает нам f ~max~ в качестве приблизительного решения.
Обратной стороной всех алгоритмов стохастического поиска, и особенно случайного поиска, является то, что они могут быть столь же неэффективными, как алгоритмы грубой силы, если вы не сбалансируете их.
Чем больше случайных точек вы используете, тем ближе будет приближение к наилучшему решению, но тем медленнее будет алгоритм. С бесконечным количеством случайных точек это просто обычный алгоритм грубой силы.
Вот функция, созданная FooPlot в качестве примера того, как случайный поиск ищет максимум / минимум функции:
{.ezlazyload}
Здесь есть 7 случайно сгенерированных точек, где по совпадению точка 7 расположена в значении x , которое вернет наименьшее значение y, а 5 близко к значению, которое вернет наибольшее значение y , например.
Мы ограничим область определения функции диапазоном от -1 до 2 и в
этом диапазоне, используя простое школьное исчисление, легко вывести,
что:
$$
f_ {max} = (0,73947, 0,23098) \ клин f_ {min} = (1,71548, -2,79090)
$
При этом, в зависимости от конкретной точности, которую вы ищете
(например, 95%), если случайный поиск приближается к чему-либо между
(0.7, 0.2) и (0.75, 0.25) для f ~max~ и (1.65, -2.65) и
(1.8, -2.9) для f ~min~ должно быть приблизительно хорошим решением.
Выполнение
Давайте продолжим и реализуем случайный поиск на Java. Во-первых,
давайте свяжем домен нашей функции с {-1...2} :
private static final double START_DOMAIN = -1;
private static final double END_DOMAIN = 2;
Затем давайте воспроизведем функцию из FooPlot, которая, конечно же,
возвращает y на основе x :
private double function(double x) {
return ((Math.pow(x, 2)-1)*((x-2)*Math.pow(x, 3)));
}
Наконец, реализуем сам алгоритм:
public void randomSearch() {
double startPosition = START_DOMAIN;
double maxY = function(startPosition);
double maxX = START_DOMAIN;
for (int i = 0; i < 10; i++) {
double random = ThreadLocalRandom.current().nextDouble(START_DOMAIN, END_DOMAIN);
if (function(random) > maxY) {
maxY = function(random);
maxX = random;
}
}
System.out.println("The maximum of the function f(x) is (" + maxX + ", " + maxY + ")");
}
Очевидно, что начальная позиция итерации находится в начале домена.
maxY вычисляется с использованием function() который мы определили,
а maxX устанавливается как значение в начале домена.
Это текущие максимальные значения, поскольку мы еще ничего не оценивали.
Как только мы присваиваем им значения по умолчанию с помощью for , мы
генерируем случайную точку между началом и концом домена. Затем мы
оцениваем, является ли случайная точка, переданная через function() ,
на какое-либо изменение больше, чем текущий maxY .
Примечание. Мы используем ThreadLocalRandom вместо обычного
Random поскольку ThreadLocalRandom может работать намного быстрее,
чем Random в многопоточной среде. В нашем случае это не имеет большого
значения, но может иметь существенное значение. Кроме того, с помощью
ThreadLocalRandom double s.
Если это так, maxY устанавливается для function(random) поскольку
она возвращает значение y maxX устанавливается на random как это
то, которое произвело наибольшее значение y помощью метода
function()
После завершения for у нас остаются maxX и maxY с определенными
значениями, которые, по сути, являются приближением фактических
максимальных x и y .
Выполнение этого фрагмента кода даст:
The maximum of the function f(x) is (0.7461978805972576, 0.2308765022939988)
И если сравнить это с реальными результатами, это довольно точно, с жалкими 10 случайными точками. Если увеличить количество случайных точек с 10 до 100, мы получим следующий результат:
The maximum of the function f(x) is (0.735592753214972, 0.2309513390409203)
Между ними не так много улучшений, что просто показывает, что 100 итераций совершенно не нужны . Если мы позволим себе уменьшить его с 10 до 5, мы увидим, что это отключено:
The maximum of the function f(x) is (0.6756978982704229, 0.22201906058201992)
Опять же, в зависимости от ваших требований к точности это может быть просто приемлемым решением.
Изменить алгоритм поиска минимума вместо максимума так же просто, как
заменить оператор > < в предложении if .
Заключение
Иногда приблизительного решения достаточно для ваших нужд, и вам не нужно заставлять машину искать наилучшее возможное решение.
Этот подход чрезвычайно полезен, когда вы имеете дело с проблемами огромной вычислительной сложности, и может на порядки повысить производительность вашей программы.
Конечно, если вы не сбалансируете алгоритм правильно, вы получите неэффективное решение, поэтому поиграйте с количеством случайных точек, чтобы получить эффективное.!