Macroevolutionary algorithms: a new optimization method on fitnesslandscapes

Introduces an approach to optimization problems based on a previous theoretical work on extinction patterns in macroevolution. We name them macroevolutionary algorithms (MA). Unlike population-level evolution, which is employed in standard evolutionary algorithms, evolution at the level of higher taxa is used as the underlying metaphor. The model exploits the presence of links between “species” that represent candidate solutions to the optimization problem. To test its effectiveness, we compare the performance of MAs versus genetic algorithms (GA) with tournament selection. The method is shown to be a good alternative to standard GAs, showing a fast monotonous search over the solution space even for very small population sizes. A mean field theoretical approach is presented showing that the basic dynamics of MAs are close to an ecological model of multispecies competition     

Shape analysis using genetic algorithms

This paper introduces a novel methodology for shape discrimination by combining pattern recognition techniques such as morphological processing with concepts from artificial intelligence and machine learning such as genetic algorithms (GAs). High-performance shape discrimination operators, defined as variable structuring elements and sequenced as program forms, are derived using GAs. The population of operators, iteratively evaluated according to an performance index corresponding to shape discrimination ability, evolves into an optimal set of operators using the evolutionary principles of genetic search. Experimental results are included to illustrate the feasibility of our novel methodology for developing robust shape analysis methods.     

Self-adaptive genetic algorithms with simulated binary crossover

Self-adaptation is an essential feature of natural evolution. However, in the context of function optimization, self-adaptation features of evolutionary search algorithms have been explored mainly with evolution strategy (ES) and evolutionary programming (EP). In this paper, we demonstrate the self-adaptive feature of real-parameter genetic algorithms (GAs) using a simulated binary crossover (SBX) operator and without any mutation operator. The connection between the working of self-adaptive ESs and real-parameter GAs with the SBX operator is also discussed. Thereafter, the self-adaptive behavior of real-parameter GAs is demonstrated on a number of test problems commonly used in the ES literature. The remarkable similarity in the working principle of real-parameter GAs and self-adaptive ESs shown in this study suggests the need for emphasizing further studies on self-adaptive GAs.     

Evolutionary algorithm enhancement for model predictive control and real-time decision support

Effective decision support and model predictive control of real-time environmental systems require that evolutionary algorithms operate more efficiently. A suite of model predictive control (MPC) genetic algorithms are developed and tested offline to explore their value for reducing combined sewer overflow (CSO) volumes during real-time use in a deep-tunnel sewer system. MPC approaches include the micro-GA, the probability-based compact GA, and domain-specific GA methods that reduce the number of decision variable values analyzed within the sewer hydraulic model, thus reducing algorithm search space. Minimum fitness and constraint values achieved by all GA approaches, as well as computational times required to reach the minimum values, are compared to large population sizes with long convergence times. Optimization results for a subset of the Chicago combined sewer system indicate that genetic algorithm variations with a coarse decision variable representation, eventually transitioning to the entire range of decision variable values, are best suited to address the CSO control problem. Although diversity-enhancing micro-GAs evaluate a larger search space and exhibit shorter convergence times, these representations do not reach minimum fitness and constraint values. The domain-specific GAs prove to be the most efficient for this case study. Further MPC algorithm developments are suggested to continue advancing computational performance of this important class of problems with dynamic strategies that evolve as the external constraint conditions change.     

From the Dandelion Code to the Rainbow code: a class of bijective spanning tree representations with linear complexity and bounded locality

There are many ways to represent spanning trees in genetic algorithms (GAs). Among them are Cayley codes, which represent each tree on n vertices as a string of (n-2) integers from the set [1,n]. In 2003, Thompson showed that the Dandelion Code, a Cayley code with high locality, offers consistently better performance in a GA than all other known Cayley codes, including the Pru/spl uml/fer Code and the Blob Code. In this paper, we study the Dandelion Code and its properties. We give linear-time implementations of the decoding and encoding algorithms, and prove that the representation has bounded locality and asymptotically optimal locality, unlike all other known Cayley codes. We then modify the Dandelion Code to create bijective spanning tree representations for graph topologies other than the complete graph. Two variations are described: the bipartite Dandelion Code (for encoding the spanning trees of a complete bipartite graph) and the Rainbow Code (for encoding the spanning trees of a complete layered graph). Both variations inherit the Dandelion Code's desirable properties, and have the potential to outperform existing GA representations for computationally hard transportation problems (including the Fixed Charge Transportation Problem) and multistage transportation problems, particularly on large instances.     

