第３Ｏ卷第４期　计算机仿真　２０１３年４月　

文章编号：１００６—９３４８（２０１３）０４—０３７３—０４　

基于Ｏｒａｃｌｅ罚方法的混合约束差分进化算法　

董明刚，程小辉，牛秦洲，叶汉民　

（桂林理工大学信息科学与工程学院，广西桂林５４１００４）　

摘要：为有效求解复杂约束优化问题，提出了一种基于Ｏｒａｃｌｅ的混合约束差分进化算法ＯＢＨＳａＤＥ。在ＯＢＨＳａＤＥ算法中，首　先对Ｏｒａｃｌｅ罚方法进行了改进，并符合约束优化问题的求解要求。利用改进后的Ｏｒａｃｌｅ罚方法来快速找到问题的可行域，　借助无约束优化算法ＳａＤＥ能对可行域进行有效搜索，利用序列二次规划的超线性的收敛速度来减少评估次数和提高解的　

质量。仿真结果表明，改进算法不仅减少了评估次数、提高了解的质量，且具有很好的鲁棒性，还具有较少的用户参数，提高　了算法的实用性。ＯＢＨＳａＤＥ是求解约束优化问题的一种具有竞争力的新方法。　关键词：约束优化；混合算法；罚函数；差分进化；序列二次规划　中图分类号：ＴＰ２０２．７　文献标识码：Ａ　

Ｏｒａｃｌｅ　Ｐｅｎａｌｔｙ　Ｍｅｔｈｏｄ——Ｂａｓｅｄ　Ｈｙｂｒｉｄ　Ｃｏｎｓｔｒａｉｎｅｄ　

Ｄｉｆｅｒｅｎｔｉａｌ　Ｅｖｏｌｕｔｉｏｎ　Ａｌｇｏｒｉｔｈｍ　

ＤＯＮＧ　Ｍｉｎｇ—ｇａｎｇ，ＣＨＥＮＧ　Ｘｉａｏ—ｈｕｉ，ＮＩＵ　Ｑｉｎ—ｚｈｏｕ，ＹＥ　Ｈａｎ—ｍｉｎ　

（Ｃｏｌｌｅｇｅ　ｏｆ　Ｉｎｆｏｒｍａｔｉｏｎ　Ｓｃｉｅｎｃｅ　ａｎｄ　Ｅｎｇｉｎｅｅｒｉｎｇ，Ｇｕｉｌｉｎ　Ｕｎｉｖｅｒｓｉｔｙ　ｏｆ　Ｔｅｃｈｎｏｌｏｇｙ，ＧｕｉＬｉｎ　Ｇａｎｇｘｉ　５４１００４，Ｃｈｉｎａ）　

ＡＢＳＴＲＡＣＴ：Ｔｏ　ｓｏｌｖｅ　ｃｏｍｐｌｅｘ　ｃｏｎｓｔｒａｉｎｅｄ　ｏｐｔｉｍｉｚａｔｉｏｎ　ｐｒｏｂｌｅｍｓ　ｅｆｆｅｃｔｉｖｅｌｙ，ａｎ　Ｏｒａｃｌｅ　ｐｅｎａｌｔｙ　ｍｅｔｈｏｄ—ｂａｓｅｄ　ｈｙ—　

ｂｒｉｄ　ｃｏｎｓｔｒａｉｎｅｄ　ｄｉｆｆｅｒｅｎｔｉａｌ　ｅｖｏｌｕｔｉｏｎ　ａｌｇｏｒｉｔｈｍ，ＯＢＨＳａＤＥ，ｗａｓ　ｐｒｏｐｏｓｅｄ．Ｉｎ　ＯＢＨＳａＤＥ，ｔｈｅ　ｏｒｉｇｉｎａｌ　Ｏｒａｃｌｅ　ｐｅｎａｌ・　

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

ｍｅｔｈｏｄ　ｃａｎ　ｆｉｎｄ　ｆｅａｓｉｂｌｅ　ａｒｅａｓ　ｑｕｉｃｋｌｙ．Ｔｈｅ　ａｄａｐｔｉｖｅ　ｄｉｆｆｅｒｅｎｔｉａｌ　ｅｖｏｌｕｔｉｏｎ　ａｌｇｏｒｉｔｈｍ　ＳａＤＥ　ｃａｎ　ｅｘｐｌｏｒｅ　ｆｅａｓｉｂｌｅ　ａｒｅａｓ　

