基于改進粒子群的雙層規(guī)劃求解算法研究
發(fā)布時間：2018-09-01 17:10
【摘要】：雙層規(guī)劃是一類具有兩層遞階結構的系統(tǒng)優(yōu)化問題,在數學規(guī)劃領域得到蓬勃發(fā)展,成為運籌學一個分支,目前已成功應用于諸多領域中,如經濟學、管理學、金融學、工程應用等。同時,雙層規(guī)劃模型的求解非常困難,只有在上下層目標函數及約束條件滿足相應的要求時,基于梯度的傳統(tǒng)優(yōu)化方法的求解效率才較高,但對于復雜雙層規(guī)劃(維數高、非線性、目標函數不可微、約束空間非凸等),這類方法往往難以獲得全局最優(yōu)解。近幾年來,進化算法、遺傳算法、粒子群優(yōu)化算法等一些智能優(yōu)化算法,由于其對函數要求較低并且具有較強的全局搜索能力等優(yōu)點,已被廣泛用于求解雙層規(guī)劃問題。 本文在廣泛查閱、吸收借鑒BLPP求解算法文獻的基礎上,提出采用改進的PSO算法求解BLPP問題。論文首先對基本粒子群優(yōu)化算法做了一些改進,然后將改進的算法用于求解雙層規(guī)劃模型,提出基于改進粒子群的雙層迭代算法,并通過實驗進一步驗證算法的有效性。本文所做的主要工作如下： (1)提出了一種帶自適應變異的粒子群優(yōu)化算法,主要做了如下改進：1)自適應的調整慣性權重,使算法在全局搜索能力和局部搜索能力之間達到最佳平衡；2)引入算法局部收斂的判斷機制,有效地判斷算法是否陷入局部收斂；3)全局極值變異操作。若算法陷入局部收斂,通過給全局極值增加隨機擾動,提高其跳出局部最優(yōu)點的能力。該算法能有效地防止算法陷入局部最優(yōu)點的問題,全局收斂速度和收斂精度顯著提升。 (2)提出了基于改進PSO的BLPP求解算法,即把改進的PSO算法應用于BLPP的上下兩層,將求解一般BLPP的問題轉化為通過兩個PSO算法的交互迭代來求解上下兩層規(guī)劃問題。通過與其他算法的實驗結果相對比,本算法對于求解雙層規(guī)劃模型是有效的。 (3)給出了一種用雙層規(guī)劃方法建立了包括三種回收途徑共存的閉環(huán)供應鏈模型。敘述了該模型的背景、現(xiàn)狀和需要解決的問題,建立了上下層的規(guī)劃模型,然后通過實例證明了基于改進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
本文編號：2217838
[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
【參考文獻】
相關期刊論文 前10條
1 李志剛，吳滄浦;兵力部署優(yōu)化問題的兩層規(guī)劃模型[J];北京理工大學學報;1997年03期
2 沈厚才，徐南榮，，仲偉俊;一類含0－1變量的多目標兩層決策方法研究[J];東南大學學報;1995年06期
3 趙志剛;蘇一丹;;帶自變異算子的粒子群優(yōu)化算法[J];計算機工程與應用;2006年13期
4 高岳林;任子暉;;帶有變異算子的自適應粒子群優(yōu)化算法[J];計算機工程與應用;2007年25期
5 常永明;王宇平;;求解一類特殊的雙層規(guī)劃問題的遺傳算法[J];計算機工程與應用;2009年03期
6 毛開富;包廣清;徐馳;;基于非對稱學習因子調節(jié)的粒子群優(yōu)化算法[J];計算機工程;2010年19期
7 劉國山,韓繼業(yè),汪壽陽;雙層優(yōu)化問題的信賴域算法[J];科學通報;1998年04期
8 趙志剛;王偉倩;黃樹運;;基于改進粒子群的雙層規(guī)劃求解算法[J];計算機科學;2013年S2期
9 李響;高常海;劉梁;;求解二層規(guī)劃問題的改進粒子群算法[J];徐州工程學院學報(自然科學版);2009年02期
10 刁東宇;趙英凱;;帶雙重變異算子的自適應粒子群優(yōu)化算法[J];計算機工程與設計;2009年05期
本文編號：2217838
本文鏈接：http://www.wukwdryxk.cn/guanlilunwen/gongyinglianguanli/2217838.html
