A parallel genetic algorithm for the Steiner Problem in Networks

This paper presents a parallel genetic algorithm to the Steiner Problem in Networks. Several previous papers have proposed the adoption of GAs and others metaheuristics to solve the SPN demonstrating the validity of their approaches. This work differs from them for two main reasons: the dimension and the characteristics of the networks adopted in the experiments and the aim from which it has been originated. The reason that aimed this work was namely to build a comparison term for validating deterministic and computationally inexpensive algorithms which can be used in practical engineering applications, such as the multicast transmission in the Internet. On the other hand, the large dimensions of our sample networks require the adoption of a parallel implementation of the Steiner GA, which is able to deal with such large problem instances.

Synthesis of a systolic array genetic algorithm

The paper presents a design for a hardware genetic algorithm which uses a pipeline of systolic arrays. These arrays have been designed using systolic synthesis techniques which involve expressing the algorithm as a set of uniform recurrence relations. The final design divorces the fitness function evaluation from the hardware and can process chromosomes of different lengths, giving the design a generic quality. The paper demonstrates the design methodology by progressively re-writing a simple genetic algorithm, expressed in C code, into a form from which systolic structures can be deduced. This paper extends previous work by introducing a simplification to a previous systolic design for the genetic algorithm. The simplification results in the removal of 2N 2 + 4N cells and reduces the time complexity by 3N + 1 cycles.

The systolic array genetic algorithm, an example of systolic arrays as a reconfigurable design methodology

We advocate the use of systolic design techniques to create custom hardware for Custom Computing Machines. We have developed a hardware genetic algorithm based on systolic arrays to illustrate the feasibility of the approach. The architecture is independent of the lengths of chromosomes used and can be scaled in size to accommodate different population sizes. An FPGA prototype design can process 16 million genes per second.

Breeding distribution and population decline of globally threatened Grey-necked Picathartes Picathartes oreas in Mbam Minkom Mountain Forest, southern Cameroon

The Grey-necked Picathartes Picathartes oreas, considered 'Vulnerable', is an enigmatic ground-dwelling bird endemic to the central African equatorial rainforest and belongs to a family of only two species. Its distribution extends to the two Endemic Bird Areas within Cameroon (Guinea Congo forest biome and Cameroon mountain arc) and its population is thought to be in decline throughout its range due to increasing habitat fragmentation and disturbance. During March-April 2003 and June and October 2007 we surveyed Grey-necked Picathartes in the north-western region of the Mbam Minkom Mountain Forest. In January-March 2006 we surveyed the entire mountain range and found go breeding and 24 potential breeding sites, mostly located on the western slopes. From the complete survey, we estimated the population at 44 breeding individuals. Populations were highest in the north-west region but had apparently declined from 40 breeding individuals in 2003 to 20 in 2007. This region accounted for 41% of the entire population on the mountain range during the 2006 survey. The Mbam Minkom/Kala Important Bird Area was designated based on the presence of Grey-necked Picathartes but is under high pressure of imminent destruction from agricultural encroachment and illegal timber exploitation. These results have important implications for decision making in delimiting forest boundaries and core areas for protection in the development of management plans. We suggest possible remedial actions, appropriate repeatable methods for future monitoring and opportunities for community involvement in the management and conservation of the site.

Time patterns in UK demand for alcohol and tobacco: an application of the EM algorithm

Capturing the pattern of structural change is a relevant task in applied demand analysis, as consumer preferences may vary significantly over time. Filtering and smoothing techniques have recently played an increasingly relevant role. A dynamic Almost Ideal Demand System with random walk parameters is estimated in order to detect modifications in consumer habits and preferences, as well as changes in the behavioural response to prices and income. Systemwise estimation, consistent with the underlying constraints from economic theory, is achieved through the EM algorithm. The proposed model is applied to UK aggregate consumption of alcohol and tobacco, using quarterly data from 1963 to 2003. Increased alcohol consumption is explained by a preference shift, addictive behaviour and a lower price elasticity. The dynamic and time-varying specification is consistent with the theoretical requirements imposed at each sample point. (c) 2005 Elsevier B.V. All rights reserved.

