论文部分内容阅读
全局优化和多目标优化问题是两类复杂的优化问题,它们在数学、工程、管理、军事等诸多领域有着广泛的应用,但是当问题为非线性全局优化和非线性非凸多目标优化问题时,对它们求解非常困难,研究它们高效的求解算法不仅具有重要的理论意义,而且具有广泛的应用价值。进化算法是求解这些复杂优化问题的一种智能优化算法,已经成功地解决了实际中许多复杂优化问题。随着进化算法研究和应用的不断深入,通过多种机制有机协同的进化算法已成为提高算法效率和改善其适应性的有效途径,尤其适合解决高维、非线性、不可微、多局部最优、多目标、动态不确定等复杂优化问题。本文针对高维非线性全局优化和非线性非凸多目标优化问题的高效进化算法进行了深入研究,提出了几种高效的进化算法,并以并行与分布式系统下的可分任务调度问题为实际应用背景,建立了一个任务优化调度模型,并设计了相应的进化算法对模型进行求解。具体工作如下：1、NSGA-Ⅱ(Non-dominated Sorting Genetic Algorithm-Ⅱ)算法是目前求解多目标优化问题的最有效算法之一,其中,聚集距离在NSGA-Ⅱ算法的收敛性和分布均匀性保持上起到重要的作用,但算法没有充分利用微观的个体本身和宏观的种群整体信息。为更合理地估计区域密度,使所求解集更好更均匀地收敛于Pareto最优边界,本文利用均匀聚集区间和基尼系数权重构造了一种均匀聚集距离算子,并基于该算子提出了一种改进的NSGA-Ⅱ算法。最后,通过对10个标准多目标测试问题的实验验证了算法的有效性。2、目标函数加权法是求解多目标优化问题最常用和最简单的方法。但是,对于非凸或者复杂多目标优化问题,这种方法无法求出Pareto前沿非凸部分的最优解,因而通常无法求出在整个Pareto前沿均匀分布的代表解集。为了解决这个问题,本文提出了一种新的基于自适应多适应度函数和空间划分进化算法。通过均匀设计将目标空间划分为相近大小的多个区域,每个区域由目标函数加权作为其适应度函数来搜索该区域内的非支配解。当某个区域包含较少的非支配解时,该区域会被划分为更小的子区域,且会为每个子区域添加一个新的适应度函数。因此,每个区域内的Pareto解将逐步得到更新,最终均匀地分布在整个Pareto前沿。最后,通过求解13个标准测试函数,将所提算法与10个已有算法进行了性能比较。结果表明所提算法的性能要优于已有算法,它不仅可以有效的解决非凸及复杂优化问题,而且可以在整个Pareto前沿找到分布均匀且宽广的解集。3、未成熟收敛以及收敛性能差等是目前进化算法面临的重要缺陷。为了进一步提高进化算法的全局搜索能力和避免算法陷入局部最优解,本文提出了一种基于基因多样性测度的自适应协同进化算法,并且证明了算法的全局收敛性。该算法以基因多样性测度为纽带,实现了算子之间的协同搜索；通过自适应的选择算子和变异算子维持了子种群的多样性,降低算法陷入局部最优解的可能性；通过自适应替换算子实现了各子种群信息之间的动态协同交换,提高了子种群交互信息价值潜力和算法的搜索能力。最后,通过7个函数优化实验验证了算法的有效性。4、针对并行与分布式系统下的可分任务调度这一实际应用问题,考虑到处理机的异构性,即处理机具有任意大小的通信速率、计算速率、计算启动开销和通信启动开销,本文以任务的最短完成时间为目标建立了一个新的优化模型。该模型可以解决以下三个问题：确定最优的参与计算的处理机数目、最优的处理机调度顺序,以及最优的任务分配方案。为了有效的求解该模型,本文设计了一种新的混合遗传算法,并证明了该算法以概率1收敛到全局最优解。为了加快算法的收敛,在算法中引入了局部搜索策略。最后,通过仿真实验验证了模型和算法的有效性。