A Dynamic Migration Model for Self-adaptive Genetic Algorithms

In this paper, we propose a self Adaptive Migration Model for Genetic Algorithms, where parameters of population size, the number of points of crossover and mutation rate for each population are fixed adaptively. Further, the migration of individuals between populations is decided dynamically. This paper gives a mathematical schema analysis of the method stating and showing that the algorithm exploits previously discovered knowledge for a more focused and concentrated search of heuristically high yielding regions while simultaneously performing a highly explorative search on the other regions of the search space. The effective performance of the algorithm is then shown using standard testbed functions, when compared with Island model GA(IGA) and Simple GA(SGA).

Sequence design for symbol-asynchronous CDMA with power or rate constraints

Sequence design and resource allocation for a symbol-asynchronous chip-synchronous code division multiple access (CDMA) system is considered in this paper. A simple lower bound on the minimum sum-power required for a non-oversized system, based on the best achievable for a non-spread system, and an analogous upper bound on the sum rate are first summarised. Subsequently, an algorithm of Sundaresan and Padakandla is shown to achieve the lower bound on minimum sum power (upper bound on sum rate, respectively). Analogous to the synchronous case, by splitting oversized users in a system with processing gain N, a system with no oversized users is easily obtained, and the lower bound on sum power (upper bound on sum rate, respectively) is shown to be achieved by using N orthogonal sequences. The total number of splits is at most N - 1.

A real coded genetic algorithm for data partitioning and scheduling in networks with arbitrary processor release time

The problem of scheduling divisible loads in distributed computing systems, in presence of processor release time is considered. The objective is to find the optimal sequence of load distribution and the optimal load fractions assigned to each processor in the system such that the processing time of the entire processing load is a minimum. This is a difficult combinatorial optimization problem and hence genetic algorithms approach is presented for its solution.

Quality of support for multicasting over mobile ad-hoc networks

An ad hoc network is composed of mobile nodes without any infrastructure. Recent trends in applications of mobile ad hoc networks rely on increased group oriented services. Hence multicast support is critical for ad hoc networks. We also need to provide service differentiation schemes for different group of users. An efficient application layer multicast (APPMULTICAST) solution suitable for low mobility applications in MANET environment has been proposed in [10]. In this paper, we present an improved application layer multicast solution suitable for medium mobility applications in MANET environment. We define multicast groups with low priority and high priority and incorporate a two level service differentiation scheme. We use network layer support to build the overlay topology closer to the actual network topology. We try to maximize Packet Delivery Ratio. Through simulations we show that the control overhead for our algorithm is within acceptable limit and it achieves acceptable Packet Delivery Ratio for medium mobility applications.

Solving MDPs using two-timescale simulated annealing with multiplicative weights

We develop extensions of the Simulated Annealing with Multiplicative Weights (SAMW) algorithm that proposed a method of solution of Finite-Horizon Markov Decision Processes (FH-MDPs). The extensions developed are in three directions: a) Use of the dynamic programming principle in the policy update step of SAMW b) A two-timescale actor-critic algorithm that uses simulated transitions alone, and c) Extending the algorithm to the infinite-horizon discounted-reward scenario. In particular, a) reduces the storage required from exponential to linear in the number of actions per stage-state pair. On the faster timescale, a 'critic' recursion performs policy evaluation while on the slower timescale an 'actor' recursion performs policy improvement using SAMW. We give a proof outlining convergence w.p. 1 and show experimental results on two settings: semiconductor fabrication and flow control in communication networks.

Delay optimal control algorithm for a multiaccess fading channel with peak power constraint

We consider an optimal power and rate scheduling problem for a multiaccess fading wireless channel with the objective of minimising a weighted sum of mean packet transmission delay subject to a peak power constraint. The base station acts as a controller which, depending upon the buffer lengths and the channel state of each user, allocates transmission rate and power to individual users. We assume perfect channel state information at the transmitter and the receiver. We also assume a Markov model for the fading and packet arrival processes. The policy obtained represents a form of Indexability.

