第5章人工代谢算法
　　人工代谢算法是一种基于酶催化模拟生物体新陈代谢机理的仿生算法。代谢反应的核心是浓度的平衡，在酶对底物的催化效率达到最大且代谢反应实现平衡时，代谢系统的性能指标处于最优状态。如果将待优化的目标函数看作代谢反应速率，酶的催化过程则可视为对目标函数的优化过程。当反应实现平衡时，代谢速率取得稳态最大值，即目标函数取得最大值。本章简要介绍人工代谢算法的原理、编码、竞争算子、平衡算子、凋亡算子等代谢算子的描述及算法实现流程。
　　5．1人工代谢算法的提出
　　人工代谢算法(Artificial Metabolic Algorithm, AMA)是2009年由胡杨和桂卫华以生物体新陈代谢机理为模型提出的一种基于酶催化的仿生算法［2124］。AMA面向的对象是一个网络化的控制系统，算法通过模拟生物体新陈代谢的环境，以代谢物浓度差及底物与酶的契合程度为控制量对系统变量进行调节。它的控制目的是使整个代谢网络的流量趋于平衡和协调，这与网络控制的目的恰好一致。因此，从定性的角度来说，人工代谢算法可以实现对复杂系统、多对象多目标系统较好的实时控制。起初，人工代谢算法用于解决多对象物流配送优化问题。后来，胡杨和桂卫华又将人工代谢算法用于解决TSP问题、多对象调度问题及故障诊断问题。
　　5．2人工代谢算法的原理
　　人工代谢系统是在分析生物体新陈代谢规律的基础上，通过对酶识别能力、酶催化下细胞各类递阶调控模式的分析和模型抽象而成的一类模拟人的代谢系统。从生物化学层次看,任何代谢系统网络都是由一些支路连接而成的。对单条代谢支路的代谢反应模式为
　　A+BxC+D(5．1)
　　其中,A、B为底物； C、D为生成物； x为催化酶。双向箭头表示该反应可以平衡移动,是可逆反应。
　　若底物浓度高于生成物浓度,此时酶起到正向催化作用,反应过程向合成生成物方向进行； 若生成物浓度高于底物浓度,此时酶表现为逆向催化作用,反应过程向合成底物方向进行。在此处,酶只起常规的催化作用。若遇特殊情况,即使底物浓度低于生成物浓度,也可以通过调节酶的浓度来改变反应过程的方向,迫使反应向合成生成物方向(正向催化方向)进行,以实现整个网络的代谢平衡。对可逆反应而言，通常提到的酶是指对正反应起加速作用的催化剂。而实际上，也存在促使化学平衡向逆反应方向进行起到抑制剂的作用。为了统一起见，对酶是正、逆反应催化剂的统称，其在算法中的作用通过平衡算子来统一表征。
　　由于酶对底物具有较强的选择契合性，对于不同的底物，需要不同的酶来与之发生催化作用。通过设计竞争算子来体现酶与底物催化时的专一性。同时，生物体细胞发育机制研究表明，染色体端粒(Tefomeres)的DNA序列都随着细胞分裂次数的增加而进行缩短。在真核生物染色体中具有特殊的结构端区，即端粒区。细胞每次分裂，都由一种特殊的酶即端粒酶(Tefomerase)负责将全部端粒重复序列加到子染色体上。但该酶总是只在配子细胞和癌细胞中存在。在一般的体细胞中，端粒酶数量下降，端粒变得越来越短。染色体丢失的不仅是非编码的重复序列，而且还危及基因编码。染色体一旦缩短到临界长度，细胞便会死亡。这就是多细胞生物衰老的端粒学说。据此，根据酶催化底物的专一性设计了凋亡算子，随着代谢网络中特定回路平衡的实现，对应催化该回路底物的酶开始凋亡。这一过程是为了降低计算成本，避免产生不必要的代谢计算。
　　人工代谢算法原理的核心是浓度平衡。当各条支路及整个代谢网络实现底物与反应物浓度达到协调平衡时,新陈代谢处于最旺盛阶段,对应的目标函数也将获得最优值。其中,当目标函数达到最优值时,对应的代谢浓度将达到稳态平衡,代谢过程的反应率也将达到稳态平衡,此时的代谢物数值对应目标函数的最优值。
　　5．3人工代谢算法的描述
　　1． 浓度平衡与代谢算子
　　在人工代谢系统中，底物、反应物的初始浓度由输入输出物理量决定。系统输入输出量关系决定代谢反应率的初始值。AMA算法将“浓度平衡”即“浓度差”作为适应度函数，根据代谢支路上的代谢物的多少决定对应催化酶的浓度。
　　通过平衡算子和抑制算子等代谢算子对代谢浓度进行调节，浓度差越大，则调节幅度也越大。经反复循环调节，浓度的变化率为0(即浓度差为0)，实现浓度平衡。此时系统已完全畅通，代谢量和代谢率也逐渐趋于稳定。此时从底物到生成物之间形成一条最优的代谢通路。代谢物数值达到最大，所对应的目标函数值最大而获得最优解。
　　凋亡算子适用于多酶调控的代谢体系，凋亡算子只取全0和全1两种情形。当酶所催化的代谢反应未达到平衡时，该酶的凋亡算子置全0，表示酶尚未退出代谢体系； 当酶所催化的代谢反应已达到平衡时，该酶的凋亡算子置全1，表示酶退出代谢体系，在余下的反应中不再考虑该酶的作用。
　　2． 人工代谢算法的编码
　　设有代谢反应方程为式(5．2)、式(5．3)，其中A和B为底物，P和Q为生成物，E为催化酶。在代谢规律中，酶E先与底物结合，生成中间复合物，再生成最终生成物。具体结合方式如式(5．3)所示。
　　A+BEP+Q(5．2)
　　A+B+E［AE］+B→E+P+Q(5．3)
　　其中，［AE］为中间复合物。酶E先与底物A结合产生中间复合物［AE］，再释放出生成物P、Q并还原生成催化酶E。
　　基于共价催化的原理，人工代谢算法的编码规则如下。
　　底物A和B的浓度区间为［0,1］，由底物A和B的量各占整个反应平衡方程中全部物理量的比例可计算出浓度。在人工代谢算法中，代谢物(包括底物和生成物)和酶的编码都用二进制位串表示。
　　假设采用n位二进制代码的编码方式，即将底物实际浓度和酶的浓度各映射成［0,2n－1］上的0、1组成的编码串。中间代谢物通过底物和酶对应位置上的0、1值经过“同或”逻辑的操作得到。例如，设底物A的编码为00101101，酶E的编码为10110001，则中间物［AE］的编码由A⊙E可得到，即为01100011。显然，当中间物［AE］的编码达到11111111时，代谢平衡予以实现。这样编码的优点在于充分体现底物与酶的契合程度，从直观意义上进一步加强了算法自身的生化背景和寻优意义。
　　3． 竞争算子的设计
　　通过对生物化学中相关知识的分析，可以发现酶的催化作用有很强的选择性。对于不同的底物有不同的选择性。设有两个不同的底物A1、A2，酶E对它们的契合程度很可能有较大的差距。通过引入竞争阈值h1来评价契合程度，设待优化函数y=f(x)，其中自变量x的二进制编码（即为底物A的编码），反过来底物A的二进制串解码成对应的十进制数（即为f函数的自变量x）。
　　设底物A1、A2分别对应的十进制数为x1、x2，当满足式(5．4)时，说明底物A1的代谢量大于底物A2的代谢量，且底物A1与酶的契合程度要大于底物A2与酶的契合程度，因此底物A1较之于A2是更为理想的代谢物，因此A1应保留进入下一轮的代谢选择； 当满足式(5．5)时，说明底物A2的代谢量大于底物A1的代谢量，且底物A2与酶的契合程度要大于底物A1与酶的契合程度，因此底物A2较之于A1是更为理想的代谢物，因此A2应保留进入下一轮的代谢选择。当式(5．4)、式(5．5)均不能满足时，说明A1、A2相互之间无明显的竞争优势，因此随机选择A1、A2中的任一个进入下一轮的代谢。
　　f(x1)－f(x2)f(x1)+f(x2)≥h1
　　f(x1)－f(x2)f(x1)+f(x2)≥0(5．4)
　　f(x1)－f(x2)f(x1)+f(x2)≥h1
　　f(x1)－f(x2)f(x1)+f(x2)≤0(5．5)
　　4． 凋亡算子的设计
　　设计凋亡算子的目的是淘汰与酶过分不相匹配的底物，而对应产生新的底物。其设计过程如下。
　　设立凋亡阈值h2，对任意底物A1，对于已给定的酶E而言，基于“同或”逻辑操作计算出其中间代谢物［A1E］，设中间代谢物［A1E］对应的十进制数为k1，各位全为1时的中间代谢物对应的十进制数为k2(显然，当编码位数为n时，k2=2n－1)。当满足式(5．6)时，说明底物A1与酶E匹配程度过低，底物A1应予以凋亡，而用新的底物A2来代替。
　　由于代谢操作希望中间代谢物的同或结果尽可能接近全为1，因此新底物A2的产生过程如下。
　　设代谢物采用n位编码，则底物A1与酶不契合的程度可定义为m位，m值可由式(5．7)得出，其中函数round()表示对自变量进行四舍五入取整运算。
　　k1k2≤h2(5．6)
　　m=roundk1k2×n(5．7)
　　得到m后，在组成A1的二进制串的n位编码中随机选择m位编码进行取反操作，得到的结果即为A2。显然，A2与E的契合程度要高于A1与E的契合程度。这时A2代替A1进入下一轮的代谢计算。当不能满足式(5．6)时，说明A1尚未达到凋亡的程度，则保留A1进入下一轮的代谢计算。
　　5． 平衡因子和拟制因子的设计
　　代谢反应的平衡是维系生命活动的关键。平衡算子的目的是当代谢平衡不能持续时，产生新的代谢物来尽可能保持代谢中间物的最大化。设有底物A、B和生成物C、D，在式(5．1)中作为可逆反应，酶可完成双向催化功能。故式(5．1)等价于式(5．8)中4个反应的合成。
　　A+BE［AE］+BC+D
　　A+BE［BE］+AC+D
　　C+DE［CE］+DA+B
　　C+DE［DE］+CA+B(5．8)
　　在式(5．8)中，酶是所有能催化代谢物的作用的统称。当反应实现平衡时，酶与各物质之间的总体协调功能达到最强。从式(5．8)可以看出，当酶E确定时，4个方程中只有3个是彼此独立的，故而可以由其中的任意3个代谢物推出第四个代谢物。如果设A、B、C的编码已知，则中间代谢物［AE］、［BE］、［CE］、［DE］的二进制编码可以由“同或”逻辑得到。例如，由A的二进制编码与E的二进制编码的“同或”可以得到［AE］的编码。
　　设P1=［AE］，P2=［BE］，P3=［CE］，当代谢实现平衡时，P1、P2、P3应尽可能达到全为1。设P=P1⊙P2⊙P3，显然，P也尽可能达到全为1。再令P4=［DE］，由代谢平衡条件，P与P4应尽可能接近。故可知当达到完全理想平衡状态时有P4=P成立。代谢物D的编码可用如下方法得到： 逐位对比P和E的二进制位串，设对第i位，P(i)=E(i)时，D(i)=1； P(i)≠E(i)时，D(i)=0； 这样做的意义在于使D与E的匹配程度与P的取值更为接近，从而实现平衡状态下新代谢物的产生和搜索。
　　人工代谢算法的平衡因子km0和拟制因子ki0的初值分别为式(5．9)、式(5．10)，平衡因子km(t)和拟制因子ki(t)的调节规律分别为式(5．11)、式(5．12)。
　　km0=f(A+B)f(A+B+C+D)(5．9)
　　ki0=f(C+D)f(A+B+C+D)(5．10)
　　km(t)=km0f(A+B+C+D)f(A+B)(5．11)
　　ki(t)=ki0f(A+B+C+D)f(C+D)(5．12)
　　v(t)=f(A+B)f(A+B+C+D)+f(C+D)f(A+B+C+D)(5．13)
　　式(5．9)~式(5．12)中，f(·)表示对应物质的量，如f(A+B)表示全部反应物的浓度之和。式（5.13）中，v（t）为系统反应速率。式(5．9)~式(5．13)中，A、B、C、D为不同的底物或生成物，是随时间变化的量。
　　在人工代谢算法中，由于在实际情况下代谢路径中的代谢物浓度不可能完全为0，因此引入数学上的某一极小值ε。当代谢物浓度小于ε时，认为对应的代谢反应已实现平衡，即为
　　v(t)t<ε(5．14)
　　其中，ε是不为0的某一极小值。ε可以按实际优化进程进行交互式定义。
　　平衡算子的作用是随机选择酶E中的二进制数位，使对应的数位上的数值与底物对应数位上的数值相等，即若底物某一数位上的数值为0，则平衡算子将酶E中与底物对应数位上的数值也转化为0； 若底物某一数位上的数值为1，则平衡算子将酶E中与底物对应数位上的数值也转化为1。
　　抑制算子的作用是随机选择酶E中的二进制数位，使对应的数位上的数值与底物对应数位上的数值不相等，即若底物某一数位上的数值为0，则抑制算子将酶E中与底物对应数位上的数值转化为1； 若底物某一数位上的数值为1，则抑制算子将酶E中与底物对应数位上的数值转化为0。这种编码的思想是使酶E与底物之间的作用关系更好地与真实的“共价催化”原理相一致，从而通过调整酶E的变化来调整化学平衡。
　　平衡算子和抑制算子的值均在［0,1］区间。平衡算子在一个计算周期中的值为当前全部底物的浓度； 抑制算子在一个计算周期中的值为全部生成物的浓度。在得到平衡算子和抑制算子的值后，决定所要变换的酶的二进制编码的位数。当代谢反应达到稳态，代谢物浓度变化率趋于不变或小于ε时，代谢反应速率已达到稳态最大值，代谢寻优终止。
　　……

