基于遺傳蟻群算法的制造企業遠程服務動態配置

摘要：在客戶需求多樣化和激烈市場競爭的背景下，本文主要討論了跨地域企業之間遠程服務配置和調度過程中的優化問題。為此，本文以某一制造業企業服務平臺為例，采用基于遺傳算法與蟻群算法相融合的遠程服務配置方法進行驗證，分析其效果。本文的結論是，將Holon理論引入到企業遠程服務配置中，實現跨地域企業遠程服務合理配置與優化調度，從而使企業具有良好的環境適應性。

關鍵詞：Holon 制造企業 敏捷制造 企業遠程服務配置

引言

在激烈市場競爭的背景下，為了滿足客戶需求多樣化，人們在生產工藝和制造技術方面做了大量的研究工作。產生了許多先進的制造系統模式，如并行工程（CE）、敏捷制造（AM）、虛擬制造（VM）等制造系統模式。其中敏捷制造被認為是下一代制造策略而受到美國等發達國家的普遍重視。國際合作研究計劃智能制造系統（IMS）項目之一的合弄制造系統（HMS）則被作為實現敏捷制造的基礎而得到了由來自澳大利亞、加拿大、歐洲、日本和美國的31個成員組成的國際合作研究機構的認真深入研究。[1]

迄今為止，針對合弄制造系統的研究仍屬于一個比較前沿的課題。現有的一些理論還不是十分成熟完善，缺乏一個系統的科學方法。近些年來，一些與經典的數學規劃原理截然不同的、試圖通過模擬自然生態系統機制以求解復雜優化問題的人工智能算法相繼出現（如神經網絡、模擬退火、禁忌搜索、遺傳算法、螞蟻算法等），大大豐富了現代優化技術，也為NP 類問題提供了切實可行的方案。但無論單純利用遺傳算法還是蟻群算法都無法獲取較好的實際效果。因為遺傳算法具有快速隨機的全局搜索能力， 但對于系統中的反饋信息利用卻無能為力， 當求解到一定范圍時往往做大量無為的冗余迭代， 求精確解效率低。螞蟻算法是通過信息素的累積和更新收斂于最優路徑上， 具有分布式并行全局搜索能力。但初期信息素匱乏， 求解速度慢。因此本文提出的算法是將遺傳算法與螞蟻算法融合， 采用遺傳算法生成信息素分布， 利用螞蟻算法求精確解， 優勢互補，仿真表明取得了非常好的效果。[2]

1、問題描述

1.1有關概念的引入

Holon是復雜系統中同時具有“整體”和“部分”屬性，既具有“自治性”又具有“協作性”的實體，它既是自包含的整體（Self-contained-whole），又是相互依存的部分（Dependent-Part） 。[3-5]

1）Holon：制造系統用于轉換、運輸、儲存、確認信息和物理對象的自律的、協作的模塊。合弄由信息處理部分和通常再加一個物理處理部分組成。一個合弄可以是另一個合弄的一部分。

2）自治（Autonomy）：一個實體生成和控制它自己的計劃或策略的能力。

3）協作（Cooperation）：一個組織實體共同可以接受的計劃并且一起執行這些計劃。

4）Holon結構（Holarchy）：能夠協作達到一個目的或目標的Holon系統。Holon結構定義了Holon協作的基本規則，同時也就限制了Holon的自治性。

5）Holon制造系統（Holon Manufacturing System）：集成了所有制造活動的Holon結構，包括從訂單、設計、生產、進入市場，以實現敏捷的制造企業。

6）Holon屬性：一個實體成為Holon的屬性。自治性和協作性是最基本的Holon屬性。

7）Holon性（Holonomy）：一個實體呈現出Holon屬性的程度。[6]

通過引入具有自治協商性能的Holon概念，構建面向跨地域企業的基于Holon的遠程服務集成管理體系結構，如圖1。

■

圖1 基于Holon的遠程服務集成管理體系結構

Figure 1 Remote Service Integrated Management System Structure

1.2.遠程服務動態配置與優化調度

