面向网络资源分配的量子近似优化算法研究

作     者：何婉莹 

作者单位：沈阳航空航天大学 

学位级别：硕士

导师姓名：拱长青;闻英友

授予年度：2023年

学科分类：12[管理学] 1201[管理学-管理科学与工程(可授管理学、工学学位)] 081104[工学-模式识别与智能系统] 08[工学] 0835[工学-软件工程] 0811[工学-控制科学与工程] 0812[工学-计算机科学与技术（可授工学、理学学位）] 

主      题：资源分配 量子近似优化算法 移动边缘计算网络 车载自组织网络 

摘      要：近年来,组合优化问题得到广泛研究,其中包括路径规划、无线调度等经典问题。网络资源分配问题属于组合优化中调度问题的一种,在求解时得到问题正确解的概率较低。针对此问题,本文采用量子近似优化算法(Quantum Approximate Optimization Algorithm,QAOA)求解网络资源分配问题。它是经典算法与量子算法的结合,可以利用量子计算的高并行性,提高计算能力,目的是让QAOA可以较高概率获得网络资源分配问题的解。针对移动边缘计算网络和车载自组织网络中资源分配问题的特点,设计基于伊辛模型的QAOA进行资源分配问题求解。考虑通信延迟和负载两项指标设置问题的目标函数与约束条件,根据目标函数引入伊辛模型设置问题的初始哈密顿量和目标哈密顿量,然后理论推导初始和目标哈密顿量分别对应的量子门,设计适用于求解资源分配问题的量子门线路。最后通过实验对比不同优化器和不同步长对QAOA性能的影响。针对移动边缘计算网络架构中由于用户移动性而带来的资源分配困难问题,设计基于预测的动态资源分配方案实现实时更新资源分配方案。然后分别对比没有预测辅助的静态资源分配和存在预测算法辅助的动态资源分配的性能。结果表明,相较于静态方案来说,动态方案可以有效降低资源分配不均引起的部分服务器过载和网络延迟过大的问题。针对QAOA本身在低迭代水平求得正确解概率较低的问题,本文改进目标哈密顿量的设置方法,考虑问题的约束条件,并且设计一种新的量子线路去简化求解过程,提高成功概率。在车载自组织网络资源分配问题上验证不同目标哈密顿量对求解结果的影响。结果显示,虽然两种哈密顿量均可求得正确解,但是改进后的哈密顿量将得到正确解的概率由54.15%提升到82.9%。且平均执行时间为原来的20.8%。