智能算法学习笔记.docx

智能算法浅介
By cooler
一个比方
在工程实践中，经常会接触到一些比较“新颖的算法”如模拟退火，遗传算法，禁忌搜索，神经网络等。这些由于有一些共同的特性（比如都是模拟了自然过程），通称为“智能算法”。它们在解决一些复杂的工epeat
select a new string vn in the neighborhood of vc; (1)
if f(vc)<f(vn)
then vc:=vn;
else if random [0,1] <exp ((f (vn)-f (vc))/T) (2)
then vc:=vn;
until (termination-condition) (3)
T:=g(T,t); (4)
T:=t+1;
until (stop-criterion) (5)
end;
上面的程序中，关键的是(1)新状态产生函数，(2)新状态接受函数，(3)抽样稳定准则，(4)退温函数，(5)退火结束准则 （简称三函数两准则）是直接影响优化结果的主要环节。虽然理论证明初始值对于最后的结果没有影响，但是初温越高，得到高质量解的概率越大。所以，应该尽量选取比较高的初温。
上面关键环节的选取策略：
（1）状态产生函数：候选解由当前解的邻域函数决定，可以取互换，插入，逆序等操作产生，然后根据概率分布方式选取新的解，概率可以取均匀分布，正态分布，高斯分布，柯西分布等。
（2）状态接受函数：这个环节最关键，但是，实验表明，何种接受函数对于最后结果影响不大，所以，一般选取min [1, exp ((f (vn)-f (vc))/T)]。
（3）抽样稳定准则：一般常用的有：检验目标函数的均值是否稳定；连续若干步的目标值变化较小；规定一定的步数；
（4）退温函数：非时齐SA算法中可以采用，但是温度下降很慢；快速SA中，一般采用。目前，经常用的是，是一个不断变化的值。
（5）退火结束准则：一般的有：设置终止温度；设置迭代次数；搜索到的最优值连续多次保持不变；检验系统熵是否稳定。
为了保证有比较优的解，算法往往采取慢降温，多抽样，终止温度设的低等方式，导致算法运行时间比较长，这也是模拟退火的最大缺点。人喝醉了酒办起事来都不利索，何况兔子？
遗传算法（Genetic Algorithm, GA）
“物竞天择，适者生存”，这就是进化论。自然界想做的事，就是遗传算法想做的事。如果把遗传算法用于优化问题，它完成的还不错，而如果把它看作对自然过程高度理想化的模拟，更能显出它本身的优雅——虽然生存竞争是残酷的。
遗传算法以一种群体中的所有个体为对象，并利用随机化技术指导对一个被编码的参数空间进行高效搜索。其中，选择、交叉和变异构成了遗传算法的遗传操作；参数编码、初始群体的设定、适应度函数的设计、遗传操作设计、控制参数设定五个要素组成了遗传算法的核心内容。 作为一种新的全局优化搜索算法，遗传算法以其简单通用、健壮性强、适于并行处