2020102274478 一种基于遗传算法的区块链支付通道网络多路径寻径方法.pdf

(19)国家知识产权局

(12)发明专利

(10)授权公告号CN111429120B
(45)授权公告日2023.04.07
(21)申请号202010227447.8G06N3/126(2023.01)
(22)申请日2020.03.27(56)对比文件
(65)同一申请的已公布的文献号CN109583868A,2019.04.05
申请公布号CN111429120ACN110223055A,2019.09.10
US10305833B1,2019.05.28
(43)申请公布日2020.07.17US2019332921A1,2019.10.31
(73)专利权人武汉大学李松钊.基于区块链的物流服务交易蚁群智
地址430072湖北省武汉市武昌区珞珈山能合约算法应用研究《.南宁师范大学》.2020,全
武汉大学文.
(72)发明人陈艳姣朱笑天审查员邓雪彬

(74)专利代理机构北京睿智保诚专利代理事务
所(普通合伙)11732
专利代理师周新楣
(51)Int.Cl.
G06Q20/06(2012.01)
G06Q20/36(2012.01)权利要求书2页说明书9页附图3页
(54)发明名称
一种基于遗传算法的区块链支付通道网络
多路径寻径方法
(57)摘要
本发明公开了一种基于遗传算法的区块链
支付通道网络多路径寻径方法，为解决区块链链
下支付通道网络中可以最小化转发费用的多路
径寻径问题，将支付通道网络描述为一个具有某
些特定路由限制的特殊网络，使用遗传算法获得
最优的支付路径选择和支付金额分配方案。本发
明公开了一种基于遗传算法的区块链链下支付
通道网络中的多路径寻径方法，通过不断迭代产
生多样化解决方案，并从中挑选出较优的方案变
化为下一代的方法，以接近最优方案，从而得到
局部最优的多路径寻径方案，提高了通过支付通
道支付的成功率，并有效减少了支付过程中产生
的费用。
CN111429120B
CN111429120B权利要求书1/2页

1.一种基于遗传算法的区块链支付通道网络多路径寻径方法，其特征在于，包括：
S1：根据支付通道网络的结构构建一个有向图G，其中，图中的顶点用以参与交易的节
点，边表示支付通道，支付通道用以转发交易，支付通道的属性包括余额bal(u,v)、基础收
费系数base(u,v)和比例收费系数slope(u,v)，边的权为当前通道上流经的支付金额所产
生的收费Fee，Fee＝base(u,v)+slope(u,v)×p，表示转发交易的收费，p表示支付路径上的
支付金额，其中，支付路径为图G中的点构成的从发送方到接受方的路径，一条支付路径包
括一个或者多个支付通道；
S2：基于支付通道网络，生成初始种群，其中，初始种群中的每个个体对应k条支付路径

和每条路径上分配的支付金额P1,P2,…Pk，每条路径上分配的金额根据总金额平均分配；
S3：将每个个体对应的所有支付路径的总收费作为适应度，根据适应度选择出父辈，其
中，支付路径的收费为包含的每个支付通道的收费之和；
S4：根据适应度，对父辈进行交叉和变异操作；
S5：当种群收敛或者迭代次数达到设定阈值时，计算最后一代种群中每一个个体的总
收费，并选择总收费最小的个体作为当前k值下的最佳解决方案，当前k值下的最佳解决方
案为选择出的多条支付路径；
S6：从多条支付路径中选择出目标支付路径。
2.如权利要求1所述的方法，其特征在于，在步骤S2之前，所述方法还包括：
设置路径数量范围krange以及迭代次数阈值。
3.如权利要求1所述的方法，其特征在于，S2包括：

S2.1：将每个个体的k条路径初始分配金额均为平均分配，P1＝P2＝…＝Pk＝P/k，P表示
总金额；
S2.2：采用Dijkstra算法寻找k+1条收费最少路径，其中，每条路径上支付金额为P/k；
S2.3：从S2.2中的k+1条支付路径中选择出k条，生成一个个体；
S2.4：重复执行步骤S2.2～2.3，生成k+1个不同的个体，组成初始种群。
4.如权利要求3所述的方法，其特征在于，S3具体包括：
S3.1：适应度的计算公式为：
S3.2：以概率α选择totalFee最小的α*k个个体作为父辈，并淘汰其他个体，其中α为预
先设置的参数。
5.如权利要求1所述的方法，其特征在于，S4具体包括：
S4.1：在每个个体中，随机选择两条路径，若两条路径除起点和终点外具有公共节点，
则进行交叉操作，父辈个体和交叉后的个体共同组成新种群；
S4.2：交叉操作得到的每个个体以β的概率进行变异操作，β为预先设置的参数。
6.如权利要求5所述的方法，其特征在于，S4.1中的交叉操作具体包括：
将两条路径公共节点前后的支付通道进行交换，并且，交叉后的种群个体数量与初始
种群数量保持一致。
7.如权