Дин! Дайте вам идеи для поиска лучшего решения

искусственный интеллект алгоритм Нейронные сети
Дин! Дайте вам идеи для поиска лучшего решения
Эвристический алгоритмЭто алгоритм, основанный на интуитивном или эмпирическом построении, который может дать приближенное оптимальное решение конкретной оптимизационной задачи при приемлемых вычислительных затратах (время вычислений, занимаемое пространство и т. д.), которое согласуется с реальным оптимальным решением. отклонения, как правило, нельзя предсказать.

Поскольку общие классические алгоритмы для задач NP слишком неэффективны или даже неразрешимы, родился эвристический алгоритм. Хорошо спроектированный эвристический алгоритм обычно может получить приближенное оптимальное решение задачи за относительно короткое время, а также может получить лучшее решение за полиномиальное время для задач NP.

Эвристика не является точным алгоритмом, но обеспечивает основу для поиска оптимального решения. Как видно из определения в начале, эвристический алгоритм должен установить ряд эвристических правил, подходящих для практических задач в соответствии с реальным сценарием приложения. В то же время эвристический алгоритм имеет следующие проблемы:

  • В настоящее время нет единой и полной теоретической системы;

  • Эвристические алгоритмы столкнутся с проблемой локальных оптимумов, и трудность заключается в том, как спроектировать механизм для эффективного ухода от локальных оптимумов;

  • Большое влияние на эффект оказывает настройка параметров алгоритма, и стоит подумать о том, как эффективно установить параметры;

  • Как установить действительные условия остановки итерации и т. д.

Поэтому стоит отметить, что эвристический алгоритм не может гарантировать оптимальное решение, эффект относительно нестабилен, и его действие зависит от реальной задачи и опыта проектировщика. Однако перед лицом сложных проблем эвристический алгоритм может быть решен относительно простым способом, и разработать программу несложно.

Большинство эвристик выполняетсябиологическое или физическое явлениеEvolved, мы разделяем его на следующие категории соответственно:

  • Алгоритмы, подобные животным: алгоритм оптимизации роя частиц, алгоритм муравьиной колонии, алгоритм рыбного роя, алгоритм пчелиной колонии и т. Д .;

  • Растительноподобные алгоритмы: фототропный алгоритм, алгоритм оптимизации сорняков и др.;

  • Человекоподобные алгоритмы: генетический алгоритм, нейронная сеть, алгоритм акустического поиска и др.;

  • Алгоритмы, имитирующие физические явления: алгоритмы имитации отжига.

Затем выберите более классические эвристические алгоритмы в вышеуказанных категориях для представления.

Алгоритм имитации отжига SA

В термодинамике отжиг относится к физическому явлению, при котором объект постепенно остывает. Чем ниже температура, тем ниже энергетическое состояние объекта, при достаточно низком энергетическом состоянии жидкость начинает конденсироваться и кристаллизоваться, В кристаллическом состоянии энергетическое состояние системы самое низкое и наиболее стабильное.

Процесс физического отжига состоит из трех частей:

  • Процесс нагрева:Цель состоит в том, чтобы усилить тепловое движение частиц от положения равновесия.

  • Изотермический процесс:Для замкнутой системы, которая обменивается теплотой с окружающей средой без изменения температуры, самопроизвольное изменение состояния системы всегда происходит в сторону уменьшения свободной энергии.

  • Процесс охлаждения:Тепловое движение частиц ослабевает, и энергия системы уменьшается, достигая низшего энергетического состояния.

Метод имитации отжига представляет собой общий эвристический алгоритм.Каждое решение в пространстве поиска задачи мы представляем себе как молекулу в объекте.Для каждого решения в пространстве поиска оно имеет "энергию" как и молекула объекта, которая равна используется для Указывает, насколько это решение подходит для проблемы. Алгоритм принимает произвольное решение в пространстве поиска в качестве начального решения, генерирует новое решение случайным образом на каждом шаге и вычисляет вероятность достижения нового решения из текущего решения. Среди них процесс нагрева соответствует начальной температуре алгоритма, изотермический процесс соответствует процессу дискретизации Метрополиса алгоритма, а процесс охлаждения соответствует уменьшению контрольных параметров.

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

