基于三值光学计算机的模拟退火优化算法设计与实现

作     者：何强强 

作者单位：阜阳师范大学 

学位级别：硕士

导师姓名：王先超

授予年度：2023年

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

主      题：三值光学计算机 干扰模型 监测模型 并行 功耗 效率 

摘      要：三值光学计算机底层采用三值逻辑运算,在大规模的运算效率上远优于传统的电子计算机,并且三值光学计算机采用市场上常见的液晶作为运算部件,相比于传统的电子计算机能耗更低。不仅如此,三值光学计算机还具有强大的并行能力,面对模拟退火算法时,能够轻松的实现并行运算,提高求解的质量。而模拟退火算法在传统计算机上求解旅行商问题时存在几个突出的问题。首先,随着问题规模的增大,求解的效率逐渐降低;其次,由于大规模的运算,使得能耗加速上升;最后,传统电子计算机通常采用串行的运算方式,使得模拟退火算法的搜索范围过小,造成解的质量降低。为了解决这些问题,本文提出基于三值光学计算机的并行模拟退火算法。在本文提出干扰和监测两种不同的并行模型来不断优化模拟退火算法的求解效率和求解质量。在对比传统计算机的基础上,提出基于三值光学计算机的干扰模型。这种模型将一个大的光学处理器等分成多个小光学处理器,多个小光学处理器之间独立、并行处理模拟退火算法,通过一个单独的小光学处理器对在多个小光学处理器上运行的模拟退火算法进行干扰操作,收集每个退火温度下最好的解并作为下一温度的初始解重新分发到各个小光学处理器上,直到降温结束,得到全局最优解。由于各个小光学处理器并行搜索,从而有效提高了算法的求解效率和求解质量,通过大量的实验,验证了该模型算法优于传统的模拟退火算法。由于模拟退火算法的Metropolis准则会在一定程度上错过全局最优解,因此,在基于三值光学计算机的干扰模型基础上,进一步提出基于三值光学计算机的监测模型。该模型增加一个小光学处理器,记录全局过程最好的一个解并在模拟退火算法结束后输出这个结果。通过实验的验证,表明了该模型的解总是优于干扰模型算法。本文在提出的两大模型基础上进一步分析了功耗和时间复杂度等问题,验证了三值光学计算机相比于传统电子计算机的优越性,为三值光学计算机的进一步研究提供了新思路。