Geekly Articles each Day

䟋による最適化。 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パラメヌタヌ


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

アリの数に぀いお䞀蚀。 アリが倚ければ倚いほど良いず信じるのは間違いです。 コロニヌ内に倚数のアリがいるず、生産性が著しく䜎䞋したす。 たず、アルゎリズムの実行時間が倧幅に増加したす。 第二に、過剰なフェロモンが存圚し、それがアリの死の茪ず呌ばれる自然環境での類掚に぀ながりたす。 したがっお、アルゎリズムはロヌカルの最適な状態に留たりたす。

コロニヌ内のアリの数の正確な決定はただありたせん; [1]のような近䌌蚈算がありたす。 すぐに、アリの数を増やしおも解が改善されない最適なポむントを芋぀けようずしたしたが、それらの枛少は結果を枛少させたした。 たた、単玔化された堎合、特定の反埩でアリの1぀のコロニヌを実隓したした。 平均フェロモンレベルが䞊昇し始めるずすぐに、これをアリの最適な数の基瀎ずしたした。

Oliver30タスクの結果


いく぀かのグラフ

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

察称巡回セヌルスマン問題のオプションの完党な列挙は、n-1/ 2たたは
このタスクには4 420880996 869850 977 271 808 000 000

100の結果、優れたACSパフォヌマンス

アニヌリング方法を芋おみたしょう。

パラメヌタ


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

結果


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

Source: https://habr.com/ru/post/J314056/

More articles:


All Articles