人工智能-机器学习-遗传算法的评估汇报

人工智能-机器学习遗传算法的评估遗传算法（GeneticAlgorithms）是一种模拟生物界自然选择和遗传的启发式随机搜索算法。其基本步骤包括编码、初始群体的生成、适应度评估、选择、交叉操作和变异操作。GA是一种具有“生成+检测”的迭代过程的搜索算法。一、遗传算法的简介初始群体评估每个个体选择交叉结束是否优解？开始解编码评估函数遗传操作•遗传算法在进化搜索中基本上不用外部信息，仅用目标函数即适应度函数为依据。•适应度函数评估是选择操作的依据。•一般需将目标函数以一定的方式映射成适应度函数。新群体变异二、遗传算法的实现过程三、评估（Evaluation）EvaluationEvaluatedgenerationgeneration•GA基本上不用外部信息，仅用适应度函数来评估每个个体。•评估时需要解码（decoding），即把基因型（genotype）解转换为表示型（phenotype）解，以便利用评估函数或适应函数。X(=39)解（个体）在问题空间和遗传空间的转换，即phenotype解和genotype解之间的转换。四、Codinganddecodingcoding假如用遗传算子来区别十进制数6、7、8、9。整数表示出一个自然且平局的有序空间。因为在十进制中，下一个数只下在前一数上加1，然而用二进制编码则有明显不同：–0110011111001111–6789在6和7之间还有8和9之间只有一位发生变化，但在7和8之间四位全部不相同。coding这种不统一表现问题，在葛莱编码（graycoding）有较好的表现。Integer01234567binary000001010011100101110111Gray000001011010110111101100从上面可看到，相邻两个数之间只相差一位，用Gray代替标准的binary，这样可以使得相邻状态间的遗传算子的转换变得平滑。二值编码：问题空间的相邻解在编码空间并不相邻不利于解的搜索葛莱码：问题空间的相邻解在编码空间相邻有利于解的搜索codingGA算法分析－群体设定编码设计后的任务是初始群体的设定，其关键问题是群体规模。其中要考虑：▲初始群体如何设定？多大规模？▲进化过程中各代的群体规模如何维持？⒈初始群体的设定GA中初始群体中的个体是随机产生的，也可以根据先验知识设定初始群体⒉群体中个体的多样性模式定理告诉我们，若群体规模为M，GA可操作的模式数为M³,并在此基础上不断形成和优化积木块，直到最优解。显然，M越大，GA操作的模式越多，生成有意义的积木块的机会越高。换句话说，群体规模越大，群体中个体的多样性越高，陷入局部解的危险就越小群体规模太大的弊病计算效率由于个体被选择的概率大多采用适应度比例选择法，当规模太大时，大多数个体会被淘汰，仅少量的高适应度个体生存下来，影响配对和交叉繁殖。群体规模太小的弊病会使GA的搜索空间有限，引起未成熟收敛(prematureconvergence)结论：规模设定是一个tradeoff问题可以证明，在二进制编码的前提下，为满足隐并行性，群体的个数只要设定为即可。这个数目很大，一般设定为几十∽几百进化过程中，群体规模未必保持在相同规模，但一般情况下都保持不变22lGA算法分析－群体设定五、搜索的并行性爬山法：它保持多个候选解，删除没希望的，提高好的解决方法。上图，表明了多个候选解在搜索空间中朝最优点收敛。五、搜索的并行性图中，水平轴代表在解空间中的可能点，垂直轴反应这些解的质量。曲线上的点是遗传算法中当前群体中的候选解成员。开始时，候选解分散在可能解空间中，经过N代进化后，它们趋向于聚集在质量较高的区域。六、隐含的并行性一般地说，GA的计算能力主要来源于它的隐含并行性，即按照一些有效的原则，并行地把搜索尝试分配到搜索空间的许多领域的特性。GA的隐含并行性使GA使用相对少的串，就可以测试搜索空间里较大范围的区域。GA的这种隐含并行性，使其在复杂问题的优化求解等方面优于其它算法。GA基本上不用外部信息，仅用适应度函数作为依据GA的适应度函数不受连续可微的约束，且定义域可为任意集合，唯一要求是可计算出能加以比较的非负结果。此特点使GA应用范围很广。具有相同编码的解应有相同的适应度需要译码后再进行适应度评估七、GA算法评估－适应度函数设计⒈目标函数映射为适应度函数许多应用中，目标函数可直接作为适应度函数，但是，有些情况下需将目标函数作变换，以得到适应度函数。①最小化问题：将费用函数等最小化函数g(x)转化为适应度函数0xgCxfmaxmaxCxg可以是一个合适的值，也可采用迄今为止进化过程中g(x)的最大值或当前群体中g(x)的最大值maxC②最大化问题：将利润函数等最大化函数u(x)转化为适应度函数0minCxuxf0minCxu其他情况可以是合适的输入值，也可以是当前一代或前K代中u(x)的最小值minC⒉适应度函数标定(scaling)在应用GA尤其用GA处理小规模群体时常常会出现一些不利于优化的现象和结果：进化初期的未成熟收敛现象：基于比例选择策略，一些异常个体竞争力太强而处于主宰地位解决办法：降低异常个体的竞争力，即适应度进化后期的随机漫游现象：群体的平均适应度已接近最佳个体的适应度，此时，个体间竞争力减弱解决办法：提高个体间竞争力，即适应度七、GA算法评估－适应度函数设计①线性标定：设原适应度函数为f,标定后为f´:f´=af+b其中，a,b设定要满足：'maxavgmultfCfxfxfavgavg'和为了控制原适应度最大的个体可贡献子孙数。通常取0221..multC为了保证在以后的选择处理中平均每个个体可贡献一个期待的子孙到下一代七、GA算法评估－适应度函数设计'avgf2'avgf'minfminfavgfmaxfƒˊƒƒˊƒ'avgf2'avgfavgfmaxfminf'minfA正常线性定标B出现负适应度地线性定标一些坏个体适应度远小于群体平均适应度和最大适应度，且群体平均适应度又比较接近最大适应度时，为了拉开他们，使低适应度经定标后变成负值②σ截断(sigmatruncation)消除负适应度：σ是群体适应度的标准方差，每代要计算方差1c3③幂定标(powerlawscaling)较少使用，K与求解问题相关kiiff'cfffii'七、GA算法评估－适应度函数设计3.适应度函数与GA迭代停止条件当最优解的适应度值已知或准最优解的适应度下限可以确定时，可用作迭代停止条件否则，若发现群体中个体的进化已趋于稳定，即发现一定比例的个体具有完全相同的适应度，则停止迭代4.适应度函数与问题的约束条件GA仅靠适应度来评估和引导搜索，不能明确表示约束条件。对策：适应度函数考虑惩罚或代价约束优化问题非约束问题此类问题还可在编码和遗传操作设计方面采取一定措施七、GA算法评估－适应度函数设计