Изменение энергии — это изменение значения целевой функции, а состояние с наименьшей энергией — это оптимальное решение. Среди них критерий Метрополиса является ключом для сходимости алгоритма SA к глобальному оптимальному решению.Когда найдено плохое решение, критерий Метрополиса примет плохое решение с определенной вероятностью, так что алгоритм имеет возможность прыгать вне локального оптимума. Если предположить, что текущее допустимое решение равно x, а итеративно обновленное решение равно x_new, то соответствующая «разность энергий» определяется как:

Δf знак равно ж ( x_новый ) - ж ( х )

Плохое решение принимается с некоторой вероятностью, тогда вероятность равна:

p(Δf) = exp(-Δf/kT)

Температура T является одним из влияющих факторов критерия Метрополиса: при высокой температуре принимаются новые решения с большим отличием энергии от текущего состояния, при низких температурах принимаются только новые решения с небольшим отличием энергии от текущего состояния. .

Конкретный поток моделируемого алгоритма отжига показан на следующем рисунке:

Алгоритм имитации отжига широко используется и может эффективно решать NP-полные задачи, такие как задача коммивояжера, задача о максимальном усечении и задача о рюкзаке 0-1. Однако его параметры трудно контролировать, и нет гарантии, что он сойдется к оптимальному значению в один момент времени, в большинстве случаев он все же попадет в локальное оптимальное значение, на которое в основном влияют три ключевых параметра:

  • Настройка начального значения температуры
    Установка начального значения температуры является важным фактором, влияющим на производительность глобального поиска алгоритма имитации отжига. Если начальная температура высока, вероятность нахождения глобального оптимального решения высока, но это потребует много вычислительного времени, в противном случае можно сэкономить время вычислений, но это может сказаться на производительности глобального поиска.

  • Проблема со скоростью отжига, количество итераций для каждого значения температуры
    Производительность глобального поиска смоделированного алгоритма отжига также тесно связана со скоростью отжига. Вообще говоря, «достаточный» поиск при той же температуре вполне необходим, но чем более «достаточный» поиск, тем больше вычислительные затраты.

  • проблемы с управлением температурой
    Управление температурой также является важным фактором, влияющим на производительность глобального поиска алгоритмов имитации отжига. В сценариях практического применения из-за необходимости учитывать накладные расходы при расчете для охлаждения часто используется температурное затухание:

    Т=α×T.α∈(0,1)

    Чтобы обеспечить большее пространство поиска, α обычно принимает значение, близкое к 1, например 0,95, 0,9.

? Например: проблема с покупками продуктов

Задача о покупке продуктов — это типичная задача комбинаторной оптимизации: для набора из n овощей каждый овощ имеет свой объем w_i и цену v_i, у тёти, покупающей продукты, есть корзина для покупок вместимостью C, купить Задача тёти Цай — купить набор овощей с самой высокой ценой и положить их в корзину, не превышая вместимость корзины для покупок.


Дан набор из n овощей {x_1, x_2, ..., x_n}, x_i∈{0, 1}, каждый овощ x_i имеет атрибут {(w_i, v_i)}, а вместимость корзины — целое положительное число C, То есть решить следующую оптимизационную задачу:

Предполагая, что размер набора овощей = {2, 2, 3, 4}, установленная цена овощей = {5, 6, 7, 8}, вместимость корзины для покупок Тетушки равна 7, а исходная схема такова: обычно устанавливается в S0 = {0, 0, 0, 0}. Поскольку это максимизация общей цены овощей, то целевая функция и предельная функция имеют вид:

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

