计算机工程与应用 ›› 2009, Vol. 45 ›› Issue (4): 45-47.DOI: 10.3778/j.issn.1002-8331.2009.04.013

• 研究、探讨 • 上一篇    下一篇

快速倒序算子的研究

闭应洲1,2,丁立新1,杨小雄3   

  1. 1.武汉大学 软件工程国家重点实验室,武汉 430072
    2.广西师范学院 信息技术系,南宁 530001
    3.广西师范学院 资源与环境科学学院,南宁 530001
  • 收稿日期:2008-01-09 修回日期:2008-03-31 出版日期:2009-02-01 发布日期:2009-02-01
  • 通讯作者: 闭应洲

On faster inversion operator

BI Ying-zhou1,2,DING Li-xin1,YANG Xiao-xiong3   

  1. 1.State Key Laboratory of Software Engineering,Wuhan University,Wuhan 430072,China
    2.Department of Information Technology,Guangxi Teachers Education University,Nanning 530001,China
    3.School of Resource & Environment Science,Guangxi Teachers Education University,Nanning 530001,China
  • Received:2008-01-09 Revised:2008-03-31 Online:2009-02-01 Published:2009-02-01
  • Contact: BI Ying-zhou

摘要: 为了有效地处理建筑块,Bagley最先提出了应用倒序算子来对定义建筑块的基因进行适应性聚集。但是Bagley和Frantz的研究都表明,倒序算子太慢,作用不明显。针对TSP问题,郭涛提出一个“带导向的”倒序算子,取得了很好的效果。为了设计更快速的倒序算子,提出结合粒子群优化的方法改进郭涛算法,更好地利用当前最优解指导倒序,同时对个体施加倒序运算后立即评估,如有改进马上保存,从而巩固所获取的建筑块,不至于因为后面的错误而导致前功尽弃。实验结果证明了新算法的可行性。

关键词: 郭涛算子, 粒子群优化, 快速倒序算子

Abstract: To process building-blocks effectively,Bagley first presented the inversion operator for aggregating the genes defining building-blocks.However,Bagley and Frantz both reported that inversion was too slow and not very effective.Guotao used a “guided” inversion operator for TSP and it performed successfully.To design a faster inversion operator,this paper presented that combining Guotao’s operator with the idea from Particle Swarm Optimization,and evaluating immediately the individual while it is inverted.If the immediate solution is better,it should replace the old one.In this way,all the building-blocks from searching can be saved and exploited effectively.

Key words: Guotao operator, Particle Swarm Optimization(PSO), faster inversion operator