Jointly multi-user detection and channel estimation with genetic algorithm

This work aims at proposing the use of the evolutionary computation methodology in order to jointly solve the multiuser channel estimation (MuChE) and detection problems at its maximum-likelihood, both related to the direct sequence code division multiple access (DS/CDMA). The effectiveness of the proposed heuristic approach is proven by comparing performance and complexity merit figures with that obtained by traditional methods found in literature. Simulation results considering genetic algorithm (GA) applied to multipath, DS/CDMA and MuChE and multi-user detection (MuD) show that the proposed genetic algorithm multi-user channel estimation (GAMuChE) yields a normalized mean square error estimation (nMSE) inferior to 11%, under slowly varying multipath fading channels, large range of Doppler frequencies and medium system load, it exhibits lower complexity when compared to both maximum likelihood multi-user channel estimation (MLMuChE) and gradient descent method (GrdDsc). A near-optimum multi-user detector (MuD) based on the genetic algorithm (GAMuD), also proposed in this work, provides a significant reduction in the computational complexity when compared to the optimum multi-user detector (OMuD). In addition, the complexity of the GAMuChE and GAMuD algorithms were (jointly) analyzed in terms of number of operations necessary to reach the convergence, and compared to other jointly MuChE and MuD strategies. The joint GAMuChE-GAMuD scheme can be regarded as a promising alternative for implementing third-generation (3G) and fourth-generation (4G) wireless systems in the near future. Copyright (C) 2010 John Wiley & Sons, Ltd.

Evaluation of algorithms used to order markers on genetic maps

When building genetic maps, it is necessary to choose from several marker ordering algorithms and criteria, and the choice is not always simple. In this study, we evaluate the efficiency of algorithms try (TRY), seriation (SER), rapid chain delineation (RCD), recombination counting and ordering (RECORD) and unidirectional growth (UG), as well as the criteria PARF (product of adjacent recombination fractions), SARF (sum of adjacent recombination fractions), SALOD (sum of adjacent LOD scores) and LHMC (likelihood through hidden Markov chains), used with the RIPPLE algorithm for error verification, in the construction of genetic linkage maps. A linkage map of a hypothetical diploid and monoecious plant species was simulated containing one linkage group and 21 markers with fixed distance of 3 cM between them. In all, 700 F(2) populations were randomly simulated with and 400 individuals with different combinations of dominant and co-dominant markers, as well as 10 and 20% of missing data. The simulations showed that, in the presence of co-dominant markers only, any combination of algorithm and criteria may be used, even for a reduced population size. In the case of a smaller proportion of dominant markers, any of the algorithms and criteria (except SALOD) investigated may be used. In the presence of high proportions of dominant markers and smaller samples (around 100), the probability of repulsion linkage increases between them and, in this case, use of the algorithms TRY and SER associated to RIPPLE with criterion LHMC would provide better results. Heredity (2009) 103, 494-502; doi:10.1038/hdy.2009.96; published online 29 July 2009

Grid job scheduling using Route with Genetic Algorithm support

In 2006 the Route load balancing algorithm was proposed and compared to other techniques aiming at optimizing the process allocation in grid environments. This algorithm schedules tasks of parallel applications considering computer neighborhoods (where the distance is defined by the network latency). Route presents good results for large environments, although there are cases where neighbors do not have an enough computational capacity nor communication system capable of serving the application. In those situations the Route migrates tasks until they stabilize in a grid area with enough resources. This migration may take long time what reduces the overall performance. In order to improve such stabilization time, this paper proposes RouteGA (Route with Genetic Algorithm support) which considers historical information on parallel application behavior and also the computer capacities and load to optimize the scheduling. This information is extracted by using monitors and summarized in a knowledge base used to quantify the occupation of tasks. Afterwards, such information is used to parameterize a genetic algorithm responsible for optimizing the task allocation. Results confirm that RouteGA outperforms the load balancing carried out by the original Route, which had previously outperformed others scheduling algorithms from literature.

Change and Aging Senescence as an Adaptation

