近似算法
一万年没更新博客了……毕竟我这么弱。 来玩一玩模拟退火算法和遗传算法。 我们的问题是，给定一个乱七八糟的函数，求它在某个区域内的最大值。 模拟退火算法 爬山 爬山算法是纯粹的贪心算法。给定一个起始点，我们能爬到一个极大值。 while ( 1 ) { if ( f ( x + 0.001 ) - f ( x - 0.001 ) > eps ) x += 0.001 ; //如果向右走有利，则向右走 else if ( f ( x + 0.001 ) - f ( x - 0.001 ) < - eps ) x += 0.001 ; //如果向左走有利，则向左走 else goto finish ; //已经爬到极大值 } 爬山的缺陷在于，它会陷入局部最优解，而难以爬到全局最优解。例如下图。 我们把上面的 x+0.001 之类的操作称作“移动”。 经典模拟退火 模拟退火的思想在于，如果一个移动会 使答案变得更优 ，我们就接受这个移动；否则我们以 一定的概率 接受这个移动。 听起来很玄学。根据物理的那套理论，我们定义两个东西： - 温度 ( T ) ( T ) 。它随着时间推移而逐渐降低。 - 增量 ( E ) ( E ) 。它描述一次移动获得的好处。从 x x 移动到 x ′ x ′ 的增量定义为 f ( x ′ ) − f ( x ) f ( x ′ ) − f ( x ) ，增量越大，往 x ′ x ′ 移动的优势越大。 在模拟退火中，如果增量大于 0 0 ，则直接接受这次移动；否则按下面的概率接受移动： P = exp ( E T ) P = exp ( E T ) 听起来十分的玄学。然而它竟然可以得出精度比较好的解。伪代码如下： T = 100.0 ; //初始温度 for ( int i = 0 ; i < 100 ; i ++ ) //控制迭代次数 { tar = getPos (); //在x的周围选一个点 E = f ( tar ) - f ...