自適應協同進化算法及其在創新設計中的應用研究

摘 要：提出一種自適應協同進化算法，對其進行了數學描述。設計了一個支持該算法的創新設計系統，為分布式環境下設計人員的協作和創新思路的開拓提供了支撐平臺。算法中自適應學習的引入為在設計中自動而有效地使用先驗智能提供了可行性。最后以一個建筑實例的設計為例對所述的方法和系統加以描述。

關鍵詞：協同進化； 自適應； 創新設計

中圖法分類號：TP391．72 文獻標識碼：A 文章編號：1001-3695(2006)10-0036-03

Research on Adaptive Coevolution Algorithm and It’s

Application in Creative Design

ZHANG Guijuan， LIU Xiyu

(College of Information Management， Shandong Normal University， Jinan Shandong 250014， China)

Abstract:An adaptive coevolution algorithm and its mathematical definition are proposed， based on which a design system is constructed， who offers a supporting framework for cooperative work and creative design among distributed designers. Meanwhile the adaptive leaning in the algorithm enforces the feasibility of using design experience automatically and effectively. Finally， a case study for an architecture design is described to illustrate the method and system proposed.

Key words:Coevolution; Adaptive; Creative Design

1 引言

自20世紀末以來，計算機輔助概念設計逐漸受到人們的重視，利用計算機的快速運算能力和人工智能技術，輔助設計者進行創新概念設計，成為當前設計領域的研究熱點之一。尤其是近年來，國內外的一些學者將遺傳算法應用于創新設計的研究，顯示了遺傳算法對創新設計的支持[1]。盡管對創新設計的研究已經取得了很多令人矚目的成果，但設計（特別是有創意的設計）對人的智能有強烈依賴性，如何將計算智能應用于該過程還是一個新的而且很有吸引力的研究課題。同時人們在研究和實踐過程中逐漸意識到設計是一個群體協作的工作過程，現代產品的復雜性使得單個設計人員已不可能勝任復雜的設計任務。因此，新一代計算機輔助設計的研究必須為設計人員提供分布式環境下的設計工具和支撐框架，推進設計的自動化進程，以生產出高質量、低成本、有創意和有市場競爭力的產品[2]。

本文提出了一個自適應協同進化算法，介紹并實現了一個支持該算法的創新設計系統，目的是利用進化算法對創新設計的支持和協同算法的自適應學習能力，為分布式環境下的設計人員提供協作和設計的智能支撐平臺，更好地為并行和協同設計過程服務，加快設計的自動化進程。

2 協同進化算法

2．1 相關的研究工作

遺傳算法作為目前常用的一種優化技術，采用基于個體自身適應度的進化模式，未考慮其進化的環境和個體之間的復雜聯系對個體進化的影響，在應用中易出現未成熟收斂，并且收斂速度較慢等缺陷。現有的改進方法雖然很多[3，4]，但如果仍然只是通過個體適應度來控制個體進化，則難以獲得滿意的效果。協同進化(Coevolution)是近年來針對遺傳算法(GA)的不足而興起的一個研究熱點，意指多個種群通過適應度的關聯同時進化，最早由Ehrlich和Raven提出[5]。這一概念在理論進化中非常重要，它被廣泛定義為一種適應度基于種群密度、種群自身及相互作用種群的遺傳成分的進化，特別適合于復雜進化系統的動態描述[6]。在協同進化的模型和算法研究方面，由于研究才剛剛起步，目前還沒有成熟的統一框架，各個領域的研究者分別從不同的研究領域探討，獲得了一些成果。例如Husbands提出的子群體間的相互合作和競爭的概念[7]，Hills提出基于寄生物與寄主模型[8]，Potter[9，10]認為合作型協同進化是一種宏觀的協同進化方法，它結合并擴展了早期的進化計算的思想，以提高其通用性和在沒有人工干涉的情況下演化互適應子群體的能力。競爭型協同進化目前主要在人工智能游戲中討論[11，12]。國內對于協同進化算法的研究則始見于 20世紀90年代末期，對協同進化算法的研究才剛剛開始，其研究領域也不全面。

