Сегодня сложная тема, но мы объясним её просто и понятно. Разговор пойдёт про алгоритмы и немного про математику.
Методы Монте-Карло — это набор методов в математике для изучения случайных процессов. Случайных — это когда что-то в них происходит непредсказуемым образом, например:
- подбрасываем монетку;
- кидаем кубик;
- опускаем жетоны в ячейки со столбиками;
- ловим элементарные частицы;
- считаем столкновения молекул;
- и что угодно ещё, что происходит полностью случайно и что нельзя предсказать заранее.
Смысл методов Монте-Карло в том, чтобы использовать данные случайных событий, чтобы на их основе получить более-менее точные результаты каких-то других вычислений. Они не будут идеально и математически точными, но их уже будет достаточно, чтобы с ними полноценно работать. Иногда это проще и быстрее, чем считать всё по точным формулам.
Пример такого вычисления — построение маршрута в навигаторе. В исходном виде это задача коммивояжёра, которая требует колоссальных вычислительных ресурсов. Но благодаря приближённым методам с ней справится даже не самый мощный телефон. Один из таких методов — метод Монте-Карло.
Своё название метод получил в честь Монте-Карло — района Монако, где находится много казино с рулеткой, самым доступным источником случайных чисел в начале 20-го века.
В чём идея метода
Если совсем примитивно, то работает так:
Вместо того чтобы строить сложную математическую модель, мы берём простую формулу и пуляем в неё случайные числа. Считаем результат по каждому числу и получаем результат с нужной нам точностью. Чем больше случайных чисел — тем точнее результат.
Вот то же самое немного подробнее:
- Выбираем, что мы хотим найти или посчитать — значение формулы, площадь, объём, распределение материала или что-то ещё.
- Смотрим, как это считается в математике, и находим нужные формулы.
- На основе формул составляем критерий проверки — если случайное значение попало в этот критерий, мы его учитываем как совпавшее число, а если не попало — как не совпавшее.
- Запускаем алгоритм, который выдаёт случайные числа, и проверяем каждое по этому критерию.
- Как наберётся достаточное количество случайных чисел — считаем результат. Обычно это соотношение чисел, которые попали в критерий и которые не попали.
Чем больше будет случайных чисел — тем точнее результат.
Плюс этого метода в том, что нам не нужно запрягать весь математический аппарат для решения задачи — достаточно подставлять числа в формулу и смотреть, получилось верное значение или нет.
Как найти число пи методом Монте-Карло
Для примера покажем классическое использование метода Монте-Карло — найдём число пи. Для этого нам понадобится круг, вписанный в квадрат, причём у круга радиус будет равен 1. Это значит, что сторона квадрата равна 2 — это диаметр (или два радиуса) круга:
В этот квадрат мы будем случайным образом кидать песчинки и смотреть, попадут они в круг или нет (но останутся в границах квадрата). Исходя из этого набора данных мы можем посчитать отношение всех песчинок, которые попали в круг, ко всем песчинкам.
Теперь смотрим на формулы:
- площадь квадрата со стороной 2 равна четырём;
- площадь круга радиусом 1 равна πR² → π×1² = π.
Если мы разделим площадь круга на площадь квадрата, то получим π / 4. Но мы ещё не можем по условию посчитать площадь круга, потому что мы не знаем число π. Вместо этого мы можем разделить количество одних песчинок на другие — в этом и суть метода Монте-Карло.
Это соотношение даст нам результат — π / 4. Получается, что если мы умножим этот результат на 4, то получим число π, причём чем больше песчинок мы кинем, тем точнее будет результат.
Кидать песчинки будем так: в качестве координат попадания X и Y будем брать случайные числа от 0 до 1. Это значит, что все числа попадут только в один квадрант — правый верхний:
Но так как в этом квадранте ровно четверть круга и ровно четверть квадрата, то соотношение промахов и попаданий будет таким же, как если бы мы бросали песчинки в целый круг и целый квадрат.
Чтобы проверить, попадает ли песчинка в круг, используем формулу длины гипотенузы: x² + Y² = 1 (так как гипотенуза — это радиус окружности):
Если длина гипотенузы меньше единицы — точка попадает в круг. В итоге мы посчитаем и общее количество точек, и точек, которые попали в круг. Потом мы разделим одно на другое, умножим результат на 4 и получим приближённое значение числа π.
Программируем поиск числа пи по методу Монте-Карло
Алгоритм на языке Python, читайте комментарии, чтобы лучше разобраться в происходящем:
# подключаем модуль случайных чисел
import random
# функция, которая посчитает число пи
def count_pi(n):
# общее количество бросков
i = 0
# сколько из них попало в круг
count = 0
# пока мы не дошли до финального броска
while i < n:
# случайным образом получаем координаты x и y
x = random.random()
y = random.random()
# проверяем, попали мы в круг или нет
if (pow(x, 2) + pow(y, 2)) < 1:
# если попали — увеличиваем счётчик на 1
count += 1
# в любом случае увеличиваем общий счётчик
i += 1
# считаем и возвращаем число пи
return 4 * (count / n)
# запускаем функцию
pi = count_pi(1000000)
# выводим результат
print(pi)Где используется метод Монте-Карло
На методах Монте-Карло основано много полезного:
- моделирование облучения твёрдых тел ионами в физике;
- моделирование поведения разреженных газов
- исследования поведения разных тел при столкновении
- алгоритмы оптимизации и нахождения кратчайшего пути решения
- решение сложных интегралов (или когда их очень много)
- предсказание астрономических наблюдений
- поиск в дереве в различных алгоритмах
- алгоритмы работы некоторых функций квантового компьютера
- моделирование состояния приближённой физической среды
Без них изучать современный мир и совершать новые открытия было бы сложнее.
Преимущества и недостатки метода Монте-Карло
✅ Преимущества:
- Метод Монте-Карло может быть применён к большому спектру проблем, которые трудно или невозможно решить аналитически.
- С его помощью можно моделировать сложные системы и процессы, состоящие из множества неопределенных взаимодействующих компонентов.
- Метод позволяет получить интуитивное понимание сложных вероятностных процессов. Иногда это помогает лучше разобраться в других областях, где используется похожая механика.
- Процессы Монте-Карло легко распараллеливаются, что позволяет использовать мощности современных многоядерных и распределенных вычислительных систем и загружать их на все сто.
- Метод хорошо справляется с нелинейными зависимостями и обратной связью в системах.
- Сейчас написано уже много программ и готовых библиотек, которые сильно упрощают реализацию метода Монте-Карло.
🤔 Недостатки:
- Для получения точных результатов требуются большие вычислительные мощности, особенно в случаях с большим количеством переменных. С другой стороны, он хорошо распараллеливается, поэтому это недостаток только для слабых систем.
- Результаты моделирования сильно зависят от точности и качества входных данных, а ещё они могут быть сложны для интерпретации, особенно если моделируется множество переменных.
- Из-за использования случайных выборок результаты могут меняться от одного запуска к другому, что требует много прогонов для надёжности.
- В некоторых случаях может быть трудно определить, точно ли мы сделали достаточно прогонов, чтобы результаты сходились к истинному значению.
Что дальше
В следующей части поговорим про отжиг — интересное применение метода Монте-Карло, который имитирует физические процессы. Благодаря отжигу мы можем обучать нейросети и решать сложные комбинаторные задачи.
