关于跨域虚拟网络的优化狼群映射研究仿真

虚拟网络映射的目的是将网络底层物理资源,以高可用低开销的方式配置到虚拟网络中,进而提高物理网络的业务扩展性能.针对分布式跨域带来的网络资源异构特性,现有映射算法往往存在节点或链路负载不均衡,资源开销过大,以及报文抖动等问题,提出了优化狼群的跨域虚拟网络映射算法.由于跨域虚拟网络映射过程中,额外的资源开销主要来源于域间,因此算法将映射处理分为域内与域间两部分进行独立分析.对于域内映射只引入元胞结构,增强单目标优化处理性能,将节点采用二进制表示,并设定每一位作为一个元胞,建立节点元胞模型,通过更新元胞与近邻得到域内节点与链路资源的最优配置;对于域间映射,则在元胞基础上,引入优化狼群算法,元胞结构提高搜索的分布能力,优化狼群提高全局寻优性能,利用探狼四处游走,在元胞向量中搜索解,同时得到头狼信息,头狼产生召唤行为通知猛狼目标解的信息,从而利用分工协作实现节点与链路最优解的搜索.仿真结果表明,提出的优化狼群网络映射算法能够有效应对跨域异构资源问题,均衡节点和链路的负载,显著降低网络映射开销和网络映射执行时间.     

一种动态邻居元胞遗传算法

研究一种改进的元胞遗传算法。将遗传算法中的个体适应度和元胞自动机中的邻居定义做了结合,提出基于元胞间距离以及元胞个体适应度的"影响力算子",并作为算子中心元胞判断邻居的依据,从而形成改进算法,并对改进算法的基本性能的进行了两组定量分析,一是影响力算子对选择压和多样化损失的控制,另一部分是将算法与改良后传统元胞遗传算法做了对比测试。结果显示,即便使用最朴素的影响力算子而且不采用其它优化手段的情况下,算法依然能对选择压和多样化损失进行有效地控制,并且相较于使用了最优个体保持和小范围竞争择优的传统元胞遗传算法收敛率提高了约10%。     

基于元胞自动机遗传算法的云资源调度

针对传统遗传算法易陷入早熟收敛等问题,提出一种改进的元胞自动机遗传算法(CGA),并将其应用于云环境下的资源调度。分析云计算环境中处理用户群请求的庞大任务数及资源合理分配的问题,利用CGA算法寻求一组最优的资源调度方案。在CloudSim仿真平台上进行实验,结果表明,CGA算法能缩短任务完成时间,降低用户总成本,满足云环境下的资源调度要求。     

元胞遗传算法的收敛性分析和收敛速度估计

元胞遗传算法是空间结构化种群的遗传算法,将遗传操作限制在相邻个体之间进行,限制优势基因的扩散速度,保持种群的多样性,改善遗传算法的性能。但是,目前有关元胞遗传算法收敛性的分析还较缺乏。文中根据元胞遗传算法的特性,建立元胞遗传算法的吸收态 Markov链模型,证明元胞遗传算法的收敛性。提出元胞遗传算法的首达最优解期望时间的估算方法,并估计标准同步元胞遗传算法首达最优解期望时间的上下界。     

一种启发式网络虚拟化资源分配算法

网络虚拟化是克服当前Internet僵化问题的一种重要方法,而资源分配是网络虚拟化技术的核心.为了平衡负载,本文提出了一种启发式资源分配算法HVNE.该算法充分利用虚拟节点和虚拟链路间的关联因素(虚拟网络拓扑),将节点映射和链路映射两个过程合并为一个统一的过程,改善了传统映射算法在拓扑稀疏时,算法性能不理想的问题.此外,HVNE允许同一个虚拟请求中的多个虚拟节点映射到同一个物理节点,节约了物理链路资源.HVNE将无向图的"k-区域划分优化"理论与传统的拓扑分割理论相结合,定义了虚拟拓扑间节点的关联因子,改进了传统的星形分割方法,使之能适用于大规模网络.仿真实验表明,HVNE在保证网络负载的情况下,获得了较好的虚拟请求接受率,较高的资源利用率和网络收益.     

基于线性映射的多物种捕食元胞遗传算法

