智能优化理论-第5章文化仿生智能算法

仿生智能算法REPORTING目录5.1Memetic算法5.2文化算法PART015.1Memetic算法REPORTINGWENKUDESIGN5.1.1Memetic算法的提出Memetic算法是由澳大利亚学者Moscato和Norman在1992年提出的一种仿生智能算法，结合了全局搜索和局部启发式搜索。早在1976年，英国生态学家Dawkins在学术著作TheSelfishGene中首次提出新概念“meme”。“meme”（模因）与“gene”（基因）相对应，是文化资讯传承的单位。1989年，Moscato在撰写的技术报告中首次提出了Memetic算法的概念，并把它作为一种基于群体优化的混合式搜索算法。1992年，Moscato和Norman确立了Memetic算法，并成功应用于求解TSP问题。目前Memetic算法已用于解决函数优化、组合优化、车间生产调度、物流与供应链、神经网络训练、模糊系统控制、图像处理等问题。遗传算法基于达尔文的自然选择、生物进化论而创立，主要应用于生物进化层次。拉马克挑战了达尔文的理论，认为生物体可以将其在生命过程中获得的知识和经验在进化中传递到后代。生物进化和社会发展具有某些共同特征，且相互补充。社会发展主要通过知识进行传递，而传递方式包括结构化的语言、思想和文化等。5.1.2Memetic算法的原理5.1.2Memetic算法的原理美国细胞生物学家威尔逊认为，基因进化主要发生在生物世界中，依赖于几个世代的基因频率的改变，因此是缓慢的；文化的发展以拉马克理论为特征，依赖于获得性状的传递，相对来说传递速度比较快。在Memetic算法中，类似于遗传算法中的基因库，也有一个供模因进行繁殖的模因库。模因库在复制过程中有的模因会比其他模因表现出更大的优势。Dawkins认为模因和基因常常相互加强，自然选择也有利于那些能够为其自身利益而利用其文化环境的模因。Dawkins的模因理论认为，模因与基因类似，它是一代接一代往下传递的文化单位，如语言、观念、信仰、行为方式等文化的传递过程中与基因在生物进化过程中起到类似的作用。模因在传播中往往会因个人的思想和理解而改变，因此父代传递给子代时信息可以改变，表现在算法上就有了局部搜索的过程。5.1.2Memetic算法的原理在模因的影响下，个体都具有自我学习的倾向，即个体进行自我调整，提高自身竞争力，并由此影响下一代新产生的个体。Memetic算法也可以看成遗传算法与局部搜索算法的结合，在遗传算法过程中，所有通过进化生成的新的个体在被放入种群之前均要执行局部搜索，以实现个体在局部领域内的学习。在Memetic算法中，基因对应着问题的解，而模因对应着解的局部搜索策略。因为模因的引入，代与代之间的个体竞争力在不断提高。5.1.2Memetic算法的原理进化阶段通过选择、交叉、变异3个遗传算子，在现有种群上产生新种群。选择根据适应度值函数评价每个染色体的质量，适应度值较好的个体以更大概率被选择进入下一操作。染色体编码及初始种群产生根据问题类型确定染色体编码方式，随机生成种群大小的染色体，生成初始种群。5.1.3Memetic算法的描述

