遺伝的アルゴリズム (GA) で 巡回セールスマン問題 (TSP) を解くアニメーション

動作イメージ

GA-TSP.mp4

Untitled

ソースコード (Processing)

int n = 25; // 都市の数
int m = 6; // 遺伝子の数
City x[] = new City[n]; // 都市
IntList[] d = new IntList[m]; // 遺伝子(DNA)
IntList[] p = new IntList[m]; // 表現型(Phenotype)
FloatList dis = new FloatList(); // 総距離
int w; // width
int T = 1000000;
boolean useGA = true; // GAを使うかどうか (falseの場合は乱数を使う)

void setup() {
  size(1000, 300); frameRate(30);
  w = width/m;
  for (int i=0;i<n;i++) {
    // 乱数で都市の座標を決める
    x[i] = new City(i, random(10, w-10), random(70, height-10));
  }
  for (int i=0;i<m;i++) {
    d[i] = getInitDNA(); // 初期値(乱数)
  }
}
void draw(){
  dis.clear();
  background(255);
  stroke(122);
  text("# city = "+n+" step = "+frameCount,10,20);
  text("total distance:",10,35);
  for (int i=0;i<m;i++) {
    pushMatrix();
    // 順序表現に変換
    p[i] = encodePath(d[i]);
    // 総距離を評価
    dis.append(eval(d[i]));
    translate(w*i,0);
    text("["+i + "] "+dis.get(i),10,50);
    drawPath(d[i]);
    popMatrix();
  }
  // 各遺伝子を総距離に基いて評価
  IntList r = rankList(dis);
  // ２番目に良いものを表示（ピンク）
  pushMatrix(); translate(w*r.get(1),0);
  stroke(255, 150, 200, 200); drawPath(d[r.get(1)]);
  popMatrix();
  // １番目に良いものを表示（赤）
  pushMatrix(); translate(w*r.get(0),0);
  stroke(255, 0, 0, 200); drawPath(d[r.get(0)]);
  popMatrix();
  // 最も悪いものを表示（青）
  pushMatrix(); translate(w*r.get(r.size()-1),0);
  stroke(0, 0, 255); drawPath(d[r.get(r.size()-1)]);
  popMatrix();
  if(useGA == true){ // GAを使う場合
    // 最も悪いものを、新しく生まれたものに入れ替える
    IntList d_new = decodePath(crossPath(p[r.get(0)], p[r.get(1)]));
    d_new = mutatePath(d_new);
    d[r.get(r.size()-1)] = d_new;
  }else{ // GAを使わない場合、乱数で新しい遺伝子を得る
    d[r.get(r.size()-1)] = getInitDNA();
  }
  if(frameCount > T) noLoop();
}

// 交叉：２つの遺伝子をランダムな位置で交叉させる
IntList crossPath(IntList x, IntList y){
  IntList z = new IntList();
  int pos = (int)random(1,x.size()-1); // 交叉場所
  for(int i=0;i<x.size();i++){
    if(i < pos){
      z.append(x.get(i));
    }else{
      z.append(y.get(i));
    }
  }
  return z;
}

// 変異：遺伝子の中でランダムに２点を交換する
IntList mutatePath(IntList x){
  int pos1 = (int)random(0, x.size()-1);
  int pos2 = (int)random(0, x.size()-1);
  int tmp = x.get(pos1);
  x.set(pos1, x.get(pos2));
  x.set(pos2, tmp);
  return x;
}

// 評価：総距離に応じてランキングを付ける
IntList rankList(FloatList x){
  FloatList y = x.copy(); y.sort();
  IntList z = new IntList();
  for(int i=0;i<y.size();i++){
    for(int j=0;j<x.size();j++){
      if(y.get(i) == x.get(j)){
        z.append(j); break;
      }
    }
  }
  return z;
}

// パスの総距離を計算する
float eval(IntList d) {
  float dist_all = 0;
  for (int i=1;i<n;i++) {
    dist_all += dist(x[d.get(i-1)].x, x[d.get(i-1)].y, x[d.get(i)].x, x[d.get(i)].y);
  }
  return dist_all;
}

// パスを描く
void drawPath(IntList d) {
  strokeWeight(10);
  for (int i=0;i<n;i++) {
    x[i].display();
  }
  strokeWeight(2);
  for (int i=1;i<n;i++) {
    line(x[d.get(i-1)].x, x[d.get(i-1)].y, x[d.get(i)].x, x[d.get(i)].y);
  }
}

// パスを順序表現に符号化する
IntList encodePath(IntList x) {
  IntList u = new IntList();
  IntList y = new IntList();
  for (int i=0;i<x.size();i++) u.append(i);
  for (int i=0;i<x.size();i++) {
    for (int j=0;j<u.size();j++) {
      if(x.get(i) == u.get(j)){
        y.append(j); u.remove(j); break;
      }
    }
  }
  return y;
}

// パスを順序表現から戻す
IntList decodePath(IntList x) {
  IntList u = new IntList();
  IntList y = new IntList();
  for (int i=0;i<x.size();i++) u.append(i);
  for (int i=0;i<x.size();i++) {
    y.append(u.get(x.get(i)));
    u.remove(x.get(i));
  }
  return y;
}

// 初期DNAを得る
IntList getInitDNA() {
  IntList x = new IntList();
  for (int i=0; i<n; i++) x.append(i);
  for (int i=n-1; i>0; i--) {
    int rd = (int)random(0, i);
    // 乱数をインデックスとして利用し、その配列の中の値と配列末尾の値を交換
    // ※末尾（乱数のMAX値）はループごとにデクリメント
    // 参考: <http://okwave.jp/qa/q7687312.html>
    int tmp = x.get(rd);
    x.set(rd, x.get(i));
    x.set(i, tmp);
  }
  return x;
}

// 都市を表すオブジェクト
class City {
  int order; // 番号
  float x;float y; // 座標
  City(int order_, float x_, float y_) {
    order = order_; x = x_; y = y_;
  }
  void display() {
    point(x, y); fill(0); text(order, x, y);
  }
}

参考資料