首页 | 本学科首页   官方微博 | 高级检索  
相似文献
 共查询到20条相似文献,搜索用时 0 毫秒
1.
This paper presents a new exact maximum clique algorithm which improves the bounds obtained in state of the art approximate coloring by reordering the vertices at each step. Moreover, the algorithm can make full use of bit strings to sort vertices in constant time as well as to compute graph transitions and bounds efficiently, exploiting the ability of CPUs to process bitwise operations in blocks of size the ALU register word. As a result it significantly outperforms a current leading algorithm.  相似文献   

2.
A fast algorithm for the maximum weight clique problem   总被引:2,自引:0,他引:2  
L. Babel 《Computing》1994,52(1):31-38
We present a branch and bound method which finds a maximum weight clique in an arbitrary weighted graph. The main ingredients are a weighted coloring heuristic which simultaneously produces lower and upper bounds and a branching rule that uses the information obtained in the coloring. The algorithm performs comparable to the fastest method known so far but is much easier to implement.  相似文献   

3.
Simulated annealing technique has mostly been used to solve various optimization and learning problems, and it is well known that the maximum clique problem is one of the most studied NP-hard optimization problems owing to its numerous applications. In this note, a simple simulated annealing algorithm for the maximum clique problem is proposed and tested on all 80 DIMACS maximum clique instances. Although it is simple, the proposed simulated annealing algorithm is efficient on most of the DIMACS maximum clique instances. The simulation results show that the proposed simulated annealing algorithm outperforms a recent efficient simulated annealing algorithm proposed by Xu and Ma, and the solutions obtained by the proposed simulated annealing algorithm have the equal quality with those obtained by a recent trust region heuristic algorithm of Stanislav Busygin.  相似文献   

4.
An effective local search for the maximum clique problem   总被引:2,自引:0,他引:2  
We propose a variable depth search based algorithm, called k-opt local search (KLS), for the maximum clique problem. KLS efficiently explores the k-opt neighborhood defined as the set of neighbors that can be obtained by a sequence of several add and drop moves that are adaptively changed in the feasible search space. Computational results on DIMACS benchmark graphs indicate that KLS is capable of finding considerably satisfactory cliques with reasonable running times in comparison with those of state-of-the-art metaheuristics.  相似文献   

5.
In this paper, we present an evolutionary algorithm (EVA) for solving the resource-constrained project scheduling problem with minimum and maximum time lags (RCPSP/max). EVA works on a population consisting of several distance-order-preserving activity lists representing feasible or infeasible schedules. The algorithm uses the conglomerate-based crossover operator, the objective of which is to exploit the knowledge of the problem to identify and combine those good parts of the solution that have really contributed to its quality. In a recent paper, Valls et al. (European J. Oper. Res. 165, 375–386, 2005) showed that incorporating a technique called double justification (DJ) in RCPSP heuristic algorithms can produce a substantial improvement in the results obtained. EVA also applies two double justification operators DJmax and DJU adapted to the specific characteristics of problem RCPSP/max to improve all solutions generated in the evolutionary process. Computational results in benchmark sets show the merit of the proposed solution method.  相似文献   

6.
7.
8.
Evolutionary game-theoretic models and, in particular, the so-called replicator equations have recently proven to be remarkably effective at approximately solving the maximum clique and related problems. The approach is centered around a classic result from graph theory that formulates the maximum clique problem as a standard (continuous) quadratic program and exploits the dynamical properties of these models, which, under a certain symmetry assumption, possess a Lyapunov function. In this letter, we generalize previous work along these lines in several respects. We introduce a wide family of game-dynamic equations known as payoff-monotonic dynamics, of which replicator dynamics are a special instance, and show that they enjoy precisely the same dynamical properties as standard replicator equations. These properties make any member of this family a potential heuristic for solving standard quadratic programs and, in particular, the maximum clique problem. Extensive simulations, performed on random as well as DIMACS benchmark graphs, show that this class contains dynamics that are considerably faster than and at least as accurate as replicator equations. One problem associated with these models, however, relates to their inability to escape from poor local solutions. To overcome this drawback, we focus on a particular subclass of payoff-monotonic dynamics used to model the evolution of behavior via imitation processes and study the stability of their equilibria when a regularization parameter is allowed to take on negative values. A detailed analysis of these properties suggests a whole class of annealed imitation heuristics for the maximum clique problem, which are based on the idea of varying the parameter during the imitation optimization process in a principled way, so as to avoid unwanted inefficient solutions. Experiments show that the proposed annealing procedure does help to avoid poor local optima by initially driving the dynamics toward promising regions in state space. Furthermore, the models outperform state-of-the-art neural network algorithms for maximum clique, such as mean field annealing, and compare well with powerful continuous-based heuristics.  相似文献   

