Алгоритмы, методы, исходники / Форум

Алгоритмы, методы, исходники / Форум (http://forum.algolist.ru/)
-   Искусственный интеллект, нейронные сети (http://forum.algolist.ru/algorithm-artificial-neural/)
-   -   Параметры генетических алгоритмов (http://forum.algolist.ru/algorithm-artificial-neural/1607-parametry-geneticheskih-algoritmov.html)

Adavrorin 30.01.2009 02:45

Параметры генетических алгоритмов
 
Здравствуйте, я недавно увлёкся ГА и у меня возникли некоторые вопросы.

1) Почему ГА реализуются на двоичных векторах? Понятно, что это оптимизирует вычисления. С другой стороны, программисту гораздо удобнее не кодировать потенциальное решение через нули и единицы, а пользоваться произвольным набором "координат".
2) Как определяется количество "родителей" для кроссинговера? В англоязычной Википедии написано, что большее число "родителей" даёт лучшие результаты. Есть ли здесь какой-либо алгоритм определения оптимума?
3) Аналогично, как определяется вероятность мутации и количество мутировавших хромосом?
4) Максимальная численность популяции ограничена, или задаётся какой-либо функцией (например, от номера поколения или среднего значения функции приспособленности)?
Заранее спасибо за ответы.

Роман Грицуляк 29.05.2009 01:21

Ответ
 
Отвечаю по порядку:
1) Не всегда, бывают даже непрерывные генетические алгоритмы.
2) Больше - быстрее сходится. Тут довольно четко.
3) Исключительно в зависимости от задачи.
Зачастую мутация дает лучшие результаты (более быстрый поиск решения) чем скрещивание.
4) Опять же от задачи и вычислительных ресурсов зависит. Больше популяция - более полное исследование пространства, более точный ответ. Но:
Более медленное исследование.

Успехов!

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

Цитата:

Сообщение от Adavrorin (Сообщение 6041)
Здравствуйте, я недавно увлёкся ГА и у меня возникли некоторые вопросы.

1) Почему ГА реализуются на двоичных векторах? Понятно, что это оптимизирует вычисления. С другой стороны, программисту гораздо удобнее не кодировать потенциальное решение через нули и единицы, а пользоваться произвольным набором "координат".
2) Как определяется количество "родителей" для кроссинговера? В англоязычной Википедии написано, что большее число "родителей" даёт лучшие результаты. Есть ли здесь какой-либо алгоритм определения оптимума?
3) Аналогично, как определяется вероятность мутации и количество мутировавших хромосом?
4) Максимальная численность популяции ограничена, или задаётся какой-либо функцией (например, от номера поколения или среднего значения функции приспособленности)?
Заранее спасибо за ответы.


Adavrorin 24.10.2009 19:24

Большое спасибо, что ответили. Сейчас, честно говоря, совершенно случайно заглянул.

1) Хорошо, но есть ли какие-нибудь критерии?
Например, пусть в задаче коммивояжёра n городов, причём n - не степень 2. Тогда, в случае двоичного кодирования, разным городам будет соответствовать разное количество комбинаций. Соответственно, города с большим количеством комбинаций получат преимущество и при кроссинговере и при мутации. А это, в свою очередь, замедлит сходимость. Можно ли в таком случае сравнить сходимости бинарного ГА и n-мерного?
2)Т.е. если взять за родителей всю популяцию, то сходимость увеличится?
3), 4) -всё понял.


Часовой пояс GMT +4, время: 02:26.