Multiobjective optimization and multiple constraint handling withevolutionary algorithms. II. Application example

For part I see ibid., 26-37. The evolutionary approach to multiple function optimization formulated in the first part of the paper is applied to the optimization of the low-pressure spool speed governor of a Pegasus gas turbine engine. This study illustrates how a technique such as the multiobjective genetic algorithm can be applied, and exemplifies how design requirements can be refined as the algorithm runs. Several objective functions and associated goals express design concerns in direct form, i.e., as the designer would state them. While such a designer-oriented formulation is very attractive, its practical usefulness depends heavily on the ability to search and optimize cost surfaces in a class much broader than usual, as already provided to a large extent by the genetic algorithm (GA). The two instances of the problem studied demonstrate the need for preference articulation in cases where many and highly competing objectives lead to a nondominated set too large for a finite population to sample effectively. It is shown that only a very small portion of the nondominated set is of practical relevance, which further substantiates the need to supply preference information to the GA. The paper concludes with a discussion of the results     

Multiobjective optimization of trusses using genetic algorithms

In this paper we propose the use of the genetic algorithm (GA) as a tool to solve multiobjective optimization problems in structures. Using the concept of min–max optimum, a new GA-based multiobjective optimization technique is proposed and two truss design problems are solved using it. The results produced by this new approach are compared to those produced by other mathematical programming techniques and GA-based approaches, proving that this technique generates better trade-offs and that the genetic algorithm can be used as a reliable numerical optimization tool.     

A case study of memetic algorithms for constraint optimization

There is a variety of knapsack problems in the literature. Multidimensional 0–1 knapsack problem (MKP) is an NP-hard combinatorial optimization problem having many application areas. Many approaches have been proposed for solving this problem. In this paper, an empirical investigation of memetic algorithms (MAs) that hybridize genetic algorithms (GAs) with hill climbing for solving MKPs is provided. Two distinct sets of experiments are performed. During the initial experiments, MA parameters are tuned. GA and four MAs each using a different hill climbing method based on the same configuration are evaluated. In the second set of experiments, a self-adaptive (co-evolving) multimeme memetic algorithm (MMA) is compared to the best MA from the parameter tuning experiments. MMA utilizes the evolutionary process as a learning mechanism for choosing the appropriate hill climbing method to improve a candidate solution at a given time. Two well-known MKP benchmarks are used during the experiments.     

A unified formulation of small-strain corotational finite elements: I. Theory

This paper presents a unified theoretical framework for the corotational (CR) formulation of finite elements in geometrically nonlinear structural analysis. The key assumptions behind CR are: (i) strains from a corotated configuration are small while (ii) the magnitude of rotations from a base configuration is not restricted. Following a historical outline the basic steps of the element independent CR formulation are presented. The element internal force and consistent tangent stiffness matrix are derived by taking variations of the internal energy with respect to nodal freedoms. It is shown that this framework permits the derivation of a set of CR variants through selective simplifications. This set includes some previously used by other investigators. The different variants are compared with respect to a set of desirable qualities, including self-equilibrium in the deformed configuration, tangent stiffness consistency, invariance, symmetrizability, and element independence. We discuss the main benefits of the CR formulation as well as its modeling limitations.     

A survey of repair methods used as constraint handling techniques in evolutionary algorithms

This paper provides a survey of the most important repair heuristics used in evolutionary algorithms to solve constrained optimization problems. Popular techniques are reviewed, such as some crossover operators in permutation encoding, algorithms for fixing the number of 1s in binary encoded genetic algorithms, and more specialized techniques such as Hopfield neural networks, heuristics for graphs and trees, and repair heuristics in grouping genetic algorithms. The survey also gives some indications about the design and implementation of hybrid evolutionary algorithms, and provides a revision of the most important applications in which hybrid evolutionary techniques have been used.     

基于改进的粒子滤波非线性约束优化算法

传统的非线性约束优化算法的精度较低,为了克服这一问题,提出了一种基于粒子滤波的新型优化算法。该算法用于解决非线性约束优化问题,并结合粒子滤波器的模型和机制。首先,利用粒子滤波算法的基本原理建立这种优化算法,并给出算法的操作步骤;然后将非线性约束优化问题转换为函数优化问题函数优化问题,并针对非线性约束优化问题,建立粒子滤波优化算法的数学模型。仿真实验结果证明了这种新型算法的正确性,并且表明了相对于传统的优化算法,基于粒子滤波器的优化方法在解决非线性优化问题方面具有更高的效率和速率,并对今后的非线性约束优化问题具有适应性。     

