基于进化算法的图分区问题修正：实现purple节点占优分区

问题背景 #

需要用进化算法对igraph构建的10行5列网格图做分区，要求分成5个诱导子图：

• 每个子图至少包含5个节点
• 多数子图中purple节点数量多于orange节点

当前基于GA包实现的代码仅能生成垂直分区方案，无法满足purple占优的要求。

原代码 #

library(igraph)
library(GA)
library(ggplot2)
library(dplyr)
library(gridExtra)

# original graph
n_rows <- 10
n_cols <- 5
g <- make_lattice(dimvector = c(n_cols, n_rows))
n_nodes <- vcount(g)

node_colors <- rep("white", n_nodes)
for (row in 0:(n_rows-1)) {
    start_index <- row * n_cols + 1
    node_colors[start_index:(start_index+2)] <- "orange"  
    node_colors[(start_index+3):(start_index+4)] <- "purple"    
}

# define fitness function based on constraints
fitness <- function(solution) {
    subgraphs <- split(1:n_nodes, solution)
    
    # check if all subgraphs have at least 5 nodes
    if (any(sapply(subgraphs, length) < 5)) {
        return(-Inf)
    }
    
    # count purple wins
    purple_wins <- sum(sapply(subgraphs, function(sg) {
        sum(node_colors[sg] == "purple") > sum(node_colors[sg] == "orange")
    }))
    
    return(purple_wins)
}

# genetic Algorithm
ga_result <- ga(
    type = "permutation",
    fitness = fitness,
    min = 1,
    max = 5,
    popSize = 50,
    maxiter = 1000,
    run = 100,
    pmutation = 0.2,
    monitor = FALSE,
    keepBest = TRUE
)

# multiple solutions
n_solutions <- 3  # Number of solutions to display
solutions <- ga_result@solution[1:n_solutions,]

for (i in 1:n_solutions) {
    cat("Solution", i, "\n")
    cat("Fitness score:", ga_result@fitness[i], "\n\n")
    plot_subgraphs(solutions[i,], i)
    cat("\n")
}

运行输出 #

Solution 1 
Fitness score: 2 

Subgraph 1 : 4 9 14 19 24 29 34 39 44 49 
Purple: 10 Orange: 0 

Subgraph 2 : 3 8 13 18 23 28 33 38 43 48 
Purple: 0 Orange: 10 

Subgraph 3 : 2 7 12 17 22 27 32 37 42 47 
Purple: 0 Orange: 10 

Subgraph 4 : 1 6 11 16 21 26 31 36 41 46 
Purple: 0 Orange: 10 

Subgraph 5 : 5 10 15 20 25 30 35 40 45 50 
Purple: 10 Orange: 0 


Solution 2 
Fitness score: 2 

Subgraph 1 : 5 10 15 20 25 30 35 40 45 50 
Purple: 10 Orange: 0 

Subgraph 2 : 2 7 12 17 22 27 32 37 42 47 
Purple: 0 Orange: 10 

Subgraph 3 : 4 9 14 19 24 29 34 39 44 49 
Purple: 10 Orange: 0 

Subgraph 4 : 1 6 11 16 21 26 31 36 41 46 
Purple: 0 Orange: 10 

Subgraph 5 : 3 8 13 18 23 28 33 38 43 48 
Purple: 0 Orange: 10 

核心问题 #

1. GA类型选择错误：使用permutation（排列类型）会强制解为节点的排序，天然倾向于垂直/水平的规则分区，限制了解空间的探索
2. 适应度函数引导性不足：仅统计purple占优的子图数量，没有奖励更优的分区结构（如连通性），也没有强化purple的占优幅度，导致算法困在局部最优的垂直分区中

修正方案 #

1. 更换GA类型为integer #

integer类型允许每个节点独立分配分区编号（1-5），完全匹配图分区的需求，打破排列类型带来的规则分区限制。

2. 优化适应度函数 #

• 保留节点数量约束：子图节点数不足5则返回负无穷
• 增加连通性奖励：给连通的诱导子图额外加分，引导算法生成合理的子图结构
• 强化purple占优奖励：不仅统计占优子图数量，还根据purple与orange的数量差额外加分，鼓励算法生成purple占比更高的子图