圖2為企業遠程服務Holon 的動態配置機制。調度Holon 通過與訂單Holon 協作，采用周期性的或基于事件的調度調整技術，不斷調整調度計劃以優化服務分配。調度Holon 首先通過訂單處理模塊調度Holon 通過與訂單Holon 協作，采用周期性的或基于事件的調度調整技術，不斷調整調度計劃以優化服務分配。調度Holon 首先通過訂單處理模塊。

圖2 企業遠程服務-Holon 的動態配置機制

Figure 2，Remote Service of Enterprise—Dynamic Allocation Mechanism of Holon

2、遺傳算法的優化機理與模型描述

遺傳算法是由美國密執安大學的John Holland教授于1975 年首先提出的一類仿生型優化算法。其優點是具有大范圍全局搜索的能力和潛在的并行性；其缺點是對于系統中的反饋信息利用不夠，當求解到一定范圍時往往做大量無為的冗余迭代，求精確解效率低。[7]

2.1 染色體選擇、編碼及初始種群生成

染色體使用蟻群算法中的參數：a，β，p，t，q。這樣可以利用遺傳算法確定蟻群算法的最優參數組合；由于實數編碼的遺傳算法具有精度高、搜索空間大、易于引入特定領域的啟發信息等優點，故蟻群聚類算法中采用十進制實數編碼；初始種群根據預設數量采用隨機方式生成。

2.2 遺傳操作

2.2.1 適應度函數的選取

在遺傳算法中，適應度函數的選取是相當重要的，它關系到算法的收斂速度與所得解的優劣。適應度函數的選取要與要解決的問題相結合，由目標函數決定。本文中適應度函數F定義為F=Fr，其中Fr 為評估聚類算法的F-Measure 函數即■。F-Measure，值越大，相應個體的適應度就越高。采用度量值（F-Measure）法作為聚類算法的評估函數。F-Measure 融合了信息檢索中的查準率與查全率的思想，F-Measure 值越高，聚類效果越好。—個聚類J及與此相關的分類i的查準率與查全率定義為： ■ （1）

■ （2）

其中Nij是在聚類j 中分類i的元素數；Nj 是分類i中的元素數；Nj 是聚類J中的元素數，分類i的F—Measure定義為：

■ （3）

■ （4）

2.2.2 個體選擇

采用錦標賽選擇法，根據適應度函數選取進行交叉的個體。基本思想是：從群體中任意選擇一定數目的個體，其中適應度最高的個體保存到下一代。這一過程反復執行，直到保存到下一代的個體數達到預先設定的數目為止。

2.2.3 交叉與變異操作

交叉算子，采用均勻交叉方法：依概率交換兩個父輩個體基因串的每一位。過程為：首先，隨機產生一個與父輩個體基因同樣長度的二進制串，稱為交叉模板。然后根據模板對兩個父輩染色體進行交叉，得到兩個新的后代個體。

變異：采用高斯變異方法，這種方法起源于進化策略。一般在進化策略中的一個個體包含兩個元素（x，or），其中第一個向量x 表示搜索空間中的一個點，第二個向量or 表示標準差。后代（x′，or′）由下式產生：

■ （5）

■ （6）

其中N（0， Δσ）是均值為0，標準差為σ的獨立高斯隨機數向量。

3、遺傳算法與蟻群算法的融合

蟻群算法（ant colony algorithm）是由意大利學者M.Dorigo等人于20 世紀90 年代初期通過模擬自然界中蟻群集體尋徑的行為而提出的一種基于種群的啟發式仿生進化算法，其優點是搜索精確度高，缺點是初期信息素缺乏，導致搜索速度慢。[11]

3.1遺傳算法與蟻群算法銜接

傳統的螞蟻遺傳混合算法都通過設置一個固定的迭代次數來控制遺傳算法和螞蟻算法的融合，即使種群進化效果不理想，其算法也要在繼續進行數次的無用迭代后才轉向另一種算法，使算法整體收斂速度偏慢。針對此缺點，本文采取一種動態螞蟻遺傳算法（DAAGA）。該算法的具體步驟如下：

①設置遺傳操作的最小迭代次數■和最大迭代次數■

②在設定的迭代次數范圍內，如果連續n代，都滿足■ 其中， ■（ ■表示遺傳算法第n代種群的最大適應度值，■表示遺傳算法第n代種群的平均適應度值）。則結束遺傳操作，生成信息素，更新全局解，開始調用蟻群算法。

