一种保证全局收敛的认知优化算法

王春梅,　孙家泽

(西安邮电大学 计算机学院,陕西 西安　710121)

一种保证全局收敛的认知优化算法

王春梅,孙家泽

(西安邮电大学 计算机学院,陕西 西安710121)

摘要:文章针对传统社会认知优化算法全局收敛慢的问题,提出了一种保证全局收敛的认知优化算法。该算法应用Tent 映射初始化知识库,提高初始解的质量;邻域搜索过程采用混沌搜索,增强算法跳出局部最优解的能力;通过增加混沌库来提高搜索的遍历性,实现和知识库协同寻优,从而构建为一种新的混沌混合认知优化算法；同时以Solis和Wets提出的随机算法收敛定理为基础，给出了该算法的全局收敛性证明。标准测试函数的仿真优化结果表明,该混合算法对非线性规划问题具有较强的求解能力,算法寻优效率高、全局性能好、优化结果稳定,性能明显优于标准认知优化算法。

关键词:社会认知算法;混沌优化;Tent映射;全局收敛;非线性规划问题

0引言

非线性规划是具有非线性约束条件或目标函数的数学规划,是运筹学的一个重要分支,非线性规划在工程、管理、经济、科研、军事等方面都有广泛的应用,为最优设计提供了有力的工具。一般来说,约束非线性规划问题可以表示为:

minf(x)，

(1)

其中,x=[x1…xq…xn]，1≤q≤n,xq∈[lq,uq],lq和uq分别为定义域的下界和上界;S为定义空间,SF为满足所有约束的可行空间,SF⊆S;f(x)为最小化目标函数。由于f(x)和g(x)往往是非线性、不可微、不连续的,并且此问题是NP-hard[1]问题,传统的确定性算法解决此类约束优化问题非常困难,因此寻找求解该问题的有效方法是科学技术和工程应用中的一个重要课题。

社会认知理论研究表明,社会学习比生物或昆虫系统的进化要智能得多。文献[2]基于社会认知理论提出了社会认知优化算法(social cognitive optimization algorithm,SCO),该算法比基于生物和昆虫社会的遗传算法、粒子群等优化算法的智能性和社会性更高。学习个体充分利用社会群体的交互和共享进行模仿学习和观察学习来进化迭代,因此该算法具有较强的收敛速度,适合于大规模的约束问题的处理[3],该算法对于解决多峰、非连通甚至难以建立数学模型的优化问题都有着很好的效果,并在调度、设计、控制等实际问题上得到应用[4],该算法的收敛速度快、稳定性好并且与初始值无关,是一个值得进一步深入研究的智能算法。

文献[5]提出了无免费午餐定理(no free lunch theorem,NFL)。该定理指出没有一种算法对任何问题都是最优的,不同的算法都有其不同的应用优势与不足,算法之间存在着互补性。SCO 也不例外,它的算法简单、快速,是一种很好的问题求解模式,但是缺乏有效的局部搜索机制。因此,从解决实际问题角度出发,融合不同类型机制的优化算法,充分发挥它们各自的优势,构造混合优化算法,是拓宽算法适用范围和提高算法性能的有效手段。

为此,一些研究者对SCO算法进行了改进研究。文献[6]用SCO融合自组织迁移算法,通过2个参数来协调2个算法优化的过程;文献[7]针对电力系统无功优化问题,提出了基于农夫捕鱼算法的社会认知算法;文献[8]对SCO算法进行改进,并融合到文化算法的过程中,构造了一种文化社会认知优化算法,并解决QoS感知的云服务组合优化问题;文献[9]提出用离散自然认知优化算法解决三维碎片的全局匹配问题。

本文基于算法混合的思想,在认知优化算法中引入基于Tent映射的混沌搜索机制,增加个体的多样性,增强算法的全局和局部寻优能力,从而构建一种新的认知优化算法——混沌认知优化算法TSCO；同时以Solis和Wets提出的随机算法收敛定理[10]为基础，给出了该算法的全局收敛性证明。标准测试函数的优化试验结果表明,混沌认知优化算法寻优效率高、收敛速度快,明显优于基本认知优化算法。

1混沌优化算法

混沌是自然界广泛存在的一种非线性现象,具有随机性、遍历性和对初始条件的极度敏感性等特点,在一定范围内能够按其自身的规律不重复地遍历所有状态。混沌策略经常应用在优化领域,以提高寻优速度。

