计算与人工智能通识 第7章 进化计算与群智能技术

遗传算法简介01遗传算法基本思想和组成要素02遗传算法实现与应用03群智能算法概述04本讲提纲粒子群算法及应用05第7章

进化计算与群智能算法遗传算法（GeneticAlgorithm,GA）是一种模拟生物进化论和遗传学机理的随机搜索技术，它依据“适者生存、优胜劣汰”的自然进化法则，致力于探寻全局最优解。7.1遗传算法简介20世纪60~70年代，美国密歇根大学的JohnHolland教授及其学生团队提出了编码、交叉、变异、选择以及适应度评价等核心机制，开创性地将这些自然科学的原理应用于计算机科学与优化问题的求解中，从而奠定了遗传算法的基础.20世纪80年代开始被学术界广泛接受及应用。JohnHolland教授达尔文进化论孟德尔遗传学说遗传算法的提出者及发展历程7.1遗传算法简介（1）物种的可变性：物种会随着时间的推移发生演化。（2）自然选择：生物在生存竞争中，适应环境的个体更有可能生存下来并繁衍后代，从而将其有利的遗传特征传递给下一代。（3）共同祖先：所有的生物都有一个或多个共同的祖先，并通过长时间的演化形成了现今多种多样的生物种类。达尔文进化论：物竞天择，适者生存遗传算法的生物学背景7.1遗传算法简介（1）分离定律：基因作为独立的单位会代代相传，细胞中的成对遗传单位分别来自于雌雄亲本；（2）独立分配定律：染色体上的等位基因能够独立地进行遗传。孟德尔遗传学说：物种的进化是由于基因的遗传和变异遗传算法的生物学背景7.1遗传算法简介优点

全局优化能力。处理数学描述复杂的问题。处理缺少数学模型的问题。抗噪声能力。支持并行和分布式处理。持续学习的适应性。

特殊定义。超参数优化。计算密集型操作。过早收敛风险。无绝对最优解。局限性7.1遗传算法简介适用场景问题具有复杂的数学表述：遗传算法的优势在于，它仅需依赖适应度函数的结果。因此，它适用于那些目标函数难以明确区分或根本无法区分的问题，以及参数众多或参数类型混合的问题。无需数学表述的问题：遗传算法并不要求问题必须有明确的数学描述。只要能够获得一个评分值，或者有方法比较两个解的优劣，遗传算法就能发挥作用。包含噪声环境的问题：遗传算法对于数据可能不一致的问题表现出很强的适应性，这类问题可能源于传感器输出的数据波动或人工评分的主观性。涉及环境变化的问题：遗传算法能够通过持续生成适应新环境的新一代种群，来有效应对环境的缓慢变化。7.1遗传算法简介遗传算法的基本思想遗传算法本质上是一种并行、高效、全局搜索的方法，它能在搜索过程中自动获取和积累有关搜索空间的知识，并自适应地控制搜索过程以求得最优解。在遗传算法的每一代中，模拟自然选择过程（适应度较高的个体具有更高的概率产生下一代），根据个体在问题域中的适应度值和从自然遗传学中借鉴来的再造方法（交叉和变异）进行个体选择，产生一个新的近似解。这个过程导致种群中个体的进化，得到的新个体比原个体更能适应环境，就像自然界中的改造一样。如此迭代，直至产生一个适应度最高的个体（最优解）。7.2基本思想和组成要素遗传算法的组成要素1.染色体和基因一个染色体代表了问题的一个候选解。借鉴生物学中的概念，一个染色体由多个基因构成。例如，使用一个二进制字符串表示问题的一个候选解（染色体），那么该二进制字符串中的每一位被称为一个基因，即一个解码单元。将问题的候选解表示为染色体的过程称为编码。7.2基本思想和组成要素7.2基本思想和组成要素遗传算法的组成要素2.种群待解决问题候选解的集合。因为种群中的每个个体由染色体表示，所以种群也可视为染色体的集合。3.适应度函数和适应度值适应度函数用于计算种群中每个个体（染色体）的适应度值。计算得到的适应度值越大，说明该染色体的质量越高（是一个更好的解），也就更有可能被用于繁殖后代。遗传算法的组成要素4.选择在种群中挑选用于繁殖下一代的所有染色体的过程。染色体的适应度值越高，被选中的几率越大。适应度值较低的染色体依然可被选择，但概率较低。5.交叉为了创造一对新个体，作为双亲的两个父代个体交换某些基因形成子代个体的过程，亦称为重组。交叉操作依概率进行，即：一对染色体是否进行交叉操作由预先定义的交叉概率决定。7.2基本思想和组成要素遗传算法的组成要素6.变异一个或多个染色体基因的随机更改，依概率进行，但变异的概率一般都较小。变异旨在周期性的随机更新种群，丰富染色体的多样性，使算法在解空间的未知区域进行搜索，避免陷入局部解。例如，染色体的第6个基因发生变异，如下图所示。7.2基本思想和组成要素遗传算法的基本流程7.3遗传算法的实现过程遗传算法的关键步骤解析1.编码遗传算法通过编码将问题的解空间映射到遗传算法的搜索空间，所以遗传算法中编码方式的选择对算法的性能和效率有着至关重要的影响。二进制编码实数编码排列编码7.3遗传算法的实现过程遗传算法的关键步骤解析（1）二进制编码遗传算法中最基本、最常用的编码方式。它将问题的解空间映射到一个由0和1组成的二进制字符串上，每个二进制位代表解的一个特征或决策变量的一部分。二进制编码一般用于将数值转为二进制串，用以求解问题。二进制编码具有编解码简单、交叉和变异操作易于实现的优点，但在表示高精度连续变量时可能存在精度损失的问题。7.3遗传算法的实现过程编码原理：要想实现每个数值都能分配一个独一无二的串，那么串所能表示的数值个数就要大于等于数值解的个数。一个长度为n的串，能表示2"个数。假设某一参数的区间范围是[a,b]，精度为E的条件下，二进制串的长度为n，三者关系需满足:

