0 引言

饲料配方优化是饲料生产企业关注的核心问题，其任务是要以满足各类营养指标、适口性,以及原料配合工艺等诸多约束为前提，尽可能降低饲料的成本。饲料配方的优化设计过程一般可被描述为一个形如式(1) ~(3) 的线性规划(linear Programming,LP)模型^[1-3]。其中，m为配合饲料所要的原料种类数，c_i(i=1,2,…,m)表示各原料成本，X= [x₁ x₂ … x_m] (0%≤x_i≤100%)表示各原料所占配比；该型饲料须满足n种营养指标，b_j表示该型饲料以解向量X进行配比时能够提供第j种营养的实际值，upperB_j和lowerB_j分别表示第j种营养指标需要满足的上、下边界值；premix表示预混料在配合饲料中所占的比例。式(2) 中出现的b_i可依据式(3) 进行计算。

$\mathbf{To}\text{ }\mathbf{minimize}cost=\text{ }\left[ {{c}_{1}}{{c}_{2}}\ldots {{c}_{m}} \right]\times {{\left[ {{x}_{1}}{{x}_{2}}\ldots {{x}_{m}} \right]}^{T}}$

(1)

$\left\{ {\matrix{ {lower{B_j} \le {b_j} \le upper{B_j}{\rm{ }}(j = 1,2,...,n)} \cr {premix + \sum\limits_{i = 1}^m {{x_i} = 100\% } } \cr {0\% \le {x_i} \le 100\% {\rm{ }}(i = 1,2,...,m)} \cr } } \right.$

(2)

$\left[ \begin{matrix} {{b}_{1}} \\ {{b}_{2}} \\ \vdots \\ {{b}_{n}} \\ \end{matrix} \right]=\left[ \begin{matrix} {{a}_{11}}&{{a}_{12}}&\cdots &{{a}_{1m}} \\ {{a}_{21}}&{{a}_{22}}&\cdots &{{a}_{2m}} \\ \vdots &\vdots &\vdots &\vdots \\ {{a}_{n1}}&{{a}_{n2}}&\cdots &{{a}_{nm}} \\ \end{matrix} \right]\times \left[ \begin{matrix} {{x}_{1}} \\ {{x}_{2}} \\ \vdots \\ {{x}_{m}} \\ \end{matrix} \right]$

(3)

其中a_ij表示原料j中第i种营养的含量。

但是，实际工业生产中的饲料配方优化模型往往更为复杂。举例说来，一些实际的计算案例为了更为有效地调整与指定配方，不仅要求饲料吨成本最小化，还要求精饲料消耗量最小化，优化问题则成为一个复杂的多目标优化问题；还有一些计算案例，由于对配料养分的变异性加以考虑^[4]或对配合饲料的工艺条件进行限制^[5]而引入了约束，优化模型的解空间可能变得病态化(ill-condition)。对于这些实际生产中遇到的复杂饲料配方优化问题，研究者逐步将求解思路转向智能优化算法。其原因在于：智能算法在问题的解空间中以“生成+检测”的方式对最优解进行搜索，只要对问题的潜在解能够正确编码并以合理的目标函数对潜在解的优劣进行评价，算法不受问题性质的局限，对于各类饲料配方优化模型具有广泛的适用性。截止目前，一些解决饲料配方优化问题的智能算法相继被提出，诸如：遗传算法^[6-7]、模拟退火算法^[8]等。当然，这些智能优化算法对于较复杂的饲料配方优化问题尚存在早熟收敛的风险，因此，寻求更优秀的饲料配方优化方法仍然是饲料生产企业的内在需求。

人工鱼群算法(Artificial Fish School Algorithm,AFSA) 作为智能算法的一个新分支^[9]，具有良好的自组织与自适应性，全局优化能力强，收敛速度快，用法灵活，已被成功应用于诸多工程领域^[10-13]。尤其在求解石油运输系统多级站定位优化^[10]、网络路由优化^[11]等具有NP-C(Non-deterministic Polynomial-Complete)复杂程度的问题中表现出了远优于遗传算法(Genetic Algorithm,GA)的性能。而AFSA在饲料配方优化中的应用未见报道。考虑到AFSA出色的优化性能，以及饲料生产企业对于优秀饲料配方算法的实际需求，本文根据饲料配方优化设计的特点与性质，提出一种基于共生系统的鱼群算法并将其应用于饲料配方的优化求解，最后通过实际算例对算法的有效性进行了验证。

1 人工鱼群算法

与遗传算法类似，AFSA同样依赖一个种群：人工鱼群。AFSA对解空间的搜索方式也可归为“生成+检测”的方式。不同之处在于，遗传算法通过交叉和变异生成新解，而AFSA则通过人工鱼在解空间中游动而遇到新解。遗传算法的优化机理是“个体竞争”，AFSA的优化原理则体现在“个体自治”和“群体协作”。人工鱼个体在解空间中的游动只遵循简单的优化规则(即：追尾、聚群、觅食、随机游动)，而当多条人工鱼发生聚集时，由于个体间的协作与相互影响，人工鱼能够以集群的形式体现深刻的优化智能，该现象称为“突现(emergence)”^[14]。图 1以2维解空间为例对一条人工鱼进行了示意。不失一般性，它在解空间的位置为X，其适应度值可用函数fitness(X)计算。人工鱼X有步长(Step-limit) 和视野(Visual-limit)两个属性。通过执行追尾、聚群、觅食、随机游动等行为，人工鱼X可实现其在Step-limit范围内的移动；当有人工鱼Y进入人工鱼X的Visual-limit范围时，X、Y结成一种临时的“伙伴关系”。“伙伴”在AFSA中是一个重要的概念，也是AFSA得以体现群体智能的基础。图 2为AFSA的流程图。一般可根据待求解问题的性质采取一定的行为策略来安排人工鱼执行各个行为的顺序，即：图 2中的阴影部分。关于AFSA的具体算法描述及人工鱼各行为的伪代码，详见文献^[15]。

2 基于共生系统的鱼群算法框架 2.1 基本AFSA在饲料配方优化中面临的技术难点

饲料配方优化对解向量的精度有较高的要求。对于配比解向量X = [x₁ x₂ … x_m]中的每一个决策变量x_i，工业上实际的要求一般至少精确到小数点后4位。这给应用AFSA进行饲料配方优化带来了技术上的困难，因为自从2002年AFSA首次被提出以来，其较低的收敛精度一直被认为是导致AFSA未被学术界广泛接受的原因之一。针对求解精度无法满足工业要求的问题，有必要改进现有AFSA的运算框架以提高收敛精度。不失一般性，本节选取著名的Peaks函数作为算例，从参数Visual和Step对算法产生的影响出发，着重考察AFSA的收敛过程，据此得出对AFSA进行改进的依据。Peaks函数的表达式如式(4) 所示，图 3(a)、(b)分别展示了Peaks函数的曲面和极值分布情况。由于饲料配方优化问题是一个最小化问题，也以最小化Peaks函数值进行考察。本文的考察包括两组共6次实验。组①考察Step造成的影响：Visual=1.2，Step=0.8；Visual=1.2，Step=0.5；Visual=1.2，Step=0.05。组②考察Visual产生的影响：Visual=0.8，Step=0.5；Visual=1.0，Step=0.5；Visual=1.8，Step=0.5 。各次实验中AFSA的参数按表 1进行配置。对于一般的优化问题，种群规模PopSize只需设定在20~40，本例设为400只是为了方便观察鱼群的收敛形态。

$\begin{align} & z=3{{(1-x)}^{2}}{{e}^{-{{x}^{2}}-{{(y+1)}^{2}}}}-10(\frac{x}{5}-{{x}^{3}}-{{y}^{5}}){{e}^{-{{x}^{2}}-{{y}^{2}}}} \\ & -\frac{1}{3}{{e}^{-{{(x+1)}^{2}}-{{y}^{2}}}} \\ \end{align}$

(4)

根据表 1的参数配置本文做了6次独立实验去最小化Peaks函数。鱼群的最终收敛形态如图 4所示，图中每个点代表一条人工鱼。从图 4(a)~(c)不难看出，当视野范围Visual取值一定而步长Step设定值越小时，鱼群的聚集程度就越高，聚集度越高越有助于提高AFSA的收敛精度；然而，过小的步长Step设置会严重迟滞整个算法的搜索进程，这也是我们将第一组实验的迭代次数设定为200而不像第二组设为50的原因。图 4(d)~(f)则表明，当步长Step一定而视野范围Visual变化时，AFSA的全局收敛性随Visual的增大而提高，但较大的Visual值在AFSA迭代后期又带来了新的问题，即：人工鱼会感知到更多伙伴从而误判所处区域的拥挤程度并最终导致整个种群中近半数的人工鱼无法聚集，只能在全局极值附近震荡，此外，即使在全局极值处成功聚集成群的人工鱼也因同样的原因无法进一步聚集到更小区域去执行细粒度搜索(如图 4(f)所示的情况)，这也有碍于AFSA收敛精度的提高。

根据前述实验分析，提高AFSA收敛精度的关键在于保证人工鱼在算法迭代的初期具有较大的Visual和Step而在迭代的后期具有较小的Visual和Step。其目的旨在保证算法初期收敛的全局性与快速性，以及算法后期收敛的精确性。换言之，改进AFSA的可行方案是实现对AFSA两个参数Visual和Step的动态调整。

2.2 基于共生系统的人工鱼群算法框架

AFSA是受鱼群在水域中协作觅食行为的启发，对鱼类各种行为在计算机上进行程序模拟从而形成的一种优化算法。该算法的优化机制发端于鱼群内各人工鱼个体之间的协作关系。事实上，在自然界中，不同类的鱼种之间也在长期的进化历程中发展出了类似的互助协作关系，这种现象在生物学上称为“共生”，如图 5所示。

借鉴该生物学现象，我们构造了一个由两个鱼群构成的最简共生系统。两个鱼群记为群H和群S。其中，鱼群H中的个体称为宿主，鱼群S中的个体称为共生体。根据生物共生现象，共生体以某种形式从宿主获益以提高自身对自然界的适应性。相应地，在我们所构造的共生系统中，鱼群S中的共生体也以一定的规则从鱼群H获益。具体表现为：群S中的任一共生体X^S的Visual和Step可根据其与群H中所有宿主之间距离的代数平均值进行调整，算法进行至第k代的共生体人工鱼X^S的Visual和Step可分别根据式(5) ~(6) 计算。这样做的好处是让远离宿主群H的共生体人工鱼具有较大的Visual和Step以保证其能够快速聚集到主极值区域，而让位于宿主群H中心区域的共生体人工鱼具有较小的Visual和Step以保证其能对该区域进行深入的细粒度搜索以提高收敛精度。式(5) ~(6) 中涉及到的PopSize_H表示群H的种群规模，λ为收缩因子，取值区间为[0.1,0.8]。

$Visua{{l}_{k}}=\frac{\sum\limits_{j=1}^{PopSiz{{e}_{H}}}{\left\| \overrightarrow{X_{j}^{H}}-\overrightarrow{{{X}^{S}}} \right\|}}{PopSiz{{e}_{H}}}$

(5)

$Ste{{p}_{k}}=\lambda \cdot Visua{{l}_{k}}$

(6)

在本文所提出人工共生系统中，宿主群H扮演了标准AFSA的角色，而共生体群S则起到了辅助宿主群H进行更细粒度搜索的作用。此外，在设定中，宿主群H和共生体群S的角色允许互换。随着算法的迭代与演进，如果最优解连续m代没有更新，则将宿主群H变为共生体群，而原共生体群S变为新的宿主群。M可在5至20之间取值。这样，图 2中标准AFSA的流程就可改进为图 6的形式。为验证基于共生系统的AFSA的有效性，以C++对其进行编程实现，测试仍采用Peaks函数。算法参数设置为：PopSize = PopSize_H + PopSize_S = 200 + 200; Visual = 2; Step = 1; δ= 0.6; try_Number = 100。图 7对互为共生关系的两个鱼群的分布情况进行了展示。不难看出，由于双群之间的协作和互益关系，基于共生系统的AFSA对Peaks函数的优化不论在收敛速度方面还是收敛精度方面均显著优于标准AFSA。显然，本节提出的基于共生关系的鱼群算法框架是有效的。

3 在饲料配方优化问题中的应用 3.1 人工鱼在解空间的位置表达及鱼群初始化

利用AFSA对问题进行求解的关键之一是如何合理地将问题的潜在解映射成人工鱼在解空间中的位置。考虑到本文待求解问题本身的性质，可直接用解向量X = [x₁ x₂ … x_m]对人工鱼在m-维解空间中的位置进行表征。本文以[0,1]区间内服从均匀分布的随机小数对人工鱼编码各维度进行赋值的方式初始化人工鱼种群。

3.2 评价函数的设计

人工鱼个体的优劣以其适应度值作为评判依据，而其适应度值通常以优化模型的目标函数进行计算。换言之，可令fitness(X)=cost=[c₁ c₂ … c_m]×[x₁ x₂ … x_m]^T。 饲料成本越小，fitness(X)的值越小，则意味人工鱼个体越优。显而易见，饲料配方优化问题是一个最小化问题。

然而，由于约束的存在，简单地以目标函数cost作为适应度值的计算依据并不合理。这是因为，解空间被约束分割为了两部分：可行解域和非可行解域。一些不满足约束的非可行解存在目标函数cost值优于最优解的可能。例如潜在解(0,0,…,0) 的目标函数值为0，仅以目标函数cost=0来判断，该解最优，这显然有悖于事实。因此，对于饲料配方优化问题的非可行解应另行设计一种评价函数，使非可行解的适应度值在与可行解的比较中不占优势。根据引言，饲料配方优化问题有(n+1+m+δ)个约束。这些约束大致可分为如下4类：①禽畜生长发育对饲料营养指标所提出的n个不等式约束；②利用m种原料进行饲料配比时各原料所占比重之和客观上须等于100%这样的1个等式约束；③m个决策变量的客观取值范围须落入区间[0,1]内造成的m个不等式约束；④原料养分变异性、配合饲料的工艺条件等客观存在的δ个非线性约束，实际考虑的情况不同，此类约束的个数δ一般不定，当且仅当δ=0时问题模型退化为线性模型。对于①类和②类约束造成的非可行解，本文采用一种基于外点惩罚函数法的评价函数来计算其适应度值，见式(7) ，其中Δb_i表示超出营养指标上限或低于营养指标下限的差值，p₁和p₂均为惩罚因子；对于③类约束产生的非可行解，可直接将解向量越界的维度赋值为0%或100%进行简单的修复处理；得益于智能算法宽泛的适用性与开放的计算框架，对④类约束的处理方式同样可采取与处理①、②类约束相同的方法，利用外点惩罚函数法对目标函数添加惩罚项以评价非可行解。由于这δ个惩罚项的描述形式与实际考虑的④类约束的具体形式相关，本文仅在式(7) 中以∑δi=1item_i对这δ个惩罚项进行简略描述，其具体描述形式可根据实际需要设计，本文不再赘述。

$\eqalign{ & fitness(X) = cost + \cr & {p_1} \cdot \left| {100\% {\rm{0}}\sum\limits_{i = 1}^m {{x_i}} } \right| + {p_2} \cdot \sum\limits_{i = 1}^n {\Delta {b_i}} {\rm{ + }}\sum\limits_{i = 1}^\delta {ite{m_i}} \cr} $

(7)

3.3 人工鱼行为算子的描述 3.3.1 步长(Step-limit)的重新定义

对于一个m维解空间的问题来说，人工鱼一次游动的最大活动范围是一个以Step-limit为半径的m维超球体。人工鱼位置的更新则是通过在各维度上进行一次模运算来完成。这带来了繁重的计算量和算法耗时。为提高算法速度，本文对Step-limit重新进行了定义：令Step-limit表示m维解空间中的人工鱼个体在任意维度上的最大移动步长。换言之，人工鱼个体的最大活动范围变成一个m维超立方体，如图 8所示。此种情况下，在更新人工鱼位置时可免去耗时的模运算，有助于提高算法速度。

3.3.2 行为算子与行为策略

在标准AFSA中，人工鱼通过执行随机游动、觅食、追尾、聚群等4种行为对解空间搜索。其中，觅食是优化的基础，追尾增加收敛的快速性，聚群确保收敛的稳定性，而随机游动则为产生新解提供可能。AFSA的提出者李晓磊认为在实际优化中可根据求解问题的性质对AFSA进行适当简化^[15]。黄光球等^[16]通过数学推导论证了AFSA的全局收敛性，并指出：只要保持AFSA基本特征不变，其全局收敛性不受算法形式影响。文献^[11]对此进行了尝试，只选取了随机游动、觅食和追尾等3个行为而未采用聚群，却很好地求解了一个具有NP-C求解复杂度的优化问题。依据前述研究的理论指导和优化经验，本文只选取随机游动、觅食和追尾3个行为算子。以下对3种行为的实现方法及行为策略进行描述。

1) 随机游动。

