Программирование игр, создание игрового движка, OpenGL, DirectX, физика, форум
GameDev.ru / Программирование / Форум / Генетические алгоритмы в разработке игр. (комментарии) (4 стр)

Генетические алгоритмы в разработке игр. (комментарии) (4 стр)

Страницы: 1 2 3 4 5 Следующая »
DelfigamerПостоялецwww29 мар. 201816:55#45
Fantarg
> Эти 64 ячейки - они блокированы
Изображение
tacПостоялецwww29 мар. 201822:35#46
Delfigamer
> Вы жопой слушаете, или только притворяетесь?
и что там в той фразе? чем они противоречат тому, что я сказал?
tacПостоялецwww29 мар. 201822:36#47
exchg
> Тот же это в смысле полный перебор всех вариантов?
да, только в другом порядке ... покрайней мере, есть такое объективное сомнение ... и еще надо доказать, что это не так.
exchg
> И при этом гарантированно возвращает самый оптимальный результат?
и при этом как раз ничего гарантированно не возвращает

Правка: 29 мар. 2018 22:41

tacПостоялецwww29 мар. 201822:40#48
kipar
> Иначе выглядит как "мы применим здесь ГА(\нейронку\диплернинг\подставить
> слово) потому что можем, и вот они за 100500 поколений находят не совсем
> провальное решение, мы молодцы".
вот и кипар говорит, то о чем я ... приятно видеть тут (на форуме) разумные слова
tacПостоялецwww29 мар. 201823:08#49
exchg
> Применительно к поиску в полях решений с размерами в которых актуально
> применять ГА, полный перебор неактуален в силу времени

мы говорим, не совсем о том полном переборе .. Я покажу это на задаче на счет которой у меня опубликовано пара научных статей в реферируемых журналах.

если на пальцах, то там показано как нить РНК (белок) сворачивается в 3D глобулу. Парадокс Левенталя говорит нам о том как раз, что если просчитывать все возможные варианты различных состояний, то это время займет у молекулы (не у компьютера!!) больше времени жизни вселенной. Что очевидно показывает якобы не применимость тут полного перебора. Но перебора именно ВСЕХ состояний. Но даже молекула его не делает, она как бы знает путь, но откуда? чтобы знать как сворачиваться, она уже должна знать какой из поворотов предпочесть на каждом шаге. Гипотеза простая - она сворачивается по пути наибольшей энергетической минимизации.

В моей же статье был предложен подход, когда перебор во первых был дискретный с определенным шагом по углам поворотов. Потом перебираем все возможные повороты, скажем 100 аминокислот * 7 (атомов основной цепи аминокислоты, которые имеет смысл вращать) * 360 (дискретных градусов) = 252 000 попыток поворотов ... по сути это секунды ... аналог этому это обсуждаемые тут 64 варианта действий бота

но в отличии от ГА мы не имеем нескольких ботов (кстати у него их тоже 64, вот откуда путаница) а он только один ... но даже в такой простой задаче как у него вычисления повторяются для каждого бота 64*64 = 4 096 и вот это умножаем на время, число ходов ботов до их смерти, ну где то в середине около 100 ходов (этого число плавает конкретно у него, но разумно было его бы этим числом ограничить, за меньшие число боты ничему не научатся, а за большие не станут умирать и будут просто жрать не находя лучших решений) , т.е. в этой игрушечной задачи 400 000 на одно поколение в среднем

я же сделав 252 000 в куда сложнейшем мире, сразу делаю отбор по функции пригодности, т.е. выбираю лучший из возможных поворотов РНК .... а ГА в той задаче только через 400 000 просчетов отбирает по своей функции пригодности (кто остался жив в среде) 8 ботов и начинает все заново

я же считаю следующий шаг уже из лучшего возможного положения ... таким образом, делая особый полный перебор с отбором по функции пригодности, я делаю меньше расчетов в наверное сложнейшей вычислительной задачи биоинформатики, чем ГА в студенческой демонстрационной задачке

и чей перебор круче? ))

конечно, это ужасное огрубление ... так то надо читать статьи ... и там уже можно говорить о проблеме локальных минимумов, но в ГА они тоже есть ... ну т.е. дальше уже не детский разговор

