受果蝇觅食过程的启发，台湾学者Pan^[1]于2012年提出了较为高效的群智能优化算法——果蝇算法(FOA, fruit fly optimization algorithm)。由于该算法原理清晰、参数较少、操作简单，受到广泛关注。学者通过深入研究将其运用到预测、物流、调度、结构设计等领域，得到了较高的认可度。该算法同样存在不足^[2-3]：1)标准果蝇算法无法求解最优值为负的问题；2)解决复杂、高维和非线性优化问题的能力较弱；3)易陷入局部极值点等。

针对上述典型问题，不少学者对标准果蝇算法进行了改进。在候选解产生方面：Pan^[4]在味道浓度判定值中加入可以为负的逃逸参数，使得候选解能够取到负值。在搜索半径方面：Pan等^[5]引入自适应参数来调节果蝇的搜索半径，使之能够较好地平衡全局搜索能力及局部搜索能力。在飞行策略方面：Wang^[6]、Li^[7]、张前图等^[8]加入了群体协作和随机摄动的操作，进而解决算法的早熟问题。在种群多样性方面：刘志雄等^[9]将果蝇群体分成多个相同规模的子种群、韩俊英等^[10]提出了一种动态双子群协同进化FOA，提升搜索精度。

研究通过设计混合算法：融合免疫反应^[11-13]的混合果蝇算法(IAFOA, fruit fly optimization algorithm based on immune algorithm)对标准果蝇算法进行性能改进。充分利用免疫算法来改善果蝇算法后期易陷入局部极值的不足，即当进化停滞步数t大于进化停滞步数阈值T时，执行免疫操作^[14-15]来克服基本果蝇算法的缺陷。通过标准函数及求解0~1背包问题的测试验证改进算法具有较好的鲁棒性及智能性^[16]。最后，将其应用于桁架结构优化问题，通过对比其他算法验证IAFOA的可行性。

1 基本果蝇算法

果蝇算法(FOA, fruit fly optimization algorithm)是一种新兴启发式算法，模拟自然界果蝇的觅食活动寻求目标函数的最优解，果蝇觅食示意图，如图 1所示。其基本步骤如下^[17-19]

步骤1：初始化参数。设置种群规模S_Sizepop和最大迭代次数M_Maxgen，初始化种群位置

$ ({X_{{\rm{\_axis }}}}, Y{{\rm{ }}_{{\rm{\_axis }}}})。$

(1)

步骤2：赋予果蝇个体觅食的随机方向及距离

