蚁群聚类组合方法参数M的研究

蚁群算法中参数在不同取值情况下,常常会对算法的性能和求解效率产生重大影响。该文在基于蚁群聚类组合方法的研究基础上,重点研究了蚁群聚类组合方法KMAOC算法中蚁群算法参数蚂蚁数m对KMAOC算法性能的影响,对KMAOC算法中的参数蚂蚁数m分别取值进行实验,通过几组实验验证提供了KMAOC算法中参数蚂蚁数m配置的较好建议。     

无线多媒体传感器网络蚁群路由算法研究

对蚁群路由算法在无线传感器网络中的应用进行了调查,给出了一种基于基本蚁群路由算法的无线多媒体传感器网络的QoS路由算法,并通过仿真实验研究了前向蚂蚁数量及网络节点数量对算法性能的影响.为了提高算法性能,将前向蚂蚁数量引入到信息素挥发因子中,以减少算法对前向蚂蚁数量的依赖.同时引入基于地理位置已知的前向邻居节点集的概念对算法进行改进,以解决基本蚁群路由算法初始化问题.仿真结果表明改进后的蚁群路由算法能够有效提高算法性能.     

面向负载均衡的自主式虚拟机动态迁移框架

借鉴蚁群算法的思想,提出了一种面向负载均衡的自主式虚拟机动态迁移框架,该框架不需要中央管理模块,能够实现服务器的自主迁移,避免了单点失效。利用智能蚂蚁的搜索,实现了自主式框架的迁移机制,而且使用模糊逻辑推理,根据系统的负载状况自动地调整智能蚂蚁的搜索半径来提高搜索性能。最后扩展了云计算平台CloudSim,实现了提出的虚拟机自主式迁移框架。在扩展后的CloudSim平台上进行的仿真实验验证了该框架的可行性。确定了合适的框架参数,并且通过仿真实验与比较分析,验证了所提出的自主式虚拟机迁移框架具有良好的负载均衡效果。     

云环境下基于性能向量的虚拟机部署算法

针对云计算环境下虚拟机部署问题,提出充分考虑了系统负载均衡的PM-LB虚拟机部署算法。首先,采用性能向量,规范化地描述虚拟基础设施性能状况;然后,通过计算待部署虚拟机和服务器性能向量的相对距离,得到待部署虚拟机的匹配向量;最后,将匹配向量与系统负载向量综合分析,得到虚拟机部署结果。在CloudSim环境下进行了实验仿真,实验结果证明,使用所提算法可获得较好的系统负载均衡效果和较高的资源利用率。     

面向云数据中心的虚拟机部署时延优化算法研究

最优化虚拟机部署时延可以有效地提高云数据中心的效率,然而,目前虚拟机部署时延最优化问题主要针对的是单资源类型的部署。本文主要工作是考虑了服务器内资源容量及虚拟机多类型资源需求时虚拟机部署最优化时延问题。首先,将最优化虚拟机部署时延问题进行了形式化建模,并证明了该问题为一个NPC问题。接着,通过遗传结合贪心策略提出了一种高效的虚拟机部署算法优化时延。该算法的主要特点在于：结合了贪心策略指导个体在初始化、选择、交叉、变异时形成最优解,并且在交叉过程中采用奇、偶数位个体交叉的方式形成新个体,既避免了个体间的重复交叉,又通过多样化的新个体形成使得算法的解不会陷入局部最优。另外,由于遗传算法在交叉过程中会存在交叉冲突问题(服务器容量超载),还设计了一种交叉冲突检查方法避免了交叉冲突后非法个体的生成。最后,通过实验比对,将提出的算法分别与最新研究成果VMPDN、粒子群优化算法等算法比较,结果表明提出算法有效的缩短了虚拟机的部署时延。同时通过不同资源类型数量、迭代次数及种群大小的情况下,分析和考察了算法的性能,结果表明提出算法的性能仍好于其他的算法。     

蚁群算法中蚂蚁更新方法之研究

蚁群算法是根据蚂蚁的觅食行为而提出的随机优化算法,但其存在早熟收敛和搜索精度低等问题。模拟生物克隆选择中5%的B细胞自然消亡过程,在蚁群算法进化过程中分别基于代间差分、混沌理论、变异原理等方法设计了8种蚂蚁更新算法,按照模拟退火方法进行更新后蚂蚁的选择。通过数值试验得出结论：基于代间差分和混沌变异的蚂蚁更新算法是一种很好的选择,并且当性能较差的20%左右蚂蚁按照这种算法更新时效果较好。这种算法可以有效克服蚁群算法的早熟现象,能够加快收敛速度。     

面向数据中心的虚拟机部署及优化算法

虚拟机动态配置是解决数据中心能耗低效的有效方法。针对动态配置过程中的虚拟机部署及优化问题展开研究,提出一种新的面向系统能耗的虚拟机部署算法以及基于主动迁移的优化策略。为了降低系统能耗,新算法采用基于服务器利用率的最佳适配降序算法求解虚拟机部署方案;同时为了适应应用负载的动态变化,新算法启动主动迁移策略对部署方案进行优化,即通过启发式算法在当前部署的基础上搜索使系统能耗更低的优化方案,并根据新部署对虚拟机执行主动迁移。考虑到迁移会导致应用服务质量降级和额外能耗,新算法通过在优化策略中设置基于服务器利用率的启动门限,对虚拟机主动迁移频率进行控制。仿真实验表明,所提算法在系统能耗、虚拟机迁移频率、服务器状态切换频率以及服务质量等多项性能指标上均有显著提高     

