Введение
Генетический алгоритм, как он определен в Википедии, черпает вдохновение в процессе естественного отбора, предложенном Чарльзом Дарвином. В более общем плане мы можем понять естественный процесс и то, как он связан с генетическим алгоритмом, используя следующее описание:
Мы начнем с начальной популяции, которая будет иметь определенные черты, как показано на рисунке 1. Эта начальная популяция будет протестирована в определенной среде, чтобы наблюдать, насколько хорошо индивидуумы (родители) в этой популяции работают на основе заранее определенных критериев пригодности. Пригодность в случае машинного обучения может быть любой метрикой производительности - точностью, точностью, отзывчивостью, оценкой F1, auc и другими. Основываясь на значении приспособленности, мы выбираем наиболее эффективных родителей («выживаемость наиболее приспособленных») в качестве выжившей популяции (рис. 2).
Теперь родители в выжившей популяции будут спариваться, чтобы произвести потомство, используя комбинацию двух шагов: кроссовер / рекомбинация и мутация. В случае кроссовера гены (параметры) от спаривающихся родителей будут рекомбинированы, чтобы произвести потомство, при этом каждый ребенок унаследует некоторые гены (параметры) от каждого родителя (рисунок 3).
Наконец, в случае мутации некоторые значения генов (параметров) будут изменены для сохранения генетического разнообразия (Рисунок 4). Это позволяет природному / генетическому алгоритму обычно находить лучшее решение.
На рисунке 5 показано второе поколение населения, которое будет включать как выживших родителей, так и детей. Мы оставляем выживших родителей, чтобы сохранить наилучшие параметры приспособленности на случай, если показатели приспособленности потомства окажутся хуже, чем у родителей.
Модуль генетического алгоритма для XGBoost:
Мы создадим модуль генетического алгоритма, настроенный для XGBoost. Ниже приводится описание XGboost:
XGBoost - это оптимизированная библиотека с распределенным повышением градиента, которая отличается высокой эффективностью, гибкостью и переносимостью. В нем реализованы алгоритмы машинного обучения в рамках Gradient Boosting.
Модуль будет иметь функции для выполнения четырех шагов: (i) инициализация, (ii) выбор, (iii) кроссовер и (iv) мутация, аналогичные тому, что обсуждалось выше (небольшой раздел этого кода вдохновлен пост здесь).
Инициализация:
Первым шагом является инициализация, при которой параметры инициализируются случайным образом для создания популяции. Это похоже на первое поколение популяции, показанное на рисунке 1. Код ниже показывает процесс инициализации, в котором мы генерируем вектор, содержащий параметры. В случае XGBoost мы выбрали 7 параметров для оптимизации: learning_rate, n_estimators, max_depth, min_child_weight, subsample, colsample_bytree и gamma. Подробное описание этих параметров можно найти здесь.
def initilialize_poplulation(numberOfParents):
learningRate = np.empty([numberOfParents, 1])
nEstimators = np.empty([numberOfParents, 1], dtype = np.uint8)
maxDepth = np.empty([numberOfParents, 1], dtype = np.uint8)
minChildWeight = np.empty([numberOfParents, 1])
gammaValue = np.empty([numberOfParents, 1])
subSample = np.empty([numberOfParents, 1])
colSampleByTree = np.empty([numberOfParents, 1])
for i in range(numberOfParents):
print(i)
learningRate[i] = round(random.uniform(0.01, 1), 2)
nEstimators[i] = random.randrange(10, 1500, step = 25)
maxDepth[i] = int(random.randrange(1, 10, step= 1))
minChildWeight[i] = round(random.uniform(0.01, 10.0), 2)
gammaValue[i] = round(random.uniform(0.01, 10.0), 2)
subSample[i] = round(random.uniform(0.01, 1.0), 2)
colSampleByTree[i] = round(random.uniform(0.01, 1.0), 2)
population = np.concatenate((learningRate, nEstimators, maxDepth, minChildWeight, gammaValue, subSample, colSampleByTree), axis= 1)
return population
Пределы параметров основаны либо на пределах, описанных в документации XGBoost, либо на разумном предположении, если верхний предел установлен на бесконечность. Мы начинаем с создания пустого массива для каждого параметра, а затем заполняем его случайными значениями.
Выбор родителей (выживание наиболее приспособленных)
На втором этапе мы обучаем нашу модель, используя исходную популяцию, и вычисляем значение пригодности. В этом случае мы рассчитаем F1-рейтинг.
def fitness_f1score(y_true, y_pred):
fitness = round((f1_score(y_true, y_pred, average='weighted')), 4)
return fitness
#train the data annd find fitness score
def train_population(population, dMatrixTrain, dMatrixtest, y_test):
fScore = []
for i in range(population.shape[0]):
param = { 'objective':'binary:logistic',
'learning_rate': population[i][0],
'n_estimators': population[i][1],
'max_depth': int(population[i][2]),
'min_child_weight': population[i][3],
'gamma': population[i][4],
'subsample': population[i][5],
'colsample_bytree': population[i][6],
'seed': 24}
num_round = 100
xgbT = xgb.train(param, dMatrixTrain, num_round)
preds = xgbT.predict(dMatrixtest)
preds = preds>0.5
fScore.append(fitness_f1score(y_test, preds))
return fScore
Мы определим, сколько родителей мы хотели бы выбрать, и создадим массив с выбранными родителями на основе их значения пригодности.
#select parents for mating
def new_parents_selection(population, fitness, numParents):
selectedParents = np.empty((numParents, population.shape[1])) #create an array to store fittest parents
#find the top best performing parents
for parentId in range(numParents):
bestFitnessId = np.where(fitness == np.max(fitness))
bestFitnessId = bestFitnessId[0][0]
selectedParents[parentId, :] = population[bestFitnessId, :]
fitness[bestFitnessId] = -1 #set this value to negative, in case of F1-score, so this parent is not selected again
return selectedParents
Кроссовер
Существуют различные методы определения кроссовера в случае генетических алгоритмов », такие как одноточечный, двухточечный и k-точечный кроссовер, равномерный кроссовер и кроссовер для упорядоченных списков. Мы собираемся использовать однородный кроссовер, где каждый параметр для ребенка будет независимо выбран от родителей на основе определенного распределения. В нашем случае мы будем использовать «дискретное равномерное распределение из numpy random function.
'''
Mate these parents to create children having parameters from these parents (we are using uniform crossover method)
'''
def crossover_uniform(parents, childrenSize):
crossoverPointIndex = np.arange(0, np.uint8(childrenSize[1]), 1, dtype= np.uint8) #get all the index
crossoverPointIndex1 = np.random.randint(0, np.uint8(childrenSize[1]), np.uint8(childrenSize[1]/2)) # select half of the indexes randomly
crossoverPointIndex2 = np.array(list(set(crossoverPointIndex) - set(crossoverPointIndex1))) #select leftover indexes
children = np.empty(childrenSize)
'''
Create child by choosing parameters from two parents selected using new_parent_selection function. The parameter values
will be picked from the indexes, which were randomly selected above.
'''
for i in range(childrenSize[0]):
#find parent 1 index
parent1_index = i%parents.shape[0]
#find parent 2 index
parent2_index = (i+1)%parents.shape[0]
#insert parameters based on random selected indexes in parent 1
children[i, crossoverPointIndex1] = parents[parent1_index, crossoverPointIndex1]
#insert parameters based on random selected indexes in parent 1
children[i, crossoverPointIndex2] = parents[parent2_index, crossoverPointIndex2]
return children
Мутация
Последним шагом будет привнесение разнообразия в детей путем случайного выбора одного из параметров и изменения его значения на случайную величину. Мы также введем некоторые ограничения, чтобы ограничить изменяемые значения в определенном диапазоне. Пропуск этих ограничений может привести к ошибке.
def mutation(crossover, numberOfParameters):
#Define minimum and maximum values allowed for each parameter
minMaxValue = np.zeros((numberOfParameters, 2))
minMaxValue[0:] = [0.01, 1.0] #min/max learning rate
minMaxValue[1, :] = [10, 2000] #min/max n_estimator
minMaxValue[2, :] = [1, 15] #min/max depth
minMaxValue[3, :] = [0, 10.0] #min/max child_weight
minMaxValue[4, :] = [0.01, 10.0] #min/max gamma
minMaxValue[5, :] = [0.01, 1.0] #min/maxsubsample
minMaxValue[6, :] = [0.01, 1.0] #min/maxcolsample_bytree
# Mutation changes a single gene in each offspring randomly.
mutationValue = 0
parameterSelect = np.random.randint(0, 7, 1)
print(parameterSelect)
if parameterSelect == 0: #learning_rate
mutationValue = round(np.random.uniform(-0.5, 0.5), 2)
if parameterSelect == 1: #n_estimators
mutationValue = np.random.randint(-200, 200, 1)
if parameterSelect == 2: #max_depth
mutationValue = np.random.randint(-5, 5, 1)
if parameterSelect == 3: #min_child_weight
mutationValue = round(np.random.uniform(5, 5), 2)
if parameterSelect == 4: #gamma
mutationValue = round(np.random.uniform(-2, 2), 2)
if parameterSelect == 5: #subsample
mutationValue = round(np.random.uniform(-0.5, 0.5), 2)
if parameterSelect == 6: #colsample
mutationValue = round(np.random.uniform(-0.5, 0.5), 2)
#indtroduce mutation by changing one parameter, and set to max or min if it goes out of range
for idx in range(crossover.shape[0]):
crossover[idx, parameterSelect] = crossover[idx, parameterSelect] + mutationValue
if(crossover[idx, parameterSelect] > minMaxValue[parameterSelect, 1]):
crossover[idx, parameterSelect] = minMaxValue[parameterSelect, 1]
if(crossover[idx, parameterSelect] < minMaxValue[parameterSelect, 0]):
crossover[idx, parameterSelect] = minMaxValue[parameterSelect, 0]
return crossover
Реализация
Мы реализуем модуль, описанный выше, для обучения на наборе данных. Набор данных взят из Репозитория машинного обучения UCI. Он содержит набор из 102 молекул, 39 из которых идентифицированы людьми как обладающие запахом, который можно использовать в парфюмерии, а 69 не имеют желаемого запаха. Набор данных содержит 6 590 низкоэнергетических конформаций этих молекул, содержащих 166 характеристик. Мы делаем минимальные предубеждения как цель этого урока, чтобы понять генетический алгоритм.
# Importing the libraries
import numpy as np
import pandas as pd
import geneticXGboost #this is the module we crated above
import xgboost as xgb
np.random.seed(723)
# Importing the dataset
dataset = pd.read_csv('clean2.data', header=None)
X = dataset.iloc[:, 2:168].values #discard first two coloums as these are molecule's name and conformation's name
y = dataset.iloc[:, 168].values #extrtact last coloum as class (1 => desired odor, 0 => undesired odor)
# Splitting the dataset into the Training set and Test set
from sklearn.model_selection import train_test_split
X_train, X_test, y_train, y_test = train_test_split(X, y, test_size = 0.20, random_state = 97)
# Feature Scaling
from sklearn.preprocessing import StandardScaler
sc = StandardScaler()
X_train = sc.fit_transform(X_train)
X_test = sc.transform(X_test)
#XGboost Classifier
#model xgboost
#use xgboost API now
xgDMatrix = xgb.DMatrix(X_train, y_train) #create Dmatrix
xgbDMatrixTest = xgb.DMatrix(X_test, y_test)
Для начала у нас есть 8 родителей, и мы выбираем 4 наиболее подходящих для спаривания родителей. Создадим 4 поколения и будем следить за фитнесом (F1-score). Половина родителей в следующем поколении будут наиболее подходящими родителями, выбранными из предыдущего поколения. Это позволит нам сохранить лучший показатель пригодности, по крайней мере, такой же, как у предыдущего поколения, в случае, если показатель пригодности детей будет хуже.
numberOfParents = 8 #number of parents to start
numberOfParentsMating = 4 #number of parents that will mate
numberOfParameters = 7 #number of parameters that will be optimized
numberOfGenerations = 4 #number of genration that will be created
#define the population size
populationSize = (numberOfParents, numberOfParameters)
#initialize the population with randomly generated parameters
population = geneticXGboost.initilialize_poplulation(numberOfParents)
#define an array to store the fitness hitory
fitnessHistory = np.empty([numberOfGenerations+1, numberOfParents])
#define an array to store the value of each parameter for each parent and generation
populationHistory = np.empty([(numberOfGenerations+1)*numberOfParents, numberOfParameters])
#insert the value of initial parameters in history
populationHistory[0:numberOfParents, :] = population
for generation in range(numberOfGenerations):
print("This is number %s generation" % (generation))
#train the dataset and obtain fitness
fitnessValue = geneticXGboost.train_population(population=population, dMatrixTrain=xgDMatrix, dMatrixtest=xgbDMatrixTest, y_test=y_test)
fitnessHistory[generation, :] = fitnessValue
#best score in the current iteration
print('Best F1 score in the this iteration = {}'.format(np.max(fitnessHistory[generation, :])))
#survival of the fittest - take the top parents, based on the fitness value and number of parents needed to be selected
parents = geneticXGboost.new_parents_selection(population=population, fitness=fitnessValue, numParents=numberOfParentsMating)
#mate these parents to create children having parameters from these parents (we are using uniform crossover)
children = geneticXGboost.crossover_uniform(parents=parents, childrenSize=(populationSize[0] - parents.shape[0], numberOfParameters))
#add mutation to create genetic diversity
children_mutated = geneticXGboost.mutation(children, numberOfParameters)
'''
We will create new population, which will contain parents that where selected previously based on the
fitness score and rest of them will be children
'''
population[0:parents.shape[0], :] = parents #fittest parents
population[parents.shape[0]:, :] = children_mutated #children
populationHistory[(generation+1)*numberOfParents : (generation+1)*numberOfParents+ numberOfParents , :] = population #srore parent information
Наконец, мы получаем лучший результат и соответствующие параметры:
#Best solution from the final iteration
fitness = geneticXGboost.train_population(population=population, dMatrixTrain=xgDMatrix, dMatrixtest=xgbDMatrixTest, y_test=y_test)
fitnessHistory[generation+1, :] = fitness
#index of the best solution
bestFitnessIndex = np.where(fitness == np.max(fitness))[0][0]
#Best fitness
print("Best fitness is =", fitness[bestFitnessIndex])
#Best parameters
print("Best parameters are:")
print('learning_rate', population[bestFitnessIndex][0])
print('n_estimators', population[bestFitnessIndex][1])
print('max_depth', int(population[bestFitnessIndex][2]))
print('min_child_weight', population[bestFitnessIndex][3])
print('gamma', population[bestFitnessIndex][4])
print('subsample', population[bestFitnessIndex][5])
print('colsample_bytree', population[bestFitnessIndex][6])
Теперь давайте визуализируем изменение приспособленности популяции с каждым поколением (рисунок ниже). Хотя мы уже начали с высокого показателя F1 (~ 0,98), у двух родителей в случайно сгенерированной исходной популяции мы смогли улучшить его в последнем поколении. Самый низкий показатель F1 составил 0,9143 для одного родителя в исходной популяции, а лучший результат - 0,9947 для одного из родителей в последнем поколении. Это демонстрирует, что мы можем улучшить метрику производительности в XGBoost с помощью простой реализации генетического алгоритма. Окончательный код можно найти в моем аккаунте на github. Он также содержит код, который позволит вам наблюдать за изменением различных параметров с каждым поколением.
