遗传算法 - 交叉和变异无法正常工作

Genetic Algorithm - Crossover and Mutation not working correctly

我正在使用 GA Package 来最小化一个函数。以下是我实施的几个阶段。

0. Libraries and dataset 

library(clusterSim)      ## for index.DB()
library(GA)              ## for ga() 
data("data_ratio")
dataset2 <- data_ratio
set.seed(555)

1. Binary encoding and generate initial population.

initial_population <- function(object) {
    ## generate a population where for each individual, there will be number of 1's fixed between three to six
    population <- t(replicate(object@popSize, {i <- sample(3:6, 1); sample(c(rep(1, i), rep(0, object@nBits - i)))}))
    return(population)
}

2. Fitness Function Minimizes Davies-Bouldin (DB) Index.

DBI2 <- function(x) {
    ## number of 1's will represent the initial selected centroids and hence the number of clusters
    cl <- kmeans(dataset2, dataset2[x == 1, ])
    dbi <- index.DB(dataset2, cl=cl$cluster, centrotypes = "centroids")
    score <- -dbi$DB

    return(score)
}

3. User defined crossover operator. This method of crossover will avoid situations where no clusters are 'turned-on'. The pseudocode can be found .

pairwise_crossover <- function(object, parents){
    fitness <- object@fitness[parents]
    parents <- object@population[parents, , drop = FALSE]
    n <- ncol(parents)
    children <- matrix(as.double(NA), nrow = 2, ncol = n)
    fitnessChildren <- rep(NA, 2)

    ## finding the min no. of 1's between 2 parents
    m <- min(sum(parents[1, ] == 1), sum(parents[2, ] == 1))
    ## generate a random int from range(1,m)
    random_int <- sample(1:m, 1)
    ## randomly select 'random_int' gene positions with 1's in parent[1, ]
    random_a <- sample(1:length(parents[1, ]), random_int)
    ## randomly select 'random_int' gene positions with 1's in parent[1, ]
    random_b <- sample(1:length(parents[2, ]), random_int)
    ## union them
    all <- sort(union(random_a, random_b))
    ## determine the union positions
    temp_a <- parents[1, ][all]
    temp_b <- parents[2, ][all]

    ## crossover
    parents[1, ][all] <- temp_b
    children[1, ] <- parents[1, ]
    parents[2, ][all] <- temp_a
    children[2, ] <- parents[2, ]

    out <- list(children = children, fitness = fitnessChildren)
    return(out)
}

4. Mutation.

k_min <- 2
k_max <- ceiling(sqrt(75))

my_mutation <- function(object, parent){
    pop <- parent <- as.vector(object@population[parent, ])
    for(i in 1:length(pop)){
            if((sum(pop == 1) < k_max) && pop[i] == 0 | (sum(pop == 1) > k_min && pop[i] == 1)) {
                    pop[i] <- abs(pop[i] - 1)
                    return(pop) 
            }

    }

}

5. Putting the pieces together. Using roulette-wheel selection, crossover prob. = 0.8, mutation prob. = 0.1 

g2<- ga(type = "binary", 
    population = initial_population, 
    fitness = DBI2, 
    selection = ga_rwSelection,
    crossover = pairwise_crossover,
    mutation = my_mutation,
    pcrossover = 0.8,
    pmutation = 0.1,
    popSize = 100, 
    nBits = nrow(dataset2))

我创建初始种群的方式是，对于种群中的每个个体，1's 的数量固定在 3 到 6 之间。交叉和变异运算符旨在确保解决方案最终不会有太多的集群 (1's) 成为 'turned-on'。在整合它们之前，我分别尝试了我的交叉和变异函数，它们似乎工作正常。

理想情况下，最终的解决方案将有 1's +-=1 来自初始种群的数量，即，如果一个个体的染色体中有三个 1's，它将最终随机拥有两个、三个或四个 1's。但我得到了这个解决方案，它显示 12 个集群 (1's) 是 'turned-on'，这意味着交叉和变异运算符运行良好。

> sum(g2@solution==1)
[1] 12

这里的问题可以通过复制所有代码重现。任何熟悉 GA 包的人都可以帮助我吗？

[编辑]

尝试使用不同的数据集 iris，让我陷入了以下错误。 （只改了数据，其余设置不变）

0. Libraries and dataset 

library(clusterSim)      ## for index.DB()
library(GA)              ## for ga() 
## removed last column since it is a categorical data
dataset2 <- iris[-5]
set.seed(555)

> Error in kmeans(dataset2, centers = dataset2[x == 1, ]) : 
  initial centers are not distinct

我试着查看 code，发现这个错误是由 if(any(duplicated(centers))) 引起的。这可能意味着什么？