，其中

被称为编码精度δ例如:想达到1e-5的精度，对于区间为[0,10]，串的长度n应该满足计算得到n≥20。n=20时，串提供的精度约为0.00000954。变量X的某值xi的二进制编码yi的计算公式为：7.3遗传算法的实现过程二进制编码示例：假设有一个拥有两个决策变量的优化问题，每个变量的取值范围都在[0,1]之间，精度为0.1。根据精度计算可得，串长至少为4。因此，两个变量的取值可以分别编码为两个长度为4的二进制串，构成一个总长度为8的染色体。例如，X1=0.2、X2=0.8，根据编码计算公式可以近似编码为00111100（注意：在实际计算中这里可能产生精度损失）。X1

=((0.2-0)/15)2=(3)2=0011X2=((0.8-0)/15)2=(12)2=11007.3遗传算法的实现过程解码原理：将二进制串转换为原参数数值的过程称为解码。一般的，区间范围为[a,b]，串长为n，当前串对应的十进制值为T（例如二进制1011对应的十进制值为11），则该串对应的实值x为:解码示例：

7.3遗传算法的实现过程遗传算法的关键步骤解析（2）实数编码实数编码是指个体的每个基因值用某一范围内的一个实数来表示，编码长度等于决策变量的个数。这种编码方式直接反映了问题的解空间，避免了二进制编码中的精度损失问题，特别适用于连续变量的优化问题。示例：对于一个两变量的优化问题，其中每个变量的取值范围在[0,10]之间。我们可以直接使用实数来表示每个变量的值，例如X1=3.4、X2=8.7。这个候选解可以表示为一个长度为2的实数向量[3.4,8.7]。在实数编码下，交叉和变异操作需要采用特定的方法来实现，如算术交叉和多项式变异等。7.3遗传算法的实现过程遗传算法的关键步骤解析（3）排列编码排列编码是针对特定问题（如旅行商问题TSP）的一种编码方式。它将有限集合内的元素进行排列来表示问题的解。这种编码方式使得问题表示简洁且易于理解，特别适用于需要排序或排列的问题。在TSP问题中，假设有n个城市需要访问，则一个可能的解可以表示为一个长度为n的整数向量，其中每个整数代表一个城市的编号，且每个编号只出现一次。例如，[4,2,3,1,5]表示先访问城市4，然后访问城市2、3、1、5，最后回到起点城市4。7.3遗传算法的实现过程遗传算法的关键步骤解析2.种群初始化种群初始化指的是在选定编码方案后通过某种方式产生N个染色体，其中N称为种群规模。种群初始化方法的选择取决于具体问题的特点和需求。常用种群初始化方法有：随机初始化法(无先验知识)、均匀分布初始化法、聚类初始化法、问题特定初始化法（有先验知识）、进化初始化法等。7.3遗传算法的实现过程遗传算法的关键步骤解析3.选择（1）轮盘赌选择轮盘赌选择是一种基于适应度比例的选择方法，较为常用，其基本思想是各个个体被选中的概率与其适应度大小成正比。个体适应度值被选中概率

x1100.1

x2200.2

x3300.3

