計算機科學技術

相關性粒子群優(yōu)化模型

申元霞，王國胤，曾傳華

摘要：目的：粒子群優(yōu)化算法因概念簡潔、優(yōu)化性能良好等特點在諸多工程領域得到了成功地應用。但是在求解復雜優(yōu)化問題時，算法易陷入早期收斂。如何克服早期收斂并提高優(yōu)化性能是粒子群優(yōu)化研究的熱點問題。針對這個問題，本文從如何合理利用自身經(jīng)驗信息和群體共享信息的角度進行探討。方法：首先基于認知論的觀點對速度更新公式中的隨機因子進行了分析，建立了粒子對自身經(jīng)驗信息和群體共享信息認知的內(nèi)在聯(lián)系，提出了相關性粒子群優(yōu)化模型。該模型采用Copula函數(shù)去刻畫隨機因子間的相關結構，通過不同的相關結構和相關性程度反映粒子對自身經(jīng)驗信息和群體共享信息利用策略的差異；接著給出了基于Gaussian copula的相關性粒子群優(yōu)化模型的實現(xiàn)方法。最后從理論上給出了隨機因子間相關程度與群體多樣性的關系式；證明了隨機因子間相關程度與算法收斂性的關系，同時給出了相關性粒子群優(yōu)化模型的收斂條件。結果：從隨機因子相關系數(shù)與種群多樣性的關系式分析可以看出，在相關性粒子群優(yōu)化模型中群體預期多樣性的期望隨著相關系數(shù)的變化而變化。當隨機因子間呈正線性相關時群體預期多樣性的期望為最大；當隨機因子間呈負線性相關時群體預期多樣性的期望為最小。從隨機因子間相關程度與算法收斂性的關系分析可知：（1）對于不同的相關程度，當慣性權重ω、加速系數(shù)滿足給出的條件時，粒子位置期望均收斂于粒子自身最優(yōu)位置和群體最優(yōu)位置的算術均值。（2）從給出的粒子位置方差極限與隨機因子相關系數(shù)的關系表達式可知，在粒子收斂的過程中，粒子位置的波動幅度與隨機因子的相關程度有關。當隨機因子間呈完全正線性相關時，粒子位置變量均方收斂于粒子自身最優(yōu)位置和群體最優(yōu)位置的算術均值。Gaussian copula相關性粒子群優(yōu)化模型的相關系數(shù)方差分析可知，隨機因子間相關程度的水平設置對模型的優(yōu)化性能有特別顯著的影響；數(shù)值仿真實驗結果表明，當相關系數(shù)為1時，基于Gaussian copula相關性粒子群優(yōu)化模型不僅具有高的收斂精度，同時具有快的收斂速度；當相關系數(shù)為-1時，該模型易陷入局部最優(yōu)。結論：在隨機因子認知分析的基礎上，本文給出了隨機因子的相關性假設，提出了相關性PSO模型。該模型采用Copula函數(shù)描述了粒子對自身經(jīng)驗信息和群體共享信息持有態(tài)度的關聯(lián)性，通過分析Gaussian copula的概率特性解釋了相關性粒子群優(yōu)化模型的認知行為。當慣性權重、加速系數(shù)都保持固定策略的前提下，群體預期的多樣性隨著相關系數(shù)的增加而增大；粒子位置的波動幅度隨隨機因子相關程度的變化而變化。隨著相關系數(shù)的增加，模型的優(yōu)化性能有明顯提高的趨勢；當隨機因子成完全正線性相關時，模型的綜合優(yōu)化性能達最高。

來源出版物：軟件學報, 2011, 22(4): 695-708

入選年份：2016

支持大數(shù)據(jù)管理的NoSQL系統(tǒng)研究綜述

申德榮，于戈，王習特，等