$ \left\{ \begin{array}{l} {X_i} = {X_{{\rm{\_axis}}}}{\rm{ + }}{R_{{\rm{ Value }}}}, \\ {Y_i} = {Y_{{\rm{ \_axis }}}}{\rm{ + }}{R_{{\rm{ Value }}}}。\end{array} \right. $

(2)

步骤3：起初不能获知食物源位置，先计算果蝇个体与原点之间的距离D_i，再计算味道浓度判定值S_i，

$ {{D_i} = \sqrt {X_i^2 + Y_i^2} , } $

(3)

$ {{S_i} = 1/{D_i}}。$

(4)

步骤4：将S_i带入味道浓度判定函数(fitness function)求出果蝇个体位置的味道浓度T_i,

$ {T_i} = {\rm{ Fitness }}({S_i})。$

(5)

步骤5：找出果蝇群体中味道浓度最高的个体为

$ [{B_{{\rm{ BestTaste }}}}, {B_{{\rm{ BestIndex }}}}, ] = {\rm{min}}({T_i})。$

(6)

步骤6：保留最佳味道浓度值与坐标，种群中其他个体向该位置飞去，

$ {T_{{\rm{ Best }}}} = {B_{{\rm{ Best Taste }}}}, $

(7)

$ \left\{ \begin{array}{l} {X_{{\rm{\_axis}}}} = {X_{{\rm{ bestIndex }}}}, \\ {Y_{{\rm{\_axis}}}} = {Y_{{\rm{ bestIndex }}}}。\end{array} \right. $

(8)

步骤7：终止条件，判断最佳位置浓度是否优于前一代，并且达到最大迭代次数，否则跳转步骤2进入迭代寻优。

2 融合免疫反应的混合果蝇算法

果蝇具有较发达的嗅觉和视觉系统，在觅食过程中先通过嗅觉进行大范围搜索，并向周围的果蝇发出食物气味信息。当果蝇通过比较发现具有较高浓度的位置时，果蝇个体将依靠视觉功能飞向该位置。正是由于这样的种群特性，降低了种群多样性，使模拟其特性的果蝇算法同其他仿生智能算法一样具有容易陷入局部最优的缺陷，带来早熟问题。

免疫算法从体细胞理论和网络理论中得到启发，实现了与免疫系统类似的自我调节和生成不同抗体的功能。该算法具有很强的局部搜索能力，将其引入果蝇算法执行过程后期，提出融合免疫反应的混合果蝇算法IAFOA，新算法IAFOA可以用来平衡果蝇算法易陷入局部最优的不足，提高搜索效率。2种标准算法对应关系如表 1所示。

2.1 免疫算法

免疫算法(IA, immune algorithm)是一种仿生优化类算法，该研究最初是从20世纪80年代中期的免疫学研究发展而来。1990年，Bersini^[20]首次使用免疫算法来解决问题。IA算法通过模拟生物免疫系统功能进行抗原(目标函数)的识别，对免疫系统中的存储记忆原理的模拟，抗原和抗体(优化解)的结合，以及免疫系统自身多样性的模仿，实现了类似于免疫系统的抗原识别、细胞分化、记忆和自我调节的功能^[21]。其基本步骤如下：

步骤1：抗原识别。输入目标函数和约束条件作为免疫算法的抗原。

步骤2：产生初始抗体。在解空间范围内随机产生初始抗体。

步骤3：计算亲和性(适应度评价)。按给定的适应度评价函数判定各个抗体与抗原的亲和性及抗体和抗体之间的亲和性。

抗原与抗体V之间的亲和性A_v定义为

$ {A_{\rm{v}}} = 1/[1 + {O_{\rm{P}}}{t_{\rm{v}}}], $

(9)

式中：O_Pt_v表示抗原和抗体的匹配程度；A_v的值介于0~1之间。当O_Pt_v=0时，A_v=1，这表明抗体和抗原非常匹配, 即该抗体为最优的解。

步骤4：记忆单元的更新。将步骤3计算出的与抗原亲和性最高的抗体加入记忆单元，并取代原有抗体。

步骤5：促进和抑制节的产生。计算抗体i的期望值E_xi，期望值低的抗体将被抑制。

$ {E_{xi}} = {A_i}/{C_i}, $

(10)

式中：A_i是抗原与抗体i的亲和性；C_i是抗体i的数目。

步骤6：产生新抗体。父代通过遗传、变异、交叉产生下一代抗体。

步骤7：是否满足终止条件。是，终止算法；否，跳转步骤3。

2.2 IAFOA种群多样性改进

免疫系统是通过阻拦细菌入侵维持生物正常代谢的基本防御系统。该系统通过识别基因类型以产生不同的抗体，通过调节机制促进新个体的出现、抑制个体的过多产生，从而实现生物的多样性^[22]。

设免疫系统有N个抗体，每个抗体有M个基因，如图 2所示。第j个基因的信息熵H_j(N)为

$ {H_j}(N) = \sum\limits_{i = 1}^N {( - {P_{ij}} \times {\rm{log}}{P_{ij}})} 。$

(11)

如果在位置j上所有抗体的等位基因都相同，那么H_j(N)等于0。

故，系统的平均信息熵H(N)为

$ H(N) = \sum\limits_{j = 1}^M {{H_j}} (N)/M。$

(12)

2.3 IAFOA算法的执行

算法以标准果蝇算法为基本框架，调用FOA算法，构造各次迭代的可行解集，然后采用进化停滞步数t作为触发条件，当t＞T(进化停滞步数阈值)时，调用IA搜索过程，将免疫算法中免疫因子(对应果蝇个体)寻求抗原(对应果蝇算法中的食物源)产生抗体(优化解)的过程用于扩大搜索的空间。对经过IA搜索后获得的可行解集执行精英保留策略，得到的优化解与原可行解集共同用于更新搜索空间中气味信息的浓度，以指导其他果蝇的路径寻找机制。

其中，进化停滞步数阈值T为进入IA算法的指标，过早引入IA算法，不利于IA的搜索能力，甚至无法收敛可行解；过晚进入IA算法，不利于提高计算效率。通过多次独立试验取值，研究采用T=3作为进入IA算法的触发条件值。

如满足触发条件，则以某一固定概率p将果蝇重新分配到寻优空间中，并对不同个体根据其适应度值赋予不同的自适应免疫概率P(i)，通过P(i)选出需进行免疫操作的果蝇个体，执行免疫操作，进而迭代搜索得优化解放入原优化解集进行比较。

$ P(i) = \frac{{({T_{{\rm{ Best }}}} - {T_i})}}{{({T_{{\rm{ Best }}}} - {T_{{\rm{ Worst }}}})p}}, $

(13)

其中，为避免算法陷入局部最优解，给定IA算法中免疫因子一定的初始概率p=0.25使其随机分配，增加解的多样性。

IAFOA的流程如下

步骤1：初始化参数。设置种群规模S_Sizepop和最大迭代次数M_Maxgen，初始化种群位置X_{_axis}和Y_{_axis}，进化停滞步数t=0。

步骤2：根据式(3)随机产生果蝇群体。

步骤3：采用式(4)~式(7)对种群进行操作。

步骤4：根据式(14)记录并保留最佳味道浓度值，更新进化迭代步数t。

$ \left\{ {\begin{array}{*{20}{l}} {if({B_{{\rm{ Best Taste }}}} < {T_{{\rm{ Best }}}})}\\ {{\kern 1pt} {\kern 1pt} {\kern 1pt} {\kern 1pt} {\kern 1pt} {\kern 1pt} {\kern 1pt} {\kern 1pt} {T_{{\rm{ Best }}}} = {B_{{\rm{ Best Tastel }}}}}\\ {{\rm{ }}{\kern 1pt} {\kern 1pt} {\kern 1pt} {\kern 1pt} {\kern 1pt} {\kern 1pt} {\rm{else }}(t = t + 1)}\\ {{\kern 1pt} {\kern 1pt} {\kern 1pt} {\kern 1pt} {\kern 1pt} {\kern 1pt} {\kern 1pt} {\kern 1pt} {T_{{\rm{ Best }}}} = {B_{{\rm{ BestTaste2}}}}}\\ {{\rm{ }}{\kern 1pt} {\kern 1pt} {\kern 1pt} {\kern 1pt} {\kern 1pt} {\kern 1pt} {\kern 1pt} {\kern 1pt} {\kern 1pt} {\kern 1pt} {\kern 1pt} {\kern 1pt} {\kern 1pt} {\kern 1pt} {\kern 1pt} {\kern 1pt} {\kern 1pt} {\kern 1pt} {\kern 1pt} {\kern 1pt} {\kern 1pt} {\kern 1pt} {\kern 1pt} {\kern 1pt} {\kern 1pt} {\kern 1pt} {\kern 1pt} {\kern 1pt} {\kern 1pt} {\rm{end }}} \end{array}} \right. $

(14)

步骤5：判断t＜T是否成立，若是直接转步骤7；否则，根据式(13)计算果蝇个体自适应免疫概率，按照免疫算法进行免疫操作，未执行免疫操作的个体转步骤7。

步骤6：对执行免疫操作所得的新种群重复执行步骤2~步骤4进行迭代搜索。

步骤7：令g_gen=g_gen+1，若g_gen＜M_Maxgen则转步骤2，否则终止迭代。

IAFOA流程图，如图 3所示。

3 仿真实验

为验证文中算法的有效性，选取4个标准测试函数进行数值仿真试验来测试IAFOA算法的性能^[23]。另外，选取0~1背包问题进行仿真实验，将结果与其他算法进行比较。初始化参数：种群规模S_Sizepop=200，最大迭代次数M_Maxgen=1 000，维度D=30，初始概率p=0.25，进化停滞步数阈值T=3。

3.1 标准函数测试

第1个标准函数：Rosenbrock函数

$ {f_1}(x){\rm{ }} = \mathop \sum \limits_{i = 1}^{d - 1} [100{({x_{i + 1}} - x_i^2)^2} + {({x_i} - 1)^2}]。$

第2个标准函数：Ackley函数

$ {f_2}(x) = - a{\rm{exp}}( - b\sqrt {\frac{1}{d}\sum\limits_{i = 1}^d {x_i^2} } ) - {\rm{exp}}(\frac{1}{d}\sum\limits_{i = 1}^d {{\rm{cos}}} (c{x_i})) + a + {\rm{exp}}(1)。$

第3个标准函数：Griewank函数

$ {f_3}(x) = \frac{1}{{4{\kern 1pt} {\kern 1pt} {\kern 1pt} 000}}\sum\limits_{i = 1}^D {x_i^2} - \prod\limits_{i = 1}^D {{\rm{cos}}} \left( {\frac{{{x_i}}}{{\sqrt i }}} \right) + 1。$

第4个标准函数：Schaffer函数

$ {f_4}(x) = {\rm{sin}}\left( {\frac{{\sqrt {\sum\limits_{i = 1}^D {(x_i^2)} } - 0.5}}{{1 + 0.001 * {{\left( {\sum\limits_{i = 1}^D {(x_i^2)} } \right)}^2}}}} \right) + 0.5, $

式中：Rosenbrock函数为单峰值函数，主要用来测试文中改进算法在运算过程中的收敛性能；Ackley函数和Griewank函数均为较复杂的多峰值函数，易使算法陷入局部最优，从而得不到真正的最优值，用来测试改进算法处理易陷入“早熟”的能力；Schaffer函数具有复杂的空间性，用来测试改进算法的计算精度、收敛稳定性和算法时间复杂度。4种标准函数如图 4所示。

通过运用4种不同标准函数分别对文中改进算法的收敛性能、运行效率、处理“局部最优”以及“早熟”问题进行测试，寻优测试中的最优值、平均值，反映出解的质量。标准差反映了算法的鲁棒性。运行时间则反映算法收敛速度及精度。由表 2可以看出，融合免疫反应的混合果蝇算法在标准函数上的表现优于标准果蝇算法。该改进算法是可行且有效的。

为了更加直观地看出改进算法性能的有效性，图 5是免疫算法(IA, immune algorithm)、粒子群算法(PSO，particle swarm optimization)、标准果蝇算法(FOA, fruit fly optimization algorithm)及融合免疫反应的混合果蝇算法(IAFOA, fruit fly optimization algorithm based on immune algorithm)在上述4种标准函数下的收敛曲线图。采用多次运行结果的平均值作为最终结果以避免偶然误差。

3.2 求解0~1背包问题

0~1背包问题是组合优化领域常见问题之一，该问题的描述为：设物品总数为D，第i个物品的体积和价格分别为w_i和p_i，一个背包的最大容量为V，怎样选择物品使得背包的总价值最大，即为0~1背包问题。其数学模型为

$ { {\rm{max}} f = \mathit{\boldsymbol{RX}} = \sum\limits_{i = 1}^D {{R_i}} {x_i}, } $

(15)

$ {\rm{s}}.{\rm{t}}.\;{\bf{WX}} = \sum\limits_{i = 1}^D {{w_i}} {x_i} \le V, $

(16)

式中：R =(R₁, R₂, …, R_D)、W =(w₁, w₂, …, w_D)、X =(x₁, x₂, …, x_D)分别表示物品的价值向量、体积向量、解向量；x_i为决策向量，x_i=0表示未放入包，x_i=1表示放入包。

算例的基本参数设置，如表 3所示。

改进算法及其他3种标准算法的优化对比，如表 4和图 6所示。结果表明，改进算法在求解0~1背包问题时的优化性能较优。

4 IAFOA对桁架结构的优化 4.1 桁架结构优化模型 4.1.1 优化模型

以截面积为设计变量的桁架优化模型问题描述为

$ {{\rm{min}}F = W(x), } $

(17)

$ {{\rm{ s}}{\rm{.t}}{\rm{. }}{g_i}(x) \le 0, i = 1, 2, \cdots , m, } $

(18)

式中：g_i(x)为约束函数；m为约束个数。

4.1.2 目标函数

$ W(A) = \sum\limits_{i = 1}^n \rho {A_i}{L_i}, $

(19)

式中：W(A)为结构的重量；A_i、L_i分别为第i根杆件的截面积和长度；ρ为材料密度；n为设计变量个数。

4.1.3 约束条件

结构中各个杆件需满足强度、刚度、稳定性及截面尺寸的要求

$ {\frac{{{\sigma _i}}}{{[\sigma ]}} - 1 \le 0, } $

(20)

$ {\frac{{{\mu _j}}}{{{\mu _{{\rm{max}}}}}} - 1 \le 0, } $

(21)

$ {{A_{{\rm{min}}}} \le {A_i} \le {A_{{\rm{max}}}}, } $

(22)

式中：σ_i为第i根杆件的正应力；[σ]为材料的许用应力；μ_j为节点j的位移；μ_max节点j的许用位移；A_min、A_max分别为杆件截面的上、下限。

4.2 算例1

建立10杆桁架结构模型，如图 7所示，其包含节点数6个，设计变量10个，为求得结构的最小总重量，现对其进行优化。E=68 950 MPa，ρ=2 768/m³，σ=±172.4 MPa，规定杆件截面面积的浮动范围为[0.645, 258]cm²，该结构体系中图示节点受到大小为P=444.5 kN且方向向下的集中荷载，优化结果如表 5所示。

4.3 算例2

选取25杆件空间桁架结构^[22]，如图 8所示。桁架结构的基本参数：杆件长度l=0.635 m，弹性模量E=6.895×10⁴MPa，材料密度ρ=2.678×10³ kg/m³，许用应力范围：[-275.8, 275.8]，结构受荷载情况如表 6所示，节点1和节点2的最大竖向位移y=8.889 mm。优化结果如表 7所示。

4.4 算法迭代曲线对比

通过该经典算例模型进行优化对比，由表 5及表 7优化结果可以看出，新算法IAFOA在求解速度和优化程度上的表现更良好，能够达到预想结果。通过图 9迭代曲线可以看出，IAFOA算法具有较好的全局搜索能力，在收敛速度及精度上比其他3种标准算法有较大的提高。

5 结论

研究将IA引入到FOA中构建IAFOA算法。IAFOA同时结合了原有标准FOA算法的全局搜索能力和IA算法自身较强的局部搜索能力，在数值模拟、求解优化问题以及算例分析中IAFOA在收敛性、运行效率、跳出“局部最优”上均取得了较好的结果。文中虽然改进了算法的一些不足，但缺乏对参数停滞步数阔值T、固定概率p的调节，还需要更加详细的改进以求IAFOA算法收敛得更快更精准。另外，文中实例较为简单，算法应用于复杂结构优化中的相关研究仍需进一步深入。