• C#，动态规划（DP）模拟退火（Simulated Annealing）算法与源代码

    1 模拟退火

    *问题:**给定一个成本函数f:r^n–>r*，找到一个 n 元组，该元组最小化 f 的值。请注意，最小化函数值在算法上等同于最大化(因为我们可以将成本函数重新定义为 1-f)。 很多有微积分/分析背景的人可能都熟悉单变量函数的简单优化。例如，函数 f(x) = x^2 + 2x 可以通过将一阶导数设置为零来优化，从而获得产生最小值 f(-1) = -1 的解 x = -1 。这种技术适用于变量很少的简单函数。然而，通常情况下，研究人员对优化几个变量的函数感兴趣，在这种情况下，只能通过计算获得解。

    一个困难的优化任务的极好例子是芯片平面规划问题。假设你在英特尔工作，你的任务是设计集成电路的布局。您有一组不同形状/大小的模块，以及可以放置模块的固定区域。你想要达到的目标有很多:最大化导线连接元件的能力，最小化净面积，最小化芯片成本，等等。考虑到这些，您创建了一个成本函数，取所有，比如说， 1000 个变量配置，并返回一个代表输入配置“成本”的实数值。我们称之为目标函数，因为目标是最小化它的值。 一个简单的算法是完全的空间搜索——我们搜索所有可能的配置，直到找到最小值。这对于变量很少的函数来说可能就足够了，但是我们想到的问题需要这样一个强力算法来玩 *O(n！)*。

    由于这类问题和其他 NP 难问题的计算困难，许多优化试探法已经被开发出来，试图产生一个好的，尽管可能是次优的值。在我们的例子中，我们不一定需要找到一个严格的最优值——找到一个接近最优的值将满足我们的目标。一种广泛使用的技术是模拟退火，通过它我们引入了一定程度的随机性，有可能从一个更好的解转移到一个更差的解，试图逃离局部极小值并收敛到一个更接近全局最优的值。

    模拟退火是基于冶金实践，通过这种实践，材料被加热到高温并冷却。在高温下，原子可能会不可预测地移动，通常会随着材料冷却成纯晶体而消除杂质。这是通过模拟退火优化算法复制的，能量状态对应于当前解。 在这个算法中，我们定义了一个初始温度和一个最低温度，初始温度通常设置为 1，最低温度的数量级为 10^-4.当前温度乘以某个分数α，然后降低，直到达到最低温度。对于每个不同的温度值，我们运行核心优化例程的次数是固定的。优化程序包括找到一个相邻解并以概率e^(f(c–f(n)】接受它，其中 c 是当前解而 n 是相邻解。通过对当前解施加微小的扰动来找到相邻解。这种随机性有助于避开优化启发式算法的常见陷阱——陷入局部极小值。通过潜在地接受一个比我们目前拥有的更差的最优解，并以与成本增加相反的概率接受它，算法更有可能收敛到全局最优。设计一个邻居函数是相当棘手的，必须在个案的基础上完成，但以下是在位置优化问题中寻找邻居的一些想法。

    • 在随机方向上将所有点移动 0 或 1 个单位
    • 随机移动输入元素
    • 交换输入序列中的随机元素
    • 置换输入序列
    • 将输入序列分成随机数量的段和置换段

    一个警告是，我们需要提供一个初始解决方案，以便算法知道从哪里开始。这可以通过两种方式来实现:(1)使用关于问题的先验知识来输入良好的起点，以及(2)生成随机解。尽管生成随机解更糟糕，有时会抑制算法的成功，但对于我们对环境一无所知的问题，这是唯一的选择。

    还有许多其他优化技术，尽管模拟退火是一种有用的随机优化启发式方法，适用于大型离散搜索空间，在这些空间中，随着时间的推移，最优性是优先的。下面，我包含了一个基于位置的模拟退火的基本框架(可能是模拟退火最适用的优化风格)。当然，成本函数、候选生成函数和邻居函数必须根据手头的具体问题来定义，尽管核心优化例程已经实现。

    2 源程序（文本格式）

    using System;
    using System.Text;

    namespace Legalsoft.Truffer.Algorithm
    {
        ///


        /// 算法核心数据类
        /// 含：方差系数均方根误差，配置参数（数组）
        ///
        public class Anneal_Solution
        {
            ///
            /// 方差系数均方根误差
            /// Coefficient of Variance Root Mean Squared Error
            /// 默认初值0.0；不超过1.0；
            ///
            public double CVRMSE { get; set; } = 0.0;
            ///
            /// 配置参数（数组）
            /// 整型数组；无初值（null）；
            ///
            public int[] Config { get; set; } = null;
            ///
            /// （无参）默认构造函数
            ///
            public Anneal_Solution()
            {
            }
            ///
            /// （有参）构造函数
            ///
            /// 方差系数均方根误差
            /// 配置参数（数组）
            public Anneal_Solution(double CVRMSE, int[] configuration)
            {
                this.CVRMSE = CVRMSE;
                Config = configuration;
            }
        }

        ///


        /// 模拟退火算法
        ///
        public class Simulated_Annealing
        {
            private static Random rand { get; set; } = new Random((int)DateTime.Now.Ticks);

            public static string Solve(int M = 15, int N = 15, double T_Minium = 0.0001, double Alpha = 0.9, int Maxium_Iterations = 100)
            {
                string[,] sourceArray = new string[M, N];
                Anneal_Solution min = new Anneal_Solution(double.MaxValue, null);
                Anneal_Solution currentSol = Rand_Solution(M);

                double temperature = 1.0;
                while (temperature > T_Minium)
                {
                    for (int i = 0; i < Maxium_Iterations; i++)
                    {
                        if (currentSol.CVRMSE < min.CVRMSE)
                        {
                            min = currentSol;
                        }

                        Anneal_Solution newSol = Neighbor(currentSol);
                        double ap = Math.Pow(Math.E, (currentSol.CVRMSE - newSol.CVRMSE) / temperature);
                        if (ap > rand.NextDouble())
                        {
                            currentSol = newSol;
                        }
                    }
                    temperature *= Alpha;
                }
                #endregion

                for (int i = 0; i < sourceArray.GetLength(0); i++)
                {
                    for (int j = 0; j < sourceArray.GetLength(1); j++)
                    {
                        sourceArray[i, j] = "X";
                    }
                }

                foreach (int k in min.Config)
                {
                    int[] coord = Index_To_Points(M, N, k);
                    sourceArray[coord[0], coord[1]] = "-";
                }

                StringBuilder sb = new StringBuilder();
                for (int i = 0; i < sourceArray.GetLength(0); i++)
                {
                    for (int j = 0; j < sourceArray.GetLength(1); j++)
                    {
                        sb.Append(sourceArray[i, j] + ", ");
                    }
                    sb.AppendLine("
    ");
                }
                return sb.ToString();
            }

            public static Anneal_Solution Neighbor(Anneal_Solution currentSol)
            {
                return currentSol;
            }

            public static Anneal_Solution Rand_Solution(int n)
            {
                int[] a = new int[n];
                for (int i = 0; i < n; i++)
                {
                    a[i] = i + 1;
                }
                return new Anneal_Solution(-1, a);
            }

            public static double Cost(int[] inputConfiguration)
            {
                return -1;
            }

            public static int[] Index_To_Points(int M, int N, int index)
            {
                int[] points = { index % M, index / M };
                return points;
            }
        }
    }
     

    3 代码格式

    1. using System;
    2. using System.Text;
    3.  
    4. namespace Legalsoft.Truffer.Algorithm
    5. {
    6.     /// 
    7.     /// 算法核心数据类
    8.     /// 含：方差系数均方根误差，配置参数（数组）
    9.     /// 
    10.     public class Anneal_Solution
    11.     {
    12.         /// 
    13.         /// 方差系数均方根误差
    14.         /// Coefficient of Variance Root Mean Squared Error
    15.         /// 默认初值0.0；不超过1.0；
    16.         /// 
    17.         public double CVRMSE { get; set; } = 0.0;
    18.         /// 
    19.         /// 配置参数（数组）
    20.         /// 整型数组；无初值（null）；
    21.         /// 
    22.         public int[] Config { get; set; } = null;
    23.         /// 
    24.         /// （无参）默认构造函数
    25.         /// 
    26.         public Anneal_Solution()
    27.         {
    28.         }
    29.         /// 
    30.         /// （有参）构造函数
    31.         /// 
    32.         /// 方差系数均方根误差
    33.         /// 配置参数（数组）
    34.         public Anneal_Solution(double CVRMSE, int[] configuration)
    35.         {
    36.             this.CVRMSE = CVRMSE;
    37.             Config = configuration;
    38.         }
    39.     }
    40.  
    41.     /// 
    42.     /// 模拟退火算法
    43.     /// 
    44.     public class Simulated_Annealing
    45.     {
    46.         private static Random rand { get; set; } = new Random((int)DateTime.Now.Ticks);
    47.  
    48.         public static string Solve(int M = 15, int N = 15, double T_Minium = 0.0001, double Alpha = 0.9, int Maxium_Iterations = 100)
    49.         {
    50.             string[,] sourceArray = new string[M, N];
    51.             Anneal_Solution min = new Anneal_Solution(double.MaxValue, null);
    52.             Anneal_Solution currentSol = Rand_Solution(M);
    53.  
    54.             double temperature = 1.0;
    55.             while (temperature > T_Minium)
    56.             {
    57.                 for (int i = 0; i < Maxium_Iterations; i++)
    58.                 {
    59.                     if (currentSol.CVRMSE < min.CVRMSE)
    60.                     {
    61.                         min = currentSol;
    62.                     }
    63.  
    64.                     Anneal_Solution newSol = Neighbor(currentSol);
    65.                     double ap = Math.Pow(Math.E, (currentSol.CVRMSE - newSol.CVRMSE) / temperature);
    66.                     if (ap > rand.NextDouble())
    67.                     {
    68.                         currentSol = newSol;
    69.                     }
    70.                 }
    71.                 temperature *= Alpha;
    72.             }
    73.             #endregion
    74.  
    75.             for (int i = 0; i < sourceArray.GetLength(0); i++)
    76.             {
    77.                 for (int j = 0; j < sourceArray.GetLength(1); j++)
    78.                 {
    79.                     sourceArray[i, j] = "X";
    80.                 }
    81.             }
    82.  
    83.             foreach (int k in min.Config)
    84.             {
    85.                 int[] coord = Index_To_Points(M, N, k);
    86.                 sourceArray[coord[0], coord[1]] = "-";
    87.             }
    88.  
    89.             StringBuilder sb = new StringBuilder();
    90.             for (int i = 0; i < sourceArray.GetLength(0); i++)
    91.             {
    92.                 for (int j = 0; j < sourceArray.GetLength(1); j++)
    93.                 {
    94.                     sb.Append(sourceArray[i, j] + ", ");
    95.                 }
    96.                 sb.AppendLine("
      "      );
    97.             }
    98.             return sb.ToString();
    99.         }
    100.  
    101.         public static Anneal_Solution Neighbor(Anneal_Solution currentSol)
    102.         {
    103.             return currentSol;
    104.         }
    105.  
    106.         public static Anneal_Solution Rand_Solution(int n)
    107.         {
    108.             int[] a = new int[n];
    109.             for (int i = 0; i < n; i++)
    110.             {
    111.                 a[i] = i + 1;
    112.             }
    113.             return new Anneal_Solution(-1, a);
    114.         }
    115.  
    116.         public static double Cost(int[] inputConfiguration)
    117.         {
    118.             return -1;
    119.         }
    120.  
    121.         public static int[] Index_To_Points(int M, int N, int index)
    122.         {
    123.             int[] points = { index % M, index / M };
    124.             return points;
    125.         }
    126.     }
    127. }

  • 相关阅读:
    BPA、BPM、BPR傻傻分不清楚？与RPA又有何关系？
    网络编程 WSAStartup
    SkeyeVSS密集场所人流密度监控预警解决方案
    Vue源码学习(五):<templete>渲染第四步,生成虚拟dom并将其转换为真实dom
    监听el-table滚动
    【MySQL篇】初识数据库
    SpringBoot项目使用hutool工具进行HttpClient接口调用的处理(文件上传)
    Mini小主机All-in-one搭建教程1-安装Esxi7.0虚拟机系统
    分布式存储系统——ceph
    免费版Photoshop2024智能人像磨皮插件
  • 原文地址：https://blog.csdn.net/beijinghorn/article/details/124744526