进化计算（一）

2024-07-15 15:50:02| 来源: 网络整理| 查看: 265

进化计算基本原理&遗传算法&GP 进化计算（EAs）DefinationClassificationKey Concept部分名词解释Parallel Search基本步骤可用EA解决的常见优化问题遗传算法（GA）名词解释(Biology)名词解释(Algorithm)CodeSelection（1）轮盘赌-Roulette Wheel Selection（2）Rank Selection-分级选择（3）Tournament Selection-联赛选择（4）Elitism-精英策略（5）子代选择的方法适应度函数fitness的选取遗传算法的一般步骤基本概念应用遗传编程-GPGA vs. GPFunctions & TerminalsGP for Regression 本文参考链接

进化计算（EAs） Defination

In computer science, evolutionary computation is a family of algorithms for global optimization inspired by biological evolution, and the subfield of artificial intelligence and soft computing studying these algorithms. In technical terms, they are a family of population-based trial and error problem solvers with a metaheuristic or stochastic optimization character.

Classification

进化计算包括遗传算法(Genetic Algorithms)、遗传规划（Genetic Programming）、进化策略(Evolution Strategies)和进化规划(Evolution Programming)4种典型方法。

Key Concept Population-Based Stochastic Optimization Methods（多点随机）Inherently Parallel （多点并行搜索，不容易陷入局部最优解）Metaheuristics（启发式）部分名词解释代数（generation）：种群进化的代数，即迭代的次数；群体的规模（popsize）：一般地，个体数量在整个进化过程中是不变的；当前解：新解的父解（parent，或称为父亲、父体等）；后代解（offspring，或称为儿子、后代等）：产生的新解；交叉重组：两父代个体随机匹配并将部分结构加以替换重组形成新个体。 Parallel Search

Local search and Divide-and-Conquer（N维问题转换为多个一维问题）都容易造成局部最优。因此，需要采用Parallel并行搜索的方式进行优化，即Population-Based。

基本步骤

进化计算的基本步骤包括基因编码（适于计算机处理）、选择（根据适应度函数）、复制（Elitism）、交叉重组（繁衍后代）和变异（提高随机性）。其中选择和交叉重组完成了大部分搜索功能，而变异则可以防止陷入局部最优解。基本步骤如下：在这里插入图片描述 Codeing：将实际问题转换为计算机可以执行的问题； Objective Function：待求解的目标函数 Domain Knoeledge：对自变量的约束 Evolutionary Search：评价（适应度函数）——选择——杂交（交叉重组）——突变（变异）

可用EA解决的常见优化问题

TSP：Travelling Salesman Problem。不一定能求出最优解，只能收敛于（近似逼近）最优解，得到一个次优解，因为他们本质都是随机算法，大多都会以类似“一定概率接受或舍去”的思路去筛选解。使用遗传算法求解旅行商问题 in Java； Knapsack Problem:背包问题。使用遗传算法求解背包问题 in Python； Bin Packing Problem等。

遗传算法（GA）名词解释(Biology) 基因：DNA片段Gene Trait:基因性状（基因控制的特性外在表现形式）Allele:某一性状的可能取值Genotype:具体基因型Phenotype:基因特性的外在表现（不同Genotype可能对应相同的Phenotype）名词解释(Algorithm) Individual：个体，表示目标函数特定解的一个向量（多变量）;Population：种群，a set of individual(Evolve based on population—>Global Optimization)；Offspring：后代，交叉重组产生的new individuals；encoding：编码方式，Binary vs.Gray。(Gray:任意两个相邻编码之间汉明距离均为1。实际应用中，每次仅变化1位，不存在多位变化的同步问题，相对stable) Code

遗传算法（GA）中的编码方式-二进制编码、格雷编码、实数编码。

Selection （1）轮盘赌-Roulette Wheel Selection

适应度高的在轮盘上所占面积大，即适应度越高被选中的概率越大。轮盘赌算法基本步骤：link。缺点：

适应度为负值无法表示概率。适应度的值不确定可能会导致资源过度集中。（某一个体适应度的值过高）（2）Rank Selection-分级选择

不直接使用原始适应度的值，而是对其进行排序（适应度越高，Rank等级越高）后利用排序值进行轮盘赌。采用该种方法就可以缩小差距，同时解决负数问题。

（3）Tournament Selection-联赛选择

N个Individuals为一组进行比较，胜者（适应度最大的）被选中。其中，Tournament Size即N对选择结果的影响较大。若N=2，则倒数第一个不会被选中；若N=3，则倒数第一和倒数第二个不可能被选中。

（4）Elitism-精英策略

由于进化的随机性，需要保证当前种群中的最优解不被交叉重组破坏或不被lost（若best solution被破坏，可能导致收敛不稳定）。因此，采用copy的方法，将当前generation的best solution复制到next generation。

（5）子代选择的方法子代完全替换父代子代与父代混合后再进行Selection

最终保证群体规模不变。

适应度函数fitness的选取

可以参考该篇博客，但需要注意举例3选取的适应度函数中max分母中f(x)前为‘-’，min分母中f(x)前为+。

遗传算法的一般步骤基本概念

重要词汇：Chromosome（Coding/Representation）、Crossover、Mutation、Selection

基本思想：

将每一个solution编码表示成一个chromosome；随机生成多个chromosome作为初始solution；经过适应度计算、选择、交叉重组、变异更新迭代。

基本步骤：首先实现从性状到基因的映射，即编码工作；然后从代表问题可能潜在解集的一个种群开始进行进化求解，即种群初始化工作；初代种群产生后，按照优胜劣汰的原则，根据个体适应度大小挑选个体（选择）；随后进行复制（精英策略）、交叉、变异（产生子代，防止陷入局部最优），产生出代表新的解集的群体。重新对其进行选择、复制、交叉、变异…如此往复，逐代演化产生出越来越好的近似解。

应用

示例1：遗传算法用于特征选择

特征选择基本原理

从初始特征中选择特征子集：降维或去除相关性期望达到的目标：降低训练难度；加快运行速度；高精确度；更好的理解力方法：Filter Method—不考虑具体使用的分类器的特性；Wrapper Method—将分类器的属性也考虑在特征选择当中（即分类器不同特征选择结果也不同）。

利用GA进行特征选择维度过高时可以先降维再GA，效果可能会更好。在这里插入图片描述