一种求解多处理机调度问题的自适应蚁群算法

将蚁群算法应用于求解多处理机调度问题,提出一种自适应蚁群算法．算法以最小化makespan为调度目标,根据蚂蚁留下的信息素指导蚁群在解空间展开全局搜寻,将任务分配在恰当的机器上,并通过自适应调整阈值实现全局探索与精细查找的平衡．实验结果表明算法具有较好的优化性能．     

一种面向传感器网络的蚁群优化路径恢复算法

为了找到动态传感器网络中的能量有效路径,提出了一种基于蚁群优化的传感器网络路径恢复算法.设计了一种新的路径选择概率模型,使得能够找到一条从源节点到sink的能量有效路径,该路径兼顾了路径能量消耗和节点剩余能量情况.为了适应网络动态变化,提出了局部信息素再初始化规则,利用该规则可在网络失效节点的附近进行局部信息素再初始化,在保留大部分原有最优路径的信息的同时,还能进行局部搜寻,以寻找新的路径,从而达到快速路径恢复的目的.仿真实验表明,所提算法在寻找路径上所消耗的能量最少,节点的剩余能量最大,在网络存在失效节点的情况下能够快速恢复路径.     

一种异步蚁群算法求解柔性作业车间调度问题

调度问题广泛存在于资源共享型系统中,大多数的调度问题都属于混合整数规划问题.大规模混合整数规划问题是计算科学领域中的NP-hard经典问题之一,一般认为无法用精确计算求解.生产调度是调度的一个重要分支,是实现智能制造关键环节之一.针对多品种变批量柔性作业车间调度问题,以最小制造期为优化目标,设计了一种基于Petri网的异步并行蚁群算法,其中:提出了一种基于Petri网的步可达图构造方法,用于蚁群算法解空间的构造;探讨了传统蚁群算法搜索机制,并给出了一种基于异步仿真时钟的蚁群并行搜索方法;仿真结果表明,多线程控制方法可以有效地避免算法的早熟收敛问题.将所提出的算法应用于某安防件智能制造系统的柔性作业车间调度中,降低了系统的总制造时间,获得较好工程效果的同时验证了算法的有效性.     

一种面向多处理器系统的在线低功耗调度算法

针对当前多处理器系统中的散热瓶颈问题,基于处理器动态速度调节技术,提出了一种在线低功耗调度算法(PEQUI).PEQUI以动态均衡算法(EQUI)为基础,公平地分配处理器资源,依据处理器功耗与运行速度间存在非线性关系,以正比于系统任务数的方式调节处理器运行速度.与传统低功耗调度算法相比,PEQUI仅基于当前待调度任务的信息进行决策,决策参数少.以能量消耗与任务执行流时间为评价算法性能的指标,利用在线竞争分析方法证明了PEQUI算法与最优离线算法相比可达到常数竞争比(10).模拟结果表明,PEQUI比最近到达处理器共享算法(LAPS)和恒速EQUI算法能更好地优化系统整体性能和能量消耗.在相同负载情况下,与LAPS相比,PEQUI在降低功耗的同时系统平均运行时间也降低了近7%.     

一种面向通信开销的网格工作流调度算法

采用任务—资源分配图定义了网格任务调度模型,运用动态规划的方法提出了面向通信开销的工作流任务调度算法。采用扩展的拓扑排序算法对具有依赖关系的工作流任务进行划分,根据划分的任务子集得到相应的调度阶段,在每一阶段选择满足约束条件和以计算开销、通信开销以及任务执行成功率为最优目标函数的资源节点进行任务分配,从而使工作流任务调度目标函数最优。应用Grid Sim工具包实现了该调度算法,并与Min-Min算法进行对比分析。仿真结果表明,基于动态规划的网格工作流调度算法具有良好的适应性,且能较好地处理不同网络环境下任务间存在大量数据传输的网格调度问题。     

一种面向多目标的数据流操作符调度算法

针对Aurora数据流管理系统中最小代价(MC)和最小延迟(ML)操作符调度算法的不足,提出一种新的综合算法(MCL),运用运筹学多目标思想,通过调整策略转折时机使总体执行代价和平均元组通过延迟达到综合最优,具有更好的服务质量,尤其在后续处理速度慢时,控制两项指标可以节省资源配合后续处理,进而提高整体性能.通过仿真新算法的有效性得到证明.     

面向多核虚拟机的高效瞬态协同调度算法