前言

“智能”已经成为当代出现频次越来越高的词汇，这正是人类社会迈入智能时代的一个重要标志。智能正飞速地融入科学、工程、经济、国防及人类社会生活的方方面面： 智能科学、智能材料、智能机器人、智能生产线、智能控制、智能预测、智能决策、智能制导、智能炸弹、智能手机、智能家电、智能家居、智能楼宇……智能水平的高低，在很大程度上已经成为衡量一个国家综合国力、科技水平高低的重要标志。

在科学研究、工程设计、经济管理、国防建设等领域存在着大量需要优化求解的复杂问题。采用传统的优化方法通常需要给出待优化问题的精确数学模型，包括决策变量、约束条件和目标函数。传统优化方法包括线性规划、动态规划、整数规划和分支定界等运筹学中的经典算法，这些算法计算复杂，只适用于小规模问题； 用构造型优化算法快速建立问题的解，一般优化效果差，难以满足工程需要。总之，传统的优化算法是以给出优化问题的精确数学模型为基础的。然而，科学、工程、经济等领域提出的优化问题越来越复杂，难以建立精确的数学模型； 有的问题变量维数大，阶次高，目标函数多，约束条件复杂，即使建立复杂的数学模型也难以求解。因此，面临日益复杂的优化问题，基于精确模型的传统优化算法面临着极大的挑战。

