[發(fā)明專利]基于復(fù)雜網(wǎng)絡(luò)的粒子群優(yōu)化方法

有效

• 申請?zhí)枺?/td>: 201410185023.4
• 申請日: 2014-05-05
• 公開（公告）號: CN103971160B
• 公開（公告）日: 2017-02-15
• 發(fā)明（設(shè)計）人: 杜文博;蔡開泉;劉琛;高陽
• 申請（專利權(quán)）人: 北京航空航天大學(xué)
• 主分類號: G06N3/00
• 分類號: G06N3/00
• 代理公司: 北京永創(chuàng)新實專利事務(wù)所11121
• 代理人: 祗志潔

技術(shù)領(lǐng)域

本發(fā)明涉及計算機技術(shù)領(lǐng)域，具體涉及一種基于復(fù)雜網(wǎng)絡(luò)的粒子群優(yōu)化方法，用于解決現(xiàn)實世界的多目標優(yōu)化問題，例如用于空管領(lǐng)域，解決航班起降排序問題。

背景技術(shù)

現(xiàn)實世界的很多優(yōu)化問題屬于多目標優(yōu)化問題，多個相互競爭目標的優(yōu)化結(jié)果是得到一組可行解。例如資產(chǎn)投資的多目標優(yōu)化，物資調(diào)用車輛路徑的優(yōu)選，新產(chǎn)品的優(yōu)化設(shè)計，產(chǎn)品生產(chǎn)調(diào)度等等方面。例如，對于航班起降排序問題，問題的求解空間由所有可能的航班起降的時間序列組成，空間的每一點為一個時間序列(也即一種航班起降排序方法)，每一點在每一維度上的坐標為一架飛機的起飛或降落的時間。根據(jù)不同的目的，建立不同的目標函數(shù)，例如：極小化總空中延誤，極小化總起飛/降落時間等等，種群粒子在求解空間中尋找優(yōu)解。

智能優(yōu)化算法(Intelligent Optimization Algorithm)，又稱智能計算(Intelligent Computation)，是通過模擬或揭示某些自然現(xiàn)象或過程發(fā)展而來的優(yōu)化算法，其思想和內(nèi)容涉及數(shù)學(xué)、物理學(xué)、生物學(xué)和計算機科學(xué)等學(xué)科，它不依賴梯度信息，具有全局、并行、高效的優(yōu)化性能，魯棒性和通用性強，為解決大規(guī)模非線性問題提供了新的思路和手段?，F(xiàn)實世界的優(yōu)化問題常常為大規(guī)模非線性問題，目前可采用智能優(yōu)化算法來解決。

粒子群算法是由Kennedy和Eberhart于1995年開發(fā)的一種模仿鳥類群體行為的智能優(yōu)化算法，基本思想是通過群體中個體之間的協(xié)作和信息共享來尋找最優(yōu)解。PSO的優(yōu)勢在于簡單容易實現(xiàn)并且沒有許多參數(shù)的調(diào)節(jié)，但是也存在容易陷入局部最優(yōu)、早熟收斂或停滯等問題。

眾所周知，系統(tǒng)的結(jié)構(gòu)決定系統(tǒng)的功能，更合理、更有效的系統(tǒng)結(jié)構(gòu)可以使得系統(tǒng)以更低的成本代價獲得更好的系統(tǒng)功能。復(fù)雜網(wǎng)絡(luò)作為一門研究復(fù)雜系統(tǒng)的新興學(xué)科，可以將任何的復(fù)雜系統(tǒng)抽象成為由互相作用的個體組成的網(wǎng)絡(luò)。復(fù)雜網(wǎng)絡(luò)是指具有自組織、自相似、吸引子、小世界、無標度中部分或全部性質(zhì)的網(wǎng)絡(luò)。對于粒子群算法，每一個粒子可以看成網(wǎng)絡(luò)中的一個點，每一對可以傳遞信息的粒子間視為有邊相連，這些點和連邊構(gòu)成了種群的網(wǎng)絡(luò)拓撲?，F(xiàn)有種群的網(wǎng)絡(luò)結(jié)構(gòu)通常為全連通網(wǎng)絡(luò)或規(guī)則網(wǎng)絡(luò)，典型代表為環(huán)形網(wǎng)絡(luò)。全連通網(wǎng)絡(luò)中任意粒子與其余粒子都有連邊，具有最快的收斂速度，可是也因此具有一定的“盲目性”，容易陷入局部最優(yōu)。環(huán)形網(wǎng)絡(luò)中每個粒子只與其相鄰的兩個粒子有連邊，種群的信息傳遞速度較慢，可以有效地避免全連通網(wǎng)絡(luò)的“盲目”收斂，對復(fù)雜問題可以取得較好的優(yōu)化效果，但是其收斂速度也因此受到很大的影響。

目前將PSO用于解決多目標優(yōu)化問題屬于一個研究熱點，例如航班起降排序問題，將粒子的坐標代入目標函數(shù)，以適應(yīng)值評判解的好壞，根據(jù)種群的拓撲結(jié)構(gòu)和PSO的更新規(guī)則不斷進化，直到取得滿意解或達到最大優(yōu)化代數(shù)。但是，由于目前PSO應(yīng)用中，種群的網(wǎng)絡(luò)結(jié)構(gòu)的限制，使得獲取結(jié)果的收斂速度降低或者容易陷入局部最優(yōu)。

發(fā)明內(nèi)容

本發(fā)明針對目前采用PSO進行多目標優(yōu)化時，由于種群網(wǎng)絡(luò)結(jié)構(gòu)使得收斂速度過快或者容易陷入局部最優(yōu)的問題，提供了一種新型的基于復(fù)雜網(wǎng)絡(luò)的粒子群優(yōu)化方法。本發(fā)明的粒子群優(yōu)化方法中采用了一種新型的種群網(wǎng)絡(luò)拓撲——無標度網(wǎng)絡(luò)，來平衡進行多目標優(yōu)化時種群的收斂速度和優(yōu)化效果。

本發(fā)明的基于復(fù)雜網(wǎng)絡(luò)的粒子群優(yōu)化方法，包括以下步驟：

第一步，確定尋優(yōu)空間，設(shè)置種群規(guī)模，隨機設(shè)置各粒子的位置和速度。

第二步，根據(jù)無標度網(wǎng)絡(luò)的產(chǎn)生機制建立種群網(wǎng)絡(luò)拓撲，具體建立方法是：設(shè)當前存在的連通網(wǎng)絡(luò)中有m₀個粒子，對于新加入的粒子，將該粒子與已存在的網(wǎng)絡(luò)中的m個節(jié)點連接，m小于m₀，新加入粒子與網(wǎng)絡(luò)中已存在的節(jié)點i相連接的概率P_i為：

Pi=Ki/Σj=1m0Kj]]>