Fast in-memory XPath search using compressed indexes

A large fraction of an XML document typically consists of text data. The XPath query language allows text search via the equal, contains, and starts-with predicates. Such predicates can be efficiently implemented using a compressed self-index of the document's text nodes. Most queries, however, contain some parts querying the text of the document, plus some parts querying the tree structure. It is therefore a challenge to choose an appropriate evaluation order for a given query, which optimally leverages the execution speeds of the text and tree indexes. Here the SXSI system is introduced. It stores the tree structure of an XML document using a bit array of opening and closing brackets plus a sequence of labels, and stores the text nodes of the document using a global compressed self-index. On top of these indexes sits an XPath query engine that is based on tree automata. The engine uses fast counting queries of the text index in order to dynamically determine whether to evaluate top-down or bottom-up with respect to the tree structure. The resulting system has several advantages over existing systems: (1) on pure tree queries (without text search) such as the XPathMark queries, the SXSI system performs on par or better than the fastest known systems MonetDB and Qizx, (2) on queries that use text search, SXSI outperforms the existing systems by 1-3 orders of magnitude (depending on the size of the result set), and (3) with respect to memory consumption, SXSI outperforms all other systems for counting-only queries.

Solution of MDPS using simulation-based value iteration

This article proposes a three-timescale simulation based algorithm for solution of infinite horizon Markov Decision Processes (MDPs). We assume a finite state space and discounted cost criterion and adopt the value iteration approach. An approximation of the Dynamic Programming operator T is applied to the value function iterates. This 'approximate' operator is implemented using three timescales, the slowest of which updates the value function iterates. On the middle timescale we perform a gradient search over the feasible action set of each state using Simultaneous Perturbation Stochastic Approximation (SPSA) gradient estimates, thus finding the minimizing action in T. On the fastest timescale, the 'critic' estimates, over which the gradient search is performed, are obtained. A sketch of convergence explaining the dynamics of the algorithm using associated ODEs is also presented. Numerical experiments on rate based flow control on a bottleneck node using a continuous-time queueing model are performed using the proposed algorithm. The results obtained are verified against classical value iteration where the feasible set is suitably discretized. Over such a discretized setting, a variant of the algorithm of [12] is compared and the proposed algorithm is found to converge faster.

Search for Higgs bosons predicted in two-Higgs-doublet models via decays to tau lepton pairs in 1.96 TeV proton-antiproton collisions

We present the results of a search for Higgs bosons predicted in two-Higgs-doublet models, in the case where the Higgs bosons decay to tau lepton pairs, using 1.8 inverse fb of integrated luminosity of proton-antiproton collisions recorded by the CDF II experiment at the Fermilab Tevatron. Studying the observed mass distribution in events where one or both tau leptons decay leptonically, no evidence for a Higgs boson signal is observed. The result is used to infer exclusion limits in the two-dimensional parameter space of tan beta versus m(A).

Search for Higgs bosons predicted in two-Higgs-doublet models via decays to tau lepton pairs in 1.96 TeV proton-antiproton collisions

We present the results of a search for Higgs bosons predicted in two-Higgs-doublet models, in the case where the Higgs bosons decay to tau lepton pairs, using 1.8 inverse fb of integrated luminosity of proton-antiproton collisions recorded by the CDF II experiment at the Fermilab Tevatron. Studying the observed mass distribution in events where one or both tau leptons decay leptonically, no evidence for a Higgs boson signal is observed. The result is used to infer exclusion limits in the two-dimensional parameter space of tan beta versus m(A).

Search for a Fermiophobic Higgs Boson Decaying into Diphotons in p p-bar Collisions at sqrt{s} = 1.96 TeV

