进化算法是建立在自然选择原理和自然遗传机制上的新型优化算法,有着简单、通用、健壮性强、适于并行处理等显著特点。多目标优化问题是科学和工程研究领域的一个难题和热点问题,得到了社会各界的广泛关注。研究表明,应用进化算法求解多目标优化问题比较合适。
近几年来,为了克服进化算法的早熟收敛问题,保持解群体的多样性,很多研究者通过引用目标空间划分的思想来优化多目标问题。本文针对现有基于目标空间分割思想的进化算法计算时间复杂度高的缺陷,提出了一种改进的基于目标空间分割的多目标进化算法(OSD-MOEA),并利用该算法的目标空间分割的思想解决了一种网格任务调度中并行程序的调度问题。本文主要工作如下：
1、本文通过引用目标空间划分的思想来优化多目标问题,提出了一种基于目标空间分割思想的改进的多目标进化算法(Improved MOEA based on objectiv-space-divided,简称OSD-MOEA)。该算法包含以下几个方面：通过对解群体的目标空间分割特点的分析,提出了一种把个体之间的Pareto支配关系转化成分割区间索引值的排序关系的目标空间分割算法；在目标空间分割算法的基础上,设计了一种简单、高效的基于分割区间索引值的环境选择操作算子。该算子不需要比较个体之间的支配关系,而是根据个体在当前搜索目标空间的分割区间索引值来完成多目标进化算法中的环境选择操作。在对当前搜索目标空间进行分割时,无法避免在同一分割区间内存在多个个体,为了保持群体的分布性,本文设计了一种快速的优先选择最接近分割区间原点的个体拥挤机制。
2、针对提出的OSD-MOEA算法,本文进行了大量的仿真实验,通过计算一组有代表性的测试函数,与目前性能较好的多目标进化算法NSGA2和基于目标空间分割的PSFGA进行比较,分析了OSD-MOEA的各项性能。结果表明该算法提高了算法的运行效率,降低了算法的时间复杂度。
3、针对网格中相互独立的多任务调度问题,本文提出了一种基于费用-时间的网格任务调度算法(C&T-OSD-GTSA)。算法结合了OSD-MOEA算法的空间划分排序的思想,通过对网格中相互独立的多任务问题进行建模,针对费用和时间权重的不同,进行了仿真实验。实验结果表明,C&T-OSD-GTSA在算法的收敛性和Pareto解集的分布性上都取得了满意的效果。
暂无评论