поэтому надо не в лоб решать задачу, как там сделано с перебором по ГА ... а найти целевую функцию, понять какие законы в мире. Если еда разбрасывается случайно, то чего мы хотим от ботов? Чтобы они случайно искали? Ну вот они и бегают совершенно случайно и натыкаются на еду ... какая же это логичная программа действий? Вот если бы задачу ставить пройти по такому пути, который короче или дает меньше повреждений ... то вот тут как то ГА использовать не хотят? ответьте почему? (если внимательно меня читали, то я уже сам написал выше)

Правка: 29 мар. 2018 23:40

DelfigamerПостоялецwww29 мар. 201823:53#50
tac
> и что там в той фразе? чем они противоречат тому, что я сказал?
tac
> ну нет этого там, там нигде не говорится про последовательность команд
Ролик
> Именно программа - и есть их геном, который будет изменяться в процессе
> эволюции. ДНК бота - это 64 ячейки, замкнутые по кругу. Ячейки
> заполняются числами от 0 до 63, каждое число - это команда.
Какое слово тебе не понятно?

Правка: 29 мар. 2018 23:54

exchgПостоялецwww30 мар. 20182:10#51
tac
> да, только в другом порядке ... покрайней мере, есть такое объективное сомнение
> ... и еще надо доказать, что это не так.
Не, в ГА перебор всех вариантов это частный случай. Который может не наступить как
в следствии большого поля поиска так и в следствии застревания в локальном минимуме.

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

> мы говорим, не совсем о том полном переборе ..
Не ну конечно я допускаю отбрасывание заведомо неподходящих решений и т.д.
По поводу статьи я ничего не понимаю в этой предметной области, поэтому мне сложно
что-то оценить. Но глупо было сравнивать жизнь ботов (в конкретно этом видео) с реальными
задачами.  У меня на практике например задачи в которых размер поля решений порядка
1500^900.

> поэтому надо не в лоб решать задачу, как там сделано с перебором по ГА ... а
> найти целевую функцию, понять какие законы в мире.
Ну да, но как уже указывали выше - это все условности обучающего материала. Хотя,
сказать честно, это просто вводная статья в мир ГА и ее вообще рассматривать серьезно не
имеет смысла. Потому, что если взглянуть на реальный мир ГА, то для входа в область нужно
прочитать и осилить хотя бы 1-2к страниц текстов по ГА. И это только выжимки.

> Если еда разбрасывается случайно, то чего мы хотим от ботов? Чтобы они случайно
> искали? Ну вот они и бегают совершенно случайно и натыкаются на еду ... какая
> же это логичная программа действий?
Не, ну тут можно например сформулировать и так - мы хотим чтобы боты выработали
оптимальную стратегию поиска пищи в условиях неопределенности. ))

> Вот если бы задачу ставить пройти по такому пути, который короче или дает
> меньше повреждений ... то вот тут как то ГА использовать не хотят? ответьте
> почему?
Хотят и используют, причем очень успешно. Например http://www.oracle.com/us/products/applications/routing-cloud-serv… e-2413009.pdf
построено на генетике. Если разговор за учебные материалы, то я не знаю. Наверно у
авторов фантазии не хватает.

qGrinПостоялецwww25 апр. 20188:24#52
KKH
> Странная статья. Мы решаем проблему одним алгоритмом, но знаем результат по
> другим причинам. И сравниваем то что получилось с тем, что должно получиться.
> Зачем эти хождения вокруг да около ?
Для ситуаций когда мы знаем точку А, мы знаем точку Б, но мы не знаем оптимальный путь из А в Б.
Скажем АИ для автогонок мог быть построен таким способом.

Что почитать для начала по этой теме? Поближе к геймдеву и АИ.

Правка: 25 апр. 2018 8:26

0iStalkerМодераторwww27 апр. 20188:36#53
tac
> Но перебора именно ВСЕХ состояний. Но даже молекула его не делает, она как бы
> знает путь, но откуда? чтобы знать как сворачиваться, она уже должна знать
> какой из поворотов предпочесть на каждом шаге. Гипотеза простая - она
> сворачивается по пути наибольшей энергетической минимизации.

Внезапные параллели...https://gamedev.ru/flame/forum/?id=235459  (где-то в районе 18 - 20 минуты)

