In recent years, neural heuristics leveraging deep reinforcement learning have exhibited considerable promise in addressing multi-objective combinatorial optimization problems (MOCOPs). Nonetheless, challenges persist in attaining both high learning efficiency and optimal solution quality. To address this issue, we propose a novel multi-objective optimization algorithm grounded in information geometry and machine learning principles, which integrates adaptive gradient descent with meta-reinforcement learning techniques to effectively tackle MOCOPs. In this paper, we present a meta-learning framework aimed at enhancing model performance in multi-objective combinatorial optimization through tensor remodeling, preconditioned gradient descent, and entropy regularization strategies. Experimental results demonstrate that the proposed method yields significant performance improvements across several classic multi-objective combinatorial optimization challenges, including the Multi-objective Traveling Salesman Problem (MOTSP), Multi-objective Vehicle Routing Problem (MOCVRP), and Multi-objective Knapsack Problem (MOKP).
DebK.PratapA.AgarwalS.MeyarivanT. (2002). A Fast and Elitist Multiobjective Genetic Algorithm: NSGA-II, Volume 6. New York, NY: IEEE. https://doi.org/10.1109/4235.996017.
8.
GendreauM.PotvinJ. Y. (2005). Tabu search. In E. K. Burke & G. Kendall (Eds.), Search Methodologies: Introductory tutorials in optimization and decision support techniques (pp. 165–186). Boston, MA: Springer US. ISBN 978-0-387-28356-2. https://doi.org/10.1007/0-387-28356-0_6
9.
IbarzB.KurinV.PapamakariosG.NikiforouK.BennaniM.CsordásR.DudzikA. J.BošnjakM.VitvitskyiA.RubanovaY.DeacA.BevilacquaB.GaninY.BlundellC.VeličkovićP. (2022). A generalist neural algorithmic learner. In B. Rieck & R. Pascanu (Eds.), Proceedings of the first learning on graphs conference, Proceedings of Machine Learning Research (Vol. 198, pp. 2:1–2:23). https://proceedings.mlr.press/v198/ibarz22a.html.
10.
KangS.HwangD.EoM.KimT.RheeW. (2023). Meta-learning with a geometry-adaptive preconditioner. In Proceedings of the IEEE/CVF conference on computer vision and pattern recognition (CVPR) (pp. 16080–16090). https://arxiv.org/abs/2304.01552.
LeeY.ChoiS. (2018). Gradient-based meta-learning with learned layerwise metric and subspace. In J. Dy & A. Krause (Eds.), Proceedings of the 35th international conference on machine learning, Proceedings of Machine Learning Research (Vol. 80, pp. 2927–2936). https://proceedings.mlr.press/v80/lee18a.html.
17.
LiZ.ZhouF.ChenF.LiH. (2017). Meta-sgd: Learning to learn quickly for few-shot learning. arXiv preprint arXiv:1707.09835https://arxiv.org/abs/1707.09835.
18.
LinX.YangZ.ZhangQ. (2022). Pareto set learning for neural multi-objective combinatorial optimization. arXiv preprint arXiv:2203.15386https://doi.org/10.48550/arXiv.2203.15386.
19.
LiuF.LinX.WangZ.ZhangQ.XialiangT.YuanM. (2024a). Multi-task learning for routing problem with cross-problem zero-shot generalization. In Proceedings of the 30th ACM SIGKDD conference on knowledge discovery and data mining KDD ’24 (p. 1898–1908). New York, NY, USA: Association for Computing Machinery. ISBN 9798400704901. https://doi.org/10.1145/3637528.3672040
20.
LiuF.XialiangT.YuanM.LinX.LuoF.WangZ.LuZ.ZhangQ. (2024b). Evolution of heuristics: Towards efficient automatic algorithm design using large language model. In Forty-first international conference on machine learning. https://openreview.net/forum?id=BwAkaxqiLB.
21.
LourençoH. R.MartinO. C.StützleT. (2003). Iterated local search. In F. Glover & G. A. Kochenberger (Eds.), Handbook of metaheuristics (pp. 320–353). Boston, MA: Springer US. ISBN 978-0-306-48056-0. https://doi.org/10.1007/0-306-48056-5_11
22.
LustT.TeghemJ. (2010a). The multiobjective traveling salesman problem: A survey and a new approach. Berlin, Heidelberg: Springer Berlin Heidelberg. ISBN 978-3-642-11218-8, pp. 119–141. https://doi.org/10.1007/978-3-642-11218-8_6
23.
LustT.TeghemJ. (2010b). Two-phase pareto local search for the biobjective traveling salesman problem. Journal of Heuristics, 16(3), 475–510. https://doi.org/10.1007/s10732-009-9103-9
24.
MeyersonE.NelsonM. J.BradleyH.GaierA.MoradiA.HooverA. K.LehmanJ. (2023). Language model crossover: Variation through few-shot prompting. arXiv preprint arXiv:2302.12170https://arxiv.org/abs/2302.12170.
25.
NicholA.AchiamJ.SchulmanJ. (2018). On first-order meta-learning algorithms. arXiv preprint arXiv:1803.02999https://arxiv.org/abs/1803.02999.
26.
RajasegaranJ.KhanS.HayatM.KhanF. S.ShahM. (2020). Meta-learning the learning trends shared across tasks. arXiv preprint arXiv:2010.09291https://arxiv.org/abs/2010.09291.
Romera-ParedesB.BarekatainM.NovikovA.BalogM.KumarM. P.DupontE.RuizF. J. R.EllenbergJ. S.WangP.FawziO.KohliP.FawziA. (2024). Mathematical discoveries from program search with large language models. Nature, 625(7995), 468–475. https://doi.org/10.1038/s41586-023-06924-6
29.
SimonC.KoniuszP.NockR.HarandiM. (2020). On modulating the gradient for meta-learning. In A. Vedaldi, H. Bischof, T. Brox & J. M. Frahm (Eds.), Computer Vision – ECCV 2020 (pp. 556–572). Cham: Springer International Publishing. ISBN 978-3-030-58598-3.
WangC.YuT. (2023). Efficient training of multi-task combinatorial neural solver with multi-armed bandits. arXiv preprint arXiv:2305.06361https://arxiv.org/abs/2305.06361.
32.
WangQ.SuF.DaiS.LuX.LiuY. (2024). Adagc: A novel adaptive optimization algorithm with gradient bias correction. Expert Systems with Applications, 256, 124956. https://doi.org/10.1016/j.eswa.2024.124956
33.
YangS.ZhaoH.ZhuS.ZhouG.XuH.JiaY.ZanH. (2024). Zhongjing: Enhancing the chinese medical capabilities of large language model through expert feedback and real-world multi-turn dialogue. Proceedings of the AAAI Conference on Artificial Intelligence, 38(17), 19368–19376. https://doi.org/10.1609/aaai.v38i17.29907
34.
ZhangQ.LiH. (2007). Moea/d: A multiobjective evolutionary algorithm based on decomposition. IEEE Transactions on Evolutionary Computation, 11(6), 712–731. https://doi.org/10.1109/TEVC.2007.892759
35.
ZhangY.WangJ.ZhangZ.ZhouY. (2021). Modrl/d-el: Multiobjective deep reinforcement learning with evolutionary learning for multiobjective optimization. In 2021 International joint conference on neural networks (IJCNN) (pp. 1–8). https://doi.org/10.1109/IJCNN52387.2021.9534083
36.
ZhangZ.WuZ.ZhangH.WangJ. (2023). Meta-learning-based deep reinforcement learning for multiobjective optimization problems. IEEE Transactions on Neural Networks and Learning Systems, 34(10), 7978–7991. https://doi.org/10.1109/TNNLS.2022.3148435
37.
ZhaoD.KobayashiS.SacramentoJ.von OswaldJ. (2020). Meta-learning via hypernetworks. In Proceedings of the 4th workshop on meta-learning at NeurIPS 2020 (MetaLearn 2020). s.l.: NeurIPS. https://doi.org/10.3929/ethz-b-000465883
