竞选算法及其应用研究
|
摘要
无免费午餐定理(No Free Lunch Theorems)证明了一个特定的优化问题一定存在着最适用的优化算法的必然性。因此,探索新型的优化算法将始终是一项有科学意义和实用价值的工作。竞选算法是一种新型的启发式优化算法,其搜索机制模拟竞选活动中对更高支持率的追求动机。本文研究竞选算法及其适用领域,选取了优化问题中两个热点和难点问题——车间调度问题和机器人路径规划问题作为竞选算法优化应用的研究对象,探讨竞选算法在求解车间调度和机器人路径规划问题上的有效性和相关的特点。
本文首先介绍最新的优化算法——竞选算法的基本思想,实现过程和特点,并使用验证函数对竞选算法进行检验,结果表明,竞选算法无论在局部挖掘还是全局搜索上均表现出优异的性能,是一个有发展前景的优化算法。
其次,研究了车间调度问题相关内容,并在此基础上设计了一种实现车间调度的竞选算法,引入一种解的新表达法,并建立了相应的解译规则,避免了非法解的产生;对获得适应度函数的方法进行了探讨。经对MT06调度问题实验证明,取得良好的效果。
再次,根据移动机器人路径规划问题的特性,设计出一种新的基于竞选算法的移动机器人全局最优路径规划方法。该方法包括三个步骤:第一步是采用链接图理论建立移动机器人的自由空间模型,第二步是采用Dijkstra算法在自由空间中搜索出一条无碰撞次优路径,第三步是采用竞选算法对次优路径的位置进行调整和优化,从而得到机器人的全局最优路径。仿真实验的结果显示这种方法建模相对简单,能有效地找到全局最优路径。
最后,对整个论文的工作进行了总结,并指明可以改善算法的收敛性和研究竞选算法的空间扩展性作为进一步探索的方向。
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.
本文首先介绍最新的优化算法——竞选算法的基本思想,实现过程和特点,并使用验证函数对竞选算法进行检验,结果表明,竞选算法无论在局部挖掘还是全局搜索上均表现出优异的性能,是一个有发展前景的优化算法。
其次,研究了车间调度问题相关内容,并在此基础上设计了一种实现车间调度的竞选算法,引入一种解的新表达法,并建立了相应的解译规则,避免了非法解的产生;对获得适应度函数的方法进行了探讨。经对MT06调度问题实验证明,取得良好的效果。
再次,根据移动机器人路径规划问题的特性,设计出一种新的基于竞选算法的移动机器人全局最优路径规划方法。该方法包括三个步骤:第一步是采用链接图理论建立移动机器人的自由空间模型,第二步是采用Dijkstra算法在自由空间中搜索出一条无碰撞次优路径,第三步是采用竞选算法对次优路径的位置进行调整和优化,从而得到机器人的全局最优路径。仿真实验的结果显示这种方法建模相对简单,能有效地找到全局最优路径。
最后,对整个论文的工作进行了总结,并指明可以改善算法的收敛性和研究竞选算法的空间扩展性作为进一步探索的方向。
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.
引文
[1]Vesterstroem,Jakob S and Riget,Jacques.Particle Swarms:Extensions for Improved Local,Multi-modal,and Dynamic Search in Numerical Optimization[D]:[Master's thesis Department of Computer Science].Danmark:University of Aarhus,2002
[2]Kirkpatrick S,C.D.Gelatt Jr,M.P.Vecchi.Optimization by Simulated Annealing[J].Science,1983(3):671-680
[3]徐宁,李春光,张健等.几种现代优化算法的比较研究[J].系统工程与电子技术,2002,24(12):100-103
[4]段海滨,王道波,于秀芬.几种新型仿生优化算法的比较研究[J].计算机仿真,2007,24(3):169-172
[5]吕文阁,袁清坷,骆少明等.一种新型的启发式优化算法一竞选算法[A].2006年全国组合优化学术会议论文,郑州:2006
[6]杜健辉,吕文阁,侯梦华.基于竞选算法的Otsu阂值快速确定方法[J].机电工程,2007,36(3):57-58
[7]郑玲利,吕文阁.基于竞选算法的机床主轴结构优化设计[J].机械设计与制造,2006,(08):35-37
[8]吕文阁,杜健辉,李劲等.用竞选算法优化双万向轴的设计[J].材料研究与应用,2007,1(03):221-223
[9]Nontazeri M.And Van Wassenhove L.N.Analysis of scheduling rules for an FMS[J].International Journal of Production Research,1990,28:785-802
[10]E.L.Lawler.Management Sci.sequencing of a single machine subject to precedence[J].Optimal constraints,1973,1(19):544-546
[11]Y.Cho,S.Sahni.preemptive scheduling of independent jobs with release and due times on open,flow and job shops[J],oper.Res,1981,29:511-522
[12]Wu,Szu-Yung,David and Richard A.Wysk.An application of discrete-event sumulation to Int.J.Prod.Reson-line control and scheduling in flexible manufacturing[J].oper.Res,1989,12(9):1603-1623
[13]刘作军.基于电路地图的移动机器人路径规划方法研究[D]:[博士学位论文].天津:南开大学,2005年
[14]张捍东,郑睿等.移动机器人路径规划技术的现状与展望[J].系统仿真学报,2005,17(2):439-443
[15]石鸿雁,孙茂相,孙昌志.未知环境下移动机器人路径规划方法[J].沈阳工业大学学报,2005,27(1):63-69
[16]D H Wolpert,W G Macready.No free lunch theorems for optimization[J].IEEE Transactions on Evolutionary Computation,1997,1(1):67-82
[17]李敏强,冠纪淞,林丹等.遗传算法的基本原理与应用[M].北京:科学出版社,2002
[18]Graves S.A Review of Production Scheduling[J].Operations Research,1981,29(4):646-675
[19]Garey M,Tarjan R,Wilfong G.One-processor scheduling with symmetric earliness and tardiness penalties[J].Mathematics of Operations Research,1988,13:330
[20]李素萍.生产调度系统在企业中的应用[J].煤矿机械,2005,3
[21]秦绪伟,罗焕佐.流程工业计划调度技术研究与发展分析[J].计算机工程与应用,2004,19:1-5
[22]张海燕,姜莉莉.一种新型的车间作业计划及调度监控集成系统的实施[J].机床与液压,2002,2:42-44.
[23]玄光男,程润伟.遗传算法与工程优化[M].清华大学出版社,2004
[24]李启堂,丁书斌,王敏等.基于混合遗传算法的车间调度问题研究[J].机械设计与制造,200 7,5:199-201
[25]周陆俊.计算机辅助车间作业计划研究[D]:[硕士研究生学位论文].南京:南京林业大学,2005,6:35-36
[26]Claude Pegard.A mobile robot using a panoramic view[A].Proceeding of the 1996 IEEE Int.Con.On robotics and Au-tomation,Minneapolis,1996:89-94
[27]R A V Brooks.Solving the Find-Path Problem by Good Representation of Free Space[J].IEEE Trans on Sys Man and Cybern,1983,13(3):190-197.
[28]C.Wongngamnit,D.Angluin.The robot,the grid,and the algorithm[A].Technical Report,YALE/DCS/TR-1188.Yale University Computer Science Department,New Haven.CT,1999
[29]Qussama Khatib.Real-Time Obstacle Avoidance for Manipulators and Mobile Robots[J].Proc of The 1994 IEEE.
[30]张颖,吴成东,原宝龙.机器人路径规划方法综述[J].控制工程,2003.10:152-155
[31]周明,孙树栋.遗传算法原理及应用[M].国防工业出版社,1999
[32]Tsoukalas L.H,Houstis EN,Jones GV.Neurofuzzy motion planners for intelligent robots[J].Journal of Intelligent and Robotic Systems,1997,19:339-356
[33]刘彩虹,胡吉全,齐晓宁.基于混合遗传算法的连续空间下机器人的路径规划[J].武汉理工大学学报(自然科学版),2003,27(6):819-821
[34]秦元庆,孙德宝,李宁等.基于粒子群算法的移动机器人路径规划[J].机器人,2004,26(3):222-225
[35]Habib M K,Asama H.Eficient method to generate collision free paths for autonomous mobile robot based on new free space structuring approach[C].IEEE/RSJ International Workshop on Intelligent Robots and Systems,Osaka,Japan,1991:56-356
[36]严蔚敏,吴伟民.数据结构(C语言版)[M].北京:清华大学出版社,1997
[37]王万良 吴启迪 生产调度智能算法及其应用[M].北京:科学出版社,2007,4
[38]毕慧敏,董海鹰.改进遗传算法在机器人路径规划中的应用[J].测控技术,2005,25(4):53-54
[39]孙树栋,曲彦宾.遗传算法在机器人路径规划中的应用研究[J].西北工业大学学报,1998,16(1):79-83
[40]周明,孙树栋,彭炎午.用遗传算法规划移动机器人路径[J],西北工业大学学报,1998,16(4):581-583
[41]刘成良,张凯,付庄等.神经网络在机器人路径规划中的应用研究[J].机器人,2001,23(7):605-608
[42]樊长虹,卢有章,刘宏等.基于神经网络的移动机器人路径规划[J].计算机工程与应用,2004(8):86-89
[43]龚进峰,彭商贤.数字势场和遗传算法的机器人路径规划的方法[J].天津大学学报,2002,35(4):525-529
[44]武彬,吴耿锋,马飞等.基于免疫算法的移动机器人路径规划系统,计算机工程,2004,30(12):122-123
[45]宋道金,李宏涛,李彩等.基于混沌控制的移动机器人的路径规划[J].计算机应用研究,2004(2):34-36
[46]李彩虹,张景元,李贻斌.基于模糊控制的移动机器人的路径规划[J].淄博学院学报,2001,3(3):27-30
[47][日]白井良明.机器人工程[M],北京:科学出版社,2001
[48]殷际英、何广平.关节机器人[M],北京:化学工业出版社 2003
[49]雷英杰、张善文、李续武等.Matlab遗传算法工具箱及应用[M],西安:西安电子科技大学出版社,2005.
[50]飞思科技产品研发中心.matlab 6.5辅助优化计算与设计[M],北京:电子工业出版社,2003
[2]Kirkpatrick S,C.D.Gelatt Jr,M.P.Vecchi.Optimization by Simulated Annealing[J].Science,1983(3):671-680
[3]徐宁,李春光,张健等.几种现代优化算法的比较研究[J].系统工程与电子技术,2002,24(12):100-103
[4]段海滨,王道波,于秀芬.几种新型仿生优化算法的比较研究[J].计算机仿真,2007,24(3):169-172
[5]吕文阁,袁清坷,骆少明等.一种新型的启发式优化算法一竞选算法[A].2006年全国组合优化学术会议论文,郑州:2006
[6]杜健辉,吕文阁,侯梦华.基于竞选算法的Otsu阂值快速确定方法[J].机电工程,2007,36(3):57-58
[7]郑玲利,吕文阁.基于竞选算法的机床主轴结构优化设计[J].机械设计与制造,2006,(08):35-37
[8]吕文阁,杜健辉,李劲等.用竞选算法优化双万向轴的设计[J].材料研究与应用,2007,1(03):221-223
[9]Nontazeri M.And Van Wassenhove L.N.Analysis of scheduling rules for an FMS[J].International Journal of Production Research,1990,28:785-802
[10]E.L.Lawler.Management Sci.sequencing of a single machine subject to precedence[J].Optimal constraints,1973,1(19):544-546
[11]Y.Cho,S.Sahni.preemptive scheduling of independent jobs with release and due times on open,flow and job shops[J],oper.Res,1981,29:511-522
[12]Wu,Szu-Yung,David and Richard A.Wysk.An application of discrete-event sumulation to Int.J.Prod.Reson-line control and scheduling in flexible manufacturing[J].oper.Res,1989,12(9):1603-1623
[13]刘作军.基于电路地图的移动机器人路径规划方法研究[D]:[博士学位论文].天津:南开大学,2005年
[14]张捍东,郑睿等.移动机器人路径规划技术的现状与展望[J].系统仿真学报,2005,17(2):439-443
[15]石鸿雁,孙茂相,孙昌志.未知环境下移动机器人路径规划方法[J].沈阳工业大学学报,2005,27(1):63-69
[16]D H Wolpert,W G Macready.No free lunch theorems for optimization[J].IEEE Transactions on Evolutionary Computation,1997,1(1):67-82
[17]李敏强,冠纪淞,林丹等.遗传算法的基本原理与应用[M].北京:科学出版社,2002
[18]Graves S.A Review of Production Scheduling[J].Operations Research,1981,29(4):646-675
[19]Garey M,Tarjan R,Wilfong G.One-processor scheduling with symmetric earliness and tardiness penalties[J].Mathematics of Operations Research,1988,13:330
[20]李素萍.生产调度系统在企业中的应用[J].煤矿机械,2005,3
[21]秦绪伟,罗焕佐.流程工业计划调度技术研究与发展分析[J].计算机工程与应用,2004,19:1-5
[22]张海燕,姜莉莉.一种新型的车间作业计划及调度监控集成系统的实施[J].机床与液压,2002,2:42-44.
[23]玄光男,程润伟.遗传算法与工程优化[M].清华大学出版社,2004
[24]李启堂,丁书斌,王敏等.基于混合遗传算法的车间调度问题研究[J].机械设计与制造,200 7,5:199-201
[25]周陆俊.计算机辅助车间作业计划研究[D]:[硕士研究生学位论文].南京:南京林业大学,2005,6:35-36
[26]Claude Pegard.A mobile robot using a panoramic view[A].Proceeding of the 1996 IEEE Int.Con.On robotics and Au-tomation,Minneapolis,1996:89-94
[27]R A V Brooks.Solving the Find-Path Problem by Good Representation of Free Space[J].IEEE Trans on Sys Man and Cybern,1983,13(3):190-197.
[28]C.Wongngamnit,D.Angluin.The robot,the grid,and the algorithm[A].Technical Report,YALE/DCS/TR-1188.Yale University Computer Science Department,New Haven.CT,1999
[29]Qussama Khatib.Real-Time Obstacle Avoidance for Manipulators and Mobile Robots[J].Proc of The 1994 IEEE.
[30]张颖,吴成东,原宝龙.机器人路径规划方法综述[J].控制工程,2003.10:152-155
[31]周明,孙树栋.遗传算法原理及应用[M].国防工业出版社,1999
[32]Tsoukalas L.H,Houstis EN,Jones GV.Neurofuzzy motion planners for intelligent robots[J].Journal of Intelligent and Robotic Systems,1997,19:339-356
[33]刘彩虹,胡吉全,齐晓宁.基于混合遗传算法的连续空间下机器人的路径规划[J].武汉理工大学学报(自然科学版),2003,27(6):819-821
[34]秦元庆,孙德宝,李宁等.基于粒子群算法的移动机器人路径规划[J].机器人,2004,26(3):222-225
[35]Habib M K,Asama H.Eficient method to generate collision free paths for autonomous mobile robot based on new free space structuring approach[C].IEEE/RSJ International Workshop on Intelligent Robots and Systems,Osaka,Japan,1991:56-356
[36]严蔚敏,吴伟民.数据结构(C语言版)[M].北京:清华大学出版社,1997
[37]王万良 吴启迪 生产调度智能算法及其应用[M].北京:科学出版社,2007,4
[38]毕慧敏,董海鹰.改进遗传算法在机器人路径规划中的应用[J].测控技术,2005,25(4):53-54
[39]孙树栋,曲彦宾.遗传算法在机器人路径规划中的应用研究[J].西北工业大学学报,1998,16(1):79-83
[40]周明,孙树栋,彭炎午.用遗传算法规划移动机器人路径[J],西北工业大学学报,1998,16(4):581-583
[41]刘成良,张凯,付庄等.神经网络在机器人路径规划中的应用研究[J].机器人,2001,23(7):605-608
[42]樊长虹,卢有章,刘宏等.基于神经网络的移动机器人路径规划[J].计算机工程与应用,2004(8):86-89
[43]龚进峰,彭商贤.数字势场和遗传算法的机器人路径规划的方法[J].天津大学学报,2002,35(4):525-529
[44]武彬,吴耿锋,马飞等.基于免疫算法的移动机器人路径规划系统,计算机工程,2004,30(12):122-123
[45]宋道金,李宏涛,李彩等.基于混沌控制的移动机器人的路径规划[J].计算机应用研究,2004(2):34-36
[46]李彩虹,张景元,李贻斌.基于模糊控制的移动机器人的路径规划[J].淄博学院学报,2001,3(3):27-30
[47][日]白井良明.机器人工程[M],北京:科学出版社,2001
[48]殷际英、何广平.关节机器人[M],北京:化学工业出版社 2003
[49]雷英杰、张善文、李续武等.Matlab遗传算法工具箱及应用[M],西安:西安电子科技大学出版社,2005.
[50]飞思科技产品研发中心.matlab 6.5辅助优化计算与设计[M],北京:电子工业出版社,2003