全部 标题 作者
关键词 摘要

OALib Journal期刊
ISSN: 2333-9721
费用:99美元

查看量下载量

相关文章

更多...

一种基于Rough集理论的两阶段禁忌搜索算法*

, PP. 478-484

Keywords: 禁忌搜索(TS),Rough集,集中性,多样性,旅行商问题(TSP)

Full-Text   Cite this paper   Add to My Lib

Abstract:

针对以旅行商问题(TSP)为代表的组合优化问题提出一种基于Rough集理论的两阶段禁忌搜索算法.该算法没有采用多数自适应禁忌搜索算法所用的动态调整禁忌搜索参数的方式平衡集中性搜索和多样性搜索,而是采用两阶段搜索策略.第一阶段着眼于多样性搜索.通过激励搜索过程远离起点,对解空间进行相当程度的探索,在此基础上构造希望区域决策表,继而获得希望区域.第二阶段着眼于集中性搜索.以包含希望区域的最佳解作为起点进行集中性搜索.在选择当前解时,利用多样性搜索得到的路径信息进行有条件的限制.TSP基准问题的计算结果表明该算法是可行有效的.

References

[1]  Han Jianchao, Hu Xiaohua, Lin T Y, et al. A New Computation Model for Rough Set Theory Based on Database Systems // Proc of the 5th International Conference on Data Warehousing and Knowledge Discovery. Prague, Czechoslovakia, 2003: 381390
[2]  Wang Ling. Intelligent Optimization Algorithms with Applications. Beijing, China: Tsinghua University Press, 2001 (in Chinese) (王 凌.智能优化算法及其应用.北京:清华大学出版社, 2001)
[3]  Kalinli A, Karaboga D. Training Recurrent Neural Networks by Using Parallel Tabu Search Algorithm Based on Crossover Operation. Engineering Applications of Artificial Intelligence, 2004, 17(5): 529542
[4]  Chelouah R, Siarry P. Tabu Search Applied to Global Optimization. European Journal of Operational Research, 2000,123(2): 256270
[5]  Ferland J A, Ichoua S, Lavoie A, et al. Scheduling Using Tabu Search with Intensification and Diversification. Computers and Operations Research, 2001, 28 (11): 10751092
[6]  Michel G, Gilbert L, Frederic S. A Tabu Search Heuristic for the Undirected Selective Traveling Salesman Problem. European Journal of Operation Research, 1998, 106(1): 539545
[7]  He Yi, Liu Guangyuan, Qiu Yuhui. A New Adaptive Search Strategy of Intensification and Diversification in Tabu Search. Journal of Computer Research and Development, 2004, 41(1): 162166 (in Chinese) (贺 一,刘光远,邱玉辉. Tabu Search中集中性和多样性的自适应搜索策略.计算机研究与发展, 2004, 41(1): 162166)
[8]  Pawlak Z, GrzymalaBusse J, Slowinski R, et al. Rough Sets. Communication of the ACM, 1995, 38(11): 8995
[9]  Pawlak Z. Rough Sets: Theoretical Aspect of Reasoning about Data. Dordrecht, Netherlands: Kluwer Academic Publishers, 1991
[10]  Wang Guoyin. Rough Set Theory and Knowledge Acquisition. Xi’an, China: Xi’an Jiaotong University Press, 2001 (in Chinese) (王国胤. Rough集理论与知识获取.西安:西安交通大学出版社, 2001)
[11]  Higgins A J. A Dynamic Tabu Search for LargeScale Generalised Assignment Problems. Computers and Operations Research, 2001, 28(10): 10391048
[12]  Grabowskia J, Wodeckib M. A Very Fast Tabu Search Algorithm for the Permutation Flow Shop Problem with Makespan Criterion. Computers and Operations Research, 2004, 31(11): 18911909
[13]  Wong S K M, Ziarko W. On Optimal Decision Rules in Decision Table. Bulletin of Polish Academy of Science, 1985, 33(11/12): 693696
[14]  Jelonek J, Krowiec K, Slowinski R. Rough Set Reduction of Attributes and Their Domains for Neural Networks. Computational Intelligence, 1995, 11(2): 339347
[15]  Liu Shaohui, Sheng Qiujian, Wu Bin, et al. Research on Efficient Algorithms for Rough Set Methods. Chinese Journal of Computers, 2003, 26(5): 524529 (in Chinese) (刘少辉,盛秋戬,吴 斌,等.Rough集高效算法研究.计算机学报, 2003, 26(5): 524529)
[16]  Wang Jue, Wang Ju. Reduction Algorithms Based on Discernibility Matrix: The Ordered Attributes Method. Journal of Computer Science and Technology, 2001,16(6): 489504
[17]  Wang Guoyin, Yu Hong, Yang Dachun. Decision Table Reduction Based on Conditional Information Entropy. Chinese Journal of Computers, 2002, 25(7): 759766 (in Chinese) (王国胤,于 洪,杨大春.基于条件信息熵的决策表约简.计算机学报, 2002, 25(7): 759766)
[18]  Demirhan M, Ozdamar L. A Note on the Use of a Fuzzy Approach in Adaptive Partitioning Algorithms for Global Optimization. IEEE Trans on Fuzzy Systems, 1999, 7(4): 468475
[19]  Bazan J G, Skowron A, Synak P. Dynamic Reducts as a Tool for Extracting Laws from Decision Tables // Ras Z W, Zemankiva M, eds. Methodologies for Intelligent Systems. Berlin, Germany: SpringerVerlag, 1994: 346355
[20]  Li Fan, Liu Qihe, Ye Mao, et al. Approaches to Knowledge Reductions in Inconsistent Decision Tables. Control and Decision, 2006, 21(8): 857 862 (in Chinese) (李 凡,刘启和,叶 茂,等.不一致决策表的知识约简方法研究.控制与决策, 2006, 21(8): 857 862)
[21]  Li Fan, Liu Qihe, Yang Guowei. A New Crossover Operator Based on the Rough Set Theory for Genetic Algorithms // Proc of the 4th International Conference on Machine Learning and Cybernetics. Guangzhou, China, 2005, Ⅴ: 29072912
[22]  Glover F. Tabu Search-Part I. ORSA Journal on Computing, 1989, 1(3): 190206
[23]  Glover F. Tabu Search-Part II. ORSA Journal on Computing, 1990, 2(1): 432
[24]  Montemanni R, Moon J N J, Smith D H. An Improved Tabu Search Algorithm for the FixedSpectrum FrequencyAssignment Problem. IEEE Trans on Vehicular Technology, 2003, 52(4): 891901

Full-Text

Contact Us

service@oalib.com

QQ:3279437679

WhatsApp +8615387084133