为提高捕食元胞遗传算法的性能及在基因型上对种群进行区分,提出一种基于线性映射的多物种捕食元胞遗传算法。该算法通过引入映射矩阵,改变种群基因型到表现型的映射关系,使不同物种间所携带的遗传信息不同。在进化过程中,不同物种采用不同的遗传方式进行交叉,并根据种群离散程度自适应调整映射矩阵系数控制种群进化方向,有效提高算法跳出局部最优的能力。对若干低维及高维典型函数进行仿真实验,将文中算法与其它同类算法对比,实验结果表明,文中算法在全局收敛率上具有较明显的优势。     

基于改进元胞多目标遗传算法的机床主轴优化

为了进一步提高元胞遗传算法在求解多目标优化问题时的收敛性和分布性。在多目标元胞遗传算法的基础上,引入了三维空间元胞,提出了三维元胞多目标遗传算法。采用多目标基准测试函数对该算法进行了测试,并将其与目前比较流行的几种多目标遗传算法进行对比。结果表明,此种算法在收敛性和分布性上取得了更好的效果。采用以上这几种算法分别对机床主轴多目标优化问题进行了求解,相比其他几种算法,改进的多目标元胞遗传算法得到了更优的结果,说明了改进的算法在求解此问题时行之有效。     

基于遗传算法的可扩展应用层组播树构建

在应用层组播中,为降低节点的路径延时,通常采用遗传算法和启发式算法来减小组播树直径的方法,但在组播树具有大规模节点数时,遗传算法收敛时间长,而采用启发式算法难以在有约束条件下达到全局最优.本文在具有超节点的双层应用层组播模型基础上,提出了利用遗传算法构建出度受限最小带权路径延时生成树（MWPL-DC-ST）的生成算法GA-MWPL-DC-ST,利用该算法可在超节点上对双层组播树进行分布式构建,从而将求最优解问题的巨大计算量分担到多个超节点上.算法中的初始化、杂交和变异阶段采用启发式算法,对变异参数进行适应性调整,加快了算法的收敛速度.仿真试验表明,本文提出的双层应用层组播模型和GA-MWPL-DC-ST算法能得到比启发式算法更优的解,与采用单层模型的遗传算法相比较,显著降低了算法收敛时间,解决了遗传算法构建有大规模节点数的应用层组播树的可扩展性问题.     

基于最优子网的虚拟网络映射算法

针对在虚拟网络映射过程中物理资源碎片化导致嵌入请求被拒绝,从而降低物理资源利用率的问题,提出一种基于最优子网的虚拟网络映射算法,通过优化的重边匹配算法,合并符合约束条件的虚拟节点,同时粗化网络拓扑,运用广度优先搜索算法创建候选物理子网集合,将粗化后的虚拟网络请求映射至最优子网。仿真结果表明,该算法能够减小链路映射跳数,提升虚拟网络请求接受率和收益开销比。     

基于多中心城市策略的分层元胞遗传算法

为提高分层元胞遗传算法在解决复杂函数优化问题时的求解精度、收敛速度和求解效率.在分层元胞遗传算法的基础上借鉴西方经济理论中中心城市思想提出了一种基于多中心城市策略的分层元胞遗传算法.该算法在进化初期选择适应度值高的多个个体作为种群进化过程中的中心城市,中心城市周围元胞空间的个体按照一定的迁移规则往中心城市迁移,全局最优...     

Solving very large instances of the scheduling of independent tasks problem on the GPU

In this paper, we present two new parallel algorithms to solve large instances of the scheduling of independent tasks problem. First, we describe a parallel version of the Min–min heuristic. Second, we present GraphCell, an advanced parallel cellular genetic algorithm (CGA) for the GPU. Two new generic recombination operators that take advantage of the massive parallelism of the GPU are proposed for GraphCell. A speedup study shows the high performance of the parallel Min–min algorithm in the GPU versus several CPU versions of the algorithm (both sequential and parallel using multiple threads). GraphCell improves state-of-the-art solutions, especially for larger problems, and it provides an alternative to our GPU Min–min heuristic when more accurate solutions are needed, at the expense of an increased runtime.     

多目标函数优化的元胞蚂蚁算法

提出一种求解多目标函数优化的元胞蚂蚁算法．该方法将元胞自动机演化规则引入蚂蚁算法，给出了在连续空间多目标函数优化的算法描述，定义了与蚂蚁信息素释放有关的元胞演化规则及蚂蚁邻域的转移概率，并实现了算法的具体步骤．在Matlab环境下，采用该算法对一些典型的测试函数进行求解和验证．实验结果表明，该方法具有向真实的Pareto前沿逼近的效果，是一种求解多目标优化的有效方法．     

Firefly-inspired algorithm for discrete optimization problems: An application to manufacturing cell formation

