基于計算智能的信息處理技術的研究與應用

劉 偉，田 娥，譚苗苗

(1.北京聯合大學 機電學院，北京 100020；2.北京智能機械創新設計服務工程技術研究中心，北京 100020)

?

基于計算智能的信息處理技術的研究與應用

劉 偉1,2，田 娥1,2，譚苗苗1,2

(1.北京聯合大學 機電學院，北京 100020；2.北京智能機械創新設計服務工程技術研究中心，北京 100020)

計算智能是人工智能的重要分支，以數據為基礎，主要借鑒連接主義和行為主義的思想，基于生物進化和細胞網絡等機制，具有分布、并行、自適應、自組織和自學習等特點。首先介紹了計算智能的起源和概念，然后以人工神經網絡、遺傳算法、蟻群算法為例闡述了其原理和應用，最后介紹了在新技術條件下，計算智能的發展趨勢及有待解決的一些問題。

計算智能；人工神經網絡；遺傳算法；蟻群算法

美國學者J.C.Bezdekek在1992年首次提出了“計算智能”的概念，1994年7月，在IEEE首次國際計算智能大會上，神經網絡、進化計算以及模糊系統被首次合并在一起，使計算智能成為了一個統一的技術范疇。由于計算智能的算法具有自學習、自組織、自適應的特征和簡單、通用、魯棒性強、易并行處理等特點，因此自誕生以來就被廣泛應用于信息安全、模式識別、數據分類與挖掘、優化設計、故障診斷、機器學習、聯想記憶和控制等領域[1]。

1 計算智能的概念

人工智能是相對于人的自然智能而言的，用人工方法和技術，模仿、延伸和擴展人的智能[2]，分為符號主義(也稱為邏輯主義)、連接主義(也稱為仿生主義)和行為主義(也稱為進化主義)三大學派。傳統的人工智能是基于符號主義的，它以知識為基礎，通過推理進行問題求解，也稱為符號智能。

計算智能則主要借鑒連接主義和行為主義的思想，基于生物進化和細胞網絡等機制，以數據為基礎，通過訓練建立聯系，模仿生物體系和人類智能機制，進行問題求解。其特點是以分布式方式存儲信息，以并行方式處理信息，具有自組織及自學習能力，善于處理非程序的、非數值的信息。

20世紀中葉，符號智能體系占據主導地位，有了很大的進展。但后期遇到了一些困難，逐漸轉入相對停滯[3]。隨著神經網絡的出現，計算智能逐漸引起了人們的關注。

2 計算智能的典型算法及應用

計算智能與各種數學方法相結合，出現了很多分支。其中比較典型的有人工神經網絡、遺傳算法和蟻群算法。

2.1 人工神經網絡

人工神經網絡由美國科學家MCCulloch和Pitts于1943年提出，是連接主義的經典代表。它是由大量神經元廣泛互連而成的復雜網絡系統[4]。

2.1.1 神經元及其特性

神經元是神經網絡的基本組成單元，其模型如圖1所示。

圖1 神經元模型

單個神經元由多個輸入xi(i=1，2，…，n)和一個隨時間t變化的輸出y組成。中間狀態由輸入信號的權和表示，而輸出為

(1)

式中：θj為閾值；wji為連接權；f為激勵函數，是常用線性函數、S型函數和閾值型函數。

2.1.2 人工神經網絡的結構與特點

人工神經網絡由許多神經元組成，具有并行分布結構，分為遞歸(反饋)網絡和前饋(多層)網絡兩類。

1)遞歸網絡

也稱為反饋網絡，如圖2所示。圖中，Vi表示節點的狀態，xi為節點的輸入(初始)值，xi′為收斂后的輸出值(i=1，2，…，n)。Hopfield網絡、Elmman網絡和Jordan網絡是遞歸網絡中具有代表性的例子。

圖2 遞歸(反饋)網絡

2)前饋網絡

也稱為多層網絡，如圖3所示。信號單向流通，不存在同層間的連接。

圖3 前饋(多層)網絡

前饋網絡的例子有多層感知器(MLP)、學習矢量量化(LVQ)網絡、小腦模型連接控制(CMAC)網絡和數據處理方法(GMDH)網絡等。

人工神經網絡的主要學習算法包括有師學習算法、無師學習算法和強化學習算法。

2.1.3 人工神經網絡的應用