x4400.47.3遗传算法的实现过程遗传算法的关键步骤解析（1）轮盘赌选择为了在计算机上方便地实现轮盘赌选择，通常需要计算每个个体的累积概率。累积概率表示从第一个个体到当前个体为止，所有个体被选中概率之和。累积概率的计算公式为：q(x1)=0.1q(x2)=0.1+0.2=0.3q(x3)=0.1+0.2+0.3=0.6q(x4)=0.1+0.2+0.3+0.4=1.0假设生成的随机数为0.25，则因为0.1<0.25≤0.3，所以选择个体x27.3遗传算法的实现过程遗传算法的关键步骤解析（1）轮盘赌选择轮盘赌的选择过程如下：1）生成随机数：在[0,1]区间内生成一个均匀分布的随机数r。2）匹配随机数：将生成的随机数r与每个个体的累积概率进行比较，找到满足条件q(xk-1)<r≤q(xk)的个体xk,其中k为选中的个体索引。注意，这里q(x0)被定义为0，以便比较第一个个体。3）选择个体：根据上一步的结果，选择个体xk进入下一代种群。4）重复过程：如果需要选择多个个体，则重复步骤1至3，直到达到所需的个体数量。7.3遗传算法的实现过程遗传算法的关键步骤解析（2）基于排序的选择基于排序的选择策略是在轮盘赌选择的基础上改进而来。这种方法的核心思想是将种群中的个体按照适应度进行排序，然后根据排序结果为每个个体赋予一个排名值，根据排名值计算轮盘赌的概率。个体适应度值排名值被选中概率（轮盘赌）被选中概率（基于排序）

x11010.100.1

x21330.130.3

x31220.120.2

x47540.750.4假设我们有一个包含4个个体的种群，每个个体的适应度值分别为10,13,12,75。由于种群规模为4，则适应度最高的个体获得排名值4，以此类推。7.3遗传算法的实现过程遗传算法的关键步骤解析（2）基于排序的选择该方法适用于个体适应度比其他所有个体大得多的情况（如上表中x4）。依据排名值而非适应度值，可以消除适应度值带来的巨大差异，避免少数高适应度个体被过度重复选择，从而占据下一代的全部种群。同样，如果种群中多个个体的适应度值很相似（如上表中x1，x2，x3），该方法可将他们进行有效区分，为优秀个体带来优势。7.3遗传算法的实现过程遗传算法的关键步骤解析（3）锦标赛选择锦标赛选择是一种基于竞争的选择方法。在每次选择操作中，从种群中随机选择一定数量（如3个，称为锦标赛规模）的个体进行锦标赛，即比较它们的适应度值，选择适应度值最高的个体进入下一代种群。锦标赛选择在实际应用中经常被使用，因为它与遗传算法的适应度函数尺度无关，只关注个体之间的适应度值相对大小，而不是绝对大小。7.3遗传算法的实现过程遗传算法的关键步骤解析（4）精英保留选择精英保留选择是一种保证最优个体不被破坏的选择方法。在每次选择操作之前，首先找出当前种群中适应度最高的个体（或几个个体），然后将这些个体直接复制到下一代种群中。接下来，对剩余的个体执行其他选择操作（如轮盘赌选择、锦标赛选择等）。这种方法可以有效地保留种群中的优秀个体，防止算法在进化过程中丢失最优解。7.3遗传算法的实现过程4.交叉（1）单点交叉在个体的基因序列上随机选择一个交叉点，将两个个体的基因序列在交叉点处交换，生成两个新的子代个体。7.3遗传算法的实现过程（2）两点交叉和多点交叉两点交叉：在个体的基因序列上随机选择两个交叉点，将两个个体的基因序列在这两个交叉点之间的部分进行交换，生成两个新的子代个体。注意：两点交叉可以通过执行两次位置不同的单点交叉来实现，同理，多点交叉可以看作是两点交叉的拓展。7.3遗传算法的实现过程（3）均匀交叉对于每个基因位，以一定的概率（如0.5）选择从一个父代个体继承该基因位的值，从另一个父代个体继承该基因位的值，生成两个新的子代个体。注意：结果随机7.3遗传算法的实现过程（4）部分匹配交叉一种用于解决特定类型问题（如旅行商问题TSP）的交叉方法。它首先随机选择两个交叉点，然后建立一个映射关系来确保交叉后生成的子代个体中的基因不重复。

