竞选算法及其应用分析

《竞选算法及其应用分析》由会员上传分享，免费在线阅读，更多相关内容在学术论文-天天文库。

1、广东r[业大学硕十论文现代启发式算法为禁忌算法。在每次迭代中，也是由某当代点的邻域来得到下一代最优可能点。不同的是，该算法保存一个禁忌表，在禁忌表中出现的点不允许出现在下一代点中，这样就可以避免算法陷入局部最优。还有一种很重要的算法为基于群体(population)的算法。该类算法为概率算法，候选解作为群体中的个体被保存下来。典型的，遗传算法、粒子群算法和蚁群算法都属于这类算法。遗传算法口1是以决策变量的编码作为运算对象，直接以目标函数作为搜索信息，可同时在多点进行信息搜索，具有天生的并行性，使用概率搜索技术，增加了其搜索过程的灵活性。粒子群算法⋯初始化为一群

2、随机粒子(随机解)，然后通过迭代找到最优解，在每一次迭代中，粒子通过跟踪两个“极值"来更新自己，另一个极值是整个种群目前找到的最优解，粒子群算法具有收敛快的特点。蚁群算法⋯中蚂蚁运动时会在路径上释放出信息素寻找路径，蚂蚁之间交换着路径信息，通过信息素的作用使整个蚁群的行为具有非常高的自组织性，最终通过蚁群的集体自催化行为找出最优路径，蚁群算法具有很强的发现较好解的能力，最早成功应用于解决N-P难题中著名的旅行商问题。本文所要研究的竞选算法也为基于群体的算法。1．2竞选算法竞选算法¨1是一种原创性的算法，是新型的启发式算法，人们通过模拟自然界和人类社会的各种行为

3、、特征和机制，提出了一些具有优秀搜索能力的现代优化算法一一启发式优化算法，正如模仿物种进化的遗传算法、模拟金属冷却过程的退火算法、模拟蚂蚁觅食过程的蚁群算法、模拟鸟类或鱼群生活行为的粒子群算法、模拟人类和动物记忆功能的禁忌搜索算法等一样，竞选算法也是模拟人类的竞选活动而设计出来的，其搜索机制模拟竞选活动中对更高支持率的追求动机。竞选算法将搜索空间比拟成选民，竞选人是当前解。竞选人的支持率通过对选民的抽样调查来估算，选民的支持根据竞选人对选民的影响按比例分配给各个竞选人，根据支持的分布计算出支持率重心，即下一个竞选地点，如此反复进行的搜索，最终达到具有最高支持的

4、竞选地点，即全局最优解。2第一章绪论竞选算法和遗传算法有很多共同之处。两者都随机初始化种群，都使用评估值来评价系统，而且都根据评估值来进行一定的随机搜索。竞选算法与遗传算法的信息共享机制是很不同的。在遗传算法中，染色体互相共享信息，所以整个种群的移动是比较均匀的向最优区域移动。在竞选算法中，距离当前解距离近的信息以大权重传给下一循环，属于集中式的信息流动，整个搜索更新过程可能以更快的速度收敛。通过使用遗传算法的标准性能测试函数，对竞选算法进行了验算，证明算法高效可行。体现了竞选算法收敛快；齐次(只使用当前循环的信息)；参数多，灵活的优点。是一个有发展前景的优化

5、算法。目前，竞选算法已应用在图像处理¨1和机械设计n¨引等优化问题上，显示了良好的优化效果。1．3相关应用问题的研究概况1．3．1车间调度问题车间调度问题是一个古老而又传统的问题，对它的研究始于20世纪50年代，早在1954年Johnson对两台机床FlowShop型调度问题进行了研究后，提出了解决n／2／F／Cmax和部分特殊n／3／F／Cmax问题的优化算法，这代表调度理论研究的开始，以后它便开始了对调度问题进行了广泛研究‘91。60—70年代建立了调度理论的主体(经典调度理论)，并重视调度复杂性的研究。由于调度问题是制造系统中最基本，最重要而又最复杂的问

6、题之一，国内外无数的学者对其进行了广泛的探讨和研究，也提出了各种各样的算法，建立了不同的理论框架模型。车间调度问题的复杂性，各种不同的具体问题往往有很多不同的解决方法，因此需要从策略上去考虑车间调度问题，形成各种研究方法策略以指导对车间调度的研究。七十年代，人们开始了算法复杂性的研究，多数调度问题被证明属于N．P完全问题或N．P难问题，难以找到多项式算法，因此开始关注启发式算法。Panwalka总结和归纳出了113条调度规则，并对其进行了分类。七十年代末期，经典调度理论趋向成熟。随着70年代后期各类调度广东工业大学硕士论文问题与调度理论研究的深入及各种杂交学科

7、的发展，又涌现出了许多新的车间调度理论与方法，如：基于运筹学方法、基于控制的方法、基于启发式规则的调度方法、基于人工智能的方法、基于知识的调度方法、确定性最优化方法、整数规划、仿真调度方法等n01。八十年代初期，Stephen等从三个方面对调度进行了重新考察，对未来发展做了分析和预测，认为理论与实际的结合将会成为研究热点。这个富有挑战性的课题吸引了机械、计算机、管理等诸多领域的学者，许多跨学科的方法被应用到研究中。其中最引人注目的就是以Carnegie．Melton大学的M．Fox为代表的学者们开展的基于约束传播的ISIS研究，它标志了人工智能开始真正应用于调

8、度问题。八十年代后期，Rodarnme