🥑 ☹️ 🤳🏽 例による最適化。 Antアルゴリズム（ACS）対アニーリング法。パート2 👨‍🎨 👨‍👩‍👦 👨🏽‍🔧

一連の記事「例による最適化」を続けます。この記事では、 ~~ボロボロの~~対称巡回セールスマン問題に関する2つのヒューリスティックアルゴリズムを比較します。今日は、このトピックをさらに深く掘り下げ、antアルゴリズムの特定の変更を分析します。

両方のアルゴリズムには多くの修正と多くの潜在的な修正があるため、この記事ではどちらの方法が一般的に優れているかを証明しません。ここで、勝者は特定の修正と特定のパラメーターでのみ決定されます。この記事の目的は、離散的最適化の分野で読者の視野を広げることであり、両方のアルゴリズムの動作を改善するための提案です。

Antアルゴリズムの修正版は、1997年にMarco DorigoとLuca Gambardellaによって提案されたACS（Ant Colony System）によって選択されました。 AS（Ant System）との主な違いは次のとおりです。

1）最も魅力的な都市と通常のASのように選択肢とのバランスが設定されます

arg max {[τ（r、u）] ^α* [ω（r、u）] ^β} if q <= q0（式1）

u ϵ Jk“ r”

それ以外の場合は、ASに沿ってトランジションを選択します

ここで、[τ（r、u）]はエッジ上のフェロモンレベル（r、u）、[ω（r、u）]はエッジ上の距離に反比例する重み（r、u）、βは調整可能なパラメーター、アルゴリズムは、より短い距離の都市を選択する傾向があります、α-1に等しい、q-ランダムに選択された数値、q0-1つの頂点から別の頂点への遷移が式1に従って進むことを選択する確率、u-まだ訪れていない都市

2）フェロモンのグローバル更新に加えて、ローカル更新も発生します。フェロモンのレベルは、アリが反復を通過するたびに変化します（ここでは、アリの自然の生息地により近くなります）。

τ（r、s）=（1-p）*τ（r、s）+ p *τ0（式2）

ここで、pはローカル更新レベル、τ0=初期フェロモンの値は次のように計算されます：τ0=（n * Lnn）^-1、Lnnは別の最適化方法で取得できる近似最適値です。

3）フェロモンのグローバル更新中に、アルゴリズムの開始以降の最適なエッジ（グローバルベスト）、または反復時の最適なエッジ（ローカルベスト）のいずれかのみがエッジに追加されます。世界最高のrib骨に適用しました。

τ（r、s）=（1-e）*τ（r、s）+ e *（Lbest ^ -1）（式3）

ここで、eはグローバル更新レベル、Lbestはk番目の反復またはグローバルベストでの最適なルート長（最短）です。

これらの変更により、アルゴリズムのパフォーマンスが大幅に向上しました。アニーリング方法は、速度の向上を除いて、前の記事と同じままです。読者のzartdinovに、速度を上げるためのシンプルで非常に効果的な提案をありがとう。

次に、Oliver30、Eli51、Eli101などの既知の座標上のタスクを比較します。最適なソリューションが見つかりました。また、2つのアルゴリズムの都市数に対する時間依存性の近似式を導き出し、最後に、これらすべての要因を考慮して、今日の勝者を決定しようとします。

Oliver30チャレンジから始めましょう、最高のソリューション-423.7406

ACSパラメーター：

反復数（世代）-2500 *
世代内のアリの数は7です*
都市の数-30 *
アルファ（係数。フェロモンの方向）-1
ベータ（経路長の方向係数）-2
p（ローカル更新フェロモン係数）-0.09
e（グローバル更新フェロモン係数）-0.09
q（最も魅力的な都市を選択する係数）-0.9
アリの初期位置-ランダム

*-タスクのディメンションからの変数パラメーター

アリの数について一言。アリが多ければ多いほど良いと信じるのは間違いです。コロニー内に多数のアリがいると、生産性が著しく低下します。まず、アルゴリズムの実行時間が大幅に増加します。第二に、過剰なフェロモンが存在し、それがアリの死の輪と呼ばれる自然環境での類推につながります。したがって、アルゴリズムはローカルの最適な状態に留まります。

