动态多目标优化的预测遗传算法

为了在动态环境中很好地跟踪最优解,考虑动态优化问题的特点,提出一种新的多目标预测遗传算法.首先对 Pareto 前沿面进行聚类以求得解集的质心;其次应用该质心与参考点描述 Pareto 前沿面;再次通过预测方法给出预测点集,使得算法在环境变化后能够有指导地增加种群多样性,以便快速跟踪最优解;最后应用标准动态测试问题进行算法测试,仿真分析结果表明所提出算法能适应动态环境,快速跟踪 Pareto 前沿面.     

On improving multiobjective genetic algorithms for design optimization

This paper presents some improvements to Multi-Objective Genetic Algorithms (MOGAs). MOGA modifies certain operators within the GA itself to produce a multiobjective optimization technique. The improvements are made to overcome some of the shortcomings in niche formation, stopping criteria and interaction with a design decision-maker. The technique involves filtering, mating restrictions, the idea of objective constraints, and detecting Pareto solutions in the non-convex region of the Pareto set. A step-by-step procedure for an improved MOGA has been developed and demonstrated via two multiobjective engineering design examples: (i) two-bar truss design, and (ii) vibrating platform design. The two-bar truss example has continuous variables while the vibrating platform example has mixed-discrete (combinatorial) variables. Both examples are solved by MOGA with and without the improvements. It is shown that MOGA with the improvements performs better for both examples in terms of the number of function evaluations.     

Adaptive genetic algorithms guided by decomposition for PCSPs: application to frequency assignment problems

This paper proposes Adaptive Genetic Algorithms Guided by structural knowledges coming from decomposition methods, for solving PCSPs. The family of algorithms called AGAGD_x_y is designed to be doubly generic, meaning that any decomposition method and different heuristics for the genetic operators can be considered. To validate the approach, the decomposition algorithm due to Newman was used and several crossover operators based on structural knowledge such as the cluster, separator and the cut were tested. The experimental results obtained on the most challenging Minimum Interference-FAP problems of CALMA instances are very promising and lead to interesting perspectives to be explored in the future.     

Decomposition methods in multiobjective discrete-time dynamic problems

Decomposition methods for multicriteria dynamic (discrete-time) problems are derived. In these methods, the original problem is reduced to a series of multicriteria subproblems related to individual stages. Hence, the dimensionality of decision variables in each subproblem is smaller than in the original problem. The following decomposition procedures for such problems are developed: (1) a dynamic programming method, (2) a two-point boundary value problem method, (3) multilevel methods, and (4) the formulation of a temporal hierarchy. For completeness, methods for multicriteria dynamic problems are reviewed that, at the outset, transform a problem into a series of single-objective problems. Formulation of the multiobjective problem in the context of a multilayer temporal hierarchy is also presented. The temporal structure motivates problem simplification by decomposing the overall decision-making problem according to relative time scales.     

Adaptive differential dynamic programming for multiobjective optimal control

An efficient numerical solution scheme entitled adaptive differential dynamic programming is developed in this paper for multiobjective optimal control problems with a general separable structure. For a multiobjective control problem with a general separable structure, the “optimal” weighting coefficients for various performance indices are time-varying as the system evolves along any noninferior trajectory. Recognizing this prominent feature in multiobjective control, the proposed adaptive differential dynamic programming methodology combines a search process to identify an optimal time-varying weighting sequence with the solution concept in the conventional differential dynamic programming. Convergence of the proposed adaptive differential dynamic programming methodology is addressed.     

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

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

Adaptive mutation in genetic algorithms

 In Genetic Algorithms mutation probability is usually assigned a constant value, therefore all chromosome have the same likelihood of mutation irrespective of their fitness. It is shown in this paper that making mutation a function of fitness produces a more efficient search. This function is such that the least significant bits are more likely to be mutated in high-fitness chromosomes, thus improving their accuracy, whereas low-fitness chromosomes have an increased probability of mutation, enhancing their role in the search. In this way, the chance of disrupting a high-fitness chromosome is decreased and the exploratory role of low-fitness chromosomes is best exploited. The implications of this new mutation scheme are assessed with the aid of numerical examples.     

Exact algorithms for OWA-optimization in multiobjective spanning tree problems

This paper deals with the multiobjective version of the optimal spanning tree problem. More precisely, we are interested in determining the optimal spanning tree according to an Ordered Weighted Average (OWA) of its objective values. We first show that the problem is weakly NP-hard. We then propose different mixed integer programming formulations, according to different subclasses of OWA functions. Furthermore, we provide various preprocessing procedures, the validity scopes of which depend again on the considered subclass of OWA functions. For designing such procedures, we propose generalized optimality conditions and efficiently computable bounds. These procedures enable to reduce the size of the instances before launching an off-the-shelf software for solving the mixed integer program. Their impact on the resolution time is evaluated on the basis of numerical experiments.     

