基于Genalg包的R语言整数规划消防站配置问题咨询

嘿，我刚好折腾过用genalg解决这类组合优化问题，结合你的需求给你梳理下怎么把约束加回去，拿到和Excel整数规划匹配的结果：

先明确核心目标与约束 #

咱们的核心是最小化消防站的数量，硬约束是任意两个消防站之间的车程不能超过15分钟，而且你已经有了Excel IP的预期结果，这就有了很好的参考基准。

把约束加回genalg的关键步骤 #

genalg作为遗传算法包，核心是靠适应度函数引导搜索方向，所以约束得嵌到这个函数里，给违反规则的解加惩罚，让算法自动避开它们。

1. 重构适应度函数，嵌入约束逻辑 #

首先得把你的车程时间数据整理成矩阵（比如travel_time_matrix，travel_time_matrix[i,j]就是城市i到j的车程），然后在适应度函数里做两件事：计算消防站数量（我们要最小化它），检查约束并加惩罚。

给你写个示例代码片段，直接改改就能用：

# 二进制编码：1=在该城市建消防站，0=不建
fitness_func <- function(chromosome) {
  # 先计算当前解的消防站数量
  station_count <- sum(chromosome)
  
  # 找出选中的消防站对应的城市索引
  selected_cities <- which(chromosome == 1)
  
  # 检查约束：所有选中的消防站之间车程必须≤15分钟
  penalty <- 0
  if (length(selected_cities) >= 2) {
    # 生成所有两两组合逐一检查
    city_pairs <- combn(selected_cities, 2)
    for (k in 1:ncol(city_pairs)) {
      i <- city_pairs[1, k]
      j <- city_pairs[2, k]
      if (travel_time_matrix[i, j] > 15) {
        # 每违反一次约束加个大惩罚，比如1000，让这个解的适应度暴跌
        penalty <- penalty + 1000
      }
    }
  }
  
  # genalg默认是最大化适应度，所以我们把目标取反（要最小化数量，就用负的），再加上惩罚
  return(-(station_count + penalty))
}

2. 调优遗传算法参数，让结果更靠谱 #

为了让genalg的结果贴近Excel的IP结果，你得调整几个关键参数，避免算法过早陷入局部最优：

• popSize：把种群规模调大些，比如从默认50改成150或200，给算法更多搜索空间
• iter：增加迭代次数，比如设成800或1000，让算法有足够时间收敛到最优解
• mutationChance：突变概率调到0.02-0.05之间，防止种群过早同质化

调用代码示例：

library(genalg)

# 假设你的城市数量是n，即车程矩阵的行数
n <- nrow(travel_time_matrix)

# 运行遗传算法
ga_result <- rbga.bin(size = n,
                      fitnessFunc = fitness_func,
                      popSize = 150,
                      iter = 800,
                      mutationChance = 0.03)

# 提取最优解
best_chromosome <- ga_result$population[which.max(ga_result$fitness), ]
best_station_count <- sum(best_chromosome)

cat("找到的最优消防站数量：", best_station_count, "\n")
cat("选中的城市索引：", which(best_chromosome == 1), "\n")

3. 和Excel IP结果对比校准 #

跑完之后拿结果和Excel的预期值对比：

• 如果数量一致，说明约束逻辑没问题；
• 如果有差异，先检查约束是不是理解错了（比如是不是要求每个城市到最近消防站车程≤15？如果是这个的话，约束检查逻辑要改成每个城市到选中消防站的最小车程是否达标）；
• 要是结果波动大，就再调大种群规模或迭代次数，或者调整惩罚项的数值，让约束的优先级更高。

小提醒 #

可以先拿一小部分城市数据测试下适应度函数的约束逻辑，确认没问题再跑全量数据，这样能少踩很多坑～

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