基于混沌的优化理论,主要是利用混沌序列的遍历性、随机性、规律性来搜索寻找问题的最优解。混沌序列的产生有很多种方法[11],文献[12]研究表明基于Tent映射的混沌序列的迭代速度优于基于Logistic映射的混沌序列,并且具有全局遍历性,初始值敏感性不强,迭代过程适合于计算机运行,该方法已经在一些领域成功应用[13]。一维Tent映射函数经过贝努利变换后可表示为:

(2)

即

xk+1=2xkmod1

(3)

对于[0,1]之间的浮点数,在计算机进行Tent映射时,实际是将小数部分的二进制数进行无符号左移。这种运算特点充分利用了计算机的特性,因此Tent映射的迭代速度要快于Logistic 映射。但是由于计算机字长有限,小数部分的二进制序列经过一定次数的无符号左移运算将趋向全0,即趋向Tent映射的不动点。并且迭代序列中存在小周期,例如4周期(0.2,0.4,0.6,0.8);还存在不稳周期点,例如(0,0.25,0.50,0.75,1.00)都将迭代到不动点0。

基于Tent映射的区间(Vmin,Vmax)中混沌序列产生的步骤如下:

(1) 取初值x0(x0应避免落入小周期点内)。

(2) 以(3)式进行迭代,迭代M(一般取300)次,产生区间(0,1)中的混沌点xM,在迭代过程中,如果xi={0,0.25,0.50,0.75,1.00}或者xi=xi-k，k={1,2,3,4},这时让xi=xi-1+ε来避免落入小周期和不稳定点。

(3) 根据(4)式计算混沌值,Vmax为区间上界,Vmin为区间下界。

(4)

2基于Tent映射的混沌认知优化算法

2.1改进策略

SCO算法的迭代策略是根据社会认知理论中人类的学习过程来进行的,传统SCO算法主要考虑的是大多数人群的学习模式。为了提高算法的遍历性,本文算法进一步考虑遍历性和随机性强的混沌搜索策略,引入混沌搜索库和传统的知识库同步迭代,协同更新。混沌库采用基于Tent映射的混沌搜索策略来避免迭代过程的早熟,同时在局部搜索操作中使用混沌搜索来提高局部搜索的效率,同时初始化采用混沌映射来产生初始位置。

2.2混沌社会认知算法的基本概念

(1) 知识点。知识点是位于知识空间(例如搜索空间)中对位置x水平(例如适应值函数值)的描述构成的点。

(2) 知识库。知识库是一系列知识点的集合,这个集合是有固定大小的。

(3) 学习代理。学习代理是一个学习行为个体,支配库中的一个知识点,通过学习代理个体的学习来更新知识库。

(4) 领域搜索。2个点x1和x2,对x2的领域搜索就是以x1作为参考点选出一个新的点x′。

(5) 混沌搜索。即按照Tent映射产生的混沌序列来构造新的点。

整个优化过程通过一系列学习代理的多次迭代来完成,其原理如图1所示。

图1　混沌社会认知优化原理图

2.3基于混沌策略的认知优化算法步骤

假设知识库中知识点的个数是Npop,混沌库中知识点个数是Ntent,学习代理的数量是Nc,混沌认知优化算法流程图如图2所示,算法具体步骤如下:

(1) 初始化过程。① 在知识库中按Tent映射生成(Npop+Ntent)个知识点,并计算其适应值;② 给每个学习代理随机分配库中的一个知识点,但不允许把一个知识点重复分配给多个学习代理。

(3) 库更新过程。从知识库中移去Nc个具有最差水平的知识点,用本次迭代学习中(包括混沌库中点)最好的Nc个体。

(4) 重复步骤(2)～步骤(4),直到满足停止条件(例如达到预先确定的迭代次数,或者结果达到预先设定的精度)。

社会认知优化的参数包括Npop、Ntent、Nc和T，其中T为学习循环的循环次数。那么函数总的运行次数为:

图2　混沌认知优化算法流程图

2.4TSCO算法的全局收敛性

从上述算法的过程可以看到,TSCO算法是一种典型的随机类优化算法,Solis和Wets给出了随机算法全局收敛的充要条件[10],其主要内容如下。