无效解（存在重复）7.3遗传算法的实现过程（4）部分匹配交叉此时就需要通过映射关系修复交叉后的子代个体，以确保每个城市只被访问一次。具体处理过程如下：1）根据交换的两组基因建立映射关系，示例中建立的映射关系为1↔6↔3↔4,2↔5。2）由于中间个体A’中存在重复基因1，按照映射关系将其中一个转变为4，重复该过程，直至不存在冲突位置。7.3遗传算法的实现过程5.变异（1）反转变异适用于二进制编码染色体。反转变异是指以某一较小的概率反转某些基因位的值。对于二进制编码的个体，反转变异就是将某些基因位上的基因值取反（0变1，1变0）。举例：假设有一个二进制编码的个体10110011，若第三个基因位发生变异，则变异后的个体为10010011。针对二进制编码和排列编码的变异策略7.3遗传算法的实现过程5.变异（2）交换变异适用于二进制编码染色体或排列编码染色体。随机选择两个基因位进行互换，如下图所示。（3）逆序变异适用于二进制编码染色体或排列编码染色体。在染色体中随机选择一个基因序列，然后将该基因序列逆置，如下图所示。针对二进制编码和排列编码的变异策略7.3遗传算法的实现过程5.变异（4）插入变异适用于二进制编码染色体或排列编码染色体。随机选择染色体（个体编码）上的一个基因（或基因片段），然后将其插入到染色体中的另一个随机位置，从而生成一个新的染色体（个体）。如下图所示。针对二进制编码和排列编码的变异策略7.3遗传算法的实现过程5.变异（1）均匀变异：取值范围内的一个随机数。（2）非均匀变异：随着迭代次数的增加，变异量逐渐减小。有助于在搜索初期进行全局搜索，而在搜索后期进行局部搜索。变异量大小与当前进化代数和基因原始值有关。（3）边界变异：它使得变异后的基因值更趋向于取值范围的边界。这种变异方式有助于探索解空间的边界区域，可能发现更优的解。（4）高斯变异：以高斯分布（正态分布）产生的随机数来替换原有基因值的一种变异方式。这种变异方式有助于在解空间中进行更加细致的搜索。针对实数编码的变异策略7.3遗传算法的实现过程6.遗传算法的结束条件（1）达到预设的最大迭代次数（2）当前最优解的适应度已经超过预设值或达到期望解决方案（3）前几代的最优解与当前的最优解之间的差别已经趋于稳定或缩小到一个较小的范围内（4）系统出现了无法解决的异常情况或技术问题7.3遗传算法的实现过程scikit-opt（简称sko）为用户提供了一个灵活的框架，以应用于各种优化问题。其中，GA类和GA_TSP类是特别用于解决优化问题的两个关键类，它们分别针对一般优化问题和旅行商问题（TSP）进行了专门的优化处理。通过灵活的配置和自定义选项，用户可以针对特定问题调整算法行为，以期获得更好的优化结果。7.4遗传算法的应用使用scikit-opt库求解函数极值Schaffer函数F2，是一种多维优化测试函数，由Dr.Schaffer于1984年提出。该函数表达式相对简单，但其优化过程却极具挑战性，常用于检验优化算法的局部搜索能力和全局搜索能力。函数公式如下所示：注意：案例代码实现基于sko库的GA模块，GA模块默认使用二进制编码，选择方法采用轮盘赌选择。7.4遗传算法的应用遗传算法的常用设置参数种群大小（PopulationSize）交叉率（CrossoverRate）变异率（MutationRate）选择方法（SelectionMethod）停止准则（TerminationCriterion）编码方式（Encoding）其他参数7.4遗传算法的应用群智能算法的概念群体智能（Swarmintelligence，SI）是分散的、自组织的自然或人工系统的集体行为。这个概念是由GerardoBeni和Wang于1989年在细胞机器人系统的背景下引入的。群智能算法模拟自然界中生物群体行为来解决复杂优化问题，自然界中的蚂蚁群落、鱼群、鸟群、陆地动物等群体由众多简单个体组成，群体中的个体通过与环境之间的相互作用和相互之间直接或间接的通信方式，实现复杂的寻路、觅食等群体行为。7.5群智能算法生物界的群体行为：蚁群寻路鸟群觅食鱼群觅食7.5群智能算法自1992年Dorigo受蚂蚁在寻找食物过程中发现路径的行为启发，提出了蚁群优化(AntColonyOptimization，ACO)理论，之后群体智能作为一个研究热点吸引了大量研究者。陆续提出了几十种群智能算法，一些典型的算法列举如下：蚁群优化算法（AntColonyOptimization，ACO，1992）粒子群优化算法（ParticleSwarmOptimization，PSO，1995）人工蜂群算法（ArtificialBeeColony，ABC，2007）布谷鸟搜索算法（CuckooSearch，CS，2009）萤火虫算法（FireflyAlgorithm，FA，2009）蝙蝠算法（BatAlgorithm，BA，2010）灰狼优化算法（GreyWolfOptimizer，GWO，2012）鲸鱼优化算法（WhaleOptimizationAlgorithm，WOA，2016）7.5群智能算法群智能算法的应用领域：优化问题（OptimizationProblems）群体智能算法广泛用于解决工程、物流、金融和电信等不同领域的优化问题。机器人与自动化（RoboticsandAutomation）群体智能技术越来越多地应用于机器人技术和自动化，协调自主代理和多机器人系统的行为。数据挖掘与机器学习（DataMiningandMachineLearning）群体智能算法用于数据挖掘和机器学习应用，用于特征选择、聚类、分类和异常检测任务。电信与网络（TelecommunicationsandNetworking）群体智能技术用于电信和网络优化资源分配路由和负载平衡任务，其它新兴应用（OtherEmergingApplications）群体智能越来越多地应用于农业科技、医疗保健、环境监测和智慧城市等新兴领域。7.5群智能算法蚁群算法简介：蚁群路径选择示意图，图中F表示食物源(Food)，N表示巢穴(Nest)7.5群智能算法蚂蚁出巢觅食时，寻路路径是随机的。蚂蚁在寻路过程中，会在沿途释放出一种叫做信息素（pheromone）的物质。经过该路径的其它蚂蚁能感知到释放的信息素，路径上的信息素浓度会随着时间的流逝而降低。不同路径中，长度较短的路径上单位时间内往返的蚂蚁数目更多，释放的信息素浓度也更高。其它蚂蚁出巢时会倾向于选择信息素浓度更高的路径。经过一段时间长度较短的路径上蚂蚁越来越多，信息素越来越浓，形成正反馈机制。另外一条长度较长的路径上信息素越来越淡，蚂蚁越来越少。蚁群算法简介：7.5群智能算法蚁群算法流程图7.5群智能算法蚁群算法的应用：蚁群算法可以有效地解决旅行商问题、图着色问题、网络路由问题、车辆路径问题、分配问题等全局寻优问题。这些问题在高维度空间求解时，使用遍历搜索方法需要耗费巨大的计算时间，传统的穷举算法难以甚至无法求解。旅行商问题图着色问题7.5群智能算法蚁群算法的应用：

