【作者】 李劲；

【导师】 吕文阁；

【作者基本信息】 广东工业大学 ， 机械设计及理论， 2008， 硕士

【摘要】 无免费午餐定理(No Free Lunch Theorems)证明了一个特定的优化问题一定存在着最适用的优化算法的必然性。因此,探索新型的优化算法将始终是一项有科学意义和实用价值的工作。竞选算法是一种新型的启发式优化算法,其搜索机制模拟竞选活动中对更高支持率的追求动机。本文研究竞选算法及其适用领域,选取了优化问题中两个热点和难点问题——车间调度问题和机器人路径规划问题作为竞选算法优化应用的研究对象,探讨竞选算法在求解车间调度和机器人路径规划问题上的有效性和相关的特点。本文首先介绍最新的优化算法——竞选算法的基本思想,实现过程和特点,并使用验证函数对竞选算法进行检验,结果表明,竞选算法无论在局部挖掘还是全局搜索上均表现出优异的性能,是一个有发展前景的优化算法。其次,研究了车间调度问题相关内容,并在此基础上设计了一种实现车间调度的竞选算法,引入一种解的新表达法,并建立了相应的解译规则,避免了非法解的产生;对获得适应度函数的方法进行了探讨。经对MT06调度问题实验证明,取得良好的效果。再次,根据移动机器人路径规划问题的特性,设计出一种新的基于竞选算法的移动机器人全局最优路径规划方法。该方法包括三个步骤:第一步是采用链接图理论建立移动机器人的自由空间模型,第二步是采用Dijkstra算法在自由空间中搜索出一条无碰撞次优路径,第三步是采用竞选算法对次优路径的位置进行调整和优化,从而得到机器人的全局最优路径。仿真实验的结果显示这种方法建模相对简单,能有效地找到全局最优路径。最后,对整个论文的工作进行了总结,并指明可以改善算法的收敛性和研究竞选算法的空间扩展性作为进一步探索的方向。更多还原

【Abstract】 NFL(No Free Lunch Theorems) proves that a specific optimization problem has inevitably the most corresponding optimization algorithm. Therefore, exploring new optimization algorithms will always be a work of scientific and practical value.Election-survey Algorithm is a new heuristic optimization algorithm, It simulates the motivation of election candidates to obtain the highest support ratio in campaign.This paper researchs Election-survey Algorithm and its suitable realm. This paper selects two hot and difficult issues in optimization problem-Job Shop Scheduling and robot path planning-as study objects of Election-survey Algorithm optimization application,and argues effectiveness and related characteristics about solving Job Shop Scheduling and robot path planning.Firstly ,This paper introduces the latest optimization algorithm - basic idea, implementation and characteristics of Election-survey Algorithm, and applys test function to verify Election-survey Algorithm, The computing results show that Election-survey Algorithm demonstrated outstanding performance in local excavation and global search,and is a promising optimization algorithm.Secondly, This paper researchs subjects concerning Job Shop Scheduling problems, and design an kind of Election-survey Algorithm to achieve Job Shop Scheduling, introduce a new method to express solution, and establish corresponding decoding rules to prevent illegal results; discuss the method earning fitness function. Experiment on scheduling problem MT06 had a good effect.Thirdly, basing on characteristics of mobile robot path planning, we designs a kind of Election-survey Algorithm to solve global optimal result of mobile robot path planning. This method consists of three steps: The first step is to establish free space model of mobile robot by a link graph theory, the second step is to use the Dijkstra algorithm to search out a suboptimal collision-free path in free space, the third step is to use Election-survey Algorithm to readjust and optimize location of sub-optimal path ,and then obtain the global optimal robot path. Simulation result show that this modeling method is relatively simple and can effectively find the global optimal path.Finally, the paper summaries all the work,and points out that improving convergence of Election-survey Algorithm and researching expansion of the Algorithm is further direction of exploration.更多还原