Computationally efficient algorithms for constraint handling with guaranteed stability and near optimality

Predictive control strategies allow for the systematic handling of constraint, performance and stability. However, the associated algorithms can be computational burdensome and/or difficult to unravel. The aim of this paper is to discuss and compare algorithms based on invariant sets which meet the additional requirement for computational simplicity. There may of course be a concomitant loss of optimality, but as illustrated, this can be minimal and often is a small price to pay when one considers the significant improvements in efficiency.     

Inequality constraint handling in genetic algorithms using a boundary simulation method

Constraint handling is one of the major concerns when applying genetic algorithms (GAs) to solve constrained optimization problems. This paper proposes a boundary simulation method to address inequality constraints for GAs. This method can efficiently generate a feasible region boundary point set to approximately simulate the boundary of the feasible region. Based on the results of the boundary simulation method, GAs can start the genetic search from the boundary of the feasible region or the feasible region itself directly. Furthermore, a series of genetic operators that abandon or repair infeasible individuals produced during the search process is also proposed. The numerical experiments indicate that the proposed method can provide competitive results compared with other studies.     

Computer-based algorithms for multiple criteria and multiple constraint level integer linear programming

This paper investigates algorithm development and implementation for multicriteria and multiconstraint level (MC²) integer linear programming problems. MC² linear programming is an extension of linear programming (LP) and multiple criteria (MC) linear programming and a promising computer-aided decision technique in many applications. Here, we present two of the most recent techniques, the MC² branch-and-partition algorithm and the MC² branch-and-bound algorithm, to solve MC² integer linear programs. We describe the design and implementation of a C++ software library for these approaches, and then conduct a comparison study in terms of computational efficiency and complexity through a series of empirical tests.     

Multiobjective and multi-physics topology optimization using an updated smart normal constraint bi-directional evolutionary structural optimization method

To date the design of structures using topology optimization methods has mainly focused on single-objective problems. Since real-world design problems typically involve several different objectives, most of which counteract each other, it is desirable to present the designer with a set of Pareto optimal solutions that capture the trade-off between these objectives, known as a smart Pareto set. Thus far only the weighted sums and global criterion methods have been incorporated into topology optimization problems. Such methods are unable to produce evenly distributed smart Pareto sets. However, recently the smart normal constraint method has been shown to be capable of directly generating smart Pareto sets. Therefore, in the present work, an updated smart Normal Constraint Method is combined with a Bi-directional Evolutionary Structural Optimization (SNC-BESO) algorithm to produce smart Pareto sets for multiobjective topology optimization problems. Two examples are presented, showing that the Pareto solutions found by the SNC-BESO method make up a smart Pareto set. The first example, taken from the literature, shows the benefits of the SNC-BESO method. The second example is an industrial design problem for a micro fluidic mixer. Thus, the problem is multi-physics as well as multiobjective, highlighting the applicability of such methods to real-world problems. The results indicate that the method is capable of producing smart Pareto sets to industrial problems in an effective and efficient manner.     

Multiobjective topology optimization of structures using genetic algorithms with chromosome repairing

In this work, a genetic algorithm (GA) for multiobjective topology optimization of linear elastic structures is developed. Its purpose is to evolve an evenly distributed group of solutions to determine the optimum Pareto set for a given problem. The GA determines a set of solutions to be sorted by its domination properties and a filter is defined to retain the Pareto solutions. As an equality constraint on volume has to be enforced, all chromosomes used in the genetic GA must generate individuals with the same volume value; in the coding adopted, this means that they must preserve the same number of “ones” and, implicitly, the same number of “zeros” along the evolutionary process. It is thus necessary: (1) to define chromosomes satisfying this propriety and (2) to create corresponding crossover and mutation operators which preserve volume. Optimal solutions of each of the single-objective problems are introduced in the initial population to reduce computational effort and a repairing mechanism is developed to increase the number of admissible structures in the populations. Also, as the work of the external loads can be calculated independently for each individual, parallel processing was used in its evaluation. Numerical applications involving two and three objective functions in 2D and two objective functions in 3D are employed as tests for the computational model developed. Moreover, results obtained with and without chromosome repairing are compared.     

A unified formulation of honeycomb and diamond networks