人工神經網絡在自動控制、圖像處理、模式識別、數據挖掘等領域有廣泛的應用，其獨特的結構和信息處理的方法使其表現出了良好的性能。

反向傳播(BP)網絡利用輸出響應與期望輸出之間的誤差作為導師信號，對網絡連接強度進行反復調節，當參數適當時，能夠收斂到較小的均方差，主要應用于分類、函數逼近、優化預測等方面，是目前應用最廣的網絡之一。

自適應諧振理論(ART)網絡能根據可選參數對輸入數據進行粗略分類，在模式識別、故障檢測與診斷、數據挖掘等領域應用廣泛[5]。具有聚類效果好、自適應能力及穩定性強、算法簡單高效的優點。

Hopfield網絡依靠集體協同能自發產生計算行為。它包括主要應用于聯想記憶的離散型網絡和主要應用于優化計算的連續型網絡。另外，Hopfield網絡在圖像識別、加工車間調度、LSI優化布局及線性系統模型參數估計等方面也有廣泛的應用[6]。

此外，比較常見的人工神經網絡模型還有：雙向聯想存儲器(BAM)、博爾茨曼(Boltzmann)機(BM)、對流傳播網絡(CPN)、自組織映射網(SOM)等。

2.2 遺傳算法

遺傳算法是進化計算的一種最重要的形式。它是由美國Michigan大學的J.Holland教授于1975年模仿生物遺傳學和自然選擇機理首先提出的。其主要特點是群體搜索策略和群體之間的信息交換。

2.2.1 遺傳算法的基本機理

1)基本遺傳算法[7]的數學模型

基本遺傳算法可表示為

SGA=(C,E,P0,M,Φ,Γ,Ψ,T)

(2)

式中：C為個體編碼；E為適應度函數；P0為初始種群；M為種群規模；Φ為選擇算子；Γ為交叉算子；Ψ為變異算子；T為終止條件。

圖4所示為基本遺傳算法的流程圖。

圖4 遺傳算法的基本流程圖

2)編碼

編碼[7-9]指的是把問題的可行解從解空間轉換到搜索空間，反過來則稱為解碼。

常用的編碼準則是有意義的積木塊編碼規則和最小字符集編碼規則。

常見的編碼方法有二進制、格雷碼、浮點數、多參數級聯等編碼規則。

3)適應度函數

適應度函數是判斷個體好壞的標準。要求滿足單值、連續、非負、最大化、盡可能簡單等條件。

4)選擇

選擇是指根據適者生存的原則從當前群體中確定可以遺傳到下一代群體中的個體。它的作用是保持群體的規模不變，決定算法的進化方向。

輪盤賭、隨機競爭、最佳保留等是較常用的選擇方法。

5)交叉

交叉是指互相交換兩個以一定概率選擇出來的個體的部分基因，體現了全局搜索能力。

單點交叉、兩點交叉與多點交叉、均勻交叉、算術交叉等是較常見的交叉方法。

6)變異

變異是指以較小的概率將個體某個或某些基因值用其他等位基因來替換，體現了局部搜索能力。

常見的變異方法有基本位變異、均勻變異、邊界變異等。

7)終止條件

如果沒有終止條件，遺傳算法會反復迭代下去，無限逼近最優解。規定迭代次數、控制偏差、檢查適應度的變化等是較常見的終止方法。

2.2.2 遺傳算法的應用

遺傳算法不依賴于問題的具體領域，因此應用非常廣泛。

1)優化問題

這是遺傳算法的經典應用領域，對于非線性、模型多、目標覆蓋廣的函數優化問題和搜索空間受問題規模制約的組合優化問題，遺傳算法比傳統優化方法更加有效。比如：使用混合遺傳算法來解決貨船裝載的優化問題[10]；應用并行遺傳算法求解多目標優化問題[11]等。

2)生產調度問題

傳統的數學建模方法很難對付生產過程中出現的復雜調度問題，而遺傳算法則可以用來開發車間生產調度系統，比如設計排產規則、構建排產模型、建立最小化完工時間[12]等。

3)自動控制領域

遺傳算法主要用于離線設計分析和在線自適應調節。比如在電力系統中進行負荷檢測，遏制超調量的過高；改變模糊控制器參數，實現模糊控制的在線自動優化。

