Abstract Genetic algorithms are a practical approach for finding near‐optimal solutions for nondeterministic polynomial‐hard problems. In this work we exploit the parallel processing capability of graphics processing units and Nvidia's CUDA programming platform to accelerate the island model genetic algorithm by modifying the evolutionary operations to fit the hardware architecture and have successfully achieved significant computational speedups.

MOTIVATION: The three dimensional tertiary structure of a protein at near atomic level resolution provides insight alluding to its function and evolution. As protein structure decides its functionality, similarity in structure usually implies similarity in function. As such, structure alignment techniques are often useful in the classifications of protein function. Given the rapidly growing rate of new, experimentally determined structures being made available from repositories such as the Protein Data Bank, fast and accurate computational structure comparison tools are required. This paper presents SPalignNS, a non-sequential protein structure alignment tool using a novel asymmetrical greedy search technique. RESULTS: The performance of SPalignNS was evaluated against existing sequential and non-sequential structure alignment methods by performing trials with commonly used datasets. These benchmark datasets used to gauge alignment accuracy include (i) 9538 pairwise alignments implied by the HOMSTRAD database of homologous proteins; (ii) a subset of 64 difficult alignments from set (i) that have low structure similarity; (iii) 199 pairwise alignments of proteins with similar structure but different topology; and (iv) a subset of 20 pairwise alignments from the RIPC set. SPalignNS is shown to achieve greater alignment accuracy (lower or comparable root-mean squared distance with increased structure overlap coverage) for all datasets, and the highest agreement with reference alignments from the challenging dataset (iv) above, when compared with both sequentially constrained alignments and other non-sequential alignments. AVAILABILITY AND IMPLEMENTATION: SPalignNS was implemented in C++. The source code, binary executable, and a web server version is freely available at: http://sparks-lab.org CONTACT: [email protected].

This paper presents the results obtained using an unbiased Population Based Search (PBS) for optimising Morse atomic clusters. PBS is able to repeatedly obtain all putative global minima for Morse clusters in the range 5 ≤ N ≤ 80, N = 147, ρ = 3,6,10, 14, as reported in the Cambridge Cluster Database. In addition, putative global minima have been established for Morse clusters in the range 81 ≤ N ≤ 146, ρ = 14. The PBS algorithm incorporates and extends key techniques that have been developed in other cluster optimisation algorithms over the last decade. Of particular importance are the use of cut and paste operators, structure niching and a new operator, Directed Optimisation, which extends the previous concept of directed mutation. In addition, PBS is able to operate in a parallel mode for optimising larger clusters.

The p-median problem is one of choosing p facilities from a set of candidates to satisfy the demands of n clients such that the overall cost is minimised. In this paper, PBS, a population based hybrid search algorithm for the p-median problem is introduced. The PBS algorithm uses a genetic algorithm based meta-heuristic, primarily based on cut and paste crossover operators, to generate new starting points for a hybrid local search. For larger p-median instances, PBS is able to effectively utilise a number of computer processors. It is shown empirically that PBS is able to effectively solve p-median problems for a large range of the commonly used p-median benchmark instances.

The p-center problem is one of choosing p facilities from a set of candidates to satisfy the demands of n clients in order to minimize the maximum cost between a client and the facility to which it is assigned. In this article, PBS, a population based meta-heuristic for the p-center problem, is described. PBS is a genetic algorithm based meta-heuristic that uses phenotype crossover and directed mutation operators to generate new starting points for a local search. For larger p-center instances, PBS is able to effectively utilize a number of computer processors. It is shown empirically that PBS has comparable performance to state-of-the-art exact and approximate algorithms for a range of p-center benchmark instances.

In this paper, we introduce DLS-MC, a new stochastic local search algorithm for the maximum clique problem. DLS-MC alternates between phases of iterative improvement, during which suitable vertices are added to the current clique, and plateau search, during which vertices of the current clique are swapped with vertices not contained in the current clique. The selection of vertices is solely based on vertex penalties that are dynamically adjusted during the search, and a perturbation mechanism is used to overcome search stagnation. The behaviour of DLS-MC is controlled by a single parameter, penalty delay, which controls the frequency at which vertex penalties are reduced. We show empirically that DLS-MC achieves substantial performance improvements over state-of-the-art algorithms for the maximum clique problem over a large range of the commonly used DIMACS benchmark instances.

The combination of local optimisation heuristics and genetic algorithms has been shown to be an effective approach for finding near-optimum solutions to the travelling salesman problem (TSP). In problem domains where the problem can be represented geometrically, such as networks and chemical structures, the combination of local optimisation operators and phenotype genetic operators has also been an effective approach. This paper evaluates the combination of local optimisation heuristics and phenotype genetic operators when applied to the TSP. The local optimisation heuristics reduce the search domain, while the phenotype genetic operators eliminate the creation of invalid tours and also assist the generation of suboptimal schema. The implementation of the genetic algorithm is described and results presented.

It is generally accepted that survivable networks tend to consist of network elements (nodes and links) where no individual element is significantly more important than any other element. Using a traffic based network survivability metric Si, which quantifies the impact of removing network element i from a network of N elements, this paper investigates the modification of link capacities to simultaneously maximise average network survivability (1/N/spl Sigma//sub i=1//sup N/S/sub i/) and minimise the variability of Si (var(Si)). For some networks there appears to be an unique optimal set of link capacities however, for others, a number of possible optima exist. For these networks a Pareto-optimal set was generated so that a decision could be made on which link enhancements should be performed. The change in optima as a consequence of changes in the budget for link enhancements and also in changes in the required network traffic load were also investigated.