设鱼群中第i条人工鱼在解空间中的位置为X_i，该位置向量的第d维记为X_i^d。若人工鱼i在执行随机游动行为后到达下一个位置X_i|_next，则随机游动行为的执行过程可描述为式(8) ，其中rnd表示一个在区间(-1,1) 上服从均匀分布的随机数，记为rnd~U(-1,1) 。由于随机游动行为较为简单，易于理解，本文不对其伪代码进行描述。

$X_{i}^{d}{{|}_{next}}=X_{i}^{d}+rnd\cdot Step$

(8)

2) 觅食。

设第i条人工鱼在解空间中的位置为X_i，其在最大步长Step范围内随机选择一个位置X_j，若fitness(X_i)>fitness(X_j)，说明位置X_j比X_i优，则人工鱼i游动到位置X_j，该过程按式(9) 执行；若fitness(X_i)≤fitness(X_j)，则人工鱼i重新在最大步长Step定义的范围内随机选择一个位置并再次判断是否满足游动条件；若反复尝试try_Number次后，仍不满足游动条件，则觅食行为失败，转而执行随机游动。

$X_{i}^{d}{{|}_{next}}=X_{j}^{d}$

(9)

觅食行为的伪代码描述如下，其中X_j的生成方式可按式(8) 以类似于随意游动的方式实现：