5.1.3Memetic算法的描述交叉模仿生物体的繁殖过程，通过对完成选择操作后的种群中的个体进行两两交叉，将会生成同等数量的新的个体。单点交叉在个体编码串中随机设置一个交叉点，然后在该点相互交换两个配对个体的部分基因。多点交叉具体操作过程首先在相互配对的两个个体编码串中随机设置几个交叉点，然后交换每个交叉点之间的部分基因。03变异将个体编码串中的某些基因值用其他基因值来替换，从而形成一个新的个体。01均匀交叉两个配对个体的每一位基因都以相同的概率进行交换，从而形成两个新的个体。02算术交叉由两个个体的线性组合而产生出新的个体。5.1.3Memetic算法的描述Memetic算法的实现首先需要初始化种群，通过随机生成一组空间分布的染色体（解）作为初始解。通过迭代搜索最优解，在每一次迭代中，染色体通过交叉、变异和局部搜索进行更新。该算法与遗传算法有相似之处，但又不局限于简单遗传算法，它充分吸收了遗传算法和局部搜索算法的优点。它不仅具有很强的全局寻优能力，同时每次交叉和变异后均进行局部搜索，通过优化种群分布，及早剔除不良种群，进而减少迭代次数，加快算法的求解速度，保证了算法解的质量。在Memetic算法中，局部搜索策略非常关键，它直接影响到算法的效率。01020304055.1.4Memetic算法的流程5.1.5Memetic算法的特点及其意义01Memetic算法具有并行性，表现在内在并行性和内含并行性两方面。02内在并行性适合于大规模运算，让多台机器各自独立运行种群进化运算。内含并行性可以同时搜索种群的不同方向，提高了搜索最优解的概率。03适应度函数评估个体，不受约束条件限制，不需要目标函数导数，适合复杂优化问题。群体搜索策略扩大了解的搜索空间，提高算法的全局搜索能为与求解质量。局部搜索策略改善了种群结构，提高算法局部搜索能力。5.1.5Memetic算法的特点及其意义5.1.5Memetic算法的特点及其意义容错能力很强，初始种群可能包含与最优解相差很远的个体，但算法能通过遗传操作与局部搜索等策略过滤掉适应度很差的个体。Memetic算法提供了一种解决优化问题的新方法，对于不同领域的优化问题，可以通过改变交叉、变异和局部搜索策略来求解，扩大了算法的应用领域。PART025.2文化算法REPORTINGWENKUDESIGN文化算法是由美国学者Reynolds在1994年提出的，是一种通过文化系统演化模型求解进化计算问题的算法。文化算法被定义为“一个通过符号编码表示众多概念的系统，而这些概念是在群体内部及不同群体之间被广泛和相对长久传播的”。文化算法已用于解决约束单目标优化、多目标优化、作业调度、图像分割、语义网络、数据挖掘、航迹规划等问题。5.2.1文化算法的提出5.2.2文化算法的基本结构与原理信念空间和种群空间。文化算法是一种基于知识的双层进化系统，包含两个进化空间种群空间、信念空间和接口函数。接口函数包括接收、更新、影响函数。文化算法基本结构包括三大部分种群空间模拟个体根据一定行为准则进化，信念空间模拟文化形成、传递、比较和更新等进化过程。两个空间相互独立演化，定期贡献精英个体给上层空间，上层空间不断进化精英群体影响或控制下层空间群体。通过特定协议进行信息交流，形成“双演化、双促进”的进化机制。0102035.2.2文化算法的基本结构与原理信念空间将得到的个体经验按一定规则比较优化，形成群体经验，并根据新获取的个体经验通过更新函数更新现有的信念空间。信念空间用更新后的群体经验通过影响函数来修改种群空间中个体的行为规则，进而高效地指引种群空间的进化。文化算法的基本原理：通过性能函数评价种群空间的个体适应度，将种群空间个体在进化过程中所形成的个体经验传递给信念空间。5.2.2文化算法的基本结构与原理5.2.2文化算法的基本结构与原理选择函数从现有种群中选择一部分个体作为下一代个体的父辈，进行下一轮的迭代，直至满足终止条件。文化算法提供了一种多进化过程的计算模型，任何符合文化算法要求的进化算法都可以嵌入框架中作为种群空间的一个进化过程。5.2.3文化算法求解约束优化问题的描述写设计01文化算法的设计过程包括：种群空间和信念空间设计；接收函数、更新函数和影响函数设计。02文化算法中存在着多种类型的知识，即约束知识、规范知识、地形知识、环境知识等。03种群空间设计是指对个体进行编码，以浮点数编码为例，编码长度等于问题定义的解的变量个数。5.2.3文化算法求解约束优化问题的描述写设计每个基因等于解的每一维变量，若待求解问题中的一个有效解为D为解的变量维数，则即为解对应的编码。02约束知识用于表达和处理约束条件（边界），将搜索空间划分为可行域和非可行域，并划分为较小的子空间，称为“元”。03每个信念元都包含若干属性，如Classi表示约束性质，Cntli、Cnt2i是内置于信念元的计数器，分别表示该区域中可行和非可行候选解的个数。01d[]用来记录第i信念元在哪些维度上进行划分，生成子树。lNode[]、uNode[]均为1×n的向量，分别表示第i信念元各维度上的最小值和最大值。lNode[]与uNode[]结合起来，定义了信念元i的边界范围；Parenti表示信念树中该信念元的父节点：Childreni表示信念树中该信念元的子节点列表。Cntli与Cnt2i结合起来还可提供该区域内可行候选解与非可行候选解的相对比例；Deepi用来表示第i信念元所处的信念树（在“地形知识”部分介绍）的深度。5.2.3文化算法求解约束优化问题的描述写设计03算法初始化主要实现对种群空间和信念空间的初始化，并评估初始种群的适应度。01实现基本文化算法的程序流程包括参数初始化、算法初始化、搜索求解和输出结果四个步骤。02参数初始化是对手动输入的设置，包括输入种群舰模、种群最大