Weighted local sharing and local clearing for multimodal optimisation

Local sharing is a method designed for efficient multimodal optimisation that combines fitness sharing with spatially structured populations and elitist replacement. In local sharing, the bias towards sharing and the influence of spatial structure is controlled by the deme (neighbourhood) size. This introduces an undesirable trade-off; to maximise the sharing effect large deme sizes must be used, but the opposite must be true if one wishes to maximise the influence of spatial population structure. This paper introduces two modifications to the local sharing method. The first alters local sharing so that parent selection and fitness sharing operate at two different spatial levels; parent selection is performed within small demes, while the effect of fitness sharing is weighted according to the distance between individuals in the entire population structure. The second method replaces fitness sharing within demes with clearing to produce a method that we call local clearing. The proposed methods, as tested on several benchmark problems, demonstrate a level of efficiency that surpasses that of traditional fitness sharing and standard local sharing. Additionally, they offer a level of parameter robustness that surpasses other elitist niching methods, such as clearing. Through analysis of the local clearing method, we show that this parameter robustness is a result of the isolated nature of the demes in a spatially structured population being able to independently concentrate on subsets of the desired optima in a fitness landscape.     

Multiobjective evolutionary algorithms: analyzing the state-of-the-art

Solving optimization problems with multiple (often conflicting) objectives is, generally, a very difficult goal. Evolutionary algorithms (EAs) were initially extended and applied during the mid-eighties in an attempt to stochastically solve problems of this generic class. During the past decade, a variety, of multiobjective EA (MOEA) techniques have been proposed and applied to many scientific and engineering applications. Our discussion's intent is to rigorously define multiobjective optimization problems and certain related concepts, present an MOEA classification scheme, and evaluate the variety of contemporary MOEAs. Current MOEA theoretical developments are evaluated; specific topics addressed include fitness functions, Pareto ranking, niching, fitness sharing, mating restriction, and secondary populations. Since the development and application of MOEAs is a dynamic and rapidly growing activity, we focus on key analytical insights based upon critical MOEA evaluation of current research and applications. Recommended MOEA designs are presented, along with conclusions and recommendations for future work.     

Parallel evolution using multi-chromosome cartesian genetic programming

Parallel and distributed methods for evolutionary algorithms have concentrated on maintaining multiple populations of genotypes, where each genotype in a population encodes a potential solution to the problem. In this paper, we investigate the parallelisation of the genotype itself into a collection of independent chromosomes which can be evaluated in parallel. We call this multi-chromosomal evolution (MCE). We test this approach using Cartesian Genetic Programming and apply MCE to a series of digital circuit design problems to compare the efficacy of MCE with a conventional single chromosome approach (SCE). MCE can be readily used for many digital circuits because they have multiple outputs. In MCE, an independent chromosome is assigned to each output. When we compare MCE with SCE we find that MCE allows us to evolve solutions much faster. In addition, in some cases we were able to evolve solutions with MCE that we unable to with SCE. In a case-study, we investigate how MCE can be applied to to a single objective problem in the domain of image classification, namely, the classification of breast X-rays for cancer. To apply MCE to this problem, we identify regions of interest (RoI) from the mammograms, divide the RoI into a collection of sub-images and use a chromosome to classify each sub-image. This problem allows us to evaluate various evolutionary mutation operators which can pairwise swap chromosomes either randomly or topographically or reuse chromosomes in place of other chromosomes.     

Multiobjective evolutionary algorithms: a comparative case studyand the strength Pareto approach

