您现在的位置是：首页 > 技术资料 > 基于模糊C均值聚类的锦标赛选择机制与多目标优化研究

推荐星级：

基于模糊C均值聚类的锦标赛选择机制与多目标优化研究

更新时间：2019-12-24 07:07:16 大小：2M 上传用户：zhiyao6 查看TA发布的资源 标签：模糊C均值聚类 下载积分：1分评价赚积分（如何评价?）打赏收藏评论(0) 举报

资料介绍

本文提出了一种用于多目标优化的进化算法——基于模糊C均值聚类的进化算法(A Fuzzy C-Means Clustering Based Evolutionary Algorithm,FCEA).在算法的迭代过程中,先利用模糊C均值聚类算法寻找种群的分布结构,通过对每一代种群进行模糊划分,获得每个个体隶属于每一类的隶属度,然后本文设计了一种基于隶属度的锦标赛选择算子,用于从整个种群中选择相似个体进行重组,引导算法进行搜索.实验结果表明,基于隶属度的锦标赛选择算子的应用能够提升算法的性能,与MOEA/D-DE、NSGAII、SPEA2、SMS-EMOA等先进的优化算法进行比较的结果表明,FCEA在求解具有复杂Pareto前沿的多目标优化问题(GLT系列)时具有一定的竞争力.

部分文件列表

文件名	大小
基于模糊C均值聚类的锦标赛选择机制与多目标优化研究.pdf	2M

立即下载

【关注视频号领20积分】【关注公众号立即送20积分】

部分页面预览

（完整内容请下载后查看）

第１１期

电ꢀ

ꢀ

子ꢀ

ꢀ

学ꢀ

ꢀ

报

Ｖｏｌ．４５ꢀ Ｎｏ．１１

Ｎｏｖ．ꢀ ２０１７

２０１７年１１月

ＡＣＴＡＥＬＥＣＴＲＯＮＩＣＡＳＩＮＩＣＡ

基于模糊Ｃ均值聚类的锦标赛选择机制

与多目标优化研究

张ꢀ 屹^１，余ꢀ 振^１，李子木^１，陆瞳瞳^２

（１．三峡大学机械与动力学院，湖北宜昌４４３００２；２．常州大学商学院，江苏常州２１３１６４）

ꢀ ꢀ 摘ꢀ 要：ꢀ 本文提出了一种用于多目标优化的进化算法———基于模糊Ｃ均值聚类的进化算法（ＡＦｕｚｚｙＣ⁃Ｍｅａｎｓ

ＣｌｕｓｔｅｒｉｎｇＢａｓｅｄＥｖｏｌｕｔｉｏｎａｒｙＡｌｇｏｒｉｔｈｍ，ＦＣＥＡ）．在算法的迭代过程中，先利用模糊Ｃ均值聚类算法寻找种群的分布结

构，通过对每一代种群进行模糊划分，获得每个个体隶属于每一类的隶属度，然后本文设计了一种基于隶属度的锦标

赛选择算子，用于从整个种群中选择相似个体进行重组，引导算法进行搜索．实验结果表明，基于隶属度的锦标赛选择

算子的应用能够提升算法的性能，与ＭＯＥＡ／Ｄ⁃ＤＥ、ＮＳＧＡＩＩ、ＳＰＥＡ２、ＳＭＳ⁃ＥＭＯＡ等先进的优化算法进行比较的结果表

明，ＦＣＥＡ在求解具有复杂Ｐａｒｅｔｏ前沿的多目标优化问题（ＧＬＴ系列）时具有一定的竞争力．

关键词： ꢀ 进化算法；多目标优化；模糊Ｃ均值聚类；隶属度选择

中图分类号： ꢀ ＴＰ１８ꢀ ꢀ ꢀ 文献标识码： ꢀ Ａꢀ ꢀ ꢀ 文章编号： ꢀ ０３７２⁃２１１２（２０１７）１１⁃２６７７⁃０８

电子学报ＵＲＬ：ｈｔｔｐ：／／ｗｗｗ．ｅｊｏｕｒｎａｌ．ｏｒｇ．ｃｎꢀ

ＤＯＩ：１０．３９６９／ｊ．ｉｓｓｎ．０３７２⁃２１１２．２０１７．１１．０１５

ＴｏｕｒｎａｍｅｎｔＳｅｌｅｃｔｉｏｎｆｏｒＭｕｌｔｉｏｂｊｅｃｔｉｖｅＯｐｔｉｍｉｚａｔｉｏｎ

