www.machinelearningmastery.ru

Машинное обучение, нейронные сети, искусственный интеллект
Header decor

Home

Введение в оптимизацию с помощью генетического алгоритма

Дата публикации Jul 3, 2018

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

С Pixabay поqimono

Введение

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

Рисунок 1. Хромосома и ген.

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

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

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

Рисунок 2. Генетический алгоритм шагов.

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

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

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

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

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

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

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

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

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

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

Рисунок 3. Пример двоичного кодирования.

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

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

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

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

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

F (X) = 2х + 2

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

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

F (7) = 2 (7) + 2 = 16

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

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

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

выбор

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

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

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

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

  1. Кроссовер (рекомбинация)
  2. перегласовка

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

Рисунок 4. Кроссовер и мутация.

Кроссовер

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

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

перегласовка

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

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

Рисунок 5. Мутация путем случайного обновления некоторых генов.

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

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


Ссылки

[1] Эйбен, Агостон Э. и Джеймс Э. Смит. Введение в эволюционные вычисления. Том 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]

Оригинальная статья

Footer decor

© www.machinelearningmastery.ru | Ссылки на оригиналы и авторов сохранены. | map