ｅｆｆｅｃｔｉｖｅｌｙ．Ａｎｄ　ｗｉｔｈ　ｔｈｅ　ｈｅｌｐ　ｏｆ　ｓｅｑｕｅｎｔｉａｌ　ｑｕａｄｒａｔｉｃ　ｐｒｏｇｒａｍｍｉｎｇ，ｔｈｅ　ｉｍｐｒｏｖｅｄ　ｓｏｌｕｔｉｏｎｓ　ｃａｎ　ｂｅ　ｆｏｕｎｄ　ｗｉｔｈ　ｆｅｗｅｒ　

ｎｕｍｂｅｒ　ｏｆ　ｆｕｎｃｔｉｏｎ　ｅｖａｌｕａｔｉｏｎｓ．Ｓｉｍｕｌａｔｉｏｎ　ｅｘｐｅｒｉｍｅｎｔｓ　ａｎｄ　ｃｏｍｐａｒｅｄ　ｒｅｓｕｌｔｓ　ｓｈｏｗ　ｔｈａｔ　ｔｈｅ　ｐｒｏｐｏｓｅｄ　ａｐｐｒｏａｃｈ　ｎｏｔ　ｏｎ—　

ｌｙ　ｃａｎ　ｉｍｐｒｏｖｅ　ｔｈｅ　ｑｕａｌｉｔｙ　ｏｆ　ｔｈｅ　ｓｏｌｕｔｉｏｎ　ａｎｄ　ｒｅｄｕｃｅ　ｔｈｅ　ｎｕｍｂｅｒ　ｏｆ　ｆｕｎｃｔｉｏｎ　ｅｖａｌｕａｔｉｏｎｓ，ｂｕｔ　ａｌｓｏ　ｉｓ　ｒｏｂｕｓｔ．Ｉｎ　ａｄｄｉ－　

ｔｉｏｎ，ｄｕｅ　ｔｏ　ｔｈｉｓ　ｍｅｔｈｏｄ　ｈａｓ　ｆｅｗｅｒ　ｕｓｅｒ　ｐａｒａｍｅｔｅｒｓ，ｔｈｅ　ｐｒａｃｔｉｃａｌｉｔｙ　ｏｆ　ｉｔ　ｉｓ　ｅｎｈａｎｃｅｄ．Ｔｈｅ　ｐｒｏｐｏｓｅｄ　ａｐｐｒｏａｃｈ　ｉｓ　ａ　

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

ＫＥＹＷＯＲＤＳ：Ｃｏｎｓｔｒａｉｎｅｄ　ｏｐｔｉｍｉｚａｔｉｏｎ；Ｈｙｂｒｉｄ　ａｌｇｏｒｉｔｈｍ；Ｐｅｎａｌｔｙ　ｆｕｎｃｔｉｏｎ；Ｄｉｆｆｅｒｅｎｔｉａｌ　ｅｖｏｌｕｔｉｏｎ；Ｓｅｑｕｅｎｔｉａｌ　ｑｕａｄ－　

ｒａｔｉｃ　ｐｒｏｇｒａｍｍｉｎｇ　

１　引言　

Ｓｔｏｒｎ和Ｐｒｉｃｅ为求解切比雪夫多项式拟合问题时发明　

了差分进化算法（Ｄｉｆｅｒｅｎｔｉａｌ　ｅｖｏｌｕｔｉｏｎ，ＤＥ）…。与其它进化　

计算方法相比，ＤＥ执行简单，在收敛速度和搜索性能方面都　

具有一定的优势。近年ＤＥ在ＩＥＥＥ进化计算大会举办的各　

种竞赛中屡创佳绩，成为进化计算领域研究的热点之一＿２　Ｊ。　

考虑到ＤＥ在无约束优化中优异表现，已有研究者将约　

束处理技术引入ＤＥ用于求解约束优化问题　．４』，取得了较　

基金项目：国家自然科学基金项目（６１２０３１０９）；广西教育厅科研项目　（２０１２０４ＬＸ１５５）　收稿日期：２０１２—０９—２５修回日期：２０１２—１０—１５　好的效果。但就目前的研究而言，主要存在如下不足：①对　

于复杂约束，找到可行解需要很大的计算代价；②在进化的　

后期，很难快速找到一个更好的解，容易陷入局部极值；③算　

法的性能极大的依赖于参数的选择，如何选择最佳的参数仍　

