Matlab实战：基于自适应遗传算法的分布式系统优化

背景与问题引入
遗传算法与自适应改进原理
分布式系统任务调度优化模型
自适应遗传算法（AGA）的设计
MATLAB 环境配置与工具准备
自适应遗传算法 MATLAB 实现详解
实验案例一：小规模系统调度优化
实验案例二：大规模分布式调度优化
结果可视化与收敛性分析
性能对比与扩展研究

1. 背景与问题引入

随着云计算与分布式计算的发展，任务调度成为核心问题：

数据中心由成百上千个服务器节点组成
任务数量庞大，且任务执行时间在不同节点上可能不同
目标：减少整体任务完成时间（Makespan）、提高资源利用率

挑战：

任务调度是 NP难问题，无法用穷举法求解
系统异构性与动态性导致传统算法容易陷入局部最优
需要全局搜索与动态适应能力强的优化算法

解决方案：采用 自适应遗传算法（AGA），在进化过程中动态调整交叉率和变异率，实现全局搜索与局部开发的平衡。

2. 遗传算法与自适应改进原理

2.1 遗传算法（GA）基本流程

遗传算法模拟自然选择与基因进化过程，核心步骤：

flowchart LR
    A[初始化种群] --> B[适应度评估]
    B --> C[选择算子]
    C --> D[交叉算子]
    D --> E[变异算子]
    E --> F[更新种群]
    F --> G{终止条件?}
    G -- 否 --> B
    G -- 是 --> H[输出最优解]

2.2 自适应遗传算法（AGA）改进点

问题：固定交叉率 $P_c$ 和变异率 $P_m$ 导致算法早熟或收敛慢
改进：根据当前代种群适应度动态调整

公式如下：

$$ P_c = \begin{cases} k_1 \frac{f_\text{max}-f'}{f_\text{max}-\bar{f}}, & f' > \bar{f}\\ k_2, & f' \le \bar{f} \end{cases} \quad P_m = \begin{cases} k_3 \frac{f_\text{max}-f_i}{f_\text{max}-\bar{f}}, & f_i > \bar{f}\\ k_4, & f_i \le \bar{f} \end{cases} $$

$f_\text{max}$：当前最大适应度
$\bar{f}$：当前平均适应度
$f'$：参与交叉的父代个体适应度
$f_i$：参与变异的个体适应度
$k_1..k_4$：控制系数（经验取值）

3. 分布式系统任务调度优化模型

3.1 问题建模

假设系统有 $M$ 个计算节点
有 $N$ 个任务，每个任务在不同节点上执行时间不同，用矩阵 $T \in \mathbb{R}^{M\times N}$ 表示

目标函数（最小化最大完成时间）：

$$ \min \; F(X) = \max_{1 \le i \le M} \sum_{j=1}^N t_{ij} x_{ij} $$

$$ \text{s.t. } \sum_{i=1}^{M} x_{ij} = 1,\; x_{ij} \in \{0,1\} $$

$x_{ij} = 1$ 表示任务 $j$ 分配给节点 $i$

3.2 染色体编码

每个染色体长度为 $N$
第 $j$ 个基因值 $c_j \in [1,M]$ 表示任务 $j$ 的分配节点

例如，[2 1 3 3 2] 表示：

任务1分配给节点2
任务2分配给节点1
…

4. 自适应遗传算法设计

核心步骤：

初始化种群：随机分配任务
适应度函数：计算每条染色体的最大节点负载
自适应调整算子概率
选择-交叉-变异
迭代至收敛或达到代数限制

5. MATLAB 环境配置与工具准备

安装 MATLAB R2020b 以上版本
推荐开启并行计算加速评估：

parpool('local'); % 打开默认并行池

若使用 GA 工具箱，可对比验证自写 AGA 的效果

6. 自适应遗传算法 MATLAB 实现详解

以下是完整实现示例：

6.1 初始化种群

function pop = initPopulation(popSize, M, N)
    pop = randi(M, popSize, N); % 每个基因为1~M
end

6.2 适应度函数

function fitness = evaluate(pop, t, M, N)
    popSize = size(pop,1);
    fitness = zeros(popSize,1);
    for i = 1:popSize
        load = zeros(1,M);
        for j = 1:N
            load(pop(i,j)) = load(pop(i,j)) + t(pop(i,j), j);
        end
        fitness(i) = max(load); % Makespan
    end
end

6.3 自适应概率

function [pc, pm] = adaptRates(fitness, params, i)
    fmax = max(fitness); favg = mean(fitness);
    fi = fitness(i);
    if fi > favg
        pc = params.k1*(fmax-fi)/(fmax-favg);
        pm = params.k3*(fmax-fi)/(fmax-favg);
    else
        pc = params.k2; pm = params.k4;
    end
    pc = max(min(pc,1),0);
    pm = max(min(pm,1),0);
end

6.4 主函数

function [bestSol,bestFitness] = AGA_DistributedScheduling(t, M, N, params)
    pop = initPopulation(params.popSize, M, N);
    fitness = evaluate(pop, t, M, N);
    bestFitness = zeros(params.maxGen,1);

    for gen = 1:params.maxGen
        newPop = pop;
        for i=1:params.popSize
            [pc, pm] = adaptRates(fitness, params, i);
            % 选择
            parentIdx = randi(params.popSize,1,2);
            parent = pop(parentIdx,:);
            % 交叉
            if rand < pc
                pt = randi(N-1);
                child = [parent(1,1:pt), parent(2,pt+1:end)];
            else
                child = parent(1,:);
            end
            % 变异
            for j=1:N
                if rand < pm
                    child(j) = randi(M);
                end
            end
            newPop(i,:) = child;
        end
        pop = newPop;
        fitness = evaluate(pop, t, M, N);
        [bestFitness(gen), idx] = min(fitness);
        bestSol = pop(idx,:);
    end
end

7. 实验案例一：小规模系统优化

M = 3; N = 6;
t = [8 6 10 4 9 7;
     7 8 6  5 10 8;
     9 7 8  6  7 6]; % 节点x任务矩阵

params = struct('popSize',50,'maxGen',100,'k1',0.9,'k2',0.6,'k3',0.1,'k4',0.01);
[bestSol,bestFitness] = AGA_DistributedScheduling(t,M,N,params);

disp('最优分配方案:'), disp(bestSol)
plot(bestFitness), title('AGA 收敛曲线'), xlabel('代数'), ylabel('最优Makespan')

8. 实验案例二：大规模分布式调度

模拟 10 节点、50 任务系统：

M = 10; N = 50;
t = randi([5,30], M, N);
params.maxGen = 200; params.popSize = 100;

[bestSol,bestFitness] = AGA_DistributedScheduling(t,M,N,params);

结果表明，自适应遗传算法可以有效收敛至较优解，并显著提升分布式系统任务调度效率。

9. 结果可视化与收敛性分析

plot(bestFitness,'-o','LineWidth',1.5)
xlabel('Generation'); ylabel('Best Fitness');
title('自适应遗传算法收敛曲线');
grid on;

前期快速下降，后期平稳收敛
可进一步使用热力图展示节点负载分布

10. 性能对比与扩展研究

对比固定参数 GA 与 AGA：AGA 收敛更快，最终解更优
扩展研究方向：
- 多目标优化（结合能耗）
- 并行 AGA（利用 MATLAB 并行计算工具箱）
- 混合算法（AGA + 局部搜索）