Хабр Курсы для всех
РЕКЛАМА
Практикум, Хекслет, SkyPro, авторские курсы — собрали всех и попросили скидки. Осталось выбрать!
Хабр доступен 24/7 благодаря поддержке друзей
Комментарии 15
Интересный разбор, как-то игрался после видео на ютубе с этим симулятором, который почти тоже самое делает
Мне кажется, что можно добавить шанс выйти из локальных максимумов, если не ограничивать мутации жёстко каким-то интервалом. То есть чтобы функция mutate с небольшим шансом могла привести к очень большим изменениям. Если, например, вместо Random.Range() в пределах (-0.1, 0.1) использовать нормальное распределение, и вместо выбор случайной ноги мутировать каждую с шансом 0.5. Тогда если мы решаем задачу, где непонятно какие лучше взять начальные условия, то можно надолго её запустить и ждать пока эволюция выйдет из локального максимума
Мне кажется, что можно добавить шанс выйти из локальных максимумов, если не ограничивать мутации жёстко каким-то интервалом. То есть чтобы функция mutate с небольшим шансом могла привести к очень большим изменениям. Если, например, вместо Random.Range() в пределах (-0.1, 0.1) использовать нормальное распределение, и вместо выбор случайной ноги мутировать каждую с шансом 0.5. Тогда если мы решаем задачу, где непонятно какие лучше взять начальные условия, то можно надолго её запустить и ждать пока эволюция выйдет из локального максимума
Никогда не выйдет из локального максимума, все вариативные гены будут только у родственников элиты, генов элиты там будет много, но с посредственным реузльтатом и большой смертностью, фактически они не будут эволюционировать, а будут стрирать свои вариативные гены в потомках, то есть потомок двух метисов будет рождать клона элиты, процесс будет идти лавинообразно и никакие случайные мутации никогда не вытолкнут из этого локального минимума, потому что надо будет заменить 60 процентов генома элиты, а потом выдержать несколько поколений с чудовищной смертностью и давлением доминантных генов, проще говоря, можно было пройти мимо этого локального максимума, но не через него. Даже внедрение полностью случайного набора ген на весь геном не спасает положение, они просто дохнут и их потомки тоже их очень жёско вытесняют хорошо приспособленные особи. надо не просто вариативные гены, а их сохранение на протяжении поколений, это могут сделать только хорошо приспособленные особи. Фактически начинать нужно было с начала или принципы такого ГА слишком примитивны, выбирайте сами. В кратце, обычная модель ГА, не поощеряет параллельные ветки, они ломают геномы друг друга слишком сильно.
Интересно, а если добавить «скрещивание» особей, у которых приспособленность максимальна (топ — элита популяции). Ускорится схождение?
Да, я тоже залогинился, чтобы задать этот вопрос. Почему не применяется «кроссинговер»? Например, обмен значениями случайных параметров.
Ускорится поиск локального максимума. Фактически это суперигнорирование эволюции вида, то есть, эволюция индивидуума ускоряется, а эволюция вида замедляется. А если вид не эволюционен, то малейшее усложнение условий, и вид или вымирает или становится очень плохо приспособленным, так что проще заново начать поиск, чем использовать существующие гены.
То это будут уже генетические алгоритмы, а не эволюционные вычисления :-)
Да, кроссовер ускоряет сходимость и уменьшает случайные блуждания. Эффективность ГА выше эволюционных вычислений (к слову сказать ГА были разработаны в 70-ых, а эволюционные в 60-ых годах).
Ну тут появляются следующие проблемы:
1) Падает разнообразие популяции и в итоге вся популяция начинает через какое-то время окучивать один минимум.
2) Как следствие этого может случиться преждевременная сходимость.
С этим приходиться бороться предупреждая близкоросдтвенное скрещивание. Собственно применение элитизма поэтому очень спорная эвристика, так что элитных особей нужно сохранять небольшое количество и только для того что бы не потерять наилучшее (на текущий момент) решений, а скрещиваться желательно всем.
Еще есть один момент с кроссовером. На самом деле теорема схем работает только для дискретного (например, бинарного, собственно базовый алфавит человеческого генома состоит всего из 4-х букв) представления параметров модели. А вот когда они представлены реальными числами… ну тут все становится сложно: как с кроссовером, так и с мутациями, особенно с кроссовером.
Вообще, если функцию (которую надо оптимизировать) можно представить в явно виде (и целевая функция будет одна), то лучше использовать Simlated Annealing или CMA-ES — они дают хорошее и устойчивое решение. Если же функция задана неявно и точно вычислить функционал сложно или если оптимизация многокритериальная — тот тут все же лучше GA, таки они более универсальны и мощные.
Да, кроссовер ускоряет сходимость и уменьшает случайные блуждания. Эффективность ГА выше эволюционных вычислений (к слову сказать ГА были разработаны в 70-ых, а эволюционные в 60-ых годах).
Ну тут появляются следующие проблемы:
1) Падает разнообразие популяции и в итоге вся популяция начинает через какое-то время окучивать один минимум.
2) Как следствие этого может случиться преждевременная сходимость.
С этим приходиться бороться предупреждая близкоросдтвенное скрещивание. Собственно применение элитизма поэтому очень спорная эвристика, так что элитных особей нужно сохранять небольшое количество и только для того что бы не потерять наилучшее (на текущий момент) решений, а скрещиваться желательно всем.
Еще есть один момент с кроссовером. На самом деле теорема схем работает только для дискретного (например, бинарного, собственно базовый алфавит человеческого генома состоит всего из 4-х букв) представления параметров модели. А вот когда они представлены реальными числами… ну тут все становится сложно: как с кроссовером, так и с мутациями, особенно с кроссовером.
Вообще, если функцию (которую надо оптимизировать) можно представить в явно виде (и целевая функция будет одна), то лучше использовать Simlated Annealing или CMA-ES — они дают хорошее и устойчивое решение. Если же функция задана неявно и точно вычислить функционал сложно или если оптимизация многокритериальная — тот тут все же лучше GA, таки они более универсальны и мощные.
То это будут уже генетические алгоритмы, а не эволюционные вычисления :-)Не вводите в заблуждение: ГА это подкласс эволюционных вычислений, в большинстве случаев эволюция без генов, это очень примитвная и не интересная штука подобная случайному поиску, поэтому очень часто ставят знак равенства между ГА и ЭВ.
Цитирую:
Selection (отбор). После оценки существ лучшим из них разрешается репликация, позволяющая стать основой следующего поколения.У вас происходит передача генов потомкам, значит это ГА, кроссинговер не важен, это уже детали реализации, почкование там или три отца одна самка. В природе есть почкование, на что я уже указал, а кроме того есть виды, которые используют одновременно и бесполое разнможение и половое, что заранее отсекает возможные аргументы, что они не эволюционируют генетически.
Именно наличие операции кроссовера и отличает ГА от других разновидностей ЭВ. При этом сам кроссовер может быть самым разнообразным — как классическим, работающим с битовыми строками (с разными вариантами разрезания исходных генов), так и еще кучей разновидностей (непрерывным, пространственным, работающим с генами переменной длины как в генетическом программировании и т.п.) Главное, чтобы он умел объединять родительские гены в новые гены потомка, которые будут иметь что-то общее с обоими родителями.
Не вводите в заблуждение: ГА это подкласс эволюционных вычислений, в большинстве случаев эволюция без генов, это очень примитвная и не интересная штука подобная случайному поиску, поэтому очень часто ставят знак равенства между ГА и ЭВ.
Не ввожу, т.к. исторически все разновидности эволюционных алгоритмов развивались независимо друг от друга: Фогелем (эволюционное программирование), Холландом (генетические алгоритмы) и Швефелем с Реченбергом (эволюционная стратегия), а затем уже Коза (генетическое программирование). Все они имею разные наборы эвристик и разное метаматематическое обоснование.
И никто знак равенства между ЭВ и ГА, не ставит т.к. второе имеет вполне конкретные отличительные особенности и определение: обязательно наличие кроссовера, отбора и мутации, причем оператор кроссовера тут ключевой — нет кроссовера, нет генетических алгоритмов, а тех же мутаций может в принципе может и вообще не быть, а под первое можно притянуть практически что угодно — это как ставить знак равенства между рациональными и натуральными числами.
А во деталями реализации будет то как реализованы операторы кроссовера, мутации и селекции.
По сабжу тут вообще получается случайный поиск с выбором лучших особей из популяции параметры которых описаны реальными числами — по факту это эволюционная стратегия, совершенно другой класс алгоритмов. Ну на сегодня самым совершенным вариантом является The Covariance Matrix Adaptation Evolution Strategy, который с непрерывными моделями будет работать лучше чем Real-Coded Genetic Algorithm, по вполне понятным причинам — фигово теорема схем и гипотеза строительных блоков работают с реальными числами, только с дискретным представлением она и выполняется
Одним из первых моих приложений было эволюционное.
Было когда-то видео «Как эволюция работает на самом деле», к нему прилагались исходники, но, увы, ссылка вела в 404.
Я написал аналог на MonoGame, удивился как лагало и оставил до лучших времён. Но с тех пор эволюционное программирование меня привлекает. Хотя я и не понимаю, как его оптимизировать.
P.S. Скачал тот старый проект, не компилится. Вот такой я был.
Было когда-то видео «Как эволюция работает на самом деле», к нему прилагались исходники, но, увы, ссылка вела в 404.
Я написал аналог на MonoGame, удивился как лагало и оставил до лучших времён. Но с тех пор эволюционное программирование меня привлекает. Хотя я и не понимаю, как его оптимизировать.
P.S. Скачал тот старый проект, не компилится. Вот такой я был.
Построение генетических алгоритомов, на самом деле тривиально. Только строились они, для того что бы понять как эволюция функционирует в биологии, а в биологии есть два принципиальных момента, которые пропускают в генетических алгоритмах. В биологии за наиболее важные признаки отвечают сразу несколько ген, поэтому важный признак просто взять и исчезнуть не может, а следствием этого является эпигинетика, которая может деактивировать или активировать отдельные гены, при этом не испортив весь механизм, потому что отключение важного признака одним геном становится невозможным. Я бы сказал, что это кардиально изменяет принцип функционирования ГА и эволюции в частности.
У меня как-то была идея доработать алгоритмы на основе идей нашего эволюциониста Северцова. Но пока руки не доходят.
Эволюционные вычисления: учим табуретку ходить
Прочитал как «Эволюционные вычисления: учим табуретку кодить» :)
Зарегистрируйтесь на Хабре, чтобы оставить комментарий
Эволюционные вычисления: учим табуретку ходить