Генетический алгоритм
Женя19 февраля 2006Data Mining3 комментария
Женя19 февраля 2006Data Mining3 комментария
Хочу применить ГА для оптимизации функции по 50 параметрам. Какой размер популяции наилучшим образом подходил-бы, в первую очередь необходимо получить приемлимое решение, скорость значения не имеет. С вероятностью возникновения мутации, кроссовера и инверсии в общем определился, но если кто-то подскажет дополнительно - буду благодарен. К сожалению опыта применения ГА у меня нет, поэтому буду рад любой информации, спасибо.
Комментарии
Войдите или зарегистрируйтесь для добавления комментариев.
Qai
20 февраля 2006 05:04 Ссылка
Обновлён
Размер популяции существенно зависит от рассматриваемой задачи. Чем сложнее задача, тем больше должно быть особей в популяции. По своему опыту могу сказать, что для *настроенного* генетического алгоритма, как правило, хватает 100-150 особей. В ряде исследований по поиску оптимальных значений параметров ГА также рекомендуется выбирать популяцию в 100-200 особей, но лично я против идеи о существовании таких оптимальных значений, т.к. задачи и схемы эволюционного поиска бывают разные, да и сами условия поиска в процессе работы ГА все время меняются. Попробуйте начать с популяции в 50 особей, а дальше ориентируйтесь на результаты экспериментов.
По поводу вероятностей операторов. На счет инверсии ничего сказать не могу (не использовал), хотя в литературе ее вероятность рекомендуют выбирать малой. Вероятность кроссовера рекомендуют выбирать в диапазоне 0,6 - 0,9 (т.е. от 60% до 90% потомков создаются в результате скрещивания, а остальные являются копиями родительских особей). Хотя где-то читал, что современные тренды таковы, что вероятность кроссовера часто устанавливают в 1. Для оператора мутации вероятность зависит от того, как делается мутация. Если каждый разряд мутирует независимо, то достаточно неплохой вариант, когда Pm = 1/N, где N -- длина хромосомы в битах (подразумевается бинарное кодирование, в случае вещественного кодирования появляются дополнительные параметры), тогда, в среднем, каждая хромосома будет мутировать один раз.
При настройке параметров важно соблюсти баланс между поисковыми способностями ГА и использованием уже найденных решений (т.н. соотношение exploration-exploitation). В любом случае, окончательный ответ на вопрос о выборе значений параметров можно получить, скорее всего, только экспериментально.
Спасибо, именно это я и хотел узнать, у меня вычисление целевой функции занимает 1-2 секунды, поэтому сильно не поэкспериментирую, я хотел сразу попасть по-ближе к нужным параметрам. Еще вопрос, имеет ли особое значение метод отбора родительских хромосом, я использую компоненту с этого сайта - там турнирный метод.
Имеет, именно благодаря селекции и возможен направленный поиск (без нее ГА будет представлять собой весьма извращенную форму случайного поиска). Сам по себе турнирный отбор очень гибок, изменяя размер турнира, можно управлять давлением селекции: чем больше размер, тем более "строгий" отбор. Как правило, большее давление селекции положительно влияет на скорость работы ГА, однако есть риск потерять разнообразие особей в популяции, что может привести к преждевременной сходимости алгоритма.