第5章　人工代谢算法

5.1　人工代谢算法的提出

人工代谢算法（Artificial Metabolic Algorithm，AMA）是2009年由胡杨和桂卫华以生物体新陈代谢机理为模型提出的一种基于酶催化的仿生算法^[21-24]。AMA面向的对象是一个网络化的控制系统，算法通过模拟生物体新陈代谢的环境，以代谢物浓度差及底物与酶的契合程度为控制量对系统变量进行调节。它的控制目的是使整个代谢网络的流量趋于平衡和协调，这与网络控制的目的恰好一致。因此，从定性的角度来说，人工代谢算法可以实现对复杂系统、多对象多目标系统较好的实时控制。起初，人工代谢算法用于解决多对象物流配送优化问题。后来，胡杨和桂卫华又将人工代谢算法用于解决TSP问题、多对象调度问题及故障诊断问题。

5.2　人工代谢算法的原理

人工代谢系统是在分析生物体新陈代谢规律的基础上，通过对酶识别能力、酶催化下细胞各类递阶调控模式的分析和模型抽象而成的一类模拟人的代谢系统。从生物化学层次看，任何代谢系统网络都是由一些支路连接而成的。对单条代谢支路的代谢反应模式为

其中，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）所示。

其中，［AE］为中间复合物。酶E先与底物A结合产生中间复合物［AE］，再释放出生成物P、Q并还原生成催化酶E。

基于共价催化的原理，人工代谢算法的编码规则如下。

底物A和B的浓度区间为［0，1］，由底物A和B的量各占整个反应平衡方程中全部物理量的比例可计算出浓度。在人工代谢算法中，代谢物（包括底物和生成物）和酶的编码都用二进制位串表示。

假设采用n位二进制代码的编码方式，即将底物实际浓度和酶的浓度各映射成［0，2ⁿ-1］上的0、1组成的编码串。中间代谢物通过底物和酶对应位置上的0、1值经过“同或”逻辑的操作得到。例如，设底物A的编码为00101101，酶E的编码为10110001，则中间物［AE］的编码由A⊙E可得到，即为01100011。显然，当中间物［AE］的编码达到11111111时，代谢平衡予以实现。这样编码的优点在于充分体现底物与酶的契合程度，从直观意义上进一步加强了算法自身的生化背景和寻优意义。

3. 竞争算子的设计

通过对生物化学中相关知识的分析，可以发现酶的催化作用有很强的选择性。对于不同的底物有不同的选择性。设有两个不同的底物A₁、A₂，酶E对它们的契合程度很可能有较大的差距。通过引入竞争阈值h₁来评价契合程度，设待优化函数y=f（x），其中自变量x的二进制编码（即为底物A的编码），反过来底物A的二进制串解码成对应的十进制数（即为f函数的自变量x）。设底物A₁、A₂分别对应的十进制数为x₁、x₂，当满足式（5.4）时，说明底物A₁的代谢量大于底物A₂的代谢量，且底物A₁与酶的契合程度要大于底物A₂与酶的契合程度，因此底物A₁较之于A₂是更为理想的代谢物，因此A₁应保留进入下一轮的代谢选择；当满足式（5.5）时，说明底物A₂的代谢量大于底物A₁的代谢量，且底物A₂与酶的契合程度要大于底物A₁与酶的契合程度，因此底物A₂较之于A₁是更为理想的代谢物，因此A₂应保留进入下一轮的代谢选择。当式（5.4）、式（5.5）均不能满足时，说明A₁、A₂相互之间无明显的竞争优势，因此随机选择A₁、A₂中的任一个进入下一轮的代谢。

4. 凋亡算子的设计

设计凋亡算子的目的是淘汰与酶过分不相匹配的底物，而对应产生新的底物。其设计过程如下。

设立凋亡阈值h₂，对任意底物A₁，对于已给定的酶E而言，基于“同或”逻辑操作计算出其中间代谢物［A₁E］，设中间代谢物［A₁E］对应的十进制数为k₁，各位全为1时的中间代谢物对应的十进制数为k₂（显然，当编码位数为n时，k₂=2ⁿ-1）。当满足式（5.6）时，说明底物A₁与酶E匹配程度过低，底物A₁应予以凋亡，而用新的底物A₂来代替。

由于代谢操作希望中间代谢物的同或结果尽可能接近全为1，因此新底物A₂的产生过程如下。

设代谢物采用n位编码，则底物A₁与酶不契合的程度可定义为m位，m值可由式（5.7）得出，其中函数round（）表示对自变量进行四舍五入取整运算。

得到m后，在组成A₁的二进制串的n位编码中随机选择m位编码进行取反操作，得到的结果即为A₂。显然，A₂与E的契合程度要高于A₁与E的契合程度。这时A₂代替A₁进入下一轮的代谢计算。当不能满足式（5.6）时，说明A₁尚未达到凋亡的程度，则保留A₁进入下一轮的代谢计算。