1. Если овощей i нет в корзине, бросьте их прямо в корзину;
2. Если овоща i нет в корзине для покупок, но корзина полна, достаньте овощ j из корзины с завязанными глазами и уступите место овощу i;
3. Если овощ i уже находится в корзине для покупок, сначала достаньте овощ i, затем выберите овощ j с завязанными глазами и положите его в корзину.

В зависимости от ситуации, созданной тремя новыми решениями, будет три ситуации в разнице в стоимости и разнице в объеме корзины для покупок.

Разница в стоимости корзины:

Разница в объеме корзины:

Поскольку задача покупки продуктов является задачей оптимизации с ограничениями, критерий Метрополиса необходимо соответствующим образом скорректировать:

Затем по правилам расчета, описанным выше, задаем начальную температуру T, коэффициент спада температуры α и количество итераций K для каждой температуры, и будет получен оптимальный план закупки продуктов: S = {1, 1, 1 , 0}. То есть Totalsize=7, Totalvalue=18.


Генетический алгоритм ГА

Генетический алгоритм опирается на теорию эволюции Дарвина и теорию генетики Менделя, моделирует решаемую задачу как процесс биологической эволюции, генерирует решение следующего поколения с помощью таких операций, как репликация, скрещивание, мутация и т. д., и постепенно устраняет низкое значение фитнес-функции. , добавьте решения с высокими значениями фитнес-функции. Таким образом, после N поколений эволюции очень вероятно, что будут развиваться особи с высокими значениями функции приспособленности.

Давайте сначала рассмотрим некоторые родственные биологические концепции генетики:

Разновидность:Эволюция организмов осуществляется в форме группы, такая группа называется популяцией;

физическое лицо:отдельные организмы, составляющие популяцию;

Ген:генетический фактор;

хромосома:содержит набор генов;

Соревнование на выживание, выживает сильнейший:У особей с высокой приспособленностью к среде больше возможностей участвовать в размножении, и потомства будет все больше, у особей с низкой приспособленностью меньше возможностей участвовать в размножении, и потомства будет все меньше;

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

Соответствующий генетический алгоритм также имеет следующие основные компоненты:

  • кодирование

  • фитнес-функция

  • генетический оператор

  • Рабочие параметры


кодирование

Генетический алгоритм абстрагирует объекты в строки, расположенные в определенном порядке с помощью определенного механизма кодирования.Кодирование в основном делится на следующие категории:

  • Самый простой способ кодированиябинарный код, то есть закодировать решение задачи в виде бинарного массива;

  • обменное кодированиеОбычно он используется для решения задач сортировки: таких как проблема TSP, в которой используется строка генетических кодов для представления порядка пройденных городов;

  • древовидное кодированиедля эволюционного программирования в генетическом программировании;

  • кодировка значенияДля решения сложных численных задач.

Кодирование в основном следует трем принципам:

1. Полнота: все решения проблемного пространства могут быть представлены правилами кодирования;

2. Разумность: любой ген соответствует возможному решению;

3. Отсутствие избыточности. Существует однозначное соответствие между пространством задач и пространством выражений, сформированным правилами кодирования.


фитнес-функция

Оценка качества особи (решения) генетическим алгоритмом измеряется значением фитнес-функции, чем больше значение фитнес-функции, тем лучше качество особи. Функция пригодности является движущей силой процесса эволюции генетического алгоритма, а также единственным критерием естественного отбора, который необходимо конструировать в соответствии с конкретной решаемой задачей.

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


генетический оператор

К генетическим операторам относятся операторы селекции, операторы кроссинговера и операторы мутации.


выберите операцию

Операция отбора относится к операции выживания наиболее приспособленных особей. Люди с высокой приспособленностью имеют высокую вероятность быть унаследованными в следующем поколении; люди с низкой приспособленностью имеют небольшую вероятность быть унаследованными в следующем поколении.

