MOEA/D with uniform decomposition measurement for many-objective problems

Many-objective problems (MAPs) have put forward a number of challenges to classical Pareto-dominance based multi-objective evolutionary algorithms (MOEAs) for the past few years. Recently, researchers have suggested that MOEA/D (multi-objective evolutionary algorithm based on decomposition) can work for MAPs. However, there exist two difficulties in applying MOEA/D to solve MAPs directly. One is that the number of constructed weight vectors is not arbitrary and the weight vectors are mainly distributed on the boundary of weight space for MAPs. The other is that the relationship between the optimal solution of subproblem and its weight vector is nonlinear for the Tchebycheff decomposition approach used by MOEA/D. To deal with these two difficulties, we propose an improved MOEA/D with uniform decomposition measurement and the modified Tchebycheff decomposition approach (MOEA/D-UDM) in this paper. Firstly, a novel weight vectors initialization method based on the uniform decomposition measurement is introduced to obtain uniform weight vectors in any amount, which is one of great merits to use our proposed algorithm. The modified Tchebycheff decomposition approach, instead of the Tchebycheff decomposition approach, is used in MOEA/D-UDM to alleviate the inconsistency between the weight vector of subproblem and the direction of its optimal solution in the Tchebycheff decomposition approach. The proposed MOEA/D-UDM is compared with two state-of-the-art MOEAs, namely MOEA/D and UMOEA/D on a number of MAPs. Experimental results suggest that the proposed MOEA/D-UDM outperforms or performs similarly to the other compared algorithms in terms of hypervolume and inverted generational distance metrics on different types of problems. The effects of uniform weight vector initializing method and the modified Tchebycheff decomposition are also studied separately.     

求解背包问题的贪心遗传算法及其应用

分析了文献[2]中求解背包问题(KP)的混合遗传算法(HGA)所采用的贪心变换方法缺陷;重新定义了贪心变换的概念,并给出了一种新的且更高效的贪心变换方法,将此方法与遗传算法相结合得到一种新的混合遗传算法,称之贪心遗传算法(简记GGA).利用GGA得出了文献[2,4]中一个著名KP问题实例的目前最好结果;同时,对于文献[7]中的KP问题实例和一个随机生成的KP问题实例,将GGA算法与求解KP问题的最有效算法HGA算法进行对比计算,结果表明GGA算法远远优于HGA算法.     

An improved firefly algorithm for solving dynamic multidimensional knapsack problems

There is a wide range of publications reported in the literature, considering optimization problems where the entire problem related data remains stationary throughout optimization. However, most of the real-life problems have indeed a dynamic nature arising from the uncertainty of future events. Optimization in dynamic environments is a relatively new and hot research area and has attracted notable attention of the researchers in the past decade. Firefly Algorithm (FA), Genetic Algorithm (GA) and Differential Evolution (DE) have been widely used for static optimization problems, but the applications of those algorithms in dynamic environments are relatively lacking. In the present study, an effective FA introducing diversity with partial random restarts and with an adaptive move procedure is developed and proposed for solving dynamic multidimensional knapsack problems. To the best of our knowledge this paper constitutes the first study on the performance of FA on a dynamic combinatorial problem. In order to evaluate the performance of the proposed algorithm the same problem is also modeled and solved by GA, DE and original FA. Based on the computational results and convergence capabilities we concluded that improved FA is a very powerful algorithm for solving the multidimensional knapsack problems for both static and dynamic environments.     

利用遗传算法求解静态与动态背包问题的研究

为了有效处理遗传算法在求解静态与动态背包问题时产生非正常编码个体的问题,在分析已有处理方法不足的基础上,基于贪心策略提出了一种贪心修正算子与贪心优化算子相结合的新方法,并将该方法与遗传算法相融合给出了求解静态与动态背包问题的有效算法.仿真计算结果表明,在求解静态与动态背包问题时,利用所提出的新方法不仅可以解决非正常编码个体的问题,而且还能够显著提高个体所对应的可行解的质量,极大地改善了遗传算法的求解效果.     

Chain-reaction solution update in MOEA/D and its effects on multi- and many-objective optimization