是一个难题；④要提高约束ＤＥ算法的性能，需将ＤＥ算法和　

约束处理技术结合起来考虑，但现有算法往往仅关心其中某　

一方面。　

近几年，在ＤＥ的研究方面，Ｑｉｎ等人提出的自适应ＤＥ　

（Ｓｅｌｆ—ａｄａｐｔｉｖｅ　ＤＥ，ＳａＤＥ）在无约束连续优化领域表现出优　

异的寻优性能　ｊ。约束处理技术方面也取得了一些新的进　

展。最近，Ｓｃｈｌｕｔｅｒ和Ｇｅｒｄｔｓ提出了一个新的面向混合整数　优化的高效自适应约束处理方法：Ｏｒａｃｌｅ罚函数方法　ｊ。并　

－－－——３７３・－－

——　将该方法与蚁群优化方法结合用于求解混合整数非线性优　

化问题　’　，结果证明Ｏｒａｃｌｅ罚方法具有鲁棒、容易实现和控　

制的优点，在帮助蚁群优化算法发现约束问题的全局最优解　

方面具有较高的潜力。序列二次规划（Ｓｅｑｕｅｎｔｉａｌ　Ｑｕａｄｒａｔｉｃ　

Ｐｒｏｇｒａｍｍｉｎｇ，ＳＱＰ）已成为求解非线性约束优化问题的一类　

重要方法之一＿９　Ｊ。它不仅能同时处理等式和不等式约束，并　

且具有超线性的收敛速度，受到广泛关注。其主要不足在于　

需要利用函数的梯度信息，并且其性能主要依赖于初始的解　

的选择。　本文正是基于这些考虑而提出的，拟将上述几个方法有　

机融合，实现优势互补，达到对约束优化问题高效求解的目　

的。首先对Ｏｒａｃｌｅ罚方法进行了改进，并将其引入到无约束　

优化算法ＳａＤＥ中形成一种基于Ｏｒａｃｌｅ的自适应约束差分进　

化算法ＯＢＳａＤＥ（Ｏｒａｃｌｅ　ｐｅｎａｌｔｙ　ｍｅｔｈｏｄ—Ｂａｓｅｄ　ＳａＤＥ）。为加　

快ＯＢＳａＤＥ算法在进化后期的收敛速度，将ＳＱＰ方法用于对　

ＯＢＳａＤＥ的搜索结果进行进一步的搜索，形成混合差分进化　

算法（Ｏｒａｃｌｅ　ｐｅｎａｌｔｙ　ｍｅｔｈｏｄ—Ｂａｓｅｄ　Ｈｙｂｒｉｄ　ＳａＤＥ，ＯＢＨ—　

ＳａＤＥ）。利用典型测试函数验证了本文提出的方法的可行　

性和有效性。　

２相关技术介绍　

２．１面向无约束优化的ＳａＤＥ算法　

最近，Ｑｉｎ等人提出了一种面向无约束优化问题的高效　

的自适应差分进化算法ＳａＤＥ＿５］。ＳａＤＥ具体该算法将“ＤＥ／　

ｒａｎｄ／ｌ／ｂｉｎ”、“ＤＥ／ｒａｎｄ—ｔｏ—ｂｅｓｔ／２／ｂｉｎ”、“ＤＥ／ｒａｎｄ／２／ｂｉｎ’’　

和“ＤＥ／ｃｕｒｒｅｎｔ—ｔｏ—ｒａｎｄ／１”四种尝试向量产生策略用于构　

造向量产生策略池。对于当前种群中的每一个目标向量按　

照从前期学习周期内获得的改进解的成功率学习得到的概　

率从四种向量策略中进行选择。选中的策略随后用于产生　

相应的尝试向量。在前期学习周期内获得改进向量成功率　

越高的策略，被选择的概率越大。除向量产生策略以外，ＤＥ　

的两个关键控制参数：缩放因子Ｆ和交叉概率ｃ　也采用了　

类似的自适应调整方法。有关ＳａＤＥ的更多信息参见文献　

［５］。　

２．２面向混合整数优化的Ｏｒａｃｌｅ罚方法　

Ｏｒａｃｌｅ罚函数方法属于一类自适应罚函数方法　ｊ，这种　

方法的主要思想是将目标函数转换成一个附加的等式约束　