Evolutionary algorithms (EAs) are often well-suited for optimization problems involving several, often conflicting objectives. Since 1985, various evolutionary approaches to multiobjective optimization have been developed that are capable of searching for multiple solutions concurrently in a single run. However, the few comparative studies of different methods presented up to now remain mostly qualitative and are often restricted to a few approaches. In this paper, four multiobjective EAs are compared quantitatively where an extended 0/1 knapsack problem is taken as a basis. Furthermore, we introduce a new evolutionary approach to multicriteria optimization, the strength Pareto EA (SPEA), that combines several features of previous multiobjective EAs in a unique manner. It is characterized by (a) storing nondominated solutions externally in a second, continuously updated population, (b) evaluating an individual's fitness dependent on the number of external nondominated points that dominate it, (c) preserving population diversity using the Pareto dominance relationship, and (d) incorporating a clustering procedure in order to reduce the nondominated set without destroying its characteristics. The proof-of-principle results obtained on two artificial problems as well as a larger problem, the synthesis of a digital hardware-software multiprocessor system, suggest that SPEA can be very effective in sampling from along the entire Pareto-optimal front and distributing the generated solutions over the tradeoff surface. Moreover, SPEA clearly outperforms the other four multiobjective EAs on the 0/1 knapsack problem     

On the role of population size and niche radius in fitness sharing

We propose a characterization of the dynamic behavior of an evolutionary algorithm (EA) with fitness sharing as a function of both the niche radius and the population size. Such a characterization, given in terms of the mean and the standard deviation of the number of niches found during the evolution, can be applied to any EA employing a proportional selection mechanism and does not make any assumption on either the fitness landscape or the internal parameters of the EA itself. On the basis of the proposed characterization, a method for estimating the optimal values for the population size and the niche radius without any a priori information on the fitness landscape is presented and tested on a standard set of functions. The proposed method also provides the best solution for the problem at hand, i.e., the solution obtained in correspondence of such optimal values, at no additional cost.     

Backward-chaining evolutionary algorithms

Starting from some simple observations on a popular selection method in Evolutionary Algorithms (EAs)—tournament selection—we highlight a previously-unknown source of inefficiency. This leads us to rethink the order in which operations are performed within EAs, and to suggest an algorithm—the EA with efficient macro-selection—that avoids the inefficiencies associated with tournament selection. This algorithm has the same expected behaviour as the standard EA but yields considerable savings in terms of fitness evaluations. Since fitness evaluation typically dominates the resources needed to solve any non-trivial problem, these savings translate into a reduction in computer time. Noting the connection between the algorithm and rule-based systems, we then further modify the order of operations in the EA, effectively turning the evolutionary search into an inference process operating in backward-chaining mode. The resulting backward-chaining EA creates and evaluates individuals recursively, backward from the last generation to the first, using depth-first search and backtracking. It is even more powerful than the EA with efficient macro-selection in that it shares all its benefits, but it also provably finds fitter solutions sooner, i.e., it is a faster algorithm. These algorithms can be applied to any form of population based search, any representation, fitness function, crossover and mutation, provided they use tournament selection. We analyse their behaviour and benefits both theoretically, using Markov chain theory and space/time complexity analysis, and empirically, by performing a variety of experiments with standard and back-ward chaining versions of genetic algorithms and genetic programming.     

Evolutionary dynamics for the spatial Moran process

Evolutionary dynamics for the Moran process have been previously examined within the context of fixation behaviour for introduced mutants, where it was demonstrated that certain spatial structures act as amplifiers of selection. This article will revisit the assumptions for this spatial Moran process and show that proportional global fitness, introduced as part of the Moran process, is necessary for the amplification of selection to occur. Here it is shown that under the condition of local proportional fitness selection the amplification property no longer holds. In addition, regular structures are also shown to have a modified fixation probability from a panmictic population when local selection is applied. Theoretical results from population genetics, which suggest fixation probabilities are independent of geography, are discussed in relation to these local graph-based models and shown to have different assumptions and therefore not to be in conflict with the presented results. This paper examines the issue of fixation probability of an introduced advantageous allele in terms of spatial structure and various spatial parent selection models. The results describe the relationship between structured populations and individual selective advantage in a problem independent manner. This is of significant interest to the theory of fine-grained spatially-structured evolutionary algorithms since the interaction of selection and space for diversity maintenance, selection strength and convergence underlies resulting evolutionary trajectories.     