摘要：目的：隨著云計算、互聯(lián)網(wǎng)等技術的發(fā)展，大數(shù)據(jù)廣泛存在。分析大數(shù)據(jù)的特點以及支持大數(shù)據(jù)管理系統(tǒng)面臨的關鍵技術，探索大數(shù)據(jù)管理的前沿研究和研究挑戰(zhàn)，主要包括數(shù)據(jù)存儲模型和查詢處理策略，支持事務處理的分布式事務，提高系統(tǒng)性能的負載動態(tài)均衡和副本管理策略。方法：依據(jù)大數(shù)據(jù)特點和大數(shù)據(jù)管理需求，結合分布式數(shù)據(jù)庫、NoSQL數(shù)據(jù)庫和云計算等技術，研究大數(shù)據(jù)管理技術。首先，基于key-value的數(shù)據(jù)模型和基于hash的分布索引策略；其次，將數(shù)據(jù)一致性維護交由用戶管理或回避兩段提交協(xié)議（2PC）的分布式事務管理技術；第三，多模式的負載動態(tài)均衡策略；第四，自適應的副本管理策略和多種一致性維護方法共存；第五，基于MapReduce分布式框架的復雜查詢處理與優(yōu)化策略。結果：key-value數(shù)據(jù)模型滿足海量數(shù)據(jù)管理的可擴展性、簡單查詢的高效率等應用需求。key-value數(shù)據(jù)存儲系統(tǒng)典型采用基于key哈希存儲或范圍存儲，基于BloomFilter局部過濾技術以及多種索引共存的數(shù)據(jù)索引策略，但只支持簡單的查詢操作和單key的事務特性，限制了 key-value存儲系統(tǒng)的應用。key-value數(shù)據(jù)存儲系統(tǒng)典型，一種方法是將一致性檢查交給應用層處理，但增加了開發(fā)者負擔；另一種是實現(xiàn)多key的本地事務或將事務限制在同組內(nèi)的分布式事務，雖然可避開兩段提交協(xié)議（2PC），但并不能靈活而低代價地支持真正的分布式事務。針對資源負載、數(shù)據(jù)負載和任務負載（用戶負載、事務負載、操作負載等），分別側重資源負載均衡分配、數(shù)據(jù)動態(tài)遷移、任務動態(tài)遷移的動態(tài)負載平衡模型，能夠有效提高系統(tǒng)資源利用率、系統(tǒng)吞吐率和系統(tǒng)整體性能，但沒有綜合考慮多類型負載均衡的影響作用。自適應的副本管理策略對系統(tǒng)彈性、動態(tài)負載均衡和改善系統(tǒng)性能等方面具有重要作用，需要有可行的均衡副本策略的利益和代價模型，提高副本對系統(tǒng)的貢獻度；根據(jù)應用需求，采用多種一致性策略共存模式，如面向事務處理的強一致性和弱一致性數(shù)據(jù)維護策略，并通過多策略相互作用來提升系統(tǒng)的性能和可擴展性。將復雜查詢交由應用層處理，或基于MapReduce模型組件定義查詢視圖并應用MapReduce架構并行地處理，后者是當前流行的用于復雜查詢和大數(shù)據(jù)分析的分布式并行處理架構。結論：大數(shù)據(jù)帶來了大機遇，key-value數(shù)據(jù)存儲系統(tǒng)已成為了研究者關注的熱點問題。為有效地支持大數(shù)據(jù)管理，有關key-value數(shù)據(jù)存儲系統(tǒng)及其相關研究還有許多挑戰(zhàn)性問題，需要研究者去研究和探討，典型研究包括海量數(shù)據(jù)分布存儲與局部性、分布式事務管理模型、負載均衡的自適應性、靈活支持復雜查詢、自適應的的副本管理策略以及有關key-value數(shù)據(jù)模型的支持理論等。

來源出版物：軟件學報, 2013, 24(8): 1786-1803

入選年份：2016

知識圖譜構建技術綜述

劉嶠，李楊，段宏，等

