kipar
Генетические алгоритмы это чисто математическая отрасль. Смайл (который c ними выигрывал на AI Cup) писал что там и скрещивание не нужно, только мутации и отбор.
Это уже не генетические алгоритмы, а эволюционная стратегия - другой стек методов, они тоже как и ГА относятся к эволюционному исчислению, но ключевое отличие ГА от прочих эволюционных - именно в наличии кроссовера - он ускоряет сходимость, правда повышает вероятность преждевременной сходимости.
tac
ГА будет ошибаться большие число раз, чем если сделать полный перебор ..
Увы и ах, теорема схемы и теоремой прайса (наверное так переводиться, не путать с теоремой Прайса!) говорят об обратном - они обладаю глобальной сходимостью за конечный интервал времени, более короткий (частота "правильных" блоков растет в геометрической прогрессии) нежели чем перебор. Это математические теоремы, которые в отличии от Вашего тезиса имеют строгое математическое доказательство (недавно еще и обновились). Со строгим формальным выводом проблемы только у гипотезы строительных блоков имеются (ибо формулировка у неё не совсем точная).
В моей же статье был предложен подход, когда перебор во первых был дискретный с определенным шагом по углам поворотов. Потом перебираем все возможные повороты, скажем 100 аминокислот * 7 (атомов основной цепи аминокислоты, которые имеет смысл вращать) * 360 (дискретных градусов) = 252 000 попыток поворотов ... по сути это секунды ... аналог этому это обсуждаемые тут 64 варианта действий бота
О ужас! Если бы так пытались решать задачи глобального плейсмента и роутинга, то никаких intel i7 с двумя миллиардами транзисторов никогда не появилось, до сих пор бы разводился 286 процессор...
но в отличии от ГА мы не имеем нескольких ботов (кстати у него их тоже 64, вот откуда путаница) а он только один ... но даже в такой простой задаче как у него вычисления повторяются для каждого бота 64*64 = 4 096 и вот это умножаем на время, число ходов ботов до их смерти, ну где то в середине около 100 ходов (этого число плавает конкретно у него, но разумно было его бы этим числом ограничить, за меньшие число боты ничему не научатся, а за большие не станут умирать и будут просто жрать не находя лучших решений) , т.е. в этой игрушечной задачи 400 000 на одно поколение в среднем
Вычислений целевой функции (интегральная оценка энергии к концу раунда) у него 64 на одно поколение, т.е. на 3000 итераций у него приходиться всего 192000 вызовов целевой функции - очень неплохо, т.к. полное число решений его задачи составляет 64^64 - это число в котором больше 100 нолей (3.94e+115) если что.
я же сделав 252 000 в куда сложнейшем мире, сразу делаю отбор по функции пригодности, т.е. выбираю лучший из возможных поворотов РНК .... а ГА в той задаче только через 400 000 просчетов отбирает по своей функции пригодности (кто остался жив в среде) 8 ботов и начинает все заново
Что вокруг чего вращается? Если вращение происходит вокруг 7 молекул, то всего дискретных решений там меньше чем 10^18, ну эт почти на 100 порядков меньше, чем в примере с генетическим программированием. Если же звеньев все же куда больше, то:
Но даже молекула его не делает, она как бы знает путь, но откуда? чтобы знать как сворачиваться, она уже должна знать какой из поворотов предпочесть на каждом шаге. Гипотеза простая - она сворачивается по пути наибольшей энергетической минимизации.
Двигаемся по антиградиенту, пока он не станет равным 0 и будем Вам счастье. Это все градиентные методы так ВНЕЗАПНО работают - их море, известны давно (один из них носит имя Гаусса-Зейделя, другой Ньютона, самые супер-современные - имена математиков середины 20-го века), а самое главное - даже не надо изобретать велосипед: все есть в учебниках (Поляк, Самарский):
В моей же статье был предложен подход, когда перебор во первых был дискретный с определенным шагом по углам поворотов. Потом перебираем все возможные повороты, скажем 100 аминокислот * 7 (атомов основной цепи аминокислоты, которые имеет смысл вращать) * 360 (дискретных градусов) = 252 000 попыток поворотов
Тот же BFGS гарантирует локальную сверхлинейную скорость сходимости, так что для оптимизации квадратичной функции потребуется всего n-шагов, где n-размерность задачи. Если вы там крутите вокруг 7 молекул, то решение будет найдено за 7 итераций, если вокруг, ну я там не знаю, даже если звеньев таки много - 7*100, то 700 итераций...причем решение будет непрерывным, а не как у вас - натянули сову на глобус - непрерывную задачу на дискретные перебор и радуйтесь 200к итерациям...гхм... А если уж взять метод Ньютона, то у того вообще квадратичная сходимость - еще быстрее чем BFGS...ну я даже хз
Вообще не понятна ценность и актуальность этого - представить фолдинг, как задачу оптимизации - тривиальная, любой студент после численных и вычметодов может сделать. А вот симуляция временной эволюции системы взаимодействующих атомов с учетом всех факторов - это да, это долго и тяжко.
0iStalker
Внезапные параллели...https://gamedev.ru/flame/forum/?id=235459 (где-то в районе 18 - 20 минуты)
А! Оганов - очень крутой дядька, разработал программу USPEX, которую используют для предсказания кристаллических структур - там как раз используются эволюционные алгоритмы для этого. Вообще это очень нетривиальная задача - раньше с предсказанием структур кристаллов были серьезные проблемы - даже для самых простых не получалось предсказать :-)
А привет кого-то – это вообще как?
Тема в архиве.