类选择排序的可逆逻辑综合算法

可逆逻辑综合是指对给定的可逆函数自动构造对应的可逆逻辑电路.由于搜索空间随电路规模增长成指数增长,现有的可逆逻辑综合算法虽然能够得到近似最优的解,但是都存在计算时间过长的问题.文中提出了一种类似选择排序的可逆逻辑综合算法,其实质为基于变换规则的合成法.它采用一个无向无权图表示所有可以进行变换的路径,在综合的过程中,采用选择排序思想每次从小到大的选择需要交换的输出项,然后从路径选择图中找到最优的路径进行变换,最终使得函数的输出序列有序即完成综合.此外,文中还对得到的量子电路进行了优化.实验表明,相比其它综合算法,该算法不仅总能获得最优解或近似最优解,而且效率高、易于实现.     

量子可逆逻辑电路综合的快速算法研究

可逆逻辑有许多应用,尤其在量子计算领域,量子可逆逻辑电路是构建量子计算机的基本单元,量子可逆逻辑电路综合就是根据电路功能,以较小的量子代价自动构造量子可逆逻辑电路.文中结合可逆逻辑电路综合的多种算法,提出了一种新颖高效的算法,自动构造正极性Reed-Muller展开式(RM),在生成量子可逆逻辑电路的解空间树上,采用总体层次遍历,局部深度搜索,借鉴模板优化技术,构造限界函数快速剪去无解或非最优解的分枝,优先探测RM中的因子,以极高的效率生成最优电路.以国际公认的3变量可逆函数测试标准,该算法不仅能够生成全部最优电路,而且运行速度远远超过同类算法.     

基于带权有向图的可逆逻辑综合改进算法

为减少可逆逻辑综合中使用的可逆门,通过对基于带权有向图的可逆逻辑综合算法的分析,针对函数转换过程中过渡门数较多及电路优化算法简单的问题,提出了有效的等复杂度基本输出变换的概念,扩充并证明了Toffoli门序列的移动和化简规则,给出了改进的基于带权有向图的可逆逻辑综合算法。实验结果表明,该算法不仅减少了可逆电路构成时所使用的可逆门,而且对构建的可逆电路实现了有效化简,大幅度减少了门数和控制位数,降低了可逆电路代价。     

基于关联选择的可逆逻辑综合算法

可逆逻辑综合是可逆计算的重要内容,为了解决可逆逻辑综合中可逆电路构造和优化问题,提出一种基于关联选择的可逆逻辑综合算法及相应的优化算法.将可逆函数用真值表表示,按真值表从上往下的顺序综合,并若干相关联变量作为综合的目标位,分别计算相对混乱度和绝对混乱度,以最小混乱度原则选取可逆逻辑门.该算法及其优化算法的时间复杂度为O(n2×2n),空间复杂度为O(n×2n),优于最佳算法的空间复杂度O(2n!).通过C++语言实现对3变量全部函数及部分4变量函数的综合,并与其他可逆逻辑综合算法的结果及benchmark范例比较,结果表明平均门数均具有一定优势.     

基于规则的可逆Toffoli电路优化算法

可逆电路的优化是可逆逻辑综合的关键问题之一.为了解决可逆Toffoli电路优化问题中算法复杂度高和电路规模可扩充性差的问题,分析归纳了相邻Toffoli门的关系,提出并证明了可逆Toffoli电路中子序列的移动和化简规则,并基于这些规则给出了可逆Toffoli电路的优化算法.根据移动规则对可逆电路进行正向和反向扫描,寻找满足化简规则的子序列进行优化,直到可逆电路不发生变化为止.该优化算法与可逆电路的输入线数无关,无需存储额外信息,适用于各种不同类型的Toffoli电路合成方法,算法复杂度为O(s3),优于通常使用的模板优化的复杂度O(n!t2s3).在具体实例和国际认可的所有3变量可逆函数上的验证结果表明,该优化算法能有效地减少可逆电路的门数和控制位数,降低可逆电路的代价.     

基于矩阵初等变换的量子可逆逻辑电路双向综合算法

基于矩阵初等变换,提出了量子可逆逻辑电路双向综合算法。该算法依据两数字间的汉明距离,通过交换矩阵行号或矩阵元素对量子可逆逻辑电路的矩阵进行初等行变换。在变换的过程中,利用邻接矩阵的电路转化规则,生成任意给定置换的量子可逆逻辑电路。与其它同类算法相比,由于不需要穷尽搜索,该算法的时空复杂度有大幅降低;又由于采用任意n量子扩展通用Toffoli门,该算法可综合任一置换(奇或偶置换)的量子可逆逻辑电路,并且电路中门的数量有所减少。     

逻辑函数适于双逻辑实现的探测算法

提出一种判定逻辑函数是否适于双逻辑实现的探测算法,直接从XOR逻辑的特点出发,即2个汉明距离为2 的最小项可以由 XOR 逻辑表示.通过计算函数最小项之间的汉明距离分析其所具有的逻辑模式,给出探测适用于双逻辑实现的判断条件.该算法已用 C 语言实现,并应用于 MCNC benchmark 电路的判定测试,实验结果验证了其有效性.     

