Генетический алгоритм выбора и кроссовера

Question

Я проводил некоторые исследования по генетическим алгоритмам для проекта в моем классе ai, но меня немного смущает то, что кажется традиционным алгоритмом.

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

Также кроссовер меня смущает. Он случайным образом выбирает точки каждый раз, чтобы склеить родительскую информацию. Но для кроссоверов, по-видимому, имеет больше смысла меняться на основе предыдущей информации. Если известно, что строка хромосомы имеет хорошие значения до некоторой точки, кроссовер все еще может быть случайным, но не в диапазоне хорошей части в строке.

Есть мысли?

Answer 1

Выбор

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

Как правило, чем сложнее проблема, тем больше таких локальных оптимумов . Отбор других людей в дополнение к лучшим поддерживает разнообразие населения: решения распределяются дальше в пространстве поиска, и если часть населения застряла в локальном оптимуме, другая часть населения все еще может прогрессировать.

Современные генетические алгоритмы обычно посвящают много усилий сохранению разнообразия популяции для предотвращения преждевременной конвергенции . Одним из методов для этого является совместное использование фитнеса . Другой простой способ сделать это - разделить популяцию на разные виды, чтобы особи разных видов не могли (или только редко) могли размножаться друг с другом.

Crossover

Кроссовер пытается распределить хорошие части генома среди людей, которые возникли в результате мутации. Было бы неплохо, если бы можно было просто поменять хорошие части генома, и это было предпринято; Например, вы можете посмотреть на каждый ген и измерить среднюю пригодность людей, обладающих этим геном.

Однако есть две основные проблемы:

1. Это вычислительно дорого.

2. В геноме могут быть взаимозависимости. Может быть, ген A выглядит действительно хорошо в соответствии с вашей метрикой, а ген B - нет, поэтому вы не обращаете на это внимания. В действительности, возможно, что ген А на самом деле не работает без присутствия гена В.

Answer 2

Не выбираем лучшее =>, потому что иначе вы очень можете застрять на локальном оптимуме. По той же причине, выбор рулетки - вещь из прошлого, и крутые дети используют ранговый отбор (сортировка потомков по пригодности и сохранение, скажем 1/10 из лучших, отметьте «стратегии развития»). Выбор рулетки, то есть пропорциональный отбор по фитнесу, не работает хорошо, если шкала фитнеса не очень регулярна, и на практике она никогда регулярна.

Crossover => Стратегии Evolution просто используют мутацию и вполне подходят без кроссовера. Кроссовер предполагает, что ваша целевая функция может быть аккуратно разложена на несколько битов, которые найдет кроссовер. В большинстве генотипов различные части генотипа связаны очень нелинейным образом. Это очень наивно и верно только для игрушечных задач. Если у вас нет серьезных оснований использовать оператор кроссовера, просто обойтись без него, бритвой Оккама и всем прочим.

Answer 3

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

Answer 4

А как насчет замены видов после кроссовера?

Я выбираю виды для размножения методом выбора колеса рулетки.Мой коэффициент кроссовера составляет 0,7 (70%), но я на самом деле не знаю, что это значит.Означает ли это, что я выбираю 70 пар родителей, скрещиваю их и заменяю две худшие в пуле новыми двойками?Или это означает, что я выбираю 70/2 = 35 пар родителей, скрещиваю их и заменяю их худшими?

Я действительно не знаю, какими видами вы заменяете новых детей?Что если фитнес детей хуже фитнеса худших двоих в бассейне?Пожалуйста, объясните процесс замены в методе пропорционального выбора на колесо рулетки.

Answer 5

Я думаю, что DataWraith достаточно хорошо ответили на вопрос.Что касается кроссовера, я просто добавлю, что Джон Холланд утверждает, что GA работает неявно , вычисляя приспособленность каждой подстроки хромосомы ("схема"), используя рандомизированный кроссовер и выбор, вместо того, чтобы вычислять его явно,быть чрезвычайно трудоемким (как сказал DataWraith).Голландия называет этот процесс «неявным параллелизмом».

-Ted