图的Steiner最小树问题的混合遗传算法

图的Steiner最小树问题是经典的组合优化问题,在通信网络和电路设计中有广泛应用。文中在遗传算法的基础上,对交叉率pc和变异率pm采用自适应过程,构造一种新的确定pc和pm的公式,有效解决了参数选取对最终结果的影响问题。再与模拟退火算法相结合,提出了一种解决Steiner最小树问题的混合遗传算法。该算法克服了遗传算法易早熟和收敛性能差的缺点,有效地增强了算法的进化能力。通过对OR-Library的部分实例进行计算结果表明,在大多数情况下混合遗传算法比遗传算法有更好的性能。     

变邻域分解多目标自适应差分进化算法

分解方法是处理复杂问题常用的一种手段,而差分进化算法被广泛地应用于多目标优化问题(multiobjective optimization problems,MOP),为了克服经典差分进化算法和分解方法的缺陷,本文提出了一种自适应差分进化算法和变邻域分解方法相结合的新颖算法一ADEMO/D-ENS,该算法采用Tchebycheff方法将多目标优化问题分解成多维标量优化子问题,并利用邻域子问题的信息进行优化,基于邻域种群集依概率自适应选择邻域种群规模;同时采用概率匹配(]probability match,PM)自适应方法从差分策略池中选择差分进化策略;同时分析了算法的复杂度;最后,通过和经典的非支配排序遗传算法(non-dominated sorting genetic algorithmsⅡ,NSGA-Ⅱ)和多目标差分进化算法(multi-objective differential evolution algorithm,MODE)仿真对比,说明ADEMO/D-ENS方法可以更有效的处理多目标优化问题.     

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

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

数据驱动选择策略的多目标差分进化算法

针对多目标差分进化算法求解复杂多目标优化问题时,最优解选择策略中非支配排序计算复杂度高的问题,提出一种数据驱动选择策略的多目标差分进化(MODE-DDSS)算法.首先,设计多目标差分进化算法的优化解排序等级评估准则,建立基于评估准则的优化解排序等级评估库;其次,设计基于优化解双向搜索机制和无重复比较机制的数据驱动选择策略,实现优化解的高效搜索和快速排序;最后,构建数据驱动选择策略的多目标差分进化算法,降低算法在最优解选择操作中的时间复杂度,提高算法的寻优效率.实验结果表明,所提出的MODE-DDSS算法能够有效减少最优解在选择过程中的比较次数,提升多目标差分进化算法解决复杂多目标优化问题的寻优效率.     

解决多目标优化问题的几种进化算法的比较研究

进化算法具有适于解决多目标优化问题的特性,近来一直用于求解此类问题。群体智能优化算法是一种基于群体智能的进化算法,通过简单个体的交互表现出高度智能,大大增强了解决和处理优化问题的能力。分析了遗传算法、粒子群算法和混洗蛙跳算法的具体流程,比较了这三种进化算法的优劣。     

一种种群自适应收敛的快速遗传算法

作为一种全局搜索算法,遗传算法的局部搜索能力较低,后期产生的无效进化与早熟收敛影响优化的速度和精度。已有的改进策略多以算法的时间复杂度为代价提高后期效率,严重限制了遗传算法在工业控制系统中的应用。针对这种情况,提出了一种新型种群自适应收敛的快速遗传算法,即通过提高种群的遗传质量,在严格控制算法复杂度的前提下提高优化性能。仿真结果证明,在不增加时间复杂度的前提下,新算法显著地提升了收敛精度和收敛速度。     

一种子群体个数动态变化的多目标优化协同进化算法

给出一种新型的在多目标优化条件下的进化算法群体停滞判别准则，并基于该准则提出一种合作型多目标优化协同进化算法．该算法在运行过程中自适应地决定子群体的新增和灭绝．使得子群体个数依据需要动态变化，减小了对计算资源的消耗，并解决了对复杂多目标优化问题难以事先进行分解的问题．对所提算法的计算复杂度进行了理论分析，并把它与已有的多目标进化算法进行了比较，结果表明所提算法具有较高的搜索性能．     

