Genetic algorithms: a survey

Genetic algorithms provide an alternative to traditional optimization techniques by using directed random searches to locate optimal solutions in complex landscapes. We introduce the art and science of genetic algorithms and survey current issues in GA theory and practice. We do not present a detailed study, instead, we offer a quick guide into the labyrinth of GA research. First, we draw the analogy between genetic algorithms and the search processes in nature. Then we describe the genetic algorithm that Holland introduced in 1975 and the workings of GAs. After a survey of techniques proposed as improvements to Holland's GA and of some radically different approaches, we survey the advances in GA theory related to modeling, dynamics, and deception

Managing interprocessor delays in distributed recursive algorithms

For a class of distributed recursive algorithms, it is shown that a stochastic approximation-like tapering stepsize routine suppresses the effects of interprocessor delays.

Performance of a pipelined ring algorithm for Fast Fourier Transform on transputer arrays

In this paper a pipelined ring algorithm is presented for efficient computation of one and two dimensional Fast Fourier Transform (FFT) on a message passing multiprocessor. The algorithm has been implemented on a transputer based system and experiments reveal that the algorithm is very efficient. A model for analysing the performance of the algorithm is developed from its computation-communication characteristics. Expressions for execution time, speedup and efficiency are obtained and these expressions are validated with experimental results obtained on a four transputer system. The analytical model is then used to estimate the performance of the algorithm for different number of processors, and for different sizes of the input data.

Fast algorithm for data exchange in reconfigurable tree structures

This paper presents a fast algorithm for data exchange in a network of processors organized as a reconfigurable tree structure. For a given data exchange table, the algorithm generates a sequence of tree configurations in which the data exchanges are to be executed. A significant feature of the algorithm is that each exchange is executed in a tree configuration in which the source and destination nodes are adjacent to each other. It has been proved in a theorem that for every pair of nodes in the reconfigurable tree structure, there always exists two and only two configurations in which these two nodes are adjacent to each other. The algorithm utilizes this fact and determines the solution so as to optimize both the number of configurations required and the time to perform the data exchanges. Analysis of the algorithm shows that it has linear time complexity, and provides a large reduction in run-time as compared to a previously proposed algorithm. This is well-confirmed from the experimental results obtained by executing a large number of randomly-generated data exchange tables. Another significant feature of the algorithm is that the bit-size of the routing information code is always two bits, irrespective of the number of nodes in the tree. This not only increases the speed of the algorithm but also results in simpler hardware inside each node.

Line clipping revisited: Two efficient algorithms based on simple geometric observations

Two new line clipping algorithms, the opposite-corner algorithm and the perpendicular-distance algorithm, that are based on simple geometric observations are presented. These algorithms do not require computation of outcodes nor do they depend on the parametric representations of the lines. It is shown that the opposite-corner algorithm perform consistently better than an algorithm due to Nicholl, Lee, and Nicholl which is claimed to be better than the classic algorithm due to Cohen-Sutherland and the more recent Liang-Barsky algorithm. The pseudo-code of the opposite-corner algorithm is provided in the Appendix.

Solvation dynamics in slow, viscous liquids: Application to amides

As the viscosity of a liquid increases rapidly in the supercooled regime, the nature of molecular relaxation can exhibit dynamics rather different from the fast dynamics observed in the normal regime. In this article, we present theoretical studies of solvation dynamics and orientational relaxation in slow liquids. As the local short-range correlations are important in the slow liquids, we have extended our previous theory to take into account the shea-range pair correlations between the polar solute and the dipolar solvent molecules. Application of the generalized theory To the study of solvation dynamics of amide systems gives nice agreement with the experimental results of Maroncelli and co-workers (J. Phys. Chem. 1990, 94, 4929). The theory also provides valuable insight into the orientational relaxation precesses in the viscous liquids.

S-nets: A Petri net based model for performance evaluation of real-time scheduling algorithms