Honeycomb and diamond networks have been proposed as alternatives to mesh and torus architectures for parallel processing. When wraparound links are included in honeycomb and diamond networks, the resulting structures can be viewed as having been derived via a systematic pruning scheme applied to the links of 2D and 3D tori, respectively. The removal of links, which is performed along a diagonal pruning direction, preserves the network's node-symmetry and diameter, while reducing its implementation complexity and VLSI layout area. In this paper, we prove that honeycomb and diamond networks are special subgraphs of complete 2D and 3D tori, respectively, and show this viewpoint to hold important implications for their physical layouts and routing schemes. Because pruning reduces the node degree without increasing the network diameter, the pruned networks have an advantage when the degree-diameter product is used as a figure of merit. Additionally, if the reduced node degree is used as an opportunity to increase the link bandwidths to equalize the costs of pruned and unpruned networks, a gain in communication performance may result     

Genetic algorithms optimization for normalized normal constraint method under Pareto construction

This paper presents the resolution of multiobjective optimization problems as a tool in engineering design. In the literature, the solutions of this problems are based on the Pareto frontier construction. Therefore, substantial efforts have been made in recent years to develop methods for the construction of Pareto frontiers that guarantee uniform distribution and exclude the non-Pareto and local Pareto points. The normalized normal constraint is a recent contribution that generates a well-distributed Pareto frontier. Nevertheless, these methods are susceptible of improvement or modifications to obtain the same level of results more efficiently. This paper proposes a modification of the original normalized normal constraint method using a genetic algorithms in the optimization task. The results presented in this paper show a suitable behavior for the genetic algorithms method compared to classical Gauss–Newton optimization methods which are used by the original normalized normal constraint method.     

Multiobjective optimization and evolutionary algorithms for the application mapping problem in multiprocessor system-on-chip design

Sesame is a software framework that aims at developing a modeling and simulation environment for the efficient design space exploration of heterogeneous embedded systems. Since Sesame recognizes separate application and architecture models within a single system simulation, it needs an explicit mapping step to relate these models for cosimulation. The design tradeoffs during the mapping stage, namely, the processing time, power consumption, and architecture cost, are captured by a multiobjective nonlinear mixed integer program. This paper aims at investigating the performance of multiobjective evolutionary algorithms (MOEAs) on solving large instances of the mapping problem. With two comparative case studies, it is shown that MOEAs provide the designer with a highly accurate set of solutions in a reasonable amount of time. Additionally, analyses for different crossover types, mutation usage, and repair strategies for the purpose of constraints handling are carried out. Finally, a number of multiobjective optimization results are simulated for verification.     

A prolog constraint handling rules compiler and runtime system

The most recent and advanced implementation of constraint handling rules (CHR) is introduced in a logic programming language. The Prolog implementation consists of a runtime system and a compiler. The runtime system utilizes attributed variables for the realization of the constraint store with efficient retrieval and update mechanisms. Rules describing the interactions between constraints are compiled into Prolog clauses by a compiler, the core of which comprises a small number of compact code generating templates in the form of definite clause grammar rules.     

A unified formulation of Kautz network and generalized hypercube

Hypercube and Kautz network each possess certain desirable properties. However, some of the attractive features of one network are not found in the other. A novel class of network topologies proposed in this paper has the generalized hypercube and the Kautz network as its two extremes. The proposed network inherits the topological properties of both the Kautz network and the generalized hypercube to a varying degree. This allows us to trade-off cost and performance effectively and construct networks which are most suitable for a particular purpose. In the present paper, we investigate the connectivity, wide-diameter, fault-tolerance, Hamiltonicity.     

LMI-based controller synthesis: A unified formulation and solution

This paper proposes a unified approach to linear controller synthesis that employs various LMI conditions to represent control specifications. We define a comprehensive class of LMIs and consider a general synthesis problem described by any LMI of the class. We show a procedure that reduces the synthesis problem, which is a BMI problem, to solving a certain LMI. The derived LMI condition is equivalent to the original BMI condition and also gives a convex parametrization of all the controllers that solve the synthesis problem. The class contains many of widely-known LMIs (for H_∞ norm, H₂ norm, etc.), and hence the solution of this paper unifies design methods that have been proposed depending on each LMI. Further, the class also provides LMIs for multi-objective performance measures, which enable a new formulation of controller design through convex optimization. © 1998 John Wiley & Sons, Ltd.     

优化多重过滤的序列查询算法研究

序列数据是一种重要的数据类型,在诸多领域都有应用,比如说文本、生物数据库以及Web访问日志等。在对该类型数据进行分析的时候,对于相关信息的获取一般都是通过相似性查询得到的。本文首先根据序列查询算法的特点,提出了SSQ_MF,也就是多重过滤算法。并在此基础上设计了最优过滤顺序模型和过滤集大小估计的相关实验。实验结果表明,SSQ_MF算法的查询性能优于单一过滤器算法和随机过滤顺序的多过滤器算法。