大自然中的各种生物、植物、动物及各种自然现象呈现出生生不息的景象，总是给人以深刻的启迪。人们从中发现了许多隐含其中的信息存储、处理、交换、适应、更新、进化的机制，蕴含着优化的机理。于是，人们从中获得了设计灵感。例如，模拟蚁群从蚁穴到食物源避过障碍选择一条最短路径，Dorigo博士于1991年设计了蚁群优化算法，开辟了模拟群居昆虫觅食行为或动物捕猎行为的群智能优化算法的先河。除早期模拟大脑功能的模糊逻辑算法、神经网络算法及遗传算法外，近30年来，大量的智能优化算法在国内外犹如雨后春笋般地涌现出来。为了向广大读者全面而系统地介绍原创的智能优化算法，弥补国内外同类书籍的不足，本书精选了106种原创的智能优化算法，一般称它们为基本算法。本书把这些算法概括分为六大类，并分别编入六篇共106章加以介绍。各篇的内容概括如下。

第一篇： 仿人智能优化算法，包括模拟人脑思维、人体系统、组织、器官乃至细胞及人类社会竞争进化等相关的20种智能优化算法。

第二篇： 进化算法，包括模拟自然界的生物在生殖繁衍过程中，通过遗传和变异及“优胜劣汰”的自然选择法则，不断地进化的优化算法10种。