Правка: 27 апр. 2018 8:37

DelfigamerПостоялецwww27 апр. 201813:51#54
tac
> Но перебора именно ВСЕХ состояний. Но даже молекула его не делает, она как бы
> знает путь, но откуда? чтобы знать как сворачиваться, она уже должна знать
> какой из поворотов предпочесть на каждом шаге. Гипотеза простая - она
> сворачивается по пути наибольшей энергетической минимизации.
Я встречал объяснение, что молекула именно что перебирает ВСЕ состояния, только делает это не последовательно, а одновременно, а неоптимальные состояния впоследствии опускаются до более оптимальных, так что в итоге из ВСЕХ состояний остаётся только несколько стабильных.
kiparПостоялецwww27 апр. 201814:55#55
Delfigamer
квантовая суперпозиция на уровне белковых молекул? Звучит как новое слово в физике.
DelfigamerПостоялецwww27 апр. 201815:42#56
kipar
Вовсе не новое, белки с самого начала квантовой физикой и считали, потому что если держать атомы за шарики, то почему-то неправильно молекула сворачивается.
Вон, даже парень с лекции рассказывает, что они кристаллы не каким-нибудь физиксом считают, а по уравнению, как положено.
kiparПостоялецwww28 апр. 20182:26#57
Delfigamer
То как считали ладно. Но белковая молекула макрообъект, для них суперпозиция несколько... невероятна.
DelfigamerПостоялецwww28 апр. 201811:08#58
Molecular dynamics simulations of biomolecules typically treat the molecule of interest and surrounding solvent as classical particles interacting through an empirically derived and computationally tractable potential energy function (the ‘force field’). The system’s dynamics propagate through time by means of numerical integration of Hamilton’s equations of motion, typically discretized into steps of the order of femtoseconds.

Окей, видимо, это было не совсем правильное объяснение.
CrazyFizikПостоялецwww19 мая 20183:52#59
emptiness_rain
При увеличении количества поколений до 500 - билд получается всегда один и тот же.
Поэтому для балансировки важно правильно подобрать количество итераций.

Это не баг - это фича алгоритма - он так и должен работать и итоге нашел глобальный оптимум: билд который будет надирать задницы всем остальным билдам. Как раз типичное время сходимости для GA в большинстве задач - это порядка 300-600 поколений (но в ряде задач могут и доходить нескольких тысяч), т.е. тут проблема не в количестве итераций, а в том, что сама модель боя манчкино-уязвимая и надо её менять, а вместо этого вы просто используйте решение которое не сошлось.
Если хотите получит множество локальных решений, тот тут в помощь градиентные методы - метод покоординатного спуска, BFGS и т.д. - несколько запусков оптимизации с разных точек (не менее чем n+1, но если хотите совсем по хардкору, то n^2) - это самое простое, а так то для многоэкстремальной оптимизации есть свои специальные методы.

Другие советы, это:
- использование нишевания - канонические ГА устроены так, что в них вся популяция в итоге сходиться к ОДНОМУ оптимальному решению, такова теорема Схема и строительных блоков, если хотите найти несколько решений, то юзайте нишевание или субпопуляции
- оценивайте не по одному критерию, а по нескольким, для этого разработан Non-dominated sorting genetic algorithm, сейчас уже существует 3-я версия. На выходе будет получен фронт Парето - весь набор оптимальных решений для многокритериальной задачи оптимизации (но для этого критерии должны друг другу противоречить!)
- вообще схема мутации и кроссовера далеко не самая эффективная, для непрерывных моделей применяются немного другие приемы (SBX, BLX-alpha, polinomial muatation, gaussian muatation и т.д. и т.п.), хороший обзор приемов можно найти в статье Tackling Real-Coded Genetic Algorithm, там правда не все современные перечислены. Но вообще насколько я знаю, теорема схем работает только для бинарного/дискретного представления генотипа, а для реальных чисел сходимость, увы не доказана (тут в помощь Больцмановский отжиг, только от медленный...очень...)

Правка: 19 мая 2018 5:36

Страницы: 1 2 3 4 5 Следующая »

/ Форум / Программирование игр / Общее

2001—2018 © GameDev.ru — Разработка игр