1、实验十遗传算法与优化问题数学实验q 本实验主要介绍 遗传算法的基本理论，然后通过求解几个简单的函数最值问题，来说明如何利用遗传算法进行初步的优化计算 。问题背景和实验目的q 遗传算法（ Genetic Algorithm，简称 GA），是模拟达尔文的遗传选择和自然淘汰的生物进化过程的计算 机算法，它由美国 Holland 教授 1975年提出 。q 遗传算法作为一种新的全局优化搜索算法，以其简单通用、鲁棒性强、适合并行处理及应用范围广等显著特点，奠定了它作为 21世纪关键智能计算之一的地位 。q 基本思想 ：遗传算法基本原理u 基于模仿生物界遗传学的遗传过程，把问题的参数用基因来表示，把问题的
2、解用染色体来表示代表（在计算机里用二进制码表示），从而得到一个由具有不同染色体的个体组成的群体。u 这个群体在问题特定的环境里生存竞争，适者有最好的机会生存和产生后代，后代随机化地继承父代的最好特征，并也在生存环境的控制支配下继续这一过程。u 群体的染色体都将逐渐适应环境，不断进化，最后收敛到一族最适应环境的类似个体，即得到问题最优解。遗传学相关概念 遗传学遗传算法 数学1 个体 要处理的基本对象、结构也就是可行解2 群体 个体的集合 被选定的一组可行解3 染色体个体的表现形式 可行解的编码4 基因 染色体中的元素 编码中的元素5 基因位某一基因在染色体中的位置元素在编码中的位置6 适应值个体
3、对于环境的适应程度，或在环境压力下的生存能力可行解所对应的适应函数值7 种群 被选定的一组染色体或个体根据入选概率定出的一组可行解8 选择 从群体中选择优胜的个体，淘汰劣质个体的操作保留或复制适应值大的可行解，去掉小的可行解遗传学相关概念 遗传学 遗传算法 数学9 交叉 一组染色体上对应基因段的交换根据交叉原则产生的一组新解10 交叉概率染色体对应基因段交换的概率（可能性大小）闭区间 0,1上的一个值，一般为0.650.9011 变异 染色体水平上基因变化编码的某些元素被改变12 变异概率染色体上基因变化的概率（可能性大小）开区间 (0,1)内的一个值 , 一般为0.0010.0113 进化、
4、适者生存个体进行 优胜劣汰的进化，一代又一代地优化目标函数取到最大值， 最优的 可行解q 遗传算法计算优化的过程就如同生物学上生物遗传进化的过程，主要有三个基本操作（或算子）：遗传算法的步骤 l 选择（ Selection）l 交叉（ Crossover）l 变异（ Mutation）遗传算法的步骤 q 遗传算法基本步骤：u 把这些可行解置于问题的 “环境 ” 中，按适者生存的原则，选取较适应环境的 “染色体 ”进行复制，并通过交叉、变异过程产生更适应环境的新一代 “染色体 ” 群u 把问题的解表示成 “染色体 ”，在算法中就是以二进制编码的串，给出一群 “染色体 ”，也就是假设的可行解u 经
5、过这样的一代一代地进化，最后就会收敛到最适应环境的一个 “染色体 ” 上，它就是问题的最优解遗传算法有很多种具体的不同实现过程，这里仅介绍标准遗传算法的主要步骤。遗传算法具体步骤 选择编码策略，把参数集合（可行解集合）转换染色体结构空间； 定义适应函数，便于计算适应值； 确定遗传策略，包括选择群体大小，选择、交叉、变异方法以及确定交叉概率、变异概率等遗传参数； 随机产生初始化群体； 计算群体中的个体或染色体解码后的适应值； 按照遗传策略，运用选择、交叉和变异算子作用于群体，形成下一代群体； 判断群体性能是否满足某一指标，或者已完成预定的迭代次数，不满足则返回第五步，或者修改遗传策略再返回第六步
6、遗传算法具体步骤 产生初始群体是否满足终止条件得到结果 是结束程序否计算每个个体的适应值以概率选择遗传算子选择一个个体复制到新群体选择两个个体进行交叉插入到新群体选择一个个体进行变异插入到新群体得到新群体例 1. 设 f(x) = -x2 + 2x + 0.5，求 max f(x), x-1, 2。遗传算法的实际应用 我们将通过这个简单的求最值问题来详细给出遗传算法的整个过程。（ 1）编码和产生初始群体u 首先需要确定编码的策略，也就是说如何把 -1, 2 区间内的数用计算机语言表示出来。编码就是从表现型到基因型的映射，编码时要注意以下三个原则：n 完备性：问题空间中所有点（潜在解）都能成为 GA编码空间中的点（染色体位串）的表现型；n 健全性： GA编码空间中的染色体位串必须对应问题空间中的某一潜在解；n 非冗余性：染色体和潜在解必须一一对应