CSNEO:协同服务器与网络能耗优化的VM映射算法

已有针对虚拟机映射问题的研究,主要以提高服务器资源及能耗效率为目标.综合考虑虚拟机映射过程中对服务器及网络设备能耗的影响,在对物理服务器、虚拟机资源及状态,虚拟机映射、网络通信矩阵等概念定义的基础上,对协同能耗优化及网络优化的虚拟机映射问题进行了建模.将问题抽象为多资源约束下的装箱问题与二次分配QAP问题,并设计了基于蚁群算法ACO与局部搜索算法2-exchange结合的虚拟机映射算法CSNEO来进行问题的求解.通过与MDBP-ACO、vector-VM等四种算法的对比实验结果表明:CSNEO算法一方面在满足多维资源约束的前提下,实现了更高的虚拟机映射效率;另一方面,相比只考虑网络优化的虚拟机放置算法,CSNEO在实现网络优化的同时具有更好的能耗效率.     

基于架构负载感知的虚拟机聚簇部署算法

针对云计算中虚拟机部署问题,提出了一种基于架构负载感知的虚拟机聚簇部署算法。首先计算云数据中心各层架构的负载,并在架构内对主机进行聚簇。虚拟机进行部署时,先按照相应的规则进行虚拟机间的聚簇,并优先选择负载较低的架构进行部署,架构选择后,进行虚拟机簇与主机簇的匹配以选择最优的主机簇进行部署。最后通过CloudSim进行仿真验证,将其与贪婪算法及基于架构负载感知的基本部署算法进行比较,证明了算法在部署时间方面有明显的优越性,并提高了网络资源的利用率。     

云环境下一种基于能耗感知的虚拟机部署算法

云计算技术已经越来越得到人们的关注和接受。在保证用户性能的前提下,怎样有效提高服务器资源的利用率,同时又能节约能源已成为一个热门话题。针对云计算环境下虚拟机初次部署问题,提出了一种基于能耗感知的虚拟机部署算法（ PAVMAA）。该算法充分考虑用户对于不同应用的不同需求,从系统整体最优角度考虑,以能耗与利用率之间的最佳组合点为出发点,通过计算虚拟机性能需求期望与服务器空闲性能之间的欧几里得距离来匹配部署虚拟机。通过Cloudsim仿真平台上的实验,结果表明：算法实现简单,能明显降低能量消耗。     

改进的蚁群算法及其在2DHP模型中的应用

为了提高蛋白质折叠问题解的质量,采用蚁群算法对蛋白质的折叠问题进行研究,并且在现有的蚁群算法的基础上成功引入了淘汰和克隆机制,使其具有更好的运算效率,并成功应用到2DHP模型中.在蚁群对最优值进行搜索的过程中,容易出现局部最优点,导致影响解的质量.为了避免计算结果收敛到局部最优点,引入了一种最大最小蚁群策略.选择测试序列进行实验,实验结果表明,该算法在保证解的质量的同时,还具有较高的效率.     

On the Invariance of Ant Colony Optimization

Ant colony optimization (ACO) is a promising metaheuristic and a great amount of research has been devoted to its empirical and theoretical analysis. Recently, with the introduction of the hypercube framework, Blum and Dorigo have explicitly raised the issue of the invariance of ACO algorithms to transformation of units. They state (Blum and Dorigo, 2004) that the performance of ACO depends on the scale of the problem instance under analysis. In this paper, we show that the ACO internal state - commonly referred to as the pheromone - indeed depends on the scale of the problem at hand. Nonetheless, we formally prove that this does not affect the sequence of solutions produced by the three most widely adopted algorithms belonging to the ACO family: ant system, MAX-MIN ant system, and ant colony system. For these algorithms, the sequence of solutions does not depend on the scale of the problem instance under analysis. Moreover, we introduce three new ACO algorithms, the internal state of which is independent of the scale of the problem instance considered. These algorithms are obtained as minor variations of ant system, MAX-MIN ant system, and ant colony system. We formally show that these algorithms are functionally equivalent to their original counterparts. That is, for any given instance, these algorithms produce the same sequence of solutions as the original ones.     

云计算环境下基于蚁群优化算法的资源调度策略

针对当前云计算环境中节点规模巨大,单个节点资源配置较低,寻找有效计算资源效率不高的缺点,文中在Google公司的Map/Reduce框架上提出了两个基于蚁群优化的资源调度策略ACO1和ACO2,并在这两个资源调度策略中引入双向蚂蚁机制。在该双向蚂蚁机制中蚂蚁通过相互交流,能够快速地发现合适的虚拟机资源,从而使得Master节点能够快速地为用户任务分配虚拟机。实验结果表明这两个利用了双向蚂蚁机制的资源调度策略显著减少了为用户任务寻找虚拟机的时间,从而使得用户任务能够更快地获得虚拟机,保证用户作业能够按时完成。     