有几点值得一提：

  1. 在crossover中，为了在parent[1, ]中随机select 'random_int'个基因位置为1，你将下面的代码行从

    random_a <- sample(1:length(parents[1, ]), random_int)

    到

    random_a <- sample(which(parents[1, ]==1), random_int)

    另一位父母也是如此。

    但是，我认为这种交叉策略可以保证任何后代都可以打开的簇位总数最多为其 parent 的 1 位的最大数量（在这种情况下可以是 6从初始种群开始，如果你只想在解决方案基因中有 1 位差异，它不是应该是 4 吗？）。

    下图显示了3个随机selected位置，其中至少一个parent基因有1位，同时交叉产生后代。

  1. 在mutation函数中，我想，为了更明确，我们应该改变这行代码

    if((sum(pop == 1) < k_max) && pop[i] == 0 | (sum(pop == 1) > k_min && pop[i] == 1))

    来自

    if((sum(pop == 1) < k_max && pop[i] == 0) | (sum(pop == 1) > k_min && pop[i] == 1))

    有适当的parenthesis。

  2. 此外，您的 fitness 函数（Davies-Bouldin's index 测量簇分离）似乎有利于打开更多簇。

最后我认为是 mutation 是罪魁祸首，如果您将 k_max 更改为较低的值（例如 3）并将 pmutation 更改为较低的值（例如 pmutation = 0.01)，你会发现在最终的解决方案中，所有的基因都打开了4位。

[编辑]

set.seed(1234)
k_min = 2
k_max = 3 #ceiling(sqrt(75))
#5. Putting the pieces together. Using roulette-wheel selection, crossover prob. = 0.8, mutation prob. = 0.1
g2<- ga(type = "binary", 
        population = initial_population, 
        fitness = DBI2, 
        selection = ga_rwSelection,
        crossover = pairwise_crossover,
        mutation = my_mutation,
        pcrossover = 0.8,
        pmutation = 0.01,
        popSize = 100, 
        nBits = nrow(dataset2))    

g2@solution # there are 6 solution genes
    x1 x2 x3 x4 x5 x6 x7 x8 x9 x10 x11 x12 x13 x14 x15 x16 x17 x18 x19 x20 x21 x22 x23 x24 x25 x26 x27 x28 x29 x30 x31 x32 x33 x34 x35 x36 x37
[1,]  0  0  0  0  0  0  1  0  1   0   1   0   0   0   0   0   0   0   0   0   0   0   0   0   0   0   0   0   0   0   0   0   0   0   0   0   0
[2,]  0  0  0  0  0  0  1  0  0   0   1   0   0   0   0   0   0   1   0   0   0   0   0   0   0   0   0   0   0   0   0   0   0   0   0   0   0
[3,]  0  0  0  0  0  0  1  0  0   0   1   0   0   0   0   0   0   0   0   0   0   1   0   0   0   0   0   0   0   0   0   0   0   0   0   0   0
[4,]  0  0  0  0  0  0  1  1  0   0   0   0   0   0   0   0   0   1   0   0   0   0   0   0   0   0   0   0   0   0   0   0   0   0   0   0   0
[5,]  0  0  0  1  0  0  0  0  0   0   1   0   0   0   0   0   0   1   0   0   0   0   0   0   0   0   0   0   0   0   0   0   0   0   0   0   0
[6,]  0  0  0  1  0  0  0  0  0   0   1   0   0   0   0   0   0   0   0   0   0   1   0   0   0   0   0   0   0   0   0   0   0   0   0   0   0
     x38 x39 x40 x41 x42 x43 x44 x45 x46 x47 x48 x49 x50 x51 x52 x53 x54 x55 x56 x57 x58 x59 x60 x61 x62 x63 x64 x65 x66 x67 x68 x69 x70 x71 x72
[1,]   0   0   1   0   0   0   0   0   0   0   0   0   0   0   0   0   0   0   0   0   0   0   0   0   0   0   0   0   0   0   0   0   0   0   0
[2,]   0   0   1   0   0   0   0   0   0   0   0   0   0   0   0   0   0   0   0   0   0   0   0   0   0   0   0   0   0   0   0   0   0   0   0
[3,]   0   0   1   0   0   0   0   0   0   0   0   0   0   0   0   0   0   0   0   0   0   0   0   0   0   0   0   0   0   0   0   0   0   0   0
[4,]   0   0   1   0   0   0   0   0   0   0   0   0   0   0   0   0   0   0   0   0   0   0   0   0   0   0   0   0   0   0   0   0   0   0   0
[5,]   0   0   1   0   0   0   0   0   0   0   0   0   0   0   0   0   0   0   0   0   0   0   0   0   0   0   0   0   0   0   0   0   0   0   0
[6,]   0   0   1   0   0   0   0   0   0   0   0   0   0   0   0   0   0   0   0   0   0   0   0   0   0   0   0   0   0   0   0   0   0   0   0
     x73 x74 x75
[1,]   0   0   0
[2,]   0   0   0
[3,]   0   0   0
[4,]   0   0   0
[5,]   0   0   0
[6,]   0   0   0

rowSums(g2@solution) # all of them have 4 bits on
#[1] 4 4 4 4 4 4

[EDIT2]

  1. 实际上，crossover策略保证了parent组合中没有额外的位打开，即children中1位的总数=总数parent 中的 1 位，但任何个人 child 都可以打开更多位。下面显示了一个单独的后代可以比 parent 中的任何一个都打开更多位的示例：