【作者】 刘瑞林；

【导师】 张涛；

【作者基本信息】 长江大学 ， 应用数学， 2022， 硕士

【摘要】 同时优化多个目标函数的问题称为多目标规划问题。多目标规划问题的求解算法主要有以下三类:将多目标规划问题转换为一组单目标规划问题的求解算法、基于运筹学与优化理论的求解算法以及基于非支配排序的进化算法。多目标规划问题的解往往是一个解集,转换为单目标规划问题的方法,在一次求解中一般只能得到一个解,如果需要得到整个解集,需要改变算法参数反复运行。基于运筹学与优化理论的方法又受到很多条件限制,算法的适应性不足。目前,基于非支配排序的进化算法是求解多目标规划问题的不二法门。多目标进化算法具有很强的适应性和优异的性能,但是为了得到较好的解集,往往需要长时间运行。主要是因为两方面因素:非支配排序的高时间复杂度和种群数量与算法搜索效率的制约关系。目前,多目标进化算法已经发展成熟,深度学习正在逐步进入这一研究领域。但是深度学习在多目标规划问题的算法设计中,往往承担代理模型的角色,并没有采用深度学习方法来构造求解算法的核心部分。另一个方向上,基于强化学习的多目标规划算法,研究工作由来已久,深度学习引入后也逐渐出现了基于深度强化学习的多目标规划算法,并且有些学者已经开展了一些应用研究。但是一方面,尚未及时将各种新发展的深度强化学习方法引入到各种数值优化问题中,另一方面对于传统的进化算法的经验利用不足。本研究课题开展多目标规划问题的深度学习算法研究,主要探索深度学习方法在多目标规划问题算法构造中的应用,提出了两类五种基于深度学习的多目标规划问题求解算法。将多目标规划问题的求解转换为数字图像处理问题,利用参数化测试问题制作数据集,构建了监督学习的端到端深度卷积神经网络模型,训练完成后在测试问题中进行了测试,测试结果较好。但是该方法在泛化能力上仍然存在缺陷。受这一方法启发,针对非支配排序过程,本研究课题根据非支配关系在数字图像中的特征,提出了一种卷积核,利用该卷积核实现了一种用于非支配排序的前馈深度卷积神经网络。借助于深度卷积神经网络在GPU上的高效并行化实现,该算法极大地提高了非支配排序的效率。并且本研究证明了该算法的正确性。基于深度强化学习的方法,将多目标规划问题的求解过程转换为马尔可夫决策过程,提出了另外一类三种算法。其中MOP-DQN算法基于深度Q学习算法、而MOP-AC和MOP-AC-sample算法是基于Actor-Critic算法提出的。我们在SCH问题上测试了这三种算法的求解能力,实验表明,基于Actor-Critic的算法比基于Q学习的算法具有更强的求解能力。MOP-AC算法的求解能力更强,而MOP-AC-sample算法具有更强的探索性。然而,这些算法也存在一些缺陷。对于求解多目标规划问题的深度强化学习算法,我们难以找到一个通用的、高效的奖赏函数,在求解过程中普遍存在奖赏稀疏性问题。对于算法中的深度神经网络,也没有明确的构造方法,是否与问题关联还没有得到全面的印证。因此,算法的普适性受到了限制。更多还原

【Abstract】 Optimizing multiple objective functions simultaneously is termed multi-objective programming problem.There are three kinds of algorithms for solving multi-objective programming problems,transforming multi-objective problems into a set of single-objective programming problems,methods based on theories of operational research and optimization,and evolutionary algo-rithms based on non-dominated sorting.The solution of a multi-objective programming problem is usually a set,and the method of converting to a single-objective programming problem can merely obtain one solution per step.If the whole solution set is needed,the algorithm parameters need to be varied and solved repeatedly.The method based on the theories of op-erational research and optimization is limited by many conditions,and the adaptability of the algorithm is insufficient.At present,evolutionary algo-rithm based on non-dominated sorting is the main approach to solve multi-objective programming problems.The multi-objective evolutionary algo-rithm has strong adaptability and excellent performance,but in order to obtain a better solution set,it often needs a large iterations,mainly because of two factors,the high time complexity of non-dominant sorting and the trade off between the population size and algorithm search efficiency.Recently,multi-objective evolutionary algorithms have been difficult to put forward effective new algorithms,and deep learning has gradually entered this research field.However,at present,deep learning often acts as a proxy model in the algorithm design of multi-objective programming problems,and the core solution part of the algorithm is not constructed by deep learning method.In another aspect,based on the study of reinforce-ment learning has a long history.Deep reinforcement learning also gradually appeared,and some scholars have carried out some applied research,but on the one hand,various novel developed deep reinforcement learning methods have not been introduced into various numerical optimization problems.On the other hand,the experience of traditional evolutionary algorithms has not been exploited sufficiently.This research is aimed at proposing deep learning algorithm for multi-objective programming problems,mainly explores the application of deep learning method in constructing algorithms for multi-objective programming problems,and proposes two types of five algorithms based on deep learning.The solving procedure of multi-objective programming problem was trans-formed into digital image processing problem,the parameterized test problem was used to generate data set,and the end-to-end deep convolutional neural network model of supervised learning was constructed.After the training was completed,testing was carried out by the testing problem,and the test result was acceptable.However,this method still has some defects in generalization ability.Inspired by this method and aiming at the process of non-dominated sorting,this research project proposes a convolution kernel according to the characteristics of non-dominated relations in digital images,and takes advan-tage of this convolution kernel to implement a feedforward deep convolution neural network for non-dominated sorting.With the efficient parallelization of deep convolutional neural network on GPU,the algorithm greatly im-proves the efficiency of non-dominated sorting,and the correctness of the algorithm is proved in this research.Based on the deep reinforcement learn-ing method,the solving process of multi-objective programming problem is transformed into markov decision process,and another three algorithms of another class are proposed in this study.Among them,MOP-DQN algorithm is based on deep Q learning algorithm,while MOP-AC and MOP-AC-sample algorithm are proposed based on Actor-Critic algorithm.We tested the ability of these three algorithms on the SCH problem,and the experiments showed that the algorithm based on Actor-Critic has stronger solving ability than the algorithm based on Q learning.The MOP-AC algorithm has stronger solving ability,while the MOP-AC-sample algorithm is more exploratory.更多还原