基于遺傳算法的信息系統(tǒng)優(yōu)選法研究

［摘 要］ 現(xiàn)代企業(yè)管理中，使用信息系統(tǒng)并采用仿真及遺傳算法優(yōu)選方法的目的就是為了更容易、更快捷地做出更好的決策。本文闡述了優(yōu)選仿真方法、優(yōu)選仿真系統(tǒng)和信息系統(tǒng)之間的數(shù)據(jù)傳輸接口以及數(shù)據(jù)優(yōu)選和仿真的時間復雜度等問題，并通過一個基于遺傳算法的調(diào)度實例來實施優(yōu)選法，然后通過仿真來評價每個方案的性能，以確定最適合的方案。

［關鍵詞］ 優(yōu)選法；遺傳算法；仿真法；信息系統(tǒng)

［中圖分類號］F270.7；TP315［文獻標識碼］A［文章編號］1673-0194（2008）09-0077-03

1 簡 介

當前，越來越多的企業(yè)會經(jīng)常遇到資源優(yōu)化配置的問題［1］，除了產(chǎn)品的數(shù)量和質(zhì)量外，一個非常重要的問題就是生產(chǎn)成本，因此在應對市場不穩(wěn)定及產(chǎn)品多樣化的同時，企業(yè)都在尋求獲取更多純利潤的方法。在這種情況下，信息系統(tǒng)和現(xiàn)代企業(yè)支持方法或系統(tǒng)（優(yōu)選法、仿真法、專家系統(tǒng)、數(shù)據(jù)挖掘系統(tǒng)等）的結(jié)合是幫助公司在競爭中取得戰(zhàn)略優(yōu)勢和成功的關鍵。現(xiàn)在的發(fā)展趨勢是把所有有助于建立高品質(zhì)企業(yè)的系統(tǒng)互聯(lián)起來，并借助決策支持系統(tǒng)和人工智能方法，建立一個高級管理信息系統(tǒng)來幫助決策者。

使用優(yōu)選和仿真法實現(xiàn)的生產(chǎn)調(diào)度系統(tǒng)的主要數(shù)據(jù)和信息流動圖如圖1所示。

市場對特定產(chǎn)品及服務的需求會在企業(yè)內(nèi)部引發(fā)一系列的應對措施。根據(jù)市場需求和庫存數(shù)量，企業(yè)都希望采用最佳的生產(chǎn)調(diào)度方案來實施生產(chǎn)。所以，企業(yè)需要在一個仿真模型中實驗，來選擇一個最佳調(diào)度方案。調(diào)度方案優(yōu)選和系統(tǒng)仿真是基于信息系統(tǒng)數(shù)據(jù)庫中的數(shù)據(jù)。本文中描述的優(yōu)選過程是基于遺傳算法實現(xiàn)的，并通過仿真實驗進行了性能測試。

2 信息系統(tǒng)

在構(gòu)建仿真模型和調(diào)度方案實施的開始階段，系統(tǒng)結(jié)構(gòu)數(shù)據(jù)被集成在模型當中，因此模型必須以容易改變和更新數(shù)據(jù)的方式建立，無論輸入數(shù)據(jù)的質(zhì)量如何，必須進行模型敏感度分析。通過這個步驟可以確定各種假設對仿真系統(tǒng)狀態(tài)的影響幅度，有時一個特定的假設會對結(jié)果產(chǎn)生非常大的影響，因此明智的做法是收集有關系統(tǒng)及其運行情況等相關信息。

調(diào)度方案仿真及生產(chǎn)計劃所需數(shù)據(jù)通常是從企業(yè)的信息系統(tǒng)內(nèi)收集而來的。由于很多企業(yè)，尤其是小型企業(yè)，沒有一個足夠先進的信息系統(tǒng)，因此需要升級系統(tǒng)以支持優(yōu)選法及仿真法的實施。同時還必須考慮到信息系統(tǒng)與仿真模型之間數(shù)據(jù)的傳輸。

為了測試調(diào)度方案的性能，信息系統(tǒng)中用于優(yōu)選和仿真的數(shù)據(jù)應當是真實有效的。如果信息系統(tǒng)中的數(shù)據(jù)沒有根據(jù)市場需求進行動態(tài)更新的話（如圖1所示），那么，優(yōu)選就需要重復進行。由于時間復雜度的問題，將會降低調(diào)度的質(zhì)量。在后面描述的例子中將說明信息系統(tǒng)中使用優(yōu)選法和仿真法的過程，這個信息系統(tǒng)能很好地處理生產(chǎn)系統(tǒng)和優(yōu)選仿真系統(tǒng)中的數(shù)據(jù)和事務。

3 優(yōu)選法和仿真法

