多智能體網(wǎng)絡(luò)在運(yùn)籌學(xué)圖與網(wǎng)絡(luò)分析教學(xué)中的應(yīng)用論文
引言
運(yùn)籌學(xué)作為科學(xué)名字最早出現(xiàn)在20世紀(jì)30年代末，那時(shí)候的運(yùn)籌學(xué)可以說就是戰(zhàn)爭的“工具”，當(dāng)時(shí)中英美借助運(yùn)籌學(xué)的思想，強(qiáng)有力的打擊了德意日三國，為二戰(zhàn)的勝利奠定了基礎(chǔ)。二戰(zhàn)勝利后運(yùn)籌學(xué)被廣泛的應(yīng)用到工農(nóng)業(yè)生產(chǎn)的各個(gè)領(lǐng)域，大大的提高了我們的生產(chǎn)效率，這也促使近幾十年運(yùn)籌學(xué)獲得了空前的發(fā)展。圖與網(wǎng)絡(luò)分析作為運(yùn)籌學(xué)的一個(gè)重要分支，現(xiàn)如今已被廣泛的應(yīng)用到物理、化學(xué)、控制論、信息論，科學(xué)管理、電子計(jì)算機(jī)等各個(gè)領(lǐng)域[1]。在實(shí)際生活、生產(chǎn)和科學(xué)研究中，有很多問題可以用圖論的理論和方法來解決。因此在運(yùn)籌學(xué)的教學(xué)中如何能夠使學(xué)生更加深刻的理解圖與網(wǎng)絡(luò)分析就顯得尤為重要。在該章節(jié)的教學(xué)中引用一些更實(shí)際的網(wǎng)絡(luò)的例子來解釋有關(guān)網(wǎng)絡(luò)的概念無疑能夠使教學(xué)更加生動(dòng)易懂。而多智能體網(wǎng)絡(luò)是近20年控制領(lǐng)域的研究熱點(diǎn)[2]，利用多智能體網(wǎng)絡(luò)來解釋圖的有關(guān)概念既能拓廣學(xué)生的視野，又能使學(xué)生更容易理解，從而調(diào)動(dòng)學(xué)生的學(xué)習(xí)積極性，進(jìn)而使得我們的教學(xué)效果得到大幅度提高。
1 多智能體網(wǎng)絡(luò)與圖
眾所周知，許多網(wǎng)絡(luò)都可以看成是多智能體網(wǎng)絡(luò)，如無人機(jī)網(wǎng)絡(luò)，移動(dòng)機(jī)器人網(wǎng)絡(luò)，那么這些網(wǎng)絡(luò)和圖有什么關(guān)系呢？當(dāng)我們把無人機(jī)抽象成頂點(diǎn)，兩架無人機(jī)之間如果有信息交流就連一條邊，這樣無人機(jī)網(wǎng)絡(luò)就可以看成一個(gè)圖，如果我們這樣去解釋圖能夠使很多同學(xué)相信原來圖真的可以包含很多復(fù)雜的內(nèi)容，圖真的可以和很多的實(shí)際問題產(chǎn)生密切的聯(lián)系，從而激起同學(xué)學(xué)習(xí)圖論的興趣。
2 有向圖與無向圖
在圖論中為什么要把圖分成有向圖和無向圖呢？他們的區(qū)別的本質(zhì)又在哪里呢？我們可以借助多智能體網(wǎng)絡(luò)跟同學(xué)們這樣解釋：在有些無人機(jī)網(wǎng)絡(luò)中信息的交流是相互的，無人機(jī)甲可以接收到向無人機(jī)已的信息，同時(shí)無人機(jī)已也可以接收到無人機(jī)甲的信息，即信息可以在這兩架無人機(jī)之間共享互通，這樣形成的圖就是無向圖；而在有些無人機(jī)網(wǎng)絡(luò)中信息交流可能是單向的`，無人機(jī)甲可以接收無人機(jī)已的信息，而無人機(jī)已卻不能接收無人機(jī)甲的信息，這樣形成的圖就是有向圖，如果我們能這樣去解釋有向圖和無向圖而不在拘泥于“單行線和雙行線”，肯定能夠使同學(xué)們對于有向圖和無向圖的理解更加深刻，也使之能夠明白為什么非要把圖分成有向圖和無向圖來進(jìn)行研究。
3 連通性的概念與意義
所謂圖的連通性是指圖中的任意兩個(gè)頂點(diǎn)都是連通的，也即是任意兩個(gè)頂點(diǎn)之間都存在一條初等鏈。而針對無人機(jī)網(wǎng)絡(luò)，所謂連通性是指任意兩個(gè)無人機(jī)即使兩者之間不能進(jìn)行直接的信息交流也能夠借助其他的無人機(jī)進(jìn)行間接的信息交流，從而實(shí)現(xiàn)信息的共享。
如圖1的無人機(jī)網(wǎng)絡(luò)就是一個(gè)聯(lián)通圖，而圖2的無人機(jī)網(wǎng)絡(luò)已就是不聯(lián)通的。對于無人機(jī)網(wǎng)絡(luò)來說連通性意味著什么呢？這意味著這個(gè)無人機(jī)網(wǎng)絡(luò)可以實(shí)現(xiàn)網(wǎng)絡(luò)一致性[3]，所謂網(wǎng)絡(luò)一致性是指網(wǎng)絡(luò)的一種集體行為，即每一個(gè)無人機(jī)的狀態(tài)（或者說行為）可以趨近于一致，而多智能體網(wǎng)絡(luò)的一致性問題是當(dāng)今控制論領(lǐng)域研究的一個(gè)熱點(diǎn)問題，這個(gè)時(shí)候?qū)W生會(huì)明白原來連通性背后隱藏著這么大的意義�。⊥瑫r(shí)也進(jìn)一步的拓廣了同學(xué)們的視野，使他們明白了圖與網(wǎng)絡(luò)分析在當(dāng)今科學(xué)研究的前沿中起到了多么重要的作用，從而激起他們對圖論學(xué)習(xí)的積極性。這時(shí)候我們可以誘導(dǎo)學(xué)生思考這樣一個(gè)問題：在一個(gè)無人機(jī)網(wǎng)絡(luò)中，整個(gè)網(wǎng)絡(luò)時(shí)時(shí)刻刻都不是聯(lián)通的，那么這個(gè)時(shí)候整個(gè)網(wǎng)絡(luò)還能實(shí)現(xiàn)一致性嗎？
比如整個(gè)網(wǎng)絡(luò)可能在圖3和圖4兩個(gè)網(wǎng)絡(luò)中進(jìn)行著隨機(jī)切換，這兩個(gè)網(wǎng)絡(luò)都不是聯(lián)通的，那么這個(gè)時(shí)候網(wǎng)絡(luò)能實(shí)現(xiàn)一致性嗎？
回答是肯定的。最新的研究結(jié)果表明，只要整個(gè)網(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之間相互切換時(shí)，整個(gè)網(wǎng)絡(luò)是可以實(shí)現(xiàn)一致性的。從而我們能夠引入一個(gè)新的概念“聯(lián)合聯(lián)通”，所謂聯(lián)合聯(lián)通是指當(dāng)整個(gè)網(wǎng)絡(luò)在若干個(gè)拓?fù)浣Y(jié)構(gòu)上切換時(shí)，如果這些拓?fù)浣Y(jié)構(gòu)的并是一個(gè)聯(lián)通網(wǎng)絡(luò)，這時(shí)候就稱隨時(shí)間演化的網(wǎng)絡(luò)是聯(lián)合聯(lián)通的。而“聯(lián)合聯(lián)通”這個(gè)概念在現(xiàn)在的大多數(shù)的運(yùn)籌性的教科書中都沒有出現(xiàn)，從而能夠進(jìn)一步的擴(kuò)大學(xué)生的知識(shí)面。
4 支撐樹的概念與意義
在講到支撐樹的概念的時(shí)候我們可以先讓同學(xué)們比較兩個(gè)無人機(jī)網(wǎng)絡(luò)圖5和圖6，問問同學(xué)們，這兩個(gè)網(wǎng)絡(luò)哪個(gè)網(wǎng)絡(luò)可能更能夠節(jié)約通信成本。從而我們能夠引入樹與支撐樹的概念。使得學(xué)生能夠明白要想實(shí)現(xiàn)網(wǎng)絡(luò)一致性在聯(lián)通性的基礎(chǔ)上網(wǎng)絡(luò)還可以進(jìn)一步的簡化，即網(wǎng)絡(luò)圖只要存在支撐樹多智能體網(wǎng)絡(luò)就能夠?qū)崿F(xiàn)一致性，從而求一個(gè)聯(lián)通圖的最小生成樹就顯得尤為重要，因?yàn)閷τ诙嘀悄荏w網(wǎng)絡(luò)來說求一個(gè)聯(lián)通圖的最小支撐樹問題就是節(jié)約通信成本的問題，在當(dāng)今資源緊缺的情況下節(jié)約成本的意義是顯而易見的。
實(shí)際上，在圖論中的很多概念的講解都可以借組多智能體網(wǎng)絡(luò)，比如：度與連接矩陣的概念等，在這里就不一一敘述了。
5 結(jié)論
圖與網(wǎng)絡(luò)分析中的很多概念的講解都可以借助多智能體這個(gè)實(shí)際網(wǎng)絡(luò)，這樣做不僅能夠使問題變的通俗易懂，使學(xué)生對于概念的理解更加深刻，同時(shí)也拓廣了學(xué)生的知識(shí)面，從而極大地提高教學(xué)效果。
參考文獻(xiàn)：
[1] 錢頌迪，《運(yùn)籌學(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.
【多智能體網(wǎng)絡(luò)在運(yùn)籌學(xué)圖與網(wǎng)絡(luò)分析教學(xué)中的應(yīng)用論文】相關(guān)文章：
網(wǎng)絡(luò)分析小論文03-31
概念圖在小學(xué)數(shù)學(xué)教學(xué)中的應(yīng)用論文06-20
運(yùn)籌學(xué)應(yīng)用課程教學(xué)改革思考論文06-21
監(jiān)控系統(tǒng)在智能樓宇中的應(yīng)用及發(fā)展論文02-03
運(yùn)籌學(xué)在系統(tǒng)工程理論中的地位及應(yīng)用教育論文07-04
多媒體通信技術(shù)在智能電網(wǎng)中的應(yīng)用論文07-09