多智慧體網路在運籌學圖與網路分析教學中的應用論文
多智慧體網路在運籌學圖與網路分析教學中的應用論文
引言
運籌學作為科學名字最早出現在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.