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

Введение

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

Графическое представление

Что происходит внутри Google Analytics?

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

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

- GA производит более уникальные случайные решения во втором поколении

- Этот процесс продолжается до тех пор, пока не будут достигнуты наиболее оптимальные решения или не будет достигнут жесткий предел генерации.

Что такое генетические операторы?

GA имеет два основных генетических оператора: Кросс-овер и Мутация.

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

Мутация. Родительское решение выбирается и изменяется, чтобы получить лучшее дочернее решение.

Всего у RGenoud 9 генетических операций, которые представляют собой разные формы основного кроссовера и мутации. Пользователь может установить вес для каждого из 9 операторов как (P1 = 20, P2 = 15… .P9 = 10). Чем выше вес, тем выше использование оператора при создании новых решений.

Пример 1:

GA для непрерывных данных

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

Ниже приведен пример бизнес-задачи, которая была сведена к форме уравнения.

В приведенном ниже коде запускается алгоритм GA для определения значений x1, x2 и x3 таким образом, чтобы значение y было максимальным.

setwd("D:/Puneeth Workshop/personal/Personal Workshop/Genetic Algorithm Paper")
library("rgenoud")
##---
# Using GA to solve an equation with floating points.
##---
#Define the objective function
func <-  function(sol){
#GA provides the solution/population as a vector of length 3  
x1 <- sol[1]
x2 <- sol[2]
x3 <- sol[3]
# Equation
y=3*x1 + tan(x2) - cos(x3)
#Return the value to GA  
  return(y)
}
# Set the boundary values for each parameter X1,X2 and X3
# X1 should be between value 3 and 5. x2 between 2 and 8.
mat <- matrix(c(3,5,2,8,1,4),3,2,byrow = TRUE)
# Run the GA Algorithm
GA <- genoud(func,nvars = 3,max = TRUE,pop.size = 100,max.generations = 100,wait.generations = 10,Domains = mat,boundary.enforcement = 2,print.level = 2)
# Maximum possible solution of the equations 
GA$value
# The parameters of the solutions
GA$par

Целевая функция (func): простая определяемая пользователем функция, в которой выполняется решение.

nvars: количество переменных, переданных в целевую функцию.

max: определите, является ли решение проблемой максимизации или минимизации.

pop.size: количество популяции или решения в каждом поколении.

max.generations: максимальное количество произведенных поколений.

домены: устанавливает граничный предел для каждой переменной.

Border.enforcement: убедитесь, что значения переменных находятся в установленных пределах.

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

Пример 2:

GA для дискретных данных с ограничениями

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

Графические представления

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

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

Таблица объемов продукта.

Таблица стоимости складских площадей.

В идеальной ситуации алгоритм будет хранить все 10 продуктов на складе W1 с наименьшими затратами на единицу объема. Однако это не соответствовало бы ограничениям по вместимости склада. Следовательно, мы применяем штраф к решениям, которые не соответствуют ограничениям. Это гарантирует, что окончательное решение, к которому мы приходим, будет наилучшим возможным решением, удовлетворяющим всем применяемым ограничениям.

Ниже приведен код

#GA to solve discrete data to simulate multiple scenarios and use constrains and penalty.
library("rgenoud")
#Create the tables
Prod <- data.frame(prod=c('P1','P2','P3','P4','P5','P6','P7','P8','P9','P10'),Vol=c(5,10,15,5,20,15,10,20,5,5))
WH <- data.frame(WH=c('1','2','3','4'),WH.Cost=c(5,10,12,15),Capacity=c(25,25,25,55))
func <- function(sol){
  
  #Add the product-warehouse allignment by GA to the product table
  Prod <- cbind(Prod,sol)
  
  #Obtain the warehouse costs based on the stocking allginments
  Prod <- merge(Prod,WH,by.x="sol",by.y="WH")
  
  #Determine the total warehouse stocking costs
  Prod$cost <- Prod$Vol * Prod$WH.Cost
  
  #Total stocking Cost
  Tot.Cost <- sum(Prod$cost)
  
  #Check for Warehouse Capacity
  Cap <- aggregate(Prod$Vol,by=list(Prod$sol),FUN=sum)
  Cap$Group.1 <- as.factor(Cap$Group.1)
  
  #Apply Penalty if the capacity constrains are not met
  Tot.Cost <- ifelse(Cap[Cap$Group.1=='1',2] > 25 || Cap[Cap$Group.1=='2',2] > 25 || Cap[Cap$Group.1=='3',2] > 25 || Cap[Cap$Group.1=='4',2] > 55,Tot.Cost * 1000,Tot.Cost)
#Return Value
  return(Tot.Cost)
}#End of objective function
# Define Boundary Matrix
# Each product should be stocked across any of the 4 warehouses
mat <- matrix(rep(c(1,4),10),10,2,byrow = TRUE)
GA <- genoud(func,nvars = 10,max = FALSE,pop.size = 500,max.generations = 100,wait.generations = 10,Domains = mat,boundary.enforcement = 2,data.type.int = TRUE)
#data.type.int will ensure GA produces only integers between the set domains ie 1 & 4
# Maximum possible solution of the equations 
GA$value
# The parameters of the solutions
GA$par

Сценарий складирования, смоделированный алгоритмом.

Мы наблюдаем, что алгоритм обеспечивает наилучшее возможное за счет накопления максимальной емкости на складах с более низкими затратами на хранение, то есть W1, W2, W3, а оставшиеся продукты складываются в W4, поскольку у него более высокие затраты на хранение. Также решение и встретило ограничение мощности.

Заключение

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