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

申元霞，王國胤，曾傳華

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

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

入選年份：2016

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

申德榮，于戈，王習(xí)特，等

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

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

入選年份：2016

知識圖譜構(gòu)建技術(shù)綜述

劉嶠，李楊，段宏，等

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

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

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

劉唐，彭艦，楊進(jìn)

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

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

入選年份：2016