假设1f(D(z,ξ))≤f(z),且如果ξ∈S,则f(D(z,ξ))≤f(ξ)。

假设2假设S存在任意Borel子集A,如果它的测度满足条件v(A)>0,v(A)是A的闭包,那么有:

(5)

其中,μk(A)为由测度μk所得到的A的概率。

(6)

其中,P[zk∈Rε]为第k步算法生成的解zk∈Rε的概率;Rε为全局最优点集合。

下面分析TSCO算法是否满足上述假设。

定理2TSCO算法满足假设1。

对函数D进行定义:

(7)

其中,pgk为第k步的全局最优点;g(xik)为第k步的第i个代理的更新;xik为第k代时的粒子i的位置。本算法保留了学习过程中的最优解,从中容易看出,按照函数D的定义,TSCO算法满足假设1。

定理3TSCO算法满足假设2。

对于规模为N=Ntent+Nc的群体,如果假设2成立,即证明TSCO算法满足(8)式:

(8)

其中,Mi,k为在算法第k代时点i的支撑集。

定理4TSCO算法以概率1全局收敛于全局最优解。

由定理2和定理3可知,TSCO算法满足假设1和假设2,由定理1可知TSCO算法以概率1全局收敛于全局最优解。

2.5求解非线性规划问题

应用混沌认知优化算法求解非线性规划问题时,以目标函数作为知识点的适应度评价函数,且函数值越小表示该知识点的水平越好。在处理约束问题时,违约处理是一个重要问题,在群体智能算法中对于一个点违背约束处理常用策略如(9)式所示,即

(9)

对约束的处理规则为:① 任何可行空间中的点优于非可行空间中的点;② 可行空间中的2个点适应值越小越好;③ 非可行空间中的2个点违约值越小越好。

3数值试验与仿真

为了测试本文提出的混沌认知优化算法(TSCO)求解带约束的非线性规划问题的性能,同时为使测试结果具有可比性,本文以文献[2]中经典的4个基准非线性规划问题为测试对象,4个基准问题如下所述。

(1)G1。

minG1(x)=5x1+5x2+5x3+5x4-

定义域:

0≤xi≤100,i=10,11,12;

最优值：G1(x*)=-15。

(2)G2。

0≤xi≤10,1≤i≤n。

最优值：G2(x*)=0.803 553。

(3)G3。

105-4x1-5x2+3x7-9x8≥0,

-10x1+8x2+17x7-2x8≥0,

8x1-2x2-5x9+2x10+12≥0,

3x1-6x2-12(x9-8)2+7x10≥0,

定义域:-10.0≤xi≤10.0,i=1,…,10。

最优值:G3(x*)=24.306 209 1。

(4)G4。

minG4(x)=x1+x2+x3;

s.t.

1-0.002 5(x4+x6)≥0,

1-0.002 5(x5+x7-x4)≥0,

1-0.01(x8-x5)≥0,

x1x6-833.332 52x4-100x1+83 333.333≥0，

定义域:

100≤x1≤10 000；1 000≤xi≤10 000,i=2,3；

100≤xi≤10000,i=4,…,8。

最优值:G4(x*)=7 049.330 923。

本文在4个问题下对社会认知优化算法(SCO)和基于Tent映射的混沌社会认知优化算法(TSCO)性能进行对比测试。

在标准社会认知优化算法和改进的社会认知优化算法中,设定库中知识点个数Npop=95,Ntent=5,学习代理个数Nc=15,循环学习次数T=2 000,每个问题执行50次。计算其最好结果、最差结果和平均结果来比较改进后的算法和传统认知优化算法的性能。

社会认知优化算法和改进的社会认知优化算法独立运行50次,在目标函数平均值、最差结果、最好结果方面的对比见表1所列。

从表1的试验结果可以看出,与传统的社会认知算法SOC相比,4个问题TSCO的平均值和最好值与问题的最优值更接近,解的精度更高,这说明TSCO算法在求解非线性规划问题中的效率更高、稳定性更好。

2种算法在50次求解过程的平均目标函数f(x)与该问题最优值差的绝对值Fnorm和迭代次数的对数曲线如图3所示。图3中总的迭代次数为2 000次,为了图示的清晰,选取了100的整数倍次(t/100)的优化值。由图3可以看出,该算法与传统社会认知算法相比收敛速度较快,随着学习次数的增加,目标函数减小更快。

