Edge exchanges in the degree-constrained minimum spanning tree problem

We describe a branch and bound algorithm to solve the degree-constrained minimum spanning tree problem. We propose an edge exchange analysis frequently used in the algorithm and three types of heuristic methods. Computational results are reported for problems with up to 200 vertices. These results are much better than known results from the literature.     

求解度约束最小生成树的新的快速算法

针对度约束最小生成树问题,提出了一种新的快速算法。新的快速算法分为两个主要部分,第一部分从一棵最小生成树出发,构造一棵度约束树。第二部分设计了一种改进策略,从第一部分求得的度约束树出发,每次去掉树的一条边,将顶点按照连通性划分成两个集合,在不违反度约束的情况下,从这两个集合构成的边割中,选择一条权值减少最大的边添加到图中。通过大量的数值实验表明新的快速算法性能良好。     

A hybrid evolutionary approach to the registration area planning problem

The last two decades have witnessed a phenomenal growth in the number of cellular wireless network users which in turn stressed the need to utilize the limited network bandwidth in an efficient manner. The network bandwidth is consumed not only by user traffic, but also by control traffic needed for ensuring the mobility of users. As we don’t have any control over the volume of user traffic, all attempts to efficiently use bandwidth are based on frequency reuse and minimizing the control traffic. The registration area planning (RAP) problem seeks a partition of the cells of the network into contiguous areas called registration areas so that the bandwidth consumed by control signals is minimized. RAP problem in an \(\mathcal {NP}\) -Hard problem. In this paper, we present a steady-state grouping genetic algorithm with local search to solve this problem. We have compared our approach with the state-of-the-art approaches reported in the literature. Computational results show the effectiveness of our approach.     

A swarm intelligence approach to the quadratic minimum spanning tree problem

The quadratic minimum spanning tree problem (Q-MST) is an extension of the minimum spanning tree problem (MST). In Q-MST, in addition to edge costs, costs are also associated with ordered pairs of distinct edges and one has to find a spanning tree that minimizes the sumtotal of the costs of individual edges present in the spanning tree and the costs of the ordered pairs containing only edges present in the spanning tree. Though MST can be solved in polynomial time, Q-MST is NP-Hard. In this paper we present an artificial bee colony (ABC) algorithm to solve Q-MST. The ABC algorithm is a new swarm intelligence approach inspired by intelligent foraging behavior of honey bees. Computational results show the effectiveness of our approach.     

A new approach to the surface intersection problem

Planar cut and surface intersection software is an important part of any computer aided design system. This paper presents two new ideas in the numerical solution of such problems. The first is the notion of topology resolution. In this process, the structure of the intersection curves, including the identification of closed interior loops, is determined prior to their actual numerical solution. The second idea is to compute the intersection curves as the numerical solution of a differential algebraic equation, yielding intersection curves which are (nearly) parametrized by arclength.     

Human evolutionary model: A new approach to optimization

The aim of this paper is to propose the Human Evolutionary Model (HEM) as a novel computational method for solving search and optimization problems with single or multiple objectives. HEM is an intelligent evolutionary optimization method that uses consensus knowledge from experts with the aim of inferring the most suitable parameters to achieve the evolution in an intelligent way. HEM is able to handle experts’ knowledge disagreements by the use of a novel concept called Mediative Fuzzy Logic (MFL). The effectiveness of this computational method is demonstrated through several experiments that were performed using classical test functions as well as composite test functions. We are comparing our results against the results obtained with the Genetic Algorithm of the Matlab’s Toolbox, Evolution Strategy with Covariance Matrix Adaptation (CMA-ES), Particle Swarm Optimizer (PSO), Cooperative PSO (CPSO), G3 model with PCX crossover (G3-PCX), Differential Evolution (DE), and Comprehensive Learning PSO (CLPSO). The results obtained using HEM outperforms the results obtained using the abovementioned optimization methods.     

A dandelion-encoded evolutionary algorithm for the delay-constrained capacitated minimum spanning tree problem

This paper proposes an evolutionary algorithm with Dandelion-encoding to tackle the Delay-Constrained Capacitated Minimum Spanning Tree (DC-CMST) problem. This problem has been recently proposed, and consists of finding several broadcast trees from a source node, jointly considering traffic and delay constraints in trees. A version of the problem in which the source node is also included in the optimization process is considered as well in the paper. The Dandelion code used in the proposed evolutionary algorithm has been recently proposed as an effective way of encoding trees in evolutionary algorithms. Good properties of locality has been reported on this encoding, which makes it very effective to solve problems in which the solutions can be expressed in form of trees. In the paper we describe the main characteristics of the algorithm, the implementation of the Dandelion-encoding to tackled the DC-CMST problem and a modification needed to include the source node in the optimization. In the experimental section of this article we compare the results obtained by our evolutionary with that of a recently proposed heuristic for the DC-CMST, the Least Cost (LC) algorithm. We show that our Dandelion-encoded evolutionary algorithm is able to obtain better results that the LC in all the instances tackled.     