A new class of nets, called S-nets, is introduced for the performance analysis of scheduling algorithms used in real-time systems Deterministic timed Petri nets do not adequately model the scheduling of resources encountered in real-time systems, and need to be augmented with resource places and signal places, and a scheduler block, to facilitate the modeling of scheduling algorithms. The tokens are colored, and the transition firing rules are suitably modified. Further, the concept of transition folding is used, to get intuitively simple models of multiframe real-time systems. Two generic performance measures, called �load index� and �balance index,� which characterize the resource utilization and the uniformity of workload distribution, respectively, are defined. The utility of S-nets for evaluating heuristic-based scheduling schemes is illustrated by considering three heuristics for real-time scheduling. S-nets are useful in tuning the hardware configuration and the underlying scheduling policy, so that the system utilization is maximized, and the workload distribution among the computing resources is balanced.

Effect of Short Duration of Load increment on the Compressibility of Soils

This study concerns the effect of duration of load increment (up to 24 h) on the consolidation properties of expansive black cotton soil (liquid limit = 81%) and nonexpansive kaolinite (liquid limit = 49%). It indicates that the amount and rate of compression are not noticeably affected by the duration of loading for a standard sample of 25 mm in height and 76.2 mm in diameter with double drainage. Hence, the compression index and coefficient of consolidation can be obtained with reasonable accuracy even if the duration of each load increment is as short as 4 h. The secondary compression coefficient (C-alpha epsilon) for kaolinite can be obtained for any pressure range with 1/2 h of loading, which, however, requires 4 h for black cotton soil. This is because primary consolidation is completed early in the case of kaolinite. The paper proves that the conventional consolidation test can be carried out with much shorter duration of loading (less than 4 h) than the standard specification of 24 h or more even for remolded fine-grained soils.

(PEG)(x)NH4ClO4: A new polymeric fast proton conductor

A new polymer electrolyte (PEG)(x) NH4ClO4(x = 5, 10, 15, 20) has been prepared that shows protonic conduction. The room temperature conductivities are of the order of 10(-7) S/cm, and increase with decrease in salt concentration. NMR line width studies indicate fairly low glass transition temperatures of the polymer salt complexes.

Short-bite chiral diphosphazanes derived from (S)-?-methyl benzyl amine and their Pd, Pt and Rh metal complexes

New chiral diphosphazane ligands of the type Ph(2)PN(S-*CHMePh)PYY' {YY'= Ph(2) (2), O2C6H4 (3); Y= Ph, Y'= Cl {4a (SS), 4b (SR)}, N(2)C(3)HMe(2)-3,5 {5a (SR), 5b (SS)} are synthesised starting from a chiral aminophosphine, Ph(2)PNH(S-*CHMePh) (1). The structure of one of the diastereomer 5a has been confirmed by single crystal X-ray diffraction {Orthorhombic system, P2(1)2(1)2(1); a=10.456 (4), b=15.362 (7), c=17.379 (6) Angstrom, Z=4}. Transition metal mononuclear complexes [Rh{eta(2)-(Ph(2)P)(2)N- (S-*CHMePh)}(2)](+)(BF4)(-) (6), [PdCl2{eta(2)-(Ph(2)P)(2)N(S-*CHMePh)}] (7) and [PtCl2{eta(2)-(Ph(2)P)(2)N- (S-*CHMePh)}] (8) have also been synthesised. The structure of the palladium complex 7 is solved by X-ray crystallography {Orthorhombic system, P2(1)2(1)2(1); a=8.746 (2), b=18.086 (2), c=20.811 (3) Angstrom, Z=4}. All these compounds are characterised by micro analyses, IR and NMR spectroscopic data.

Some Algorithms for Eigensubspace Estimation

