首页 | 本学科首页   官方微博 | 高级检索  
     


Evolutionary algorithms,simulated annealing and tabu search: a comparative study
Affiliation:1. Department of Management Sciences, City University of Hong Kong, Tat Chee Ave, Kowloon Tong, Hong Kong;2. School of Information Technology, Jiangxi University of Finance and Economics, Nanchang, Jiangxi 330013, People’s Republic of China;3. International Center of Management Science and Engineering, School of Management and Engineering, Nanjing University, Nanjing 210093, People''s Republic of China;4. Department of Industrial & Systems Engineering, National University of Singapore, Singapore;1. Research Group Logistics, Hasselt University, Agoralaan Gebouw D, 3590 Diepenbeek, Belgium;2. Research Foundation Flanders (FWO), Egmontstraat 5, 1000 Brussels, Belgium;3. CORMSIS Centre of Operational Research, Management Sciences and Information Systems, University of Southampton, Southampton, SO17 1BJ, UK;1. State Key Laboratory of Digital Manufacturing Equipment and Technology, School of Mechanical Science and Engineering, Huazhong University of Science and Technology, Wuhan 430074, China;2. School of Mechatronic Engineering and Automation, Shanghai University
Abstract:Evolutionary algorithms, simulated annealing (SA), and tabu search (TS) are general iterative algorithms for combinatorial optimization. The term evolutionary algorithm is used to refer to any probabilistic algorithm whose design is inspired by evolutionary mechanisms found in biological species. Most widely known algorithms of this category are genetic algorithms (GA). GA, SA, and TS have been found to be very effective and robust in solving numerous problems from a wide range of application domains. Furthermore, they are even suitable for ill-posed problems where some of the parameters are not known before hand. These properties are lacking in all traditional optimization techniques. In this paper we perform a comparative study among GA, SA, and TS. These algorithms have many similarities, but they also possess distinctive features, mainly in their strategies for searching the solution state space. The three heuristics are applied on the same optimization problem and compared with respect to (1) quality of the best solution identified by each heuristic, (2) progress of the search from initial solution(s) until stopping criteria are met, (3) the progress of the cost of the best solution as a function of time (iteration count), and (4) the number of solutions found at successive intervals of the cost function. The benchmark problem used is the floorplanning of very large scale integrated (VLSI) circuits. This is a hard multi-criteria optimization problem. Fuzzy logic is used to combine all objective criteria into a single fuzzy evaluation (cost) function, which is then used to rate competing solutions.
Keywords:
本文献已被 ScienceDirect 等数据库收录!
设为首页 | 免责声明 | 关于勤云 | 加入收藏

Copyright©北京勤云科技发展有限公司  京ICP备09084417号