Оператор отбора в базовом генетическом алгоритме (SGA) принимает метод отбора рулетки, и его основная идея заключается в следующем.Вероятность того, что каждый человек будет выбран, пропорциональна значению его функции пригодности.

Этапы реализации метода выбора колеса рулетки следующие:

  • Рассчитать значение пригодности всех людей в группе;

  • Рассчитать вероятность выбора каждой особи;

  • Рассчитать кумулятивную вероятность;

  • Используйте имитацию азартной игры (т. е. сгенерируйте случайное число от 0 до 1 и сопоставьте вероятность наследования каждого человека со следующим поколением, чтобы определить, передается ли каждый человек по наследству в следующее поколение).


? Например

Пусть имеются хромосомы S1 = 3 (00011), S2 = 10 (01010), S3 = 17 (10001), S4 = 22 (10110), согласно фитнес-функции F(S) = S^2 -2 Пригодность каждой хромосомы может быть получена:

  • F(S1) = 3^2 -2 = 7

  • F(S2) = 10^2 -2 = 98

  • F(S3) = 17^2 -2 = 287

  • F(S4) = 22^2 -2 = 482

Предположим, что есть 4 случайных числа r1=0,061, r2=0,242, r3=0,402, r4=0,728, тогда, объединив пригодность каждой хромосомы, мы можем получить:


кроссовер

Операция кроссинговера означает, что две парные хромосомы каким-то образом обмениваются друг с другом частью своих генов в соответствии с вероятностью кроссинговера Pc, в результате чего образуются две новые особи. Операция кроссовера — важная особенность, отличающая генетические алгоритмы от других эволюционных алгоритмов, играющая ключевую роль в генетических алгоритмах и являющаяся основным методом создания новых особей. Оператор кроссинговера в базовом генетическом алгоритме (SGA) использует оператор кроссинговера с одной точкой, кроме того, есть кроссинговер с двумя точками и кроссовер на основе «и/или».

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

Двухточечный кроссинговер (бинарное кодирование) заключается в выборе двух точек кроссинговера, при этом часть гена-потомка между двумя точками кроссинговера получается из одного родительского гена, а оставшаяся часть получается из другого родительского гена.

Кроссовер на основе «и/или» (двоичное кодирование) заключается в выполнении побитовой обработки «и»/«или» над двумя родительскими генами для получения генов-потомков.


операция мутации

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

Операция кроссовера и операция мутации взаимодействуют друг с другом, чтобы завершить глобальный поиск и локальный поиск в пространстве поиска. Оператор мутации в базовом генетическом алгоритме (SGA) использует базовый оператор мутации битов.

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


Рабочие параметры

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

Размер популяции относится к количеству особей в популяции.Большая численность популяции не может оптимизировать результаты генетического алгоритма.Рекомендуемая численность популяции составляет 15-30. Коэффициент кроссовера обычно должен быть относительно большим, обычно 85%-95%. Скорость изменения, как правило, должна быть относительно небольшой, обычно используется 0,5–1%.

Как показано на рисунке выше, основной процесс генетического алгоритма:

1. Инициализировать счетчик эволюционной алгебры (t=0), T — максимальная эволюционная алгебра, а затем случайным образом сгенерировать M особей в качестве начальной популяции P(t);

2. Проведите индивидуальную оценку: рассчитайте значение пригодности каждого человека в P(t);

3. Выполните операцию выбора: примените оператор выбора к группе;

4. Выполните операцию кроссовера: примените оператор кроссовера к группе;

5. Выполнить операцию мутации: применить оператор мутации к популяции;

6. С помощью шагов 2-5 получают популяцию следующего поколения P(t+1);

7. Условие завершения определяет, достигает ли эволюционная алгебра максимального значения: если t≦T, то t ←t+1, перейти к шагу 2, если t>T, завершить и вывести решение.

Существует две схемы оптимизации производительности генетических алгоритмов: катаклизм и элитарность.

