智能优化方法及其应用研究

生物体和自然生态系统可以通过自身的演化就使许多在人类看来高度复杂的优化问题得到满意的解决,受此启发,产生了以模仿自然与生物机理为特征的智能优化方法,它们为用传统的优化方法难以解决的NP-困难问题提供了有效的解决途径。任务的合理分配与调度是并行分布式系统获取高性能的关键因素之一,它们是NP-困难的问题,基于智能优化方法的任务分配与调度算法是解决这些问题的有效算法。本论文主要研究三种典型的智能优化算法,遗传算法、蚁群优化算法和粒子群优化算法,研究如何通过免疫原理提高它们的性能,并把它们应用于解决异构环境下的独立任务分配问题及同构和异构环境下的相关任务调度问题。 提出了具有免疫特性的蚁群优化算法,针对蚁群优化算法易于陷入早熟收敛和局部求精能力不足的缺点,从人工免疫系统的基本原理出发,设计了三种免疫算子:免疫抑制算子、信息素平滑算子和接种疫苗算子;使用免疫抑制算子、信息素平滑算子来保持蚁群的多样性,使算法在迭代的后期依然保持进化能力,使用接种疫苗算子来提高算法的局部求精能力,使蚁群优化算法在局部开采和全局探索间取得更好的平衡。通过典型旅行商问题和任务分配与调度问题,对算法进行了仿真比较,结果表明免疫算子能有效地提高蚁群优化算法的性能。 提出了离散粒子群优化算法的基本设计原则,根据离散量运算的特点,对粒子的位置、速度等量及其运算规则进行了重新定义,为抑制早熟停滞现象,为粒子和粒子群分别定义了个体多样性、微观多样性和宏观多样性,从人工免疫系统的基本原理出发,提出用排斥算子和膨胀算子来增加或保持粒子群的多样性,用接种疫苗算子来加强算法的求精能力。通过典型旅行商问题和任务分配与调度问题,对算法进行了仿真比较,结果表明离散粒子群优化算法能够很好地应用到组合优化问题中。 针对异构环境下独立任务分配问题,基于遗传算法、蚁群优化算法、离散粒子群优化算法和免疫原理,分别就解空间的直接和间接编码方式,提出了一些新的优化算法。基于直接编码方式的算法有免疫遗传算法、免疫蚁群优化算法和免疫离散粒子群优化算法,它们直接以解空间为算法的搜索空间;基于间接编码方式的算法有免疫混合遗传算法、分段免疫混合蚁群优化算法和免疫混合离散粒子群优化算法,它们是表启发式分配算法和智能优化算法的结合,以任务分配顺序表为搜索空间,搜索最优的任务分配顺序,然后把搜索出的任务分配顺序表用最小完成时间算法进行解码,得到相应的一个分配方案。这些算法采用了免疫原理