5. 平衡因子和拟制因子的设计

代谢反应的平衡是维系生命活动的关键。平衡算子的目的是当代谢平衡不能持续时，产生新的代谢物来尽可能保持代谢中间物的最大化。设有底物A、B和生成物C、D，在式（5.1）中作为可逆反应，酶可完成双向催化功能。故式（5.1）等价于式（5.8）中4个反应的合成。

在式（5.8）中，酶是所有能催化代谢物的作用的统称。当反应实现平衡时，酶与各物质之间的总体协调功能达到最强。从式（5.8）可以看出，当酶E确定时，4个方程中只有3个是彼此独立的，故而可以由其中的任意3个代谢物推出第四个代谢物。如果设A、B、C的编码已知，则中间代谢物［AE］、［BE］、［CE］、［DE］的二进制编码可以由“同或”逻辑得到。例如，由A的二进制编码与E的二进制编码的“同或”可以得到［AE］的编码。

设P₁=［AE］，P₂=［BE］，P₃=［CE］，当代谢实现平衡时，P₁、P₂、P₃应尽可能达到全为1。设P=P₁⊙P₂⊙P₃，显然，P也尽可能达到全为1。再令P₄=［DE］，由代谢平衡条件，P与P₄应尽可能接近。故可知当达到完全理想平衡状态时有P₄=P成立。代谢物D的编码可用如下方法得到：逐位对比P和E的二进制位串，设对第i位，P（i）=E（i）时，D（i）=1；P（i）≠E（i）时，D（i）=0；这样做的意义在于使D与E的匹配程度与P的取值更为接近，从而实现平衡状态下新代谢物的产生和搜索。

人工代谢算法的平衡因子k_m0和拟制因子k_i0的初值分别为式（5.9）、式（5.10），平衡因子k_m（t）和拟制因子k_i（t）的调节规律分别为式（5.11）、式（5.12）。

式（5.9）～式（5.12）中，f（·）表示对应物质的量，如f（A+B）表示全部反应物的浓度之和。式（5.13）中，v（t）为系统反应速率。式（5.9）～式（5.13）中，A、B、C、D为不同的底物或生成物，是随时间变化的量。

在人工代谢算法中，由于在实际情况下代谢路径中的代谢物浓度不可能完全为0，因此引入数学上的某一极小值ε。当代谢物浓度小于ε时，认为对应的代谢反应已实现平衡，即为

其中，ε是不为0的某一极小值。ε可以按实际优化进程进行交互式定义。

平衡算子的作用是随机选择酶E中的二进制数位，使对应的数位上的数值与底物对应数位上的数值相等，即若底物某一数位上的数值为0，则平衡算子将酶E中与底物对应数位上的数值也转化为0；若底物某一数位上的数值为1，则平衡算子将酶E中与底物对应数位上的数值也转化为1。

抑制算子的作用是随机选择酶E中的二进制数位，使对应的数位上的数值与底物对应数位上的数值不相等，即若底物某一数位上的数值为0，则抑制算子将酶E中与底物对应数位上的数值转化为1；若底物某一数位上的数值为1，则抑制算子将酶E中与底物对应数位上的数值转化为0。这种编码的思想是使酶E与底物之间的作用关系更好地与真实的“共价催化”原理相一致，从而通过调整酶E的变化来调整化学平衡。

平衡算子和抑制算子的值均在［0，1］区间。平衡算子在一个计算周期中的值为当前全部底物的浓度；抑制算子在一个计算周期中的值为全部生成物的浓度。在得到平衡算子和抑制算子的值后，决定所要变换的酶的二进制编码的位数。当代谢反应达到稳态，代谢物浓度变化率趋于不变或小于ε时，代谢反应速率已达到稳态最大值，代谢寻优终止。

5.4　人工代谢算法的实现流程

人工代谢算法的实现流程如图5.1所示。首先，设定基本的代谢参数，包括底物点数目m；酶的取值e；代谢计算迭代次数G；代谢点编码位数n；竞争阈值h₁；凋亡阈值h₂。其次，通过对实际问题的编码，将待优化问题的自变量空间用底物的取值来表示。采用竞争、凋亡、平衡等酶的3种代谢算子计算方式来选取新的底物。根据酶与底物契合程度的高低来筛选出一批更为合适的底物进入下一轮的代谢选择。上述过程反复进行，最后通过判断是否达到代谢计算的迭代次数或判断酶与底物契合的稳固程度来决定代谢计算是否可以完成。在完成代谢计算后，通过对反复“发酵”后得到最优底物进行解码可以得到实际问题的最优解。