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

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

Страницы: 1 2 3 4
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
построено на генетике. Если разговор за учебные материалы, то я не знаю. Наверно у
авторов фантазии не хватает.

Страницы: 1 2 3 4

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

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