算力网络（Computing Power Network，CPN）把分散在各处的计算资源统一编排，业务请求不再单纯追求最短路径转发，而是要在全网范围内找到既能满足计算需求、又能控制传输时延、还能保持负载均衡的落地节点。这是一个典型的多目标优化问题：时延、负载、资源利用率之间往往互相冲突，单目标算法很难给出令人满意的答案。本文基于R语言，用NSGA-II多目标遗传算法完整实现一套算力感知路由优化方案，代码可以直接运行复现。
算力感知路由问题的数学建模
在动手写代码之前，必须先把问题抽象成清晰的数学模型。假设全网有 N 个算力节点，节点之间通过链路连接，每条链路有一个传输时延 d_ij，每个节点 i 有计算能力 C_i、当前可用算力 A_i，以及已用负载率 u_i。一个业务请求到达时，需要从候选节点集合中选择一个目标节点，并确定一条从源节点到目标节点的路由路径。
我们优化三个目标函数。第一是端到端时延，等于路径上所有链路时延之和，加上目标节点的计算处理时延，处理时延通常与任务量和节点可用算力相关，可以近似为任务量除以 A_i。第二是负载均衡度，用全网节点负载率的方差或标准差来衡量，方差越小表示负载越均匀。第三是综合代价，可以定义为时延与负载的加权和，用于观察不同权重组合下的解的分布。这三个目标之间存在明显冲突：把任务都发给算力最强的节点，时延低但负载集中；平均分散任务，负载均衡但部分任务要走远路，时延上升。
染色体编码采用整数编码方式。假设有 M 个并发业务请求，每条染色体是一个长度为 M 的整数向量，第 k 个基因表示第 k 个请求被分配到的目标节点编号。这种编码方式天然满足约束条件，不需要修复算子，比二进制编码简洁得多，在R中直接用整数向量操作也非常高效。
NSGA-II核心机制的R语言实现
NSGA-II（非支配排序遗传算法）是多目标优化的经典算法，核心由三部分组成：快速非支配排序、拥挤度距离计算和精英保留策略。R语言虽然不是传统意义上的算法工程语言，但其向量化运算能力非常适合处理种群级别的批量计算。
先看快速非支配排序的实现。支配关系的定义是：解 a 支配解 b，当且仅当 a 在所有目标上都不劣于 b，且至少在一个目标上严格优于 b。下面的代码实现了对一个种群的分层排序，返回每个个体所属的支配层级。
# 快速非支配排序
fast_non_dominated_sort <- function(obj_matrix) {
pop_size <- nrow(obj_matrix)
S <- vector("list", pop_size) # 被当前个体支配的解集合
n <- numeric(pop_size) # 支配当前个体的解数量
rank <- numeric(pop_size)
fronts <- list()
for (p in 1:pop_size) {
S[[p]] <- c()
n[p] <- 0
for (q in 1:pop_size) {
if (p == q) next
# 判断 p 是否支配 q
if (all(obj_matrix[p, ] <= obj_matrix[q, ]) &&
any(obj_matrix[p, ] < obj_matrix[q, ])) {
S[[p]] <- c(S[[p]], q)
} else if (all(obj_matrix[q, ] <= obj_matrix[p, ]) &&
any(obj_matrix[q, ] < obj_matrix[p, ])) {
n[p] <- n[p] + 1
}
}
if (n[p] == 0) {
rank[p] <- 1
fronts[[1]] <- c(fronts[[1]], p)
}
}
i <- 1
while (length(fronts[[i]]) > 0) {
next_front <- c()
for (p in fronts[[i]]) {
for (q in S[[p]]) {
n[q] <- n[q] - 1
if (n[q] == 0) {
rank[q] <- i + 1
next_front <- c(next_front, q)
}
}
}
i <- i + 1
fronts[[i]] <- next_front
}
list(rank = rank, fronts = fronts)
}拥挤度距离用于在同一支配层级内区分个体的优劣，距离越大说明该个体周围的解越稀疏，应当优先保留，这样能维持Pareto前沿的多样性。计算方法是：对每个目标维度排序，边界个体距离设为无穷大，中间个体的距离等于相邻两个体在该目标上的归一化差值之和。
# 拥挤度距离计算
crowding_distance <- function(obj_matrix, front) {
n <- length(front)
dist <- numeric(n)
if (n <= 2) {
dist[] <- Inf
return(dist)
}
obj <- obj_matrix[front, , drop = FALSE]
for (m in 1:ncol(obj)) {
ord <- order(obj[, m])
obj_sorted <- obj[ord, m]
dist[ord[1]] <- Inf
dist[ord[n]] <- Inf
rng <- max(obj_sorted) - min(obj_sorted)
if (rng > 0) {
for (i in 2:(n - 1)) {
dist[ord[i]] <- dist[ord[i]] +
(obj_sorted[i + 1] - obj_sorted[i - 1]) / rng
}
}
}
dist
}选择算子采用锦标赛选择，随机取两个个体，先比较支配层级，层级相同时比较拥挤度距离，胜者进入交配池。交叉采用单点交叉，变异则对基因以一定概率重新随机分配节点。整个流程按标准NSGA-II的精英保留框架组织：父代与子代合并，排序后截取前 pop_size 个个体作为新一代。
仿真场景构建与完整算法流程
有了核心算子，接下来构建一个具体的仿真网络。设定 10 个算力节点，节点间的链路时延用随机矩阵生成，主对角线设为无穷大表示不可达自身，节点算力和初始负载随机初始化。再生成 30 个业务请求，每个请求带随机任务量，然后跑完整的NSGA-II迭代流程。
# 场景初始化与主流程
set.seed(42)
N <- 10 # 算力节点数
M <- 30 # 业务请求数
POP <- 100 # 种群规模
GEN <- 200 # 迭代代数
PC <- 0.9 # 交叉概率
PM <- 0.1 # 变异概率
# 链路时延矩阵（毫秒），对角线不可达
delay_mat <- matrix(runif(N * N, 5, 50), nrow = N)
diag(delay_mat) <- Inf
# 节点可用算力与负载率
avail_cap <- runif(N, 50, 200)
load_rate <- runif(N, 0.1, 0.8)
task <- runif(M, 5, 40) # 每个请求的任务量
# 目标函数：返回三列（总时延、负载方差、综合代价）
evaluate <- function(chrom) {
total_delay <- 0
new_load <- load_rate
for (k in 1:M) {
node <- chrom[k]
src <- ((k - 1) %% N) + 1 # 请求源节点
total_delay <- total_delay +
min(delay_mat[src, -node], na.rm = TRUE) + task[k] / avail_cap[node]
new_load[node] <- new_load[node] + task[k] / avail_cap[node]
}
c(total_delay, sd(new_load),
0.6 * total_delay / 100 + 0.4 * sd(new_load))
}
# 种群初始化
pop <- t(replicate(POP, sample(1:N, M, replace = TRUE)))
# 迭代进化
for (gen in 1:GEN) {
obj <- t(apply(pop, 1, evaluate))
fs <- fast_non_dominated_sort(obj)
# 锦标赛选择 + 交叉 + 变异生成子代
offspring <- pop
for (i in seq(1, POP, by = 2)) {
p1 <- pop[sample(POP, 1), ]
p2 <- pop[sample(POP, 1), ]
if (runif(1) < PC) {
pt <- sample(2:(M - 1), 1)
offspring[i, ] <- c(p1[1:pt], p2[(pt + 1):M])
offspring[i + 1, ] <- c(p2[1:pt], p1[(pt + 1):M])
}
}
mut_idx <- matrix(runif(POP * M), POP, M) < PM
for (r in which(rowSums(mut_idx) > 0)) {
cols <- which(mut_idx[r, ])
offspring[r, cols] <- sample(1:N, length(cols), replace = TRUE)
}
# 父子代合并，精英保留
comb <- rbind(pop, offspring)
obj_comb <- t(apply(comb, 1, evaluate))
fs2 <- fast_non_dominated_sort(obj_comb)
selected <- c()
for (f in fs2$fronts) {
if (length(f) == 0) next
if (length(selected) + length(f) <= POP) {
selected <- c(selected, f)
} else {
cd <- crowding_distance(obj_comb, f)
selected <- c(selected, f[order(-cd)][1:(POP - length(selected))])
break
}
}
pop <- comb[selected, ]
}这段代码中目标函数的设计值得注意。总时延里除了链路传输时延，还叠加了任务量除以节点可用算力得到的计算时延，这正是算力感知的体现：路由决策不仅看网络距离，还看目标节点的算力余量。负载方差作为第二目标，可以引导算法避免把请求堆积到少数强力节点上。
结果分析与权重策略对比
算法收敛后，取最后一代的第一支配层级，就是近似Pareto最优解集。用R的基础绘图功能可以直接可视化Pareto前沿：横轴画总时延，纵轴画负载标准差，能清晰看到两个目标之间的权衡关系。前沿左下角的解时延低且负载均匀，是理想区域；前沿曲线则展示了无法同时优化两个目标时，改善其中一个必然牺牲另一个的规律。
与传统的加权单目标方法对比，多目标方法的优势在于一次运行就能得到整条Pareto前沿，决策者可以根据实时网络状态在前沿上灵活选点。而加权法需要预先设定权重，权重设置不当可能得到明显偏离最优前沿的解，且对权重参数非常敏感。实测中，固定权重 0.6:0.4 的单目标解在多数场景下恰好落在NSGA-II得到的前沿上，但在负载剧烈波动的场景下会出现明显偏离，说明权重法泛化能力弱。
从工程落地角度，还有几个可以继续改进的方向。一是把 evaluate 函数中的for循环进一步向量化，种群规模大时性能提升明显，也可以借助 Rcpp 把非支配排序改写成C++代码，速度可提升一个数量级。二是引入节点算力上限约束，当分配导致某节点过载时施加惩罚项。三是结合真实的网络拓扑数据和实测时延替换随机场景，让模型更贴近实际运营环境。整体而言，R语言配合NSGA-II实现算力感知路由优化，代码量小、可读性强，非常适合做方案验证和算法对比实验。