所有数学稿件请用Word+MathType排版。谢谢合作！公式尽....DOC

1、2018 年 5 月 重庆师范大学学报(自然科学版) May 2018第 35 卷 第 3 期 Journal of Chongqing Normal University(Natural Science) Vol.35 No.3-*收稿时间：2017-02-28 修回时间：2018-04-14资助项目：国家自然科学基金 (No.11431004；No.11671062；No.11271391)；重庆市基础与前沿研究计划项目(No.cstc2015jcyjA00027)；重庆市教委科学技术研究项目(No.KJ1500303); 重庆市科委科学研究项目(No.cstc2014jcyjA00004

2、); 重庆市研究生科研创新项目(No.CYS17174).第一作者简介：徐威娜，女，研究方向为多目标优化理论与方法，E-mail：doris_；通信作者：赵克全，教授，博士生导师，E-mail:所有数学稿件请用 Word+MathType 排版。谢谢合作！公式尽量接排，有式号的公式断行居中。全文公式拉通编号(1)、(2) 等，不要分节编号。DOI:基于选择算子改进的多目标基因算法徐威娜，汪定国，赵克全(重庆师范大学 数学科学学院，重庆 401331)摘要：【目的】为了提高多目标基因算法的有效性，获得更真实的 Pareto 前沿面。【方法】利用有效点定义减少计算复杂度，并基于分类 Pareto

3、前沿面的动态规划，定义了密度指数描绘前沿面上有效点的密集程度，使得被选点差异性更大且更靠近前沿面。【结果】在减少计算复杂度和增加被选点多样性这两方面改进了多目标基因算法。【结论】数值实验结果表明该方法是有效的。数学稿件可根据需要将必要的公式写入摘要中。关键词：基因算法；多目标优化；Pareto 前沿；选择算子中图分类号：O221.6 文献标志码：A 文章编号：1672-6693(2018)03- -多目标优化理论与方法在经济管理、工程设计和交通规划等诸多领域均有十分广泛的应用。目前关于多目标优化理论与方法的研究已取得了一系列基础且重要的研究成果 1-5。多目标优化问题的求解方法是多目标优化研究

4、领域中十分重要的研究方向。目前，关于多目标优化问题的求解方法主要包括两种类型，一种是通过某种适当的标量化方法将多目标优化问题转化为单目标优化问题，进而通过研究单目标优化问题获得多目标优化问题的一些重要性质，如 -约束法 1、线性加权法 2-3和理想点法 4等。虽然单目标优化问题的计算方法已经发展得比较完善，但其每次计算只能得到一个解，在实际应用中决策者通常希望得到一系列方案以适应不同的实际需求。而另一种类型则是直接设计求解多目标优化问题的算法，其中以基因算法为代表的进化计算方法已取得了大量的研究成果 6-8。近些年来，一些学者进一步对多目标基因算法进行了改进 9-15。特别地，Deb 11提出

5、了将种群内每个个体按 Pareto 解进行分层排序，偏好位于目标空间中稀疏区域的个体。值得注意的是，多目标基因算法中主要关注这两个基本问题：选择的点均匀分布在 Pareto 前沿面上以及更靠近真实的 Pareto 前沿面。受文献9-10 的启发，本文针对选择算子在保留被选择点的多样性和减少迭代过程中的计算复杂度这两方面进行改进。该算法在文献11中提出的 Pareto 前沿面分层选择的基础上，定义了新的密度指数用于刻画 Pareto 前沿面上有效点的密集程度，使得每一步迭代过程被选中点的稀疏性更大并且更靠近前沿面。最后，通过测试函数进行数值实验，结果表明该算法是有效的。1 预备知识本部分主要介绍

6、一些基本定义和基因算法的基本步骤。(公式请参考下面，尽量接排。向量、矩阵用加黑的斜体表示)给定向量 ， ，定义序关系：12,n=x（ ） 12(,)ny R; ； ，且至iiyx ,iix， ,12,iixyn少有一个 使得 。 iix考虑如下多目标优化问题：重庆师范大学学报(自然科学版) http:/ 第 35 卷。12(MOP)min(),(),(),pFfxfx X定义 1 假定 ，如果不存在 使得 ，则称 是(MOP)的有效点，5*xXX*F*为 (MOP)的 Pareto 有效解。*x定义 2 假定 ，如果不存在 使得 ，则称 是(MOP)的弱有效点，5*x*()x*x为 (MOP)