在這個以基因算法為基礎的調(diào)度方案實例中，主要分析的是一個資源有限的車間式生產(chǎn)。如果需要生產(chǎn)幾種類型的產(chǎn)品，但是每條生產(chǎn)線只能生產(chǎn)一種產(chǎn)品，這就帶來了調(diào)度的問題。基礎調(diào)度方案制訂好時，該調(diào)度方案只能被當成一個可行性方案，在需求變化時有可能改變該方案。在調(diào)度完成后，如果出現(xiàn)緊急指令，則某些工作就可能被提前；如出現(xiàn)取消指令或設備故障問題，則需重新調(diào)度，形成一個新的可行性方案［2］。由于資源限制、時間限制、機器調(diào)整次數(shù)、次序及系統(tǒng)等原因，調(diào)度是一個很復雜的任務。

完整的調(diào)度方案由一定數(shù)量的可行的、不重復的工作組成，并按照可變的順序排列。工作順序在投入生產(chǎn)之前隨時可以加入新的工作從而改變。由于生產(chǎn)調(diào)度的任務是要把一系列的工作以一定順序安排好，以滿足給定標準，因此將展示的調(diào)度形式可以看作是一個組合的、元啟發(fā)式的問題。該任務極其復雜，不是所有的可行性方案都能被接受，因為有些方案可能會超出系統(tǒng)的限度。

為了防止互相沖突的調(diào)度方案出現(xiàn)，本文采用了一種有限制條件的算法。調(diào)度算法在工作列表上選擇第一項工作并優(yōu)先進行調(diào)度。接著該算法選擇下一項工作，并按照限制條件和已有的方案對其進行調(diào)度。該過程隨即在每項工作上重復，直到制訂出一個能滿足工作列表上每項工作標準的可行性方案。在基本方案完成時，需要運用遺傳算法對其進行優(yōu)選。優(yōu)選結(jié)束后，方案將在仿真模型中進行仿真，從而確定其可行性。

3. 1基于遺傳算法的優(yōu)選法

調(diào)度算法運用信息系統(tǒng)中的序列數(shù)據(jù)來構(gòu)建最初的種群，并通過遺傳算法來進行優(yōu)選。遺傳算法把適者生存法和一種以搜索算法進行的規(guī)整但隨機的信息交換方法結(jié)合起來。這種算法首先隨機地把各項工作排序，從而形成第一代的調(diào)度方案，也就是第一代種群。該種群由有限數(shù)量的個體（調(diào)度方案）組成，這些個體每迭代一次即可形成新的一代。通過仿真模型可以對每個種群的適應度進行評估，優(yōu)選過程必須確保只有種群中一部分通過評估，以作為演化新個體的基礎。演化過程是通過遺傳算子來實現(xiàn)的，遺傳算子可把一代的種群變換為下一代的種群。演化過程一直重復，直到產(chǎn)生的調(diào)度方案滿足評價函數(shù)。最后一代的調(diào)度方案將在可視仿真模型中進行模擬，以選擇出最合適或最佳的方案。

要在遺傳算法基礎上構(gòu)建優(yōu)選程序，需要定義4個對遺傳算法操作非常必要的因素：染色體句法、染色體解碼、染色體評估和染色體算子。另外還需要定義遺傳算法應用程序的其他部分，如母體選擇，但這部分一般關聯(lián)不大而且取決于要解決的問題。詳細的遺傳算法敘述見文獻［3］。

同時，還應確定種群評估的數(shù)量。比如種群較多，就可采用依次評估，也可以把種群分為幾個子種群來進行評估。哪種方法更好可通過實驗決定，同時也取決于具體的問題。另外，評價函數(shù)應該也可以評價方案的優(yōu)劣，但由于可能存在相互沖突的評價標準而難以操作。

文獻［4］描述了對于不同遺傳算子和選擇類型、代數(shù)和種群規(guī)模等問題的調(diào)度結(jié)果。在遺傳算法的幫助下并遵守各種限制條件，調(diào)度的目標是找到完成從生產(chǎn)到庫存所耗費的最短時間。優(yōu)選的結(jié)果取決于輸入數(shù)據(jù)和遺傳算法參數(shù)的選擇。參數(shù)選擇的方法稍后介紹。由于基因算法優(yōu)選開始時產(chǎn)生了一個種群，因此所有顯示的結(jié)果是30次迭代的平均數(shù)。

種群規(guī)模從兩方面影響遺傳算法的操作。一方面是每一代中為下幾代提供原材料的個體數(shù)量。另一方面是在擁有同樣代數(shù)的情況下，種群規(guī)模越大效果越好。圖2展示了20代中種群規(guī)模對收斂性的影響。

由圖2分析可知，隨著種群規(guī)模的增加，算法的性能在改善，但這樣會相應增加搜索時間。從種群規(guī)模對測試結(jié)果產(chǎn)生的影響來看，使用包含60個個體的種群是適當?shù)摹Ｈ绻獪p少搜索時間，就可以使用少數(shù)幾代執(zhí)行演化，如圖2所示，種群的適應度在第一個十代之后不會發(fā)生太大的變化。另外，較好的結(jié)果最早在第五代或第六代的時候就出現(xiàn)了。

