Calculating the extremal number ex (v ; {C3, C4, ..., Cn})
- Authors: Tang, Jianmin , Lin, Yuqing , Miller, Mirka
- Date: 2006
- Type: Text , Journal article
- Relation: Electronic Notes in Discrete Mathematics Vol. 27, no. (2006), p. 101-102
- Full Text: false
- Reviewed:
- Description: This paper introduces and analyzes a parallel method of simulated annealing. Borrowing from genetic algorithms, an effective combination of simulated annealing and genetic algorithms, called parallel recombinative simulated annealing, is developed. This new algorithm strives to retain the desirable asymptotic convergence properties of simulated annealing, while adding the populations approach and recombinative power of genetic algorithms. The algorithm iterates a population of solutions rather than a single solution, employing a binary recombination operator as well as a unary neighborhood operator. Proofs of global convergence are given for two variations of the algorithm. Convergence behavior is examined, and empirical distributions are compared to Boltzmann distributions. Parallel recombinative simulated annealing is amenable to straightforward implementation on SIMD, MIMD, or shared-memory machines. The algorithm, implemented on the CM-5, is run repeatedly on two deceptive problems to demonstrate the added implicit parallelism and faster convergence which can result from larger population sizes.
- Description: C1
HSAGA and its application for the construction of near-Moore digraphs
- Authors: Tang, Jianmin , Miller, Mirka , Lin, Yuqing
- Date: 2008
- Type: Text , Journal article
- Relation: Journal of Discrete Algorithms Vol. 6, no. 1 (2008), p. 73-84
- Full Text: false
- Reviewed:
- Description: The degree/diameter problem is to determine the largest graphs or digraphs of given maximum degree and given diameter. This paper deals with directed graphs. General upper bounds, called Moore bounds, exist for the largest possible order of such digraphs of maximum degree d and given diameter k. It is known that simulated annealing and genetic algorithm are effective techniques to identify global optimal solutions. This paper describes our attempt to build a Hybrid Simulated Annealing and Genetic Algorithm (HSAGA) that can be used to construct large digraphs. We present our new results obtained by HSAGA, as well as several related open problems. © 2007 Elsevier B.V. All rights reserved.
- Description: C1