7、的弱 Pareto 有效解。*假设 和 分别为第 代父代和子代。基因算法的基本步骤为：步骤 1，赋初值；步骤 1.1，)(tPOt产生初始种群 ；步骤 1.2，设置交叉概率、变异概率和最大迭代次数；步骤 2，当最大迭代次数未0达到，执行；步骤 2.1，交叉算子产生 ；步骤 2.2，变异算子产生 ；步骤 2.3，评估 和)(1tO)(2tO)(1tO，计算适应度函数；步骤 2.4，选择算子构建下一代种群。)(2tO2 基于改进选择算子的多目标基因算法本节从两方面对选择算子进行改进，提出一种解决无约束多目标优化问题的基因算法。首先，对选择算子的后代进行遴选时，若一点被视为有效点，则那些在 中的点则

8、不是有效点，可以去除该多余nR搜索空间。该判断可以保留种群内有效点且不影响后续迭代过程中有效点的选择。假设种群内有 个点n且点 是有效点，且属于 中点的数量为 ，则在下一步中需要运算的点是 个而不是 ，0i0niRmm新的计算量将少于原来的 。原先的种群数量和迭代步骤是巨大的，该方法最大的优点在于可以减()O少计算的存储量和计算时间，降低计算复杂度。定理 1 如果点 在种群 中被判断为有效点，则所有在 中的点被定义为0()FxN00()()nFxxR集合 。 中全部有效点等价于 中有效点。MN证明 假设 为 中的有效点，则任意 ，不存在 。又由0()M1()NM10()F定义可知，任意 使得

9、，则可得任意 ，不存在 。因2x20()xF x()x此， 为 中的有效点。0()FN反之， 为 中的有效点，可得任意 ，不存在 。又由任意x()xN0()Fx使得 ，则 中无有效点。则任意 ，不存在1()M10()Fx M1M为 中的有效点。因此， 中全部有效点等价于 中全部有效点。 0,FxN N证毕第 3 期 徐威娜，等：多目标优化近似解的一些非线性标量化性质因此，减少计算量的改进选择算子算法设计如下。算法 1 步骤 1，输入当前种群，其目标函数值和被选择点的数量；步骤 2，当被选择点的数量没有达到或种群的大小没有填充满，求得 Pareto 前沿面；步骤 3，如果 是有效点，则满足 的

10、将被移出当前种群；iynkiyRk步骤 4，表示 Pareto 前沿面。对选择算子做出的改进还体现在选择点的多样性。为了获得均匀分布的解，保持种群的多样性很重要。如果选择算子中没有体现多样性的原则，在计算过程中种群趋于形式相对更少的一些集群，则无法准确地描绘出完整的 Pareto 前沿面。因此，刻画密集程度和判断其密度显得十分重要。为保持种群点的密度，若有效点位于 Pareto 前沿面的疏松区域，则该有效点进入下一次迭代种群的概率越大。Pareto 前沿面的疏松区域定义为：随机选出一个前沿面上的点当作参考点并计算该点到前沿面上其它点的距离，并划分出最小和最大距离，得到距离范围后进行等距隔断，每

11、一个间断中有效点的数量作为疏松程度的判断。若迭代过程中有效点数量减少，则后续迭代时有效点分布将更稀疏。本文的选择算子不只是保持点的密度，还保证得到尽可能完整的 Pareto 解。该方法的优点在于保持目标函数空间的全局密度性，计算出的密度作为结果对于其他方法保持相似的计算有效性。算法 2 步骤 1，输入：初始种群、初始种群目标函数值和被选择点的数量(x popu-size)。步骤 2，当被选择点的数量没有达到或者种群数量没有充满，则执行步骤 2.1。步骤 2.1，Pareto 分层：在种群目标函数值中选择 Pareto 点，Pareto 点集定义为 ，并将 Pareto 点S移出种群目标函数值。

12、步骤 2.2，在 中动态控制被选择点的数量: ，如果 少于 的长度 ，则可以在S1ipousiz-ex()Ls中选择点 ，否则 ，重复计算。（变量只能用一个符号表示，若有说明可作为下标）Spousiz-ex1i步骤 2.3，判断有效点唯一性：如果 ，则在 中只有唯一有效点，直接增加下一代种群，()LsS返回步骤 2，否则返回步骤 2.4。步骤 2.4，计算距离：随机选择 中点 作为参考点，计算 到 中所有点的距离，并定义该距离S*x*x为 。令 为 中最小值， 为 中最大值。DabD步骤 2.5，计算数量：将 划分为相同长度的 个间隔，统计每一个间断有效点的数量。令 ,an，其中 为第 个间断

13、中有效点的数量。12,()npp ()i步骤 2.6，计算被选择间隔的概率：若某一间隔没有包含 中任一有效点，则该间隔的概率为 0。S若一间隔包含 中全部有效点，则概率为 1。否则，定义间断概率为 ，并标准化 。S ()()1piip重庆师范大学学报(自然科学版) http:/ 第 35 卷步骤 2.7，累计概率：累计 ， 。p()1)(0)iipi，步骤 2.8，使用轮盘赌策略选择一个点进入下一层种群：若随机数在 中，且(1)(pii， 则在第 个间断中随机选择一个有效点，并将其放入下一次种群。(0)pi步骤 3，返回步骤 2 定义下一层 Pareto 前沿面。重复步骤 2 直到选择种群被填

14、满，则每一个点都会被分类到某一 Pareto 前沿面。定义 Pareto 前沿面指标 为 。()yStyl注 1 需要注意的是，在步骤 2.3 中动态控制 中被选择点的数量，不仅保证种群的多样性还遵循一种原则，即较低层次的 Pareto 前沿面需要选择更多的有效点。另外在步骤 2.6 中，概率的定义可表示为间断的数量越少则间断被选择的概率更大。本文改进的选择算子需要结合算法 1 和算法 2。这仅需要改变算法 2 的步骤 2.1 为：步骤 2.1，Pareto 层：选择 sele-value 中的有效点 ，有效点集被定义为 ，并从 sele-value 中移除iyS该有效点和位于 中的全部点。n

15、iyR3 数值实验本节对改进的基因算法进行数值实验. 首先, 将算法应用于 3 个多目标测试函数 11。数值实验均在Matlab 2010a 环境中执行。针对文献10,15中的测试函数，见表 1。图 1-3 描绘了这 3 个模型的目标函数值空间，曲线为 Pareto 前沿面。表 1 多目标测试问题（表应该为三线表，且需要有英文表题）Tab.1 Multi-objective Text Problems问题 维数 定义域 目标函数 最优解 凸性SCH 1 5,0221()(),fxfx0,2x凸FON 3 -4,4 4,3122ep()()iifxx1231,非凸KUR 3 5,110.8321

16、e()|5sin()niiiifxx见参考文献11 非凸图 1 SCH 图 2 FON 图 3 KUR第 3 期 徐威娜，等：多目标优化近似解的一些非线性标量化性质Fig.1 SCH Fig.2 FON Fig.3 KUR图均应有中、英文图题针对文献10,15中的测试问题。图 4-12 给出了这些测试问题的目标函数值空间，曲面或曲线代表了 Pareto 前沿面。在这些测试问题中，UF1-7 有 2 个目标函数， UF8-10 有 3 个目标函数，UF5-6 和 9的 Pareto 点是不连续的。因 UF1 和 UF2 的图相似，这里只给出 UF1 的图。本文使用文献15中的性能指标，这里用 表

17、示，假设 是沿着 Pareto 前沿均匀分布点的集合，IGDH*P令 是求解得到的点集合。则 与 的平均距离定义为 ，其中A*PA*I(,)(,)|vPdAA。 的数值越小意味着集合 更接近理论的 Pareto 前沿 且最终(,)minyAdvvIGD(,) *P获得的点有更好的差异性。双目标问题的种群数量为 100，三目标问题的种群数量为 150，函数评估的数量少于 300 000。每次实验，独立运行算法 30 次。其指标 见表 2。IGDH图 4 UF1 图 5 UF3 图 6 UF4Fig.4 UF1 Fig.5 UF3 Fig.6 UF4图 7 UF5 图 8 UF6 图 9 UF7F

18、ig.7 UF5 Fig.8 UF6 Fig.9 UF7图 10 UF8 图 11 UF9 图 12 UF10Fig.10 UF8 Fig.11 UF9 Fig.12 UF10重庆师范大学学报(自然科学版) http:/ 第 35 卷表 2 的数值性能IGDHTab. 2 Numerical Performance of IGD函数 UF1 UF2 UF3 UF4 UF5 UF6 UF7 UF8 UF9 UF10平均值 0.009 6 0.008 5 0.038 4 0.016 4 0.103 8 0.120 0 0.062 5 0.132 3 0.101 1 0.163 0最小值 0.006

19、 4 0.006 2 0.008 0 0.010 3 0.079 1 0.032 4 0.025 3 0.092 8 0.073 4 0.100 2最大值 0.020 7 0.018 0 0.118 5 0.021 6 0.170 3 0.438 9 0.121 5 0.191 7 0.151 8 0.252 1从表 2 中可得，算法在解决 UF2 中执行效果最好， 平均值为 0.008 5。UF1-2 的平均 值IGDHIGDH少于 0.01。UF3,4,7 平均 值介于 0.01 和 0.10。其他问题的 值在 0.10 和 0.20 之间。IGDHI参考文献：1 林锉云,董家礼 .多目标

20、最优化的方法与理论 M.吉林:吉林教育出版社,1992.LIN C Y,DONG J L.The method and theory of multi-objective optimizationM.Jilin:Jinlin Education Publishing House,1992.2 胡毓达.多目标决策 M.上海:上海科学技术出版社,2010.HU Y D.Multi-objective decisionM.Shanghai:Shanghai Scientific multi-objective optimization; Pareto frontier; selection oper

21、ator一、关于页眉页脚的设置方法：选“ 页面布局 ” “页面设置”“ 版式”勾选“首页不同” 和“奇偶页不同 ”及下面的应用于“整篇文档”。二、关于数学公式：1.变量请全部用斜体，矩阵请用加黑的斜体表示，导数、三角函数、自然对数的底 e、max、Re 、def、inf、sup、矩阵的转置 T 等符号均用正体；2.自然数集 N，整数集 Z，有理数集 Q，实数集 R，复数集 C 请全部用加粗、正体；3.编了式号的公式请提行居中，式号需右对齐，例如(1),abcR公式只有在文中需要的地方才编号，后文若未提及前面的某式，该式不用编号。公式编号请全文统一用连续的号，1，2，3，不要编为 1.1，2.1 等形式！