Как Генетический Алгоритм Работ
Контур алгоритма
Следующий контур результирует, как работает генетический алгоритм:
Алгоритм начинается с создания случайной начальной генеральной совокупности.
Затем алгоритм создает последовательность новых популяций. На каждом шаге алгоритм использует индивидуумов в текущем поколении, чтобы создать следующее население. Чтобы создать новое население, алгоритм выполняет следующие шаги:
Считает каждый представитель текущего населения путем вычисления ее значения соответствия. Эти значения называются необработанными счетами соответствия.
Масштабирует необработанные счета соответствия, чтобы преобразовать их в более полезную область значений значений. Эти масштабированные значения называются значениями ожидания.
Выбирает представителей, называемых родительскими элементами, исходя из их ожиданий.
Некоторые индивидуумы нынешнего населения, имеющие более низкую пригодность, выбраны в качестве элитных. Эти элитные индивидуумы передаются в следующее население.
Производит детей от родительских элементов. Дети генерируются или путем внесения случайных изменений в единый объект-родитель - мутация - или путем объединения векторных записей пары родительских элементов - кроссовер.
Заменяет текущее население на дочерние элементы для формирования следующей генерации.
Алгоритм останавливается, когда достигается один из критериев остановки. Смотрите Условия Остановки для Алгоритма.
Начальная генеральная совокупность
Алгоритм начинается с создания случайной начальной генеральной совокупности, как показано на следующем рисунке.
В этом примере начальной генеральной совокупности содержит 20 индивидуумов. Обратите внимание, что все индивидуумы в начальную генеральную совокупность лежат в верхнем правом квадранте изображения, то есть их координаты лежат между 0 и 1. В данном примере InitialPopulationRange опция [0;1].
Если вы знаете примерно, где лежит минимальная точка для функции, вы должны задать InitialPopulationRange чтобы точка лежала вблизи середины этой области значений. Например, если вы верите, что минимальная точка для функции Растригина близка к точке [0 0], можно задать InitialPopulationRange чтобы быть [-1;1]. Однако, как показывает этот пример, генетический алгоритм может найти минимум даже с менее чем оптимальным выбором для InitialPopulationRange.
Создание следующей генерации
На каждом шаге генетический алгоритм использует текущее население, чтобы создать детей, которые составляют следующую генерацию. Алгоритм выбирает группу индивидуумов в текущем населении, называемую родительскими элементами, которые вносят свои гены - записи своих векторов - в свои дети. Алгоритм обычно выбирает индивидуумов, которые имеют лучшие значения соответствия, в качестве родительских элементов. Можно задать функцию, которую алгоритм использует для выбора родительских элементов в SelectionFcn опция. См. раздел Опции выбора.
Генетический алгоритм создает три типа детей для следующей генерации:
Элитир индивидуумы в текущем поколении с лучшими значениями фитнеса. Эти индивидуумы автоматически доживают до следующей генерации.
Перекрестие создается путем объединения векторов пары родительских элементов.
Дети мутаций создаются путем введения случайных изменений или мутаций к единому объекту-родителю.
Следующая принципиальная схема иллюстрирует три типа дочерних элементов.
Мутация и кроссовер объясняют, как задать количество дочерних элементов каждого типа, который генерирует алгоритм, и функции, которые он использует для выполнения кроссовера и мутации.
Следующие разделы объясняют, как алгоритм создает дети кроссовера и мутации.
Дети кроссовера
Алгоритм создает детей-кроссоверов путем объединения пар родительских элементов в текущем населении. В каждой координате дочернего вектора функция кроссовера по умолчанию случайным образом выбирает запись или ген в той же координате от одного из двух родительских элементов и присваивает ее дочернему элементу. Для задач с линейными ограничениями функция перекрестия по умолчанию создает дочерний элемент как случайный взвешенное среднее значение родительских элементов.
Дети-мутации
Алгоритм создает детей-мутаций путем случайного изменения генов отдельных родительских элементов. По умолчанию для задач без ограничений алгоритм добавляет случайный вектор из Гауссова распределения к родительскому элементу. Для ограниченных или линейно ограниченных задач ребенок остается допустимым.
Следующий рисунок показывает дети начальной генеральной совокупности, то есть населения на второй генерации, и указывает, являются ли они детьми элиты, кроссовера или мутации.
Графики поздних поколений
Следующий рисунок показывает населения в итерациях 60, 80, 95 и 100.
|
|
|
|
|
|
Когда число поколений увеличивается, индивидуумы в населении сближаются и приближаются к минимальной точке [0 0].
Условия остановки для алгоритма
Генетический алгоритм использует следующие опции, чтобы определить, когда остановиться. Смотрите значения по умолчанию для каждой опции при запуске opts = optimoptions('ga').
MaxGenerations- Алгоритм останавливается, когда количество поколений достигаетMaxGenerations.MaxTime- Алгоритм останавливается после запуска на количество времени в секундах, равноеMaxTime.FitnessLimit- Алгоритм останавливается, когда значение функции соответствия для лучшей точки в текущем населении меньше или равноFitnessLimit.MaxStallGenerations- Алгоритм останавливается, когда среднее относительное изменение значения функции соответствия надMaxStallGenerationsменьшеFunction tolerance.MaxStallTime- Алгоритм останавливается, если нет улучшения целевой функции в течение интервала времени в секундах, равномMaxStallTime.FunctionTolerance- Алгоритм запускается до тех пор, пока среднее относительное изменение значения функции соответствия не перестанетMaxStallGenerationsменьшеFunction tolerance.ConstraintTolerance- TheConstraintToleranceне используется в качестве критерия остановки. Он используется, чтобы определить допустимость относительно нелинейных ограничений. Кроме того,max(sqrt(eps),ConstraintTolerance)определяет допустимость относительно линейных ограничений.
Алгоритм останавливается, как только достигается любое из этих условий.
Выбор
Функция выбора выбирает родительские элементы для следующей генерации на основе их масштабированных значений из функции масштабирования соответствия. Масштабированные значения соответствия называются значениями ожидания. Индивидуум может быть выбран более одного раза в качестве родительского элемента, в этом случае он способствует своим генам более чем одному ребенку. Опция выбора по умолчанию, @selectionstochunif, выкладывает строку, в которой каждый родительский элемент соответствует сечению линии длины, пропорциональному ее масштабируемому значению. Алгоритм перемещается вдоль линии в шагах равного размера. На каждом шаге алгоритм выделяет родительский элемент из секции, в которую он входит.
Более детерминированный опция выбора @selectionremainder, который выполняет два шага:
На первом этапе функция выбирает родительские элементы определенно согласно целочисленной части масштабируемого значения для каждого индивидуума. Например, если масштабированное значение индивидуума составляет 2,3, функция выбирает этого индивидуума дважды в качестве родительского элемента.
На втором этапе функция выбора выбирает дополнительные родительские элементы, используя дробные части масштабированных значений, как при стохастическом равномерном выборе. Функция выкладывает строку в разделах, длины которых пропорциональны дробной части масштабируемого значения индивидуумов, и перемещается вдоль линии равными шагами, чтобы выбрать родительские элементы.
Обратите внимание, что если дробные части масштабированных значений все равны 0, как может произойти с помощью
Topмасштабирование, выбор полностью детерминирован.
Дополнительные сведения и дополнительные опции выбора см. в разделе Опции выбора.
Опции воспроизведения
Опции размножения контролируют, как генетический алгоритм создает следующую генерацию. Опции:
EliteCount- Количество индивидуумов с лучшими значениями соответствия в текущем поколении, которые гарантированно доживут до следующей генерации. Эти индивидуумы называются элитными детьми.Когда
EliteCountэто, по крайней мере, 1, лучшее значение соответствия может только уменьшиться от одной генерации к следующему. Это то, что вы хотите сделать, поскольку генетический алгоритм минимизирует функцию соответствия. НастройкаEliteCountк высокому значению заставляет наиболее подходящие индивидуумов доминировать в населении, что может сделать поиск менее эффективным.CrossoverFraction- Часть особей следующей генерации, кроме элитных детей, которые создаются кроссовером. Установка перекрестной дроби описывает, как значениеCrossoverFractionвлияет на эффективность генетического алгоритма.
Потому что элитные индивидуумы уже были оценены, ga не переоценивает функцию соответствия элитных индивидуумов при размножении. Это поведение принимает, что функция соответствия индивидуума не случайна, но является детерминированной функцией. Чтобы изменить это поведение, используйте выходную функцию. См. EvalElites в государственной структуре.
Мутация и кроссовер
Генетический алгоритм использует индивидуумов в текущем поколении, чтобы создать детей, которые составляют следующую генерацию. Помимо элитных детей, которые соответствуют индивидуумам в текущем поколении с лучшими значениями соответствия, алгоритм создает
Дети-кроссоверы путем выбора векторных записей или генов из пары индивидуумов в текущем поколении и объединяет их, чтобы сформировать ребенка
Дети мутаций путем применения случайных изменений к одному индивидууму в текущем поколении, чтобы создать ребенка
Оба процесса необходимы для генетического алгоритма. Crossover позволяет алгоритму извлечь лучшие гены от разных индивидуумов и рекомбинировать их в потенциально превосходных детей. Мутация добавляет разнообразия населения и тем самым увеличивает вероятность того, что алгоритм сгенерирует индивидуумов с лучшими значениями соответствия.
Смотрите Создание Следующей Генерации для примера того, как генетический алгоритм применяет мутацию и кроссовер.
Можно задать, сколько из каждого типа дочерних элементов создает алгоритм следующим образом:
EliteCountопределяет количество элитных дочерних элементов.CrossoverFractionзадает долю населения, отличную от элитных дочерних элементов, которые являются дочерними элементами кроссовера.
Для примера, если PopulationSize является 20, а EliteCount является 2, и CrossoverFraction является 0.8, номера каждого типа детей в следующей генерации следующие:
Есть два элитных ребенка.
Существует 18 особей кроме элитных детей, поэтому алгоритм округляет 0,8 * 18 = 14,4 до 14, чтобы получить количество детей-кроссоверов.
Остальные четыре индивидуумов, кроме элитных детей, являются детьми с мутациями.