Недавно Analyticsvidhya опубликовала статью под названием «Введение в генетический алгоритм и их применение в науке о данных». Появился автор Шубхам Джайн, который сделал исчерпывающий и краткий обзор генетического алгоритма на простом для понимания языке и перечислил его практическое применение в представлены различные области, с акцентом на применение генетических алгоритмов в науке о данных. Эта статья была составлена The Heart of the Machine, а ссылка на исходный текст находится в конце статьи.
Введение
Несколько дней назад я задался целью решить практическую задачу - проблему продаж в гипермаркете. После разработки некоторых функций с несколькими простыми моделями я занял 219-е место в таблице лидеров.
Хотя результаты хорошие, я все еще хочу добиться большего. Итак, я начал исследовать методы оптимизации, которые могли бы улучшить оценку. В результате я нашел один, он называется Генетический Алгоритм. После применения его к задаче о продажах в супермаркетах мой результат подскочил на вершину таблицы лидеров.
Правильно, я прыгнул прямо с 219-го на 15-е только с помощью генетического алгоритма, потрясающе! Я считаю, что после прочтения этой статьи вы также сможете свободно применять генетические алгоритмы, и вы обнаружите, что когда вы применяете их к проблеме, с которой имеете дело, эффект значительно улучшается.
содержание
1. Происхождение теории генетических алгоритмов
2. Вдохновленный биологией
3. Определение генетического алгоритма
4. Конкретные шаги генетического алгоритма
инициализация
фитнес-функция
выберите
Пересекать
Мутации
5. Применение генетического алгоритма
Выбор функций
Реализовано с помощью библиотеки TPOT
6. Практическое применение
7. Заключение
1. Происхождение теории генетических алгоритмов
Начнем со знаменитой цитаты Чарльза Дарвина:
Часто выживает не самый сильный или самый умный, а самый адаптируемый.
Вы можете подумать: какое отношение это предложение имеет к генетическим алгоритмам? Фактически вся концепция генетического алгоритма основана на этом предложении.
Поясним на базовом примере:
Давайте начнем с сценария: теперь, когда вы король страны, и, чтобы спасти свою страну от катастрофы, вы применяете набор законов:
- Вы выбираете всех хороших людей и просите их увеличить население нации, рождая.
- Этот процесс продолжался в течение нескольких поколений.
- Вы обнаружите, что у вас уже есть целая группа хороших людей.
Этот пример маловероятен, но я использую его, чтобы помочь вам понять концепцию. То есть мы меняем входное значение (например, население), чтобы получить лучшее выходное значение (например, лучшую страну). Теперь я предполагаю, что у вас есть общее представление о концепции, что смысл генетических алгоритмов должен быть связан с биологией. Итак, давайте быстро рассмотрим некоторые небольшие понятия, чтобы мы могли связать их с пониманием.
2. Вдохновленный биологией
Я думаю, вы еще помните эту фразу: «Клетки — краеугольный камень всего живого». Хромосомы представляют собой агрегаты ДНК.
Традиционно эти хромосомы могут быть представлены последовательностями чисел 0 и 1.
Хромосома состоит из генов, которые, по сути, являются строительными блоками ДНК.Каждый ген в ДНК кодирует уникальный признак, например цвет волос или глаз. Я надеюсь, что вы вспомните биологические концепции, упомянутые здесь, прежде чем продолжить чтение. Эта часть закончена, теперь давайте посмотрим, что на самом деле означает так называемый генетический алгоритм?
3. Определение генетического алгоритма
Сначала давайте вернемся к рассмотренному ранее примеру и подведем итоги того, что мы сделали.
- Во-первых, мы устанавливаем начальную численность населения нации.
- Затем мы определяем функцию, которую используем, чтобы отличать хороших людей от плохих.
- Опять же, мы отбираем хороших людей и позволяем им производить собственное потомство.
- В конце концов, эти потомки заменяют некоторых плохих парней из первоначальных граждан и повторяют процесс.
Вот как на самом деле работает генетический алгоритм, то есть он в основном пытается в какой-то степени имитировать процесс эволюции.
Итак, чтобы формально определить генетический алгоритм, мы можем думать о нем как о методе оптимизации, который пытается найти некоторые входные данные, с помощью которых мы можем получить наилучшее выходное значение или результат. Принцип работы генетического алгоритма также взят из биологии. Конкретный процесс показан на следующем рисунке:
Итак, теперь давайте разберем весь процесс шаг за шагом.
4. Конкретные шаги генетического алгоритма
Чтобы упростить объяснение, давайте сначала разберемся со знаменитой задачей комбинаторной оптимизации «задачей о рюкзаке». Если вы все еще не понимаете, вот версия моего объяснения.
К примеру, вы собираетесь гулять месяц, а носить рюкзак можете только с ограничением по весу в 30 кг. Теперь у вас есть разные необходимые предметы, каждый со своими «очками выживания» (как указано в таблице ниже). Поэтому ваша цель — максимизировать свои «очки выживания» при ограниченном весе рюкзака.
4.1 Инициализация
Здесь мы используем генетический алгоритм для решения этой задачи о рюкзаке. Первым шагом является определение нашей популяции. Популяция состоит из особей, и каждая особь имеет свой набор хромосом.
Мы знаем, что хромосомы могут быть выражены в виде двоичных строк.В этой задаче 1 представляет наличие гена в следующей позиции, а 0 означает потерю. (Примечание переводчика: автор заимствует хромосомы и гены для решения предыдущей задачи о рюкзаке, поэтому гены в определенном положении представляют элементы в приведенной выше таблице задач о рюкзаке, например, спальный мешок в первой позиции, затем это отражается в хромосоме. в это время. Положение «гена» хромосомы — это первый «ген» этой хромосомы.)
Теперь давайте рассмотрим 4 хромосомы на рисунке как нашу начальную совокупность значений.
4.2 Фитнес-функция
Далее, давайте рассчитаем показатели пригодности для первых двух хромосом. Для хромосомы A1 [100110] имеются:
Аналогично, для хромосомы A2 [001110] имеем:
По этому вопросу мы утверждаем, что, когда хромосома содержит больше показателей выживания, это означает, что она более адаптивна.
Таким образом, из рисунка видно, что хромосома 1 более адаптивна, чем хромосома 2.
4.3 Выбор
Теперь мы можем начать выбирать подходящие хромосомы из популяции и позволять им «спариваться» друг с другом, чтобы произвести собственное потомство. Это общая идея операции отбора, но это приведет к тому, что хромосомы будут меньше отличаться друг от друга через несколько поколений и потеряют разнообразие. Поэтому мы обычно используем «метод выбора колеса рулетки».
Представьте себе колесо рулетки, теперь разделим его на m частей, где m — количество хромосом в нашей популяции. Площадь области, занимаемой каждой хромосомой на рулетке, будет выражена пропорционально показателю пригодности.
На основе значений на изображении выше мы создаем следующую «рулетку».
Теперь колесо начинает вращаться, и мы выбираем область, на которую указывает фиксированная точка на картинке, в качестве первого родителя. Затем для второго родителя делаем то же самое. Иногда мы также отмечаем два фиксированных указателя на пути, как показано ниже:
Таким образом, мы можем получить обоих родителей за один раунд. Мы называем этот метод «метод стохастической универсальной селекции».
4.4 Кроссовер
На предыдущем шаге мы выбрали родительские хромосомы, которые дадут потомство. Итак, с биологической точки зрения, так называемый «кроссовер» на самом деле относится к размножению. Теперь давайте «скрестим» хромосомы 1 и 4 (выделенные на предыдущем шаге), см. изображение ниже:
Это самая основная форма пересечения, и мы называем ее «пересечение в одной точке». Здесь мы случайным образом выбираем точку кроссинговера, а затем выполняем перекрестный обмен между хромосомами до и после точки кроссинговера, таким образом производя новое потомство.
Если вы задаете две точки пересечения, то этот метод называется «многоточечное пересечение», см. рисунок ниже:
4.5 Вариация
Если мы теперь посмотрим на это с биологической точки зрения, то зададимся вопросом: имеют ли потомки, полученные в результате описанного выше процесса, те же черты, что и их родители? Ответ - нет. По мере того как потомство растет, в его генах происходят изменения, которые отличают его от родителей. Мы называем этот процесс «мутацией», и его можно определить как случайные изменения, происходящие в хромосомах, и именно благодаря мутациям в популяции существует разнообразие.
На следующем рисунке показан простой пример мутации:
После завершения мутации мы получаем новую особь, и эволюция завершается, весь процесс выглядит следующим образом:
После раунда «генетической мутации» мы используем функцию пригодности для проверки этих новых потомков.Если функция определяет, что они достаточно подходят, они будут использоваться для замены тех хромосом, которые недостаточно подходят из популяции. Возникает вопрос: по какому стандарту мы должны, наконец, судить о том, что потомство достигло наилучшего уровня физической подготовки?
Вообще говоря, существуют следующие условия прекращения:
- После X итераций в целом мало что изменилось.
- Заранее определим количество эволюций алгоритма.
- Когда наша фитнес-функция достигает заранее определенного значения.
Хорошо, теперь я предполагаю, что у вас есть базовое понимание сути генетических алгоритмов, так что теперь давайте применим его в сценарии науки о данных.
5. Применение генетического алгоритма
5.1 Выбор функций
Подумайте об этом всякий раз, когда вы участвуете в конкурсе по науке о данных, какой метод вы используете, чтобы выбрать те функции, которые важны для прогнозирования вашей целевой переменной? Вы часто оцениваете важность функций в своей модели, затем вручную устанавливаете порог и выбираете функции, важность которых выше этого порога.
Итак, есть ли способ справиться с этим лучше? Фактически, одним из самых продвинутых алгоритмов для задачи выбора признаков является генетический алгоритм.
Наш предыдущий подход к задаче о рюкзаке может быть полностью применен здесь. Теперь давайте начнем с установления «хромосомной» популяции, где хромосомы по-прежнему представляют собой двоичные строки, «1» означает, что модель включает функцию, «0 означает, что модель исключает функцию».
Однако одно отличие состоит в том, что наша фитнес-функция должна немного измениться. Фитнес-функция здесь должна быть эталоном точности этого соревнования. То есть, если предсказанное значение хромосомы точнее, то можно сказать, что ее пригодность выше.
Теперь я предполагаю, что вы имеете небольшое представление об этом методе. Я не буду сразу объяснять решение этой проблемы, а давайте сначала реализуем его с помощью библиотеки TPOT.
5.2 Реализация с библиотекой TPOT
Эта часть считается целью, которую вы в конечном итоге хотите достичь, когда впервые прочитаете эту статью. То есть: осознать. Итак, сначала давайте кратко рассмотрим библиотеку TPOT (Техника оптимизации конвейера на основе дерева), которая основана на библиотеке scikit-learn. На рисунке ниже показана базовая структура передачи.
Серая область на рисунке автоматически обрабатывается с помощью библиотеки TPOT. Для реализации автоматической обработки этой части необходим генетический алгоритм.
Мы не будем углубляться здесь, а применим это напрямую. Чтобы иметь возможность использовать библиотеку TPOT, вам необходимо сначала установить некоторые библиотеки Python, на которых построен TPOT. Ниже быстро устанавливаем их:
# installing DEAP, update_checker and tqdm
pip install deap update_checker tqdm
# installling TPOT
pip install tpot
Здесь я использовал Big Mart Sales (адрес набора данных:данные hack.analytics vi.com/contest/PRA…код питона:
# import basic libraries
import numpy as np
import pandas as pd
import matplotlib.pyplot as plt
%matplotlib inline
from sklearn import preprocessing
from sklearn.metrics import mean_squared_error
## preprocessing
### mean imputations
train['Item_Weight'].fillna((train['Item_Weight'].mean()), inplace=True)
test['Item_Weight'].fillna((test['Item_Weight'].mean()), inplace=True)
### reducing fat content to only two categories
train['Item_Fat_Content'] = train['Item_Fat_Content'].replace(['low fat','LF'], ['Low Fat','Low Fat'])
train['Item_Fat_Content'] = train['Item_Fat_Content'].replace(['reg'], ['Regular'])
test['Item_Fat_Content'] = test['Item_Fat_Content'].replace(['low fat','LF'], ['Low Fat','Low Fat'])
test['Item_Fat_Content'] = test['Item_Fat_Content'].replace(['reg'], ['Regular'])
train['Outlet_Establishment_Year'] = 2013 - train['Outlet_Establishment_Year']
test['Outlet_Establishment_Year'] = 2013 - test['Outlet_Establishment_Year']
train['Outlet_Size'].fillna('Small',inplace=True)
test['Outlet_Size'].fillna('Small',inplace=True)
train['Item_Visibility'] = np.sqrt(train['Item_Visibility'])
test['Item_Visibility'] = np.sqrt(test['Item_Visibility'])
col = ['Outlet_Size','Outlet_Location_Type','Outlet_Type','Item_Fat_Content']
test['Item_Outlet_Sales'] = 0
combi = train.append(test)
for i in col:
combi[i] = number.fit_transform(combi[i].astype('str'))
combi[i] = combi[i].astype('object')
train = combi[:train.shape[0]]
test = combi[train.shape[0]:]
test.drop('Item_Outlet_Sales',axis=1,inplace=True)
## removing id variables
tpot_train = train.drop(['Outlet_Identifier','Item_Type','Item_Identifier'],axis=1)
tpot_test = test.drop(['Outlet_Identifier','Item_Type','Item_Identifier'],axis=1)
target = tpot_train['Item_Outlet_Sales']
tpot_train.drop('Item_Outlet_Sales',axis=1,inplace=True)
# finally building model using tpot library
from tpot import TPOTRegressor
X_train, X_test, y_train, y_test = train_test_split(tpot_train, target,
train_size=0.75, test_size=0.25)
tpot = TPOTRegressor(generations=5, population_size=50, verbosity=2)
tpot.fit(X_train, y_train)
print(tpot.score(X_test, y_test))
tpot.export('tpot_boston_pipeline.py')
После запуска кода tpot_exported_pipeline.py поместит код Python для оптимизации пути. Мы можем обнаружить, что ExtraTreeRegressor может лучше всего решить эту проблему.
## predicting using tpot optimised pipeline
tpot_pred = tpot.predict(tpot_test)
sub1 = pd.DataFrame(data=tpot_pred)
#sub1.index = np.arange(0, len(test)+1)
sub1 = sub1.rename(columns = {'0':'Item_Outlet_Sales'})
sub1['Item_Identifier'] = test['Item_Identifier']
sub1['Outlet_Identifier'] = test['Outlet_Identifier']
sub1.columns = ['Item_Outlet_Sales','Item_Identifier','Outlet_Identifier']
sub1 = sub1[['Item_Identifier','Outlet_Identifier','Item_Outlet_Sales']]
sub1.to_csv('tpot.csv',index=False)
Если вы отправите этот CSV, то обнаружите, что то, что я обещал в первую очередь, не было полностью реализовано. Так я тебе лгу? конечно, нет. На самом деле в библиотеке TPOT есть простое правило. Если вы не будете запускать TPOT слишком долго, то он не определит наиболее вероятный способ решения вашей проблемы.
Итак, вы должны увеличить алгебру эволюции, взять чашку кофе и пойти на прогулку, а остальное оставить на TPOT. Кроме того, вы также можете использовать эту библиотеку для задач классификации. Для получения дополнительной информации см. этот документ:rhiever.github.io/tpot/. Помимо игры,…
6. Практическое применение
Генетические алгоритмы имеют множество приложений в реальном мире. Здесь я перечислил несколько интересных сценариев, но из-за нехватки места не буду подробно их описывать.
6.1 Технический проект
Инженерное проектирование в значительной степени зависит от компьютерного моделирования и симуляции, чтобы сделать процесс проектирования быстрым и экономичным. Здесь можно оптимизировать генетические алгоритмы и дать хороший результат.
связанные ресурсы:
- Диссертация: Инженерное проектирование с использованием генетических алгоритмов
- адрес:Поклонение.Конечно.Состояние IA.Qota/CGI/view con…
6.2 Маршруты движения и доставки (задача коммивояжера)
Это очень известная проблема, которую используют многие торговые компании, чтобы сделать доставку более быстрой и экономичной. Генетические алгоритмы также используются для решения этой проблемы.
6.3 Роботы
Генетические алгоритмы широко используются в робототехнике. Фактически, генетические алгоритмы в настоящее время используются для создания самообучающихся роботов, которые могут действовать как люди, выполняя такие задачи, как приготовление пищи, стирка и многое другое.
связанные ресурсы:
Диссертация: Генетические алгоритмы для автонастройки управления движением мобильного робота
адрес:PDF-файл: .semantic science.org/7 from 8 from/FAA787…
7. Заключение
Надеемся, что после введения в эту статью вы теперь достаточно понимаете генетический алгоритм и будете использовать библиотеку TPOT для его реализации. Но знание этой статьи также очень ограничено, если вы не практикуете это сами.
Поэтому, читатели и друзья, попробуйте реализовать это сами, будь то соревнования по науке о данных или в жизни.
выбран изAnalyticsvidhya Сборник "Сердце машины"