除了以上3個方面外，遺傳算法在機器學習、圖像處理、人工生命和數據挖掘等方面也有廣泛的應用。

2.3 蟻群算法

蟻群算法是由意大利學者Dorigo等人在1991年受蟻群尋找食物過程中發現路徑的行為的啟發提出的[13-14]。它具有全局尋優、信息正反饋、啟發式搜索和分布式計算等特征，在求解TSP[15-16]、job-shop調度[17-18]和資源二次分配[19]等復雜優化問題特別是離散優化問題方面具有優勢。

2.3.1 蟻群算法基本原理

研究發現，螞蟻運動時會在它所經過的路徑上留下外激素，某一路徑上越多的螞蟻走過，留下的外激素就越多，其濃度就越大。

以求解n個城市的TSP問題為例來說明蟻群算法的系統模型[20]。假設螞蟻個數為m，τij(t)表示t時刻路徑ij上外激素的濃度，并且τij(0)=C(常數)。

螞蟻k運動時，轉移概率取決于外激素的濃度，即

(3)

式中：allowedk={0，1，…，n-1}表示螞蟻k下一步允許選擇的城市。用tabuk(k=1，2，…，m)來記錄螞蟻及目前已經走過的城市。

外激素濃度會逐漸降低，螞蟻每完成一次循環，各路徑上信息量需作調整，即

τij(t+n)=(1-ρ)·τij(t)+Δτij

(4)

(5)

(6)

式中：Q是常數；Lk表示螞蟻k在本次循環中所走過路徑的長度。

蟻群算法流程圖如圖5所示。

圖5 蟻群算法流程圖

2.3.2 蟻群算法的應用

經過20多年的發展，蟻群算法被持續改進，出現了很多改進的版本，比如多態蟻群算法[21]、帶聚類處理的蟻群算法[22]、連續正交蟻群算法[23]等等，其應用領域也在不斷擴大，尤其是在解決NP組合優化問題中顯示出優越性。

1)車間作業調度問題

這個問題的本質是在時間上合理分配系統的有限資源，在滿足一些約束條件的同時，達到某些目標的最優化。蟻群算法在解決工序車間問題[24]、排列流車間問題[25]、單機器總延遲問題[26]、資源受限項目調度問題[27]、組車間調度問題[28]等方面取得了良好的效果。

2)車輛路徑問題

這是運輸組織優化的核心問題，要求車輛有序地經過一系列客戶點，在滿足一定約束的條件下，使總運輸成本最小。蟻群算法在解決車輛路徑問題方面有眾多的研究成果，比如多車場車輛路徑問題[29]、周期性車輛路徑問題[30]、分離配送車輛路徑問題[31]、隨機需求車輛路徑問題[32]、有時間窗的車輛路徑問題[33]等。

除上述兩個領域之外，蟻群算法在二次分配問題[34]、網絡路由優化[35]、最短公超序問題[36]以及系統辨識[37]等方面也有廣泛的應用。

3 計算智能的發展

由于具有分布、高度并行、自學習、自組織、自適應等特性，計算智能在信息處理領域得到了廣泛的應用。然而隨著工業4.0時代的到來和互聯網技術的迅猛發展，計算智能也面臨著很多有待于進一步研究和解決的理論和應用問題。

1)計算智能各種算法的參數選擇現階段還主要依賴于實驗或經驗，缺乏堅實的數學基礎。因此，對各種算法的工作機理、數學基礎和動力學特性等需要進一步深入研究，這是計算智能的基石。

2)更好地接近人腦智能和更好地模擬自然現象本質的新的智能模擬算法將成為發展方向之一。各學科不斷交叉發展，對人腦的模糊邏輯思維、空間想象和形象思維等人類智慧的研究進一步加深，必然推動新的智能模擬算法的出現和發展。

3)計算智能各種智能算法的融合將是發展的一個趨勢。各種不同的算法，各有其特長與局限，對不同的算法進行比較融合，使其優勢互補，就有可能得到更強大的計算能力。比如模糊邏輯和遺傳算法融合形成的模糊遺傳算法和神經網絡融合形成的模糊神經網絡，遺傳算法和神經網絡融合形成的遺傳神經網絡等都比原來的算法表現出了更好的性能，并進一步擴展了應用范圍。

