時(shí)間：2023-02-04 21:30:32
開篇：寫作不僅是一種記錄，更是一種創(chuàng)造，它讓我們能夠捕捉那些稍縱即逝的靈感，將它們永久地定格在紙上。下面是小編精心整理的12篇遺傳算法論文，希望這些內(nèi)容能成為您創(chuàng)作過(guò)程中的良師益友，陪伴您不斷探索和進(jìn)步。
影響抄板落料特性的主要因素有:抄板的幾何尺寸a和b、圓筒半徑R、圓筒的轉(zhuǎn)速n、抄板安裝角β以及折彎抄板間的夾角θ等［4，9］。在不同的參數(shù)a、β、θ下，抄板的安裝會(huì)出現(xiàn)如圖1所示的情況。圖1描述了不同參數(shù)組合下抄板的落料特性橫截面示意圖。其中，圖1(a)與圖1(b)、圖1(c)、圖1(d)的區(qū)別在于其安裝角為鈍角。當(dāng)安裝角不為鈍角且OB與OC的夾角σ不小于OD與OC夾角ψ時(shí)(即σ≥ψ)，會(huì)出現(xiàn)圖1(b)所示的安裝情況;當(dāng)σ＜ψ時(shí)，又會(huì)出現(xiàn)圖1(c)與圖1(d)所示的情況，而兩者區(qū)別在于，η+θ是否超過(guò)180°，若不超過(guò)，則為圖1(c)情況，反之則為圖1(d)情況。其中，點(diǎn)A為抄板上物料表面與筒壁的接觸點(diǎn)或?yàn)槲锪媳砻媾c抄板橫向長(zhǎng)度b邊的交點(diǎn);點(diǎn)B為抄板的頂點(diǎn);點(diǎn)C為抄板折彎點(diǎn);點(diǎn)D為抄板邊與筒壁的交點(diǎn);點(diǎn)E為OB連線與圓筒內(nèi)壁面的交點(diǎn);點(diǎn)F為OC連線與圓筒內(nèi)壁面的交點(diǎn)。
1．1動(dòng)力學(xué)休止角(γ)［4，10］抄板上的物料表面在初始狀態(tài)時(shí)保持穩(wěn)定，直到物料表面與水平面的夾角大于物料的休止角(最大穩(wěn)定角)時(shí)才發(fā)生落料情況。隨著轉(zhuǎn)筒的轉(zhuǎn)動(dòng)，抄板上物料的坡度會(huì)一直發(fā)生改變。當(dāng)物料的坡度大于最大穩(wěn)定角時(shí)，物料開始掉落。此時(shí)，由于物料的下落，物料表面重新達(dá)到最大穩(wěn)定角開始停止掉落。然而，抄板一直隨著轉(zhuǎn)筒轉(zhuǎn)動(dòng)，使得抄板內(nèi)物料的坡度一直發(fā)生改變，物料坡度又超過(guò)最大休止角。這個(gè)過(guò)程一直持續(xù)到抄板轉(zhuǎn)動(dòng)到一定位置(即抄板位置處于最大落料角δL時(shí))，此時(shí)抄板內(nèi)的物料落空。通常，在計(jì)算抄板持有量時(shí)，會(huì)采用動(dòng)力學(xué)休止角來(lái)作為物料發(fā)生掉落的依據(jù)，即抄板內(nèi)的物料坡度超過(guò)γ時(shí)，物料開始掉落。該角主要與抄板在滾筒中的位置δ、動(dòng)摩擦因數(shù)μ和弗勞德數(shù)Fr等有關(guān)。
1．2抄板持有量的計(jì)算
隨著抄板的轉(zhuǎn)動(dòng)，一般可以將落料過(guò)程劃分為3部分(R－1，R－2，R－3)，如圖1(a)所示。在轉(zhuǎn)動(dòng)過(guò)程中，當(dāng)抄板轉(zhuǎn)角δ超過(guò)動(dòng)力學(xué)休止角γ時(shí)，落料過(guò)程從R－1區(qū)域轉(zhuǎn)變到R－2區(qū)域，在這兩個(gè)區(qū)域內(nèi)，物料不僅受到抄板的作用還受到滾筒壁面的作用。當(dāng)物料表面上的A點(diǎn)與D點(diǎn)重合時(shí)，從R－2區(qū)域轉(zhuǎn)變到R－3區(qū)域，在該區(qū)域內(nèi)，物料僅受抄板作用［4］。然而，抄板情況為圖1(c)、圖1(d)時(shí)只會(huì)經(jīng)歷R－1、R－3區(qū)域。因?yàn)樵谶\(yùn)轉(zhuǎn)過(guò)程中，抄板上物料的A點(diǎn)與D點(diǎn)重合時(shí)抄板的轉(zhuǎn)角不會(huì)超過(guò)動(dòng)力學(xué)休止角γ，所以不會(huì)經(jīng)歷R－2區(qū)域;但是，當(dāng)物料的休止角足夠小時(shí)，由于物料表面只會(huì)與抄板接觸(即A點(diǎn)不會(huì)超出D點(diǎn))，圖1(c)、圖1(d)的抄板落料過(guò)程只會(huì)經(jīng)歷R－3區(qū)域。以下根據(jù)不同的區(qū)域建立了不同組合下抄板持料量的數(shù)學(xué)模型。
2研究結(jié)果與分析
2．1最大落料角結(jié)果分析
通過(guò)MatLab編制以上推導(dǎo)公式的計(jì)算程序，模擬計(jì)算了120種不同組合(β、θ、a不同)下抄板的最大落料角。其中，物料動(dòng)摩擦因數(shù)為0．53［8］，轉(zhuǎn)筒干燥機(jī)半徑為300mm，且其抄板安裝角為10°、30°、50°、70°、90°、110°，抄板間夾角為90°、110°、130°、150°，抄板縱向長(zhǎng)度a為30、45、60、75、90mm，橫向長(zhǎng)度b為60mm。并且，根據(jù)Kelly和O＇Donnell通過(guò)驗(yàn)證得出的公式(1)只適用于Fr小于0．4的情況［4］，此次模擬的轉(zhuǎn)筒干燥機(jī)角速度為0．84rad/s。表1給出了模擬結(jié)果中較為典型的數(shù)據(jù)。從模擬結(jié)果中可以得出，當(dāng)a、θ不變時(shí)，δL隨著安裝角β的增大而增大;當(dāng)a、β不變時(shí)，δL隨著θ的增大而減小。當(dāng)抄板情況如圖1(a)、(b)、(c)時(shí)，且β、θ不變時(shí)，抄板最大落料角隨著長(zhǎng)度a的增大而增大;而圖1(d)情況則反之，并且會(huì)出現(xiàn)最大落料角小于0°的情況，這是由于抄板無(wú)法抄起物料所導(dǎo)致的結(jié)果。另外，在圖1(d)情況下，抄板的最大落料角非常小，這會(huì)使得干燥器的效率很低。因此，在探討抄板優(yōu)化問(wèn)題上，不考慮圖1(d)這種情況下的抄板。
2．2優(yōu)化目標(biāo)與結(jié)果分析
水平直徑上均勻撒料雖好，但是物料應(yīng)與熱氣均勻接觸，如果在路徑長(zhǎng)的地方撒料多些，就可以使熱效率高些。又因?yàn)閳A筒中心熱氣量比邊緣多以及在圓筒下半部分超出干燥圓的區(qū)域存在物料，所以落料均勻度考慮為物料在干燥圓橫截面積上撒料均勻。評(píng)判干燥圓橫截面積上落料均勻的具體方法如下:把干燥圓橫截面積劃分20個(gè)等分，以水平直徑為X軸，鉛垂直徑為Y軸，圓心O為原點(diǎn)，采用定積分方法求解每個(gè)劃分點(diǎn)的x坐標(biāo)，每個(gè)劃分點(diǎn)的鉛垂線與干燥圓壁面(上半部分)有一個(gè)交點(diǎn)，連接圓心與每個(gè)點(diǎn)，可以得出每條連線與X軸的夾角δi(i=1～21，步長(zhǎng)為1，δ1為0°)，如圖2所示。在合理的設(shè)計(jì)下，不僅希望落料過(guò)程中抄板在干燥圓面積上撒料越均勻越好，δL也應(yīng)越接近180°越好。因此，優(yōu)化函數(shù)為最大落料角和抄板在干燥圓而積上落料的均方差。并且，根據(jù)國(guó)內(nèi)外實(shí)際情況，抄板的安裝角一般為90°并且抄板間夾角一般不為銳角，由于機(jī)構(gòu)的限制和不考慮圖1(d)的情況，在研究抄板優(yōu)化問(wèn)題時(shí)只探討安裝角在70°～110°、抄板夾角在90°～130°以及抄板縱向長(zhǎng)度在30～90mm之間的情況。其余參數(shù)同上。采用了線性加權(quán)和法來(lái)求解此多目標(biāo)優(yōu)化結(jié)果。其中，f1為1/δL的最優(yōu)化值，f2為q的最優(yōu)化值;均方差q=(1n∑ni=1(qi－qa)2)12，每相鄰角度落料面積差qi=A(δi)－A(δi+1)，qa為面積差的平均值。當(dāng)δL≤δi+1－δi2，n=i;反之則n=i+1，且δi+1=δL。s1、s2為權(quán)重系數(shù)，由于干燥器的效率主要與抄板的撒料均勻有關(guān)，但是如果落料角很小、撒料很均勻，干燥器效率也不高，綜合考慮下，取s1、s2分別為0．4、0．6。通過(guò)編寫MatLab程序，確定優(yōu)化函數(shù)，然后采用MatLab遺傳算法工具箱進(jìn)行計(jì)算，設(shè)置相關(guān)參數(shù):最大代數(shù)為51，種群規(guī)模為20，交叉概率為0．2，選擇概率為0．5。運(yùn)行算法并顯示結(jié)果，β、θ、a較優(yōu)結(jié)果分別為:1．844rad、1．571rad、51．609mm。
3結(jié)論
關(guān)鍵詞:量子遺傳算法;多目標(biāo)分配;最優(yōu)化
中圖分類號(hào):TP18 文獻(xiàn)標(biāo)識(shí)碼:A 文章編號(hào):1674-7712 (2012) 12-0176-01
一、引言
遺傳算法不同于傳統(tǒng)尋優(yōu)算法的特點(diǎn)在于:遺傳算法在尋優(yōu)過(guò)程中,僅需要得到適應(yīng)度函數(shù)的值作為尋優(yōu)的依據(jù);同時(shí)使用概率性的變換規(guī)則,而不是確定性的變換規(guī)則;遺傳算法適應(yīng)度函數(shù)的計(jì)算相對(duì)于尋優(yōu)過(guò)程是獨(dú)立的;算法面對(duì)的是參數(shù)的編碼集合,而并非參數(shù)集合本身,通用性強(qiáng)。它尤其適用于處理傳統(tǒng)優(yōu)化算法難于解決的復(fù)雜和非線性問(wèn)題。[1]
目前,GA已經(jīng)在很多領(lǐng)域得到成功應(yīng)用,但隨著問(wèn)題規(guī)模的不斷擴(kuò)大和搜索空間的更加復(fù)雜,GA在求解很多具體問(wèn)題時(shí)往往并不能表現(xiàn)出其優(yōu)越性。于是,近年來(lái)便出現(xiàn)了遺傳算法與其它理論相結(jié)合的實(shí)踐,其中遺傳算法與量子理論的結(jié)合是一個(gè)嶄新的、極富前景和創(chuàng)意的嘗試。
量子遺傳算法QGA是量子計(jì)算特性與遺傳算法相結(jié)合的產(chǎn)物。基于量子比特的疊加性和相干性,在遺傳算法中借鑒量子比特的概念,引入了量子比特染色體。由于量子比特染色體能夠表征疊加態(tài),比傳統(tǒng)GA具有更好的種群多樣性,同時(shí)QGA也會(huì)具有更好的收斂性,因此在求解優(yōu)化問(wèn)題時(shí),QGA在收斂速度、尋優(yōu)能力方面比GA都將有較大的提高。QGA的出現(xiàn)結(jié)合了量子計(jì)算和遺傳算法各自的優(yōu)勢(shì),具有很高的理論價(jià)值和發(fā)展?jié)摿Α?/p>
本論文提出用量子遺傳算法處理和解決多目標(biāo)分配問(wèn)題,為多目標(biāo)問(wèn)題的解決提供一種新的思路。
二、量子遺傳算法
在傳統(tǒng)計(jì)算機(jī)中,信息存儲(chǔ)是以二進(jìn)制來(lái)表示,不是“0”就是“1”態(tài),但是在量子計(jì)算機(jī)中,充當(dāng)信息存儲(chǔ)單元的物質(zhì)是一個(gè)雙態(tài)量子系統(tǒng),稱為量子比特(qubit),量子比特與比特不同之就在于它可以同時(shí)處在兩個(gè)量子態(tài)的疊加態(tài),量子進(jìn)化算法建立在量子的態(tài)矢量表述基礎(chǔ)上,將量子比幾率幅表示應(yīng)用于染色體的編碼,使得一條染色體可以表示個(gè)態(tài)的疊加,并利用量子旋轉(zhuǎn)門更新染色體,從而使個(gè)體進(jìn)達(dá)到優(yōu)化目標(biāo)的目的。
一個(gè) 位的量子位染色體就是一個(gè)量子位串,其表示如下:
其中 。在多目標(biāo)優(yōu)化中,一個(gè)量子染色體代表一個(gè)決策向量,在量子態(tài)中一個(gè) 位的量子染色體可以表達(dá) 個(gè)態(tài),采用這種編碼方式使得一個(gè)染色體可以同時(shí)表達(dá)多個(gè)態(tài)的疊加,使得量子進(jìn)化算法比傳統(tǒng)遺傳算法擁有更好的多樣性特征。
為了實(shí)現(xiàn)個(gè)體的進(jìn)化,經(jīng)典進(jìn)化算法中通過(guò)染色體的交叉、變異操作推進(jìn)種群的演化,而對(duì)量子進(jìn)化算法而言,量子染色體的調(diào)整主要是通過(guò)量子旋轉(zhuǎn)門實(shí)現(xiàn)的,算法流程如下:
(1)進(jìn)化代數(shù)初始化: ;
(2)初始化種群 ,生成并評(píng)價(jià) ;
(3)保存 中的最優(yōu)解 ;
(4) ;
(5)由 生成 ;
(6)個(gè)體交叉、變異等操作,生成新的 (此步可省評(píng)價(jià));
(7)評(píng)價(jià) ,得到當(dāng)前代的最優(yōu)解 ;
(8)比較 與 得到量子概率門 ,保存最優(yōu)解于 ;
(9)停機(jī)條件 當(dāng)滿足停機(jī)條件時(shí),輸出當(dāng)前最優(yōu)個(gè)體,算法結(jié)束,否則繼續(xù);
(10)以 更新 ,轉(zhuǎn)到4)。
三、基于量子遺傳算法的多目標(biāo)分配應(yīng)用
如今為了滿足市場(chǎng)的需要,很多工廠的生產(chǎn)種類多、生產(chǎn)量大,從而設(shè)置了不同的生產(chǎn)車間,根據(jù)產(chǎn)品的性質(zhì)分配生產(chǎn)車間合理與否直接影響工廠的經(jīng)濟(jì)收益,這同樣可采用遺傳算法的目標(biāo)分配方法進(jìn)行分配。
模型構(gòu)建:設(shè)工廠有i個(gè)生產(chǎn)車間。 為在第i個(gè)車間生產(chǎn)第j種產(chǎn)品的收益, 為第j種產(chǎn)品的需求量;如果第j種產(chǎn)品被選中,則 為在第i個(gè)車間生產(chǎn)該產(chǎn)品的總收益。由題意知為求解 最大問(wèn)題。
仿真實(shí)例:設(shè)有10個(gè)生產(chǎn)車間,要生產(chǎn)15種產(chǎn)品,用Matlab程序編程,設(shè)定40個(gè)粒子,迭代200次,代溝0.9。運(yùn)行結(jié)果如下:
此圖表明經(jīng)200次迭代后的目標(biāo)分配方案為:第1種產(chǎn)品由第3個(gè)車間生產(chǎn),以此類推,車間5生產(chǎn)第2種產(chǎn)品,車間8生產(chǎn)第3種產(chǎn)品,……。次方案對(duì)應(yīng)的車間總收益值為2.7030e+003,成功進(jìn)行了多目標(biāo)分配問(wèn)題的解決。
四、結(jié)論
基于量子遺傳算法的多目標(biāo)分配,為多目標(biāo)分配突破傳統(tǒng)尋優(yōu)模式找到了一個(gè)可行的解決方法。根據(jù)這種方法實(shí)驗(yàn),仿真結(jié)果可以看出,基本符合要求,并且能夠在一定的時(shí)間內(nèi)得到最優(yōu)的分配方案,因此,本文在探索多目標(biāo)分配問(wèn)題上找到了一種新的解決思路。
參考文獻(xiàn):
[1]吉根林.遺傳算法研究綜述[J].計(jì)算機(jī)應(yīng)用與軟件,2004,21(2):69-73
[2]肖曉偉,肖迪.多目標(biāo)優(yōu)化問(wèn)題的研究概述[J].計(jì)算機(jī)應(yīng)用研究,2011,3,28(3):805-808
[3]原銀忠,韓傳久.用遺傳算法實(shí)現(xiàn)防空導(dǎo)彈體系的目標(biāo)分配[J].火力與指揮控制,2008,3,33(3):80-83
[關(guān)鍵詞] 配送 車輛路徑問(wèn)題 時(shí)間窗 遺傳算法
隨著經(jīng)濟(jì)全球化趨勢(shì)的加強(qiáng)，科學(xué)技術(shù)尤其是信息技術(shù)的發(fā)展突飛猛進(jìn)，產(chǎn)品營(yíng)銷范圍日趨擴(kuò)大，社會(huì)生產(chǎn)、物資流通、商品交易及其管理方式正在發(fā)生著深刻的變革，與此相適應(yīng)，被普遍認(rèn)為企業(yè)在降低物資消耗、提高勞動(dòng)生產(chǎn)率以外的“第三利潤(rùn)源”的現(xiàn)代物流在世界范圍內(nèi)廣泛興起，目前正在成為全球經(jīng)濟(jì)發(fā)展的一個(gè)重要熱點(diǎn)和新的經(jīng)濟(jì)增長(zhǎng)點(diǎn)。隨著傳統(tǒng)批發(fā)、交通運(yùn)輸、倉(cāng)儲(chǔ)業(yè)向現(xiàn)代物流轉(zhuǎn)化，尤其是配送方式的采用，對(duì)運(yùn)輸成本和時(shí)間的有效控制日漸成為城市配送車輛路徑問(wèn)題的一項(xiàng)重要目標(biāo)。VRP一直以來(lái)都是車輛調(diào)度所重點(diǎn)研究的方向。而在城市內(nèi)采取的配送方式恰恰具備了VRP問(wèn)題的一般特征和優(yōu)化調(diào)度條件。
一、VRP模型的條件及假設(shè)
VRP問(wèn)題是指按要求用多個(gè)車輛從配送中心對(duì)顧客進(jìn)行配給貨物。各顧客點(diǎn)的位置和需求量為己知，各車輛的裝載質(zhì)量己知，力求尋找一個(gè)好的配送方案，使得總代價(jià)最小(車輛盡量少，行車總距離盡量短，總費(fèi)用盡量低等)，由VRP的定義不難看出，必須滿足以下條件及假設(shè)：
1.僅考慮位置已知的單一配送中心，所有的配送車輛以配送中心為起點(diǎn)，并最終回到配送中心。
2.每條配送路徑上各需求點(diǎn)的需求量之和不超過(guò)車輛的裝載質(zhì)量，被配送貨物是可混裝的貨物。
3.每條配送路徑的長(zhǎng)度不超過(guò)車輛一次允許行駛的最大距離，配送中心有足夠的資源以供配送，并且有足夠的運(yùn)輸能力。
4.各個(gè)客戶需求和所在地均已知，每個(gè)需求點(diǎn)的需求由且僅由一輛車一次送貨滿足。
5.滿足總時(shí)間約束與時(shí)間窗口。必須在時(shí)間區(qū)間[ei,lj]訪問(wèn)點(diǎn)i客戶，并允許在i處等待，車輛服務(wù)的總時(shí)間不能超過(guò)物流中心的時(shí)間約束。
6.多個(gè)客戶之間存在優(yōu)先關(guān)系，必須在訪問(wèn)客戶j之前訪問(wèn)客戶i。
二、帶時(shí)間窗VRP模型的建立
基于文獻(xiàn)一文中的模型，并考慮配送系統(tǒng)是一個(gè)服務(wù)系統(tǒng)，所提供的服務(wù)必須能夠讓客戶方便、滿意。配送系統(tǒng)的運(yùn)作成本必須和配送系統(tǒng)其他性能參數(shù)綜合進(jìn)行考評(píng)，單純對(duì)成本進(jìn)行評(píng)價(jià)是沒(méi)有任何實(shí)際意義的。需要關(guān)注和努力的是：要在保證配送滿足客戶要求、提升客戶滿意度的同時(shí)，通過(guò)各種技術(shù)和管理手段，降低運(yùn)作成本。因此，本文將建立改進(jìn)的運(yùn)輸路徑模型，在傳統(tǒng)的車輛配送成本最小化目標(biāo)的基礎(chǔ)上，兼顧客戶對(duì)配送時(shí)間的要求，使車輛等待和延誤時(shí)間之和最小化。
（1）
（2）
式中K――車隊(duì)規(guī)模，即總的車輛數(shù)目；
k――車輛數(shù)目(k=1,2,……,K)；
N――有待訪問(wèn)的總的客戶的數(shù)目；
O――配送中心；
Q――每輛車輛的容量，這里假設(shè)所有車輛同質(zhì)，容量均為Q;
i,j――顧客數(shù)(i=1,2,……,N；j=1,2,……,N)；
T――個(gè)很大的數(shù)字；
C――每輛車單位運(yùn)距的運(yùn)費(fèi)；
t0――車輛從配送中心出發(fā)的時(shí)間；
e0――車輛可離開配送中心的最早時(shí)間；
ei――到達(dá)客戶i處規(guī)定最早到達(dá)時(shí)間；
l0――車輛返回配送中心的最晚時(shí)間；
li――到達(dá)客戶i處規(guī)定最晚到達(dá)時(shí)間；
dij――從客戶i到客戶j的距離；
pj――每個(gè)客戶單位卸貨量的卸載費(fèi)用；
mi――客戶i的貨運(yùn)需求量；
tki、tkj――第k輛車到達(dá)客戶i、j處的時(shí)間；
tij――連接客戶i和客戶j的行駛時(shí)間；
si――客戶i處的服務(wù)時(shí)間；
wi――在客戶i的等待時(shí)間，wi≥0。
兩個(gè)決策變量如下：
這個(gè)模型通用性很強(qiáng)，經(jīng)過(guò)參數(shù)的不同設(shè)定，可以轉(zhuǎn)換為其它組合優(yōu)化問(wèn)題的數(shù)學(xué)模型。
三、帶時(shí)間窗VRP模型的遺傳算法求解
在模型的處理上，根據(jù)本文提出的模型單位標(biāo)量不統(tǒng)一的特殊性來(lái)選擇權(quán)重系數(shù)變化法，將變化后的多目標(biāo)函數(shù)經(jīng)分析和試驗(yàn)得出各個(gè)子目標(biāo)函數(shù)的數(shù)量級(jí)大小并確定權(quán)重，最后加權(quán)化為單目標(biāo)函數(shù)用遺傳算法求解。
1.懲罰函數(shù)的引入。在以往的對(duì)含有時(shí)間窗約束的車輛配送系統(tǒng)的研究中，所研究的成本大多僅包含行駛成本，但事實(shí)上，還包括其它成本(如裝卸搬運(yùn)成本)，將時(shí)間窗約束轉(zhuǎn)化為懲罰函數(shù)而體現(xiàn)在模型中。
式中c1――車輛在任務(wù)點(diǎn)處等待單位時(shí)間的機(jī)會(huì)成本。
c2――車輛在要求時(shí)間之后到達(dá)單位時(shí)間所處以的懲罰值(c1和c2的大小，要根據(jù)實(shí)際情況來(lái)定)。
2.建立適度度函數(shù)。根據(jù)遺傳算法中適應(yīng)度函數(shù)的特點(diǎn)，需要將原目標(biāo)函數(shù)式變化為：
(4)
(5)
式中A*，B* ――變化后的目標(biāo)函數(shù)值，取值范圍為[0，1)；
Amax,Bmax――分別是原始目標(biāo)函數(shù)。
適應(yīng)度函數(shù)因此變化為：f(A,B)=α×A*+β×B*(6)
經(jīng)過(guò)分析和實(shí)驗(yàn)發(fā)現(xiàn)，A*，B*經(jīng)過(guò)處理后，A*的數(shù)量級(jí)一般是10-2，B＊的數(shù)量級(jí)一般是10-1。
3.用遺傳算法求解帶時(shí)間窗VRP模型。本文取α＝0.8,β＝0.2，用遺傳算法進(jìn)行求解。在運(yùn)用遺傳算法求解后，驗(yàn)證了該算法易于理解，對(duì)問(wèn)題的依賴性較小，對(duì)其求解的函數(shù)要求簡(jiǎn)單，實(shí)現(xiàn)起來(lái)簡(jiǎn)單高效，若參數(shù)選擇的合理，收斂速度很快，但是遺傳參數(shù)的控制對(duì)于算法的收斂速度影響很大，在參數(shù)選擇方面有一定難度。雖然文中使用的是根據(jù)以往學(xué)者經(jīng)驗(yàn)選定的參數(shù)，但計(jì)算表明最優(yōu)解所在“代”數(shù)的穩(wěn)定性不是很好，這也是以后需要進(jìn)一步研究的地方。
四、結(jié)論
在傳統(tǒng)的車輛配送成本最小化為目標(biāo)的基礎(chǔ)上，兼顧客戶對(duì)配送時(shí)間的要求，建立了帶時(shí)間窗的車輛路徑優(yōu)化多目標(biāo)模型。在對(duì)模型的處理上，將兩個(gè)量綱不統(tǒng)一的子目標(biāo)函數(shù)除以各子目標(biāo)函數(shù)的最大值后使其變成無(wú)量綱的函數(shù)，并通過(guò)權(quán)重系數(shù)變化法將各個(gè)子目標(biāo)函數(shù)線性加權(quán)和作為多目標(biāo)優(yōu)化問(wèn)題的適應(yīng)度函數(shù)，使得多目標(biāo)優(yōu)化問(wèn)題轉(zhuǎn)化為單目標(biāo)優(yōu)化問(wèn)題后再用遺傳算法求解。
參考文獻(xiàn):
[1]王 惠:引入顧客滿意度求解車輛優(yōu)化調(diào)度問(wèn)題.大連海事大學(xué)碩士論文,2006:1～13
[2]盛麗俊:帶有時(shí)間窗的車輛路徑問(wèn)題的優(yōu)化研究.大連海事大學(xué)碩士論文,2002:13～57
[3]牟燕妮:物流配送中路徑優(yōu)化的選擇研究.沈陽(yáng)工業(yè)大學(xué)碩士論文,2006:28～41
關(guān)鍵詞：遺傳算法；運(yùn)籌學(xué)；應(yīng)用
中圖分類號(hào)：F27 文獻(xiàn)標(biāo)識(shí)碼：A
收錄日期：2011年10月28日
一、遺傳算法簡(jiǎn)介
遺傳算法（GAS）是由美國(guó)密執(zhí)根大學(xué)的Holland等人創(chuàng)立的。與其他啟發(fā)式方法順序搜索解空間的工作方式不同，遺傳算法采用解的種群作為工作單元，使用模仿生物進(jìn)化的適者生存原則指導(dǎo)搜索并改進(jìn)目標(biāo)。種群由代表個(gè)體的定長(zhǎng)字符串組成，每個(gè)個(gè)體表示解空間的一個(gè)點(diǎn)，每個(gè)解的質(zhì)量，通過(guò)依賴于問(wèn)題目標(biāo)函數(shù)的適應(yīng)值函數(shù)來(lái)進(jìn)行評(píng)估。搜索過(guò)程通過(guò)進(jìn)化來(lái)進(jìn)行，每代中的個(gè)體以正比于它的適應(yīng)值的概率遺傳到下一代。它使用3個(gè)基本算子：選擇、交叉和變異。選擇是指?jìng)€(gè)體以其適應(yīng)值比例復(fù)制到池中；交叉是池中的兩個(gè)個(gè)體進(jìn)行，組合形成一個(gè)（或幾個(gè)）新個(gè)體，復(fù)制和交叉將好的特性進(jìn)行遺傳；變異則是發(fā)生在少數(shù)字符串某基因位上的基因的突變，它使搜索過(guò)程能夠有機(jī)會(huì)從搜索到的局部最優(yōu)解逃出。
解決一個(gè)實(shí)際問(wèn)題的遺傳算法通常包括下列兩個(gè)決策步驟：（1）將求解問(wèn)題模型化為符合遺傳算法的框架。可行解空間的定義，適應(yīng)值函數(shù)的表現(xiàn)形式，解的字符串表達(dá)式方式；（2）遺傳算法參數(shù)的設(shè)計(jì)。種群規(guī)模，復(fù)制、交叉、變異的概率選擇，進(jìn)化最大代數(shù)，終止準(zhǔn)則設(shè)定等。
二、遺傳算法的基本特點(diǎn)
（一）結(jié)構(gòu)特點(diǎn)。遺傳算法是以適應(yīng)值提供的啟發(fā)式信息進(jìn)行搜索的，與其他啟發(fā)式（模擬退火、爬山法、神經(jīng)網(wǎng)絡(luò)等）方法相比，在結(jié)構(gòu)和工作過(guò)程方面的特點(diǎn)見表1。（表1）
（二）實(shí)驗(yàn)性能方面的特點(diǎn)
1、高效性。遺傳算法具有大范圍全局搜索的特點(diǎn)，與問(wèn)題領(lǐng)域無(wú)關(guān)，前期工作量比較少。
2、健壯性。遺傳算法的搜索是用種群作為基本單元，采用三個(gè)不同作用的基本算子進(jìn)行搜索的，解的結(jié)果隨時(shí)間增加而趨于穩(wěn)定，不受初始解的影響，而且不因?qū)嵗牟煌懽儭?/p>
3、通用性和靈活性。遺傳算法可用于多種優(yōu)化搜索問(wèn)題，解題程序可以通用，針對(duì)不同的實(shí)例，適當(dāng)調(diào)整算子參數(shù)，就可以使算法執(zhí)行獲得最佳的解結(jié)果和占用CPU機(jī)時(shí)的關(guān)系。
三、遺傳算法在解決經(jīng)典運(yùn)籌問(wèn)題中的應(yīng)用
（一）旅行商問(wèn)題（TSP）。旅行商問(wèn)題自誕生以來(lái)，頗受數(shù)學(xué)家推崇，今天的旅行商問(wèn)題已遠(yuǎn)遠(yuǎn)超過(guò)其本身的含義，成為一種衡量算法優(yōu)劣的標(biāo)準(zhǔn)。旅行商問(wèn)題是采用非標(biāo)準(zhǔn)編碼遺傳算法求解最成功的一例，基因編碼用推銷員順序經(jīng)歷的城市名表示，求最佳路線即是改變編碼次序而求最低適應(yīng)值的問(wèn)題。對(duì)類似字符串使用標(biāo)準(zhǔn)交叉，產(chǎn)生的后代可能有重復(fù)或丟失的元素，因而成為非可行解。為克服這種困難，人們提出許多非標(biāo)準(zhǔn)的交叉和變異方法：交叉主要采用重排序方法――部分匹配重排序，順序交叉和循環(huán)交叉等；變異主要采用位點(diǎn)、反轉(zhuǎn)、對(duì)換、插入等方法，使旅行商問(wèn)題得以有效地解決。值得一提的是，清華大學(xué)張雷博士提出的自適應(yīng)多點(diǎn)交叉算子，能夠保證多點(diǎn)交叉后路徑的可行性，加快了搜索速度。
（二）作業(yè)調(diào)度問(wèn)題。作業(yè)調(diào)度問(wèn)題同樣是自然變更次序的問(wèn)題，可以用基于變更次序的遺傳算法進(jìn)行處理。（表2）
（三）背包問(wèn)題。一維、二維和三維背包問(wèn)題在商業(yè)和工業(yè)領(lǐng)域有著廣泛的應(yīng)用，基于遺傳算法的求解方法很多。傳統(tǒng)求解采用啟發(fā)式規(guī)則，決定下一步該裝哪一塊和裝在哪里，此時(shí)變更次序的編碼與啟發(fā)式安置策略是利用遺傳算法解決這類問(wèn)題的最為出色的方法，Lin使用一系列的懲罰項(xiàng)指導(dǎo)其搜索策略，測(cè)定單個(gè)個(gè)體的適應(yīng)值。
Bortfeldt使用一個(gè)層次背包問(wèn)題，個(gè)體用它們的層次代表，當(dāng)兩個(gè)親代被選擇交叉時(shí)，它們的層次混在一起，從中選擇最好的作為子代的第一層，再?gòu)挠嘞碌慕M件中選擇最好的作為第二層，以此類推，直至產(chǎn)生所有的層次。
陳國(guó)良等設(shè)計(jì)了一種“與/或”交叉方法，使子代繼承雙親的同型基因，對(duì)雜型基因采用不同支配方式，這種策略為遺傳算法的硬件實(shí)現(xiàn)創(chuàng)造了良好的條件。
（四）時(shí)刻表排定問(wèn)題。Corne對(duì)Edinburgh大學(xué)7日內(nèi)的28個(gè)時(shí)間期間安排40門課的考試問(wèn)題作了處理，尋找一個(gè)可行的時(shí)間排定表，使每個(gè)學(xué)生參加的考試在時(shí)間上能夠錯(cuò)開，時(shí)刻表用字符串代表，字符串每個(gè)位置代表一門課，該位置的值代表考試的時(shí)間，用均勻交叉和標(biāo)準(zhǔn)變異操作求解。
這類問(wèn)題擴(kuò)展到基于二維的矩陣代表的逼近問(wèn)題，Colorini使用行代表教師列代表可用的小時(shí)數(shù)的矩陣，每個(gè)單元的值為教師在此時(shí)承擔(dān)的任務(wù)，包括教室和其他一些資源配置，教師的任務(wù)是事先給定的，故行都是可行的，列代表的時(shí)間安排可能會(huì)發(fā)生沖突，將此沖突用懲罰函數(shù)表示在適應(yīng)值函數(shù)中，而且采用修復(fù)算子在評(píng)價(jià)之前盡量將結(jié)論調(diào)整回可行區(qū)域內(nèi)，該算法用Milan學(xué)校的實(shí)際數(shù)據(jù)進(jìn)行了檢驗(yàn)。
除此之外，遺傳算法在運(yùn)輸問(wèn)題、指派問(wèn)題、分割問(wèn)題及網(wǎng)絡(luò)計(jì)劃優(yōu)化問(wèn)題等方面都獲得了非常成功的應(yīng)用，這些問(wèn)題被認(rèn)為是NP類問(wèn)題，其規(guī)模隨變量的增加呈指數(shù)增長(zhǎng)，遺傳算法在這些問(wèn)題的求解中，充分體現(xiàn)了其操作性能方面的優(yōu)勢(shì)。
四、應(yīng)用和推廣中存在的問(wèn)題
在上述問(wèn)題中，遺傳算法求解展示了優(yōu)良的性能，但遺傳算法并未像其他啟發(fā)式方法那樣容易地被OR學(xué)者廣泛接受而用于大量的實(shí)際問(wèn)題中，究其原因，主要有以下幾點(diǎn)：
（一）傳播方式的障礙。遺傳算法最初的工作是以密執(zhí)根大學(xué)嚴(yán)謹(jǐn)?shù)难芯啃〗M作為研究項(xiàng)目和學(xué)術(shù)討論中心，當(dāng)研究成員擴(kuò)大時(shí)，這類討論會(huì)演變?yōu)闄C(jī)構(gòu)的學(xué)術(shù)會(huì)議（美國(guó)現(xiàn)有5個(gè)，歐洲有3個(gè)，我國(guó)目前還沒(méi)有），許多研究者聚于此而遠(yuǎn)離問(wèn)題導(dǎo)向，有關(guān)的會(huì)議論文公開出版數(shù)量很少，而且，由于歷史原因，研究者常常將他們的研究結(jié)果選擇在有關(guān)人工智能的雜志上發(fā)表，導(dǎo)致了應(yīng)用遺傳算法的信息很緩慢地?cái)U(kuò)散到其他不同技術(shù)應(yīng)用領(lǐng)域的工作者中，這與模擬退火等其他啟發(fā)式方法快速在運(yùn)籌學(xué)會(huì)議及雜志上發(fā)表相反。由于缺乏交流導(dǎo)致了兩方面的問(wèn)題：一是許多關(guān)于遺傳算法的論文不能與從其他方法得到的結(jié)論進(jìn)行質(zhì)量的比較，二是削弱了許多遺傳算法多的潛在使用者用遺傳算法與其他方法競(jìng)爭(zhēng)的信心。
（二）術(shù)語(yǔ)的隔膜。初始跨入遺傳算法領(lǐng)域的使用者常常感到起步非常艱難，遺傳算法依賴于遺傳學(xué)的術(shù)語(yǔ)也像模擬退火的術(shù)語(yǔ)來(lái)自于統(tǒng)計(jì)熱力學(xué)一樣。然而，溫度、冷卻等可能很快賦予新的意義，但遺傳算法中的基因位、染色體、遺傳型卻難以很快被人理解和接受；另外，許多發(fā)表的研究偏重于用某些專門函數(shù)檢驗(yàn)他們的新思路或新設(shè)想，這對(duì)于全面理解該技術(shù)固然是一件好事，但對(duì)于一個(gè)面對(duì)如此豐富復(fù)雜材料的初用者會(huì)發(fā)現(xiàn)，他將不知從何做起。即使一個(gè)非常愿意使用遺傳算法的人，也要有足夠的決心去克服上述障礙。
（三）方法的局限性。對(duì)于具有強(qiáng)約束的優(yōu)化問(wèn)題，采用懲罰函數(shù)逼近常常達(dá)不到預(yù)想的結(jié)果。Radcliffe評(píng)論說(shuō)：“約束通常被認(rèn)為是遺傳算法面臨的最大問(wèn)題”因?yàn)閼土P因子選擇不當(dāng)時(shí)，會(huì)招致錯(cuò)誤結(jié)論。目前，求解帶約束優(yōu)化問(wèn)題的啟發(fā)式遺傳方法已經(jīng)有了一些，但是，它們多數(shù)與問(wèn)題領(lǐng)域相關(guān)，在這方面還缺少普遍適用的方法的系統(tǒng)研究。
（四）編碼的困難。不是所有問(wèn)題解空間中的點(diǎn)都能明顯地用編碼表示，作為OR研究者，常常從問(wèn)題結(jié)構(gòu)取得利益，用矩陣、樹、網(wǎng)絡(luò)或其他更適用的方法建立表達(dá)式；串表達(dá)中的建筑塊假說(shuō)建議適用較少的字符，導(dǎo)致人們對(duì)二進(jìn)制編碼的偏愛(ài)，但二進(jìn)制編碼具有一定的映射誤差（實(shí)際計(jì)算時(shí)，我們是把問(wèn)題作為整數(shù)規(guī)劃），特別是它不能直接反映出所求問(wèn)題本身結(jié)構(gòu)特征，因此很難滿足生成有意義的積木塊編碼原則；再者，二進(jìn)制字符的長(zhǎng)度隨問(wèn)題發(fā)生明顯變化，當(dāng)問(wèn)題復(fù)雜時(shí)會(huì)因?yàn)榫幋a太長(zhǎng)而無(wú)法進(jìn)行正常工作。
以上的種種阻力，在一定程度上減緩了遺傳算法在運(yùn)籌學(xué)實(shí)際問(wèn)題中的推廣和應(yīng)用。
主要參考文獻(xiàn)：
[1]陳國(guó)良等.遺傳算法及其應(yīng)用.北京：人民郵電出版社，1996.6.
關(guān)鍵詞：電網(wǎng)規(guī)劃；地理信息系統(tǒng)（GIS）；遺傳算法；現(xiàn)代啟發(fā)式方法
0 引言
電網(wǎng)規(guī)劃是電力系統(tǒng)規(guī)劃的重要環(huán)節(jié)[1]，電網(wǎng)規(guī)劃方案的優(yōu)劣直接影響到電網(wǎng)的建設(shè)費(fèi)用以及運(yùn)行費(fèi)用。傳統(tǒng)的規(guī)劃很難對(duì)地理實(shí)體進(jìn)行數(shù)據(jù)采集，規(guī)劃模型往往也忽略地表因素（障礙物等）的影響，所以精度較低，規(guī)劃結(jié)果往往不具備實(shí)用性和可操作性，此外傳統(tǒng)的規(guī)劃很難實(shí)現(xiàn)可視化，缺乏直觀性。結(jié)合GIS 平臺(tái)，對(duì)電網(wǎng)規(guī)劃問(wèn)題進(jìn)行優(yōu)化，既可以方便的把地貌因素運(yùn)用到電網(wǎng)規(guī)劃中，又使規(guī)劃結(jié)果直觀可視，從而大大提高了結(jié)果的科學(xué)性和實(shí)用性。
1 基于GIS平臺(tái)電網(wǎng)規(guī)劃的特點(diǎn)
在電網(wǎng)規(guī)劃中引入GIS系統(tǒng)有如下特點(diǎn)：
（1）電網(wǎng)規(guī)劃要求大量詳細(xì)的地理信息，如變電站位置、變壓器位置等。借用GIS平臺(tái)可以使規(guī)劃區(qū)域的整個(gè)電網(wǎng)直觀地顯示在屏幕上，規(guī)劃人員能夠方便地確定待選變電站和待選線路路徑。
（2）把GIS引入電網(wǎng)規(guī)劃中，用戶可以考慮許多實(shí)際的約束條件，如地理位置、街道等的互連關(guān)系、街區(qū)布局等等，而且由于空間數(shù)據(jù)模型的引入，這些約束條件對(duì)用戶是透明的，可以直接從地圖上獲得，建模工作將得到簡(jiǎn)化。
（3）結(jié)合GIS的電網(wǎng)提供了從文-圖和從圖-文的雙向查詢，不但能通過(guò)系統(tǒng)開發(fā)的查詢工具對(duì)任意點(diǎn)取圖上目標(biāo)進(jìn)行所見即所得的查詢，而且可以對(duì)電網(wǎng)圖層空間的每一層設(shè)置其顯示范圍、是否可視等屬性[2]～[4]。
2、基于GIS平臺(tái)的電網(wǎng)規(guī)劃方法
電網(wǎng)規(guī)劃分為經(jīng)典方法和現(xiàn)代啟發(fā)式方法，傳統(tǒng)的經(jīng)典方法能夠得到解析解，在理論上能使得規(guī)劃結(jié)果相對(duì)最優(yōu)，但對(duì)問(wèn)題的規(guī)模、約束條件的數(shù)量、問(wèn)題的組合度比較敏感，容易陷入“維數(shù)災(zāi)”而難以在合理時(shí)間內(nèi)求得結(jié)果。近幾年出現(xiàn)的基于生物學(xué)、人工智能的現(xiàn)代啟發(fā)式算法具有直觀、靈活、計(jì)算速度快、不受限于問(wèn)題規(guī)模等特點(diǎn)，不僅遵循配網(wǎng)規(guī)劃常用規(guī)則，而且便于規(guī)劃人員應(yīng)用過(guò)去的經(jīng)驗(yàn)，在配網(wǎng)規(guī)劃中能很快得到近似最優(yōu)解。由于現(xiàn)代啟發(fā)式方法優(yōu)勢(shì)明顯，所以傳統(tǒng)的經(jīng)典方法已經(jīng)很少使用。
2.1 Tabu 搜索算法
Tabu 搜索方法是一種亞啟發(fā)式隨機(jī)搜索算法，它從一個(gè)初始可行解X0（為n維向量）出發(fā)，選擇一系列的特定搜索方向（移動(dòng)）作為試探，從當(dāng)前解的鄰域N（X）中隨機(jī)產(chǎn)生一系列試驗(yàn)解X1，X2，… XK選擇其中最好的解X*作為當(dāng)前解，即令Xcurrent=X*，重復(fù)迭代，直到滿足一定的終止準(zhǔn)則。
文獻(xiàn)[5]運(yùn)用Tabu 搜索算法，在GIS平臺(tái)上對(duì)網(wǎng)架模型進(jìn)行優(yōu)化。目標(biāo)函數(shù)是年費(fèi)用最小，年費(fèi)用為線路的新建投資年費(fèi)用、維護(hù)年費(fèi)用和運(yùn)行、折舊年費(fèi)用，約束條件包含配網(wǎng)輻射限制、負(fù)荷需求限制和線路潮流限制三個(gè)方面。該文以備選網(wǎng)絡(luò)的生成樹作為Tabu搜索的初始解，使得輻射性的約束自然滿足，Tabu 搜索算法中采用“交換移動(dòng)”進(jìn)一步判斷輻射性，Tabu表是先進(jìn)先出的管理模式。Tabu 搜索結(jié)果可以在GIS界面中形象的觀察到。
2.2 遺傳算法（GA）
遺傳算法是目前比較成熟的一種啟發(fā)式算法，遺傳算法類似于自然進(jìn)化，通過(guò)作用與染色體上的基因?qū)ふ液玫娜旧w來(lái)求解問(wèn)題[6]。
文獻(xiàn)[7]結(jié)合GA 和GIS 提出了一種新的電網(wǎng)規(guī)劃模型，該模型目標(biāo)函數(shù)中包含線路各種設(shè)備投資、維護(hù)、運(yùn)行費(fèi)用和用戶停電損失費(fèi)用。約束條件為輸送功率、電流允許范圍、最小電壓降以及網(wǎng)絡(luò)的輻射性。通過(guò)根節(jié)點(diǎn)融合法來(lái)保證網(wǎng)絡(luò)的輻射性，并考慮到了中間節(jié)點(diǎn)和分支點(diǎn)，形成真正可行的網(wǎng)絡(luò)接線方案，從而使該方法可以考慮各種復(fù)雜的網(wǎng)絡(luò)結(jié)構(gòu)，更適用于電網(wǎng)GIS規(guī)劃。GA 算子過(guò)程采用Elitism 算法：每次構(gòu)造子代種群時(shí)，都從父代種群中選擇一定的最優(yōu)個(gè)體直接作為子代個(gè)體，在隨機(jī)選擇時(shí)，適應(yīng)度高的以一定比例選中，經(jīng)試驗(yàn)證明變異率為0.02時(shí)遺傳算法的性能較好。該文最后對(duì)一個(gè)算例進(jìn)行投資總額分析，分析表明考慮可靠性價(jià)值可以節(jié)省資本，減少配網(wǎng)的投資金額。但該文僅解決了單條饋線優(yōu)化規(guī)劃，沒(méi)有考慮線路之間的接線模式的影響。
2.3電源追蹤算法
所謂電源追蹤就是在選中桿塔或者桿塔上設(shè)備時(shí)， 搜索給該設(shè)備供電的變電站。
文獻(xiàn)[8]將網(wǎng)絡(luò)拓?fù)浼夹g(shù)與電網(wǎng)GIS的開發(fā)相結(jié)合， 為電力企業(yè)的設(shè)備管理及輔助決策提供了圖形化的管理工具， 提高了電力企業(yè)的工作效率。它提出電源追蹤算法，該算法即使在網(wǎng)絡(luò)拓?fù)潢P(guān)聯(lián)屬性字段的數(shù)據(jù)不全時(shí)， 也能快速、準(zhǔn)確的定位電源點(diǎn)， 提高了電網(wǎng)電源追蹤模塊的實(shí)用性， 更好地滿足了實(shí)際工程的應(yīng)用需要。具體算法原理和過(guò)程如下：當(dāng)拓?fù)湫畔?shù)據(jù)不全時(shí)， 算法轉(zhuǎn)為執(zhí)行基于啟發(fā)式搜索的拓?fù)浞治鲎粉櫋Ｋ恍枰柚負(fù)潢P(guān)聯(lián)屬性字段的值， 而是通過(guò)地理信息系統(tǒng)軟件提供的拓?fù)浞治龊瘮?shù)就可建立起整個(gè)電網(wǎng)絡(luò)， 并通過(guò)這個(gè)網(wǎng)絡(luò)進(jìn)行搜索， 從而選擇出設(shè)備到其供電電源的最優(yōu)路徑。
3 結(jié)論
1、每種算法都有自己的優(yōu)點(diǎn)，但任何一種算法都有自己的不足。各種算法雖然在理論上能較好的滿足規(guī)劃要求，但還很難便捷的應(yīng)用到實(shí)際中。
2、盡管基于GIS的電網(wǎng)規(guī)劃方法的研究已取得很多成果，但至今還沒(méi)有比較完善的電網(wǎng)規(guī)劃軟件能夠方便地應(yīng)用到實(shí)際規(guī)劃工作中。因此，研究開發(fā)相對(duì)完善實(shí)用的電網(wǎng)規(guī)劃軟件和基于GIS的電網(wǎng)規(guī)劃軟件將是電網(wǎng)規(guī)劃研究工作者們今后工作中的首要任務(wù)。
參考文獻(xiàn)
[1]趙帥虎，吳健，陳丁劍.基于GIS 配電網(wǎng)自動(dòng)化分布式協(xié)同建模技術(shù)的研究[J]. 微型電腦應(yīng)用.Vol.27，No.1，2011.1：6
[2]王金鳳.基于GIS的配電網(wǎng)優(yōu)化規(guī)劃研究.碩士學(xué)位論文[D].鄭州大學(xué)，2002.4
[3] 張志波.基于GIS技術(shù)的縣級(jí)配電網(wǎng)架優(yōu)化規(guī)劃軟件[D].碩士學(xué)位論文.河北農(nóng)業(yè)大學(xué)，2008.6
[4]張林峰.基于地理信息系統(tǒng)的智能城市電網(wǎng)規(guī)劃.碩士學(xué)位論文[D].華北電力大學(xué)，2006.12
[5]楊麗徙，王金鳳，陳根永.基于GIS 和Tabu 搜索的配電網(wǎng)優(yōu)化規(guī)劃[J].鄭州大學(xué)學(xué)報(bào)（公學(xué)版）.VOL 23，No.3，2002.9：75-77
[6]劉娜.基于遺傳算法的農(nóng)村配電網(wǎng)檢修計(jì)劃方法的研究[D].沈陽(yáng)農(nóng)業(yè)大學(xué)，2005.10
[7]王春生，趙凱，彭建春.基于地理信息系統(tǒng)和遺傳算法的配電網(wǎng)優(yōu)化規(guī)劃[J].電力系統(tǒng)自動(dòng)化.2000.7.48-51
[7]趙強(qiáng)，楊柳.基于啟發(fā)式搜索的配電網(wǎng)GIS拓?fù)浞治鯷J]. 計(jì)算機(jī)應(yīng)用與軟件.Vol.25，No.9，2008.9：181-183
[8]陳珊. WebGIS中最短路徑算法及其應(yīng)用的研究[D]. 上海： 華東師范大學(xué)， 2005.
【關(guān)鍵詞】云計(jì)算；DAG圖；遺傳；蟻群；任務(wù)；融合
本文提出一種基于DAG模型的優(yōu)先級(jí)表的依賴任務(wù)調(diào)度算法。以時(shí)間觸發(fā)調(diào)度，采用重復(fù)調(diào)度。當(dāng)每次調(diào)度事件發(fā)生時(shí)，包含那些上一次調(diào)度事件中已經(jīng)被調(diào)度但還沒(méi)有開始執(zhí)行或被迫中斷的任務(wù), 還有新到達(dá)的任務(wù)，。這與云計(jì)算中資源的動(dòng)態(tài)性是相應(yīng)的。
在算法實(shí)現(xiàn)方面，我們考慮將遺傳算法和蟻群算法相結(jié)合，利用遺傳算法進(jìn)行前期訓(xùn)練然后利用蟻群算法進(jìn)一步進(jìn)行搜索收斂，最終得到最優(yōu)調(diào)度方案。結(jié)合云計(jì)算任務(wù)調(diào)度的特點(diǎn)，本文選取遺傳算法和蟻群算法的參數(shù)設(shè)置，將問(wèn)題轉(zhuǎn)換到云計(jì)算任務(wù)調(diào)度問(wèn)題上來(lái)，提出融合遺傳算法[1]和蟻群算法[2][3]的云計(jì)算任務(wù)調(diào)度算法。
一、問(wèn)題提出
每個(gè)子任務(wù)用圓圈表示，圈中T表示任務(wù)號(hào)，Q表示計(jì)算量，而DAG圖中的箭頭表示子任務(wù)之間的優(yōu)先關(guān)系，C(i,j)表示任務(wù)Ti與Tj之間的通信量。圖1所示，箭頭從前驅(qū)指向后繼，前驅(qū)是后繼的必要，只有在某個(gè)任務(wù)的所有前驅(qū)都完成時(shí)，該任務(wù)才被執(zhí)行。在任務(wù)調(diào)度過(guò)程中重復(fù)調(diào)度，當(dāng)每次調(diào)度事件發(fā)生時(shí)，任務(wù)組中既包含新到達(dá)的任務(wù)，。這與云計(jì)算中資源的動(dòng)態(tài)性相適應(yīng)的。算法使用更新的資源信息對(duì)任務(wù)進(jìn)行調(diào)度，這與動(dòng)態(tài)的云計(jì)算環(huán)境是相適應(yīng)的。
Fig.1 DAG task graph
圖1 任務(wù)DAG圖
由各種任務(wù)分配方案需要進(jìn)行優(yōu)化。如圖2任務(wù)劃分后的一種方案。
Fig.2 Sub-task resource allocation plan
圖2 子任務(wù)資源分配圖
設(shè)有m個(gè)計(jì)算結(jié)點(diǎn)所組成的云計(jì)算系統(tǒng)P={P1,P2,…,Pm}，每個(gè)結(jié)點(diǎn)Pj處理能力為d。需要運(yùn)行m個(gè)子任務(wù)T={t1,t2,…,tm}，一般地。將任務(wù)調(diào)度問(wèn)題描述成如下五元組∑=(T,,Q,C,X,w)。其中：“”是T中子任務(wù)間的優(yōu)先關(guān)系；Q是一個(gè)維的矩陣，其元素qij表示子任務(wù)ti在處理機(jī)Pj上的執(zhí)行時(shí)間；C是一個(gè)維通信矩陣，cij表示子任務(wù)ti與tj之間的通信時(shí)間；X是一個(gè)維的任務(wù)分配矩陣，其中Xij=1,表示ti分配到處理機(jī)Pj上執(zhí)行，否則Xij=0；w表示通信和執(zhí)行之間的差異。
二、算法實(shí)現(xiàn)
利用遺傳算法進(jìn)行前期的訓(xùn)練。得到的信息素作為蟻群算法的初始值，最終得到最優(yōu)或次優(yōu)調(diào)度方案。
(1)設(shè)置遺傳算法參數(shù)；(2)假定遺傳算法結(jié)束條件；
(3)生成初始種群P（0），g=0； (4)計(jì)算P(0)中的個(gè)體適應(yīng)值；
(5)反復(fù)執(zhí)行，直到滿足結(jié)束條件；
①根據(jù)個(gè)體適應(yīng)值及選擇策略確定P(g)內(nèi)選擇概率；
②進(jìn)行PC交叉操作；
③ 進(jìn)行Pm變異操作；
④計(jì)算P(g+1)中個(gè)體的適應(yīng)值，g=g+1；
(6)P(G)從中選擇適應(yīng)能力強(qiáng)的個(gè)體，放入集合中，作為優(yōu)化集合；
(7)對(duì)于集合中的每個(gè)優(yōu)化解，將遺傳算法求解結(jié)果轉(zhuǎn)換為蟻群算法中的信息素值；
(8)設(shè)置蟻群算法控制參數(shù)；(9)設(shè)置蟻群算法結(jié)束條件；
(10)將m只螞蟻散布到n個(gè)計(jì)算結(jié)點(diǎn)上；
(11)對(duì)螞蟻的分配結(jié)果計(jì)算目標(biāo)函數(shù)，選取當(dāng)前的最佳解；
(12)更新計(jì)算結(jié)點(diǎn)的信息素值；
(13)若滿足蟻群算法結(jié)束條件，退出；否則，返回執(zhí)行步驟(10)。
三、總結(jié)
在云計(jì)算環(huán)境里調(diào)度計(jì)算是影響云計(jì)算能否成功的最重要的因素之一。由于資源在廣域上分布，本質(zhì)上異構(gòu)，相異的存取和花費(fèi)模式、負(fù)載和可用性動(dòng)態(tài)變化，因此云計(jì)算環(huán)境下的任務(wù)管理十分復(fù)雜。在云計(jì)算系統(tǒng)中，如何協(xié)調(diào)和分配任務(wù)，這就是調(diào)度需要解決的問(wèn)題。本文在廣泛閱讀國(guó)內(nèi)外相關(guān)文獻(xiàn)后，歸納云計(jì)算和任務(wù)調(diào)度方面的研究成果，提出基于DAG以及融合遺傳算法和蟻群算法的動(dòng)態(tài)云計(jì)算任務(wù)調(diào)度算法。
通過(guò)實(shí)驗(yàn)結(jié)果分析比較可以看出，本文提出的算法在運(yùn)行性能上具有一定的優(yōu)勢(shì)，充分驗(yàn)證了算法的合理性和有效性。當(dāng)然，在仿真環(huán)境的限制下，可能實(shí)驗(yàn)結(jié)果有細(xì)微的差別，但我們相信本文提出的算法不失為合理而有效的算法。
參考文獻(xiàn)：
[1]Annie S W, Han Y et al.An incremental genetic algorithm approach to multiprocessor scheduling[J],2004,15(9):824-834
[2] Dorigo M,Gambardella L M.Ant colony system: A cooperative learning approach to the traveling salesman problem,IEEE Trans. Evolutionary Computation[J],1997,1(1):53-66
[3] HUI YAN，XUE-QIN SHEN et al. AN IMPROVED ANT ALGORITHM FOR JOBSCHEDULING IN GRID COMPUTING.IEEE Proceeding of the Fourth International Conference on Machine Learning and Cybernetics[C], Guangzhou, August 2005:2957-2961
[4] Foster I,Kesselman C,Tuccke. The Anatomy of the Grid：Enabling Scalable Virtual Organizations[J].International Joural of Supercomputer Application，2001；15(3):200-222
[5]I Foster,C Kesselman.Grid Services for Distributed System Integration[J].Computer,2002,35(6):37-46
[6] 孫玉濤,網(wǎng)格計(jì)算環(huán)境中的動(dòng)態(tài)任務(wù)調(diào)度算法研究,云南師范大學(xué)碩士論文.2007
關(guān)鍵詞：排課；NP；多約束條件；遺傳算法
中圖分類號(hào)：TP311文獻(xiàn)標(biāo)識(shí)碼：A文章編號(hào)：1009-3044(2008)27-1958-02
Research on the Algorithms of the Course Scheduling System for College under the Multi-constrained Conditions
CHEN Xing-gang, MENG Xiang-jing, LI Jing, SONG Jian
(Electronic Science and Information Technology Institute, Guizhou University, Guiyang 550025 China)
Abstract：College course arrangement is a typical combinatorial optimization and NP-hard problem. As the current College Enrollment Expansion and consolidation trend, increasing the size of colleges and universities, the growing tension school resources, for teachers and students during school hours, school locations and other issues on the arrangements being bound by the conditions of a growing number of reality, This paper will adopt strategies to be one of the course arrangement of resources and constraints analysis, and then focus on the course arrangement commonly used in genetic algorithm.
Key words：course scheduling; NP; multi-constrained conditions; GA
排課是高校教學(xué)管理中的一項(xiàng)重要而且難度和復(fù)雜度都極高的基本工作。特別是近年來(lái)，隨著我國(guó)高校的擴(kuò)招和合并，學(xué)校的教學(xué)資源（如教室、實(shí)驗(yàn)室、語(yǔ)音室等）愈顯緊張；同時(shí)，在學(xué)分制的制度下，課程的類別越分越多，有公共必修課、公共選修課、專業(yè)基礎(chǔ)課、專業(yè)必修課、專業(yè)選修課等等；再者，上課的教師也會(huì)有一些特殊情況需要考慮。這樣一來(lái)，排課人員在排課時(shí)倍感棘手，以至于開學(xué)后因排課問(wèn)題還會(huì)影響到教學(xué)的正常進(jìn)行。
目前，國(guó)內(nèi)的許多高校都引進(jìn)了不同智能化程度的排課軟件，然而，其應(yīng)用的效果都有些不盡如人意，雖然耗費(fèi)了教務(wù)處工作人員大量的時(shí)間和精力，但遺留下的問(wèn)題還是很多。
下面我們基于人工排課的宏觀指導(dǎo)思想，列出約束限制條件，采用遺傳算法，進(jìn)行多輪次掃描計(jì)算，以改變目前的排課系統(tǒng)沖突多、調(diào)整應(yīng)變能力弱，排課時(shí)間長(zhǎng)的問(wèn)題，從而求得合理性解。
1 排課時(shí)所受的約束限制條件
高校排課問(wèn)題，它要求將課程、教師、班級(jí)安排在一個(gè)有限的時(shí)間和空間當(dāng)中去，要求避免沖突且盡量滿足一些其它條件，這實(shí)際上是五個(gè)相互制約的因素的組合優(yōu)化問(wèn)題。1975年，美國(guó)S.Even等人證明了高校排課問(wèn)題也是一個(gè)NP(Non-deterministic Polynomial)難問(wèn)題，即多項(xiàng)式復(fù)雜程度的非確定性問(wèn)題，即找不到多項(xiàng)式時(shí)間求解算法。具體到高校排課系統(tǒng)的算法上，五個(gè)相互制約的因素它們所受到的約束限制條件有：
1) 不能在同一時(shí)間給同一位教師安排多個(gè)班級(jí)課程(合班除外) 或同時(shí)講授多門課程。
2) 不能在同一時(shí)間給同一個(gè)教室安排多個(gè)班級(jí)上課(合班除外) 或多位教師授課。
3) 不能在同一時(shí)間給同一個(gè)班級(jí)安排多門課程或同時(shí)在不同的教室上課。
4) 不能在安排教室時(shí)使教室容納人數(shù)小于上課學(xué)生人數(shù)。
5) 對(duì)于需要特殊場(chǎng)所的課程, 如體育課、實(shí)驗(yàn)課、語(yǔ)音教室等, 應(yīng)安排相應(yīng)地點(diǎn)或?qū)嶒?yàn)室上課。
以上是高校排課時(shí)必須滿足的條件, 否則無(wú)法進(jìn)行正常教學(xué)。在能夠進(jìn)行正常教學(xué)的情況下我們還應(yīng)考慮到教學(xué)效果，學(xué)生學(xué)習(xí)效率， 教師、學(xué)生的便利等其他因素，因此，還要考慮一些盡量去實(shí)現(xiàn)的約束條件，這包括：
1) 一門課程的幾次課在一周之內(nèi)應(yīng)間隔排列。
2) 上課人數(shù)盡量接近教室容量。
3) 排課時(shí)可注意文科類課程和理科類課程交叉安排,避免使學(xué)生產(chǎn)生倦怠感, 有利于提高學(xué)習(xí)效率。
4) 體育課最好不要安排在一天中的第1-2節(jié), 并且在體育課后最好不要再安排其它課程, 保證教學(xué)效果。
5) 同一班級(jí)連續(xù)兩次講課之間更換教室盡可能少；同一課程的不同講次盡量不換教室。
6) 不要在一天中給教師或?qū)W生安排太多課程, 最好不要連續(xù)上課超過(guò) 6 節(jié), 有利于提高教學(xué)效果和學(xué)習(xí)效率。
2 排課問(wèn)題描述
在排課問(wèn)題中，我們的基本任務(wù)是將班級(jí)、教室、課程、教師安排在一周內(nèi)且不發(fā)生時(shí)間沖突[2]。據(jù)此，對(duì)這五個(gè)相互制約的因素我們給出如下的描述：
學(xué)校有R間教室，C個(gè)班，S門課程，T位教師，P個(gè)時(shí)間段。
1) 教室集合R（R1,R2,…,Rr），每間教室分別可容納（X1,X2,…,Xy）人；
2) 班級(jí)集合C（C1,C2,…,Cc），每個(gè)班級(jí)分別有（K1,K2,…,Kc）人，其中有x個(gè)班級(jí)上合班課；
3) 課程集合S（S1,S2,…,Ss），每門課對(duì)應(yīng)Ci個(gè)班，1位教師，（1≤Ci
4) 教師集合T（T1,T2,…,Tt），每位教師對(duì)應(yīng)Sm門課，Cc個(gè)班，（1≤Sm
5) 時(shí)間集合P(P1，P2，…，Pp)，假設(shè)一周上五天課，每天分為五個(gè)教學(xué)單元，每個(gè)單元為2個(gè)課時(shí)，即上午2個(gè)，下午2個(gè),晚上1個(gè)，則時(shí)間集合包含25個(gè)時(shí)間段。如11代表周一第一個(gè)教學(xué)單元，即周一1、2節(jié)，12代表周一第二個(gè)教學(xué)單元，即周一3、4節(jié)，以此類推，這些時(shí)間段構(gòu)成一個(gè)時(shí)間集合P(11,12,13,…,55)。
3 算法研究
從20世紀(jì)50年代以來(lái)，國(guó)際上就有人著手研究應(yīng)用計(jì)算機(jī)進(jìn)行排課的問(wèn)題。國(guó)外的研究表明，解決大規(guī)模的排課問(wèn)題單純依靠數(shù)學(xué)方法是行不通的，進(jìn)入20世紀(jì)90年代以后，國(guó)外對(duì)排課問(wèn)題的研究仍然十分活躍。國(guó)外目前較多采用著色算法、數(shù)學(xué)方法、模擬退火技術(shù)、禁忌算法、局部?jī)?yōu)化算法和遺傳算法等。
3.1 遺傳算法
遺傳算法(Genetic Algorithm，GA)是一種有效的解決最優(yōu)化問(wèn)題的方法或計(jì)算模型。遺傳算法的研究歷史比較短，它出現(xiàn)在20世紀(jì)六、七十年代，主要是由美國(guó)Michigan大學(xué)教授John Holland與其同事、學(xué)生們通過(guò)對(duì)生物進(jìn)化過(guò)程進(jìn)行模擬，研究形成的一個(gè)較完整的理論和一種全新的概率優(yōu)化方法。John Holland提出這一算法的最初目的是研究自然系統(tǒng)的自適應(yīng)行為，并用于設(shè)計(jì)具有自適應(yīng)功能的軟件系統(tǒng)。隨后經(jīng)過(guò)20余年的發(fā)展，計(jì)算智能化己經(jīng)作為人工智能研究的一個(gè)重要方向，以及后來(lái)的人工生命研究興起,使遺傳算法受到廣泛的關(guān)注。目前，遺傳算法作為具有系統(tǒng)優(yōu)化、適應(yīng)和學(xué)習(xí)的高性能計(jì)算和建模方法的研究漸趨成熟。
GA算法具有下述特點(diǎn)：
1) GA是對(duì)問(wèn)題參數(shù)的編碼組進(jìn)行進(jìn)貨，而不是直接對(duì)參數(shù)本身。
2) GA的搜索是從問(wèn)題解的編碼組開始搜索，而不是從單個(gè)解開始。
3) GA使用目標(biāo)函數(shù)值（適應(yīng)度）這一信息進(jìn)行搜索，而不需導(dǎo)數(shù)等其他信息。
4) GA算法使用的選擇、交叉、變異這三個(gè)算子都是隨機(jī)操作，而不是確定規(guī)則。
3.2 算法描述
利用遺傳算法解最優(yōu)化問(wèn)題，首先應(yīng)對(duì)可行域中的點(diǎn)進(jìn)行編碼（一般采用二進(jìn)制編碼），然后在可行域中隨機(jī)挑選一些編碼組作為進(jìn)化起點(diǎn)的第一代編碼組，并計(jì)算每個(gè)解的目標(biāo)函數(shù)值，也就是編碼的適應(yīng)度。接著就像自然界中一樣，利用選擇機(jī)制從編碼組中隨機(jī)挑選編碼作為繁殖過(guò)程前的編碼樣本。選擇機(jī)制應(yīng)保證適應(yīng)度較高的解能夠保留較多的樣本；而適應(yīng)度較低的解則保留較少的樣本，甚至被淘汰。在接下去的繁殖過(guò)程中，遺傳算法提供了交叉和變異兩種算子對(duì)挑選后的樣本進(jìn)行交換。交叉算子交換隨機(jī)挑選的兩個(gè)編碼的某些位，變異算子則直接對(duì)一個(gè)編碼中的隨機(jī)挑選的某一位進(jìn)行反轉(zhuǎn)。這樣通過(guò)選擇和繁殖就產(chǎn)生了下一代編碼組。重復(fù)上述選擇和繁殖過(guò)程，直到結(jié)束條件得到滿足為止。進(jìn)化過(guò)程最后一代中的最優(yōu)解就是用遺傳算法解最優(yōu)化問(wèn)題時(shí)所得到的最終結(jié)果。
用遺傳算法解決組合優(yōu)化問(wèn)題的一般流程用數(shù)學(xué)語(yǔ)言描述如下:
1) 將待解決問(wèn)題的相關(guān)參數(shù)進(jìn)行編碼；
2) 隨機(jī)地初始化種群X(0)=(xl,x2,...,xm)，其中m為群體規(guī)模；
3) 對(duì)當(dāng)前代種群X(t)中的每個(gè)個(gè)體xi計(jì)算其適應(yīng)度值f(xi)，適應(yīng)度值的大小體現(xiàn)了該個(gè)體性能的優(yōu)劣；
4) 應(yīng)用選擇算子產(chǎn)生中間代X(t)；
5) 對(duì)X(t)應(yīng)用雜交、變異算子，產(chǎn)生新一代的種群X(t+l)。雜交和變異算子的目的在于擴(kuò)展有限個(gè)體的覆蓋面，體現(xiàn)全局搜索的思想；
f.進(jìn)化到下一代，代計(jì)數(shù)器t加1。如果滿足終止條件，則執(zhí)行下一步7),否則轉(zhuǎn)步驟3)；
g.輸出近似最優(yōu)解。
相應(yīng)的執(zhí)行框圖如圖1所示。
參考文獻(xiàn)：
[1] 朱莉娟,李冬.計(jì)算機(jī)排課問(wèn)題中幾種算法的探討[J].新鄉(xiāng)教育學(xué)院學(xué)報(bào).2007,(9).
[2] 唐勇,唐雪飛,王玲.基于遺傳算法的排課系統(tǒng)[J].計(jì)算機(jī)應(yīng)用.2002，(1):93-94,97.
[3] 沈麗容,陳明磊.基于遺傳算法的高校排課系統(tǒng)研究[J].計(jì)算機(jī)與信息技術(shù),2006,(11).
[4] 石菁,李洪波.排課算法比較[J].福建電腦.2007,(8).
〔關(guān)鍵詞〕知識(shí)圖譜；專家系統(tǒng)；發(fā)展軌跡
DOI：10．3969／j．issn．1008－0821．2012．02．040
〔中圖分類號(hào)〕G250.71 〔文獻(xiàn)標(biāo)識(shí)碼〕A 〔文章編號(hào)〕1008－0821（2012）02－0159－08
Knowledge-based Expert System Development Overview MapLiao Yi
（Political Department，National University of Defense Technology，Changsha 410073，China）
〔Abstract〕Artificial intelligence expert system is the most important and most active areas of an application,which implements the artificial intelligence research from theory to practice,turning from the general reasoning strategies of a major breakthrough in the use of expertise.This chronological order,the expert system into the 1980s before the 1980s,1990s,2000,after four stages.Articles using bibliometric methods,analysis of the expert system development process,development and trends,pointing out that the current phase is the development of expert systems,expert systems into a variety of commercial operation,need to address the knowledge acquisition bottleneck,matching conflicts and other issues for expert systems to understand and master the subject structure,evolution,development and so provide an unique perspective and knowledge.
〔Key words〕knowledge maps;expert systems;the development trajectory
專家系統(tǒng)作為人工智能的一個(gè)重要分支，發(fā)展已經(jīng)超過(guò)50年，在很多應(yīng)用領(lǐng)域都獲得了廣泛使用，取得了豐碩成果。本文運(yùn)用文獻(xiàn)計(jì)量這一獨(dú)特視角對(duì)專家系統(tǒng)進(jìn)行了再回顧和再分析，將智能科技劃分為初創(chuàng)期、成長(zhǎng)期、低谷期、發(fā)展期，利用詞頻分析、共引分析、作者共現(xiàn)分析等方法揭示專家系統(tǒng)的學(xué)科結(jié)構(gòu)、影響程度、關(guān)鍵節(jié)點(diǎn)與時(shí)間點(diǎn)等重要而獨(dú)特的知識(shí)，為了解和掌握專家系統(tǒng)的發(fā)展與演化過(guò)程提供了獨(dú)特視角。
1 數(shù)據(jù)來(lái)源
SCI（Science Citation Index）是美國(guó)科學(xué)情報(bào)研究所ISI（Institute for Science Information）出版的期刊文獻(xiàn)檢索工具，所收錄的文獻(xiàn)覆蓋了全世界最重要和最有影響力的研究成果，成為世界公認(rèn)的自然科學(xué)領(lǐng)域最為重要的評(píng)價(jià)工具。本文以Web of Science中的SCI數(shù)據(jù)庫(kù)為數(shù)據(jù)來(lái)源，選用高級(jí)檢索方式，以“Expert System/Experts System”作為主題詞，于2011年5月在Web of Secience中進(jìn)行檢索，一共檢索到14 500篇相關(guān)文獻(xiàn)記錄。獲得的年度分布如圖1。所示。雖然，專家系統(tǒng)研究從20世紀(jì)五六十年代就開始了，但是從圖1可以看出直到1982年才有主題詞與專家系統(tǒng)相關(guān)的論文出現(xiàn)。圖1表明1991年左右，專家系統(tǒng)相關(guān)論文達(dá)到了峰值，但隨后呈逐年下降的趨勢(shì)。到1999年，只有494篇。但21世紀(jì)開始，專家系統(tǒng)相關(guān)論文又出現(xiàn)了增加的趨勢(shì)，并維持在一個(gè)穩(wěn)定的水平中。圖1 專家系統(tǒng)在SCI數(shù)據(jù)庫(kù)文獻(xiàn)發(fā)表年度變化情況
2012年2月第32卷第2期基于知識(shí)圖譜的專家系統(tǒng)發(fā)展綜述Feb.，2012Vol.32 No.22 專家系統(tǒng)前40年的發(fā)展
本文利用基于JAVA平臺(tái)的引文分析可視化軟件Citespace，首先設(shè)定時(shí)間跨度為1950-1991年，時(shí)間切片長(zhǎng)度為1年，聚類方式為共被引聚類（Cited Reference），閾值選擇為（2，2，20）、（3，3，20）、（3，3，20）。Citespace得出這些引文的時(shí)間跨度為1950－1990年，可以繪制出該時(shí)間段的專家系統(tǒng)論文時(shí)區(qū)分布圖，如圖2所示。我們以年代先后為序，將20世紀(jì)80年代以前作為第一階段，80年代至90年代作為第二階段。圖2 1950-1991年各年度專家系統(tǒng)論文之間的時(shí)區(qū)分布圖
2.1 專家系統(tǒng)起源時(shí)期
根據(jù)圖2顯示，這段時(shí)期有7個(gè)突出節(jié)點(diǎn)，既有7位代表人物。第一個(gè)節(jié)點(diǎn)代表的是“人工智能之父”――英國(guó)著名科學(xué)家阿蘭?麥席森?圖靈（Alan Mathison Turing），他于1950年在《心靈》雜志上《計(jì)算機(jī)器與智能》，提出了著名的“圖靈測(cè)試”，探討了機(jī)器智能的可能性，為后來(lái)的人工智能科學(xué)提供了開創(chuàng)性的構(gòu)思［1］。
第二個(gè)節(jié)點(diǎn)代表的是美國(guó)工程院院士、加州大學(xué)扎德（LA.Zadeh）教授，他于1965年在《信息與控制》雜志第8期上發(fā)表題為《模糊集》的論文，提出模糊集合理論，給出了模糊性現(xiàn)象定量描述和分析運(yùn)算的方法，從而誕生了模糊數(shù)學(xué)。1978年，扎德教授提出了“可能性理論”，將不確定性理解為可能性，為模糊集理論建立了一個(gè)實(shí)際應(yīng)用上的理論框架，這也被認(rèn)為是模糊數(shù)學(xué)發(fā)展的第二個(gè)里程碑。同年，國(guó)際性期刊《International Journal of Fuzzy Sets and System》誕生，這使得模糊理論得到普遍承認(rèn)，理論研究高速發(fā)展，實(shí)際應(yīng)用迅速推廣。
第三個(gè)節(jié)點(diǎn)代表的美國(guó)兩院院士、卡內(nèi)基-梅隆大學(xué)教授艾倫?紐厄爾（Allen Newell），1972年，他出版了《人怎樣解題》（Human Problem Solving)一書，書中描述了他和西蒙試圖建立一個(gè)計(jì)算機(jī)化的“通用問(wèn)題求解器”的歷程：20世紀(jì)50年代，他們發(fā)現(xiàn)，人類的問(wèn)題解決，在一定知識(shí)領(lǐng)域內(nèi)可以通過(guò)計(jì)算機(jī)實(shí)現(xiàn)，所以他們開始用計(jì)算機(jī)編程來(lái)解決問(wèn)題，1956年，他們研發(fā)出了邏輯理論家和通用問(wèn)題求解器（General Problem Solver），并建立了符號(hào)主義人工智能學(xué)派。我們可以看出，這本書是對(duì)他以前所作工作的總結(jié)與歸納，而邏輯理論家和通用問(wèn)題求解器正是專家系統(tǒng)的雛形，為專家系統(tǒng)的出現(xiàn)奠定了堅(jiān)實(shí)的基礎(chǔ)。
但是艾倫?紐厄爾的嘗試無(wú)法解決大的實(shí)際問(wèn)題，也很難把實(shí)際問(wèn)題改造成適合于計(jì)算機(jī)解決的形式，并且對(duì)于解題所需的巨大搜索空間也難于處理。為此，美國(guó)國(guó)家工程院院士、斯坦福大學(xué)教授費(fèi)根鮑姆（E.A.Feigenbaum）等人在總結(jié)通用問(wèn)題求解系統(tǒng)成功與失敗的經(jīng)驗(yàn)基礎(chǔ)上，結(jié)合化學(xué)領(lǐng)域的專門知識(shí)，于1965年研制了世界上第一個(gè)專家系統(tǒng)dendral，可以推斷化學(xué)分子結(jié)構(gòu)。專家系統(tǒng)進(jìn)入了初創(chuàng)期，其代表有dendral、macsyma（數(shù)學(xué)專家系統(tǒng)）等，第一代專家系統(tǒng)以高度專業(yè)化、求解專門問(wèn)題的能力強(qiáng)為特點(diǎn)，向人們展示了人工智能應(yīng)用的廣闊前景［2］。
第四個(gè)節(jié)點(diǎn)代表人物是美國(guó)麻省理工學(xué)院著名的人工智能學(xué)者明斯基（Minsky）。1975年，他在論文《表示知識(shí)的框架》(A Framework for Representating Knowledge，McGraw-Hill)中提出了框架理論，框架理論的核心是以框架這種形式來(lái)表示知識(shí)。理論提出后，在人工智能界引起了極大的反響，并成為了基于框架的專家系統(tǒng)的理論基礎(chǔ)，基于框架的專家系統(tǒng)適合于具有固定格式的事物、動(dòng)作或事件。
第五個(gè)節(jié)點(diǎn)代表人物是美國(guó)普林斯頓大學(xué)教授格倫謝弗（Glenn Shafer），他在1976年出版了《數(shù)學(xué)理論的證據(jù)》（A mathematical theory of evidence）一書，介紹了由他和Dempster于1967年提出的D-S理論（即證據(jù)理論）。證據(jù)理論可處理由不知道因素引起的不確定性，后來(lái)，該理論被廣泛應(yīng)用于計(jì)算機(jī)科學(xué)和工程應(yīng)用，是基于D-S證據(jù)理論的專家系統(tǒng)的理論基礎(chǔ)。
第六個(gè)重要節(jié)點(diǎn)代表是美國(guó)斯坦福大學(xué)愛(ài)德華?漢斯?肖特利夫（Shortliff EH）教授，他于1975年在著名雜志《數(shù)學(xué)生物科學(xué)》上發(fā)表《A model of inexact reasoning in medicine》（《在醫(yī)學(xué)模型的不精確推理》）一文，他結(jié)合自己1972－1974年研制的世界第一個(gè)醫(yī)學(xué)專家系統(tǒng)――MYCIN系統(tǒng)（用于診斷和治療血液感染及腦炎感染，是第二代專家系統(tǒng)的經(jīng)典之作），提出了確定性理論，該理論對(duì)專家系統(tǒng)的發(fā)展產(chǎn)生了重大影響。
第七個(gè)節(jié)點(diǎn)代表人物是美國(guó)麻省理工學(xué)院計(jì)算機(jī)科學(xué)和人工智能實(shí)驗(yàn)室的戴維斯（Randall Davis）教授，他于1976年提出元知識(shí)的概念，并在專家系統(tǒng)的研制工具開發(fā)方面做出了突出貢獻(xiàn)――研制出知識(shí)獲取工具Teiresias，為專家系統(tǒng)獲取知識(shí)實(shí)現(xiàn)過(guò)程中知識(shí)庫(kù)的修改和添加提供了工具［3］，關(guān)Teiresias，他于1977年在《Artificial Intelligence》雜志上中進(jìn)行了詳細(xì)介紹，而這也為本時(shí)期專家系統(tǒng)的快速增多和廣泛應(yīng)用奠定了堅(jiān)實(shí)基礎(chǔ)。
20世紀(jì)70年代后期，隨著專家系統(tǒng)應(yīng)用領(lǐng)域的不斷開拓，專家系統(tǒng)研發(fā)技術(shù)逐漸走向成熟。但同時(shí)，專家系統(tǒng)本身存在的應(yīng)用領(lǐng)域狹窄、缺乏常識(shí)性知識(shí)、知識(shí)獲取困難、推理方法單一等問(wèn)題也被逐漸暴露出來(lái)。人們從各種不同類型的專家系統(tǒng)和知識(shí)處理系統(tǒng)中抽取共性，人工智能又從具體研究逐漸回到一般研究。圍繞知識(shí)這一核心問(wèn)題，人們重新對(duì)人工智能的原理和方法進(jìn)行探索，并在知識(shí)的獲取、表示以及知識(shí)在推理過(guò)程中的利用等方面開始出現(xiàn)一組新的原理、工具和技術(shù)。
2.2 專家系統(tǒng)發(fā)展的黃金時(shí)期
20世紀(jì)80年代是專家系統(tǒng)突飛猛進(jìn)、迅速發(fā)展的黃金時(shí)代，根據(jù)圖2顯示，這段時(shí)期共有論文982篇，有7個(gè)突出節(jié)點(diǎn)。
1980年，出現(xiàn)了第一個(gè)節(jié)點(diǎn)代表――美國(guó)斯坦福大學(xué)計(jì)算機(jī)科學(xué)系系主任尼爾森（NILS J.NILSSON），他出版的《人工智能原理》（《Principles of artificial intelligence》）一書，表明了拉近理論和實(shí)踐的距離的目標(biāo)，書中對(duì)基于規(guī)則的專家系統(tǒng)、機(jī)器問(wèn)題解決系統(tǒng)以及結(jié)構(gòu)對(duì)象的代表等都進(jìn)行了具體的論述。
1981年，出現(xiàn)了第二個(gè)節(jié)點(diǎn)代表――英國(guó)赫特福德大學(xué)教授Clocksin，威廉F，他出版的《PROLOG語(yǔ)言編程》一書，引起了計(jì)算機(jī)科學(xué)界的極大興趣，并已被證明是一個(gè)重要的編程語(yǔ)言和人工智能系統(tǒng)的新一代基礎(chǔ)，是專家系統(tǒng)的重要編程語(yǔ)言。
1982年，出現(xiàn)了第三個(gè)節(jié)點(diǎn)代表――美國(guó)匹茲堡大學(xué)教授米勒（Miller RA），他在《英格蘭醫(yī)藥分冊(cè)》上發(fā)表了《基于計(jì)算機(jī)的醫(yī)學(xué)內(nèi)科實(shí)驗(yàn)診斷顧問(wèn)》（An Experimental Computer based Diagnostic Consultant for General Internal Medicine.N Engl J Med,307,468-76,1982）一文，屬當(dāng)時(shí)診斷專家系統(tǒng)的代表力作，書中介紹了著名的內(nèi)科疾病診斷咨詢系統(tǒng)INTERNIST-1，之后將其不斷完善成改進(jìn)型INTERNIST-2，即后來(lái)的CADUCEUS專家系統(tǒng)，其知識(shí)庫(kù)中包含了572種疾病，約4 500種癥狀。
1983年，出現(xiàn)了第四個(gè)節(jié)點(diǎn)代表――美國(guó)的海斯羅斯（Hayes-Roth，F(xiàn)）教授，他于1983年發(fā)表著作《建立專家系統(tǒng)》，對(duì)專家系統(tǒng)建立的原則和要素、開發(fā)的生命周期等重要問(wèn)題進(jìn)行了詳細(xì)講解，為研究與開發(fā)各種類型的專家系統(tǒng)提供了理論依據(jù)。
1984年，出現(xiàn)了第五個(gè)節(jié)點(diǎn)代表――美國(guó)匹茲堡大學(xué)計(jì)算機(jī)科學(xué)、哲學(xué)和醫(yī)學(xué)教授布魯斯?布坎南（Bruce G.Buchanan），他于1984年發(fā)表著作《規(guī)則的專家系統(tǒng)：斯坦福啟發(fā)式編程項(xiàng)目Mycin實(shí)驗(yàn)》（《Rule Based Expert Systems:The Mycin Experiments of the Stanford Heuristic Programming Project》，這是有史以來(lái)關(guān)于醫(yī)療診斷系統(tǒng)MYCIN的實(shí)驗(yàn)規(guī)則庫(kù)公布。基于規(guī)則的專家系統(tǒng)MYCIN是專家系統(tǒng)開發(fā)過(guò)程中一個(gè)里程碑，研究其開發(fā)思路與方法具有非常重要的意義。
1985年，出現(xiàn)了第六個(gè)節(jié)點(diǎn)代表――美國(guó)人工智能專家、加州大學(xué)教授哈蒙（Harmon P），他出版了《專家系統(tǒng)：人工智能業(yè)務(wù)》（《Expert systems：artificial intelligence in business》）一書。書中闡述了專家系統(tǒng)如何解決問(wèn)題，代表知識(shí)，并得出推論，并介紹了人工智能的具體制度，確定了專家系統(tǒng)的市場(chǎng)。
1986年，出現(xiàn)了第七個(gè)節(jié)點(diǎn)代表――著名的專家系統(tǒng)學(xué)者沃特曼（Waterman DA），他出版了《專家系統(tǒng)指南》一書，該書對(duì)專家系統(tǒng)的概念、組成、建立過(guò)程、建立工具、應(yīng)用領(lǐng)域等做了深入淺出的系統(tǒng)介紹與論述，是當(dāng)時(shí)全面介紹專家研發(fā)與應(yīng)用的經(jīng)典書籍。
20世紀(jì)80年代初，醫(yī)療專家系統(tǒng)占主流，主要原因是它屬于診斷類型系統(tǒng)且容易開發(fā)。80年代中期，出現(xiàn)大量投入商業(yè)化運(yùn)行的專家系統(tǒng)，為各行業(yè)帶來(lái)了顯著的經(jīng)濟(jì)效益。從80年代后期開始，大量新技術(shù)成功運(yùn)用到專家系統(tǒng)之中，使得專家系統(tǒng)得到更廣泛的運(yùn)用。在這期間開發(fā)的專家系統(tǒng)按處理問(wèn)題的類型可以分為：解釋型、預(yù)測(cè)型、診斷型、設(shè)計(jì)型等。應(yīng)用領(lǐng)域擴(kuò)展到農(nóng)業(yè)、商業(yè)、化學(xué)、通信、醫(yī)學(xué)等多個(gè)方面，成為人們常用的解決問(wèn)題的手段之一。
然而，與此同時(shí)，現(xiàn)有的專家系統(tǒng)也暴露出了自身嚴(yán)重的缺陷，使不少計(jì)算機(jī)界的知名學(xué)者對(duì)專家系統(tǒng)產(chǎn)生了懷疑，認(rèn)為專家系統(tǒng)存在的問(wèn)題有以下幾點(diǎn)：（1）專家系統(tǒng)中的知識(shí)多限于經(jīng)驗(yàn)知識(shí)，極少有原理性的知識(shí)，系統(tǒng)沒(méi)有應(yīng)用它們的能力；（2）知識(shí)獲取功能非常弱。為了建造專家系統(tǒng)，必須依賴于專家獲取知識(shí)， 不僅費(fèi)時(shí)， 而且很難獲取完備性和一致性的知識(shí)；（3）求解問(wèn)題的方法比較單一，以推理機(jī)為核心的對(duì)問(wèn)題的求解尚不能反映專家從認(rèn)識(shí)問(wèn)題到解決問(wèn)題的創(chuàng)造性過(guò)程；（4）解釋功能不強(qiáng)［4］。等到學(xué)者們回過(guò)頭重新審視時(shí)，20世紀(jì)90年代的專家系統(tǒng)理論危機(jī)已然爆發(fā)。
3 90年代專家系統(tǒng)向多個(gè)方向發(fā)展
由于20世紀(jì)80年代專家系統(tǒng)研究迅猛發(fā)展，商業(yè)價(jià)值被各行各業(yè)看好，導(dǎo)致90年代大批專家系統(tǒng)從實(shí)驗(yàn)室走出來(lái)，開始了它們的工程化市場(chǎng)化進(jìn)程。從圖1看以看出，在20世紀(jì)90年代，專家系統(tǒng)的相關(guān)論文不增反減，進(jìn)入一個(gè)局部低谷期，這期間以“Expert System/Experts System”為主題詞的論文共7 547篇。本文利用Citespace軟件，設(shè)置參數(shù)為（4，4，20）（4，3，20）（4，4，20），獲取了該時(shí)期論文的引文聚類圖（如圖3所示）。圖2 專家系統(tǒng)1990－2000年的論文引文聚類圖
從圖3中我們可以看出，全圖的節(jié)點(diǎn)比較分散，沒(méi)有形成大的聚類，這表示該階段沒(méi)有形成重點(diǎn)研究方向，也沒(méi)有重大科研成果和標(biāo)志性著作產(chǎn)生，專家系統(tǒng)的市場(chǎng)化進(jìn)程嚴(yán)重牽引了研究者們的注意力，這是專家系統(tǒng)研究陷入低谷期的重要原因。
這段時(shí)間專家系統(tǒng)的研究工作大致分以下幾個(gè)方面：第一個(gè)研究方向依舊是建立在扎德（LA.Zadeh）教授模糊理論上的模糊專家系統(tǒng)，它同樣是該年代專家系統(tǒng)研究的重點(diǎn)方向。
第二個(gè)研究方向是骨架專家系統(tǒng)，代表人物有美國(guó)斯坦福大學(xué)的愛(ài)德華?漢斯?肖特利夫（Shortliff EH）教授。1974年末，MYCIN系統(tǒng)基本建成后，MYCIN的設(shè)計(jì)者們就想到用其它領(lǐng)域的知識(shí)替換關(guān)于感染病學(xué)的知識(shí)，可能會(huì)得到一個(gè)新的專家系統(tǒng)，這種想法導(dǎo)致了EMYCIN骨架系統(tǒng)的產(chǎn)生。EMYCIN的出現(xiàn)大大縮短了專家系統(tǒng)的研制周期，隨后，AGE、OPS5、KEE、KBMS、GESDE等骨架系統(tǒng)應(yīng)運(yùn)而生，它們?cè)?0世紀(jì)90年代專家系統(tǒng)的研究進(jìn)程中，發(fā)揮著重要作用。
第三個(gè)研究方向是故障診斷專家系統(tǒng)，代表人物有美國(guó)麻省理工學(xué)院的蘭德爾?戴維斯（Randall Davis）教授。他于1984年在《人工智能》雜志上發(fā)表了《基于結(jié)構(gòu)和行為的診斷推理 》（《Diagnostic Reasoning Based on Structure and Behavior》）一文，該論文描述了一個(gè)利用知識(shí)結(jié)構(gòu)和行為，在電子電路領(lǐng)域進(jìn)行故障診斷排除的專家系統(tǒng)。之后，故障診斷專家系統(tǒng)在電路與數(shù)字電子設(shè)備、機(jī)電設(shè)備等各個(gè)領(lǐng)域已取得了令人矚目的成就，已成為當(dāng)今世界研究的熱點(diǎn)之一。
第四個(gè)研究方向是基于規(guī)則的專家系統(tǒng)，布魯斯?布坎南（Bruce G.Buchanan）的著作對(duì)基于規(guī)則的專家系統(tǒng)在這個(gè)時(shí)期的發(fā)展仍有著積極的指導(dǎo)作用。多種基于規(guī)則的專家系統(tǒng)進(jìn)入了試驗(yàn)階段。傳統(tǒng)基于規(guī)則的專家系統(tǒng)只是簡(jiǎn)單的聲明性知識(shí)，而目前，規(guī)則的形式開始向產(chǎn)生式規(guī)則轉(zhuǎn)變，并趨向于提供較完善的知識(shí)庫(kù)建立和管理功能。
第五個(gè)研究方向是知識(shí)工程在專家系統(tǒng)中的運(yùn)用。代表人物是美國(guó)斯坦福大學(xué)的克蘭西教授（Clancy W J），他于1985年在《人工智能》雜志上發(fā)表了重要論文《啟發(fā)式分類》（《Heuristis classification》），啟發(fā)式分類即對(duì)未知領(lǐng)域情況的類的識(shí)別過(guò)程。它是人類思維解決問(wèn)題的重要方法，在人工智能、專家系統(tǒng)中可常用啟發(fā)式設(shè)計(jì)計(jì)算機(jī)程序，模擬人類解決問(wèn)題的思維活動(dòng)。
第六個(gè)研究方向是機(jī)器學(xué)習(xí)在專家系統(tǒng)中的運(yùn)用。代表人物是機(jī)器學(xué)習(xí)領(lǐng)域前輩、澳洲悉尼大學(xué)著名教授John Ross Quinlan。他于1986年在《機(jī)器學(xué)習(xí)》（《Mach.Learn》）雜志上發(fā)表《決策樹算法》（《Induction of Decision Trees》）一文，文中他詳細(xì)描述了決策樹算法的代表――ID3算法。之后，有大量學(xué)者圍繞該算法進(jìn)行了廣泛的研究，并提出多種改進(jìn)算法，由于決策樹的各類算法各有優(yōu)缺點(diǎn)，在專家系統(tǒng)的實(shí)際應(yīng)用中，必須根據(jù)數(shù)據(jù)類型的特點(diǎn)及數(shù)據(jù)集的大小，選擇合適的算法。
第七個(gè)研究方向是神經(jīng)網(wǎng)絡(luò)專家系統(tǒng)，代表人物有人工智能專家Stephan I.Gallant和美國(guó)加利福尼業(yè)大學(xué)教授巴特?卡斯科（Bart Kosko）。Gallant于1988年在《ACM的通信》上發(fā)表了《連接主義專家系統(tǒng)》（《Connectionist expert systems》）一文，文中講述Gallant 設(shè)計(jì)了一個(gè)連接主義專家系統(tǒng)（Connectionist expert system），其知識(shí)庫(kù)是由一個(gè)神經(jīng)網(wǎng)絡(luò)實(shí)現(xiàn)的（即神經(jīng)網(wǎng)絡(luò)知識(shí)獲取），開創(chuàng)了神經(jīng)網(wǎng)絡(luò)與專家系統(tǒng)相結(jié)合的先例。
第八個(gè)研究方向是遺傳算法在專家系統(tǒng)中的運(yùn)用。代表人物是遺傳算法領(lǐng)域著名學(xué)者、美國(guó)伊利諾伊大學(xué)David Goldberg教授和人工智能專家L.Davis。1989年，Goldberg出版了專著《搜索、優(yōu)化和機(jī)器學(xué)習(xí)中的遺傳算法》，該書系統(tǒng)總結(jié)了遺傳算法的主要研究成果，全面而完整地論述了遺傳算法的基本原理及其應(yīng)用；1991年，Davis編輯出版了《遺傳算法手冊(cè)》，書中包含了遺傳算法在科學(xué)計(jì)算、工程技術(shù)和社會(huì)經(jīng)濟(jì)中的大量應(yīng)用實(shí)例，該書為推廣和普及遺傳算法的應(yīng)用起到了重要的指導(dǎo)作用。這些都推動(dòng)了基于遺傳算法的專家系統(tǒng)的研發(fā)推廣。
第九個(gè)研究方向是決策支持系統(tǒng)在專家系統(tǒng)中的運(yùn)用，代表人物是美國(guó)加利福尼亞大學(xué)伯克利分校教授埃弗雷姆?特班（Efraim Turban）。他于1990年出版了《決策支持和專家系統(tǒng)的管理支持系統(tǒng)》（《Decision support and expert systems:management support systems》）一書。20世紀(jì)80年代末90年代初，決策支持系統(tǒng)開始與專家系統(tǒng)相結(jié)合，形成智能決策支持系統(tǒng)，該系統(tǒng)充分做到了定性分析和定量分析的有機(jī)結(jié)合，將解決問(wèn)題的范圍和能力提高到一個(gè)新的層次。
第十個(gè)研究方向是各種理論知識(shí)在專家系統(tǒng)中的綜合運(yùn)用，代表人物是美國(guó)加利福尼業(yè)大學(xué)教授巴特?卡斯科（Bart Kosko）和美國(guó)伊利諾伊州研究所教授Abdul-Rahman K.H。卡斯科（Kosko）于1992年出版《神經(jīng)網(wǎng)絡(luò)和模糊系統(tǒng)：一個(gè)擁有機(jī)器智能的動(dòng)力系統(tǒng)方法》（《Neural networks and fuzzy systems:a dynamical systems approach to machine intelligence》）一書，這是第一本將神經(jīng)網(wǎng)絡(luò)和模糊系統(tǒng)結(jié)合起來(lái)的讀本，也是神經(jīng)網(wǎng)絡(luò)與模糊理論綜合應(yīng)用于專家系統(tǒng)建設(shè)的經(jīng)典著作；Abdul-Rahman K.H教授于1995年，在美國(guó)電氣和電子工程師協(xié)會(huì)的《電力系統(tǒng)及自動(dòng)化》（《Transactions on Power Systems》）會(huì)議刊上發(fā)表了《人工智能模糊無(wú)功負(fù)荷的最優(yōu)VAR控制方法 》（《AI approach to optimal VAR control with fuzzy reactive loads》）一文，論文提出了一個(gè)解決無(wú)功功率（VAR）控制問(wèn)題，這個(gè)方法包含了專家系統(tǒng)、模糊集理論和人工神經(jīng)網(wǎng)絡(luò)的重要知識(shí)。
雖然專家系統(tǒng)大量建造，但投入實(shí)際運(yùn)行的專家系統(tǒng)并不多，且效率較低，問(wèn)題求解能力有待進(jìn)一步提高。原因之一就是專家系統(tǒng)主要是模擬某一領(lǐng)域中求解特定問(wèn)題的專家的能力，而在模擬人類專家協(xié)作求解方面很少或幾乎沒(méi)有做什么工作。然而在現(xiàn)實(shí)世界中，協(xié)作求解具有普遍性，針對(duì)特定領(lǐng)域、特定問(wèn)題的求解僅僅具有特殊性，專家系統(tǒng)雖然在模擬人類專家某一特定領(lǐng)域知識(shí)方面取得了成功，但它仍然不能或難以解決現(xiàn)實(shí)世界中的問(wèn)題。其次，開發(fā)的專家系統(tǒng)的規(guī)模越來(lái)越大，并且十分復(fù)雜。這樣就要求將大型專家系統(tǒng)的開發(fā)變成若干小的、相對(duì)獨(dú)立的專家系統(tǒng)來(lái)開發(fā)，而且需要將許多不同領(lǐng)域的專家系統(tǒng)聯(lián)合起來(lái)進(jìn)行協(xié)作求解。然而，與此相關(guān)的分布式人工智能理論和實(shí)用技術(shù)尚處在科研階段。只有分布式系統(tǒng)協(xié)作求解問(wèn)題得以解決，才能克服由于單個(gè)專家系統(tǒng)知識(shí)的有限性和問(wèn)題求解方法的單一性等導(dǎo)致系統(tǒng)的“脆弱性”，也才能提高系統(tǒng)的可靠性，并且在靈活性、并行性、速度等方面帶來(lái)明顯的效益［5］。
4 21世紀(jì)專家系統(tǒng)進(jìn)入穩(wěn)定發(fā)展時(shí)期
進(jìn)入21世紀(jì)，專家系統(tǒng)開始緩慢發(fā)展，這期間以“Expert System/Experts System”為主題詞的論文共5 964篇。本文利用Citespace軟件，設(shè)置參數(shù)為（6，6，20）（5，5，20）（5，5，20），獲取了該時(shí)期論文的引文聚類圖（如圖4所示）。圖4 專家系統(tǒng)2000－2010年的論文引文聚類圖
這個(gè)時(shí)期專家系統(tǒng)有3個(gè)主要研究方向：第一個(gè)是研究方向是節(jié)點(diǎn)明顯的基于模糊邏輯的專家系統(tǒng)研究方向。90年代以來(lái)，模糊控制與專家系統(tǒng)技術(shù)相結(jié)合，進(jìn)一步提高了模糊控制器的智能水平。基于模糊邏輯的專家系統(tǒng)有以下優(yōu)點(diǎn)：一是具有專家水平的專門知識(shí)，能表現(xiàn)專家技能和高度的技巧以及有足夠的魯棒性（即健壯性）；二是能進(jìn)行有效的推理，能夠運(yùn)用人類專家的經(jīng)驗(yàn)和知識(shí)進(jìn)行啟發(fā)性的搜索和試探性的推理；三是具有靈活性和透明性。
第二個(gè)是研究方向是Rete模式匹配算法在專家系統(tǒng)中的應(yīng)用，代表人物是美國(guó)卡內(nèi)基―梅隆大學(xué)計(jì)算機(jī)科學(xué)系的Charles L.Forgy教授，1979年，他首次提出Rete算法。專家系統(tǒng)工具中一個(gè)核心部分是推理機(jī)，Rete算法能利用推理機(jī)的“時(shí)間冗余”特性和規(guī)則結(jié)構(gòu)的相似性，并通過(guò)保存中間運(yùn)算結(jié)果的方法來(lái)提高推理的效率。1982年，他在《人工智能》雜志上發(fā)表《Rete算法：許多模式／多對(duì)象的模式匹配問(wèn)題的一個(gè)快速算法》（《Rete:A Fast Algorithm for the Many Pattern/Many Object Pattern Match Problem》）一文，該文解釋了基本算法的概念，介紹了詳細(xì)的算法，描述了模式和適當(dāng)?shù)膶?duì)象交涉算法，并說(shuō)明了模式匹配的執(zhí)行操作。
第三個(gè)是研究方向是專家系統(tǒng)在電力系統(tǒng)中的運(yùn)用。世界各國(guó)的專家們開始熱衷于在電力生產(chǎn)的各個(gè)環(huán)節(jié)使用專家系統(tǒng)，代表人物有日本的福井賢、T.Sakaguchi、印度的Srinivasan D、美國(guó)伊利諾伊州研究所的Abdul-Rahman K.H、希臘雅典國(guó)立技術(shù)大學(xué)的Protopapas C.A、和中國(guó)的羅旭，他們?cè)诿绹?guó)電氣和電子工程師協(xié)會(huì)的《電力傳輸》（《IEEE transactions on power delivery）會(huì)議刊及《電源設(shè)備系統(tǒng)》會(huì)議刊（《On Power Apparatus and Systems》）上發(fā)表了多篇有影響力的論文，內(nèi)容涉及系統(tǒng)恢復(fù)、電力需求預(yù)測(cè)、變電站故障診斷和報(bào)警處理等多方面。
這十年間，專家系統(tǒng)的研究不再滿足于用現(xiàn)有各種模型與專家系統(tǒng)進(jìn)行簡(jiǎn)單結(jié)合，形成基于某種模型的專家系統(tǒng)的固有模式。研究者們不斷探索更方便、更有效的方法，來(lái)解決困擾專家系統(tǒng)的知識(shí)獲取瓶頸、匹配沖突、組合爆炸等問(wèn)題，而這也推動(dòng)了研究不斷向深層次、新方向發(fā)展。但是，由于專家系統(tǒng)應(yīng)用的時(shí)間長(zhǎng)、領(lǐng)域廣，他們?cè)庥龅钠款i問(wèn)題一時(shí)得不到有效解決，導(dǎo)致了這一時(shí)期末，專家系統(tǒng)研究呈現(xiàn)出暫時(shí)的下滑現(xiàn)象。
5 專家系統(tǒng)發(fā)展趨勢(shì)分析
圖一發(fā)展曲線上第二個(gè)時(shí)間節(jié)點(diǎn)是1992年，從該年起專家系統(tǒng)相關(guān)論文呈下降趨勢(shì)，然后在2002年又開始緩慢增長(zhǎng)，近一年多來(lái)又開始下降，這標(biāo)志著專家系統(tǒng)研究在布滿荊棘的道路上前行，前景是光明的，但道路是曲折的。本文以5年為一個(gè)單位，統(tǒng)計(jì)了1990－2009年20年期間專家系統(tǒng)相關(guān)論文中高頻詞的變化情況，如表1所示，從該表可以獲得這個(gè)時(shí)期專家系統(tǒng)研究的一些特點(diǎn)。
（1）在1990-1999年期間，人工智能出現(xiàn)新的研究，由于網(wǎng)絡(luò)技術(shù)特別是國(guó)際互連網(wǎng)技術(shù)發(fā)展，人工智能開始由單個(gè)智能主體研究轉(zhuǎn)向基于網(wǎng)絡(luò)環(huán)境下的分布式人工智能研究，使人工智能更加實(shí)用，這給專家系統(tǒng)帶來(lái)了發(fā)展的希望。正因?yàn)槿绱耍覀儚脑~頻上可以看出，人工智能（artificial intelligence）一詞在這十年一直位居前兩位，在專家系統(tǒng)研究中處于主導(dǎo)地位，而與其相關(guān)的知識(shí)表示（knowledge representation）、知識(shí)獲取(knowledge acquisition)等，也成為了學(xué)者們研究的重點(diǎn)方向。
（2）該時(shí)期的第二個(gè)特點(diǎn)是神經(jīng)網(wǎng)絡(luò)研究的復(fù)蘇。神經(jīng)網(wǎng)絡(luò)是通過(guò)模擬人腦的結(jié)構(gòu)和工作模式，使機(jī)器具有類似人類的智能，如機(jī)器學(xué)習(xí)、知識(shí)獲取、專家系統(tǒng)等。我們從詞頻上可以看出神經(jīng)網(wǎng)絡(luò)（neural network）一詞得以快速增長(zhǎng)，1995年時(shí)位列第一，進(jìn)入21世紀(jì)也是穩(wěn)居第二位，神經(jīng)網(wǎng)絡(luò)很好地解決了專家系統(tǒng)中知識(shí)獲取的瓶頸問(wèn)題，能使專家系統(tǒng)具有自學(xué)習(xí)能力，它的出現(xiàn)為專家系統(tǒng)提供了一種新的解決途徑［6］，同時(shí)也顯示出他獨(dú)有的生機(jī)與活力。
（3）該時(shí)期是模糊邏輯的發(fā)展時(shí)期。模糊理論發(fā)展至今已接近三十余年，應(yīng)用范圍非常廣泛，它與專家系統(tǒng)相結(jié)合，在故障診斷、自然語(yǔ)言處理、自動(dòng)翻譯、地震預(yù)測(cè)、工業(yè)設(shè)計(jì)等方面取得了眾多成果。我們從詞頻上可以看出，模糊邏輯（fuzzy logic）一詞，除在1990－1994年期間位居第六位外，之后都位居前三甲，2000-2004年期間更是位列第一。模糊控制與專家系統(tǒng)技術(shù)相結(jié)合，進(jìn)一步提高了模糊控制器智能水平，這種控制方法既保持了基于規(guī)則的方法的價(jià)值和用模糊集處理帶來(lái)的靈活性，同時(shí)把專家系統(tǒng)技術(shù)的表達(dá)與利用知識(shí)的長(zhǎng)處結(jié)合起來(lái)，能處理更廣泛的控制問(wèn)題。
（4）故障診斷成為專家系統(tǒng)研究與應(yīng)用的又一重要領(lǐng)域。故障診斷專家系統(tǒng)的發(fā)展起始于20世紀(jì)70年代末,雖然時(shí)間不長(zhǎng),但在電路與數(shù)字電子設(shè)備、機(jī)電設(shè)備等各個(gè)領(lǐng)域已取得了令人矚目的成就,已成為當(dāng)今世界研究的熱點(diǎn)之一。這從高頻詞分布可以開出，故障診斷（fault diagnosis）從1995-1999年間的最后一位攀升至2005-2009年間的第一位，足見其強(qiáng)大的生命力。在專家系統(tǒng)己有較深厚基礎(chǔ)的國(guó)家中，機(jī)械、電子設(shè)備的故障診斷專家系統(tǒng)已基本完成了研究和試驗(yàn)的階段，開始進(jìn)入廣泛應(yīng)用。
（5）遺傳算法的應(yīng)用逐漸增多。20世紀(jì)90年代，遺傳算法迎來(lái)了發(fā)展時(shí)期，無(wú)論是理論研究還是應(yīng)用研究都成了十分熱門的課題。尤其是遺傳算法的應(yīng)用研究顯得格外活躍，不但應(yīng)用領(lǐng)域擴(kuò)大，而且利用遺傳算法進(jìn)行優(yōu)化和規(guī)則學(xué)習(xí)的能力也顯著提高。進(jìn)入21世紀(jì)，遺傳算法的應(yīng)用研究已從初期的組合優(yōu)化求解擴(kuò)展到了許多更新、更工程化的應(yīng)用方面。這在高頻詞分布中可以看出，以2000作為臨界點(diǎn)，遺傳算法（genetic algorithms）從20世紀(jì)90年代的10名之后，到位于高頻詞前六強(qiáng)之中，充分反映出它發(fā)展的良好勢(shì)頭。
6 小 結(jié)
專家系統(tǒng)是20世紀(jì)下半葉發(fā)展起來(lái)的重大技術(shù)之一，它不僅是高技術(shù)的標(biāo)志，而且有著重大的經(jīng)濟(jì)效益。“知識(shí)工程之父”E.Feignbaum在對(duì)世界許多國(guó)家和地區(qū)的專家系統(tǒng)應(yīng)用情況進(jìn)行調(diào)查后指出：幾乎所有的ES都至少將人的工作效率提高10倍，有的能提高100倍，甚至300倍［7］。
專家系統(tǒng)技術(shù)能夠使專家的專長(zhǎng)不受時(shí)間和空間的限制，以便推廣稀缺的專家知識(shí)和經(jīng)驗(yàn)；同時(shí)，專家系統(tǒng)能促進(jìn)各領(lǐng)域的發(fā)展，是各領(lǐng)域?qū)＜覍I(yè)知識(shí)和經(jīng)驗(yàn)的總結(jié)和提煉。
專家系統(tǒng)發(fā)展的近期目標(biāo)，是建造能用于代替人類高級(jí)腦力勞動(dòng)的專家系統(tǒng)；遠(yuǎn)期目標(biāo)是探究人類智能和機(jī)器智能的基本原理，研究用自動(dòng)機(jī)模擬人類的思維過(guò)程和智能行為，這幾乎涉及自然科學(xué)和社會(huì)科學(xué)的所有學(xué)科，遠(yuǎn)遠(yuǎn)超出了計(jì)算機(jī)科學(xué)的范疇。
隨著人工智能應(yīng)用方法的日漸成熟，專家系統(tǒng)的應(yīng)用領(lǐng)域也不斷擴(kuò)大。有人類活動(dòng)的地方，必將有智能技術(shù)包括專家系統(tǒng)的應(yīng)用，專家系統(tǒng)將成為21世紀(jì)人類進(jìn)行智能管理與決策的工具與助手。
參考文獻(xiàn)
［1］百度百科［EB］.http:∥baike.省略/view/2130.htm．
［2］黃可鳴.專家系統(tǒng)二十年［J］.計(jì)算機(jī)科學(xué)，1986，（4）：26-37.
［3］路耀華.思維模擬與知識(shí)工程［M］.北京：清華大學(xué)出版社，1997．
［4］趙致琢.專家系統(tǒng)研究［J］.貴州大學(xué)學(xué)報(bào)：自然科學(xué)版，1990，（6）：40-48.
［5］鄒光宇.專家系統(tǒng)發(fā)展現(xiàn)狀及其應(yīng)用前景［J］.電力勘測(cè)，1994，（3）：21-26.
論文摘要： 從現(xiàn)有安全設(shè)施來(lái)看，TDCS網(wǎng)絡(luò)系統(tǒng)安全體系初步形成。但是，隨著計(jì)算機(jī)網(wǎng)絡(luò)的日益普及，各種安全威脅和計(jì)算機(jī)病毒也隨之而來(lái)。現(xiàn)有的網(wǎng)絡(luò)安全系統(tǒng)雖然起到一定的防護(hù)作用，但并不能完全解決整個(gè)骨干網(wǎng)絡(luò)的系統(tǒng)安全問(wèn)題。因此，擬采用基于遺傳算法和神經(jīng)網(wǎng)絡(luò)的入侵檢測(cè)技術(shù)，結(jié)合遺傳算法和神經(jīng)網(wǎng)絡(luò)各自的優(yōu)點(diǎn)，加強(qiáng)對(duì)TDCS網(wǎng)絡(luò)的監(jiān)視和防護(hù)。
1 TDCS網(wǎng)絡(luò)安全狀況
1.1 TDCS網(wǎng)絡(luò)安全現(xiàn)狀
TDCS（TrainOperation Dispatching Command System）是覆蓋全路的列車調(diào)度指揮管理系統(tǒng)，分為鐵道部、鐵路局和車站三級(jí)建設(shè)，能及時(shí)、準(zhǔn)確地為全路各級(jí)調(diào)度指揮管理人員提供現(xiàn)代化的調(diào)度指揮手段和平臺(tái)，是鐵路運(yùn)輸調(diào)度指揮現(xiàn)代化建設(shè)的標(biāo)志。但是，隨著計(jì)算機(jī)網(wǎng)絡(luò)的日益普及，各種安全威脅和計(jì)算機(jī)病毒也隨之而來(lái)，這就導(dǎo)致TDCS網(wǎng)絡(luò)存在著安全隱患。
1.2 TDCS網(wǎng)絡(luò)安全存在的問(wèn)題
在TDCS網(wǎng)絡(luò)中主要存在著以下幾方面安全問(wèn)題：1）間接來(lái)自于互聯(lián)網(wǎng)的病毒威脅；2）操作系統(tǒng)的安全威脅；3）應(yīng)用軟件的安全威脅；4）計(jì)算機(jī)設(shè)置的安全隱患；5）實(shí)時(shí)監(jiān)控能力弱。
2 TDCS網(wǎng)絡(luò)安全防護(hù)
2.1 TDCS網(wǎng)絡(luò)目前采取的安全防護(hù)措施
針對(duì)TDCS網(wǎng)絡(luò)存在的安全問(wèn)題，結(jié)合各種技術(shù)和方法，目前全路系統(tǒng)信息安全防護(hù)體系采取的措施有：
1）防火墻系統(tǒng)。防火墻技術(shù)是實(shí)現(xiàn)子網(wǎng)邊界安全的重要技術(shù)。首先路由器將對(duì)網(wǎng)絡(luò)層安全進(jìn)行初步保證，但路由器的訪問(wèn)控制列表只能作為防火墻系統(tǒng)的一個(gè)重要補(bǔ)充，只能通過(guò)防火墻系統(tǒng)來(lái)實(shí)現(xiàn)復(fù)雜的安全控制。
2）身份認(rèn)證系統(tǒng)。由于TDCS人員結(jié)構(gòu)復(fù)雜，用戶眾多，安全意識(shí)參差不齊，所以用戶的工作內(nèi)容也不盡相同，對(duì)于如此重要的系統(tǒng)，目前采用的以靜態(tài)密碼為主的身份認(rèn)證系統(tǒng)帶來(lái)的安全威脅是非常嚴(yán)重的，會(huì)造成比較大的安全風(fēng)險(xiǎn)。為了解決此類安全隱患，實(shí)用動(dòng)態(tài)口令對(duì)TDCS用戶進(jìn)行身份認(rèn)證是非常必要的。
3）網(wǎng)絡(luò)防病毒系統(tǒng)。根據(jù)對(duì)病毒來(lái)源的分析，TDCS網(wǎng)絡(luò)防病毒系統(tǒng)主要體現(xiàn)在以下三個(gè)方面：第一，防病毒集中統(tǒng)一管理，就是在鐵路局內(nèi)部安裝防病毒軟件管理系統(tǒng)，對(duì)所有客戶端防病毒軟件進(jìn)行統(tǒng)一管理；第二，服務(wù)器病毒防護(hù)，就是對(duì)各種服務(wù)器進(jìn)行病毒掃描和清除；第三，桌面防毒防護(hù)，就是對(duì)各項(xiàng)桌面系統(tǒng)軟件進(jìn)行病毒掃描和清楚。
4）入侵檢測(cè)系統(tǒng)。入侵檢測(cè)的主要功能是控制對(duì)網(wǎng)絡(luò)的非法控制，通過(guò)監(jiān)視、限制通過(guò)網(wǎng)絡(luò)的數(shù)據(jù)流，防止外對(duì)內(nèi)、內(nèi)對(duì)外的非法訪問(wèn)，隔離內(nèi)部網(wǎng)和外部網(wǎng)，為監(jiān)視TDCS局域網(wǎng)安全提供便利。
5）安全漏洞評(píng)估系統(tǒng)。
2.2 TDCS網(wǎng)絡(luò)采用入侵檢測(cè)進(jìn)行防護(hù)的好處
通過(guò)以上介紹，我們不難發(fā)現(xiàn)，在TDCS網(wǎng)絡(luò)安全體系中，入侵檢測(cè)系統(tǒng)是唯一一個(gè)通過(guò)數(shù)據(jù)和行為模式判斷其是否有效的系統(tǒng)。
形象地說(shuō)，入侵檢測(cè)系統(tǒng)就是網(wǎng)絡(luò)攝像機(jī)，能夠捕獲并記錄網(wǎng)絡(luò)上的所有數(shù)據(jù)，同時(shí)它也是智能攝像機(jī)，能夠分析網(wǎng)絡(luò)數(shù)據(jù)并提煉出可疑的、異常的網(wǎng)絡(luò)數(shù)據(jù)，它還是X光攝像機(jī)，能夠穿透一些巧妙的偽裝，抓住實(shí)際的內(nèi)容。此外，它還是保安員的攝像機(jī)，能夠?qū)θ肭中袨樽詣?dòng)地進(jìn)行反擊，如阻斷連接。
在TDCS網(wǎng)絡(luò)中引入入侵檢測(cè)技術(shù)，主要是實(shí)現(xiàn)對(duì)網(wǎng)絡(luò)的非法控制，通過(guò)監(jiān)視、限制通過(guò)網(wǎng)絡(luò)的數(shù)據(jù)流，給網(wǎng)絡(luò)系統(tǒng)提供對(duì)外部攻擊、內(nèi)部攻擊和誤操作的安全保護(hù)，為監(jiān)視TDCS局域網(wǎng)安全提供更多便利。
3 基于遺傳算法和神經(jīng)網(wǎng)絡(luò)的入侵檢測(cè)系統(tǒng)
3.1 傳統(tǒng)的IDS存在的問(wèn)題
1）準(zhǔn)確性差。傳統(tǒng)的統(tǒng)計(jì)方法需要依賴于一些假設(shè)，如審計(jì)數(shù)據(jù)（或用戶行為）的分布符合高斯分布，實(shí)際上用戶行為具有隨機(jī)性，這些假設(shè)有時(shí)可能無(wú)效，從而導(dǎo)致較高的錯(cuò)誤率。
2）靈活性差。傳統(tǒng)的IDS對(duì)攻擊特征的刻畫只能是某些固定的序列，但現(xiàn)實(shí)中的入侵者利用的手段往往是有變化的，而要在入侵模式庫(kù)中反映出所有可能的變化是不可能的。
3）適應(yīng)性差。入侵者的攻擊方法是在不斷發(fā)展的，但傳統(tǒng)的入侵檢測(cè)系統(tǒng)無(wú)法有效地預(yù)測(cè)和識(shí)別新的攻擊方法，使系統(tǒng)的適應(yīng)性受到限制。
3.2 采用基于遺傳算法的神經(jīng)網(wǎng)絡(luò)IDS的好處
將遺傳算法全局搜索最優(yōu)和傳統(tǒng)神經(jīng)網(wǎng)絡(luò)局部尋優(yōu)結(jié)合起來(lái)，取長(zhǎng)補(bǔ)短，既可以減小遺傳算法的搜索空間、提高搜索效率，又可以較容易地收斂到最優(yōu)解，為求解多目標(biāo)優(yōu)化問(wèn)題提供了新的策略。
4 結(jié)束語(yǔ)
目前在TDCS網(wǎng)絡(luò)安全系統(tǒng)中采用的IDS一般都是基于神經(jīng)網(wǎng)絡(luò)技術(shù)的，由于神經(jīng)網(wǎng)絡(luò)的設(shè)計(jì)主要依據(jù)設(shè)計(jì)者的經(jīng)驗(yàn)在大樣本空間反復(fù)實(shí)驗(yàn)來(lái)進(jìn)行選取，尚無(wú)理論上的指導(dǎo)，因此在神經(jīng)網(wǎng)絡(luò)的初始連接權(quán)以及網(wǎng)絡(luò)結(jié)構(gòu)的選擇上具有很大的隨機(jī)性，很難選取具有全局性的初始點(diǎn)，因而網(wǎng)絡(luò)求得全局最優(yōu)的可能性小。本文提出的技術(shù)很好的克服了這些缺點(diǎn)，較好地解決了問(wèn)題。
參考文獻(xiàn)：
[1]鐵道部運(yùn)輸局，鐵路列車調(diào)度指揮系統(tǒng)，北京：中國(guó)鐵道出版社，2006.10.
[2]高麗，鐵路站段計(jì)算機(jī)網(wǎng)絡(luò)故障解決方法[J].鐵路計(jì)算機(jī)應(yīng)用，2006，13（9）：13-16.
[3]周明孫、樹棟，遺傳算法原理及應(yīng)用，北京：國(guó)防工業(yè)出版社，1999.
[關(guān)鍵詞]拉鏈檢測(cè)；背光照明；圖像分割；遺傳算法；
中圖分類號(hào)：TB 文獻(xiàn)標(biāo)識(shí)碼：A 文章編號(hào)：1009-914X（2015）23-0197-01
引言
目前拉鏈生產(chǎn)企業(yè)一般采用人工方法進(jìn)行檢測(cè)，這種檢測(cè)方法，效率低、成本高、勞動(dòng)強(qiáng)度大，拉鏈容易出現(xiàn)多齒、少齒、鏈齒分布不均等缺陷。本文提出一種新的自動(dòng)檢測(cè)拉鏈?zhǔn)欠翊嬖诙帻X、少齒缺陷的拉鏈智能檢測(cè)方案。該方案采用白光LED背光照明技術(shù)使得采集的圖像背景與拉鏈呈現(xiàn)對(duì)比明顯的兩色，采用中值濾波算法濾去干擾噪聲，通過(guò)改進(jìn)的Otsu法獲取拉鏈圖像閾值，然后進(jìn)行圖像二值化分割，并對(duì)處理后的圖像采用拉鏈間距的判別方法進(jìn)行識(shí)別判斷。
1 光源照明技術(shù)
圖像采集處理系統(tǒng)中常用的光源有白熾燈、鹵素?zé)簟⒌怄u燈、氣體放電燈和發(fā)光二極管[1] 等，照明方式有直接照明、背光照明、暗視場(chǎng)照明、散射照明和同軸照明等。光源與照明方式的配合不僅要照亮物體，還要盡可能地突出物體特征量，使物體待檢測(cè)區(qū)域與其它區(qū)域產(chǎn)生明顯的區(qū)別[2]，以便特征的提取和判斷。通過(guò)對(duì)多種光源及照明方式的實(shí)驗(yàn)，本方案采用白色LED背光照明，其具有拉鏈背景均勻單一，拉鏈與背景呈現(xiàn)分明的兩色，拉鏈輪廓清晰等優(yōu)點(diǎn)，并且不存在直接照明產(chǎn)生的陰影及金屬拉鏈反光等問(wèn)題。
2 圖像處理算法
2.1 灰度變換
彩色圖像包含大量的顏色信息，直接對(duì)真彩圖像進(jìn)行處理會(huì)耗費(fèi)較多的時(shí)間。為了提高圖像處理速度，同時(shí)又不損失感興趣區(qū)域的細(xì)節(jié)信息，通常將彩色圖像變換為灰度圖像。
2.2 圖像濾波
在拉鏈圖像采集的過(guò)程中，由于攝像頭、光源、電磁干擾、機(jī)械振動(dòng)等影響，采集的拉鏈圖像存在著噪聲干擾。中值濾波可以在去除點(diǎn)、線噪聲的同時(shí)很好地保護(hù)圖像的邊緣，對(duì)抑制圖像中的脈沖噪聲和椒鹽噪聲特別有效[3]，拉鏈圖像中的噪聲主要是椒鹽噪聲，本文案采用中值濾波法對(duì)灰度化后的拉鏈圖像進(jìn)行濾波處理。
2.3 基于遺傳算法的Otsu閾值分割
Otsu閾值分割法不需要先驗(yàn)知識(shí)，且算法簡(jiǎn)單、分割質(zhì)量好等優(yōu)點(diǎn)[4]，非常適合于目標(biāo)與背景兩類的圖像分割問(wèn)題，但其求解過(guò)程計(jì)算量大，本文將遺傳算法引入Otsu閾值求解過(guò)程中，利用遺傳算法所具有的快速尋優(yōu)的特點(diǎn)，以縮短計(jì)算時(shí)間。
3 檢測(cè)方案
在密閉暗箱中采用白光LED背光照明技術(shù)對(duì)拉鏈圖像進(jìn)行采集，采集的拉鏈圖像拉鏈為黑色、背景為白色，拉鏈輪廓清晰，對(duì)比度高。為了驗(yàn)證該方案的檢測(cè)效果，在實(shí)驗(yàn)過(guò)程中采用了兩幅拉鏈圖像：一幅正品拉鏈圖像，一幅次品拉鏈圖像，如圖1所示。為提高處理速度，方便拉鏈圖像的二值化處理，采用加權(quán)平均值法對(duì)采集的拉鏈圖像進(jìn)行灰度化處理。由于加權(quán)平均值算法中的權(quán)值都是浮點(diǎn)數(shù)，采用加權(quán)平均值法處理速度較慢，對(duì)此提出了改進(jìn)算法。
對(duì)分割后的二值圖像從左至右進(jìn)行掃描，統(tǒng)計(jì)拉鏈間距的個(gè)數(shù)，并記錄各個(gè)間距的值，計(jì)算鏈齒間距與鏈齒間距均值的誤差和相鄰鏈齒間距的誤差，如果誤差都在一定范圍內(nèi)則認(rèn)為拉鏈?zhǔn)钦罚駝t就是次品。該方案采用了首次閾值計(jì)算采樣，即計(jì)算第一幀采集的拉鏈圖像的閾值并保存為標(biāo)準(zhǔn)閾值，后續(xù)圖像分割只需要調(diào)用該閾值即可，減少了系統(tǒng)處理時(shí)間。
4 試驗(yàn)結(jié)果分析
整個(gè)檢測(cè)方案在HHARM2410開發(fā)平臺(tái)上予以實(shí)現(xiàn)，實(shí)驗(yàn)表明該方案可以準(zhǔn)確地檢測(cè)出拉鏈多齒、少齒、鏈齒分布不均的缺陷，從而判斷出正品拉鏈和次品拉鏈。
圖2是對(duì)圖1所示的拉鏈采用白光LED背光照明采集得到的拉鏈圖像，從采集的效果可以看出無(wú)論什么材質(zhì)或顏色的拉鏈采用背光照明后，拉鏈都是黑色的，拉鏈和背景對(duì)比分明、輪廓清晰，不存在反光和暗影等缺陷，使得該方案具有較強(qiáng)的通用性，能夠?qū)Χ喾N類型的拉鏈進(jìn)行處理。
采用改進(jìn)的加權(quán)平均值法對(duì)圖2進(jìn)行灰度化處理，并采用中值濾波算法對(duì)灰度化圖像進(jìn)行濾波處理后的圖像如圖3所示，從處理結(jié)果可以看出中值濾波法很好地濾除了拉鏈圖像中的椒鹽噪聲。
該實(shí)驗(yàn)中分別采用Otsu法和基于遺傳算的改進(jìn)Otsu法對(duì)濾波后的灰度圖像進(jìn)行閾值求取，表1給出了用兩種方法求取的閾值和所用的時(shí)間，從表可以看出兩種算法求得閾值相同，但引入遺傳算法后的改進(jìn)Otsu法處理時(shí)間有所縮短，系統(tǒng)的處理速度得到提高，本文采用基于GA的Otsu法對(duì)拉鏈圖像進(jìn)行分割，分割后的二值圖像如圖4所示，由分割結(jié)果可以看出目標(biāo)與背景錯(cuò)分幾率低，邊緣清晰，噪聲少。
5 結(jié)論
實(shí)驗(yàn)結(jié)果表明該方案能夠?qū)Χ喾N拉鏈自動(dòng)提出特征并進(jìn)行處理判斷，可以準(zhǔn)確地檢測(cè)拉鏈多齒、少齒、鏈齒分布不均的缺陷，具有較高的處理速度和通用性。
參考文獻(xiàn)
[1] 高峰. 圖像處理技術(shù)在啤酒瓶在線檢測(cè)系統(tǒng)中的應(yīng)用[D]. 西安工業(yè)大學(xué)碩士學(xué)位論文. 2011.
[2] 劉圣. 工業(yè)圖像檢測(cè)系統(tǒng)關(guān)鍵技術(shù)的研究及應(yīng)用[D]. 上海交通大學(xué)碩士學(xué)位論文. 2007.
關(guān)鍵詞：Java 實(shí)踐教學(xué) 實(shí)踐能力 創(chuàng)新能力 教學(xué)方法
文章編號(hào)：1672-5913(2011)18-0012-04 中圖分類號(hào)：G642 文獻(xiàn)標(biāo)識(shí)碼：B
基金項(xiàng)目：甘肅政法學(xué)院青年科研基金項(xiàng)目(GZF2010XQNLW53)。
Java課程是應(yīng)用實(shí)踐性的課程。長(zhǎng)期教學(xué)經(jīng)驗(yàn)說(shuō)明，單純的“理論+程序演示”的理論教學(xué)方法以及 “學(xué)生自主實(shí)驗(yàn)+教師隨堂指導(dǎo)”的實(shí)驗(yàn)教學(xué)方法存在著一些缺陷，表現(xiàn)為學(xué)生創(chuàng)新能力的欠缺和自主實(shí)踐能力較差。
教學(xué)過(guò)程是一個(gè)系統(tǒng)過(guò)程，涉及到該門課程的所有教學(xué)和實(shí)踐環(huán)節(jié)，其中任意一個(gè)環(huán)節(jié)的薄弱都會(huì)導(dǎo)致學(xué)生實(shí)踐和創(chuàng)新能力培養(yǎng)效果不佳。因此，Java理論教學(xué)環(huán)節(jié)、實(shí)驗(yàn)教學(xué)環(huán)節(jié)、學(xué)期課程設(shè)計(jì)、學(xué)年論文(設(shè)計(jì))、畢業(yè)論文(設(shè)計(jì))環(huán)節(jié)、學(xué)科競(jìng)賽環(huán)節(jié)、校外實(shí)踐環(huán)節(jié)等方面都是培養(yǎng)學(xué)生實(shí)踐和創(chuàng)新能力的關(guān)鍵環(huán)節(jié)。
以貫穿Java教學(xué)整個(gè)過(guò)程的各個(gè)重要環(huán)節(jié)為切入點(diǎn)，從細(xì)節(jié)入手，扎扎實(shí)實(shí)落實(shí)好每一個(gè)關(guān)鍵環(huán)節(jié)，是保證培養(yǎng)學(xué)生的Java實(shí)踐和創(chuàng)新能力的根本。
1 在理論教學(xué)環(huán)節(jié)中培養(yǎng)學(xué)生的實(shí)踐和創(chuàng)新能力
1.1 以問(wèn)題和實(shí)際項(xiàng)目為核心，采用以線帶點(diǎn)的教學(xué)模式
需求是創(chuàng)新和應(yīng)用成果產(chǎn)生的動(dòng)力和源泉。傳統(tǒng)的Java教材和教學(xué)內(nèi)容是按知識(shí)點(diǎn)為模塊組織的，即一個(gè)知識(shí)點(diǎn)，一個(gè)針對(duì)該知識(shí)點(diǎn)的例題，這樣雖然有利于學(xué)生循序漸進(jìn)地學(xué)習(xí)和掌握各個(gè)基本知識(shí)點(diǎn)
及其用法，但這種教學(xué)方法，有時(shí)會(huì)導(dǎo)致學(xué)生一聽就會(huì)，一用就忘。其原因在于，學(xué)生從根本上并沒(méi)有掌握該知識(shí)點(diǎn)到底有什么用，只是聽懂了那道例題而已，沒(méi)有深層的理解和舉一反三的能力，學(xué)過(guò)時(shí)間不久，就會(huì)全然忘記。當(dāng)學(xué)生遇到一個(gè)實(shí)際問(wèn)題時(shí)，就會(huì)束手無(wú)策，不能將當(dāng)時(shí)上課時(shí)感覺(jué)已經(jīng)“掌握得很好”的各個(gè)知識(shí)點(diǎn)進(jìn)行融會(huì)貫通和綜合運(yùn)用。因此，教師在教學(xué)中要運(yùn)用幾個(gè)能貫穿大部分教學(xué)知識(shí)點(diǎn)的綜合實(shí)例和實(shí)際應(yīng)用項(xiàng)目，有說(shuō)服力地說(shuō)明貫穿在其中的各知識(shí)點(diǎn)的重要性和用法。經(jīng)過(guò)較長(zhǎng)時(shí)間的檢驗(yàn)，這種教學(xué)方法的優(yōu)點(diǎn)是：其一，可以提高課堂教學(xué)的趣味性；其二，可以減少學(xué)生在學(xué)習(xí)各個(gè)知識(shí)點(diǎn)時(shí)的茫然和困惑；其三，可以提高學(xué)生綜合各個(gè)知識(shí)點(diǎn)，形成知識(shí)網(wǎng)絡(luò)，進(jìn)而進(jìn)行實(shí)際問(wèn)題解決的能力。
所謂“以線帶點(diǎn)”是以問(wèn)題和實(shí)際項(xiàng)目為主線，貫穿各個(gè)分散的Java知識(shí)點(diǎn)，完成Java知識(shí)點(diǎn)的脈絡(luò)化。
1.2 以學(xué)生為主體，教師為主導(dǎo)
在以往教學(xué)過(guò)程中，限于課時(shí)，“滿堂灌”現(xiàn)象仍時(shí)有發(fā)生，結(jié)果是教學(xué)任務(wù)完成了，但學(xué)生的主體地位沒(méi)有體現(xiàn)出來(lái)，沒(méi)有充分參與到教學(xué)過(guò)程中，積極性不高，教學(xué)效果受到很大影響。為了克服這一點(diǎn)，“互問(wèn)互答”的啟發(fā)式和討論式教學(xué)是一種好方式，這樣可以最大程度地調(diào)動(dòng)學(xué)生學(xué)習(xí)積極性和主動(dòng)性，也有利于讓學(xué)生在教學(xué)過(guò)程中保持精力集中的良好狀態(tài)，長(zhǎng)期以來(lái)可以培養(yǎng)學(xué)生創(chuàng)造性思維能力。教師在教學(xué)過(guò)程中，從一個(gè)較高的高度引導(dǎo)學(xué)生如何學(xué)習(xí)知識(shí)，提高學(xué)生學(xué)習(xí)效率和獲取新知的能力，真正實(shí)現(xiàn)教學(xué)相長(zhǎng)。
1.3 開拓視野，編寫高效的程序
在講授類創(chuàng)建方法的時(shí)候，教師除了講授用傳統(tǒng)的“new類構(gòu)造方法”的方式外，可以介紹運(yùn)用java.lang包中Class類的forName方法創(chuàng)建類對(duì)象[1]，同時(shí)介紹運(yùn)用Java設(shè)計(jì)模式中的“工廠模式”進(jìn)行類對(duì)象的創(chuàng)建，并比較幾種創(chuàng)建類對(duì)象方法的異同，從而培養(yǎng)學(xué)生運(yùn)用多種方法解決同一問(wèn)題的能力。
引導(dǎo)學(xué)生在算法設(shè)計(jì)上下功夫，一個(gè)實(shí)用軟件的開發(fā)，往往需要編寫高效率的算法，因此，算法的設(shè)計(jì)在Java程序教學(xué)中仍然是非常重要的。但由于課時(shí)有限，不可能占用較多課時(shí)來(lái)彌補(bǔ)學(xué)生在算法方面的不足，可以做到的是，引導(dǎo)學(xué)生總結(jié)和復(fù)習(xí)先修的算法設(shè)計(jì)課程以及其他程序設(shè)計(jì)課程中所學(xué)的算法設(shè)計(jì)知識(shí)，借助Java程序進(jìn)行實(shí)現(xiàn)，并比較效率；介紹一些智能算法如“遺傳算法”的設(shè)計(jì)和實(shí)現(xiàn)的相關(guān)知識(shí)，幫助學(xué)有余力的學(xué)生運(yùn)用這些智能算法進(jìn)行實(shí)際問(wèn)題的解決，將非常有助于提高學(xué)生創(chuàng)新能力的培養(yǎng)。
2 注重實(shí)驗(yàn)教學(xué)課堂的效率
Java實(shí)驗(yàn)教學(xué)是Java教學(xué)的重要組成部分，更是提高學(xué)生動(dòng)手能力和創(chuàng)新能力的重要途徑。
2.1 落實(shí)實(shí)驗(yàn)預(yù)習(xí)
一般情況下，實(shí)驗(yàn)課時(shí)是2學(xué)時(shí)，這對(duì)于一個(gè)較大的實(shí)驗(yàn)項(xiàng)目來(lái)說(shuō)，根本沒(méi)有可能在2個(gè)實(shí)驗(yàn)學(xué)時(shí)中完成，因此，提前布置實(shí)驗(yàn)任務(wù)并督促學(xué)生按期完成非常重要。如一個(gè)JSP項(xiàng)目“學(xué)生成績(jī)管理系統(tǒng)”的綜合實(shí)驗(yàn)項(xiàng)目，應(yīng)讓學(xué)生在做該實(shí)驗(yàn)項(xiàng)目之前，就基本完成系統(tǒng)的設(shè)計(jì)及大部分的編碼工作。在實(shí)驗(yàn)課堂中，主要是配置好開發(fā)環(huán)境和調(diào)試系統(tǒng)，在指導(dǎo)教師的指導(dǎo)下解決遇到的問(wèn)題并按指導(dǎo)教師的要求做進(jìn)一步的改進(jìn)和完善。
2.2 檢驗(yàn)實(shí)驗(yàn)效果
指導(dǎo)教師對(duì)于學(xué)生的實(shí)驗(yàn)成果應(yīng)及時(shí)檢查和提問(wèn)，及時(shí)發(fā)現(xiàn)每個(gè)學(xué)生在做實(shí)驗(yàn)項(xiàng)目時(shí)遇到的問(wèn)題以及該生對(duì)該實(shí)驗(yàn)理解、設(shè)計(jì)和實(shí)現(xiàn)的程度。
3 重視課程設(shè)計(jì)、學(xué)年論文設(shè)計(jì)與實(shí)踐
Java課程設(shè)計(jì)是在學(xué)生學(xué)習(xí)完Java程序設(shè)計(jì)課程后對(duì)其進(jìn)行的一次全面的綜合練習(xí)和考查。課設(shè)成績(jī)將作為本課程的期末考核成績(jī)的重要組成部分。通過(guò)課程設(shè)計(jì)，使學(xué)生能夠得到較系統(tǒng)的技能訓(xùn)練，從而鞏固和加深對(duì)Java編程的基礎(chǔ)理論知識(shí)的理解，培養(yǎng)學(xué)生綜合運(yùn)用所學(xué)知識(shí)解決實(shí)際問(wèn)題的能力，使學(xué)生成為具有扎實(shí)的理論基礎(chǔ)和較強(qiáng)的獨(dú)立動(dòng)手能力的應(yīng)用型人才。
3.1 注重題目設(shè)計(jì)的目標(biāo)性和歸類
針對(duì)不同的Java應(yīng)用，將課程設(shè)計(jì)題目合理歸類，如“基于Java SE的桌面應(yīng)用系統(tǒng)”類、“基于Java EE的Web應(yīng)用開發(fā)系統(tǒng)”類、“基于Java ME的移動(dòng)設(shè)備系統(tǒng)”類等。從而做到有針對(duì)性。
在指導(dǎo)學(xué)生選題時(shí)，告訴學(xué)生在完成該題目時(shí)，可以在哪些方面有創(chuàng)新點(diǎn)和亮點(diǎn)，并將這些創(chuàng)新點(diǎn)的完成情況作為評(píng)價(jià)課程設(shè)計(jì)成績(jī)的重要依據(jù)。
3.2 強(qiáng)調(diào)學(xué)生所做項(xiàng)目的實(shí)用性和原創(chuàng)性
以往學(xué)生所做的課程設(shè)計(jì)、學(xué)年論文設(shè)計(jì)與實(shí)踐項(xiàng)目大都源于教師指定的題目，而這些題目往往都是一些虛擬項(xiàng)目如“XX項(xiàng)目的設(shè)計(jì)與實(shí)現(xiàn)”，題目本身比較含糊，導(dǎo)致學(xué)生無(wú)法進(jìn)行具體的需求分析，只能造出一個(gè)“需求分析和開發(fā)背景”。這樣的項(xiàng)目完成后，即使做得比較“完美”，也是離實(shí)際應(yīng)用較遠(yuǎn)，不能投入實(shí)際應(yīng)用。
培養(yǎng)學(xué)生求真務(wù)實(shí)、追求原創(chuàng)的素養(yǎng)，克服浮躁情緒，避免僅為完成任務(wù)抄襲他人項(xiàng)目成果。在教學(xué)過(guò)程中，經(jīng)常發(fā)現(xiàn)部分學(xué)生將資料查閱變成了“復(fù)制―粘貼”：不去汲取他人項(xiàng)目成果中的精華，也不去做任何改進(jìn)，直接原封不動(dòng)地套用。結(jié)果自己在“實(shí)
踐”過(guò)程中不但沒(méi)有學(xué)到任何知識(shí)，積累任何開發(fā)經(jīng)驗(yàn)，反而養(yǎng)成了不勞而獲，抄襲剽竊的壞習(xí)氣。因此，在引導(dǎo)學(xué)生進(jìn)行項(xiàng)目實(shí)踐的過(guò)程中，在對(duì)其進(jìn)行各階段指導(dǎo)和檢查時(shí)必須嚴(yán)格把關(guān)，引導(dǎo)和幫助學(xué)生樹立良好的專業(yè)道德素質(zhì)和研發(fā)精神。
4 畢業(yè)論文環(huán)節(jié)的創(chuàng)新能力培養(yǎng)
4.1 設(shè)計(jì)、指導(dǎo)與完成創(chuàng)新性、研究性題目
在前些年的畢業(yè)論文選題中，較多見的是：“基于Java SE的XX系統(tǒng)的設(shè)計(jì)與實(shí)現(xiàn)”，“基于JSP的XX系統(tǒng)的設(shè)計(jì)與實(shí)現(xiàn)”等。目前這類題目作為計(jì)算機(jī)本科生畢業(yè)論文題目，有以下一些弊端：
1) Java的開放資源非常多，以這類命題的網(wǎng)絡(luò)及參考書資源、甚至整個(gè)軟件設(shè)計(jì)開發(fā)背景、設(shè)計(jì)過(guò)程、實(shí)現(xiàn)過(guò)程、實(shí)現(xiàn)的全部源碼都有現(xiàn)成的。
2) 虛擬項(xiàng)目較多，大都是自圓其說(shuō)，如對(duì)系統(tǒng)的設(shè)計(jì)和開發(fā)背景是自定的，而不是源于實(shí)際用戶的實(shí)際開發(fā)要求。學(xué)生在完成過(guò)程中，沒(méi)有與用戶溝通和交流的機(jī)會(huì)，沒(méi)有反復(fù)滿足用戶具體、特殊要求的過(guò)程，從而導(dǎo)致學(xué)生沒(méi)有通過(guò)想辦法、找妙招來(lái)解決問(wèn)題的磨礪過(guò)程。
3) 若有兩個(gè)以上的學(xué)生選擇了題目不同，但實(shí)際設(shè)計(jì)和實(shí)現(xiàn)過(guò)程大同小異的題目，就不能保證一人一題的原則。
畢業(yè)論文與設(shè)計(jì)是對(duì)本科生本科學(xué)習(xí)知識(shí)的大檢閱，也是對(duì)本科生學(xué)術(shù)研究能力、分析和解決實(shí)際問(wèn)題能力的重要培養(yǎng)環(huán)節(jié)，也是為本科生將來(lái)深造和從事研發(fā)相關(guān)工作所作的一個(gè)鋪墊。為了突出畢業(yè)論文(或設(shè)計(jì))環(huán)節(jié)中對(duì)學(xué)生創(chuàng)新能力的培養(yǎng)，在畢業(yè)論文的選題上，指導(dǎo)教師應(yīng)進(jìn)一步把關(guān)，設(shè)計(jì)出具有實(shí)際開發(fā)背景、創(chuàng)新性和一定研究性的題目。
4.2 注重對(duì)現(xiàn)有軟件包的二次開發(fā)
基于Java的用于各種研究和實(shí)踐的軟件包有很多，以基于Java的多Agent開發(fā)工具包JADE(Java Agent Development Framework)[2]和遺傳算法工具包JGAP(Java Genetic Algorithms Package)[3]為例，說(shuō)明
利用基于Java的工具包進(jìn)行二次開發(fā)來(lái)培養(yǎng)學(xué)生創(chuàng)新能力的實(shí)例。
對(duì)于基礎(chǔ)較好、有較強(qiáng)科研興趣的學(xué)生，可以引導(dǎo)其運(yùn)用諸如JADE這樣的多Agent系統(tǒng)開發(fā)工具包開發(fā)簡(jiǎn)單實(shí)用的多Agent系統(tǒng)，從而帶動(dòng)學(xué)生學(xué)習(xí)和研究多Agent系統(tǒng)的理論和實(shí)踐方法。遺傳算法是當(dāng)前應(yīng)用廣泛地智能算法之一，而基于Java語(yǔ)言的遺傳算法工具包JGAP中已實(shí)現(xiàn)了簡(jiǎn)單遺傳算法和部分高級(jí)遺傳算法的基本框架，可以引導(dǎo)學(xué)生快速在其基礎(chǔ)上完成一些改進(jìn)和在開發(fā)，最終達(dá)到學(xué)生理解遺傳算法基本理論和實(shí)際應(yīng)用的目的。
5 以競(jìng)賽高度為標(biāo)桿，促進(jìn)學(xué)生進(jìn)行高層次編程訓(xùn)練
Java競(jìng)賽題目具有很強(qiáng)的新穎性和挑戰(zhàn)性，其目的在于考察參賽學(xué)生的創(chuàng)造性解決實(shí)際問(wèn)題的能力和編程思維。引導(dǎo)學(xué)生參與各級(jí)各類的Java編程競(jìng)賽或以歷屆競(jìng)賽題目作為訓(xùn)練，都能達(dá)到提高學(xué)生的創(chuàng)新意識(shí)和能力以及培養(yǎng)拔尖學(xué)生的目的。
6 產(chǎn)學(xué)研結(jié)合
6.1 創(chuàng)新實(shí)驗(yàn)室和基地建設(shè)
為了使學(xué)生具有快速適應(yīng)市場(chǎng)Java人才的需求、能夠獨(dú)立創(chuàng)業(yè)的目的，根據(jù)學(xué)校客觀條件的不同，建立一定規(guī)模的創(chuàng)新實(shí)驗(yàn)室或聯(lián)系實(shí)驗(yàn)基地尤為重要。這是因?yàn)椋?/p>
1) 較大型工程實(shí)踐項(xiàng)目的開發(fā)都需要一個(gè)較長(zhǎng)的周期，一般為3～5個(gè)月或更長(zhǎng)。對(duì)參與完成項(xiàng)目的學(xué)生的訓(xùn)練和培養(yǎng)也需要一個(gè)較長(zhǎng)的周期。而普通和短期的實(shí)驗(yàn)項(xiàng)目訓(xùn)練無(wú)法達(dá)到培養(yǎng)學(xué)生獨(dú)立承擔(dān)實(shí)際工程項(xiàng)目的能力。
2) 在對(duì)學(xué)生進(jìn)行訓(xùn)練和實(shí)際項(xiàng)目的開發(fā)過(guò)程中，不可能占用正常的上課時(shí)間，而是充分利用課外、周末以及節(jié)假日的課余時(shí)間，有教師指導(dǎo)團(tuán)隊(duì)對(duì)學(xué)生進(jìn)行輔導(dǎo)、訓(xùn)練和協(xié)同項(xiàng)目開發(fā)。
3) 一個(gè)固定而且全天候的實(shí)驗(yàn)場(chǎng)所和一定數(shù)量、檔次的儀器設(shè)備是能否完成創(chuàng)新性實(shí)驗(yàn)和實(shí)際項(xiàng)目開發(fā)的重要保障。
6.2 承接軟件開發(fā)項(xiàng)目，為學(xué)生走向市場(chǎng)奠定基礎(chǔ)
由指導(dǎo)教師牽頭，分析和研究市場(chǎng)對(duì)Java編程人員的需求，有針對(duì)性地承攬學(xué)校及校外的應(yīng)用開發(fā)項(xiàng)目，組建以學(xué)生為主體的項(xiàng)目開發(fā)小組，進(jìn)行項(xiàng)目開發(fā)。
6.3 進(jìn)入課題組，鍛煉科研能力
指導(dǎo)教師帶領(lǐng)學(xué)生進(jìn)入創(chuàng)新實(shí)驗(yàn)室，共同開展和完成Java相關(guān)的科研、教學(xué)改革和實(shí)踐項(xiàng)目，讓參與項(xiàng)目的學(xué)生體驗(yàn)科研過(guò)程，學(xué)習(xí)科研方法，培養(yǎng)科研精神。
7 教學(xué)中應(yīng)用系統(tǒng)科學(xué)方法
系統(tǒng)科學(xué)方法理論是計(jì)算機(jī)科學(xué)與技術(shù)的重要的方法論之一[4]。面向?qū)ο缶幊趟枷牒蛙浖こ淌窍到y(tǒng)科學(xué)方法在軟件開發(fā)中的集中體現(xiàn)。在學(xué)生的
實(shí)踐教學(xué)各個(gè)環(huán)節(jié)中，往往會(huì)做一些類似于“XX信息系統(tǒng)的設(shè)計(jì)與實(shí)現(xiàn)”之類的項(xiàng)目。但學(xué)生在實(shí)踐過(guò)程中，急于求成，只關(guān)注系統(tǒng)的實(shí)現(xiàn)，一開始就寫源碼，不注重按軟件工程理論和方法進(jìn)行系統(tǒng)分析和設(shè)計(jì)，也不注重系統(tǒng)中類的設(shè)計(jì)和類間關(guān)系的設(shè)計(jì)，是導(dǎo)致項(xiàng)目開發(fā)失敗或脫離實(shí)際應(yīng)用的重要原因。更嚴(yán)重的是，這樣的開發(fā)習(xí)慣一旦養(yǎng)成，將會(huì)被學(xué)生帶到今后的實(shí)際項(xiàng)目開發(fā)中，情況會(huì)更加糟糕。
8 結(jié)語(yǔ)
通過(guò)長(zhǎng)期的Java教學(xué)實(shí)踐，筆者總結(jié)出“學(xué)生實(shí)踐和創(chuàng)新能力培養(yǎng)效果的好壞取決于每個(gè)教學(xué)環(huán)節(jié)完成好壞”的結(jié)論。從細(xì)節(jié)入手，扎扎實(shí)實(shí)完成好每一個(gè)教學(xué)環(huán)節(jié)，不僅可以培養(yǎng)學(xué)生實(shí)踐和創(chuàng)新能力，而且可以幫助學(xué)生養(yǎng)成良好的學(xué)習(xí)、研究習(xí)慣并為學(xué)生就業(yè)奠定堅(jiān)實(shí)基礎(chǔ)。
參考文獻(xiàn)：
[1] 耿祥義,張躍平. Java 2實(shí)用教程[M]. 3版. 北京:清華大學(xué)出版社,2006: 95.
[2] Carie G. JADE TUTORIAL:JADE PROGRAMMING FOR BEGINNERS[EB/OL]. [2011-03-07]. /doc/ JADEProgramming-Tutorial-for-beginners.pdf.
[3] Java Genetic Algorithms Package[EB/OL]. [2011-03-07]. .
[4] 董榮勝,古天龍. 計(jì)算機(jī)科學(xué)與技術(shù)方法論[M]. 北京:人民郵電出版社,2002:117.
On Students’ Practicing and Creative Ability Training in Java Teaching
LI Ruisheng
(College of Computer Science, Gansu Institute of Political Science and Law, Lanzhou 730070, China)
【Abstract】Based on the concepts of genetic algorithm and BP neural network，the paper studies the optimization of BP neural network algorithm， and the effectiveness of the algorithm is verified by an example.
【關(guān)鍵詞】遺傳算法；BP神經(jīng)網(wǎng)絡(luò)；優(yōu)化算法
【Keywords】genetic algorithm； BP neural network； algorithm optimization
【中圖分類號(hào)】TPl83 【文獻(xiàn)標(biāo)志碼】A 【文章編號(hào)】1673-1069（2017）04-0135-02
1 引言
神經(jīng)網(wǎng)絡(luò)是一種模仿動(dòng)物神經(jīng)網(wǎng)絡(luò)行為特征，進(jìn)行分布式并行信息處理的算法數(shù)學(xué)模型，憑借著復(fù)雜的系統(tǒng)結(jié)構(gòu)，通過(guò)對(duì)系統(tǒng)內(nèi)部節(jié)點(diǎn)連接關(guān)系的調(diào)節(jié)，實(shí)現(xiàn)對(duì)信息的高效處理。作為技術(shù)最為成熟的神經(jīng)網(wǎng)絡(luò)模擬，BP神經(jīng)網(wǎng)絡(luò)具有良好的自學(xué)習(xí)、自適應(yīng)以及泛化能力，在許多領(lǐng)域中都有著廣泛的應(yīng)用。而針對(duì)BP神經(jīng)網(wǎng)絡(luò)在應(yīng)用環(huán)節(jié)存在的問(wèn)題，需要采取相應(yīng)的優(yōu)化算法，提升神經(jīng)網(wǎng)絡(luò)的收斂速度和理能力。
2 遺傳算法與BP神經(jīng)網(wǎng)絡(luò)
遺傳算法遵循的是生物界中適者生存的法則，其基本原理，是指將問(wèn)題參數(shù)進(jìn)行編碼，形成染色體，通過(guò)迭代的方式，運(yùn)用選擇、變異、交叉等運(yùn)算，對(duì)種群中染色體的信息進(jìn)行交換，繼而形成能夠滿足優(yōu)化目標(biāo)的染色體。
BP（Back Propagation）神經(jīng)網(wǎng)絡(luò)最初產(chǎn)生于1986年，屬于一種依照誤差逆?zhèn)鞑ニ惴ㄓ?xùn)練的多層前饋網(wǎng)絡(luò)，也是當(dāng)前技術(shù)條件下應(yīng)用最為廣泛的神經(jīng)網(wǎng)絡(luò)模型之一，其可以對(duì)輸入-輸出模式的映射關(guān)系進(jìn)行學(xué)習(xí)和存儲(chǔ)，同時(shí)不需要對(duì)能夠揭示這些映射關(guān)系的方程進(jìn)行描述。神經(jīng)網(wǎng)絡(luò)具備自適應(yīng)和自組織能力，在進(jìn)行學(xué)習(xí)和訓(xùn)練的過(guò)程中，可以通過(guò)改變突觸權(quán)重值的方式，更好地適應(yīng)周邊環(huán)境的變化。在同一個(gè)神經(jīng)網(wǎng)絡(luò)中，如果內(nèi)容不同，學(xué)習(xí)方式不同，則會(huì)產(chǎn)生不同的功能。人工神經(jīng)網(wǎng)絡(luò)從本質(zhì)上看，更加接近具備自主學(xué)習(xí)能力的系統(tǒng)，可以通過(guò)不斷的學(xué)習(xí)，超出最初設(shè)計(jì)的知識(shí)水平。在人工神經(jīng)網(wǎng)絡(luò)中，比較常見的學(xué)習(xí)方法有兩種，一是有監(jiān)督的學(xué)習(xí)，可以結(jié)合標(biāo)準(zhǔn)樣本，進(jìn)行分類或者模仿，二是無(wú)監(jiān)督的學(xué)習(xí)，在制定相應(yīng)的學(xué)習(xí)規(guī)則后，系統(tǒng)會(huì)根據(jù)自身所處環(huán)境，進(jìn)行學(xué)習(xí)內(nèi)容的分析和選擇，更加接近人腦的功能特點(diǎn)。
3 基于遺傳算法的優(yōu)化BP神經(jīng)網(wǎng)絡(luò)算法
3.1 算法基本原理
①BP算法。BP神經(jīng)網(wǎng)絡(luò)算法主要包括了數(shù)據(jù)流的前向計(jì)算和誤差信號(hào)的反向傳播兩個(gè)方面的內(nèi)容，結(jié)合三層BP神經(jīng)網(wǎng)絡(luò)的拓?fù)浣Y(jié)構(gòu)，假定x為網(wǎng)絡(luò)輸入，y為結(jié)果輸出，當(dāng)處于正向傳播過(guò)程時(shí)，數(shù)據(jù)的傳輸為輸入層隱層輸出層，每一層神經(jīng)元的狀態(tài)僅僅會(huì)影響下一層神經(jīng)元，而如果輸出層無(wú)法獲得期望輸出，則會(huì)自動(dòng)轉(zhuǎn)向誤差信號(hào)的反向傳播流程。在BP神經(jīng)網(wǎng)絡(luò)中，網(wǎng)絡(luò)的訓(xùn)練實(shí)際上是對(duì)閾值和權(quán)值進(jìn)行調(diào)整的過(guò)程，當(dāng)網(wǎng)絡(luò)誤差縮小到設(shè)定值，或者訓(xùn)練步數(shù)達(dá)到設(shè)定步數(shù)時(shí)，會(huì)自動(dòng)停止訓(xùn)練。
②遺傳算法。遺傳算法可以從代表問(wèn)題可能潛在解集的種群開始，種群中的每一個(gè)染色體都帶有相應(yīng)的特征，染色體可以看作若干基因的集合，為了便于分析，需要做好編碼，完成從表現(xiàn)型到基因型的映射。在演化過(guò)程中，依照問(wèn)題域中存在的個(gè)體的適應(yīng)度，進(jìn)行個(gè)體的挑選和交叉，然后變異出新的解集種群。選擇末代種群中的最優(yōu)個(gè)體進(jìn)行解碼，就可以得到問(wèn)題的近似最優(yōu)解。
3.2 優(yōu)化BP算法
BP神經(jīng)網(wǎng)絡(luò)算法具有極強(qiáng)的局部尋優(yōu)能力，但是容易陷入局部極小的問(wèn)題，遺傳算法具有良好的全局優(yōu)化性和自適應(yīng)性，但是局部尋優(yōu)能力不足。對(duì)此，可以將遺傳算法與BP算法結(jié)合起來(lái)，實(shí)現(xiàn)對(duì)于網(wǎng)絡(luò)拓?fù)浣Y(jié)構(gòu)和網(wǎng)絡(luò)權(quán)值、網(wǎng)絡(luò)閾值的優(yōu)化。
①權(quán)值優(yōu)化。在傳統(tǒng)的BP網(wǎng)絡(luò)中，連接權(quán)值的學(xué)習(xí)算法容易陷入局部極小，無(wú)法得到全局最優(yōu)。對(duì)此，可以引入遺傳算法代替?zhèn)鹘y(tǒng)的學(xué)習(xí)方法，對(duì)神經(jīng)網(wǎng)絡(luò)的權(quán)值進(jìn)行優(yōu)化。在這個(gè)過(guò)程中，需要解決幾個(gè)比較關(guān)鍵的問(wèn)題，一是編碼方案，可供選擇的權(quán)值編碼方式包括實(shí)數(shù)編碼和二級(jí)制編碼，前者是以實(shí)數(shù)表示權(quán)值，非常直觀，不過(guò)需要對(duì)遺傳算子進(jìn)行重新設(shè)計(jì)，后者是利用0，1字符串表示權(quán)值；二是適應(yīng)度函數(shù)，引入遺傳算法后，網(wǎng)絡(luò)的機(jī)構(gòu)以確定，在這種情況下，網(wǎng)絡(luò)的誤差越大，適應(yīng)度越小；三是進(jìn)化過(guò)程，主要是對(duì)選擇、交叉、變異算子的選擇，如果必要，也可以重新設(shè)計(jì)；四是混合訓(xùn)練神經(jīng)網(wǎng)絡(luò)，遺傳算法能夠在大規(guī)模、復(fù)雜性的空間中實(shí)現(xiàn)可靠搜索，而且不需要有關(guān)誤差函數(shù)梯度的信息，優(yōu)勢(shì)相當(dāng)明顯。可以通過(guò)在誤差函數(shù)中增加懲罰項(xiàng)的方式，降低網(wǎng)絡(luò)的復(fù)雜程度。
②權(quán)值和結(jié)構(gòu)同時(shí)優(yōu)化。BP神經(jīng)網(wǎng)絡(luò)連接權(quán)的進(jìn)化，要求明確的網(wǎng)絡(luò)結(jié)構(gòu)，網(wǎng)絡(luò)結(jié)構(gòu)直接影響著神經(jīng)網(wǎng)絡(luò)本身對(duì)于信息的處理能力。神經(jīng)網(wǎng)路的結(jié)構(gòu)包括了網(wǎng)絡(luò)連接方式（拓?fù)浣Y(jié)構(gòu)）和節(jié)點(diǎn)轉(zhuǎn)換函數(shù)，完善的結(jié)構(gòu)不僅需要能夠?qū)?wèn)題進(jìn)行有效解決，還不能存在冗余節(jié)點(diǎn)和冗余連接。伴隨著進(jìn)化算法的應(yīng)用，網(wǎng)絡(luò)設(shè)計(jì)在很多時(shí)候被看作搜索問(wèn)題，評(píng)價(jià)的標(biāo)準(zhǔn)包括了抗噪性、學(xué)習(xí)準(zhǔn)確率以及泛化能力等。結(jié)構(gòu)進(jìn)化的關(guān)鍵體現(xiàn)在結(jié)構(gòu)編碼和算子設(shè)計(jì)，而結(jié)構(gòu)編碼方案則會(huì)影響算子設(shè)計(jì)的效果。以三層前饋型BP網(wǎng)絡(luò)為例，其輸入層和輸出層節(jié)點(diǎn)的數(shù)量已經(jīng)確定，優(yōu)化算法需要重點(diǎn)研究隱含層的節(jié)點(diǎn)數(shù)量。考慮到問(wèn)題本身的復(fù)雜性，二進(jìn)制編碼的方法并不適用，因此選擇實(shí)數(shù)編碼，在隱含層節(jié)點(diǎn)增加二級(jí)制編碼作為控制基因，通過(guò)隨機(jī)函數(shù)產(chǎn)生。當(dāng)控制基因的數(shù)值為0時(shí)，對(duì)應(yīng)的隱含層節(jié)點(diǎn)對(duì)輸出層無(wú)用，而當(dāng)控制基因的數(shù)值為1時(shí)，隱含層節(jié)點(diǎn)對(duì)輸出層作用。需要注意的一點(diǎn)，當(dāng)選擇實(shí)數(shù)編碼方案時(shí)，為了明確編碼的長(zhǎng)度，需要確定隱層的最大神經(jīng)元數(shù)目。
4 仿真試驗(yàn)
結(jié)合已知數(shù)據(jù)，對(duì)某地區(qū)小麥吸漿蟲的發(fā)生程度進(jìn)行預(yù)測(cè)。對(duì)問(wèn)題進(jìn)行深入分析，可以轉(zhuǎn)化為相應(yīng)的輸入輸出系統(tǒng)，可以通過(guò)神經(jīng)網(wǎng)絡(luò)進(jìn)行表達(dá)。現(xiàn)有的研究成果表明，小麥吸漿蟲的發(fā)生與氣候因素關(guān)系密切，因此可以利用氣象因子對(duì)問(wèn)題進(jìn)行分析。選擇2000年到2015年的氣象數(shù)據(jù)，設(shè)置40個(gè)研究樣本，以x1-x14表示需要處理的原始數(shù)據(jù)（氣象因子），Y表示小麥吸漿蟲的發(fā)生程度。從減小誤差的角度，對(duì)原始數(shù)據(jù)進(jìn)行預(yù)處理。以優(yōu)化后的BP算法進(jìn)行神經(jīng)網(wǎng)絡(luò)訓(xùn)練，結(jié)合訓(xùn)練結(jié)果進(jìn)行MATLAB仿真。在仿真試驗(yàn)中，需要做好一些關(guān)鍵參數(shù)額的設(shè)置，遺傳算法和BP算法的最大代數(shù)分別為100，BP算法均方誤差為0.001，會(huì)激活函數(shù)為雙曲正切S型，線性輸出層，學(xué)習(xí)算法被設(shè)置為經(jīng)過(guò)改進(jìn)的自適應(yīng)學(xué)習(xí)率的梯度下降學(xué)習(xí)算法。
設(shè)定14作為隱層神經(jīng)元的上限，由于編碼長(zhǎng)度固定且迭代代數(shù)一定，在所有的試驗(yàn)中，遺傳算法的復(fù)雜度都是相同的。結(jié)合仿真試驗(yàn)分析，隱含神經(jīng)元的最優(yōu)數(shù)目為5、6、7，與傳統(tǒng)方法得到的結(jié)果基本一致。相比較而言，利用遺傳算法同時(shí)進(jìn)行結(jié)構(gòu)和權(quán)值的優(yōu)化，最為顯著的優(yōu)勢(shì)在于能夠?qū)﹄[層神經(jīng)元的數(shù)目進(jìn)行自適應(yīng)確定，減少嘗試的次數(shù)，提升計(jì)算效率。
而結(jié)合相應(yīng)的訓(xùn)練結(jié)果分析，利用遺傳算法進(jìn)行BP神經(jīng)網(wǎng)絡(luò)連接權(quán)值的優(yōu)化，相比較傳統(tǒng)算法更加有效，不過(guò)同樣需要進(jìn)行網(wǎng)絡(luò)結(jié)構(gòu)的嘗試，換言之就是選擇合適的隱層神經(jīng)元數(shù)目。不僅如此，利用遺傳算法同時(shí)對(duì)神經(jīng)網(wǎng)絡(luò)的權(quán)值和結(jié)構(gòu)進(jìn)行優(yōu)化，智能型更強(qiáng)，可能找到合適的初始權(quán)值和優(yōu)秀的網(wǎng)絡(luò)結(jié)構(gòu)，不過(guò)，如果數(shù)據(jù)煩瑣，搜索的速度會(huì)變慢。
