R语言中离散选项的组合优化问题求解

适用的优化方法及实现 #

1. 遗传算法（GA包） #

遗传算法天然适配离散参数空间的优化需求，可直接指定每个变量的可选值集合，无需算法自行生成连续参数。

library(GA)

# 目标函数（简化你的原函数）
Fn <- function(x) sum(x)

# 定义每个变量的离散选项集
vars_options <- list(
  As = seq(1.5, 3, by = 0.3),
  Bs = c(1, 2),
  Cs = seq(1, 60, by = 10),
  Ds = seq(60, -60, length.out = 5),
  Es = c(1, 2, 3)
)

# 运行遗传算法，强制变量取指定集合中的值
ga_result <- ga(
  type = "real-valued", 
  fitness = function(x) Fn(x),
  lower = sapply(vars_options, min),
  upper = sapply(vars_options, max),
  popSize = 20,
  maxiter = 50,
  # 自定义突变规则：仅从对应变量的选项中选取新值
  mutation = function(x) {
    idx <- sample(1:length(x), 1)
    x[idx] <- sample(vars_options[[idx]], 1)
    x
  }
)

# 提取最优参数并匹配回原选项集
best_pars <- ga_result@solution
best_pars_matched <- mapply(
  function(x, opts) opts[which.min(abs(x - opts))], 
  as.list(best_pars), vars_options
)
best_pars_matched

2. 粒子群优化（自定义离散版本） #

标准粒子群优化针对连续空间，可通过自定义位置更新规则，让粒子仅在给定的参数选项中移动，适配离散场景。

# 目标函数
Fn <- function(x) sum(x)

# 参数选项集
vars_options <- list(
  As = seq(1.5, 3, by = 0.3),
  Bs = c(1, 2),
  Cs = seq(1, 60, by = 10),
  Ds = seq(60, -60, length.out = 5),
  Es = c(1, 2, 3)
)

# 自定义离散粒子群优化函数
discrete_psoptim <- function(vars_list, fitness_fn, nparticles = 10, maxiter = 30) {
  # 初始化粒子位置：从各变量选项中随机选取
  particles <- do.call(rbind, lapply(1:nparticles, function(i) {
    sapply(vars_list, function(opts) sample(opts, 1))
  }))
  
  # 初始化个体最优与全局最优
  pbest <- particles
  pbest_fitness <- apply(pbest, 1, fitness_fn)
  gbest_idx <- which.max(pbest_fitness)
  gbest <- pbest[gbest_idx, ]
  gbest_fitness <- pbest_fitness[gbest_idx]
  
  # 迭代更新
  for (iter in 1:maxiter) {
    for (i in 1:nparticles) {
      # 更新粒子位置：以概率切换到个体最优、全局最优或随机选项
      for (j in 1:length(vars_list)) {
        particles[i, j] <- sample(
          c(pbest[i, j], gbest[j], sample(vars_list[[j]], 1)),
          1,
          prob = c(0.4, 0.4, 0.2)
        )
      }
      
      # 更新最优记录
      current_fitness <- fitness_fn(particles[i, ])
      if (current_fitness > pbest_fitness[i]) {
        pbest[i, ] <- particles[i, ]
        pbest_fitness[i] <- current_fitness
        
        if (current_fitness > gbest_fitness) {
          gbest <- particles[i, ]
          gbest_fitness <- current_fitness
        }
      }
    }
  }
  
  list(gbest_pars = gbest, gbest_fitness = gbest_fitness)
}

# 运行离散PSO
pso_result <- discrete_psoptim(vars_options, Fn)
pso_result$gbest_pars
pso_result$gbest_fitness

3. 贪心算法 #

贪心算法实现简单、计算高效，适合变量间优先级明确的场景：每次固定其他变量为当前最优值，单独优化一个变量，多轮迭代直到无法提升。

# 目标函数
Fn <- function(x) sum(x)

# 参数选项集
vars_options <- list(
  As = seq(1.5, 3, by = 0.3),
  Bs = c(1, 2),
  Cs = seq(1, 60, by = 10),
  Ds = seq(60, -60, length.out = 5),
  Es = c(1, 2, 3)
)

# 自定义贪心优化函数
greedy_optim <- function(vars_list, fitness_fn) {
  # 初始化当前最优参数
  current_best <- sapply(vars_list, function(opts) opts[1])
  current_best_fitness <- fitness_fn(current_best)
  improved <- TRUE
  
  # 多轮迭代直到无提升
  while (improved) {
    improved <- FALSE
    # 逐个变量优化
    for (var_idx in 1:length(vars_list)) {
      for (opt in vars_list[[var_idx]]) {
        temp_pars <- current_best
        temp_pars[var_idx] <- opt
        temp_fitness <- fitness_fn(temp_pars)
        
        if (temp_fitness > current_best_fitness) {
          current_best <- temp_pars
          current_best_fitness <- temp_fitness
          improved <- TRUE
        }
      }
    }
  }
  
  list(best_pars = current_best, best_fitness = current_best_fitness)
}

# 运行贪心算法
greedy_result <- greedy_optim(vars_options, Fn)
greedy_result$best_pars
greedy_result$best_fitness

方法选择建议 #

• 若参数组合规模极大（百万级以上），遗传算法是优先选择，能在有限迭代中逼近全局最优。
• 若参数维度低、追求计算速度，贪心算法实现简单，但可能陷入局部最优。
• 离散粒子群优化适合需要平衡探索与利用的场景，自定义规则后适配性强。

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