遺伝的アルゴリズムの交叉方法

[toru]

TSPを解く遺伝的アルゴリズムの交叉についてアルゴリズムがプログラムに書き直せないので、ご教授ください。
単純に5都市の問題として考えています。

定義1：親1の巡回路を(1,2,3,4,5)、親2の巡回路を(2,1,3,5,4)とします。tourという2次元配列には巡回路が入っています。
例えばtour[parent1][]=(1,2,3,4,5)、tour[parent2][]=(2,1,3,5,4)といった具合です。
定義2：子は1次元配列で構成されており、出発都市のみランダムで決定されております。
また、アルゴリズムに従い、どちらの親の都市を受け継ぐか決定しています。
例えば、出発都市が3と決定しているとし、どちらの親の都市を受け継ぐか決まっているとすると、
child[]=(3,親1,親1,親2,親1)という風になっており、この親の判定は1か2でマークされています。
つまり、プログラム上のchildは、child[]=(3,1,1,2,1)というような配列になっています。

まとめると、親1の巡回路を(1,2,3,4,5)、親2の巡回路を(2,1,3,5,4)、子の出発都市を3とする。
この時(1,1,2,1)の順番で親の都市が選択された場合、子の巡回路は、(3,1,2,5,4)となります。
この親1、親2の振り分けの部分がプログラムではうまく書くことができません。
もうすでにchildに入れられた都市が重複して入れられてしまうのです。

雑なアルゴリズムですが、よろしくお願いします。
また、質問があれば何なりとお答えしますのでよろしくお願いします。
iはループの判定に、city_numは今回5都市ですので5です。

コード:

/*child[i]が1だった場合、親1を入れる*/
for(i = 1; i < city_num; i++){
   if(child[i] == 1){
      //子の持つ都市と重複しないように、親1の都市を入れる。
   }
}
/*child[i]が2だった場合、親2を入れる*/
for(i = 1; i < city_num; i++){
   if(child[i] == 2){
      //子の持つ都市と重複しないように、親2の都市を入れる
   }
}

[softya（ソフト屋)]

申し訳ないですがトピックの無闇な削除は禁止させていただいております。
回答が付いていないのは、その方面に詳しい回答者が少ないのが原因ですのでお待ちいただくしかありません。
フォーラムルールを守ったご利用をお願いします。

あと問題の有るコードでも投稿していただいたほうが良いと思います。
アルゴリズムに詳しくなくてもバグがつかめる場合も多々あるからです。
今のままだと課題の丸投げとなってしまいますから。

[usao]

私が問題自体を誤解しているのかもしれませんが，

都市間で経路が繋がってる箇所と繋がってない箇所があるんじゃないかと思うのですが，
そんなシンプルな方法で新しい経路を作ってしまっても良いものなのでしょうか？
（それともそうやって作った経路の中に，繋がってないルートがあった場合は，その経路を単に棄却するのかな？？）