MOEA/D is one of the promising evolutionary algorithms for multi- and many-objective optimization. To improve the search performance of MOEA/D, this work focuses on the solution update method in the conventional MOEA/D and proposes its alternative, the chain-reaction solution update. The proposed method is designed to maintain and improve the variable (genetic) diversity in the population by avoiding duplication of solutions in the population. In addition, the proposed method determines the order of existing solutions to be updated depending on the location of each offspring in the objective space. Furthermore, when an existing solution in the population is replaced by a new offspring, the proposed method tries to reutilize the existing solution for other search directions by recursively performing the proposed chain-reaction update procedure. This work uses discrete knapsack and continuous WFG4 problems with 2–8 objectives. Experimental results using knapsack problems show the proposed chain-reaction update contributes to improving the search performance of MOEA/D by enhancing the diversity of solutions in the objective space. In addition, experimental results using WFG4 problems show that the search performance of MOEA/D can be further improved using the proposed method.     

遗传交叉和变异对种群多样性的影响

首先,定义了群体的算术交叉扩展子空间、寻优空间和基因位直方图概念,并分析了交叉在解空间的扩展性．然后,证明了在二进制编码中,交叉不能改变基因层次上的多样性;而在实数编码中,在一定条件下,算术交叉可改变基因层次上的多样性,但以扩大寻优空间、产生无用解为代价．随后,证明了交叉可改变个体层次上的多样性,而变异可改变以上两个层次上的多样性．最后,分析了所得结论对遗传算法的改进和应用具有的指导意义,并通过仿真加以验证．     

Effects of nongeometric binary crossover on multiobjective 0/1 knapsack problems

Standard binary crossover operators (e.g., one-point, two-point, and uniform) tend to decrease the diversity of solutions while they improve the convergence to the Pareto front. This is because standard binary crossover operators, which are called geometric crossovers, always generate an offspring in the line segment between its parents under the Hamming distance in the genotype space. In our former study, we have already proposed a nongeometric binary crossover operator to generate an offspring outside the line segment between its parents. In this article, we examine the effect of our crossover operator on the performance of evolutionary multiobjective optimization (EMO) algorithms through computational experiments on various multiobjective knapsack problems. Experimental results show that our crossover operator improves the search ability of EMO algorithms for a wide range of test problems. This work was presented in part at the 13th International Symposium on Artificial Life and Robotics, Oita, Japan, January 31–February 2, 2008     

An effective hybrid harmony search-based algorithm for solving multidimensional knapsack problems

This study presents an effective hybrid algorithm based on harmony search (HHS) for solving multidimensional knapsack problems (MKPs). In the proposed HHS algorithm, a novel harmony improvisation mechanism is developed with the modified memory consideration rule and the global-best pitch adjustment scheme to enhance the global exploration. A parallel updating strategy is employed to enrich the harmony memory diversity. To well balance the exploration and the exploitation, the fruit fly optimization (FFO) scheme is integrated as a local search strategy. For solving MKPs, binary strings are used to represent solutions and two repair operators are applied to guarantee the feasibility of the solutions. The HHS is calibrated based on the Taguchi method of design-of-experiment. Extensive numerical investigations based on well-known benchmark instances are conducted. The comparative evaluations indicate the HHS is much more effective than the existing HS and FFO variants in solving MKPs.     

Measuring the convergence and diversity of CDAS Multi-Objective Particle Swarm Optimization Algorithms: A study of many-objective problems

The interest for many-objective optimization has grown due to the limitations of Pareto dominance based Multi-Objective Evolutionary Algorithms when dealing with problems of a high number of objectives. Recently, some many-objective techniques have been proposed to avoid the deterioration of these algorithms' search ability. At the same time, the interest in the use of Particle Swarm Optimization (PSO) algorithms in multi-objective problems also grew. The PSO has been found to be very efficient to solve multi-objective problems (MOPs) and several Multi-Objective Particle Swarm Optimization (MOPSO) algorithms have been proposed. This work presents a study of the behavior of MOPSO algorithms in many-objective problems. The many-objective technique named control of dominance area of solutions (CDAS) is used on two Multi-Objective Particle Swarm Optimization algorithms. An empirical analysis is performed to identify the influence of the CDAS technique on the convergence and diversity of MOPSO algorithms using three different many-objective problems. The experimental results are compared applying quality indicators and statistical tests.     

