分布式训练异构任务调度算法研究

分布式机器学习中的工作结点在训练过程中经常需要处理异构任务,但任务发布者可能无法根据有效的先验知识确定边缘服务器集群中哪些是处于训练状态的工作结点。针对边缘服务器集群无法同时满足训练性能与服务质量最大化的问题,对异构任务调度算法进行了研究。首先在集群资源约束下分析了分布式训练收敛性能的影响因素;其次建立了最大化训练性能的优化目标;最后转化为多维多选择背包问题进行求解。仿真结果表明,所提异构任务调度算法能够在保证服务质量的同时,最大化分布式训练性能。     

融合Shapley值和粒子群优化算法的混合特征选择算法

针对在模式分类问题中,数据往往存在不相关的或冗余的特征,从而影响分类的准确性的问题,提出一种融合Shapley值和粒子群优化算法的混合特征选择算法,以利用最少的特征获得最佳分类效果。在粒子群优化算法的局部搜索中引入博弈论的Shapley值,首先计算粒子（特征子集）中每个特征对分类效果的贡献值（Shapley值）,然后逐步删除Shapley值最低的特征以优化特征子集,进而更新粒子,同时也增强了算法的全局搜索能力,最后将改进后的粒子群优化算法运用于特征选择,以支持向量机分类器的分类性能和选择的特征数目作为特征子集评价标准,对UCI机器学习数据集和基因表达数据集的17个具有不同特征数量的医疗数据集进行分类实验。实验结果表明所提算法能有效地删除数据集中55%以上不相关的或冗余的特征,尤其对于中大型数据集能删减80%以上,并且所选择的特征子集也具有较好的分类能力,分类准确率能提高2至23个百分点。     

基于极大团的边缘云节点聚合算法

组合多个边缘云可以向用户提供更强大的云计算服务,在大量边缘云节点集合中选择适当的节点进行组合是一项具有挑战性的任务。该问题被建模成由云节点作为顶点、节点之间的链路作为边的资源拓扑图。云组合的构建过程等同于在该图中选择子图的过程,这是一个NP完全问题。子图的选择策略是决定云组合性能的重要因素,现有的minStar算法贪心地选择节点之间通信延迟最小的子图,将最优资源分配给当前用户,导致了局部最优和全局性能不良的问题。鉴于此,提出基于极大团的边缘云资源分配算法,提取图中的极大团并将其划分为若干互不重叠的规模较小的完全子图,以子图为单位构建资源块,以资源块为单位进行资源的分配。实验结果表明,与minStar算法相比,新算法将全局最大通信延迟降至原来的50%。     

针对移动云计算任务迁移的快速高效调度算法

计算量较大的应用程序由于需要大量的能耗,因此在电池容量有限的移动设备上运行时十分受限。云计算迁移技术是保证此类应用程序在资源有限的设备上运行的主流方法。针对无线网络中应用程序任务图的调度和迁移问题,提出了一种快速高效的启发式算法。该算法将能够迁移到云端的任务都安排在云端完成这种策略作为初始解,通过逐次计算可迁移任务在移动端运行的能耗节省量,依次将节省量最大的任务迁移到移动端,并依据任务间的通讯时间及时更新各个任务的能耗节省量。为了寻找全局最优解,构造了适用于此问题的禁忌搜索算法,给出了相应的编码方法、禁忌表、邻域解以及算法终止准则。构造的禁忌搜索算法以提出的启发式解为初始解进行全局搜索,并实现对启发解的进一步优化。通过 实验 将所提方法与无迁移、随机迁移、饱和迁移3类算法进行对比,结果表明提出的启发式算法能够快速有效地给出能耗更小的解。例如,在宽度为10的任务图上,当深度为8时,无迁移、随机迁移与饱和迁移的能耗分别为5461、3357和2271能量单位,而给出的启发解对应的能耗仅为2111。在此基础上禁忌搜索算法又将其能耗降低到1942, 这进一步说明了提出的启发式算法能够产生高质量的近似解。     

带权图的均衡 k划分

