Математическое обеспечение модели компьютерного прогнозирования противоположных событий на основе идеи Марко Дориго

АННОТАЦИЯ

В статье представлены результаты разработки компьютерного способа прогнозирования появления случайного события в единичном случае на основе идей муравьиного алгоритма и цепей Маркова. Также в статье приводится пример создания данных на основе метода Монте-Карло.

ABSTRACT

The article presents the results of developing a computer method for predicting the occurrence of a random event in a single case based on the ideas of the ant algorithm and Markov chains. Also in the article you will give an example of creating data based on the Monte Carlo method.

Рассмотрим последовательность наблюдений, в каждом из которых фиксируется появление некоторого события. Пусть моменты времени появления события случайны. Допустим, что с появлением события связан некоторый выигрыш наблюдателя. Тогда задача заключается в том, чтобы достоверно предсказать появление события в следующем (будущем) единичном наблюдении. Задача в данной постановке является классической задачей теории вероятностей благодаря работам Р. Мизеса, Ф.П. Рамсея, А.Н. Колмогорова, К.Р. Поппера, Я. Бернулли, П.С. Лапласа и других. Следует отметить, что актуальность данной абстрактной задачи в общей постановке связана с тем, что новые разработанные исследователями различные методы прогнозирования, основанные на вероятностном подходе, можно проверить на этой задаче. С этой точки зрения актуальность исследования перенесена в область поиска, выбора или разработки оптимального метода нахождения решения данной задачи. Выбор метода тесно связан с начальной накопленной информацией о конкретном наблюдаемом событий. При учитывании по Геделю (Курт Гедель) неполноты начальных данных интересными для разработки представляются устойчивые методы, не чувствительные к качеству входных данных. Перспективными в этом подходе являются комбинированные методы [1]. Сравнительный анализ показывает, что комбинированными методами удается построить решения, раскрывающие причинно-следственные связи события, необходимые условия или признаки его возникновения.  

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

Следует отметить, что переход системы из одного состояния в другое осуществляется в случайные моменты времени. Тогда задача заключается в том, чтобы достоверно предсказать переход состояния системы из начального состояния в другое. Представим решение данной задачи и построим диаграмму Мура для цепи Маркова. Схема представлена на рисунке 1, где  – состояние системы, отражающее наступление события,  – состояние системы, которое отражает наступление противоположного события,  − переходные вероятности системы. Итак, данная схема в постановке задачи — это однородная цепь Маркова с непрерывным временем.

Рисунок 1. Однородная цепь Маркова

Согласно теории цепей Маркова нам необходимо определить неизвестные переходные вероятности и вероятности пребывания системы в заданных состояниях во времени. Для этого воспользуемся идеями Марко Дориго [2] в формуле для вычисления значений вероятностей выбора дуги графа муравьем в муравьином алгоритме. Как известно, в муравьином алгоритме устойчивый ферменный след условных муравьев накапливается на тех дугах, которые чаще, чем другие дуги, встречаются в вариантах решений. То есть при построении различных вариантов маршрута в заданном графе эти дуги чаще встречаются в различных последовательностях. Такие дуги можно считать опорными для составления оптимального маршрута (цикл Гамильтона в задаче коммивояжера).

Обозначим матрицу переходов системы:

                                                                 (1)

Причем,

                                                                    (2)

Далее приведем формулу вероятностей переходов муравья из одного узла в другой в муравьином алгоритме Дориго:

                                                                     (3)

 − величина, обратная длине ребра графа,

 – количество муравьиного феромона,

 − некоторые параметры управления сходимостью алгоритма.

Представим входные данные задачи в таблице 1, где отражена накопленная информация о событии в терминологии цепей Маркова.

Таблица 1. 

Начальные данные задачи

Переходы					Сумма
Значения

Примечание: 

Здесь  − эмпирические оценки интенсивности переходов,  − настраиваемые значения управляющей системой величины, в нашем случае –феромонного следа. Начальные значения феромонного следа можно задать произвольно. Таким образом, мы определили все составляющие формулы (3) для вычисления вероятностей переходов Марковской цепи.

                                                                   (4)

Параметры   выберем из условия 

Допустим, что мы наблюдаем начальное состояние  системы. Интенсивности переходов  составляют полную группу событий. В компьютерной модели разыграем несколько раз методом Монте-Карло полную группу.  На основе формулы (4) и результата разыгрывания случайной величины, которая отражает дуги графа (Рисунок 1) изменим значение величины феромона, участвующей в расчете вероятностей переходов   в формуле (4).

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

                                                                 (5)

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