4)大數據時代的到來，也給計算智能的發展帶來新的挑戰與機遇。因為面對多樣、多變的海量數據，計算智能的算法直接在數據上進行分析和處理，不依賴于知識，不需要問題的精確建模，因此適用于大數據分析；計算智能中的模糊邏輯、粗糙集等方法能夠對不完全、不確定的數據進行有效處理，增強了分析結果的客觀性和精確性；計算智能算法具有啟發式特征，有高度的自組織、自適應、泛化和抽象的能力，在解決海量數據所帶來的大規模復雜問題方面表現出了良好的性能。

4 結束語

計算智能是一門涉及計算機科學、物理學、數學、生理學、心理學、神經科學等的交叉學科，它將不同的學科緊密聯系起來，受到了各學科領域越來越多的關注。與傳統方法相比，計算智能更適于解決一些大規模的復雜問題。在人類社會已經進入以大數據、云計算、物聯網等技術為代表的智能化時代的背景下，計算智能的應用前景必然會越來越廣闊。

[1] 蘇建元.計算智能主要算法的比較與融合[J].中國電子科學研究院學報, 2007(1):52-56.

[2] 史忠植.高級人工智能[M].北京:科學出版社,1998.

[3] 董聰,郭曉華.智能計算中的熱點問題[J].計算機科學, 1999, 26(4):5-9.

[4] CHUANG J H, WANG P H. Automatic classification of block-shaped parts based on their 2D projections [J]. Computers & industrial engineering 1999, 36 (3):697-718.

[5] 高曉紅. ART神經網絡的發展與應用[J].電腦知識與技術, 2007( 20):509-526.

[6] 郭鵬. Hopfield網絡在優化計算中的應用[J].計算機仿真, 2002( 11): 22-25.

[7] 周明,孫樹棟.遺傳算法原理及應用[M].北京：國防工業出版社,1999.

[8] 雷英杰,張善文,李續武.MATLAB遺傳算法工具箱及應用[M].西安:西安電子科技大學出版社,2005.

[9] 云慶夏,黃光球,王戰權.遺傳算法和遺傳規劃——一種搜索尋優技術[M].北京:冶金工業出版社,1997.

[10] 朱瑩,向先波,楊運桃.基于混合遺傳算法的雜貨船裝載優化問題[J].中國船艦研究, 2015, 10(6):126-132.

[11] 潘欣.種群分布式并行遺傳算法解化工多目標優化問題[J].化工進展, 2015,34(5): 1236-1240.

[12] 韋勇福,曾盛綽.基于遺傳算法的車間生產調度系統研究[J].裝備制造技術, 2014(11) :205-207.

[13] COLORNI A, DORIGO M, MANIEZZO V. Distributed optimization by ant colonies[C]//Proc. the First European Conference on Artificial Life. Paris: Elsevier Publishing,1991:134-142.

[14] DORIGO M. Optimization, learning and natural algorithms[D]. Milano,Italy:Politecnico di Milano,1992.

[15] DORIGO M, GAMBARDELLA L M. Ant colony system: a cooperative learning approach to traveling salesman problem[J]. IEEE transactions on evolutionary computing, 1997, 1(1):53-56.

[16] SONG Xuemei, LI Bing, YANG Hongmei, et al. Improved ant colony algorithm and its applications in TSP[C]//Proc. the Sixth International Conference on Intelligent Systems Design and Applications. Washington, DC, USA: IEEE Computer Society, 2006:1145-1148.

[17] COLORNI A, DORIGO M, MANIEZZO V. Ant colony system for job-shop scheduling[J]. Belgian journal of operations research statistics and computer science,1994,34(1):39-53.

[18] ZHANG J, HU X M, TAN X, et al. Implementation of an ant colony optimization technique for job shop scheduling problem[J]. Transactions of the institute of measurement and control,2006,28(1),93-108.

[19] MANIEZZO V, COLORNI A. The ant system applied to the quadratic assignment problem[J]. IEEE transactions knowledge and data engineering, 1999,1(5): 769-778.

[20] 黃席樾,張著洪,何傳江.現代智能算法理論及應用[M].北京:科學出版社,2005.

[21] 徐精明,曹先彬,王煦法.多態蟻群算法[J].中國科學技術大學學報,2005,35(1):59-65.

[22] 胡小兵,黃席樾.對一類帶聚類特征TSP問題的蟻群算法求解[J].系統仿真學報,2004,16(2):2683-2686.

