763
个编辑
更改
跳到导航
跳到搜索
第64行：
第64行： − + − − The following pseudocode presents the simulated annealing heuristic as described above. It starts from a state {{math|''s''<sub>0</sub>}} and continues until a maximum of {{math|''k''<sub>max</sub>}} steps have been taken. In the process, the call {{math|neighbour(''s'')}} should generate a randomly chosen neighbour of a given state {{mvar|s}}; the call {{math|random(0, 1)}} should pick and return a value in the range {{math|[0, 1]}}, [[Uniform distribution (continuous)|uniformly at random]]. The annealing schedule is defined by the call {{math|temperature(''r'')}}, which should yield the temperature to use, given the fraction {{mvar|r}} 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. − − − − <div style="margin-left: 35px; width: 600px"> − − 35px; width: 600px 第99行：
第89行： − − </div> − − / div
→伪代码Pseudocode
对于任何给定的有限问题，随着退火时间表的扩展，模拟退火算法终止于全局最优解的概率接近1。<ref>{{cite journal |doi=10.1109/34.295910 |title=Simulated annealing: A proof of convergence |year=1994 |last1=Granville |first1=V. |last2=Krivanek |first2=M. |last3=Rasson |first3=J.-P. |journal=IEEE Transactions on Pattern Analysis and Machine Intelligence |volume=16 |issue=6 |pages=652–656}}</ref> 然而，因为确保取得大概率成功所需的时间通常超过完全搜索[[解空间]]所需的时间，所以这一理论结果并不是特别有用。{{Citation needed|date=June 2011}}
对于任何给定的有限问题，随着退火时间表的扩展，模拟退火算法终止于全局最优解的概率接近1。<ref>{{cite journal |doi=10.1109/34.295910 |title=Simulated annealing: A proof of convergence |year=1994 |last1=Granville |first1=V. |last2=Krivanek |first2=M. |last3=Rasson |first3=J.-P. |journal=IEEE Transactions on Pattern Analysis and Machine Intelligence |volume=16 |issue=6 |pages=652–656}}</ref> 然而，因为确保取得大概率成功所需的时间通常超过完全搜索[[解空间]]所需的时间，所以这一理论结果并不是特别有用。{{Citation needed|date=June 2011}}
==伪代码Pseudocode==
==伪代码==
下面的伪代码展示了上面描述的模拟退火启发式代码。它从状态<math>s_{0}</math>开始，一直持续到已经采取了最多<math>k_{max}</math>个步骤。在这个过程中，调用<math>neighbour(s)</math>应该通过随机选择产生一个给定状态为<math>s</math>的邻居; 调用<math>random(0,1)</math>应该均匀且随机地选择并返回一个范围在<math>[0,1]</math>内的值。退火时间表由调用<math>temperature(r)</math>定义，给定到目前为止所花费的时间预算的分数<math>r</math>，调用该温度来产生要使用的温度。
下面的伪代码展示了上面描述的模拟退火启发式代码。它从状态<math>s_{0}</math>开始，一直持续到已经采取了最多<math>k_{max}</math>个步骤。在这个过程中，调用<math>neighbour(s)</math>应该通过随机选择产生一个给定状态为<math>s</math>的邻居; 调用<math>random(0,1)</math>应该均匀且随机地选择并返回一个范围在<math>[0,1]</math>内的值。退火时间表由调用<math>temperature(r)</math>定义，给定到目前为止所花费的时间预算的分数<math>r</math>，调用该温度来产生要使用的温度。
<div style="margin-left: 35px; width: 600px">
<div style="margin-left: 35px; width: 600px">
{{framebox|blue}}
{{framebox|blue}}
</div>
</div>
==参数选择==
==参数选择==