ixon@seed.net.tw最佳化 (Optimization)
Evolver---以基因演算法為基礎之最佳化軟體
基因演算法 (Genetic Algorithms, GA) 簡介
在1960年代，John Von 提出一個自我複製的理論而奠定基因演算法之基礎。之後，美國密西根大學的Holland延續此觀念於1970年代提出基因演算法，其理論主要是根據達爾文的進化論發展而來，亦即母群體隨著世代演化競爭-「物競天擇，適者生存」的原理及受控變化-「複製、交配、突變」保留適應力較佳的染色體。由自然的角度來看，演化是在動態變化的環境下逐漸演化的一種適應 (adaptation) 過程，並非在靜態環境下立即可得的最佳化結果。在演化過程中的系統會趨向複雜。因此演化可視為適應性複雜系統 (adaptive complex system) 的變化過程，同時也是在生命與智慧本質中的必要基本過程。
基因演算法為一個強而有效隨機的最佳化搜尋方法，是最佳化的方法之一，模仿學習大自然生物的遺傳演化及篩選的特性，經由競爭淘汰進而保留生命力較強較適合生存的個體，它模仿生物進化的過程來獲得最好的結果，使問題較不易陷入局部最佳解，而向全域的最佳解收斂。基因演算法有理論作為基礎且經驗證明其在複雜空間中強韌的搜索能力。
GA是根據一組染色體 (chromosome)，稱作population，一個染色體表示問題的一個可能的解。染色體通常由一串變數所組成，其中的每個元素稱為基因，而基因的值則稱為allele，基因演算法針對各類問題，有種種不同的行為機制、個體結構 (編碼方式)、和群體組織。根據欲求解問題的環境，所設計出計算的方法，其個體會有不同的結構和行為─這就是根據環境特性的啟發 (heuristic)，來設計參數所形成的表現型 (phenotype)。而基因演算法中，其個體的基本組成都來自位元 (bit) 的結合─資訊基本單位的結合，所形成的基因型 (genotype)。在實際應用上，如果要使基因演算法更有效的解決問題，就必須針對各類問題，設計其表現型，以求運用各類問題的相關知識，來加快其演化速度。基因演算法可視為類似隨機搜尋的最佳化演算法。因為其本質是非決定性 (nondeterministic)，所以能搜尋問題空間裏所有的可能解答。而在計算的群體中，大量個體追隨環境利基，聚集而形成各式族群 (species)。不同族群也就代表了用以解決問題的不同途徑與其資訊─這就是基因演算法含有多樣性以解決問題的能力。尤其在大部份複雜非線性的數學問題上，因為缺乏解析決定的求解方法，基因演算法便成為最有效的數值分析工具。
GA之運用領域
GA 能迅速的找出困難問題的最佳解，現今電腦計算日漸強大，所以基因演算法之最佳化已漸漸被廣泛的應用在各個領域；如：最佳化參數設計、工程設計、排程問題、分類系統、控制系統工程等等，且都有不錯的成果。主要有以下幾個常用領域：
1. 人工智慧之運用：提供最佳化搜尋法，或結合其他搜尋法增加求解速率。
2. 機器視覺：運用在圖形辨識的方面。
3. 財務：對公司的財務作最佳的運用。
4. 物流：把貨物用最少的運送成本，準時送至每一客戶手中。
5. 排程：工廠的工單作最佳的安排以滿足交期等限制。
6. 資源分配：把資源做分配以做出最有效的利用。
7. 製造：使所有機器在最佳化的情形下，能做最完善的利用及保養。
8. 預算：在有限的預算下做最有效的利用。
9. 工程運用：對工程的進度安排及分配工作的執行人數做出最佳的組合。
Evolver 介紹
以往GA的缺點被認為在於計算時間長，但是此缺點也由於現今電腦技術的進步而漸漸的被克服了。Evolver已超越了傳統的"solver"方式而使用基因演算法來解決最困難而且之前被認為無解的問題，像一些需要不斷查詢複雜資料表格的問題，此類問題就像是自然界中的進化過程。基因演算法能解決一些其他方法無法解決的問題，而Evolver讓使用者更簡單的應用這個演算法到他們商業用途上。Evolver會產生解答：例如最好的搭配或是最有效率的輸入組合，這些結果可以降低成本而且顯著的提昇工作或是產品的表現。
Evolver主要功能
² 轉換Recipe -把組合中的每一獨立變數不斷的轉換，找出最佳的組合。
² 分群Grouping -把一母體中的各種元素分做不同的群體。例如：把一群工人分配到最適當的工作，或者如何把存貨做最有價值的處理。
² 表單安排Order -有一整列的元素。例如：學生如何選課。工廠如何把所有的工單作最佳的組合。
² 預算控制Budget -做出不超過總成本的最佳解。
² 專案執行Project -專案執行的各種路徑及方式以元素表示，尋找出最適解但不違反各階段之優先權重的限制。
² 排程Schedule -滿足所有限制的最佳解，並且不超過所限制的時間等限制式。
Evolver具有基因演算法的所有特性，而且並不需要太高深的技術支援，對於電腦硬體及軟體並無嚴苛的限制，使用者也不需要具備十分深厚的基因演算法理論基礎，只需要有基本的認識即可，軟體需求也僅要求具備EXCEL便可使用，對於個人學術研究或公司商業運用在最佳化的範疇上，不失為一方便且效率極高的工具。
· Evolver : The innovative Optimizer for Windows
中崗科技有限公司 台北市和平東路二段259號9樓 Tel:02-27045535 / Fax:02-2754-1785
Ixon Technology 9F, No.259,Sec. 2, Ho Ping East Road, Taipei, Taiwan, R.O.C. 106
Copyright 1998中崗科技Web站所登載的文章係屬本公司,版權所有,勿任意轉載,違者必究