(19)中华 人民共和国 国家知识产权局 (12)发明 专利申请 (10)申请公布号 (43)申请公布日 (21)申请 号 202111451281.9 (22)申请日 2021.12.01 (71)申请人 杭州电子科技大 学 地址 310018 浙江省杭州市钱塘区白杨街 道2号大街 (72)发明人 万健　张雪容　张纪林　曾艳　 殷昱煜　 (74)专利代理 机构 浙江千克知识产权代理有限 公司 33246 代理人 周雷雷 (51)Int.Cl. G06N 20/00(2019.01) G06Q 10/10(2012.01) (54)发明名称 一种利用启发式算法降低联邦学习中设备 空跑时间的方法 (57)摘要 本发明公开了一种利用启发式算法降低联 邦学习中设备跑时间的方法。 本发 明利用启发式 算法中的模拟退火算法求解局部最优解， 得出令 各参与方设备空跑时间缩短的解决方案。 相较于 传统的联邦学习算法， 本发明设定在每轮运算中 各参与方迭代的次数可以不同。 利用模拟退火算 法， 根据数据预处理阶段得到的参与方平均迭代 时间求解每轮参与方的最优迭代次数。 并将传统 联邦学习算法中参与方本地训练和 中央服务器 求解下一轮参与方名单的串行设计改为并行设 计， 从而尽可能降低参与方空等时间。 权利要求书1页 说明书6页 附图2页 CN 114118444 A 2022.03.01 CN 114118444 A 1.一种利用启发式算法降低联邦学习中设备跑时间的方法， 其特征在于该方法包括如 下步骤： 步骤1. 在数据预处理阶段， 中央服务器将初始化好的模型下发到参与本次训练的所 有客户端， 客户端利用本地数据集进行多次迭代并求得平均迭代 时间， 随后将各自的平均 迭代时间上传到中央服 务器； 中央服务器从完备客户端集K中随机选择C个客户端作为首轮运算的参与 方， 并利用启 发式模拟退火算法求得参与方的局部最优迭代次数； 约定参与此次联邦学习的所有客户为 客户端， 参与每 轮训练的客户端为 参与方； 步骤2. 参与方根据中央服务器下发的迭代次数以及模型参数进行训练， 并将本地训 练得出的新的参数 上传到中央服 务器； 步骤3. 在参与方进行本地训练时， 中央服务器并行的随机选择下一轮参与 方名单， 并 利用启发式模拟退火算法计算下一轮参与方的局部最优迭代次数； 启发式模拟退火算法会 选择当前解空间的临近最优解作为下一个解； 若临近解空间没有比当前解更优的解， 则以 一定的概 率接受次优解； 步骤4 参与方将本地运算得出的新参数上传到中央服务器， 中央服务器对参数进行平 均， 并判断模式是否收敛； 若收敛， 则停止运算； 若不收敛， 则根据步骤3得出的下一轮参与 方名单， 中央服务器将聚合后的模型参数和利用启发式模拟退火算法得出的迭代次数下发 到对应的参与方中， 进行新的一轮运 算； 步骤5. 周期性循环步骤2到步骤4 直至模型收敛。 2.根据权利要求1所述的一种利用启发式算法降低联邦学习中设备跑时间的方法， 其 特征在于： 步骤3中约定模拟退火算法中产生 新解的方式： A、 对本轮参与方的平均迭代时间进行从长到短排序epochTimeDoubleArr， 优先挑选平 均迭代选耗时最久的参与方epochTimeDoubleArr[i]， 其中i初始值为0， 让其迭代次数加j， j初始值为1， 并以该参与方运算一轮所花费 的总时间为基准； 其他参与方以该基准为线， 计 算各自的本轮迭代次数， 让各自的本轮总耗时和基准相 差最少； 然后计算新解中各参与方 设备空跑总时间， 并与原解进行对比； 若新解空跑总时间更少， 则直接替换原解， 否则以一 定的概率进行替换， 这个概 率会随温度降低而逐渐降低； B、 若得出的新解中参与方设备空跑总时间比原解更久， 且没有达到替换原解的概率， 则顺序挑选平均迭代耗时次之的参与方epochTimeDoubleArr[i+1]让其迭代次数加j， 并按 照步骤A的过程 求解新解， 进行是否替换原解的判断； C、 若在当前解的基础上， 分别以各个参与 方的迭代次数加j所得的总时间为新基准， 皆 没有找到更优解， 且都没有达到以次优解替换更优解的概率； 则取步骤A中排序数组 epchTimeDoubleArr中平均迭代耗时最长的参与方， 让他的迭代次数在当前解的基础上加 1， 并继续A过程， 以此类 推。 3.根据权利要求2所述的一种利用启发式算法降低联邦学习中设备跑时间的方法， 其 特征在于： 参与方运 算一轮所花费的总时间=迭代次数*单次迭代耗时。 4.根据权利要求2所述的一种利用启发式算法降低联邦学习中设备跑时间的方法， 其 特征在于： 各自的本轮总耗时=迭代次数*平均迭代时间。权　利　要　求　书 1/1 页 2 CN 114118444 A 2一种利用启发式算法降低联邦学习中设 备空跑时间的方 法 技术领域 [0001]本发明属联邦学习领域， 具体涉及一种利用启发式算法中的模拟退火算法根据联 邦学习中每轮运算各参与方的训练能力， 动态设计一种局部最优的参与方本轮迭代 次数， 从而降低联邦学习中各个参与方设备空跑总时间的方法。 背景技术 [0002]近年来， 随着固网宽带、 移动互联网、 物联网的的快速发展， 数据正呈爆炸式的增 长。 海量数据成为人工智能领域的燃料， 同时也带来新的挑战。 在大数据大模型的双重挑战 下， 人们提出用计算机集群来代替单机进 行模型训练， 以解决单机无法存储海量数据、 算力 有限训练复杂模型耗时过久甚至无法训练的瓶颈， 因此分布式机 机器学习应运而生。 [0003]而联邦学习是一种带有隐私保护、 安全加密技术的分布式机器学习框架， 它既解 决了单个主机 GPU/CPU扩展能力有限的问题， 能实现大量节 点同时训练大规模模型， 同时考 虑了用户对数据隐私性和安全性的需要。 传统的分布式机器学习采用集中收集各方数据， 再将数据进行分布式存储， 把任务分散到多个GPU/CPU机器上进 行处理的方法， 从而提升运 算效率。 但这种集中式管理数据的模式在实际的生产生活中往往是难以实现的。 一个AI项 目可能涉及多个领域， 需要融合各个公司、 各个部门的数据。 但考虑到行业竞争和消费者日 益增长的隐私安全需求等多方面因素， 将多个公司甚至同一 公司不同部门的数据进行集成 都面临着巨大阻力。 因此在大多 数行业中， 数据以孤岛的方式存在。 而 联邦学习旨在让分散 的参与方在满足不向其 他参与者披露隐私数据的前提下， 协作进行机器学习的模型训练。 [0004]目前的研究中已提出很多联邦学习的算法， 根据联邦学习数据的特点(不同的参 与方数据重叠的程度)， 联邦学习可以分为横向联邦学习、 纵向联邦学习、 迁移联邦学习。 横 向联邦学习适合于业务场景相似的参与方， 用户重叠部 分较少， 但用户特征相似。 纵向联邦 学习适合于业务特征不同， 用户特征相差大， 但用户空间重叠部 分多。 迁移联邦学习是对横 向联邦学习和纵向联邦学习的补充， 适合于参与方用户空间和特征空间都重叠较少的情 况。 此外， 联邦学习迁移模型不迁移数据的特性是强调将数据留在数据拥有者本地， 由各个 参与方在本地训练模型， 将训练得出 的参数传递给可信中央服务器， 由中央服务器汇总 各 方的训练参数， 构建更加精确的全局模 型。 且联邦学习的参与方往往 是数量众多的， 这意味 着在每一轮迭代后大量的参与方都需要与中央服务器进行通信， 而网络的不稳定性直接导 致通信成为了联邦学习提升效率的一个瓶颈。 现有的技术从通信方面进 行联邦学习算法优 化往往有这样两种 方式： 增加 客户端的计算量， 用更复杂的计算代替简单 的梯度下降或增 加客户端迭代 次数； 模型压缩， 因为一个大的模型在参数更新的时候可能要更新成千上百 万个参数， 模型压缩的目的是通过模型压缩技术来减少每一次通信需要传递的参数量， 从 而加快各参与方与中央服务器的通信速度。 但这些方法 并没有考虑到联邦学习中由于各个 参与方的数据量不同和算力的不同， 导致一次通信前各方完成一次迭代所花费 的时间也大 不相同。 在通信前迭代相同的次数很有可能造成速度快的参与方等待速度 慢的参与方的局 面， 从而导 致部分参与方GPU/ CPU空跑的情况。说　明　书 1/6 页 3 CN 114118444 A 3