欢迎来到知嘟嘟! 联系电话:13095918853 卖家免费入驻,海量在线求购! 卖家免费入驻,海量在线求购!
知嘟嘟
我要发布
联系电话:13095918853
知嘟嘟经纪人
收藏
专利号: 2019104145943
申请人: 杭州电子科技大学
专利类型:发明专利
专利状态:已下证
专利领域: 计算;推算;计数
更新日期:2024-01-05
缴费截止日期: 暂无
价格&联系人
年费信息
委托购买

摘要:

权利要求书:

1.一种基于平衡探索与利用的蒙特卡洛树搜索方法,其特征在于,包括以下步骤:S01:选择阶段:从搜索树的根结点开始,根据节点的uct值向下寻找未扩展完全的节点;

S02:扩展阶段:从就绪队列中随机选择一个任务,选择可以执行的处理器,以此作为扩展节点;

S03:模拟阶段:从扩展节点开始,随机从就绪队列中选择任务,贪心地选择处理器,直到就绪队列中任务为空为止;

S04:回传阶段:根据模拟阶段获得的makespan值,回传更新从根节点到新的扩展节点之间的所有节点;

S05:重复上述步骤S01-S04,直到满足迭代次数限制或时间限制,最终返回一个最小的makespan值。

2.根据权利要求1所述的一种基于平衡探索与利用的蒙特卡洛树搜索方法,其特征在于,所述步骤S01还包括:若树节点已经扩展完全,则根据UCT公式计算出最大的UCT值作为搜索路径中新的节点。

3.根据权利要求2所述的一种基于平衡探索与利用的蒙特卡洛树搜索方法,其特征在于,所述UCT值的计算按如下公式计算求出,其中,c是一个常量参数,主要用于再平衡探索和利用间的权重;Q(v')表示当前任务节点的累积回报;N(v')表示当前任务节点的访问次数;N(v)表示当前任务节点的父亲节点的访问次数;V(s)表示当前节点在t次模拟时访问了s次的方差再加上 其中Xt表示t次模拟时的平均Q(v')值, 表示总的平均Q(v')值。

4.根据权利要求3所述的一种基于平衡探索与利用的蒙特卡洛树搜索方法,其特征在于,所述步骤S02还包括:扩展节点时需对该节点进行初始化,设置Q(v')=0,N(v')=0。

5.根据权利要求3或4所述的一种基于平衡探索与利用的蒙特卡洛树搜索方法,其特征在于,所述步骤S04包括:更新任务节点访问次数以及任务节点累计回报值。

6.根据权利要求5所述的一种基于平衡探索与利用的蒙特卡洛树搜索方法,其特征在于,所述任务节点访问次数N(v')的更新方式为N(v')=N(v')+1,任务节点累计回报Q(v')的更新方式为:Q(v')=Q(v')+makespan。