Алгоритм Монте Карло и глобальная оптимизация

Дали интересную задачи с реализацией ПС на тему Обезьянего Поиска(С использованием алгоритма решения задачи глобальной оптимизации)

Но меня интересует вопрос как находятся решения по Алгоритму Монте-Карло?

На рисунке предоставлен кусок алгоритма,над которым я вожусь(Это из книги Карпенко-Алгоритмы вдохновлённые природой)

Мои попытки собрать в кучу вышли в следующие вопросы.

1)Сгенерировал случайным образом размерность вектора,а вот дальше тупик.Дальнейшие действия после генерации размерности вектора ввели в заблуждение.Какие величины они от меня требуют?Если я только лишь работаю с размерностью вектора.

2)Затем в 3-ем пункте мы снова генерируем точку,возможно это элемент моего вектора(То есть мои исходные данные среди которых я буду находить решение или экстремум)

3)И наконец проблема это формула фитнесс функции.Описание я нашёл,я понял что она функция приспособленности и в некоторых случаях минимизация(то есть из всей значений я должен найти минимум)

Если не сложно сможете объяснить понятным языком или указать литературу или сайт где будет пояснено понятным языком.

Миниатюры

 

0

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

Да, это целевая функция, которую нужно минимизировать. Функция подбирается так, чтобы её глобальный минимум был решением задачи.

Например, мы хотим решить уравнение x^2=4. Перепишем по-другому: x^2-4=0. Выражение слева может быть положительным, нулём и отрицательным. А его квадрат (x^2-4)^2 может быть только положительным или нулём. Причём ноль — минимум — соответствует точному решению уравнения. Поэтому целевая функция f(x) = (x^2-4)^2 подходит для задачи.

Кстати, x здесь это число. Или одномерный вектор. Будь перед нами система из N уравнений, целевая функция, вероятно, была бы N аргументов. Или одного аргумента размерности N.

Размерность вектора определяется целевой функцией и на протяжении всего алгоритма постоянна.

Сообщение от redseven Затем в 3-ем пункте мы снова генерируем точку

Ключевая фраза — мы генерируем точку. Скажем, задача одномерна. Тогда просто берём любой генератор случайных чисел. Если задача многоразмерная, тут уже есть больше простора для фантазии.

Сам же алгоритм не регламентирует ни выбор целевой функции, ни выбор генератора.

Скажем, мы выбрали стандартное нормальное распределение.

Реализуем алгоритм с 4 итерациями:

1

Спасибо большое
уже начало что-то прояснятся по поводу алгоритма

Но вот про фитнесс-функцию снова спрошу,2 вопроса возникло.

Дело в том что нигде толком не указывается формула этой фитнес-функции,даже вы указали пример формулы X^2-4=0.

1)А существует ли общая формула?(например если бы она была,я бы её в программе записал бы и работал напрямую).
2)А простое условие проверки на минимум тоже может подойти в качестве фитнес-функции?

По поводу алгоритма
Судя по алгоритму указанному выше и плюс я ещё внимательно перечитал.
Я понял что вся суть Монте Карло сводится к тому что я на протяжении всей длинны вектора(Допустим мой вектор-массив на 9 значений)

1)Создаю динамический массив
2)Заполняю его случайными числами
2)Нахожу минимум(то есть минимальное значение временного массива)
3)Запоминаю его(заношу в главный вектор-массив)
4)Очищаю временный массив(для повторения следующей генерации)
5)Делаю это столько раз,сколько нужно заполнить главный вектор(к примеру 9 раз)

В итоге мой вектор заполнен минимальными числами.

Правильно ли это рассуждение про алгоритм?

0

Сообщение от redseven А существует ли общая формула?

Нет, не существует.
Фитнес-функция выбирается творчески, для каждой задачи по-своему.
Основная суть ф-ф в том, чтобы задачу сформулировать в терминах минимизации некоторой функции.
Вот к примеру любое уравнение вида A=B можно представить в виде задачи минимизации (A-B)^2. Я выше написал, почему.
Ещё пример: силовые методы укладки графа на плоскости позволяют сформулировать задачу визуализации графа (где какие вершины нарисовать) в терминах минимизации некоторой функции (потенциала).
Почти любая задача аппроксимации может быть сформулирована в терминах минимизации (пример — метод наименших квадратов).
Общей формулы, понятно, нет, как нет общей формулы для решения любого (ЛЮБОГО) уравнения.

Сообщение от redseven А простое условие проверки на минимум тоже может подойти в качестве фитнес-функции?

Что это такое?

Сообщение от redseven Я понял что вся суть Монте Карло сводится к тому что я на протяжении всей длинны вектора(Допустим мой вектор-массив на 9 значений)

Я предлагаю забыть о векторах и для начала разобраться с числами. Число — это вектор длины один. То есть |X|=1 в тексте.
X и X* — числа.

Как тогда выглядит алгоритм? Распишите сами. Вся суть в шагах 3 и 4. В начале генерируем случайное число, а затем сравнимаем значения ф-ф для неё и уже найденного приближения.

0

Вот как я понимаю:
Для начала нужно на основании вашей задачи придумать уравнение с неизвестными и приравнять к нулю. Свести вашу задачку в математическое выражение, это творческая задача. Затем задать пределы поиска переменным minX maxX и желаемую точность корня(сколько знаков после запятой). Это тоже вы задаете. Вроде таких людей называют аналитик. Задать пределы количества итераций MaxIter.
Суть Монте-Карло это обычный случайный поиск.
Пример: возьмем отбалды любую формулу (представим вы ее вывели) X^2-4=0
Задаем пределы поиска minX maxX: от 0 до 10. Задаем точность например 2 знака. Суть расчета найти такой X чтобы при подстановке в целевую функцию она бы минимально отличалась от нуля ( 0 идеально).
1)Разбрасываем N точек на интервале от 0 до 10 например 20 точек.
Считаем массив f(x).Находим два минимальных числа с разными знаками и сохраняем X которым они относятся minX maxX. Разные знаки значит на этом интервале есть корень. Проверяем сколько нулей после запятой если подставить ближайшее к нулю из двух minX maxX точность решения устраивает?
Если да то выход, иначе cнова пункт 1 но уже на найденном мелком интервале. Снова разбрасываем N точек но уже от minX до maxX. И так повторяем пока итераций будет меньше MaxIter или точность не устраивает.
Зачем разбрасывать точки когда корень один? Потому, что в реальности может быть много локальных минимумов из которых другие методы не смогут выйти или будут выходить долго.

0