從當前的種群中選擇個體并將其置于下一代的方法依賴于現(xiàn)有數(shù)據(jù)，但是，大多數(shù)遺傳算法的研究采用精英選擇法［5］［6］。精英選擇法提供足夠多樣的個體和一種可以相對較快地取得最優(yōu)結(jié)果的收斂法。更重要的一個因素是遺傳算子的選擇，其選擇很大程度上依賴于所研究問題的可能解決方法的數(shù)量。

本文希望找到這樣的遺傳算子，它能為最終取得滿意結(jié)果提供可靠的收斂性，同時產(chǎn)生一套可行的評價標準。另外，測量包含60個個體的種群中遺傳算子的影響，實驗證明，不同規(guī)模的種群在可接受的時間內(nèi)可以演化出20代，而且所得的結(jié)果比較滿意并適合實踐應用。

仿真實驗檢測了3種交叉算子和一種變異算子。置換交叉（PermutX）在把兩個個體交叉后執(zhí)行置換，局部順序交叉（LOX）執(zhí)行局部基因排序，而部分匹配交叉（PMX）執(zhí)行部分匹配。變異可以采用不同的方法來完成，針對調(diào)度問題，插入變異（MutVrine）是非常適合的一種選擇。

從圖3分析可知，最適合的算子是LOX算子和MutVrine算子。應根據(jù)調(diào)度系統(tǒng)的具體應用來決定選擇哪種算子。

依據(jù)實驗結(jié)果可以看出，選擇適合的算子是非常重要的。在本文仿真實驗中選擇的是LOX算子，它在少于10代當中就取得了很好的結(jié)果。在選擇遺傳算子和演化參數(shù)后，即可構(gòu)建調(diào)度系統(tǒng)。該系統(tǒng)將簡化人機選擇，使操作員能夠方便地交互和試驗。調(diào)度結(jié)束后，操作員可根據(jù)他們的經(jīng)驗和對生產(chǎn)系統(tǒng)的了解，得到最優(yōu)的、可行的調(diào)度方案。

在遺傳算法優(yōu)選后，應用程序用最短的生產(chǎn)時間找到最適合的調(diào)配方案。最后，在5個可用的調(diào)度方案中，使用LOX遺傳算子得到第20代種群，優(yōu)選花費的時間為56秒。被選的調(diào)配方案在可視仿真模型［6］上得到檢驗，同時觀察系統(tǒng)運轉(zhuǎn)狀態(tài)。圖4展示了最佳的兩個方案的統(tǒng)計結(jié)果。

從顯示的結(jié)果中，可以看出這兩個方案在系統(tǒng)運行中沒有太大的差異。因此，不管選擇哪個方案，系統(tǒng)都應該運行良好。假設操作員選擇方案2，即該方案為目前的可操作方案。該方案可立即開始實施，并持續(xù)，直到方案執(zhí)行結(jié)束。但是，如果在方案實施當中系統(tǒng)中出現(xiàn)大的變化，如故障、阻礙或緊急指令，在完成方案中的特定部分的同時，也需準備一個新的可行性方案，并隨變化而變化。

4 結(jié) 論

本文闡述了信息系統(tǒng)的優(yōu)選和仿真對想取得或保持市場戰(zhàn)略優(yōu)勢的企業(yè)的重要性，并通過一個基于遺傳算法的調(diào)度實例來實施優(yōu)選法，并通過仿真來評價每個方案的性能，幫助操作員選擇最適合的方案來實施。

以遺傳算法為基礎的調(diào)配方法與仿真法的結(jié)合被證明是有效和成功的。由此得到的經(jīng)驗將加速集成管理的信息系統(tǒng)的進一步發(fā)展，并使公司取得戰(zhàn)略優(yōu)勢。遺傳算法在智能決策和控制系統(tǒng)中的運用具有可行性和可操作性，該調(diào)度方案改善了企業(yè)生產(chǎn)中產(chǎn)品的流動，從而降低了管理成本和生產(chǎn)成本。

主要參考文獻

［1］ E A Silver，D F Pyke. Inventory Management and Production Planning and Scheduling［M］. NY：John Wiley Sons， 1998.

［2］ M Kljajiaelig;， I Bernik， U Breskvar. Production Planning Using Simulation and Genetic Algorithms in Multi-criteria Scheduling Optimization［C］. //editors: Florjanèiè， J， Paape， B. Organisation and Management: Selected Topics［M］. Frankfurt：P Lang， 2003：193-208.

［3］ A Papler， R Leskovar， A Nemec， V Rejec. Interactive Multicriteria Production Scheduling［C］. Proceedings of the 6th International Symposium on Operational Research， 2001：153-158.

［4］ M Kljajiaelig;， I Bernik， A #352;kraba. Simulation Approach to Decision Assessment in Enterprises［J］. Simulation，2000，75（4）：199-210.

［5］ G Syswerda. Uniform Crossover in Genetic Algorithms［C］. Proceedings of the 3rd International Conference on Genetic Algorithms， 1989.

［6］ G Syswerda. Schedule Optimization Using Genetic Algorithms［C］. // Davis L（ed）. Handbook of Genetic Algorithms［M］. NY：Van Nostrand Reinhold，1991.