2007
DocumentsDate added
Benchmark Functions for the CEC’2008 Special Session and Competition on Large Scale Global Optimization
Abstract: In the past two decades, different kinds of nature-inspired optimization algorithms have been designed and applied to solve optimization problems, e.g., simulated annealing (SA), evolutionary algorithms (EAs), differential evolution (DE), particle swarm optimization (PSO), Ant Colony Optimisation (ACO), Estimation of Distribution Algorithms (EDA), etc. Although these approaches have shown excellent search abilities when applying to some 30-100 dimensional problems, many of them suffer from the "curse of dimensionality", which implies that their performance deteriorates quickly as the dimensionality of search space increases. The reasons appear to be two-fold. First, complexity of the problem usually increases with the size of problem, and a previously successful search strategy may no longer be capable of finding the optimal solution. Second, the solution space of the problem increases exponentially with the problem size, and a more efficient search strategy is required to explore all the promising regions in a given time budget.
Historically, scaling EAs to large size problems have attracted much interest, including both theoretical and practical studies. The earliest practical approach might be the parallelism of an existing EA. Later, cooperative coevolution appears to be another promising method. However, existing work on this topic are often limited to the test problems used in individual studies, and a systematic evaluation platform is not available in the literature for comparing the scalability of different EAs.
In this report, 6 benchmark functions are given based on [1] and [2] for high-dimensional optimization. All of them are scalable for any size of dimension. The codes in Matlab and C for them are available at http://nical.ustc.edu.cn/cec08ss.php. The other benchmark function (Function 7 - FastFractal "DoubleDip") is generated based on [3] [4]. The C code for function 7 has been contributed by Ales Zamuda from the University of Maribor, Slovenia. It uses the GJC / CNI interface to run the Java code from C++. In the package, C code is provided in a separate zip file, named "cec08-f7-cpp.zip".
The mathematical formulas and properties of these functions are described in Section 2, and the evaluation criteria are given in Section 3.
Abstract: In the past two decades, different kinds of nature-inspired optimization algorithms have been designed and applied to solve optimization problems, e.g., simulated annealing (SA), evolutionary algorithms (EAs), differential evolution (DE), particle swarm optimization (PSO), Ant Colony Optimisation (ACO), Estimation of Distribution Algorithms (EDA), etc. Although these approaches have shown excellent search abilities when applying to some 30-100 dimensional problems, many of them suffer from the "curse of dimensionality", which implies that their performance deteriorates quickly as the dimensionality of search space increases. The reasons appear to be two-fold. First, complexity of the problem usually increases with the size of problem, and a previously successful search strategy may no longer be capable of finding the optimal solution. Second, the solution space of the problem increases exponentially with the problem size, and a more efficient search strategy is required to explore all the promising regions in a given time budget.
Historically, scaling EAs to large size problems have attracted much interest, including both theoretical and practical studies. The earliest practical approach might be the parallelism of an existing EA. Later, cooperative coevolution appears to be another promising method. However, existing work on this topic are often limited to the test problems used in individual studies, and a systematic evaluation platform is not available in the literature for comparing the scalability of different EAs.
In this report, 6 benchmark functions are given based on [1] and [2] for high-dimensional optimization. All of them are scalable for any size of dimension. The codes in Matlab and C for them are available at http://nical.ustc.edu.cn/cec08ss.php. The other benchmark function (Function 7 - FastFractal "DoubleDip") is generated based on [3] [4]. The C code for function 7 has been contributed by Ales Zamuda from the University of Maribor, Slovenia. It uses the GJC / CNI interface to run the Java code from C++. In the package, C code is provided in a separate zip file, named "cec08-f7-cpp.zip".
The mathematical formulas and properties of these functions are described in Section 2, and the evaluation criteria are given in Section 3.
Crowd Control with Swarm Intelligence
Abstract: This paper presents a uniform conceptual model based on the particle swarm optimization (PSO) paradigm to simulate crowds in computer graphics. According to the mechanisms of PSO, each person (particle) in the crowd (swarm) can adopt the information to search a path from the initial position to the specified target (optimum) automatically. However, PSO aims to obtain the optimal solution, while the purpose of this study concentrates on the generated paths of particles. Hence, in order to generate appropriate paths of people in a crowd, we propose a method to employ the computational facilities provided in PSO. The proposed model is simple, uniform, and easy to implement. The results of simulations demonstrate that using PSO with the proposed technique can generate appropriate non-deterministic, non-colliding paths in several different scenarios, including static obstacles, moving targets, and multiple crowds.
Abstract: This paper presents a uniform conceptual model based on the particle swarm optimization (PSO) paradigm to simulate crowds in computer graphics. According to the mechanisms of PSO, each person (particle) in the crowd (swarm) can adopt the information to search a path from the initial position to the specified target (optimum) automatically. However, PSO aims to obtain the optimal solution, while the purpose of this study concentrates on the generated paths of particles. Hence, in order to generate appropriate paths of people in a crowd, we propose a method to employ the computational facilities provided in PSO. The proposed model is simple, uniform, and easy to implement. The results of simulations demonstrate that using PSO with the proposed technique can generate appropriate non-deterministic, non-colliding paths in several different scenarios, including static obstacles, moving targets, and multiple crowds.
On The Extension of ECGA for Different Variable Types: Integers and Real Numbers
Abstract: Extended compact genetic algorithm (ECGA) is an algorithm that can solve hard problems in the binary domain. ECGA is reliable and accurate because of the capability of detecting building blocks, but certain difficulties are encountered when we directly apply ECGA to problems in the integer domain. In this paper, we propose a new algorithm that extends ECGA, called integer extended compact genetic algorithm (iECGA). iECGA uses a modified probability model and inherits the capability of detecting building blocks from ECGA. iECGA is specifically designed for problems in the integer domain and can avoid the difficulties that ECGA encounters.
We also develop a new optimization framework that consists of the extended compact genetic algorithm (ECGA) and split-on-demand (SoD), an adaptive discretization technique, to tackle the characteristic determination problem for solid state devices. As most decision variables of characteristic determination problems are real numbers due to the modeling of physical phenomena, and ECGA is designed for handling discrete-type problems, a specific mechanism to transform the variable types of the two ends is in order. Therefore, in this study, we employ the proposed framework on three study cases to demonstrate that the technique proposed in the domain of evolutionary computation can provide not only the high quality optimization results but also the flexibility to handle problems of different formulations.
Abstract: Extended compact genetic algorithm (ECGA) is an algorithm that can solve hard problems in the binary domain. ECGA is reliable and accurate because of the capability of detecting building blocks, but certain difficulties are encountered when we directly apply ECGA to problems in the integer domain. In this paper, we propose a new algorithm that extends ECGA, called integer extended compact genetic algorithm (iECGA). iECGA uses a modified probability model and inherits the capability of detecting building blocks from ECGA. iECGA is specifically designed for problems in the integer domain and can avoid the difficulties that ECGA encounters.
We also develop a new optimization framework that consists of the extended compact genetic algorithm (ECGA) and split-on-demand (SoD), an adaptive discretization technique, to tackle the characteristic determination problem for solid state devices. As most decision variables of characteristic determination problems are real numbers due to the modeling of physical phenomena, and ECGA is designed for handling discrete-type problems, a specific mechanism to transform the variable types of the two ends is in order. Therefore, in this study, we employ the proposed framework on three study cases to demonstrate that the technique proposed in the domain of evolutionary computation can provide not only the high quality optimization results but also the flexibility to handle problems of different formulations.
A Survey of Linkage Learning Techniques in Genetic and Evolutionary Algorithms
Abstract: This paper reviews and summarizes existing linkage learning techniques for genetic and evolutionary algorithms in the literature. It first introduces the definition of linkage in both biological systems and genetic algorithms. Then, it discusses the importance for genetic and evolutionary algorithms to be capable of learning linkage, which is referred to as the relationship between decision variables. Existing linkage learning methods proposed in the literature are reviewed according to different facets of genetic and evolutionary algorithms, including the means to distinguish between good linkage and bad linkage, the methods to express or represent linkage, and the ways to store linkage information. Studies related to these linkage learning methods and techniques are also investigated in this survey.
Abstract: This paper reviews and summarizes existing linkage learning techniques for genetic and evolutionary algorithms in the literature. It first introduces the definition of linkage in both biological systems and genetic algorithms. Then, it discusses the importance for genetic and evolutionary algorithms to be capable of learning linkage, which is referred to as the relationship between decision variables. Existing linkage learning methods proposed in the literature are reviewed according to different facets of genetic and evolutionary algorithms, including the means to distinguish between good linkage and bad linkage, the methods to express or represent linkage, and the ways to store linkage information. Studies related to these linkage learning methods and techniques are also investigated in this survey.
Linkage Identification by Perturbation and Decision Tree Induction
Abstract: The purpose of linkage identification in genetic and evolutionary algorithms is to detect the tightly linked variables of the fitness function. If such linkage information is not known a priori and can be obtained through computation, the crossover or recombination operator can accordingly mix discovered sub-solutions effectively without disrupting them. In this paper, we propose a linkage identification technique, called inductive linkage identification (ILI), employing perturbation with decision making. With the proposed scheme, the linkage information can obtained by constructing an ID3 decision tree to learn the mapping from population of solutions to their corresponding fitness differences caused by perturbation and inspecting the constructed decision tree for variables exhibiting strong interdependencies with one another. The numerical results show that the proposed technique can accomplish the identical linkage identification tasks with a lower number of function evaluations compared to similar methods proposed in the literature. Moreover, the proposed technique is shown able to handle both uniformly scaled and exponentially scaled problems.
Abstract: The purpose of linkage identification in genetic and evolutionary algorithms is to detect the tightly linked variables of the fitness function. If such linkage information is not known a priori and can be obtained through computation, the crossover or recombination operator can accordingly mix discovered sub-solutions effectively without disrupting them. In this paper, we propose a linkage identification technique, called inductive linkage identification (ILI), employing perturbation with decision making. With the proposed scheme, the linkage information can obtained by constructing an ID3 decision tree to learn the mapping from population of solutions to their corresponding fitness differences caused by perturbation and inspecting the constructed decision tree for variables exhibiting strong interdependencies with one another. The numerical results show that the proposed technique can accomplish the identical linkage identification tasks with a lower number of function evaluations compared to similar methods proposed in the literature. Moreover, the proposed technique is shown able to handle both uniformly scaled and exponentially scaled problems.
Crowd Control with Swarm Intelligence
Abstract: This paper presents a uniform conceptual model based on the particle swarm optimization (PSO) paradigm to simulate crowds in computer graphics. According to the mechanisms of PSO, each person (particle) in the crowd (swarm) can adopt the information to search a path from the initial position to the specified target (optimum) automatically. However, PSO aims to obtain the optimal solution, while the purpose of this study concentrates on the generated paths of particles. Hence, in order to generate appropriate paths of people in a crowd, we propose a method to employ the computational facilities provided in PSO. The proposed model is simple, uniform, and easy to implement. The results of simulations demonstrate that using PSO with the proposed technique can generate appropriate non-deterministic, non-colliding paths in several different scenarios, including static obstacles, moving targets, and multiple crowds.
Abstract: This paper presents a uniform conceptual model based on the particle swarm optimization (PSO) paradigm to simulate crowds in computer graphics. According to the mechanisms of PSO, each person (particle) in the crowd (swarm) can adopt the information to search a path from the initial position to the specified target (optimum) automatically. However, PSO aims to obtain the optimal solution, while the purpose of this study concentrates on the generated paths of particles. Hence, in order to generate appropriate paths of people in a crowd, we propose a method to employ the computational facilities provided in PSO. The proposed model is simple, uniform, and easy to implement. The results of simulations demonstrate that using PSO with the proposed technique can generate appropriate non-deterministic, non-colliding paths in several different scenarios, including static obstacles, moving targets, and multiple crowds.
Enabling the Extended Compact Genetic Algorithm for Real-Parameter Optimization by using Adaptive Discretization
Abstract: This paper proposes an adaptive discretization method, called Split-on-Demand (SoD), to enable probabilistic model building genetic algorithms (PMBGAs) to solve optimization problems in the continuous domain. The procedure, effect, and usage of SoD are described in detail. As an example of using SoD with PMBGAs, the integration of SoD and the extended compact genetic algorithm (ECGA), named real-coded ECGA (rECGA), is proposed and numerically examined in the study. The numerical experiments include a set of benchmark functions and a real-world application, the economic dispatch problem. The results on the benchmark functions indicate that SoD is a better discretization method than two well-known methods: the fixed-height histogram (FHH) and the fixed-width histogram (FWH). Moreover, the experimental results on the economic dispatch problems demonstrate that rECGA works quite well, and the solutions better than the best known results presented in the literature are achieved.
Abstract: This paper proposes an adaptive discretization method, called Split-on-Demand (SoD), to enable probabilistic model building genetic algorithms (PMBGAs) to solve optimization problems in the continuous domain. The procedure, effect, and usage of SoD are described in detail. As an example of using SoD with PMBGAs, the integration of SoD and the extended compact genetic algorithm (ECGA), named real-coded ECGA (rECGA), is proposed and numerically examined in the study. The numerical experiments include a set of benchmark functions and a real-world application, the economic dispatch problem. The results on the benchmark functions indicate that SoD is a better discretization method than two well-known methods: the fixed-height histogram (FHH) and the fixed-width histogram (FWH). Moreover, the experimental results on the economic dispatch problems demonstrate that rECGA works quite well, and the solutions better than the best known results presented in the literature are achieved.
Introducing Fault Tolerance to XCS
Abstract: In this paper, we introduce fault tolerance to XCS and propose a new XCS framework called XCS with Fault Tolerance (XCS/FT). As an important branch of learning classifier systems, XCS has been proven capable of evolving maximally accurate, maximally general problem solutions. However, in practice, it oftentimes generates a lot of rules, which lower the readability of the evolved classification model, and thus, people may not be able to get the desired knowledge or useful information out of the model. Inspired by the fault tolerance mechanism proposed in field of data mining, we devise a new XCS framework by integrating the concept and mechanism of fault tolerance into XCS in order to reduce the number of classification rules and therefore to improve the readability of the generated prediction model. The workflow and operations of the XCS/FT framework are described in detail. A series of $N$-multiplexer experiments, including 6-bit, 11-bit, 20-bit, and 37-bit multiplexers, are conducted to examine whether XCS/FT can accomplish its goal of design. According to the experimental results, XCS/FT can offer the same level of prediction accuracy on the test problems as XCS can, while the prediction model evolved by XCS/FT consists of significantly fewer classification rules.
Abstract: In this paper, we introduce fault tolerance to XCS and propose a new XCS framework called XCS with Fault Tolerance (XCS/FT). As an important branch of learning classifier systems, XCS has been proven capable of evolving maximally accurate, maximally general problem solutions. However, in practice, it oftentimes generates a lot of rules, which lower the readability of the evolved classification model, and thus, people may not be able to get the desired knowledge or useful information out of the model. Inspired by the fault tolerance mechanism proposed in field of data mining, we devise a new XCS framework by integrating the concept and mechanism of fault tolerance into XCS in order to reduce the number of classification rules and therefore to improve the readability of the generated prediction model. The workflow and operations of the XCS/FT framework are described in detail. A series of $N$-multiplexer experiments, including 6-bit, 11-bit, 20-bit, and 37-bit multiplexers, are conducted to examine whether XCS/FT can accomplish its goal of design. According to the experimental results, XCS/FT can offer the same level of prediction accuracy on the test problems as XCS can, while the prediction model evolved by XCS/FT consists of significantly fewer classification rules.
Characteristic Determination for Solid State Devices with Evolutionary Computation
Abstract: In this paper, we develop a new optimization framework that consists of the extended compact genetic algorithm (ECGA) and split-on-demand (SoD), an adaptive discretization technique, to tackle the characteristic determination problem for solid state devices. Because most decision variables of characteristic determination problems are real numbers due to the modeling of physical phenomena, and ECGA is designed for handling discrete-type problems, a specific mechanism to transform the variable types of the two ends is in order. In the proposed framework, ECGA is used as a back-end optimization engine, and SoD is adopted as the interface between the engine and the problem. Moreover, instead of one mathematical model with various parameters, characteristic determination is in fact a set of problems of which the mathematical formulations may be very different. Therefore, in this study, we employ the proposed framework on three study cases to demonstrate that the technique proposed in the domain of evolutionary computation can provide not only the high quality optimization results but also the flexibility to handle problems of different formulations.
Abstract: In this paper, we develop a new optimization framework that consists of the extended compact genetic algorithm (ECGA) and split-on-demand (SoD), an adaptive discretization technique, to tackle the characteristic determination problem for solid state devices. Because most decision variables of characteristic determination problems are real numbers due to the modeling of physical phenomena, and ECGA is designed for handling discrete-type problems, a specific mechanism to transform the variable types of the two ends is in order. In the proposed framework, ECGA is used as a back-end optimization engine, and SoD is adopted as the interface between the engine and the problem. Moreover, instead of one mathematical model with various parameters, characteristic determination is in fact a set of problems of which the mathematical formulations may be very different. Therefore, in this study, we employ the proposed framework on three study cases to demonstrate that the technique proposed in the domain of evolutionary computation can provide not only the high quality optimization results but also the flexibility to handle problems of different formulations.
Real-Coded ECGA for Economic Dispatch
Abstract: In this paper, we propose a new approach that consists of the extended compact genetic algorithm (ECGA) and split-on-demand (SoD), an adaptive discretization technique, to economic dispatch (ED) problems with nonsmooth cost functions. ECGA is designed for handling problems with decision variables of the discrete type, while the decision variables of ED problems are oftentimes real numbers. Thus, in order to employ ECGA to tackle ED problems, SoD is utilized for discretizing the continuous decision variables and works as the interface between ECGA and the ED problem. Furthermore, ED problems in practice are usually hard for traditional mathematical programming methodologies because of the equality and inequality constraints. Hence, in addition to integrating ECGA and SoD, in this study, we devise a repair operator specifically for making the infeasible solutions to satisfy the equality constraint. To examine the performance and effectiveness, we apply the proposed framework to two different-sized ED problems with nonsmooth cost function considering the valve-point effects. The experimental results are compared to those obtained by various evolutionary algorithms and demonstrate that handling ED problems with the proposed framework is a promising research direction.
Abstract: In this paper, we propose a new approach that consists of the extended compact genetic algorithm (ECGA) and split-on-demand (SoD), an adaptive discretization technique, to economic dispatch (ED) problems with nonsmooth cost functions. ECGA is designed for handling problems with decision variables of the discrete type, while the decision variables of ED problems are oftentimes real numbers. Thus, in order to employ ECGA to tackle ED problems, SoD is utilized for discretizing the continuous decision variables and works as the interface between ECGA and the ED problem. Furthermore, ED problems in practice are usually hard for traditional mathematical programming methodologies because of the equality and inequality constraints. Hence, in addition to integrating ECGA and SoD, in this study, we devise a repair operator specifically for making the infeasible solutions to satisfy the equality constraint. To examine the performance and effectiveness, we apply the proposed framework to two different-sized ED problems with nonsmooth cost function considering the valve-point effects. The experimental results are compared to those obtained by various evolutionary algorithms and demonstrate that handling ED problems with the proposed framework is a promising research direction.
Particle Swarm Guided Evolution Strategy
Abstract: Evolution strategy (ES) and particle swarm optimization (PSO) are two of the most popular research topics for tackling real-parameter optimization problems in evolutionary computation. Both of them have strengths and weaknesses for their different search behaviors and methodologies. In ES, mutation, as the main operator, tries to find good solutions around each individual. While in PSO, particles are moving toward directions determined by certain global information, such as the global best particle. In order to leverage the specialties offered by both sides to our advantage, this paper combines the essential mechanism of ES and the key concept of PSO to develop a new hybrid optimization methodology, called particle swarm guided evolution strategy. We introduce swarm intelligence to the ES mutation framework to create a new mutation operator, called guided mutation, and integrate the guided mutation operator into ES. Numerical experiments are conducted on a set of benchmark functions, and the experimental results indicate that PSGES is a promising optimization methodology as well as an interesting research direction.
Abstract: Evolution strategy (ES) and particle swarm optimization (PSO) are two of the most popular research topics for tackling real-parameter optimization problems in evolutionary computation. Both of them have strengths and weaknesses for their different search behaviors and methodologies. In ES, mutation, as the main operator, tries to find good solutions around each individual. While in PSO, particles are moving toward directions determined by certain global information, such as the global best particle. In order to leverage the specialties offered by both sides to our advantage, this paper combines the essential mechanism of ES and the key concept of PSO to develop a new hybrid optimization methodology, called particle swarm guided evolution strategy. We introduce swarm intelligence to the ES mutation framework to create a new mutation operator, called guided mutation, and integrate the guided mutation operator into ES. Numerical experiments are conducted on a set of benchmark functions, and the experimental results indicate that PSGES is a promising optimization methodology as well as an interesting research direction.
Interactive Music Composition with Evolutionary Computation
Abstract: This article presents an interactive music composition system which utilizes the black-box optimization model of evolutionary computation. The core CFE framework—Composition, Feedback, and Evolution—is presented and described. The music composition system produces short, manageable pieces of music by interacting with users. The essential features of the system include the capability of creating customized pieces of music based on the user preference and the facilities specifically designed for generating a large amount of music. In addition to the system structure and implementation, we also introduce the auxiliary functionalities of the system. Finally, several pieces of music composed by the described system are demonstrated as showcases. This work shows that it is feasible and promising for computers to automatically compose customized or personalized music.
Abstract: This article presents an interactive music composition system which utilizes the black-box optimization model of evolutionary computation. The core CFE framework—Composition, Feedback, and Evolution—is presented and described. The music composition system produces short, manageable pieces of music by interacting with users. The essential features of the system include the capability of creating customized pieces of music based on the user preference and the facilities specifically designed for generating a large amount of music. In addition to the system structure and implementation, we also introduce the auxiliary functionalities of the system. Finally, several pieces of music composed by the described system are demonstrated as showcases. This work shows that it is feasible and promising for computers to automatically compose customized or personalized music.