A MORE BIOLOGICALLY MOTIVATED GENETIC ALGORITHM: THE MODEL AND SOME RESULTS

For more than two decades, genetic algorithms (GAs) have been studied by researchers from different fields. Over the years, many modifications have been suggested to alleviate the difficulties encountered by GAs in solving different problems. Despite these modifications, with the increase in application traditional GAs remain inadequate for many practical purposes. This paper introduces a new genetic model called the structured genetic algorithm (sGA) to address some of the difficulties encountered by the simple genetic approaches in solving various types of problems. The novelty of this genetic model lies primarily in its redundant genetic material and a gene activation mechanism that utilizes a multilayered structure for the chromosome. This representation provides genetic variation and has many advantages in search and optimization. For example, it can retain multiple (alternative) solutions or parameter spaces in its representation. In effect, it also works as a long-term distributed memory within the population, enabling rapid adaptation in non stationary environments. Theoretical arguments and empirical studies are presented which demonstrate that the sGA can more efficiently solve complex problems than simple GAs. It is also noted that the sGA exhibits greater implicit nondisruptive diversity than other exist-     

A novel parallel hybrid intelligence optimization algorithm for a function approximation problem

A novel parallel hybrid intelligence optimization algorithm (PHIOA) is proposed based on combining the merits of particle swarm optimization with genetic algorithms. The PHIOA uses the ideas of selection, crossover and mutation from genetic algorithms (GAs) and the update velocity and situation of particle swarm optimization (PSO) under the independence of PSO and GAs. The proposed algorithm divides the individuals into two equation groups according to their fitness values. The subgroup of the top fitness values is evolved by GAs and the other subgroup is evolved by the PSO algorithm. The optimal number is selected as a global optimum at every circulation which shows better results than both PSO and GAs, then improves the overall performance of the algorithm. The PHIOA is used to optimize the structure and parameters of the fuzzy neural network. Finally, the experimental results have demonstrated the superiority of the proposed PHIOA to search the global optimal solution. The PHIOA can improve the error accuracy while speeding up the convergence process, and effectively avoid the premature convergence to compare with the existing methods.     

ptGAs--genetic algorithms evolving noncoding segments by means of promoter/terminator sequences

In this article we present work on chromosome structures for genetic algorithms (GAs) based on biological principles. Mainly, the influence of noncoding segments on GA behavior and performance is investigated. We compare representations with noncoding sequences at predefined, fixed locations with "junk" code induced by the use of promoter/terminator sequences (ptGAs) that define start and end of a coding sequence, respectively. As one of the advantages of noncoding segments a few researchers have identified the reduction of the disruptive effects of crossover, and we solidify this argument by a formal analysis of crossover disruption probabilities for noncoding segments at fixed locations. The additional use of promoter/terminator sequences not only enables evolution of parameter values, but also allows for adaptation of number, size, and location of genes (problem parameters) on an artificial chromosome. Randomly generated chromosomes of fixed length carry different numbers of promoter/terminator sequences resulting in genes of varying size and location. Evolution of these ptGA chromosomes drives the number of parameters and their values to (sub)optimal solutions. Moreover, the formation of tightly linked building blocks is enhanced by self-organization of gene locations. We also introduce a new, nondisruptive crossover operator emerging from the ptGA gene structure with adaptive crossover rate, location, and number of crossover sites. For experimental comparisons of this genetic operator to conventional crossover in GAs, as well as properties of different ptGA chromosome structures, an artificial problem from the literature is utilized. Finally, the potential of ptGA is demonstrated on an NP-complete combinatorial optimization problem.     

The Dandelion Code: A New Coding of Spanning Trees for Genetic Algorithms

There are many applications where it is necessary to find an optimal spanning tree. For several of these, recent research has suggested the use of genetic algorithms (GAs). Historically, the Pruumlfer code has been one of the most popular representations for spanning trees, due largely to the bijective mapping between genotype and phenotype. However, it is has attracted much criticism for its low locality, a primary reason for its poor performance in GAs. Other representations such as direct encoding and network random keys have been shown to be far more effective. In 2001, an alternative called the Blob code was identified and adapted for use in GAs. It was shown to exhibit significantly higher locality than the Pruumlfer code. For a simple test problem, a GA using the Blob code was found to substantially outperform one using the Pruumlfer code. This paper suggests an alternative called the Dandelion code, which is more efficient and exhibits yet higher locality. Although both direct encoding and NetKeys are shown to give better results on the test problems used in this paper, the Dandelion code should be considered as a strong alternative, particularly for very large networks     