A new method to solve generalized multicriteria optimization problems using the simple genetic algorithm

Genetic algorithms (GAs), which are directed stochastic hill climbing algorithms, are a commonly used optimization technique and are generally applied to single criterion optimization problems with fairly complex solution landscapes. There has been some attempts to apply GA to multicriteria optimization problems. The GA selection mechanism is typically dependent on a single-valued objective function and so no general methods to solve multicriteria optimization problems have been developed so far. In this paper, a new method of transformation of the multiple criteria problem into a single-criterion problem is presented. The problem of transformation brings about the need for the introduction of thePareto set estimation method to perform the multicriteria optimization using GAs. From a given solution set, which is the population of a certain generation of the GA, the Pareto set is found. The fitness of population members in the next GA generation is calculated by a distance metric with a reference to the Pareto set of the previous generation. As we are unable to combine the objectives in some way, we resort to this distance metric in the positive Pareto space of the previous solutions, as the fitness of the current solutions. This new GA-based multicriteria optimization method is proposed here, and it is capable of handling any generally formulated multicriteria optimization problem. The main idea of the method is described in detail in this paper along with a detailed numerical example. Preliminary computer generated results show that our approach produces better, and far more Pareto solutions, than plain stochastic optimization methods.     

Multimodal optimization using a bi-objective evolutionary algorithm

In a multimodal optimization task, the main purpose is to find multiple optimal solutions (global and local), so that the user can have better knowledge about different optimal solutions in the search space and as and when needed, the current solution may be switched to another suitable optimum solution. To this end, evolutionary optimization algorithms (EA) stand as viable methodologies mainly due to their ability to find and capture multiple solutions within a population in a single simulation run. With the preselection method suggested in 1970, there has been a steady suggestion of new algorithms. Most of these methodologies employed a niching scheme in an existing single-objective evolutionary algorithm framework so that similar solutions in a population are deemphasized in order to focus and maintain multiple distant yet near-optimal solutions. In this paper, we use a completely different strategy in which the single-objective multimodal optimization problem is converted into a suitable bi-objective optimization problem so that all optimal solutions become members of the resulting weak Pareto-optimal set. With the modified definitions of domination and different formulations of an artificially created additional objective function, we present successful results on problems with as large as 500 optima. Most past multimodal EA studies considered problems having only a few variables. In this paper, we have solved up to 16-variable test problems having as many as 48 optimal solutions and for the first time suggested multimodal constrained test problems which are scalable in terms of number of optima, constraints, and variables. The concept of using bi-objective optimization for solving single-objective multimodal optimization problems seems novel and interesting, and more importantly opens up further avenues for research and application.     

An economical cognitive approach for bi-objective optimization using bliss points, visualization, and interaction

When an optimization problem encompasses multiple objectives, it is usually difficult to define a single optimal solution. The decision maker plays an important role when choosing the final single decision. Pareto-based evolutionary multiobjective optimization (EMO) methods are very informative for the decision making process since they provide the decision maker with a set of efficient solutions to choose from. Despite that the set of efficient solutions may not be the global efficient set, we show in this paper that the set can still be informative when used in an interactive session with the decision maker. We use a combination of EMO and single objective optimization methods to guide the decision maker in interactive sessions.     

Niche identification techniques in multimodal genetic search with sharing scheme

Genetic algorithms with sharing have been applied in many multimodal optimization problems with success. Traditional sharing schemes require the definition of a common sharing radius, but the predefined radius cannot fit most problems where design niches are of different sizes. Yin and Germay proposed a sharing scheme with cluster analysis methods, which can determine design clusters of different sizes. Since clusters are not necessarily coincident with niches, sharing with clustering techniques fails to provide maximum sharing effects. In this paper, a sharing scheme based on niche identification techniques (NIT) is proposed, which is capable of determining the center location and radius of each of existing niches based on fitness topographical information of designs in the population. Genetic algorithms with NIT were tested and compared to GAs with traditional sharing scheme and sharing with cluster analysis methods in four illustrative problems. Results of numerical experiments showed that the sharing scheme with NIT improved both search stability and effectiveness of locating multiple optima. The niche-based genetic algorithm and the multiple local search approach are compared in the fifth illustrative problem involving a discrete ten-variable bump function problem.     

