[發(fā)明專利]基于蟻群算法的地理信息多目標(biāo)帕累托解的可視化方法

在審

• 申請(qǐng)?zhí)枺?/td>: 201410425441.6
• 申請(qǐng)日: 2014-08-26
• 公開（公告）號(hào): CN104156483A
• 公開（公告）日: 2014-11-19
• 發(fā)明（設(shè)計(jì)）人: 張加萬(wàn);陳輝;蔣心怡;康凱
• 申請(qǐng)（專利權(quán)）人: 天津大學(xué)
• 主分類號(hào): G06F17/30
• 分類號(hào): G06F17/30
• 代理公司: 天津市北洋有限責(zé)任專利代理事務(wù)所 12201
• 代理人: 李素蘭

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

本發(fā)明涉及地理信息(GIS)領(lǐng)域和可視化領(lǐng)域的結(jié)合，特別是涉及一種地理信息多目標(biāo)帕累托解的可視化方法。

背景技術(shù)

基于地理信息上的多目標(biāo)探索決策是一個(gè)非常復(fù)雜的問(wèn)題。如果將傳統(tǒng)方法結(jié)合一個(gè)可視化的分析框架就可解決這類問(wèn)題，這其中包含了多目標(biāo)優(yōu)化算法、可視分析和交互技術(shù)。

多目標(biāo)優(yōu)化算法與數(shù)學(xué)優(yōu)化難題中的多目標(biāo)函數(shù)優(yōu)化算法相關(guān)聯(lián)而且是相似的。目標(biāo)優(yōu)化決策需要在兩個(gè)或者多個(gè)相互沖突的目標(biāo)中進(jìn)行妥協(xié)。然而，這些問(wèn)題是非常難解決的。其原因是：首先，如果用戶有多個(gè)不同的目標(biāo)，且這些目標(biāo)都是非常絕對(duì)的、很難量化和需要實(shí)時(shí)調(diào)整的；那么，難點(diǎn)包含多目標(biāo)和多約束都需要被非常合適的規(guī)定，優(yōu)化其中的任何一個(gè)都可能是一個(gè)NP難度問(wèn)題；相關(guān)的技術(shù)挑戰(zhàn)是如何同時(shí)考慮到所有的目標(biāo)和約束并且在沖突的情形下發(fā)現(xiàn)妥協(xié)的方法。其次，盡管當(dāng)前的分析方法能夠減少算法的復(fù)雜度，但是仍然存在許多的問(wèn)題，即優(yōu)化的結(jié)果可能只是局部最優(yōu)的結(jié)果，另一種情形就是優(yōu)化的算法在利用地理信息的數(shù)據(jù)計(jì)算的時(shí)候可能是不收斂的。再次，本領(lǐng)域需要一個(gè)更加方便和可以交互的系統(tǒng)。用戶需要可信任算法。

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

為了克服上述現(xiàn)有技術(shù)存在的問(wèn)題，本發(fā)明提出了一種基于蟻群算法的地理信息多目標(biāo)帕累托解的可視方法，通過(guò)改進(jìn)的蟻群算法對(duì)地理信息處理后得出來(lái)的帕累托解的可視化表示，幫助用戶進(jìn)行基于地理信息方面的決策，提供給用戶一種可以反饋和交互的優(yōu)化算法方法，并且設(shè)計(jì)出一個(gè)可視分析的框架來(lái)動(dòng)態(tài)的調(diào)整算法的解來(lái)影響最后的結(jié)果，用戶可以通過(guò)可視化的表示來(lái)查看結(jié)果，同時(shí)通過(guò)交互來(lái)影響最后算法的結(jié)果。

本發(fā)明提出一種基于蟻群算法的地理信息多目標(biāo)帕累托解的可視方法，利用地理信息數(shù)據(jù)和與目標(biāo)優(yōu)化相關(guān)的統(tǒng)計(jì)數(shù)據(jù)，用可視分析技術(shù)展示多目標(biāo)優(yōu)化結(jié)果，其特征在于，該方法包括以下步驟：

步驟一、設(shè)定蟻群算法初始時(shí)刻的位置，該位置即用戶在想要探索的區(qū)域通過(guò)點(diǎn)擊選擇的地點(diǎn)；

步驟二、設(shè)定目標(biāo)條件和約束條件；

步驟三、設(shè)定單一目標(biāo)和相應(yīng)的權(quán)重；

步驟四、設(shè)定全局的目標(biāo)函數(shù)F，

F＝MAX(condA*Avalue+condB*Bvalue-condC*Cvalue-condD*Dvalue+condE*Evalue)其中：condA、condB、condC、condD、condE這些變量的值的范圍是0-1，表示的是用戶限定各個(gè)單目標(biāo)所占全局目標(biāo)的權(quán)重分布；

步驟五、執(zhí)行改進(jìn)蟻群算法，

步驟六、計(jì)算出帕累托解，帕累托解的組成是根據(jù)用戶自定義的目標(biāo)組成的[PFvalue,PAvalue,PBvalue,PCvalue,PDvalue,PEvalue]，PFvalue代表的是目標(biāo)函數(shù)的最優(yōu)解，但是有時(shí)候并不是目標(biāo)最優(yōu)就是用戶偏好的最優(yōu)，用戶可能會(huì)根據(jù)某個(gè)維度重新設(shè)置權(quán)重，獲得更好的最優(yōu)。同時(shí)PFvalue的值在蟻群算法進(jìn)行比較的時(shí)候會(huì)影響信息素的值，各個(gè)參數(shù)的定義如下：

PAvalue＝condA*Avalue

PBvalue＝condB*Bvalue

PCvalue＝condC*Cvalue

PDvalue＝condD*Dvalue

PEvalue＝condE*Evalue

當(dāng)蟻群算法執(zhí)行結(jié)束之后，我們將根據(jù)計(jì)算出結(jié)果的解進(jìn)行排序，選取出前15％的記錄，用平行坐標(biāo)坐標(biāo)的方式可視化表示，用戶可以直觀查看解，同時(shí)再進(jìn)行調(diào)節(jié)參數(shù)重新計(jì)算。

步驟七、利用可視化交互操作進(jìn)行驗(yàn)證，若所獲得的帕累托解不是理想結(jié)果，則調(diào)整步驟一至步驟三的設(shè)定值，直至獲得理想結(jié)果。

所述改進(jìn)蟻群算法，具體包括以下步驟：

用戶在指定的地圖區(qū)域內(nèi)用鼠標(biāo)點(diǎn)選初始螞蟻的位置；

用戶在不同的地方點(diǎn)選了30只螞蟻的位置后，開始執(zhí)行算法：

對(duì)于30只螞蟻，同時(shí)開始進(jìn)行尋路，當(dāng)每只螞蟻迭代次數(shù)少于500次時(shí)，重復(fù)執(zhí)行以下處理，即根據(jù)信息素溶度隨機(jī)出來(lái)的隨機(jī)數(shù)(1,2,3,4,5,6,7,8)，其中每個(gè)數(shù)字代表的是一個(gè)方向，1代表向上，2代表向右上，3代表向右，4代表向右下，5代表向下，6代表向左下，7代表向左，8代表向左上；

如果挑選的方向是走不通的，那么重新在挑選一個(gè)方向；

如果挑選的方向是走得通的，判斷螞蟻?zhàn)哌^(guò)的地方是否滿足條件：

若螞蟻?zhàn)哌^(guò)的地方滿足條件，那么更新這塊的信息素+0.001f，然后計(jì)算螞蟻的步長(zhǎng)，以跳出局部極值；