Генетический алгоритм. Как делается жизнь?

Question

[Дмитрий Башинский]

Всем привет. Сегодня задавал вопросы получил быстро ответы, очень приятный форум.

Расскажу немного о себе
Я программирую уже около 5 лет 3 года их них на C# мне всегда нравилось делать ботов, но последнее время много смотрю о обучении машин и наткнулся на генетический алгоритм.
Я разобрался и реализовал генетический алгоритм который собирает указанное слово, но больше похоже на подбор с оценкой, но не суть.
Я наткнулся на такое https://www.youtube.com/watch?v=SfEZSyvbj2w

И вроде мне все понятно как реализовано но не понятна одна мелочь. У них 64 слота действий, как я понял действия делаются по порядку и тут у меня возникли вопросы:
1. Если в мире все рандомно, а оно делает все по списку, выживать оно не научится, или каким образом выполняются команды?
2. Когда команды заканчиваются, список начинается заново? если да то тогда я тем более не пойму как они все же "учатся" ибо одни и те же действия в одном и том же порядке
3. Есть ли условия между условиями? Например у него есть команда "посмотри туда" эта команда по идее может вернуть нам новую команду в зависимости от того что "там" есть или это нарушит принцип генетического алгоритма.

Answer 1

[Иван Корюков]

1) да, рандомно, но теоретически существует такой алгоритм (последовательность команд), которая позволяет организму выживать как можно дольше в этом рандомном мире. Ну например: если сделать последовательность ходов такой, что траектория движения будет покрывать как можно большую площадь, и разбавить её операциями поедания с разных сторон, то шансы организма на выживание гораздо выше чем у организма, который ходит в одну сторону и ожидает пищу только слева.
2) Да, последовательность команд зациклена. Дело в том, что обучение производит не организм, а... программа, которая отбирает те организмы, которые выжили. Малая часть выбранных и размноженных организмов подвергается мутации, т.е. их последовательность команд изменяется. если изменение удачное, то этот организм, вероятно, попадёт в следующее поколение, и организмов с такой мутацией станет больше. Повторяя это много раз можно найти оптимальный алгоритм поведения бота. Скорее всего он будет коррелировать с алгоритмом генерации мира.
3) генетическое программирование это... не конкретный алгоритм, это скорее идея, которая имеет обязательные для выполнения шаги, но каждый шаг можно реализовать совершенно различными способами. Условия и команды здесь могут быть какими угодно, это всего лишь описание среды в которой производится оптимизация.

Comments

[Дмитрий Башинский]

спасибо!

Answer 2

[evgeniy_lm]

Генетический алгоритм по сути это и есть подбор с оценкой, но в отличии от тупого перебора создаются несколько наборов данных (популяция) из них выбираются те у которых значение целевой функции лучшие. Затем из выбранных наборов данных (особей) формируются новые особи путем скрещивания, объединения частей данных (генов). Все повторяется до тех пор пока не будет достигнут результат. Так же каждое новое поколение должно мутировать, необходимо вносить изменения в гены случайным образом. Это необходимо чтобы не возникло вырождение популяции т.е. может возникнуть ситуация когда следующее поколение будет хуже предыдущего

Твое видео не очень хорошо иллюстрирует суть ГА. Это видео более грамотное

Answer 3

[xdgadd]

Это почти нейронка. Представьте, что каждое число в ячейке - это коэффициент 64х мерной прямой. По сути, здесь происходит аппроксимация функции оптимального поведения с помощью генетических алгоритмов.

Answer 4

[SolidMinus]

генетические алгоритмы - это не алгоритмы обучения, это алгоритмы оптимизации. Наподобии градиентного спуска, адама и прочих. И, к слову, один из самых неэффективных. Он просто очень красиво показывает эволюцию и не более. Хотите заниматься машинным обучением - почитайте про стохастический градиентный спуск, градиентный бустинг, рандомные леса, и SVM-машины. Ну и про нейронки почитайте. но только после всего этого

Comments

[⚡ Kotobotov ⚡]

что значит не эффективный? Чтоб 2+2 посчитать не эффективный.
Они для решения задач в которых нет никакого спуска, когда например пространство возможностей условно бесконечное и ты не можешь оценить например влияние какого-то параметра на результат (выбрать оптимальный шаг в спуске).
при таком раскладе - весь твой "градиентный" спуск сам сведется к генетическому алгориму, и даже вопросов не будет эффективно ли это или нет, потому как других вариантов решения и не будет.

[SolidMinus]

дима кубитский, Я это и имел ввиду. Суть в том, что это слишком частный случай. Ты сам написал:

"-> при таком раскладе - весь твой "градиентный" спуск сам сведется к генетическому алгориму"