基于QoS约束的启发式网格资源分配算法研究

由于网格环境的资源分配问题属于NP难题而难以通过精确算法获得最优解,提出一种针对具有用户QoS需求的资源分配问题进行求解的启发式方法;首先,在资源分配模型目标函数中考虑QoS约束,然后采用改进的蚁群算法对资源分配方案进行寻优,在信息素的初始化、局部信息素和全局信息素的更新以及资源选择机制中,都加入了QoS约束,使得通过改进蚁群算法求解出的最优解能满足用户QoS需求和实现资源负载平衡;实验结果表明:文中算法得到的平均调度时间较QoS-F和QoS-GA分别减少了42.96％和24.49％,是一种符合网格环境的有QoS约束的有效资源分配方法.     

卫星数传调度的蚁群优化模型及算法

针对卫星数传调度问题,提出了基于任务－资源关联结点的新型解构造图模型,人工蚁群通过任务边和资源弧分阶段进行任务调度序列和资源分配序列构造,设计了任务调度和资源分配启发式信息,以增强蚁群在伪随机状态转移过程中的搜索能力。通过局部信息素更新防止算法陷入局部最优,利用全局信息素更新的信息素正反馈机制使算法逐渐收敛到全局最优。仿真结果表明,新型解构造图反映了任务与资源之间的密切联系,分阶段状态转移策略和启发式信息的利用有助于增强算法的寻优能力,算法正确可行,并具有良好的收敛性、鲁棒性。     

改进蚁群算法在机器人路径规划中的应用

针对传统蚁群算法在移动机器人路径规划问题中存在的易陷入局部最优与收敛速度慢等问题,提出一种改进的蚁群算法。根据起点到终点距离和地图参数构建全局优选区域,提高该区域内初始信息素浓度,避免算法初期盲目搜素;利用局部分块优化策略分别对各个子区域进行寻优并更新区域内最优路径信息素,增强局部搜索能力,加快收敛速度;对全局路径进行寻优,更新全局最优路径信息素。在信息素更新公式中引入信息素增强因子,加强最优路径信息素含量,应用反向学习优化信息素,改进状态选择概率,提高算法寻优能力。实验结果表明,改进后的算法明显提高了收敛速度,同时寻优能力更强。     

混合蚁群算法在网格计算任务调度中的应用

网格环境下的资源分配与任务调度问题已经被证明了是一个NP难题,而传统的任务调度算法很难对大量的异构的、动态的网格任务进行有效的调度。本文提出了一种任务调度模型,并且在该模型中采用混合蚁群算法,该算法以信息素为启发,引导蚂蚁选择最优资源。蚂蚁选择资源之后不仅进行信息素的整体更新,还要求预分配网格资源时进行信息素的局部更新。模拟实验表明该算法是一种快速,有效,负载更均衡的算法。     

双信息素蚁群算法及其在TSP中的应用研究

提出了一种新的蚁群算法,通过在算法中引入双信息素,很好地改进了算法在解决TSP(旅行商)问题时的收敛性和最优解的全局性.一方面通过提高全局信息素对城市路径选择的影响度,很大程度上缩短了算法寻优时间,使算法收敛性得到很大的改善;另一方面通过对接近最优解的一定范围内次优解进行局部更新,避免了算法容易收敛于局部最优解的缺点,极大地改进了最优解的全局特性.在MATLAB中构建了基于蚁群算法的TSP问题模型,仿真结果表明,独立的全局信息素使蚁群很快集中于各个次优解区域搜索,局部更新策略又使蚁群跳出局部级值寻找最优,仿真结果证明算法的改进十分有效.     

改进蚁群算法在基于服务质量的Web服务组合优化中的应用

为了克服基础蚁群算法存在的前期搜索速度较慢、后期极易陷入局部最优解的缺点,提出初始信息素分布策略和局部优化策略;同时还提出了依赖解的质量的信息素更新依据,以增强算法过程中信息素的有效积累。将该改进蚁群算法应用于基于服务质量(QoS)的Web服务组合优化问题中,通过在数据集QWS2.0上的实验对改进蚁群算法的可用性和有效性进行了验证。结果表明改进的蚁群算法与基础蚁群算法、利用解与理想解距离更新信息素的改进蚁群算法以及用支配程度作为解的个体评价的改进遗传算法相比,能够找到更多的非劣解,寻优能力更优,表现出了较稳定的性能。     

基于混合蚁群算法的网格任务调度

针对网格任务调度的调度时间长、资源负载不平衡等问题,提出一种基于混合蚁群算法的网格任务调度方法。该方法将禁忌搜索作为蚁群算法的局部搜索策略,以扩大解的搜索空间,避免陷入局部最优,并通过多样化机制提高算法收敛速度。利用平衡因子调节信息素的更新,改善资源的负载平衡性能。     