第三篇： 群智能优化算法，包括模拟自然界群居昆虫的觅食、繁殖等行为或动物群体的捕猎策略等对问题求解的优化算法34种。

第四篇： 仿植物生长算法，包括模拟花、草、树木等植物生长过程中的向光性、光合作用、根吸水性、种子繁殖、花朵授粉等表现出的自适应、竞争、进化、优化行为的算法10种。

第五篇： 仿自然优化算法，包括模拟风、雨、云等自然现象，模拟物理、化学、数学定律，模拟生态系统的自组织临界性、混沌现象、随机分形等非线性科学的优化算法27种。

第六篇： 涌现计算，指模拟自然界中复杂适应系统的涌现现象、涌现行为，通过人工生命的主体按简单规则在一定的环境下不断地演化来获得优化问题最优或准最优的模拟解。本篇介绍涌现计算的5种例子，包括一维元胞自动机的涌现计算、Conwey生命游戏的涌现计算、蚂蚁系统觅食路径的涌现计算、数字人工生命Autolife的涌现行为和黏菌的铁路网络涌现计算。

本书介绍的106种智能优化算法，涉及从地球上的万物之灵——智能水平最高的人，到介于动物和真菌之间的低级黏菌生物； 从海洋中世界上最大的哺乳动物鲸鱼到海洋微小无脊椎动物磷虾； 从凶猛的野生群居动物老虎、狮子到幼小的蚂蚁、蜜蜂； 从自然界的风、雨、云、雷电现象到地球上的水循环、食物链……内容涵盖面之广，可以说陆海空无所不及： 从陆地到海洋，从水中到空中，从有生命的动植物、微生物到无生命的自然现象，从物理化学数学、非线性科学到复杂适应系统等。

