水波优化算法

水波优化算法（Water wave optimization, WWO） 是一种基于浅水波理论的启发式算法。 它是由郑宇军教授于2015年提出的[1]。

算法简介

水波优化算法(Water Wave Optimization, WWO)是一种新兴的基于浅水波理论的元启发式算法。该算法将种群中每个解类比为一个具有波长λ和波高h的“水波”，通过模拟水波的传播、折射和碎浪运动机制在解空间中进行高效搜索。算法将待求解优化问题和浅水波模型进行类比，如表 1 所示。

表 1 浅水波模型与实际问题之间的对应关系

水波优化算法的核心是为每个解分配与其适应度成反比的波长，并使每个解传播(搜索)范围与其波长成正比例:距离海平面越近的点，对应的解越优，相应的水波越高，那么水波的波高越大、波长越小，如图 1 所示。在 每一次的迭代过程中，传播操作使每个波 x在与其波长λx成比例的范围内移 动每个维度d来创建新的波 x'，如下式所示。

其中函数 rand 用于生成指定范围内的一个随机数，L(d)表示解空间在d维上的长度。

图 1 WWO 中解的适应度、波长和波高的关系

WWO 还提供了反射和碎浪两个操作。当某个解经过指定次迭代后仍未 改进，其能量耗尽，波高将为 0，那么应用反射操作将其替换为其与当前最优解之间的一个随机解，以避免算法搜索陷入停滞。每当发现一个新的当前 最优解，则应用碎浪操作就会把它分裂出几个孤立的波，每个波在一个随机的方向上从新的最佳波移动一小段距离，从而加强局部搜索。通过上述操作，WWO算法能够在全局搜索和局部搜索间达到一个很好的动态平衡。

相关研究

自 WWO 算法被提出以来，因其框架简单、易于实施、控制参数较少、性能优等特点引起了相当多的关注。目前的研究主要在两个方面:一方面研究是改进算法中的算子和种群学习机制来提高算法的性能和收敛性,可以通过改变自身算子[2-5]或者将 WWO 与其他启发式和元启发式相结合[6-11]，目前，WWO 算法及其变体已应用于许多工业问题[12-23]。另一个方面的研究主要是使 WWO 适应特殊的组合优化问题(COP)。一类 COP 可以表示为整数规划(IP)问题[24-28],算法的另一种变体提出了使用单波而不是波群[29,30]。

最新进展

郑宇军教授于2019年在Applied Soft Computing Journal上发表了论文《Water wave optimization for combinatorial optimization: Design strategies and applications》[31]，该论文提出了一种系统方法，包括一套基本步骤和策略，使水波优化（WWO）适用于不同COP的具体启发式算法，利用通用算法框架，设计人员只要根据给定问题的组合特性，专注于调整prorogation算子和波长计算方法，就能轻松得出有效的问题解决算法。

参考文献

[1] Zheng, Yu-Jun. Water wave optimization: A new nature-inspired metaheuristic[J]. Computers & Operations Research, 2015, 55:1-11.

[2] Zhang B, Zhang M X, Zhang J F, et al. A water wave optimization algorithm with variable population size and comprehensive learning[C]//International Conference on Intelligent Computing. Springer, Cham, 2015: 124-136.

[3] Liang J J, Qu B Y, Suganthan P N, et al. Problem definitions and evaluation criteria for the CEC 2015 competition on learning-based real-parameter single objective optimization[J]. Technical Report201411A, Computational Intelligence Laboratory, Zhengzhou University, Zhengzhou China and Technical Report, Nanyang Technological University, Singapore, 2014.

[4] Wu X, Zhou Y, Lu Y. Elite opposition-based water wave optimization algorithm for global optimization[J]. Mathematical Problems in Engineering, 2017, 2017.

[5] Zhang J, Zhou Y, Luo Q. An improved sine cosine water wave optimization algorithm for global optimization[J]. Journal of Intelligent & Fuzzy Systems, 2018, 34(4): 2129-2141.

[6] Hematabadi A A, Foroud A A. Optimizing the multi-objective bidding strategy using min–max technique and modified water wave optimization method[J]. Neural Computing and Applications, 2018: 1-19.

[7] Rong Z Y, Zhang M X, Du Y C, et al. A Hybrid Evolutionary Algorithm for Combined Road-Rail Emergency Transportation Planning[C]//International Conference on Swarm Intelligence. Springer, Cham, 2018: 465-476.

[8] Zheng Y J, Wang Y, Ling H F, et al. Integrated civilian–military pre-positioning of emergency supplies: A multiobjective optimization approach[J]. Applied Soft Computing, 2017, 58: 732-741.

[9] Lenin K, Ravindhranath Reddy B, Suryakalavathi M. Hybridization of firefly and water wave algorithm for solving reactive power problem[C]//International journal of engineering research in Africa. Trans Tech Publications, 2016, 21: 165-171.