Multiobjective optimization and multiple constraint handling withevolutionary algorithms. I. A unified formulation

In optimization, multiple objectives and constraints cannot be handled independently of the underlying optimizer. Requirements such as continuity and differentiability of the cost surface add yet another conflicting element to the decision process. While “better” solutions should be rated higher than “worse” ones, the resulting cost landscape must also comply with such requirements. Evolutionary algorithms (EAs), which have found application in many areas not amenable to optimization by other methods, possess many characteristics desirable in a multiobjective optimizer, most notably the concerted handling of multiple candidate solutions. However, EAs are essentially unconstrained search techniques which require the assignment of a scalar measure of quality, or fitness, to such candidate solutions. After reviewing current revolutionary approaches to multiobjective and constrained optimization, the paper proposes that fitness assignment be interpreted as, or at least related to, a multicriterion decision process. A suitable decision making framework based on goals and priorities is subsequently formulated in terms of a relational operator, characterized, and shown to encompass a number of simpler decision strategies. Finally, the ranking of an arbitrary number of candidates is considered. The effect of preference changes on the cost surface seen by an EA is illustrated graphically for a simple problem. The paper concludes with the formulation of a multiobjective genetic algorithm based on the proposed decision strategy. Niche formation techniques are used to promote diversity among preferable candidates, and progressive articulation of preferences is shown to be possible as long as the genetic algorithm can recover from abrupt changes in the cost landscape     

Evolutionary algorithm with a directional local search for multiobjective optimization in combinatorial problems

Evolutionary algorithms (EAs) are often employed to multiobjective optimization, because they process an entire population of solutions which can be used as an approximation of the Pareto front of the tackled problem. It is a common practice to couple local search with evolutionary algorithms, especially in the context of combinatorial optimization. In this paper a new local search method is proposed that utilizes the knowledge concerning promising search directions. The proposed method can be used as a general framework and combined with many methods of iterating over a neighbourhood of an initial solution as well as various decomposition approaches. In the experiments the proposed local search method was used with an EA and tested on 2-, 3- and 4-objective versions of two well-known combinatorial optimization problems: the travelling salesman problem (TSP) and the quadratic assignment problem (QAP). For comparison two well-known local search methods, one based on Pareto dominance and the other based on decomposition, were used with the same EA. The results show that the EA coupled with the directional local search yields better results than the same EA coupled with any of the two reference methods on both the TSP and QAP problems.     

A fuzzy self-tuning parallel genetic algorithm for optimization

The genetic algorithm (GA) is now a very popular tool for solving optimization problems. Each operator has its special approach route to a solution. For example, a GA using crossover as its major operator arrives at solutions depending on its initial conditions. In other words, a GA with multiple operators should be more robust in global search. However, a multiple operator GA needs a large population size thus taking a huge time for evaluation. We therefore apply fuzzy reasoning to give effective operators more opportunity to search while keeping the overall population size constant. We propose a fuzzy self-tuning parallel genetic algorithm (FPGA) for optimization problems. In our test case FPGA there are four operators—crossover, mutation, sub-exchange, and sub-copy. These operators are modified using the eugenic concept under the assumption that the individuals with higher fitness values have a higher probability of breeding new better individuals. All operators are executed in each generation through parallel processing, but the populations of these operators are decided by fuzzy reasoning. The fuzzy reasoning senses the contributions of these operators, and then decides their population sizes. The contribution of each operator is defined as an accumulative increment of fitness value due to each operator's success in searching. We make the assumption that the operators that give higher contribution are more suitable for the typical optimization problem. The fuzzy reasoning is built under this concept and adjusts the population sizes in each generation. As a test case, a FPGA is applied to the optimization of the fuzzy rule set for a model reference adaptive control system. The simulation results show that the FPGA is better at finding optimal solutions than a traditional GA.     

