Зачем вам нужно масштабирование в генетических алгоритмах?

Question

Чтение книги «Генетические алгоритмы» Дэвида Э. Голдберга, он упоминает масштабирование пригодности в генетических алгоритмах.

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

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

Answer 1

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

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

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

Answer 2

@ Ответ sgvd дает действительные баллы, но я хотел бы подробнее остановиться.

Прежде всего, нам нужно определить, что означает фактическое масштабирование. Если это означает просто умножение пригодности на какой-то фактор, то это делает не изменить отношения в населении - если лучший индивидуум имел в 10 раз более высокий фитнес, чем худший, после такого умножения это по-прежнему верно (если вы не умножаетесь на ноль что не имеет никакого реального смысла). Таким образом, гораздо более разумное масштабирование пригодности является аффинным преобразованием фитнес значений:

scaled(f) = a * f + b 

т.е. значения умножаются на некотором числе и смещения на другое число, вверх или вниз.

Фитнес-масштабирование имеет смысл только с определенными типами стратегий выбора, а именно теми, где вероятность выбора пропорциональна пригодности физических лиц .

Фитнес скейлинг играет, по сути, два ролей.Первый из них просто практичен - если вы хотите, чтобы вероятность была пропорциональна фитнесу, вам нужно, чтобы фитнес был положительным. Итак, если ваше сырое значение пригодности может быть отрицательным (но ограничено снизу), вы можете настроить его, чтобы вы могли вычислять вероятности из него. Пример: если ваш фитнес дает значения из диапазона [-10, 10], вы можете просто добавить 10 к значениям, чтобы получить все положительные значения.

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

Предположим, что ваши исходные значения пригодности дают значения из диапазона [0, 100]. Если бы вы оставили это таким образом, у худших людей была бы нулевая вероятность выбора, а лучшие из них имели бы до 100 раз более высокую вероятность, чем самые худшие (исключая действительно худшие). Однако давайте установим масштабные коэффициенты в a = 1/2, b = 50. Затем диапазон преобразуется в [50, 100]. И сразу, происходят две вещи:

1. Даже самые плохие люди имеют отличную от нуля вероятность быть выбранным.
2. Лучшие люди теперь только в 2 раза чаще выбираются, чем самые худшие.

Exploration против эксплуатации

Устанавливая коэффициенты масштабирования вы можете контролировать, будет ли алгоритм делать больше разведки над эксплуатацией и наоборот. Чем больше «сжато» значения будут после масштабирования, тем больше исследований будет сделано (поскольку вероятность того, что лучшие люди будут выбраны по сравнению с худшими, будет уменьшена). И наоборот, чем больше «расширенных» будут значениями, тем больше будет выполнено эксплуатация (потому что вероятность того, что лучшие люди будут выбраны по сравнению с худшими, будет увеличена).

Другие стратегии выбора

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

Рейтинга Выбор

Рейтинг выбор идентичен выбор колеса рулетки, но число вероятности являются производными от не являются исходными значениями пригодности. Вместо этого все население сортируется по исходным значениям пригодности, а ранг (т. Е. Позиция в отсортированном списке) - это число, из которого вы получаете вероятность выбора.

Это полностью устраняет несоответствие, когда есть один или два «больших» человека и множество «маленьких». Они будут просто оценены.

Выбор турнира

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

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

---

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

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