收稿日期：2012-05-29；修回日期：2012-07-03
基金项目：广西自然科学基金资助项目（0832084）；广西高等学校科研资助项目
（201202ZD032）；广西混杂计算与集成电路设计分析重点实验室资助项目
作者简介：李景洋（1989-），女，硕士研究生，主要研究方向为计算智能；王勇（1963-），男（通信作者），教授，博士，主要研究方向为计算智能、数据挖掘（wangygxnn@sina．com ）；路闯（1985-），男，硕士研究生，主要研究方向为数据挖掘、计算智能．
具有认知能力的捕鱼策略优化算法
*
李景洋，王
勇，路闯
（广西民族大学信息科学与工程学院，南宁530006）
摘
要：针对捕鱼策略优化方法在处理复杂优化问题时易陷入局部极值，且后期收敛速度慢的缺陷，根据现实
中渔夫的捕鱼习惯，将渔夫的认知能力应用到基本FSOA 中，提出了一种改进的具有认知能力的捕鱼策略优化方法（CAFSOA ）。该算法中的渔夫可根据其前期捕鱼经验和当前体状况来判断何处鱼的浓度比较高。实验结果表明，该优化方法具有较快的收敛速度和较好的优化精度，能有效地避免早熟收敛问题。关键词：捕鱼策略优化方法；具有认知能力的捕鱼策略优化方法；认知能力；优化中图分类号：TP18；TP301.6
文献标志码：A
文章编号：1001-3695（2013）01-0124-03
doi ：10．3969/j．issn．1001-3695．2013．01．030
FSOA with cognitive ability
LI Jing-yang ，WANG Yong ，LU Chuang
（College of Information Science ＆Engineering ，Guangxi University for Nationalities ，Nanning 530006，China ）
Abstract ：In order to overcome the shortcoming of standard FSOA that was easily trapped in local optimum and had a low con-vergence rate in the late period ，according to the fishing habit of fishers ，this paper applied the fishers ’cognitive ability in FSOA ，and put forward an improving FSOA with cognitive ability．In this optimization algorithm ，every fisher could estimate ，according to his fishing experience and the state the group were being in ，where was relatively thick with fish in comparison with the area around him．The experiment results show that this optimization algorithm has the great advantages of a rapid con-vergence rate and a high accurate numerical solution over standard FSOA ，and can effectively avoid being trapped into local optimum．
Key words ：FSOA ；CAFSOA ；cognitive ability ；optimization
近年来，演化计算等基于自然法则的随机搜索算法的研究越来越受到人们的重视。自20世纪60年代Holland
［1］
提出遗
传算法（GA ）以来，该领域的研究取得了较大的进展
［1 13］
。1995年，Kennedy 等人提出了粒子优化算法（PSO ）［2］。1996年，Dorigo 等人［6］
提出了蚁算法（ACA ）。2002年，李晓磊等
人
［8］
提出了人工鱼算法（AFSA ）。这些随机搜索算法为解
决工程技术等方面的复杂优化问题提供了新的契机。
最近，文献［11］则根据渔夫捕鱼行为习惯，提出了一种采用捕鱼策略的优化方法（FSOA ）。该算法具有原理简单、设置参数少、易于编码实现等优点，但是该算法却存在搜索效率不高、易陷入局部极值的缺陷。针对基本FSOA 存在的缺陷，文献［14 17］从不同的角度对FSOA 进行了改进。文献［14］采用动态策略的模拟捕鱼优化算法，文献［15］提出将FSOA 与PSO 相结合的优化算法，文献［16］提出采用正交变换确定探测点的改进方法，文献［17］提出采用随机动态选择探测点的改进方法。这些改进方法增强了算法搜索跳出局部最优解的能力，在很大程度上提高了算法的搜索效率，但仍然没能从根本上避免该算法在搜索过程中陷入局部极值的情况发生。
针对基本FSOA 存在的不足，本文将人类智能与渔夫捕鱼习惯相结合，提出一种具有认知能力的捕鱼策略优化方法（FSOA with cognitive ability ，CAFSOA ）。该算法中的渔夫可根
据其前期捕鱼经验和当前体状况来判断何处鱼的浓度比较高。为了测试本文算法的性能，选取了几个典型的优化问题进行算法优化性能实验。实验结果表明，该改进算法具有较好的优化性能，可有效地避免早熟收敛问题。
1基本FSOA 介绍
在基本FSOA 中，渔夫采用移动搜索与收缩搜索相结合的
搜索策略，以方体格式确定探测点。具体方法如下（以求最大值为例）：
设D 中随机分布有k 个渔夫。i 渔夫在t 时刻的位置为X
i
（t ）=［x i
1（t ），…，x i n （t ）］（将下鱼网点抽象为无体积的点，用以表征问题的候选解）。i 渔夫在点X i
（t ）的四周按方体格式下鱼网，得到以X i
（t ）为中心的下鱼网点集为
Ω（X i （t ））=｛X i （t +1）=［
x i
1（t +1），…，x i n （t +1）］|x i j （t +1）∈｛x i j （t ）－l （
－），x i j （t ），x i j （t ）+l （
+）
｝，j =1，2，…，n ｝
其中：x i
j （t ）∈D j ，
l （－）
和l
（
+）
均为大于0的数。若x i j （t ）－l
（
－）
≤a j ，则令x i j （t ）－l
（
－）
=a j ；若x i j （t ）+l （+）
≥b j ，则令x i
j （t ）+
l （
+）
=b j （j =1，…，n ）。1）移动搜索
若f （X i （t +1））满足公式f （X i
（t +1））=
max X i （t +1）∈Ω（X i （t ））
f （X i （t +1））＞f （X i （t ）），则i 渔夫将从X i
（t ）移到
第30卷第1期2013年1月计算机应用研究
Application Research of Computers Vol.30No.1Jan．2013
X i（t+1）进行状态更新，并在点X i（t+1）处继续按前面的方法开展寻优活动，以期搜寻到比点X i（t+1）更优的点X i（t+2）。按这样的方法展开搜索，称之为移动搜索。
2）收缩搜索若f（X i（t+1））满足公式f（X i（t+1））= max
X i（t+1）∈Ω（X i（t））
f（X i（t+1））≤f（X i（t）），则i渔夫暂时不进行状态更新（即不移动），并记X i（t+1）=X i（t）。然后仍然在X i （t）处按方体格式下鱼网得到下网点集为
Ω（X i（t+1））=｛X i（t+2）=［x i1（t+2），…，x i n（t+2）］|x i j（t+2）∈｛x i j（t+1）－αl（－），x i j（t+1），x i j（t+1）+αl（+）｝，j=1，2，…，n｝
其中，α（0＜α＜1）称为收缩因子。然后按前面的方法来确定Ω（X i（t+1））中是否有比X i（t+1）更优的点。按这样的方法展开搜索，称之为收缩搜索。
说明：a）算法设有公告板，公告板是记录最优渔夫个体状态的地方，每个渔夫将自己当前状态与公告板中记录进行比较，若优于公告板中的记录，则用自身状态更新公告板中的记录，否则公告板的记录不变；b）算法设在有同一点处可进行收缩搜索次数的最大阈值。若某渔夫在某点处进行收缩搜索次数达到了最大阈值，但其状态仍未发生改变，则该渔夫要在打渔作业区中重新随机选点。
2具有认知能力的改进FSOA
本文提出的改进FSOA主要采用以下策略：a）渔夫利用自身的判断力和推理能力，根据体到的鱼浓度最高位置和自己之前的捕鱼经验来推测哪个区域鱼的浓度可能会比较高；b）渔夫若发现某处鱼的浓度是当前最高的，则采用逐渐向该处靠近的搜索方法；c）不再采用收缩搜索策略。具体方法描述如下：
设至第t步，体到的最优位置为G（t）=（g1（t），…，g n
（t）），且至第t步，渔夫到的最优点为B i（t）=（b i
1（t），…，b i
n
（t）），i渔夫在t时刻位于X i（t）=（x i
1（t），…，x i
n
（t））。
情况1若X i（t）≠G（t），则渔夫i将按式（1）随机选取N 个探测点：
P i j（t+1）=X i（t）+r j l（βj·
Q j（t+1）
‖Q j（t+1）‖
+（1－βj）
G（t）－X i（t）
‖G（t）－X i（t）‖
）
（1）
其中：j=1，…，N，Q j（t+1）=［q j1（t+1），…，q j n（t+1）］，q j k（t+ 1）为［－1，1］中的均匀随机分布，r
j
和βj为［0，1］中的均匀随机分布，l为渔夫的投网半径。
情况2若X i（t）=G（t）渔夫按式（2）来确定N个探测点：
P i j（t+2）=X i（t+1）+r jˑlˑ
Q j（t+2）
‖Q j（t+2）‖
，j=1，…，N（2）
其中：Q j（t+2）=［q j1（t+2），…，q j n（t+2）］，q j k（t+2）为［－1，1］中的均匀随机分布，r
j
为（0，1）中的均匀随机分布，l为渔夫的投网半径。
记P i best（t+1）=best｛P i j（t+1）：1≤j≤N｝。
若P i best（t+1）比X i（t）好，则渔夫i将移到P i best（t+1）。此时，记X i（t+1）=P i best（t+1）。
若P i best（t+1）不如X i（t）好，则i渔夫将根据下面两种情况来确定其下一步的行为。若X i（t）=G（t），则至第t+1步，渔夫i仍逗留在位置G（t），或者说，渔夫i在第t+1步移到位置X i（t+1）=G（t）；否则渔夫按式（3）来确定X i（t+1）=（x i1（t+1），…，x i
n
（t+1））：
x i j（t+1）=x i j（t）+r1ˑ（b i j（t）－x i j（t））+r2ˑ
exp（－（
g j（t）－x i j（t）
‖G（t）－X i（t）‖
）2）（g j（t）－x i j（t））（3）算法具体步骤如下：
a）初始化：在可行域内随机生成k个渔夫，初始化各个渔夫的捕鱼经验，记录体最优渔夫所在的位置。
设定探测点个数N，算法最大迭代次数Gen等参数。
b）对体中的每个渔夫i执行如下操作：
（a）评价渔夫所在位置鱼的浓度，若渔夫处于体最优位置则执行（b），否则执行（c）。
（b）按式（2）选取N个探测点，若P i
best
（t+1）比X i（t）好，则X i（t+1）=P i best（t+1），否则X i（t+1）=G（t）。更新B i（t+ 1）。
（c）按式（1）选择N个探测点，若P i
best
（t+1）＞X i（t）则移动到P i best（t+1）处，否则按式（3）移动。更新B i（t+1）。
c）记录最优渔夫的位置G（t+1）。
d）t←t+1，判断算法是否达到终止条件，若是则转至e），否则转b）。
e）输出结果，程序结束。
3数值实验仿真
为了验证CAFSOA的有效性，选择以下六个经典的基准函数进行测试，并同基本FSOA、FPSOA［15］、RFSOA［17］等进行比较。这六个基准测试函数如下：
f1（X）=10cos（2πx1）+10cos（2πx2）－x21－x22－20
其中－5．12≤x i≤5．12。该函数为典型多峰函数，在（0，0）处取得全局极大值0。
f2（X）=（x21+x22）0.25［sin2（50（x21+x22）0.1）+1.0］
其中－100≤x i≤100。该函数在（0，0）处取得全局极小值0。
f3（X）=0.5+
sin2x21+x
槡22－0.5
［1.0+0.001（x21+x22）］2
其中－100≤x i≤100。该函数在（0，0）处取得全局极小值0。
f4（X）=
1
4000
∑
2
i=1
x2i－
2
i=1
cos（
x i
槡i
）+1
其中－600≤x i≤600。该函数在点（0，0）处取得全局极小值0。
f5（X）=∑
10
i=1
x2i，－5．12≤x i≤5．12
该函数在点（0，0，…，0）处取得全局极小值0。
f6（X）=∑
10
i=1
（x i+0.5）2，－100≤x i≤100
该函数在－0．5≤x i≤0．5区间内取得全局极小值0。
本次实验使用的计算机为AMD Phantom（TM）ⅡP820、2GB 内存的PC机，编程软件为MATLAB2010a。
参数设置如下：FSOA、RFSOA中收缩因子α=0．5，收缩次数阈值C=5。FPSOA中惯性权重ω=0．628，加速常数c1=c2= 2。以下参数设置相同：探测点数N=8，渔夫规模均为50，最大迭代次数均为100次。当算法达到全局极值点或达到最大迭代次数时，算法终止。为了避免随机性对实验结果造成的影响，每一种算法对每个函数均独立运行20次，并求平均值。实验结果如表1所示。
·
521
·
第1期李景洋，等：具有认知能力的捕鱼策略优化算法
表1
正则化匹配26个字母python实验结果
测试函数算法最优值最差值
平均值
平均迭代次数CAFSOA
6．394884621840902e －014－3．197442310920451e －01539f 1（X ）
FSOA 3．874491545730052e －005－0．009433993296597－0．002826175720966100FPSOA －6．039613253960852e －014－7．214135067101779e －008－5．069123076850701e －009100RFSOA －7．526501377697059e －008
－4．921284844527918e －006
－8．734453867731418e －007
100CAFSOA 8．2740e －0401．3279e －0236．9546e －025100f 2（X ）
FSOA 3．4476e －0082．3728e －0067．1876e －007100FPSOA 7．267268566454941e －0147．890705783984666e －0111．009318106073049e －011100RFSOA 1．697235426741108e －012
1．034144405679264e －0082．132502862544690e －009100CAFSOA 02．220446049250313e －014
3．608224830031759e －015
75f 3（X ）
FSOA 5．1263e －0050．00970．0073100FPSOA 2．8383e －0070．00970．0092100RFSOA 1．178002140278522e －012
0．0097159098878930．006801823272038100CAFSOA 0
1．6653e －0151．0547e －01682f 4（X ）
FSOA 4．120425574359876e －0040．1608374869694930．039129856567956100FPSOA 2．306055346679159e －0110．0222394763110530．005544080662932100RFSOA 1．084010659013757e －0111．061511623046130e －0082．132342885596827e －009100CAFSOA 4．921934878451077e －010
2．385445263172086e －005
3．81541286321886e －007
100f 5（X ）
FSOA 6．5992e －0060．00970．0043
100FPSOA 3．604648610741578e －0060．0017212595978534．075072506448829e －004100RFSOA 7．249296682838757e －007
6．381171673508562e －005
5．715492320157143e －006
100CAFSOA 00049f 6（X ）
FSOA 021．398FPSOA 0348．45100RFSOA
29
5933
3．51855e +003
100
由表1可见：从“最优值”评价指标上看，CAFSOA 能到函数f 1、
f 3、f 4和f 6的全局最优点，而FPSOA 、FSOA 只能到函数f 6的全局最优点。对于函数f 2，四种算法在最大次数为100次时，均未到全局最优点，但CAFSOA 的优化精度大约是FSOA 的5倍，是FPSOA 、RFSOA 的3倍。对于函数f 5，CAF-SOA 的优化精度均比FPSOA 、RFSOA 的优化精度高。从“最差值”和“平均值”评价指标上看，CAFSOA 的优化性能均优于FSOA 、FPSOA 和RFSOA 。从“平均迭代次数”评价指标上看，CAFSOA 的收敛速度均比FSOA 、FPSOA 、RFSOA 快。
为了更加清楚地对各算法的性能进行分析比较，给出了每种算法分别优化各个函数的收敛曲线，如图1 6所示。
由图1 6所示，
CAFSOA 克服了FSOA 的搜索效率不高、易陷入局部极值的缺点，表现出更快的收敛速度和更高的搜索效率，其优化性能总体上比FSOA 、
FPSOA 、RFSOA 好
。
4结束语
本文利用渔夫具有判断和推理能力的特点，提出了CAF-
SOA 。渔夫根据自身对周围环境的认知，独立选择自己的捕鱼策略。实验仿真结果表明，
CAFSOA 具有较强的搜索能力和较高的搜索效率，在收敛速度和优化精度上均比基本FSOA 及其改进算法有了较大的提高。参考文献：
［1］HOLLAND J H．Adaptation in nature and artificial systems ［M ］．［S．
l．］：MIT Press ，1992．
［2］EBERHART R C ，SHI Yu-hui ，KENNEDY J．Swarm intelligence
［M ］．San Francisco ：Morgan Kaufman Publishers ，2001．
［3］THERAULAZ G ，BONABEAU E ，DENEUBOURG J L．Self-organiza-tion of hierarchies in animal societies ：the case of the primitively eu-social wasp polistes dominulus christ ［J ］．Journal of Theoretical Bi-ology ，1995，174（3）：313-323．
［4］THERAULAZ G ，BONABEAU E ，DENEUBOURG J L．Response thresh-old reinforcement and division of labour in insect societies ［J ］．Proc of the Royal Society of London B ，1998，265（1393）：327-332．
［5］EUSUFFM M ，LANSEY K E．Optimization of water distribution net-work design using shuffled frog leaping algorithm ［
J ］．Journal of Wa-ter Resources Planning and Management ，2003，129（3）：210-225．
（下转第157页）
·
621·计算机应用研究
第30卷
示的叠加态，并将包括权重信息在内的所有简历信息随机输入
叠加态，并保存起来。现要从1024份简历中到这3人（目
标态），按照本文算法进行迭代，其目标结果分别用a 0、
a 1、a 2表示，非目标态（其他人）迭代结果用
b 表示。迭代结果如图2所示
。
从图2中可以看出，迭代曲线非常平滑，当搜索进行到R =CI （
arccos 3/槡1024
2arcsin 3/槡1024
）=14步时，目标态都将以各自最大概
率被检出，且检出概率分别等于目标态预先赋予的权重系数，同时非目标态概率为零，迭代结果均遵守
原Grover 算法的各项性质。在整个迭代过程中，非目标态的概率幅值始终显著小于目标态幅值，不会对目标态的识别造成干扰。与原Grover 算法目标态搜索结果的比较如表1所示。本文提出的算法是可靠而有效的。表1
本文算法与原Grover 算法迭代结果比较
算法|a 0〉|a 1〉|a 2〉本文算法0．77460．54770．3162原Grover 算法
0．5774
0．5774
0．5774
如果在计算过程中，系统引入了一定量的噪声，则对本文算法的迭代结果影响如图3所示。
可见，在没有过大噪声引入的前提下，目标态仍然能够得到有效识别，目标态可根据赋予的权重系数得到有效区分；非
目标态对目标态的干扰随着噪声的增大而变大，相比原Grover 算法，算法的抗噪声性能没有得到明显改善。
4结束语
本文对改变叠加态初态的幅值对使用Grover 算法进行迭代可能导致的结果进行了分析，得出了任意改变目标态的幅值可能导致算法失效的结论；在此基础上分析了在保证算法有效性前提下，引入权重系数必须满足目标态与非目标态概率之和等于1这一约束条件；基于条件提出了固定目标权重的量子搜索算法，能够成功搜索到目标态，并能够以权重值的概率有效地区别目标元素间的重要性差异。本文算法没有改善抗噪性，今后可进一步研究算法结构以提高算法的抗噪表现。参考文献：
［1］ZALKA C．Grover ’s quantum searching algorithm is optimal ［J ］．
Physical Reiew A ，1999，60（4）：2746-2751．
［2］GROVER L K．Quantum computers can search rapidly by using al-most any transformation ［J ］．Physical Review Letters ，1998，80（29）：4329-4332．
［3］张湿东，韦耿，吴乐南．一种改进的Grover 量子搜索算法［J ］．信
号处理，
2009，25（2）：256-259．［4］周立志，李飞，郑宝玉．一种改进的量子Grover 算法［J ］
．南京邮电大学学报：自然科学版，
2011，32（2）：27-30．［5］LONG Gui-lu ，LI Yan-song ，ZHANG Wei-lin ，et al ．Phase matching
in quantum searching ［J ］．Physics Letters A ，1999，26（10）：27-34．
［6］李盼池，李士勇．基于自适应相位旋转的Grover 量子搜索算法
［J ］．系统仿真学报，2009，21（12）：3557-3560．
［7］周日贵，曹建．旋转迭代量子搜索算法［J ］
．西南交通大学学报，2010，45（4）：585-588．
［8］夏克文，苏昶，沈钧毅，等．一种改进的Grover 量子搜索算法［J ］．
西安交通大学学报，
2007，41（10）：1127-1131．［9］BIHAM E ，BIHAM O ，BIRON D．Grover ’s quantum search algorithm
for an arbitrary initial amplitude distribution ［J ］．Physical Review A ，1999，60（4）：2742-2745．
［10］BIHAM E ，KENIGSBERG D．Grover ’s quantum search algorithm for
an arbitrary initial mixed state ［J ］．Physical Review A ，2002，66（6）：06230101-06230104．
［11］PABLO-NORMAN B ，RUIZ-ALTABA M．Noise in Grover ’s quantum
search algorithm ［J ］．Physical Review A ，1999，61（1）：405-408．
（上接第126页）
［6］DORIGO M ，MANIEZZO V ，COLORIA A．Ant system ：optimization
by a colony of cooperating agents ［J ］IEEE Trans on Systems ，Man ，and Cybernetics ：Part B ，1996，26（1）：29-41．
［7］JIAO Li-cheng ，WANG Lei．A novel genetic algorithm based on immu-nity ［J ］．IEEE Trans on System ，Man and Cybernetic ，2000，30（5）：552-561．
［8］李晓磊，邵之江，钱积新．一种基于动物自治体的寻优模式：鱼
算法［
J ］．系统工程理论与实践，2002，22（11）：32-38．［9］周永华，毛宗源．一种新的全局优化搜索算法—人口迁移算法
［J ］．华南理工大学学报：自然科学版，2003，31（3）：1-5．
［10］KRISHNANAND K N．GHOSE D．Glowworm swarm based optimiza-tion algorithm for multimodel functions with collective robotics appli-cations ［J ］．Multiagent and Grid Systems ，2006，2（3）：209-222．［11］陈建荣，王勇．采用捕鱼策略的优化方法［J ］
．计算机工程与应用，
2009，45（9）：53-56．［12］OFTADEH R ，MAHJOOB M J ，SHARITATPANAHI M．A novel meta-
heuristic optimization algorithm inspired by group hunting of animals ：hunting search ［J ］．Computer and Mathematics with Applica-tions ，2010，60（7）：2087-2098．
［13］DAI Chao-hua ，CHEN Wei-rong ，SONG Yong-hua ，et al ．Seeker opti-mization algorithm ：a novel stochastic search algorithm for global nu-merical optimization ［J ］．Journal of Systems Engineering and E-lectronics ，2010，21（2）：300-311．
［14］王勇，庞兴．一种采用动态策略的模拟捕鱼优化方法［J ］
．山东大学学报：工学版，
2010，40（3）：19-25．［15］庞兴，王勇．PSO 与捕鱼策略相结合的优化方法［J ］．计算机工程
与应用，
2011，47（8）：36-40．［16］WANG Yong ，HE De-niu ，GUAN Yi-jun ，dt al ．An improving FSOA
by using orthogonal transform ［J ］．Communication in Computer and Information Science ，2011，144（PARTZ ）：63-69．
［17］何德牛，王勇，管忆军．采用随机探测的改进FSOA ［J ］．计算机工
程与应用，
2011，47（36）：44-46．·
751·第1期马颖，等：基于固定目标权重的量子搜索算法

版权声明：本站内容均来自互联网，仅供演示用，请勿用于商业和其他非法用途。如果侵犯了您的权益请与我们联系QQ:729038198，我们将在24小时内删除。