Embedding linear programming in multi objective genetic algorithms for reducing the size of the search space with application to leakage minimization in water distribution networks

This paper shows how embedding a local search algorithm, such as the iterated linear programming (LP), in the multi-objective genetic algorithms (MOGAs) can lead to a reduction in the search space and then to the improvement of the computational efficiency of the MOGAs. In fact, when the optimization problem features both continuous real variables and discrete integer variables, the search space can be subdivided into two sub-spaces, related to the two kinds of variables respectively. The problem can then be structured in such a way that MOGAs can be used for the search within the sub-space of the discrete integer variables. For each solution proposed by the MOGAs, the iterated LP can be used for the search within the sub-space of the continuous real variables. An example of this hybrid algorithm is provided herein as far as water distribution networks are concerned. In particular, the problem of the optimal location of control valves for leakage attenuation is considered. In this framework, the MOGA NSGAII is used to search for the optimal valve locations and for the identification of the isolation valves which have to be closed in the network in order to improve the effectiveness of the control valves whereas the iterated linear programming is used to search for the optimal settings of the control valves. The application to two case studies clearly proves the reduction in the MOGA search space size to render the hybrid algorithm more efficient than the MOGA without iterated linear programming embedded.     

Improving multi-objective genetic algorithms with adaptive design of experiments and online metamodeling

Applications of multi-objective genetic algorithms (MOGAs) in engineering optimization problems often require numerous function calls. One way to reduce the number of function calls is to use an approximation in lieu of function calls. An approximation involves two steps: design of experiments (DOE) and metamodeling. This paper presents a new approach where both DOE and metamodeling are integrated with a MOGA. In particular, the DOE method reduces the number of generations in a MOGA, while the metamodeling reduces the number of function calls in each generation. In the present approach, the DOE locates a subset of design points that is estimated to better sample the design space, while the metamodeling assists in estimating the fitness of design points. Several numerical and engineering examples are used to demonstrate the applicability of this new approach. The results from these examples show that the proposed improved approach requires significantly fewer function calls and obtains similar solutions compared to a conventional MOGA and a recently developed metamodeling-assisted MOGA.     

Stochastic sampling design using a multi-objective genetic algorithm and adaptive neural networks

This paper presents a novel multi-objective genetic algorithm (MOGA) based on the NSGA-II algorithm, which uses metamodels to determine optimal sampling locations for installing pressure loggers in a water distribution system (WDS) when parameter uncertainty is considered. The new algorithm combines the multi-objective genetic algorithm with adaptive neural networks (MOGA–ANN) to locate pressure loggers. The purpose of pressure logger installation is to collect data for hydraulic model calibration. Sampling design is formulated as a two-objective optimization problem in this study. The objectives are to maximize the calibrated model accuracy and to minimize the number of sampling devices as a surrogate of sampling design cost. Calibrated model accuracy is defined as the average of normalized traces of model prediction covariance matrices, each of which is constructed from a randomly generated sampling set of calibration parameter values. This method of calculating model accuracy is called the ‘full’ fitness model. Within the genetic algorithm search process, the full fitness model is progressively replaced with the periodically (re)trained adaptive neural network metamodel where (re)training is done using the data collected by calling the full model. The methodology was first tested on a hypothetical (benchmark) problem to configure the setting requirement. Then the model was applied to a real case study. The results show that significant computational savings can be achieved by using the MOGA–ANN when compared to the approach where MOGA is linked to the full fitness model. When applied to the real case study, optimal solutions identified by MOGA–ANN are obtained 25 times faster than those identified by the full model without significant decrease in the accuracy of the final solution.     

Entropy-based multi-objective genetic algorithm for design optimization

Obtaining a fullest possible representation of solutions to a multiobjective optimization problem has been a major concern in Multi-Objective Genetic Algorithms (MOGAs). This is because a MOGA, due to its very nature, can only produce a discrete representation of Pareto solutions to a multiobjective optimization problem that usually tend to group into clusters. This paper presents a new MOGA, one that aims at obtaining the Pareto solutions with maximum possible coverage and uniformity along the Pareto frontier. The new method, called an Entropy-based MOGA (or E-MOGA), is based on an application of concepts from the statistical theory of gases to a baseline MOGA. Two demonstration examples, the design of a two-bar truss and a speed reducer, are used to demonstrate the effectiveness of E-MOGA in comparison to the baseline MOGA.     

基于多目标遗传算法的RITS物理结构优化设计

提出了RITS物理结构优化设计问题模型和基于多目标优化的解决思路。RITS结构优化设计待优化函数具有高维、多峰、非线性等特点，求解难度人。重点研究了一类基于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.     

Evolutionary multi criteria design optimization of robot grippers

