[發(fā)明專利]基于自適應(yīng)量子蟻群的鐵路交通換乘方案查詢方法及裝置

有效

• 申請?zhí)枺?/td>: 201310242304.4
• 申請日: 2013-06-18
• 公開（公告）號: CN103336799B
• 公開（公告）日: 2017-11-14
• 發(fā)明（設(shè)計）人: 游曉明;劉升
• 申請（專利權(quán)）人: 上海工程技術(shù)大學(xué)
• 主分類號: G06F17/30
• 分類號: G06F17/30;G06N3/00
• 代理公司: 上海科盛知識產(chǎn)權(quán)代理有限公司31225
• 代理人: 趙繼明

1.一種基于自適應(yīng)量子蟻群的鐵路交通換乘方案查詢方法，其特征在于，包括以下步驟：

1)管理控制臺通過管理機對查詢機終端進行權(quán)限設(shè)置和數(shù)據(jù)庫更新設(shè)置；

2)查詢機終端啟動，觸摸屏接收查詢請求，并將查詢請求發(fā)送給中心處理模塊；

3)中心處理模塊根據(jù)查詢請求從站點數(shù)據(jù)庫模塊中獲取與查詢信息相匹配的站點信息，并構(gòu)建多模式最優(yōu)路徑模型；

4)中心處理模塊基于多模式最優(yōu)路徑模型執(zhí)行自適應(yīng)量子蟻群算法，計算獲得不同最優(yōu)目標(biāo)下的最優(yōu)鐵路換乘方案，輸出最優(yōu)路徑，所述的最優(yōu)目標(biāo)包括時間最短、換乘最少和路程最少；

5)對多模式最優(yōu)路徑模型的數(shù)值進行更新，并判斷優(yōu)化是否結(jié)束，若是，則將計算結(jié)果反饋給觸摸屏，執(zhí)行步驟6)，若否，返回步驟4)；

6)觸摸屏顯示計算結(jié)果；

所述的步驟4)中的自適應(yīng)量子蟻群算法具體包括如下步驟：

401)初始化包含m個個體的量子蟻群Q(t)：其中，

qit=qit(1,1)qit(1,2)...qit(1,n)qit(2,1)qit(2,2)...qit(2,n)............qit(n,1)qit(n,2)...qit(n,n)n×n,i=1,2,...,m]]>

qit(j,k)=αit(j,k)βit(j,k),j,k=1,2,...,n]]>

為第t次迭代的第i個個體，且通過量子測量算子使的任意行和列有且僅有一個元素為1，其余為0，n為站點個數(shù)，t為迭代數(shù)，初始迭代數(shù)t＝0；

402)將m個螞蟻隨機地置于n個站點其中一個站點上，每只螞蟻通過重復(fù)地應(yīng)用狀態(tài)轉(zhuǎn)移規(guī)則，建立一個路徑，直至所有螞蟻均完成解路徑的構(gòu)造；

采用3-OPT局部尋優(yōu)算法提升解集的每條路徑，直到無法優(yōu)化為止；

使用量子旋轉(zhuǎn)門Q-gates更新Q(t)：

Q(t+1)=G(θ)Q(t),G(θ)=COS(θ)-SIN(θ)SIN(θ)COS(θ),θ=0.01π;]]>

使用測量算子測量Q(t)；

評估Q(t)；

存儲和記錄當(dāng)代最優(yōu)解；

t＝t+1；

403)判斷是否滿足終止準(zhǔn)則，滿足則算法迭代結(jié)束輸出最優(yōu)解，否則跳轉(zhuǎn)至步驟402)；

通過量子測量算子測量Q(t)，使的任意行和列有且僅有一個元素為1，具體操作如下：

a0)設(shè)種群中的第i個個體的為量子的概率幅表示，j,k＝1,2,...,n，其中

αit(l,h)=1-(βit(l,h))2]]>

El=1nΣj=1nd[l,j]Ll=max{|d[l,j]-El|,j=1,2...n}]]>

其中，d[l,h]為站點(l,h)間距離；

a1)N＝{1,2,...,n}，tabu＝Φ，a取初值為1，tabu＝tabu∪{a}；

a2)對于的a行，隨機生成列b，b＝INT(Rand[0,1]×n)+1，b∈N，

如果并且q∈[0,1]是一個自適應(yīng)值，則

否則，令U為從a點出發(fā)的可行集，τ(a,s)為邊(a,s)上的信息素濃度；η(a,s)＝1/d(a,s)代表邊(a,s)上的自啟發(fā)量，γ代表自啟發(fā)量的權(quán)重；

a3)a＝b，tabu＝tabu∪{b}，重復(fù)步驟a2)、a3)，直到的任意行和列有且僅有一個元素為1；

通過控制量子測量算子中的q值可控制算法的收斂方向，提高算法的全局搜索能力，q的具體設(shè)計如下：

q=BaseNum,t≤CBaseNum*EndStep-tEndStep-C,otherwise]]>

其中EndStep為預(yù)先設(shè)定的量子蟻群最大迭代代數(shù)，t為蟻群演化當(dāng)前代數(shù)，BaseNum∈[0,1]、C均為常數(shù)。