摘要：目的：知識圖譜技術在人工智能領域的成功應用引起了業(yè)界和學術界的廣泛關注。知識圖譜是一個結構化的語義知識庫，其基本組成單位是（實體，關系，實體）三元組，及相關的屬性信息。實體間通過關系相互聯(lián)結，構成網(wǎng)狀的知識結構，形成對物理世界中的概念、對象及其相互關系的一種符號表達。知識圖譜構建是一個熱點集中的交叉研究領域，仍有許多值得長期研究和關注的突出問題，具有技術復雜度高、構建難度大的特點。本文從知識圖譜的定義和技術架構出發(fā)，對構建知識圖譜涉及的關鍵技術進行了自底向上的解析。目的是宣傳該技術，吸引更多的關注和科研投入。方法和結果：知識圖譜的構建過程是一個數(shù)據(jù)驅動的持續(xù)迭代更新過程。本文首先對知識圖譜構建相關的關鍵技術進行了全面調(diào)研和分類整理，然后對跨語種知識圖譜構建技術和知識圖譜典型應用的發(fā)展現(xiàn)狀進行了簡述，最后總結了知識圖譜構建技術當前面臨的主要問題和挑戰(zhàn)。其中，重點介紹了知識圖譜系統(tǒng)的邏輯構成和核心構建技術。知識圖譜的典型邏輯構成包括數(shù)據(jù)層（知識庫）和模式層（本體庫）等兩大功能組件。本文介紹的知識圖譜構建技術專指從原始數(shù)據(jù)出發(fā)，采用一系列自動化或半自動化的技術手段，迭代地從原始數(shù)據(jù)中提取出知識元素（事實、屬性、本體等），并將其分別存入數(shù)據(jù)層和模式層的過程。按照自底向上的構建邏輯，從信息抽取到知識入庫，將涉及的關鍵技術進一步劃分為3個層次，（1）信息抽取層，擇要介紹了開放域信息抽取領域近年來取得的新進展。（2）知識融合層，主要介紹實體鏈接技術和知識合并技術的發(fā)展現(xiàn)狀及其在知識圖譜構建領域的應用。（3）知識加工層，對本體抽取、知識推理和知識質量評估等知識圖譜擴容關鍵技術進行了歸納和總結。結論：可以預見，隨著Google Now，Microsoft Cortana，Apple Siri，IBM Watson等基于知識圖譜的商業(yè)智能產(chǎn)品的社會滲透程度不斷提高，知識圖譜技術將迎來新的發(fā)展機遇。例如，Siri已成為美國第二大移動搜索引擎和排名第一的移動語音服務應用，影響和改變了許多人的觀念和生活模式。而在2016年美國大選中，通過Xkeyscore項目采集并存放在Spy Cloud上的希拉里私人郵件，成為了導致選情反轉的關鍵，該項目本身也是一個知識圖譜項目。因此，知識圖譜技術正在對人類生活和社會發(fā)展產(chǎn)生深刻的影響，值得投入更多的研究努力。

來源出版物：計算機研究與發(fā)展, 2016, 53(3): 582-600入選年份：2016

異構延遲容忍移動傳感器網(wǎng)絡中基于轉發(fā)概率的數(shù)據(jù)傳輸

劉唐，彭艦，楊進