ＢａｓｅｄｏｎＦｕｚｚｙＣ⁃ＭｅａｎｓＣｌｕｓｔｅｒｉｎｇＭｅｔｈｏｄ

ＺＨＡＮＧＹｉ^１，ＹＵＺｈｅｎ^１，ＬＩＺｉ⁃ｍｕ^１，ＬＵＴｏｎｇ⁃ｔｏｎｇ^２

（１．ＣｏｌｌｅｇｅｏｆＭｅｃｈａｎｉｃａｌａｎｄＰｏｗｅｒＥｎｇｉｎｅｅｒｉｎｇ，ＣｈｉｎａＴｈｒｅｅＧｏｒｇｅｓＵｎｉｖｅｒｓｉｔｙ，Ｙｉｃｈａｎｇ，Ｈｕｂｅｉ４４３００２，Ｃｈｉｎａ；

２．ＳｃｈｏｏｌｏｆＢｕｓｉｎｅｓｓ，ＣｈａｎｇｚｈｏｕＵｎｉｖｅｒｓｉｔｙ，Ｃｈａｎｇｚｈｏｕ，Ｊｉａｎｇｓｕ２１３１６４，Ｃｈｉｎａ）

Ａｂｓｔｒａｃｔ：ꢀ ＡｆｕｚｚｙＣ⁃ｍｅａｎｓｃｌｕｓｔｅｒｉｎｇｂａｓｅｄｅｖｏｌｕｔｉｏｎａｒｙａｌｇｏｒｉｔｈｍｃａｌｌｅｄＦＣＥＡｗａｓｐｒｏｐｏｓｅｄｔｏｏｐｔｉｍｉｚｅｍｕｌｔｉｏｂ⁃

ｊｅｃｔｉｖｅｏｐｔｉｍｉｚａｔｉｏｎｐｒｏｂｌｅｍｓ．Ｉｎｔｈｅｐｒｏｃｅｓｓｏｆｉｔｅｒａｔｉｏｎｏｆｔｈｉｓａｌｇｏｒｉｔｈｍ，ａｆｕｚｚｙＣ⁃ｍｅａｎｓｃｌｕｓｔｅｒｉｎｇｍｅｔｈｏｄｉｓｆｉｒｓｔｌｙｅｍ⁃

ｐｌｏｙｅｄｔｏｉｍｐｌｅｍｅｎｔａｆｕｚｚｙｐａｒｔｉｔｉｏｎｏｆｔｈｅｐｏｐｕｌａｔｉｏｎｓｏａｓｔｏｄｉｓｃｏｖｅｒｔｈｅｐｏｐｕｌａｔｉｏｎｄｉｓｔｒｉｂｕｔｉｏｎｓｔｒｕｃｔｕｒｅａｎｄｔｏｏｂｔａｉｎａ

ｍｅｍｂｅｒｓｈｉｐｍａｔｒｉｘｏｆｔｈｅｐｏｐｕｌａｔｉｏｎａｔｅａｃｈｇｅｎｅｒａｔｉｏｎ．Ａｃｃｏｒｄｉｎｇｔｏｔｈｅｄｉｓｔｒｉｂｕｔｉｏｎｓｔｒｕｃｔｕｒｅ，ａｍｅｍｂｅｒｓｈｉｐｂａｓｅｄｔｏｕｒｎａ⁃

ｍｅｎｔｓｅｌｅｃｔｉｏｎｓｔｒａｔｅｇｙ（ＭＢＴＳ）ｉｓｄｅｓｉｇｎｅｄｔｏｓｅｌｅｃｔｎｅｉｇｈｂｏｒｉｎｇｓｏｌｕｔｉｏｎｓｆｒｏｍｔｈｅｐｏｐｕｌａｔｉｏｎｆｏｒｒｅｃｏｍｂｉｎａｔｉｏｎａｎｄｔｏ

ｇｕｉｄｅｓｅａｒｃｈ．ＴｈｅｅｘｐｅｒｉｍｅｎｔｓｐｒｅｓｅｎｔｔｈａｔＭＢＴＳｓｉｇｎｉｆｉｃａｎｔｌｙｃｏｎｔｒｉｂｕｔｅｓｔｏｔｈｅｐｅｒｆｏｒｍａｎｃｅｏｆＦＣＥＡ．Ｃｏｍｐａｒｉｓｏｎｅｘｐｅｒｉ⁃