for t←0 to try_Number

generate a position X_j within Step-limit;

if (fitness(X_i)>fitness(X_j))

for d←0 to m

X_i^d|_next=X_j^d;

end for

break;

else

t++;

end if

end for

3) 追尾。

追尾行为主要体现了人工鱼对其Visual-limit范围内优秀个体的学习和模仿。设第i条人工鱼在解空间中的位置为X_i，在其Visual-limit范围内有n_f条人工鱼，称人工鱼i的n_f个伙伴。假定人工鱼i的伙伴中，所在位置为X_sp的人工鱼最优，且满足追尾条件fitness(X_sp)·n_f<fitness(X_i)·δ，则人工鱼i按式(10) 以随机步长向X_sp游动，其中δ称为拥挤度因子，式(10) 中的rnd表示一个在区间(0,0.001) 上服从均匀分布的随机数，记为rnd~U(0,0.001) ；当追尾条件不满足或n_f=0时，追尾失败，转而执行觅食。

$X_{i}^{d}{{|}_{next}}=X_{i}^{d}+\min \{rnd\cdot (X_{sp}^{d}-X_{i}^{d}),Step\}$

(10)

追尾行为的伪代码描述如下：

if (n_f ≠ 0 and fitness(X_sp)·n_f<fitness(X_i)·δ)