基于元胞多目标遗传算法的蜗杆优化设计

为研究蜗杆传动的多目标优化问题,提出一种自适应差分进化的元胞多目标遗传算法。该算法针对元胞遗传算法的特点,对基本的差分进化策略进行改进,得到一种参数自适应控制策略。将该算法与目前性能优异的4种多目标进化算法在三目标的基准测试函数进行对比实验,结果表明所提算法相对于其他算法具有明显的优势,能够在保证良好收敛性的同时,使获得的Pareto前端分布性更加均匀,覆盖范围更广;工程实例求解结果也表明了算法的工程可行性。     

基于GA的网络最短路径多目标优化算法研究

针对现有基于遗传算法(GA)优化的网络最短路径算法存在优化目标单一、遗传编码质量低、搜索策略间平衡性差、适应度分配效率与灵活性较低等问题,建立一种多目标优化最短路径自适应GA模型,提出了优先级编码和优先级索引交叉算子,引入了遗传算子参数的模糊控制机制和基于自适应加权的适应度分配方法.实验结果表明,该算法的准确性和稳定性高、复杂度合理,实现了对网络设计优化中多目标最短路径问题的高质量求解.     

多目标遗传算法及在过程优化综合中的应用

化工过程的多目标优化综合问题可归结为多目标混合整数非线性规划(MOMINLP)模型的求解,求解方法主要有数学规划法和多目标进化算法。以多目标遗传算法(MOGA)为代表的进化算法被认为是特别适合求解此类问题。遗传算法大多用于单目标问题的优化,近十几年来将遗传算法应用到多目标优化的研究得到了很大的发展。本文对多目标遗传算法的一些重要概念、发展历程进行了回顾。针对化工过程的模型特点,对MOGA在过程综合中的应用研究进行了讨论,并认为混合遗传算法应是求解此类问题的有效算法。     

A new evolutionary approach to the degree-constrained minimumspanning tree problem

Finding the degree-constrained minimum spanning tree (d-MST) of a graph is a well-studied NP-hard problem of importance in communications network design and other network-related problems. In this paper we describe some previously proposed algorithms for solving the problem, and then introduce a novel tree construction algorithm called the randomized primal method (RPM) which builds degree-constrained trees of low cost from solution vectors taken as input. RPM is applied in three stochastic iterative search methods: simulated annealing, multistart hillclimbing, and a genetic algorithm. While other researchers have mainly concentrated on finding spanning trees in Euclidean graphs, we consider the more general case of random graph problems. We describe two random graph generators which produce particularly challenging d-MST problems. On these and other problems we find that the genetic algorithm employing RPM outperforms simulated annealing and multistart hillclimbing. Our experimental results provide strong evidence that the genetic algorithm employing RPM finds significantly lower-cost solutions to random graph d-MST problems than rival methods     

交通选线优化算法的设计与实现

将交通选线问题求解转化为最小生成树（Minimun Spanning Tree,MST）的求解,对比了经典MST求解算法,以图论为基础,采取一种求最小生成树的改进遗传算法．该算法以二进制编码表示最小树问题,用深度优先搜索算法进行图的连通性判断,并采用相应的适应度函数、单亲换位算子和单亲逆转算子及多种控制进化策略,能在一次遗传进化过程中获得一批最小生成树,可供决策部门综合评价与决策．     

A Flexible Algorithm for Generating All the Spanning Trees in Undirected Graphs

In this paper we propose an algorithm for generating all the spanning trees in undirected graphs. The algorithm requires O (n+m+ τ n) time where the given graph has n vertices, m edges, and τ spanning trees. For outputting all the spanning trees explicitly, this time complexity is optimal. Our algorithm follows a special rooted tree structure on the skeleton graph of the spanning tree polytope. The rule by which the rooted tree structure is traversed is irrelevant to the time complexity. In this sense, our algorithm is flexible. If we employ the depth-first search rule, we can save the memory requirement to O (n+m). A breadth-first implementation requires as much as O (m+ τ n) space, but when a parallel computer is available, this might have an advantage. When a given graph is weighted, the best-first search rule provides a ranking algorithm for the minimum spanning tree problem. The ranking algorithm requires O (n+ m + τ n) time and O (m+ τ n) space when we have a minimum spanning tree. Received January 21, 1995; revised February 19, 1996.     

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

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

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

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

