域约束免疫进化算法优化

科学、工程、社会和经济等领域中的许多优化问题，最终均可以归结为求解一个带有约束条件的函数优化问题，对其求解是进化算法（EA）界乃至优化界所面临的巨大挑战。对于约束优化问题，已有的许多算法都是基于梯度的概念[160]，其适用于目标函数和约束函数可微的情形，而且一般只能保证求到局部最优解。遗传算法[161]可被用于求解此类问题，但是，在处理实际复杂问题时，算法的未成熟收敛、局部搜索能力差以及中后期搜索效率低是其明显的缺点，同时，基于遗传算法的约束条件的处理多采用罚函数法，但是，罚因子的确定是很困难的，一般需通过多次实验来调节[162]。受生物免疫原理启发，作者在文献[54]中创造性地提出了免疫进化算法，其更好的优化性能已从理论上予以了证明[158]，并得到了应用的检验[163～166]。在此基础上，针对域约束优化问题提出一种更为高效的普适算法，即域约束普适免疫进化算法[167]，它不仅解决了域约束优化问题的困扰，也为其他形式的约束优化问题的进一步研究奠定了基础。

1.域约束的最优化问题

只含上、下限的约束的优化问题可以描述为

当区间[bi，ai]（i＝1，2，…，n）的范围均不超过某一上限时，可以把此区间内的解视为是隶属于某一抗体群的抗体，依据免疫学的机理，产生的下一代该抗体群的抗体（解）也应落在上述区间内。适应度则体现该抗体群内抗体（解）生存能力的强弱，适应度高的个体易被激活，相反，适应度低的个体则易处于抑制状态。免疫进化算法采用十进制表达问题，由式（5-22）生殖方式产生的子代抗体（解）不能保证一定落在该区间内，这不仅造成了计算的浪费，而且还会破坏原有的生殖分布。在免疫进化算法的基础上提出了一种区间变换技术，它能确保生殖后得到的抗体（解）满足区间约束，该技术不仅可以克服采用试凑法和罚函数法带来的不足，而且还可相应地提高计算效率。

2.区间变换的实施步骤

式中：i＝1，2，…，n；σ0＝2。

3.域约束免疫进化算法的表述

基于上述区间变换技术，域约束优化问题的免疫进化算法的表述的流程表述如下：

4.算法测试

为了检验域约束普适免疫进化算法的性能，同样以例5-1～例5-4的典型的测试函数为例进行测试计算。

算法中各主要参数统一取为群体数量N＝200、总进化代数T＝50、初始标准差σ0＝3、标准差动态调整系数A＝3，最优个体随迭代的变化见图5-7～图5-10。

图5-7　例5-1收敛测试结果

图5-8　例5-2收敛测试结果

图5-9　例5-3收敛测试结果

图5-10　例5-4收敛测试结果

由图5-7～图5-10可见，算法中的最优个体向全局最优解的收敛能在50步以内完成，优于免疫进化算法的测试结果[54]。

5.遗传算法欺骗问题测试

单调函数和单峰函数满足遗传算法的模式定理和积木块假设，但是大多数实际优化问题的目标函数常常为非单调函数或多峰函数，因此搜索过程中可能存在某些低阶模式难以重组为期望的高阶模式，这类问题统称为遗传算法欺骗问题（GA Deceptive Problem）[162，168]。

为了分析域约束普适免疫进化算法在求解遗传算法欺骗问题时的性能，对下述典型的大海捞针问题（Needle-in-a-haystack）进行了测试，即

当a＝3.0，b＝0.05时，max f（0，0）＝3600；该函数有4个局部极值点为（-5.12，5.12）、（-5.12，-5.12）、（5.12，-5.12）、（5.12，5.12），对应的函数极值均为2748.78。遗传算法求解此类问题很难克服模式的欺骗性，故遗传算法搜索到全局最优解就成为了一个随机事件，遗传算法的求解结果见表5-3[162]，表5-3同时列出了域约束免疫进化算法的10次求解结果（求解参数同上）。表5-3中分子数字表示收敛次数，分母数字表示试验总次数。

表5-3　普适免疫进化算法对大海捞针问题的测试

由表5-3可见，域约束免疫进化算法能非常好地收敛到全局最优解，其优化效果远好于遗传算法的计算结果。(www.xing528.com)

6.域约束免疫进化算法特点

研究分析表明，域约束免疫进化算法有以下主要特点：

（1）该算法能保证下一代的解仍落在原区间内，从而提高了计算效率。

（2）该算法进一步简化了参数设置，增强了模式的统一性，易于软件实现。

（3）从搜索的进程上而言，它能更好的平衡全局搜索和局部搜索。

（4）它为不等式约束和等式约束优化问题的解决奠定了基础。