Re: [問題] 關於基因演算法

[H45 (!H45)]

※ 引述《freelance978 (阿什坎迪)》之銘言：
: 剛剛閱讀有關Hybrid K-medoid Algorithm的文章
: 他有提到三個步驟  1選擇 2交配 3突變
: 染色體編碼方式是整數編碼(Integer Representation)
: 每筆資料會被依序編號 1,2,…,n，其中 n 為資料的總筆數。
: 將每一條染色體固定長度為 K，K為分群數，
: 且每一條染色體裡的每一個基因(gene)放入的可以是任何一筆資料的編號 1,2,…,n
: 而這染色體的 K 個基因裡的數字，分別地代表某一群資料集的群集中心資料點之編號。
: ex:若資料集中有 10 筆資料（給予編號 1..10），欲分成 3 群(K=3)，
: 其隨機產生的染色體表示假設為： 2   5   8  ，代表的意思是資料集分成三群後
: 各群中心
: 我要問的是他提到的交配跟突變方法:
: 交配: 混合子集重組交配法(Mix Subset Recombination Crossover)
: 突變: Flip Mutation
: 有人聽過這兩個方法嗎
: 查過他的ref 還是沒寫得很清楚
: 謝謝

上面有寫啊。

以下節錄自 "A Hybrid Algorithm for K-medoid Clustering of Large Data Sets"
Wrote by W. Sheng and X. Liu:

In order to avoid producing illegal individuals or producing offspring 
identical to the parents, we apply the mix subset recombination crossover 
[5], which has a built-in mutation with probability of Pm,mix. Given two 
parent individuals X1 and X2 with k features, mix subset recombination 
crossover works as follows:

(1) Mix X1 and X2 to obtian Xmix by appending one parent individual to 
another and then the features of resulting Xmix are randomly scrabled.
(2) Perform flip mutation on each feature of Xmix with a predetermined 
probability Pm,mix and then randomly scrable the features of Xmix again.
(3) Build the offspring X3 by coping features from Xmix starting at the 
leftmost feature and going featurewise to the right, subject to the condition 
that features already in X3 are skipped.
(4) Build the offspring X4 by coping features from Xmix starting at the 
rightmost feature and going featurewise to the left. subject to the condition 
that features already in X4 are skipped.

The crossover is applied on each paired parent with probability of Pc.
After crossover, the probability Pm of flip mutation will be applied to the 
offspring. Flip mutation replaces the chosen feature by another randomly 
generated feature, subject to the restriction that the new feature is not 
presented in the current genotype of the individual.

哪邊看不懂？需要講解嗎？

--
※ 發信站: 批踢踢實業坊(ptt.cc) 
◆ From: 140.116.247.22
推 costbook:我不懂為什麼把資料搬來搬去就會有近似解...
推 hilorrk:這是有數學證明的　GA其實算是一種統計(機率)
→ hilorrk:不得不讚嘆大自然的神奇..沒有數學也能衍生出基因這種東西
→ H45:這篇文章用的方法暫不評論 提到GA 比起均勻分佈的隨機搜尋法
→ H45:GA是一種更有效率的搜尋策略
推 costbook:這麼說PSO的原理也是一樣囉？
推 micklin:是
推 freelance978:scrabled是什麼意思
→ H45:以上次我們私下討論的結果 似乎是將基因重新排列的意思
推 freelance978:恩我知道 感謝H45解惑  我只是想確認一下才提問
→ pinglin02:Genetic Algorithm 還有扯到crossover 如果拿掉它的話
→ pinglin02:另一個比較單純的heuristic algorithm叫hill climb
→ pinglin02:是單純的random+evaluation 去找到local optimum
推 pinglin02:並不是所有的問題GA都比hill climbing有效率的