模拟退火程序.txt

以一个简单的例子说明模拟退火算法的思想。 模拟退火法求函数f(x,y) = 5sin(xy) + x^2 + y^2的最小值

[原创]模拟退火算法  

 


/*
*  模拟退火法求函数f(x,y) = 5sin(xy) + x^2 + y^2的最小值
*  日期:2004-4-16
*  作者:ARMYLAU
*　EMAIL:[e-mail]
*  结束条件为两次最优解之差小于某小量
*/
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) );
        }
    }
}