多智能體網(wǎng)絡(luò)在運籌學(xué)圖與網(wǎng)絡(luò)分析教學(xué)中的應(yīng)用

何廣

摘要：本文介紹如何巧妙地應(yīng)用多智能體網(wǎng)絡(luò)來解釋運籌學(xué)圖與網(wǎng)絡(luò)分析教學(xué)中有關(guān)圖的一些概念，比如：連通性，度，支撐樹等，從而使得我們的教學(xué)更加生動與形象，同時也使得學(xué)生對這些概念的理解更加深刻。

Abstract： This paper introduces how to use multi-agent networks to explain some concepts related to map graphs such as connectivity， degree， support tree in the teaching of operational research map and networks analysis， which makes our teaching more vivid and image， and also makes students understand these concepts more deeply.

關(guān)鍵詞： 聯(lián)通圖；支撐樹；多智能體

Key words： connected graph；support tree；multi-agent

中圖分類號：TB114.1 文獻(xiàn)標(biāo)識碼：A 文章編號：1006-4311（2017）21-0238-02

0 引言

運籌學(xué)作為科學(xué)名字最早出現(xiàn)在20世紀(jì)30年代末，那時候的運籌學(xué)可以說就是戰(zhàn)爭的“工具”，當(dāng)時中英美借助運籌學(xué)的思想，強(qiáng)有力的打擊了德意日三國，為二戰(zhàn)的勝利奠定了基礎(chǔ)。二戰(zhàn)勝利后運籌學(xué)被廣泛的應(yīng)用到工農(nóng)業(yè)生產(chǎn)的各個領(lǐng)域，大大的提高了我們的生產(chǎn)效率，這也促使近幾十年運籌學(xué)獲得了空前的發(fā)展。圖與網(wǎng)絡(luò)分析作為運籌學(xué)的一個重要分支，現(xiàn)如今已被廣泛的應(yīng)用到物理、化學(xué)、控制論、信息論，科學(xué)管理、電子計算機(jī)等各個領(lǐng)域[1]。在實際生活、生產(chǎn)和科學(xué)研究中，有很多問題可以用圖論的理論和方法來解決。因此在運籌學(xué)的教學(xué)中如何能夠使學(xué)生更加深刻的理解圖與網(wǎng)絡(luò)分析就顯得尤為重要。在該章節(jié)的教學(xué)中引用一些更實際的網(wǎng)絡(luò)的例子來解釋有關(guān)網(wǎng)絡(luò)的概念無疑能夠使教學(xué)更加生動易懂。而多智能體網(wǎng)絡(luò)是近20年控制領(lǐng)域的研究熱點[2]，利用多智能體網(wǎng)絡(luò)來解釋圖的有關(guān)概念既能拓廣學(xué)生的視野，又能使學(xué)生更容易理解，從而調(diào)動學(xué)生的學(xué)習(xí)積極性，進(jìn)而使得我們的教學(xué)效果得到大幅度提高。

1 多智能體網(wǎng)絡(luò)與圖

眾所周知，許多網(wǎng)絡(luò)都可以看成是多智能體網(wǎng)絡(luò)，如無人機(jī)網(wǎng)絡(luò)，移動機(jī)器人網(wǎng)絡(luò)，那么這些網(wǎng)絡(luò)和圖有什么關(guān)系呢？當(dāng)我們把無人機(jī)抽象成頂點，兩架無人機(jī)之間如果有信息交流就連一條邊，這樣無人機(jī)網(wǎng)絡(luò)就可以看成一個圖，如果我們這樣去解釋圖能夠使很多同學(xué)相信原來圖真的可以包含很多復(fù)雜的內(nèi)容，圖真的可以和很多的實際問題產(chǎn)生密切的聯(lián)系，從而激起同學(xué)學(xué)習(xí)圖論的興趣。

2 有向圖與無向圖

在圖論中為什么要把圖分成有向圖和無向圖呢？他們的區(qū)別的本質(zhì)又在哪里呢？我們可以借助多智能體網(wǎng)絡(luò)跟同學(xué)們這樣解釋：在有些無人機(jī)網(wǎng)絡(luò)中信息的交流是相互的，無人機(jī)甲可以接收到向無人機(jī)已的信息，同時無人機(jī)已也可以接收到無人機(jī)甲的信息，即信息可以在這兩架無人機(jī)之間共享互通，這樣形成的圖就是無向圖；而在有些無人機(jī)網(wǎng)絡(luò)中信息交流可能是單向的，無人機(jī)甲可以接收無人機(jī)已的信息，而無人機(jī)已卻不能接收無人機(jī)甲的信息，這樣形成的圖就是有向圖，如果我們能這樣去解釋有向圖和無向圖而不在拘泥于“單行線和雙行線”，肯定能夠使同學(xué)們對于有向圖和無向圖的理解更加深刻，也使之能夠明白為什么非要把圖分成有向圖和無向圖來進(jìn)行研究。

3 連通性的概念與意義

所謂圖的連通性是指圖中的任意兩個頂點都是連通的，也即是任意兩個頂點之間都存在一條初等鏈。而針對無人機(jī)網(wǎng)絡(luò)，所謂連通性是指任意兩個無人機(jī)即使兩者之間不能進(jìn)行直接的信息交流也能夠借助其他的無人機(jī)進(jìn)行間接的信息交流，從而實現(xiàn)信息的共享。