量子可逆逻辑综合的关键技术及其算法

最优化量子可逆逻辑的关键在于用最小的量子代价自动构造量子可逆逻辑.为了提高可逆逻辑自动生成与优化的效率,提出了类模板技术和一种快速算法.模板技术是一个有效的优化工具,类模板技术可以显著提高模板技术的匹配效率;R-M算法是可逆逻辑综合的一种较好的迭代方法,基于R-M算法的原始思想,构造了一个Hash函数,并在此基础上提出了一种可逆逻辑综合的快速算法.实验结果表明,在同等实验环境下使用类模板技术与快速算法,其优化的效果与效率远远优于已知的其他算法.     

基于均值改进控制策略的昂贵约束并行代理优化算法

针对具有黑箱特性的昂贵约束优化问题及工程中计算资源利用率不高问题,提出了新的基于均值改进控制策略的并行代理优化算法.该算法为了减少仿真建模计算负担,选取Kriging近似模型对目标函数和约束函数进行近似估计.在Kriging模型基础上,利用均值改进与新增试验样本间的不等关系构建具有距离特性的控制函数.算法的均值改进控制策略通过控制函数调整最大改进值,实现样本设计空间的多点填充.算法适用范围:1)计算成本主要来自于仿真估计而非优化;2)复杂的工程或商业软件内部无法修改的昂贵仿真问题.数值算例和仿真案例表明:该算法可有效获取近似最优解,减少仿真试验次数的同时弱化均值改进准则的贪婪特性.相比于其他多点填充策略,均值改进控制策略可有效提升算法计算效率.此外,算法获取优化问题近似最优解的稳定性和精度均具有一定优势.     

基于汉明距离的改进粒子群算法求解旅行商问题

针对传统粒子群算法不适合求解离散型问题,提出一种基于汉明距离的改进粒子群算法。该算法保留了粒子群算法的基本思想和流程,并基于汉明距离为粒子定义了一种新型的速度表示。同时,为了使算法寻优能力更高、避免迭代过程陷入局部最优无法跳出,设计了2-opt和3-opt算子,结合随机贪婪规则,使求解质量更高、收敛更快。在算法后期,为了提高粒子在整体解空间中的全局搜索能力,采用一部分粒子重新生成的方式去重新探索解空间。为了验证算法的有效性,采用了众多旅行商问题（TSP）标准算例进行测试。实验结果表明,对于小规模TSP,该算法可以找到历史最优解;对于大规模TSP,如城市数在100以上的问题,也可以找到满意解,与已知最优解之间偏差度较小,通常在5%以内。     

基于位运算的量子可逆逻辑电路快速综合算法

量子可逆逻辑电路是构建量子计算机的基本单元.本文结合可逆逻辑电路综合的多种算法,根据可逆逻辑电路综合的本质是置换问题,巧妙应用位运算构造高效完备的Hash函数,提出了基于Hash表的新颖高效的量子可逆逻辑电路综合算法,可使用多种量子门,以极高的效率生成最优的量子可逆逻辑电路,从理论上实现制造量子电路的成本最低.按照国际同行认可的3变量可逆函数测试标准,该算法不仅能够生成全部最优电路,而且运行速度远远超过其它算法.实验结果表明,该算法按最小长度标准综合电路的平均速度是目前最好结果的69.8倍.     

最小生成树灵敏度分析算法研究

在最小生成树数学性质的基础上,给出最小生成树灵敏度分析算法.该算法在图的各种属性发生变化(如边的权值变化、增加或删除边或结点)的情况下,在原有最小生成树的基础上快速调整,而不是从头计算来得到新的最优解.算法还给出了每边权值在何范围内变化时,最优解不变.最后通过一个示例来说明算法的原理及应用.     

化学反应蚁群优化算法

针对化学反应优化对反馈信息利用不足导致后期求解效率低的问题,提出化学反应蚁群优化算法.该算法利用化学反应优化生成较优解,通过信息素转换策略将较优解转换为蚁群算法的初始信息素,最后由蚁群算法累积更新信息素得到最优解.以TSP为例进行仿真,结果表明,与化学反应优化、蚁群算法、模拟退火算法相比,所提算法具有更高的寻优能力、收敛效率和计算效率.     

基于L-ESOP约简的量子线性电路逻辑综合算法

为生成在门数指标上近最优的量子线性电路,提出一种基于L-ESOP表达式约简的量子线性电路逻辑综合算法.首先通过异或运算逐步将量子线性电路每个输出的L-ESOP表达式约简成fi=xi的恒等函数形式,算法执行过程中的每次异或运算均对应一个CNOT门,将这些CNOT门逆序排列便得到结果电路;为进一步降低门数,提出3种前瞻性启发式规则,将这些规则分别应用于算法的3个不同阶段,以最大幅度地减少后续异或操作次数为衡量指标选择算法相应阶段参与异或运算的L-ESOP表达式.实验结果表明,文中算法在综合量子线性电路时所需的CNOT门数少于其他算法,且这种优势随着线路数的增加越发明显,在生成100线电路时所需的平均门数较其他算法降低了21.69%;另外,该算法可在多项式时间内完成,在生成100线电路时平均耗时仅用71.55 ms.     

