文档介绍：会计学
1
几种智能算法的原理及应用介绍
主要内容：
1. 遗传算法
2. 蚁群算法
3. 模拟退火算法
4. 粒子群算法
5. 总结与体会
第1页/共77页
1. 遗传算法
遗传算法简介
遗传算法的基本思想
遗传算法的基本操作
遗传算法的构成要素
遗传算法的操作步骤
遗传算法的特点
遗传算法的应用领域
遗传算法的应用举例
第2页/共77页
遗传算法简介
遗传算法简称GA（Genetic Algorithms）是1962年由美国Michigan大学的Holland教授提出的模拟自然界遗传机制和生物进化论而成的一种并行随机搜索最优化方法。
遗传算法是以达尔文的自然选择学说为基础发展起来的。
自然选择学说包括以下三个方面：
（1）遗传：这是生物的普遍特征，亲代把生物信息交给子代，子代总是和亲代具有相同或相似的性状。生物有了这个特征，物种才能稳定存在。
（2）变异：亲代和子代之间以及子代的不同个体之间的差异，称为变异。变异是随机发生的，变异的选择和积累是生命多样性的根源。
（3）生存斗争和适者生存：具有适应性变异的个体被保留下来，不具有适应性变异的个体被淘汰，通过一代代的生存环境的选择作用，性状逐渐逐渐与祖先有所不同，演变为新的物种。
第3页/共77页
遗传算法的基本思想
遗传算法将“优胜劣汰，适者生存”的生物进化原理引入优化参数形成的编码串联群体中，按所选择的适应度函数并通过遗传中的复制、交叉及变异对个体进行筛选，使适适应度高的个体被保留下来，组成新的群体，新的群体既继承了上一代的信息，又优于上一代。这样周而复始，群体中个体适应度不断提高，直到满足一定的条件。遗传算法的算法简单，可并行处理，并能到全局最优解。
第4页/共77页
遗传算法的基本操作
遗传算法的基本操作主要有：复制、交叉、变异。
（1）复制（Reproduction Operator）
复制是从一个旧种群中选择生命力强的个体位串产生新种群的过程。具有高适应度的位串更有可能在下一代中产生一个或多个子孙。
复制操作可以通过随机方法来实现。首先产生0~1之间均匀分布的随机数，若某串的复制概率为40%，~，该串被复制，否则被淘汰。
第5页/共77页
遗传算法的基本操作
（2）交叉（Crossover Operator）
复制操作能从旧种群中选择出优秀者，但不能创造新的染色体。而交叉模拟了生物进化过程中的繁殖现象，通过两个染色体的交换组合，来产生新的优良品种。
交叉的过程为：在匹配池中任选两个染色体，随机选择一点或多点交换点位置；交换双亲染色体交换点右边的部分，即可得到两个新的染色体数字串。
交叉体现了自然界中信息交换的思想。交叉有一点交叉、多点交叉、还有一致交叉、顺序交叉和周期交叉。一点交叉是最基本的方法，应用较广。它是指染色体切断点有一处，例：
第6页/共77页
遗传算法的基本操作
（3）变异(Mutation Operator)
变异运算用来模拟生物在自然的遗传环境中由于各种偶然因素引起的基因突变，它以很小的概率随机地改变遗传基因（表示染色体的符号串的某一位）的值。在染色体以二进制编码的系统中，它随机地将染色体的某一个基因由1变为0，或由0变为1。
若只有选择和交叉，而没有变异，则无法在初始基因组合以外的空间进行搜索，使进化过程在早期就陷入局部解而进入终止过程，从而影响解的质量。为了在尽可能大的空间中获得质量较高的优化解，必须采用变异操作。变异操作如下所示：
第7页/共77页
遗传算法的构成要素
遗传算法的构成要素主要有：染色体编码方法、个体适应度评价、遗传算子及遗传算法的运行参数。
（1）染色体编码方法
基本遗传算法使用固定长度的二进制符号来表示群体中的个体，其等位基因是由二值符号集{0,1}所组成。初始个体基因值可用均匀分布的随机值生成，如：
就可表示一个个体，该个体的染色体长度是18。
第8页/共77页
遗传算法的构成要素
（2）个体适应度评价
基本遗传算法与个体适应度成正比的概率来决定当前群体中每个个体遗传到下一代群体中的概率多少。为正确计算这个概率，要求所有个体的适应度必须为正数或零。因此，必须先确定由目标函数值J到个体适应度f之间的转换规则。
（3）遗传算子
基本遗传算法使用下述三种遗传算子：
① 选择运算:使用比例选择算子；
② 交叉运算:使用单点交叉算子；
③ 变异运