コロニー内のアリの数の正確な決定はまだありません; [1]のような近似計算があります。すぐに、アリの数を増やしても解が改善されない最適なポイントを見つけようとしましたが、それらの減少は結果を減少させました。また、単純化された場合、特定の反復でアリの1つのコロニーを実験しました。平均フェロモンレベルが上昇し始めるとすぐに、これをアリの最適な数の基礎としました。

Oliver30タスクの結果：

いくつかのグラフ：

4番目のグラフは、アルゴリズムがそこで停止するのではなく、別の方法を探し続けていることを示しています。アリの数が50〜100に増加すると、平均生成距離の広がりは20〜30の範囲で減少し、ジャムが発生します。

対称巡回セールスマン問題のオプションの完全な列挙は、（n-1）！/ 2または

このタスクには4 420880996 869850 977 271 808 000 000

100％の結果、優れたACSパフォーマンス

アニーリング方法を見てみましょう。

パラメータ：

都市の数-30 *
初期温度-35,000 *
最終温度-0.1
温度式-初期温度/ k回目の反復
反復回数-350 000 *
受入確率関数-exp（-ΔE/ T）
潜在的なルート（生成ファミリ）の決定-ベクトルの一部（現在のルート）は、一様分布によってランダムに選択された2つの番号から変換されます。

*-タスクのディメンションからの変数パラメーター

結果：

30都市の時間と品質の両方で、ACSは大きな差で勝ちました。このタスクだけでなく、他の30でも2つのアルゴリズムをテストしました-ACSは確かに単純なアニーリングメソッドを無効にします。

現在、タスクは51都市のEil51にあり、最適なソリューションは426、7000反復、アリの数9です

いくつかのグラフ：

4番目のチャートには、回帰直線が追加されています。一般に、多くの外国の研究におけるEil51問題は、はるかに多くの反復でテストされました。多分それがグローバル最適が見つからなかった理由かもしれません、率直に言って、私はそれを大規模な反復でテストし、見つかった最大値は427です。

この機会に、反復回数からのフェロモンの変化を「リアルモード」で見てみましょう。私はこの写真がとても気に入りました。

グローバルな更新なしで、ASのような共通の蒸発係数を追加すると、より大きな効果が得られます。

2,500,000回の繰り返しでのアニーリング方法を見る

かなり良い結果ですが、まだACSはまだ来ていません。

Eil101タスクは101の都市に対応し、最適な距離は629、9000回の反復、アリの数11です。

いくつかのグラフ：

ここで、100回目のタスクでは9,000回の反復がかなり小さくなっていますが、この結果を7,000,000回の反復で同じ時間間隔でのアニーリングと比較します。

ACSが示したよりもかなり安定した結果。しかし、ACSを使用すると、検索を従来のアニーリングよりも管理しやすくすることができます（後者では、少なくとも停止条件を導入できますが、次の記事ではさらに詳しく説明します）。そのため、ACSは現在、あらゆる点で最大100のピークを獲得しています。さらに、ACSコードを最適化することは依然として可能ですが、アニーリング方法をさらに高速化することは不可能です。（この場合、コードの最適化は不十分です）。

ACSのメインプラス（およびantアルゴリズムの他の修正）を繰り返します。無限の反復回数でグローバルな最適値を検索する場合、グローバルを見つける確率は1になる傾向があります。もちろん問題は時間内です。迅速に、しかしおおよそ、または長いが、確かに。そのため、都市の数に対する時間の依存性（各アルゴリズムで同じ反復回数）を構築することを提案します。

ACSの反復回数-10 000、アリ-10。

SAの反復回数は7,000,000です。

わあ！アニーリング法は、頂点の数に関係なく一定の時間がかかることがわかります。回帰を構築することにより、ACSの時間の複雑さを判断します。

t = 0.0044939x ^ 2 + 0.72097x + 3.8225（式4）

ここで、xは都市の数、tはACSランタイムです

最大100個の頂点を持つ2つのアルゴリズムが時間と品質の両方にほぼ匹敵する場合（ACSをわずかに上回る）、1000の都市ではACSで10,000回、SAで7,000,000回の反復がほぼ除外されます。似ているはずです。

ご覧ください。

