31
个编辑
更改
跳到导航
跳到搜索
第19行：
第19行： − + 第27行：
第27行： − 是一种用于逼近给定函数全局最优值的概率模拟退火。具体来说，它是一个亚启发式近似全局优化在一个大的搜索空间为最佳化问题。当搜索空间是离散的(例如，旅行推销员问题)时，经常使用它。对于那些在一定时间内找到一个近似的全局最优解比找到一个精确的局部最优解更重要的问题，模拟退火可能比诸如梯度下降法之类的替代方法更可取。+ 第35行：
第35行： − 这个名字和灵感来自于冶金学中的退火，这种技术包括对材料进行加热和控制冷却，以增加其晶体的尺寸并减少其缺陷。两者都是材料的属性，取决于它的热力学自由能。加热和冷却材料都会影响温度和热力学自由能。+ 第41行：
第41行： − 模拟退火可以用来逼近具有多个变量的函数的全局最小值。1983年，这种方法被柯克帕特里克、小格拉特和维奇用来解决旅行推销员问题。他们还提出了它现在的名字---- 模拟退火。+ 第49行：
第49行： − 模拟退火算法中实现的缓慢冷却的概念被解释为在探索解决方案空间时接受较差解决方案的概率缓慢下降。接受较差的解是元启发法的一个基本属性，因为它允许对全局最优解进行更广泛的搜索。一般来说，模拟退火算法的工作原理如下。温度从最初的正值逐渐降低到零。该算法在每个时间步随机选择一个接近当前解的解，测量其质量，并根据温度相关的概率选择更好或更坏的解，在搜索过程中分别保持在1(或正)和向零递减。+ 第57行：
第57行： − 模拟可以通过求解密度函数的动力学方程或采用随机抽样方法进行。这种方法是对 Metropolis-Hastings 算法的一种改进，该算法是一种用来生成蒙特卡罗方法热力学系统状态样本的方法，由 n. Metropolis 等人发表。1953年。+ 第75行：
第75行： − + 第85行：
第85行： − 在每个步骤中，模拟退火启发式考虑当前状态的一些相邻状态 s * ，然后根据概率决定是将系统移动到状态 s * 还是保持在状态 s * 。 这些可能性最终导致系统进入低能状态。通常，这个步骤会重复进行，直到系统达到对应用程序足够好的状态，或者直到给定的计算预算用完。+ − 第95行：
第94行： − 解决方案的优化包括评估问题状态的邻居，这些邻居是通过保守地改变给定状态而产生的新状态。例如，在中东旅行推销员问题，每个州通常被定义为要参观的城市的排列，而其邻州则是通过颠倒任意两个连续城市的顺序而产生的排列组合。这种明确界定的改变各国以产生邻国的方式被称为“移动” ，不同的移动会产生不同的邻国集合。这些移动通常会导致最后一个状态的最小改变，以尝试通过迭代改进解决方案的各个部分(例如旅行推销员问题中的城市连接)来逐步改进解决方案。+ 第104行：
第103行： − 像爬山这样的简单的启发式方法，通过寻找更好的邻居来寻找更好的邻居，当他们达成一个没有更好的邻居的解决方案时就停止，不能保证会导致任何现有的更好的解决方案，他们的结果可能很容易地只是一个局部的最佳解决方案，而实际的最佳解决方案将是一个可能不。元启发法利用解的邻域作为探索解空间的方法，尽管它们更喜欢更好的邻域，但它们也接受更差的邻域以避免陷入局部最优; 如果运行足够长的时间，它们可以找到全局最优。+ 第226行：
第225行： − 冷却时间表对模拟退火性能的影响的例子。问题在于重新排列图像的像素点，使某个势能函数最小化，从而导致相似的颜色在短距离内相互吸引，在稍大的距离内相互排斥。Elementary 移动交换两个相邻的像素。这些图像获得了一个快速冷却时间表(左)和一个缓慢的冷却时间表(右) ，产生的结果分别类似于非晶和晶体固体。+ 第257行：
第256行： − +
无编辑摘要
Simulated Annealing can be used to solve combinatorial problems. Here it is applied to the [[travelling salesman problem to minimize the length of a route that connects all 125 points.]]
Simulated Annealing can be used to solve combinatorial problems. Here it is applied to the [[travelling salesman problem to minimize the length of a route that connects all 125 points.]]
模拟退火可以用来解决组合问题。这里我们将它应用到[[旅行推销员问题最小化连接所有125个点的路径长度]。]
模拟退火可以用来解决组合问题。这里我们将它应用到[[旅行商问题-最小化连接所有125个点的路径长度]。]
Simulated annealing (SA) is a probabilistic technique for approximating the global optimum of a given function. Specifically, it is a metaheuristic to approximate global optimization in a large search space for an optimization problem. It is often used when the search space is discrete (e.g., the traveling salesman problem). For problems where finding an approximate global optimum is more important than finding a precise local optimum in a fixed amount of time, simulated annealing may be preferable to alternatives such as gradient descent.
Simulated annealing (SA) is a probabilistic technique for approximating the global optimum of a given function. Specifically, it is a metaheuristic to approximate global optimization in a large search space for an optimization problem. It is often used when the search space is discrete (e.g., the traveling salesman problem). For problems where finding an approximate global optimum is more important than finding a precise local optimum in a fixed amount of time, simulated annealing may be preferable to alternatives such as gradient descent.
Simulated annealing (SA)模拟退火是一种用于逼近给定函数全局最优值的概率方法。具体来说，它是在大搜索空间中针对优化问题近似全局优化提出的一种元启发法。当搜索空间是离散的(例如，旅行商问题)时，经常使用它。对于那些在一定时间内找到一个近似的全局最优解比找到一个精确的局部最优解更重要的问题，模拟退火可能比诸如梯度下降等替代方法更可取。
The name and inspiration come from annealing in metallurgy, a technique involving heating and controlled cooling of a material to increase the size of its crystals and reduce their defects. Both are attributes of the material that depend on its thermodynamic free energy. Heating and cooling the material affects both the temperature and the thermodynamic free energy.
The name and inspiration come from annealing in metallurgy, a technique involving heating and controlled cooling of a material to increase the size of its crystals and reduce their defects. Both are attributes of the material that depend on its thermodynamic free energy. Heating and cooling the material affects both the temperature and the thermodynamic free energy.
这个名字和灵感来自于冶金学中的退火，这种技术涉及对材料进行加热和控制冷却以增加其晶体的尺寸并减少其缺陷。两者都是材料的属性，取决于它的热力学自由能。加热和冷却材料都会影响温度和热力学自由能。
Simulated annealing can be used to approximate the global minimum for a function with many variables. In 1983, this approach was used by Kirkpatrick, Gelatt Jr.,Vecchi, <ref name=":2" /> for a solution of the traveling salesman problem. They also proposed its current name, simulated annealing.
Simulated annealing can be used to approximate the global minimum for a function with many variables. In 1983, this approach was used by Kirkpatrick, Gelatt Jr.,Vecchi, <ref name=":2" /> for a solution of the traveling salesman problem. They also proposed its current name, simulated annealing.
Simulated annealing can be used to approximate the global minimum for a function with many variables. In 1983, this approach was used by Kirkpatrick, Gelatt Jr.,Vecchi, for a solution of the traveling salesman problem. They also proposed its current name, simulated annealing.
Simulated annealing can be used to approximate the global minimum for a function with many variables. In 1983, this approach was used by Kirkpatrick, Gelatt Jr.,Vecchi, for a solution of the traveling salesman problem. They also proposed its current name, simulated annealing.
模拟退火可以用来逼近具有多个变量的函数的全局最小值。1983年，这种方法被Kirkpatrick, Gelatt Jr.,Vecchi用来解决旅行商问题。他们还提出了它现在的名字---- 模拟退火。
This notion of slow cooling implemented in the simulated annealing algorithm is interpreted as a slow decrease in the probability of accepting worse solutions as the solution space is explored. Accepting worse solutions is a fundamental property of metaheuristics because it allows for a more extensive search for the global optimal solution. In general, simulated annealing algorithms work as follows. The temperature progressively decreases from an initial positive value to zero. At each time step, the algorithm randomly selects a solution close to the current one, measures its quality, and moves to it according to the temperature-dependent probabilities of selecting better or worse solutions, which during the search respectively remain at 1 (or positive) and decrease towards zero.
This notion of slow cooling implemented in the simulated annealing algorithm is interpreted as a slow decrease in the probability of accepting worse solutions as the solution space is explored. Accepting worse solutions is a fundamental property of metaheuristics because it allows for a more extensive search for the global optimal solution. In general, simulated annealing algorithms work as follows. The temperature progressively decreases from an initial positive value to zero. At each time step, the algorithm randomly selects a solution close to the current one, measures its quality, and moves to it according to the temperature-dependent probabilities of selecting better or worse solutions, which during the search respectively remain at 1 (or positive) and decrease towards zero.
模拟退火算法中实现的缓慢冷却的概念可被理解为探索解决方案空间时接受较差解决方案的概率缓慢下降。接受较差的解是元启发法的一个基本属性，因为它允许对全局最优解进行更广泛的搜索。一般来说，模拟退火算法的工作原理如下：温度从最初的正值逐渐降低到零。该算法在每个时间步长上随机选择一个接近当前解的解，测量其质量，并根据温度相关的概率选择更好或更坏的解，在搜索过程中分别保持在1(或正值)并向零递减。
The simulation can be performed either by a solution of kinetic equations for density functions or by using the stochastic sampling method. The method is an adaptation of the Metropolis–Hastings algorithm, a Monte Carlo method to generate sample states of a thermodynamic system, published by N. Metropolis et al. in 1953.
The simulation can be performed either by a solution of kinetic equations for density functions or by using the stochastic sampling method. The method is an adaptation of the Metropolis–Hastings algorithm, a Monte Carlo method to generate sample states of a thermodynamic system, published by N. Metropolis et al. in 1953.
可以通过求解密度函数的动力学方程或采用随机抽样方法进行模拟仿真。这种方法是对 Metropolis-Hastings 算法（一种用于生成热力学系统的样本状态的Monte Carlo方法）的一种改进，该算法在1953年由N. Metropolis等人提出。
hill climb algorithm, as there are many local maxima. By cooling the temperature slowly the global maximum is found.|500px]]
hill climb algorithm, as there are many local maxima. By cooling the temperature slowly the global maximum is found.|500px]]
模拟退火寻求最大值。这里的目的是达到最高点；但是由于存在许多局部最大值，仅使用简单的爬坡算法是不够的。通过缓慢冷却温度，可以找到全局最大值。 | 500px ]
模拟退火寻求最大值。这里的目的是达到最高点；但是由于存在许多局部最大值，仅使用简单的爬坡算法是不够的。通过缓慢冷却温度，可以找到全局最大值。
At each step, the simulated annealing heuristic considers some neighboring state s* of the current state s, and probabilistically decides between moving the system to state s* or staying in-state s. These probabilities ultimately lead the system to move to states of lower energy. Typically this step is repeated until the system reaches a state that is good enough for the application, or until a given computation budget has been exhausted.
At each step, the simulated annealing heuristic considers some neighboring state s* of the current state s, and probabilistically decides between moving the system to state s* or staying in-state s. These probabilities ultimately lead the system to move to states of lower energy. Typically this step is repeated until the system reaches a state that is good enough for the application, or until a given computation budget has been exhausted.
在每个步骤中，模拟退火这种启发式算法都会考虑当前状态s的某个相邻状态s *，并概率性地决定系统的下一个状态是移至状态s *还是保持状态s。这些概率最终会使系统进入能量较低的状态。通常来说需要重复执行迭代步骤，直到系统达到足以满足应用程序的能量状态或耗尽了给定的计算预算。
在每个步骤中，模拟退火这种启发式算法都会考虑当前状态s的某个相邻状态s^*，并概率性地决定系统的下一个状态是移至状态s^*还是保持状态s。这些概率最终会使系统进入能量较低的状态。通常来说需要重复执行迭代步骤，直到系统达到足以满足应用程序的能量状态或耗尽了给定的计算预算。
Optimization of a solution involves evaluating the neighbours of a state of the problem, which are new states produced through conservatively altering a given state. For example, in the travelling salesman problem each state is typically defined as a permutation of the cities to be visited, and its neighbours are the set of permutations produced by reversing the order of any two successive cities. The well-defined way in which the states are altered to produce neighbouring states is called a "move", and different moves give different sets of neighbouring states. These moves usually result in minimal alterations of the last state, in an attempt to progressively improve the solution through iteratively improving its parts (such as the city connections in the traveling salesman problem).
Optimization of a solution involves evaluating the neighbours of a state of the problem, which are new states produced through conservatively altering a given state. For example, in the travelling salesman problem each state is typically defined as a permutation of the cities to be visited, and its neighbours are the set of permutations produced by reversing the order of any two successive cities. The well-defined way in which the states are altered to produce neighbouring states is called a "move", and different moves give different sets of neighbouring states. These moves usually result in minimal alterations of the last state, in an attempt to progressively improve the solution through iteratively improving its parts (such as the city connections in the traveling salesman problem).
解决方案的优化包括评估问题状态的邻居，这些邻居是通过保守地改变给定状态而产生的新状态。例如在旅行商问题中，每个地点通常被定义为要访问的城市的排列，通过反转任意两个邻近城市顺序产生邻居的排列集合，不同的移动产生不同的近邻城市集。这种明确界定的改变各地以产生邻近城市集合的方式被称为“移动”。这些移动最后通常会让状态的更改迭代量降到最低，尝试通过迭代改善解决方案的组成部分（例如旅行商问题中的城市联系）来逐步改善解决方案。
解决方案的优化包括评估问题状态的邻居，这些邻居是通过保守地改变给定状态而产生的新状态。例如在旅行商问题中，每个地点通常被定义为要访问的城市的排列，通过反转任意两个邻近城市顺序产生邻居的排列集合，不同的移动产生不同的近邻城市集。这种明确界定的改变各地以产生邻近城市集合的方式被称为“移动”。这些移动最后通常会让状态的更改迭代量降到最低，尝试通过迭代改善解决方案的组成部分（例如旅行商问题中的城市联系）来逐步改善解决方案。
Simple heuristics like hill climbing, which move by finding better neighbour after better neighbour and stop when they have reached a solution which has no neighbours that are better solutions, cannot guarantee to lead to any of the existing better solutions their outcome may easily be just a local optimum, while the actual best solution would be a global optimum that could be different. Metaheuristics use the neighbours of a solution as a way to explore the solutions space, and although they prefer better neighbours, they also accept worse neighbours in order to avoid getting stuck in local optima; they can find the global optimum if run for a long enough amount of time.
Simple heuristics like hill climbing, which move by finding better neighbour after better neighbour and stop when they have reached a solution which has no neighbours that are better solutions, cannot guarantee to lead to any of the existing better solutions their outcome may easily be just a local optimum, while the actual best solution would be a global optimum that could be different. Metaheuristics use the neighbours of a solution as a way to explore the solutions space, and although they prefer better neighbours, they also accept worse neighbours in order to avoid getting stuck in local optima; they can find the global optimum if run for a long enough amount of time.
像爬山这样的简单的启发式方法通过逐步寻找更好的邻居移动，在没有更好邻居处停止，这种方法结果很容易是局部最优解，而实际最优解可能是有所不同的全局最优。元启发法为避免陷入局部最优，通过改变选择邻居的方法，即尽管他们更喜欢更好的邻居，但他们也接受更坏的邻居，把解的邻居用作探索解空间。如果运行足够长的时间，这种方法可以找到全局最优值。
像爬山这样的简单的启发式方法通过逐步寻找更好的邻居移动，在没有更好邻居处停止，这种方法结果很容易是局部最优解，而实际最优解可能是有所不同的全局最优。元启发法为避免陷入局部最优，通过改变选择邻居的方法，即尽管他们更喜欢更好的邻居，但他们也接受更坏的邻居，把解的邻居用作探索解空间。如果运行足够长的时间，这种方法可以找到全局最优值。
| footer= Example illustrating the effect of cooling schedule on the performance of simulated annealing. The problem is to rearrange the pixels of an image so as to minimize a certain potential energy function, which causes similar colours to attract at short range and repel at a slightly larger distance. The elementary moves swap two adjacent pixels. These images were obtained with a fast cooling schedule (left) and a slow cooling schedule (right), producing results similar to amorphous and crystalline solids, respectively.
| footer= Example illustrating the effect of cooling schedule on the performance of simulated annealing. The problem is to rearrange the pixels of an image so as to minimize a certain potential energy function, which causes similar colours to attract at short range and repel at a slightly larger distance. The elementary moves swap two adjacent pixels. These images were obtained with a fast cooling schedule (left) and a slow cooling schedule (right), producing results similar to amorphous and crystalline solids, respectively.
举例说明冷却时间表对模拟退火性能的影响。问题是重新排列图像的像素，使某个势能函数最小化，这会使相似的颜色在短距离内相互吸引并在稍大的距离处相互排斥。基本移动方式是交换两个相邻像素。这些图像是通过快速冷却过程（左）和缓慢冷却过程（右）获得的，分别产生类似于非晶态和结晶态固体。
举例说明冷却时间表对模拟退火性能的影响。问题是重新排列图像的像素，使某个势能函数最小化，这会使相似的颜色在短距离内相互吸引并在稍大的距离处相互排斥。基本移动方式是交换两个相邻像素。这些图像是通过快速冷却过程（左）和缓慢冷却过程（右）获得的，分别产生类似于非晶态和结晶态固体。
The following pseudocode presents the simulated annealing heuristic as described above. It starts from a state and continues until a maximum of steps have been taken. In the process, the call should generate a randomly chosen neighbour of a given state ; the call should pick and return a value in the range , uniformly at random. The annealing schedule is defined by the call , which should yield the temperature to use, given the fraction of the time budget that has been expended so far.
The following pseudocode presents the simulated annealing heuristic as described above. It starts from a state and continues until a maximum of steps have been taken. In the process, the call should generate a randomly chosen neighbour of a given state ; the call should pick and return a value in the range , uniformly at random. The annealing schedule is defined by the call , which should yield the temperature to use, given the fraction of the time budget that has been expended so far.
下面的伪代码展示了上面描述的模拟退火启发式代码。它从状态<math>''s''<sub>0</sub></math>开始，一直持续到已经采取了最多<math>''k''<sub>max</sub></math>个步骤。在这个过程中，调用<math>neighbour(''s'')</math>应该通过随机选择产生一个给定状态为<math>s</math>的邻居; 调用<math>random(0,1)</math>应该均匀且随机地选择并返回一个范围在<math>[0,1]</math>内的值。退火时间表由调用<math>temperature(''r'')</math>定义，给定到目前为止所花费的时间预算的分数<mvar>r<\mvar>，调用该温度来产生要使用的温度。
下面的伪代码展示了上面描述的模拟退火启发式代码。它从状态<math>''s''<sub>0</sub></math>开始，一直持续到已经采取了最多<math>k<sub>max</sub></math>个步骤。在这个过程中，调用<math>neighbour(s)</math>应该通过随机选择产生一个给定状态为<math>s</math>的邻居; 调用<math>random(0,1)</math>应该均匀且随机地选择并返回一个范围在<math>[0,1]</math>内的值。退火时间表由调用<math>temperature(r)</math>定义，给定到目前为止所花费的时间预算的分数<math>r<\math>，调用该温度来产生要使用的温度。