求解多目标最小生成树的改进多目标蚁群算法

多目标最小生成树问题是典型的NP问题。针对此问题,提出一种改进的多目标蚁群算法。为获得更好的非劣前端,通过合理选取多个信息素扩散源与扩散策略来避免其早熟收敛,并引入非支配排序算子,提高种群多样性并避免算法过早陷入局部最优解。对比实验结果表明：对于多目标最小生成树问题,该算法是有效的,不但在求解效率和解的质量方面优于相关算法,而且随着问题规模的扩大,算法仍保持较好的性能。     

Low latency and energy efficient routing tree for wireless sensor networks with multiple mobile sinks

We propose the minimum Wiener index spanning tree (MWST) as a routing topology that is suitable for sensor networks with multiple mobile base nodes. However, it was proved that finding a spanning tree with the minimum Wiener index from a weighted graph is NP-hard. To address this problem and analyze the effectiveness of the MWST as the routing tree on sensor networks with multiple mobile base nodes, we designed two algorithms: a branch and bound algorithm for small-scale wireless sensor networks and a simulated annealing algorithm for large-scale wireless sensor networks. The simulation results show that MWST outperforms the minimum spanning tree (MST), one of the representative spanning trees used in many routing protocols for sensor networks, in terms of energy efficiency and packet delay.     

A graph approach to generate all possible regression submodels

A regression graph to enumerate and evaluate all possible subset regression models is introduced. The graph is a generalization of a regression tree. All the spanning trees of the graph are minimum spanning trees and provide an optimal computational procedure for generating all possible submodels. Each minimum spanning tree has a different structure and characteristics. An adaptation of a branch-and-bound algorithm which computes the best-subset models using the regression graph framework is proposed. Experimental results and comparison with an existing method based on a regression tree are presented and discussed.     

Algorithms for Computing the QR Decomposition of a Set of Matrices with Common Columns

The QR decomposition of a set of matrices which have common columns is investigated. The triangular factors of the QR decompositions are represented as nodes of a weighted directed graph. An edge between two nodes exists if and only if the columns of one of the matrices is a subset of the columns of the other. The weight of an edge denotes the computational complexity of deriving the triangular factor of the destination node from that of the source node. The problem is equivalent to constructing the graph and finding the minimum cost for visiting all the nodes. An algorithm which computes the QR decompositions by deriving the minimum spanning tree of the graph is proposed. Theoretical measures of complexity are derived and numerical results from the implementation of this and alternative heuristic algorithms are given.     

A learning automata-based heuristic algorithm for solving the minimum spanning tree problem in stochastic graphs

During the last decades, a host of efficient algorithms have been developed for solving the minimum spanning tree problem in deterministic graphs, where the weight associated with the graph edges is assumed to be fixed. Though it is clear that the edge weight varies with time in realistic applications and such an assumption is wrong, finding the minimum spanning tree of a stochastic graph has not received the attention it merits. This is due to the fact that the minimum spanning tree problem becomes incredibly hard to solve when the edge weight is assumed to be a random variable. This becomes more difficult if we assume that the probability distribution function of the edge weight is unknown. In this paper, we propose a learning automata-based heuristic algorithm to solve the minimum spanning tree problem in stochastic graphs wherein the probability distribution function of the edge weight is unknown. The proposed algorithm taking advantage of learning automata determines the edges that must be sampled at each stage. As the presented algorithm proceeds, the sampling process is concentrated on the edges that constitute the spanning tree with the minimum expected weight. The proposed learning automata-based sampling method decreases the number of samples that need to be taken from the graph by reducing the rate of unnecessary samples. Experimental results show the superiority of the proposed algorithm over the well-known existing methods both in terms of the number of samples and the running time of algorithm.