表1　TSCO算法运行结果

图3　迭代过程适应值变化对比图

4结束语

本文提出了一个求解非线性规划问题的、基于Tent映射的混沌社会认知优化算法,给出了该算法的全局收敛性证明。标准测试函数的仿真优化结果表明,本文算法收敛速度快、寻优效率高、全局性能好、优化结果稳定,性能明显优于标准认知优化算法,为求解非线性规划问题提供了一种新的有效算法。

[参考文献]

[1]Wang T.Global optimization for constrained nonlinear programming [M].Urbana:Illinois University Press,2001:8-11.

[2]Xie X F,Zhang W J,Yang Z L.Social cognitive optimization for nonlinear programming problems[C]//International Conference on Machine Learning and Cybernetics.IEEE,2002:779-783.

[3]Xie X F,Zhang W J.Solving engineering design problems by social cognitive optimization[M]//Genetic and Evolutionary Computation-GECCO 2004.Berlin:Springer,2004:261-262.

[4]孙家泽,王曙燕,张建科,等.求解非线性互补问题的熵函数认知优化算法[J].计算机工程与应用,2010,46(21):40-42.

[5]Wolpert D H,Macready W G.No free lunch theorems for optimization[J].IEEE Transactions on Evolutionary Computation,1997,1(1):67-82.

[6]彭斌.社会认知优化改进及其应用研究 [D].南京:南京工业大学,2006.

[7]白云,徐刚刚,宋阳.基于改进社会认知算法的电力系统多目标无功优化[J].黑龙江电力,2012,34(2):120-124.

[8]刘志中,王志坚,薛霄,等.基于文化社会认知算法的云服务优化组合研究[J].计算机科学,2013,40(5):103-106,140.

[9]孙家泽,耿国华.基于群体智能的三维碎片全局最优匹配方法[J].计算机应用,2016,36(1):266-270.

[10]Solis F J,Wets J B.Minimization by random search techniques[J].Mathematics of Operations Research,1981,6(1):9-30.

[11]程志刚,张立庆,李小林,等.基于Tent映射的混沌混合粒子群优化算法[J].系统工程与电子技术,2007,29(1):103-106.

[12]Rong H.Study of adaptive chaos embedded particle swarm optimization algorithm based on Skew Tent map[C]//International Conference on Intelligent Control and Information Processing.IEEE,2010:316-321.

[13]王立宏,王曙燕,孙家泽.一种分阶段组合测试数据生成算法[J].计算机应用与软件,2013,30(3):67-70.

(责任编辑胡亚敏)

A social congitive optimization algorithm for guaranteeing global convergence

WANG Chun-mei,SUN Jia-ze

(School of Computer Science and Technology, Xi’'an University of Posts and Telecommunications, Xi’an 710121, China)

Abstract:To improve the global convergence speed of classical social cognitive optimization(SCO) algorithm, a guaranteed global convergence SCO based on Tent map(TSCO) is proposed. In the proposed algorithm, Tent map is used to initialize the knowledge libraries to improve the quality of the initial solution; neighborhood search by using chaotic search method enhances the algorithm’s ability for escaping from the local optimal solution; chaotic libraries improve the ergodicity of the search and achieve the collaborative optimization with knowledge libraries. So a new chaotic hybrid SCO is constructed. And the global convergence proof is made based on the convergence theorem in Solis and Wets’ stochastic algorithm. The results of simulated optimization in standard test functions show that the algorithm has a strong ability to solve the nonlinear programming problems. The algorithm has high searching efficiency, good global performance and stable optimized result, which is significantly better than standard cognitive optimization algorithms in performance.

Key words:social cognitive optimization(SCO); chaotic optimization; Tent map; global convergence; nonlinear programming problem

收稿日期：2015-07-01；修回日期：2016-02-17

基金项目：陕西省自然科学基金资助项目(2015JM6359);陕西省工业科技攻关资助项目(2016JY-086);陕西省教育厅自然科学基金资助项目(15JK1672;15JK1678)和西安市科技计划资助项目(CXY1516 (4))

作者简介：王春梅(1979-),女,甘肃兰州人,西安邮电大学讲师.

doi:10.3969/j.issn.1003-5060.2016.05.013

中图分类号:TP18

文献标识码：A

文章编号：1003-5060(2016)05-0636-06