Quasi-conformal mapping with genetic algorithms applied to coordinate transformations

In this paper, piecewise conformal mapping for the transformation of geodetic coordinates is studied. An algorithm, which is an improved version of a previous algorithm published by Lippus [2004a. On some properties of piecewise conformal mappings. Eesti NSV Teaduste Akademmia Toimetised Füüsika-Matemaakika 53, 92–98; 2004b. Transformation of coordinates using piecewise conformal mapping. Journal of Geodesy 78 (1–2), 40] is presented; the improvement comes from using a genetic algorithm to partition the complex plane into convex polygons, whereas the original one did so manually. As a case study, the method is applied to the transformation of the Spanish datum ED50 and ETRS89, and both its advantages and disadvantages are discussed herein.     

Unsatisfying functions and multiobjective fuzzy satisfaction design using genetic algorithms

This paper describes a new fuzzy satisfaction method using genetic algorithms (GA) for multiobjective problems. First, an unsatisfying function, which has a one-to-one correspondence with the membership function, is introduced for expressing "fuzziness". Next, the multiobjective design problem is transformed into a satisfaction problem of constraints by introducing an aspiration level for each objective. Here, in order to handle the fuzziness involved in aspiration levels and constraints, the unsatisfying function is used, and the problem is formulated as a multiobjective minimization problem of unsatisfaction ratings. Then, a GA is employed to solve the problem, and a new strategy is proposed to obtain a group of Pareto-optimal solutions in which the decision maker (DM) is interested. The DM can then seek a satisfaction solution by modifying parameters interactively according to preferences.     

Target-matching test problem for multiobjective topology optimization using genetic algorithms

This paper describes the multiobjective topology optimization of continuum structures solved as a discrete optimization problem using a multiobjective genetic algorithm (GA) with proficient constraint handling. Crucial to the effectiveness of the methodology is the use of a morphological geometry representation that defines valid structural geometries that are inherently free from checkerboard patterns, disconnected segments, or poor connectivity. A graph- theoretic chromosome encoding, together with compatible reproduction operators, helps facilitate the transmission of topological/shape characteristics across generations in the evolutionary process. A multicriterion target-matching problem developed here is a novel test problem, where a predefined target geometry is the known optimum solution, and the good results obtained in solving this problem provide a convincing demonstration and a quantitative measure of how close to the true optimum the solutions achieved by GA methods can be. The methodology is then used to successfully design a path-generating compliant mechanism by solving a multicriterion structural topology optimization problem.     

Integrated multiobjective optimization and a priori preferences using genetic algorithms

One of the tasks of decision-making support systems is to develop methods that help the designer select a solution among a set of actions, e.g. by constructing a function expressing his/her preferences over a set of potential solutions. In this paper, a new method to solve multiobjective optimization (MOO) problems is developed in which the user’s information about his/her preferences is taken into account within the search process. Preference functions are built that reflect the decision-maker’s (DM) interests and use meaningful parameters for each objective. The preference functions convert these objective preferences into numbers. Next, a single objective is automatically built and no weight selection is performed. Problems found due to the multimodality nature of a generated single cost index are managed with Genetic Algorithms (GAs). Three examples are given to illustrate the effectiveness of the method.     

Swarm algorithms with chaotic jumps applied to noisy optimization problems

In this paper, we investigate the use of some well-known versions of particle swarm optimization (PSO): the canonical PSO with gbest model and lbest model with ring topology, the Bare bones PSO (BBPSO) and the fully informed particle swarm (FIPS) on noisy optimization problems. As far as we know, some of these versions like BBPSO and FIPS had not been previously applied to noisy functions yet. A hybrid approach which consists of the swarm algorithms combined with a jump strategy has been developed for static environments. Here, we focus on investigating the introduction of the jump strategy to the swarm algorithms now applied to noisy optimization problems. The hybrid approach is compared experimentally on different noisy benchmark functions. Simulation results indicate that the addition of the jump strategy to the swarm algorithms is beneficial in terms of robustness.     

Evolutionary algorithms with dynamic population size and localexploration for multiobjective optimization

