Simulated Annealing
22
其他的问题(2/4) 其他的问题(2/4)
价值函数(Cost Function) 价值函数(Cost Function) – Hard Constraints 在不违背合适解的条件下,所提出的强制规定. 在不违背合适解的条件下,所提出的强制规定. – Soft Constraints 无论这种解是否违背条件,都算是合适解. 无论这种解是否违背条件,都算是合适解. – HardConstraints会给一个很大的weight HardConstraints会给一个很大的weight – SoftConstraints则是情况给予不同的weight SoftConstraints则是情况给予不同的weight
Simulated Annealing
26
算法修正(1/2) 算法修正(1/2)
可接受的机率(Acceptance Probability) 可接受的机率(Acceptance Probability)
P(E) =1 (E / t)
– 少计算exponential会加快速度 少计算exponential会加快速度 – 建立一个可查询各种值的table 建立一个可查询各种值的table 冷却(Cooling) 冷却(Cooling) – 花一些时间找寻最佳温度(包括最终温度,温差)
19
机率函(3/3)
当 T越高或 f越小时,则 p(X ' ) 越大,相对的扰动解被接受成新解的机 越大, 率越高. 因此会随着迭代次的增加而逐渐下,所以较差的扰动解被接受成 因此 T 新解的机会也随着 T 的下而越越小. 所以当迭代到最后因为温度 T 已到达低点,这时系统只会接受较佳的 扰动解为新解. 而扰动解 f (X ' ) 若小于目前解 f (X )则一定接受为新解,但若是 f ( X ' ) > f ( X ) 则接受为新解的机率随着f 的变大而越小.