Эта статья короткое ответвление от цикла статьей по биовычислениям:
От белков к РНК, Мат. критерии, Как уменьшить число поворотов цепи?, Как оценить ход сворачивания односпиральной РНК?
В этих статьях задача сворачивания РНК представлена в новом свете — как задача теории игр. Но традиционно эта задача сейчас решается с применением различных стахостических оптимизирующих методов. А к ним относятся методы основанные на методе Монте-Карло, метод отжига, генетические алгоритмы, искусственные нейронные сети, Q-обучение, и все те которые представляют задачу как энергетическую поверхность в которой ищут экстремумы.
Казалось бы сама физика велит использовать эти методы в таких задачах как сворачивание РНК/белков. Здесь мы посмотрим почему это сильно проблемно.
Основная идея очень проста на самом деле. Давайте возьмем простейшую из игр с противником крестики-нолики, и построим энергетическую поверхность и её изменения при ходах игроков. На рисунке отображена в первом ряду энергетическая поверхность в начале игры, во втором ряду после хода крестиков в позицию 2 (позиции от 1 до 9, перечисляя слева на право, снизу вверх).
Рисунок справа показывает 3-х мерную дискретную поверхность, которая образуется. По оси Y – отображается энергетическая оценка по методу Мини-Макс, по оси Z – позиция хода текущего игрока, а по оси X – позиция хода противника. Каждая точка на поверхности показывает, какие шансы у игрока противника в зависимости от сделанного хода игрока. Проекции этой поверхности – на рисунке по центру вид сбоку, а слева вид сверху.
Мы видим, что ход в позицию 5 увеличивает шансы игрока (см. вид сбоку). Ход же в другие позиции не дает видимых преимуществ – площадь на виде сверху заполнена почти равномерно. Если же игрок поставит крестик в позицию 2, то энергетическая поверхность существенно изменится. Тогда, если нолик займет позицию 5, то наиболее опасная позиция для крестиков становится 8. Из вида сверху понятно, что если не будет разыгрываться центральная позиция 5, то шансы игроков уже не столь равномерны, как в начале игры. Так установка в позицию 1, 3, 5, 7 расширяет возможности ноликов, а 4 сильно снижает.
Мне остается только спросить: что будут искать оптимизирующие алгоритмы, когда каждый новый ход так изменяет энергетическую поверхность, что она становится практически неповторяемой? Будет ли хоть малейшая оптимизация по сравнению с полным перебором?
Автор: tac
