多智能體網絡在運籌學圖與網絡分析教學中的應用

何廣

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

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.

關鍵詞： 聯通圖；支撐樹；多智能體

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

中圖分類號：TB114.1 文獻標識碼：A 文章編號：1006-4311（2017）21-0238-02

0 引言

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

1 多智能體網絡與圖

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

2 有向圖與無向圖

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

3 連通性的概念與意義

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

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

比如整個網絡可能在圖3和圖4兩個網絡中進行著隨機切換，這兩個網絡都不是聯通的，那么這個時候網絡能實現一致性嗎？

回答是肯定的。最新的研究結果表明，只要整個網絡是“聯合聯通”的，網絡就能夠實現一致性[3，4]，而圖3和圖4的并就是圖1，而圖1是聯通圖，因此多智能體網絡在圖3和圖4之間相互切換時，整個網絡是可以實現一致性的。從而我們能夠引入一個新的概念“聯合聯通”，所謂聯合聯通是指當整個網絡在若干個拓撲結構上切換時，如果這些拓撲結構的并是一個聯通網絡，這時候就稱隨時間演化的網絡是聯合聯通的。而“聯合聯通”這個概念在現在的大多數的運籌性的教科書中都沒有出現，從而能夠進一步的擴大學生的知識面。

4 支撐樹的概念與意義

在講到支撐樹的概念的時候我們可以先讓同學們比較兩個無人機網絡圖5和圖6，問問同學們，這兩個網絡哪個網絡可能更能夠節約通信成本。從而我們能夠引入樹與支撐樹的概念。使得學生能夠明白要想實現網絡一致性在聯通性的基礎上網絡還可以進一步的簡化，即網絡圖只要存在支撐樹多智能體網絡就能夠實現一致性，從而求一個聯通圖的最小生成樹就顯得尤為重要，因為對于多智能體網絡來說求一個聯通圖的最小支撐樹問題就是節約通信成本的問題，在當今資源緊缺的情況下節約成本的意義是顯而易見的。

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

5 結論

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

參考文獻：

[1] 錢頌迪，《運籌學》，清華大學出版社，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.