Zen-ReqOptimizer: a search-based approach for requirements assignment optimization

At early phases of a product development lifecycle of large scale Cyber-Physical Systems (CPSs), a large number of requirements need to be assigned to stakeholders from different organizations or departments of the same organization for review, clarification and checking their conformance to standards and regulations. These requirements have various characteristics such as extents of importance to the organization, complexity, and dependencies between each other, thereby requiring different effort (workload) to review and clarify. While working with our industrial partners in the domain of CPSs, we discovered an optimization problem, where an optimal solution is required for assigning requirements to various stakeholders by maximizing their familiarity to assigned requirements, meanwhile balancing the overall workload of each stakeholder. In this direction, we propose a fitness function that takes into account all the above-mentioned factors to guide a search algorithm to find an optimal solution. As a pilot experiment, we first investigated four commonly applied search algorithms (i.e., GA, (1 + 1) EA, AVM, RS) together with the proposed fitness function and results show that (1 + 1) EA performs significantly better than the other algorithms. Since our optimization problem is multi-objective, we further empirically evaluated the performance of the fitness function with six multi-objective search algorithms (CellDE, MOCell, NSGA-II, PAES, SMPSO, SPEA2) together with (1 + 1) EA (the best in the pilot study) and RS (as the baseline) in terms of finding an optimal solution using an real-world case study and 120 artificial problems of varying complexity. Results show that both for the real-world case study and the artificial problems (1 + 1) EA achieved the best performance for each single objective and NSGA-II achieved the best performance for the overall fitness. NSGA-II has the ability to solve a wide range of problems without having their performance degraded significantly and (1 + 1) EA is not fit for problems with less than 250 requirements Therefore we recommend that, if a project manager is interested in a particular objective then (1 + 1) EA should be used; otherwise, NSGA-II should be applied to obtain optimal solutions when putting the overall fitness as the first priority.     

Tuning of PID controller based on a multiobjective genetic algorithm applied to a robotic manipulator

Most controllers optimization and design problems are multiobjective in nature, since they normally have several (possibly conflicting) objectives that must be satisfied at the same time. Instead of aiming at finding a single solution, the multiobjective optimization methods try to produce a set of good trade-off solutions from which the decision maker may select one. Several methods have been devised for solving multiobjective optimization problems in control systems field. Traditionally, classical optimization algorithms based on nonlinear programming or optimal control theories are applied to obtain the solution of such problems. The presence of multiple objectives in a problem usually gives rise to a set of optimal solutions, largely known as Pareto-optimal solutions. Recently, Multiobjective Evolutionary Algorithms (MOEAs) have been applied to control systems problems. Compared with mathematical programming, MOEAs are very suitable to solve multiobjective optimization problems, because they deal simultaneously with a set of solutions and find a number of Pareto optimal solutions in a single run of algorithm. Starting from a set of initial solutions, MOEAs use iteratively improving optimization techniques to find the optimal solutions. In every iterative progress, MOEAs favor population-based Pareto dominance as a measure of fitness. In the MOEAs context, the Non-dominated Sorting Genetic Algorithm (NSGA-II) has been successfully applied to solving many multiobjective problems. This paper presents the design and the tuning of two PID (Proportional–Integral–Derivative) controllers through the NSGA-II approach. Simulation numerical results of multivariable PID control and convergence of the NSGA-II is presented and discussed with application in a robotic manipulator of two-degree-of-freedom. The proposed optimization method based on NSGA-II offers an effective way to implement simple but robust solutions providing a good reference tracking performance in closed loop.     

Chaotic populations in genetic algorithms