for d←0 to m

X_i^d|_next=X_i^d+min{rnd·(X_sp^d－X_i^d),Step};

end if

4) 行为策略。

图 9所示流程为本文算法采取的行为策略。

5) 标本。

与GA中精英保留策略类似，AFSA中通常会设置一个人工鱼标本用来保存各次迭代中的最优个体，记为fish-specimen。既保证了算法不退化，也便于输出最终解。

3.4 算法流程与步骤

将图 9流程代入图 6的行为策略部分，可得到求解饲料配方优化问题的基于共生系统的AFSA的完整运行框架和流程。下面以伪代码形式对算法进行描述：

1) Setting parameters,including PopSize_H,PopSize_S,Visual,Step,try_Number,MaxIteration,m,p₁,p₂;

2) Initialize fish[PopSize_H+PopSize_S] and evaluate the fitness of fish[i],where i=0 to PopSize_H + PopSize_S －1;

3) Set fish[0 ~ PopSize_H－1].Tag = H;Set fish[PopSize_H ~ PopSize_H+PopSize-1].Tag = S;

4) Set fish-specimen

5) for iteration←1 to MaxIteration

for i←0 to PopSizeH+PopSize_S－1

 fish[i].BehavioralStrategy();

 evaluate fish[i].fitness;

 if(fish[i].fitness<fish-specimen.fitness)

   fish-specimen = fish[i];

 end if