3. 调整GA参数 #

• 增大种群规模、迭代次数，提高变异率，帮助算法跳出局部最优
• 使用适合整数类型的交叉和变异策略

修正后的完整代码 #

library(igraph)
library(GA)
library(ggplot2)
library(dplyr)
library(gridExtra)

# 构建网格图
n_rows <- 10
n_cols <- 5
g <- make_lattice(dimvector = c(n_cols, n_rows))
n_nodes <- vcount(g)

# 分配节点颜色：每行前3个orange，后2个purple
node_colors <- rep("white", n_nodes)
for (row in 0:(n_rows-1)) {
    start_index <- row * n_cols + 1
    node_colors[start_index:(start_index+2)] <- "orange"  
    node_colors[(start_index+3):(start_index+4)] <- "purple"    
}

# 定义改进的适应度函数
fitness <- function(solution) {
    subgraphs <- split(1:n_nodes, solution)
    
    # 约束：每个子图至少5个节点
    if (any(sapply(subgraphs, length) < 5)) {
        return(-Inf)
    }
    
    # 计算每个子图的核心统计
    subgraph_stats <- lapply(subgraphs, function(sg) {
        list(
            purple = sum(node_colors[sg] == "purple"),
            orange = sum(node_colors[sg] == "orange"),
            # 检查诱导子图是否连通
            connected = is.connected(induced_subgraph(g, sg))
        )
    })
    
    # 奖励1：purple占优的基础分 + 占优幅度额外奖励
    purple_bonus <- sum(sapply(subgraph_stats, function(st) {
        if (st$purple > st$orange) {
            1 + (st$purple - st$orange)/5  # 基础分1，每多1个purple加0.2分
        } else {
            0
        }
    }))
    
    # 奖励2：连通子图额外加分
    connectivity_bonus <- sum(sapply(subgraph_stats, function(st) {
        if (st$connected) 0.5 else 0
    }))
    
    # 总适应度
    return(purple_bonus + connectivity_bonus)
}

# 运行改进后的遗传算法
ga_result <- ga(
    type = "integer",  # 更换为整数分配类型
    fitness = fitness,
    min = 1,
    max = 5,
    popSize = 100,  # 增大种群规模
    maxiter = 1500,  # 增加迭代次数
    run = 150,
    pmutation = 0.3,  # 提高变异率
    crossover = gaint_spCrossover,  # 适合整数类型的交叉策略
    mutation = gaintMutator,  # 适合整数类型的变异策略
    monitor = FALSE,
    keepBest = TRUE
)

# 补充原代码缺失的绘图函数
plot_subgraphs <- function(solution, idx) {
    partition_colors <- rainbow(5)[solution]
    plot(g, 
         vertex.color = partition_colors,
         vertex.size = 8,
         vertex.label = node_colors,
         main = paste("Solution", idx, "Fitness:", round(ga_result@fitness[idx], 2))
    )
    # 打印子图统计
    subgraphs <- split(1:n_nodes, solution)
    for (i in 1:length(subgraphs)) {
        sg <- subgraphs[[i]]
        purple <- sum(node_colors[sg] == "purple")
        orange <- sum(node_colors[sg] == "orange")
        cat(paste0("Subgraph ", i, " : ", paste(sg, collapse = " "), "\n"))
        cat(paste0("Purple: ", purple, " Orange: ", orange, "\n\n"))
    }
}

# 展示前3个最优解
n_solutions <- 3
solutions <- ga_result@solution[1:n_solutions,]

for (i in 1:n_solutions) {
    cat("Solution", i, "\n")
    cat("Fitness score:", round(ga_result@fitness[i], 2), "\n\n")
    plot_subgraphs(solutions[i,], i)
    cat("\n")
}

修正说明 #

• 更换GA类型后，算法可以自由探索任意分区结构，不再局限于垂直/水平分区
• 优化后的适应度函数同时引导算法满足节点数量约束、purple占优、子图连通性三个核心需求
• 参数调整提升了算法的全局搜索能力，更容易跳出局部最优解

内容的提问来源于stack exchange，提问作者farrow90