Evolutionary computing (EC) is an area of computer sciences and applied mathematics covering heuristic optimization algorithms inspired by evolution in Nature. EC extensively study all the variety of ...methods which were originally based on the principles of selectionism. As a result, many new algorithms and approaches, significantly more efficient than classical selectionist schemes, were found. This is especially true for some families of special problems. There are strong arguments to believe that EC approaches are quite suitable for modeling and numerical analysis of those methods of synthetic biology and biotechnology that are known as in vitro evolution. Therefore, it is natural to expect that the new algorithms and approaches developed in EC can be effectively applied in experiments on the directed evolution of biological macromolecules. According to the John Holland's Schema theorem, the effective evolutionary search in genetic algorithms (GA) is provided by identifying short schemata of high fitness which in the further search recombine into the larger building blocks (BBs) with higher and higher fitness. The multimodularity of functional biological macromolecules and the preservation of already found modules in the evolutionary search have a clear analogy with the BBs in EC. It seems reasonable to try to transfer and introduce the methods of EC, preserving BBs and essentially accelerating the search, into experiments on in vitro evolution. We extend the key instrument of the Holland's theory, the Royal Roads fitness function, to problems of the in vitro evolution (Biological Royal Staircase, BioRS, functions). The specific version of BioRS developed in this publication arises from the realities of experimental evolutionary search for (DNA-) RNA-devices (aptazymes). Our numerical tests showed that for problems with the BioRS functions, simple heuristic algorithms, which turned out to be very effective for preserving BBs in GA, can be very effective in in vitro evolution approaches. We are convinced that such algorithms can be implemented in modern methods of in vitro evolution to achieve significant savings in time and resources and a significant increase in the efficiency of evolutionary search.
The theory and practice of genetic algorithms is largely based on the Schema Theorem. It was formulated for a canonical genetic algorithm and proves its ability to generate a sufficient number of ...effective schemata of individuals. Genetic algorithms to solve specific problems and to be different from canonical ones have to be checked to find out whether the Schema Theorem evaluates the algorithm fitness. The article validates the way of testing the algorithm developed as a technique of an area search. The methodology and research results are stated consistently. Coding specifics of the search queries are noted, a criterion of the coding method applicability is substantiated. A variant of the genotype geometric coding is proposed. In comparison with other methods of binary search coding, it provides a short code length and uniqueness as well as conforms the formulated criterion of applicability. Supporting experimental results are given. The Schema Theorem is shown to hold with the iterative execution of the genetic algorithm being tested.
Over the years, evolutionary computation has come to be recognized as one of the leading algorithmic paradigms in the arena of global black box optimization. The distinguishing facets of evolutionary ...methods, inspired by Darwin’s foundational principles of natural selection, stem mainly from their population-based search strategy—which gives rise to the phenomenon of
implicit parallelism
. Precisely, even as an evolutionary algorithm manipulates a population of a few candidate solutions (or: individuals),
it is able to simultaneously sample
,
evaluate
,
and process a vast number of regions of the search space
. This behavior is in effect analogous to our inherent cognitive ability of processing diverse information streams (such as sight and sound) with apparent simultaneity in different regions of our brain. For this reason, evolutionary algorithms have emerged as the method of choice for those search and optimization problems where a collection of multiple target solutions (that may be scattered throughout the search space) are to be found in a single run. With the above in mind, in this paper we return to the roots of evolutionary computation, with the aim of shedding light on a variety of problem settings that are uniquely suited for exploiting the implicit parallelism of evolutionary algorithms. Our discussions cover established concepts of multi-objective and multi-modal optimization, as well as new (schema) theories pertaining to emerging problem formulations that entail multiple searches to be carried out at once. We capture associated research activities under the umbrella term of
multi-X evolutionary computation
, where
X
, as of now, represents the following list: {“objective,” “modal,” “task,” “level,” “hard,” “disciplinary,” “form”}. With this, we hope that the present position paper will serve as a catalyst for effecting further research efforts into such areas of optimization problem-solving that are well-aligned with the fundamentals of evolutionary computation; in turn prompting the steady update of the list
X
with new applications in the future.
Schema theory is the most well-known model of evolutionary algorithms. Imitating from genetic algorithms (GA), nearly all schemata defined for genetic programming (GP) refer to a set of points in the ...search space that share some
syntactic
characteristics. In GP, syntactically similar individuals do not necessarily have similar semantics. The instances of a syntactic schema do not behave similarly, hence the corresponding schema theory becomes unreliable. Therefore, these theories have been rarely used to improve the performance of GP. The main objective of this study is to propose a schema theory which could be a more realistic model for GP and could be potentially employed for improving GP in practice. To achieve this aim, the concept of
semantic
schema is introduced. This schema partitions the search space according to semantics of trees, regardless of their syntactic variety. We interpret the semantics of a tree in terms of the mutual information between its output and the target. The semantic schema is characterized by a set of semantic building blocks and their joint probability distribution. After introducing the semantic building blocks, an algorithm for finding them in a given population is presented. An extraction method that looks for the most significant schema of the population is provided. Moreover, an exact microscopic schema theorem is suggested that predicts the expected number of schema samples in the next generation. Experimental results demonstrate the capability of the proposed schema definition in representing the semantics of the schema instances. It is also revealed that the semantic schema theorem estimation is more realistic than previously defined schemata.
In this paper, fractal image compression using schema genetic algorithm (SGA) is proposed. Utilizing the self-similarity property of a natural image, the partitioned iterated function system (PIFS) ...will be found to encode an image through genetic algorithm (GA) method. In SGA, the genetic operators are adapted according to the schema theorem in the evolutionary process performed on the range blocks. Such a method can speed up the encoder and also preserve the image quality. Simulations show that the encoding time of our method is over 100 times faster than that of the full search method, while the retrieved image quality is still acceptable. The proposed method is also compared to another GA method proposed by Vences and Rudomin. Simulations also show that our method is superior to their method in both the speedup ratio and retrieved quality. Finally, a comparison of the proposed SGA to the traditional GA is presented to demonstrate that when the schema theorem is embedded, the performance of GA has significant improvement.
The adoption of probabilistic models for selected individuals is a powerful approach for evolutionary computation. Probabilistic models based on high-order statistics have been used by estimation of ...distribution algorithms (EDAs), resulting better effectiveness when searching for global optima for hard optimization problems. This paper proposes a new framework for evolutionary algorithms, which combines a simple EDA based on order 1 statistics and a clustering technique in order to avoid the high computational cost required by higher order EDAs. The algorithm uses clustering to group genotypically similar solutions, relying that different clusters focus on different substructures and the combination of information from different clusters effectively combines substructures. The combination mechanism uses an information gain measure when deciding which cluster is more informative for any given gene position, during a pairwise cluster combination. Empirical evaluations effectively cover a comprehensive range of benchmark optimization problems.
► Exact schema theorem to predict exact number of copies of schemas. ► Analysis of crossover and mutation probabilities using the proposed exact schema theorem. ► GA and tabu search for fuzzy ...c-means.
This paper proposes an exact schema theorem that is able to predict the expected number of copies of schemas in the next GA generation. It focuses on two-point crossover, which is widely used in many GA applications. As two important GA control parameters, crossover probability (
p
c
) and mutation probability (
p
m
) affect the performance of GAs drastically. A set of good GA parameters help in improving the ability of a GA to search for near global optimal solutions. This work shows that optimal
p
c
and
p
m
do not exist in most cases. As a result, a compromised pair of
p
c
and
p
m
may help improve the performance of GA. A multiple population search strategy enabled fuzzy
c-means based evolutionary approach, which embeds the proposed exact schema theorem, to machine cell formation is then proposed. The approach enables the crossover and mutation probabilities of GAs to be made adaptive to suit different stages of the search for near optimal solutions. Three case studies were conducted. The proposed approach was able to provide better solutions consistently.
An improved evolutionary algorithm (SCAGA) is proposed in this paper. The algorithm is based on new population initialization method and genetic operator. SCAGA adopts the crossover probability and ...mutation probability that vary with the increase of evolution generation in order to control genetic operations in an effective range. Meanwhile, SCAGA presents a new crossover strategy that restricts the cross of the chromosomes to some extent to protect good genes schema. The schema theorem is employed in the algorithm to analyze the working mechanism of SCAGA. According to experiment results for test functions and TSP problems, SCAGA is effective.
Genetic programming (GP) is one of the most widely used paradigms of evolutionary computation due to its ability to automatically synthesize computer programs and mathematical expressions. However, ...because GP uses a variable length representation, the individuals within the evolving population tend to grow rapidly without a corresponding return in fitness improvement, a phenomenon known as bloat. In this paper, we present a simple bloat control strategy for standard tree-based GP that achieves a one order of magnitude reduction in bloat when compared with standard GP on benchmark tests, and practically eliminates bloat on two real-world problems. Our proposal is to substitute standard subtree crossover with the one-point crossover (OPX) developed by Poli and Langdon (Second online world conference on soft computing in engineering design and manufacturing, Springer, Berlin (
1997
)), while maintaining all other GP aspects standard, particularly subtree mutation. OPX was proposed for theoretical purposes related to GP schema theorems, however since it curtails exploration during the search it has never achieved widespread use. In our results, on the other hand, we are able to show that OPX can indeed perform an effective search if it is coupled with subtree mutation, thus combining the bloat control capabilities of OPX with the exploration provided by standard mutation.
In the light of a recently derived evolution equation for genetic algorithms we consider the schema theorem and the building block hypothesis. We derive a schema theorem based on the concept of
...showing that schemata of higher than average effective fitness receive an exponentially increasing number of trials over time. The equation makes manifest the content of the building block hypothesis showing how fit schemata are constructed from fit sub-schemata. However, we show that, generically, there is no preference for short, low-order schemata. In the case where schema reconstruction is favored over schema destruction, large schemata tend to be favored. As a corollary of the evolution equation we prove Geiringer's theorem.
PDF
