Стохастическая оптимизация: случайный поиск в Java

1 min


Введение

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

В то время как грубая сила алгоритмы предоставляют нам лучшее решение, они ужасно неэффективны. Это не проблема для небольших наборов данных, но большинство реальных проблем и областей поиска требуют таких огромных вычислительных возможностей, которые должны быть решены в разумные сроки, чтобы такие компьютеры, вероятно, существовали за пределами предсказуемого будущего.

В таких случаях необходимо использовать новый подход, и вместо поиска самого лучшего решения мы выбираем приблизительное решение, которое будет работать для нас достаточно хорошо.

Существует множество методов оптимизации, и каждый метод может быть реализован с помощью множества различных алгоритмов. Мы начнем с реализации наименее эффективного и наиболее интуитивного Стохастический поиск алгоритм – Случайный поиск,

В погоне за эффективностью за абсолютную корректность было разработано много случайных алгоритмов, кульминацией которых стали эволюционные алгоритмы, такие как Генетические алгоритмы,

Случайный поиск

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

Затем он приступает к проверке каждой из этих точек путем сравнения текущего еМаксимум по отношению к значению точки, в которой он включен, присваивая ему новое значение при необходимости. После прохождения всех сгенерированных точек, он возвращает нам еМаксимум в качестве приблизительного решения.

Недостатком всех алгоритмов стохастического поиска, особенно случайного поиска, является то, что они может быть столь же неэффективным, как алгоритмы грубой силы, если вы не уравновешиваете это.

Чем больше случайных точек вы используете, тем ближе будет приближение к абсолютному наилучшему решению, но тем медленнее будет алгоритм. С бесконечным количеством случайных точек это просто обычный алгоритм перебора.

Вот функция, сгенерированная FooPlot В качестве примера того, как случайный поиск ищет максимум / минимум функции:

функция

Здесь есть 7 случайно сгенерированных точек, где совпадению смысл 7 расположен на Икс значение, которое вернет самое низкое 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) для еМаксимум а также (1.65, -2.65) а также (1.8, -2.9) для емин должно быть примерно хорошим решением.

Реализация

Давайте продолжим и осуществим случайный поиск в 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 в многопоточной среде. В нашем случае это не имеет большого значения, но может иметь большое значение. Кроме того, легче определить диапазон doubleс помощью ThreadLocalRandom,

Если это так, то maxY установлен на function(random) как он возвращает y значение и maxX установлен на random поскольку это тот, который произвел самый большой y значение через function() метод.

После for цикл заканчивается, мы остались с maxX а также maxY с определенными значениями, которые, по сути, являются приближением того, что фактический максимум Икс а также 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 пункт.

Вывод

Иногда приблизительное решение достаточно для ваших нужд, и вам не нужно заставлять вашу машину находить наилучшее из возможных решений.

Этот подход чрезвычайно полезен, когда вы имеете дело с проблемами огромной вычислительной сложности и может на несколько порядков повысить производительность вашей программы.

Конечно, если вы не уравновешиваете алгоритм правильно, вы получите неэффективное решение, поэтому поиграйтесь с количеством случайных точек, чтобы получить эффективное.


0 Comments

Ваш e-mail не будет опубликован. Обязательные поля помечены *