如圖1的無人機(jī)網(wǎng)絡(luò)就是一個聯(lián)通圖，而圖2的無人機(jī)網(wǎng)絡(luò)已就是不聯(lián)通的。對于無人機(jī)網(wǎng)絡(luò)來說連通性意味著什么呢？這意味著這個無人機(jī)網(wǎng)絡(luò)可以實現(xiàn)網(wǎng)絡(luò)一致性[3]，所謂網(wǎng)絡(luò)一致性是指網(wǎng)絡(luò)的一種集體行為，即每一個無人機(jī)的狀態(tài)（或者說行為）可以趨近于一致，而多智能體網(wǎng)絡(luò)的一致性問題是當(dāng)今控制論領(lǐng)域研究的一個熱點問題，這個時候?qū)W生會明白原來連通性背后隱藏著這么大的意義啊！同時也進(jìn)一步的拓廣了同學(xué)們的視野，使他們明白了圖與網(wǎng)絡(luò)分析在當(dāng)今科學(xué)研究的前沿中起到了多么重要的作用，從而激起他們對圖論學(xué)習(xí)的積極性。這時候我們可以誘導(dǎo)學(xué)生思考這樣一個問題：在一個無人機(jī)網(wǎng)絡(luò)中，整個網(wǎng)絡(luò)時時刻刻都不是聯(lián)通的，那么這個時候整個網(wǎng)絡(luò)還能實現(xiàn)一致性嗎？

比如整個網(wǎng)絡(luò)可能在圖3和圖4兩個網(wǎng)絡(luò)中進(jìn)行著隨機(jī)切換，這兩個網(wǎng)絡(luò)都不是聯(lián)通的，那么這個時候網(wǎng)絡(luò)能實現(xiàn)一致性嗎？

回答是肯定的。最新的研究結(jié)果表明，只要整個網(wǎng)絡(luò)是“聯(lián)合聯(lián)通”的，網(wǎng)絡(luò)就能夠?qū)崿F(xiàn)一致性[3，4]，而圖3和圖4的并就是圖1，而圖1是聯(lián)通圖，因此多智能體網(wǎng)絡(luò)在圖3和圖4之間相互切換時，整個網(wǎng)絡(luò)是可以實現(xiàn)一致性的。從而我們能夠引入一個新的概念“聯(lián)合聯(lián)通”，所謂聯(lián)合聯(lián)通是指當(dāng)整個網(wǎng)絡(luò)在若干個拓?fù)浣Y(jié)構(gòu)上切換時，如果這些拓?fù)浣Y(jié)構(gòu)的并是一個聯(lián)通網(wǎng)絡(luò)，這時候就稱隨時間演化的網(wǎng)絡(luò)是聯(lián)合聯(lián)通的。而“聯(lián)合聯(lián)通”這個概念在現(xiàn)在的大多數(shù)的運籌性的教科書中都沒有出現(xiàn)，從而能夠進(jìn)一步的擴(kuò)大學(xué)生的知識面。

4 支撐樹的概念與意義

在講到支撐樹的概念的時候我們可以先讓同學(xué)們比較兩個無人機(jī)網(wǎng)絡(luò)圖5和圖6，問問同學(xué)們，這兩個網(wǎng)絡(luò)哪個網(wǎng)絡(luò)可能更能夠節(jié)約通信成本。從而我們能夠引入樹與支撐樹的概念。使得學(xué)生能夠明白要想實現(xiàn)網(wǎng)絡(luò)一致性在聯(lián)通性的基礎(chǔ)上網(wǎng)絡(luò)還可以進(jìn)一步的簡化，即網(wǎng)絡(luò)圖只要存在支撐樹多智能體網(wǎng)絡(luò)就能夠?qū)崿F(xiàn)一致性，從而求一個聯(lián)通圖的最小生成樹就顯得尤為重要，因為對于多智能體網(wǎng)絡(luò)來說求一個聯(lián)通圖的最小支撐樹問題就是節(jié)約通信成本的問題，在當(dāng)今資源緊缺的情況下節(jié)約成本的意義是顯而易見的。

實際上，在圖論中的很多概念的講解都可以借組多智能體網(wǎng)絡(luò)，比如：度與連接矩陣的概念等，在這里就不一一敘述了。

5 結(jié)論

圖與網(wǎng)絡(luò)分析中的很多概念的講解都可以借助多智能體這個實際網(wǎng)絡(luò)，這樣做不僅能夠使問題變的通俗易懂，使學(xué)生對于概念的理解更加深刻，同時也拓廣了學(xué)生的知識面，從而極大地提高教學(xué)效果。

參考文獻(xiàn)：

[1] 錢頌迪，《運籌學(xué)》，清華大學(xué)出版社，1981.09.

[2]Georg S. Seyboth， Dimos V. Dimarogonas， Karl H. Johansson， Event based broadcasting for multi-agent average consensus， Automatica， 49：245-252，2013.

[3]Ali Jadbabaie， Jie Li， A. Stephen Morse， Coordination of groups of mobile autonomous agents using nearest neighbor rules， IEEE Transactions on Automatic Control， 48（6）：988-1000，2003.

[4]Wei Ren， Randal W. Beard， Consensus seeking in multiagent systems under dynamically changing interaction topologies， IEEE Transactions on Automatic Control， 50（5）：655-661，2005.