Understanding why we age is a long-lived open problem in evolutionary biology. Aging is prejudicial to the individual, and evolutionary forces should prevent it, but many species show signs of senescence as individuals age. Here, I will propose a model for aging based on assumptions that are compatible with evolutionary theory: i) competition is between individuals; ii) there is some degree of locality, so quite often competition will be between parents and their progeny; iii) optimal conditions are not stationary, and mutation helps each species to keep competitive. When conditions change, a senescent species can drive immortal competitors to extinction. This counter-intuitive result arises from the pruning caused by the death of elder individuals. When there is change and mutation, each generation is slightly better adapted to the new conditions, but some older individuals survive by chance. Senescence can eliminate those from the genetic pool. Even though individual selection forces can sometimes win over group selection ones, it is not exactly the individual that is selected but its lineage. While senescence damages the individuals and has an evolutionary cost, it has a benefit of its own. It allows each lineage to adapt faster to changing conditions. We age because the world changes.

Endothelial nitric oxide synthase polymorphisms and adaptation of parasympathetic modulation to exercise training

SILVA, B. M., F. J. NEVES, M. V. NEGRÃO, C. R. ALVES, R. G. DIAS, G. B. ALVES, A. C. PEREIRA, M. Urbana A. RONDON, J. E. KRIEGER, C. E. NEGRÃO, and A. C. DA NOBREGA. Endothelial Nitric Oxide Synthase Polymorphisms and Adaptation of Parasympathetic Modulation to Exercise Training. Med. Sci. Sports Exerc., Vol. 43, No. 9, pp. 1611-1618, 2011. Purpose: There is a large interindividual variation in the parasympathetic adaptation induced by aerobic exercise training, which may be partially attributed to genetic polymorphisms. Therefore, we investigated the association among three polymorphisms in the endothelial nitric oxide gene (-786T>C, 4b4a, and 894G>T), analyzed individually and as haplotypes, and the parasympathetic adaptation induced by exercise training. Methods: Eighty healthy males, age 20-35 yr, were genotyped by polymerase chain reaction-restriction fragment length polymorphism analysis, and haplotypes were inferred using the software PHASE 2.1. Autonomic modulation (i.e., HR variability and spontaneous baroreflex sensitivity) and peak oxygen consumption ((V) over dotO(2peak)) were measured before and after training (running, moderate to severe intensity, three times per week, 60 min.day(-1), during 18 wk). Results: Training increased (V) over dotO(2peak) (P < 0.05) and decreased mean arterial pressure (P < 0.05) in the whole sample. Subjects with the -786C polymorphic allele had a significant reduction in baroreflex sensitivity after training (change: wild type (-786TT) = 2% +/- 89% vs polymorphic (-786TC/CC) = -28% +/- 60%, median +/- quartile range, P = 0.03), and parasympathetic modulation was marginally reduced in subjects with the 894T polymorphic allele (change: wild type (894GG) = 8% +/- 67% vs polymorphic (894GT/TT) = -18% +/- 59%, median +/- quartile range, P = 0.06). Furthermore, parasympathetic modulation percent change was different between the haplotypes containing wild-type alleles(-786T/4b/894G) and polymorphic alleles at positions -786 and 894 (-786C/4b/894T) (-6% +/- 56% vs -41% +/- 50%, median T quartile range, P = 0.04). Conclusions: The polymorphic allele at position -786 and the haplotype containing polymorphic alleles at positions -786 and 894 in the endothelial nitric oxide gene were associated with decreased parasympathetic modulation after exercise training.

Gait Pattern Adaptation for an Active Lower-Limb Orthosis Based on Neural Networks

This work deals with neural network (NN)-based gait pattern adaptation algorithms for an active lower-limb orthosis. Stable trajectories with different walking speeds are generated during an optimization process considering the zero-moment point (ZMP) criterion and the inverse dynamic of the orthosis-patient model. Additionally, a set of NNs is used to decrease the time-consuming analytical computation of the model and ZMP. The first NN approximates the inverse dynamics including the ZMP computation, while the second NN works in the optimization procedure, giving an adapted desired trajectory according to orthosis-patient interaction. This trajectory adaptation is added directly to the trajectory generator, also reproduced by a set of NNs. With this strategy, it is possible to adapt the trajectory during the walking cycle in an on-line procedure, instead of changing the trajectory parameter after each step. The dynamic model of the actual exoskeleton, with interaction forces included, is used to generate simulation results. Also, an experimental test is performed with an active ankle-foot orthosis, where the dynamic variables of this joint are replaced in the simulator by actual values provided by the device. It is shown that the final adapted trajectory follows the patient intention of increasing the walking speed, so changing the gait pattern. (C) Koninklijke Brill NV, Leiden, 2011