基于级联信息素更新蚁群算法的多用户检测

给出了基本蚁群算法在多用户检测中的具体实现,同时针对基本蚁群算法易陷入局部最优解的缺点,提出了一种改进蚁群算法的多用户检测方法。该算法对蚁群算法的信息素更新采用串联式的多级更新策略,首先进行有选择性的信息素更新,然后引进随机扰动因子进一步修改信息素,最后采用最大门限确定信息素的范围。最终的仿真结果表明:所提出的级联信息素更新蚁群算法的多用户检测(UCP-ACO-MUD)算法具有较强的跳出局部最优解的性能,效果良好。     

启发式强化学习机制的异构双种群蚁群算法

针对传统蚁群算法在解决TSP问题时易陷入局部最优、收敛速度较慢的问题,提出了一种基于启发式强化学习的异构双种群蚁群算法。蚁群分为主种群和子种群,主种群负责解的构建和信息素的更新,子种群则是在构建解的同时对主种群的解集进行替换。算法初期利用启发式算子自适应地控制两个种群的交流频率,通过偏离度系数控制解的交换方式。前期让子种群的最优解去替换主种群的随机解,增加解的多样性,同时引入强化学习机制对交流后主种群最优路径上的信息素进行自适应的奖赏,以增大最优公共路径以后被选择的概率。后期则控制子种群的最优解去替换主种群的最差解,强化最优路径上信息素的量,并对主种群最优路径上的信息素进行奖赏,进一步提高算法的收敛速度。实验仿真表明,算法能够有效地跳出局部最优,并且解的质量在大规模测试集上有明显的改善。     

改进蚁群算法求解最短路径问题

针对蚁群算法在求解最短路径问题时存在容易陷入局部最优解的问题,对经典蚁群算法提出三方面改进。首先,在初始化信息素浓度时加入方向引导,加快初始搜索速度;其次,在局部信息素浓度更新过程中采用信息素重分配思想,避免由路径信息素衰减过程导致的最优路径信息素浓度过分减少;最后,在全局信息素更新过程中引入动态因子,使其自适应地更新较优路径信息素浓度,以提高全局搜索能力。仿真实验结果表明,该改进算法可以保证收敛速度,并提高算法搜索到最优路径的几率。     

基于多物品拍卖的网格映射算法设计与模拟

由于网格底层资源的异构、广域分布、自治等特性和网格高层的服务质量 (QoS)要求,使得网格资源映射算法的设计和模拟具有相当的难度。提出了基于多物品拍卖的网格资源映射算法,解决了网格系统中相互独立任务模式的资源映射问题。同时对比了当前的网格资源映射模拟工具,阐述了利用GridSim建立基于多物品拍卖的资源映射算法模拟平台的主要步骤。最后模拟实验表明此算法具有优良性能。     

面向自主网格的多Agent动态协同图构造算法

网格环境的复杂性和动态性迫切需要自主计算技术的支持。在前期工作中给出地自主网格体系结构基础上,为解决任务执行过程中资源或服务失效情况下多Agent间协同的问题,提出了多Agent动态协同图的概念和任务偏序集驱动地多Agent动态协同图构造算法。图中的顶点是由Agent和自主网格服务组成的序偶,构造算法由任务偏序集到服务集的映射,逐层构造图中的顶点。该图通过Agent对本地服务的感知和Agent间的通信,达到任务执行过程中服务间自主协同的目标。模拟实验的结果验证了算法的正确性,表明算法的时间复杂度主要由任务哈斯图的层数决定,并且Agent的感知时间具有鲁棒性。     

QoS-based Task Group Deployment on Grid by Learning the Performance Data

Overhead of executing fine-grain tasks on computational grids led to task group or batch deployment in which a batch is resized according to the characteristics of the tasks, designated resource, and the interconnecting network. An economic grid demands an application to be processed within the given budget and deadline, referred to as the quality of service (QoS) requirements. In this paper, we increase the task success rate in an economic grid by optimally mapping the tasks to the resources prior to the batch deployment. The task-resource mapping (Advance QoS Planning) is decided based on QoS requirement and by mining the historical performance data of the application tasks using a genetic algorithm. The mapping is then used to assist in creating the task groups. Practical experiments are conducted to validate the proposed method and suggestions are given to implement our method in a cloud environment as well as to process real-time tasks.     

基于平均等待时间约束的松弛预留机制