Genetic programming with one-point crossover and subtree mutation for effective problem solving and bloat control

Genetic programming (GP) is one of the most widely used paradigms of evolutionary computation due to its ability to automatically synthesize computer programs and mathematical expressions. However, because GP uses a variable length representation, the individuals within the evolving population tend to grow rapidly without a corresponding return in fitness improvement, a phenomenon known as bloat. In this paper, we present a simple bloat control strategy for standard tree-based GP that achieves a one order of magnitude reduction in bloat when compared with standard GP on benchmark tests, and practically eliminates bloat on two real-world problems. Our proposal is to substitute standard subtree crossover with the one-point crossover (OPX) developed by Poli and Langdon (Second online world conference on soft computing in engineering design and manufacturing, Springer, Berlin (1997)), while maintaining all other GP aspects standard, particularly subtree mutation. OPX was proposed for theoretical purposes related to GP schema theorems, however since it curtails exploration during the search it has never achieved widespread use. In our results, on the other hand, we are able to show that OPX can indeed perform an effective search if it is coupled with subtree mutation, thus combining the bloat control capabilities of OPX with the exploration provided by standard mutation.     

Interactive balance space approach for solving multi-level multi-objective programming problems

This paper studies a multi-level multi-objective decision-making (ML-MODM) problems with linear or non-linear constraints. The objective functions at each level are non-linear functions, which are to be maximized or minimized.This paper presents a three-level multi-objective decision-making (TL-MODM) model and an interactive algorithm for solving such a model. The algorithm simplifies three-level multi-objective decision-making problems by transforming them into separate multi-objective decision making problems at each level, thereby avoiding the difficulty associated with non-convex mathematical programming. Our algorithm is an extension of the work of Shi and Xia [X. Shi, H. Xia, Interactive bi-level multi-objective decision making, Journal of the Operational Research Society 48 (1997) 943-949], which dealt with interactive bi-level multi-objective decision-making problems, with some modifications in assigning satisfactoriness to each objective function in all the levels of the TL-MODM problem. Also, we solve each separate multi-objective decision making problem of the TL-MODM problem by the balance space approach.A new formula is introduced to interconnect the satisfactoriness and the proportions of deviation needed to reflect the relative importance of each objective function. Thus, we have the proportions of deviation including satisfactoriness.In addition, we present new definitions for the satisfactoriness and the preferred solution in view of singular-level multi-objective decision making problems that corresponds to the η-optimal solution of the balance space approach. Also, new definitions for the feasible solution and the preferred solution (η-optimal point) of the TL-MODM problem are presented. An illustrative numerical example is given to demonstrate the algorithm.     

Using objective reduction and interactive procedure to handle many-objective optimization problems

A number of practical optimization problems are posed as many-objective (more than three objectives) problems. Most of the existing evolutionary multi-objective optimization algorithms, which target the entire Pareto-front are not equipped to handle many-objective problems. Though there have been copious efforts to overcome the challenges posed by such problems, there does not exist a generic procedure to effectively handle them. This paper presents a simplify and solve framework for handling many-objective optimization problems. In that, a given problem is simplified by identification and elimination of the redundant objectives, before interactively engaging the decision maker to converge to the most preferred solution on the Pareto-optimal front. The merit of performing objective reduction before interacting with the decision maker is two fold. Firstly, the revelation that certain objectives are redundant, significantly reduces the complexity of the optimization problem, implying lower computational cost and higher search efficiency. Secondly, it is well known that human beings are not efficient in handling several factors (objectives in the current context) at a time. Hence, simplifying the problem a priori addresses the fundamental issue of cognitive overload for the decision maker, which may help avoid inconsistent preferences during the different stages of interactive engagement. The implementation of the proposed framework is first demonstrated on a three-objective problem, followed by its application on two real-world engineering problems.     

Group properties of crossover and mutation