ｍｅｎｔｓｓｈｏｗｔｈａｔｔｈｅｐｒｏｐｏｓｅｄＦＣＥＡｏｕｔｐｅｒｆｏｒｍｓＭＯＥＡ／Ｄ⁃ＤＥ，ＮＳＧＡＩＩ，ＳＰＥＡ２ａｎｄＳＭＳ⁃ＥＭＯＡｏｎｓｏｌｖｉｎｇＧＬＴｔｅｓｔ

ｓｕｉｔｅｗｉｔｈｃｏｍｐｌｉｃａｔｅｄＰａｒｅｔｏＦｒｏｎｔ（ＰＦ）ｓｈａｐｅｓ．

Ｋｅｙｗｏｒｄｓ：ꢀ ｅｖｏｌｕｔｉｏｎａｒｙａｌｇｏｒｉｔｈｍ；ｍｕｌｔｉｏｂｊｅｃｔｉｖｅｏｐｔｉｍｉｚａｔｉｏｎ；ｆｕｚｚｙＣ⁃ｍｅａｎｓｃｌｕｓｔｅｒ；ｍｅｍｂｅｒｓｈｉｐｓｅｌｅｃｔｉｏｎ

算法和基于分解的多目标进化算法．基于支配的多目标

进化算法包括ＮＳＧＡＩＩ^［１］、ＳＰＥＡ及改进后的ＳＰＥＡ２^［２］

１ꢀ 引言

ꢀ ꢀ 工程领域和科学研究中的最优化问题经常需要同

时处理多个相互冲突的目标，称之为多目标优化问题

（ＭｕｌｔｉｏｂｊｅｃｔｉｖｅＯｐｔｉｍｉｚａｔｉｏｎＰｒｏｂｌｅｍｓ，ＭＯＰｓ）．目前，用于

解决多目标优化问题的多目标进化算法（Ｍｕｌｔｉｏｂｊｅｃｔｉｖｅ

ＥｖｏｌｕｔｉｏｎａｒｙＡｌｇｏｒｉｔｈｍｓ，ＭＯＥＡｓ）大致可以分为三类，即

基于支配的多目标进化算法、基于指标的多目标进化

等．对于基于分解和基于指标的多目标进化算法，有代

表性的分别是ＭＯＥＡ／Ｄ^{［３，４］}和ＳＭＳ⁃ＥＭＯＡ^［５］

．

此外，为了改善多目标进化算法的收敛性和多样

性等性能，许多基于聚类的多目标进化算法成为研究

热点．Ｗｅｎｂｉｎ等^［６］将聚类应用于环境选择过程，提出了

一种基于模糊Ｃ均值聚类的多目标遗传算法．Ｓａｎｔｏｓｈ

收稿日期：２０１６⁃０５⁃２３；修回日期：２０１６⁃１２⁃１４；责任编辑：李勇锋

基金项目：国家自然科学基金（Ｎｏ．７１５０１１１０）

电ꢀ ꢀ 子ꢀ ꢀ 学ꢀ ꢀ 报

２０１７年

２６７８

Ｍｕｎｇｌｅ等^［７］利用模糊聚类减小Ｐａｒｅｔｏ解集的大小，设

Ｓｔｅｐ７更新种群ꢀ 利用更新准则，生成下一代种群

计出了一种基于聚类的遗传算法．ＷｕＣｈｕｎｇｕｏ等^［８］

设

Ｐ，ＰＡ．

＝

Ｓｔｅｐ８判断终止条件ꢀ 若算法的迭代次数达到上

计了基于近邻传播聚类的遗传算法，提出了一种基于

［９］

限ｍａｘＧｅｎｓ，则输出最终种群Ｐ，否则跳转至Ｓｔｅｐ２．

２．２ꢀ 模糊Ｃ均值聚类算法

模糊Ｃ均值聚类算法（ＦＣＭ）^［１０］主要用于对数据集

进行模糊划分．假设有Ｎ个数据点ｘ^１，ｘ^２，…，ｘ^Ｎ需要分

成Ｃ类，则对这些数据点的模糊划分可以表示成一个

聚类的适应度赋值策略．ＭＡＡｂｉｄｏ

设计了一种基于

分层聚类的多目标进化算法，通过引入分层聚类来剔

除多余的非支配个体．目前，多数基于聚类的多目标进

化算法主要集中研究聚类在环境选择过程中的应用，

对如何选择优良父代个体的研究很少．

＝