应该指出的是，有关智能优化算法的分类还没有统一的标准，因此从不同的角度会有不同的分类方法，如自然计算、仿生计算、进化计算、智能优化算法及计算智能等。本书之所以把上述前五大类优化算法统称为智能优化算法，是因为这些算法都凸显出智能性或灵性的特点。它们通过确定性算法加启发式随机搜索的反复迭代获取优化问题的最优数值解。而涌现计算是指模拟自然界中复杂适应系统的涌现现象、行为，通过人工生命的主体按简单规则在一定的环境下不断地演化来获得优化问题最优或准最优的模拟解。

本书介绍了百余种智能优化算法和涌现计算的原创算法，目的在于使广大读者开阔视野，从复杂适应系统理论的高度上认识、理解各种智能优化算法和涌现计算的原理及其本质特征，从中受到启迪； 并进一步激励人们从千变万化、五彩斑斓的大千世界中生生不息的各种生物、各种周而复始的自然现象中发现、捕捉灵感，提出、设计、创造出更多更好的智能优化算法，以满足科学、工程、经济、管理、国防等领域中各种复杂优化问题的需要。

基于上述宗旨，加之受篇幅所限，每种算法只从原创算法的提出、个体行为或习性、算法原理、算法的数学描述、算法实现等方面简要介绍，每种算法的篇幅平均控制在5页左右。在编写中，尽可能保持原创算法的主要内容及所用符号。为方便起见，对少数算法的符号做了适当的改动，并适当补充一些从网上收集的相关插图和对算法原理说明的辅助材料。由于本书章节多，因此将作为智能优化算法的理论基础部分的内容以附录的形式给出，便于读者单独阅读。

参加编写或提供素材的还有宁永臣、李盼池、李浩、左兴权、柏继云、张秀杰、宋申民、李巍、班晓军、赵宝江、黄金杰、袁丽英、栾秀春、黄忠报、章钱、郭成、杨丹、郭玉、张恒、张逸达、王振杨、徐宝华等。

在编写过程中除引用了原创算法的文献外，还参考了国内外相关研究的主要文献及有价值的博士、硕士学位论文等，为便于读者进一步研究查阅，将这些文献一并列入本书的参考文献。在此，对被引用文献的作者表示衷心感谢！除参考文献前面的部分书籍外，文献的编号原则上是按照各章内容出现的顺序编排的。

本书的出版始终得到清华大学出版社的大力支持，在此表示由衷的谢意！

本书内容涉及专业知识面甚广，受编者知识面所限，书中内容难免存在不足，恳请广大读者给予指正！

李士勇2018年5月