ｇｏ（；）＝＿厂（　）一ｎ＝０，参数Ｑ称为Ｏｒａｃｌｅ。在新的描述中，目　

标函数是多余的，可以声明成一个恒等于０的函数　）　Ｏ。　

新的约束优化问题可表示成如下的形式：　

ｍｉ　）　０　

Ｓｕｂｊｅｃｔ　ｔｏ：　

ｇｏ（　）＝，（　）一Ｑ＝０　（Ｉ）　

．ｇｊ（　）＝０，　＝１，２，…，ｍ　

ｇｉ（　）≥０，　＝ｍ　＋１，…，ｍ　其中ｍｅ和ｍ分别为等式约束和不等式约束的个数。在这　

．．．——３７４　．．——　种新的描述下，罚函数中的目标函数和罚函数的剩余函数可　

以自适应的调整。罚函数ｐ（　）可以定义成如下形式：　如果，（；）＞ｎ或ｒｅｓ（ｋ）＞０，　

ｐ（ｋ）＝　・Ｉ＿厂（未）一ｎ　Ｉ＋（１一　）・ｒｅｓ（ｘ）　（２）　

否则　

Ｐ（　）＝一Ｉ，（　）一ｎ　Ｉ　（３）　其中＿厂（　）是目标函数，Ｑ是Ｏｒａｃｌｅ参数，　是自适应系数，　ｒｅｓ（￣）是剩余函数，具体定义参见文献［４］。　

２．３序列二次规划方法ＳＱＰ　

ＳＱＰ方法最早由Ｗｉｌｓｏｎ于１９６３年在其博士论文中首次　提出隅］，特别适用于非线性约束规划问题．其基本思路是用　

一系列的线性规划或二次规划来逐次逼近原非线性规划问　

题。对于具有约束的非线性优化问题，ＳＱＰ算法构成如下形　

式的二次规划子问题：　

ｍｉｎ　１　ｄ　ｄ＋　）　ｄ　

Ｖｇ　（　）　ｄ＋ｇｌ（　）＝０，ｉ＝１，…，ｍ　（４）　

ｇ　（　）　ｄ＋ｇｆ（　）≤０，ｉ＝ｍ　＋１，…，ｍ　

其中，ｍ　为等式约束的数目，　为第ｋ次迭代的近似解，矩　

阵　是拉格朗日Ｈｅｓｓ矩阵的拟牛顿近似矩阵，常用的更新　

公式为：　

＋　一　Ｔ　Ｔ　＋ｌ＝　＋　一　（５）　ｑ　５ｋＮｋ￥ｋ　通过求解二次规划问题（４），可以得到一个矢量ｄ　，该　

矢量形成　的迭代公式：　

＋ｌ：　＋　ｄ　（６）　ＳＱＰ算法通过不断迭代式（５）从而逼近优化问题的最优　

解。式（６）中的　为步长参数。　

３提出的算法　

３．１　Ｏｒａｃｌｅ罚方法的改进　

根据进化计算国际会议上关于ＣＯＰｓ的通标准　Ｊ，解　

认为是可行的，如果Ｉ＾Ｊ（　）Ｉ一　≤０，　＝ｌ，２，…ｍ　，并且　

（　）≤Ｏ，　＝ｍ　＋１，…，ｍ，这里ｈ（ｘ）为等式约束，ｓ为等式约　

束的违反容忍值，推荐采用０．０００１。Ｏｒａｃｌｅ罚函数采用了不　

同于通常ＣＯＰｓ的模型描述方式和约束违反容忍标准。在　

Ｏｒａｃｌｅ罚函数中，对所有约束，包括等式与不等式，都允许约　

束违反容忍。然而在进化计算会议标准中约束违反容忍仅　

应用于等式约束。此外，在Ｏｒａｃｌｅ罚函数方法中要求所有约　

束毋（　）≥０而在通常的ＣＯＰｓ描述中要求ｇ　（　）≤Ｏ。因此，　

当用其来对ＣＯＰｓ进行约束处理，Ｏｒａｃｌｅ罚函数方法必须要　

进行修改。　这里，定义了新的约束函数ｇ　（ｉ），表示方法如下：　

）：ｆ　－Ｉ　¨．　一　（７）　

Ｌ　一岛　Ｊ　Ｊ　ｍ　十ｌ，…＇ｍ　定理１：如果　是约束优化问题的一个可行解，那么ｇ　，　

（　）１＞０√＝１，２，…ｍ．