Хабр Курсы для всех
РЕКЛАМА
Практикум, Хекслет, SkyPro, авторские курсы — собрали всех и попросили скидки. Осталось выбрать!
Хабр доступен 24/7 благодаря поддержке друзей
Комментарии 44
>Возможно ли это?
Конечно нет. Любая одна функция приводит точку к локальному минимуму, а две функции — к дерганию между их локальными минимумами.
Если же используется градиентный спуск и шаги относительно градиента стремятся к нулю, то такая функция — среднее арифметическое между ними.
В итоге, я так понимаю, вы просто используете свое приближение функции энергии и тупой алгоритм покоординатного спуска. Если добавить сюда метод отжига, то может получиться лучший результат.
Конечно нет. Любая одна функция приводит точку к локальному минимуму, а две функции — к дерганию между их локальными минимумами.
Если же используется градиентный спуск и шаги относительно градиента стремятся к нулю, то такая функция — среднее арифметическое между ними.
В итоге, я так понимаю, вы просто используете свое приближение функции энергии и тупой алгоритм покоординатного спуска. Если добавить сюда метод отжига, то может получиться лучший результат.
Если добавить сюда метод отжига, то может получиться лучший результат.
Обоснуйте.
Обоснуйте.
В прошлой статье была цитата про тепловое движение атомов. Это ядро метода имитации отжига на мой взгляд.
Чем это отличается от
Любая одна функция приводит точку к локальному минимуму, а две функции — к дерганию между их локальными минимумами.
Что понимается под «Любая одна функция». Можно сделать функционал с такой низкой энергетикой, что он попав даже в неглубокий минимум не выйдет из него.
А имитация отжига хорошо согласуется с представлениями о процессах в химии (о тепловом движении). С другой стороны Имитация отжига не согласуется с нелинейной моделью, в которой последовательность поворотов играет важную роль. В любом случае, параллельная оптимизация сразу многих параметров должна обладать большей стабильностью нежели оптимизация поочередно каждого из параметров в синхронном режиме.
По поводу колебаний между лок. минимумами написано много трудов — с этим можно бороться и известно как.
А имитация отжига хорошо согласуется с представлениями о процессах в химии (о тепловом движении). С другой стороны Имитация отжига не согласуется с нелинейной моделью, в которой последовательность поворотов играет важную роль. В любом случае, параллельная оптимизация сразу многих параметров должна обладать большей стабильностью нежели оптимизация поочередно каждого из параметров в синхронном режиме.
По поводу колебаний между лок. минимумами написано много трудов — с этим можно бороться и известно как.
Да, нету тут энергии, есть просто геометрия водородных связей.
А может кто знает, есть ли исходный код этого метода в сети?
Градиентный спуск имеется в виду?
нет. метод отжига и именно в той вариации, где есть выход из локальный минимумов, а не только спуск по ним. Хорошие описание тоже годится, пока не нахожу
habrahabr.ru/post/112189/
Вариацией параметров алгоритма и добиваются определенного поведения. Но подбор параметров алгоритма делается под конкретную задачу.
Вариацией параметров алгоритма и добиваются определенного поведения. Но подбор параметров алгоритма делается под конкретную задачу.
Да, это базовый его вариант.
Ок. Чем это отличается от того, что делаю я. Я не делаю ничего случайно — у меня полный перебор специально отобранных возможных поворотов. Это как я вижу одно отличие. Больше нет. Так?
Плюс имитаци отжига и градиентной оптимизации в увеличении детализации по мере приближения к минимуму (лок. или глоб.).
Полный перебор с заданным (постоянным) квантованием может оказаться либо не слишком точным, либо слишком вычислительно тяжелым.
Кстати слишком большое значение кванта как раз и приводит к потере устойчивости (числовая погрешность, низкая обусловленность задачи). А при потере устойчивости возникают автоколебания узлов модели молекулы и зацикливание между конечным числом локальных минимумов.
К вопросу о поворотах в 3D модели молекулы и колебаниям атомов: в литературе ОЧЕНЬ рекомендуют использовать при поворотах вычисления через КВАТЕРНИОНЫ именно ввиду низкой обусловленности вычислений через ЭЙЛЕРОВЫ УГЛЫ и матрицы поворотов.
Полный перебор с заданным (постоянным) квантованием может оказаться либо не слишком точным, либо слишком вычислительно тяжелым.
Кстати слишком большое значение кванта как раз и приводит к потере устойчивости (числовая погрешность, низкая обусловленность задачи). А при потере устойчивости возникают автоколебания узлов модели молекулы и зацикливание между конечным числом локальных минимумов.
К вопросу о поворотах в 3D модели молекулы и колебаниям атомов: в литературе ОЧЕНЬ рекомендуют использовать при поворотах вычисления через КВАТЕРНИОНЫ именно ввиду низкой обусловленности вычислений через ЭЙЛЕРОВЫ УГЛЫ и матрицы поворотов.
Разве при вычислении через КВАТЕРНИОНЫ, будут получаться другие углы, чем через ЭЙЛЕРОВЫ УГЛЫ и матрицы поворотов?
Во-первых, кватернионная алгебра ВСЕГДА выдает направление поворота по кратчайшей дуге (вроде это нативная фича такая). Во-вторых, у поворотов через матрицы направляющих косинусов НИЗКАЯ ОБУСЛОВЛЕННОСТЬ (читай УСТОЙЧИВОСТЬ). Плохая обусловленность означает, что малая погрешность параметров на входе дает большое отклонение результата.
И это базовый вариант не может выскочить из локального минимума. Так? Если нет, то чем это обеспечивается?
Этой строчкой:
if P(e, enew, T) > random() then // Should we move to it?
s ← snew; e ← enew
Метод может сделать переход, даже если оценочная функция хуже текущей. Но чем больше разница, тем меньше вероятность такого перехода.
if P(e, enew, T) > random() then // Should we move to it?
s ← snew; e ← enew
Метод может сделать переход, даже если оценочная функция хуже текущей. Но чем больше разница, тем меньше вероятность такого перехода.
Понятно. Этого мало — выстрел в случайном направлении.
Не в случайном, а в неплохом.
В случае полного перебора соседей (в вашем случае для случайной пары углов), можно использовать следующую вариацию алгоритма — вычислить P для каждого соседа, нормировать их сумму на 1 и выбрать соседа в соответствии с получившимся случайным распределением.
В случае полного перебора соседей (в вашем случае для случайной пары углов), можно использовать следующую вариацию алгоритма — вычислить P для каждого соседа, нормировать их сумму на 1 и выбрать соседа в соответствии с получившимся случайным распределением.
т.е. Вы предлагает взять скажем 10 самых лучших состояний, из которых выбираем куда повернуться, и повернуться не в одно самое лучшие, а время от времени поворачиваться случайно в одно из 10-ти лучших. Так?
Я предлагаю брать все, но с разными вероятностями. Но никто не мешает пробовать разные вариации.
Вот это и будет «выстрел в случайном направлении», и буду я прыгать по кочкам и ямкам с разными вероятностями.
Мне тут похожий вопрос задали по почте. Скопирую сюда:
Мне тут похожий вопрос задали по почте. Скопирую сюда:
ГА не подходит по той же причине почему и метод отжига :) Конечно, все для этого есть и можно это делать. Но результата не будет — не найдут эти алгоритмы ничего. Я наверно напишу про это отдельную статью на хабре, как ответвление этого цикла статей.
Почему? Если кратко — то потому что это все ОПТИМИЗИРУЮЩИЕ алгоритмы, а что оптимизировать каждый раз не известно. Вот я построил вам целевую функцию — можете оптимизировать. Но на самом деле незачем — т.к. и простой поиск найдет и даже по скорости вряд ли уступит.
Задача тут другая. Вот дальше мы будем образовывать водородные связи не между одной парой нуклеотидов, а между 2-5 парами… и все нужно искать подходящую целевую функцию, старую выкинь и растери. Что тут дадут оптимизирующие алгоритмы? Ничего, они будут искать фигню, т.к. не будут знать как поменялись условия. И так постоянно, шаг за шагом — нужно уточнять целевую функцию. А это не математическая задача, а задача моделирования. Мы хотим шаг за шагом строить все более точную и точную модель, того что имеем. А когда построим не нужны нам будут эти оптимизирующие алгоритмы, т.к. мы поймем что происходит в био. процессе. Понятно излагаю?
Задача здесь как раз поиск минимума на энергетической поверхности. Только ее трудно рассчитать, поэтому нужно использовать приближения. Вопрос выбора хорошего приближения не менее важен, чем выбор алгоритма оптимизации.
В шахматах оптимизирующие алгоритмы не применяются. Тем не менее, там есть похожие вещи. Чем хуже вариант, тем на меньшую глубину он просчитывается (вместо того, чтобы отбрасывать его совсем). По-моему весьма похоже на метод отжига.
В играх для одного игрока я применял другую его модификацию и получал неплохие результаты.
В шахматах оптимизирующие алгоритмы не применяются. Тем не менее, там есть похожие вещи. Чем хуже вариант, тем на меньшую глубину он просчитывается (вместо того, чтобы отбрасывать его совсем). По-моему весьма похоже на метод отжига.
В играх для одного игрока я применял другую его модификацию и получал неплохие результаты.
Или еще по другому попробую пояснить. Тут надо понять, что это задача другого типа — это не поиск минимума на энергетической поверхности. Это задача аналогичная поиску хода в компьютерных шахматах. Почему там не применяется метод отжига, или другие оптимизирующие алгоритмы? Там применяется минимакс + эвристики! Вот из чего надо исходить. А почему так — понимаете?
Если да, то это как раз то, что делалось в Rosseta@home и я бежал от этого как от огня :)
Выше я описал две целевые функции
1. locScore = (r1 + r2 + r3 + a1 + a2 + a3)
2. if (maxR > maxA) { locScore = maxR; } else { locScore = maxA; }
Знаете ли вы как их объединить в одну? Т.е. скажем если 5 раз применяли первую целевую функцию, затем 5 раз применяли вторую и получили некий результат (понижение «энергии»). То надо, чтобы функция полученная после объединения, после ее применения 5 раз давала бы такой же результат как если применять первую и вторую по очереди. Возможно ли это?
Собственно подстановка (1) в (2) — есть процедура тривиальная. В чем проблема?
То, что в итоге получается нелинейная (недифференцируемая?) функция итак понятно, если в этом загвоздка. Ну та и аналитически ее решать необязательно.
Вы не пробовали объединить усилия с этим проектом distributed.ru/forum/?t=1067&p=47?
Очень хотелось бы поучаствовать в отечественном прикладном проекте распределенных вычислений.
Очень хотелось бы поучаствовать в отечественном прикладном проекте распределенных вычислений.
«Возможно ли это?» А если добавить еще одно условие:
if (maxR > maxA) { locScore = maxR; } else { locScore = maxA; }
if (locScore < [какое-то значение]) locScore = (r1 + r2 + r3 + a1 + a2 + a3)
[какое-то значение] что-то вроде (120+120+120+160+160+160)/2
if (maxR > maxA) { locScore = maxR; } else { locScore = maxA; }
if (locScore < [какое-то значение]) locScore = (r1 + r2 + r3 + a1 + a2 + a3)
[какое-то значение] что-то вроде (120+120+120+160+160+160)/2
(120+120+120+160+160+160)/12
Это типа до такого-то расстояния одна целевая функция, а потом другая? Это не совсем то, что хотелось бы.
Еще можно складывать квадраты расстояний и углов, это обобщенные координаты?
Даже не так, почему вы складываете просто расстояния и углы, а не их квадраты, они же вроде ортогональные?
а зачем делать лишние умножение? В чем разница?
Ладно, вы меня подловили, я думаю, что энергия пропорциональна квадрату. Разница: 1^2+1^2<2^2+0^2. Т.е. если есть одно большое расстояние и несколько маленьких, то функция будет больше, чем в случае, когда расстояние «распределено» поровну между переменными. А это ближе к вашей второй целевой функции, чем первая. Другими словами, нечто промежуточное между первой и второй функциями.
«Это типа до такого-то расстояния одна целевая функция, а потом другая?». Нет, это я так понял слова «Каждый из вариантов хорош по своему. Для начала сворачивания хорош второй. После наличия уже грубой структуры может пригодится и первый.». Прежде всего, моя функция не совсем корректна, так как не монотонная. При достижении порога [какое-то значение], плохой вариант(тот, для которого неверно второе условие) «отскакивает». После чего рассматриваются другие варианты. Если после его оптимизации он снова достигает порога, но второе условие верно, то он проходит. Таким образом, да все значения меньше порога — это сумма, но кроме того, они получены после рассмотрения плохих вариантов, т.е. формирования грубой структуры.
Зарегистрируйтесь на Хабре, чтобы оставить комментарий
Часть №4. Биовычисления по сворачиванию. Как оценить ход сворачивания односпиральной РНК?