Цитата(Mirkes @ 11.2.2012, 05:00  ) |
| если получили больше заданной величины |
Заданная величина я так понимаю это число - которое мы использовали в первом операторе скрещивания (вероятность хромосомы быть родителем)? Или же это опять random?
| Версия для печати темы
Нажмите сюда для просмотра этой темы в оригинальном формате |
| Форум программистов > Алгоритмы > Генетические алгоритмы |
| Автор: serega721 11.2.2012, 00:15 |
| Добрый день! Только вот начал изучать предмет генетические алгоритмы и столкнулся с непониманием использования оператора мутации, а именно: Всегда ли после оператора скрещивания мы используем мутацию? Все ли хромосомы подвергаются мутации? И как мы определяем какие именно биты и в каком количестве будем инвертировать? За любые ответы буду очень признателен. |
| Автор: Mirkes 11.2.2012, 05:00 |
| В классических генетических алгоритмах есть несколько независимых операций модификации генов: 1. Кроссинговер (скрещивание). Он бывает одноточечным и многоточечным. 2. Мутация В генетике есть еще пара операций, которые в генетических алгоритмах не используются - вставка и выпадение. Операции скрещивания и мутации независимы. многоточечное скрещивание имеет следующий алгоритм. Определяем набр точек скрещивания i1,...ik далее определяем двух потомков по формуле первый a[1],...,a[i1],b[i1+1],...,b[i2],a[i2+1],... второй b[1],...,b[i1],a[i1+1],...,a[i2],b[i2+1],... Теперь мутация. Мутация определяется своей вероятностью. Для каждого потомка кидаем кости - если получили больше заданной величины, быть мутации. ген (позицию) для мутации определяем вторым бросанием костей (генератором случайных чисел). Небольшое замечание. Только в крайне примитивных случаях параметры модели в генетическом программирвании кодируют битовой цепочкой. Такое кодирование делает мутацию разных битов имеющей (слишком) разное влияние на результат. Другие варианты кодирования можно найти в литературе. |
| Автор: serega721 11.2.2012, 13:35 | ||
Заданная величина я так понимаю это число - которое мы использовали в первом операторе скрещивания (вероятность хромосомы быть родителем)? Или же это опять random? |
| Автор: Mirkes 11.2.2012, 15:33 | ||||
Прошу прощения за иносказательность. Пусть вероятность мутации равна 0<=p<=1. Генерируем случайное число из диапазона [0,1] (бросаем кости). Если число больше p, тогда мутация состоится. Генерируем случайное целое число из диапазона [0,число генов]. Ген с выброшенным номером подвергается мутации. |
| Автор: Mirkes 11.2.2012, 16:06 |
| Перечитал все и понял что получается скомканная куча. Поэтому решил еще раз записать один из классических вариантов. Начнем с терминологии. ген - единица информации в коде. В простейшем случае - 1 бит. геном - полная последовательность, кодирующая одну особь. Хромосом в генетических алгоритмах нет. Для алгоритма в целом определяются несколько параметров 1. Вероятность мутации pm 2. Размер популяции n 3. Число рождающихся особей m 4. Спсоб вычисления фитнес функции (всегда неотрицательна, чем больше, тем лучше) 5. Число разрезов в геноме k (кратность кроссинговера), в классике 1. Для каждой особи в популяции определено значение финтес функции. Генетический алгоритм в каждой эпохе проходит два этапа 1. размножение. 2. отбор. Размножение. Для каждой особи определяется вероятность принять участие в размножении. Есть множество алгоритмов рассчета этих вероятностей. Наиболее простой и классический - пропорционально значению фитнес функции: Кроме того, фиксируется способность одной особи принять участие в нескольких операциях размножения за один этап размножения. Один этап размножения состоит в m последовательных выполнениях следующей процедуры Генерируем случайное число из диапазона от 0 до суммы фитнес функции всех особей, претендующих на участие в размножении. Далее перебирая последовательно по номерам особей имеющейся популяции вычитая из полученного случайного числа значение фитнес функции. Та особь, на которой значение числа станет меньше нуля, отбирается для скрещивания. Аналогично выбирается партнер. Для отобранной пары выполняется процедура скрещивания с рождением двух новых особей. Определяем набр точек скрещивания i1,...ik далее определяем двух потомков по формуле первый a[1],...,a[i1],b[i1+1],...,b[i2],a[i2+1],... второй b[1],...,b[i1],a[i1+1],...,a[i2],b[i2+1],... Для каждой из новых особей выполняем следующую процедуру Генерируем случайное число из диапазона [0,1]. Если число больше p, тогда мутация состоится. Генерируем случайное целое число из диапазона [0,число генов]. Ген с выброшенным номером подвергается мутации. Потом проводится этап селекции. Как правило задается доля старого поколения, переходящая в новое. Остальное выбирается из новых особей. Отбор ведется по значению фитнес функции. Вроде так. |
| Автор: _Y_ 11.2.2012, 20:12 |
| Когда-то прочитал вот такую книжку: Melanie Mitchell An Introduction to Genetic Algorithms Просто так прочитал, для развлечения. Отлично написана: все понятно и ясно, да, к тому же, сразу хочется только ими всегда и заниматься  Если удасться ее найти - очень рекомендую  |
| Автор: Avrilfun41 18.2.2012, 22:29 |
| Прощу прощения что вмешиваюсь. Тоже начал заниматься генетическими алгоритмами - не могли бы подсказать литературу на русском по этой теме? Буду очень признателен. |
| Автор: Polesinskij 31.10.2013, 19:05 |
Модератор: Сообщение скрыто. |