An important tool in signal processing is the use of eigenvalue and singular value decompositions for extracting information from time-series/sensor array data. These tools are used in the so-called subspace methods that underlie solutions to the harmonic retrieval problem in time series and the directions-of-arrival (DOA) estimation problem in array processing. The subspace methods require the knowledge of eigenvectors of the underlying covariance matrix to estimate the parameters of interest. Eigenstructure estimation in signal processing has two important classes: (i) estimating the eigenstructure of the given covariance matrix and (ii) updating the eigenstructure estimates given the current estimate and new data. In this paper, we survey some algorithms for both these classes useful for harmonic retrieval and DOA estimation problems. We begin by surveying key results in the literature and then describe, in some detail, energy function minimization approaches that underlie a class of feedback neural networks. Our approaches estimate some or all of the eigenvectors corresponding to the repeated minimum eigenvalue and also multiple orthogonal eigenvectors corresponding to the ordered eigenvalues of the covariance matrix. Our presentation includes some supporting analysis and simulation results. We may point out here that eigensubspace estimation is a vast area and all aspects of this cannot be fully covered in a single paper. (C) 1995 Academic Press, Inc.

Highly Efficient and Thermally Stable Second-Order Nonlinear Optical Chromophores and Electrooptic Polymers

Organic polymeric electro-optic (E-O) materials have attracted significant attention because of their potential use as fast and efficient components of integrated photonic devices (1,2). However, the practical application of these materials in optical devices is somewhat limited by the stringent material requirements imposed by the device design, fabrication processes and operating environments. Among the various material requirements, the most notable ones are large electro-optic coefficients (r(33)) and high thermal stability (3). The design of poled polymeric materials with high electro-optic activity (r(33)) involves the optimization of the percent incorporation of efficient (large beta mu) second order nonlinear optical (NLO) chromophores into the polymer matrices and the effective creation of poling-induced non-centrosymmetric structures. The factors that affect the material stability are a) the inherent thermal stability of the NLO chromophores, b) the chemical stability of the NLO chromophores during the polymer processing conditions, and c) the long-term dipolar alignment stability at high temperatures. Although considerable progress has been made in achieving these properties (4), organic polymeric materials suitable for practical E-O device applications are yet to be developed. This chapter highlights some of our approaches in the optimization of molecular and material nonlinear optical and thermal properties.

How fast is ultrafast chemistry

The field of ultrafast chemistry has seen a string of remarkable discoveries in the recent years. In this article we briefly discuss some of the problems solved recently. The understanding that has emerged from these studies has important consequences non only in chemistry but also in diverse biological processes.

Uracil excision repair in Mycobacterium tuberculosis cell-free extracts

Uracil excision repair is ubiquitous in all domains of life and initiated by uracil DNA glycosylases (UDGs) which excise the promutagenic base, uracil, from DNA to leave behind an abasic site (AP-site). Repair of the resulting AP-sites requires an AP-endonuclease, a DNA polymerase, and a DNA ligase whose combined activities result in either short-patch or long-patch repair. Mycobacterium tuberculosis, the causative agent of tuberculosis, has an increased risk of accumulating uracils because of its G + C-rich genome, and its niche inside host macrophages where it is exposed to reactive nitrogen and oxygen species, two major causes of cytosine deamination (to uracil) in DNA. In vitro assays to study DNA repair in this important human pathogen are limited. To study uracil excision repair in mycobacteria, we have established assay conditions using cell-free extracts of M. tuberculosis and M. smegmatis (a fast-growing mycobacterium) and oligomer or plasmid DNA substrates. We show that in mycobacteria, uracil excision repair is completed primarily via long-patch repair. In addition, we show that M. tuberculosis UdgB, a newly characterized family 5 UDG, substitutes for the highly conserved family 1 UDG, Ung, thereby suggesting that UdgB might function as backup enzyme for uracil excision repair in mycobacteria. (C) 2011 Elsevier Ltd. All rights reserved.

Lattice model for rapidly folding protein-like heteropolymers

Protein folding is a relatively fast process considering the astronomical number of conformations in which a protein could find itself. Within the framework of a lattice model, we show that one can design rapidly folding sequences by assigning the strongest attractive couplings to the contacts present in a target native state, Our protein design can be extended to situations with both attractive and repulsive contacts. Frustration is minimized by ensuring that all the native contacts are again strongly attractive. Strikingly, this ensures the inevitability of folding and accelerates the folding process by an order of magnitude, The evolutionary implications of our findings are discussed.