Локальная поисковая способность генетического алгоритма сильна, но легко попасть в ловушку локальной оптимальности.Чтобы выпрыгнуть из локального экстремума, необходимо убить текущих выдающихся особей, чтобы точки, находящиеся далеко от текущее экстремальное значение имеет достаточно места для эволюции.катастрофаподумал о. При использовании скрещивания и мутации для создания потомства весьма вероятно, что полученное оптимальное решение будет потеряно на промежуточном этапе.В каждом поколении потомства текущее оптимальное решение сначала копируется в потомство, чтобы предотвратить генерацию Оптимальное решение разрушается кроссинговером и мутацией, т.Элитарностьподумал о.

Существует определенная степень противоречия между катастрофой и элитарностью: механизм катастрофы заключается в уничтожении выдающихся личностей, механизм элитарности — в сохранении лучших личностей в потомстве. Но на самом деле они могут сосуществовать.Перед операцией кроссовера в каждом поколении лучшая особь копируется в следующее поколение, но когда в следующих n последовательных поколениях нет лучшей особи, может случиться так, что генетический алгоритм попал в ловушку. В это время можно использовать механизм катастрофы, чтобы помочь алгоритму выйти за пределы локального оптимума. При построении генетических алгоритмов по конкретным сценариям можно выборочно принять катастрофу и элитарность.


? Вернемся к примеру выше: покупка продуктов

Задача о покупке продуктов — это типичная задача комбинаторной оптимизации: для набора из n овощей каждый овощ имеет свой объем w_i и цену v_i, у тёти, покупающей продукты, есть корзина для покупок вместимостью C, купить Задача тёти Цай — купить набор овощей с самой высокой ценой и положить их в корзину, не превышая вместимость корзины для покупок.

Дан набор из n овощей {x_1, x_2, ..., x_n}, x_i∈{0, 1}, каждый овощ x_i имеет атрибут {(w_i, v_i)}, а вместимость корзины — целое положительное число C, То есть решить следующую оптимизационную задачу:

Задача тетушки о покупке продуктов естественным образом соответствует двоичному кодированию: набор из n овощей, которые нужно решить {x_1, x_2, ..., x_n}, представлен в виде бинарной хромосомы длины n.

Предполагая, что размер набора овощей = {2, 2, 3, 4}, установленная цена овощей = {5, 6, 7, 8}, а вместимость корзины тети равна 10, следующие совокупности генерируются случайным образом (n=4, размер популяции равен 4): S1=0001, S2=0101, S3=1000, S4=1111.

Так как это максимизирует общую цену овощей, сначала рассчитайте общую цену на человека, а затем рассчитайте общий объем на человека:

Из-за ограничения верхнего предела грузоподъемности при расчете пригодности необходимо учитывать этот фактор, поэтому добавляется штрафной срок:

Среди них параметр α – коэффициент штрафа, α > 1,0, чем больше значение, тем больше штраф.

Предполагая, что коэффициент штрафа равен 10, пригодность каждого человека составляет:

S1 = 0001, TotalSize=4, TotalValue=8, Fitness=8;

S2 = 0101, TotalSize=6, TotalValue=14, Fitness=14;

S3 = 1000, TotalSize=2, TotalValue=5, Fitness=5;

S4 = 1111, TotalSize = 11, TotalValue = 26, Fitness = 16.

Предположим, сгенерировано 4 случайных числа, r1=0,22, r2=0,57, r3=0,41, r4=0,79.

Тогда популяция следующего поколения T1 = 0101, T2 = 1000, T3 = 0101, T4 = 1111. Затем выбранные популяции случайным образом спариваются, а затем случайным образом устанавливаются точки кроссинговера в соответствии со скоростью кроссинговера, и происходит обмен частью генов парных хромосом посредством одноточечного кроссинговера.

Предполагая, что T1 и T4 являются парными, пересечение является второй позицией; T2 и T3 являются парными, а пересечение является третьей позицией, тогда новая популяция после кроссовера будет:

U1 = 0111, TotalSize=9, TotalValue=21, Fitness=21;

U2 = 1001, TotalSize=6, TotalValue=13, Fitness=13;

U3 = 0100, TotalSize=2, TotalValue=6, Fitness=6;

U4 = 1101, TotalSize=8, TotalValue=19, Fitness=19.

Предположим снова, что U3 мутирован в третьей и четвертой позициях, тогда:

U1 = 0111, TotalSize=9, TotalValue=21, Fitness=21;

U2 = 1001, TotalSize=6, TotalValue=13, Fitness=13;

U3 = 0111, TotalSize=9, TotalValue=21, Fitness=21;

U4 = 1101, TotalSize=8, TotalValue=19, Fitness=19.

На данный момент моя тетя нашла лучшие решения для покупок продуктов U1 и U3.


? Еще пример: проблемы с поездками (если разбираетесь, то можете быстро листать~)

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

Как показано в приведенной выше таблице, присвойте каждому городу числовой код, тогда маршрут (то есть хромосома) будет представлен массивом, содержащим n кодов городов, порядок элементов массива представляет порядок проезда, а элементы в массиве не будет повторяться, потому что город проигрывается только один раз.

Предполагая: S1 = {17, 3, 21, …, 30}, порядок движения следующий: Чжэнчжоу -> Шанхай -> Фучжоу -> … -> Чэнду.

Чем короче общая поездка тети, тем лучше, затем возьмите обратную величину от общей поездки маршрута в качестве фитнес-функции. Предполагая, что восточная долгота равна x, а северная широта равна y, тогда координаты города равны (x, y), тогда маршрут S_i = {(x_1, y_1), (x_2, y_2), ..., ( x_n, y_n)} , i∈[0, m], поэтому:

Здесь также используется метод выбора рулетки. Затем маршруты случайным образом объединяются в пары, а пересечения выбираются случайным образом в соответствии с частотой пересечений. Для последовательности путей метод одноточечного кроссинговера нельзя использовать для простого обмена частью генов родительских хромосом, потому что легко вызвать повторяющиеся коды городов в хромосомах потомков. Получить коды городов перекрестков от отца, сохранить эти коды в порядке в отце и заполнить голову потомства, а остальные коды городов получить от матери и заполнить потомства. Например:

Отец: {1, 2, 3, 4, 5, 6, …}

Мать: {31, 2, 3, 11, 1, 5, …}

Дети: {1, 3, 4, 5, 6, …, 31, 2, 11, …}

Используемый здесь метод мутации заключается в случайном выборе двух кодов городов на маршруте в соответствии с частотой мутаций, а затем обмене позициями этих двух кодов. Например, S = {1, 3, 4, 5, 6, ..., 31, 2, 11, ...}, тогда после мутации T = {1, 11, 4, 5, 6, .. ., 31, 2, 3, …}.

На данный момент тетя может найти кратчайший маршрут в соответствии с этим генетическим алгоритмом~


Стратегия эволюции ES

Стратегия эволюции — метод решения задач оптимизации параметров, имитирующий принцип биологической эволюции. Характеристики эволюционной стратегии следующие:

  • Отбор в эволюционной стратегии осуществляется детерминированным образом, что отличается от метода случайного отбора в генетическом алгоритме;

  • Оператор рекомбинации в эволюционной стратегии отличается от кроссовера в генетическом алгоритме тем, что он не просто заменяет определенную часть особи, а заставляет изменить каждую частицу особи.

Стратегии эволюции можно разделить на две категории: (μ+λ)-ES и (μ,λ)-ES.


(μ+λ)-ES

Каждая итерация порождает λ новых решений, и при сравнении с родителем лучшее μ становится родителем следующей итерации, а остальные сразу отбрасываются.

Этот метод вводит идею популяции, которую легко распараллелить, но легко попасть в ловушку локальной оптимальности, которая в основном используется в многокритериальной оптимизации.