A genetic algorithm with disruptive selection

Genetic algorithms are a class of adaptive search techniques based on the principles of population genetics. The metaphor underlying genetic algorithms is that of natural evolution. Applying the “survival-of-the-fittest” principle, traditional genetic algorithms allocate more trials to above-average schemata. However, increasing the sampling rate of schemata that are above average does not guarantee convergence to a global optimum; the global optimum could be a relatively isolated peak or located in schemata that have large variance in performance. In this paper we propose a novel selection method, disruptive selection. This method adopts a nonmonotonic fitness function that is quite different from traditional monotonic fitness functions. Unlike traditional genetic algorithms, this method favors both superior and inferior individuals. Experimental results show that GAs using the proposed method easily find the optimal solution of a function that is hard for traditional GAs to optimize. We also present convergence analysis to estimate the occurrence ratio of the optima of a deceptive function after a certain number of generations of a genetic algorithm. Experimental results show that GAs using disruptive selection in some occasions find the optima more quickly and reliably than GAs using directional selection. These results suggest that disruptive selection can be useful in solving problems that have large variance within schemata and problems that are GA-deceptive     

Parametric and nonparametric evolutionary computing with a content-based feature selection approach for parallel categorization

This paper proposes two modified evolutionary computing methods for genetic algorithms (GAs) and proves an effective content-based feature selection approach to improve clustering performance. The conventional GAs suffer from the problem of slow learning and are prone to be trapped into a local minimum due to a high dimensional exploration space. In this paper, we propose a parametric and a nonparametric evolutionary algorithms to properly adjust the operators of GA. In the parametric approach, several fuzzy control parameters are artificially defined to adaptively optimize the GA behaviors. By contrast, they are automatically adjusted by GA itself in the nonparametric approach. Moreover, a content-based feature selection (CFS) approach is demonstrated to create a robust semantic space and reduce the number of dimension which accelerates the speed of evolutionary computing. We take advantage of a parallel computing technology to improve the efficiency of clustering. The experimental results show that our methods enhance the performance of the standard GA and are more efficient than those implemented on a single processor. The CFS approach not only reduces the document dimension, but also indirectly advances clustering efficiency.     

Effects of different chromosome representations in developing genetic algorithms to solve DFJS scheduling problems

This paper attempts to compare the effect of using different chromosome representations while developing a genetic algorithm to solve a scheduling problem called DFJS (distributed flexible job shop scheduling) problem. The DFJS problem is strongly NP-hard; most recent prior studies develop various genetic algorithms (GAs) to solve the problems. These prior GAs are similar in the algorithmic flows, but are different in proposing different chromosome representations. Extending from this line, this research proposes a new chromosome representation (called S_OP) and develops a genetic algorithm (called GA_OP) to solve the DFJS problem. Experiment results indicate that GA_OP outperforms all prior genetic algorithms. This research advocates the importance of developing appropriate chromosome representations while applying genetic algorithms (or other meta-heuristic algorithms) to solve a space search problem, in particular when the solution space is high-dimensional.     

Time scheduling of transit systems with transfer considerations using genetic algorithms

Scheduling of a bus transit system must be formulated as an optimization problem, if the level of service to passengers is to be maximized within the available resources. In this paper, we present a formulation of a transit system scheduling problem with the objective of minimizing the overall waiting time of transferring and nontransferring passengers while satisfying a number of resource- and service-related constraints. It is observed that the number of variables and constraints for even a simple transit system (a single bus station with three routes) is too large to tackle using classical mixed-integer optimization techniques. The paper shows that genetic algorithms (GAs) are ideal for these problems, mainly because they (i) naturally handle binary variables, thereby taking care of transfer decision variables, which constitute the majority of the decision variables in the transit scheduling problem; and (ii) allow procedure-based declarations, thereby allowing complex algorithmic approaches (involving if then-else conditions) to be handled easily. The paper also shows how easily the same GA procedure with minimal modifications can handle a number of other more pragmatic extensions to the simple transit scheduling problem: buses with limited capacity, buses that do not arrive exactly as per scheduled times, and a multiple-station transit system having common routes among bus stations. Simulation results show the success of GAs in all these problems and suggest the application of GAs in more complex scheduling problems.     