A Constructive Genetic Algorithm for permutation flowshop scheduling

The general flowshop scheduling problem is a production problem where a set of n jobs have to be processed with identical flow pattern on in machines. In permutation flowshops the sequence of jobs is the same on all machines. A significant research effort has been devoted for sequencing jobs in a flowshop minimizing the makespan. This paper describes the application of a Constructive Genetic Algorithm (CGA) to makespan minimization on flowshop scheduling. The CGA was proposed recently as an alternative to traditional GA approaches, particularly, for evaluating schemata directly. The population initially formed only by schemata, evolves controlled by recombination to a population of well-adapted structures (schemata instantiation). The CGA implemented is based on the NEH classic heuristic and a local search heuristic used to define the fitness functions. The parameters of the CGA are calibrated using a Design of Experiments (DOE) approach. The computational results are compared against some other successful algorithms from the literature on Taillard`s well-known standard benchmark. The computational experience shows that this innovative CGA approach provides competitive results for flowshop scheduling; problems. (C) 2007 Elsevier Ltd. All rights reserved.

A Taxonomy for Locality Algorithms on Peer-to-Peer Networks

The continuous growth of peer-to-peer networks has made them responsible for a considerable portion of the current Internet traffic. For this reason, improvements in P2P network resources usage are of central importance. One effective approach for addressing this issue is the deployment of locality algorithms, which allow the system to optimize the peers` selection policy for different network situations and, thus, maximize performance. To date, several locality algorithms have been proposed for use in P2P networks. However, they usually adopt heterogeneous criteria for measuring the proximity between peers, which hinders a coherent comparison between the different solutions. In this paper, we develop a thoroughly review of popular locality algorithms, based on three main characteristics: the adopted network architecture, distance metric, and resulting peer selection algorithm. As result of this study, we propose a novel and generic taxonomy for locality algorithms in peer-to-peer networks, aiming to enable a better and more coherent evaluation of any individual locality algorithm.

Some heuristic algorithms for total tardiness minimization in a flowshop with blocking

The flowshop scheduling problem with blocking in-process is addressed in this paper. In this environment, there are no buffers between successive machines: therefore intermediate queues of jobs waiting in the system for their next operations are not allowed. Heuristic approaches are proposed to minimize the total tardiness criterion. A constructive heuristic that explores specific characteristics of the problem is presented. Moreover, a GRASP-based heuristic is proposed and Coupled with a path relinking strategy to search for better outcomes. Computational tests are presented and the comparisons made with an adaptation of the NEH algorithm and with a branch-and-bound algorithm indicate that the new approaches are promising. (c) 2007 Elsevier Ltd. All rights reserved.

A hybrid case adaptation approach for case-based reasoning

Case-Based Reasoning is a methodology for problem solving based on past experiences. This methodology tries to solve a new problem by retrieving and adapting previously known solutions of similar problems. However, retrieved solutions, in general, require adaptations in order to be applied to new contexts. One of the major challenges in Case-Based Reasoning is the development of an efficient methodology for case adaptation. The most widely used form of adaptation employs hand coded adaptation rules, which demands a significant knowledge acquisition and engineering effort. An alternative to overcome the difficulties associated with the acquisition of knowledge for case adaptation has been the use of hybrid approaches and automatic learning algorithms for the acquisition of the knowledge used for the adaptation. We investigate the use of hybrid approaches for case adaptation employing Machine Learning algorithms. The approaches investigated how to automatically learn adaptation knowledge from a case base and apply it to adapt retrieved solutions. In order to verify the potential of the proposed approaches, they are experimentally compared with individual Machine Learning techniques. The results obtained indicate the potential of these approaches as an efficient approach for acquiring case adaptation knowledge. They show that the combination of Instance-Based Learning and Inductive Learning paradigms and the use of a data set of adaptation patterns yield adaptations of the retrieved solutions with high predictive accuracy.