基于改进的遗传算法的多目标优化问题研究

研究多目标优化算法问题,针对传统的多目标优化算法由于计算复杂度非常高,难以获得令人满意的解等问题,在图论和遗传算法基础上,提出了一种改进的遗传算法求解多目标优化方法。首先采用二进制编码表示最小树问题,然后采用深度优先搜索算法进行图的连通性判断,给出了一种新的适应度函数,以提高算法执行速度和进化效率。最后仿真结果表明,与经典的Prim算法和Kruskal算法相比,新算法复杂度较低,并能在第一次遗传进化过程中获得一批最小生成树,适合于解决不同类型的多目标最小树问题。     

基于改进遗传算法的最小生成树算法

以图论和改进遗传算法为基础,提出了一种求最小生成树的遗传算法。该算法采用二进制表示最小树问题,并设计出相应的适应度函数、算子以及几种控制策略,以提高执行速度和进化效率。传统算法一次只能得到一个候选解。用该算法对其求解,可以在较短的时间内以较高的概率获得多个候选解。应用实例表明该算法优于传统算法。     

求解多目标最小生成树的一种新的遗传算法

在改进的非支配排序遗传算法（NSGA-II）的基础上,提出了一种新的基于生成树边集合编码的繁殖算子求解多目标最小生成树问题的遗传算法。通过快速非支配排序法,降低了算法的计算复杂度,引入保存精英策略,扩大采样空间。实验结果表明：对于多目标最小生成树问题,边集合编码具有较好的遗传性和局部性,而且基于此繁殖算子的遗传算法在求解效率和解的质量方面都优于基于PrimRST的遗传算法。     

遗传算法在求解最小生成树中的运用

以图论和遗传算法为基础,提出了求解最小生成树问题的遗传算法。该算法解决了常用二进制编码不能正确表达最小生成树的问题,利用Prufer数对生成树进行编码;在遗传操作中对变异算子进行了改进,避免了由于变异产生大量不可行解。从而提高了遗传算法的效率;通过数值试验,表明该算法简单,高效,收敛率高。     

一种基于构建基因库求解TSP问题的遗传算法

在分析了已有的求解TSP问题的优化算法后,提出了一种将建立基因库(Ge)与遗传算法结合起来的新算法(Ge_GA)。该算法的目的是用基因库指导整个种群的进化,其核心问题是基因库的建立及如何将基因库运用到遗传算法中。试验结果表明,基因库有效地提高了群体演化的质量,局部搜索与全局搜索的结合大大提高了算法收敛速度。对于每个测试的实例,其结果与最优解的误差都不超过0.001％。特别是对难于求解的TSP问题,如pcb442和n1577,都能够在理想的时间内找到最优解。     

求解度约束最小生成树的新的遗传算法

针对度约束最小生成树问题的特征,设计了一种新的编码方式,并在此基础上提出了一个新遗传算法来求解该问题。该算法采用新的启发式杂交算子、变异算子和局部搜索算子,以概率1收敛到全局最优解。数值实验表明该算法优于文中提出的其他4种算法。     

基于prüfer数的遗传算法求解度约束最小树问题

度约束最小树问题属于NP-完全问题,是一类比较难解的问题,但在现实中具有非常重要的应用价值。探讨了如何将基于prüfer数的遗传算法应用于该问题,并给出了相应的算法。采用C语言和MATLAB的混合编程实现该算法,数值分析的结果显示了遗传算法求解该问题的有效性及其应用价值。     

求解多目标最小生成树问题的改进算法

多目标最小生成树问题是典型的NP问题,Zhou和Gen提出了一种用于计数多目标最小生成树问题的所有非劣最优最小生成树的算法,但该算法无法保证能够找到所有非劣最优最小生成树.针对此问题,提出一种改进的计数算法,并定性说明改进算法能够找到问题的所有非劣最优最小生成树.改进算法在进行子树剔除时增加了一些条件.模拟实验结果表明,改进后的计数算法能够找到所有的非劣最优解.这也说明该算法具有应用的潜力.     

遗传算法在人工智能中的应用

随着人工智能技术研究的不断深入,人工智能在现实生活中问题的应用也更加广泛,遗传算法就是人工智能中的一个分支,它的思想来自于大自然中优胜劣汰的自然定则,有着很强的适应性和可扩展性。本文就将通过介绍遗传算法在多目标最小生成树中的应用,来展示它在组合优化问题上与其他常规算法相比所具有的不可比拟的优势。     

基于多目标遗传算法求解多边谈判问题的Pareto解