end for

if (fish-specimen is not updated for m iterations)

 for i←0 to PopSize_H+PopSize_S －1

  if (fish[i].Tag == H)

  fish[i].Tag = S;

  else

  fish[i].Tag = H;

  end if

 end for

end if

end for

6) Output the solution vector represented by fish-specimen as the finally obtained solution to the problem.

4 算例验证

为验证本文提出算法(Sym-AFSA)的有效性，以C++对Sym-AFSA进行程序编写，并以3个实际算例对其测试和验证。测试平台为Intel Core i7-4790 CPU @ 3.6GHz，16GB RAM。此外，本文还将Sym-AFSA与模拟退火搜索算法(SAA)^[8]，以及两种遗传算法(GA)^[6]和HGA^[7]的结果进行了对比。本文算法Sym-AFSA的参数设定如下： PopSize_H+PopSize_S = 20+20; Visual = 2; Step = 1; δ=0.6；try_Number = 100; p₁=10; p₂=4; MaxIteration=1000。

算例有3个： 1) 50~80kg生长肥育猪的饲料配方算例；2) 0~3周龄肉用仔鸡的饲料配方算例；3) 0~3周龄番鸭饲料的饲料配方算例。表 2~4分别列出了3个算例的配方原料和营养组分，各算法结果见表 5~10。