9.
Xia  Xiaoyun  Huang  Zhengxin  Peng  Xue  Chen  Zefeng  Xiang  Yi 《The Journal of supercomputing》2022,78(9):11949-11973
The Journal of Supercomputing - The maximum internal spanning tree (MIST) problem is to find a spanning tree with maximum number of internal node for an undirected graph. It is a variation of the...  相似文献   

10.
Wang RL  Tang Z  Cao QP 《Neural computation》2003,15(7):1605-1619
In this article, we present a solution to the maximum clique problem using a gradient-ascent learning algorithm of the Hopfield neural network. This method provides a near-optimum parallel algorithm for finding a maximum clique. To do this, we use the Hopfield neural network to generate a near-maximum clique and then modify weights in a gradient-ascent direction to allow the network to escape from the state of near-maximum clique to maximum clique or better. The proposed parallel algorithm is tested on two types of random graphs and some benchmark graphs from the Center for Discrete Mathematics and Theoretical Computer Science (DIMACS). The simulation results show that the proposed learning algorithm can find good solutions in reasonable computation time.  相似文献   

11.
In this paper, we solve the maximum agreement subtree problem for a set T of k rooted leaf-labeled evolutionary trees on n leaves where T contains a binary tree. We show that the O(kn3)-time dynamic-programming algorithm proposed by Bryant [Building trees, hunting for trees, and comparing trees: theory and methods in phylogenetic analysis, Ph.D. thesis, Dept. Math., University of Canterbury, 1997, pp. 174-182] can be implemented in O(kn2+n2logk−2nloglogn) and O(kn3−1/(k−1)) time by using multidimensional range search related data structures proposed by Gabow et al. [Scaling and related techniques for geometry problems, in: Proc. 16th Annual ACM Symp. on Theory of Computing, 1984, pp. 135-143] and Bentley [Multidimensional binary search trees in database applications, IEEE Trans. Softw. Eng. SE-5 (4) (1979) 333-340], respectively. When k<2+(logn−logloglogn)/(loglogn), the first implementation will be significantly faster than Bryant's algorithm. For k=3, it yields the best known algorithm which runs in O(n2lognloglogn)-time.  相似文献   

12.
Stochastic local search algorithms (SLS) have been increasingly applied to approximate solutions of the weighted maximum satisfiability problem (MAXSAT), a model for solutions of major problems in AI and combinatorial optimization. While MAXSAT instances have generally a strong intrinsic dependency between their variables, most of SLS algorithms start the search process with a random initial solution where the value of each variable is generated independently with the same uniform distribution. In this paper, we propose a new SLS algorithm for MAXSAT based on an unconventional distribution known as the Bose-Einstein distribution in quantum physics. It provides a stochastic initialization scheme to an efficient and very simple heuristic inspired by the co-evolution process of natural species and called Extremal Optimization (EO). This heuristic was introduced for finding high quality solutions to hard optimization problems such as colouring and partitioning. We examine the effectiveness of the resulting algorithm by computational experiments on a large set of test instances and compare it with some of the most powerful existing algorithms. Our results are remarkable and show that this approach is appropriate for this class of problems.  相似文献   

13.
14.
The vehicle routing problem with time windows is a complex combinatorial problem with many real-world applications in transportation and distribution logistics. Its main objective is to find the lowest distance set of routes to deliver goods, using a fleet of identical vehicles with restricted capacity, to customers with service time windows. However, there are other objectives, and having a range of solutions representing the trade-offs between objectives is crucial for many applications. Although previous research has used evolutionary methods for solving this problem, it has rarely concentrated on the optimization of more than one objective, and hardly ever explicitly considered the diversity of solutions. This paper proposes and analyzes a novel multi-objective evolutionary algorithm, which incorporates methods for measuring the similarity of solutions, to solve the multi-objective problem. The algorithm is applied to a standard benchmark problem set, showing that when the similarity measure is used appropriately, the diversity and quality of solutions is higher than when it is not used, and the algorithm achieves highly competitive results compared with previously published studies and those from a popular evolutionary multi-objective optimizer.  相似文献   