ACS 200都市（ランダムな都市）、時間-311.54秒。

SA 200都市（上記と同じ）、時間103.19秒。

順次起動します。両方が同じ結果を示す可能性はどのくらいですか？おもしろい瞬間が出ました。おそらく100分の1が一致したのでしょうか？しかし、あなたも私もこれをもう知らないでしょう）

一般に、一連のテスト、および300の頂点で、ほぼ同じ結果が得られ、プラスを超えるとアニーリング方法はなくなります。

制限時間が100を超える頂点数の場合、単純なアニーリング方法はACSよりも優れています。繰り返しますが、MMAS、ACSローカル検索、またはその他の変更ではなくACSです。

しかし、グローバルな最適化を見つける必要がある場合があり、Antアルゴリズムと競合できる人はほとんどいません。

次に、シミュレーテッドアニーリング法の高速化についていくつか説明します。

読者がdaiver19を提案したように、もちろん、各反復でルートをカウントしないでください。

条件付きルートがあります：

1 2 3 4 5 6 7 8 9

2つの数字がランダムに選択されました（2.5）

これで、距離（1,2）と（5,6）を計算し、距離（1,5）と（2,6）を計算するだけで十分です。

ただし、非対称の問題では、これは機能しません。

これにより、都市の数はアルゴリズムの実行時間に影響を与えず、さらにかなりの時間を要したfliplr関数が削除されました。乱数の配列も事前に作成されました。これにより、前の記事でアルゴリズムの速度が大幅に向上しました。

また、読者の1人は、2つの頂点間のパスを反転するのではなく、2つの頂点を再配置したときの結果に興味を持っています。 1,000,000回の反復で、Eil101の101都市で結果を見てみましょう。

パスの反転ははるかに優れています。

他の多くのことを見せて伝えたいと思いますが、それでも記事はかなり長いです。次の出版物では、アニーリング方法を「ねじり」、より管理しやすいものにしています。また、antアルゴリズムの他の修正を検討し、もう少し深く掘り下げてから、遺伝学に進むこともできます。

ここで、無条件のリーダー（これまで最大100個のピーク）がどのようにグローバルなより良いパスに向かっているかを確認することを提案します。

また、時間のリーダーとSAの頂点の数を調べることを提案します。これにより、34秒で4,000,000回の反復で1000の頂点の近似解が得られます。前回の記事で500頂点の2,000,000回の反復が90秒だった場合、14.6になりました！

そのようなもの。コメント付きのソース。コードの読みやすさと速度のバランスを維持しようとしました。 MatLabを初めて使用する人でも、アルゴリズムの本質を理解するのに非常に役立つので、それらに目を通すことをお勧めします。

シミュレーテッドアニーリング。 コメント付きの完全なコード

