推荐星级:
- 1
- 2
- 3
- 4
- 5
基于模糊C均值聚类的锦标赛选择机制与多目标优化研究
资料介绍
本文提出了一种用于多目标优化的进化算法——基于模糊C均值聚类的进化算法(A Fuzzy C-Means Clustering Based Evolutionary Algorithm,FCEA).在算法的迭代过程中,先利用模糊C均值聚类算法寻找种群的分布结构,通过对每一代种群进行模糊划分,获得每个个体隶属于每一类的隶属度,然后本文设计了一种基于隶属度的锦标赛选择算子,用于从整个种群中选择相似个体进行重组,引导算法进行搜索.实验结果表明,基于隶属度的锦标赛选择算子的应用能够提升算法的性能,与MOEA/D-DE、NSGAII、SPEA2、SMS-EMOA等先进的优化算法进行比较的结果表明,FCEA在求解具有复杂Pareto前沿的多目标优化问题(GLT系列)时具有一定的竞争力.
部分文件列表
文件名 | 大小 |
基于模糊C均值聚类的锦标赛选择机制与多目标优化研究.pdf | 2M |
部分页面预览
(完整内容请下载后查看)第 11 期
电ꢀ
ꢀ
子ꢀ
ꢀ
学ꢀ
ꢀ
报
Vol.45ꢀ No.11
Nov.ꢀ 2017
2017 年 11 月
ACTA ELECTRONICA SINICA
基于模糊 C 均值聚类的锦标赛选择机制
与多目标优化研究
张ꢀ 屹1,余ꢀ 振1,李子木1,陆瞳瞳2
(1.三峡大学机械与动力学院,湖北宜昌 443002;2.常州大学商学院,江苏常州 213164)
ꢀ ꢀ 摘ꢀ 要:ꢀ 本文提出了一种用于多目标优化的进化算法———基于模糊 C 均值聚类的进化算法(A Fuzzy C⁃Means
Clustering Based Evolutionary Algorithm,FCEA).在算法的迭代过程中,先利用模糊 C 均值聚类算法寻找种群的分布结
构,通过对每一代种群进行模糊划分,获得每个个体隶属于每一类的隶属度,然后本文设计了一种基于隶属度的锦标
赛选择算子,用于从整个种群中选择相似个体进行重组,引导算法进行搜索.实验结果表明,基于隶属度的锦标赛选择
算子的应用能够提升算法的性能,与 MOEA/ D⁃DE、NSGAII、SPEA2、SMS⁃EMOA 等先进的优化算法进行比较的结果表
明,FCEA 在求解具有复杂 Pareto 前沿的多目标优化问题(GLT 系列)时具有一定的竞争力.
关键词: ꢀ 进化算法; 多目标优化; 模糊 C 均值聚类; 隶属度选择
中图分类号: ꢀ TP18ꢀ ꢀ ꢀ 文献标识码: ꢀ Aꢀ ꢀ ꢀ 文章编号: ꢀ 0372⁃2112 (2017)11⁃2677⁃08
电子学报 URL: http:/ / www.ejournal.org.cnꢀ
DOI: 10.3969/ j.issn.0372⁃2112.2017.11.015
Tournament Selection for Multiobjective Optimization
Based on Fuzzy C⁃Means Clustering Method
ZHANG Yi1 ,YU Zhen1 ,LI Zi⁃mu1 ,LU Tong⁃tong2
(1.College of Mechanical and Power Engineering,China Three Gorges University,Yichang,Hubei 443002,China;
2.School of Business,Changzhou University,Changzhou,Jiangsu 213164,China)
Abstract:ꢀ A fuzzy C⁃means clustering based evolutionary algorithm called FCEA was proposed to optimize multiob⁃
jective optimization problems.In the process of iteration of this algorithm,a fuzzy C⁃means clustering method is firstly em⁃
ployed to implement a fuzzy partition of the population so as to discover the population distribution structure and to obtain a
membership matrix of the population at each generation.According to the distribution structure,a membership based tourna⁃
ment selection strategy (MBTS) is designed to select neighboring solutions from the population for recombination and to
guide search.The experiments present that MBTS significantly contributes to the performance of FCEA.Comparison experi⁃
ments show that the proposed FCEA outperforms MOEA/ D⁃DE,NSGAII,SPEA2 and SMS⁃EMOA on solving GLT test
suite with complicated Pareto Front (PF) shapes.
Key words:ꢀ evolutionary algorithm;multiobjective optimization;fuzzy C⁃means cluster;membership selection
算法和基于分解的多目标进化算法.基于支配的多目标
进化算法包括 NSGAII[1] 、SPEA 及改进后的 SPEA2[2]
1ꢀ 引言
ꢀ ꢀ 工程领域和科学研究中的最优化问题经常需要同
时处理多个相互冲突的目标,称之为多目标优化问题
(Multiobjective Optimization Problems,MOPs).目前,用于
解决多目标优化问题的多目标进化算法(Multiobjective
Evolutionary Algorithms,MOEAs) 大致可以分为三类,即
基于支配的多目标进化算法、基于指标的多目标进化
等.对于基于分解和基于指标的多目标进化算法,有代
表性的分别是 MOEA/ D[3,4] 和 SMS⁃EMOA[5]
.
此外,为了改善多目标进化算法的收敛性和多样
性等性能,许多基于聚类的多目标进化算法成为研究
热点.Wenbin 等[6] 将聚类应用于环境选择过程,提出了
一种基于模糊 C 均值聚类的多目标遗传算法.Santosh
收稿日期:2016⁃05⁃23;修回日期:2016⁃12⁃14;责任编辑:李勇锋
基金项目:国家自然科学基金(No.71501110)
电ꢀ ꢀ 子ꢀ ꢀ 学ꢀ ꢀ 报
2017 年
2678
Mungle 等[7] 利用模糊聚类减小 Pareto 解集的大小,设
Step7 更新种群ꢀ 利用更新准则,生成下一代种群
计出了一种基于聚类的遗传算法.Wu Chunguo 等[8]
设
P,P A.
=
Step8 判断终止条件ꢀ 若算法的迭代次数达到上
计了基于近邻传播聚类的遗传算法,提出了一种基于
[9]
限 maxGens,则输出最终种群 P,否则跳转至 Step2.
2.2ꢀ 模糊 C 均值聚类算法
模糊 C 均值聚类算法(FCM)[10] 主要用于对数据集
进行模糊划分.假设有 N 个数据点 x1 ,x2 ,…,xN 需要分
成 C 类,则对这些数据点的模糊划分可以表示成一个
聚类的适应度赋值策略.M A Abido
设计了一种基于
分层聚类的多目标进化算法,通过引入分层聚类来剔
除多余的非支配个体.目前,多数基于聚类的多目标进
化算法主要集中研究聚类在环境选择过程中的应用,
对如何选择优良父代个体的研究很少.
=
隶属度矩阵 U {μij },1<i<N,1≤j≤C,该隶属度矩阵需
本文通过引入聚类算法,设计了一种基于隶属度
的锦标赛选择算子(A Membership Based Tournament Se⁃
lection Operator,MBTS),以标准遗传算法为基础提出了
基于模糊 C 均值聚类的进化算法 ( A Fuzzy C⁃Means
Clustering Based Evolutionary Algorithm,FCEA). 与传统
的锦标赛选择算子不同的是,MBTS 采用隶属度锦标赛
选择机制进行父代个体的选择,仅仅使用了种群的聚
类信息.实验结果表明,FCEA 与其他几种经典的进化算
法相比,具有一定的竞争力.
满足如下条件:
μij ∈[0,1]
(1)
(2)
C
=
μ
1,1≤i≤N
∑
ij
=
j
1
N
0<
μ <N,1≤j≤C
(3)
∑
ij
=
i
1
其中 μij 表示第 i 个数据点隶属于第 j 类的隶属度,μij 的
值越高表示第 i 个数据点隶属于第 j 类的程度越高.
FCM 算法的流程如算法 1 所示.
2ꢀ 基于模糊 C 均值聚类的进化算法
算法 1ꢀ FuzzyC⁃means(P,C)
2.1ꢀ FCEA 算法描述
1
N
=
×
1.Input:P { x ,…,x },number of clusters C,positive⁃definite ( n n)
weight matrix A,weighting exponent m,1ư 5≤m≤3ư 0,maximum number
iterations t.
FCEA 算法的流程如下所示:
1
2
N
=
Step1 初始化ꢀ 初始化种群 P {x ,x ,…,x },配
置算法中的相关参数如聚类个数 C、进化代数 maxGens、
=
2.Generate an initial membership matrix U randomly,U {μij }.
=
3.for k 1 to t do
=
交叉变异概率等,并构建一个外部种群 A P.
N
(μ )m xi
Step2 聚类操作ꢀ 利用模糊 C 均值聚类算法(Fuzzy
C⁃Means Clustering Method,FCM)对种群 P 进行聚类,获
∑
N
ij
=
i
1
=
4.Update the cluster centersꢀ υj
5.Update membership valuesꢀ μij
.
(μ )m
∑
ij
=
得种群的隶属度矩阵,U {μij },1≤i≤N,1≤j≤C.
=
i
1
-
-
1
xi υj
2/ (m 1)
C
Step3 构建交配池ꢀ 为每个个体 xi 构建相对应的
-
A
=
.
∑
( ( ) )
xi υp
i
交配池 Qi ,Qi P\{x },并执行 Step4~ Step6.
-
=
p
1
A
=
N
C
m
m
2
- -
(μ (k) μij (k 1)) ≤ε then
ij
6.if
Step4 选择操作ꢀ 调用基于隶属度的锦标赛选择算
∑∑
=
=
1
i
1
j
i
=
子,选择优良父代个体,存入集合 Qp 中,Qp MBTS(Q ).
=
where ε represents the given sensitivity threshold,ε 0ư 01.
ꢀ
Step5 交叉变异ꢀ 先利用差分算子将当前个体 xi
与父代个体相加产生交叉个体 yi′ ,再利用多项式变异算
子对交叉个体进行变异,产生变异个体 yi″ .此外,在完成
交叉与变异后,使用修正方案对不在决策空间范围内
的交叉个体和变异个体进行修正.最后将生成的子代个
=
7.return membership matrix U {μij }.
8.end if
9.end for
2.3ꢀ 基于隶属度的锦标赛选择算子(MBTS)
FCEA 算法采用了改进的锦标赛选择算子(MBTS)
选择父代个体,MBTS 的基本流程如算法 2 所示.首先,
根据最大隶属度原则确定当前个体所属的类 m;然后,
从交配池 Qi 中随机选择 n 个个体,并比较其在类 m 中
的隶属度值,其中隶属度最大的个体将被选作父代个
体执行交叉变异产生子代.
体 yi ( y1 ,y2 ,…,yN ) 保存于外部种群 A 中,A A∪
=
=
{yi }.修正方案为 yi
=
a , if y <a
ì
i
i
i
ï
ï
b , else if y >b ,其中 a 和 b 分别表示基 因 的 上 下
í
i
i
i
i
i
ï
ï
y , otherwise
î
i
边界.
算法 2ꢀ MBTS(Qi )
Step6 环境选择操作ꢀ 采用 SMS⁃EMOA[5] 算法中
的基于超体积度量的环境选择算子淘汰种群中质量差
i
=
Input:mating pool Q ,membership matrix U {μij },1≤i≤N,1≤j≤C,
i
cluster index m which denotes the cluster that xi belongs to,a parent
=
的个体,A Environmental- Selection(A∪{y }).
全部评论(0)