≪グローバル検索アルゴリズム｜Global Search Algorithm｜oem_src≫:パーティクル・クラスタ・アルゴリズム

6574 ワード

最適化マシン学習

序文
ニュートン法,勾配法,共役勾配法,擬ニュートン法を含むいくつかの反復アルゴリズムについて,初期点から反復シーケンスを生成することができる.反復シーケンスは局所極小点に収束することが多い.したがって,アルゴリズムがグローバル最小点に収束することを保証するために,グローバル極小点付近で初期点を選択する必要がある場合がある.さらに,これらの方法はターゲット関数を計算する必要がある.
グローバル最適化アルゴリズムは現代の啓発アルゴリズムとも呼ばれ、グローバル最適化性能を有し、汎用性が高く、並列処理に適したアルゴリズムである.このアルゴリズムは一般的に厳密な理論的根拠を有し,単純に専門家の経験に頼るのではなく,理論的には一定の時間内に最適解または近似最適解を見つけることができる.遺伝アルゴリズムは知能最適化アルゴリズムの一つに属する.
よく用いられるグローバル最適化アルゴリズムには,遺伝アルゴリズム,シミュレーションアニーリングアルゴリズム,タブー探索アルゴリズム,粒子群アルゴリズム,蟻群アルゴリズムがある.
PSOアルゴリズム
粒子群アルゴリズム(Particle swarm optimization)はJames Kennedy&Russell Eberhartによって提案された.前節で論じたシミュレーションアニーリングアルゴリズムとは異なり,粒子群アルゴリズムは単一反復点のみを更新するのではなく,群と呼ばれる反復点のセットを更新する.クラスタ内の各点をパーティクルと呼びます.グループは、各メンバーが移動し、集約を形成することを意図しているが、移動方向はランダムである無秩序なグループと見なすことができる.
具体的には,ターゲット関数のn上の極小点を求める過程である.1)ℝnでランダムにデータ点のセットを生成し,各点に1つの速度を与え,1つの速度ベクトルを構成する.これらの点は、パーティクルの位置として扱われ、速度を指定して動きます.2)データ点毎に対応する目標関数値を計算し,計算結果に基づいて新しいデータ点のセットを生成し,新しい運動速度を与える.
各粒子はこれまで最良の位置を追跡し続け,これまで最良の位置はPbest,グローバル最良の位置Gbestと呼ばれた.粒子の個体最適位置と群の群のグローバル最適位置に基づいて、各粒子の運動速度を調整し、パーティクルの「相互作用」を実現します.すなわち、各反復で、pbestとgbestの重みとして2つの乱数を生成し、pbestとgbestの組み合わせ値を構成します.それぞれ速度項とランダム項と呼ばれ、重み付け後の既存速度を加えることで、既存の速度の更新を実現できます.
ターゲット関数は、
vt+1id=vtid+c1r1(Pid−xid+c2r2(Pgd−xid))(1)xt+1id=xidt+vt+1id(2)
r 1,r 2はU(0,1)分布に従う乱数であり、学習因子c 1,c 2は非負の定数であり、通常はc 1=c 2=2,vid∈[vmin,vmax]、vmaxは自己設定の定数であり、反復終了条件は予め設定された最大反復数または所定の最小適応度閾値である.
Matlabコードの例:

%%       PSO       
%
%%     
clc
clear

%%      
%           
c1 = 1.49445;
c2 = 1.49445;

maxgen=500;   %       
sizepop=100;   %    

Vmax=1;
Vmin=-1;
popmax=5;
popmin=-5;

%%          
for i=1:sizepop
    %        
    pop(i,:)=5*rands(1,2);    %    
    V(i,:)=rands(1,2);  %     
    %     
    fitness(i)=fun(pop(i,:));   %       
end

%%          
[bestfitness bestindex]=min(fitness);
zbest=pop(bestindex,:);   %    
gbest=pop;    %    
fitnessgbest=fitness;   %        
fitnesszbest=bestfitness;   %        

%%     
for i=1:maxgen

    for j=1:sizepop

        %    
        V(j,:) = V(j,:) + c1*rand*(gbest(j,:) - pop(j,:)) + c2*rand*(zbest - pop(j,:));
        V(j,find(V(j,:)>Vmax))=Vmax;
        V(j,find(V(j,:)%    
        pop(j,:)=pop(j,:)+0.5*V(j,:);
        pop(j,find(pop(j,:)>popmax))=popmax;
        pop(j,find(pop(j,:)%    
        fitness(j)=fun(pop(j,:)); 

    end

    for j=1:sizepop

        %      
        if fitness(j) < fitnessgbest(j)
            gbest(j,:) = pop(j,:);
            fitnessgbest(j) = fitness(j);
        end

        %      
        if fitness(j) < fitnesszbest
            zbest = pop(j,:);
            fitnesszbest = fitness(j);
        end
    end 
    yy(i)=fitnesszbest;    

end
%%     
plot(yy)
title('       ','fontsize',12);
xlabel('    ','fontsize',12);ylabel('   ','fontsize',12);

参考論文:[1].An introduction to optimization-最適化導論[J].Edwin K.P.Chong. [2].より簡略化されたより効率的な粒子群アルゴリズム

详细解策略模式追MM,附:追MM有危険,请慎重.

各種検索アルゴリズムの効率比較