首先介绍国外学者在该领域所做的研究,然后论述多边谈判问题中的解的概念,提出一种采用多目标遗传算法求解多边谈判问题解的方法,利用VC++编写了该方法的算法软件,并通过示例分析计算,说明了该方法的可行性和有效性。     

应用遗传算法的DSS模型设计研究

在DSS模型设计中，采用遗传程序设计可以更灵活地处理遗传算法中的表示问题。本文通过讨论遗传算法的特性，DSS模型库的特点而研究了DSS模型遗传程序设计的方法。     

Random-tree Diameter and the Diameter-constrained MST

A minimum spanning tree (MST) with a small diameter is required in numerous practical situations such as when distributed mutual-exclusion algorithms are used, or when information retrieval algorithms need to compromise between fast access and small storage. The Diameter-Constrained MST (DCMST) problem can be stated as follows: given an undirected, edge-weighted graph, G , with n nodes and a positive integer, k , find a spanning tree with the smallest weight among all spanning trees of G which contain no path with more than k edges. This problem is known to be NP-complete, for all values of k ; 4 h k h ( n m 2). In this paper, we investigate the behavior of the diameter of an MST in randomly generated graphs. Then, we present heuristics that produce approximate solutions for the DCMST problem in polynomial time. We discuss convergence, relative merits, and implementation of these heuristics. Our extensive empirical study shows that the heuristics produce good solutions for a wide variety of inputs.     

基于LEACH的簇树网络路由算法研究

分簇算法是目前无线传感器网络(WSN)研究的重点之一;在对LEACH算法(低功耗自适应聚类路由算法)进行研究分析的基础之上,针对LEACH算法中簇头节点与基站(BS)之间单跳通信能耗较大的问题,采用连通网络中最小生成树的Prim算法,提出了一种簇树网络路由算法;该算法使得簇头节点间通信代价耗费降低,仿真结果说明了该算法的可行性和有效性。     

基于遗传算法的平流层飞艇路径规划设计

利用传统线性化方法--小扰动法将模型线性化,结合平流层飞艇的工作特性,把飞艇上升运动看成是纵向基准运动和横侧向扰动运动.然后采用最小值原理,根据飞艇的控制量和边界条件,设计和优化飞艇的上升轨迹,其性能目标函数是从初始点到目标点运动过程中能量消耗最小.利用遗传算法,在运动模型和控制量变化的共同约束作用下,求取目标函数的最小值.最后根据飞艇实际工作过程,对仿真结果分析表明,该方法具有实际应用价值.     

基于生长树的遗传聚类算法研究

分析了目前基于目标函数聚类算法的不足,面对形状复杂且非重叠的样本聚类问题,定义了最邻近距离和生长树的概念。随机选取生长树初始种子点,以最邻近距离作为生长树生长的方向和样本划分依据,以最终生长树大小为聚类目标函数,引入遗传算法,提出基于生长树的遗传聚类算法,并通过实例进行了算法测试和比较。算法测试表明：基于生长树的遗传聚类算法对于形状复杂且非重叠样本的聚类是完全可行和有效的。     

基于高维空间稀疏最小生成树自适应覆盖模型的一类分类算法

最小生成树数据描述( MSTCD)在刻画高维空间样本点分布时,将所有图形的边作为新增虚拟样本以提供目标类样本分布描述,这种描述存在分支多、覆盖模型复杂的问题.针对该问题,依据特征空间中同类样本分布的连续性规律,文中提出基于稀疏最小生成树覆盖模型的一类分类算法.该方法首先构建目标类数据集的稀疏k近邻图表示,通过递归图分割...     

基于蚁群算法的多目标网络铺设策略研究

研究通信网络在不同目标下的铺设策略。为满足不同需求,建立网络终端之间的距离矩阵并将其转化为一个全连通无向赋权图。根据网络设计标准,以最低成本为唯一目标建立最短路径模型,利用Prim算法求解得到最小生成树。在最小生成树逻辑结构上建立稳定性度约束模型,给出满足度约束的铺设方案。综合考虑网络铺设的多方面影响因素,建立多目标组合优化模型,基于蚁群算法设计不同链路通断概率、不同链路数目和较高稳定性下的全局最优铺设策略。     

一种寻求MST的分布式算法

为解决最小生成树(MST)算法中的NP完全问题,使之适应实际网络环境的性能需求,提出一种寻求MST的分布式算法。该算法建立在MST性质的基础之上,利用数据融合逐步构建网络的MST。此过程不再需要传统洪泛连接信息,最多只需3×lbn次的信息交互,且去除了冗余信息。该算法具有收敛速度快、资源消耗低的特点。