1、遗传算法的编码与适应度函数姓名：赵文娟学号： 30808120304遗传算法的特点：n （ 1）遗传算法不是直接作用在参变量集上，而是 利用参变量集的某种编码；n （ 2）遗传算法不是从单个点，而是从一个点的群体开始搜索；n （ 3） 遗传算法利用适应值信息 ，无需导数或其它辅助信息；n （ 4）遗传算法利用概率转移规则，而非确定性规则。遗传算法的编码和适应度函数的重要性n 遗传编码是整个遗传算法执行的基础n 遗传算法的适应度函数 (Fitness Function)的选取直接影响到遗传算法的收敛速度以及能否找到最优解 ,因为遗传算法在进化搜索中基本不利用外部信息 ,仅以适应度函数为依据 ,利
2、用种群每个个体的适应度来进行搜索。 遗传算法的基本定理n 模式 就是一个相同的构形，它描述的是一个串的子集，这个集合中的串之间在某些位上是相同的。 n 一个 模式 H的阶 就是出现在模式中确定位置的数目，记为 o（ H） 。n 一个 模式的定义长度 是模式中第一个确定位置和最后一个确定位置之间的距离，记为（ H)。模式的概念说明V+=0， 1， * 模式， *代表不确定字母 .串长为 L的二进制串上的模式共有 3l个 .一般的，对于 基数为 k的字母表，共有 (k+1)l个模式例如：串长为 7的模式 H=*11*0* ， A=0111000是模式 H的一个表示。 所有模式并不是以同等机会产生的
3、 ，有些模式比起其它的更加确定，例如：与 0*相比，模式 011*1*在相似性方面是更明确的表示。n 一个模式 H的阶 出现在模式中确定位置的数目 。例如：模式 011*1*的阶为 4可记为， o（ 011*1*） =4 ；模式 0*的阶为 1 。n 一个模式的定义长度 模式中第一个确定位置和最后一个确定位置之间的距离 。例如：模式 011*1*的定义长度为 4，可记为 =4； 0*的定义长度为 =0。注：串的阶和定义长度是用于讨论 串的相似性的符号 。 n 在复制阶段，每个串根据它的适应度值进行复制，更确切的说，一个串 Ai的复制概率为 ：n m（ H， t+1） = m（ H， t） nf
4、(H)/ 其中 f(H)是在第 t代中模式 H的串的平均适应值。n 整个群体的平均适应值可记为 /n故模式的复制生长方程可以表示为 :m（ H， t+1） = m（ H， t） / n 一个特定的模式按照其平均适应值与群体的平均适应值之间的比率生长 n 下面推出一个定量表达式，假设某一特定模式下的适应值高出群体平均适应值以上一个 c， c为一常数，则模式的复制生长方程可变为：n m（ H， t+1） = m（ H， t） =（ 1+c） m （ H， t）从 t=0开始，假设 c是一个固定值，可以推得：m（ H， t） = m（ H， 0） （ 1+c） t上式表明，在群体平均适应度以上（以下）的模式将会以指数增长（衰减）的方式被复制 。 模式定理n 模式的阶和定义长度两个概念提供了一个分析遗传算法中遗传算子对包含在群体中基因块的作用效果的基本的方法。n m=m（ H， t），第 t代中模式 H有 m个代表串包含在群体中 A（ t）中的样本。 t不同， m也不同。n 模式定理 ：遗传算法中，在选择、交叉、编译算子的作用下，具有低阶、短的定义长度，且平均适应度高于群体平均适应度的模式将按指数级增长。
