Симуляция Монте-Карло и алгоритмы имитации отжига

Симуляция Монте-Карло

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

где Р (х) — распределение случайной величины х ф (х) — функция случайной величины х_у подлежащая оценке; N — размерность величины х.

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

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

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

Алгоритм равномерного формирования выборки. Принимая тот факт, что мы не способны полностью исследовать все возможные значения функции плотности распределения Р (х)_у мы можем попробовать сгенерировать равномерно распределенные значения величины х и попытаться использовать их для получения оценки исследуемой функции ф (х).

Для проведения подобной оценки мы можем рассчитать нормализующую константу Z_R:

где R — размер выборки; Р*(^^г)) — точечные оценки плотности распределения Р (х) для полученных значений величины х.

В результате общая формула (2.61) получения оценки Ф преобразуется в следующее выражение:

Хотя данный подход и показывает нам способ решения проблемы формирования оценки математического ожидания исследуемой функции, не используя напрямую выборку из сложного распределения Р (х), в решении реальных задач он используется редко. Особенностью функций плотности распределений Р (х) и оцениваемых функций ф (х), встречаемых в биоинформатических моделях, является многомерность распределения случайной величины х в сочетании с небольшими размерами областей значений, дающих весомый вклад в оценку функции ср (х) относительно всего пространства состояний. При использовании равномерного формирования выборки к задачам такого типа появляется проблема данного метода, связанная с тем, что для попадания величины х хотя бы несколько раз в интересующую нас область пространства состояний модели требуются слишком большие объемы (R) выборки.

Выборка по значимости. Возможным решением проблемы сокращения необходимых объемов выборки для получения репрезентативных значений величины х является отказ от равномерного исследования пространства состояний модели. Допустим, нам доступно некоторое распределение с плотностью Q (x), из которого мы с легкостью способны сформировать выборку значений. При этом плотность распределения Q (x) близка к плотности требуемого распределения Р (х) (рис. 2.26).

Рис. 2.26. Пример функций, задействованных в выборке по значимости:

Р*(х) — плотность распределения случайной величины х; Q*(x) — дополнительное распределение, из которого мы способны сформировать выборку значений величины х; ф (.г) — функция случайной величины х, оценку Ф которой мы пытаемся получить При таком подходе нам остается только скомпенсировать разницу плотностей распределений Р (х) и Q (x) с помощью специального взвешивающего фактора w_t:

включив его в формулу (2.61) оценки значения математического ожидания функции ф (х):

Практическая сложность применения данного подхода состоит в том, что у нас нет возможности оценить точность получаемой оценки Ф искомой величины Ф. Проблемы с точностью оценки могут возникать в случаях, когда есть области, в которых плотность дополнительного распределения Q*(x) низка при больших значениях произведения |ф (х) Р х (х) |.