>まとめると、親1の巡回路を(1,2,3,4,5)、親2の巡回路を(2,1,3,5,4)、子の出発都市を3とする。
>この時(1,1,2,1)の順番で親の都市が選択された場合、子の巡回路は、(3,1,2,5,4)となります。
どういうルールでその子の経路が作られたのか
というあたりをもっと順を追って(各ステップを）明確に説明できませんか？
それができれば，TSPがどうのという話とは関係なく，
「その処理部分だけ」を（誰かが）回答することが可能な気がします．

あと，
>childに入れられた都市が重複して入れられてしまうのです。
ということが起こるコードを提示しましょう．

[toru]

お二方、ご指摘ありがとうございます。
削除に関してはルールの理解不足でした。大変申し訳ございません。以後、気を付けます。

自分が考えたプログラムと同時に、交叉の方法の全文を載せてみます。
変数等、分からないものがあればまた質問してください。お願いします。

3．交叉
選択された両親から子を一つ生成する。まず、ランダムに一都市を選択し子供の出発都市(s)とする。
親1と親2のsの次に訪問する都市をそれぞれc1,c2とする。この時、子において、sの次に訪問する都市候補はc1とc2である。
都市c1,c2がsの次に訪問される確率はsからの距離が近い都市の訪問される確率が高くなるように、式(2)で計算される。
ただし、d(x,y)は都市x,y間の距離を表す。

c1を訪問する確率＝d(s,c2)/(d(s,c1)+d(s,c2))
c2を訪問する確率＝d(s,c1)/(d(s,c1)+d(s,c2))　　　・・・式(2)

次に訪問する都市候補は、sを起点とする親の巡回路で最初に訪問する、子の巡回路での未訪問都市とし、式(2)と同様にして都市訪問を決定していく。
以下、同じ操作を繰り返すことにより子の巡回路を得る。
ここで、親1の巡回路を(1,2,3,4,5)、親2の巡回路を(1,5,2,3,4)、子の出発都市を1とする。
この時、(2,1,1,2)の順番で親の都市が選択された場合、子の巡回路は(1,5,2,3,4)となる。

以上が問題になります。
以下は自分が書いた交叉の関数のプログラムです。コメントアウトの部分で重複が起こり、うまく結果が出ていないようです。
質問等があれば受け付けています。よろしくお願いいたします。

コード:

/* 交叉 */
void crossover(){
	int s,i,j,k,c1,c2;
	double d,random;
	srand((unsigned)time(NULL));
	
	s = rand() % city_num;

	
	child[0] = s;	//子の出発都市確定
	
	for(i = 1;i < city_num; i++){
		c1 = tour[parent1][s+1 % city_num];		//子の未訪問都市候補（親1）
		c2 = tour[parent2][s+1 % city_num];		//子の未訪問都市候補（親2）
		
		
		/*C1が訪問される確率を求める*/
		d = (double)distance(s,c2) / (double)(distance(s,c1)+distance(s,c2));
		d = d * 100;
		random = (double)(rand() % 100);
		
		/*確率に基づき子が親1を継ぐか親2を継ぐか決める(マークする)*/
		if(0 <= random && random <= d){
			child[i] = 1;
			s = c1;
		}
		else{
			child[i] = 2;
			s = c2;
		}
	}
	
		/*for(i = 1;i < city_num;i++){
		switch(child[i % city_num]){
			case 1:
				if(child[i % city_num] == tour[parent1][i % city_num] || child[i % city_num] == tour[parent2][i % city_num]){
					j = 0;
					do{
						j++;
						child[i % city_num] = tour[parent1][i+j];
					}while(child[i % city_num] == tour[parent1][i+j]);
				}
				else
					child[i % city_num] = tour[parent1][i % city_num];
				
				break;
			
			case 0:
				if(child[i % city_num] == tour[parent1][i % city_num] || child[i % city_num] == tour[parent2][i % city_num]){
					j = 0;
					do{
						j++;
						child[i % city_num] = tour[parent2][i+j % city_num];
					}while(child[i % city_num] == tour[parent2][i+j % city_num]);
				}
				else
					child[i % city_num] = tour[parent2][i % city_num];
				
				break;
		}
	}*/
	
}

[たいちう]

toruさんの遺伝子は参考ページの「パス表現」のようですが、「順序表現」に変更するとうまくいくでしょう。
順序型GAの遺伝子表現と操作 "セールスマン巡回問題を例に"

オフトピック

usaoさん

> 都市間で経路が繋がってる箇所と繋がってない箇所があるんじゃないかと思うのですが，
> そんなシンプルな方法で新しい経路を作ってしまっても良いものなのでしょうか？
> （それともそうやって作った経路の中に，繋がってないルートがあった場合は，その経路を単に棄却するのかな？？）

問題の前提によりますね。
都市を飛行機で移動する場合、車で移動する場合、自家用ヘリで移動する場合など。
都市が座標を持っていて、直線距離の和が最短になるものを選ぶとか、道のりの最短とか。

道のりが必要な場合、2次元のデータが必要なので、繋がっていない都市の場合には、
道のり(コスト)を無限大として扱ったりもできるでしょう。

[toru]

[quote="たいちう"]toruさんの遺伝子は参考ページの「パス表現」のようですが、「順序表現」に変更するとうまくいくでしょう。
順序型GAの遺伝子表現と操作 "セールスマン巡回問題を例に"

回答ありがとうございます。
ただ、私の参考にしている論文を見ると、このアルゴリズムはパス表現を用いると明記されております。それでも、順序表現の方がよろしいのでしょうか？

[usao]

>ここで、親1の巡回路を(1,2,3,4,5)、親2の巡回路を(1,5,2,3,4)、子の出発都市を1とする。
>この時、(2,1,1,2)の順番で親の都市が選択された場合、子の巡回路は(1,5,2,3,4)となる。

各ステップを書き下すと…


子の出発都市を1　：　子の経路データ ( 1, *, *, *, * )
→c1 は，親１のデータ内で1の次にあるやつ　→　c1=2
　→c2 は，親２のデータ内で1の次にあるやつ　→　c2=5
　↓
c2を選択　：　子の経路データ ( 1, 5, *, *, * )
　→親１のデータ内で5の次は1だけど，1は既に子の経路に含まれているからその次の2 → c1 = 2
　→c2 = 2
　↓
c1を選択　：　子の経路データ ( 1, 5, 2, *, * )
　→c1 = 3
　→c2 = 3
　↓
c1 を選択　：　子の経路データ ( 1, 5, 2, 3, * )
　→c1 = 4
　→c2 = 4
　↓
c2を選択　：　子の経路データ ( 1, 5, 2, 3, 4 )


…ということでしょうか．
であれば，このルールをそのままコーディングすればよいように思うのですが，

コード:

        c1 = tour[parent1][s+1 % city_num];     //子の未訪問都市候補（親1）
        c2 = tour[parent2][s+1 % city_num];     //子の未訪問都市候補（親2）

これでは，そのルールを考えていないように見えます．
（sというのは都市の名前であって，配列添え字の演算に使っているのもおかしいような？）

「c1,c2の決め方」をより細かく書き下し，それをコード化するとよいのではないでしょうか．
例えば，c1の決め方であれば，子の現在位置がsであるとき，

(1) tour[parent1]の中から値がsな要素を探索する．
　ここでは仮に，c1=探索結果　としておく．
(2) c1 を１個後ろの要素（c1が配列末尾だったら先頭要素）にずらす．
(3) このc1が　子の経路データchild[] に既に含まれているかどうか判定
(3.1)含まれていないならc1はこの値で決定
(3.2)含まれているなら(2)に戻る

といった感じに．

[たいちう]

> ただ、私の参考にしている論文を見ると、このアルゴリズムはパス表現を用いると明記されております。
> それでも、順序表現の方がよろしいのでしょうか？

お手元の論文もtoruさんの受けている指示も、私には知る由がない訳でして。。。
判断を求められても困ります。


一般論としてはパス表現と交叉は相性が悪く、無理やり実装するならばかなりひねくれた方法になると思います。
エレガントな方法を私が知らないだけかもしれませんが。お手元の論文では交叉の実装方法について書かれていますか？

私見ですが、TSPでのパス表現は方便の様なもので、遺伝子型と表現型という概念に触れずに、
GAを素人向けに表面的に説明するために使える程度です。
パス表現のコーディングで苦労させてから、実はこんなにいいアイデアがあるんだよ、とか。


ちなみに、TSPのパス表現で、相性の良い遺伝子操作に「反転」があります。
複数の連続した遺伝子座の反転です。
これもtoruさんの受けている指示がわからないので、役に立つかは判りませんが。