Jia Ya-Hui, Mei Yi, Zhang Mengjie
IEEE Trans Cybern. 2023 May;53(5):3205-3219. doi: 10.1109/TCYB.2022.3169210. Epub 2023 Apr 21.
Uncertainty is ubiquitous in real-world routing applications. The automated design of the routing policy by hyperheuristic methods is an effective technique to handle the uncertainty and to achieve online routing for dynamic or stochastic routing problems. Currently, the tree representation routing policy evolved by genetic programming is commonly adopted because of the remarkable flexibility. However, numeric representations have never been used. Considering the practicability of the numeric representations and the capability of the numeric optimization methods, in this article, we investigate two numeric representations on a representative stochastic routing problem and uncertain capacitated arc routing problem. Specifically, a linear representation and an artificial neural-network (ANN) representation are implemented and compared with the tree representation to reveal the potential of the numeric representations and the characteristics of their optimization. Experimental results show that the tree representation is the best choice, but on a majority of the test instances, the numeric representations, especially the ANN representation, can provide competitive performance. Further analyses also show that training a good ANN representation policy requires more training data than the tree representation. Finally, a guideline of representation selection is given.
不确定性在现实世界的路由应用中无处不在。通过超启发式方法自动设计路由策略是处理不确定性以及实现动态或随机路由问题在线路由的有效技术。目前，由于具有显著的灵活性，遗传编程演化出的树形表示路由策略被广泛采用。然而，数值表示从未被使用过。考虑到数值表示的实用性和数值优化方法的能力，在本文中，我们针对一个具有代表性的随机路由问题和不确定容量弧路由问题研究了两种数值表示。具体而言，实现了线性表示和人工神经网络（ANN）表示，并将其与树形表示进行比较，以揭示数值表示的潜力及其优化特性。实验结果表明，树形表示是最佳选择，但在大多数测试实例上，数值表示，尤其是ANN表示，可以提供具有竞争力的性能。进一步分析还表明，训练一个良好的ANN表示策略比树形表示需要更多的训练数据。最后，给出了表示选择的指导原则。
