基于優化模糊遺傳算法的地理信息個性化推送方法

邵改革，盧小平，杜耀剛，李國清

（1．河南理工大學 礦山空間信息技術國家測繪地理信息局重點實驗室，河南 焦作454003；2．河南北斗空間科技有限公司，河南 鄭州450003；3．河南省遙感測繪院，河南 鄭州450003）

隨著“數字城市”成果的廣泛應用及“智慧城市”建設的啟動，物聯網和云計算等技術正在迅速發展，人們生產生活以及各類傳感網產生的數據已從TB級增長到PB級，進入到了智慧城市的“大數據時代”［1－2］。因此，如何從海量數據中挖掘有用的信息、提高信息的應用價值，成為當前亟待解決的技術難題。

目前，LBS技術能夠讓用戶在附近位置根據興趣點進行搜索，但仍沒有達到智慧城市的設想，地理信息應該實現更加智能化、人性化的服務。面對龐大的地理空間信息，通過智能計算快速檢索和處理，并挖掘其中有用的信息為公眾服務，以達到在合適的時間、關注的地點，將正確的信息推送給需要的人個性化服務。本文通過運用遺傳算法的最優搜索特征，結合神經網絡和模糊分類，建立用戶的動態模型，并對用戶的下一步行為進行預測，將動態模型過濾后的各類地理空間信息推送給用戶，免去用戶自行搜索的煩惱。

1 關鍵技術

1．1 模糊遺傳算法

遺傳算法是一種模擬遺傳選擇和自然淘汰的生物進化過程計算模型，通過自然選擇、遺傳、變異等作用機制，形成全局最優化算法［3］。在遺傳算子進行選擇、交叉和變異的作用下，原來具有低階、短定義距和平均適應度高于整個種群平均適應度的模式在子代繁衍中得到指數級增長［4］。一個模式Hi在選擇階段，各模式按照其適應度在種群適應度中所占的比例m進行復制，若Hi的適應度較大，其復制概率越高，反之則容易丟失。經過選擇后，Hi理論上應有m×f（Hi）／favg個樣本。交叉操作與Hi所定義的距離Di相關，Di越大，Hi產生交叉的概率就越高。遺傳算法從問題解的子集開始搜索，并同時對空間中的多個解進行評估，從建立的模型中實現全局擇優［5］。

地理空間數據不僅具有空間性、時間性、復雜性等特點，還包括空間的不確定性，以及人的思想、行為活動等，也存在一定的不確定性，這可以利用模糊集理論引入多準則決策來解決實際建模中的不確定性問題［6］。模糊集可根據自組織、自適應特點，采用模糊模型控制諸如時變、非線性、不確定等復雜關系，不斷完善非線性系統的建模與控制［7－8］。通過對用戶進行分析，建立不同的評價指標，然后對指標值進行模糊化，最后加權平均反模糊化，可得用戶的權重輸出：

式中：wi為規則權重；αi（x）為輸入值x的模糊度；Vi為集合的容積；ci為集合權重。每個權值計算過程中，可以通過隨機梯度下降方法調整權重，改善模糊系統中的不確定性規則。隱含層的多層神經網絡解決了多層網絡中隱含單元連接權值的學習問題，其方法是不斷調整權值使得整個網絡的總誤差最小。假設輸入的節點、隱含節點和輸出節點分別為Ik，Mk和Ok，wij為網絡節點權值，則輸入層和隱含層的關系表示為

隱含層到輸出層的權值矩陣為W，則W的計算方法：

1．2 改進的模糊遺傳算法

遺傳算法雖然可以求解全局最優，但收斂速率與局部最優形成矛盾，導致因顧及收斂速率而陷入局部最優 通過對變異算子進行改進 增加遺傳算法收斂全局最優的概率，可快速找到全局最優解。改進后變異概率Pm自適應變化為

