как мутировать потомство в генетическом алгоритме?

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

Я пишу код генетического алгоритма, но не знаю, как реализовать мутацию. Предположим, потомок, который будет мутирован, представляет собой строку типа 10110011110101000111 длиной 20.

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

Другими словами, есть ли у каждого бита в потомстве шанс мутировать в соответствии с сгенерированным случайным числом, или только у одного бита есть шанс мутации?


mutation genetic-algorithm
person Mohammad Asasi    schedule 02.07.2016    source источник
comment
Это зависит. Какова вероятность любой мутации или каждой мутации?   -  person jonrsharpe    schedule 02.07.2016
comment
Это выбор дизайна. Один может превзойти другого.   -  person ayhan    schedule 02.07.2016
comment
Уважаемый jonrsharpe, я не совсем понял ваш вопрос, но для вашего сведения я установил скорость мутации на 0,001. Я генерирую случайное число в цикле for, и если сгенерированное случайное число ниже этой скорости мутации, бит переключается. Это означает, что все биты имеют шанс мутации.   -  person Mohammad Asasi    schedule 02.07.2016
comment
Любой выбор в порядке. Используйте тот, который работает лучше всего.   -  person Ray    schedule 02.07.2016
comment
@MohammadAsasi Я голосую за то, чтобы закрыть этот вопрос как слишком широкий, без указания проблемной области, значения кодировки и вероятностей каждого события, о котором идет речь. не может дать конкретного ответа. То, что вы делаете в генетическом алгоритме, сильно зависит от этих элементов, а вы не указали ни один из них.   -  person Patrick Trentin    schedule 04.07.2016

Ответы (1)


arrow_upward
2
arrow_downward

«Традиционно» частота мутаций pmutation («Генетические алгоритмы поиска, оптимизации и машинного обучения» Дэвида Э. Голдберга) является мерой сходства с тем, что случайные элементы вашей хромосомы будут преобразованы во что-то другое (ваш «вариант 1»).

т.е. если ваша хромосома закодирована как двоичная строка длиной 1000, а pmutation равно 1% (0.01), это означает, что 10 из ваших 1000 бит (в среднем) будут перевернуты.

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

Учтите, что если L - это длина бинарной хромосомы:

  • для унимодальных областей поиска 1/L часто предлагается как хороший коэффициент мутации (например, "Как на самом деле работают генетические алгоритмы: мутация и восхождение на холм" Х. Мюленбейна).
  • для мультимодальных пространств поиска частота мутаций, значительно превышающая 1/L, является стандартной, и ваш "вариант 2" вызовет некоторые проблемы.

«вариант 1» немного более гибкий и следует правилу наименьшего удивления, поэтому без других подробностей , я бы выбрал его.

person manlio    schedule 04.07.2016