2．2 自適應協同進化遺傳算法

在解決優化問題時，協同進化算法將最優化問題的一個完全解分解為部分解[9]，一個部分解反映問題的一個方面，利用進化算法進化部分解形成的種群，通過部分解的組合來搜索完全解的空間，在處理復雜問題時顯示出了良好的適應性。對于部分解如何選擇合作者，不少學者提出貪婪法、隨機選擇或選擇平均個體的形式，雖然對特定問題解決有一定的成效，但并不具備普遍性。本文提出利用策略庫存儲特定問題的策略信息，為部分解組成完全解提供了支持，使算法具有很好的適應性。同時根據學習和進化兩種不同的自適應過程，提出了一種自適應協同進化算法，其數學定義如下：

定義1 自適應協同進化。多群體系統中種群之間為了相互適應各自屬性的進化而進化，同時各種群為實現統一目標而對其策略空間進行自適應學習的現象稱為自適應協同進化。

定義2 個體。個體表示為I=(Rit，St)，其中，Rit表示時刻t個體I的屬性，是個體外在靜態特征的描述，St表示時刻t個體I的策略集，St={s1，s2，…，sn}表示個體的行為特征。個體的表現型為屬性與策略集的集成表示。

定義3 種群。一個種群是若干個體Ij的集合，表示為P={Rpi，Ij，Spi}，其中，Rpi為時刻t種群P的屬性，Spi為時刻t種群P的策略空間，Ij為P中的個體（j=1，2，…，k）。種群P的聯合策略空間Spi=(st，1×st，2×…×st，ki)。