7.5群智能算法粒子群算法的基本原理：

粒子群算法模拟鸟群觅食，初始时在搜索空间中随机生成一群粒子的位置参数，将位置参数代入需要求解的函数获取个体函数值，在这些函数值里找出群体最优解。每个粒子还有一个初始时随机生成的速度值决定它们下一步的方向和距离。每个粒子由当前速度、当前位置、个体历史最优位置和群体最优位置等数据以及更新公式来获取新的速度和位置，在新的位置中找出新的群体最优解，重复迭代执行上述步骤。图参考：Intuitionofparticleswarmoptimization()个体当前位置个体当前速度个体历史最优位置群体最优位置个体历史最优位置7.6粒子群算法及应用基本粒子群算法公式

KennedyEberhart1995年7.6粒子群算法及应用基本粒子群算法公式

7.6粒子群算法及应用

粒子群算法公式图解（2维函数求最小值）

7.6粒子群算法及应用

粒子群算法公式图解（2维函数求最小值）

7.6粒子群算法及应用标准粒子群算法公式

粒子群算法公式的改进7.6粒子群算法及应用

粒子群算法公式的改进7.6粒子群算法及应用粒子群算法各参数权重影响1. 粒子数量（Number of Particles）

粒子数量影响算法的搜索范围和搜索速度。一般来说，粒子数量越多，搜索范围越广，越能快速找到全局最优解，但同时也会增加算法的计算复杂度。2. 迭代次数（Number of Iterations）

迭代次数影响算法的搜索精度和计算时间。一般来说，迭代次数越多，算法收敛的可能性越大，但同时也会增加计算时间。在高维度空间中，落入局部最优解后，迭代次数的增加并不一定能够脱离局部最优解，因此增加迭代次数并不一定能够收敛得到全局最优解。7.6粒子群算法及应用粒子群算法各参数权重影响3. 惯性权重ω

速度的惯性权重ω作用是平衡粒子的历史速度和当前速度对位置更新的影响。较大的权重值能够增加粒子的探索能力，但可能导致粒子在搜索空间中震荡，增加收敛时间；较小的权重值能够增加粒子的局部搜索能力，加快收敛速度，但可能导致陷入局部最优解。