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