基于交叉算子和邻域搜索算子的离散粒子群优化算法
A Novel Discrete Particle Swarm Optimization Algorithm Base on Crossover Operator and Neighborhood Search
DOI: 10.12677/CSA.2017.712141, PDF,    国家科技经费支持
作者: 张文学*：宁夏医科大学 理学院，宁夏 银川；韦晓宁：宁夏医科大学附属回医中医医院 信息科，宁夏 吴忠；万晓伟：宁夏第五人民医院 信息科，宁夏 石嘴山
关键词: 离散粒子群；交叉算子；邻域搜索；组合优化；流水车间调度；Discrete Particle Swarm Optimization； Crossover Operator； Neighborhood Search； Combinatorial Optimization； Flowshop Scheduling
摘要: 基于交叉算子、邻域搜索算子和粒子群算法信息更新的本质机理，重新定义了粒子的基本运算，包含粒子位置的减法运算，粒子速度的数乘运算、加法运算以及粒子位置与速度的加法运算；提出了一种通用的新型离散粒子群优化算法；最后，以流水车间调度问题中23个标准算例为实验数据进行了仿真实验，实验结果表明了本文所提出算法的有效性。
Abstract: Based on crossover operator, neighborhood search and the essential mechanism of information updating in particle swarm optimization, a novel discrete particle swarm optimization (NDPSO) algorithm is proposed in which some basic operations on particles velocity and location are redefined. The NDPSO is a general-purpose optimizing model for combinatorial optimization problem; It is evaluated with 23 benchmark instances of flowshop scheduling problem and found to be more efficient and effective than existing algorithms.
文章引用：张文学, 韦晓宁, 万晓伟. 基于交叉算子和邻域搜索算子的离散粒子群优化算法[J]. 计算机科学与应用, 2017, 7(12): 1262-1269. https://doi.org/10.12677/CSA.2017.712141

参考文献

[1] Eberhard, R. and Kennedy, J. (1995) A New Optimizer Using Particle Swarm Theory. Proceedings of Sixth International Symposium on Micro Machine and Human Science, Nagoya, 4-6 October 1995, 39-43. [Google Scholar] [CrossRef] 
[2] Kennedy, J. and Eberhard, R. (1995) Particle Swarm Optimization. Proceedings of IEEE Conference on Neural Networks, Piscataway, IEEE Press, 1942-1948. [Google Scholar] [CrossRef] 
[3] Lin, C.J. and Hsieh, M.H. (2008) Classification of Mental Task from EEG Data Using Neural Networks Based on Particle Swarm Optimization. Neurocomputing, 72, 1121-1130. [Google Scholar] [CrossRef] 
[4] 谈超, 李小平. 双目标无等待流水线调度的加权混合算法[J]. 计算机科学, 2008(11): 199-213.
[5] Karakuzu, C. (2008) Fuzzy Controller Training Using Particle Swarm Optimization for Nonlinear System Control. ISA Transactions, 47, 229-239. [Google Scholar] [CrossRef] [PubMed]
[6] 沈林成, 霍霄华, 牛轶峰. 离散粒子群优化算法研究现状综述[J]. 系统工程与电子技术, 2008(10): 1986-1994.
[7] Clerc, M. (2004) Discrete Particle Swarm Optimization Illustrated by the Traveling Salesman Problem. Springer Berlin Heidelberg, 47, 219-239. [Google Scholar] [CrossRef] 
[8] Wang, K.P., Huang, L., Zhou, C.G., et al. (2003) Particle Swarm Optimization for Traveling Salesman Problem. International Conference on Machine Learning and Cybernetics, 3, 1583-1585.
[9] Shi, X.H., Liang, Y.C., Lee, H.P., et al. (2007) Particle Swarm Optimization-Based Algorithms for TSP and Generalized TSP. Information Processing Letters, 103, 169-176. [Google Scholar] [CrossRef] 
[10] Shi, Y. and Eberhard, R. (1998) A Modified Particle Swarm Optimizer. IEEE World Congress on Computational Intelligence, Anchorage, 69-73. [Google Scholar] [CrossRef] 
[11] Murata, T., Ishibuchi, H. and Tanaka, H. (1996) Genetic Algorithms for Flowshop Scheduling Problems. Computers and Industrial Engineering, 30, 1061-1071. [Google Scholar] [CrossRef] 
[12] Eksioglu, B., Eksioglu, S.D. and Jain, P. (2008) A Tabu Search Algorithm for the Flowshop Scheduling Problem with Changing Neighborhoods. Computers & Industrial Engineering, 54, 1-11. [Google Scholar] [CrossRef] 
[13] Lawler, E.L., Lenstra, J.K., Rinnooy, K.A., et al. (1997) The Traveling Salesman Problem—A Guided Tour of Combinatorial Optimization. John Wiley & Sons, Hoboken.
[14] Grabowski, J. and Pempera, J. (2005) Some Local Search Algorithm Search for No-Wait Flow-Shop Problem with Makespan Criterion. Computers & Operations Research, 32, 2197-2212. [Google Scholar] [CrossRef] 
[15] Schuster, C.J. and Framinan, J.M. (2003) Approximative Procedures for No-Wait Job Shop Scheduling. Operations Research Letters, 31, 308-318. [Google Scholar] [CrossRef] 
[16] 潘全科, 谢圣献, 张亚卿, 等. 解决无等待流水线调度问题的新算法[J]. 机械科学与技术, 2006(12): 1487-1490.
[17] Rajendran, C. (1994) A No-Wait Flowshop Scheduling Heuristic to Minimize Makespan. Journal of the Operational Research Society, 45, 472-478. [Google Scholar] [CrossRef]