基于FPGA的组合优化求解方法及装置

    专利2024-12-16  11


    本发明涉及计算机,尤其涉及一种基于fpga的组合优化求解方法及装置。


    背景技术:

    1、组合优化问题是一类典型的非确定性多项式时间(non-deterministicpolynomial,np)难问题,如旅行商问题(traveling salesman problem,tsp)、背包问题、调度问题、物流供应以及社会科学中的人群意向倾向等问题。这些问题需要在给定一组约束条件下找到最优解,其中最优解通常是指最小化或最大化某种特定目标函数。

    2、传统的组合优化问题求解方法包括:中央处理器(central processing unit,cpu)计算、图形处理器(graphics processing unit,gpu)并行计算以及一些新兴的技术,如量子计算机等。

    3、但是,传统的组合优化问题求解方法在某些情况下可能会面临挑战,cpu计算速度可能受到限制,而gpu虽然能够提供并行性,但对于一些复杂问题的性能提升有限,量子计算机尚处于研发阶段,尚未广泛应用。亟待寻求一种高效且可扩展的解决方案,以满足目前组合优化问题求解的需求。


    技术实现思路

    1、本发明提供一种基于fpga的组合优化求解方法及装置,用以解决传统的组合优化问题求解方法在某些情况下可能会面临挑战的问题。

    2、本发明提供一种基于fpga的组合优化求解方法,包括:

    3、将预先设置的模拟分叉算法在现场可编程逻辑门阵列fpga上进行硬件实现,得到基于fpga的组合优化问题求解器;

    4、通过所述基于fpga的组合优化问题求解器对预先设置的组合优化问题进行求解,得到组合优化求解结果。

    5、根据本发明提供的一种基于fpga的组合优化求解方法,所述通过所述基于fpga的组合优化问题求解器对预先设置的组合优化问题进行求解,得到组合优化求解结果,包括:

    6、在所述fpga上,对预先设置的哈密顿函数hbsb中的n个变量并行求偏导,得到2n个偏微分方程;其中,所述hbsb与所述组合优化问题相关,n为大于0的整数,n表征自旋玻璃态问题中的待求解自旋个数;

    7、通过对所述2n个偏微分方程求解来对所述组合优化问题进行求解,得到所述组合优化求解结果。

    8、根据本发明提供的一种基于fpga的组合优化求解方法,所述通过对所述2n个偏微分方程求解来对所述组合优化问题进行求解,得到所述组合优化求解结果,包括:

    9、通过欧拉算法或模拟非线性哈密顿系统中的绝热演化算法,确定所述2n个偏微分方程的优化解,作为所述组合优化求解结果。

    10、根据本发明提供的一种基于fpga的组合优化求解方法,在所述通过所述基于fpga的组合优化问题求解器对预先设置的组合优化问题进行求解,得到组合优化求解结果之前,所述方法还包括:

    11、通过预先设置的输入输出io通信接口,接收用户指定需要求解的优化函数;

    12、所述通过所述基于fpga的组合优化问题求解器对预先设置的组合优化问题进行求解,得到组合优化求解结果,包括:

    13、通过所述基于fpga的组合优化问题求解器对所述组合优化问题中的所述优化函数进行求解,得到所述组合优化求解结果。

    14、根据本发明提供的一种基于fpga的组合优化求解方法,在所述通过所述基于fpga的组合优化问题求解器对预先设置的组合优化问题进行求解,得到组合优化求解结果之后,所述方法还包括:

    15、通过所述io通信接口,将所述组合优化求解结果发送至所述用户;

    16、其中,所述组合优化求解结果包括中间求解结果和最终求解结果中的至少一项。

    17、根据本发明提供的一种基于fpga的组合优化求解方法,所述方法还包括:

    18、利用预先设置的数据存储模块,存储所述组合优化问题对应的问题实例、算法参数、中间求解结果和最终求解结果中的至少一项。

    19、本发明还提供一种基于fpga的组合优化求解装置,包括:

    20、处理模块,用于将预先设置的模拟分叉算法在现场可编程逻辑门阵列fpga上进行硬件实现,得到基于fpga的组合优化问题求解器;

    21、求解模块,用于通过所述基于fpga的组合优化问题求解器对预先设置的组合优化问题进行求解,得到组合优化求解结果。

    22、本发明还提供一种电子设备,包括存储器、处理器及存储在存储器上并可在处理器上运行的计算机程序,所述处理器执行所述程序时实现如上述任一种所述基于fpga的组合优化求解方法。

    23、本发明还提供一种非暂态计算机可读存储介质,其上存储有计算机程序,该计算机程序被处理器执行时实现如上述任一种所述基于fpga的组合优化求解方法。

    24、本发明还提供一种计算机程序产品,包括计算机程序,所述计算机程序被处理器执行时实现如上述任一种所述基于fpga的组合优化求解方法。

    25、本发明提供的基于fpga的组合优化求解方法及装置,将模拟分叉算法与fpga结合起来对组合优化问题进行求解,利用fpga的并行计算能力,实现了组合优化问题的高效求解,加速了决策过程;利用fpga的高度定制性,可以根据特定组合优化问题的要求进行硬件设计,将其优化为问题的特定特征;利用fpga的低延迟特性,能够缩短数据传输时的通信用时,更快更高效的完成程序所需的输入输出,对于实时应用,如交通信号灯优化或机器人路径规划,低延迟是至关重要的,因为它确保了即时响应和决策的实现,本发明的方法可以很好地适应;利用fpga的低功耗特性,可以适应于需要长时间运行或移动设备上的使用,在许多组合优化问题中,长时间计算是必要的,因此低功耗有助于减少能源消耗和热量产生;另外,fpga可以提供硬件加速,相对于纯软件实现,通常能够实现更快的计算速度;fpga不一定是一个独立的fpga芯片,还可以通过fpga集群实现高度可扩展性,可以处理大规模的问题。综上,本发明利用fpga芯片的特殊优势,通过硬件设计模拟分叉算法,以实现组合优化问题的高效求解,具有广泛的适用性,能够满足各种不同领域的需求。



    技术特征:

    1.一种基于fpga的组合优化求解方法,其特征在于,包括:

    2.根据权利要求1所述的基于fpga的组合优化求解方法,其特征在于,所述通过所述基于fpga的组合优化问题求解器对预先设置的组合优化问题进行求解,得到组合优化求解结果,包括:

    3.根据权利要求2所述的基于fpga的组合优化求解方法,其特征在于,所述通过对所述2n个偏微分方程求解来对所述组合优化问题进行求解,得到所述组合优化求解结果,包括:

    4.根据权利要求1至3任一项所述的基于fpga的组合优化求解方法,其特征在于,在所述通过所述基于fpga的组合优化问题求解器对预先设置的组合优化问题进行求解,得到组合优化求解结果之前,所述方法还包括:

    5.根据权利要求4所述的基于fpga的组合优化求解方法,其特征在于,在所述通过所述基于fpga的组合优化问题求解器对预先设置的组合优化问题进行求解,得到组合优化求解结果之后,所述方法还包括:

    6.根据权利要求1至3任一项所述的基于fpga的组合优化求解方法,其特征在于,所述方法还包括:

    7.一种基于fpga的组合优化求解装置,其特征在于,包括:

    8.一种电子设备,包括存储器、处理器及存储在所述存储器上并可在所述处理器上运行的计算机程序,其特征在于,所述处理器执行所述程序时实现如权利要求1至6任一项所述基于fpga的组合优化求解方法。

    9.一种非暂态计算机可读存储介质,其上存储有计算机程序,其特征在于,所述计算机程序被处理器执行时实现如权利要求1至6任一项所述基于fpga的组合优化求解方法。

    10.一种计算机程序产品,包括计算机程序,其特征在于,所述计算机程序被处理器执行时实现如权利要求1至6任一项所述基于fpga的组合优化求解方法。


    技术总结
    本发明提供一种基于FPGA的组合优化求解方法及装置,涉及计算机技术领域,基于FPGA的组合优化求解方法包括:将预先设置的模拟分叉算法在现场可编程逻辑门阵列FPGA上进行硬件实现,得到基于FPGA的组合优化问题求解器;通过所述基于FPGA的组合优化问题求解器对预先设置的组合优化问题进行求解,得到组合优化求解结果。本发明实施例利用FPGA芯片的特殊优势,通过硬件设计模拟分叉算法,以实现组合优化问题的高效求解,具有广泛的适用性,能够满足各种不同领域的需求。

    技术研发人员:张兴华,赵胜达,王良,王铭扬
    受保护的技术使用者:北京交通大学
    技术研发日:
    技术公布日:2024/4/29
    转载请注明原文地址:https://wp.8miu.com/read-80510.html

    最新回复(0)