多智能體網(wǎng)絡(luò)中的動(dòng)態(tài)一致平均算法及其應(yīng)用
發(fā)布時(shí)間：2018-11-09 09:41
【摘要】：本文研究多智能體網(wǎng)絡(luò)中的一類重要問題——?jiǎng)討B(tài)一致平均問題,具體而言,即網(wǎng)絡(luò)中所有智能體動(dòng)態(tài)地跟蹤一組時(shí)變參考輸入信號(hào)的均值,并使得每個(gè)智能體的跟蹤結(jié)果都等于該組時(shí)變信號(hào)的均值。本文研究的則是如何分布式地求解該問題。而分布式計(jì)算又可分為有中心分布式計(jì)算與無中心分布式計(jì)算兩大類,后者相較于前者具有通信更均衡、算法更魯棒、隱私保護(hù)性更強(qiáng)等優(yōu)點(diǎn),因而無中心分布式信息處理的應(yīng)用前景更廣泛。本文首先介紹了幾種現(xiàn)有的無中心分布式動(dòng)態(tài)一致平均算法,然后在前人的基礎(chǔ)上設(shè)計(jì)開發(fā)了一種新的無中心分布式求解動(dòng)態(tài)一致平均的算法DDAC。 DDAC相較于前人設(shè)計(jì)的算法,具有更好的參數(shù)可調(diào)性,在大量的數(shù)值實(shí)驗(yàn)中,也具有更高的收斂精度。動(dòng)態(tài)一致平均算法擁有很多重要的應(yīng)用,除了用于需要直接動(dòng)態(tài)跟蹤時(shí)變信號(hào)的一些實(shí)際應(yīng)用(位置跟蹤、編隊(duì)控制等)之外,本文還原創(chuàng)性地提出將動(dòng)態(tài)一致平均算法用于處理一些優(yōu)化問題的子問題,并重點(diǎn)以低秩矩陣補(bǔ)全問題為例來說明這一原創(chuàng)性想法的有效性與先進(jìn)性。本文對(duì)低秩矩陣補(bǔ)全問題進(jìn)行了研究,并在前人提出的一種集中式求解矩陣補(bǔ)全問題的算法基礎(chǔ)上,設(shè)計(jì)開發(fā)出了兩種新的無中心分布式矩陣補(bǔ)全算法D-LMaFit與DDAC-LMaFit。在此研究過程中,我們指出將有中心分布式(并行)實(shí)現(xiàn)的算法改造為無中心分布式算法的關(guān)鍵與難點(diǎn),即如何使用無中心分布式的算法取代網(wǎng)絡(luò)中心節(jié)點(diǎn)。對(duì)此我們給出答案,即動(dòng)態(tài)一致平均算法可以解決該難點(diǎn)。我們使用了兩種動(dòng)態(tài)一致平均算法(前人提出的EXTRA與本文中新設(shè)計(jì)的DDAC算法)解決該難點(diǎn),分別對(duì)應(yīng)地得到前述兩種算法。并且,考慮到實(shí)際應(yīng)用中有對(duì)于數(shù)據(jù)的隱私保護(hù)的需要,我們分析了分布式低秩矩陣補(bǔ)全問題中的隱私保護(hù)問題,并以D-LMaFit算法為例,證明了對(duì)于一系列能夠?qū)⑵涓率綄憺橐粋�(gè)線性時(shí)不變系統(tǒng)的算法,若網(wǎng)絡(luò)拓?fù)錆M足一定條件,則該算法具有對(duì)于隱私保護(hù)的性能。作為更多擴(kuò)展,結(jié)合我們提出的動(dòng)態(tài)一致平均算法可以替代中心節(jié)點(diǎn)的求平均操作,我們還對(duì)兩種一階優(yōu)化算法——梯度下降法與鄰近點(diǎn)梯度法的無中心分布化實(shí)現(xiàn)進(jìn)行了研究,并分別設(shè)計(jì)得到了若干有效的新的無中心分布式梯度下降法(DDAC-GD算法、EXTRA-GD算法與FODAC-GD算法)與新的無中心分布式鄰近點(diǎn)梯度法(DDAC-PG算法、EXTRA-PG算法與FODAC-PG算法)。全文致力于研究無中心分布式動(dòng)態(tài)一致平均算法,設(shè)計(jì)了一種新的有效的算法；并對(duì)如何將有中心分布式(并行)實(shí)現(xiàn)的算法通過求解動(dòng)態(tài)一致平均子問題,設(shè)計(jì)為無中心分布式的算法進(jìn)行了討論,相應(yīng)地設(shè)計(jì)了若干新的用于求解不同問題的無中心分布式算法。大量的數(shù)值實(shí)驗(yàn)則表明了算法的有效性。本文的研究為設(shè)計(jì)無中心分布式算法提供了新思路。
[Abstract]:In this paper, we study a class of important problems in multi-agent networks, that is, the dynamic uniform averaging problem. In particular, all agents in the network dynamically track the mean value of a set of time-varying reference input signals. The tracking results of each agent are equal to the mean of the time-varying signals. In this paper, we study how to solve the problem distributed. Distributed computing can be divided into two categories: distributed computing with center and distributed computing without center. Compared with the former, the latter has the advantages of more balanced communication, more robust algorithm, stronger privacy protection, and so on. Therefore, the application prospect of distributed information processing without center is more extensive. This paper first introduces several existing distributed dynamic uniform averaging algorithms without center, and then designs and develops a new algorithm, DDAC., for solving dynamic uniform averaging without center on the basis of previous researches. Compared with the previous algorithms, DDAC has better parameter adjustability and higher convergence accuracy in a large number of numerical experiments. The dynamic uniform averaging algorithm has many important applications, except for some practical applications (position tracking, formation control, etc.) that require direct dynamic tracking of time-varying signals. This paper also proposes to apply the dynamic uniform averaging algorithm to the subproblems of some optimization problems, and takes the low rank matrix complement problem as an example to illustrate the validity and advanced nature of this original idea. In this paper, the low rank matrix complement problem is studied, and on the basis of a centralized algorithm to solve the matrix complement problem, two new non-central distributed matrix complement algorithms D-LMaFit and DDAC-LMaFit. are designed and developed. In the course of this research, we point out the key and difficulty of transforming the distributed algorithm with the center (parallel) into the distributed algorithm without center, that is, how to replace the center node of the network with the algorithm without center distribution. We give the answer that the dynamic uniform averaging algorithm can solve the problem. We use two dynamic uniform averaging algorithms (EXTRA proposed by previous authors and DDAC algorithm designed in this paper) to solve this problem and obtain the two algorithms mentioned above respectively. Considering the need of data privacy protection in practical application, we analyze the privacy protection problem in distributed low rank matrix complement problem, and take D-LMaFit algorithm as an example. It is proved that for a series of algorithms which can be written as a linear time-invariant system, if the network topology satisfies certain conditions, the algorithm has the property of privacy protection. As a further extension, the dynamic uniform averaging algorithm proposed by us can replace the averaging operation of the central node. We also study the realization of two first-order optimization algorithms, i.e. gradient descent method and adjacent point gradient method, and design several effective non-central distributed gradient descent methods (DDAC-GD), respectively. EXTRA-GD algorithm and FODAC-GD algorithm) and new non-center distributed adjacent point gradient method (DDAC-PG algorithm, EXTRA-PG algorithm and FODAC-PG algorithm). This paper is devoted to the research of distributed uniform averaging algorithm without center, and designs a new and effective algorithm. And how to design the distributed algorithm without center by solving the dynamic uniform average subproblem is discussed. Several new distributed algorithms are designed to solve different problems. A large number of numerical experiments show the effectiveness of the algorithm. The research in this paper provides a new idea for the design of distributed algorithm without center.
【學(xué)位授予單位】：中國科學(xué)技術(shù)大學(xué)
【學(xué)位級(jí)別】：碩士
【學(xué)位授予年份】：2016
【分類號(hào)】：TP18
本文編號(hào)：2320048
[Abstract]:In this paper, we study a class of important problems in multi-agent networks, that is, the dynamic uniform averaging problem. In particular, all agents in the network dynamically track the mean value of a set of time-varying reference input signals. The tracking results of each agent are equal to the mean of the time-varying signals. In this paper, we study how to solve the problem distributed. Distributed computing can be divided into two categories: distributed computing with center and distributed computing without center. Compared with the former, the latter has the advantages of more balanced communication, more robust algorithm, stronger privacy protection, and so on. Therefore, the application prospect of distributed information processing without center is more extensive. This paper first introduces several existing distributed dynamic uniform averaging algorithms without center, and then designs and develops a new algorithm, DDAC., for solving dynamic uniform averaging without center on the basis of previous researches. Compared with the previous algorithms, DDAC has better parameter adjustability and higher convergence accuracy in a large number of numerical experiments. The dynamic uniform averaging algorithm has many important applications, except for some practical applications (position tracking, formation control, etc.) that require direct dynamic tracking of time-varying signals. This paper also proposes to apply the dynamic uniform averaging algorithm to the subproblems of some optimization problems, and takes the low rank matrix complement problem as an example to illustrate the validity and advanced nature of this original idea. In this paper, the low rank matrix complement problem is studied, and on the basis of a centralized algorithm to solve the matrix complement problem, two new non-central distributed matrix complement algorithms D-LMaFit and DDAC-LMaFit. are designed and developed. In the course of this research, we point out the key and difficulty of transforming the distributed algorithm with the center (parallel) into the distributed algorithm without center, that is, how to replace the center node of the network with the algorithm without center distribution. We give the answer that the dynamic uniform averaging algorithm can solve the problem. We use two dynamic uniform averaging algorithms (EXTRA proposed by previous authors and DDAC algorithm designed in this paper) to solve this problem and obtain the two algorithms mentioned above respectively. Considering the need of data privacy protection in practical application, we analyze the privacy protection problem in distributed low rank matrix complement problem, and take D-LMaFit algorithm as an example. It is proved that for a series of algorithms which can be written as a linear time-invariant system, if the network topology satisfies certain conditions, the algorithm has the property of privacy protection. As a further extension, the dynamic uniform averaging algorithm proposed by us can replace the averaging operation of the central node. We also study the realization of two first-order optimization algorithms, i.e. gradient descent method and adjacent point gradient method, and design several effective non-central distributed gradient descent methods (DDAC-GD), respectively. EXTRA-GD algorithm and FODAC-GD algorithm) and new non-center distributed adjacent point gradient method (DDAC-PG algorithm, EXTRA-PG algorithm and FODAC-PG algorithm). This paper is devoted to the research of distributed uniform averaging algorithm without center, and designs a new and effective algorithm. And how to design the distributed algorithm without center by solving the dynamic uniform average subproblem is discussed. Several new distributed algorithms are designed to solve different problems. A large number of numerical experiments show the effectiveness of the algorithm. The research in this paper provides a new idea for the design of distributed algorithm without center.
【學(xué)位授予單位】：中國科學(xué)技術(shù)大學(xué)
【學(xué)位級(jí)別】：碩士
【學(xué)位授予年份】：2016
【分類號(hào)】：TP18
【參考文獻(xiàn)】
相關(guān)期刊論文 前1條
1 林安亞;凌青;;多智能體網(wǎng)絡(luò)中的分布式動(dòng)態(tài)一致平均算法[J];電子技術(shù);2016年06期
，本文編號(hào)：2320048
本文鏈接：http://sikaile.net/kejilunwen/zidonghuakongzhilunwen/2320048.html
最近更新
教材專著