桁架结构振动的主动模糊控制中主动杆数目与位置优化

研究了采用自适应模糊控制器抑制桁架结构振动时的主动杆数目与位置优化问题.通过定义输入能量相关矩阵优化了主动杆的数目.基于主动杆的控制能量配置准则,给出了主动杆优化配置的模型.研究基于整数编码的遗传算法用于大型离散体中的作动器组合优化问题.最后针对挠性空间智能桁架结构的振动控制仿真,使用基于整数编码的遗传算法(GAs)优化主动杆位置.结果表明对于采用自适应模糊控制律的离散体结构振动控制是行之有效的.     

Bio-inspired computational heuristics for parameter estimation of nonlinear Hammerstein controlled autoregressive system

In this study, strength of evolutionary computational intelligence based on genetic algorithms (GAs) is exploited for parameter identification of nonlinear Hammerstein controlled autoregressive (NHCAR) systems. The fitness function is constructed for the NHCAR system by defining an error function in the mean square sense. Unknown adjustable weights of the system are optimized with GAs, used as an effective tool for effective global search. Comparative analysis of the proposed scheme is made from true parameters of the systems for a number of scenarios based on different levels of signal-to-noise ratios. The validation of the performance is made through statistics based on sufficiently large number of runs using indices of mean absolute error, variance account for, and Thiel’s inequality coefficient as well as their global versions.

     

Representations and evolutionary operators for the scheduling of pump operations in water distribution networks

Reducing the energy consumption of water distribution networks has never had more significance. The greatest energy savings can be obtained by carefully scheduling the operations of pumps. Schedules can be defined either implicitly, in terms of other elements of the network such as tank levels; or explicitly, by specifying the time during which each pump is on/off. The traditional representation of explicit schedules is a string of binary values with each bit representing pump on/off status during a particular time interval. In this paper, we formally define and analyze two new explicit representations based on time-controlled triggers, where the maximum number of pump switches is established beforehand and the schedule may contain fewer than the maximum number of switches. In these representations, a pump schedule is divided into a series of integers with each integer representing the number of hours for which a pump is active/inactive. This reduces the number of potential schedules compared to the binary representation, and allows the algorithm to operate on the feasible region of the search space. We propose evolutionary operators for these two new representations. The new representations and their corresponding operations are compared with the two most-used representations in pump scheduling, namely, binary representation and level-controlled triggers. A detailed statistical analysis of the results indicates which parameters have the greatest effect on the performance of evolutionary algorithms. The empirical results show that an evolutionary algorithm using the proposed representations is an improvement over the results obtained by a recent state of the art hybrid genetic algorithm for pump scheduling using level-controlled triggers.     

An overview of evolutionary algorithms: practical issues and common pitfalls

An overview of evolutionary algorithms is presented covering genetic algorithms, evolution strategies, genetic programming and evolutionary programming. The schema theorem is reviewed and critiqued. Gray codes, bit representations and real-valued representations are discussed for parameter optimization problems. Parallel Island models are also reviewed, and the evaluation of evolutionary algorithms is discussed.     

Predicting financial activity with evolutionary fuzzy case-based reasoning

Predicting financial activity through examining the short-term liquidity is crucial within today’s turbulent financial environment. Firms, governments, and individuals all need an effective methodology based on liquidity information that plays performance deterioration warning a priori bankruptcy prediction. In this paper, we propose a hybrid decision model using case-based reasoning augmented with genetic algorithms (GAs) and the fuzzy k nearest neighbor (fuzzy k-NN) methods for predicting the financial activity rate. GAs are used to determine the optimal or near-optimal weight vector of financial features expressed in linguistic values by the expert. A fuzzy k-NN-based CBR scheme is designed to compute memberships of financial activity rates and to provide a more flexible and practical mechanism for acquiring, creating, and reusing the expert’s decision knowledge. An empirical experimentation using 746 publicly traded Taiwanese firms shows that the average accuracy of the rating is about 92.36%, which is superior to other related models. The proposed approach not only can lend support to the decision of an expert, but also allow proper feedback for the expert to improve the quality of the decision.