%   (     ) %-------------------------------------------------------------------------- tic % clearvars -except cities clearvars % ----------------------------------------------------------------- % -  m = 1000000; % ---------------------------------------------------------------- %   Tstart = 100000; %   Tend = 0.1; %     T = Tstart; %  S = inf; %   n = 500; %  ? g = 1; % ------------------------------------------------------------------- %   dist = zeros(n,n); % ------------------------------------------------------------------------- %   (x,y) cities = rand(n,2)*100; %      RANDONE = rand(m,1); %      D = randi(n,m,2); %    ROUTE = randperm(n); %    for i = 1:n for j = 1:n % dist (  ) dist(i,j) = sqrt((cities(i,1) - cities(j,1))^2 + ... (cities(i,2) - cities(j,2))^2); end end %  ,   -  for k = 1:m %    Sp = 0; %     , ROUTEp - %   %   ROUTEp = ROUTE; %    transp = D(k,[1,2]); %    ,      . if transp(1) < transp(2) if transp(1) ~= 1 && transp(2) ~= n S = dist(ROUTE(transp(1)-1),ROUTE(transp(1))) + ... dist(ROUTE(transp(2)),ROUTE(transp(2)+1)); elseif transp(1) ~= 1 && transp(2) == n S = dist(ROUTE(transp(1)-1),ROUTE(transp(1))) + ... dist(ROUTE(transp(2)),ROUTE(1)); elseif transp(1) == 1 && transp(2) ~= n S = dist(ROUTE(end),ROUTE(transp(1))) + ... dist(ROUTE(transp(2)),ROUTE(transp(2)+1)); end else if transp(2) ~= 1 && transp(1) ~= n S = dist(ROUTE(transp(2)-1),ROUTE(transp(2))) + ... dist(ROUTE(transp(1)),ROUTE(transp(1)+1)); elseif transp(2) ~= 1 && transp(1) == n S = dist(ROUTE(transp(2)-1),ROUTE(transp(2))) + ... dist(ROUTE(transp(1)),ROUTE(1)); elseif transp(2) == 1 && transp(1) ~= n S = dist(ROUTE(end),ROUTE(transp(2))) + ... dist(ROUTE(transp(1)),ROUTE(transp(1)+1)); end end %------------------------------------------------------------------------- if transp(1) < transp(2) ROUTEp(transp(1):transp(2)) = ROUTEp(transp(2):-1:transp(1)); if transp(1) ~= 1 && transp(2) ~= n Sp = dist(ROUTEp(transp(1)-1),ROUTEp(transp(1))) + ... dist(ROUTEp(transp(2)),ROUTEp(transp(2)+1)); elseif transp(1) ~= 1 && transp(2) == n Sp = dist(ROUTEp(transp(1)-1),ROUTEp(transp(1))) + ... dist(ROUTEp(transp(2)),ROUTEp(1)); elseif transp(1) == 1 && transp(2) ~= n Sp = dist(ROUTEp(end),ROUTEp(transp(1))) + ... dist(ROUTEp(transp(2)),ROUTEp(transp(2)+1)); end else ROUTEp(transp(2):transp(1)) = ROUTEp(transp(1):-1:transp(2)); if transp(2) ~= 1 && transp(1) ~= n Sp = dist(ROUTEp(transp(2)-1),ROUTEp(transp(2))) + ... dist(ROUTEp(transp(1)),ROUTEp(transp(1)+1)); elseif transp(2) ~= 1 && transp(1) == n Sp = dist(ROUTEp(transp(2)-1),ROUTEp(transp(2))) + ... dist(ROUTEp(transp(1)),ROUTEp(1)); elseif transp(2) == 1 && transp(1) ~= n Sp = dist(ROUTEp(end),ROUTEp(transp(2))) + ... dist(ROUTEp(transp(1)),ROUTEp(transp(1)+1)); end end %-------------------------------------------------------------------------- if Sp < S ROUTE = ROUTEp; iter = k; else %    P = exp((-(Sp - S)) / T); if RANDONE(k) <= P ROUTE = ROUTEp; end end %   T = Tstart / k; %    if T < Tend break; end; end %   citiesOP(:,[1,2]) = cities(ROUTE(:),[1,2]); plot([citiesOP(:,1);citiesOP(1,1)],[citiesOP(:,2);citiesOP(1,2)],'-r.') msgbox ('!') %   clearvars -except cities ROUTE S iter %   toc

