改进的DSM算法（共9篇）
改进的DSM算法 篇1
在现实生活中,无论从事什么样的职业,都会遇到优化问题。随着科技的不断发展、世界的不断变化,早前一些静态的、传统的方法,如单纯形法、共轭梯度法、模式搜索法以及牛顿法等,已经不能够很好的处理一些复杂的问题,于是动态的、高效的粒子群算法(PSO)便成为了众多学者研究的热点[1]。
基本PSO算法虽然比较简单,实现相对容易,不需要调整太多的参数,同时算法的早期收敛速度也比较快；但算法后期会受到随机振荡现象的影响,导致算法搜索到全局最优解的时间比较长,减慢了收敛速度;并且在一定程度上使其局部搜索能力表现较差,极易陷入局部最小值,精度降低,易发散[2]。针对基本粒子群算法的收敛精度问题,该文提出了一种新的改进粒子群优化算法—LPSO。
1 改进PSO算法研究
1.1 基本PSO算法
随机初始一群粒子,每个粒子均不包括体积和质量信息,将每个粒子都看作为优化过程中的一个可行解,粒子的好坏通过一个事先设定好的适应度函数来进行确定。优化过程中,每个粒子都将在可行解空间中进行运动,由一个速度变量决定其方向和距离。通常情况下粒子将追随当前的最优粒子,并经过不断的迭代搜索最后得到全局最优解。在每一次迭代过程中,粒子都将会跟踪两个最优值:一个是粒子本身迄今为止找到的最优解,即局部最优解;另一个是整个粒子群体到目前为止找到的最优解,即全局最优解[3]。
假设一个由n个粒子组成的粒子种群在d维的搜索空间中按照一定的速度进行飞行。粒子i在t时刻的状态属性设置如下:
位置:
Xi(t)=(xi1(t),xi2(t),…,xid(t)
xid (t)∈[Ld,Ud]
其中Ld为搜索空间的下限,Ud为搜索空间的上限;
速度:
其中:vmin为最小速度,vmax为最大速度;
个体最优值位置:
Pi(t)=(pit(t),pi2(t),…,piD(t))
全局最优值位置:
pg(t)=(Pgt(t)pg2(t)…,pgD(t))其中:1≤d,1≤i≤M。
那么粒子在t+1时刻的位置可以通过下式来得到:
式中,r1、r2都为均匀分布在(0,1)区间的随机数;c1、c2是学习因子,一般取2。
基本的PSO算法尽管比较简单,实现也相对容易,并且不需要调整太多的参数,早期收敛速度快;但同时也存在其局限性,由于粒子在移动时没有选择性,即使下一个粒子位置的评价函数值较差,粒子还是利用逐个位置来代替当前位置,这样就使得粒子很容易跳出最优解附近的某一邻域,因此在一定程度上表现出较差的局部搜索能力,比较容易陷入局部最小值,降低了精度,也易发散[4]。鉴于基本粒子群算法还存在一些不足之处,该文提出了一种新的改进的粒子群算法,下面将对其做具体介绍。
1.2 粒子群算法的改进算法研究
该文所提出的改进的粒子群算法主要是在基本粒子群算法基础上,对以下几个方面做了改进:
(1)惯性权重模型。
由于惯性权重w较大时,算法具有较强的全局搜索能力;w较小时,则算法局部搜索能力较强。所以本文中采用线性模型,随着迭代次数的增加,将w由初始的0.9线性递减至0.4,以达到期望的优化目的。权重函数w由下式确定:
式中Wmax为最大惯性权重,一般取0.9,wmin为最小惯性权重,一般取0.4。
(2)学习因子模型。
学习因子c1、c2表示粒子向个体最优值和全局最优值进化的随机加速权值。当c1、c2都等于0时,粒子会按照当前速度进行飞行,直到运动至边界处。当学习因子较小时,粒子将会在远离最优值区域内发生振荡现象;较大的学习因子则可以促使粒子快速向最优解区域内移动。所以该文中采用自适应模型,如下式所示:
式中cmax为最大学习因子,Cmin为最小学习因子,MaxDT为最大迭代次数,t为当前迭代次数。
(3)粒子位置更新方程的改进。
基本PSO算法前期,精度较低,易发散。如果参数较大的话,在后期收敛速度会变慢,从而无法继续进行优化。在进化规划中,算法中若带有高斯变异和柯西变异算子时,算法都会取得较好的收敛效果,因此,该文中对个体最优解加入了高斯算子,每次找到一个个体最优值时,将在其周围利用高斯算子进行局部搜索。这样不仅可以提高算法前期的收敛精度,还可以改进算法后期的收敛速度,可以有效避免后期在最优解附近发生振荡。所以该文中的粒子位置通过下式来进行更新:
是均值为0,方差为1的高斯变量,fmin是n个粒子中的最小适应函数值,即当前最优值,β是尺度因子,通常取0.6。
(4)早熟收敛的改进策略。
PSO运行过程中,如果其中一个粒子发现一个当前最优位置,此时其他的粒子会快速向其聚集。如果该最优位置是个局部极值点,或者两个粒子均处于局部极值点,此时整个粒子种群将不可能在解空间内重新进行寻优,导致算法失去了搜索能力,陷入局部最优,这一现象就称为早熟收敛。该文对会与当前最优解重叠的粒子加入交叉操作过程,这样可以使该粒子状态重新更新,寻找新的搜索区域,从而跳出函数的局部极值点。首先给定一个阈值,如果其中一个粒子与当前最优粒子的位置距离小于之前设定的阈值,则对其进行交叉操作。具体的交叉公式如下:
式中x是粒子位置,x为粒子速度,pi是介于[0,1]之间的一个随机数,x'ibest为局部最优解。
2 仿真实验
(1)粒子群算法性能比较仿真。
为了验证改进粒子群算法的有效性,该文中选取标准的测试函数,分别利用基本粒子群算法和改进后的粒子群算法对函数进行优化,寻找适应度函数的最优解。
测试函数:Griewank函数
式(6)中的X表示一个粒子,xi为粒子的每个分量,d为每个粒子的维数[3]。
首先在[-10,10]的区间内均匀生成两组数,作为初始的粒子种群,数的个数为生成粒子的个数,每个粒子都是二维的,则该函数的三维图形如图1所示。由图可以看出:该函数存在多个局部极值点,但只存在唯一的全局最优点在(0,0)处。
该文在进行仿真实验过程中的相关参数设置如下:学习因子cimin=2,cimax=5,粒子个数n=100,粒子维数D=10,粒子位置范围xi∈[-100,100],最大迭代次数选取为100次,交叉操作过程中的阈值g取0.5,尺度因子β取0.6。仿真结果如下,图2中描述的是函数的最优适应值与迭代次数之间的关系。
由上述仿真结果可以看出,改进的粒子群算法(LPSO)较基本粒子群算法,不管是收敛精度还是循环迭代次数,都有所提高,验证了改进算法的有效性。
3 结语
该文在基本PSO的基础上,对参数的选择进行了调整,同时引入高斯算子及交叉操作过程。仿真结果证明,改进后的算法收敛效果较好。
参考文献
[1]张必兰.改进的粒子群优化算法及应用研究[D].重庆:重庆大学,2007.
[2]李丽,牛奔.粒子群优化算法[M].北京:冶金工业出版社,2009.
[3]吴进华,吴华丽,周仕.基于模拟退火的粒子群算法[J].仪器仪表学报,2008.
[4]Yumao Li.Particle swarm optimization algorithm research and improvement[D].Northwestern university master degree thesis,2009.
[5]任小波,杨忠秀.一种动态扩散粒子群算法[D].银川:宁夏工程学院,2010.
[6]刘逸.粒子群优化算法的改进及应用研究[D].西安:西安电子科技大学,2013.
改进的DSM算法 篇2
摘要：针对DV-Hop算法采用跳数乘以平均每跳跳距估算节点间的跳距，利用三边测量法或极大似然估计法估算节点坐标信息，算法过程存在缺陷从而造成定位误差过高的问题。为此提出一种基于节点密度区域划分的DVHop改进算法（DZDVHop），依据网络的连通度和节点密度限制参与估算的信标节点的跳数，采用加权质心法估算定位坐标。Matlab仿真测试结果表明，在相同的网络硬件和拓扑结构环境下，改进后的算法能有效地减少节点通信量，且平均定位误差率比传统的DVHop算法减少了13.6%左右，提高了定位精度。〖BP）〗
针对DVHop算法采用跳数乘以平均每跳跳距估算节点间的跳距，利用三边测量法或极大似然估计法估算节点坐标信息，算法过程存在缺陷从而造成定位误差过高的问题。为此提出一种基于节点密度区域划分的DVHop改进算法（DZDVHop），依据网络的连通度和节点密度限制参与估算的信标节点的跳数，采用加权质心法估算定位坐标。Matlab仿真测试结果表明，在相同的网络硬件和拓扑结构环境下，改进后的算法能有效地减少节点通信量，且平均定位误差率比传统的DVHop算法减少了13.6%左右，提高了定位精度。
关键词：
无线传感器网络；密度区域划分；节点定位；限跳机制
中图分类号：TP393
文献标志码：A
0引言
现代电子技术、检测技术和信号处理等技术的进步，促进了低功耗、多功能智能传感器的快速发展[1]。无线传感器网络（Wireless Sensor Network，WSN）是指由大量成本低廉的具有智能感知能力、计算能力、无线通信能力的传感器节点组成的网络，它可以感知、采集和处理网络覆盖区域内目标对象的信息[2-3]。作为一种新型信息获取的系统，WSN广泛应用于军事、环境监测、城市交通、灾难防控等众多领域[4]。节点定位问题是传感器网络进行目标识别、监控、定位等应用的前提，也是传感器网络应用的关键技术之一[5-7]。研究节点定位算法的意义主要体现在两方面：一是，WSN中的多数应用都依赖于传感器节点或者被检测目标的地理位置信息，不知检测目标位置而获取的任何信息都是没有意义的[8]；二是，WSN网络的运行和管理需要节点位置信息的支持。因此，准确估算节点位置，在传感器网络的应用中起着至关重要的作用。
节点定位技术分为基于测距（Range Based）的定位算法和无需测距（Range Free）的定位算法两类[3]1283，[5]39，[8]3。基于测距的定位算法原理是：通过测量节点与节点间的直线距离或角度信息估算未知节点的坐标位置，目前这类测距技术主要有RSSI（Received Signal Strength Indicator）、TOA（Time of Arrival）、TDOA（Time Difference on Arrival）和AOA（Angle of Arrival）等[1]77，[5]40。基于测距定位算法的优点是定位精度较高，缺点是网络中的节点需要增加特殊的测距设备，从而导致节点成本较高。而无需测距的定位算法原理是：不需要测量节点间的实际距离以及节点间的方位角，只根据网络中节点间的连通性、同向性等信息，就可以估算出未知节点的坐标位置，常用的无需测距技术有：APIT（Approximate PointinTriangulation test）、质心算法、DVHop（Distance VectorHop）和Amorphous等算法[5]40，[9]。无需测距定位算法的优点是：组网成本低、网络资源开销少，缺点是定位误差率稍高。实践证明无需测距定位技术更能适合多数WSN的应用，而在众多无需测距的定位算法中，DVHop算法以其算法过程的简单性和实效性成为目前应用较多的种类之一[7]2468。WSN中的节点分为两类：一类是预先已知自身位置信息的传感器节点，称之为信标节点（或“锚节点”），信标节点的坐标信息既可以通过全球定位系统（Global Positioning System，GPS）等技术自动获得，也可以在部署网络时靠人工设置[8]6；第二类节点是预先并不知道自身的位置，通常称之为待定位节点或者未知节点。这些未知节点的位置信息就需要利用本文和相关研究所探讨的相关定位算法进行估算。
1经典DVHop算法描述
美国Rutgers University的〖BP（〗Dragos 〖BP）〗Niculescu等将距离矢量路由与GPS原理相结合提出了一系列分布式定位算法（Ad Hoc Positioning System，APS）[10]。APS共包括DVHop、DV Distance、Euclidean、DV Coordinate、DV Bearing和DV Radial等6种类型。其中应用较多的是DVHop，DVHop的执行过程可归纳为以下3个阶段[1]77，[5]40，[11]。首先，接收并存储未知节点与它邻近的每个信标节点间最小跳数；信标节点向邻居节点广播包含自身地理位置信息的分组，这样网络中的所有节点都能记录下自己到每个信标节点的最小跳数。其次，计算未知节点与信标节点的跳距；每个信标节点根据上述第一个阶段的操作，记录下了自己与其他信标节点的坐标值以及它们间的跳数。最后利用式（1），就可以估算出自己的平均每跳跳距。其中：（xi，yi）、（xj，yj）是信标节点i和j的坐标，hj是信标节点i与j之间的跳数。
简单选择排序算法的改进算法 篇3
排序算法是一种被广泛使用的算法, 在计算机软件领域发挥着重要作用。排序是将数据元素的任一序列, 重新排列成一个关键字有序的序列。基于比较和移动的排序算法具有通用性, 包括插入排序、选择排序、交换排序、归并排序、基数排序等等。各种排序的算法各具有优缺点, 但就其全面性能而言, 很难提出一种被公认的最好的方法。判断一个排序算法优劣的标准一般为时间复杂度、空间复杂度和稳定性。
一、简单选择排序算法
1、排序方法
选择排序 (Selection Sort) 是最符合人们思维习惯的一种排序方法。基本思路是每次从待排文件中挑选一个key值最小的 (或最大的) 记录放置于它应所在的位置。若待排文件长度为n, 则选择n-1趟便达到排序目的。选择排序一般又分为“直接选择排序”和“堆选择排序”。
2、直接选择排序的C语言算法
对上述算法进行优化, 在一趟中找到key, 如果该key就是i位置上的记录, 就不用交换。算法如下:
3、直接选择排序的算法分析
设排序文件的记录长度为n。算法中共进行了n-1趟选择, 每趟选择一个当前最小key的记录, 要经过n-i (1≤i≤n-1) 次的key比较, 故总的key比较次数C为:
另外, 当文件按key正序时, 记录移动次数等于0。而完全逆序时, 每趟选择后有3次记录移动, 所以最多移动次数为3 (n-1) 。故直接选择排序的时间复杂度T (n) =O (n2) 。直接选择排序属于稳定排序。
二、简单选择排序算法的改进算法
1、排序方法
基本思路是每次从待排文件中挑选一个key值最小的和一个key值最大的记录, 最小的放置于最前面, 最大的放置于最后面的位置。若待排文件长度为n, 则选择n/2趟便达到排序目的。
2、改进算法的C语言算法
3、改进算法的算法分析
设排序文件的记录长度为n。算法中共进行了n/2趟选择, 每趟选择一个当前最小key和最大key的记录, 要经过2 (n-2i) (1≤i≤n/2) 次的key比较, 故总的key比较次数C为:
C和=直ni∑/=1接2 (2选n择-排2i序) 的算法相比, 时间复杂度仍为T (n) =O (n2) , 但选择趟数减少了一半, 比较次数因为内循环中比较了2次, 和直接选择排序比较次数相当。
结束语
本文作者提出的上述改进的选择排序算法, 已通过在VC++6.0环境进行正确性测试。该算法是在简单选择排序的基础上提出来的改进算法, 提高效率是显而易见的。
摘要：排序算法是一种被广泛使用的算法, 在计算机软件领域发挥着重要作用。经典的排序包括:冒泡排序、选择排序、插入排序等等。本文以简单选择排序算法为基础, 对其进行改进, 得出与之具有更高的排序效率。
关键词：选择排序,改进算法
参考文献
[1]严蔚敏等:《数据结构 (C语言版) 》, 清华大学出版社, 2005.7。
[2]潭浩强:《C程序设计》, 清华清华大学出版社, 1999.4。
[3]方同祝、胡正国、田铮、金文凯:《一种节省空间的排序算法》, 《小型微型计算机系统》, Vol.26 No.7 July 2005。
[4]王敏:《改进的双向选择排序算法》, 《信息技术》, 2010年第9期。
改进的DSM算法 篇4
在噪声消除系统中,若观测噪声为有色噪声,则基于最小二乘准则(LS),提出了两段RLS-RELS算法,这是一种改进的.递推增广最小二乘法,该自适应算法能显著减小噪声的影响,提高信号质量.并在此基础上提出了计算噪声方差的估值方法.计算机数值仿真例子和信噪比的计算比较证明了算法的正确性和有效性.
作 者：许鹏 窦寅丰 XU Peng DOU Yin-feng 作者单位：许鹏,XU Peng(暨南大学珠海学院计算机系,珠海,519070)
窦寅丰,DOU Yin-feng(黑龙江大学电子工程,哈尔滨,150080)
改进的DSM算法 篇5
教学中的最后一个环节, 也是最能体现学生学习情况、教师授课效果的环节就是考试。但面对各高校每年大量扩招的现状, 考试命题、阅卷等工作越来越繁重, 这无疑使得命题效率、试卷质量、阅卷差错率受到或多或少的影响。同时, 传统命题方式, 可能产生不同教师命题, 内容侧重点、难点有所差异, 无法更客观、公正地反映学生的学习效果及教师的教学质量, 无法对教师的教学改革提供更积极有益的理论指导。因此, 推行无纸化考试, 采用高效智能算法自动生成试题成为对学生考核手段变革的必然。
组卷问题是一个全局寻优的问题, 在寻优过程中需要综合考虑章节 (ch) 、题型 (ty) 、知识点 (Kn) 、难度系数 (Di) 、区分度 (De) 、答题时间 (Ti) 、分数 (Sc) 等各种约束条件。则每道题目可用一个形如: (Ch, Ty, Kn, Di, De, Ti, Sc) 的7维向量描述。设题库中题目数量为n, 则n道题目可用式 (1) 所示的7×n阶矩阵描述。
式 (1) 中:七种参数既可由用户手工输入, 也可利用之前的模板自动产生。试卷生成算法可转化为如何在已有n道题目的题库中选择m道题目, 使这m道题目在章节、知识点、难度系数、区分度等方面满足或最接近用户的需求, 即在该7×n阶矩阵中选则最优的7×m阶子矩阵。
1 传统试卷生成算法
经过20多年的发展, 目前主要采用的试卷生产算法有以下三种:
1.1 随机选取法
根据用户输入的考试要求, 随机从试题库中选取满足条件的试题组成试卷, 直到整份试卷组成或已搜索到题库末尾。该方法具有很大的随机性和不确定性, 无法从整体上把握教学的要求, 不具有智能性[1], 且组卷效率低下。
1.2 回溯试探法
即将随机选取法产生的每一个状态类型记录下来, 当搜索失败时释放上次的状态类型, 再按照一定的变换规律重新选取, 直到满足要求的整份试卷自动生成[2]。
1.3 传统遗传算法
遗传算法 (Genetic Algorithm) 是模拟达尔文进化论的自然选择和遗传学机理的生物进化过程的计算模型, 是一种通过模拟自然进化过程搜索最优解的方法。遗传算法从代表问题可能潜在的解集的一个种群 (Population) 开始, 而一个种群则由经过基因 (Gene) 编码的一定数目的个体 (Individual) 组成。每个个体实际上是染色体 (Chromosome) 带有特征的实体。应用于组卷中, 种群即初始交配池中试卷的集合, 个体即每一套试卷而染色体即组成该试卷的每道试题。传统遗传算法生成试卷的思路如图1所示。
首先按特定方法对试题进行编码, 然后从原始题库中抽取出一定数量的试题生成n份初始试卷, 作为遗传算法的交配池。计算其中每份试题的适应度值, 并按照预先设置好的复制、交叉、变异原则进行相应运算, 衡量适应度值是否满足要求。如果满足则解码生成试卷, 否则继续进行交叉变异等各项运算, 直至适应度值满足要求或达到预先设定好的代数要求为止。
2 基于改进遗传算法的试卷生成算法设计
遗传算法具有内在的并行性, 全局寻优和收敛速度快的特点, 这些都易于处理试题库自动组卷问题[3]。但基于传统的遗传算法的组卷方法易发生早熟、收敛速度慢等问题, 针对这些问题, 魏平等[4]采用稳态策略的单亲遗传算法求解组卷问题, 通过突变算子的引入, 使整个种群保持在最有可能获得成功的状态, 加快算法向全局最优值的逼近速度。王淑佩等[5]提出了一种自适应调整种群适应值分布的基于小生境技术的遗传算法并将之应用于求解组卷问题。
本文采用一种新的基于改进遗传算法的试卷生成算法, 具体设计如下:
2.1 编码设计及初始种群的生成
试题编码采用分组自然数编码方式。按照题型将其分为不同组, 组内采用自然数按照题目录入的先后顺序编码。在系统生成试卷前, 首先需要用户提供期望的难度、章节、及命题蓝图。如:用户期望的试卷难度为0.8, 命题范围为1～6章, 并选用1号命题蓝图, 即:整份试卷满分100, 其中选择题20×2分、填空题10×1分、判断题10×1分、简答题4×5分、程序设计题2×10分。运用石中盘[6]的理论, 根据用户输入的期望难度值自动生成各种难度试题占整份试卷的百分比, 再在遵从章节分配和命题蓝图等约束条件的前提下, 随机生成初始种群。表现形式如表1, 表2所示。
2.2 适应度函数
适应度函数用于衡量个体性能的优略程度, 他的设计对遗传算子有很大影响, 是优化个体的依据[7]。本文采用实际属性值和用户期望值之差作为适应度函数, 差值越小说明个体适应度越高, 越符合用户的期望, 反之, 适应性越低。
试卷难度:Di (x) =Dih-g (x) 。式中:Dih为用户期望的难度系数;
同理可得出区分度的适应度函数De (x) 。
章节:C (xi) =Ch-Ci。式中C (xi) 为第i章的值, Ch为用户期望该章节试题占整份试卷的比例;Ci为该章节题目实际所占比例。
整份试卷的适应度:
F (x) =max[Di (x) , De (x) , C (x) ]
2.3 选择算子
对原种群中的个体按适应度值的大小排序, 取值最小的前20%个体直接进入下一代种群, 余下的个体两两配对, 按交叉、变异概率进行相应运算。
2.4 交叉算子及变异算子
为了避免早熟及收敛速度慢等问题, 在交叉算子和变异算子的设计上采用自适应方法, 根据不同个体的适应度值选取适合自己的交叉和变异算子。给定标准交叉、变异概率 (j, b) , 当适应度函数的值较大时, 个体的交叉、变异概率增大。
交叉概率:
变异概率:
3 结 语
经试验, 该算法在交叉概率j为0.78～0.82, 变异概率b=0.3, 种群大小Popsize=80, 固定最大代数Maxgen=150时可快速、高效得到有用解。
参考文献
[1]全惠云, 范国闯.基于遗传算法的试题库智能组卷系统研究[J].武汉大学学报:自然科学版, 1999, 45 (5) :758-760.
[2]杨青.基于遗传算法的试题库自动组卷问题的研究[J].济南大学学报:自然科学版, 2004, 18 (3) :228-230.
[3]王淑佩, 易叶青.基于改进自适应遗传算法的组卷研究[J].科学技术与工程, 2006, 6 (4) :469-473.
[4]魏平, 干海光, 熊伟清.基于进化稳定策略的单亲遗传算法求解组卷问题[J].微电子学与计算机, 2005, 21 (2) :105-109.
[5]王淑佩.一种新的基于小生境的自适应遗传算法[D].兰州:兰州理工大学, 2006.
[6]石中盘, 韩卫.基于概率论和自适应遗传算法的智能抽题算法[J].计算机工程, 2002 (1) :141-143.
[7]周文举.基于遗传算法的自动组卷系统研究与实现[D].济南:山东师范大学, 2006.
改进的DSM算法 篇6
互联网技术的发展,硬件技术和通信技术的进步共同加快了计算机领域的进步。20世纪80年代出现了并行计算,支持同步的算法、程序和体系结构的开发。随后出现了分布式计算,它要求各个处理机之间能够协同计算,通过处理机间的通信共同解决问题。网格计算技术[1]的发展则迎合了21世纪并行与分布式计算技术的发展趋势,它是以资源共享为目的,支持对可计算资源的远程和并发的访问,用高速网络连接的地理上分布的可计算资源所组成的一个具有单一系统映像的高性能计算和信息服务环境。
网格资源包括计算资源、存储资源和通信资源。对于网格用户而言,它向网格系统提交任务,由网格调度程序按照某种调度策略把用户提交的任务分配给网格系统中的可用资源。如何使这些资源高效地完成计算任务是网格系统的研究重点之一。
由于在网格环境下的任务调度主要考虑的是一组相互独立、任务之间没有通信和数据依赖的元任务(metatask)映射。现有的任务调度算法可以分为在线模式(on-line)和批模式(batch-mode)两种。在线模式是任务一到来就加以映射,而批模式则是把任务收集起来等映射事件到来后才对这些任务进行集中映射。相比而言,批模式得到了大量的资源信息,从而可以做出更合理的任务映射策略。在这里讨论的是批处理模式的任务调度,即调度程序的执行周期到时再集中映射。
以时间跨度(makespan)为优化目标的任务—资源映射是一个NP完全问题,解决这类问题常用启发式算法。经典的批模式算法有Min-min、Max-min、Suffrage、遗传算法、蚁群算法等。T.Braun[3]等人通过对一些常用的算法进行了比较,在一定规模时遗传算法所求出的时间跨度要优于其他算法一些,但随着规模扩大,其收敛性降低[4],因此本文提出了将遗传算法和Min-min算法相结合的改进遗传算法的任务调度优化模型,该算法也适合大规模任务的调度,并进行了仿真实验。
1 问题描述
任务调度问题的实质[2]就是在一个有n个需要调度的任务、m个可用的资源(主机或集群) 的网格环境下,把n个子任务J={J1,J2,…,Jn}以合理的方式调度到m个资源R={R1,R2,…,Rm}上去,目的是得到尽可能小的总执行时间,提高系统吞吐量等。具体描述如下:
(1) J是n个需要调度的任务集合,Ji表示第i个任务。每个任务的任务量大小用百万指令(MI)表示,且每个任务只能一个资源上执行完成。
(2) R是m个可用的资源集合,Rj表示第j个资源。每个资源的计算能力用百万指令每秒(MIPS)表示。
(3) n个任务在m个不同资源上的预测执行时间ETC( Expected Time to Compute)是一个n×m的矩阵。矩阵中的每一行代表某一个任务在m台资源上的不同执行时间,每一列代表在同一台资源上n个任务的不同执行时间。ETC(i,j)表示第i个任务在第j个资源上的执行时间。
(4) 资源j的最早可用时间为STARTTIME(j)。
(5) 把任务i所需的数据从存储系统传输到资源j上的传输时间为TRANS(i,j)。
(6) 第i个任务在第j台资源上的预测最小完成时间为MCT(i,j),则MCT(i,j)=STARTTIME(j)+TRANS(i,j)+ETC(i,j)。
(7) 任务i的最小完成时间为Ci,当任务分配给第j个资源时,Ci=MCT(i,j)。
(8) 所有任务都执行完成的时间为时间跨度(makespan),即makespan=Max{Ci,i=1,2,…,n}。
2 设计与实现
遗传算法(GA)是Holland于1975 年受生物进化论的启发而提出的,并行性和全局解空间搜索是GA的两个最显著的特点。网格任务调度问题是一个NP问题,在一定规模时,用遗传算法进行网格任务调度能得到很好的性能。Min-min算法是一种实现起来很简单的算法,算法的执行时间也很快,具有较好的时间跨度。遗传算法随着调度规模的扩大,在一定调度时间限制内,它的收敛性会逐渐降低。因此,本文提出一种将Min-min算法和遗传算法相结合的改进遗传算法。
2.1 Min-min算法
Min-min算法的主要思想如下(仍然考虑n个任务,m个执行单元的情况):
(1) 对集合中每一个等待分配的任务T,分别计算出分配该任务到m台机器上的最小完成时间,这就得到了一个n×m的MCT矩阵。
当需要调度的任务集合非空时,反复执行以下操作直至集合为空:
(2) 利用MCT矩阵,对集合中每一个等待分配的任务分别找到能够最短时间完成该任务的执行单元及最短完成时间,在所有的最短完成时间中找出最小的最短完成时间对应的任务a,设其对应的主机为b,把任务a分配到机器b上。
(3) 从任务集合中把任务a删除,同时更新MCT矩阵。
2.2 染色体的编码与解码
染色体的编码形式有很多种,可以采用直接编码(直接对子任务的执行状态编码)或者间接编码。本文采用间接编码方式,对每个子任务占用资源编码。染色体的长度等于子任务的数量,染色体中的每一位都是正整数,每一位的位置编号代表子任务的编号,而该位置上的正整数值代表该子任务所占用资源的编号。假设有10个子任务,3个可用资源,则染色体串长为10,每个基因的值则为随机产生的3个资源的编号,则可以随机产生了下面的一个染色体编码:
{2,1,3,2,2,3,1,1,3,1}
这个染色体代表第一个任务由第二个资源上运行,第二个任务由第一个资源执行,以此类推,第十个任务由第一个资源执行。染色体以数组形式存放。
产生了一个染色体后,还必须对其进行解码,得到不同资源上任务的分布情况。将任务按照占用的资源分类,生成多组按照资源编号分类的任务序列,每个序列的编号就是某一个资源的编号,序列中的元素就是在该资源上执行的任务,这样我们就得到了所有任务在多个资源上运行的分布情况。以上面的染色体为例,解码后产生3个资源的任务序列:
R1:{2,7,8,10} R2:{1,4,5} R3:{3,6,9}
这样就可以计算出每个资源完成该资源上分配的所有任务花费的时间,最大花费时间即为时间跨度。
2.3 初始种群生成与适应度函数
在网格环境下,对任务调度的实时性有较高的要求,为提高算法收敛的速度以及改善算法的结果,要求初始种群既具有随机性的个体,又具有一些比较优秀的个体。本调度算法是在Min-min算法基础上,采用遗传算法对其性能进行提高,又可以避免单独采用遗传算法对大规模任务资源匹配的低收敛性。我们可以先将用Min-min算法产生的染色体作为初始种群的优秀个体,再随机产生其他个体。
遗传算法在进化搜索中基本不利用外部信息,仅以适应度函数为依据,利用种群中每个个体的适应度值来进行搜索。因此适应度函数的选取至关重要,直接影响到遗传算法的收敛速度以及能否找到最优解。由于网格调度的目标是时间跨度尽可能小,因此适应度可定义为:
fitness(i)=1/makespan(i)
即染色体i的适应度值等于该染色体的时间跨度的倒数。若时间跨度越小,则适应度值越大,被选择的可能性越大。
2.4 个体选择
选择操作是决定父代种群中哪些个体,以及能以多大可能性被挑选来复制或遗传到下一代的进化操作。选择算子以对个体的适应度评价为基础,其主要作用是对搜索提供导向:挑选最优秀个体,使算法避免无效搜索且能快速搜索到问题的最优解。
假设本算法的种群大小为popsize,为了保留优秀个体,先选择Min-min算法产生的个体和父代中的最优个体,其他的popsize-2个个体采用轮盘赌法[5]进行选择。个体的选择概率为:
Pi=fitness(i)/∑fitness(j)
需要进行popsize-2轮选择。每一轮产生一个[0,1]均匀随机数,若该数位于某个体累积概率下的那个区间,则选择该个体。
2.5 交叉与变异
交叉的目的是为了在下一代产生新的个体,通过交叉操作,遗传算法的搜索能力能够得以飞跃地提高。这里的交叉算子采用多点交叉,对于m个交叉点的多点交叉,随机选择m个交叉位置,在交叉点之间的变量间续地相互交换,产生两个新的后代,但在第一位变量与第一交叉点之间的一段不做交换,交叉点的个数根据染色体的长度进行选择。多点交叉具有很强破坏性,可以促进解空间的搜索。
变异本身是一种局部随机搜索,与选择操作结合在一起,保证了遗传算法的有效性,是遗传算法具有局部的随机搜索能力,同时使得遗传算法保持种群的多样性,以防止出现非成熟收敛。
这里变异算子实质上就是将某个子任务迁移到另一个资源上执行,为了防止某个子任务在迁移后,执行的时间增大而造成种群退化,规定迁移后子任务占用的资源不是随机产生,而是在除了该子任务目前占用的资源外的资源集合中,选择使该子任务执行时间最短的资源,将其迁移到该资源上执行。
2.6 算法流程
(1) 随机产生n个任务,m个资源,根据任务的任务量大小和资源的计算能力生成一个n×m的初始MCT矩阵。
(2) 根据Min-min算法生成一条对应该调度的染色体。
(3) 随机产生大小为M的初始种群,根据每个资源上的子任务的执行序列,计算每条染色体的适应值。
(4) 选择染色体进行交叉操作和变异操作,计算新生成染色体的适应值,生成新的种群。
(5) 判断是否满足遗传算法的终止条件,如果满足,则停止计算,输出最小时间和对应的染色体;如果不满足,则返回(4)。
3 仿真结果与分析
本文的实验是对gridsim、遗传算法、Min-min算法深入研究的基础上进行的,任务的长度范围、资源的执行能力范围、任务分配给某一资源的执行时间等是模仿gridsim计算得到的,数据跟现实的情况比较相似。该算法用到的主要参数有:解的群体规模为20,交叉和变异概率分别为0.8和0.2,任务个数为表2中的几种,资源个数为10,算法终止条件设为到达一定的进化终止代数,最大进化代数设为100,如果算法连续20代没有找到更好的解我们则认为算法基本收敛。
图1描绘了三种算法时间跨度随任务数大小的变化曲线。从图中我们可以看出:改进GA相对于Min-min算法在性能上会普遍有所提高;对于GA,当任务数较少时(小于40个),性能对于Min-min算法也会提高,较小还高于IGA,随着任务数的增加,性能会逐渐下降,甚至还低于Min-min算法。所以GA不太适合用于大规模的网格任务调度,而本文提出的这种改进遗传算法对网格任务调度普遍适用。
4 结束语
用遗传算法和Min-min算法作为网格任务调度算法已经得到广泛的应用。当规模较小时,遗传算法被证明是一种最有效的启发式调度算法,但随着资源数和任务数的不断增加,遗传算法的性能逐渐降低,到达一定规模时甚至还低于Min-min算法,这样不仅性能得不到提高,而且还会增加调度时间。本文提出一种将Min-min算法和遗传算法相结合的改进遗传算法,这种算法对于大规模任务调度性能也比较高。
由于本文在设计时没有将经济因素考虑在内,下一步的工作可以将开支预算与时间期限考虑在内,再结合本算法,可用于基于经济模型的网格任务调度。另外,模拟退火算法局部搜索能力比较强,遗传算法全局搜索能力较强,将两者结合搜索能力会尽一步提高,性能可能会有所提高。
参考文献
[1]Foster I,Kesselman C.The Grid-Blueprint for a New Computing Infra-structure.Morgan Kaufmann Publishers,1998.
[2]Abraham A,Buyya R,Nath B.Nature’s heuristics for scheduling jobs on computational grids.In The8th IEEE International Conference on Advanced Computing and Communications India,2000.
[3]Braun T,Siegel H,Beck N.A comparison of eleven static heuristics for mapping a class of independent tasks onto heterogeneous distributed computing systems.Journal of Parallel and Distributed Computing,2001,61(6):810-837.
[4]Carretero J,Xhafa F.Using genetic algorithms for scheduling jobs in large scale grid applications.In Workshop of the European Chapter on Metaheuristics EUME2005,Metaheuristics and Large Scale Optimiza-tion.Vilnius,Lithuania,2005(5):19-21.
改进的DSM算法 篇7
建筑行业一直都是我国的支柱产业,为国民经济增长和社会发展做出了重要贡献。尽管建筑行业在国民经济中的影响力和投资总量很大,但我国建筑业长期以来一直是一个劳动密集、粗放经营的行业,管理水平和科技贡献率不高。当今激烈的市场竞争环境下,建筑工程项目逐渐朝着大型化和复杂化方向发展,业主对建筑项目设计的周期、成本和质量要求越来越高,建筑工程设计成为建筑工程项目发展的瓶颈的现象越来越明显,研究表明,仅占整个项目费用3%~10%的建筑工程设计过程是影响整个项目成败的关键因素[1]。BEDE的研究报告也指明建筑工程领域最主要的问题是缺乏对设计信息的有效管理。因此对建筑工程设计进行有效的管理是非常必要的,本文将基于设计信息流的产品开发过程建模技术、设计结构矩阵运用于建筑设计领域,提出了基于设计活动间的信息耦合关系进行协同设计研究。
现代建筑产品的开发需要大量不同学科专业的设计师共同参与做出大量的决策,涉及到建筑、结构、给排水、暖通空调、电气等多学科,需要多工种的交叉和协调。各个学科自成体系,但又密切相关,如图1。因此在建筑工程设计中,各专业工种之间的协调管理,是关系建筑工程质量优劣的重要因素,各专业之间必须相互协调,加强配合,才能使所设计的建筑使用方便,功能合理,设计质量才能得以保证。
图1表示了普通办公楼设计中常见的12个设计活动,分别属于5个专业领域,各个活动之间的循环迭代的信息流动关系如图所示。对于大型的建筑工程设计过程而言,每个专业均是由几十甚至上百个活动组成,其信息流动的复杂程度就更加难以想象。同时,由于在设计过程中各专业设计人员从自身角度考虑问题,也不可避免地容易引起数据冲突,为了在设计过程中尽早地解决各专业之间的矛盾,保证各专业设计人员及时地交换信息,消解冲突,必须对各专业进行协调管理。
2设计结构矩阵
1981年,Steward首次将设计结构矩阵(Design Structure Matrix, DSM)运用到复杂系统的识别、分析和管理中[2],如图2(a) 所示,DSM采用可视化的方法分析价值流,能更好地描述产品开发流程中的关键动态特性,改善信息流、优化任务排序并减少返工[3,4]。
DSM是一个n阶方阵,用于显示矩阵中的各个元素的交互关系,如图2(b)所示,“×”表示所在行列元素间存在信息的交流与反馈,若“×”在下三角表示信息流的前向传递,在上三角则表示信息反馈。
DSM理论模型作为一种基于矩阵的、紧凑的表达模型,能站在全局的角度,采用可视化的方法反映任务之间关系(信息流)并分析信息流,图2(c)表示采用聚类的方法对过程结构进行优化。DSM建模方法由于矩阵本身不受任务数目限制,并且易于使用计算机编程计算,具有良好的可操作性和稳健性。
根据领域的不同,DSM矩阵可以分为4种类型 [5],包括产品架构、组织架构、过程架构以及综合产品、组织、过程的多领域模型。其中组织架构DSM模型的分析主要是通过聚类的方式,把信息交流需求最大的成员分为一组,将矩阵变换成为成员之间具有高度交互性的类———系统团队。矩阵变换的目的是使类内部具有高耦合度,而类外具有尽可能低的耦合度。通过关注不同成员的沟通需求,从而得到有效的组织设计模式。
3基于 DSM的建筑工程协同设计
3.1 传统建筑工程设计的过程及其局限性
传统的建筑设计一般采用串行设计,即“抛过墙”式建筑产品设计模式,图3(a)为传统建筑设计过程,3(b)为传统建筑设计组织结构图。由图可以看出,传统的设计模式从时间上和功能上把各学科的专职人员彼此孤立开来,存在一系列问题:信息流动是单向的,下游的设计结果不能及时反馈给上游进行设计评价和修改,项目集成性差;设计信息交流不畅、沟通困难而出现的潜在危险,往往在施工过程中才能发现;设计修改频繁,设计质量难以得到保证:建筑工程设计周期长,项目开发成本高,建筑质量受到影响等问题。
设计过程中信息的管理是目前建筑设计企业必须面对的一个难题,在当今知识经济社会,沟通和协调比命令和控制更为重要,据权威机构研究表明,良好的信息沟通和协调可以减少工程建设费用的20%左右[6]。因此引入新方法、新工具对建筑设计过程进行管理是非常必要的。
3.2 建筑工程设计初始 DSM 模型的建立
本文采用图1表示的普通楼宇设计工程中常见的12项设计任务为例,把各设计活动间的信息流关系用DSM矩阵表示出来,如图4,然后采用DSM聚类规则进行聚类分析。
3.3 DSM 聚类基本原则
DSM聚类原则以下列步骤展开[7]:
(1)设计优化的目的是使DSM尽量成为下三角矩阵。
(2)根据DSM,若矩阵中某一行全为零,则说明对应该行的设计行为不需要其他设计行为提供信息,因此应尽可能早地执行,将这些设计移到DSM的顶端。每次移动一个学科,且需将其行列及相关标记一起移动。移动结束,再对矩阵其他设计重复进行步骤(1),直到再无这样的设计。
(3)根据DSM,若矩阵中某一列全为零,则说明对应该列的设计行为没有对其他设计行为提供信息,因此应尽可能晚地执行,将这些专业设计移到DSM的底端。每次移动一项专业设计,且需将其行列及相关标记一起移动。移动结束,再对矩阵其他专业设计重复进行步骤(2),直到再无这样的专业设计活动。
(4)如果经过步骤(1)、(2) DSM中再无未调整的专业设计,则矩阵已经达到最优化;否则,剩余的专业设计必定包含信息循环(至少一个)。
(5)找出信息循环,使用所谓的“路径搜索”方法。在该方法中,从某一专业设计开始,向前或向后跟踪信息流,直到第二次追溯到同一个专业设计,这之间的所有专业设计构成一个信息流循环。
(6)将简单循环中的专业设计合并起来,并用另一代表专业设计代替,并重新开始步骤(1)的操作。
对于小型矩阵,只要通过一系列的行列变换就可以获得新的DSM优化矩阵,对于大型的矩阵则可以通过相关智能算法如遗传算法等获得新的优化结果矩阵。
由于建筑工程设计各活动间的耦合性较强,所以本案例中没有空行空列, 可以直接从步骤(3)开始,根据图4初始信息流,利用以上规则进行优化,得到新的DSM矩阵,如图5所示。
不难看出,通过DSM聚类优化,使得原来隶属于不同专业领域的设计活动之间复杂的设计迭代关系转化为4个工作团队之间的关系,其中总体规划设计和结构选型设计组成一协同设计团队,在设计的初期就考虑到了建筑设计与结构设计间的关系避免了传统设计过程中结构设计发现建筑设计不合理而引起的设计大返工。同样,功能要求和局部细化设计人员组成协同设计团队;局部细化、空调系统设计、管道通风设计、楼板梁柱墙体设计组成一协同设计团队;梁柱墙体设计和电气装配设计组成以协同设计团队。其中局部细化、梁柱设计、墙体设计同时属于两个协同设计团队,说明需要加强这些活动和两个团队间的协调沟通。通过DSM聚类,可以首先在团队内部进行信息交互,并行协同地进行设计;然后再以团队为单位进行更高层面的信息交互,可以减少由于不同专业领域间耦合带来频繁更改,返工等影响,既缩短了设计周期,减少了返工成本,又保证了建筑工程设计质量。
因此,笔者认为,在建筑工程设计企业,有必要建立协同设计团队,专门负责跨专业、跨部门、耦合关系强的设计活动间的协调与沟通,并以正式的组织形式确定下来,避免设计人员只为参会而来的临时心理,直到建筑工程项目设计工程结束。
4结 语
目前,建筑工程设计由于专业的分割形成了一个个的“学科孤岛”,本文采用DSM分解聚类方法,确定任务之间的耦合关系,通过对设计任务重新规划,建立协同设计团队,让参与整个系统设计的全部人员都能了解到其他专业的约束要求和优化目标,使设计从项目初始阶段就具有全局观,减少设计过程中由于设计冲突而导致的频繁设计更改,提高设计效率。
摘要：在分析当前我国建筑工程设计现状及存在问题的基础上,提出利用设计结构矩阵(Design Structure Matrix,DSM)对建筑工程设计活动进行聚类分析,通过对设计任务进行重组,形成协同设计团队进行并行设计,从而减少设计过程中由于设计冲突而导致的频繁设计更改,提高了设计效率。
改进的DSM算法 篇8
关键词：禁忌搜索算法,最短路径优化算法,智能路由,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) 将禁忌搜索算法与算法进行混合, 拓展算法的适用域, 提高算法的性能。
改进的DSM算法 篇9
遗传算法采用了基于种群的全局搜索方法,它有很大机会获得全局最优解,因此笔者提出了一个改进隐马尔可夫模型(HMM)的方法,即把遗传算法应用到Baum-Welch算法B值的优化当中,实验结果表明该方法产生的模型识别率较高。
1 遗传算法
遗传算法[2]模拟自然界优胜劣汰的进化现象,把可能的解编码成向量———染色体,把搜索空间映射到遗传空间。它通过不断计算各个染色体的适应度值,从而选择最好的染色体,来获得最优解。
遗传算法的3个主要算子是选择、交叉和变异,操作的对象为个体,它们构成了整个遗传过程,使遗传算法具有其他传统方法所没有的优良特性。
2 HMM
笔者采用的HMM模型状态数为5,码本的大小选为128,模型参数用λ=(A,B,л)来表示,状态转移矩阵为A=[αij],输出分布矩阵为B=[bjk],初始状态分布矩阵为л=[лi],观测序列为O=O1,O2,…,OT。
在HMM识别中,训练数据用来训练模型,测试数据用来识别模型。其中,训练过程很重要。传统的训练方法是Baum-Welch算法,笔者引入了遗传算法来优化B值,使最终得到的系统模型最优。
3 用遗传算法改进HMM
传统的离散HMM(DHMM)训练算法是先初始化DHMM,即初始化状态转移矩阵A、输出分布矩阵B和初始状态向量л,然后用Baum-Welch算法进行迭代训练,找到最优的HMM。全局寻优是遗传算法的一个主要功能,笔者把遗传算法与Baum-Welch算法结合起来进行训练,得到最终较优的模型。
3.1 遗传算法的步骤
大体来说,遗传算法主要由以下4步组成[2]:第一步随机地建立初始群体;第二步计算各个体的适应度;第三步根据遗传规律,利用复制、交叉和变异3种算子产生新群体;第四步反复执行二、三步后,一旦达到终止条件,选择最佳个体作为遗传算法的结果。
3.2 遗传算法的设计
1)编码。由于B矩阵中每一行元素之和为1,为保证每次产生的新一代种群的个体参数仍满足此条件,需要做归一化的工作。这里每一个个体对应于一个HMM,染色体对应于模型的参数B,编码采用二进制编码方法。
2)适应度函数。DHMM的训练中希望训练数据对模型的似然概率越高越好,这里个体的适应度用各个训练样本的对数似然概率来表示
式中,O(k)表示用于训练模型的第k个观测序列,P(O(k)|λ)为似然概率。
遗传算法中,个体的适应度由适应度函数[3]来度量,必须保证越符合目标的个体其适应度越高。
3)选择策略。实验中采用了轮盘赌选择方法[4],由于该方法还要求适应度为正值,所以需要对适应值做进一步的调整使其为正值。选择策略的选取直接影响着算法的收敛,最常用的是基于适应值比例的选择和基于排名的选择。
4)遗传算子。笔者采用的是多点交叉,基本位变异,种群的大小设为100,杂交的概率Pc取0.8,变异的概率Pm取0.005。遗传算子包含杂交算子和变异算子。某种程度上,杂交算子相当于一个局部搜索操作,它产生父代附近的2个子代,而变异算子则使得个体能够跳出当前的局部搜索区域,二者的结合正好体现了遗传算法的优化所在。
5)终止准则。实验中采用的是预先设置最大进化的代数作为终止准则,最大进化代数设置为500。
4 实验结果及讨论
笔者所用HMM为自左向右无跨越模型,每个单词的模型为5个状态,观测符号M为128。用10个孤立词16个人的发音来做实验,每个人每个词发音3次,其中9人的发音用于训练模型,7人用于识别,故每个词的HMM参数使用27个序列来训练,21个序列来做识别。笔者用软件仿真实现了遗传算法以及Baum-Welch算法,优化了HMM,得到了较高的系统识别率。
传统算法和改进后算法所得识别率的比较,见表1。从中可以看出改进后算法比传统的训练算法识别率有所提高。特别是在信噪比(SNR)变低时,改进后算法的识别率比传统算法识别率提高更多一些,这些可作为进一步研究抗噪语音识别的基础。
(%)
参考文献
[1]尹星云,王洵,董兰芳,等.隐马尔可夫模型设计人脸表情识别系统[J].电子科技大学学报,2003,32(6):725-728.
[2]王晓勇.基于遗传算法和神经网络的故障诊断研究[J].微计算机信息,1998,34(2):219-221.
[3]张思才,张方晓.一种遗传算法适应度函数的改进方法[J].计算机应用与软件,2011,23(2):108-110.