基于改进粒子群的双层规划求解算法研究

发布时间：2018-09-01 17:10

【摘要】：双层规划是一类具有两层递阶结构的系统优化问题,在数学规划领域得到蓬勃发展,成为运筹学一个分支,目前已成功应用于诸多领域中,如经济学、管理学、金融学、工程应用等。同时,双层规划模型的求解非常困难,只有在上下层目标函数及约束条件满足相应的要求时,基于梯度的传统优化方法的求解效率才较高,但对于复杂双层规划(维数高、非线性、目标函数不可微、约束空间非凸等),这类方法往往难以获得全局最优解。近几年来,进化算法、遗传算法、粒子群优化算法等一些智能优化算法,由于其对函数要求较低并且具有较强的全局搜索能力等优点,已被广泛用于求解双层规划问题。本文在广泛查阅、吸收借鉴BLPP求解算法文献的基础上,提出采用改进的PSO算法求解BLPP问题。论文首先对基本粒子群优化算法做了一些改进,然后将改进的算法用于求解双层规划模型,提出基于改进粒子群的双层迭代算法,并通过实验进一步验证算法的有效性。本文所做的主要工作如下： (1)提出了一种带自适应变异的粒子群优化算法,主要做了如下改进：1)自适应的调整惯性权重,使算法在全局搜索能力和局部搜索能力之间达到最佳平衡；2)引入算法局部收敛的判断机制,有效地判断算法是否陷入局部收敛；3)全局极值变异操作。若算法陷入局部收敛,通过给全局极值增加随机扰动,提高其跳出局部最优点的能力。该算法能有效地防止算法陷入局部最优点的问题,全局收敛速度和收敛精度显著提升。 (2)提出了基于改进PSO的BLPP求解算法,即把改进的PSO算法应用于BLPP的上下两层,将求解一般BLPP的问题转化为通过两个PSO算法的交互迭代来求解上下两层规划问题。通过与其他算法的实验结果相对比,本算法对于求解双层规划模型是有效的。 (3)给出了一种用双层规划方法建立了包括三种回收途径共存的闭环供应链模型。叙述了该模型的背景、现状和需要解决的问题,建立了上下层的规划模型,然后通过实例证明了基于改进PSO的BLPP求解算法是有效的,也是可行的。最后,总结本文所做的主要工作,并提出了进一步的研究方向。
[Abstract]:Bilevel programming is a kind of system optimization problem with two-level hierarchical structure. It has developed vigorously in the field of mathematical programming and become a branch of operational research. It has been successfully applied in many fields, such as economics, management, finance, etc. Engineering applications, etc. At the same time, it is very difficult to solve the bilevel programming model. Only when the upper and lower level objective function and constraint conditions meet the corresponding requirements, the traditional optimization method based on gradient is more efficient, but for complex bilevel programming (dimension is high), Nonlinear, objective function is not differentiable, constrained space is not convex, etc., this kind of method is difficult to obtain the global optimal solution. In recent years, some intelligent optimization algorithms, such as evolutionary algorithm, genetic algorithm, particle swarm optimization algorithm and so on, have been widely used in solving bilevel programming problems due to their low requirement for function and strong global searching ability. On the basis of consulting widely and drawing lessons from the literature of BLPP algorithm, this paper proposes an improved PSO algorithm to solve BLPP problem. In this paper, we first improve the basic particle swarm optimization algorithm, then apply the improved algorithm to solve the bilevel programming model, propose a two-level iterative algorithm based on the improved particle swarm optimization algorithm, and further verify the effectiveness of the algorithm through experiments. The main work of this paper is as follows: (1) A particle swarm optimization algorithm with adaptive mutation is proposed. The optimal balance between the global search ability and the local search ability is achieved. 2) the judgment mechanism of local convergence is introduced to determine effectively whether the algorithm is trapped in local convergence and whether the algorithm falls into local convergence or not) the global extremum mutation operation. If the algorithm is trapped in local convergence, its ability to jump out of the local optimum can be improved by adding random disturbance to the global extremum. The algorithm can effectively prevent the algorithm from falling into the problem of local optimum, and the global convergence speed and convergence accuracy are improved significantly. (2) an improved BLPP algorithm based on PSO is proposed, that is, the improved PSO algorithm is applied to the upper and lower layers of BLPP. The problem of solving general BLPP is transformed into the problem of upper and lower two-level programming through the interactive iteration of two PSO algorithms. Compared with the experimental results of other algorithms, this algorithm is effective for solving the bilevel programming model. (3) A closed-loop supply chain model with three recovery paths is established by using the bilevel programming method. The background, current situation and problems to be solved of the model are described. The upper and lower level programming model is established, and the BLPP algorithm based on improved PSO is proved to be effective and feasible. Finally, the main work done in this paper is summarized, and the further research direction is put forward.
【学位授予单位】：广西大学
【学位级别】：硕士
【学位授予年份】：2014
【分类号】：TP18

【参考文献】