『MATLAB知能アルゴリズム30ケース分析』1、遺伝アルゴリズム(量子)2、BPニューラルネットワーク3、粒子群アルゴリズム4、魚群アルゴリズム5、模擬アニーリングアルゴリズム6、蟻群アルゴリズム
一、BPニューラルネットワーク  
 原理(http://wenku.baidu.com/link?url=L737z2YWEJkSJk7QmW__NnKUw4nwuftKQb1Ks8CvbS6yKu9ZKgH2NMbWfXFkU0eVI69iAfErei4NKG4IkWx0UQ4sfew1nlRi6zRjficNPzy)
誤差逆伝搬アルゴリズムによって訓練された多層フィードフォワードネットワークであり,現在最も広く応用されているニューラルネットワークモデルの一つである.BPネットワークは大量の
このマッピング関係を記述する数学的方程式を事前に明らかにすることなく,入出力モードマッピング関係を明らかにした.その学習規則は最速降下法を用いています
逆伝搬により,ネットワークの重み値としきい値を絶えず調整し,ネットワークの誤差を平方と最小にした.BPニューラルネットワークモデルトポロジーは入力層(input)を含む
、hide layer、および出力層(output layer).

          、  、   。   ，          。
               ，         ，               

BPネットワークは広く応用されているが、自身にもいくつかの欠陥と不足があり、主に以下のいくつかの方面の問題を含む.
まず,学習速度が固定されているため,ネットワークの収束速度が遅く,長い訓練時間が必要である.いくつかの複雑な問題に対して、BPアルゴリズムは、主に学習速度が小さすぎるため、変化する学習速度または適応的な学習速度を用いて改善することができる訓練時間が非常に長い可能性がある.
次に、BPアルゴリズムは、勾配降下法を用いて局所最小値を生成する可能性があるため、重み値をある値に収束させることができるが、誤差平面のグローバル最小値であることは保証されない.この問題は付加運動量法を用いて解決できる.
再び,ネットワーク隠蔽層の層数と単位数の選択は理論的に指導されておらず,一般的に経験的または反復実験によって決定される.そのため,ネットワークには冗長性が大きく,ネットワーク学習の負担もある程度増大することが多い.
最後に,ネットワークの学習と記憶は不安定である.すなわち,学習サンプルを増やせば,訓練されたネットワークは最初から訓練を開始する必要があり,従来の重み値や閾値は記憶されていない.ただし、予測、分類、またはクラスタリングの比較的良い重み値は保存できます.

 
  
1 传统的BP算法简述
 
  
　　BP算法是一种有监督式的学习算法，其主要思想是：输入学习样本，使用反向传播算法对网络的权值和偏差进行反复的调整训练，使输出的向量与期望向量尽可能地接近，当网络输出层的误差平方和小于指定的误差时训练完成，保存网络的权值和偏差。具体步骤如下：
 
  
　　（1）初始化，随机给定各连接权及阀值。
 
  
　　（2）由给定的输入输出模式对计算隐层、输出层各单元输出　　
 
  　　（3）计算新的连接权及阀值，计算公式如下： 
   
  
　　（4）选取下一个输入模式对返回第2步反复训练直到网络设输出误差达到要求结束训练。
 
  
　　传统的BP算法，实质上是把一组样本输入/输出问题转化为一个非线性优化问题，并通过负梯度下降算法，利用迭代运算求解权值问题的一种学习方法，但其收敛速度慢且容易陷入局部极小，为此提出了一种新的算法，即高斯消元法。
 
  
2 改进的BP网络算法
 
  
　　2．1 改进算法概述
 
  
　　此前有人提出：任意选定一组自由权，通过对传递函数建立线性方程组，解得待求权。本文在此基础上将给定的目标输出直接作为线性方程等式代数和来建立线性方程组，不再通过对传递函数求逆来计算神经元的净输出，简化了运算步骤。没有采用误差反馈原理，因此用此法训练出来的神经网络结果与传统算法是等效的。其基本思想是：由所给的输入、输出模式对通过作用于神经网络来建立线性方程组，运用高斯消元法解线性方程组来求得未知权值，而未采用传统BP网络的非线性函数误差反馈寻优的思想。
 
  
　　2．2 改进算法的具体步骤
 
  
　　对给定的样本模式对，随机选定一组自由权，作为输出层和隐含层之间固定权值，通过传递函数计算隐层的实际输出，再将输出层与隐层间的权值作为待求量，直接将目标输出作为等式的右边建立方程组来求解。
 
  　　（1）随机给定隐层和输入层间神经元的初始权值。 
   
  
　　（2）由给定的样本输入计算出隐层的实际输出。
 
  
　　（3）计算输出层与隐层间的权值。以输出层的第r个神经元为对象，由给定的输出目标值作为等式的多项式值建立方程。　 　　
 
  
    （4）重复第三步就可以求出输出层m个神经元的权值，以求的输出层的权矩阵加上随机固定的隐层与输入层的权值就等于神经网络最后训练的权矩阵。
 
  
3 计算机运算实例
 
  
  %% 清空环境变量 clc clear
 
  
%% 训练数据预测数据 data=importdata('test.txt');
 
  
%从1到768间随机排序 k=rand(1,768); [m,n]=sort(k);
 
  
%输入输出数据 input=data(:,1:8); output =data(:,9);
 
  
%随机提取500个样本为训练样本，268个样本为预测样本 input_train=input(n(1:500),:)'; output_train=output(n(1:500),:)'; input_test=input(n(501:768),:)'; output_test=output(n(501:768),:)';
 
  
%输入数据归一化 [inputn,inputps]=mapminmax(input_train);
 
  
%% BP网络训练 % %初始化网络结构 net=newff(inputn,output_train,10);
 
  
net.trainParam.epochs=1000; net.trainParam.lr=0.1; net.trainParam.goal=0.0000004;
 
  
%% 网络训练 net=train(net,inputn,output_train);
 
  
%% BP网络预测 %预测数据归一化 inputn_test=mapminmax('apply',input_test,inputps);   %网络预测输出 BPoutput=sim(net,inputn_test);
 
  
%% 结果分析 %根据网络输出找出数据属于哪类 BPoutput(find(BPoutput<0.5))=0; BPoutput(find(BPoutput>=0.5))=1;
 
  
%% 结果分析 %画出预测种类和实际种类的分类图 figure(1) plot(BPoutput,'og') hold on plot(output_test,'r*'); legend('预测类别','输出类别') title('BP网络预测分类与实际类别比对','fontsize',12) ylabel('类别标签','fontsize',12) xlabel('样本数目','fontsize',12) ylim([-0.5 1.5])
 
  
 %预测正确率 rightnumber=0; for i=1:size(output_test,2)     if BPoutput(i)==output_test(i)         rightnumber=rightnumber+1;     end end rightratio=rightnumber/size(output_test,2)*100;
 
  
sprintf('测试准确率=%0.2f',rightratio)
 
  二、遗传算法 
  
http://blog.csdn.net/breezedust/article/details/12378031
  
  
蟻群アルゴリズムが関連分野の研究者の注意を引き起こすのは,この解法が問題解の迅速性,グローバル最適化特徴,および有限時間における答えの合理性を結びつけることができるからである.その中で,最適化の迅速性は正フィードバック式の情報伝達と蓄積によって保証される.アルゴリズムの早熟性収束はまたその分布式計算の特徴によって避けることができて、同時に、貪欲な啓発を持っています
  
図3蟻群が障害物の前に一定時間経過した場合
式探索特徴の蟻群システムはまた探索過程の早期に許容できる問題解を見つけることができる.この優れた問題分布式解モデルは関連分野の研究者の注目と努力を経て,最初のアルゴリズムモデルに基づいて大きな改善と拡張を得た.
一定時間が経過すると,食物源から戻ったアリがD点に到達しても同様に障害物に遭遇し,選択も必要となる.このときA,Bの両側の情報素濃度は同じであり,それらは依然として半分が左,半分が右である.しかし、A側のアリが障害物を完全に迂回してC点に到達した場合、B側のアリは、歩く経路が長いため、まだC点に到達できず、図3は、障害物の前にアリ群が一定時間経過した後の状況を示す.
このとき,蟻の巣からC点に来た蟻にとっては,A側の情報素濃度が高く,B側の情報素が低いため,A側の経路を選択する傾向にある.このような結果、A側のアリはますます多くなり、最終的にすべてのアリがこの短い経路を選択し、図4はアリ群が最終的に選択した経路を示している.
  
図4蟻群の最終選択経路
上記の過程は,アリが残した情報素の「正のフィードバック」過程によるものであることは明らかである.アリ個体はこのような情報の交流を通じて食べ物を検索する目的を達成している.蟻群アルゴリズムの基本思想もこの過程から転化した.

  

  

  

  

  

  

  
       
                        ，            ，             。  ，         。               
 。
2.2.1    
                ，                  。                     。           ，         ，           ，           ，              。                        ，                   、   、          ，           。                  。
     
2.2.2    
          ，                。                              。       ，                     ，                    。    ，              、    、    、    、           NP            。
2.2.3      
                          ，                .                      。                     。                      。         、        、    、                    。
2.2.4    
                       。                ，         。                  、               、                 、           、                、                           。                    。
2.2.5     
                    ，                      。  ，                        。  ，                、           、         、                         。  
2.2.6     
                    。        ，   、    、                 ，         。                          。                          。        (      )、    、                。
2.2.7     
         、                               。                       。                。                           。                ，            、    、    、                   ，                。             ，                     ，                      。
2.2.8     
1989 ，  Standford   Koza            ,      :             ,         ,                。             ,        ,             、       。                 。  ，Koza   ADF  ，While   GPELST   。
2.2.9     
                    ，           ，        ，            。  ，               ，              ，               ；                          ，                ；                             。
2.2.10     
                ，               、     、             。                ，          ，           。  ，               ，              .             ，               。Sunil                      。                           ，                      。
  
 
  
三、粒子群算法
 
  
 
 
  
 
  
 粒子群优化算法(PSO)是一种进化计算技术(evolutionary computation)，1995 年由Eberhart 博士和kennedy 博士提出，源于对鸟群捕食的行为研究 。该算法最初是受到飞鸟集群活动的规律性启发，进而利用群体智能建立的一个简化模型。粒子群算法在对动物集群活动行为观察基础上，利用群体中的个体对信息的共享使整个群体的运动在问题求解空间中产生从无序到有序的演化过程，从而获得最优解。
 
  
基本思想
 
  
    正如简介所描述的那样，粒子群算法是模拟群体智能所建立起来的一种优化算法，像后面我向大家介绍的蚁群算法也属于这类算法，粒子群算法可以用鸟类在一个空间内随机觅食为例，所有的鸟都不知道食物具体在哪里，但是他们知道大概距离多远，最简单有效的方法就是搜寻目前离食物最近的鸟的周围区域。
 
  
    所以，粒子群算法就是把鸟看成一个个粒子，并且他们拥有位置和速度这两个属性，然后根据自身已经找到的离食物最近的解和参考整个共享于整个集群中找到的最近的解去改变自己的飞行方向，最后我们会发现，整个集群大致向同一个地方聚集。而这个地方是离食物最近的区域，条件好的话就会找到食物。这就是粒子群算法，很好理解。
 
  
算法描述
 
  
    所以，我们需要一个pbest来记录个体搜索到的最优解，用gbest来记录整个群体在一次迭代中搜索到的最优解。速度和粒子位置的更新公式如下：
 
  
 
 
  
    v[i] = w * v[i] + c1 * rand() * (pbest[i] - present[i]) + c2 * rand() * (gbest - present[i])    
 
  
    present[i] = present[i] + v[i]                                                                                                          
 
  
    其中v[i]代表第i个粒子的速度，w代表惯性权值,c1和c2表示学习参数，rand()表示在0-1之间的随机数,pbest[i]代表第i个粒子搜索到的最优值,gbest代表整个集群搜索到的最优值,present[i]代表第i个粒子的当前位置。
 
  但是粒子群算法并没有像遗传算法那样有选择交叉变异这样的过程，而更多的是体现在追踪单个粒子和共享集体最优信息来实现向最优空间搜索的形式，但是正由于它不同于遗传算法那样去忽略个体的一些内在联系，所以 
  往往会陷入局部最优 
  ，所以，在粒子群算法中 
  加入像遗传算法中的变异或者模拟退火等，可以跳过这个局部最优解 
  。 
  
研究鸟群系统，每个鸟在这个系统中就称为主体。主体有适应性，它能够与环境及其他的主体进行交流，并且根据交流的过程“学习”或“积累经验”改变自身结构与行为。整个系统的演变或进化包括：新层次的产生（小鸟的出生）；分化和多样性的出现（鸟群中的鸟分成许多小的群）；新的主题的出现（鸟寻找食物过程中，不断发现新的食物）。
 
  
    所以CAS系统中的主体具有4个基本特点（这些特点是粒子群算法发展变化的依据）：
 
  
 
   
首先，主体是主动的、活动的。
 
   
主体与环境及其他主体是相互影响、相互作用的，这种影响是系统发展变化的主要动力。
 
   
环境的影响是宏观的，主体之间的影响是微观的，宏观与微观要有机结合。
 
   
最后，整个系统可能还要受一些随机因素的影响。
 
  
 
  
粒子群算法就是对一个CAS系统－－－鸟群社会系统的研究得出的。
 
  
       粒子群算法（ Particle Swarm Optimization, PSO）最早是由Eberhart和Kennedy于1995年提出，它的基本概念源于对鸟群觅食行为的研究。设想这样一个场景:一群鸟在随机搜寻食物，在这个区域里只有一块食物，所有的鸟都不知道食物在哪里，但是它们知道当前的位置离食物还有多远。那么找到食物的最优策略是什么呢?最简单有效的就是搜寻目前离食物最近的鸟的周围区域。   
 
  
      PSO算法就从这种生物种群行为特性中得到启发并用于求解优化问题。在PSO中，每个优化问题的潜在解都可以想象成d维搜索空间上的一个点，我们称之为“粒子”（Particle），所有的粒子都有一个被目标函数决定的适应值(Fitness Value )，每个粒子还有一个速度决定他们飞翔的方向和距离，然后粒子们就追随当前的最优粒子在解空间中搜索。Reynolds对鸟群飞行的研究发现。鸟仅仅是追踪它有限数量的邻居但最终的整体结果是整个鸟群好像在一个中心的控制之下.即复杂的全局行为是由简单规则的相互作用引起的。
 
  
不同点
 
  

    与 遗传算法比较，PSO的信息共享机制是很不同的。在遗传算法中，染色体(chromosomes)互相共享信息，所以整个种群的移动是比较均匀的向最优区域移动。在PSO中, 只有gBest (orlBest) 给出信息给其他的 粒子， 这是单向的信息流动。整个搜索更新过程是跟随当前最优解的过程。与遗传算法比较, 在大多数的情况下，所有的粒子可能更快的收敛于 最优解。 
  
 
  四、模拟退火算法 
    
  
  
　1. アナログアニーリングアルゴリズム
　　2. 遺伝アルゴリズム
  
一.山登りアルゴリズム(Hill Climbing)
         シミュレーションアニーリングを紹介する前に,まず山登りアルゴリズムを紹介する.山登りアルゴリズムは、現在の解の近接解空間から現在の解として最適解を選択するたびに、局所最適解に達するまで、単純な貪欲探索アルゴリズムである.
         山登りアルゴリズムの実現は簡単で,その主な欠点は局所最適解に陥り,必ずしもグローバル最適解を探索できるとは限らないことである.図1に示すように、C点が現在の解であると仮定すると、山登りアルゴリズムがA点を探索する局所最適解は、A点がその方向に小幅に移動してもより優れた解が得られないため、探索を停止する.
  
図1
  
  
二.模擬焼なまし(SA,Simulated Annealing)思想
         山登り法は完全な貪欲法であり,毎回マウス目寸光の現在の最適解を選択するため,局所的な最適値しか探索できない.シミュレーションアニーリングも実は欲張りアルゴリズムであるが,その探索過程はランダム因子を導入した.シミュレーションアニーリングアルゴリズムは,現在の解よりも悪い解を一定の確率で受け入れるため,この局所的な最適解から飛び出し,グローバルな最適解に達する可能性がある.図1を例にとると,シミュレーションアニーリングアルゴリズムは局所最適解Aを探索した後,一定の確率でEの移動を受け入れる.このような局所最適でない移動を何回か経てD点に到達するかもしれないので,局所最大値Aから飛び出した.
         シミュレーションアニーリングアルゴリズムの説明:
         J(Y(i+1)>=J(Y(i)) (すなわち、移動後により好ましい解が得られる)と、常にその移動を受け入れる
         J(Y(i+1)ここでの「一定確率」の計算は金属製錬のアニーリング過程を参照し,これもシミュレーションアニーリングアルゴリズム名の由来である.
熱力学の原理によると、温度がTの場合、エネルギー差dEの降温が現れる確率はP(dE)であり、
　　　　P(dE) = exp( dE/(kT) ) 
ここで、kは定数であり、expは自然指数を表し、dE<0である.この公式は、温度が高いほど、エネルギー差がdEの温度を下げる確率が大きくなることを明らかにした.温度が低ければ低いほど、温度が下がる確率は小さくなります.また、dEは常に0より小さい(そうでなければアニールと呼ばない)ため、dE/kT<0であるため、P(dE)の関数取値範囲は(0,1)である.
温度Tが低下するとP(dE)は徐々に低下する.
低い解への一次移動を温度ホッピング過程と見なし,確率P(dE)でこのような移動を受け入れた.
山登りアルゴリズムとシミュレーションアニーリングについて、興味深い比喩があります.
山に登るアルゴリズム:ウサギは今より高いところに向かって飛びます.遠くない最高峰を見つけましたしかし、この山はエベレストとは限らない.これが山登りアルゴリズムであり,局所最適値がグローバル最適値であることを保証することはできない.
模擬焼なまし:ウサギが酔っ払った.ランダムに長い間踊っていましたその間、高いところに向かうかもしれないし、平地に足を踏み入れるかもしれない.しかし、徐々に目が覚めて最高方向に飛び上がった.これがシミュレーションアニーリングである.
  
シミュレーションアニーリングの擬似コード表現を以下に示す.
  
三.アナログアニーリングアルゴリズムの擬似コード
  
コード
/**J(y):状態yにおける評価関数値*Y(i):現在の状態を表す*Y(i+1):新しい状態を表す*r:温度を下げる速さを制御する*T:システムの温度、システムの初期は高温の状態にあるべきである*T_min:温度の下限、温度TがT_に達したらmin、検索*/while(T)を停止 > T_min ) { 　　dE = J( Y(i+1) ) - J( Y(i) ) ;  　　if ( dE >=0 ) //移動を表すとより良い解が得られ,常に移動Y(i+1)を受け入れる. = Y(i) ; //Y(i)からY(i+1)への移動elseを受け入れる// 関数exp(dE/T)の取値範囲は(0,1)、dE/Tが大きいほどexp(dE/T)もif ( exp( dE/T ) > random( 0 , 1 ) ) Y(i+1) = Y(i) ; //Y(i)からY(i+1)への移動を受け入れる}T = r * T ; //温度を下げてアニールすると、0/*rが大きすぎると、グローバル最適解を検索する可能性が高くなりますが、検索のプロセスも長くなります.rが小さすぎると、検索のプロセスは速くなりますが、最終的にはローカル最適値*/iに達する可能性があります. ++ ; }  
  
四.シミュレーションアニーリングアルゴリズムを用いて旅行者の問題を解決する
旅行者問題(TSP,Traveling Salesman Problem):N都市があり、その中のある問題から出発し、唯一すべての都市を遍歴し、出発した都市に戻り、最短のルートを求める.
旅行者問題はいわゆるNP完全問題に属し,TSPを正確に解決するにはすべての経路の組合せを窮挙するしかなく,その時間的複雑さはO(N!)である.
シミュレーションアニーリングアルゴリズムを用いてTSPの近似最適経路を比較的速く求めることができる.(遺伝アルゴリズムを用いてもよいが、次の記事で紹介する)シミュレーションアニーリングによるTSP解決の考え方:
1.新しい遍歴経路P(i+1)を生成し、経路P(i+1)の長さL(P(i+1)を計算する.
2.L(P(i＋1)＜L(P(i))))の場合、P(i＋1)を新たな経路とし、そうでなければ模擬焼なましの確率でP(i＋1)を受け入れ、その後温度を下げる
3.終了条件が満たされるまで手順1、2を繰り返す
新しいパスを作成する方法はいくつかありますが、以下の3つを挙げます.
1.ランダムに2つのノードを選択し、パス内の2つのノードの順序を入れ替える.
2.ランダムに2つのノードを選択し、パス内の2つのノード間のノードを順番に逆転します.
3.3つのノードm,n,kをランダムに選択し、ノードmとnとの間のノードをノードkの後ろにシフトする.
  
五.アルゴリズム評価
        シミュレーションアニーリングアルゴリズムはランダムアルゴリズムであり,必ずしもグローバルな最適解を見つけることができず,問題の近似最適解を比較的速く見つけることができる. パラメータが適切に設定されている場合,シミュレーションアニーリングアルゴリズムの探索効率は窮挙法よりも高い.