Генетический алгоритм - пошаговое объяснение на примере
В этой статье я собираюсь объяснить, как работает генетический алгоритм (ГА), решая очень простую задачу оптимизации. Идея этой заметки состоит в том, чтобы понять концепцию алгоритма путем пошагового решения задачи оптимизации.
Оценим оптимальные значения a и b с помощью GA, которые удовлетворяют приведенному ниже выражению.
Любая задача оптимизации начинается с целевой функции. Приведенное выше уравнение можно записать как:
Понятно, что значение функции равно 0. Эта функция является нашей целевой функцией, и цель состоит в том, чтобы оценить значения a и b таким образом, чтобы значение целевой функции было минимизировано до нуля. Весь процесс оптимизации описан ниже в виде четырех основных шагов и закодирован в R для одной итерации (или генерации).
Шаг 1
Этот шаг начинается с угадывания начальных наборов значений a и b, которые могут включать или не включать оптимальные значения. Эти наборы значений называются «хромосомами», а этап называется «инициализация популяции». Здесь популяция означает наборы a и b [a, b]. Случайная равномерная функция используется для генерации начальных значений a и b. В этой задаче оптимизации шесть наборов значений a и b генерируются между 1 и 10. Код R для генерации исходных хромосом показан ниже.
intial_popu <- NULL x <- 1 repeat { crm <- runif(2,1,10) crm <- as.integer(crm) intial_popu <- rbind(intial_popu,crm) x = x+1 if (x == 7){ break } } rownames(intial_popu) <- c('Cromosome1','Cromosome2','Cromosome3','Cromosome4','Cromosome5','Cromosome6')print(intial_popu) ## [,1] [,2] ## Cromosome1 5 9 ## Cromosome2 9 7 ## Cromosome3 9 9 ## Cromosome4 3 3 ## Cromosome5 7 8 ## Cromosome6 8 4
Шаг 2
На этом этапе вычисляется значение целевой функции для каждой хромосомы. Значение целевой функции также называется значением пригодности. Этот шаг очень важен и называется «выбором», потому что наиболее подходящие хромосомы отбираются из популяции для последующих операций.
На основе значений пригодности выбираются более подходящие хромосомы, у которых есть возможность производить низкие значения функции приспособленности (поскольку значение нашей целевой функции должно быть равно 0), и им позволяют выжить в последующих поколениях. Некоторые хромосомы отбрасываются, поскольку они непригодны для получения низких значений приспособленности.
Одним из наиболее широко используемых методов отбора в GA является «метод колеса рулетки». Метод колеса рулетки подробно рассматривается ниже.
Метод колеса рулетки
Колесо рулетки - это круговая диаграмма, где стоимость каждого пирога выражается с точки зрения вероятности пригодности. Обратите внимание, что значение пригодности и вероятность пригодности - это два разных термина. В этой задаче оптимизации хромосома, которая дает низкое значение пригодности, имеет высокую вероятность пригодности. Вероятность приспособленности каждой хромосомы вычисляется на основе значений приспособленности. Хромосома с высокой вероятностью пригодности будет иметь больше шансов быть выбранной. Следующее выражение используется для вычисления вероятности пригодности отдельной хромосомы.
Где, FP = вероятность пригодности i -й хромосомы, Fi = значение пригодности i -й хромосомы
На этом рисунке показаны вероятности пригодности для шести разных хромосом, вычисленные с использованием приведенного выше выражения. Сумма всех вероятностей пригодности всегда должна быть равна 1.
Чтобы выбрать наиболее подходящие хромосомы, генерируются шесть случайных вероятностей (т. Е. Для генерации шести значений от 0 до 1). В качестве примера предположим, что сгенерированные шесть вероятностей таковы:
Pr 01 = 0,02 для хромосомы 1
Pr 02 = 0,13 для хромосомы 2
Pr 03 = 0,40 для хромосомы 3
Pr 04 = 0,60 для хромосомы 4
Pr 05 = 0,85 для хромосомы 5
Pr 06 = 0,96 для хромосомы 6
Выбор осуществляется на основе положения указанных выше значений вероятности на колесе рулетки, выраженных в шкале кумулятивных вероятностей пригодности. Сегменты, на которых лежат указанные выше значения, выбираются для следующего шага. Помните, что каждый сегмент представляет соответствующую ему хромосому. Для лучшего понимания колесо рулетки выпрямлено и показаны положения сгенерированных значений вероятности.
На этой иллюстрации хромосомы 1, 2,5,6 выбраны из 6 хромосом. Последовательность хромосом следует слева направо: синий - хромосома -1, оранжевый - хромосома -6. Эти хромосомы будут использоваться для выполнения операции кроссовера на следующем этапе. Наконец, новый набор хромосом:
Новая хромосома-1 = Хромосома -1
Новая хромосома-2 = Хромосома -1
Новая хромосома-3 = Хромосома -2
Новая хромосома-4 = Хромосома -2
Новая хромосома -5 = Хромосома -5
Новая хромосома-6 = Хромосома -6
Вышеуказанные новые хромосомы являются потенциальными родителями для операции кроссовера. Замечено, что хромосомы -3 и -4 были отброшены как непригодные.
Для этой задачи оптимизации ниже представлен фрагмент R-кода для выбора наиболее подходящих хромосом (новой популяции).
## Function to compute fitness fit <- function(A){ a <- A[1] b <- A[2] return(((2*a^2 + b) - 57)) } fitness <- apply(intial_popu, 1, FUN = 'fit') fitting <- 1/(fitness) probfitting <- fitting/sum(fitting)#generate random values of fitness prob. from 0 to 1 prob_gen <- runif(6,0,1) newpopulation <- NULL for(rr in prob_gen){ sum <- 0 for(prob in probfitting){ sum <- sum + prob if(rr < sum){ bin <- prob cromosomeS <- which(probfitting == bin, arr.ind = T) if(length(cromosomeS)>1){ cromosomeS <- cromosomeS[1] } else{ cromosomeS <- cromosomeS } cromname <- paste0('Cromosome',cromosomeS[1]) newcromosome <- intial_popu[which(rownames(intial_popu) == cromname),] break } } newpopulation <- rbind(newpopulation,newcromosome,deparse.level = 2) } rownames(newpopulation) <- rownames(intial_popu)print(newpopulation) ## [,1] [,2] ## Cromosome1 5 9 ## Cromosome2 5 9 ## Cromosome3 9 7 ## Cromosome4 5 9 ## Cromosome5 5 9 ## Cromosome6 5 9
Шаг 3
Этот шаг называется «кроссовером». На этом этапе хромосомы выражаются в виде генов. Это может быть сделано путем преобразования значений a и b в двоичные строки, что означает, что значения должны быть выражены в терминах 0 или 1. Например, двоичная форма числа 9 - [1001].
Что такое кроссовер?
Кроссовер - это «изменение одного (0 или 1) или группы генов (например, [1,0,1])», произошедшее из-за спаривания между двумя родительскими хромосомами. Новая хромосома, полученная после операции кроссовера, называется «потомством». Следующая иллюстрация объясняет процесс кроссовера. Всегда помните, что кроссовер происходит между родительскими хромосомами.
В нашей текущей задаче оптимизации хромосомы, полученные на шаге 2, записываются в двоичном виде. Например, если двоичное представление a = [1,0,0,1] и b = [1,1,1,0], то хромосома [a, b] выражается как [1,0,0, 1,1,1,1,0]. Все хромосомы преобразованы в двоичную форму и записаны в виде матрицы с 6 строками и 8 столбцами.
Здесь вступает в игру один важный параметр, который называется параметр кроссовера. Значение этого параметра находится в диапазоне от 0 до 1. Значение 0,5 указывает на то, что из шести хромосом трем хромосомам разрешено кроссинговер с образованием трех потомков.
Затем идет подбор позиций. Гены будут подвергаться кроссоверу в выбранных положениях хромосомы. Например, если хромосома [1,1,0,1,1,0,0,1] и позиция 2 (слева). Тогда значение 1 будет заменено значением хромосомы спаривания в той же позиции. Помните, что для кроссовера можно выбрать несколько позиций или сегментов.
Блок R-кода, который включает функцию преобразования целого числа в двоичные строки и операцию пересечения, представлен ниже.
##Function to convert integer to binary binary <- function(x) { i <- 0 string <- numeric(32) while(x > 0) { string[32 - i] <- x %% 2 x <- x %/% 2 i <- i + 1 } first <- match(1, string) string[first:32] }##create binary matrix of 8 cols and 6 rows binary_popu <- matrix(NA,nrow = 6,ncol = 8) for(i in 1:nrow(newpopulation)){ x <- binary(newpopulation[i,1]) binary_popu[i,1:length(x)] <- x y <- binary(newpopulation[i,2]) binary_popu[i,5:(4+length(y))] <- y } rownames(binary_popu) <- rownames(newpopulation) cross_paramter <- 0.5 i = 1 crom_cross <- NULL while(length(crom_cross) < 3){ cross.crossover.prob <- runif(6,0,1) crom_cross <- which(cross.crossover.prob < cross_paramter,arr.ind = T) i = i + 1 } parents <- binary_popu[crom_cross,] position = 2 ##crossover position cross_parent <- parents cross_parent[1,1:position] <- parents[2,1:position] cross_parent[2,1:position] <- parents[3,1:position] cross_parent[3,1:position] <- parents[1,1:position] listofindex <- which(row.names(binary_popu) %in% row.names(cross_parent)) offSpring <- binary_popu offSpring[listofindex,] <- cross_parentprint(offSpring) ##offspring after crossover ## [,1] [,2] [,3] [,4] [,5] [,6] [,7] [,8] ## Cromosome1 1 0 1 NA 1 0 0 1 ## Cromosome2 1 0 1 NA 1 0 0 1 ## Cromosome3 1 0 0 1 1 1 1 NA ## Cromosome4 1 0 1 NA 1 0 0 1 ## Cromosome5 1 0 1 NA 1 0 0 1 ## Cromosome6 1 0 1 NA 1 0 0 1
Шаг - 4
Этот шаг называется «мутация». Мутация - это процесс изменения значения гена, т.е. замена значения 1 на 0 и наоборот. Например, если хромосома потомства [1,0,0,1], после мутации она становится [1,1,0,1]. Здесь решено мутировать 2-е значение хромосомы потомства. Он был изменен на 1 с 0.
Теперь возникает вопрос, сколько генов нужно изменить и на каких позициях. Параметр мутации определяет, сколько генов нужно мутировать. Если параметр мутации равен 0,1 (обычно сохраняются низкие значения). Тогда 0,1-кратное общее количество генов может мутировать. В данной задаче оптимизации общее количество генов составляет 48 (6 x 8). Следовательно, допускается мутация 4,8 ~ 5 генов.
Что касается позиций мутаций, выбираются 5 случайных значений строк и столбцов. Иллюстрация процесса мутации приведена ниже.
После мутации бинарные хромосомы преобразуются в целочисленную форму и рассчитываются значения приспособленности. Если какая-либо из хромосом дает целевое значение пригодности, равное 0, мы останавливаемся на этом. В противном случае процесс будет повторяться от шага - 2 до шага - 4, приравнивая мутировавшие хромосомы к новой популяции.
Блок R-кода для этого шага представлен ниже.
mutation_paramter <- 0.09 no.of.mutations <- 4 ## Calculated as nrow(offSpring)*ncol(offSpring)*mutation_paramter randrow <- round(runif(no.of.mutations,1,nrow(offSpring))) rancol <- round(runif(no.of.mutations,1,ncol(offSpring))) ## Now get the offsprings by mutating at above position for(r in 1:length(randrow)){ if(is.na(offSpring[randrow[r],rancol[r]])){ offSpring[randrow[r],rancol[r]] <- NA }else{ if(offSpring[randrow[r],rancol[r]] == 0){ offSpring[randrow[r],rancol[r]] <- 1 }else{ offSpring[randrow[r],rancol[r]] <- 0 } } } print(offSpring) ## Chromosomes after mutation ## [,1] [,2] [,3] [,4] [,5] [,6] [,7] [,8] ## Cromosome1 1 0 1 NA 1 0 0 1 ## Cromosome2 1 0 1 NA 1 0 0 1 ## Cromosome3 1 0 0 1 1 1 0 NA ## Cromosome4 1 0 1 NA 0 0 0 1 ## Cromosome5 1 0 1 NA 1 0 0 1 ## Cromosome6 1 1 1 NA 1 0 0 1## Now convert binary back to integer binary_decimal = function(base_number, base = 2) { split_base = strsplit(as.character(base_number), split = "") return(sapply(split_base, function(x) sum(as.numeric(x) * base^(rev(seq_along(x) - 1))))) } offSpring_inter <- matrix(NA,6,2) for(i in 1:nrow(offSpring)){ a <- offSpring[i,1:4] a <- na.omit(a) a <- as.numeric(paste(a, collapse = "")) a <- binary_decimal(a) b <- offSpring[i,5:8] b <- na.omit(b) b <- as.numeric(paste(b, collapse = "")) b <- binary_decimal(b) offSpring_inter[i,1] <- a offSpring_inter[i,2] <- b } rownames(offSpring_inter) <- rownames(offSpring) ## Chromosomes converted back to integer after end of 1st of generation print(offSpring_inter) ## [,1] [,2] ## Cromosome1 5 9 ## Cromosome2 5 9 ## Cromosome3 9 6 ## Cromosome4 5 1 ## Cromosome5 5 9 ## Cromosome6 7 9
Окончательный результат этой задачи оптимизации показан ниже, где значения пригодности вычислены для 10 поколений. Хромосома 6, то есть [a, b] = [5,7], является оптимальным решением, при котором значение пригодности равно 0.
## Iteration: 1 ## Cromosome1 Cromosome2 Cromosome3 Cromosome4 Cromosome5 Cromosome6 ## -30 76 -17 -18 -3 -45 ## Iteration: 2 ## Cromosome1 Cromosome2 Cromosome3 Cromosome4 Cromosome5 Cromosome6 ## -3 45 -40 -42 -30 -3 ## Iteration: 3 ## Cromosome1 Cromosome2 Cromosome3 Cromosome4 Cromosome5 Cromosome6 ## -3 -3 -3 -3 -7 -3 ## Iteration: 4 ## Cromosome1 Cromosome2 Cromosome3 Cromosome4 Cromosome5 Cromosome6 ## -3 -2 -2 -3 -3 -3 ## Iteration: 6 ## Cromosome1 Cromosome2 Cromosome3 Cromosome4 Cromosome5 Cromosome6 ## -3 -3 -3 -3 -2 -3 ## Iteration: 7 ## Cromosome1 Cromosome2 Cromosome3 Cromosome4 Cromosome5 Cromosome6 ## -3 -20 -3 -3 -3 -2 ## Iteration: 8 ## Cromosome1 Cromosome2 Cromosome3 Cromosome4 Cromosome5 Cromosome6 ## -3 -2 -3 -2 -2 -2 ## Iteration: 9 ## Cromosome1 Cromosome2 Cromosome3 Cromosome4 Cromosome5 Cromosome6 ## 46 -2 -2 -20 -2 -2 ## Iteration: 10 ## Cromosome1 Cromosome2 Cromosome3 Cromosome4 Cromosome5 Cromosome6 ## -3 -19 -1 47 -1 0## The final set of Chromosomes ## [,1] [,2] ## Cromosome1 5 4 ## Cromosome2 4 6 ## Cromosome3 5 6 ## Cromosome4 7 6 ## Cromosome5 5 6 ## Cromosome6 5 7
Ссылка
Деб К. Многоцелевая оптимизация с использованием эволюционных алгоритмов (2005)
