-
MOGA
x
i
是第
t
代种群中个体，其
rank
值定义为：
rank
(
x
i
,
t
)<
/p>
?
1
?
p
i
(
t
)
p
i
(
t
)
为第
t
< br>代种群中所有支配
x
i
的个体数
目
适应值（
fitness
value
）分配算法：
1
、
将所有
个体依照
rank
值大小排序分类；
2
、
利用插
值函数给所有个体分配适应值（从
rank1
到
*
rank
n
?
N
）
，一般采用线性函
数
3
、
<
/p>
适应值共享：
rank
值相同的个体拥有
相同的适应值，
保证后期选择时同一
rank
值的个体概率相同
最后采用共享适应值随机选取的方法选择个体进入下一代
一种改进的排序机制（
ranking
scheme
）
：
< br>向量
y
a
?
(
y
a
,1
,
???
,
y
a
,
q
)
和
y
b
?
(
y
b
,1
,
???
,
y
b
,
q
)
比较
goal vector
：
< br>g
?
g
1
,
???
,
g
q
分为以下三种情况：
?
?
1
、
?
k
?
1,
???<
/p>
,
q
?
1
;
?
i
?
1,
???
,
k
;
?
j
?
k
?
1,
???
,
q
;
?
y
a
,
i
?
g
i
?
?
?
y
a
,
j
?
g
j<
/p>
?
2
、
?
i
?
1,
???
,
q
;
y
a
,
i
?
g
i
当
y
a
支配
< br>y
b
时，选择
y
a
3
、
?
j
?
1,
???
,
q
;
y
a
,
j
?
g
j
当<
/p>
y
b
支配
y
a
时，选择
y
b<
/p>
优点：算法思想容易，效率优良
缺点：算法容易受到小生境的大小影响
理论上给出了参数
?
share
的计
算方法
?
?
?
?
NPGA
基本思想：
1
、初始化种群
Pop
2
、锦标赛选择机制：随机选取两个个体
x
1
和
x
2
和一个
Pop
的
子集
CS(Comparison Set)
< br>做参照系。若
x
1
被
CS
中不少于一
个个体支配，而
< br>x
2
没有被
CS
中任一个体支配，则选择
x
2
。
3
、其他情况一律称为死结（
Tie
）
，采用适应度共享机制选择。
个体适应度
：
f
i
小生境计数（
Niche Count
）
：
m
i
?<
/p>
?
j
?
Pop<
/p>
Sh
?
?
d
?
i
,
j
?
?
?
d
?
,
?
< br>1-
共享函数：
Sh
(
d
)
?
?
?
share
?
0,
?
d
?
?
share
d
?
?
share
f
i
共享适应度（
the shared
fitness
）
：
m
i
选择共享适应度较大的个体进入下一代
优点：能够快速找到一些好的非支配最优解域
能够维持一个较长的种群更新期
缺点：需要设置共享参数
需要选择一个适当的锦标赛机制
限制了该算法的实际应用效果
NPGA II
基本思想：
1
、初始化种群
Pop
2
、
Pareto
排序：非支配个体
rank=0
；其余个体
rank=
支配该个体的个体数目
<
/p>
3
、锦标赛选择机制：种群中任选两个个体
x
1
和
x
2
，
若
rank
?
x
1
?
?<
/p>
rank
?
x
2
?
，则选择
x
1
；
若是
rank
?
x
1
?
?
rank
?
x
2
?
，称为死结（
Tie
）
，
采用适应度共享机制选择。
小生境计数（
Niche
Count
）
：
?
d
ij
?
?
?
?
?
1
?
?
if
d
i
j
?
?
share
m
i
?
?
j
?
Pop
?
?
share
?
?
0
if
d
?
?
ij
share
?
这里的
Pop
只包含当前一代里
的个体，在
NPGA
中，
计算
m
i
公式中的
Pop
包含当前一代以及已经产生的
属于下一代的所有个体
最后，选择计数较小的个体进入下一代
在计算
Niched
Count
之前还要对函数值进行标准化：
< br>O
i
?
O
i
,min
O
?
O
i
,max
< br>?
O
i
,min
'
i
NSGA
和简单的遗传算法的不同点在于
selection
operator
works
，
crossover
and
mutation
operator
是一样的
不一样的共享函数：
?
?
d
i
< br>,
j
?
2
?
1-
?
,
if
d
i
,
j
?
?
share
Sh
?
d
i
,
j<
/p>
?
?
?
?
?
?
share
?<
/p>
?
?
0,
otherwise
d
i
,
j
表示个体
i
和
j
之间的距离
?
share
是共享参数，表示小生境的半径
小生境计数（
Niche Count
）
：
m
i
?<
/p>
共享适应值：
df
?
j
?
currentfront
S
h
?
?
d
?<
/p>
i
,
j
?
?
?
m
i
最后采用随机余数比例算法选择个体进行重新构造种群的基础
优点：优化目标个数任选
非支配最优解分布均匀
允许存在多个不同的等效解
缺点：计
算复杂度过高（
O
?
MN
3
?
）
不具有精英保留机制
需要预设共享参数
?
share
NSGA II
加入精英保留机制
快速非支配排序方法（
Fast Nondominated
Sorting
Approach
）
：
支配计数
n
p
：支配解
p
的解数量
支配解集
S
p
：解
p
支配的解集合
1
、
计算出每一个解的
n
p
和
S
p
，第一级非支配解
n
p
?
0
< br>，单独放入一个
集合；
2
、
遍历成
员
q
和
S
q<
/p>
，逐步递减
n
q
，如果可以减少为
0
，将
p
放入单独
的集合
Q
，构成
第二级非支配解；
3
、
重复步
骤
2
，直到所有成员全部分类完成。
Crowded-
comparison Approach
1
、
计算集
合
I
的长度，初始化；
2
、
对每一个目标，利用目标值进行排序；
3
、
赋予边
界点（第一个和最后一个）最大值，确保它们不会被剔除；
4
、
循环计算其他点的
crowded
distance.
I
?
i
?
dis
tan
ce
?
I
?
i
?
dis
tan
ce
?
?
I
?
i
?
1
?
.
m
?
I
?
i
?
1
?
.
m
?
max
min
f
m
?
f
m
其中，
I
为非支配集合，
I
?
i
?
< br>.
m
表示第
m
< br>个目标在第
i
个个体处的目标值，
max
min
f
< br>m
/
f
m
分别表示第
m
个目标的最大最小函数值
值越小，越拥挤
Crowded-Comparison Operator
：
i
j
if
?
i
rank
?
j
rank
?
or
n
n
?
?
i
rank
?<
/p>
j
rank
?
and
?
i
dis
tan
ce
?
j
dis
tan
ce
?
?
Replace the sharing
function approach in NSGA
可以一定程度上消除一下两点：
（
1
）
the
sharing function
太过于依赖共享参数，不容易设定
（
2
）
the
sharing function
时间复杂度达到
O
N
?
?
2
算法主循环：
1
、
初始<
/p>
种群
P
0
（
size
?
N
）<
/p>
，并利用
binary
tournament
selection,
recombination and mutation operators
构建一个子代种群
Q
0
（
size
?
N
）
;
2
、
合并<
/p>
P
0
和
Q
0
，记
R
0
?
P
0
?
Q
0
第
t
代：
合并
P
t<
/p>
和
Q
t
，记
R
t
?
P
t
?
Q
t
对
R
t
< br>进行非支配分类，结果记作
F
?
?
F
1
,
F<
/p>
2
,
???
?<
/p>
循环计算
crowded
distance of
F
i
，并入
P
t
?
1