Добро пожаловать, гость
:: алгоритмы  и методы :: :: олимпиадные задачи :: :: связь :: :: о сайте :: :: форум ::

Форум работает в режиме архива, только для чтения и поиска.
Архив 2004 Архив 2007 Архив 2013

 
 
Опции темы Поиск в этой теме Опции просмотра
  #1  
Старый 30.01.2009, 02:45
Новичок

Отправить личное сообщение для Adavrorin Посмотреть профиль Найти все сообщения от Adavrorin
 
Регистрация: 30.01.2009
Сообщений: 2

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

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

 
Сообщений: n/a

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

Успехов!

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

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

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

Отправить личное сообщение для Adavrorin Посмотреть профиль Найти все сообщения от Adavrorin
 
Регистрация: 30.01.2009
Сообщений: 2

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

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


Опции темы Поиск в этой теме
Поиск в этой теме:

Расширенный поиск
Опции просмотра


Похожие темы
Тема Автор Раздел Ответов Последнее сообщение
Эффективность алгоритмов сортировки Andrey K Сортировка и поиск 10 12.12.2009 18:50
Объединение стохастических алгоритмов see Математические алгоритмы (другое) 0 29.08.2008 16:07
Автоматизированное составление расписаний с использованием генетических алгоритмов. GreatWizard Математические алгоритмы 1 28.04.2008 14:41
Российский конкурс алгоритмов Gribok Участие 0 15.12.2007 13:28