GAによる巡回セールスマン問題の最適化

GA(遺伝的アルゴリズム)は最適化手法の一つで、選択、交叉、突然変異を繰り返すことによる最適化を行うアルゴリズムです。

リポジトリはこちら
https://github.com/hinahina-chips/GA-TSP/tree/main

まずは総距離の短い順にソートしておきます。

以下の操作に従って実装します。

• 選択：エリート選択。上位半分を選択。

void select_gene1(){
	long i, j;
    for(i = 0; i < NUM_GENE; i++){
        for(j = 0; j < NUM_CITY; j++) Gene[i][j] = Gene[i % (NUM_GENE / 2)][j]; //上位半分をコピー
    }
}

• 交叉：適当に交叉させると同じ都市(City)が同じ経路(Gene)に含まれるということが起こるため、マスク交叉を行う。

void kousa_gene_pair(long p1[], long p2[]){
    long mask[NUM_CITY];
	long num_mask;
    long i, j, n = 0;
	num_mask = 0;
	mask[0] = 300;//nになり得ない適当な値を初期値として格納
    for(i = 0;; i++){
        n = num_where(p1, p2[n]); //P2[n]の都市がp1のどの要素番号か返す関数num_where
        if(mask[0] == n) break; //既出の要素番号が出たら終了
        mask[num_mask] = n; //mask配列に格納
        num_mask++;//mask配列の要素をインクリメント
    }
    ex_kousa(p1, p2, mask, num_mask);//交叉用の交換関数
}

• 突然変異：一定確率でランダムに入れ替える

void mutate_gene_each(long i, long j){
	long n, m, k;
	n = Gene[i][j];
	for(;;){
		m = rand() % NUM_CITY;
		if (m != n) break;
	}

	Gene[i][j] = m;
	
	for(k = 0; k < NUM_CITY; k++){
		if(Gene[i][k] == m) break;
	}
	Gene[i][k] = n;
}

とはいってもGAのみでは10都市くらいの小規模な巡回セールスマン問題しか解けませんでした。そこで以下の処理を追加しました。

• 前世代の最適経路と総距離を保存し、現世代の最適経路と比較して良い方を残す

• ローカルサーチを実装して交差している経路を無くす(元論文があるんですけど前すぎて見つからんかった...)

void local_gene(){
    long i,j;
    long p[NUM_CITY];
    long p_bef[NUM_CITY];

    for(i = 0; i < NUM_GENE; i++){
        for(j = 0; j < NUM_CITY; j++){
            p[j] = Gene[i][j];	//遺伝子情報を1次元配列pに一時的に格納
            p_bef[j] = Gene[i][j];
        }

        local_each(p);

        for(j = 0; j < NUM_CITY; j++){
        	Gene[i][j] = p[j];//一次元配列pをGeneに戻す
        }
    if (F_local == 1){
   	    fprintf(Fp_deb, "before local_sort in local_each\n"); 
   	    for (j = 0; j < NUM_CITY; j++) fprintf(Fp_deb, "%ld", p_bef[j]);
   	    fprintf(Fp_deb, "\n");
   	    
		fprintf(Fp_deb, "after local_sort in local_each\n"); 
		output_gene(i);
		
	}
	
	
	}
	
}

void local_each(long p[]){
    long i, j, g, k;
    double vii, v_ij, vij, vjj;
	

    
	for(i = 0; i < NUM_CITY-2; i++){
        for(j = i+2; j < NUM_CITY; j++){
            
            vij = kyori(p[i], p[j]);
            v_ij =kyori(p[i + 1], p[(j + 1) % NUM_CITY]);
            vii = kyori(p[i], p[i + 1]);
            vjj = kyori(p[j], p[(j + 1) % NUM_CITY]);
            
            if((vij + v_ij) < (vii + vjj)) {
            	F_local = 1;
				local_sort( i+1, j, p);//localサーチの条件	
		    }
				
		}
	}		
}

• 後半は突然変異の処理確率を減らす

結果

ローカルサーチを入れたおかげでどちらも交差点はなくなっていますね。最適化も進んでいるのでGAは有効であるということが分かります。面白い...