Movements, activity patterns and home range of a female brown bear (Ursus arctos, L.) in the Rodopi Mountain Range, Greece

Movements and activity patterns of an adult radio-tagged female brown bear accompanied by her cubs were documented for the first time in Rodopi area (NE Greece) from August 2000 to July 2002. Average daily movements were 2.45 +/- 2.26 SD km, (range 0.15-8.5 km). The longest daily range could be related to human disturbance (hunting activity). The longest seasonal distance (211 km), during Summer 2001 coincided with the dissolution of the family. With cubs, the female was more active during daytime (73 % of all radio-readings) than when solitary (28 %). The female switched to a more crepuscular behaviour, after separation from the yearling (July 2001). According to pooled data from 924 activity - recording sessions, during the whole monitoring period, the female was almost twice as active during day time while rearing cubs (51 % active) than when solitary (23 %). The autumn and early winter home range size of the family was larger (280 km(2)) than after the separation from the cubs (59 km(2)). During the family group phase, home range size varied from 258 km(2) in autumn to 40 km(2) in winter (average denning period lasted 107 days : December 2000-March 2001). The bear hibernated in the Bulgarian part of the Rodopi Range during winters of 2001 and 2002.

Use of a novel Hill-climbing genetic algorithm in protein folding simulations

We have developed a novel Hill-climbing genetic algorithm (GA) for simulation of protein folding. The program (written in C) builds a set of Cartesian points to represent an unfolded polypeptide's backbone. The dihedral angles determining the chain's configuration are stored in an array of chromosome structures that is copied and then mutated. The fitness of the mutated chain's configuration is determined by its radius of gyration. A four-helix bundle was used to optimise simulation conditions, and the program was compared with other, larger, genetic algorithms on a variety of structures. The program ran 50% faster than other GA programs. Overall, tests on 100 non-redundant structures gave comparable results to other genetic algorithms, with the Hill-climbing program running from between 20 and 50% faster. Examples including crambin, cytochrome c, cytochrome B and hemerythrin gave good secondary structure fits with overall alpha carbon atom rms deviations of between 5 and 5.6 Angstrom with an optimised hydrophobic term in the fitness function. (C) 2003 Elsevier Ltd. All rights reserved.

Chromatographic alignment of LC-MS and LC-MS/MS datasets by genetic algorithm feature extraction

Liquid chromatography-mass spectrometry (LC-MS) datasets can be compared or combined following chromatographic alignment. Here we describe a simple solution to the specific problem of aligning one LC-MS dataset and one LC-MS/MS dataset, acquired on separate instruments from an enzymatic digest of a protein mixture, using feature extraction and a genetic algorithm. First, the LC-MS dataset is searched within a few ppm of the calculated theoretical masses of peptides confidently identified by LC-MS/MS. A piecewise linear function is then fitted to these matched peptides using a genetic algorithm with a fitness function that is insensitive to incorrect matches but sufficiently flexible to adapt to the discrete shifts common when comparing LC datasets. We demonstrate the utility of this method by aligning ion trap LC-MS/MS data with accurate LC-MS data from an FTICR mass spectrometer and show how hybrid datasets can improve peptide and protein identification by combining the speed of the ion trap with the mass accuracy of the FTICR, similar to using a hybrid ion trap-FTICR instrument. We also show that the high resolving power of FTICR can improve precision and linear dynamic range in quantitative proteomics. The alignment software, msalign, is freely available as open source.

Variable step LMS algorithm using the accumulated instantaneous error concept

The convergence speed of the standard Least Mean Square adaptive array may be degraded in mobile communication environments. Different conventional variable step size LMS algorithms were proposed to enhance the convergence speed while maintaining low steady state error. In this paper, a new variable step LMS algorithm, using the accumulated instantaneous error concept is proposed. In the proposed algorithm, the accumulated instantaneous error is used to update the step size parameter of standard LMS is varied. Simulation results show that the proposed algorithm is simpler and yields better performance than conventional variable step LMS.