随着多核硬件技术的迅速发展和应用对计算能力需求的不断增强,多核虚拟机应用也越来越广泛。但多核虚拟机会引发锁占用的可扩展性问题,锁占用严重影响系统的整体性能。本文基于Linux的完全公平调度器(CFS)设计并实现了一个高效的瞬态协同调度算法,能够高效地解决锁占用问题并获得更好的系统性能。实验结果表明,相比Linux 2.6.38内核,该算法可以显著地提高系统性能,在SysBench.OLTP的测试用例中系统整体性能最多提高到3.41倍,并且对调度公平性几乎没有影响。     

一种改进的蚁群算法

传统的蚁群算法存在难以确定计算参数,求解大规模问题时不易收敛的问题.本文针对该问题对蚁群算法进行改进,结合专家系统和遗传算法来自动确定系统参数,并采用分而治之的策略对大规模问题进行分解.仿真实验表明,该策略提高了问题求解的效率.     

一种自适应蚁群分类算法

将分类学习看作是一个找出最优分类规则的优化问题,提出一种自适应蚁群分类算法——AdaptiveL_AMP,以得到一组可理解的分类规则.在基于规则的分类方法中,规则评价函数的选取至关重要,本文提出的算法能够针对不同数据集自动选取与之相适应的规则评价函数以提高分类准确性.此外,为进一步提高算法的分类准确率,设计了一种局部搜索策略并将其融入到AdaptiveL_AMP算法中.最后对算法进行了分析,并在多个公用的真实数据集上与相关算法进行了比较,结果表明AdaptiveL_AMP算法能够更加有效地解决分类问题.     

面向绿色制造的一种作业调度模型及其算法

建立了面向绿色调度的模型,旨在优化调度过程中产品的质量、生产成本、资源消耗、环境污染和生产周期．将多目标遗传算法与模糊优选技术相结合对该模型求解,并用案例验证了模型的实用性和算法的可行性．     

一种面向HPC Cloud系统的在线作业调度算法

针对HPC Cloud中的作业之间对网络I/O资源的竞争问题,提出了一种基于动态规划算法、二分搜索算法和网络最大流算法的在线作业调度算法——DBMF算法.DBMF算法专注于物理节点上网络I/O的负载均衡,通过物理节点之间的网络I/O负载均衡来减少对网络I/O资源的竞争.通过与FCFS和RSF算法进行对比,DBMF调度算法有效提高了HPC Cloud的系统负载,减少了作业之间对网络I/O资源的竞争.     

人力资源调度的蚁群算法模型

针对企业人力资源管理中的生产安排、工作分配和设备布置的优化调度问题,在对蚁群算法进行总结分析的基础上,提出了求解该问题的蚁群算法模型.并对蚁群算法模型进行了改进,提高了算法的全局搜索能力.提出了基于蚁群算法的人力资源调度策略,并用数学模型对求解问题进行描述,给出了算法步骤.实例证明:改进蚁群算法能有效节省人力资源成本,为人力资源调度提供参考.     

一种改进的蚁群求解算法

为了提高蚁群算法的求解性能,对基本蚁群算法进行了改进.采用上三角的信息素存储形式、改禁忌表为可选表、遗传算法中的交叉及变异、全局更新信息素等做法对基本蚁群算法进行改进,并介绍了在Matlab环境下编程实现的方法及步骤,仿真实验求解了16个城市的TSP问题,得到最短距离为73.988,结果表明了编程思路的正确性及算法的高效性.此改进算法改善了随着求解空间的增加而导致的求解效率低下及因迭代次数的增加而造成的信息素量堆积导致的不成熟收敛,提高了搜索能力及速度,拓展了搜索空间.     

SSA:一种面向CQF模型的TSN资源调度算法

时间敏感网络(time sensitive networking,TSN)的目标是在工业控制和5G领域为时间敏感流提供低延迟、低抖动的确定性传输服务.资源调度是保证TSN服务质量的关键技术之一.为此,TSN标准中提出循环队列转发模型(cyclic queuing and forwarding,CQF),但是缺乏相应的资源调度算法对多流进行合理的资源分配以避免传输冲突.由于时间敏感流量具有周期性、特征预知的特点,主要从时间维度研究如何将CQF模型中的队列资源合理分配给多条数据流.将该问题抽象为多约束条件下的资源规划最大化问题,提出基于起始时隙分配的轻量级资源调度算法(start-slot assignment based scheduling algorithm,SSA).SSA通过对端系统上发送时隙进行调节,在满足约束条件的前提下最大化对队列资源的使用,避免了端到端逐跳的时隙分配.实验结果表明,与不控制时隙的直接调度方式相比,该算法能够将成功调度的流数目平均提高41.84%.     