A hybrid evolutionary approach for solving the ontology alignment problem

Ontologies are recognized as a fundamental component for enabling interoperability across heterogeneous systems and applications. Indeed, they try to fit a common understanding of concepts in a particular domain of interest to support the exchange of information among people, artificial agents, and distributed applications. Unfortunately, because of human subjectivity, various ontologies related to the same application domain may use different terms for the same meaning or may use the same term to mean different things, raising the so‐called heterogeneity problem. The ontology alignment process tries to solve this semantic gap by individuating a collection of similar entities belonging to different ontologies and enabling a full comprehension among different actors involved in a given knowledge exchanging. However, the complexity of the alignment task, especially for large ontologies, requires an automated and effective support for computing high‐quality alignments. The aim of this paper is to propose a memetic algorithm to perform an efficient matching process capable of computing a suboptimal alignment between two ontologies. As shown by experiments, the memetic approach is more suitable for ontology alignment problem than a classical evolutionary technique such as genetic algorithms. © 2012 Wiley Periodicals, Inc.     

A new approach to fuzzy initial value problem

In this paper, we consider a high-order linear differential equation with fuzzy initial values. We present solution as a fuzzy set of real functions such that each real function satisfies the initial value problem by some membership degree. Also we propose a method based on properties of linear transformations to find the fuzzy solution. We find out the solution determined by our method coincides with one of the solutions obtained by the extension principle method. Some examples are presented to illustrate applicability of the proposed method.     

A new algorithm for solving the tree isomorphism problem

The problem and known algorithms for its solution are briefly discussed. An efficient algorithm for canonical coding of unlabelled trees is described. Several applications of the code, including the tree isomorphism problem, are considered. Efficiency of the algorithm is evaluated and discussed.     

An evolutionary approach to generalized biobjective traveling salesperson problem

We consider the generalized biobjective traveling salesperson problem, where there are a number of nodes to be visited and each node pair is connected by a set of edges. The final route requires finding the order in which the nodes are visited (tours) and finding edges to follow between the consecutive nodes of the tour. We exploit the characteristics of the problem to develop an evolutionary algorithm for generating an approximation of nondominated points. For this, we approximate the efficient tours using approximate representations of the efficient edges between node pairs in the objective function space. We test the algorithm on several randomly-generated problem instances and our experiments show that the evolutionary algorithm approximates the nondominated set well.     

A new numerical approach to a non-steady filtration problem

A free-boundary transient problem of seepage flow is studied from a numerical standpoint. From a suitable formulation of the problem in terms of variational inequality we introduce a new numerical approach of the implicit type and based on the finite element method. In this approach the problem is solved on a fixed region and the position of the free boundary is automatically found as part of the solution of the problem; so it is not necessary to solve a succession of problems with different positions of the free boundary. We prove stability and convergence for the approximate solution and we give several numerical results. Work supported by C. N. R. of Italy through the Laboratorio di Analisi Numerica of Pavia.     

An evolutionary approach for the nurse rerostering problem

The personnel scheduler constructs a deterministic personnel roster that determines the line-of-work for each personnel member. When unexpected events disrupt this roster, the feasibility needs to be restored by constructing a new workable roster. The scheduler must reassign the set of employees in order to cover the disrupted shift such that the staffing requirements and the time-related personnel constraints remain satisfied. In this paper, we propose an evolutionary meta-heuristic to solve the nurse rerostering problem. We show that the proposed procedure performs consistently well under many different circumstances. We test different optimisation strategies and compare our procedure with the existing literature on a dataset that is carefully designed in a controlled and varied way.     

A new approach to estimating the expected first hitting time of evolutionary algorithms