式中：Pmax是最大的變異概率，f為變異個體的適應度，fmax是種群最大的適應度，favg為適應度的平均值，k為自然環境的擾動。當試驗個體的適應度大于整個種群的適應度時，該個體的適應性就越強，其發生變異的概率就越小；反之，則適應性就較弱，而且為增加種群的多樣性，其突變的概率也越大。改進后的遺傳算法可使局部搜索能力顯著增強，達到全局收斂，提高效率。

本文提出一種基于改進的遺傳算法、模糊理論和神經網絡的集成算法，即充分結合遺傳算法的全局搜索最優性、模糊理論處理非線性關系時的優勢及神經網絡的自適應和學習能力等優點。假設待處理數據為Y，其每條記錄包含n個自變量和1個因變量，其中自變量與因變量呈非線性關系。利用模糊集合的模糊函數處理自變量和因變量的映射關系，建立一個神經網絡模型，網絡輸入的節點數為n，輸出層的節點數為1，隱含層根據樣本容量而定；然后以神經網絡的輸出值構建權值網絡，并利用改進的遺傳算法優化網絡權值模型，將遺傳算法和模糊神經網絡模型整合在一起。優化后的模糊遺傳算法流程如圖1所示，其中G是當代數，M為每代種群中最大個體數。

2 信息個性化推送服務的實現

2．1 推送流程

運用模糊遺傳算法建立針對每個用戶的動態模型，根據用戶的興趣、行為習慣和社會需求等進行地理信息個性推送服務。

1）充分收集用戶個人的興趣信息，利用模糊神經網絡的監督學習建立動態模型，根據用戶的行為趨勢不斷進行修正，從而建立預測模型。

2）將過濾后的地理空間信息根據用戶位置進行推送，從而實現了推送個性化信息。

3）用戶對接受到的推送信息評價后自動反饋到動態模型，可對預測模型進行不斷修正和完善，如圖2所示。

2．2 搜索匹配

圖1 優化后的模糊遺傳算法流程

圖2 信息推送流程

當用戶使用關鍵詞進行搜索時，可自動記錄用戶的檢索和查詢情況，通過分析用戶的查詢結果來獲取用戶的使用信息 采用向量模型匹配關鍵詞的方法可提高索引詞的選擇和語義提取，關鍵詞在文檔中的權重定義為

其中：fwi為關鍵詞w在文檔中的出現概率；N，nw為信息庫中文檔個數和包含關鍵詞的文檔個數；wi是文檔中所有關鍵詞的個數。如果一個詞條在文檔中出現的次數越多，其權重就越大；若一個詞條在不同的文檔中出現的次數越多，則其對于文檔庫中文檔的區分能力就越差，即詞條的權重受到lg（N／nw）的制約。

根據用戶使用關鍵詞檢索情況對用戶進行分類，這就需要判定用戶查詢與結果記錄詞條的相關性，可通過相似度函數進行計算，即顧忌文本的長度和查詢字符串的長度，具體表達式為

式中：qi為q的第i個詞條的權重；wi為q的第i個詞條在文檔d中的權重；｜d｜和｜q｜分別表示文檔和查詢字符串的長度。

2．3 推送模型

在用戶所處位置P點范圍R內，搜索所有符合條件的信息，通過動態模型進行篩選，并按照預測模型推送給用戶個性化服務信息，這些信息可劃分為吃、住、游、購、娛和美共六類。根據用戶的興趣和類型進行區分后，可將不同類別的信息推送給相應的用戶，從而提高了信息推送的質量。每條信息選取距離、類別、價格、時效和好評共五項指標，各個因子的權重可根據經驗賦予不同的權重，如表1所示。

表1 權重分配

表1中，距離采用反距離權法，即wd＝k／R；價格由用戶的使用記錄生成，按照t分布函數求出置信度為90%的置信區間，將其作為用戶價格的參數。為保證推送信息的實效性，采用反時間差法計算時間。