A search for a narrow diphoton mass resonance is presented based on data from 3.0 fb^{-1} of integrated luminosity from p-bar p collisions at sqrt{s} = 1.96 TeV collected by the CDF experiment. No evidence of a resonance in the diphoton mass spectrum is observed, and upper limits are set on the cross section times branching fraction of the resonant state as a function of Higgs boson mass. The resulting limits exclude Higgs bosons with masses below 106 GeV at a 95% Bayesian credibility level (C.L.) for one fermiophobic benchmark model.

Pareto-optimal solutions for multi-objective optimization of fed-batch bioreactors using nondominated sorting genetic algorithm

Many optimal control problems are characterized by their multiple performance measures that are often noncommensurable and competing with each other. The presence of multiple objectives in a problem usually give rise to a set of optimal solutions, largely known as Pareto-optimal solutions. Evolutionary algorithms have been recognized to be well suited for multi-objective optimization because of their capability to evolve a set of nondominated solutions distributed along the Pareto front. This has led to the development of many evolutionary multi-objective optimization algorithms among which Nondominated Sorting Genetic Algorithm (NSGA and its enhanced version NSGA-II) has been found effective in solving a wide variety of problems. Recently, we reported a genetic algorithm based technique for solving dynamic single-objective optimization problems, with single as well as multiple control variables, that appear in fed-batch bioreactor applications. The purpose of this study is to extend this methodology for solution of multi-objective optimal control problems under the framework of NSGA-II. The applicability of the technique is illustrated by solving two optimal control problems, taken from literature, which have usually been solved by several methods as single-objective dynamic optimization problems. (C) 2004 Elsevier Ltd. All rights reserved.

Search for exclusive Z boson production and observation of high mass ppbar->gammagamma->p+ll+pbar events in ppbar collisions at sqrt(s) = 1.96 TeV

We present a search for exclusive Z boson production in proton-antiproton collisions at sqrt(s) = 1.96 TeV, using the CDF II detector at Fermilab. We observe no exclusive Z->ll candidates and place the first upper limit on the exclusive Z cross section in hadron collisions, sigma(exclu) gammagamma->p+ll+pbar, and measure the cross section for M(ll) > 40 GeV/c2 and |eta(l)|

Search for the Higgs boson produced in association with Z→ℓ+ℓ- using the matrix element method at CDF II

We present a search for associated production of the standard model (SM) Higgs boson and a $Z$ boson where the $Z$ boson decays to two leptons and the Higgs decays to a pair of $b$ quarks in $p\bar{p}$ collisions at the Fermilab Tevatron. We use event probabilities based on SM matrix elements to construct a likelihood function of the Higgs content of the data sample. In a CDF data sample corresponding to an integrated luminosity of 2.7 fb$^{-1}$ we see no evidence of a Higgs boson with a mass between 100 GeV$/c^2$ and 150 GeV$/c^2$. We set 95% confidence level (C.L.) upper limits on the cross-section for $ZH$ production as a function of the Higgs boson mass $m_H$; the limit is 8.2 times the SM prediction at $m_H = 115$ GeV$/c^2$.

Detection of multiple source locations using a glowworm metaphor with applications to collective robotics

This paper presents a glowworm swarm based algorithm that finds solutions to optimization of multiple optima continuous functions. The algorithm is a variant of a well known ant-colony optimization (ACO) technique, but with several significant modifications. Similar to how each moving region in the ACO technique is associated with a pheromone value, the agents in our algorithm carry a luminescence quantity along with them. Agents are thought of as glowworms that emit a light whose intensity is proportional to the associated luminescence and have a circular sensor range. The glowworms depend on a local-decision domain to compute their movements. Simulations demonstrate the efficacy of the proposed glowworm based algorithm in capturing multiple optima of a multimodal function. The above optimization scenario solves problems where a collection of autonomous robots is used to form a mobile sensor network. In particular, we address the problem of detecting multiple sources of a general nutrient profile that is distributed spatially on a two dimensional workspace using multiple robots.