万有引力搜索算法（通用6篇）
万有引力搜索算法 篇1
自然世界中的系统基本上是非线性的,而辨识系统［1］是建立这些复杂的非线性系统模型最有效的方法。其中T - S模型［2 － 4］是一种有效的辨识工具,其采用线性方程去表示每一个非线性系统局部区域的局部规则,以局部线性化为基础,通过模糊推理的方法实现全局的非线性。
本文基于引力搜索优化算法( gm GSA)［5 － 7］辨识T - S模型的参数,但该算法在优化过程中仍存在早熟收敛现象,易陷入局部最优。为克服标准引力搜索算法中全局搜索能力弱的缺点,本文借鉴遗传算法中基因突变( Genetic Mutations,GM) 原理［8］,提出基于基因变异的引力搜索算法,用来辨识T - S模型的参数。同时利用基于模拟退火［9］和遗传算法的模糊C均值算法( SAGAFCM) 来辨识T - S模型的结构。该方法辨识出的系统模型精确,且在系统辨识中得到广泛应用。
1 T - S模型
T - S模型是一种描述复杂非线性过程的数学模型,可看作是分段线性化的扩展,将非线性系统作为一系列线性系统的加权组合［2］,能将线性控制理论应用到非线性控制系统中。典型的T - S模糊系统的模糊规则为
式中,i = 1,2,…,m为模糊规则数; x =[x1,x2,…,xn] 为输入量; n为输入变量x的维数; w =[w1,w2,…,wn] 为n条规则的参数; yi为第ith条规则的输出; Aji为模糊子集。若给定输入x =[x1,x2,…,xn],则最终的输出变量y可由式( 2) 计算得到
式中,yi为第i条规则的输出; μi为第i条规则的真值; μi( x) 为隶属度函数,第i条规则模糊集的隶属度函数为hi( x) ,为各模糊子集的乘积,采用高斯隶属度函数
式中,cij为中心参数ci的第j个分量; σij是基宽参数 σi的第j个分量。
2引力搜索算法的T - S模型辨识
2. 1引力搜索算法
引力搜索算法( GSA)［5］是模拟万有引力定律的智能优化算法,在GSA算法中,种群个体在万有引力的作用下相互运动,个体的位置代表优化问题的解,质量通过函数值计算,解越好质量越大。通过引力作用,个体之间相互吸引并向质量最大的个体方向运动。当搜索结束时,质量最大的个体处在最优位置上,其位置信息对应相应优化问题的最优解。在对最优解进行搜索的过程当中,依靠彼此间力的作用达到优化信息的共享,最终在万有引力的作用下,使得种群朝着最优解所在的区域运动。设有N个个体存在于D维空间中,则第i个个体的位置信息表达式为
式中,xid代表第i个个体在d维空间的具体信息。则在t时刻,个体j对个体i的力为
式中,Mai为个体i在t时刻的惯性质量; Mpj为个体j在t时刻的惯性质量; G ( t) 为t时刻的引力因子; ε 为一个恒定的极小值; Rij( t) 为物体i与物体j间的欧氏距离。则在t时刻,个体i在d维上受到的合力
式中,j是[0,1]范围内的一个随机值; kbest为有引力作用在i上的个体数量; Fijd( t) 表示第j个个体对第i个个体在d维空间上的引力。则在力的作用下,个体i在t时刻在d维上得到的加速度为
式中,Mii为第i个个体的惯性质量。在迭代过程中,个体的速度和位置更新方式如式( 8) 和式( 9) 所示。
式中,randi是[0,1]的均匀分布。引力因子G会随着迭代的进行逐渐减小。
通过个体的适应度值来计算其惯性质量的大小, 惯性质量相对较大的个体所处的位置较优,其距离最优值也相对较近,该个体对其他个体的力的作用也较大,同时其所获得的加速度相对较小,运动较慢。个体的质量以及惯性质量如式( 10) ~ 式( 12) 所示。
式中,fiti( t) 为第i个个体t时刻的适应值; best( t) 为t时刻最好的适应值; worst( t) 为t时刻最差的适应值; Mi( t) 为第i个体t时刻惯性质量,对于求最小值问题, best( t) 和worst( t) 定义如下
对于求最大值问题,best( t) 和worst( t) 定义如下
2. 2基于基因变异的引力搜索算法
为克服标准引力搜索算法中全局搜索能力弱的缺点, 借鉴遗传算法中基因突变原理,提出基于基因变异的引力搜索算法,即gm GSA,算法在搜索策略上的变化如下:
( 1) 设变异概率为pr,同时产生一个到之间的随机数,当pr> pm时,随机产生新个体,否则个体位置不变
式( 17) 中,r'指产生新粒子的步长; xjd( t) 和xkd( t) 表示从种群中随机选取的两个位置,式( 18) 中,表示粒子原来的位置。
( 2) 对新个体进行评估,若新评估值fitnew优于原先值fitold,则对个体位置xid( t) 更新到xjd( t + 1) ,否则个体位置xid( t) 不变
gm GSA搜索方式不同于传统的GSA搜索方式,增加了一个变异概率,使得种群多样性增加,算法全局搜索能力增强。
2. 3辨识原理
T - S模型辨识分结构辨识和参数辨识,通常先进行结构辨识,确定规则数及规则中心参数,然后再辨识模型参数。结构辨识中不考虑参数辨识的影响,参数辨识是在已经辨识出的模型结构前提下进行的,不能实现全局优化。本文采用基因变异的引力搜索算法同时确定模型结构和参数,实现模型全局优化辨识。具体方法为: 聚类中心的维数为n,m为指定的聚类数, 聚类中的编码如图1所示。通过引力搜索和基因变异混合优化算法确定类中心,每个类表示一条规则,类中心即为高斯隶属度函数的中心参数ci,同时辨识出的参数还有基宽参数 σi,模型的后件参数wi和bi,算法实现简单。每个个体表示一个完整的解ci,σi,wi和bi。个体编码方法如图2所示。
假设L对训练数据( x1,y1) ,…,( xL,yL) ,采用经验风险最小化方法,训练目标使辨识误差最小
式中,n为训练样本数; yi和^yi为第i个输入样本的期望输出和模糊系统输出。
2. 4基于模拟退火遗传算法的FCM算法
模糊C均值聚类( Fuzzy C - Means Cluster) 算法是一种模糊聚类算法,简称FCM算法,该算法是一类基于目标函数的聚类算法,通过使目标函数收敛到最小值来达到聚类效果。FCM算法聚类,原理是用一个隶属关系矩阵U来表示每个样本点对于每个类的隶属度,矩阵U中每个元素的取值范围为[0,1],任意一个元素 μij表示第j个样本数据对类i的隶属度,任意样本点还应满足其对于所有类的隶属度之和为1,假设指定的聚类数目为c,用来聚类的数据样本点为X = x1,x2,…,xn,则
模糊C均值聚类的目标函数式为
式中,ci为第i个模糊类的类中心,聚类指数m的范围为[1,∞ ],通常取m = 2,当m = 1,模糊C均值聚类变成C均值硬聚类,dij2为第i个类中心与第j个样本点的欧氏距离。
3仿真实例与分析
这部分分别给出了两个实验来验证gm GSA算法的辨识精度和经其辨识出的T - S模型的泛化能力,一个是函数逼近问题,另一个是Box - Jenkins煤气炉问题。
( 1) 静态非线性系统。下面是一个具有两输入和一输出的静态非线性系统的表达式
为了比较,取文献[10]中50组输入输出数据对来做预测测试,设定输入u1和u2随机均匀分布于[1, 5]区间。gm GSA的参数设置成G0= 10,β = 6,最大迭代次数为500,种群规模为30,模糊规则数为6,辨识参数一共42个。表1所示的是前件参数和后件参数的辨识结果。图3表示T - S模型辨识的输出和真实系统的输出以及其之间的误差输出曲线图,与其他文献结果比较如表2所示。
在此实验辨识非线性系统问题上,测试的是gm GSA的全局优化能力。表2显示,gm GSA算法辨识出T - S模型的均方差为0. 003 4,远低于其他文献辨识的结果,证明了gm GSA算法具有较好的多样性,能够摆脱局部最优值的干扰,最终寻得全局最优值。
( 2) Box - Jenkins煤气炉数据测试。gm GSA的鲁棒性,再次采用Box - Jenkins煤气炉数据作为仿真对象。前148组数据作为训练数据来辨识T - S模型,后148组数据则用来测试模型的泛化能力。gm GSA的参数设置成G0= 5,β = 6,最大迭代次数为600,种群规模为10。仿真中采用3条规则,共39个辨识参数。辨识出的模型参数如表3所示。
样本点和测试点与辨识模型的均方差分别是0. 036和0. 101,具体如图4和图5所示,与其他文献辨识结果的比较如表4所示。
该实验辨识的是煤气炉数据,主要用来测试用改进算法辨识出的T - S模型的泛化能力。从表4中观察,通过SAGA - FCM聚类和gm GSA算法辨识出的T - S模型在辨识精度上较其他文献并非最佳,但已非常接近。重要的是,当用文中所提算法辨识出的T - S模型应用到另一组测试数据时,其表现出了最佳的稳定性和准确性,体现了改进算法辨识出的T - S模型结构紧凑,且泛化能力强,继而再次证明了改进算法的有效性。
4结束语
本文主要研究了引力搜索算法,针对标准引力搜索算法易“早熟”的问题,通过分析算法中各个因子的对算法性能的影响,提出改进的gm GSA算法,通过“变异”来保持粒子的多样性,继而增加粒子种群收敛到全局最优的机会。并应用于T - S模型的辨识,经实验证明该算法具有辨识精度和较快的收敛速度,以及良好的全局收敛能力,辨识出的T - S模型结构简单,精度更高,且泛化能力强。
摘要：针对引力搜索算法在求解复杂问题时搜索精度较低、易出现早熟收敛的缺点。提出一个新颖的智能算法-基于基因突变的引力搜索算法来辨识T-S模型的参数,同时提出一种改进的聚类算法辨识T-S模型的结构,实验结果表明,改进算法辨识出的T-S模型结构紧凑、精度更高,且泛化能力强。
关键词：T-S模型辨识,基因突变,FCM聚类,引力搜索算法
用广度优先搜索算法实现路径搜索 篇2
关键词：广度优先搜索,VC语言
路径搜索是许多游戏特别是即时战略游戏的核心组成部分, 玩过即时战略游戏 (如红色警报) 的朋友们对此一定都不陌生。在这类游戏中, 玩家不需要控制游戏主角的每一步移动, 只需用鼠标点击一下目的地, 游戏主角就可以自己移动到那里。那么游戏是如何实现路径搜索的呢?实现路径搜索的算法又是什么呢?下文就以一个简单的路径搜索为例, 说明上述问题, 并给出VC++的程序实现。
1 路径搜索的实现方法
路径搜索是一个寻径问题, 所谓寻径问题, 就是在地图上的起始点A和目的点B之间寻找一条可通行的路径。显然, A和B之间可以有很多条路径, 目的就是用最短的时间找到一条最佳路径。寻找最佳路径, 其本质就是搜索, 是一个从初始节点出发, 沿着与之相连的边试探前进, 寻找目标节点的过程。
路径搜索的基本算法主要有盲目搜索和启发式搜索两种, 进行盲目搜索时, 扩展节点不估计路径代价, 是比较常用的方法, 下文采用一种盲目搜索算法——广度优先搜索算法来实现即时战略游戏中的路径搜索。
1.1 广度优先搜索算法简介
广度优先搜索算法把起点作为初始节点, 从初始节点开始, 应用算法生成第一层节点, 检查目标节点是否在这些后继节点中。若没有, 再用算法将所有第一层的节点逐一扩展, 得到第二层节点, 并逐一检查第二层节点中是否包含目标节点。如此依次扩展、检查下去, 直至发现目标节点为止。这里采用的原则是先生成的节点先扩展, 为满足这一要求, 采用“队列”这一数据结构来存储节点, 队列设置两个指针:open指针和closed指针, open指针指向扩展得到的节点, closed指向已检查过的节点。当open=closed时, 表示队列空, 当open大于队列长度时, 表示队列溢出, 如图1所示。
1.2 路径搜索的实现过程
为了具体说明广度优先搜索算法在即时战略游戏中的应用, 以一个简单的路径搜索为例, 构造一个二维地图, 如图2所示, 把地图均匀划分为若干个小方格, 在图2中共3*3个方格, 游戏主角位于一个方格中, 我们选中其他任一个方格作为目的地, 点击鼠标, 游戏主角自动选路移动到目的方格。为了更加逼近现实情况, 可以设置某些方格为障碍物, 即游戏主角必须绕过障碍才能前进。例如, 方格编号如图2所示分别为1、2、……、9, 游戏主角位于方格1中, 方格5为障碍物, 玩家要使主角移动到方格9中, 那么广度优先搜索算法把1加入队列, 此时队列包含{1}, 检查1是否目标节点, 不是目标节点则继续搜索, 从1开始搜索相邻节点, 这是第一层搜索, 得到方格2和4, 检查2和4, 不是目标节点, 则2、4进入队列, 队列包含{1, 2, 4};进行第二层搜索, 由2搜索相邻节点得到3, 也搜索到了5, 但是方格5是障碍物, 不能加入队列, 由4搜索到7, 检查3和7, 不是目标节点, 于是3、7进入队列, 队列包含{1, 2, 4, 3, 7};继续第三层搜索, 由3得到6, 由7得到8, 检查6和8, 不是目标节点, 于是6、8进入队列, 队列包含{1, 2, 4, 3, 7, 6, 8};继续第四层搜索, 由6得到9, 检查9是目标节点, 于是结束搜索。为了记住搜索的路径, 在搜索过程中, 设计数据结构记录每一个节点的前趋节点, 如2的前趋节点是1, 这样, 在找到9之后, 可以根据前趋节点回溯到节点1, 回溯过程是9、6、3、2、1。可以用“栈”这一数据结构保存回溯过程, 压栈顺序为9、6、3、2、1, 这时, 游戏主角可以按路径移动, 移动按出栈顺序进行, “栈”是后入先出的数据结构, 于是, 主角就按1-2-3-6-9的顺序完成移动。
2 程序实现
下面给出广度优先搜索的程序实现。选用VC++6.0作为程序开发平台, 建立基于对话框的工程。程序设计的关键是: (1) 编写广度优先搜索类, 用于随机生成二维地图, 并且实现路径搜索。 (2) 实现游戏主角在地图中移动。
2.1 实现广度优先搜索的类CBfs Map
下面依次介绍CBfs Map类的成员函数。
函数void Init Map () 用于初始化地图, 并随机设置障碍物。
函数void Search Path () 用于路径搜索:
2.2 实现主角在地图中移动
创建一个基于对话框的类CBfs Dlg, 在类中添加按下鼠标左键的消息响应函数On LButton Down () , 该函数根据鼠标左键点击的位置, 进行路径搜索, 代码如下:
程序运行情况如图3所示, 界面中红色栅格表示障碍, 白色部分表示通路, 当玩家点击任意空白处, 游戏主角能够自行移动到该位置。
3 结语
介绍了一种采用广度优先搜索算法实现路径搜索的方法, 并给出了原理及关键数据结构。虽然代码不多, 却实现了一个较为完整的路径搜索实例, 希望能对游戏编程爱好者们起到积极的参考作用。
参考文献
三分搜索算法 篇3
众所周知,在没有更多的关于元素组次序的信息时,要找出是否在元素组中的元素,搜索元素组中的所有元素是不可避免的。但当知道元素组按升(降)序排列时,人们往往采用分治法解决。分治法的基本思想是将一个规模为n的问题分解为k个规模较小的子问题,这些子问题互相独立且与原问题相同,递归地解这些子问题,然后将各子问题的解合并得到原问题的解。根据分治法的分割原则,应把原问题分为多少个子问题才较适宜?每个子问题是否规模相同或怎样才为适当?这些问题一般很难予以肯定的回答。但人们从大量的实践中发现,在用分治法设计算法时,最好使问题的规模大致相同。即将一个问题分成大小相等的k个子问题来处理是行之有效的。许多问题可以取k=2。这种使问题规模大致相等的做法是出自一种平衡子问题的思想,它常常比子问题规模不等的做法要好。
给定已排序的n个元素a[0:n-1],现要在这n个元素中找出一特定元素x。
二分搜索算法解决这一类问题的基本思想是将这n个元素分成大致相同的两部分,取a[(n-1)/2]与x比较。如果x=a[(n-1)/2],则找到x,算法终止。如果x<a[(n-1)/2],则只须在数组a的左半部继续搜索x。如果x>a[(n-1)/2],则只须在数组a的右半部继续搜索x。具体算法可描述如下[1]。
输入:n个元素的升序数组a[0:n-1]和元素x
输出: 如果x=a[j],1≤j≤n-1,则输出j,否则输出-1。
low←0; high←n-1;j←-1
while(low≤high)and(j=-1)
mid←[(low+high)/2]
if x=a[mid] then j←mid
else if x<a[mid] then high←mid-1
else low←mid+1
end while
return j
容易看出,每执行一次算法的while循环,待搜索数组的大小减少一半。 但在寻找的x大于或等于数组的最大元素时,算法总执行最大次数的比较,即算法并未充分利用最大数(或最小数)。因此,在最坏的情况下,while循环执行了O(log n),循环体内运算需要O(1)时间,整个算法在最坏情况下的计算时间复杂性为O(log n)。由此可见,对搜索元素大于或等于待搜索数组的最大元素时,二分搜索法的效率不如其他情况的效率。要解决这样问题的搜索效率,又兼顾搜索元素在靠近待搜索数组中间位置的搜索效率问题,可采用将待搜索数组大致三等分的搜索方法——三分搜索法来解决。
三分搜索法的基本思想与二分搜索法基本思想类似,将这n个元素分成大致相同的的三部分,取a[(n-1)/3]与x比较。如果x=a[(n-1)/3],则找到x,算法终止。如果x<a[(n-1)/3],则只须在数组a的左三分之一部分中继续搜索x。如果x>a[2(n-1)/3],则只须在数组a的右三分之一部分中继续搜索x。上述两种情况都不成立时,则在数组中间的三分之一部分中继续搜索x。具体算法可描述如下:
输入:n个元素的升序数组a[0:n-1]和元素x
输出:如果x=a[j],1≤j≤n-1,则输出j,否则输出-1。
low←0;high←n-1;j←-1
while(low≤high)and(j=-1)
mid1←[(low+(high-low)/3]
mid2←[(high-(high-low)/3]
if x=a[mid1] then j←mid1
else if x<a[mid1] then high←mid1-1
else if x=a[mid2] then j←mid2
else if x>a[mid2] then low←mid2+1
else low←mid1+1;high←mid2-1
end while
return j
这是从小到大方向上的搜索。容易看出,每执行一次算法的while循环,待搜索数组的大小减少三分之二。在寻找的x等于数组的中间元素时,算法总执行最大次数的比较。因此,在最坏的情况下,while循环执行了O(lg3n),循环体内运算需要O(2)时间,整个算法在最坏情况下的计算时间复杂性为O(lg3n)。对具体n值的数组进行搜索时,虽然三分搜索法在数据搜索时,循环次数减少了,但在一次循环中最坏情况下需要进行数据的两次比较,数据减少量在同等数据的比较量下不如二分搜索法,由于充分利用了待搜索数组的最大数和最小数,在搜索方向的选择上灵活性更强。这是因为对上述算法稍加变化可得从大到小方向上的三分法的搜索算法。
low←0;high←n-1;j←-1
while(low≤high)and(j=-1)
mid1←[low+(high-low)/3]
mid2←[high-(high-low)/3]
if x=a[mid2] then j←mid2
else if x>a[mid2] then low←mid2+1
else if x=a[mid1] then j←mid1
else if x<a[mid1] then high←mid1+1
else low←mid1+1;high←mid2-1
end while
return j
由此当对待搜索数组的结构有所了解,就可以根据搜索数的大体位置选择搜索方向,从而更快捷的搜索出该数在数组中的位置。该算法对某些数据库关于某些已排序字段进行搜索记录给出了一种新的启示。
上面的问题也可利用递归思路解决,其算法可描述如下。
int ternarysearch(int a[],int low,int high,int x)
if (high<low)
j=-1;
else
int mid1=low+(high-low)/3;
int mid2=high-(high-low)/3;
if(x=a[mid1])
j=mid1;
else if(x<a[mid1])
j=ternarysearch(a,low,mid1-1,x);
else if(x=mid2)
j=mid2;
else if(x>a[mid2])
j=ternarysearch(a,mid2+1,high,x);
else
j=ternarysearch(a,mid1+1,mid2-1,x);
return j
这是按数组元素从小到大方向上的三分搜索法的递归算法,同样也可给出从大到小方向上的三分搜索法的递归算法,不再赘述。
摘要：给出了利用最大数(或最小数)的排序元素组的三分搜索法,该方法具有编程简单且易于计算机实现等特点,也可看成是对二分搜索法的补充。
关键词：排序元素,搜索,三分搜索
参考文献
搜索算法综述 篇4
搜索 (Search) 是通过搜索方法实现从问题的表示到问题求解的过程描述。搜索算法是通过计算机的高性能来有目标地穷举一个问题解空间的部分或所有的可能情况, 从而求出问题解的一种方法。根据搜索有无引导启发信息, 可将其可分为一般搜索和启发式搜索。一般搜索, 是一种没有任何经验和知识引导的、由某种具体规则确定的非智能性搜索;启发式搜索 (Heuristic Search) 是一种有准备的、追求效率而有的放矢的智能搜索, 它要求依据某种与问题有关且有利于尽快找到问题解的知识及信息的引导, 通过逐一状态比较而找到符合规定条件的目标状态解。常用的搜索算法如图1所示。
2 状态空间搜索
状态空间搜索就是将问题求解过程表现为从初始状态到目标状态寻找这个路径的过程。通俗点说, 两点之间求一线路, 这两点是求解的开始和问题的结果, 而这一线路不一定是直线, 可以是曲折的。由于求解条件的不确定性、不完备性, 使求解问题的过程中分枝较多, 这些分支构成一个图, 这个图就是状态空间。问题的求解实际上就是在这个图中找到一条可以从开始到结果的路径, 而寻找路径的过程就是状态空间搜索。
问题的状态空间可用有向图来表达。若图中的每条边都是有方向的, 则称为有向图。有向图中的边是由两个顶点组成的有序对, 有序对通常用尖括号表示, 如< Vi, Vj>表示一条有向边, 其中, Vi是边的始点, Vj是边的终点。< Vi, Vj>和< Vj, Vi>代表两条不同的有向边。如图2 所示。
问题的状态空间图又被称为状态树 (State Tree) 。如图3 所示, 节点sk表示状态, 状态之间的连接采用有向弧 (Arc) , 弧上标以操作数O来表示状态之间的转换关系。
用状态空间法搜索求解问题, 首先要把待求解的问题表示为状态空间图, 把问题的解表示为目标节点sn。求解就是要找到从根节点s1 到达目标节点sn的搜索路径。状态空间图如图4 所示。
在状态图中寻找路径的方法可以看成一种图搜索策略。在状态图搜索中会涉及两个集合, 分别为OPEN表和CLOSED表, OPEN表和CLOSED表分别代表初始集合和满足终止条件的目标集合, 按一定规则把初始结点集合中转换到目标结点集合, 即为图中的路径求解问题。
状态图搜索流程为: (1) 创建只包含起始节点s的图G, 把s放到一个未扩展结点表OPEN中; (2) 创建已扩展结点表CLOSED, 初始状态为空表; (3) 检查OPEN表, 若为空表, 则失败退出, 否则将OPEN表中的第一个结点n移除至表CLOSED中, 若n为目标结点, 则找到解, 成功退出; (4) 扩展结点n, 生成包含n的所有后继结点 (非祖先结点) 的集合L, 把集合L中的所有结点作为n的后继结点添加到图G中; (5) 为所有未在G中出现的L成员结点分别设置指向结点n的指针, 把L的这些成员添加到表OPEN中, 对已经在OPEN和CLOSED表上的每个L成员结点, 判断是否更改其指向结点n的指针, 对已在CLOSED表中的L成员结点, 判断是否更改图G中指向其每个后继结点的指针; (6) 按某种方法重排OPEN表; (7) 返回第三步继续操作。
从图搜索流程可以看出, 有按规则重排OPEN表的步骤, 该步骤为可选步骤, 是否按照某个规则或方法重新对OPEN表排序, 对应于图搜索过程中的一般搜索和启发式搜索。常用的状态空间图搜索算法有宽度优先搜索算法、深度优先搜索算法、A* 搜索算法等。
3 常用状态空间图搜索算法
3.1 宽度优先搜索
宽度优先搜索状态图搜索, 给定图G= (V, E) 和可以识别的源结点, 对图中的边进行系统性的探索, 以发现可以从源结点s到达的所有结点。该算法能计算出从源结点s到每个可到达结点的距离, 同时生成一棵宽度优先搜索树。该树以源结点s为根节点, 包含所有可以从s到达的结点。在宽度优先搜索树中, 从结点s到结点v的简单路径所对应的就是图结点s到结点v的最短路径。宽度优先搜索算法适用于有向图, 也可用于无向图。
宽度优先搜索的过程: (1) 创建只包含起始节点s的图G, 把s放到一个未扩展结点表OPEN中; (2) 创建已扩展结点表CLOSED, 初始状态为空表; (3) 检查OPEN表, 若为空表, 则失败退出, 否则将OPEN表中的第一个结点n移除至表CLOSED中, 若n为目标结点, 则找到解成功退出; (4) 扩展结点n, 生成包含n的所有后继结点 (非祖先结点) 的集合L, 把集合L中的所有结点作为n的后继结点添加到图G中; (5) 为所有未在G中出现的L成员结点分别设置指向结点n的指针, 把L的这些成员添加到表OPEN中, 对已经在OPEN和CLOSED表上的每个L成员结点, 判断是否更改其指向结点n的指针, 对已在CLOSED表中的L成员结点, 判断是否更改图G中指向其每个后继结点的指针; (6) 返回第三步继续操作。
宽度优先搜索在搜索访问一层时, 需要记住已被访问的顶点, 以便在访问下层顶点时, 从已被访问的顶点出发, 搜索访问其邻接点。在搜索访问下层顶点时, 先从队首取出一个已被访问的上层顶点, 再从该顶点出发, 搜索访问它的各个邻接点。宽度优先搜索能在搜索树中找到从起始节点到目标结点的最短路径。
3.2 深度优先搜索算法
深度优先搜索总是对最近才发现的结点v的出发边进行探索, 直到该结点的所有出发边都被发现为止, 一旦v的所有出发边被发现, 则回溯到v的前驱结点, 搜索该前驱结点的出发边, 重复该过程, 直到从源结点可以达到的所有结点都被发现为止。在状态图中, 起始节点的深度为0, 其后继节点的深度为父节点深度加1。对有些问题, 其状态空间搜索树的深度可能为无限深, 为避免深度值太大, 通常会给出结点扩展的最大深度值, 任何节点的深度值达到最大, 都将其作为没有后继节点处理。
深度优先搜索过程如下:第一, 创建只包含起始节点s的图G, 把s放到一个未扩展结点表OPEN中;第二, 创建已扩展结点表CLOSED, 初始状态为空表;第三, 检查OPEN表, 若为空表, 则失败退出。否则将OPEN表中的第一个结点n移除至表CLOSED中, 若n为目标结点, 则找到解成功退出;第四, 若节点n的深度为最大深度值, 则返回第三步;第五, 扩展结点n, 生成包含n的所有后继结点 (非祖先结点) 的集合L, 把集合L中的所有结点作为n的后继结点添加到图G中, 如果n没有后继, 返回第三步;第六, 为所有未在G中出现的L成员结点分别设置指向结点n的指针, 把L的这些成员添加到OPEN表前, 对已经在OPEN和CLOSED表上的每个L成员结点, 判断是否更改其指向结点n的指针, 对已在CLOSED表中的L成员结点, 判断是否更改图G中指向其每个后继结点的指针;第七, 返回第三步继续操作。
上述两种方法都是一般搜索策略, 非启发式搜索。如宽度优先搜索按照层次进行搜索, 按OPEN表的先后顺序从前到后依次进行考察;深度优先搜索是按照纵向深度进行搜索, 按照OPEN表的先后顺序从后向前依次进行考察。广度和深度优先搜索都没有依据问题本身的特征, 在扩展结点时, 没有分析扩展节点在问题求解上是否有利或能否找到最优解。一般搜索算法生成无用节点量大, 效率低。在扩展结点时, 依据问题本身的特征, 预估出结点的重要性, 就能在搜索时选择有利结点, 以便找到最优解。这种搜索策略为启发式搜索。
估计结点重要性的函数为评估函数f (x) , 评估函数f (x) 定义为从初始节点s1 出发, 约束地经过节点x到达目标节点sg的所有路径中最小路径代价的估计值。评估函数的一般形式为f (x) =g (x) +h (x) , 其中, g (x) 表示从初始节点s1 到节点x的实际代价, 通常称为代价函数;h (x) 表示从x到目标节点sg的最优路径的评估代价, 它体现了问题的启发式信息, 其形式要根据问题的特性确定;h (x) 称为启发式函数。因此, 在确定f (x) 时, 要协调好代价函数和启发式函数的比重。启发式方法把对问题状态的描述转换成对问题解决程度的描述, 这一程度用评估函数的值来表示。
3.3 A* 算法
A* (A-Star) 算法是一种求解出状态空间搜索的最短路径的最快方法。如果一个评价函数可以找出最短路径, 则称之为该函数可采纳性。A* 算法是一个可采纳的较好的算法。
3.3.1 A* 算法原理
A* 算法是一种有序搜索算法, 其评估函数f是根据找最小代价路径来估算结点。每个结点x的估价函数值为两个分量, 即从起始节点到节点x的代价和结点x到目标结点的代价。
A* 算法是将OPEN表中的结点按评估函数f (x) =g (x) +h (x) 进行排序的搜索过程。其中, g (x) 是对g* (x) 的估计, h (x) 为h* (x) 的下界, 即h (x) h* (x) 。g* (x) 是从起始节点S到结点x的最小代价;h* (x) 是从结点x到目标结点的最小代价, 若有多个目标结点, 则为其中最小的一个。
3.3.2 A* 算法搜索过程
第一, 把起始节点S放到一个未扩展结点表OPEN中, 记f=h。
第二, 创建已扩展结点表CLOSED, 初始状态为空表。
第三, 检查OPEN表, 若为空表, 则失败退出, 否则选取OPEN表中未设置过的具有最小f值的结点为最优结点n移除至表CLOSED中, 若n为目标结点, 则找到解成功退出。若n为非目标结点, 扩展结点n, 生成结点n的后继结点next。
第四, 对所有后继结点操作:其一, 创建从后继结点next返回结点n的引用; 其二, g (next) =g (n) +g (n, next) ;其三, 如果n为OPEN表中的结点, 则该结点为old, 并把它添加至n的后继结点表中, 比较新旧路径代价, 如果g (next) <g (old) , 则重新确定old的父辈结点为n, 记录较小代价g (old) , 同时, 修正f (old) 的值, 若n非OPEN表中的结点, 则判断其是否在CLOSED表中;其四, 如果n在CLOSED表中, 则返回, 否则将其添加到OPEN表中, 并添加next的后继结点表;其五, 计算f值, 返回第三继续判断。
A* 算法实际上是一种基于宽度优先搜索基础上的启发式搜索算法, 通常采用估价函数:f (n) =g (n) +h (n) 对当前的搜索位置进行评估。
4 结语
搜索算法是利用计算机的高性能来有目的地穷举一个问题解空间的部分或所有的可能情况, 从而求出问题的解的一种方法。在上述几种搜索算法中, A* 算法是最优路径搜索方法, 其要解决的问题是如何设法从图中寻找到一条从起点A到目标点B的最优通路。地图寻径中, 搜索算法的应用在国内外研究中仍然是一个热点问题, 但目前仍没有一个完美的解决方案, 故对搜索算法进行进一步研究和改进有一定的学术和应用意义。
参考文献
[1]钟瑛.改进A*算法在游戏地图路径搜索中的应用研究[J].网络安全技术与应用, 2013 (8) .
[2]周先曙.最短路径问题及其解法研究[J].电脑知识与技术, 2010 (10) .
[3]邱磊.基于A*算法的游戏地图寻路实现及性能比较[J].陕西科技大学学报, 2011 (6) :89-93.
[4]翁惠玉, 俞勇.数据结构:题解与拓展[M].北京:高等教育出版社, 2011:151-155.
[5]Patrick Lester.A*Pathfinding for Beginners[EB/OL]. (2012-2-20) [2015-01-04].http://www.policyalmanac.org/games/a Star Tutorial.htm.
[6]陈和平, 张前哨.A算法在游戏地图寻径中的应用与实现[J].计算机应用与软件, 2005 (12) .
[7]刘敏.Dijkstra算法求解最短路径的设计与实现[J].电脑知识与技术, 2012 (12) :2759-2761.
和声搜索算法参数研究 篇5
在音乐创作过程中, 乐师们凭借自己的记忆, 通过反复调整乐队中各乐器的音调, 最终达到一个美妙和声的过程。Geem[1]等人受这一现象启发, 提出一种新型的群智能优化算法——和声搜索算法, 已经在函数优化[2,3]和调度[4,5,6]等问题中表现出了优势。此算法结构简单, 参数少, 通过对参数的分析及调整, 利用多维函数进行仿真实验, 最终找出最优参数组合。
1 和声搜索算法 (Harmony Search, HS)
HS是Geem等通过类比音乐和最优化问题的相似性而提出的一种现代启发式群智能算法。将乐器的和声Ri (i=1, 2, …n) 类比于函数第i分量的解向量Xi (i=1, 2, …, n) , 评价对应解的函数值。HMS为和声记忆库的大小, 即和声库中解向量的个数。和声库HM=[X1, X2…, XHMS], 其中, 每个解向量由n分量组成Xi=[xi1, xi2, …, xin], i=1, 2, …HMSHMCR是产生新解时从和声库中保留解分量的概率;PAR则为记忆扰动概率。
1.1 初始化和声库
为了保证初始解的质量和多样性, 并保证优化结果具有一定的代表性, 初始种群在函数定义域内应均匀分布, 产生方式如下:
undefined
其中r为 (0, 1) 内产生的随机数, xi∈[LBi, UBi]
1.2 新解产生
候选解X'=[x'1, x'2, …, x'n] 中的每个分量j=1, 2, …, n, 产生方式如下:
(1) 和声库的学习。
undefined
当产生的随机数小于和声记忆概率时, 从第j列分量随机选取一个, 否则就在解取值范围中随机产生一个。
(2) 候选解分量微调。如新产生的候选解分量来自于和声记忆库, 若随机数小于PAR就对其进行微调, 其中α为微调变量。
undefined
候选解评价值小于和声库中最差解则替换之, 否则和声库不更新。
与其它算法不同, 和声搜索算法候选解产生原理是多个个体合作完成, 并通过微调机制增加算法局部寻优能力。
2 参数设计
2.1 HMS设计
HMS是影响算法执行性能和优化效率的重要因素之一, 决定了算法的全局搜索能力。若值太小则不能提供足够的采样点从而导致算法优化性能较差;反之, 取值越大, 搜索全局最优解的能力越强, 但是其值也不能过大, 太大值反而会增加计算量而导致收敛时间较长。因此, 采用合适的和声库规模有利于提高算法的收敛速度和解的质量。
2.2 HMCR设计
和声库记忆选择概率是影响优化结果的一个关键因素。HMCR值较大时, 解向量从和声库中进行选择的几率较高, 更好地继承了和声库的信息, 当HMCR较小时, 新解产生随机数的概率高, 增加了和声库的多样性。
2.3 PAR设计
PAR用于控制解的扰动概率。若PAR太大, 种群中的解以较大概率进行扰动, 容易使较好的解被破坏掉;若PAR太小, 种群中的解以很小的概率参与扰动, 则会使搜索停滞不前, 搜索速度减慢, 和声库失去多样性。
3 仿真实验与数据分析
为了对几个参数的设置进行比较, 采用了一些Benchmark问题进行计算, 相关函数如下:
(1) Sphere Model
undefined
(2) Schwefel’s problem
undefined
(3) Step function
undefined
(4) Rosenbrock function
undefined
采用C++编程语言, 在处理器为Intel (R) Core (TM) i3 2GHz、内存为512M的PC机上进行程序测试。每个函数进行30次仿真, 每次仿真的迭代次数为10 000, 求其平均值。
HMCR的值为0.1～0.9, HMS=5, PAR=0.3, 得到的结果如表1所示。
从表1可知, 针对如上4个函数, HMCR越大, 效果越好, 因此对其进行进一步实验, 细化HMCR的取值, 范围为0.91～0.99, 所得结果如表2所示。
从表2 可知, 通过对以上4个函数的测试, HMCR较理想的取值为0.96和0.97。
PAR参数在0.1～0.9范围内, HMCR=0.97, HMS=5时对4个函数结果影响如表3所示。
由表3可知, 综合几个函数进行考虑, PAR的取值为0.5时得到的结果最好, 因为参数PAR的变化对函数结果的影响不是特别大, 因此不进行细化研究。
HMCR=0.97, PAR=0.5, 固定这两个参数, 对HMS进行研究, HMS的取值分别设为5、10、20、30、50。研究其对函数结果的影响, 如表4所示。
由表4可知, HMS=5时, 函数结果得到最优值。
HMS、HMCR、PAR在算法中不仅各尽其责, 而且相互影响、紧密联系, 共同影响着算法的性能。只有选择较好的组合, 才能更好地指导算法。从各个参数中选择较好值进行组合, 得到结果如表5所示。
从表5可以看出, 针对文中用到的4个基准函数, 参数组合0.97、0.5、5为最优参数设计组合, 保证了算法具有较好的全局收敛性能, 同时具有较快的收敛速度, 能有效避免算法陷入局部最优。
4结语
HS算法是一种有效的群智能优化算法, 通过参数研究找出最优参数组合, 能更有效地解决函数优化和组合优化问题, 本文通过列举法得到了较好的参数组合。当然, 针对不同的问题还需要作进一步调整, 本文为以后HS的研究奠定了基础。
摘要：合适的参数能够提高和声搜索算法的性能和收敛速度。详细介绍了和声搜索算法的流程, 并总结了每个参数对算法的作用及参数变化对算法的影响。针对如何选取参数才能达到提高算法性能的目的, 通过参数调整的方法, 利用4个基准函数对算法进行仿真实验, 实验结果表明, 较高的HMCR、PAR和HMS取较小的值能使函数得到较优值。
关键词：和声搜索算法,基准函数,参数调整,仿真实验
参考文献
[1]GEEM Z W, KIM J H, LOGANATHAN G V.A new heuristic op-timazation algorithm:harmony search[J].Simulation, 2001 (2) .
[2]GEEM Z, KIM J, LOGANATHAN G.Harmony search optimiza-tion:application to pipe network design[J].International Journal ofModel Simulation, 2002 (2) .
[3]张凤荣, 潘全科, 庞荣波, 等.基于和声退火算法的多维函数优化[J].计算机应用研究, 2010 (3) .
[4]韩红燕, 潘全科.求解批量流水线调度问题的改进和声搜索算法[J].计算机工程, 2011 (6) .
[5]李俊青, 王玉亭, 潘全科, 等.混合离散和声搜索算法求解旅行商问题[J].微电子学与计算机, 2009 (3)
万有引力搜索算法 篇6
关键词：禁忌搜索算法,最短路径优化算法,智能路由,Dijkstra算法
0 引言
计算机网络的运行质量与路由的选择方法密切相关。不同的信息传输要求可以选择和采用不同的路由选择方法。目前的网络已经十分庞大, 并且以后发展的趋势会越来越大, 传统的互联网络路由协议会显得有些力不从心, 因此使用禁忌搜索算法对路由 (链路-状态路由选择算法 (Link-State Routing, L-S) ) 进行优化, 有着十分重要的作用。禁忌搜索算法是人工智能的一种体现, 是局部领域搜索的一种扩展。禁忌搜索最重要的思想是标记对应已搜索的局部最优解的一些对象, 并在进一步的迭代搜索中尽量避开这些对象, 从而保证对不同的有效搜索途径的探索。该算法优化最短路径算法不仅能够优化路由的选路方式和选路速度, 还能对路径上Qos进行优化, 使网络发挥到最大的性能。
1 禁忌搜索算法求解最短路径优化问题的数学模型框架
假设:已知整个网络的拓扑结构和各链路的长度, 求网络中任意2个给定节点之间的最短通路。若将已知的各链路的长度改为路由时延或其他参数, 例如, 带宽, 经过的节点数, 平均通信量, 平均队列长度等因素及其给组合, 就相当于求任意2个节点之间且有最小时延或最小代价的通路。因此, 求最短通路的算法且有普遍意义。
输入:图G= (B (G) , E (G) ) 有一个源顶点s和一个汇顶点t, 以及对所有的边ij∈E (G) 的非负边长Cij。
输出:G中从S到T的最短路径的长度。
第0步:从对每个顶点做临时标记L开始, 做法如下:L (S) =0, 且对除S外所有的顶点L (I) =∞。
第1步:找带有最小临时标记的顶点 (如果有结, 随机地取一个) 。使该标记变成永久标记, 即该标记不再改变。
第2步:对每个没有永久标记但是又带有永久标记的顶点相邻的顶点j, 按如下方计算一个新的临时标记:L (j) =Min{L (i) +Cij}, 求最小是对所有带有永久标记的顶点i做的。
第3步:判断最新永久顶点y与最新临时顶点x是否相等, 如果相等则标记此路径为冗余路径:H=Dis{L (y) -L (x) }。再判断顶点y, x延伸节点集合里是否分别存在x, y顶点.如果是则将之删除。重复第2步和第3步, 直到所有的顶点都打上了永久标记为止。
2 禁忌搜索算法的基本框架
2.1 初始化阶段
步骤1:加载问题相关数据, 初始化变量, 生成初始解x0∈X (X为可行解空间) , 清空禁忌表, 设计数器为0。
2.2 搜索阶段
步骤1:搜索不在禁忌表内或满足藐视法则的邻域移动x*∈N (x0) 奂X, 其中f (x*) ≤f (x) , 坌x∈N (x0) , 而N (x0) 是x0的所有邻域解。
步骤2:更新禁忌表T及目前最优解的记录, 执行邻域移动x0←x*。
步骤3:判断是否已达到终止条件。如过达到, 则终止搜索并输出最优解;否则, 计数器记录累加1并返回此阶段步骤1继续执行。
3 算法验证
在此验证测试中, 通过设置不同的算法参数, 分别对10个例题重复进行求解, 将得出的结果进行统计分析, 以获得算法最优参数设置的方法。
4 禁忌表的大小
禁忌表的长度过小会导致搜索迂回进行, 从而陷入局部最优的状态;而禁忌表长度过长, 则会对搜索进行过度的限制, 从而导致可能会错过获得最优解的机会。将禁忌表的长度设置为0.5n至3n之间, 并且将该区域平均分为5个区间, 区间的界限为 (0.5+2.5/4 x) n, (x∈[0, 4]) 取整的结果, 其中n为顶点数目, x为禁忌表长度系数。
5 算法最大迭代次数
在此参数的测试中, 我会先给一个较大的迭代次数作为迭代上限, 如顶点数目在50个以下的实例中设置为2000, 顶点数目大于50的时候设置为4000。然后在算法执行的时候记录各个实例达到最优解的时候经历的迭代次数, 这个迭代次数称为最优迭代值, 以所有例题中最大的最优迭代值作为推荐使用的算法最大迭代次数值。这个方法能够精确地测出各个实例达到最优解时所需的迭代次数。
6 测试方法
本次测试中, 使用10个例题进行, 每一个实例均使用上述5种禁忌长度及3种初始解构建方法进行测试。同时为了获得更加准确的数据, 上述测试会重复5次。因此, 在本次测试中会产生10×5×3×5=750组数据。
利用测试所获得的数据制作了“禁忌表长度与初始解生成算法的相互作用下对各个例题的影响程度图” (图1) 。横轴代表了禁忌长度系数;纵轴则表示了与例题已知最优解偏离百分比。偏离百分比的计算公式是ε= (C-C*) /C*×100%。其中, C为算法计算出的路径总距离, C*为问题已知的最优解的总距离。
根据图1制作了“禁忌表长度系数及初始解生成算法的相互作用下对最终解的影响图” (图2) 。我把横轴设为各个初始解生成算法, 而纵轴依然表示了与例题已知最优解偏离百分比, 图表中的各条折线, 表示了在各个禁忌表长度系数下不同的初始解生成算法的变化。
图2可以总结出, 当禁忌表长度系数为3 (即禁忌表长度为顶点数目的2.375倍) 时, 并且使用任意内接法作为初始解生成方法, 所获得的最终解与目前已知最优解之间的平均偏离百分比是最低的 (0.67%) 。
当两个参数的组合达到较低的偏离百分比时, 我们希望能通过最少的迭代次数来获得较低的偏离百分比, 所以, 平均最低的最优迭代值是各个例题的最优参数的组合。
至于算法最大迭代次数的测试方法, 我先对表1中的十个最短路径问题按顶点数量分成两组, 分别为“顶点数目不大于50”及“顶点数目在50以上”。然后分别对两组中各例题的最优迭代值进行比较, 从中选出最大的最优迭代值作为该组的算法最大迭代次数。测试的数据和各组的最优迭代值在表1中。
注:表中的数据是在禁忌表长度为3、使用任意内接法生成初始解的情况下获得的.
从表1中可以获悉当顶点数目不大于50时, 用任意内接法生成初始解, 且禁忌表长度系数为3时, 若要获得质量较佳的解算法所需的最大迭代次数至少为1306次;同样道理, 当顶点数目大于50时, 若要获得质量较佳的解算法所需的最大迭代次数至少为3590次。由此, 我建议当顶点数目不大于50时, 算法最大迭代次数应设为2000次;当顶点数目大于50时, 算法最大迭代次数应设为4000次。
编译环境及所描述的测试环境, 均在同一台机器上执行。机器的硬件如下, 处理器为Intel Core i7-2610UE Processor (1.5 GHz) 、内存4GB。值得一提的是, 此程序在运行时, 中央处理器并不是满负载运行, 故处理器的时钟频率不能用来计算程序执行的时间及效率。
7 测试小结
虽然课题并未通过大规模的测试来获得算法参数的精确设定方法, 但通过前面几个小节的测试和分析, 可以总结出以下结论:
(1) 参数的设置会因问题的实例不同而有所差异;
(2) 总的来说, 初始解的生成算法对最终解的质量并无明显的影响, 但建议使用任意内接法;
(3) 禁忌表长度对最终解的质量有明显的影响, 当禁忌表长度系数为3 (即禁忌表长度为顶点数目的2.375倍) 时, 所获得的最终解的偏离值是最低的;
(4) 当顶点数目不大于50时, 最大迭代次数设为2000;当顶点数目大于50时, 最大迭代次数应设为4000。
8 总结
在实际应用中, 没有一种算法对任何问题都是有效的, 不同的算法有不同的适用领域, 也有它不适合求解的问题类型。因此, 算法的混合就成为了扩展算法的适用范围、提高算法的效率的有效途径。针对本文的研究结果, 以下几点是在未来我研究的主要方向:
(1) 在本文中的禁忌搜索算法主要使用了全邻域搜索, 所以当顶点数目增加时, 算法的搜索速度会变得较慢, 在未来的研究, 我会尝试使用各种算法缩小邻域的搜索范围, 以增加搜索速度。
(2) 对算法加入多样性和集中性策略, 以加快跳出局部最优的能力。
(3) 将禁忌搜索算法与算法进行混合, 拓展算法的适用域, 提高算法的性能。