解决无线传感器网络能量洞问题的贪婪算法

无线传感器网络中的能量洞问题是影响网络寿命的关键因素之一。在基于环模型的多跳传感器网络中,通过优化所有环的传输距离可以有效地延长网络寿命。提出了一种近似的贪婪算法（ASGT）,该算法将最优传输距离序列问题转化为最优生成树问题,在降低搜索（算法）复杂度的同时得到与最优解近似的结果。模拟实验证明了采用ASGT算法的网络寿命逼近于理想最优序列下的网络生命时间,并且与已有的文献算法相比,ASGT可以延长网络寿命两倍以上。     

基于Hash表的量子可逆逻辑电路综合的快速算法

量子可逆逻辑电路是构建量子计算机的基本单元,通过量子门的级联与组合构成量子计算机,量子可逆逻辑电路的综合就是根据电路功能,以较小的量子代价自动构造量子可逆逻辑电路.结合可逆逻辑电路综合的多种算法,提出了一种新颖高效的量子电路综合算法,巧妙构造最小完备的Hash函数,可使用多种量子门,采用任意量子代价标准,以极高的效率生成最优的量子可逆逻辑电路.为实现量子电路综合的自动化,首次提出了利用量子线的置换自动构造各种量子门库的通用算法.采用国际同行认可的3变量可逆函数测试标准,该算法不仅能够生成全部最优电路.而且运行速度远远超过其他算法·实验结果表明,该算法按最小长度、最小代价标准综合电路的平均速度分别是目前最好结果的49.15倍、365.13倍.     

基于近似计算与多数覆盖技术的电路面积优化

针对基于最小项的近似计算技术不适合解决大规模电路面积优化问题,提出一种采用乘积项和逻辑覆盖的电路面积近似计算技术优化算法.利用基于乘积项的多数覆盖技术实现近似逻辑函数搜索,用逻辑覆盖不相交运算实现近似函数错误率计算,可以有效地避免因输入变量增加和最小项数量激增导致算法效率低下甚至无法工作的问题.文中算法用C编程并经MC...     

对数/指数算法的改进及其VLSI实现

提出了一种二进制数的指数/对数运算的线性近似的改进算法,并VLSI实现。该算法能较好地提高精度,相比于现有最新文献提出的算法,对数运算的相对误差减少了46.1%,指数运算的相对误差减少了32.2%。实现时,设计了前导1探测电路和减小误差的误差补偿电路。该算法VLSI实现简单,只需组合逻辑就能在一个时钟周期内得到计算结果。     

面向防汛物资动态变化的运输车辆调度优化算法研究

为解决防汛救灾过程中受灾需求变化下的防汛物资调度问题,提出一种面向防汛物资动态变化的运输车辆调度优化算法(SOA_TV).在SOA_TV算法中,考虑车辆限载、调度车辆数量、移动距离等约束,建立防汛物资运力调度优化模型.依据已知受灾信息和仓储信息,确定受灾最小所需车辆数,获得待运输物资集合,并按照最近邻原则初始化车辆集合.引入车辆移动距离阈值,通过边权计算构建二分图,并进行矩阵转换,获得一个低维度的矩阵.最后,考虑需求不变化和动态变化两种情况下的物资分配,根据仓库点之间的运输距离和车辆负载情况更新边权值,多次执行KM算法直到获得目标模型的近似最优解.实验结果表明:在多种实验场景中,SOA_TV都能寻找到一个较优解.相比于GA和ABC,SOA_TV虽然略微降低了车辆移动总距离,但其运算时间获得大幅度削减,可在极短的时间内计算获得较优的车辆分配方案.相较于Hungarian,SOA_TV可降低运行时间和车辆移动总距离.     

移动云环境面向多重服务选择的计算卸载算法

移动云计算可以通过计算卸载改善移动设备的能效和应用的执行延时。然而面对云端的多重服务选择时,计算卸载决策是NP问题。为了解决这一问题,提出一种遗传算法寻找计算卸载的最优应用分割决策解。遗传种群初始化中,算法联立预定义和随机染色体方法进行初始种群的生成,减少了无效染色体的发生比例。同时,算法为预定义的预留种群设计一种特定的基于汉明距离函数的适应度函数,更好地衡量了染色体间的差异。种群交叉中分别利用近亲交配与杂交繁育丰富了种群个体。算法通过修正的遗传操作减少了无效解的产生,以更合理的时间代价获得了应用分割的最优可行解。应用现实的移动应用任务图进行仿真实验评估了算法效率。评估结论表明,所设计的遗传算法在应用执行能耗、执行时间以及综合权重代价方面均优于对比算法。