MOEA-D（基于分解的多目标进化算法）
MOEA-D（基于分解的多目标进化算法）是一种用于多目标优化的进化算法，其核心思想是将多目标优化问题分解为多个单目标优化问题。下面是MOEA-D算法的几个主要特点和步骤：
主要特点
分解策略：
- 将多目标优化问题通过权重向量（lambda）划分为多个子问题。每个子问题对应一个权重向量，代表目标空间中的一个方向。
邻域交互：
- 每个子问题与其邻域内的其他子问题相互影响，这有助于保持种群的多样性并促进优良解的传播。
适应度评估：
- 通过计算每个个体与理想点的距离，评估其适应度。采用加权绝对差的最大值作为个体的代价。
多样性维护：
- 通过选择、交叉和变异等操作，保持种群的多样性，避免早熟收敛。
算法步骤
初始化：
循环迭代：
- 在每次迭代中，通过交叉和变异等操作生成新个体。
- 更新每个个体的代价，使用分解代价函数评估解的质量。
- 通过支配关系确定哪些个体被优先保留。
更新Pareto前沿：
- 在每次迭代后，更新估计的Pareto前沿，并在必要时进行个体的选择和替换。
终止条件：
- 当达到预设的最大迭代次数或满足其他停止条件时，算法结束，返回Pareto前沿的解集。
应用场景
MOEA-D算法广泛应用于工程优化、资源分配、路径规划等领域，尤其是在多个相互冲突的目标之间寻求平衡时表现出色。
CreateSubProblems.m 文件代码：
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
|
function sp = CreateSubProblems(nObj, nPop, T)
empty_sp.lambda = [];
empty_sp.Neighbors = [];
sp = repmat(empty_sp, nPop, 1);
for i = 1:nPop
lambda = rand(nObj, 1);
lambda = lambda / norm(lambda);
sp(i).lambda = lambda;
end
LAMBDA = [sp.lambda]';
D = pdist2(LAMBDA, LAMBDA);
for i = 1:nPop
[~, SO] = sort(D(i, :));
sp(i).Neighbors = SO(1:T);
end
end
|
Crossover.m 文件代码：
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
|
function y = Crossover(x1, x2, params)
gamma = params.gamma;
VarMin = params.VarMin;
VarMax = params.VarMax;
alpha = unifrnd(-gamma, 1 + gamma, size(x1));
y = alpha .* x1 + (1 - alpha) .* x2;
y = min(max(y, VarMin), VarMax);
end
|
DecomposedCost.m 文件代码：
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
|
function g = DecomposedCost(individual, z, lambda)
if isfield(individual, 'Cost')
fx = individual.Cost;
else
fx = individual;
end
g = max(lambda .* abs(fx - z));
end
|
DetermineDomination.m 文件代码：
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
|
function pop = DetermineDomination(pop)
nPop = numel(pop);
for i = 1:nPop
pop(i).IsDominated = false;
end
for i = 1:nPop
for j = i + 1:nPop
if Dominates(pop(i), pop(j))
pop(j).IsDominated = true;
elseif Dominates(pop(j), pop(i))
pop(i).IsDominated = true;
end
end
end
end
|
Dominates.m 文件代码：
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
|
function b = Dominates(x, y)
if isfield(x, 'Cost')
x = x.Cost;
end
if isfield(y, 'Cost')
y = y.Cost;
end
b = all(x <= y) && any(x < y);
end
|
main.m 文件代码：
moead.m 文件代码：
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
|
clc;
clear;
close all;
CostFunction = @(x) MOP2(x);
nVar = 3;
VarSize = [nVar 1];
VarMin = 0;
VarMax = 1;
nObj = numel(CostFunction(unifrnd(VarMin, VarMax, VarSize)));
MaxIt = 100;
nPop = 50;
nArchive = 50;
T = max(ceil(0.15 * nPop), 2);
T = min(max(T, 2), 15);
crossover_params.gamma = 0.5;
crossover_params.VarMin = VarMin;
crossover_params.VarMax = VarMax;
sp = CreateSubProblems(nObj, nPop, T);
empty_individual.Position = [];
empty_individual.Cost = [];
empty_individual.g = [];
empty_individual.IsDominated = [];
z = zeros(nObj, 1);
pop = repmat(empty_individual, nPop, 1);
for i = 1:nPop
pop(i).Position = unifrnd(VarMin, VarMax, VarSize);
pop(i).Cost = CostFunction(pop(i).Position);
z = min(z, pop(i).Cost);
end
for i = 1:nPop
pop(i).g = DecomposedCost(pop(i), z, sp(i).lambda);
end
pop = DetermineDomination(pop);
EP = pop(~[pop.IsDominated]);
for it = 1:MaxIt
for i = 1:nPop
K = randsample(T, 2);
j1 = sp(i).Neighbors(K(1));
p1 = pop(j1);
j2 = sp(i).Neighbors(K(2));
p2 = pop(j2);
y = empty_individual;
y.Position = Crossover(p1.Position, p2.Position, crossover_params);
y.Cost = CostFunction(y.Position);
z = min(z, y.Cost);
for j = sp(i).Neighbors
y.g = DecomposedCost(y, z, sp(j).lambda);
if y.g <= pop(j).g
pop(j) = y;
end
end
end
pop = DetermineDomination(pop);
ndpop = pop(~[pop.IsDominated]);
EP = [EP; ndpop];
EP = DetermineDomination(EP);
EP = EP(~[EP.IsDominated]);
if numel(EP) > nArchive
Extra = numel(EP) - nArchive;
ToBeDeleted = randsample(numel(EP), Extra);
EP(ToBeDeleted) = [];
end
figure(1);
PlotCosts(EP);
pause(0.01);
disp(['Iteration ' num2str(it) ': Number of Pareto Solutions = ' num2str(numel(EP))]);
end
disp(' ');
EPC = [EP.Cost];
for j = 1:nObj
disp(['Objective #' num2str(j) ':']);
disp([' Min = ' num2str(min(EPC(j, :)))]);
disp([' Max = ' num2str(max(EPC(j, :)))]);
disp([' Range = ' num2str(max(EPC(j, :)) - min(EPC(j, :)))]);
disp([' St.D. = ' num2str(std(EPC(j, :)))]);
disp([' Mean = ' num2str(mean(EPC(j, :)))]);
disp(' ');
end
|
MOP2.m 文件代码：
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
|
function z = MOP2(x)
n = numel(x);
z = [
1 - exp(-sum((x - 1/sqrt(n)).^2));
1 - exp(-sum((x + 1/sqrt(n)).^2))
];
end
|
PlotCosts.m 文件代码：
1
2
3
4
5
6
7
8
9
10
11
12
13
|
function PlotCosts(EP)
EPC = [EP.Cost];
plot(EPC(1, :), EPC(2, :), 'x');
xlabel('1^{st} Objective');
ylabel('2^{nd} Objective');
grid on;
end
|
ZDT.m 文件代码：
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
|
function z = ZDT(x)
n = numel(x);
f1 = x(1);
g = 1 + 9 / (n - 1) * sum(x(2:end));
h = 1 - sqrt(f1 / g);
f2 = g * h;
z = [f1;
f2];
end
|
