求解组合优化问题混合蛙跳算法研究.pdf

A Dissertation Submitted to shijiazhuang University of Economics For the Academic Degree of Master of Engineering Research on binational Optimization in Shuffled Frog Leaping Algorithm Candidate:WangYuanyuan Supervisor:ProfessorWangYanqi Academic Degree Applied for:Master puter Application Technology School/Department:shijiazhuang University of Economics shijiazhuang University of Economics June, 2010 独创性声明本人郑重声明:所呈交的论文是我在导师指导下进行的研究工作及取得的研究成果。尽我所知,除了文中特别加以标注和致谢的地方外,论文中不包含其他人已经发表或撰写的研究成果,也不包含为获得石家庄经济学院或其他教育机构的学位或证书所使用过的材料。与我一同工作的同志对本研究所做的任何贡献均已在论文中作了明确的说明并表示了谢意。签名: 日期: 关于论文使用授权的说明本人完全了解石家庄经济学院有关保留、使用学位论文的规定,即: 学校有权保留送交论文的复印件,允许论文被查阅和借阅;学校可以公布论文的全部或部分内容,可以采用影印、缩印或其他复制手段保存论文。(保密的论文在解密后应遵守此规定) 签名: 导师签名: 日期: I 摘要群体智能算法是一种高效的优化算法。由单个结构复杂的个体所完成的任务可由大量结构简单的个体所组成的群体合作来完成,并且后者往往更具有健壮性、灵活性和经济上的优势。在无集中控制且不提供全局模型的前提下,群体智能算法为解决组合优化问题提供了一种新对策。混合蛙跳算法是一种新兴的群体智能算法。目前,利用混合蛙跳算法求解组合优化问题的相关成果不多见。本文对于如何利用混合蛙跳算法求解组合优化问题进行了探讨。主要研究成果如下: 首先,传统的混合蛙跳算法是通过全局最优解和当前子种群的局部最优解对子种群中的最差个体施加影响,这种优化方式是对子种群中的单一个体施加影响。在第三章中,本文提出了一种利用全局最优解“指导”每个子种群整体向前进化的策略。与传统的混合蛙跳算法不同,这种子种群进化策略可以同时作用于多个个体,是一种并行爬山的进化方式。随着城市数量的增加,常见的演化算法容易陷入局部极值的陷阱, 无法搜索到全局最优路径。由于将郭涛算法和混合蛙跳算法的优点进行了有机的结合,“当前最优解作用于整个子种群”的混合蛙跳算法在求解TSP问题时表现出了良好的性能,能够以极小的时间代价搜索到用户的满意解。其次,传统的混合蛙跳算法是通过全局最优解和当前子种群的局部最优解“吸引”每个子种群中的最差青蛙。通过这种“吸引”的作用,这两个个体指导了最差青蛙的进化方向。与传统的混合蛙跳算法不同,本文利用子种群中的其它个体对最差的个体的“排斥”作用来指导最差青蛙的进化方向。第四章中,本文利用“排斥最差个体”的混合蛙跳算法求解背包问题,该算法能够高效率地搜索到问题的全局最优解。关键词:混合蛙跳算法;组合优化;局部搜索策略;旅行商问题;背包问题 II Abstract Swarm intelligence algorithm is an efficient optimization algorithm. Large amount of simple individuals have more advantages over a single complex one. The simple individuals often show better performance on robustness、flexibility and a smaller economic cost. Swarm intelligence provides a new way to solve the combinational optimization problems without global control and global model. The Shuffled Frog Leaping algorithm(SFLA) is a kind of rising swarm intelligence optimizer. Currently , there is rare research on the