[10] Singh G, Rattan M, Gill S S, et al. Hybridization of water wave optimization and sequential quadratic programming for cognitive radio system[J]. Soft Computing, 2018: 1-21.

[11] Zhang J, Zhou Y, Luo Q. Nature-inspired approach: a wind-driven water wave optimization algorithm[J]. Applied Intelligence, 2019, 49(1): 233-252.

[12] Zhou X H, Xu Z G, Zhang M X, et al. Water wave optimization for artificial neural network parameter and structure optimization[C]//International Conference on Bio-Inspired Computing: Theories and Applications. Springer, Singapore, 2018: 343-354.

[13] Liu A, Li P, Sun W, et al. Prediction of mechanical properties of micro-alloyed steels via neural networks learned by water wave optimization[J]. Neural Computing and Applications, 2019: 1-16.

[14] Kilany M, Hassanien A E, Badr A. Accelerometer-based human activity classification using water wave optimization approach[C]//2015 11th International Computer Engineering Conference (ICENCO). IEEE, 2015: 175-180.

[15] Xu W, Ye Z, Hou Y. A fast image match method based on water wave optimization and gray relational analysis[C]//2017 9th IEEE International Conference on Intelligent Data Acquisition and Advanced Computing Systems: Technology and Applications (IDAACS). IEEE, 2017, 2: 771-776.

[16] Chen H, Hou Y, Luo Q, et al. Text feature selection based on water wave optimization algorithm[C]//2018 Tenth International Conference on Advanced Computational Intelligence (ICACI). IEEE, 2018: 546-551.

[17] Ren Z, Wang C, Fan X, et al. Fuzzy clustering based on water wave optimization[C]//2018 13th International Conference on Computer Science & Education (ICCSE). IEEE, 2018:1-5.

[18] Siva M, Balamurugan R, Lakshminarasimman L. Water wave optimization algorithm for solving economic dispatch problems with generator constraints[J]. International Journal of Intelligent Engineering and Systems, 2016, 9(4): 31-40.

[19] Zhou Y, Zhang J, Yang X, et al. Optimal reactive power dispatch using water wave optimization algorithm[J]. Operational Research, 2018: 1-17.

[20] Zhao S, Li Z, Yun X, et al. IIR filters designing by water wave optimization[C]//2017 13th IEEE International Conference on Control & Automation (ICCA). IEEE, 2017: 347-352.

[21] Fard A M F, Hajaghaei-Keshteli M. A tri-level location-allocation model for forward/reverse supply chain[J]. Applied Soft Computing, 2018, 62: 328-346.

[22] Fard A M F, Hajiaghaei-Keshteli M. A bi-objective partial interdiction problem considering different defensive systems with capacity expansion of facilities under imminent attacks[J]. Applied Soft Computing, 2018, 68: 343-359.

[23] Song Q, Zheng Y J, Huang Y J, et al. Emergency drug procurement planning based on big-data driven morbidity prediction[J]. IEEE Transactions on Industrial Informatics, 2018.

[24] Zheng Y J, Zhang B, Xue J Y. Selection of key software components for formal development using water wave optimization[J]. Journal of Software, 2016, 27(4): 933-942.

[25] Wu X B, Liao J, Wang Z C. Water wave optimization for the traveling salesman problem[C]//International Conference on Intelligent Computing. Springer, Cham, 2015: 137-146.

[26] Yun X, Feng X, Lyu X, et al. A novel water wave optimization based memetic algorithm for flow-shop scheduling[C]//2016 IEEE Congress on Evolutionary Computation (CEC). IEEE, 2016: 1971-1976.

[27] Zhao F, Liu H, Zhang Y, et al. A discrete water wave optimization algorithm for no-wait flow shop scheduling problem[J]. Expert Systems with Applications, 2018, 91: 347-363.

[28] Zhao F, Zhang L, Liu H, et al. An improved water wave optimization algorithm with the single wave mechanism for the no-wait flow-shop scheduling problem[J]. Engineering Optimization, 2018: 1-16.

[29] Shao Z, Pi D, Shao W. A novel discrete water wave optimization algorithm for blocking flow-shop scheduling problem with sequence-dependent setup times[J]. Swarm and Evolutionary Computation, 2018, 40: 53-75.

[30] Shao Z, Pi D, Shao W. A novel multi-objective discrete water wave optimization for solving multi-objective blocking flow-shop scheduling problem[J]. Knowledge-Based Systems, 2019, 165: 110-131.

[31] Zheng Y J, Lu X Q, Du Y C, et al. Water wave optimization for combinatorial optimization: Design strategies and applications[J]. Applied Soft Computing, 2019: 105611.