Следующая схема суммирует, как работает генетический алгоритм:
Алгоритм начинается с создания случайной начальной совокупности.
Затем алгоритм создает последовательность новых популяций. На каждом шаге алгоритм использует индивидуумов в текущем поколении для создания следующей популяции. Для создания нового заполнения алгоритм выполняет следующие шаги:
Оценивает каждого члена текущего населения, вычисляя его значение пригодности. Эти значения называются необработанными показателями фитнеса.
Масштабирует необработанные оценки пригодности, чтобы преобразовать их в более полезный диапазон значений. Эти масштабированные значения называются ожидаемыми значениями.
Выбор участников, называемых родителями, на основе их ожиданий.
Некоторые из людей в нынешней популяции, которые имеют более низкую пригодность, выбраны в качестве элиты. Эти элитные особи передаются следующей популяции.
Производит детей от родителей. Дети рождаются либо путем внесения случайных изменений в одного родителя - мутации - либо путем объединения векторных записей пары родителей - кроссовера.
Заменяет нынешнее население детьми для формирования следующего поколения.
Алгоритм останавливается при выполнении одного из критериев остановки. См. раздел Условия остановки алгоритма.
Алгоритм начинается с создания случайной начальной совокупности, как показано на следующем рисунке.
В этом примере начальное заполнение содержит 20 отдельных лиц. Заметим, что все особи в начальной популяции лежат в верхнем правом квадранте картины, то есть их координаты лежат между 0 и 1. Для этого примера: InitialPopulationRange опция - [0;1].
Если вы знаете приблизительно, где находится минимальная точка для функции, вы должны установить InitialPopulationRange чтобы точка лежала около середины этого диапазона. Например, если вы считаете, что минимальная точка для функции Растригина находится вблизи точки [0 0], вы можете установить InitialPopulationRange быть [-1;1]. Однако, как показывает этот пример, генетический алгоритм может найти минимум даже при менее чем оптимальном выборе для InitialPopulationRange.
На каждом этапе генетический алгоритм использует текущую популяцию для создания детей, которые составляют следующее поколение. Алгоритм выбирает группу особей в текущей популяции, называемых родителями, которые вносят свои гены - записи своих векторов - в свои дети. Алгоритм обычно выбирает людей, которые имеют лучшие значения фитнеса в качестве родителей. Можно указать функцию, которую алгоритм использует для выбора родительских элементов в SelectionFcn вариант. См. раздел Параметры выбора.
Генетический алгоритм создает три типа детей для следующего поколения:
Eliteare индивидуумы в текущем поколении с лучшими фитнес-ценностями. Эти люди автоматически доживают до следующего поколения.
Кроссоверы создаются путём объединения векторов пары родителей.
Дети мутаций создаются путем внесения случайных изменений, или мутаций, одному родителю.
Следующая принципиальная схема иллюстрирует три типа нижестоящих элементов.
Mutation and Crossover объясняет, как указать количество потомков каждого типа, который генерирует алгоритм, и функции, которые он использует для выполнения кроссовера и мутации.
В следующих разделах объясняется, как алгоритм создает детей кроссовера и мутации.
Алгоритм создает детей-кроссоверов, объединяя пары родителей в текущей популяции. При каждой координате дочернего вектора функция пересечения по умолчанию случайным образом выбирает запись или ген в одной и той же координате из одного из двух родителей и назначает его потомку. Для проблем с линейными ограничениями функция пересечения по умолчанию создает нижестоящий элемент как случайное средневзвешенное значение родителей.
Алгоритм создает детей мутаций, случайным образом изменяя гены отдельных родителей. По умолчанию для неограниченных задач алгоритм добавляет случайный вектор из гауссова распределения к родительскому. Для ограниченных или линейно ограниченных проблем потомок остается выполнимым.
На следующем рисунке показаны дети исходной популяции, то есть популяции во втором поколении, и указано, являются ли они детьми элиты, кроссовера или мутации.
На следующем рисунке показаны популяции в итерациях 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- ConstraintTolerance не используется в качестве критерия остановки. Он используется для определения осуществимости нелинейных ограничений. Также, max(sqrt(eps),ConstraintTolerance) определяет выполнимость в отношении линейных ограничений.
Алгоритм останавливается, как только выполняется одно из этих условий.
Функция выбора выбирает родители для следующего поколения на основе их масштабированных значений из функции масштабирования пригодности. Масштабированные значения пригодности называются ожидаемыми значениями. Индивидуум может быть выбран в качестве родителя более одного раза, и в этом случае он вносит свои гены более чем в одного ребенка. Опция выбора по умолчанию, @selectionstochunif, размещает строку, в которой каждый родительский элемент соответствует участку линии длины, пропорциональному ее масштабированному значению. Алгоритм движется вдоль линии шагами равного размера. На каждом шаге алгоритм выделяет родительский элемент из раздела, на котором он находится.
Более детерминированная опция выбора @selectionremainder, которая выполняет два шага:
На первом шаге функция выбирает родителей детерминированно в соответствии с целой частью масштабированного значения для каждого индивидуума. Например, если масштабированное значение индивидуума равно 2,3, функция выбирает его дважды в качестве родителя.
На втором этапе функция выбора выбирает дополнительные родители, используя дробные части масштабированных значений, как при стохастическом равномерном выборе. Функция размещает линию в секциях, длины которых пропорциональны дробной части масштабированного значения индивидов, и перемещается вдоль линии равными шагами для выбора родителей.
Обратите внимание, что если дробные части масштабированных значений все равны 0, как это может произойти с помощью Top масштабирование, выбор является полностью детерминированным.
Дополнительные сведения и дополнительные параметры выбора см. в разделе Параметры выбора.
Варианты воспроизведения управляют тем, как генетический алгоритм создает следующее поколение. Опции:
EliteCount - Количество людей с лучшими фитнес-ценностями в текущем поколении, которые гарантированно доживут до следующего поколения. Этих людей называют элитными детьми.
Когда EliteCount составляет не менее 1, лучшее значение фитнеса может уменьшиться только от одного поколения к следующему. Это то, что вы хотите, так как генетический алгоритм минимизирует функцию фитнеса. Настройка EliteCount в высокой степени заставляет наиболее приспособленных людей доминировать в популяции, что может сделать поиск менее эффективным.
CrossoverFraction - Доля личностей в следующем поколении, кроме элитных детей, которые создаются кроссовером. Установка перекрестной доли описывает, как значение CrossoverFraction влияет на производительность генетического алгоритма.
Потому что элитные люди уже были оценены, ga не переоценивает фитнес-функцию элитных особей во время размножения. Это поведение предполагает, что функция пригодности индивидуума не является случайной, а является детерминированной функцией. Чтобы изменить это поведение, используйте функцию вывода. Посмотрите EvalElites в государственной структуре.
Генетический алгоритм использует людей в текущем поколении, чтобы создать детей, которые составляют следующее поколение. Помимо элитных детей, которые соответствуют индивидуумам текущего поколения с лучшими фитнес-ценностями, алгоритм создает
Пересечение детей путем выбора векторных записей или генов из пары индивидуумов в текущем поколении и объединение их для формирования ребенка
Дети мутаций путем применения случайных изменений к одному человеку в текущем поколении для создания ребенка
Оба процесса важны для генетического алгоритма. Кроссовер позволяет алгоритму извлекать лучшие гены у разных людей и рекомбинировать их в потенциально превосходящих детей. Мутация добавляет разнообразие популяции и тем самым увеличивает вероятность того, что алгоритм будет генерировать людей с лучшими значениями пригодности.
Пример того, как генетический алгоритм применяет мутацию и кроссовер, см. в разделе Создание следующего поколения.
Можно указать, сколько нижестоящих элементов каждого типа создает алгоритм следующим образом:
EliteCount указывает количество элитных нижестоящих элементов.
CrossoverFraction определяет долю населения, отличную от элитных детей, которые являются перекрестными детьми.
Например, если PopulationSize является 20, EliteCount является 2, и CrossoverFraction является 0.8, номера каждого типа детей в следующем поколении следующие:
Есть двое элитных детей.
Есть 18 особей, кроме элитных детей, поэтому алгоритм округляет 0,8 * 18 = 14,4 до 14, чтобы получить количество детей кроссовера.
Остальные четыре человека, кроме элитных детей, являются детьми с мутациями.
