基于工作集择优保留策略算法

葛 华，王传安，赵 靖，李香云

（安徽科技学院理学院，安徽 滁州233100）

1 引 言

工作集[1]是虚拟内存管理中频繁被访问的页面（元素）集合，是在某中条件下的局部优化的集合。工作集是对处于工作状态元素进行分组，提高工作效率。当访问的元素不在当前工作集中，就将该元素换入工作集中。

Srinivas、Deb等提出NSGA[2]，按照个体元素分类分层次排序法结合个体元素适应度的不同进行优化。随后Deb等人提出NSGA－II[3]改进算法，该算法在快速找到Pareto前沿和保持种群多样性方面都有很好的效果。Zitzler提出Pareto演化算法[4]（SPEA），依据群体中个体元素Pareto强度值排序，利用外部存档技术实现保留最优解寻求最优解。

本文提出基于工作集择优保留策略算法（better element retained algorithm based on the working set，BERAW），将工作集中的个体元素根据问题求解中个体元素的贡献度大小划分优个体、良个体、劣个体，采用保留优个体，淘汰劣个体，优化良个体方法生成新的工作集，这样可以达到快速收敛的效果。

2 择优保留策略工作集算法

2.1 工作集定义

设工作集的尺度为d，则可定义工作集为W｛X1，X2，…，Xd｝，如果d为值固定不变称为静态尺度工作集，否则为动态尺度工作集。

假设W1，W2，W3为W的三个子工作集，且满足如式（1）和（2），则称其为工作集W的真划分：

则可假设W1、W2、W3三个子工作集的尺度为d1、d2、d3。

2.2 工作集的划分系数

若将工作工作集 W真划分为三个工作集W1，W2，W3。定义工作集三个的真划分系数分别为ε1，ε2，ε3，则有2.3 工作集元素贡献度

贡献度（contribution）是在问题优化求解中个体元素的贡献的程度大小。在工作集W（X1，X2，…，Xd）中元素Xi的贡献度定义如式（5）。

其中i∈｛1，2，…，d｝，fxi→W表示元素Xi在工作集问题求解中向贡献度的一个映射。

2.4 良、劣个体元素置换

在工作集中良个体元素较为接近最优解，劣个体元素离最优解较远，它们都需要置换，其置换分别如式（6）和（7）所示。

分别是置换后后的良个体和劣个体。

2.5 工作集择优保留策略算法流程

假设工作集尺度为d，用f：S→R＋表示适应度函数，本算法流程如下：

Step1初始工作集W（X1，X2，…，Xd）

其中i∈｛1，2，…，d｝，Xmin，Xmax分别是工作集中元素的初始最小、最大值。计算工作集初始适应度函数f，并分别计算工作集各元素的初始贡献度Ci，i∈ ｛1，2，…，d｝。

Step2根据个体元素贡献度的大小和划分系数ε1，ε2，ε3，将工作集中元素划分为三类，优个体、良个体、劣个体。

Step3置换良个体元素和劣个体元素。

Step4重新计算工作集的适应度函数f和工作集中各个元素的贡献度Ci。

Step5如果满足停止规则，则停止计算并输出最优适应值及相应的参数W（X1，X2，…，Xd），否则转向步骤Step2。

3 实验结果与分析

3.1 测试函数

采用4个经典的测试函数（sphere，rosenbrock，griewank，rastrigin）对本算法对求函数极值的寻优性能进行测试，4个函数分别如式（9－12）所示。

3.2 仿真实验结果及分析

实验仿真环境为Intel（R）Pentium（R）Dual E2140 2G内存、1.6GHz主频、WinXP，采用C语言编程实现实验仿真。

由式（9－12）中4个测试函数的极小值全部为0，其中f2收敛最难且其极小值求解难度较大[5]。设d等于100，工作集元素的取值范围即搜索空 间 为（100，100），ε1，ε2，ε3分 别 取0.236，0.618，0.146，迭代最大次数为2500，算法结束条件为计算误差esp小于或等于1e－7，良个体与劣个体置换原则为分别取优个体与劣个体中相邻两个体元素之间的平均值。

采用工作集择优保留策略算法进行仿真实验的数据如表1所示，可以看出rosenbrock函数较难收敛迭代次数达49次最多，时间花费也最多，griewank函数收敛速度较快仅迭代27次，极小值最大的为9.45×10－8也非常小且与理论值非常接近，由此可见，对于多维函数极小值求解，工作集择优保留策略算法并具有良好的全局收敛性能。

表1 4个标准测试函数

表2是ABC[5]与本算法进行比较结果，可以看出ABC算法在rosenbrock和rastrigin函数的极值求解中结果与理论极值偏差较大，而本算法求解4个函数的更加接近极小值。

从表2还可以看出ABC算法在求解不是很复杂度的问题时可以取得较好近似解，而在求解较为复杂的问题基本得不到满意解。本文提出的BERAW算法都可以收敛到理论最优近似解，并且算法较为稳定。

从图1、2、3、4中可以看出，4个测试函数在10次迭代以后曲线基本呈水平状态，说明采用本算法在测试函数极值求解过程中迭代10次以后就非常接近函数极值。

表2 与ABC算法极小值比较

图1 sphere函数迭代曲线

图2 rosenbrock函数迭代曲线

图3 griwank函数迭代曲线

图4 rastrigin函数迭代曲线

4 结束语

本文提出工作集择优保留策略算法是根据工作集中个体元素对问题求解的贡献度不同而对工作集进行真划分，并对不同真划分进行局部优化，保留真划分中的优个体，其余工作集个体进行改良，直至求得近似最优解。

与其他的算法相比，该算法在寻找最优解具有精度准、速度快等特点。只需要较少次数的迭代就能接近最优解，经实验仿真证实BERAW不仅具有较强的寻优能力，而且精度很高。由此可见，本文提出的BERAW在解决函数优化类问题上优势明显，今后将重点研究工作择优保留策略和其他群体智能算法结合解决群体智能优化问题。

[1]Stallings W.Operating systems：internals and design principles（5thed.）[M].New York：Prentice Hall International Inc，2005.

[2]Sriivas N，Nafpliotis N.Multiobjective optimization using nodminated sorting in genetic algorithms[J].Evol Comp，1994，2（03）：221－248.

[3]Deb K，Agrawal S，Pratap A，et al.A fast elitist nondominated sorting genetic algorithm for muti－object optimization：NSGA－II[A].In M.S.etal.（Ed.），Parallel Problem Solving from Nature－PPSNV[C].Berlin：Springer，2000.

[4]Zitzler E，Thiele L.Muliobjective evolutionary algorithms：a comparative case study and the strength pareto approach[J].IEEE Transact Evol Comp，1999，3（04）：257－271.

[5]段海滨，张祥银，徐春芳，等.仿生智能计算 [M].北京：科学出版社，2011：7－58.