2008
DocumentsDate added
Enhancing MOEA/D with Guided Mutation and Priority Update for Multi-objective Optimization
Abstract: Multi-objective optimization is an essential and challenging topic in the domains of engineering and computation because real-world problems usually include several conflicting objectives. Current trends in the research of solving multi-objective problems (MOPs) require that the adopted optimization method provides as approximation of the Pareto set such that the user can understand the tradeoff between objectives and therefore make the final decision. Recently, an efficient framework, called MOEA/D, combining decomposition techniques in mathematics and optimization methods in evolutionary computation was proposed. MOEA/D decomposes a MOP to a set of single-objective problems (SOPs) with neighborhood relationship and approximates the Pareto set by solving these SOPs. In this paper, we attempt to enhance MOEA/D by proposing two mechanisms. To fully employ the information obtained from neighbors, we introduce a guided mutation operator to replace the differential evolution operator. Moreover, a update mechanism utilizing a priority queue is proposed for performance improvement when the SOPs obtained by decomposition are not uniformly distributed on the Pareto font. Different combinations of these approaches are compared based on the test problem instances proposed for the CEC 2009 competition. The set of problem instances include unconstrained and constrained MOPs with variable linkages. Experimental results are presented in the paper, and observations and discussion are also provided.
Abstract: Multi-objective optimization is an essential and challenging topic in the domains of engineering and computation because real-world problems usually include several conflicting objectives. Current trends in the research of solving multi-objective problems (MOPs) require that the adopted optimization method provides as approximation of the Pareto set such that the user can understand the tradeoff between objectives and therefore make the final decision. Recently, an efficient framework, called MOEA/D, combining decomposition techniques in mathematics and optimization methods in evolutionary computation was proposed. MOEA/D decomposes a MOP to a set of single-objective problems (SOPs) with neighborhood relationship and approximates the Pareto set by solving these SOPs. In this paper, we attempt to enhance MOEA/D by proposing two mechanisms. To fully employ the information obtained from neighbors, we introduce a guided mutation operator to replace the differential evolution operator. Moreover, a update mechanism utilizing a priority queue is proposed for performance improvement when the SOPs obtained by decomposition are not uniformly distributed on the Pareto font. Different combinations of these approaches are compared based on the test problem instances proposed for the CEC 2009 competition. The set of problem instances include unconstrained and constrained MOPs with variable linkages. Experimental results are presented in the paper, and observations and discussion are also provided.
Analysis on the Facet of Particle Interaction in Particle Swarm Optimization
Abstract: In this paper, we analyze the behavior of particle swarm optimization (PSO) on the facet of particle interaction. We firstly propose a statistical interpretation of PSO in order to capture the stochastic behavior of the entire swarm. Based on the statistical interpretation, we investigate the effect of particle interaction by focusing on the social-only model and derive the upper and lower bounds of the expected particle norm. Accordingly, the lower and upper bounds of the expected progress rate on the sphere function are also obtained. Furthermore, the sufficient and necessary condition for the swarm to converge is derived to demonstrate the PSO convergence caused by the effect of particle interaction.
Abstract: In this paper, we analyze the behavior of particle swarm optimization (PSO) on the facet of particle interaction. We firstly propose a statistical interpretation of PSO in order to capture the stochastic behavior of the entire swarm. Based on the statistical interpretation, we investigate the effect of particle interaction by focusing on the social-only model and derive the upper and lower bounds of the expected particle norm. Accordingly, the lower and upper bounds of the expected progress rate on the sphere function are also obtained. Furthermore, the sufficient and necessary condition for the swarm to converge is derived to demonstrate the PSO convergence caused by the effect of particle interaction.
Sensibility of Linkage Information and Effectiveness of Estimated Distributions
Abstract: Probabilistic model building performed by estimation of distribution algorithms (EDAs) enables these methods to use advanced techniques of statistics and machine learning for automatic discovery of problem structures. However, in some situations, complete and accurate identification of all problem structures by probabilistic modeling is not possible because of certain inherent properties of the given problem. In this work, we illustrate one possible cause of such situations with problems composed of structures of unequal fitness contributions. Based on the illustrative example, a notion is introduced that the estimated probabilistic models should be inspected to reveal the effective search directions, and we propose a general approach which utilizes a reserved set of solutions to examine the built model for likely inaccurate fragments. Furthermore, the proposed approach is implemented on the extended compact genetic algorithm (ECGA) and experimented on several sets of additively separable problems with different scaling setups. The results indicate that the proposed method can significantly assist ECGA to handle problems comprising structures of disparate fitness contributions and therefore may potentially help EDAs in general to overcome those situations in which the entire structure of the problem cannot be recognized properly due to the temporal delay of emergence of some promising partial solutions.
Abstract: Probabilistic model building performed by estimation of distribution algorithms (EDAs) enables these methods to use advanced techniques of statistics and machine learning for automatic discovery of problem structures. However, in some situations, complete and accurate identification of all problem structures by probabilistic modeling is not possible because of certain inherent properties of the given problem. In this work, we illustrate one possible cause of such situations with problems composed of structures of unequal fitness contributions. Based on the illustrative example, a notion is introduced that the estimated probabilistic models should be inspected to reveal the effective search directions, and we propose a general approach which utilizes a reserved set of solutions to examine the built model for likely inaccurate fragments. Furthermore, the proposed approach is implemented on the extended compact genetic algorithm (ECGA) and experimented on several sets of additively separable problems with different scaling setups. The results indicate that the proposed method can significantly assist ECGA to handle problems comprising structures of disparate fitness contributions and therefore may potentially help EDAs in general to overcome those situations in which the entire structure of the problem cannot be recognized properly due to the temporal delay of emergence of some promising partial solutions.
Constructing the Rectilinear Steiner Tree in 3D ICs with Integer Extended Compact Genetic Algorithm
Abstract: Rectilinear Steiner Tree (RST) has wide researches and applications in Very Large Scale Integrated (VLSI) circuit design. Generally, the RST is used to pre-estimate the circuit wire length before the VLSI routing stage, which is applied to interconnect different circuit components. Unfortunately, how to construct a RSMT is a NP-Complete problem. To make things worse, with the developing technology of Three-Dimensional Integrated Circuits (3D ICs), the complexity of the RST construction in 3D space is much higher than traditional RST construction, which only focuses on the two dimensional plane. Obviously, it is quite urgent to develop an effective way to construct a 3D RST.
Therefore, the author presents the use of Integer Extended Compact Genetic Algorithm (iECGA), which can effectively solve highly complicated problems, to construct a 3D RST for 3D ICs. The experimental results show that the iECGA can effectively construct 3D RSTs in a reasonable time and outperforms than traditional Genetic Algorithm (GA). The author believes that the proposed strategy may be suitable for larger problems and can be extended to the problem of obstacle-aware 3D RST construction with in the future.
Abstract: Rectilinear Steiner Tree (RST) has wide researches and applications in Very Large Scale Integrated (VLSI) circuit design. Generally, the RST is used to pre-estimate the circuit wire length before the VLSI routing stage, which is applied to interconnect different circuit components. Unfortunately, how to construct a RSMT is a NP-Complete problem. To make things worse, with the developing technology of Three-Dimensional Integrated Circuits (3D ICs), the complexity of the RST construction in 3D space is much higher than traditional RST construction, which only focuses on the two dimensional plane. Obviously, it is quite urgent to develop an effective way to construct a 3D RST.
Therefore, the author presents the use of Integer Extended Compact Genetic Algorithm (iECGA), which can effectively solve highly complicated problems, to construct a 3D RST for 3D ICs. The experimental results show that the iECGA can effectively construct 3D RSTs in a reasonable time and outperforms than traditional Genetic Algorithm (GA). The author believes that the proposed strategy may be suitable for larger problems and can be extended to the problem of obstacle-aware 3D RST construction with in the future.
Sensible Linkage, Effective Distributions, and Model Pruning in Estimation of Distribution Algorithms
Abstract: Estimation of distribution algorithms (EDAs) are a class of evolutionary algorithms that replace the traditional variation operators, such as mutation and crossover, by building a probabilistic model on promising solutions and sampling the built model to generate new candidate solutions. Using probabilistic models for exploration enables these methods to use advanced techniques of statistics and machine learning for automatic discovery of problem structures. However, in some situations, complete and accurate identification of all problem structures by probabilistic modeling is not possible because of certain inherent properties of the given problem. In this work, we illustrate one possible cause of such situations with problems composed of structures of unequal fitness contributions. Based on the illustrative example, a notion is introduced that the estimated probabilistic models should be inspected to reveal the effective search directions, and we propose a general approach which utilizes a reserved set of solutions to examine the built model for likely inaccurate fragments. Furthermore, the proposed approach is implemented in the extended compact genetic algorithm (ECGA) and experimented on several sets of problems with different scaling difficulties. The results indicate that the proposed method can significantly assist ECGA to handle problems comprising structures of disparate fitness contributions and therefore may potentially help EDAs in general to overcome those situations in which the entire structure of the problem cannot be recognized properly due to the temporal delay of emergence of some promising partial solutions.
Abstract: Estimation of distribution algorithms (EDAs) are a class of evolutionary algorithms that replace the traditional variation operators, such as mutation and crossover, by building a probabilistic model on promising solutions and sampling the built model to generate new candidate solutions. Using probabilistic models for exploration enables these methods to use advanced techniques of statistics and machine learning for automatic discovery of problem structures. However, in some situations, complete and accurate identification of all problem structures by probabilistic modeling is not possible because of certain inherent properties of the given problem. In this work, we illustrate one possible cause of such situations with problems composed of structures of unequal fitness contributions. Based on the illustrative example, a notion is introduced that the estimated probabilistic models should be inspected to reveal the effective search directions, and we propose a general approach which utilizes a reserved set of solutions to examine the built model for likely inaccurate fragments. Furthermore, the proposed approach is implemented in the extended compact genetic algorithm (ECGA) and experimented on several sets of problems with different scaling difficulties. The results indicate that the proposed method can significantly assist ECGA to handle problems comprising structures of disparate fitness contributions and therefore may potentially help EDAs in general to overcome those situations in which the entire structure of the problem cannot be recognized properly due to the temporal delay of emergence of some promising partial solutions.
Recognizing Problem Decomposition with Inductive Linkage Identification: Population Requirement vs. Subproblem Complexity
Abstract: In genetic and evolutionary algorithms, the goal of linkage identification is to detect strong relationships among the decision variables of the objective function. If such relations can be identified, the crossover operator can accordingly mix and recombine the identified sub-solutions without destroying them. In our previous study, we have proposed a linkage identification technique, called inductive linkage identification (ILI), which integrates the mechanisms of perturbation and decision tree induction. With the proposed technique, linkage information of the objective function can be acquired via constructing an ID3 decision tree to model the mapping from solution strings to their corresponding fitness changes caused by perturbations and then inspecting the constructed decision tree for the decision variables exhibiting strong interdependencies with one another. In this study, we observe the behavior of ILI on decomposable problems of different subproblem complexities and make an attempt to understand the population requirement of the proposed linkage identification technique. The experimental results demonstrate that the population size required by ILI to correctly learn linkage grows sub-linearly with the problem size while grows exponentially with the complexity of constituting subproblems.
Abstract: In genetic and evolutionary algorithms, the goal of linkage identification is to detect strong relationships among the decision variables of the objective function. If such relations can be identified, the crossover operator can accordingly mix and recombine the identified sub-solutions without destroying them. In our previous study, we have proposed a linkage identification technique, called inductive linkage identification (ILI), which integrates the mechanisms of perturbation and decision tree induction. With the proposed technique, linkage information of the objective function can be acquired via constructing an ID3 decision tree to model the mapping from solution strings to their corresponding fitness changes caused by perturbations and then inspecting the constructed decision tree for the decision variables exhibiting strong interdependencies with one another. In this study, we observe the behavior of ILI on decomposable problems of different subproblem complexities and make an attempt to understand the population requirement of the proposed linkage identification technique. The experimental results demonstrate that the population size required by ILI to correctly learn linkage grows sub-linearly with the problem size while grows exponentially with the complexity of constituting subproblems.
Adaptive Discretization on Multidimensional Continuous Search Spaces
Abstract: This paper extends an adaptive discretization method, Split-on-Demand (SoD), to be capable of handling multidimensional continuous search spaces. The proposed extension is called multidimensional Split-on-Demand (mSoD), which considers multiple dimensions of the search space as a whole instead of independently discretizing each dimension as SoD does. In this study, we integrate mSoD and SoD with the extended compact genetic algorithm (ECGA) to numerically examine the effectiveness and performance of mSoD and SoD on the problems with and without linkage among dimensions of the search space. The experimental results indicate that mSoD outperforms SoD on both of the test problems and that mSoD can offer better scalability, stability, and accuracy. The behavior of mSoD is discussed, followed by the potential future work.
Abstract: This paper extends an adaptive discretization method, Split-on-Demand (SoD), to be capable of handling multidimensional continuous search spaces. The proposed extension is called multidimensional Split-on-Demand (mSoD), which considers multiple dimensions of the search space as a whole instead of independently discretizing each dimension as SoD does. In this study, we integrate mSoD and SoD with the extended compact genetic algorithm (ECGA) to numerically examine the effectiveness and performance of mSoD and SoD on the problems with and without linkage among dimensions of the search space. The experimental results indicate that mSoD outperforms SoD on both of the test problems and that mSoD can offer better scalability, stability, and accuracy. The behavior of mSoD is discussed, followed by the potential future work.
On the Effectiveness of Distributions Estimated by Probabilistic Model Building
Abstract: Estimation of distribution algorithms (EDAs) are a class of evolutionary algorithms that capture the likely structure of promising solutions by explicitly building a probabilistic model and utilize the built model to guide the further search. It is presumed that EDAs can detect the structure of the problem by recognizing the regularities of the promising solutions. However, in certain situations, EDAs are unable to discover the entire structure of the problem because the set of promising solutions on which the model is built contains insufficient information for some parts of the problem and renders EDAs incapable of accurate model building. In this work, we firstly propose a general concept that the effectiveness of probabilistic models should be evaluated and verified in EDAs. Based on the concept, we design a practical approach which utilizes a reserved set of individuals to inspect the built model for the fragments that may be inconsistent with the actual problem structure. Furthermore, we provide an implementation of the designed approach on the extended compact genetic algorithm (ECGA) and conduct numerical experiments. The results indicate that the proposed concept can significantly assist ECGA to handle problems of different scalings.
Abstract: Estimation of distribution algorithms (EDAs) are a class of evolutionary algorithms that capture the likely structure of promising solutions by explicitly building a probabilistic model and utilize the built model to guide the further search. It is presumed that EDAs can detect the structure of the problem by recognizing the regularities of the promising solutions. However, in certain situations, EDAs are unable to discover the entire structure of the problem because the set of promising solutions on which the model is built contains insufficient information for some parts of the problem and renders EDAs incapable of accurate model building. In this work, we firstly propose a general concept that the effectiveness of probabilistic models should be evaluated and verified in EDAs. Based on the concept, we design a practical approach which utilizes a reserved set of individuals to inspect the built model for the fragments that may be inconsistent with the actual problem structure. Furthermore, we provide an implementation of the designed approach on the extended compact genetic algorithm (ECGA) and conduct numerical experiments. The results indicate that the proposed concept can significantly assist ECGA to handle problems of different scalings.