This paper explores the use of intelligent techniques to obtain optimum geometrical dimensions of a robot gripper. The optimization problem considered is a non-linear, complex, multi-constraint and multicriterion one. Three robot gripper configurations are optimized. The aim is to find Pareto optimal front for a problem that has five objective functions, nine constraints and seven variables. The problem is divided into three cases. Case 1 has first two objective functions, the case 2 considers last three objective functions and case 3 deals all the five objective functions. Intelligent optimization algorithms namely Multi-objective Genetic Algorithm (MOGA), Elitist Non-dominated Sorting Genetic Algorithm (NSGA-II) and Multi-objective Differential Evolution (MODE) are proposed to solve the problem. Normalized weighting objective functions method is used to select the best optimal solution from Pareto optimal front. Two multi-objective performance measures (solution spread measure (SSM) and ratio of non-dominated individuals (RNIs)) are used to evaluate the strength of the Pareto optimal fronts. Two more multi-objective performance measures namely optimizer overhead (OO) and algorithm effort are used to find the computational effort of MOGA, NSGA-II and MODE algorithms. The Pareto optimal fronts and results obtained from various techniques are compared and analyzed.     

Design and implementation of a general software library for using NSGA-II with SWAT for multi-objective model calibration

Calibrating watershed-scale hydrologic models remains a critical but challenging step in the modeling process. The Soil and Water Assessment Tool (SWAT) is one example of a widely used watershed-scale hydrologic model that requires calibration. The calibration algorithms currently available to SWAT modelers through freely available and open source software, however, are limited and do not include many multi-objective genetic algorithms (MOGAs). The Non-Dominated Sorting Genetic Algorithm II (NSGA-II) has been shown to be an effective and efficient MOGA calibration algorithm for a wide variety of applications including for SWAT model calibration. Therefore, the objective of this study was to create an open source software library for multi-objective calibration of SWAT models using NSGA-II. The design and implementation of the library are presented, followed by a demonstration of the library through a test case for the Upper Neuse Watershed in North Carolina, USA using six objective functions in the model calibration.     

QoS全局最优的多目标Web服务选择算法*

针对现有方法的不足,提出一种基于QoS全局最优的多目标动态Web服务选择算法。在给出动态服务组合模型的基础上,以“抽象服务规划”为输入,以用户的非功能性需求为全局约束,将动态服务选择问题转换为一个带QoS约束的多目标服务组合优化问题;利用多目标蚁群算法,多个目标函数被同时优化并产生一组满足约束条件的Pareto优化解。通过运用实验与基于多目标遗传算法的Web服务选择算法进行对比,证明了该方法的可行性和有效性。     

基于遗传算法的数据中心能效仿真

随着数据中心数量和规模的不断扩大,能耗已经成为制约数据中心成本和可靠性的关键问题。而且,随着数据中心投入运营后的硬件迭代更新,数据中心服务器的异构性进一步加大,其能效也同设计建设之初相比有较大的变化。因此,根据数据中心服务器的构成和硬件配置,对整个数据中心进行动态能效仿真与分析,有助于实时掌握数据中心的能效现状,进行能效感知的负载调度,并提供能效优化的可能性。首先基于企业级服务器的SPECpower测试结果,对近年来服务器的能效发展趋势和影响因素进行了分析;然后基于遗传算法对数据中心的能效优化进行仿真,并设计了一个数据中心的能效仿真器原型系统。该仿真器可以根据供电限额、负载情况和吞吐量指标等动态仿真和调整数据中心服务器的运行状态,并对不同规模和不同服务器类型的数据中心能效进行仿真。所提出的基于遗传算法的数据中心能效仿真算法在能量最小化问题上得到了较小的误差和较短的仿真计算时间。     

A learning method for dynamic Bayesian network structures using a multi-objective particle swarm optimizer

In this article, we present a multi-objective discrete particle swarm optimizer (DPSO) for learning dynamic Bayesian network (DBN) structures. The proposed method introduces a hierarchical structure consisting of DPSOs and a multi-objective genetic algorithm (MOGA). Groups of DPSOs find effective DBN sub-network structures and a group of MOGAs find the whole of the DBN network structure. Through numerical simulations, the proposed method can find more effective DBN structures, and can obtain them faster than the conventional method.     

Model reduction by CPOD and Kriging

This paper proposes a novel approach for multi-objective optimization when the criteria of interest rely on a functional output from an expensive-to-evaluate numerical simulator. More specifically, the proposed method is developed in the frame of an automotive application. The aim of this application is to design the shape of an intake port in order to maximize the mass flow (denoted by Q) and the tumble (denoted by T), which both depend on a 3D velocity field obtained by numerical flow simulation. Since the considered flow simulator is time-consuming, using regular multi-objective genetic algorithms (MOGA) directly on integral quantities depending on the simulator output is prohibitive. Three different Reduced Order Models (ROMs) are presented. The first one consists in directly Kriging the integral quantities Q and T on the basis of the outputs computed at an initial design of experiments, and basing the optimization search on the sequentially obtained couples of response surfaces. The other methods explored in the present work consist in building a parametrized representation of the whole velocity field by different variants of the Proper Orthogonal Decomposition (POD). Instead of directly Kriging Q and T at un-sampled locations, the proposed technique is hence to proceed in two steps: first approximate the functional outcome by Kriging the POD coefficients, and then compute the integral quantities Q and T associated with the approximate 3D field. However, such an approach induces new difficulties since the truncated POD does not preserve the global (integrated) quantities, and that surrogate-based MOGA with this kind of POD are therefore likely to fail locating the (Q, T)-Pareto front accurately. This is what motivates to propose an original constrained POD method (called CPOD) meant to overcome the bias created by the truncation made in regular POD. More precisely, this means modifying the way of calculating the POD coefficients by imposing the integral quantities Q and T based on the truncated POD to match with the actual Q and T values obtained by flow simulation at the design of experiments. A detailed comparison of the Pareto sets obtained from the three ROMs demonstrates the interest of the CPOD approach.     