15.
The input to the metric maximum clustering problem with given cluster sizes consists of a complete graph G=(V,E) with edge weights satisfying the triangle inequality, and integers c1,…,cp. The goal is to find a partition of V into disjoint clusters of sizes c1,…,cp, maximizing the sum of weights of edges whose two ends belong to the same cluster. We describe an approximation algorithms for this problem with performance guarantee that approaches 0.5 when the cluster sizes are large.  相似文献   

16.
The survey of the relevant literatures shows that there have been many studies for portfolio optimization problems and that the number of studies which have investigated the optimum portfolio using evolutionary computation is quite large. But, almost none of these studies deals with genetic relation algorithm (GRA), where GRA is one of the evolutionary methods with graph structure. This study presents an approach to large-scale portfolio optimization problems using GRA with a new operator, called guided mutation. In order to pick up the most efficient portfolio, GRA considers the correlation coefficient between stock brands as strength, which indicates the relation between nodes in each individual of GRA. Guided mutation generates offspring according to the average value of correlation coefficients in each individual, which means to enhance the exploitation ability of evolution of GRA. A genetic relation algorithm with guided mutation (GRA/G) for the portfolio optimization is proposed in this paper. Genetic network programming (GNP), which was proposed in our previous research, is used to validate the performance of the portfolio generated with GRA/G. The results show that GRA/G approach is successful in portfolio optimization.  相似文献   

17.
18.
A self-stabilizing algorithm for the maximum flow problem   总被引:5,自引:0,他引:5  
Summary.  The maximum flow problem is a fundamental problem in graph theory and combinatorial optimization with a variety of important applications. Known distributed algorithms for this problem do not tolerate faults or adjust to dynamic changes in network topology. This paper presents a distributed self-stabilizing algorithm for the maximum flow problem. Starting from an arbitrary state, the algorithm computes the maximum flow in an acyclic network in finitely many steps. Since the algorithm is self-stabilizing, it is inherently tolerant to transient faults. It can automatically adjust to topology changes and to changes in other parameters of the problem. The paper presents results obtained by extensively experimenting with the algorithm. Two main observations based on these results are (1) the algorithm requires fewer than n 2 moves for almost all test cases and (2) the algorithm consistently performs at least as well as a distributed implementation of the well-known Goldberg-Tarjan algorithm for almost all test cases. The paper ends with the conjecture that the algorithm correctly computes a maximum flow even in networks that contain cycles. Received: October 1995 / Accepted: February 1997  相似文献   

19.
It is well known that timetabling problems can be very difficult to solve, especially when dealing with particularly large instances. Finding near-optimal results can prove to be extremely difficult, even when using advanced search methods such as evolutionary algorithms (EAs). The paper presents a method of decomposing larger problems into smaller components, each of which is of a size that the EA can effectively handle. Various experimental results using this method show that not only can the execution time be considerably reduced but also that the presented method can actually improve the quality of the solutions  相似文献   

20.
Approximating maximum clique with a Hopfield network   总被引:5,自引:0,他引:5  
In a graph, a clique is a set of vertices such that every pair is connected by an edge. MAX-CLIQUE is the optimization problem of finding the largest clique in a given graph and is NP-hard, even to approximate well. Several real-world and theory problems can be modeled as MAX-CLIQUE. In this paper, we efficiently approximate MAX-CLIQUE in a special case of the Hopfield network whose stable states are maximal cliques. We present several energy-descent optimizing dynamics; both discrete (deterministic and stochastic) and continuous. One of these emulates, as special cases, two well-known greedy algorithms for approximating MAX-CLIQUE. We report on detailed empirical comparisons on random graphs and on harder ones. Mean-field annealing, an efficient approximation to simulated annealing, and a stochastic dynamics are the narrow but clear winners. All dynamics approximate much better than one which emulates a "naive" greedy heuristic.  相似文献   

设为首页 | 免责声明 | 关于勤云 | 加入收藏

Copyright©北京勤云科技发展有限公司  京ICP备09084417号