遗传算法基本原理.ppt

第四章 遗传算法的基本原理 4.1 遗传算法的基本描述 4.2 遗传算法的模式理论4.3 遗传算法与其他搜索算法的比较4.4 遗传算法的高级实现4.1.1标准遗传算法流程：1编码 2初始群体的生成 3适应度评估检测 4WHILEDO 1.选择 2.交叉 3.变异 4.适应度评估检测 5ENDDO4.1遗传算法的基本描述选择 交叉当前代 中间代 下一代4.1遗传算法的基本描述4.1.3遗传编码定 义：由问题空间向GA编码空间的映射称为编码，而由编码空间向问题空间的映射成为译码。问题编码一般应满足以下三个原则：1）完 备 性（completeness）：问题空间中的所有点都能能成为GA编码空间中的点的表现型2）健 全 性（soundness）：GA编码空间中的染色体位串必须对应问题空间中的某一潜在解。3）非 冗 余 性（non-redundancy）：染色体和潜在解必须一一对应。4.1遗传算法的基本描述4.1.3遗传编码根据模式定理，DeJong进一步提出了较为客观明确的编码评估准则，称之为编码原理。具体可以概括为两条规则：1）有意义积木块编码规则：编码应易于生成与所求问题相关的短距和低阶的积木块。2）最小字符集编码规则：编码应采用最小字符集，以使问题得到自然、简单的表示和描述。4.1遗传算法的基本描述1二进制编码1）连续实函数的二进制编码设一维连续实函数 采用长度维L的二进制字符串进行定长编码，建立位串空间：k=1,2,K;l=1,2,L;K=2L表示精度为。将个体又从位串空间转换到问题空间的译码函数的公式定义为：