摘要：目的：近年來，將無線傳感器網(wǎng)絡應用于面向移動對象的數(shù)據(jù)收集成為研究的熱點。在允許移動節(jié)點間的數(shù)據(jù)傳遞存在延遲的容忍延遲移動傳感器網(wǎng)絡DTMSN（delay tolerant mobile sensor network）中，如何以盡可能低的能量能耗和盡可能小的數(shù)據(jù)傳輸延遲來達到盡可能高的傳輸可靠性，成為了DTMSN要解決的首要問題。本文針對由不同類型的移動傳感器節(jié)點構成的異構延遲容忍傳感器網(wǎng)絡 HDTMSN（heterogeneous delay tolerant mobile sensor network），提出了一種基于轉發(fā)概率的動態(tài)數(shù)據(jù)傳輸算法 FPAD（forwarding probability-based adaptive data delivery algorithm）。方法：在由異構移動傳感器節(jié)點構成的 HDTMSN中，F(xiàn)PAD算法由數(shù)據(jù)傳輸和隊列管理兩個主要部分組成。數(shù)據(jù)傳輸機制的基本思想是，網(wǎng)絡中的節(jié)點有消息等待發(fā)送時首先計算出自身的消息傳輸概率，然后獲得通信范圍內(nèi)其他節(jié)點的消息轉發(fā)概率。節(jié)點隨后將消息轉發(fā)到所有轉發(fā)概率大于自身傳輸概率的節(jié)點。針對異構環(huán)境下消息大小不同且傳輸延遲要求不同的特點，節(jié)點的傳輸概率和轉發(fā)概率的計算均由能量消耗因子和傳輸延遲因子構成，以保證消息能以更低的能量消耗和更小的傳輸延遲發(fā)送到匯聚點。隊列管理機制則是根據(jù)消息不同的傳輸延遲要求作為消息丟棄的依據(jù)，使得在盡量增大傳輸成功率的同時有效控制消息副本數(shù)量，降低網(wǎng)絡傳輸能耗，延長網(wǎng)絡壽命。結果：為驗證FPAD算法的性能，在不同的網(wǎng)絡環(huán)境下，對FPAD、SRAD（selective replication-based adaptive data delivery scheme）、DT（直接傳遞）和 Floating（泛洪）算法的網(wǎng)絡壽命、消息傳輸成功率、消息平均副本數(shù)及消息平均傳輸延遲進行實驗對比。（1）首先在默認網(wǎng)絡環(huán)境下對4個算法進行性能對比。FPAD算法的壽命達到了 1.908天，高于要進行消息轉發(fā)的SRAD算法和Floating算法。由于FPAD算法通過比較傳輸概率和轉發(fā)概率進行數(shù)據(jù)分發(fā)，從而數(shù)據(jù)傳輸成功率到達了最高的89%。對于消息平均副本數(shù)，F(xiàn)PAD算法為所有數(shù)據(jù)轉發(fā)算法中最低的 7.27。此外，F(xiàn)PAD算法的消息平均傳輸延遲為130.5 s，低于其他3個算法。（2）改變異構節(jié)點占網(wǎng)絡中總節(jié)點數(shù)的比例，觀察各種算法在不同異構節(jié)點比例下的性能。由于FPAD算法充分考慮到了網(wǎng)絡的異構性，在不同的異構節(jié)點比例下，F(xiàn)PAD算法均有著最優(yōu)的消息平均傳輸成功率、平均副本數(shù)（除不進行消息轉發(fā)的DT算法）、消息平均傳輸延遲。（3）改變節(jié)點的通信半徑，F(xiàn)PAD同樣有著最高的消息平均傳輸成功率、比SARD和Floating算法更少的消息平均副本數(shù)、以及最低的消息平均傳輸延遲。（4）改變節(jié)點的運動速度，F(xiàn)PAD算法隨著節(jié)點運動速度的增大，消息傳輸成功率也不斷提升。同時，F(xiàn)PAD算法在不同的節(jié)點運動速度下保持了低于 SARD和Floating算法的消息平均副本數(shù)和最低的消息平均傳輸延遲。（5）增大節(jié)點的消息隊列長度，使得節(jié)點能容納更多的消息，此時FPAD算法的消息傳輸成功率持續(xù)上升且明顯高于其他算法。由于FPAD始終能較好地控制消息副本數(shù)量，因此FPAD的消息平均副本數(shù)一直低于SARD和Floating算法。此外，節(jié)點存儲隊列的變化對4種算法的傳輸延遲沒有顯著影響。結論：面向由不同傳感器節(jié)點構成的可以監(jiān)測不同對象的異構延遲容忍移動傳感器網(wǎng)絡中的數(shù)據(jù)傳輸，提出了一種適用異構環(huán)境下的基于轉發(fā)概率的動態(tài)數(shù)據(jù)傳輸策略 FPAD。與已有工作相比，F(xiàn)PAD的主要貢獻表現(xiàn)在于以下2個方面。（1）在FPAD算法中，消息的轉發(fā)根據(jù)消息所在節(jié)點的傳輸概率及通信范圍內(nèi)其他節(jié)點的轉發(fā)概率確定。根據(jù)異構網(wǎng)絡的特點，傳輸概率和轉發(fā)概率均由能量消耗因子和傳輸延遲因子計算得出，使節(jié)點獲取的消息能夠以盡可能低的能量消耗和盡可能小的傳輸延遲發(fā)送到匯聚點。（2）FPAD引入適應于異構環(huán)境的消息隊列管理機制，以消息當前的延遲容忍度作為消息丟棄的依據(jù)，使得在盡量增大傳輸成功率的同時有效控制了消息副本數(shù)量，降低了網(wǎng)絡能耗，延長了網(wǎng)絡壽命。

來源出版物：軟件學報, 2013, 24(2): 215-229

入選年份：2016