Improved dynamic programming method for solving multi-objective and multi-stage decision-making problems
Abstract Multi-objective and multi-stage decision-making problems require balancing multiple objectives at each stage and making optimal decision in multi-dimensional control variables, where the commonly used intelligent optimization algorithms suffer from low solving efficiency. To this end, this...
Saved in:
| Main Authors: | , , , |
|---|---|
| Format: | Article |
| Language: | English |
| Published: |
Nature Portfolio
2025-01-01
|
| Series: | Scientific Reports |
| Subjects: | |
| Online Access: | https://doi.org/10.1038/s41598-024-83037-8 |
| Tags: |
Add Tag
No Tags, Be the first to tag this record!
|
| _version_ | 1841544760602394624 |
|---|---|
| author | Zhihao Liang Kegang Zhao Kunyang He Yanwei Liu |
| author_facet | Zhihao Liang Kegang Zhao Kunyang He Yanwei Liu |
| author_sort | Zhihao Liang |
| collection | DOAJ |
| description | Abstract Multi-objective and multi-stage decision-making problems require balancing multiple objectives at each stage and making optimal decision in multi-dimensional control variables, where the commonly used intelligent optimization algorithms suffer from low solving efficiency. To this end, this paper proposes an efficient algorithm named non-dominated sorting dynamic programming (NSDP), which incorporates non-dominated sorting into the traditional dynamic programming method. To improve the solving efficiency and solution diversity, two fast non-dominated sorting methods and a dynamic-crowding-distance based elitism strategy are integrated into the NSDP algorithm. The proposed algorithm has been verified on 12 benchmark test functions and a multi-objective travelling salesman problem. The results demonstrate that the NSDP algorithm achieves better outcome in multiple performance metrics and higher solving efficiency, compared with non-dominated sorting genetic algorithm II and multi-objective particle swarm optimization. |
| format | Article |
| id | doaj-art-8466e237479349e7bd326e85f7f6f21c |
| institution | Kabale University |
| issn | 2045-2322 |
| language | English |
| publishDate | 2025-01-01 |
| publisher | Nature Portfolio |
| record_format | Article |
| series | Scientific Reports |
| spelling | doaj-art-8466e237479349e7bd326e85f7f6f21c2025-01-12T12:19:38ZengNature PortfolioScientific Reports2045-23222025-01-0115111410.1038/s41598-024-83037-8Improved dynamic programming method for solving multi-objective and multi-stage decision-making problemsZhihao Liang0Kegang Zhao1Kunyang He2Yanwei Liu3School of Electromechanical Engineering, Guangdong University of TechnologySchool of Mechanical and Automotive Engineering, South China University of TechnologySchool of Mechanical and Automotive Engineering, South China University of TechnologySchool of Electromechanical Engineering, Guangdong University of TechnologyAbstract Multi-objective and multi-stage decision-making problems require balancing multiple objectives at each stage and making optimal decision in multi-dimensional control variables, where the commonly used intelligent optimization algorithms suffer from low solving efficiency. To this end, this paper proposes an efficient algorithm named non-dominated sorting dynamic programming (NSDP), which incorporates non-dominated sorting into the traditional dynamic programming method. To improve the solving efficiency and solution diversity, two fast non-dominated sorting methods and a dynamic-crowding-distance based elitism strategy are integrated into the NSDP algorithm. The proposed algorithm has been verified on 12 benchmark test functions and a multi-objective travelling salesman problem. The results demonstrate that the NSDP algorithm achieves better outcome in multiple performance metrics and higher solving efficiency, compared with non-dominated sorting genetic algorithm II and multi-objective particle swarm optimization.https://doi.org/10.1038/s41598-024-83037-8Multi-objective and multi-stage decision-making problemsImproved dynamic programming methodNon-dominated sortingSolving efficiency |
| spellingShingle | Zhihao Liang Kegang Zhao Kunyang He Yanwei Liu Improved dynamic programming method for solving multi-objective and multi-stage decision-making problems Scientific Reports Multi-objective and multi-stage decision-making problems Improved dynamic programming method Non-dominated sorting Solving efficiency |
| title | Improved dynamic programming method for solving multi-objective and multi-stage decision-making problems |
| title_full | Improved dynamic programming method for solving multi-objective and multi-stage decision-making problems |
| title_fullStr | Improved dynamic programming method for solving multi-objective and multi-stage decision-making problems |
| title_full_unstemmed | Improved dynamic programming method for solving multi-objective and multi-stage decision-making problems |
| title_short | Improved dynamic programming method for solving multi-objective and multi-stage decision-making problems |
| title_sort | improved dynamic programming method for solving multi objective and multi stage decision making problems |
| topic | Multi-objective and multi-stage decision-making problems Improved dynamic programming method Non-dominated sorting Solving efficiency |
| url | https://doi.org/10.1038/s41598-024-83037-8 |
| work_keys_str_mv | AT zhihaoliang improveddynamicprogrammingmethodforsolvingmultiobjectiveandmultistagedecisionmakingproblems AT kegangzhao improveddynamicprogrammingmethodforsolvingmultiobjectiveandmultistagedecisionmakingproblems AT kunyanghe improveddynamicprogrammingmethodforsolvingmultiobjectiveandmultistagedecisionmakingproblems AT yanweiliu improveddynamicprogrammingmethodforsolvingmultiobjectiveandmultistagedecisionmakingproblems |