Evolutionary algorithms (EA) have been shown to be very effective in solving practical problems, yet many important theoretical issues of them are not clear. The expected first hitting time is one of the most important theoretical issues of evolutionary algorithms, since it implies the average computational time complexity. In this paper, we establish a bridge between the expected first hitting time and another important theoretical issue, i.e., convergence rate. Through this bridge, we propose a new general approach to estimating the expected first hitting time. Using this approach, we analyze EAs with different configurations, including three mutation operators, with/without population, a recombination operator and a time variant mutation operator, on a hard problem. The results show that the proposed approach is helpful for analyzing a broad range of evolutionary algorithms. Moreover, we give an explanation of what makes a problem hard to EAs, and based on the recognition, we prove the hardness of a general problem.     

A factoring approach for the Steiner tree problem in undirected networks

In communication networks, many applications, such as video on demand and video conferencing, must establish a communications tree that spans a subset K in a vertex set. The source node can then send identical data to all nodes in set K along this tree. This kind of communication is known as multicast communication. A network optimization problem, called the Steiner tree problem (STP), is presented to find a least cost multicasting tree. In this paper, an O(|E|) algorithm is presented to find a minimum Steiner tree for series-parallel graphs where |E| is the number of edges. Based on this algorithm, we proposed an O(2^2c·|E|) algorithm to solve the Steiner tree problem for general graphs where c is the number of applied factoring procedures. The c value is strongly related to the topology of a given graph. This is quite different from other algorithms with exponential time complexities in |K|.     

基于度约束最短传输树的多路径传输协议

无线传感网络因为它的应用领域广泛性,在工业领域和理论研究领域得到了越来越多的关注。针对传输网络的数据传输可靠性的问题,提出了一种基于度约束最短传输树的多路径传输协议,该协议实现了网络中每个节点均有两条互不相关路径到达汇聚节点并且传输距离最短,同时对子节点的数量进行约束,减少了“热点问题”的发生。针对多汇聚节点网络中部署问题,提出了中间位置优选策略和边缘位置优选策略,对网络的鲁棒性和均衡节点负载进行了分析。通过实验验证了基于该协议的传输网络具有很强的健壮性和抗干扰性。     

A new evolutionary approach to cutting stock problems with and without contiguity

Evolutionary algorithms (EAs) have been applied to many optimization problems successfully in recent years. The genetic algorithm (GAs) and evolutionary programming (EP) are two different types of EAs. GAs use crossover as the primary search operator and mutation as a background operator, while EP uses mutation as the primary search operator and does not employ any crossover. This paper proposes a novel EP algorithm for cutting stock problems with and without contiguity. Two new mutation operators are proposed. Experimental studies have been carried out to examine the effectiveness of the EP algorithm. They show that EP can provide a simple yet more effective alternative to GAs in solving cutting stock problems with and without contiguity. The solutions found by EP are significantly better (in most cases) than or comparable to those found by GAs.Scope and purposeThe one-dimensional cutting stock problem (CSP) is one of the classical combinatorial optimization problems. While most previous work only considered minimizing trim loss, this paper considers CSPs with two objectives. One is the minimization of trim loss (i.e., wastage). The other is the minimization of the number of stocks with wastage, or the number of partially finished items (pattern sequencing or contiguity problem). Although some traditional OR techniques (e.g., programming based approaches) can find the global optimum for small CSPs, they are impractical to find the exact global optimum for large problems due to combinatorial explosion. Heuristic techniques (such as various hill-climbing algorithms) need to be used for large CSPs. One of the heuristic algorithms which have been applied to CSPs recently with success is the genetic algorithm (GA). This paper proposes a much simpler evolutionary algorithm than the GA, based on evolutionary programming (EP). The EP algorithm has been shown to perform significantly better than the GA for most benchmark problems we used and to be comparable to the GA for other problems.     

EvoGeneSys,a new evolutionary approach to graph generation

Graphs are widely used to represent complex and structured information of interest in various fields of science and engineering. When using graph representations, problems of special interest often imply searching. For example, searching for the prototypes representing a dataset of graphs or for the graph that optimizes a set of parameters. In any case, it is necessary that the problem solution be expressed in terms of graphs. Therefore, defining effective methods for automatically generating single graphs, or sets of graphs, representing problem solutions, is a key issue. A new evolutionary computation-based approach specifically devised for generating graphs is presented. The method is based on a special data structure, called multilist, which allows the encoding of any type of graph, directed or undirected, with or without attributes. Graph encoding by multilists makes it possible to define effective crossover and mutation operators, overcoming the problems normally encountered when implementing genetic operators on graphs. Further advantages of the proposed approach are that it does not require any problem specific knowledge and it is able to search for graphs whose number of nodes is not known a priori. Three sets of experiments were performed to test the proposed approach and the solutions found were compared with those obtained by other approaches proposed in the literature.