The term "soft computing" has recently come into vogue; it encompasses such computational techniques as neural nets, genetic algorithms, genetic programming, A-life, fuzzy systems, and probabilistic reasoning. The name "soft computing" came into use presumably because it has borrowed many of its computational metaphors from life sciences. Soft computing attempts to solve the class of computationally hard problems that do not seem to lend themselves well for classical algorithmic approaches, whereas humans are particularly adept at solving them. Processing of linguistic information such as summarization and disambiguation, processing of pictorial information such as recognizing faces in a crowd or tumors in a mammogram, filtering information from textual and pictirial databases, analogical reasoning, generalization from examples, theorem proving, are some disciplines where an investment in soft computing is expected to yield rich dividends.
As the underlying principles of soft computing are being understood, it is becoming clear that the ideas associated with this discipline are indeed powerful enough to solve computationally hard problems that are traditionally handled by conventional algorithmic (non-soft) techniques. NP-hard problems arising in combinatorial optimization, such as those arising in DNA modeling, protein folding and drug design studies; ill-posed problems (in the Hadamard sense) such as the inversion of remotely sensed data, and texture segmentation and labelling in image processing; and equalization and detection of signals in a noisy environment such as those encountered in wireless communications are few examples of hard problems. In computer science, soft computing methods have been used to optimize instruction and data pipelines in the central processing unit (CPU), cell placement and routing in VLSI design, and optimal placement of files in heterogeneous distributed processing environments. In the arena of public policy, they have been used for multi-objective optimization in environmental pollution abatement and remediation. Soft computing methods are particularly effective in search and optimization when the underlying search space is large, multimodal, and when the characteristics of the search space are not well understood. It is under these very conditions traditional optimization and search techniques such as steepest descent and dynamic programming become impractical.
Artificial neural networks (ANNs), which are essentially nonlinear mappers, use the brain metaphor. They require hundreds of processors with thousands of interconnections. Indeed the original design of the Connection Machine was influenced by the "topology and architecture" of brains. Genetic Algorithms (GAs) are stochastic search and optimization techniques. GAs and evolutionary computation, which use the twin metaphors of natural evolution and survival of the fittest, derive their strength by working on populations of solutions and are therefore best exploited in a parallel computing environment.
An off-shoot of GAs is genetic programming (GP). GAs (and GPs) function by iteratively refining a population of encoded representations of solutions (or programs). "Parents" from a population are "selected" for "crossover" and "mutation". The "offspring" form the new population. The "selection" process is controlled via a fitness measure that is closely related to the optimization objective. This generational cycle is repeated until a solution (or program) with the desirable quality is located.
The aim of genetic programming is to automatically generate correct computer programs from a population of randomly generated computer programs. In an era of escalating software development costs, it is reasonable to look for automatic methods of generating correct computer programs and GP's performance on an initial set of test problems is very encouraging.
For all their promising advantages, soft computing methods tend to be computationally intensive. The memory and computational time requirements for these techniques are higher than for traditional techniques. In ANNs, it is the processing associated with training. In GAs, a population of solutions needs to be maintained and fitness of the entire population evaluated for every generation. As the problem size increases, the network size increases in ANNs and the population size needs to be increased in GAs in order to retain the genetic variety of the population transitioning from one generation to another.
ANNs, GAs and GPs are intrinsically parallel. The parallelism of ANNs is evident at the outset. In GAs, there is an explicit parallelism as evidenced by the need to evaluate fitness of large groups of individuals in a population. The implicit parallelism becomes evident from the Schema Theorem, the fundamental theorem of GAs. This parallelism is best exploited on a parallel machine, be it a message passing, shared-memory or cellular machine. In spite of these observations, most of the current implementations are on workstations, simply because of the widespread availability of high-performance workstations. High-end processors like the CRAY, the Connection Machine (CM-5), and the Massively Parallel Processor (MPP) are not always available routinely to all investigators and institutions.
Parallel and distributed GAs have been proposed in the literature for solving large optimization problems on dedicated multiprocessor systems.These implementations consider "static" implementations with fixed-size populations and a fixed number of populations. For single-population GAs, there is evidence that variation of the population size dynamically leads to performance improvements in the search rate. Also, it is known that the population size is a critical control parameter of GA-dynamics. To the best of our knowledge, no dynamic strategies of re configuring distributed GAs have been proposed. It is certainly worth investigating dynamic population reconfiguration schemes for improving the performance of distributed GAs.