第３７卷
、，０ｌ＿３７ 第２４期
ＮＯ．２４ 计算机工程
Ｃｏｍｐｕｔｅｒ Ｅｎｇｉｎｅｅｒｉｎｇ ２０１１年ｌ２月
Ｄｅｃｅｍｂｅｒ ２Ｏ１１
・人工智能及识别技术・ 文章编号：ｌ０ｏ ．３４２８（２０１１）２４．－＿ｏ１５２— ３ 文献标识码：Ａ 中圈分类号：ＴＰ３０１・６
求解约束优化问题的佳点集多目标进化算法
裴胜玉
（广西师范大学数学科学学院，广西桂林５４１００４）
摘要：结合数论中的佳点集理论和多目标优化方法，提出一种求解约束优化问题的进化算法。将约束优化问题转化为多目标优化问题， 引入佳点集理论，以确保所构造的个体在搜索空间内分布均匀，设计变异算子增加个体多样性，采用分群局部搜索方式，并根据Ｐａｒｅｔｏ非
支配关系选择群体中的优势个体。实验结果表明，该算法具有较好的稳定性。
关甓词：进化算法；佳点集；约束优化；多目标
Ｍｕｌｔｉ－Ｏｂｊｅｃｔｉｖｅ Ｅｖｏｌｕｔｉｏｎ Ａｌｇｏｒｉｔｈｍ ０ｆ Ｇｏｏｄ Ｐｏｉｎｔ Ｓｅｔ
ｆｏｒ Ｓｏｌｖｉｎｇ Ｒｅｓｔｒａｉｎｔ Ｏｐｔｉｍｉｚａｔｉｏｎ Ｐｒｏｂｌｅｍ
ＰＥＩ Ｓｈｅｎｇ－ｙｕ
（Ｃｏｌｌｅｇｅ ｏｆＭａｔｈｅｍａｔｉｃａｌ Ｓｃｉｅｎｃｅｓ，Ｇｕａｎｇｘｉ Ｎｏｒｍａｌ Ｕｎｉｖｅｒｓｉｔｙ，Ｇｕｉｌｉｎ ５４１００４，Ｃｈｉｎａ）
［Ａｂｓｔｒａｃｔ］Ａ ｍｕｌｔｉ—ｏｂｊｅｃｔｉｖｅ ｅｖｏｌｕｔｉｏｎ ａｌｇｏｒｉｔｈｍ ｂａｓｅｄ ｏｎ ｇｏｏｄ ｐｏｉｎｔ ｓｅｔ ｉｓ ｐｒｏｐｏｓｅｄ ｔｏ ｔａｃｋｌｅ ｒｅｓｔｒａｉｎｔ ｏｐｔｉｍｉｚａｔｉｏｎ ｐｒｏｂｌｅｍｓ．Ｇｏｏｄ ｐｏｉｎｔ ｓｅｔ ｉｎ
ｎｕｍｂｅｒ ｔｈｅｏｒｙ ａｎｄ ｍｕｌｔｉ—ｏｂｊｅｃｔｉｖｅ ｏｐｔｉｍｉｚａｔｉｏｎ ｍｅｔｈｏｄｓ ａｒｅ ｉｎｔｅｇｒａｔｅｄ ｉｎｔｏ ａｌｇｏｒｉｔｈｍ．Ｒｅｓｔｒａｉｎｔ ｏｐｔｉｍｉｚａｔｉｏｎ ｐｒｏｂｌｅｍ ｉｓ ｔｒａｎｓｆｏｒｍｅｄ ｉｎｔｏ ａ
ｂｉ—ｏｂｊｅｃｔｉｖｅ ｏｐｔｉｍｉｚａｔｉｏｎ ｐｒｏｂｌｅｍ．Ｃｏｍｂｉｎｅｄ ｗｉｔｈ ｔｈｅ ｐｒｉｎｃｉｐｌｅ ｏｆ ｇｏｏｄ ｐｏｉｎｔ ｓｅｔ，ｉｔ ｍａｋｅｓ ｔｈｅ ｉｎｄｉｖｉｄｕａｌｓ ｉｎ ｓｅａｒｃｈ ｓｐａｃｅ ｄｉｓｔｒｉｂｕｔｅ ｍｏｒｅ ｅｖｅｎｌｙ． Ｔｈｅ ｎｅｗ ｍｕｔａｔｉｏｎ ｏｐｅｒａｔｏｒ ｉｓ ａｐｐｌｉｅｄ ｆｏｒ ｅｎｈａｎｃｉｎｇ ｔｈｅ ｄｉｖｅｒｓｉｔｙ ｏｆ ｔｈｅ ｏｆｆｓｐｒｉｎｇ ｐｏｐｕｌａｔｉｏｎ．Ａ ｓｕｂ—ｓｗａｒｍ ｌｏｃａｌ ｓｅａｒｃｈ ｏｐｅｒａｔｏｒ ｗｉｔｈ Ｐａｒｅｔｏ
ｎｏｎ—ｄｏｍｉｎａｔｅｄ ｉｓ ｕｓｅｄ ｔｏ ｃｈｏｏｓｅ ｔｈｅ ｂｅｓｔ ｉｎｄｉｖｉｄｕａｌｓ ｆｏｒ ｔｈｅ ｎｅｘｔ ｐｏｐｕｌａｔｉｏｎ．Ｅｘｐｅｒｉｍｅｎｔａｌ ｒｅｓｕｌｔｓ ｓｈｏｗ ｔｈａｔ ｔｈｅ ａｌｇｏｒｉｔｈｍ ｈａｓ ｇｏｏｄ ｓｔａｂｉｌｉｔｙ． ［Ｋｅｙ ｗｏｒｄｓｉ ｅｖｏｌｕｔｉｏｎ ａｌｇｏｒｉｔｈｍ；ｇｏｏｄ ｐｏｉｎｔ ｓｅｔ；ｒｅｓｔｒａｉｎｔ ｏｐｔｉｍｉｚａｔｉｏｎ；ｍｕｌｔｉ—ｏｂｊｅｃｔｉｖｅ
ＤＯＩ：１０．３９６９／ｊ．ｉｓｓｎ．１０００—３４２８．２０１ １．２４．０５ １
ｌ概述
由于约束优化问题的复杂性，而现有的求解算法大多不
能很好地处理各种类型相对复杂的约束优化问题。文献【１１利
用数论中的佳点集理论，对遗传算法（ＧｅｎｅｔｉｃＡｌｇｏｒｉｔｈｍ，ＧＡ）
中的交叉算子进行重新设计，提出佳点集遗传算法，并在许
多问题中取得满意的效果。在用进化算法求解约束优化问题
（Ｃｏｎｓｔｒａｉｎｅｄ Ｏｐｔｉｍｉｚａｔｉｏｎ Ｐｒｏｂｌｅｍｓ，ＣＯＰｓ）时，除算法本身的
搜索能力之外，处理约束条件也是优化效果的关键。目前，
常见的约束处理技术有惩罚函数法、多目标优化法等方法，
如文献【２】提出将可行解与不可行解进行算术交叉，避免引入 惩罚因子。本文针对现有处理约束技术的一些不足，采用进
化算法，提出一种新的求解约束优化问题的算法。
２约束优化问题与处理方法
约束优化问题是实际工程领域常遇到的数学规划问题。
在一般情况下，约束优化问题可描述为：
， ），Ｘ＝（Ｘｌ，Ｘ２，…， ）∈Ｒ ｇＪ（ ）≤０，Ｊ＝ｌ，２，…，ｆ
ｈｉ（ｘ）＝０，ｊ＝｛＋１，ｆ＋２，…，ｍ （１）
其中，Ｘ：（ ， ，…， ）为决策向量； 的取值范围为【ｔ，“ 】；
，（ ）、ｇ ）和ｈｊ． ）均为ｎ维欧氏空间Ｒ 上的 元函数；
， ）为目标函数；ｇ ）为不等式约束条件； ）为等式
约束条件。 基于常用的构造惩罚函数方法，本文对约束条件作如下
处理： ｆｍａｘ｛Ｏ，ｇ，（ ）｝１≤ ≤ｆ … Ｇｊ（ ） ｌｉｈ：ｘ）Ｉ ｆ十１≤ ≤ｍ ’ ６（ ） Ｇｊ（ｘ） （３）
则可以将约束条件转化为一个目标Ｇ ）。Ｇ（ ）与，（ ）构成
２个目标矢量Ｆ（ｘ）：
Ｆ（ ）＝（＿厂（ ），Ｇ（ ）） （４） 从而，由ｎ个决策变量、单个目标函数和ｆ个不等式约束和
ｍ—１个等式约束条件组成的ＣＯＰｓ就转化成含ｎ个决策变
量、２个目标函数的无约束多目标优化问题。
Ｙ＝Ｆ（ ）＝（－厂（ ），Ｇ（ ））
Ｘ：（ ，Ｘ２，…， ）∈Ｘ Ｘ＝｛（ ，ｘ２，・一， ）ｌ‘≤Ｘｉ≤ ｌｌ
，：（１１，１２，…， ）
Ｕ＝（“ｌ，“２，…，Ｕｎ） （５）
下面给出３个关于多目标优化的重要定义：
定义１设Ｄ：Ｒ ＿÷Ｒ ，７１，Ｙ２ Ｒ ，称解Ｊ，１支配解Ｙ２
当且仅当Ｏ（ｙ．）部分优于Ｏ（ｙ ），即Ｖｉｅ（１，２，…，七｝，Ｏｚ（ｙ，）≤
Ｄｆ（ ２），３ｉ∈｛ｌ，２，…， ｝，Ｏｉ（ １）＜Ｄｆ（＿），２），记做Ｙ１ Ｙ２，以上
为Ｐａｒｅｔｏ一支配。
定义２解Ｙ ∈Ｑ称为解集合Ｑ的Ｐａｒｅｔｏ最优懈当且仅
当集合｛＿）， Ｉ Ｙ ’，Ｙ’∈Ｑｊ： ，以上为Ｐａｒｅｔｏ最优解。
定义３对于给定的多目标优化问题，设定义域为Ｑ，则
其Ｐａｒｅｔｏ一最优解集ｙ 定义为：
Ｙ ＝｛Ｓ∈ＱＩ一 。∈Ｑ，Ｏ（ｓ’） Ｏ（ ）ｌ
以上为Ｐａｒｅｔｏ一最优解集。
作者筒介：裴胜玉（１９８２－），男，助教，主研方向：人工智能，进化
算法 收稿日期：２０１１－０７—２５ Ｅ・ｍａｉｌ：ｓｕｎｂａｃｋ ００７＠１６３．ｃｏｒｎ
第３７卷第２４期 裴胜玉：求解约束优化问题的佳点集多目标进化算法 １５３
将ＣＯＰｓ转化为多目标优化问题来处理，可避免使用惩
罚函数，于是可以运用多目标优化自身的特点和方法来求
解。－厂代表目标函数，Ｇ代表约束目标函数，而在非支配解
解集中，因为至多存在一个可行解，所以目标函数的最优可
行解即可行域与Ｐａｒｅｔｏ一前沿的接合点（全局最优解）。如果种
群中所有非支配个体均不可行，则种群所有个体均不可行，
所以如果种群不可行，那么可以从非支配解解集中，选择惩
罚度最小的作为下一代的最优个体；当然非支配个体中的可
行解既可以支配可行解，也可以支配不可行解，但非支配个
体中的不可行解只能支配种群中的不可行解。本文算法是运
用上面这些性质求解ＣＯＰｓ。
３佳点集多目标进化算法
３．１佳点集重要定义与性质 佳点集重要定义与性质…表述如下：
（１）令ｒＥ Ｇ ，ｓ是任意小的正数，形为Ｐｎ（ｋ）＝｛（｛ × ｝，
ｒ２ ｘｋ｝，…，｛ × ｝），ｋ＝１，２，…，ｎ｝偏差，满足妒（ ）＝Ｃ（ｒ，ｅ）ｎ “，
其中，若Ｃ（ｒ，￡）是只与，、￡有关的常数，则称 （ ）为佳点
集，ｒ为佳点。 （２）取 ＝｛２ｃｏｓ（２ｘｋ／ｐ）｝，’１≤ｋ≤ ，其中，若Ｐ表示满
足（ｐ—ｓ）／２≥Ｓ的最小素数，或ｒｋ＝｛ｅ ｝，１≤ｋ≤Ｓ，则ｒ为佳
点，｛ａ｝表示ａ的小数部分。
本文运用佳点集理论，在搜索空间中产生相对均匀分布
的个体。如图１为４００个粒子在二维空间ｔ。，ｔ：∈【Ｏ，４ｏｏ］（单位
为ｍｍ），基于佳点集理论产生的二维佳点集。
，ｉ／ｎ１ｍ 图１二雏佳点集
３．２新的变异算子 本文设计一对新的自适应变异算子 ， ’，当满足变
异概率且个体序号为偶数时，如下：
ｆ （１ ｃｕｒｒｅｎ—ｔ＿ｇ—ｅｎ） １
：｛ （ ）＿（１ Ｌ ） ，】）＜二ｎ （６） １
。ｔｈｅｒｗｉｓｅ
当满足变异概率且个体序号为奇数时，如下：
ｆ （１一ｃ…ｕｒｒｅｎｔ ｇｅｎ） １
ｔ： 一（ 。＿㈣ （ 一 ） （ｏＡ）＜二ｎ （７） ｌＷｉ’ 。ｔｈｅｒｗｉｓｅ
其中，ｉ＝１，２，…，ｎ，ｆ（ “（ｆ）分别代表第ｉ维的最低下限和
最高上限； 和 ’分别表示个体序号为偶数时的当前变异算
子和个体序号为奇数时的当前变异算子；ｕ（ｏ，１）和ｈ均表示
（０，１）之间的随机数；ｃｕｒｒｅｎｔ—ｇｅｎ、ｔｏｔａｌ—ｇｅｎ分别表示当前
迭代次数和总迭代次数。（】＿ｃｕｒｒｅｎｔ—ｇｅｎ／ｔｏｔａｌ—ｇｅｎ） 随着迭 代步数的增加而非线性降低，从而保证进化早期的高效率搜 索，也确保后期种群个体的收敛性。
３．３分群局部搜索方法 本文根据ＣＯＰｓ的特点，利用分群搜索技术，对劣势个
体进行淘汰选择，得到下一代新的优势个体，从而确保迭代
的收敛性。分群局部搜索算法如下：
ｂｅｇｉｎ 随机产生新个体ｒ，ｋ＝０，原种群Ａ，Ａ’＝ ；
ｗｈｉｌｅ ｋ＜ｎ／ｑ ｄｏ 从Ａ找出ｑ个离ｒ最近的个体，得到：Ｍ＝｛ａｌ，ａ２，…，ａ ）
单形交叉，得到：Ｍ’＝ＳＰＸ（Ｍ） 选择Ｍ’中的非支配个体，记为：ｘ－，ｘ２，…，ｘ ｒ
ｊｉ，ｉ∈［１，ｍ’】，ｊ∈【１，ｑｌ，ｉｆ Ｘｉ．＜ａｊ，ｔｈｅｎ ａｉ＝ｘｉ ｅｎｄｉｆ ｉｆ一 ｉ，ｉ∈Ｉ１，ｍ’】，Ｇ（ｘｉ）＝０，ｔｈｅｎ ａｒ＝ｘｋ．ａ 为任一个体，ｘ 为约束惩罚最小个体 ｅｎｄｉｆ
Ａ’＝ ＵＭ
ｋ＝ｋ＋１ ｅｎｄ Ｏｕｔｐｕｔ：Ａ’＝Ａ’Ｕ Ａ ｅｎｄ ３．４单形交叉算子 在局部搜索中，本文引入单形交叉算子（Ｓｉｍｐｌｅｘ ｃｒｏｓｓ— ｏｖｅｒ，ＳＰＸ），该方法不依赖于适应度信息直接生成下一代呈均
匀概率分布的种群个体。详细参见文献【３】。
３．５算法步骤 算法采用实数编码，其步骤如下： Ｓｔｅｐｌ基于佳点集理论产生初始种群ｐｏｐ＝｛ｘｊ，Ｘ２，…，
｝，给定交叉概率ｃｒｏｓｓ＝０．８，变异概率ｍｕｔａｔｉｏｎ＝０．１和分
群规模ｑ＝１２。
Ｓｔｅｐ２对种群个体在维数空间上进行交叉操作。 Ｓｔｅｐ３按照式（６）、式（７）进行变异操作，溢出时作回归处
理，保存新种群个体为ｐｏｐ’，并计算２个目标适应度值。
Ｓｔｅｐ４ ｄｉｓ（ａ，６）表示个体ａ与ｂ间的距离；ＰＯＰｉ表示种群
ｐｏｐ第ｉ个个体。执行下面操作更新个体：
ｂｅｇｉｎ ｉｆ ｄｉｓ（ｐｏｐｉ，ｐｏｐｉ’）＋ｄｉｓ（ｐｏｐｊ，ｐｏｐｊ’）≤ ｄｉｓ（ｐｏｐｌ，ｐｏｐｊ’）＋ｄｉｓ（ｐｏｐｊ，ｐｏｐｌ’）ｔｈｅｎ ｉｆ ｐｏｐｉ．＜ｐｏｐｌ’ｔｈｅｎ ｐｏｐｉ＝ｐｏｐｉ’ｅｎｄ ｉｆ
ｉｆ ｐｏｐｊ＿＜ｐｏｐｊ’ｔｈｅｎ ｐｏｐｊ＝ｐｏｐｊ’ｅｎｄ ｉｆ
ｅｌｓｅ ｉｆ ｐｏｐｉ ｐｏｐｊ’ｔｈｅｎ ｐｏｐ￣＝ｐｏｐｉ’ｅｎｄ ｉｆ
ｉｆ ｐｏｐｊ．＜ｐｏｐｉ’ｔｈｅｎ ｐｏｐｊ＝ｐｏｐｉ’ｅｎｄ ｉｆ ｅｎｄ ｉｆ ． ｅｎｄ Ｓｔｅｐ５执行３．３节算法分群局部搜索操作。
Ｓｔｅｐ６满足迭代条件则输出，否则，返回Ｓｔｅｐ２。
４实验结果与分析
本文使用１３个标准测试函数检验本文算法，这些测试
问题对于ＣＯＰｓ有广泛的代表性Ｈ］。
为了验证算法的有效性，将本文算法与文献【４】所述的基
于随机排序的约束进化策略（ＲＹ）、文献［５】所述的一种用于约
束优化问题的多目标混合进化算法等在解决上述约束问题时
的性能进行了比较。
算法的运行参数如下：群体个数ｍ＝２５２，对每个测试问
题在相同条件下独立运行
２０次，算法适应度值评价次数均