It is supposed that the finite search space omega has certain symmetries that can be described in terms of a group of permutations acting upon it. If crossover and mutation respect these symmetries, then these operators can be described in terms of a mixing matrix and a group of permutation matrices. Conditions under which certain subsets of omega are invariant under crossover are investigated, leading to a generalization of the term schema. Finally, it is sometimes possible for the group acting on omega to induce a group structure on omega itself.     

求解多目标优化问题的分级变异量子进化算法

分析量子进化算法和免疫算子的特点,提出一种分级变异的量子进化算法,用于求解多目标优化问题,算法主要基于两个策略:首先,利用快速非受控排序和密度距离计算种群抗原-抗体的亲和度;然后,基于亲和度排序将个体进行分级,最优分级中的个体作为算法中的最优个体,大部分实施量子旋转更新和免疫操作,而剩余分级中的个体实施免疫交叉操作以获得新的个体补充种群,求解多目标0/1背包问题的实验结果表明了该算法的有效性.     

Hard multidimensional multiple choice knapsack problems, an empirical study

Recent advances in algorithms for the multidimensional multiple choice knapsack problems have enabled us to solve rather large problem instances. However, these algorithms are evaluated with very limited benchmark instances. In this study, we propose new methods to systematically generate comprehensive benchmark instances. Some instances with special correlation properties between parameters are found to be several orders of magnitude harder than those currently used for benchmarking the algorithms. Experiments on an existing exact algorithm and two generic solvers show that instances whose weights are uncorrelated with the profits are easier compared with weakly or strongly correlated cases. Instances with classes containing similar set of profits for items and with weights strongly correlated to the profits are the hardest among all instance groups investigated. These hard instances deserve further study and understanding their properties may shed light to better algorithms.     

Handling many-objective optimisation problems with R2 indicator and decomposition-based particle swarm optimiser

An R2 indicator-based multi-objective particle swarm optimiser (R2-MOPSO) can obtain well-convergence and well-distributed solutions while solving two and three objectives optimisation problems. However, R2-MOPSO faces difficulty to tackle many-objective optimisation problems because balancing convergence and diversity is a key issue in high-dimensional objective space. In order to address this issue, this paper proposes a novel algorithm, named R2-MaPSO, which combines the R2 indicator and decomposition-based archiving pruning strategy into particle swarm optimiser for many-objective optimisation problems. The innovations of the proposed algorithm mainly contains three crucial factors: (1) A bi-level archiving maintenance approach based on the R2 indicator and objective space decomposition strategy is designed to balance convergence and diversity. (2) The global-best leader selection is based on the R2 indicator and the personal-best leader selection is based on the Pareto dominance. Meanwhile, the objective space decomposition leader selection adopts the feedback information from the bi-level archive. (3) A new velocity updated method is modified to enhance the exploration and exploitation ability. In addition, an elitist learning strategy and a smart Gaussian learning strategy are embedded into R2-MaPSO to help the algorithm jump out of the local optimal front. The performance of the proposed algorithm is validated and compared with some algorithms on a number of unconstraint benchmark problems, i.e. DTLZ1-DTLZ4, WFG test suites from 3 to 15 objectives. Experimental results have demonstrated a better performance of the proposed algorithm compared with several multi-objective particle swarm optimisers and multi-objective evolutionary algorithms for many-objective optimisation problems.     

Adaptive crossover,mutation and selection using fuzzy system for genetic algorithms

Genetic algorithms use a tournament selection or a roulette selection to choice better population. But these selections couldn’t use heuristic information for specific problem. Fuzzy selection system by heuristic rule base help to find optimal solution efficiently. And adaptive crossover and mutation probabilistic rate is faster than using fixed value. In this paper, we want fuzzy selection system for genetic algorithms and adaptive crossover and mutation rate fuzzy system. This work was presented in part and awarded as Young Author Award at the 13th International Symposium on Artificial Life and Robotics, Oita, Japan, January 31–February 2, 2008     

Problems, knowledge, solutions: solving complex problems

This article examines complex problem solving using drugs and cyber crime as examples.     

An enhanced genetic algorithm for constrained knapsack problems in dynamic environments

Natural Computing - In this paper, an enhanced genetic algorithm (ERGA), based on memory updating and environment reaction schemes, has been proposed to solve constrained knapsack problems in...