成本最小化
The picture form http://transwebtutors.com/economics/Profit_Function.aspx
成本最小化在現今的台灣(目前西元2014年),我覺得在人力資源上不用省,但在物力上就需要全面的自動化來完成精簡成本的目標.
基因演算法(genetic Algorithm) 筆記
生物的進化(Evolution)過程主要是通過染色體之間的交叉和變異來完成的。基於對自然界中生物遺傳與進化機理的模仿,針對不同的問題,很多學者設計了許多不同的編碼方法來表示問題的可行解,開發出了許多種不同的遺傳算子來模仿不同環境下的生物遺傳特性。這樣,由不同的編碼(Coding)方法和不同的遺傳算子就構成了各種不同的遺傳演算法。
遺傳演算法是模仿自然界生物進化機制發展起來的隨機全局搜索和優化方法,它借鑒了 達爾文的進化論和孟德爾的遺傳學說。其本質是一種高效、並行、全局搜索的方法,它能在搜索過程中自動獲取和積累有關搜索空間的知識,並自適應的控制搜索過程以求得最優解。遺傳演算法操作使用適者生存的原則,在潛在的解決方案種群中逐次產生一個近似最優解的方案,在遺傳演算法的每一代中,根據個體在問題域中的適應度值和從自然遺傳學中借鑒來的再造方法進行個體選擇,產生一個新的近似解。這個過程導致種群中個體的進化,得到的新個體比原來個體更能適應環境,就像自然界中的改造一樣。(From:wiki)
「物競天擇、適者生存」的進化論,在電腦科學的領域上,有個領域在做求取最佳解的問題,最佳解就是對於某個函數而言,什麼參數會讓這個函數得到最大或是最小的結果。
GA求解問題的7大步驟:
- 設計編碼方式(實數型基因法則不用)
- 決定群體規模
- 設計適應函數,決定個體適應度的評估標準
- 決定挑選與複製方法
- 定義交配與交配機率
- 定義突變與突變機率
- 決定終止條件
Generation:世代
Population:族群
Individual:個體
Crossover:交配
Reproduction:複製
Mutation:突變
Fitness:適應函數設計
適應函數:
用來評估個體的適應度(fitness)。
挑選機制:
挑選機制其實就是探討如何從群體(樣本空間) 挑選出個體(樣本) 的取樣
方式,被挑選的個體就是親代,可經由遺傳運算來產生子代。基本的取樣機制有
三種:(1) 隨機取樣(stochastic sampling), (2) 明確取樣(deterministic sampling),
與(3) 混合取樣(mixed sampling) (Gen and Cheng, 1997;Goldberg, 1989) 。最著
名的隨機取樣就是Holland 提出的輪盤式(roulette wheel selection) 選擇。混合取
樣是同時含有隨機與明確兩種特性,最典型的例子是Goldberg 提出的競賽挑選
(tournament selection)。此法是於群體中隨機挑選一些個體,由這些個體舉行一場
比賽來相互競爭,最優者就是雙親(Goldberg, 1989)。這個過程會重複進行,舉
行不同的賽程直到選出足夠的親代為止。若每場賽事只有2 個染色體參加,則
稱為二元競賽。
交配機率Pc:
交配是主要的遺傳運算子,將兩個染色體經過合併的程序來產生子代,讓子
代各含有雙親的部分特性。交配的目的是希望子代能夠組合出含有更高適應度的
染色體,然而有可能子代只遺傳雙親的缺點,所以交配不保證一定可以製造出更
好的子代,不過有了天擇的機制,較差的子代會逐漸被淘汰,而優良的子代可以
繼續繁衍下去。於上篇中我們已介紹了四種常用的交配方式:(1)單點、(2)兩點、
(2)多點、以及(4)均一交配(Syswerda, 1989)。許多研究顯示(Beasley, Bull, and
Martin, 1993) 兩點交配較優於單點交配,只有當群體接近收斂時,兩點交配的效
果才會遜色於單點交配(Spears and De Jong, 1993)。
突變機率Pm:
突變會導致染色體突然間做隨意的變化,常見的變化是改變染色體上的一個
基因。突變的作用會引導GA 進入未曾尋找過的基因架構,將新基因導入群體
中。但是突變次數過多將會導致GA 變成隨機演算法,會任意破壞原來的結構,
造成子代與親代喪失若干相似的特徵;而過少的突變則會造成有用的基因沒被發
覺,可能會陷入區域的最佳解。因此GA 將突變視為是次要的遺傳運算子,以
較低的機率來反轉子代的某一個位元(0 變1 或1 變0),典型的機率是pm =
0.001,此即每隔1000 個位元(或變數)才反轉一個位元(變數)。
參考資料
台灣wiki遺傳演算法
如果利用基因演算法來求取成本最小化問題,那運作方式?
有一種實數型基因演算法,差在不用編碼,直接作....
<後面補上>
留言列表