The canonical firefly algorithm is basically developed for continuous optimization problems. However, lots of practical problems are formulated as discrete optimization problems. The main purpose of this paper is to present the discrete firefly algorithm (DFA) to solve discrete optimization problems. In the DFA, we define a firefly's position in terms of changes of probabilities that will be in one state or the other. Then by using this metaheuristic algorithm, the manufacturing cell formation problem is solved. To illustrate the behavior of the proposed model and verify the performance of the algorithm, we introduce a number of numerical examples to illustrate the use of the foregoing algorithm. The performance evaluation shows the effectiveness of the DFA. The proposed metaheuristic algorithm should thus be useful to both researchers and practitioners.     

Complete sets of initial vectors for pattern growth with elementary cellular automata

Computer simulations of complex spatio-temporal patterns using cellular automata may be performed in two alternative ways, the better choice depending on the relative size between the spatial width W of the expected patterns and their corresponding temporal period T. While the traditional timewise updating algorithm is very efficient when W?T, the complementary spacewise algorithm wins whenever T?W. Independently of the algorithm used, the key to obtaining exhaustive answers, not just statistical estimates, is to have explicit knowledge of the complete sets of initial conditions that need to be individually tested as sizes grow. This paper reports an efficient algorithm for generating complete sets (without redundancy) of k-vectors of initial conditions allowing one to perform definitive classifications of patterns in systems with a minimal characteristic length k, either spatial or temporal.     

蜂窝网络分布式中继选择算法

针对蜂窝网络中的功耗优化问题,研究了如何最小化两跳中继蜂窝网络的系统总功耗。首先根据信道传输功率的闭合表达式得到满足信道最小中断概率情况下的最优链路传输功率,然后通过使用基于Acknowledgement的分布式拍卖算法(DAA-ACK)和改进的分布式拍卖算法(IDAA)帮助用户节点选择合适的中继基站。仿真结果显示,这两种算法仅需要用户节点与邻居中继基站交换少量信息,并可通过有限次迭代快速选择出使系统总功率最小的中继节点。     

基本和混合元胞自动机的伪随机数发生器研究

针对基本元胞自动机（Cellular Automata,简称CA）、混合CA的伪随机数发生器进行了深入的研究,通过对比实验观察到混沌型基本CA输出的伪随机序列质量稳定并较优,而混合CA输出伪随机序列的相关性,尽管优于基本CA的平均表现,但远差于混沌型基本CA的表现。针对混合CA的伪随机数发生器,提出了一种基于混合CA与粒子群优化（Particle Swarm Optimization,简称PSO）算法融合的伪随机数产生算法。在该算法中,元胞对应于PSO的粒子,每个元胞按照各自不同的规则进行迭代演化,其对应粒子在迭代规则空间中飞行。该算法通过计算每个元胞产生伪随机序列的熵值作为粒子的适应度函数值,有效地实现每个元胞最佳规则的搜索,一定程度上提高了混合CA产生伪随机序列的质量。给出了基于小生境技术、构造出最优CA-PSO耦合伪随机数发生器的研究方向。     

改进的基于元胞自动机扩展模型的图的最短路径算法

在基于元胞自动机单源点到单节点图的最短路算法的基础之上,通过改进控制演化的终止条件和记录演化过程中的路径信息,提出了单源点到多节点的元胞自动机扩展模型求解图的最短路算法模型，将该算法应用于城市道路交通网的实证研究之中,可以得到路段上任意两端点之间的最短路径及路权。     

细胞自动机函数优化算法

细胞自动机广泛用于仿真、建模，提出用细胞自动机进行函数优化。该思想与演化算子结合的算法CAMGA在试验中取得了很好的效果。其中对BUMP问题的求解优于现今已经发表的结果。     

基于一维扩展元胞自动机的伪随机数发生器研究

随机数作为加密数据的载体,备受关注,自然,随机数发生器亦成为密码学的重要研究课题之一。依据元胞自动机(CA)的基本理论,构造出一维扩展元胞自动机模型,借以生成随机数发生器的元胞自动机规则,同时引进遗传算法(GA),以元胞状态序列的熵作为遗传演化的适应度,从而有效地实现最佳元胞自动机规则的搜索,即构造出特定初始条件下的最优GA-CA耦合随机数发生器。最后对其生成随机数性能进行统计检验,其结果通过美国联邦信息处理标准(FIPS140-2)。为网络安全应用提供一种新的、特别适合硬件实现的、简单快速的伪随机数发生器。