隶属度矩阵Ｕ｛μ_ｉｊ｝，１＜ｉ＜Ｎ，１≤ｊ≤Ｃ，该隶属度矩阵需

本文通过引入聚类算法，设计了一种基于隶属度

的锦标赛选择算子（ＡＭｅｍｂｅｒｓｈｉｐＢａｓｅｄＴｏｕｒｎａｍｅｎｔＳｅ⁃

ｌｅｃｔｉｏｎＯｐｅｒａｔｏｒ，ＭＢＴＳ），以标准遗传算法为基础提出了

基于模糊Ｃ均值聚类的进化算法（ＡＦｕｚｚｙＣ⁃Ｍｅａｎｓ

ＣｌｕｓｔｅｒｉｎｇＢａｓｅｄＥｖｏｌｕｔｉｏｎａｒｙＡｌｇｏｒｉｔｈｍ，ＦＣＥＡ）．与传统

的锦标赛选择算子不同的是，ＭＢＴＳ采用隶属度锦标赛

选择机制进行父代个体的选择，仅仅使用了种群的聚

类信息．实验结果表明，ＦＣＥＡ与其他几种经典的进化算

法相比，具有一定的竞争力．

满足如下条件：

μ_ｉｊ∈［０，１］

（１）

（２）

Ｃ

＝

１，１≤ｉ≤Ｎ

∑

ｉｊ

＝

ｊ

１

Ｎ

０＜

μ ＜Ｎ，１≤ｊ≤Ｃ

（３）

∑

ｉｊ

＝

ｉ

１

其中 μ_ｉｊ表示第ｉ个数据点隶属于第ｊ类的隶属度，μ_ｉｊ的

值越高表示第ｉ个数据点隶属于第ｊ类的程度越高．

ＦＣＭ算法的流程如算法１所示．

２ꢀ 基于模糊Ｃ均值聚类的进化算法

算法１ꢀ ＦｕｚｚｙＣ⁃ｍｅａｎｓ（Ｐ，Ｃ）

２．１ꢀ ＦＣＥＡ算法描述

１

Ｎ

＝

１．Ｉｎｐｕｔ：Ｐ｛ｘ，…，ｘ｝，ｎｕｍｂｅｒｏｆｃｌｕｓｔｅｒｓＣ，ｐｏｓｉｔｉｖｅ⁃ｄｅｆｉｎｉｔｅ（ｎｎ）

ｗｅｉｇｈｔｍａｔｒｉｘＡ，ｗｅｉｇｈｔｉｎｇｅｘｐｏｎｅｎｔｍ，１ư ５≤ｍ≤３ư ０，ｍａｘｉｍｕｍｎｕｍｂｅｒ

ｉｔｅｒａｔｉｏｎｓｔ．

ＦＣＥＡ算法的流程如下所示：

１

２

Ｎ

＝

Ｓｔｅｐ１初始化ꢀ 初始化种群Ｐ｛ｘ，ｘ，…，ｘ｝，配

置算法中的相关参数如聚类个数Ｃ、进化代数ｍａｘＧｅｎｓ、

＝

２．ＧｅｎｅｒａｔｅａｎｉｎｉｔｉａｌｍｅｍｂｅｒｓｈｉｐｍａｔｒｉｘＵｒａｎｄｏｍｌｙ，Ｕ｛μ_ｉｊ｝．

＝

３．ｆｏｒｋ１ｔｏｔｄｏ

＝

交叉变异概率等，并构建一个外部种群ＡＰ．

Ｎ

（μ ）^ｍｘ^ｉ

Ｓｔｅｐ２聚类操作ꢀ 利用模糊Ｃ均值聚类算法（Ｆｕｚｚｙ

Ｃ⁃ＭｅａｎｓＣｌｕｓｔｅｒｉｎｇＭｅｔｈｏｄ，ＦＣＭ）对种群Ｐ进行聚类，获

∑

Ｎ

ｉｊ

＝

ｉ

１

＝

４．Ｕｐｄａｔｅｔｈｅｃｌｕｓｔｅｒｃｅｎｔｅｒｓꢀ υ_ｊ

５．Ｕｐｄａｔｅｍｅｍｂｅｒｓｈｉｐｖａｌｕｅｓꢀ μ_ｉｊ

．

（μ ）^ｍ

∑

ｉｊ

＝

得种群的隶属度矩阵，Ｕ｛μ_ｉｊ｝，１≤ｉ≤Ｎ，１≤ｊ≤Ｃ．

＝

ｉ

１

－

１

ｘ^ｉυ_ｊ

