商空間理論在網(wǎng)絡(luò)路徑分析中研究.pdf

1、粒計(jì)算理論之一——商空間理論，是張鈴、張鈸教授模擬人類智能解決問(wèn)題思路而提出的人工智能求解問(wèn)題的計(jì)算模型。商空間理論通過(guò)論域、屬性和結(jié)構(gòu)三元組(x，f，T)來(lái)描述問(wèn)題，通過(guò)取不同粒，從而建立不同粒度的商空間，形成的一套問(wèn)題求解的數(shù)學(xué)模型。其特色是用結(jié)構(gòu)將論域中元素間的聯(lián)系進(jìn)行了清晰描述，將論域中的復(fù)雜問(wèn)題轉(zhuǎn)化到不同粒度世界上進(jìn)行分析，在不同粒度世界之間進(jìn)行求解，對(duì)不同粒度上的解進(jìn)行合成得到原問(wèn)題的解，以達(dá)到降低問(wèn)題復(fù)雜度的效果。商空間理

2、論作為粒計(jì)算的理論方法主要討論的問(wèn)題：(1)如何選擇合適的粒——投影問(wèn)題？(2)如何在不同的粒上進(jìn)行問(wèn)題求解——推理問(wèn)題？(3)如何實(shí)現(xiàn)不同粒度空間上的解轉(zhuǎn)化到原問(wèn)題的解——粒度合成問(wèn)題？
　　 商空間理論給出了兩個(gè)標(biāo)志性的原理：保假原理和保真原理，保障了問(wèn)題(2)和(3)，對(duì)于問(wèn)題(1)只能在實(shí)際應(yīng)用中具體問(wèn)題需要具體對(duì)待。對(duì)于網(wǎng)絡(luò)路徑問(wèn)題，是圖論、人工智能領(lǐng)域的經(jīng)典問(wèn)題，其網(wǎng)絡(luò)的規(guī)模決定了其問(wèn)題的復(fù)雜度，也是路徑算法的“瓶頸

3、”，近年不少學(xué)者通過(guò)不同方式分解網(wǎng)絡(luò)規(guī)模來(lái)降低計(jì)算復(fù)雜度，實(shí)現(xiàn)網(wǎng)絡(luò)路徑搜索。本文針對(duì)網(wǎng)絡(luò)路徑問(wèn)題應(yīng)用商空間理論，應(yīng)用粒度分解方法將網(wǎng)絡(luò)路徑問(wèn)題分解到不同粒度商空間中，從不同粒度空間形成的分層遞階商空間鏈中獲取網(wǎng)絡(luò)路徑的解。對(duì)于網(wǎng)絡(luò)路徑分析，針對(duì)不同類型的網(wǎng)絡(luò)討論粒的選取問(wèn)題，提出其路徑算法，為網(wǎng)絡(luò)路徑分析提供一個(gè)商空間理論問(wèn)題求解模型。
　　 本文的主要工怍包括：
　　 1．研究商空間理論中粒的選取。
　　 在商

4、空間理論中，其取粒度方式有根據(jù)論域、屬性或結(jié)構(gòu)進(jìn)行劃分三種方法來(lái)形成商空間。商空間理論區(qū)別于其他粒計(jì)算理論，引入了結(jié)構(gòu)作為研究對(duì)象的拓?fù)湫畔ⅰ１疚挠懻摼W(wǎng)絡(luò)結(jié)構(gòu)中的粒的選取問(wèn)題，針對(duì)不同基本類型的網(wǎng)絡(luò)（無(wú)權(quán)網(wǎng)絡(luò)、加權(quán)網(wǎng)絡(luò)、有向網(wǎng)絡(luò)）的粒的選取進(jìn)行了討論。
　　 2．提出加權(quán)網(wǎng)絡(luò)的最佳路徑。
　　 針對(duì)加權(quán)網(wǎng)絡(luò)的結(jié)構(gòu)類型的路徑問(wèn)題，根據(jù)邊權(quán)的不同構(gòu)建等價(jià)關(guān)系，作為基本粒，將加權(quán)網(wǎng)絡(luò)粒度分解到不同邊權(quán)上的商空間上，形成分層遞階

5、商空間鏈，并基于分層遞階商空間鏈提出加權(quán)網(wǎng)絡(luò)的最佳路徑搜索算法。最佳路徑通過(guò)局部最優(yōu)實(shí)現(xiàn)全局最優(yōu)，逼近最短路徑。通過(guò)模擬數(shù)據(jù)實(shí)驗(yàn)驗(yàn)證其最佳路經(jīng)逼近最短路徑，并就成都市交通網(wǎng)絡(luò)的行車路線對(duì)最佳路徑和最短路徑進(jìn)行了比較，體現(xiàn)出最佳路徑的特色。
　　 3．提出基于商空間理論的最短路徑方法
　　 針對(duì)無(wú)向無(wú)權(quán)網(wǎng)絡(luò)，以極大完全子圖怍為基本粒，形成相容關(guān)系商空間，構(gòu)造出分層遞階商空間，實(shí)現(xiàn)無(wú)向無(wú)權(quán)網(wǎng)絡(luò)的最短路徑搜索。由于極大完全子圖

6、的求解具有高計(jì)算復(fù)雜度，不適合于大中型網(wǎng)絡(luò)的最短路徑求解。就一般網(wǎng)絡(luò)，基于經(jīng)典的Dijkstra和Floyd算法改進(jìn)，提出一種根據(jù)網(wǎng)絡(luò)最短路徑步數(shù)來(lái)求解網(wǎng)絡(luò)中所有最短路徑的方法。
　　 4．提出大規(guī)模網(wǎng)絡(luò)的社團(tuán)最短路徑算法。
　　 針對(duì)大規(guī)模網(wǎng)絡(luò)的網(wǎng)絡(luò)分析，其網(wǎng)絡(luò)規(guī)模是圖論路經(jīng)算法的瓶頸，本文提出以社團(tuán)為基本粒的多粒度網(wǎng)絡(luò)分解方法，將大規(guī)模網(wǎng)絡(luò)粒化為分層遞階商空間，實(shí)現(xiàn)大規(guī)模網(wǎng)絡(luò)的預(yù)處理。利用分層遞階商空間中的數(shù)據(jù)信息來(lái)

7、計(jì)算啟發(fā)式路徑搜索方法的估計(jì)函數(shù)，以實(shí)現(xiàn)大規(guī)模網(wǎng)絡(luò)的點(diǎn)對(duì)點(diǎn)最短路徑搜索。
　　 就多粒度網(wǎng)絡(luò)分解中的大規(guī)模網(wǎng)絡(luò)分割問(wèn)題，本文提出的方法是以模塊度作為評(píng)價(jià)準(zhǔn)則，以節(jié)點(diǎn)網(wǎng)絡(luò)屬性作為啟發(fā)式信息對(duì)網(wǎng)絡(luò)進(jìn)行分割，使得子圖規(guī)模相當(dāng)且具有社團(tuán)群聚特征。社團(tuán)子圖規(guī)模相當(dāng)使得經(jīng)典的圖論算法（如最小生成樹(shù)算法）充分發(fā)揮其作用。
　　 通過(guò)美國(guó)不同規(guī)模的城市交通網(wǎng)絡(luò)的實(shí)驗(yàn)，證實(shí)了以社團(tuán)為基本粒的多粒度網(wǎng)絡(luò)分解方法的實(shí)用性，并就網(wǎng)絡(luò)點(diǎn)對(duì)點(diǎn)最短路