用戶查詢和瀏覽信息過程中，可通過對用戶的喜好和行為趨勢進行模擬，運用模糊遺傳算法不斷完善動態模型，從而實現對用戶行為的預測。實驗中 選取了六類用戶進行模擬實驗 通過模糊神經調整用戶的類別權值，結果如表2所示。

表2 用戶類型模型

2．4 推送策略

對用戶周圍信息進行過濾和篩選后推送地理信息個性化服務，雖然提高了推送信息的準確性，但在實際操作過程中會出現符合條件的信息不足（不能完全匹配用戶特征）等問題。信息推送決策樹可根據信息推送流程及篩選條件，在信息不足時加以補充，即推送其它相關信息內容。決策樹按照二叉樹結構設計，并采用后序遍歷方法（左右根）遍歷整個二叉樹。如果訪問到右子樹即一旦出現信息不足，則停止遍歷，完成對用戶信息的推送。

2．5 結果評價

本文建立的模型可利用反饋機制來評價推送給用戶信息的質量，即用戶對接收到的推送信息的評價自動反饋到后臺服務器，據此修正用戶動態模型。推送信息的預測率是指推送信息與用戶模型的相關性程度，而信息的召回率是指被用戶確認為無用信息在總體中所占的比率。主動推送度是對推送信息的有用度和無用度的綜合評價，該指標反映了信息推送主動可用性的程度。實驗中，根據精度和性能兩個評價指標對六類用戶的反饋結果進行統計，并選擇召回率和有用度進行評定，結果如表3所示。

表3 推送質量評價 %

為評估該算法優化前后對用戶模型的影響，本文選取預測率和推送度作為評價指標，并將優化前后結果進行對比分析，結果如圖3所示。由圖3可知，優化后的個性化信息推送提高了信息的針對性和應用價值，為用戶的決策提供了可靠的參考依據。

圖3 優化前后對比

3 結束語

本文綜合利用模糊理論、遺傳算法和神經網絡等方法，并對這些算法進行改進，建立針對每個用戶的動態模型，可根據用戶位置、個人行為和興趣、社會需求等檢索條件，主動向用戶推送地理信息，實現對用戶的個性化信息推送服務。地理信息的個性化服務能夠滿足用戶對信息的需求，通過對用戶的個性、習慣等進行分析，可向用戶主動推送個性化信息，從而提供高質量的地理信息服務［9］。為提高地理信息個性推送服務的質量，還需要綜合利用更多的智能算法，不斷完善用戶動態模型，增加信息之間的關聯性，以提高信息推送的準確度和信息服務的質量。

［1］ 李德仁，姚遠，邵振峰．智慧城市中的大數據［J］．武漢大學學報：信息科學版，2014，39（6）：631－640．

［2］ 劉經南，方媛，郭遲，等．位置大數據的分析處理研究進展［J］．武 漢 大 學 學 報：信 息 科 學 版，2014，39（4）：379－385．

［3］ 馬永杰，云文霞．遺傳算法研究進展［J］．計算機應用研究，2012，29（4）：1201－1206．

［4］ 于海璁，陸鋒．一種基于遺傳算法的多模式多標準路徑規劃方法［J］．測繪學報，2014，43（1）：89－96．

［5］ 羅亞中，袁端才，唐國金．求解非線性方程組的混合遺傳算法［J］．計算力學學報，2005，22（1）：109－114．

［6］ 李卓，李永樹，梁磊．基于多級模糊與GIS的天然氣管道風險評估［J］．測繪工程，2013，22（1）：78－80．

［7］ 張東波，王耀南，易靈芝．粗集神經網絡及其在智能信息處理領域的應用［J］．控制與決策，2005，20（2）：121－125．

［8］ 杜世宏，王橋，李順．模糊對象粗糙表達及其空間關系研究［J］．遙感學報，2004，8（1）：1－7．

［9］ 陳軍，武昊，李松年，等．面向大數據時代的地表覆蓋動態服務計算［J］．測繪科學技術學報，2013，30（4）：369－374．