3.2信息素更新方法的改進

動態螞蟻遺傳算法（DAAGA）中，設■為現有種群的最優解的值，在用全局最優解更新信息素時，■設定為全局最優解的值，則利用螞蟻算法的解。遺傳算法每代最優個體以及全局最優解更新信息素的規則如下：

■其中，■

4、算法仿真結果

本文以某一個制造系統的遠程服務平臺為例，采用ACA（蟻群算法）與DAAGA（動態螞蟻遺傳算法）作比較，分析其效果。實驗數據采用UCI 機器學習庫的Wine，Iris數據集和Zoo數據集，見表1。

表1 測試數據集描述

Tab1 Description of Test Data Set

測試數據集分別用ACA（蟻群算法）與DAAGA（動態螞蟻遺傳算法）進行測試。在ACA中，參數a， β，p，t，q分別取40，100，0.1，20，300，最大迭代次數取30 次。在DAAGA 中種群大小為30，交叉概率為0.8，變異概率為O.2，最大代數為50。

圖3所示的是數據集Iris中150個數據及其聚類結果，（a），（b）分別是ACA 和DAAGA對Iris 數據集聚類的結果，圖中△，○和口分別表示類別Setosa，Versico-lour和Virginica。

■

（a） ACA 聚類結果 （b） DAAGA 聚類結果

圖3 Iris數據集的聚類結果

Figure 3 Data Set of Iris and clustering Results

從圖中可以直觀地看出DAAGA較ACA的聚類效果要好，更接近于真實分類。表2所示的是用ACA 和DAAGA 分別對2個數據集進行100 次測試的平均結果。

表2 兩種算法的測試結果

Tab2 Two kinds of Test Results

根據表2比較，實驗中各聚類數假設是已知的，與各數據集的分類數相同。從測試結果中可以看出DAAGA 的正確率比ACA 算法均有不同程度的提高，從而實現跨地域企業之間遠程服務合理配置與優化調度，達到企業遠程服務配置的自協商，使現代企業具有良好的環境適應性。

5、結論

本文討論了跨地域企業之間遠程服務的配置和調度過程中的優化問題。本文通過將Holon 理論引入到遠程服務配置管理中，首先構建了面向跨地域企業的基于Holon 的遠程服務集成管理體系結構。其次通過描述企業遠程服務Holon 間數據和功能關系，構建服務Holon 間協商方案的接收標準和服務Holon 間通訊協議，建立了基于Holon 的企業遠程服務優化調度機制。通過構建基于Holon 的遠程服務控制模型的通訊機理，建立基于Holon 的企業遠程服務優化調度機制。最后，并在此基礎上，構建基于Holon 的遠程服務自動協商規則和策略。從而實現跨地域企業之間遠程服務合理配置與優化調度，達到企業遠程服務配置的自協商，使現代企業具有良好的環境適應性，為解決跨地域企業之間遠程服務的配置和調度過程中的協商問題，使企業具有良好的環境適應性，提高生產效益。

參考文獻：

[1].唐任仲.敏捷制造基礎-合弄制造[J].工程設計，1996（1）：8-11

[2].段海濱. 蟻群算法的原理及其應用[M].北京：科學出版社， 2005.

[3].侯曉莉 李 言 李淑娟，Holon技術在敏捷制造系統中的應用研究， 自動化儀表.2006，27（5）：5-12.

[4].巫家敏， 張衛山，合弄制造-一種先進制造模式的探討[J]，機械科學與技術，2003，19（2）：339-34l.

[5].周華，楊建軍，基于全能體的MES構建[J]，制造自動化，2001，23（2）：13-16.

[6].Jie Zhang， Liang Gao， A holonic architecture of the concurrent integranted process planning system [J].Materials Processing Technology， 2003： 267- 272.

[7].熊志輝，李思昆，陳吉華，遺傳算法與螞蟻算法動態融合的軟硬件劃分[J].軟件學報.2005，16（4）：503-511.

基金項目：國家自然科學基金資助項目（71271138）；上海市教育委員會科研創新項目（12ZS133）；上海市一流學科項目（S1201YLXK）。