论文部分内容阅读
最优化问题包括连续优化问题和离散优化问题,对于连续优化问题中的多模函数问题和离散优化问题中的非确定多项式(Non-Deterministic Polynomial,NP)难问题,智能算法求解这些问题时,如果不对其改进调整,就很容易陷入局部最优,因此本文选择应用最为普遍的四种智能算法,在原算法的基础上进行修正完善,来求解一些比较复杂的连续型最优化问题(如连续型函数优化问题)和离散型组合优化问题(如旅行商(Travelling Salesman Problem, TSP)问题、应用于层次优化的聚类问题、带有约束条件的任务调度问题),从而得到比原基本算法更理想的优化效果。 论文的主要工作包括以下四个部分: (1)针对基本萤火虫群优化算法在函数优化过程中容易出现精度不高、早熟等不足,提出了一种基于精英学习的量子行为萤火虫群优化算法,以解决连续函数的优化问题。在初始化种群阶段,采用 Logistic映射混沌机制以提高初始种群的随机性和多样性;在自适应动态步长搜索的萤火虫位置移动中,对那些因轮盘赌法则而未选中的个体,采取随机的量子行为策略进行更新,对越界个体重新初始化,以保证每个个体都有不同变化,提高寻优概率;最后采用适应度评估选出的精英个体采取动态逼近学习策略,进一步提高了算法的局部搜索能力。通过对CEC2014基准函数(Benchmark functions)进行测试,结果表明改进后的人工萤火虫群优化算法比其它优化算法有更快的收敛速度和更高求解精度。 (2)针对基本免疫算法在求解离散优化问题(TSP问题)问题过程中出现的收敛过慢和封闭竞争问题,提出一种混合免疫算法(Hybrid immune algorithm, HIA)。该算法采用混合式方法,免疫算法被用于全局搜索,贪心算法则用于初始化种群并和去交叉算子一起进行局部寻优。在更新个体时,免疫算法采用高频变异算子,此算子在动态自适应变化的变异概率下进行工作,改善了种群的多样性,更易找到潜在的更有效的搜索方向,减少盲目搜索,使得子代种群朝着更有利的方向探寻,从而迅速搜索到更高质量的解区域。实验结果表明,与其它算法相比较,HIA算法能找到更加理想的全局最优解,并且性能更为稳定。实验证明 HIA算法是一种解决离散优化问题的有效算法。 (3)针对大规模 TSP问题求解效率不高的问题,通常的作法是层次求解。首先采用聚类算法把大规模TSP问题转化成若干个小规模的城市集合,然后把这个问题看作是广义旅行商问题(Generalized Traveling Salesman Problem,GTSP)。在基本入侵杂草优化算法(Invasive weed optimization algorithm,IWO)基础上,提出了一种求解聚类问题的云模型入侵杂草优化算法。该算法使用云模型入侵杂草优化算法引导 k-均值算法的搜索,使其种群在进化过程中具有明确的方向性,从而改善算法的寻优能力。为了验证所提算法的效率,针对三个聚类问题进行相应实验,实验结果表明该算法不仅具有较高的正确率和较快的收敛速度,而且还具有较强的稳定性。 (4)作业调度的实质就是实现依赖型子作业集到处理机集的映射,并寻求最好的分配方案,以获得最小化的最大完工时间(makespan)。此问题是一个带有约束条件的组合优化问题,一般情况下是一个非确定性多项式-时间-难问题(NP难问题)。为了较好解决这个问题,采用人工化学反应优化方法(artificial chemical reaction optimization algorithm,ACROA),模拟化学反应过程中主要的五种分子操作,使反应物彼此相互作用以达到最小焓(势能)状态,提出了求解依赖型作业调度问题的人工化学反应优化算法(ACROAJS)。实验结果表明,与文献中其它两种解决方案相比,所提算法提高了网格计算环境中的作业调度质量,使调度的makespan减少约5.06%。 论文最后对改进后的这四种比较有代表性的智能算法进行了总结,并提出了本人未来进一步的研究方向。