Evolutionary algorithms have been recognized to be well suited for multiobjective optimization. These methods, however, need to "guess" for an optimal constant population size in order to discover the usually sophisticated tradeoff surface. This paper addresses the issue by presenting a novel incrementing multiobjective evolutionary algorithm (IMOEA) with dynamic population size that is computed adaptively according to the online discovered tradeoff surface and its desired population distribution density. It incorporates the method of fuzzy boundary local perturbation with interactive local fine tuning for broader neighborhood exploration. This achieves better convergence as well as discovering any gaps or missing tradeoff regions at each generation. Other advanced features include a proposed preserved strategy to ensure better stability and diversity of the Pareto front and a convergence representation based on the concept of online population domination to provide useful information. Extensive simulations are performed on two benchmark and one practical engineering design problems     

Scalability problems of simple genetic algorithms

Scalable evolutionary computation has become an intensively studied research topic in recent years. The issue of scalability is predominant in any field of algorithmic design, but it became particularly relevant for the design of competent genetic algorithms once the scalability problems of simple genetic algorithms were understood. Here we present some of the work that has aided in getting a clear insight in the scalability problems of simple genetic algorithms. Particularly, we discuss the important issue of building block mixing. We show how the need for mixing places a boundary in the GA parameter space that, together with the boundary from the schema theorem, delimits the region where the GA converges reliably to the optimum in problems of bounded difficulty. This region shrinks rapidly with increasing problem size unless the building blocks are tightly linked in the problem coding structure. In addition, we look at how straightforward extensions of the simple genetic algorithm-namely elitism, niching, and restricted mating are not significantly improving the scalability problems.     

Two-dimensional packing problems using genetic algorithms

This paper presents a technique for applying genetic algorithms for the two-dimensional packing problem. The approach is applicable to not only convex shaped objects, but can also accommodate any type of concave and complex shaped objects including objects with holes. In this approach, a new concept of a two-dimensional genetic chromosome is introduced. The total layout space is divided into a finite number of cells for mapping it into this 2D genetic algorithm chromosome. The mutation and crossover operators have been modified and are applied in conjunction with connectivity analysis for the objects to reduce the creation of faulty generations. A new feature has been added to the Genetic Algorithm (GA) in the form of a new operator called compaction. Several examples of GA-based layout are presented.     

Adaptive directed mutation for real-coded genetic algorithms

Adaptive directed mutation (ADM) operator, a novel, simple, and efficient real-coded genetic algorithm (RCGA) is proposed and then employed to solve complex function optimization problems. The suggested ADM operator enhances the abilities of GAs in searching global optima as well as in speeding convergence by integrating the local directional search strategy and the adaptive random search strategies. Using 41 benchmark global optimization test functions, the performance of the new algorithm is compared with five conventional mutation operators and then with six genetic algorithms (GAs) reported in literature. Results indicate that the proposed ADM-RCGA is fast, accurate, and reliable, and outperforms all the other GAs considered in the present study.     

Adaptive parallel algorithms for integral knapsack problems

In this paper, the design of a time-efficient and processor-efficient parallel algorithm for the integral knapsack problem is considered. A parallel integral knapsack algorithm is presented, which is adaptive to all parameters, especially to the maximum size of items. The parallel complexity of another important packing problem, the integral exactly-packing problem, is also considered. An optimal O(log n log m) time, parallel integral exactly-packing algorithm is given. Since the partition problem has a constant time, constant processor reduction to the exactly-packing problem, our parallel integral exactly-packing algorithm can be used for job scheduling, task partition, and many other important practical problems. Moreover, the methods and techniques used in this paper can be used for developing processor-efficient and time-efficient parallel algorithms for many other problems. Using the new parallel integral knapsack algorithm, the previously known parallel approximation schemes for the 0–1 knapsack problem and the binpacking problem, by E. W. Mayr and P. S. Gopalkrishnan, are improved upon significantly.     

Robust confidence intervals applied to crossover operator for real-coded genetic algorithms

In this work we propose a new approach to crossover operators for real-coded genetic algorithms based on robust confidence intervals. These confidence intervals are an alternative to standard confidence intervals. In this paper, they are used for localising the search regions where the best individuals are placed. Robust confidence intervals use robust localization and dispersion estimators that are highly recommendable when the distribution of the random variables is not known or is distorted. Both situations are likely when we are dealing with the best individuals of the population, especially if the problem under study is multimodal. The performance of the crossovers based on robust intervals is evaluated using a well characterised set of optimisation problems. We have chosen problems with different features of modality, separability, regularity, and correlation among their variables. The results show that the performance of the crossovers based on robust confidence intervals is less dependent on the problem than the performance of the crossovers based on Gaussian confidence intervals. We have also made comparisons between several standard crossovers that show very interesting results, which support the idea underlying the defined operators.