遺傳算法與多Agent遺傳算法操作與性能比較

遺傳算法與多 Agent遺傳算法操作與性能比較摘要：該文主要介紹遺傳算法及其改進的混合算法多Agent遺傳算法在操作和性能上的差異，分析并證明了了遺傳算法求解高維函數(shù)優(yōu)化問題的局限性。通過實驗證明了多Agent遺傳算法的執(zhí)行性能上較遺傳算法具有很大的優(yōu)越性，特別是在求解不高于400維的優(yōu)化問題時。關鍵詞：遺傳算法；多Agent遺傳算法；高維函數(shù)優(yōu)化中圖分類號：TP301文獻標識碼：A文章編號：1009-3044(2011)16-3893-03遺傳算法（Geneticalgorithm，簡稱GA）是進化計算的一個主要分支，是二十世紀六十年代初由美國 Michigan大學的教授所提出的[1]。GA是一類隨機搜索技術，它模擬由個體組成的群體的學習過程，其中的每個個體都代表了給定的搜索空間中的一個可能解。從最初的點（即可能解）出發(fā)，通過不斷的迭代，逐步改進當前解，直至搜索到最優(yōu)解或滿意解為止。目前GA已經(jīng)在人工智能、知識發(fā)現(xiàn)、模式識別、圖象處理、決策分析、產(chǎn)品工藝設計、資源調(diào)度、股市分析等仍然不斷增加的領域中發(fā)揮出了顯著的作用。多Agent遺傳算法（Multi-AgentGeneticAlgorithm，簡稱MAGA）是GA與多Agent技術相結合的一種混合算法， 是由焦李成教授所提出的 [2]。MAGA與GA的實現(xiàn)機制與操作流程有很大不同，主要體現(xiàn)在個體之間的交互、協(xié)作和自學習上。另外從算法執(zhí)行性能上講， MAGA作為一種改進的混合GA在收斂時間、優(yōu)化結果上往往較傳統(tǒng) GA有著很大的提升，特別是在處理超大規(guī)模、 高維、復雜、動態(tài)優(yōu)化問題時 MAGA算法存在著明顯的優(yōu)勢。遺傳算法1.1遺傳算法的原理與實現(xiàn)機制GA是二十世紀六十年代初， 由美國Michigan大學的J.H.Holland教授借鑒達爾文的生物進化論和孟德爾的遺傳定律的基本思想，并從中提取、簡化與抽象而提出的第一個進化計算算法。其中，“遺傳”與“算法”的結合充分體現(xiàn)了生物科學與計算機科學的相互滲透，相互融合 [4]。它借鑒生物界的進化思想，通過計算機來模擬物種繁殖過程中父代遺傳基因的重組與“優(yōu)勝劣汰”的自然選擇機制，以解決科學與工程中的復雜問題。GA啟迪于達爾文的“優(yōu)勝劣汰”的自然選擇機制和孟德爾的遺傳學說。其算法實質(zhì)上是一個不斷循環(huán)迭代優(yōu)化的過程，標準GA的主要執(zhí)行步驟如圖 1所示，主要包括編碼、群體初始化、確定適應度函數(shù)、選擇、交叉、變異、評價和終止判定八步。1.2遺傳算法的局限性GA在解決優(yōu)化問題過程中有如下不足之處：GA在適應度函數(shù)選擇不當?shù)那闆r下有可能收斂于局部最優(yōu)，而不能達到全局最優(yōu)，故適應度函數(shù)的選取對于算法的速度和效果至關重要。對于任何一個具體的優(yōu)化問題，選擇、交叉和變異概率因子對于全局收斂的作用較大。若選擇不當，很可能造成未成熟收斂或過收斂現(xiàn)象。對于高維函數(shù)，GA的收斂速度很慢，甚至不能收斂。GA不能解決那些“大海撈針”的問題。下面通過一組