遺伝的アルゴリズムの交叉方法について

遺伝的アルゴリズムの交叉方法について。
一点交叉、複数点交叉、一様交叉について調べているのですが、
一点交叉の「効率が悪い」というもの以外
いまいち特徴(使うにあたってのメリット)がわかりません。
どうか知恵を借してください。宜しくお願いします。

行動規範の内容に同意します

回答1件

ベストアンサー

私は授業で習っただけで専門家ではありません．
授業で習ったことを踏まえて回答させていただきます．
（いくつか認識が間違っているかも知れません）

遺伝的アルゴリズムというのは，全パターンを試すことなく優れた結果を探すことに主眼が置かれているので，
一般的に交叉の方法について数学的な優劣はありません．
しかし経験的に二点交叉と一様交叉が効率が良いということが分かっているだけです．
前者は良い特徴を継承しやすく，後者は極所解に陥ることを防ぎやすいからです．

数学的には，一点交叉×２と二点交叉×１の処理は同じです．
メモリコピーを削減する賢いプログラムなら，両者ともにメモリコピー量の期待値は１／４になります．
（※下記プログラムで検証，小さい領域を優先的にコピーする場合のコピー量の期待値を算出）
交叉すればするほど良い，というわけではありませんが，
同じメモリコピー量で一点交叉の二回分を一回でやるわけですから，やはり効率は良いです．
２倍の速度で交叉が進むということは，収束する速度も速いということになります．
もちろん遺伝子の表現方法によっては，一点交叉の方が良い結果を出す場合もあります．
しかしそのような場合はあまりないため，二点交叉が好まれているということです．
この辺りは，「やってみたらそうなったから」という以外はあまりないと思います．

python
1import random
2nt = 100000
3total1 = 0
4for i in range(nt):
5    tmp = random.random()
6    total1 += tmp if tmp < 0.5 else 1 - tmp
7print total1 / nt
8total2 = 0
9for i in range(nt):
10    tmp1 = random.random()
11    tmp2 = random.random()
12    if tmp1 > tmp2:
13        tmp = tmp1
14        tmp1 = tmp2
15        tmp2 = tmp
16    total2 += (tmp2 - tmp1) if (tmp2 - tmp1) < 0.5 else 1 - (tmp2 - tmp1)
17print total2 / nt