trans gene regulation in adaptive evolution: A genetic algorithm model

This is a continuation of earlier studies on the evolution of infinite populations of haploid genotypes within a genetic algorithm framework. We had previously explored the evolutionary consequences of the existence of indeterminate—“plastic”—loci, where a plastic locus had a finite probability in each generation of functioning (being switched “on”) or not functioning (being switched “off”). The relative probabilities of the two outcomes were assigned on a stochastic basis. The present paper examines what happens when the transition probabilities are biased by the presence of regulatory genes. We find that under certain conditions regulatory genes can improve the adaptation of the population and speed up the rate of evolution (on occasion at the cost of lowering the degree of adaptation). Also, the existence of regulatory loci potentiates selection in favour of plasticity. There is a synergistic effect of regulatory genes on plastic alleles: the frequency of such alleles increases when regulatory loci are present. Thus, phenotypic selection alone can be a potentiating factor in a favour of better adaptation.

Negotiation schemes for multi-agent cooperative search

Because of limited sensor and communication ranges, designing efficient mechanisms for cooperative tasks is difficult. In this article, several negotiation schemes for multiple agents performing a cooperative task are presented. The negotiation schemes provide suboptimal solutions, but have attractive features of fast decision-making, and scalability to large number of agents without increasing the complexity of the algorithm. A software agent architecture of the decision-making process is also presented. The effect of the magnitude of information flow during the negotiation process is studied by using different models of the negotiation scheme. The performance of the various negotiation schemes, using different information structures, is studied based on the uncertainty reduction achieved for a specified number of search steps. The negotiation schemes perform comparable to that of optimal strategy in terms of uncertainty reduction and also require very low computational time, similar to 7 per cent to that of optimal strategy. Finally, analysis on computational and communication requirement for the negotiation schemes is carried out.

The Consequences of Phenotypic Plasticity in Cyclically Varying Environments: A Genetic Algorithm Study

By “phenotypic plasticity” we refer to the capacity of a genotype to exhibit different phenotypes, whether in the same or in different environments. We have previously demonstrated that phenotypic plasticity can improve the degree of adaptation achieved via natural selection (Behera & Nanjundiah, 1995). That result was obtained from a genetic algorithm model of haploid genotypes (idealized as one-dimensional strings of genes) evolving in a fixed environment. Here, the dynamics of evolution is examined under conditions of a cyclically varying environment. We find that the rate of evolution, as well as the extent of adaptation (as measured by mean population fitness) is lowered because of environmental cycling. The decrease is adaptation caused by a varying environment can, however, be partly or wholly compensated by an increase in the degree of plasticity that a genotype is capable of. Also, the reduction of population fitness caused by a variable environment can be partially offset by decreasing the total number of genetic loci. We conjecture that an increase in genome size may have been among the factors responsible for the evolution of phenotypic plasticity.

A real-time algorithm for simulation of flexible objects and hyper-redundant manipulators

Flexible objects such as a rope or snake move in a way such that their axial length remains almost constant. To simulate the motion of such an object, one strategy is to discretize the object into large number of small rigid links connected by joints. However, the resulting discretised system is highly redundant and the joint rotations for a desired Cartesian motion of any point on the object cannot be solved uniquely. In this paper, we revisit an algorithm, based on the classical tractrix curve, to resolve the redundancy in such hyper-redundant systems. For a desired motion of the `head' of a link, the `tail' is moved along a tractrix, and recursively all links of the discretised objects are moved along different tractrix curves. The algorithm is illustrated by simulations of a moving snake, tying of knots with a rope and a solution of the inverse kinematics of a planar hyper-redundant manipulator. The simulations show that the tractrix based algorithm leads to a more `natural' motion since the motion is distributed uniformly along the entire object with the displacements diminishing from the `head' to the `tail'.

Two-level k-means clustering algorithm for k-tau relationship establishment and linear-time classification