算例1 从营养指标看，各算法均得出了各项营养达标的饲料配方；但以饲料吨成本计算，各算法结果按降序排列依次为GA>SAA>HGA>Sym-AFSA (见表 8) 。Sym-AFSA得出的饲料配方吨成本比GA、SAA和HGA分别少331.41元、299.79元和87.25元。显然，SAA、GA、HGA各自收敛于局部最优解，只有Sym-AFSA得出了最优的饲料配比方案。

算例2 各算法均求出各项营养达标的饲料配方，而配合饲料的吨成本按降序排列依次为GA>SAA>HGA>Sym-AFSA(见表 9) 。其中，Sym-AFSA得出的饲料配方吨成本分别比GA、SAA和HGA分别少432.15元、314.44元和195.99元。与算例1情况相同，除Sym-AFSA外，SAA、GA以及HGA均出现了不同程度的早熟收敛。

算例3 从营养指标看，依旧是各算法均得出了营养达标的满意解，而所得饲料配方按吨成本降序排列为SAA=GA>HGA>Sym-AFSA (见表 10) 。与SAA、GA和HGA比，Sym-AFSA所得结果的吨成本分别降低175.49元、175.49元和110.69元。对于该算例，SAA与GA收敛于同一个局部解，HGA收敛于一个相对更优的解，但仍劣于Sym-AFSA的收敛解。

5 结语

本文研究工作主要聚焦于饲料配方的优化设计，优化工具采用了全局搜索能力强、收敛速度快的AFSA。为解决“AFSA收敛精度低”与“解向量配比要求精度高”之间的矛盾，提出了一种基于共生系统的AFSA运行框架，显著提高了AFSA的收敛精度。在此基础上，将基于共生系统运行框架的AFSA应用于饲料配方的优化过程。算法直接以饲料配比解向量对人工鱼在解空间中的位置进行表征，采用一种基于外点惩罚函数的评价函数对人工鱼适应度值进行评价。为进一步缩短算法运行时间，对人工鱼模型的步长(Step-limit)重新进行了定义，从而免去了耗时的模运算。人工鱼依据预定的行为策略执行随机游动、觅食、追尾等算子，实现对解空间的搜索。本文通过三个实际算例对提出算法的有效性进行验证，同时将计算结果与一些已有智能算法进行了对比。结果表明，本文算法不仅能够设计出各项营养达标的饲料配比方案，同时能够显著降低所配饲料的吨成本，其性能明显优于其他已有智能算法。