论文部分内容阅读
最优化问题在科学研究和环境工程中广泛存在,如何高效地求解现实世界中的优化问题是人工智能领域内重要的研究课题。传统求解最优化问题的方法在特定条件下可以得到理论最优解,但是对于大规模多约束优化问题往往求解困难。因此,本文以一种高效智能算法——模因算法作为基本框架,面向现实世界中不同的最优化问题,分别提出有针对性的算法改进策略,以在可接受时间范围内提供令人满意的解决方案。在优化问题层面,着重解决四个工程优化问题,包括片上网络调度问题、短波广播资源调度问题、能耗感知短波广播资源调度问题以及K摄像头放置问题。在算法设计层面,针对上述问题特点分别提出基于多启发式的模因算法、基于辅助目标的模因算法、基于推拉算子的多目标模因算法以及基于最大最小蚁群系统的模因算法。具体来说,本文主要研究成果和创新点包括:(1)提出了基于多启发式模因算法求解片上网络调度问题。首先,提出优化重叠通信路径的冲突程度来减少路径冲突的过度近似。其次,通过在调度阶段引入通信时延来避免时间上的通信冲突。再次,针对异构片上网络,提出两阶段映射以节省最大完成时间和通信花费。最后,针对该三目标优化问题(最小化最大完成时间、最小化能耗花费以及最小化冲突程度),提出基于多个问题相关启发式策略以及模因算法框架的多启发式多目标模因算法。启发式策略包括面向拓扑排序的任务聚类启发式、容量敏感的聚类改善启发式以及面向通信的螺旋映射启发式。此外,在模因算法的全局搜索阶段,采用带有非支配排序和拥挤距离的经典多目标遗传算法。在模因算法的局部搜索阶段,采用基于插入操作的帕累托局部搜索对优秀个体进行改进。实验表明,所提出的多启发式模因算法性能出众,尤其在大规模测试用例上优势明显。(2)提出了基于辅助目标模因算法求解短波广播资源调度问题。为了解决由于种群多样性不足而导致的提前收敛(早熟)现象,算法引入种群多样性作为辅助目标,将原始单目标优化问题转化为双目标优化问题。为了高效求解该转化问题,提出一个非均匀加权切比雪夫分解方法,重点关注原始优化目标以节省计算资源。此外,还采用并行分组技术对多个分解的子目标同时求解,以达到提高算法效率的目的。模因算法全局搜索阶段采用遗传算法重组父代解结构,在局部搜索阶段设计了基于指向性干扰的操作,当搜索过程陷入停滞时帮助跳出局部最优困境。仿真实验以中国境内短波广播节目和设备分布为实例,通过与当前最优求解方法的结果对比验证了所提算法的有效性。(3)提出了基于推拉算子多目标模因算法求解能耗感知短波广播资源调度问题。该研究内容出于可持续发展考量,首次提出能耗感知的短波广播资源调度问题,同时优化检测站点数目和能耗目标。针对该问题,设计了基于推拉算子的初始化过程处理带约束的多目标优化问题,加快算法收敛速度。此外,对于不同个体采用动态资源分配策略,充分利用精英个体对于种群优胜劣汰的贡献。在模因算法全局搜索阶段,仍然采用遗传算法对解空间进行探索。而在模因算法的局部搜索阶段,提出基于交换和分配两种算子的快速聚合局部搜索方法对个体进一步改进。大量实验表明,所提算法较好地解决了该能耗感知短波广播资源调度问题。(4)提出了基于最大最小蚁群系统模因算法求解K摄像头放置问题。针对最优摄像头放置问题场景下资源受限的情况,首次提出K摄像头放置问题,旨在满足摄像头数量不足的情况下尽可能监控最广泛的空间,为完善监控系统各项功能提供前期保障。针对该问题,首先提出双层选择启发式策略对贪心放置摄像头的方法进行细化。其次,采用基于记忆蚂蚁的最大最小蚁群系统作为模因算法的全局搜索策略,在保留优秀解结构的同时产生多样性较好的蚁群。作为模因算法的局部搜索策略,进一步提出运用打分函数和延迟格局检测来平衡算法的探索性与开发性。通过与当前最优算法比较,得出该模因算法性能更优的结论。