Partitional clustering algorithms, which partition the dataset into a pre-defined number of clusters, can be broadly classified into two types: algorithms which explicitly take the number of clusters as input and algorithms that take the expected size of a cluster as input. In this paper, we propose a variant of the k-means algorithm and prove that it is more efficient than standard k-means algorithms. An important contribution of this paper is the establishment of a relation between the number of clusters and the size of the clusters in a dataset through the analysis of our algorithm. We also demonstrate that the integration of this algorithm as a pre-processing step in classification algorithms reduces their running-time complexity.

A Low-Complexity Near-ML Performance Achieving Algorithm for Large MIMO Detection

In this paper, we present a low-complexity, near maximum-likelihood (ML) performance achieving detector for large MIMO systems having tens of transmit and receive antennas. Such large MIMO systems are of interest because of the high spectral efficiencies possible in such systems. The proposed detection algorithm, termed as multistage likelihood-ascent search (M-LAS) algorithm, is rooted in Hopfield neural networks, and is shown to possess excellent performance as well as complexity attributes. In terms of performance, in a 64 x 64 V-BLAST system with 4-QAM, the proposed algorithm achieves an uncoded BER of 10(-3) at an SNR of just about 1 dB away from AWGN-only SISO performance given by Q(root SNR). In terms of coded BER, with a rate-3/4 turbo code at a spectral efficiency of 96 bps/Hz the algorithm performs close to within about 4.5 dB from theoretical capacity, which is remarkable in terms of both high spectral efficiency as well as nearness to theoretical capacity. Our simulation results show that the above performance is achieved with a complexity of just O(NtNt) per symbol, where N-t and N-tau denote the number of transmit and receive antennas.

A self-adaptive migration model genetic algorithm for data mining applications

Data mining involves nontrivial process of extracting knowledge or patterns from large databases. Genetic Algorithms are efficient and robust searching and optimization methods that are used in data mining. In this paper we propose a Self-Adaptive Migration Model GA (SAMGA), where parameters of population size, the number of points of crossover and mutation rate for each population are adaptively fixed. 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 and a set of actual classification datamining problems. Michigan style of classifier was used to build the classifier and the system was tested with machine learning databases of Pima Indian Diabetes database, Wisconsin Breast Cancer database and few others. The performance of our algorithm is better than others.

Profiling k-Iteration Paths : A Generalization of the Ball-Larus Profiling Algorithm

The Ball-Larus path-profiling algorithm is an efficient technique to collect acyclic path frequencies of a program. However, longer paths -those extending across loop iterations - describe the runtime behaviour of programs better. We generalize the Ball-Larus profiling algorithm for profiling k-iteration paths - paths that can span up to to k iterations of a loop. We show that it is possible to number suchk-iteration paths perfectly, thus allowing for an efficient profiling algorithm for such longer paths. We also describe a scheme for mixed-mode profiling: profiling different parts of a procedure with different path lengths. Experimental results show that k-iteration profiling is realistic.

A genetic algorithm with characteristic amplification through multiple geographically isolated populations and varied fitness landscapes

This paper proposes a new approach, wherein multiple populations are evolved on different landscapes. The problem statement is broken down, to describe discrete characteristics. Each landscape, described by its fitness landscape is used to optimize or amplify a certain characteristic or set of characteristics. Individuals from each of these populations are kept geographically isolated from each other Each population is evolved individually. After a predetermined number of evolutions, the system of populations is analysed against a normalized fitness function. Depending on this score and a predefined merging scheme, the populations are merged, one at a time, while continuing evolution. Merging continues until only one final population remains. This population is then evolved, following which the resulting population will contain the optimal solution. The final resulting population will contain individuals which have been optimized against all characteristics as desired by the problem statement. Each individual population is optimized for a local maxima. Thus when populations are merged, the effect is to produce a new population which is closer to the global maxima.

A genetic algorithm with characteristic amplification through multiple geographically isolated populations and varied fitness landscapes