带权图的均衡 k划分是把一个图的顶点集分成k个不相交的子集,使得任意2个子集中顶点的权值之和的差异达到极小,并且连接不同子集的边权之和也达到极小。这种图的k划分问题已被应用在软硬件协同设计、大规模集成电路设计和数据划分等领域,它已被证明是NP完全问题。首先针对带权图的均衡k划分问题提出了能够生成优质近似解的启发式算法。该算法在保证子集均衡的条件下,采用最大化同一子集内部边权之和的策略来构造每一个顶点子集;构建子集 S的思想是每次从候选集中选择与子集S相连的具有最大增益的顶点放入子集S中,直到子集 S的顶点权值之和满足要求。此外,采用了定制的禁忌搜索算法对生成的初始近似解实施进一步优化。实验结果表明,当 k分别取值为2,4,8时所提算法分别在86％,81％,68％的基准图上求得的平均解优于当前最新算法求得的平均解;解的最大改进幅度可达60％以上。     

离散傅里叶变换的算术傅里叶变换算法

离散傅里叶变换(DFT)在数字信号处理等许多领域中起着重要作用.本文采用一种新的傅里叶分析技术—算术傅里叶变换(AFT)来计算DFT.这种算法的乘法计算量仅为O(N);算法的计算过程简单,公式一致,克服了任意长度DFT传统快速算法(FFT)程序复杂、子进程多等缺点;算法易于并行,尤其适合VLSI设计;对于含较大素因子,特别是素数长度的DFT,其速度比传统的FFT方法快;算法为任意长度DFT的快速计算开辟了新的思路和途径.     

立体堆与分枝界限算法

分枝界限算法是解决组合优化问题的常用方法之一.对于给定的问题和分枝策略,算法的运行时间取决于实现算法的数据结构.该文讨论了立体堆及其上的插入、删除算法;通过将分枝界限算法的运作过程与排序过程建立对应关系,给出了一般分枝界限算法的复杂度下界Ω(m+hlogh),其中m为评估的结点数,h为扩展的结点数;得出了立体堆为实现一般分枝界限算法的几乎最优数据结构;并对具体的作业分派问题实现了一个使用立体堆的分枝界限算法;提出了改善立体堆平衡性的措施.     

面向公平保障的共乘定价与匹配算法

在共乘场景中,具有相似行程和时间安排的多名乘客一同出行,可降低出行成本、提高车辆上座率和缓解交通拥堵。现有研究忽略了共乘收费标准不统一和司机恶意竞价对乘客共乘体验的影响。在同时考虑费用约束、车辆容量约束和绕路距离约束的的情况下,提出最大化匹配结果公平性的方案,并将共乘的定价与匹配过程建模为一个两阶段的主从博弈。针对上述方案,提出了一个基于K-means++的请求划分算法,以缩小司乘匹配范围,提高匹配效率;在满足所有参与者约束的前提下,设计了基于两阶段主从博弈的迭代算法DPMA,并从理论上证明了其收敛性。在纽约出租车数据集上进行了仿真实验,通过不同的参数设置验证了DPMA的收敛性。与已有的2个算法相比,DPMA在保障司机收益的同时,在公平指数上分别提高了34.03%和24.42%。实验结果表明所设计机制可以有效避免司机间的恶意竞价,且提高了共乘匹配的公平性。     

稳定的最短路径树及其构造算法

构建最短路径树是动态网络研究的重要问题之一。在动态网络中,当边状态发生变化时会引发最短路径树动态的重新构建,反复地计算不仅消耗大量时间,也会导致最短路径树的频繁变化。提出一种稳定的最短路径树构造算法,使得构造的路径树在动态网络上更稳定,即更新最短路径树所需的操作数更少。该算法通过记录频繁变化的不稳定边并尽可能避免将其加入最短路径树中,从而能够高效地减少边变化带来的操作。实验结果表明,与传统的动态最短路径树算法相比,该算法可以得到更稳定的最短路径树,并且更新时间减少了57.24%,结点更新次数降低了43.6%。