Antアルゴリズム。 コメント付きの完全なコード

 %   (     ) % ------------------------------------------------------------------------- tic % clearvars -except cities clearvars % ----------------------------------------------------------------- % -  (  ) age = 2000; % -    countage = 10; % -  n = 50; % ----------------------------------------------------------------- %  -  ,  0     %   a = 1; %  -  ,  0  %      b = 2; %  ,  e = 0.1; %  ,  p = 0.1; %    Q = 1; %        AS q = 0.9; %   ph = Q/(n*2000); % ------------------------------------------------------------------- %   dist = zeros(n,n); %    returndist = zeros(n,n); %       ROUTEant = zeros(countage,n); %       DISTant = zeros(countage,1); %       bestDistVec = zeros(age,1); %    bestDIST = inf; %   ROUTE = zeros(1,n+1); %     (    ) RANDperm = randperm(n); %   P = zeros(1,n); %    val = zeros(1); %    getcity = zeros(1); %     indexP = zeros(1); %  minDISTiterration = zeros(1); % ------------------------------------------------------------------------- %   (x,y) cities = rand(n,2)*100; %    tao = ph*(ones(n,n)); tao(logical(eye(size(tao)))) = 0; %        for i = 1:n for j = 1:n % dist (  ) dist(i,j) = sqrt((cities(i,1) - cities(j,1))^2 + ... (cities(i,2) - cities(j,2))^2); % nn (   ) if i ~= j returndist(i,j) = 1/sqrt((cities(i,1) - cities(j,1))^2 + ... (cities(i,2) - cities(j,2))^2); end end end %  for iterration = 1:age %  (  ) for k = 1:countage % ******************    ****************** %    %     ROUTEant(k,1) = randi([1 n]); %       (   ), - %   -       % ROUTEant(k,1) = RANDperm(k); %           1- % ROUTEant(k,1) = 1; %       ,    %  ,     ,      %   % if iterration == 1 % ROUTEant(k,1) = randi([1 n]); % % ROUTEant(k,1) = RANDperm(k); % % ROUTEant(k,1) = 1; % else % ROUTEant(k,1) = lastROUTEant(k); % end % ********************************************************************* %   ,   ,     for s = 2:n %     ir = ROUTEant(k,s-1); %    (  ) ,     % : tao^a*(1/S)^b % 1/S - returndist. %      (-  *  %  * - ) ,       , %      .    %   .     : % for c = 1:n % P(1,c) = tao(ir,c).^a * returndist(ir,c).^b; % end P = tao(ir,:).^a .* returndist(ir,:).^b; %   (     k- ) %  n ,      ,   %  %     ,   ,  %    0,     %       P(ROUTEant(k,1:s-1)) = 0; %       RANDONE = rand; if RANDONE <= q [val, getcity] = max(P); else %    (     = 1 ) P = P ./ sum(P); getcity = find(cumsum(P) >= RANDONE, 1, 'first'); end %  s-    k-  ROUTEant(k,s) = getcity; end %   k-  ROUTE = [ROUTEant(k,1:end),ROUTEant(k,1)]; %   S = 0; %   k-  for i = 1:n S = S + dist(ROUTE(i),ROUTE(i+1)); end %  k- ,   k-  age-  DISTant(k) = S; %     S if DISTant(k) < bestDIST bestDIST = DISTant(k); bestROUTE = ROUTEant(k,[1:end,1]); iter = iterration; end %  ""  k-  (    %      ,    %  ) % lastROUTEant = ROUTEant(1:end,end); %   ,    for tL = 1:n xL = ROUTE(tL); yL = ROUTE(tL+1); %    tao(xL,yL) = (1-p)*tao(xL,yL) + p*ph; tao(yL,xL) = (1-p)*tao(yL,xL) + p*ph; end end % -------------------------- -------------------------- %   ""   -   tao(tao < 2.500000000000000e-150) = 2.500000000000000e-150; %    for t = 1:n xG = bestROUTE(t); yG = bestROUTE(t+1); %    tao(xG,yG) = tao(xG,yG) + e*(Q/bestDIST); tao(yG,xG) = tao(yG,xG) + e*(Q/bestDIST); end end %   citiesOP(:,[1,2]) = cities(bestROUTE(:),[1,2]); plot([citiesOP(:,1);citiesOP(1,1)],[citiesOP(:,2);citiesOP(1,2)],'.r-') disp (num2str(bestDIST)) msgbox ('!') clearvars -except cities bestDIST bestROUTE iter toc

ご清聴ありがとうございました。また会うまで。

外国の著者の記事：

[1]-M.ドリゴ、LMガンバルデラ、アントコロニーシステム：巡回セールスマン問題への協調学習アプローチ//進化的計算に関するIEEEトランザクションVol。 1、1、pp。53-66、1997。

[2] T.Stützle、H。Hoos、「MAX-MIN Antシステムと巡回セールスマン問題のローカル検索」// IEEE国際会議進化計算、pp。309-314、1997年。

[3] T.Stützle、M。López-Ibáñez、P。Pellegrini、M。Maur、M。de Oca、M。Birattari、Michael Maur、M。Dorigo、「パラメータ適応におけるアリコロニー最適化」//テクニカルレポート、イリディア、Libre de Bruxelles大学、2010

例による最適化。 Antアルゴリズム（ACS）対アニーリング法。 パート2

More articles:

例による最適化。 Antアルゴリズム（ACS）対アニーリング法。パート2