This paper proposes a new approach, wherein multiple populations are evolved on different landscapes. The problem statement is broken down, to describe discrete characteristics. Each landscape, described by its fitness landscape is used to optimize or amplify a certain characteristic or set of characteristics. Individuals from each of these populations are kept geographically isolated from each other Each population is evolved individually. After a predetermined number of evolutions, the system of populations is analysed against a normalized fitness function. Depending on this score and a predefined merging scheme, the populations are merged, one at a time, while continuing evolution. Merging continues until only one final population remains. This population is then evolved, following which the resulting population will contain the optimal solution. The final resulting population will contain individuals which have been optimized against all characteristics as desired by the problem statement. Each individual population is optimized for a local maxima. Thus when populations are merged, the effect is to produce a new population which is closer to the global maxima.

RACK: RApid Clustering using K-means algorithm

The k-means algorithm is an extremely popular technique for clustering data. One of the major limitations of the k-means is that the time to cluster a given dataset D is linear in the number of clusters, k. In this paper, we employ height balanced trees to address this issue. Specifically, we make two major contributions, (a) we propose an algorithm, RACK (acronym for RApid Clustering using k-means), which takes time favorably comparable with the fastest known existing techniques, and (b) we prove an expected bound on the quality of clustering achieved using RACK. Our experimental results on large datasets strongly suggest that RACK is competitive with the k-means algorithm in terms of quality of clustering, while taking significantly less time.

Intent Based Clustering of Search Engine Query Log

The keyword based search technique suffers from the problem of synonymic and polysemic queries. Current approaches address only theproblem of synonymic queries in which different queries might have the same information requirement. But the problem of polysemic queries,i.e., same query having different intentions, still remains unaddressed. In this paper, we propose the notion of intent clusters, the members of which will have the same intention. We develop a clustering algorithm that uses the user session information in query logs in addition to query URL entries to identify cluster of queries having the same intention. The proposed approach has been studied through case examples from the actual log data from AOL, and the clustering algorithm is shown to be successful in discerning the user intentions.

Two-agent cooperative search using game models with endurance-time constraints

In this article, the problem of two Unmanned Aerial Vehicles (UAVs) cooperatively searching an unknown region is addressed. The search region is discretized into hexagonal cells and each cell is assumed to possess an uncertainty value. The UAVs have to cooperatively search these cells taking limited endurance, sensor and communication range constraints into account. Due to limited endurance, the UAVs need to return to the base station for refuelling and also need to select a base station when multiple base stations are present. This article proposes a route planning algorithm that takes endurance time constraints into account and uses game theoretical strategies to reduce the uncertainty. The route planning algorithm selects only those cells that ensure the agent will return to any one of the available bases. A set of paths are formed using these cells which the game theoretical strategies use to select a path that yields maximum uncertainty reduction. We explore non-cooperative Nash, cooperative and security strategies from game theory to enhance the search effectiveness. Monte-Carlo simulations are carried out which show the superiority of the game theoretical strategies over greedy strategy for different look ahead step length paths. Within the game theoretical strategies, non-cooperative Nash and cooperative strategy perform similarly in an ideal case, but Nash strategy performs better than the cooperative strategy when the perceived information is different. We also propose a heuristic based on partitioning of the search space into sectors to reduce computational overhead without performance degradation.

A fast algorithm for macromolecular packing calculation

An algorithm to improve the computation time of packing calculations for macromolecules is presented. This is achieved by reducing the three-dimensional search to a small set of two-dimensional searches.

Genetic algorithm for satellite customer assignment

The problem of assigning customers to satellite channels is considered. Finding an optimal allocation of customers to satellite channels is a difficult combinatorial optimization problem and is shown to be NP-complete in an earlier study. We propose a genetic algorithm (GA) approach to search for the best/optimal assignment of customers to satellite channels. Various issues related to genetic algorithms such as solution representation, selection methods, genetic operators and repair of invalid solutions are presented. A comparison of this approach with the standard optimization method is presented to show the advantages of this approach in terms of computation time