基于层次遗传算法的物流配送中心选址策略*

在考虑物流规划部门和客户双方利益的基础上,采用双层规划模型描述物流配送中心的选址问题。基于进化博弈与多目标优化的思想设计了层次遗传算法来求解该模型,通过两个遗传算法的交互迭代求解物流配送中心选址问题。最后通过算例验证了模型与算法的可行性。     

一种全终端网络可靠性多目标优化模型及求解

分析了全终端网络可靠性设计问题,针对单目标优化存在的不足,建立了一种更加贴近工程实际的极大化可靠度,同时极小化投资成本的多目标优化模型,并利用模拟退火算法对其进行了优化求解。计算机仿真实例表明:模拟退火算法在求解此问题时,无论是在Pareto解的数量上还是在Pareto解的范围上都能得到较好的优化效果。     

基于多目标遗传算法的Σ-ΔMEMS加速度计优化设计

针对单目标遗传算法设计优化高阶Σ-Δ微机电系统(Σ-ΔMEMS)加速度计时易出现的稳定性问题,提出了基于多目标遗传算法的MEMS加速度计环路滤波器优化设计方法.对三阶非限定性Σ-ΔMEMS加速度计系统,采用多目标遗传算法,将∞—范数和信噪比作为设计目标对其环路滤波器参数进行优化设计.结果表明:相比只针对信噪比进行优化的传统单目标遗传算法,多目标遗传算法在确保高信噪比的同时,提高了系统的相位裕度,使得最大稳定输入信号范围增幅超过1倍,增强了系统对MEMS敏感元件工艺误差的鲁棒性.     

Multi-objective optimization of an auto panel drawing die face design by mesh morphing

In order to facilitate the tryout or simulation process at the end of a manual auto panel drawing die face design process, we use finite element analysis (FEA) and a multi-objective genetic algorithm (MOGA) to find all the Pareto optimal solutions in one go and to achieve the optimal design of an auto panel drawing die face instead of transforming multi-objective functions into a single objective function, and employ a novel mesh morphing technique to achieve fast modification of parametric or non-parametric addendum surfaces and binder surfaces on drawing die faces without going back to CAD for reconstruction of geometric models or to FEA for remodeling. We use an auto panel drawing die face design process as an example to illustrate the application and effectiveness of this proposed approach, and come to the conclusion that the proposed approach is more effective than the traditional manual FEA method and the ‘trial-and-error’ approach in optimizing an auto panel drawing die face design.     

A multi-objective hyper-heuristic based on choice function

Hyper-heuristics are emerging methodologies that perform a search over the space of heuristics in an attempt to solve difficult computational optimization problems. We present a learning selection choice function based hyper-heuristic to solve multi-objective optimization problems. This high level approach controls and combines the strengths of three well-known multi-objective evolutionary algorithms (i.e. NSGAII, SPEA2 and MOGA), utilizing them as the low level heuristics. The performance of the proposed learning hyper-heuristic is investigated on the Walking Fish Group test suite which is a common benchmark for multi-objective optimization. Additionally, the proposed hyper-heuristic is applied to the vehicle crashworthiness design problem as a real-world multi-objective problem. The experimental results demonstrate the effectiveness of the hyper-heuristic approach when compared to the performance of each low level heuristic run on its own, as well as being compared to other approaches including an adaptive multi-method search, namely AMALGAM.     

云计算环境下基于多目标优化的虚拟机放置研究

云数据中心的规模日益增长导致其产生的能源消耗及成本呈指数级增长。虚拟机的放置是提高云计算环境服务质量与节约成本的核心。针对传统的虚拟机放置算法存在考虑目标单一化和多目标优化难以找到最优解的问题,提出一种面向能耗、资源利用率、负载均衡的多目标优化虚拟机放置模型。通过改进蚁群算法求解优化模型,利用其信息素正反馈机制和启发式搜索寻找最优解。实验结果表明,该算法综合性能表现良好,符合云环境对高效率低能耗的要求。     

数据中心电费最小化的负载调度策略

为了降低电费成本,一些数据中心使用绿色能源供电。然而,负载的波动性和电价的时间差异性给数据中心电费成本带来了挑战。针对上述问题,提出一种低成本的负载调度算法,使得数据中心电费最小化。首先,建立电力耗费模型;然后,将电费最小化问题形式化为一个多目标约束的优化问题;最后,求解该优化问题得到相应的负载调度策略。实验结果表明:该算法可以在保证负载性能的前提下,有效降低数据中心的电费成本。