遗传算法存在问题分析（共9篇）
遗传算法存在问题分析 篇1
1遗传算法存在问题
1.1早熟现象
遗传算法实质上就是在基因上进行的一系列的相关操作, 即选择、交叉和变异操作,通过选择操作,将本代种群中适应度较高的个体遗传到下一代,交叉操作可以实现基因的重组,探索适应度更高的个体,变异操作主要实现基因的突变。通过一系列的操作之后,按照进化论中的优胜劣汰原则,较好的个体逐渐地被进化,较差的个体逐渐地被淘汰,得到遗传算法所寻找的最优解。随着遗传算法的进行,部分较高适应度的个体将会保留下来,如此进行下去,种群中个体大部分的基因将会趋于一致,种群中也会存在很多相似的个体,减小了种群的多样性。从遗传理论上分析,遗传算法能够保证操作的精确度,而且算法中的群体规模可以随机选取,通过一系列操作之后,种群中个体的优秀基因肯定能够遗传到下一代,种群最终能够得出最优解。但实际上,遗传算法实现是有时间限制的,而且实现资源也是有限的,所以实现过程中要考虑到群体规模的大小,遗传算法中的这些限制可能会使群体中的个体过早地丧失多样性。
综上所述,遗传算法的早熟现象指在遗传算法实现过程中,丧失了种群个体的多样性,使个体中的基因趋于一致,导致算法的搜索停止在局部,无法实现在全局的搜索,最终得到的是局部最优解。
1.2重复基因问题
遗传算法在实现时,编码方案如果采用了实数编码,容易出现重复基因的问题。重复基因主要是指在进行交叉操作的两个染色体中存在相同的基因,选择交叉点进行交叉之后,产生的新的染色体中有两个相同的基因。
以自动组卷问题为例,重复基因问题就是指在同一套试卷中有完全相同试题的出现。在实现遗传算法时,首先要进行初始化群体,初始群体中每个个体的产生都是随机的,所以每个个体选中的试题也是随机的,不同的个体可能会选中同一道试题。当两套试卷进行交叉操作时,如果两套试卷中含有相同的试题,而且该试题在试卷中的位置不同,或是试题在两个个体的基因位不同,交叉点选在两个基因位之间,交叉操作之后产生的新个体中必定会出现两个相同的基因。
2早熟现象原因分析及解决
遗传算法在实际应用中经常出现早熟现象,出现早熟现象的原因主要有以下三点:
1) 群体规模
群体规模主要是指种群中的个体数量,其取值的大小影响着遗传算法早熟现象的发生。当群体规模取值较小时,虽然算法的收敛速度会很快,但是生成的具有较高适应度的个体的数量会很少,容易造成早熟现象的发生;当群体规模取值较大时, 保证了参加遗传算法的群体的多样性,能够产生具有较高适应度的个体,增大了得到全局最优解的可能性,但是增大了算法的计算量,降低了收敛速度。综合考虑,群体规模的取值可以在50-100之间。
2) 选择操作
在自然界中,选择过程遵循着优胜劣汰的规律,在遗传算法中,这种规律是通过选择算子来实现的。选择操作主要是在本代种群中选择适应度较高的个体保留到下一代,保证遗传算法得到最优解。选择操作通常使用轮盘赌选择方法,增大了较高适应度值的个体被遗传的概率,但是这样有可能淘汰掉本代种群中的最佳个体,也有可能本代中的最佳个体通过交叉和变异操作之后,以前良好的基因组合被破坏,容易出现早熟现象。
3) 交叉概率和变异概率
在遗传算法中,通过交叉和变异的操作,保证了种群个体的多样性。传统的遗传算法中,交叉概率和变异概率采用了固定值。如果交叉概率取值较大,提高了交叉操作的速度,同时也破坏了原来个体,算法的寻优速度就会降低;如果交叉概率取值较小,会降低遗传个体的破坏性,但是算法可能会过早地得到局部最优解。如果变异概率较小,通过变异操作产生的新个体的数量也会变小,随着遗传操作的进行,适应度较高个体就会在群体中快速繁殖,从而出现局部最优解,出现早熟现象。因此,在遗传算法实现中的交叉和变异概率采用自适应遗传算法中的动态交叉概率和动态变异概率,这样会降低早熟现象出现的概率。
3重复基因问题解决
解决重复基因问题的传统方法有两种:
第一种方法是在创建数据表时,在试题表中增加一个字段,在初始化群体时,用该字段标志试题是否被某个个体选中, 已经被选中的试题不能再次被选中,这样在种群个体中避免了重复题的出现。但是这样做违背了初始化的随机性原则。
第二种方法是移动交叉点,即在进行交叉时,先判断两个个体中是否有重复基因出现,如果有重复基因的出现,将交叉点选在两个重复基因的基因位区间之外,如果区间选在了重复基因的基因位之内,则通过左移交叉点,将交叉点移到两个重复基因的基因位范围之外。
使用移动交叉点的方法存在以下问题:一是交叉操作的交叉点具有不确定性,如果控制交叉点的位置,则对交叉算子产生一定的破坏性;二是在本次遗传操作中,通过移动交叉点的位置避免了重复基因的出现,但是当产生的新个体再次进行交叉操作时,可能还会出现重复基因,所以此种方法对以后的交叉操作没有作用,在以后生成的子代之间进行交叉时,重复基因问题还会出现。
在本文中,根据遗传学中等位基因的知识,提出了一种等位基因法解决交叉操作中重复基因问题,在进行交叉操作时, 判断出现重复基因之后,将出现的
的重复基因换到两个个体中相同的基因位,然后再进行交叉操作,这样就避免了新生成的子代中出现重复基因,可以不用考虑交叉点的位置,在任何交叉点都可以进行交叉操作,等值基因法对个体的适应度的值也没有影响,解决了重复基因的问题。
4结束语
本文主要介绍了遗传算法中经常出现的早熟现象和重复基因问题,从多方面分析了出现这些问题的原因,归纳了传统的解决办法,提出了新的解决办法,通过这些办法,能有效地降低遗传算法早熟现象和重复基因问题的出现概率。
双目标瓶颈指派问题的遗传算法 篇2
关键词 双目标； 瓶颈指派问题； 遗传算法； Pareto最优解
中图分类号 O221.6 文献标识码 A
1 引 言
经典指派问题是一类特殊的组合优化问题，是指将n项工作分配给n个工人去完成，且每个工人只能完成一项工作，每项工作只能由一个人来完成，不同的工人完成每一项工作的费用是不同的，从而求出最优指派. 所谓的最优是指使总体费用最大或者总体用时最小.
指派问题最早由Votaw和Orden提出[1]， 1955年，Kuhn给出了解指派问题的匈牙利算法[2]， 从此指派问题得到了真正的发展. 此后的几十年，指派问题的解法日趋成熟，出现了隐枚举法、分支定界法和割平面法等，但是用到最多的还是匈牙利法. 与此同时，还出现许多经典指派问题的变形，如瓶颈指派问题[3]、平衡指派问题[4]、半指派问题、多准则指派问题、分数指派问题、二次指派问题[5]、随机指派问题[6，7]、模糊指派问题[8]以及带负荷约束的指派问题[9]等，有关这些问题的介绍可参阅综述文章[10]及其参考文献.
指派问题在生产和服务系统中有着广泛的应用. 例如在咨询服务行业，决策者或者管理人员根据咨询师以往的工作表现和顾客反馈，可以给出不同咨询师完成某项工作的合适性，即费用. 经典指派问题的目标是要使这项费用最大化. 本文将在此基础上，同时考虑咨询师（工人）对工作的排名偏好，建立双目标瓶颈指派问题的模型，进而将此问题转化为单目标规划问题，并设计遗传算法来求解.
同样，模型（4）的最优解也是问题（2）的Pareto最优解. 问题（2）到模型（4）的转化方式也是处理多目标优化的常用方法.模型（3）与模型（4）相比其优势在于约束条件相较于问题（2）没有增加，问题的规模没有增大，利用我们给出的编码、交叉和变异算子可以保证个体的可行性.
参考文献
[1] DF VOTAW， A ORDEN. The personnel assignment problem[C]//Symposium on Linear Inequalities and Programming. Scoop 10， US Air Force， 1952： 155-163.
[2] H W KUHN. The Hungarian method for the assignment problem[J]. Naval research logistics quarterly， 1955， 2（1/2）： 83-97.
[3] J GORSKI， K KLAMROTH， S RUZIKA. Generalized multiple objective bottleneck problems[J]. Operations Research Letters， 2012， 40（4）： 276-281.
[4] L LIU， H MU， Y SONG， et al. The equilibrium generalized assignment problem and genetic algorithm[J]. Applied Mathematics and Computation， 2012， 218（11）： 6526–6535.
[5] A A PESSOA， PM HAHN， M GUIGNARD， et al. Algorithms for the generalized quadratic assignment problem combining Lagrangean decomposition and the Reformulation-Linearization technique[J]. European Journal of Operational Research， 2010， 206（1）： 54-63.
[6] PA KROKHMAL， PM PARDALOS. Random assignment problems[J]. European Journal of Operational Research， 2009， 194（1）： 1-17.
[7] F LI， LD XU， C JIN， et al. Random assignment method based on genetic algorithms and its application in resource allocation[J]. Expert Systems with Applications， 2012， 39（15）： 12213-12219.
[8] PN TAPKAN， LZBAKIR， A BAYKASOGLU. Solving fuzzy multiple objective generalized assignment problems directly via bees algorithm and fuzzy ranking[J]. Expert Systems with Applications， 2013， 40（3）： 892-898.
[9] 林浩，林澜. 有负荷约束的指派问题[J]. 经济数学，2013，30（1）： 17-21.
[10]D W PENTICO. Assignment problem： A golden anniversary survey[J]. European Journal of Operational Research， 2007， 176（2）： 774-793.
[11]葛悦. 模糊环境下若干网络优化问题的模型及其算法研究[D]. 哈尔滨：哈尔滨工业大学理学院数学系， 2012.
[12]D Z DU， P M PARDALOS. Minmax and Applications[M]. Netherland： Kluwer Academic Publishers， 1995.
[13]I H TOROSLU， Y ARSLANOGLU. Genetic algorithm for the personnel assignment problem with multiple objectives[J]. Information Sciences， 2007， 177（3）： 787–803.
[14]S Y LIN， S J HORNG， T W KAO， et al. Solving the bi-objective personnel assignment problem using particle swarm optimization[J]. Applied Soft Computing， 2012， 12（9）： 2840-2845.
[15]A ZINFLOU， C GAGNE， M GRAVEL. GISMOO： A new hybrid genetic/immune strategy for multiple-objective optimization[J]. Computers & Operations Research， 2012，39（9）： 1951-1968.
遗传算法求解背包问题 篇3
关键词：遗传算法,背包问题
1.背包问题
背包问题 (Knapsack Problem, 简称KP) 是运筹学中一个典型的优化难题, 在预算控制、项目选择、材料切割、货物装载等实践中有重要应用, 并且还常常作为其他问题的子问题加以研究。随着网络技术的不断发展, 背包公钥密码在电子商务中的公钥设计中也起着重要的作用。背包问题的数学模型为:
式中, n为物品的编号;m为资源的编号;cj为第j个物品的受益量;bi成为第i种资源的预算;aij为第j个物品占用第i种资源的量;xj为0-1决策变量 (当物品j被选择时xj=l, 否则xj=0) 。
KP的语言描述可以这样:现有j (j=1, 2, …, n) 个物品, 每个物品将会消耗m种资源aij (i=1, 2, …, m) , 如果将物品j装人背包将会获益cj, 与此同时, 要求所有装入背包的物品消耗的资源I不能超过bi。
背包问题可以衍生出一系列与之相关的优化问题, 如有限背包问题 (物体可具有相同价值和重量但数量是有限的) , 无限背包问题 (具有相同价值和重量的物体数量可以是无限的) , 多背包问题 (将物体装入多个容量不同的背包) 等。本文中所指背包问题如无特殊说明, 均指m=1的简单0/1背包问题。
2.应用遗传算法求解0/1背包问题
遗传算法作为一种通用的优化方法, 在组合优化的各个分支都有大量的应用。这里提供的程序是用来求解0/1背包问题的。但是稍加扩展即可用于其他问题。遗传算法的内容非常丰富, 但是这里只是使用了标准的遗传算法以利于和其它方法比较。算法根据物品数量决定基因长度。基因某一位为1表示装入此物品, 为0表示未装入此物品。由于存在约束条件, 物品总重量不能大于一给定值, 所以必须对生成的基因进行控制。有多种方法可以实现这个日的。例如:设定一阈值, 将适应度函数值大于此阈值的基因中对应密度小的位设为1。也可以将适应度函数作相应的修改。加入惩罚项, 使得当物品过多时适应度函数减少。本算法采用第二种方式。对于0/1背包问题利用简单遗传算法求解的基本步骤如下:
1.编码:
0/1背包问题可以直接利用变量xi进行编码, 即:x=[x1, x2…xn]。
2.适应度函数:
其中ρ (t) 为阙值函数, 判断是否超重。K>0为罚函数权重, 表示惩罚力度。
其直观的解释为;当背包中放置物品超出所允许的重量后, 处以超重部分k倍原价值的惩罚。考虑到适应值最高的基因未必满足背包容量要求, 所以算法中从每代保存适应值最高的基因时进行判断, 只有当其满足背包限制条件时才被作为适应值最高的予以记录。
3.遗传算子:
选择:采用轮盘赌的方式进行选择。在本算法中, 将各基因的适应值事先作处理:
以防止适应度函数值出现小于零的情况, 并且可以在一定程度上防止适应值差别过大时丢失低适应值基因的有用信息。
交叉:采用单点交叉方式, 随机选取一点作为基因的交叉点, 交叉概率Pc=0.8。
变异:采用一个较小的值如Pm=0.05。整个过程如图1.1所示。
4.主要代码:
3.总结
遗传算法已经在背包问题的求解上取得了大量成果。运用简单遗传算法求解背包问题时, 若问题的规模不大也能够得到最优解或近似最优解, 但当需求解的背包问题的规模比较大时, 用简单遗传算法得不到较理想的结果。遗传算法在运行早期个体差异较大, 后代产生的个数与父个体适应度大小成正比, 因此在早期容易使个别好的个体的后代充斥整个种群, 过快的收敛于某一局部极值处, 造成甲熟 (Premature) ;而在遗传算法后期, 适应度趋向一致, 优秀的个体在产生后代时, 优势不明显, 从而使整个种群进化停滞不前。
参考文献
[1]玄光男, 程润伟.遗传算法与工程优化[M].北京:清华大学出版社, 2004
[2]王凌, 智能优化算法及其应用[M].北京:清华大学出版社, 2001
[3]刘勇, 康立山.非数值并行算法--遗传算法[M].北京:科学出版社, 2003
[4]刘西奎, 李艳, 许进.背包问题的遗传算法求解[J].华中科技大学学报 (自然科学版) , 2002, (06)
基于遗传算法的人工智能分析 篇4
关键词：遗传算法；人工智能；全局运动估计；应用分析
中图分类号：TP18 文献标识码：A 文章编号：1007-9599 （2013） 01-0240-02
所谓人工智能，就是人工的方法通过计算机实现智能化功能，或者说是人们使用机器模拟人类的智能。由于人工智能是在机器上实现的，所以又称为机器智能。从另一个角度来看，人工智能是研究怎样使计算机来模仿人脑从事的推理、证明、识别、理解、设计、学习、思考、规划及问题求解等思维活动，来解决人类专家才能处理的复杂问题。人工智能的算法很多，包括遗传算法、进化算法、蚁群算法和专家系统、神经网络等。
1 遗传算法
遗传算法的思想是先确定编码方案，对待寻优的缺陷特征参数进行编码，按一定规模初始化种群，种群中的每一个各体就代表了一个可能的解；然后根据适应度值函数计算每一个各体的适应度值并依此决定遗传操作。根据预先确定好的种群选择方案，按一定的概率对种群进行交叉、变异得到下一代，直到遗传算法的终止条件得到满足。与传统的优化算法相比，具有的优缺点如下：
1.1 遗传算法优点。不是从单个点，而是从多个点构成的群体开始搜索。之所以说是从多点而不是从单点出发，那是因为整个算法的开始是从一个初始种群开始搜索演练最优解，是从多个点开始搜索进化寻找，这样的做的一个好处是避免局部寻找最优解，从任一解出发，按照某种机制，以一定的概率在整个求解空间中探索最优解。由于它们可以把搜索空间扩展到整个问题空间，因而具有全局优化性能。同时也缩短了整个搜寻额时间，整体上效率更高、结果更接近最优解。
实现简单，没有复杂的数学计算，在算法中，一般都有大量且复杂的计算作为整个算法的支撑，同时数学计算也是一步比较耗资源和时间的操作，然后在遗传算法中，在搜索最优解过程中，只需要由目标函数值转换得来的适应度信息再加上简单的比较，而不需要导数等其它辅助信息，操作流程也比较简单，没有过多的转换控制操作，中间也没有多少中间变量，算法具有较强的自适应性。
搜索过程不易陷入局部最优点。目前，该算法已渗透到许多领域，并成为解决各领域复杂问题的有力工具，因为是在整个求解空间中探索最优解，所以，基本上不会陷入局部最优解中去。
在遗传算法中，将问题空间中的决策变量通过一定编码方法表示成遗传空间的一个个体，它是一个基因型串结构数据；同时，可以将目标函数值转换成适应值，它用来评价个体的优劣，并作为遗传操作的依据。
但是，传统的遗传算法同样拥有缺陷。
1.2 遗传算法缺点。首先，传统的遗传算法编码和解码比较复杂，因为传统的遗传算法的染色体是用二进制编制的，一个染色体就是一串0和1组成的位串或是字符串，在进化前需要做复杂的编码工作，而在得到最优解后还要做复杂的解码工作，比较繁琐和复杂，在遗传操作过程中也不易掌控，容易出错；其次，算法对初始种群的选择有一定的依赖性。
2 遗传算法在人工智能领域的应用
遗传算法在人工智能的众多领域便得到了广泛应用[2]。例如，机器学习、聚类、控制（如煤气管道控制）、规划（如生产任务规划）、设计（如通信网络设计、布局设计）、调度（如作业车间调度、机器调度、运输问题）、配置（机器配置、分配问题）、组合优化（如TSP、背包问题）、函数的最大值以及图像处理和信号处理等等。
另一方面，人们又将遗传算法与其他智能算法和技术相结合，使其问题求解能力得到进一步扩展和提高。例如，将遗传算法与模糊技术、神经网络相结合，已取得了不少成果。
因为遗传算法是模拟生物的进化过程的一类人工智能算法，所以，在算法的初始阶段，应该给一个初始种群给算法来进化演练。
因此，第一步是初始化种群，在初始化种群时，种群的大小要设计科学，这样才能最大力度的发挥遗传算法的性能。
在初始化种群后，就要开始进入遗传演练阶段，遗传的第一步操作是对种群的每个个体计算适应度，然后进入遗传演练。
在演练过程中，模仿生物的进化过程，有双亲结合产生下一代个体，为了能够保证种群的多样化和过早的收敛于某一个局部最优解，有了变异操作。
在遗传操作过程中，如果某一代中有个体符合最优解的特征，那么整个演练过程就可以提前结束了，否则，遗传演练会一直进行下去，知道收敛于某一个最优解或是到达最大遗传代数。
3 遗传算法的全局运动估计
运动估计是连续图像运动中图像量化的过程，全局运动一般是指相关相机的运动。一个图像序列全局运动的出现被认为是有意的，例如对于平移、缩放等；或无意的，例如手颤抖或相机摆放不稳等。后者的全局运动容易产生影响视频质量的不利因素，如抖动。从压缩的角度来看，这种易抖动的运动会造成不必要的高比特率，因此需要抑制。视频的稳定化方法意在减少这种采用全局运动估计（GME）方法的视频序列所产生的抖动。
基于特征的方法为保证GME的鲁棒性需要特征提取与选择具有一致性。提取的过程包括识别潜在的兴趣点，基于纹理结构相关标准如角落和边缘，强调区分物理真实对象。然后基于他们的跟踪能力选择较好的特征。跟踪能力的性能取决于后续帧中的弹性变形、闭塞等。因为本身是相对成熟的特征跟踪，在特征提取与选择过程中全球运动估计的鲁棒性至关重要。我们指出，在运动的像素组中出现的信息对应不同的真实结构，如深度不连续，也可以很好的对应相机的运动。这种经典的方法可能涉及潜在信息的损失，同时，选择程序的跟踪能力和异常值滤除能力可能与相机的运动不相关。
通过一种新的遗传算法（GA）的方法，它结合了特征提取与选择的过程。这种方法有效地学习最佳特征，即跟踪过程中的群像素，结果的有效性在全局最大运动估计中得到体现。这种方法与经典的算法不同，事实上我们的做法是基于盲目的结构内容特性，而不是任意的子像素的全局运动评估。这种方法特别适用于视频稳定的过程。
4 展望
根据上述在人工智能方面，基于遗传算法的特征提取与选择在全球运动估计中的应用，我们可以看出通过选择一个合适的适应度函数，直接与估计的鲁棒性进行比较，该方法可以确保视频图像的增强性能，特别是应用于视频稳定。
随着科技的不断发展，更为新颖的人工智能算法在进行全面的发展，其中数据挖掘与网络智能、人工神经元网络和贝叶斯网络数据挖掘是一种从大型数据库或数据仓库中提取隐藏的预测性信息的技术，它能挖掘出数据间潜在的模式，找出最有价值的信息和知识，指导商业行为或辅助科学研究。仿照生理网络结构的非线性预测模型，通过学习进行模式识别。神经网络最早是由心理学家和神经生物学家提出的，旨在寻求开发和测试神经的计算模拟。神经网络是一组连接的输入/输出单元——神经元，其中每个连接都与一个权相对应。贝叶斯信任网描述一组随机变量的联合概率分布，它是用有向的无环图来表示的，联合空间中的每一变量在贝叶斯网中是用节点来表示的，节点的值可以是两值或多值。
这些研究方法将继续使得人工智能的发展更为迅速，并且得到在实际中的广泛应用。
参考文献：
[1]Holland J.Adaptation in Natural and Artificial Systems[M].Michigan：University of Michigan Press，2002.
[2]任江涛，黄焕宇，孙婧昊.基于相关性分析及遗传算法的高位数据特征选择[J].计算机应用，2006，6（26）：1404.
基于遗传算法求解旅行商问题 篇5
旅行商问题是一个典型的、易于描述却难于处理的组合优化问题,并且是一个NP完全难题,其可能的路径数目与城市数目n是成指数型增长的,对n个城市而言,可能的路径总数为(n-1)!。随着n的增加,路径数将按数率急剧增长,即所谓的“指数爆炸”,以n=20为例,即使用每秒一亿次的计算机按穷举搜索法求解,也需700年,所以一般很难精确地求出其最优解,因而寻找出其有效的近似求解算法就具有重要的理论意义。而遗传算法是解决复杂问题的有效方法,被广泛应用于解决旅行商问题。
遗传算法是模拟生物在自然环境中的遗传和进化过程而形成的一种自适应全局优化概率搜索算法。它最早由美国密执安大学的Holland 教授提出,起源于60年代对自然和人工自适应系统的研究。这种算法的主要特点不仅是采用群体搜索策略和可实现群体中个体之间的信息交换,且搜索过程不依赖于梯度信息。它尤其适用于处理传统搜索方法难以解决的复杂和非线性问题[1,2,3]。
1旅行商问题的描述和数学模型
1.1问题描述
旅行商问题可描述为:已知n个城市之间的距离,现有一个人必须遍历这n个城市,并且每个城市只能访问一次,最后又必须返回出发城市。如何安排他对这些城市的旅行次序,可使其旅行路线的总长度最短?
用图论的术语来说,假设有一个图g=(v,e),其中v是顶点集,e是边集,设d=(dij)是由顶点i和顶点j之间的距离所组成的距离矩阵,旅行路线选择问题就是求出一条通过所有顶点且每个顶点只通过一次的具有最小值的路径,最后又必须返回出发城市。
1.2数学模型
若对于城市v={v1,v2,v3,…,vn}的一个访问顺序为t=(t1,t2,t3,…,tn),其中ti∈v(i=1,2,3,…,n),且记tn+1=t1,则旅行商问题的数学模型为:
minundefined
2遗传算法的基本原理和算法描述
2.1基本原理
遗传算法(Genetic Algorithm,简称GA) 是近年来迅速发展起来的一种全新的随机搜索与优化算法。与传统搜索算法不同,遗传算法从一组随机产生的初始解,称为群体,开始搜索过程。群体中的每个个体是问题的一个解,称为染色体。这些染色体在后续迭代中不断进化,称为遗传。遗传算法主要通过交叉、变异、选择运算实现。交叉或变异运算生成下一代染色体,称为后代。染色体的好坏用适应度来衡量。根据适应度的大小从上一代和后代中选择一定数量的个体,作为下一代群体,再继续进化,这样经过若干代之后,算法收敛于最好的染色体,它很可能就是问题的最优解或次优解[3]。遗传算法中使用适应度这个概念来度量群体中的各个个体的在优化计算中有可能到达最优解的优良程度。度量个体适应度的函数称为适应度函数。适应度函数的定义一般与具体求解问题有关。
2.2算法分析
作为现代优化算法之一的遗传算法模拟生物界的进化规律,以求找到问题的最优结果。对于TSP的遗传算法求解,主要有如下技术细节:
2.2.1 解的表示
用先后经过的城市序列表示解,如一个可行的走法先后经过编号为1,2,3,…,n的城市,则解可表示为序列:123…n。
2.2.2 编码方法
对于上述解序列,染色体编码仍采用十进制形式,即采用所谓的自然编码,适合于染色体交叉,一个解序列即表示一条染色体。处理自然编码时,存在变异规则的确定问题,具体针对本问题的可行解序列,其中任意城市代号在同一序列中不能重复,这就给变异带来了困难。在这里我们采用自然编码进行交叉运算,而采用Grefenstette编码进行变异运算,中间过程用编码和反编码程序进行变换。下面介绍Grefenstette编码:
对于一个旅行商问题的城市列表W,假定对各城市的一个访问顺序为T:T=(t1,t2,t3,…,tn),规定每访问完一个城市,就从城市列表中W将该城市去掉,则用第i(i=1,2,3,…,n)个所访问的城市ti在所有未访问城市列表W-{t1,t2,t3,…,ti-1}中的对应位置序号r就可表示具体访问哪个城市,如此这样直到处理完W中所有的城市。将全部gi顺序排列在一起所得到的一个列表:G=(g1,g2,g3,…,gn),就可表示一条巡回路线。
2.2.3 交叉算子
交叉运算(Crossover Operator)是产生新个体的主要方法,它决定了遗传算法的全局搜索能力,传统针对TSP 问题的遗传交叉算子,如部分影射交叉(PMX)、顺序交叉(OX)、循环交叉(CX)、基于位置的交叉、基于顺序的交叉等,他们都存在两个缺点,或者交叉后的子代不能很好地保留父代的优秀基因,或者子代需要做些改动才是可行的。以下给出的交叉算子可以使交叉后的子代保证可行性的同时,并很好地继承了父代的优秀基因:
假设有n个城市1,2,…,n,染色体编码成为推销员所经过的城市顺序号。现在有待交叉的双亲:
X1=(r11,r12,r13,…,r1n)
X2=(r21,r22,r23,…,r2n)
遗传交叉的主要目的是子代尽可能地继承父代的优秀基因。把上述染色体看成一个环,即r1n的下一个城市r1n+1=r11;根据贪婪法的思想,设计交叉步骤如下:
1) 定当前城市r1c=r11,从X2中找到r2k=r1c,并把r1c加入子代。
2) 若r1c+1和r2k+1都不在子代中,比较dr1cr1c+1和dr2kr2k+1,若dr1cr1c+1>dr2kr2k+1,记为当前城市r1c=r2k+1;否则就记为当前城市r1c=r1c+1。
3) 从X2中找到r2k=r1c,并把r1c加入子代。
4) 若1) r1c+1已经在子代中,而r2k+1不在子代中, 记当前城市r1c=r2k+1,并加入到子代;2) r2k+1已经在子代中,而r1c+1不在子代中,记当前城市r1c=r1c+1,并加入到子代;3) r1c+1和r2k+1都在子代中,比较dr1cr1c+2和dr2kr2k+2。
5) 重复步骤2) ,直到完整生成子代[4]。
2.2.4 变异算子
变异运算(Mutation Operator)是产生新个体的辅助方法,但它是不可缺少的一个运算步骤,因为它决定了遗传算法的局部搜索能力,还能维持群体的多样性,防止出现早熟现象。
在种群中,对每条染色体随机产生一个变异概率random,再将随机变异概率random跟设定的变异概率Pm(0
对选择出来要进行变异的染色体,以一条染色体为例,再随机产生需要变异的基因座,要进行变异的基因座总数不超过基因总数的20%,若某一变异点处的基因值的取值范围为[Umin,Umax],变异操作就是在该范围内的一个随机数去替换原基因值。
2.2.5 选择算子
选择算子(或称复制算子,Reproduction Operator)的作用是从当前代群体中选择出一些比较优良的个体,并复制到下一代群体中。现在对于随机产生的初始种群gt,对群体gt的每个染色体gt(i,:)计算它的适应度COST=fitness(tspdist,gt),tspdist是距离矩阵,对染色体对应的适应度从小到大排序,利用评价函数eval(i)=α·(1-α)i-1,(0<α<1)给每条染色体分配一个递减的选择概率,再利用轮盘赌原理选择父代染色体复制到等待交叉的种群;α影响优劣染色体的选择概率分配。
2.2.6 终止规则
一个最为简单的停止规则是给定一个最大的遗传代数termops,算法迭代代数在达到termops时停止。
3仿真分析和结果
3.1程序流程及步骤
step1 随机生成一个有popsize个染色体的初始种群gt;
step2 对种群gt的每个染色体gt(i,:)计算它的适应度COST=fitness(tspdist,gt),tspdist是距离矩阵;
step3 对染色体对应的适应度从小到大排序,利用评价函数eval(i)=α·(1-α)i-1,(0<α<1)给每条染色体分配一个递减的选择概率,再利用轮盘赌原理选择父代染色体复制到等待交叉的种群;适应度函数如图1所示:
step4 上述杂交规则把上面选出来的种群进行两两交叉,产生两个子代,得到两个有popsize个新的种群;
step5 以一个变异概率为Pm,用上述变异规则进行染色体变异,形成popsize个下一代种群;若停止规则满足,则算法停止;否则,返回step2。程序流程图如图2所示:
3.2遗传算法运行参数的确定
1) 群体大小,即群体中所含个体的数量,一般为50～300;
2) 遗传运算的终止进化代数,一般取为60～300;
3) 变异概率,一般取为0.1～0.2;
4) 系数,一般取为0.06～0.2。
3.3仿真结果
设有12个城市(或景点),今从某市出发遍历各城市,使之旅行费用最少(即找出一条旅费最少的路径)。我们取种群代数为80,染色体个数为100,变异概率为0.2,评价函数alpha=0.1;利用Matlab所编的函数只要花7.094秒就可以得到最短路线。染色体种群进化过程实例如图3所示
参考文献
[1]周明,孙树栋.遗传算法原理及应用[M].北京:国防工业出版社,2002.
[2]刘勇,康立山,陈毓屏,等.非数值并行算法—遗传算法[M].北京:科学出版社,1995.
[3]许家玉,经亚枝.基于DSP+FPGA的遗传算法硬件实现[J].微计算机信息,2005,21-1:127-128.
[4]刘海,郝志峰,林智勇.改进遗传交叉算子求解TSP问题[J].华南理工大学学报(自然科学版),2002,30
遗传算法存在问题分析 篇6
TSP问题又称为货郎担问题, 要求一个货郎要走遍n个城市, 每个城市经且只能经过一次, 最后回到始发的城市, 这条路径又称为哈密尔顿圈或哈密尔顿回路, 问题要求找到一条最短的路径。 其数学描述如下:设城市集合V={v1, v2, … , vn}, 每对城市vi, vj∈V间的距离为d (vi, vj) ∈Z+。 求经过V中任一城市正好一次的路径 (vπ (1) , vπ (2) , …, vπ (n) ) 使得
其中 (π (1) , π (2) , …, π (n) ) 是 (1, 2, …, n) 的一个置换。
TSP问题是组合优化问题中典型的NP难问题, 是许多领域内复杂工程优化问题的抽象形式, 具有较为广泛的工程应用和现实生活背景, 如飞机航线的安排、公路网络的建设、网络通信节点的设置、物流货物配送、 超市物品上架等, 所有这些实际应用问题均可以转变为TSP问题来解决。 因此, 如何有效、快速地解决TSP问题具有很高的实际应用价值。
若穷举搜索全部可能的路径, 一定能够找到最短的那条路径。 亦即, 使用穷举法能够找到最优解。 但是, TSP问题的搜索空间会随着城市数量n的增加而急剧增加, 所有可能的旅行路径的组合数是 (n-1) !/2。 当城市个数达到50 时, 就有1.5207×1064个旅行方案。 使用常规的穷举法在如此庞大的搜索空间中寻求最优解, 对于现有的计算机而言, 是不可行的。当城市个数更多时, 更加难以求得最优解, 因此, 寻找最优解变得非常困难。 自然而然地, 各种求近似解的优化算法就成了比较现实可行的解决方法。 近几十年来, 出现了很多近似算法[1], 如贪婪算法、近邻法、双最小生成树法、最近插入法、最远插入法等等。近年来, 随着人工智能的发展, 许多更为有效的智能启发式算法应用于TSP问题, 高海昌等[2]对用于求解该问题的蚁群算法、遗传算法、模拟退火算法、禁忌搜索、神经网络、粒子群优化算法、免疫算法等进行了描述。随着研究的深入, 许多改进的优化算法不断涌现, 文献[3]提出了一种快速求解旅行商问题的蚁群算法。文献[4]将蚁群算法与免疫算法相结合应用于TSP问题求解。 Marinakis等对基于概率的旅行商问题进行研究, 提出了一种混合多粒子群优化算法[5]。 文献[6]的混合遗传算法将局部寻优与广义分割交叉算子结合, 提高了算法的执行效率。 文献[7]对传统遗传算法的交叉操作进行研究, 设计了一种顺序构造交叉算子以提高解的质量。 为了提高遗传算法解决TSP问题的效率, 文献[8]将贪婪搜索算法引入遗传变异操作中, 设计出新的贪婪子路变异算子。 大量研究表明, 融入一些其它信息如近似算法、特殊组合算子、局部搜索技术等, 能够极大地改善进化算法的搜索性能[9,10], 尤其是, 将进化算法与局部搜索相结合的方法, 已经证明是很有效的策略[11,12]。这种融有局部搜索的进化算法被称为文化基因算法[13], 从文献[11-12]可以看出, 文化基因算法具有高效的搜索性能。
为更好地求解TSP问题, 本文提出了一种基于遗传算法的文化基因算法, 将2-opt作为局部搜索算子嵌入到遗传算法中, 以加快遗传算法的收敛速度、提高解的精度。遗传算法具有很好的全局搜索能力, 2-opt针对TSP问题具有较强的局部搜索特点, 所提出的文化基因算法力图在全局和局部搜索中达到平衡和融合, 使之更有效地求解TSP问题。
1 文化基因算法
文化基因算法 (Memetic Algorithm, 简称MA) , 由Moscato在1989年首先提出[13]。 Memetic一词源于道金斯 (Dawkins) 在1976 年所著《自私的基因》 (The Selfish Gene) 中提出的一个概念——Meme。 Meme也译为“拟子”、“觅母”或“文化基因”等[14], 指的是文化领域的一个信息单位, 就如遗传学中的基因单位一样。 生物的进化一般指生物通过基因的繁殖、变异, 加上自然选择, 使生物不断适应环境的变化。 类似于生物的进化, 文化的进化是通过各种Meme被复制、被模仿稍加改变, 在人与人之间传播、变化。 有利于人类的Meme通常能得到不断的传承和发展。但是, 文化进化与生物进化不同的是, 生物基因的变异一般是随机的, 只有个别适应环境的变异能促进生物的发展, 除此以外, 或者大部分的变异对于生物的进化不起作用。而文化进化总是朝着改进的方向进化, 而不是混乱无序或无进展, 如更动听的音乐、科学的发展等等。
Moscato在1989 年首先提出文化基因算法 (MA) 正是受上述文化进化思想的启发。 本质上来说, MA就是将基于群体的全局搜索进化方法与局部搜索方法相结合的一种新技术[13]。 文献[13]中将局部搜索或优化策略比喻为Meme, 把局部搜索策略与传统的进化优化方法结合起来就形成了MA。 MA开始提出时, 特指的是遗传算法 (GA) 和局部搜索策略的结合, 随着进化优化方法研究的不断发展, 基于群体的其它智能算法如粒子群、蚁群等的MA也相继被提出。
MA比遗传算法 (GA) 、蚁群 (ACO) 、 粒子群 (PSO) 等算法有更广的范畴, 代表着一类算法。 它是一种基于种群的全局搜索和基于个体的局部启发式搜索的结合体[13], 这样的结合机制使其搜索效率在某些问题领域比传统遗传算法快几个数量级, 可应用于广泛的问题领域并得到满意的结果。 很多人将文化基因算法看作混合遗传算法、遗传局部搜索或是拉马克式进化算法, 实际上, 文化基因算法提出的是一种框架、是一个概念, 在这个框架下, 采用不同的搜索策略可以构成不同的文化基因算法, 如全局搜索策略可以采用遗传算法、进化策略、进化规划等, 局部搜索策略可以采用爬山搜索、模拟退火、贪婪算法、禁忌搜索、导引式局部搜索等。目前, 为了求解各种不同类型的优化问题已经有大量的MA被提出。 2005 年文献[15]中作者对MA进行了综述, 用框架的形式描述了文化基因这一类算法。图1 描述了传统的文化基因算法的流程图。
2 求解TSP问题的文化基因算法描述
为更好地求解TSP问题, 本文提出了一种基于遗传算法的文化基因算法, 将2-opt作为局部搜索算子嵌入到遗传算法中, 以加快遗传算法的收敛速度和提高解的质量。 遗传算法具有较强的全局搜索能力, 2-opt针对TSP问题具有很好的局部搜索效果, 所提出的文化基因算法试图在全局搜索和局部探索中达到均衡和融合, 使之能更有效率地解决TSP问题。
2.1 2-opt局部搜索
2-opt局部搜索是一种有效的局部搜索技术, 被广泛应用于旅行商 (TSP) 及其它的一些组合优化问题, 而且有研究表明2-opt局部搜索对求解旅行商问题十分有效。 2-opt局部搜索的主要意图是消除回路中所有相交的边, 因为相交的边基本上不是最优的。 主要计算过程是, 依次在哈密尔顿回路中选两条不相邻的边, 进行判断, 若这两条边相交, 则将这两条边从路径中移除, 再用另外两条新的边, 把移除边后得到的两条路径重新连接成为新的哈密尔顿圈, 如下图2 形象描述了这一过程。
2-opt的优化过程主要包含两步: (1) 先移除回路中一对相邻点之间的边, 得到两条互不相连的路径, (2) 将其中一条分支路径进行反转, 重新与另一条分支路径连接, 形成新的哈密尔顿圈 (回路) 。 反转操作可记为Turn, 对路径V中第i个点到第j个点之间的路径的反转操作记为Turn (V, i, j) 。
假设V= (v1, …, vi, vi+1, … , vj, vj+1, vn, v1) , 则Turn (V, i, j) = (v1, … , vi, vj, vj-1, … , vi+1, vj+1, vn, v1) , 当满足条件d (vi, vi+1) +d (vj, vj+1) >d (vi, vj) +d (vi+1, vj+1) , j≥i+2 时, 才会进行上述反转优化操作, 如图3 所示。
2-opt局部搜索算法的伪代码如下图所示:
2.2 算法主体设计
遗传算法是一种基于自然选择和基因遗传学原理的一种寻求全局最优解而不需要任何初始化信息的高效优化方法。它将问题的解集看作一个种群, 通过不断地选择、交叉、变异等遗传操作, 使解的质量越来越好。该算法具有全局寻优能力、适应性强、解决非线性问题具有较强的鲁棒性、对问题没有特定限制、计算过程简单、易于与其他算法结合等特点, 在函数优化、图像处理、自动控制、经济预测和工程优化等领域得到了广泛的应用, 在求解NP完全问题方面也是一种较为有效的全局方法。
针对TSP问题, 本文提出的文化基因算法, 在算法主体上采用遗传算法进行全局搜索, 在进化的过程中, 采用2-opt技术进行局部调整以加快算法的收敛速度和提高解的精度。 算法求解TSP问题的主要计算过程如下:
Step 1: 确定编码机制, 生成初始种群Vi (i=1, … , popsize) , popsize为种群的规模。 解决TSP问题通常采用城市序号对路径进行编码, 按照访问城市的顺序排列组成编码。
Step 2: 计算种群中每个个体的适应度值。 TSP求解是要寻找使目标函数最小的个体, 因此选择适应度函数。可以看出, 巡游路径越小, 适应度值越大。
Step 3: 选择算子。 算法采用最常用的轮盘赌选择策略, 适应度较高的个体具有较大被选择的机会。 计算每个个体被选择的概率为。 在轮盘赌选择的基础上, 算法也考虑到了精英个体的保留。 在对种群进行轮盘赌选择结束后, 算法会检查新生成的种群中是否包含有父代的精英个体, 若不包含, 则将新生成的子代种群中最差的个体替换为父代的精英个体。
Step 4: 交叉算子。 由交叉概率pc选择父体并进行配对, 按照交叉算法的规则生成新个体。 算法中采用单点顺序交叉法 (OSPX) 。 设两父代个体为V1, V2。随机选择一个交叉点, 定义交叉点后面的元素为拟匹配区域。 设V1, V2及交叉点表示为:
采用单点顺序交叉, 首先将V1和V2的拟匹配区域进行复制, 分别加到V2和V1的前面, 可得到
然后分别从复制的匹配区域后依次删除与前面匹配的相同的码, 最后可得到:
Step 5: 变异算子。 为了保持种群个体的多样性, 防止陷入局部最优, 本算法采用基本位变异, 以pm的变异概率对每个个体执行变异操作。随机选择个体的两个基因位, 将两个位上的码进行反转操作。设个体及随机选择的两个基因位为, 执行基本位变异操作, 执行完成后个体转换为:V1=[10 1 9 2 8 5 6 7 4 3]。
Step 6: 对新生成的子代个体执行2-opt局部搜索。 局部搜索的伪代码如图4 所示。
Step 7: 迭代终止判断. 若满足预定的终止条件 (如达到最大迭代次数) , 则算法停止迭代, 所得的路径认为是满意的路径; 否则, 转Step2, 计算新一代种群中每个个体的适应度值, 将新一代种群替换为当代种群。
3 实验测试
为了测试基于遗传算法的文化基因算法在解决TSP问题方面的表现, 本文从TSP标准问题测试库中提取了10 个测试问题, 将本文提出的算法用于求解这10 个问题, 并将算法的执行结果与当前其它一些优秀的智能算法的运行结果进行了比较。
在测试过程中, 算法采用轮盘赌选择和精英个体保留机制, 单点顺序交叉, 基本位变异, 终止代数为500, 群体大小为200, 交叉概率为0.9, 变异概率为0.09。 在Matlab环境下, 算法对每个测试问题独立进行10 次。 在相同的终止迭代条件下, 表1 给出了几种算法所求得的最短路径的平均值。 以eil51、bier127、rat195、kro B200 为例, 图5 形象展示了算法在这些测试问题上独立运行10 次的结果。
从表1 和图5 可以看出, 相较于遗传算法, 本文提出的基于遗传算法的文化基因算法所求得的路径更短, 可见融入2-opt局部搜索技术对于提高算法的性能是非常有效的。 与当前其它一些优秀的算法, 包括模拟退火、粒子群算法、蚁群算法相比, 在这些测试问题上, 基于遗传算法的文化基因算法均表现了较好的性能, 所求得的结果都优于其它算法。如图5 所示, 与其它算法相比, 本文提出的算法还具有较好的稳定性, 鲁棒性较强, 对问题的敏感性较弱, 比较适合解决此类TSP问题。
4 总结
遗传算法在求解TSP问题时往往存在着求解质量不是很高、容易陷入局部最优等一系列问题。 为了克服这些缺陷, 本文提出了一种基于遗传算法的文化基因算法。 算法在求解过程中, 将2-opt作为局部搜索算子, 嵌入到遗传算法中, 以加快遗传算法的收敛速度和提高局部搜索能力。遗传算法具有全局搜索的能力, 2-opt具有局部搜索的特点, 嵌入2-opt局部搜索的遗传算法力图在全局和局部搜索中达到平衡和融合, 使之更有效地解决TSP问题。
为检测算法的性能, 将该算法在10 个标准TSP测试问题上进行了测试, 并将测试结果与标准的遗传算法及蚁群、粒子群等其它一些优秀的算法的实验结果进行了对比, 数值实验结果表明, 本文提出的算法在求解的质量、稳定性上均表现了较好的性能, 算法的整体表现要优于其它算法。 可见融入局部搜索技术的全局搜索算法对于解决TSP问题是一条有效的途径。 探索其它更高效的局部搜索算法, 将这些局部搜索技术有效地融合到遗传算法、蚁群算法中, 以更好地解决TSP问题将是作者今后进一步的研究工作。
摘要：为更好地求解旅行商问题, 本文提出了一种基于遗传算法的文化基因算法。将2-opt作为局部搜索算子, 融入到遗传算法中, 以加快遗传算法的收敛速度和提高解的局部搜索能力。遗传算法具有全局搜索的能力, 2-opt具有局部搜索的特点, 嵌入2-opt局部搜索的遗传算法力图在全局和局部搜索中达到平衡和融合, 使之更有效地解决TSP问题。为检测算法的性能, 将该算法用于解决标准的TSP测试问题, 并将测试结果与标准的遗传算法及蚁群、粒子群等其它一些优秀的算法的实验结果做了比较, 数值实验结果证明了算法的有效性。
遗传算法存在问题分析 篇7
关键词：遗传算法,01背包问题,评价函数,遗传算子
1 问题描述及解的遗传表示
1.1 问题描述
01背包问题是一类基础的背包问题, 可以具体描叙为一个体积为volume的背包和n个物体, 对于物体i, 其体积为vi, 价值为wi, 01背包问题就是要在不超过背包体积的情况下, 使装入背包的物体价值量最大。
1.2 问题解的遗传表示［２］
因为对于一件物品只有放进与不放进两种选择, 所以只用两种状态就可以表示, 于是采用二进制编码。当xi=0时, 表示物体i不放入背包, 当xi=1时表示物体i放入背包, 则01背包问题的数学模型为, n个物体的背包问题的解可以表示为二进制串x= (x1, x2……xn) , xi=0或1。
2 遗传问题解决的关键技术
2.1 设计评价函数, 根据个体适应值对其进行优劣判定
采用经典的赌轮选择算法[3], 评价函数的功能是从群体中选择一个基因组, 选中的几率正比于基因组的适应性分数。
2.2 用遗传算子改变繁殖过程中产生的子个体遗传组成
杂交算子[4，5]要求两个染色体在同一随机位置上断裂, 然后将它们在断开点以后的部分进行互换, 以形成两个新的染色体 (子代) 。
变异算子[6，7], 沿着染色体长度, 依次对各位进行考察, 并按m_dMutationRate给定的几率, 将其中某些位进行翻转。
3 遗传问题解决的改进
可以设置适应性函数, 记下每一代中最差的价值, 然后对种群中每一个解得出的价值减去这个最差的价值, 这样相对差异变大, 接下来使用轮盘选择法, 可有效地从种群中移去最差的染色体, 因为最差的适应性分数为0[7，8]。改进的遗传算法可选择以下不同的变异算子[8-10]。
3.1 散播变异
随机地选择一对位置, 将其间的基因进行任意移动, 代码如下:
3.2 移位变异
随机选择两个点, 取出其间的染色体段, 插入到剩余染色体的一个随机位置上。
3.3 插入变异
插入变异是一种相当有效的变异。IM算子与DM算子很类似, 惟一不同点是IM一次只取出一个基因并插回染色体。
参考文献
[1]JOHN H HOLLAND.Adaptation in natural and artificial systems[M].A Bradford Book, 1992.
[2]王银年.遗传算法的研究与应用[D].无锡:江南大学, 2009.
[3]尹蔷.谈谈P和NP问题[J].大连教育学院学报, 2005 (4) .
[4]孙宇兴, 谭芬.利用动态规划解决01背包问题[J].现代交际, 2010 (5) .
[5]玄光男, 程润伟.遗传算法与工程优化[M].于歆杰, 周根贵, 译.北京:清华大学出版社, 2004.
[6]PETE BECKER.The C++standard library[M].Addison-Wesley Professional, 2006.
[7]刘刚, 何麟书.双赌轮选择遗传算法[J].北京航空航天大学学报, 2005 (8) .
[8]周永华.实数编码遗传算法杂交算子组合研究[D].广州:华南理工大学, 2003.
[9]葛继科, 邱玉辉, 吴春明, 等.遗传算法研究综述[J].计算机应用研究, 2008 (10) .
基于改进遗传算法的定位问题研究 篇8
物体定位技术已经由传统的自然规律发展到现代的GPS定位和雷达定位等,而利用物体的影子进行定位即是将自然规律与现代科技相结合而形成的一种新型定位方法。物体的影子作为直观的视觉信息,研究影子的定位方法是一项新兴主题实用技术。该项技术对视频图像资料的定位提供了解决办法,而且也为刑侦以及失踪人员侦察等工作在相当程度上创造了真实便利。由于物体在不同地点、不同日期和不同时间的影子长度和角度会发生变化,本文针对影子坐标等数据建立最小二乘优化模型,在传统遗传算法的基础上,加入了寻优范围的约束建立改进遗传算法,对比2种算法,可以得到后者搜索结果残差平方和最小,说明改进遗传算法具有很好的鲁棒性。
1 数学模型
1.1 问题描述
影子定位问题可以描述为:某一日期不同时刻t的一直杆影子的顶点坐标为(x,y),要求定位出此时刻的直杆经纬度。本文所采用数据为2015年数模竞赛A题附件1[1]。当地实际时间ts与北京时间t的时间差用Δt来表示,杆长为h。当地的纬度(φ)、太阳高度角(α)、太阳赤纬角(δ)、时角(ω)的相关公式如下:
(1)时角ω(度)[2]公式:
(2)太阳赤纬角δ[3]公式
式中,θ称日角,即θ=2πt/365.242 2,t=N-N0,N为积日,N0=79.676 4+0.242 2×(年份-1985)-INT[(年份-1985)/4]
(3)太阳高度角α[4]公式:
由此可以得出影长L与太阳运动参数的关系如下:
1.2 最小二乘优化模型
针对上述问题,要确定多个未知参数需采用最小二乘的思想建立优化模型,设研究中共有m组数据(x,y,t),令z=L2,则以残差平方和为目标函数建立规划模型如下:
2 遗传算法设计
遗传算法(Genetic Algorithm,简称GA)是美国密执安大学J.H.Holland教授于20世纪70年代中期首次提出的一种基于生物遗传和进化机制的适合复杂系统优化计算的自适应概率优化技术。作为一种智能优化算法,其鲁棒性较强,简单通用,具有较强容错能力,通过选择、交叉、变异等操作能极大限度地向最优解进行逼近。同时,变异等操作的引入可防止结果陷入局部最优解,增加搜索的灵活性。对于每一位个体,采用适应度函数对其评价。
基于上文建立的最小二乘优化模型,可以看作是染色体组(φ,h,Δt)在满足式(6)的约束条件下,通过评价函数对其进行评价,使评价值较高的个体进入到产生下一代的运算中,直至满足终止条件。遗传算法流程如图1所示。
2.1 遗传编码
比较常见的遗传算法编码方式是二进制编码、格雷编码及符号编码等。本文采用二进制进行编码,并将染色体向量记为V=(φ,h,Δt)。然而,由于实际的算子存在小数,如果直接转化为二进制,可能会因此而出现无穷小数。针对这一状况,可将精度确定于小数点后三位,转换成二进制整数后再进行编码、运算,并将运算结果转化为十进制后再除以1 000即可。例如,对于染色体向量V=(0.213,2.986,0.721),得到1 000 V=(213,298 6,721),转为二进制V=[11010101,101110101010,1011010001]2。
2.2 适应度函数
适应度函数是评价个体性能优劣的唯一指标。在本次研究中,基于最小二乘的思想,目标函数的结果值越小,表明拟合的程度越好,即所求得的经纬度更接近原始目的地。因此需将目标函数转换为适应度函数,以便进行个体优劣的目标判断。此时,可用适应度Gi表示第i位个体的优良程度:
其中,Q(Xi)是第i个母体的修正值。同时,由于该问题是带有约束的优化问题,则需在适应度上加入惩罚项。修正后的计算公式如下:
其中,f(Xi)即为式(5)的最小二乘残差平方和,M为惩罚系数,Wk为违约项,,为惩罚项,s表示违约项的个数。例如约束,则。
2.3 选择算子
如何选择参与运算的个体是遗传算法中的执行实施重点,本文中采用轮盘赌的方法进行选择。实现过程如下:
1)计算出现在种群中所有个体的适应度Gi以及所有适应度值的倒数总和S。
2)划分区间[0,1/G1S),[1/G1S,1/G2S)……[1/GnS,1),表示轮盘各扇区的面积。设置生成一个随机数N∈[0,1),根据N所在的区间进行交叉算子的选择。如N∈[1/G1S,1/G2S),则选择第2位个体进行运算。
2.4 交叉运算
交叉运算是遗传算法中目标实现的关键所在。其本质是模拟自然界中生物优胜劣汰的原则。即优良的个体将有更大的机会产生后代,从而后代性能必然不断趋近于更加优秀。在本例中,基于前述采用的是二进制编码,这里采用了单点交叉的方法。随机生成3个交叉点位,对选定的染色体组执行交叉运算。如生成的交叉点位向量Y=(5,3,6),对于染色体向量pop1和pop2,操作过程如图2所示。交叉运算以后产生后代pop1'和pop2',存入下一代中,母代的个体则继续参与其后的变异运算,从而保证了种群的多样性。
2.5 变异运算
变异运算是模拟自然界中生物进化时的产生的偶发的基因突变。事实上,在用遗传算法求取最优解问题中,变异运算一定程度上保证了种群不会陷入局部最优解,增强了遗传算法对全局最优解的搜索能力。本文采用的变异方式有旋转变异以及位变异2种。
对于旋转变异,操作方式如下:选取pm1·pop个母体,对于所选的染色体组中的3个染色体,随机选择3个位置,并分别以其为分界点,将每个染色体左右的基因互换,完成旋转变异。如对于染色体组pop:
进行旋转变异后的结果为:
至此,完成了对旋转变异的操作。对于位变异,类似于旋转变异,先选取pm2·pop个母体在生成变异位的基础上,将所对应的基因进行取反处理,即若基因为1,则取为0,反之即取为1,其他位不变。本文取变异概率pm1=0.1,pm2=0.1。
2.6 终止条件
由于本研究是一个最小二乘的优化问题,对精度要求较高才能搜索到满意最优解,设置终止条件为进化代数generation=1 000。
2.7 遗传算法的改进
为了得到精度更高的最佳结果,可以采用改进的遗传算法搜索可行解。通过传统遗传算法计算可得的解集V=(φ,h,Δt)是有一定范围的,其中h的范围为[1.86,1.946],φ的范围为[0.3,0.319],△t的范围为[0.56,0.645],因此可以认定实际上的最优解应在这些范围附近。通过重新设置变量V=(φ,h,Δt)的范围,再进一步实施遗传算法寻优,可以显著提升算法效率,从而得到更加精确的总体可行解。
设置一个放大系数λ,将上述所求解的范围记为:
则得到新的范围:
此处取λ=1.3,并将新的范围作为约束条件代入改进的遗传算法程序。
2.8 改进的遗传算法与遗传算法的实例比较
本文采用全国大学生数学建模竞赛A题目附件1的数据[1],利用最小二乘模型,分别采用2种遗传算法编程,求解结果如表1所示,进化情况分别为图3和图4所示。
由上述结果可得,采用遗传算法进行计算得到的目标函数值在10-5左右,但是所求的各组h、φ、Δt值之间偏差较大,无法得到一个确定、且较优的解答。通过表1对比可得,改进后的遗传算法获得的最优解要远远优于之前的遗传算法,所得到的解集V=(φ,h,Δt)则更加趋向于一固定值,并且算法时间复杂度也仅是呈现为线性增加,因此具有较强的通用性。研究最后,可以定位出物体所在经纬度为(N21°36'1.83″,E108°49'30″)。
3 结束语
影子的存在能够为光线估计、姿态估计、目标大小估计、深度估计、立体匹配等计算机视觉任务提供重要的线索。本文主要采用杆影日照原理,借助已知影子的轨迹可以反演出杆影目标地点的具体经纬度方位。研究中建立了影长模型和最小二乘优化模型,同时采用遗传算法来求解直杆相关参数的可行解,并对传统意义上的遗传算法提出了一定改进,缩小了遗传算法的搜索范围,大大提高了算法的效率以及结果的精度,对于精确定位具有一定的现实重要意义。
参考文献
[1]中国工业与应用数学学会.2015高教社杯全国大学生数学建模竞赛A题[EB/OL].[2015-09-12].http://www.mcm.edu.cn/html_cn/node/ac8b96613522ef62c019d1cd45a125e3.html.
[2]方荣生.太阳能应用技术[M].北京:中国农业机械出版社,1985.
[3]陈晓勇,郑科科.对建筑日照计算中太阳赤纬角公式的探讨[J].浙江建筑,2011,28(9):6-8,12.
基于遗传算法的TSP优化问题 篇9
TSP最优解的搜索空间随着城市数n成指数型增长，所以，TSP问题虽易于描述，但一般很难精确地求出其最优解。近年来，有很多解决该问题的较为有效的方法不断被推出，例如二叉树描述法、启发式搜索法、最近邻法、禁忌搜索方法、遗传算法、模拟退火算法等等[2,3,4,5,6,7]。而遗传算法[8]是模拟生物在自然环境中的遗传和进化过程而形成的一种自适应全局概率搜索算法、具有良好的全局寻优能力，成为解决TSP问题的有效方法之一。
1 TS P问题描述
TSP问题可以简单的描述为：某商人欲从自己所在的城市出发，到若干个城市去推销商品，每个城市访问一次且仅一次，最后仍然回到自己所在的城市。已知n个城市的坐标，如何安排该商人对这些城市的访问次序，可使其旅行路线的总长度最短?在现实应用中，TSP问题常常被转化为求总的费用最小的问题，不过本文只讨论如何求总路径长度最小。
2 遗传算法描述
遗传算法的通用过程可描述为：
(1)初始化确定解的基因表示，设置遗传算法的重要参数，并随机产生一个初始种群。
(2)设计评估函数设定合理的适应度函数，对群体中的每个个体计算它的适应值fitness。
(3)选择根据上一步骤计算得到的个体适应值，采用适当的选择方法，以概率的方式，从父代中选出满足要求的优良个体进入下一代。
(4)交叉针对不同问题采用不同的交叉方法，以指定的交叉概率Px对父代个体加以替换和重组从而得到子代种群。
(5)变异按照一定的变异方式，以确定的变异概率Pm随机改变当前群体中个体的某个或某些基因。
(6)终止条件判断如果满足中止条件，则将已记录的具有最好适应值的个体作为最优解，终止计算。否则返回(2)，依此循环。
遗传算法具有良好的全局搜索能力，常用于求解TSP问题。但传统的遗传算法对于该问题的求解也存在着一些有待改进的地方。比如：如何较快的找到最优解并防止“早熟”收敛[9]问题;如何同时保证收敛速度且避免陷入局部最优点[10]。另外，由于TSP问题的特殊性，传统的遗传算法中提到的许多优秀方法此时却不一定适用。因此，本文提出了一种求解TSP问题的改进遗传算法。该算法在适应度函数的选择、遗传算法的设计以及遗传算法重要参数的设置上都进行了改进。实验证明，该方法较传统的遗传算法表现出更好的收敛性和计算效率。
3 TS P问题的改进遗传算法
3.1 初始化——TS P染色体表示方式
由于TSP问题的特殊性，为了充分利用TSP信息，本文采用直观的路径表示，将染色体定义为一个线性序列。假设有8个城市，那么旅行商的路程(3-1-8-4-6-2-5-7)可直接表示为(31846257)。而城市与城市之间的距离则由各城市的坐标，根据距离公式求得。该表示方法结构简单，容易理解且实现方便。
3.2 适应度的计算
适应度函数的选择在本次TSP求解的优化方法中是非常重要的一个环节，其与选择算法密切相关，并会对实验结果造成直接的影响。由于本文采用的选择方法是轮盘赌选择法，其原理是适应度大的个体被选中的可能性也大，因此不能直接以总路径长度作为适应值fitness。在本文中采用了一种分段的变适应函数：
(max为所有染色体的最大路径长度，MAXGENS是遗传的最大代数)基于有些个体虽然不优，但仍可能包含部分优秀基因片段的事实，因此在前1 500代前使用函数(1)。通过该函数的计算将使每个个体的适应值fitness相差不大，以防止有效基因的丢失，避免了“过早收敛”。而在遗传的后期则选用函数(2)，该函数将充分凸显个体差异，加快后期收敛速度。
使用了这样的分段适应度函数之后，我们随机抽取某一次遗传过程，个数为N的种群的个体在第1 499代和在第1 500代时的Fitness值如图1所示：
由图1可以看出，使用函数(1)来统计的Fitness值在前期虽各不相同，但个体差异不大，基本处于4 500到6 500之间，在进行选择操作的时候可以保证每个个体都有充分的被选中的可能，以此确保优秀基因不丢失及种群的多样性，并且防止局部收敛。
由图2可以看出，在后期使用函数(2)来统计适应值，Fitness值跨度大约由3 000到12 000。因此在进行选择操作的时候可以加快后期的收敛速度。
3.3 选择操作
选择操作本文采用的是轮盘赌选择法。它由以下几个步骤实现。
(1)计算总适应值sum。
(2)以每个个体的适应值除以总适应值，以此作为每个个体的选择概率：cfitness=fitness/sum。
(3)计算个体的累积概率rfitness。
(4)生成随机数x，若P(i-1)
由于该方法是以概率选择为基础的，因此选择概率大的个体被选中的可能性也较大，而选择概率又与适应度成正比，所以，在进行了一次选择之后，适应度高的个体被选中的概率大，而适应度低的个体则可能被淘汰。
3.4 交叉操作
由于TSP问题中染色体编码对应于旅行路径上的城市号，则要求各位的基因值不能相同。考虑到TSP问题的该特殊性，本文提出了一种改进的交叉操作。
假设对于8个城市的TSP问题，其交叉算法描述如下。
(1)产生一个随机数i作为交配位。假设此时i=4，而父代个体A=(12345678);B=(34578216)。
(2)首先将两个个体的前i位互换。得到子代个体A1=(34575678);B1=(12348216)。
(3)对每个个体从前开始搜索，发现相同的基因则将其用0代替。于是得到A2=(34570608);B2=(12348006)。
(4)再对每个个体从第i+1位开始遍历，所有0都依次被有效基因替换。具体方法是：将对方染色体从第1位到第i位的基因依次与自身染色体中的每个基因位作对比，如果对方染色体中的某基因没有在自身整个染色体中出现过，则以此来代替0。于是得到A3=(34571628);B3=(12348576)。
这种交叉算法在考虑遗传效率的同时尽可能的继承了父代信息，维持了出发城市的不变性，并充分保证了个体的有效性。
3.5 变异操作
变异操作保证了种群的多样性，避免了过早陷入局部最优解的问题。由于TSP问题的特殊性，为了防止无效个体的出现，变异操作无法使用常规的单点基因值变异方法。本文则选择了一种简单而高效的变异操作，即产生两个随机数代表变异位，而后将这两个变异位的基因互换即可。通过大量实验证明，该方法较其他变异方法能更好的控制群体的收敛速度。能解决遗传过程中的过早收敛问题，防止局部最优解，又不会使变异前后的染色体相差甚远，迟迟无法收敛。
例如：对个体A3=(34571628)变异。首先产生两个随机数i,j。假设此时i=3,j=6。然后将这两位的基因互换，即得到变异后的个体A4=(34671528)。
3.6 算法终止条件及参数选择
以一定的迭代次数作为算法终止条件。本文设置城市数NAVRS=20，其城市坐标来源于CHN144中的部分数据。群体规模POPSIZE=50。遗传代数MAX-GENS=2 000代。交叉概率和变异概率则是以一定步长可变。实验证明，在该TSP问题中，Px、Pm取值的大小也会影响种群的收敛速度和最终结果，因此，由实验数据分析、总结，取Px:0.1-0.9,step:0.1;Pm:0.01-0.1,step:0.01。对Px,Pm的这90组组合各执行500遍，取其中路径总长最小值作为这一组合的最终路径长度。
4 实验结果
本实验是在Core Duo T2350 1.87GHz,1G内存，Windows XP系统下测试完成的。编程环境是Visual C++6.0。数据分析及画图工具是origin7.5。
4.1 改进后的实验结果
用改进后的遗传算法得到的实验结果除了出现了一个峰值之外，绝大多数Distance取值都能收敛到13 500～15 000之间，Distance值较集中，收敛效果好。说明，采用了如上的改进方法，算法的结果基本上能收敛到一个较理想的值，算法较完善。其中最短Distance取在Px=0.2,Pm=0.07，此时Distance=13675.175349655。其路径自动记录如下：
第47次Simulation completed
PXOVER=0.2 PMUTATION=0.07
Best path is:20-18-17-4-6-7-8-9-10-5-1-2-3-11-12-14-13-15-16-19-
the shortest distance=13675.175349655
4.2 改进前的实验结果
用传统遗传算法解决该TSP问题，其实验结果得到的峰值较多，没有较明显的收敛趋势，各组组合对应的Distance值波动较大，不集中。说明，没有经过改进的算法无法呈现出一个较好的收敛趋势，并且以该算法求得的最优值也不理想。其中最短Distance取在Px=0.8,Pm=0.04，此时Distance=17199.371320600。其路径自动记录如下：
第74次Simulation completed
PXOVER=0.8 PMUTATION=0.04
Best path is:14-12-6-17-19-20-16-18-15-13-11-3-2-1-7-5-8-9-10-4-
the shortest distance=17199.371320600
将改进前后的实验结果比较可以很明显的看出，改进后的遗传算法在解决该TSP问题上，不论是最终的最短路径结果，还是总体的收敛效果，确实较未改进的遗传算法更优。
4.3 本次实验求解的最优路径
本次实验所用的城市是从CHN144中随机挑选的20个城市。通过多次取样发现，不同的城市初始坐标对判断算法的优劣也有着一定的影响。比如，如果城市过于集中的话，则最终求得的Distance值也相对较为接近，从而掩盖了算法本身的优劣。因此，本实验通过随机的方式来挑选这20个城市。最短路径如图3所示：
5 结论和展望
本文是基于经典遗传算法的思想提出了一个解决TSP问题的改进方案,主要体现在适应度函数的设置、杂交和变异算法的改进以及相关参数的合理设定。通过实验证明，其相比经典算法更具灵活性和高效性。在此也可以看到,运用遗传算法解决实际问题,算法效率总是依赖于问题的编码、遗传操作算子以及适应值函数和参数的合理设置,要进行遗传算法的改进一般也要以这几个方面作为突破口。总的来说，遗传算法与其他计算机算法不同，相比之下，它比较具有随机性而不是稳定性，因此利用遗传算法解决实际问题需要选取大量数据，通过多次实验的数据分析不断改进算法和设置参数来求得更优的结果。
而对于TSP问题的遗传算法优化问题，其实还有很多可以更加改进的地方。比如Px,Pm取值：我们可以设置在收敛速度较快时适当增大Pm的值;相反，在收敛速度较慢时适当减小Pm的值，使Px,Pm根据当时的收敛速度自适应调整。另外，本文所讨论的交叉，变异等操作都是串行执行的。我们也可以考虑让两次或多次交叉、变异操作并行处理，甚至还可以考虑将父代优秀个体的直接复制与其他杂交、变异操作叠加混行来避免父代遗传的优良个体被交叉和变异所破坏等等。以上所述的优化方法还有待于在实际的TSP问题中加以证实和实现。
摘要：TSP问题是一个典型的组合优化问题,并且也是一个NP难题,其可能的路径总数与城市数目n成指数型增长,一般很难精确地求出其最优解。这里对TSP问题提出了一种改进的遗传算法,通过对遗传算法的评估函数、交叉和变异方法以及参数选择等方面的分析和修改,构造了一种自适应函数以及交叉、变异方法。通过对CHN144的测试,实验结果证明此处提出的方法能更有效的求解TSP问题。
关键词：组合优化,NP难题,旅行商问题,遗传算法
参考文献
[1]于宁莉,易东云,张栋.旅行商问题的一种快速有效的遗传算法[A].第八届中国青年运筹信息管理学者大会论文集[C],桂林,2006,534-539.
[2]WANG Yuping,HAN Lixia,LI Yinghua.A new encoding based genetic algorithm for the traveling salesman problem[J].Engineering Optimization,2006,38(1):1-13.
[3]LIU Ruochen,JIAO Licheng,DU Haifeng.Clonal strategy algorithm based on the immune memory[J].Journal of Computer Science&Tech-nology,2005,20(5):728-734.
[4]MICHEL G,GILBERT L,FREDERIC S.A tabu search heuristic for the undirected selective traveling salesman problem[J].European Journal of Operational Research.1998,106(2):539-545.
[5]邓娟,陈莘萌.一种基于最大相似性的TSP问题求解算法[J].计算机工程,2004,30(17):1-2,11.
[6]谢胜利,张燕姑,李广.基于遗传算法的旅行商问题求解[J].温州师范学院学报(自然科学版),2002,23(3):7-10.
[7]高经维,张煦,李峰,赵晖.求解TSP问题的遗传算法实现[J].计算机时代,2004,2:19-21.
[8]Z.米凯利维茨.演化程序——遗传算法和数据编码的结合[M].北京:科学出版社,2000.
[9]彭丹平,林志毅,王江晴.求解TSP的一种改进遗传算法[J].计算机工程与应用,2006,13:91-93.