基于蚁群优化算法的虚拟现场可编程门阵列部署策略

针对可重构密码资源池中,如何在最少的现场可编程门阵列（FPGA）上部署虚拟FPGA （vFPGA）的问题,结合FPGA的工作特点和应用场景的需求,在传统蚁群算法的基础上进行了优化,提出了一个基于蚁群优化（ACO）算法的vFPGA部署策略。首先,通过赋予蚂蚁资源状态感知的能力实现各个FPGA之间的负载均衡,同时避免频繁的vFPGA迁移;其次,设计预留空间,有效减少因为租户需求动态变化带来的服务等级协议（SLA）冲突;最后,对CloudSim进行功能扩展,使用合成的工作流进行仿真实验,对该策略性能进行评估。实验结果表明,所提策略可以在保证系统服务质量的前提下,提高FPGA资源利用率,减少FPGA使用量。     

Heuristics for the two‐machine scheduling problem with a single server

In this paper, the NP‐hard two‐machine scheduling problem with a single server is addressed. The problem consists of a given set of jobs to be scheduled on two identical parallel machines, where each job must be processed on one of the machines, and prior to processing, the job is set up on its machine using one server; the latter is shared between the two machines. An ant colony optimization (ACO) algorithm is introduced for the problem and its performance was assessed by comparing with an exact solution (branch and bound [B&B]), a genetic algorithm (GA), and simulated annealing (SA). The computational results reflected the superiority of “ACO” in large problems, with a performance similar to SA and GA in smaller problems, while solving the tested problems within a reasonable computational time.     

High speed ant colony optimization CMOS chip

Ant colony optimization (ACO) is an optimization computation inspired by the study of the ant colonies’ behavior. This paper presents design and CMOS implementation of the ant colony optimization based algorithm for solving the TSP problem. In order to implement ant colony optimization algorithm in CMOS, we will present a new algorithm. This algorithm is based on the original ant colony optimization but it can be implemented in CMOS. Briefly, pheromone matrix is transformed on the chip area and ants move up-down through the pheromone matrix and they make their decisions. Finally ants select a global path. In previous researches only pheromone values is used, but select the next city in this paper is based on heuristics value and pheromone value. In definition of problem, we use heuristics value as a matrix. Previous researches could not be used for wide type of optimization problem but our chip gives heuristics value initially and we can change initial value of heuristics value according to the optimization problem so this capability increases the flexibility of ACO chip. Simple circuit is used in blocks of our chip to increase the speed of convergence of ACO chip. We use Linear Feedback Shift Register (LSFR) circuit for random number generator in ACO chip. ACO chip has capability of solving the big TSP problem. ACO chip is simulated by HSPICE software and simulation results show the good performance of final chip.     

A bio-inspired distributed algorithm to improve scheduling performance of multi-broker grids

The scheduling in grids is known to be a NP-hard problem. The distributed deployment of nodes, their heterogeneity and their fluctuations in terms of workload and availability make the design of an effective scheduling algorithm a very complex issue. The scientific literature has proposed several heuristics able to tackle this kind of optimization problem using techniques and strategies inspired by nature. The algorithms belonging to ant colony optimization (ACO) paradigm represent an example of these techniques: each one of these algorithms uses strategies inspired by the self-organization ability of real ants for building effective grid schedulers. In this paper, the authors propose an on line, non-clairvoyant, distributed scheduling solution for multi-broker grid based on the alienated ant algorithm (AAA), a new ACO inspired technique exploiting a “non natural” behavior of ants and an inverse interpretation of pheromone trails. The paper introduces the proposed algorithm, explains the differences with other classical ACO approaches, and compares AAA with two different algorithms. The results of simulations show that the AAA guarantees good performance in terms of makespan, average queue waiting time and load balancing capability.     

一种求解高校最短路径的改进的启发式蚁群算法

启发信息是地理信息系统（GIS）中的关键,针对蚁群算法易陷入局部最优的缺陷,提出一种带有启发信息的改进蚁群算法。i亥算法在初始化蚁群时引入启发信息指引蚂蚁快速收敛于全局最优解,为平衡全局与局部搜索能力,也改进状态转移概率算子,从而有效提高算法性能,增加种群多样性。实验以Visual Studi02005中C＋＋编程实现仿真,结果表明此算法不但能有效求解GIS的最短路径,而且改进的算法能快速地收敛且精度高。     

调查传播算法和蚁群算法相结合求解可满足性问题

布尔可满足性问题(Boolean Satisfiability Problem,SAT)是逻辑学的一个基本问题,也是NP-hard问题。调查传播算法(Survey Propagation,SP)是求解SAT的一种非常高效的算法,但SP在难解区域极易不收敛,或者出现错误赋值。将SP算法与蚁群算法结合,把SP算法得到的消息值应用到蚁群算法中来求解3-SAT问题,使用这些消息值引导蚁群算法求解,并在算法中加入高效的局部搜索。新算法对于SP算法不收敛的一些实例也能很快找到解。