２／（ｍ１）

Ｃ

Ｓｔｅｐ３构建交配池ꢀ 为每个个体ｘ^ｉ构建相对应的

－

Ａ

＝

．

∑

( ( ) )

ｘ^ｉυ_ｐ

ｉ

交配池Ｑ^ｉ，Ｑ^ｉＰ＼｛ｘ｝，并执行Ｓｔｅｐ４～Ｓｔｅｐ６．

－

＝

ｐ

１

Ａ

＝

Ｎ

Ｃ

ｍ

２

－－

（μ （ｋ） μ_ｉｊ（ｋ１）） ≤ε ｔｈｅｎ

ｉｊ

６．ｉｆ

Ｓｔｅｐ４选择操作ꢀ 调用基于隶属度的锦标赛选择算

∑∑

＝

１

ｉ

１

ｊ

ｉ

＝

子，选择优良父代个体，存入集合Ｑ_ｐ中，Ｑ_ｐＭＢＴＳ（Ｑ）．

＝

ｗｈｅｒｅ ε ｒｅｐｒｅｓｅｎｔｓｔｈｅｇｉｖｅｎｓｅｎｓｉｔｉｖｉｔｙｔｈｒｅｓｈｏｌｄ，ε ０ư ０１．

ꢀ

Ｓｔｅｐ５交叉变异ꢀ 先利用差分算子将当前个体ｘ^ｉ

与父代个体相加产生交叉个体ｙ_ｉ^′，再利用多项式变异算

子对交叉个体进行变异，产生变异个体ｙ_ｉ^″．此外，在完成

交叉与变异后，使用修正方案对不在决策空间范围内

的交叉个体和变异个体进行修正．最后将生成的子代个

＝

７．ｒｅｔｕｒｎｍｅｍｂｅｒｓｈｉｐｍａｔｒｉｘＵ｛μ_ｉｊ｝．

８．ｅｎｄｉｆ

９．ｅｎｄｆｏｒ

２．３ꢀ 基于隶属度的锦标赛选择算子（ＭＢＴＳ）

ＦＣＥＡ算法采用了改进的锦标赛选择算子（ＭＢＴＳ）

选择父代个体，ＭＢＴＳ的基本流程如算法２所示．首先，

根据最大隶属度原则确定当前个体所属的类ｍ；然后，

从交配池Ｑ^ｉ中随机选择ｎ个个体，并比较其在类ｍ中

的隶属度值，其中隶属度最大的个体将被选作父代个

体执行交叉变异产生子代．

体ｙ^ｉ（ｙ_１，ｙ_２，…，ｙ_Ｎ）保存于外部种群Ａ中，ＡＡ∪

＝

｛ｙ^ｉ｝．修正方案为ｙ_ｉ

＝

ａ，ｉｆｙ＜ａ

ｉ

ｂ，ｅｌｓｅｉｆｙ＞ｂ，其中ａ和ｂ分别表示基因的上下

ｉ

ｙ，ｏｔｈｅｒｗｉｓｅ

ｉ

边界．

算法２ꢀ ＭＢＴＳ（Ｑ^ｉ）

Ｓｔｅｐ６环境选择操作ꢀ 采用ＳＭＳ⁃ＥＭＯＡ^［５］算法中

的基于超体积度量的环境选择算子淘汰种群中质量差

ｉ

＝

Ｉｎｐｕｔ：ｍａｔｉｎｇｐｏｏｌＱ，ｍｅｍｂｅｒｓｈｉｐｍａｔｒｉｘＵ｛μ_ｉｊ｝，１≤ｉ≤Ｎ，１≤ｊ≤Ｃ，

ｉ

ｃｌｕｓｔｅｒｉｎｄｅｘｍｗｈｉｃｈｄｅｎｏｔｅｓｔｈｅｃｌｕｓｔｅｒｔｈａｔｘ^ｉｂｅｌｏｎｇｓｔｏ，ａｐａｒｅｎｔ

＝

的个体，ＡＥｎｖｉｒｏｎｍｅｎｔａｌ_－Ｓｅｌｅｃｔｉｏｎ（Ａ∪｛ｙ｝）．

全部评论(0)

暂无评论

评论赚积分>>

上传资源上传优质资源有赏金

基于模糊C均值聚类的锦标赛选择机制与多目标优化研究

资料介绍

部分文件列表

部分页面预览

相关下载

全部评论(0)

热门标签

最新上传

热门下载

推荐下载

专栏首页