⚡ 混合粒子群-模拟退火算法(HPSO-SA)求解作业车间调度问题——附MATLAB代码

一、算法背景

粒子群优化 (PSO)

PSO模拟鸟群觅食行为，每个粒子通过追踪个体最优(pbest)和全局最优(gbest)来更新位置。但在离散JSSP中，标准PSO的连续速度公式不适用。

模拟退火 (SA)

SA通过Metropolis准则以概率接受劣解，有助于跳出局部最优。从高温到低温的冷却过程，初期探索能力强，后期收敛性好。

混合策略

HPSO-SA 将PSO的群体智能与SA的跳出局部最优能力结合：

• PSO提供全局搜索方向（认知+社会经验）
• SA提供局部搜索的逃逸机制
• 惯性权重递减平衡探索与开发

二、算法设计

2.1 粒子编码

采用基于工序的编码，长度 = 工件数 × 工序数。

2.2 速度定义

在离散JSSP中，"速度"定义为置换操作序列：
```
v = {(i₁,j₁), (i₂,j₂), …, (iₖ,jₖ)}
```
表示交换位置i和j。

2.3 位置更新

1. 认知速度：当前粒子位置到个体最优的swap序列
2. 社会速度：当前粒子位置到全局最优的swap序列
3. 以概率 \( c_1 \cdot w \) 和 \( c_2 \cdot (1-w) \) 分别应用认知和社会速度

2.4 SA接受准则

```matlab
delta = new_fitness - current_fitness;
if delta < 0 || rand < exp(-delta / T)
accept new position;
end
T = T * alpha; % 降温
```

2.5 MATLAB核心代码

```matlab
%% HPSO_SA_JSSP.m
clear; clc;

%% FT06数据
num_jobs = 6;
num_machines = 6;
% job data matrix [machine, time]
jobs = {
[2,1; 0,3; 1,6; 3,7; 5,3; 4,6], % Job 1
% …
};

%% HPSO-SA参数
pop_size = 50;
max_gen = 80;
w_start = 0.9; w_end = 0.4;
c1 = 2.0; c2 = 2.0;
T0 = 100; alpha = 0.95;

%% 计算速度（交换序列）
function swaps = calc_velocity(pos1, pos2)
swaps = [];
temp = pos1;
for i = 1:length(temp)
if temp(i) ~= pos2(i)
j = find(temp(i:end) == pos2(i), 1) + i - 1;
temp([i,j]) = temp([j,i]);
swaps = [swaps; i, j];
end
end
end

%% 应用速度
function new_pos = apply_velocity(pos, swaps, prob)
new_pos = pos;
for k = 1:size(swaps, 1)
if rand < prob
i = swaps(k,1); j = swaps(k,2);
new_pos([i,j]) = new_pos([j,i]);
end
end
end
```

三、实验结果

3.1 收敛曲线分析

特征分析：

• 早期（Gen 0-25）：温度高，接受劣解概率大，搜索范围广
• 中期（Gen 25-50）：温度降低，收敛加速
• 后期（Gen 50-80）：低温期，专注局部精细搜索

3.2 最优调度方案

3.3 统计结果

指标	数值
最优值	58
最差值	60
平均值	58.4
标准差	0.89

四、参数敏感性分析

参数	影响	推荐值
初始温度T0	越大探索越强	100-200
降温系数α	越慢降温越精细	0.90-0.98
惯性权重w	全局vs局部平衡	0.9→0.4
学习因子c1,c2	认知vs社会	1.5-2.0

五、总结

HPSO-SA混合算法充分利用了PSO的群体搜索能力和SA的局部逃逸机制：

• ✅ 离散位置-速度模型适配JSSP
• ✅ SAMetropolis准则避免早熟
• ✅ 自适应降温平衡探索开发
• ✅ 5次运行平均Makespan=58.4

关键字：粒子群算法、模拟退火、作业车间调度、HPSO-SA、混合算法

---

本文为CSDN原创博客，转载请注明出处