[原創]模擬退火算法  

 


/*
*  模擬退火法求函數f(x,y) = 5sin(xy) + x^2 + y^2的最小值
*  日期:2004-4-16
*  作者:ARMYLAU
*　EMAIL:armylau2@163.com
*  結束條件為兩次最優解之差小于某小量
*/
using System;
namespace SimulateAnnealing
{
    class Class1
    {
         // 要求最優值的目標函數
        static double ObjectFunction( double x, double y )
        {
             double z = 0.0;
             z = 5.0 * Math.Sin(x*y) + x*x + y*y;
             return z;
        }
        [STAThread]
        static void Main(string[] args)
        {
             // 搜索的最大區間
             const double XMAX = 4;
             const double YMAX = 4;
             // 冷卻表參數
             int      MarkovLength = 10000;            // 馬可夫鏈長度
             double   DecayScale = 0.95;               // 衰減參數
             double  　StepFactor = 0.02;              // 步長因子
             double   Temperature = 100;          // 初始溫度
             double  　Tolerance = 1e-8;          // 容差
             double   PreX,NextX;                // prior and next value of x 
             double   PreY,NextY;                // prior and next value of y 
             double  　PreBestX, PreBestY;        // 上一個最優解
             double   BestX,BestY;               // 最終解
             double   AcceptPoints = 0.0;         // Metropolis過程中總接受點
             Random rnd = new Random();            
             // 隨機選點
             PreX = -XMAX * rnd.NextDouble() ;
             PreY = -YMAX * rnd.NextDouble();
             PreBestX = BestX = PreX;
             PreBestY = BestY = PreY;
             // 每迭代一次退火一次(降溫), 直到滿足迭代條件為止 
             do
             {
                  Temperature *=DecayScale;
                  AcceptPoints = 0.0;
                  // 在當前溫度T下迭代loop(即MARKOV鏈長度)次
                  for (int i=0;i                   {
                      // 1) 在此點附近隨機選下一點
                      do
                      {
                           NextX = PreX + StepFactor*XMAX*(rnd.NextDouble()-0.5);
                           NextY = PreY + StepFactor*YMAX*(rnd.NextDouble()-0.5);
                      }
                      while ( !(NextX >= -XMAX && NextX = -YMAX && NextY  
                      // 2) 是否全局最優解
                      if (ObjectFunction(BestX,BestY) > ObjectFunction(NextX,NextY))
                      {
                           // 保留上一個最優解
                           PreBestX =BestX;
                           PreBestY = BestY;
                           // 此為新的最優解
                           BestX=NextX;
                           BestY=NextY;
                      }
                      // 3) Metropolis過程
                      if( ObjectFunction(PreX,PreY) - ObjectFunction(NextX,NextY) > 0 )
                      {
                           // 接受, 此處lastPoint即下一個迭代的點以新接受的點開始
                           PreX=NextX;
                           PreY=NextY;
                           AcceptPoints++;
                      }
                      else
                      {
                           double change = -1 * ( ObjectFunction(NextX,NextY) - ObjectFunction(PreX,PreY) ) / Temperature ;
                           if( Math.Exp(change) > rnd.NextDouble() )
                           {
                                PreX=NextX;
                                PreY=NextY;
                                AcceptPoints++;
                           }
                           // 不接受, 保存原解
                      }
                  }
             Console.WriteLine("{0},{1},{2},{3}",PreX, PreY, ObjectFunction ( PreX, PreY ), Temperature);
             }　while( Math.Abs( ObjectFunction( BestX,BestY) – ObjectFunction (PreBestX, PreBestY)) > Tolerance );
             Console.WriteLine("最小值在點:{0},{1}",BestX, BestY);
             Console.WriteLine( "最小值為:{0}",ObjectFunction(BestX, BestY) );
        }
    }
}