【最优化导论】模拟退火法
随机搜索求解问题为 https://www.zhihu.com/equation?tex=maximize%5C+f%28x%29%5C%5Csubject+%5C+to%5C+x%5Cin%5COmega
随机选择一个初始点 https://www.zhihu.com/equation?tex=x%5E%7B%280%29%7D ，作为下一个迭代点的备选，即对于任一点 https://www.zhihu.com/equation?tex=x%5Cin%5COmega ，存在一个集合 https://www.zhihu.com/equation?tex=N%28x%29%5Csubset+%5COmega 使得能够从该集合进行随机采样。
算法：
令，选定初始点 https://www.zhihu.com/equation?tex=x%5E%7B%280%29%7D%5Cin%5COmega 从中随机选定一个备选点如果 https://www.zhihu.com/equation?tex=f%28z%5E%7B%28k%29%7D%29%3Cf%28x%5E%7B%28k%29%7D%29 ，令,否则由如果满足停止规则，就停止迭代令回到第2步
模拟退火法
https://www.zhihu.com/equation?tex=N%28x%29 过小会导致朴素随机搜素算法可能会在局部极小点附近“卡住”，N(x)过大会导致搜索过程过慢。模拟退火算法对朴素随机算法进行修改，使其能够走出局部极小点的邻域，模拟退火的两次迭代中，算法产生的新点可能会比当前点要差。
算法：
令，选定初始点 https://www.zhihu.com/equation?tex=x%5E%7B%280%29%7D%5Cin+%5COmega 从随机选定一个备选点设计一枚特别的硬币，使其在一次抛投中出现正面的概率 https://www.zhihu.com/equation?tex=p%28k%2Cf%28z%5E%7B%28k%29%7D%29%2Cf%28x%5E%7B%28k%29%7D%29%29 ，跑一次硬币，如果出现正面，令，否则令如果满足停止规则，停止迭代令，回到第2步
维护一个最优解
https://www.zhihu.com/equation?tex=x_%7Bbest%7D%5E%7B%28k%29%7D%3D%5Cleft%5C%7B+%5Cbegin%7Barray%7D%7B%7D++x%5E%7B%28k%29%7D%2C%26++f%28x%5E%7B%28k%29%7D%3Cf%28x_%7Bbest%7D%5E%7B%28k-1%29%7D%29+%5C%5C+x_%7Bbest%7D%5E%7B%28k-1%29%7D%2C%26%E5%85%B6%E4%BB%96+%5Cend%7Barray%7D%5Cright.++
常用的概率 https://www.zhihu.com/equation?tex=p%28k%2Cf%28z%5E%7B%28k%29%7D%29%2Cf%28x%5E%7B%28k%29%7D%29%29%3Dmin%5C%7B1%2Cexp%28-%28f%28z%5E%7B%28k%29%7D%29-f%28x%5E%7B%28k%29%7D%29%29%2FT_k%29%5C%7D
构成一组正数序列，称为温度进度表
https://www.zhihu.com/equation?tex=f%28z%5E%7B%28k%29%7D%29 和https://www.zhihu.com/equation?tex=f%28x%5E%7B%28k%29%7D%29之间的差距越大，越小，采用作为下一迭代点的可能性越小。通常的做法是令温度单调递减到0（冷却过程）。一开始希望能在整个可行集内进行搜索，随着迭代开展，搜索范围应该集中到全局极小点附近区域，而不是遍历整个可行集。
一个合理的冷却进度表： https://www.zhihu.com/equation?tex=T_k%3D%5Cfrac%7B%5Cgamma%7D%7Blog%28k%2B2%29%7D
页:
[1]