定義4 系統。一個系統由若干的種群Pi組成，系統處于一定的環境 E之中，對于演化系統，種群P和環境E均在進化著，保持動態變化，因此考慮時間因素后系統表示為一個三元組Ct=(Pt，Et，Sst)，其中Pt={Pt，1，Pt，2，…，Pt，N)，t=0，1，2，…。系統的聯合策略空間Sst=(SP1t×SP2t×…×SPNt）。

定義5 個體適應度。種群Pi中個體的適應度受到種群內、種群間的相互作用和環境影響，可以表示為μt(i，k)=f(Pt，j，Pt，i′，Et)，i=1，2，…，N。μt(i，k)表示群體Pi中個體k在t時刻的適應度，它既包含了群體內部的生存競爭，也包含了群體之間的協同進化，還包括來自環境的選擇壓力等影響。

定義6 自適應學習。種群P={Rpi，Ij，Spi}，其聯合策略空間為Spi=(st，1×st，2×…×st，ki)，待學習策略集St={s1，s2，…，sn}，取i=Random(1，ki)，則種群P中個體i自適應學習后策略集為St，學習后的聯合策略空間Spi=Spist，i×St。

算法的流程描述如下：

（1）依據問題域劃分種群，所有種群組成一個進化系統；

（2）設定各項遺傳進化參數；

（3）多種群進化，當種群進化到預定代數之后，由某設定子群體將當前最優解個體放入最優解點集；

（4）系統根據最優解點集信息及策略庫搜索策略集，由其他各種群進行自適應學習，并進行指定代數的進化；

（5）剩余種群提交最優解于最優解點集，由系統組成完全解；

（6）判斷結束條件，若滿足則結束，否則轉（3）。

整個算法通過對種群內部個體屬性的遺傳進化及個體策略集和種群聯合策略空間的自適應調節，達到自適應協同進化的目的。而事實上，進化不僅僅是一種優化工具，也是一種搜索和創新工具，因為它通過結合其他的選擇來合成解決方案。通過交叉和變異兩步最有用的操作產生新的難以預料的個體，為設計者拓寬設計思路提供了創新

支持。同時個體策略集和種群策略空間的自適應調整為在設計中自動而有效地使用先驗智能提供了可行性。

3 自適應協同進化設計

以自適應協同進化算法為基礎，我們設計并實現了一個自適應協同進化系統。系統采用C/S結構，將大型分布式的創新設計抽象成自適應協同進化算法的若干種群協同進化。服務器進程負責客戶端進程的通信、協同和實例的組裝；客戶端進程負責組件的創新設計。

3．1 種群編碼及遺傳操作

考慮到概念建筑設計實體組件的屬性，如建筑外觀曲線、實體生成技術等對組件效果影響較大的控制屬性，我們設計染色體編碼格式為(p1，p2，…，pn)，其中pi(1≤i≤n)為實數，代表曲線控制點，個體染色體編碼決定了建筑外觀的二維曲線輪廓。同時設個體策略集St={s1，s2，…，sn}為一個n位二進制串，控制組件三維外觀。交叉、變異等進化操作是在個體染色體基礎上進行的，顯示了對建筑組件二維輪廓線的創新支持；而自適應學習的學習對象是個體策略集，因此可以有效利用已有的設計經驗，使得各建筑組件的三維外觀完美搭配從而最終形成整個建筑體。圖1為兩個個體及交叉和變異的結果。

按照自適應協同進化模型，個體的適應度應受種內競爭、群間協作和環境選擇壓力三個因素制約，因此我們設個體適應度：

μt(i，k)=f(Pt，j，Pt，i′，Et)=λ11(I)+λ22(P)+λ33(C)，i=1，2，…，N

其中，λi為權重參數，描述個體適應度對三個決定因素的依賴程度，∑3i=1λi=1。進行常規設計時，我們可以從用戶那里得到需求并可將其轉換為目標函數，而對于有創意的設計，種內競爭的適應度值1（I）可由設計師決定。群間協作適應值2（P）是利用個體策略集與需求策略集（待學習）的差異信息來描述個體的協作能力，與需求越相近則協作能力越好。環境選擇壓力刻畫了一個建筑整體對某部件（種群）的需求程度，需求度越高，則3（C）也越大；當需求度為0時，表明該組件對于建筑整體來說可有可無，可以略掉該組件的設計，將相應種群刪除。

3．2 相關度矩陣與策略庫

常識上建筑個體的美觀并不單由一個組件決定，而在于各個組件的搭配效果，由此形成了各種不同的建筑風格。在系統中，由于個體的策略集決定了組件的三維外觀，我們設計了相關度矩陣記錄兩個組件策略集的相關度。矩陣行和列分別代表組件的不同策略集，元素值為[0，1]之間的實數，值越大表明矩陣對應行和列的相關度越大，搭配效果也就越好。初始化為零矩陣，通過對優秀實例的學習進而修改矩陣元素值。策略庫為一個存放各種策略集的表。設計初始，由于系統沒有生成設計實例，可由人工確定若干典型的建筑設計實例并對其部件分類，確定各分類部件的策略集，根據設計師的評價值獲取不同組件特定策略集之間的關聯程度，載入關聯矩陣中。設案例評價值為δ，組件（Ξ1，Ξ2，…，Ξn），策略集標號為（K1，K2，…，Kn），設組件Ξi，Ξj對應相關度矩陣為Mij，修改后矩陣中元素值的變化為mij=λmij+(1-λ)δi=Ki且j=Kj

mij其他，λ∈[0，1]為調節參數，即不同策略集的關聯組件之間具有連接美感時，相關度矩陣將如實記錄其關聯程度。隨著設計的進行和實例庫的不斷擴充，系統可以自動且有選擇地利用其本身設計出的實例對相關度矩陣進行修改。

使用相關度矩陣和策略庫，種群內部的個體可以對先驗策略集進行自適應學習，同時先驗策略集又作為個體適應度評價的一個方面成為種群之間協同的一種方式。這樣既實現了不同群體設計的并行化，又保證了組件之間的連接美感，便于設計出令人滿意的產品。

4 應用實例

我們采用VC++6．0在Windows XP平臺上開發了上述創新設計系統，三維引擎Acis實現了建筑組件的可視化，用Socket技術完成服務器進程與客戶端進程的通信，利用SQL Server 2000設計模型庫和實例庫。將建筑分為六個子群體：樓頂、樓頂修飾、樓體、基座、雨篷、門柱等種群；知識庫設計三個相關度矩陣，分別是樓頂—樓體、樓體—基座、樓頂—基座相關度矩陣；策略庫分別設有樓頂、樓體以及基座的策略集。系統為設計師提供了前面所述各項參數的接口，設計師可按照自己的喜好確定各項參數的取值，以充分體現設計以人為本的思想。在設計過程中，設定樓體種群首先向服務器進程發送優秀個體，對樓頂及基座種群引入自適應學習過程。圖2為設計中樓頂種群的某個體自適應學習前后的三維表現。圖3為系統生成的一個設計實例。

5 結束語

概念設計是產品設計過程中最能體現人的智能并決定產品性能和成本的重要階段。將概念設計的創新研究與計算機技術緊密結合起來，通過使用計算模型和計算機工具，利用計算機的高信息存儲量以及可視化手段對支持創新設計將是一種行之有效的方法。本文提出的自適應協同進化算法及基于該算法的創新設計系統，將多種群協同進化模式應用于協同設計過程中，在利用生物演化的思想進行創新設計的同時又引入了自適應學習過程，使得系統在動態設計中智能性地使用先驗知識，提高了設計的效率。以該方法設計的建筑設計系統具備自適應能力，隨著知識庫的不斷擴充，必將為設計者提供更多更好的輔助信息。

參考文獻：

[1]Pan Yunhe. Proceedings of the 4th International Conference on Computer Aided Industrial Design and Conceptual Design[C]. Beijing: International Academic Publishers Corporation， 2001.

[2]Frazer H J. Design Workstation on the Future[C]. Proceedings of the 4th International Conference on Computer Aided Industrial Design and Conceptual Design， Beijing: International Academic Pubulishers，2001.713.

[3]Goldberg DE， Richardson J. Genetic Algorithms with Sharing for Multimodel Function Optimization[A]. Grefenstette JJ. Proceedings of the 2nd International Conference on Genetic Algorithms[C]. 1987.41-49.

[4]Rudolph G. Convergence Analysis of Canonical Genetic Algorithms[J]. IEEE Transactions on Neural Networks，1994，5(1):96101.

[5]Rosen C， et al. New Methods for Competitive Coevolution[J]. Evolutionary Computation， 1997，5(1):129.

[6]曹先彬，羅文堅，王煦法.基于生態種群競爭模型的協同進化[J].軟件學報， 2001，12(4):556-562.

[7]Husbands P， F Mill. Simulated Coevolution as the Mechanism for Emergent Planning and Scheduling[A]. R K Belew， L B Booker. Proceedings of the 4th International Conference on Genetic Algorithms[C]. 1991.264-270.

[8]Hillis D W. Coevolving Parasites Improve Simulated Evolution as an Optimization Procedure[A]. C G Langton， C Taylor， et al. Artificial LifeⅡ， SFI Studies in the Science of Complexity[M]. Addison Wesley， 1991.313-324.

[9]Mitchell A Potter， Kenneth A， et al. A Cooperative Coevolutionary Approach to Function Optimization[A]. Y Davidor. Proceedings of the 3rd Conference on Parallel Problem Solving from Nature[C]. SpringerVerlag， 1994.249-257.

[10]Mitchell A Potter. The Design and Analysis of a Computational Model of Cooperative Coevolution[D]. George Mason University，1997.

[11]Moeko Nerome， Koji Yamada， et al. Competitive Coevolution Based Gamestrategy Acquisition with the Packaging[A]. L C Jain， R K Jain. The 2nd International Conference on Knowledgebased Intelligent Electronic Systems[C]. 1998.184189.

[12]Jean M Claverie， Kenneth De Jong， Alaa F sheta. Robust Nonlinear Control Design Using Competitive Coevolution[C]. IEEE Proceedings of the 2000 Congress on Evolutionary Computation， 2000.403-409.

作者簡介：

張桂娟（1981-），女，山東日照人，碩士研究生，主要研究方向為進化計算與創新設計；劉希玉（1964-），男，山東濟南人，教授，博導，博士，主要研究方向為進化計算與人工神經網絡。

注:本文中所涉及到的圖表、注解、公式等內容請以PDF格式閱讀原文