We set two objectives for this study: one is to emulate chaotic natural populations in GA (Genetic Algorithms) populations by utilizing the Logistic Chaos map model, and the other is to analyze the population fitness distribution by utilizing insect spatial distribution theory. Natural populations are so dynamic that one of the first experimental evidences of Chaos in nature was discovered by a theoretical ecologist, May (1976, Nature, 261,459–467)[30], in his analysis of insect population dynamics. In evolutionary computing, perhaps influenced by the stable or infinite population concepts in population genetics, the status quo of population settings has dominantly been the fixed-size populations. In this paper, we propose to introduce dynamic populations controlled by the Logistic Chaos map model to Genetic Algorithms (GA), and test the hypothesis – whether or not the dynamic populations that emulate chaotic populations in nature will have an advantage over traditional fixed-size populations.The Logistic Chaos map model, arguably the simplest nonlinear dynamics model, has surprisingly rich dynamic behaviors, ranging from exponential, sigmoid growth, periodic oscillations, and aperiodic oscillations, to complete Chaos. What is even more favorable is that, unlike many other population dynamics models, this model can be expressed as a single parameter recursion equation, which makes it very convenient to control the dynamic behaviors and therefore easy to apply to evolutionary computing. The experiments show result values in terms of the fitness evaluations and memory storage requirements. We further conjecture that Chaos may be helpful in breaking neutral space in the fitness landscape, similar to the argument in ecology that Chaos may help the exploration and/or exploitation of environment heterogeneity and therefore enhance a species’ survival or fitness.     

Designing a classifier by a layered multi-population genetic programming approach

This paper proposes a method called layered genetic programming (LAGEP) to construct a classifier based on multi-population genetic programming (MGP). LAGEP employs layer architecture to arrange multiple populations. A layer is composed of a number of populations. The results of populations are discriminant functions. These functions transform the training set to construct a new training set. The successive layer uses the new training set to obtain better discriminant functions. Moreover, because the functions generated by each layer will be composed to a long discriminant function, which is the result of LAGEP, every layer can evolve with short individuals. For each population, we propose an adaptive mutation rate tuning method to increase the mutation rate based on fitness values and remaining generations. Several experiments are conducted with different settings of LAGEP and several real-world medical problems. Experiment results show that LAGEP achieves comparable accuracy to single population GP in much less time.     

基于（μ＋λ）选择策略的多目标优化分段遗传算法

在多目标优化遗传算法中，将整个种群按目标函数值划分成若干子种群，在各子种群内μ个父代经遗传操作产生λ个后代；然后将各子种群的所有父代和后代个体收集起来进行种群排序适应度共享，选取较好的个体组成下一代种群。相邻的非劣解容易分在同一子种群有利于提高搜索效率；各子种群间的遗传操作可采用并行处理；各子种群的所有
有个体收集起来进行适应度共享有利于维持种群的多样性。最后给出了计算实例。     

A novel approach to the placement and routing problems for field programmable gate arrays

This paper presents an artificial neural network (ANN) based parallel evolutionary solution to the placement and routing problems for field programmable gate arrays (FPGAs). The concepts of artificial neural networks are utilized for guiding the parallel genetic algorithm to intelligently transform a set of initial populations of randomly generated solutions to a final set of populations that contain solutions approximating the optimal one. The fundamental concept of this paper lies in capturing the various intuitive strategies of the human brain into neural networks, which may help the genetic algorithm to evolve its population in a more lucrative manner. A carefully chosen fitness function acts in the capacity of a yardstick to appraise the quality of each “chromosome” to aid the selection phase. In conjunction with the migration phase and the chosen fitness function various genetic operators are employed, to expedite the transformation of the initial population towards the final solution. The suggested algorithms have been implemented on a 12-node SGI Origin-2000 platform using the message passing interface (MPI) standard and the neural network utilities provided by MAT Lab software. The results obtained by executing the same are extremely encouraging, especially for circuits with very large number of nets.