(μ,λ)-ES

Каждая итерация порождает λ новых решений (λ>µ), из которых лучшее µ становится родителем следующей итерации, а остальные сразу отбрасываются. Таким образом, все решения выживают только в одном поколении, что позволяет избежать попадания в локальный оптимум.

(μ+λ) отбор может обеспечить выживание оптимальной особи, превращая процесс эволюции группы в монотонный восходящий тренд, но (μ+λ) отбор сохраняет старую особь, склонную к локальным оптимальным проблемам. (μ, λ)-ES, как правило, лучше, чем (μ+λ)-ES, и является основным направлением современных эволюционных стратегий.


ДНК стратегии эволюции больше не представлена ​​двоичными числами, а заменена действительными числами, которые могут решить многие практические задачи, состоящие из действительных чисел. Стратегия эволюции производит скрещивание генов потомства, что похоже на генетический алгоритм, но как следует управлять генной мутацией? Поскольку гены — это реальные числа, нет простого способа провалиться, как генетический алгоритм.

Генетическая изменчивость эволюционных стратегий определяетсяСила вариациичтобы решить, нормальное распределение играет здесь ключевую роль.

Мы рассматриваем значение гена, унаследованного от родителя, как среднее значение нормального распределения, а затем добавляем стандартное отклонение к среднему значению.В это время определяется нормальное распределение, а затем нормальное распределение используется для генерации числа . Например, сила вариации в этой позиции 8,8 равна 2,5, и нормальное распределение определяется в соответствии со стандартным отклонением 2,5 и средним значением 8,8, а затем генерируется новое значение 8,7.

Значение каждой цифры гена потомства будет мутировать через различные распределения состояний, так что будет сгенерирована совершенно новая ДНК потомства. Следовательно, интенсивность мутации также можно рассматривать как набор генетической информации, унаследованной от родительской ДНК, и сама интенсивность мутации также может быть мутирована.

Ключевыми этапами эволюционной стратегии являются: скрещивание, мутация, отбор и изменение степени мутации.

Как генетические алгоритмы,ПересекатьСуществует три основных способа обмена генами двух особей:

1. Дискретная рекомбинация:Сначала случайным образом выбираются две родительские особи, а затем их компоненты случайным образом обмениваются, чтобы сформировать компоненты новой потомственной особи, тем самым получая новую особь.

2. Срединная реструктуризация:В этом методе рекомбинации две родительские особи выбираются случайным образом, а затем среднее значение каждого компонента родительских особей используется в качестве компонента новой потомственной особи для формирования новой особи.

3. Гибридная рекомбинация:Этот метод рекомбинации характеризуется отбором родительских особей. Во время гибридной рекомбинации случайным образом выбирается фиксированная родительская особь, а затем из родительской популяции случайным образом выбирается вторая родительская особь для каждого компонента потомственной особи. То есть вторая родительская особь постоянно меняется. Что касается комбинированного метода двух особей родительского поколения, то можно использовать либо дискретный метод, либо медианный метод.

МутацииЭто относительно просто, то есть добавление нулевого среднего и дисперсии распределения Гаусса к каждому компоненту для создания нового индивидуума. Эта определенная дисперсиястепень изменчивости, степень вариации будет меняться Степень вариации относительно велика в начале работы алгоритма, а когда он будет близок к сходимости, степень вариации начнет уменьшаться.

Далее мы поймем это через более конкретный случай стратегии эволюции, как показано на рисунке ниже, это формула степени мутации в (1 + 1)-ES.

Степень вариации здесь контролируется с помощью правила успеха 1/5. Увеличьте степень вариации, когда она еще не сходится, и уменьшите степень вариации, когда она вот-вот сойдётся. Условием оценки сходимости является то, что если только 1/5 вариации лучше, чем первоначальный родитель, то она сошлась быстро; если половина вариации лучше, чем первоначальная родительница, то она не сходится.