一种新的量子蚁群优化算法

 针对蚁群算法在求解连续空间优化问题时易于陷入局部最优和收敛速度慢的问题,提出了一种新的基于量子进化的蚁群优化算法。 该算法采用量子比特的概率幅表示蚂蚁当前位置信息;设计了一种新的量子旋转门更新蚂蚁位置, 完成蚂蚁的移动;最后采用量子 非门实现蚂蚁所在位置的变异, 增加位置的多样性。不仅从理论上证明了所提出算法的收敛性,而且通过仿真实验表明该算法可使 搜索空间加倍,比传统的蚁群算法具有更好的种群多样性,更快的收敛速度和全局寻优能力。     

一种面向稀疏数据基于间接评分的协同过滤算法

针对数据稀疏性问题,从提高稀疏数据矩阵利用效率这个角度,提出了一种基于间接评分的协同过滤算法,在基于用户和基于项目的协同过滤算法基础上,将2种算法的预测评分进行动态地混合加权作为直接预测评分,同时引入"相似用户"对"相似物品"的评分作为间接预测评分,最后把间接预测和直接预测2种评分加权形成用户对项目的最终评分.为证明该方法的有效性,使用MovieLens电影评分数据集对算法进行验证,结果表明该方法的平均绝对误差要比传统的基于用户和基于项目的协同过滤算法低,表明了在稀疏数据上该文提出的基于间接评分的协同过滤算法效果更佳.     

一种求解面向服务软件部署优化问题的多目标蚁群算法

基于根据动态变化的外部环境调整面向服务软件的部署方案是提升其运行性能、降低运行成本的一种有效途径,提出一种基于多目标蚁群算法的MACO-DO,以便在自动为面向服务软件寻找一组在性能和成本之间作出最优权衡的部署方案。MACO-DO算法是对传统多目标蚁群算法的一种改进,引入摒弃精英解策略以避免算法早熟收敛,设计1个局部搜索过程以加快获得可行解的过程。在Case 1,Case 2和Case 3共3种不同规模的模拟案例上将提出的MACO-DO算法与P-ACO算法和NSGA-Ⅱ算法进行对比。研究结果表明:MACO-DO算法在求解问题上具有更好的性能。     

基于蚁群算法的灵巧卫星调度

灵巧卫星的出现将极大程度增加卫星对给定地面目标实施观测的可选方式和灵活度,使得灵巧卫星调度问题的高度组合特征更加突出,大大增加了卫星调度问题的复杂性和解搜索的寻优难度。分析了灵巧卫星调度问题的约束条件,建立了灵巧卫星调度的约束满足模型。提出了求解灵巧卫星调度方法的蚁群算法,对算法的状态转移规则、信息素更新规则以及安排观测窗口的规则做了详细描述;并提出了任务路径处理流程,以此产生调度方案,评价路径优劣,反馈给蚂蚁路径搜索阶段。通过实例计算,展现了灵巧卫星强大的观测能力以及方法的有效性。     

一种改进的蚁群聚类算法

针对现有蚁群聚类中将带聚类样本放于网格进行聚类的算法存在随机移动而延长聚类时间,及大数据集进行蚁群聚类时收敛速度慢的缺点,在蚁群进行聚类前增加数据预处理.利用两元素越相似属于同一类簇的可能性越大的思想,将样本集中的样本量缩小.研究了通过信息素进行聚类的蚁群聚类算法,使算法中的"蚂蚁"在一定指导下进行聚类,达到缩短时间的目的.最后通过实验验证了所提出算法的有效性和优越性.     

一种基于CVRP的改进蚁群算法

针对有容量约束的车辆路径优化问题（Capacity Vehicle Routing Problem,CVRP）的特点,提出了一种改进的蚁群算法。算法中,首先让蚂蚁找到需求量满足要求的客户点集,再在选定的客户集中以选择概率选择客户点,改变了基本蚁群算法的信息素更新规则,限定了路线上信息素的浓度,调整了蚂蚁的选择概率,动态改变了算法主要参数等,从而优化了其搜索解的能力和收敛速度,实例仿真证明了改进的蚁群算法对小规模CVRP的解决是有效的。