Знайомство з методом Монте-Карло

У цій статті ми не заглиблюватимемося в математику, а постараємося дати загальне уявлення про метод Монте-Карло.

Суть методу полягає в наступному: для цільової випадкової величини генерується набір випадкових значень, а потім на основі розраховуються необхідні значення.

Метод Монте-Карло має багато різних додатків. Він застосовується у таких областях: у промисловості для моделювання мінливості виробничих процесів; у фізиці, хімії та біології для моделювання різноманітних явищ; у сфері ігор для моделювання штучного інтелекту, наприклад, у китайській грі; в галузі фінансів для оцінки похідних фінансових інструментів та опціонів. По суті метод Монте-Карло використовується скрізь.

Сучасний варіант методу сформувався рамках Манхеттенського проекту, де він застосовувався для моделювання відстаней, які можуть пройти нейтрони у різних матеріалах. Ідея моделювання на основі генерації набору випадкових значень існувала вже протягом деякого часу, але особливого розвитку набула при створенні атомної бомби, поширившись потім у багатьох інших галузях знань.

Великою перевагою методу Монте-Карло є те, що він дозволяє врахувати у моделі елемент випадковості та складність реального світу. Крім того, метод є робастним по відношенню до зміни різних параметрів, таких як розподіл випадкової величини. У основі лежить закон великих чисел.

Одним із типових прикладів використання методу Монте-Карло є завдання, в яких необхідно знайти математичне очікування деякої випадкової величини. Для цього необхідно згенерувати набір випадкових значень цієї величини і визначити середнє. Випадкова величина зазвичай характеризується певним розподіломймовірностей.

Обчислення числа Пі

За допомогою методу Монте-Карло можна визначити число Пі. Код R для даного прикладу знаходиться тут.

Вписавши коло в квадрат (діаметр кола дорівнює стороні квадрата), можна висловити відношення площі кола до площі квадрата таким чином:

Якщо ми зможемо обчислити це відношення, то ми зможемо отримати значення числа Пі.

Заповнимо квадрат точками з випадковими координатами. Розрахуємо відношення кількості точок, що потрапили до кола, до загальної кількості точок. Помножимо результат на 4 щоб отримати значення числа Пі.

Чим більша кількість точок, тим ближче отримане значення до справжнього значення числа Пі.

Цей простий приклад демонструє метод Монте-Карло у дії.

Моделювання транспортних потоків

Розглянемо найкорисніший приклад. Ми можемо змоделювати транспортний потік за допомогоюмоделі Нагеля-Шрекенберга (Nagel-Schreckenberg model). У рамках цієї моделі траса складається з осередків, задана максимально допустима швидкість та певна кількість автотранспортних засобів (АТС). На кожному кроці стан усіх АТС оновлюється відповідно до таких правил:

Швидкість даного АТС v збільшується на одиницю, якщо вона менша за максимально допустиму швидкість.
Знайдемо відстань d між даними АТС і АТС, що йде попереду. Якщо швидкість цього АТС більша чи дорівнює відстані d, вона зменшується до величини d-1.
За допомогою методу Монте-Карло додамо елемент випадковості. З ймовірністю p швидкість цього АТС зменшується на одиницю.
Це АТС переміщається вперед на v одиниць.

Ця модель досить проста, але дуже ефективна. У даній моделі не враховуються ДТП чи поганеводіння. Її призначенням є моделювання спонтанних змін у характері транспортних потоків. Існують і складніші моделі, але багато хто з них засновані на моделі Нагеля-Шрекенберга.

Код для моделювання тут, а для візуалізації мовою Processing – тут.

Проблеми у рамках методу Монте-Карло

Основною проблемою є створення незалежних випадкових величин. Це не таке просте завдання, як може здатися на перший погляд. У прикладах коду ми просто викликали вбудовані функції R або Python для генерації випадкових чисел, але цей процес може бути набагато складнішим. За потреби ви можете звернутися до наукових джерел з цієї теми.

За цим посиланням ви можете знайти інформацію про те, як R здійснюється генерація випадкових чисел з рівномірним розподілом (uniform distribution).

Інша проблема у тому, як забезпечити збіжність помилки. Зверніть увагу на те, що в прикладі обчислення числа Пі помилка перестала зменшуватися. У більшості програм методу Монте-Карло для вирішення цієї проблеми використовуються дуже великі вибірки.