algorithm

욕심 많은 방법

의견에서 제안 된 한 가지 접근 방식은 가장 가까운 대상으로 먼저 이동하는 것입니다.

나는이 욕심 방법을 통해 계산 된 비용이 포함 된 데모 버전 올려 한 여기를 .

코드는 다음과 같습니다.

function greedyMethod(start_x,start_y) {
  var still_to_visit = (1<<pts.length)-1;
  var pt=[start_x,start_y];
  var s=0;
  while (still_to_visit) {
    var besti=-1;
    var bestc=0;
    for(i=0;i<pts.length;i++) {
      var bit = 1<<i;
      if (still_to_visit&bit) {
        c = fastest_route(pt,getPt(i,s));
        if (besti<0 || c<bestc) {
          besti = i;
          bestc = c;
        }
      }
    }
    s+=c;
    still_to_visit -= 1<<besti;
    pt=getPt(besti,s);
  }
  return s;
}

10 개의 표적의 경우 최적 거리의 약 두 배이지만 때로는 훨씬 더 길고 (예 : * 4) 때로는 최적에 도달하기도합니다.

이 접근 방식은 매우 효율적이므로 답변을 개선 할 수있는 몇 가지주기를 가질 수 있습니다.

다음으로 개미 식민지 방법을 사용하여 솔루션 공간을 효과적으로 탐색 할 수 있는지 확인하려고합니다.

개미 식민지 방법

개미 식민지 방법은 이 문제에 대한 놀라운 잘 작동하는 것 같다. 이 답변의 링크는 이제 탐욕과 개미 식민지 방법을 모두 사용할 때 결과를 비교합니다.

아이디어는 개미가 현재의 페로몬 수준에 따라 확률 적으로 경로를 선택한다는 것입니다. 10 번의 시도 후에 우리는 그들이 발견 한 가장 짧은 흔적을 따라 추가로 페로몬을 입금합니다.

function antMethod(start_x,start_y) {
  // First establish a baseline based on greedy
  var L = greedyMethod(start_x,start_y);
  var n = pts.length;
  var m = 10; // number of ants
  var numrepeats = 100;
  var alpha = 0.1;
  var q = 0.9;
  var t0 = 1/(n*L);

  pheromone=new Array(n+1); // entry n used for starting position
  for(i=0;i<=n;i++) {
    pheromone[i] = new Array(n);
    for(j=0;j<n;j++)
      pheromone[i][j] = t0;
  }

  h = new Array(n);
  overallBest=10000000;
  for(repeat=0;repeat<numrepeats;repeat++) {
    for(ant=0;ant<m;ant++) {
      route = new Array(n);
      var still_to_visit = (1<<n)-1;
      var pt=[start_x,start_y];
      var s=0;
      var last=n;
      var step=0;
      while (still_to_visit) {
        var besti=-1;
        var bestc=0;
        var totalh=0;
        for(i=0;i<pts.length;i++) {
          var bit = 1<<i;
          if (still_to_visit&bit) {
            c = pheromone[last][i]/(1+fastest_route(pt,getPt(i,s)));
            h[i] = c;
            totalh += h[i];
            if (besti<0 || c>bestc) {
              besti = i;
              bestc = c;
            }
          }
        }
        if (Math.random()>0.9) {
          thresh = totalh*Math.random();
          for(i=0;i<pts.length;i++) {
            var bit = 1<<i;
            if (still_to_visit&bit) {
              thresh -= h[i];
              if (thresh<0) {
                besti=i;
                break;
              }
            }
          }
        }
        s += fastest_route(pt,getPt(besti,s));
        still_to_visit -= 1<<besti;
        pt=getPt(besti,s);
        route[step]=besti;
        step++;
        pheromone[last][besti] = (1-alpha) * pheromone[last][besti] + alpha*t0;
        last = besti;
      }
      if (ant==0 || s<bestantscore) {
        bestroute=route;
        bestantscore = s;
      }
    }
    last = n;
    var d = 1/(1+bestantscore);
    for(i=0;i<n;i++) {
      var besti = bestroute[i];
      pheromone[last][besti] = (1-alpha) * pheromone[last][besti] + alpha*d;
      last = besti;
    }
    overallBest = Math.min(overallBest,bestantscore);
  }
  return overallBest;
}

결과

10 마리의 개미를 100 번 반복하는이 개미 군집 방법은 여전히 ​​매우 빠르며 (완전한 검색의 경우 3700ms에 비해 16 개의 표적에 대해 37ms) 매우 정확 해 보입니다.

아래 표는 16 개 대상을 사용한 10 회 시도의 결과를 보여줍니다.

   Greedy   Ant     Optimal
   46       29      29
   91       38      37
  103       30      30
   86       29      29
   75       26      22
  182       38      36
  120       31      28
  106       38      30
   93       30      30
  129       39      38

개미 방법은 탐욕스러운 것보다 훨씬 낫고 종종 최적에 매우 가깝습니다.