[23] HU X M, ZHANG J, LI Y. Orthogonal methods based ant colony search for solving continuous optimization problems[J]. Journal of computer science and technology, 2008, 23(1):2-18.

[24] COLORNI A, DORIGO M, MANIEZZO V. Ant system for job-shop scheduling[J]. Belgian journal of operations research, statistics and computer science,1994(34):39-53.

[25] STüTZLE T, INTELLEKTIK F, INFORMATIK F, et al. An ant approach to the flow shop problem[C]//Proc. European Congress on Intelligent Techniques & Soft Computing. [S.l.]：IEEE, 1997:1560-1564.

[26] BAUCER A, BULLNHEIMER B, HARTL R F, et al. Minimizing total tardiness on a single machine using ant colony optimization[J]. Central European journal for operations research and economics, 2000, 8(2):125-141.

[27] MERKLE D, MIDDENDORF M. An ant algorithm with a new pheromone evaluation rule for total tardiness problems [J]. Real world applications of evolutionary computing, 2000(1803):287-296.

[28] BLUM C. ACO applied to group shop scheduling: a case study on intensification and diversification [J]. Proceeding of ANTS 2002, 2002(2463):14-27.

[29] SALHI S, SARI M. A multi-level composite heuristic for the multi-depot vehicle fleet mix problem [J]. European journal for operations research, 1997, 103(1):95-112.

[30] ANGELELLI E, SPERANZA M G. The periodic vehicle routing problem with intermediate facilities[J]. European journal for operations research, 2002, 137(2):233-247.

[31] HO S C, HAUGLAND D. A tabu search heuristic for the vehicle routing problem with time windows and split deliveries [J]. Computers & operations research, 2004, 31(12): 1947- 1964.

[32] SECOMANDI N. Comparing neuro-dynamic programming algorithms for the vehicle routing problem with stochastic demands[J]. Computers & operations research, 2000,27(11): 1201-1225.

[33] NANRY W P, BARNES J W. Solving the pickup and delivery problem with time windows using reactive tabu search [J]. Transportation research part B, 2000,34(2):107-121.

[34] YAGIURA M, IBARAKI T, GLOVER F. An ejection chain approach for the generalized assignment problem[J]. Informs journal on computing, 2002,16(2):133-151.

[35] CARO G D, DORIGO M. AntNet: distributed stigmergetic control for communications networks [J]. Journal of artificial intelligence research, 1998,9(2):317-365.

[36] MICHEL R, MIDDENDORF M. An ACO algorithm for the shortest common supersequence problem[J]. McgrawHillS advanced topics in computer science series, 1999(20):51-62.

[37] WANG L, WU Q D. Linear system parameters identification based on ant system algorithm [C]//Proc. the IEEE Conference on Control Applications,2001.[S.J.]:IEEE,2001：410-406.

責任編輯：薛 京

Research and application of information processing technology based on computational intelligence

LIU Wei1,2，TIAN E1,2，TAN Miaomiao1,2

(1.CollegeofMechanical&ElectricalEngineering,BeijingUnionUniversity，Beijing100020,China;2.BeijingEngineeringResearchCenterofSmartMechanicalInnovativeDesignService，Beijing100020,China)

As an important branch of artificial intelligence, computational intelligence based on data and biological evolution and cellular network has some characteristics mainly including distribution, parallel processing, self-adaption, self-organization and self-learning, which mainly used the experience of connectionism and behaviorism. Firstly, the origin and concept of computational intelligence are introduced. Secondly, with the artificial neural network, genetic algorithm, ant colony algorithm as an example, the principle and application of the system are described. Finally, the development trend of computational intelligence and some problems to be solved under the condition of new technology are introduced.

computational intelligence; artificial neural network; genetic algorithm; ant colony algorithm

劉偉，田娥，譚苗苗.基于計算智能的信息處理技術的研究與應用[J]. 電視技術，2016,40(12)：51-56. LIU W，TIAN E，TAN M M.Research and application of information processing technology based on computational intelligence[J]. Video engineering，2016,40(12)：51-56.

TN92

B

10.16280/j.videoe.2016.12.010

北京市教育委員會科研計劃面上項目(KM201511417001)；北京市屬高等學校高層次人才引進與培養計劃項目(CCT&-TCD201404093)

2016-08-30