论文部分内容阅读
免疫优化算法是受免疫学启发,模拟自然免疫系统功能、原理和模型来解决复杂问题的一种新的智能计算方法,已经广泛应用于各个领域。随着信息技术的飞速发展,产生了越来越多的复杂海量数据,在应用免疫优化算法求解这些数据时要面临提高解的质量和求解速度等问题。近十年来,集群系统作为一种新的高性能计算平台得到了长足的发展,基于集群的计算技术为解决上述问题提供了一条途径。本文基于集群计算技术,将免疫算法应用于求解特征选择、图像降维和装箱等问题,提出了四种新的算法和并行策略,主要工作概括如下:(1)针对数据挖掘和模式识别等领域的高维数据降维问题,提出了基于免疫记忆克隆的特征选择算法。该算法利用抗体种群进行全局搜索,通过设立记忆单元来保留历史最好个体,并对其嵌入可控制搜索深度的局部搜索算子,用以加快抗体亲和力成熟速度,同时对抗体种群和记忆单元采用不同的亲合度函数以获得更好的搜索能力。在MATLAB并行计算环境下,将该算法用于6个高维数据集进行特征子集选择,实验结果表明,与标准遗传算法相比新算法具有更低的复杂度和更好的搜索能力,其鲁棒性也优于经典的串行浮点前向搜索算法。(2)针对封装式特征选择的耗时问题,提出了一种负载均衡的主从式并行免疫克隆模型。主进程利用免疫克隆算法进行特征选择,从进程并行计算个体亲和度。为进一步降低算法运行时间,基于LPT和MULTIFIT设计了启发式任务调度算法,首先基于时间复杂度预先估计种群中个体亲和度的计算时间,然后按照个体的亲和度计算时间利用提出的调度算法分配这些个体到从进程,由于考虑了负载均衡,相比直接利用数量分配个体的传统方法能获得更短的执行时间。在Linux刀片集群上基于MPICH软件对UCI数据集进行特征子集选择实验,特征子集采用最近邻分类和留一法验证评价,结果表明该算法可有效降低实验时间,在40个进程时效率最高可达75%。(3)基于生物免疫系统理论和消息传递接口提出了一种粗粒度并行免疫克隆算法,利用分布在多个处理器上的多个抗体种群同时并行搜索空间。为了避免算法早熟收敛和提高种群多样性,种群使用环状通信拓扑结构,互相通过疫苗迁移算子来交流信息。对Brodatz纹理库和真实SAR纹理图像利用Contourlet变换提取能量特征,用该算法选出的特征子集采用最近邻分类器评价,在Linux集群上的仿真结果表明算法性能优于SFFS和SGA算法,且可有效降低实验时间,在13个处理器时效率最高可达91%。(4)为了提高求解一维装箱问题解的性能和降低算法运行时间,提出了一种并行免疫克隆装箱算法。使用占优准则对数据进行预处理,并采用基于分组思想的编码和交叉算子。种群之间通过疫苗迁移算子来交流信息。在Linux集群上对OR-library运筹库的测试数据和大规模下料问题上的仿真结果表明算法性能优于经典启发式算法,且可有效降低实验时间。