传统预留机制存在预留请求拒绝率高、可能会延迟本地作业执行的缺陷。为此,提出一种基于平均等待时间(MWT)约束的松弛预留机制,并给出相应的预留接纳算法。采用松弛预留策略,在每个资源上设置任务等待时间阈值,若调度队列中排队任务的MWT超过该阈值,调度系统将使部分排队任务尽快获得空闲资源,从而减少MWT。实验结果表明,该预留机制能有效保障排队任务的MWT、提高资源利用率、降低预留请求拒绝率。     

基于Tent混沌序列的粒子群优化算法

针对粒子群优化算法易陷入局部极值和进化后期收敛速度缓慢的问题,提出基于Tent混沌序列的粒子群优化算法,应用Tent映射初始化均匀分布的粒群,提高初始解的质量,设定粒子群聚集程度的判定阈值,并引入局部变异机制和局部应用Tent映射重新初始化粒群的方法,增强算法跳出局部最优解的能力,有效避免计算的盲目性,从而加快算法的收敛速度。仿真实验结果表明,该算法是有效的。     

β-SLAM: Simultaneous localization and grid mapping with beta distributions

Simultaneous localization and mapping (SLAM) is one of the most frequently studied problems in mobile robotics. Different map representations have been proposed in the past and a popular one are occupancy grid maps, which are particularly well suited for navigation tasks. The uncertainty in these maps is usually modeled as a single Bernoulli distribution per grid cell. This has the disadvantage that one cannot distinguish between uncertainty caused by different phenomena like missing or conflicting information. In this paper, we overcome this limitation by modeling the occupancy probabilities as random variables. Those are assumed to be beta-distributed and account for the different causes of uncertainty. Based on this map representation, we derive a SLAM algorithm, including all necessary sensor models, for building maps composed of beta-distributed random variables and using these maps for localization. Furthermore, we propose measures for quantifying uncertainty in the resulting maps and for solving navigation tasks. We evaluate our approach using real-world as well as simulation-based datasets and we compare it to a state-of-the-art SLAM algorithm for building classical grid maps.     

一种基于局部特征的栅格地图拼接方法

栅格地图拼接是多机器人协作创建地图的必不可少的环节。提出一种基于局部特征的栅格地图拼接方法,旨在克服传统算法拼接效率低、拼接成功率低等问题。该方法先对栅格地图拼接建立数学模型,然后转化为图像匹配问题。搭建非线性金字塔,利用FAST算法定位特征点,使用PCA-SIFT算法建立描述符进行匹配,借助随机采样一致性优选匹配点,得到初始参数,并提出一种新型的栅格地图拼接规则。实验表明,该方法鲁棒性好、拼接速度快、拼接精度高。     

基于请求负载的网格任务模糊控制调度策略

在面向大规模复杂应用的网格环境中,网格任务的优化调度变得越来越重要.文中首先提出了一种新的网格任务-服务映射算法,即基于任务负载和优先级的网格任务模糊控制调度策略.在考虑到外部网格任务请求负载和优先级的基础上,能够减少众多网格任务的平均完成时间.使得资源利用更加合理,同时还考虑到了网格服务的价格,即在满足任务负载影响和优先级的情况下,选择价格最小的服务.最后,开发了网格任务调度中间件,并在平台上给出了算法与其他几种常见的经典调度算法进行比较的试验结果.实验表明,算法明显优于已有的经典算法,具有较好应用情景.     

A Heuristic Algorithm for Task Scheduling Based on Mean Load on Grid

Efficient task scheduling is critical to achieving high performance on grid computing environment. The task scheduling on grid is studied as optimization problem in this paper. A heuristic task scheduling algorithm satisfying resources load balancing on grid environment is presented. The algorithm schedules tasks by employing mean load based on task predictive execution time as heuristic information to obtain an initial scheduling strategy. Then an optimal scheduling strategy is achieved by selecting two machines satisfying condition to change their loads via reassigning their tasks under the heuristic of their mean load. Methods of selecting machines and tasks are given in this paper to increase the throughput of the system and reduce the total waiting time. The efficiency of the algorithm is analyzed and the performance of the proposed algorithm is evaluated via extensive simulation experiments. Experimental results show that the heuristic algorithm performs significantly to ensure high load balancing and achieve an optimal scheduling strategy almost all the time. Furthermore, results show that our algorithm is high efficient in terms of time complexity.     

一种新型的混沌步长果蝇优化算法

针对果蝇优化算法存在算法易早熟、收敛不足的问题,将Hénon混沌映射引用为步长因子,提出了一种混沌步长果蝇优化算法。利用Hénon映射所产生的混沌现象具有良好的遍历性、多样性的特点来改进果蝇算法的固定步长,并增加放大系数以提高算法的全局和局部搜索能力以及跳出局部最优解的能力。对10个经典测试函数进行测试,并与多个算法进行了对比分析,研究结果表明,该算法具有较高的全局搜索和跳出局部最优解的能力。