763
个编辑
更改
跳到导航
跳到搜索
第91行：
第91行： − + − In order to apply the simulated annealing method to a specific problem, one must specify the following parameters: the state space, the energy (goal) function {{code|E()}}, the candidate generator procedure {{code|neighbour()}}, the acceptance probability function {{code|P()}}, and the annealing schedule {{code|temperature()}} AND initial temperature <init temp>. These choices can have a significant impact on the method's effectiveness. Unfortunately, there are no choices of these parameters that will be good for all problems, and there is no general way to find the best choices for a given problem. The following sections give some general guidelines. − − In order to apply the simulated annealing method to a specific problem, one must specify the following parameters: the state space, the energy (goal) function , the candidate generator procedure , the acceptance probability function , and the annealing schedule AND initial temperature <init temp>. These choices can have a significant impact on the method's effectiveness. Unfortunately, there are no choices of these parameters that will be good for all problems, and there is no general way to find the best choices for a given problem. The following sections give some general guidelines. − − − − − − + − Simulated annealing may be modeled as a random walk on a search graph, whose vertices are all possible states, and whose edges are the candidate moves. An essential requirement for the {{code|neighbour()}} function is that it must provide a sufficiently short path on this graph from the initial state to any state which may be the global optimum{{snd}} the diameter of the search graph must be small. In the traveling salesman example above, for instance, the search space for n = 20 cities has n! = 2,432,902,008,176,640,000 (2.4 quintillion) states; yet the number of neighbors of each vertex is <math>\sum_{k=1}^{n-1} k=\frac{n(n-1)}{2}=190</math> edges, and the diameter of the graph is <math>n-1</math>. − − Simulated annealing may be modeled as a random walk on a search graph, whose vertices are all possible states, and whose edges are the candidate moves. An essential requirement for the function is that it must provide a sufficiently short path on this graph from the initial state to any state which may be the global optimum the diameter of the search graph must be small. In the traveling salesman example above, for instance, the search space for n = 20 cities has n! = 2,432,902,008,176,640,000 (2.4 quintillion) states; yet the number of neighbors of each vertex is <math>\sum_{k=1}^{n-1} k=\frac{n(n-1)}{2}=190</math> edges, and the diameter of the graph is <math>n-1</math>. − − 模拟退火可以建立成一个搜索图上的随机游动模型，其顶点是所有可能的状态，其边是候选移动。对于函数的一个基本要求是模拟退火必须提供一条足够短的路径，从初始状态所到达的任何状态都可能是全局最优状态，搜索图的直径必须很小。例如，在上面的旅行推销员示例中，n = 20个城市的搜索空间有n!= 2,432,902,008,176,640,000 (2.4 quintillion)个州;然而，每个顶点的邻接数是<math>\sum_{k=1}^{n-1} k=\frac{n(n-1)}{2}=190</math>边，图的直径是<math>n-1</math>。
→参数选择
==参数选择==
==参数选择==
为了将模拟退火算法应用于具体问题，退火过程由冷却进度表 Cooling Schedule 控制，包括控制参数的初值<math>t</math>及其衰减因子<math>Δt</math>、每个<math>t</math>值时的迭代次数<math>L</math>和停止条件<math>S</math>。模拟退火算法必须指定以下参数:状态空间、能量(目标)函数、候选生成器过程、接受概率函数以及退火时刻表和初始温度。这些参数的选择能对模拟退火算法的有效性和准确性产生很大的影响。遗憾的是，并没有适用于所有问题的参数选择方法，也没有找到对于给定问题的最佳参数选择的通用方法。下面几节给出一些一般的指导原则。
为了将模拟退火算法应用于具体问题，退火过程由冷却进度表 Cooling Schedule 控制，包括控制参数的初值 t 及其衰减因子Δt 、每个 t 值时的迭代次数L和停止条件S。模拟退火算法必须指定以下参数:状态空间、能量(目标)函数、候选生成器过程、接受概率函数以及退火时刻表和初始温度<init temp>。这些参数的选择能对模拟退火算法的有效性和准确性产生很大的影响。遗憾的是，并没有适用于所有问题的参数选择方法，也没有找到对于给定问题的最佳参数选择的通用方法。下面几节给出一些一般的指导原则。
===充分相邻 Sufficiently near neighbour===
===充分相邻 Sufficiently near neighbour===
模拟退火可以建立成一个搜索图上的随机游动模型，其顶点是所有可能的状态，其边是候选移动。对于函数的一个基本要求是模拟退火必须提供一条足够短的路径，从初始状态所到达的任何状态都可能是全局最优状态，搜索图的直径必须很小。例如，在上面的旅行推销员示例中，<math>n=20</math>个城市的搜索空间有<math>n!= 2,432,902,008,176,640,000 (2.4 亿个州)</math>个州;然而，每个顶点的邻接数是<math>\sum_{k=1}^{n-1} k=\frac{n(n-1)}{2}=190</math>边，图的直径是<math>n-1</math>。