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

Введение

Предположим, что у специалиста по данным есть набор данных изображения, разделенный на несколько классов, и должен быть создан классификатор изображений. После того, как специалист по данным изучил набор данных, K-ближайший сосед (KNN) кажется хорошим вариантом. Для использования алгоритма KNN необходимо использовать важный параметр - K. Предположим, что выбрано начальное значение 3. Ученый начинает процесс обучения алгоритму KNN с выбранным K = 3. Сгенерированная обученная модель достигла точности классификации 85%. Это приемлемый процент? По-другому, можем ли мы получить лучшую точность классификации, чем то, что мы достигли в настоящее время? Мы не можем сказать, что 85% - это лучшая точность, которую можно достичь, пока не проведем различные эксперименты. Но чтобы провести еще один эксперимент, мы определенно должны что-то изменить в эксперименте, например, изменить значение K, используемое в алгоритме KNN. Мы не можем однозначно сказать, что 3 является лучшим значением для использования в этом эксперименте, если не пытаемся применить другие значения для K и не замечаем, как изменяется точность классификации. Вопрос в том, «как найти наилучшее значение для K, которое максимизирует эффективность классификации?» Это то, что называется оптимизацией.

В оптимизации мы начинаем с каких-то начальных значений для переменных, используемых в эксперименте. Поскольку эти значения могут быть не лучшими для использования, мы должны изменять их, пока не получим лучшие. В некоторых случаях эти значения генерируются сложными функциями, которые мы не можем легко решить вручную. Но очень важно провести оптимизацию, потому что классификатор может дать плохую точность классификации не потому, что, например, данные зашумлены или используемый алгоритм обучения слабый, а из-за плохого выбора начальных значений параметров обучения. В результате исследователи операционных исследований (OR) предлагают различные методы оптимизации для выполнения такой работы по оптимизации. Согласно [1] методы оптимизации делятся на четыре основные категории:

  1. Ограниченная оптимизация
  2. Мультимодальная оптимизация
  3. Многокритериальная оптимизация
  4. Комбинаторная оптимизация

Глядя на различные природные виды, мы можем заметить, как они развиваются и приспосабливаются к своей среде обитания. Мы можем извлечь выгоду из таких уже существующих природных систем и их естественной эволюции, чтобы создать наши искусственные системы, выполняющие ту же работу. Это называется бионикой. Например, самолет основан на том, как летают птицы, радар исходит от летучих мышей, подводная лодка изобретена на основе рыбы и так далее. В результате принципы некоторых алгоритмов оптимизации исходят от природы. Например, в основе генетического алгоритма (ГА) лежит идея теории естественной эволюции Чарльза Дарвина «выживание наиболее приспособленных».

Прежде чем вдаваться в подробности того, как работает GA, мы можем получить общее представление об эволюционных алгоритмах (EAs).

Эволюционные алгоритмы (советники)

Можно сказать, что оптимизация осуществляется с помощью эволюционных алгоритмов (ЭА). Разница между традиционными алгоритмами и советниками в том, что советники не статичны, а динамичны, поскольку они могут развиваться с течением времени.

Эволюционные алгоритмы обладают тремя основными характеристиками:

  1. На основе популяции: эволюционные алгоритмы предназначены для оптимизации процесса, в котором текущие решения плохи, для создания новых, более эффективных решений. Набор текущих решений, из которых должны быть сгенерированы новые решения, называется популяцией.
  2. Для фитнеса. Если существует несколько решений, как сказать, что одно решение лучше другого? С каждым отдельным решением связано значение пригодности, рассчитываемое на основе функции приспособленности. Такое значение пригодности отражает, насколько хорошее решение.
  3. На основе вариаций: если в текущей популяции нет приемлемого решения в соответствии с функцией приспособленности, рассчитанной для каждого человека, мы должны что-то сделать, чтобы сгенерировать новые лучшие решения. В результате отдельные решения будут претерпевать ряд изменений, чтобы порождать новые решения.

Мы перейдем в GA и применим эти условия.

Генетический алгоритм (GA)

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

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

Вот описание того, как работает GA:

GA работает с популяцией, состоящей из некоторых решений, где размер популяции (popsize) - это количество решений. Каждое решение называется индивидуальным. У каждого индивидуального раствора есть хромосома. Хромосома представлена ​​как набор параметров (признаков), определяющих личность. У каждой хромосомы есть набор генов. Каждый ген каким-то образом представлен в виде строки из нулей и единиц, как показано на рисунке 1.

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

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

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

Чтобы получить полное представление о GA, необходимо ответить на два вопроса:

  1. Как два потомка появляются от двух родителей?
  2. Каким образом каждое потомство становится индивидуальным?

На эти вопросы мы ответим позже.

Представление и оценка хромосом

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

Представления, доступные для хромосомы, в том числе:

· Двоичный: каждая хромосома представлена ​​строкой из нулей и единиц.

· Перестановка: полезно для задач, связанных с упорядочиванием, таких как задача коммивояжера.

· Значение: фактическое значение кодируется как есть.

Например, если мы хотим закодировать число 7 в двоичном формате, оно может выглядеть так, как показано на рисунке 3.

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

Каждая хромосома имеет два представления.

  1. генотип: набор генов, представляющих хромосому.
  2. фенотип: фактическое физическое представление хромосомы.

В приведенном выше примере двоичное число 0111 является генотипом, а 7 - представлением фенотипа.

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

f(x)=2x+2

Где x - значение хромосомы

Тогда значение приспособленности предыдущей хромосомы будет:

f(7)=2(7)+2=16

Процесс вычисления значения приспособленности хромосомы называется оценкой.

Инициализация

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

Выбор

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

Операторы вариации

На основе выбранных особей в брачном пуле выбираются родители для спаривания. Выбор каждых двух родителей может происходить путем последовательного выбора родителей (1–2, 3–4 и т. Д.). Другой способ - случайный выбор родителей.

Для каждых двух выбранных родителей существует ряд операторов вариации, которые нужно применить, например:

  1. Кроссовер (рекомбинация)
  2. Мутация

На рисунке 4 приведен пример для этих операторов.

Кроссовер

Кроссовер в GA генерирует новое поколение так же, как и естественная мутация. Мутируя родителей старого поколения, потомки нового поколения несут гены от обоих родителей. Количество генов, передаваемых от каждого родителя, случайно. Помните, что GA - это случайный советник. Иногда потомство забирает половину своих генов от одного родителя, а другую половину от другого родителя, и иногда такие процентные изменения меняются. Для каждых двух родителей кроссовер происходит путем выбора случайной точки в хромосоме и обмена генами до и после этой точки от ее родителей. Полученные хромосомы являются потомством. Таким образом, оператор называется одноточечным кроссовером.

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

Мутация

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

Но если значение гена исходит из пространства, содержащего более двух значений, таких как 1,2,3,4 и 5, то бинарная мутация не будет применима, и мы должны найти другой способ. Один из способов - выбрать случайное значение из такого набора значений, как показано на рисунке 5.

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

Человек после мутации называется мутантом.

использованная литература

[1] Эйбен, Агостон Э. и Джеймс Э. Смит. Введение в эволюционные вычисления. Vol. 53. Гейдельберг: Спрингер, 2003.

Исходная статья доступна в LinkedIn по этой ссылке: https://www.linkedin.com/pulse/introduction-optimization-genetic-algorithm-ahmed-gad

Он также доступен на KDnuggets по этой ссылке: https://www.kdnuggets.com/2018/03/introduction-optimization-with-genetic-algorithm.html

Для связи с автором:

LinkedIn: https://linkedin.com/in/ahmedfgad

Электронная почта: [email protected]