Surrogate modeling based on an adaptive network and granular computing

Reducing the number of evaluations of expensive fitness functions is one of the main concerns in evolutionary algorithms, especially when working with instances of contemporary engineering problems. As an alternative to this efficiency constraint, surrogate-based methods are grounded in the construction of approximate models that estimate the solutions’ fitness by modeling the relationships between solution variables and their performance. This paper proposes a methodology based on granular computing for the construction of surrogate models for evolutionary algorithms. Under the proposed method, granules are associated with representative solutions of the problem under analysis. New solutions are evaluated with the expensive (original) fitness function only if they are not already covered by an existing granule. The parameters defining granules are periodically adapted as the search goes on using a neuro-fuzzy network that does not only reduce the number of fitness function evaluations, but also provides better convergence capabilities. The proposed method is evaluated on classical benchmark functions and on a recent benchmark created to test large-scale optimization models. Our results show that the proposed method considerably reduces the actual number of fitness function evaluations without significantly degrading the quality of solutions.     

基于个体适应值灰模型的交互式遗传算法

为将交互式遗传算法应用于复杂的优化问题中,提出一种基于进化个体适应值灰模型预测的交互式遗传算法,为每代适应值序列建立灰模型,以衡量个体适应值评价的不确定性,通过对灰模型的灰预测,提取进化个体评价的可信度,在此基础上,给出进化个体适应值修正公式,将该算法应用于服装进化设计系统中。实验结果表明,该算法在每代都能获取更多的满意解。     

An application of a GA with Markov network surrogate to feature selection

Surrogate models of fitness have been presented as a way of reducing the number of fitness evaluations required by evolutionary algorithms. This is of particular interest with expensive fitness functions where the time taken for building the model is outweighed by the savings of using fewer function evaluations. In this article, we show how a Markov network model can be used as a surrogate fitness function for a genetic algorithm in a new algorithm called Markov Fitness Model Genetic Algorithm (MFM-GA). We thoroughly investigate its application to a fitness function for feature selection in Case-Based Reasoning (CBR), using a range of standard benchmarks from the CBR community. This fitness function requires considerable computation time to evaluate and we show that using the surrogate offers a significant decrease in total run-time compared to a GA using the true fitness function. This comes at the cost of a reduction in the global best fitness found. We demonstrate that the quality of the solutions obtained by MFM-GA improves significantly with model rebuilding. Comparisons with a classic GA, a GA using fitness inheritance and a selection of filter selection methods for CBR shows that MFM-GA provides a good trade-off between fitness quality and run-time.     

Efficient genetic algorithms using discretization scheduling

In many applications of genetic algorithms, there is a tradeoff between speed and accuracy in fitness evaluations when evaluations use numerical methods with varying discretization. In these types of applications, the cost and accuracy vary from discretization errors when implicit or explicit quadrature is used to estimate the function evaluations. This paper examines discretization scheduling, or how to vary the discretization within the genetic algorithm in order to use the least amount of computation time for a solution of a desired quality. The effectiveness of discretization scheduling can be determined by comparing its computation time to the computation time of a GA using a constant discretization. There are three ingredients for the discretization scheduling: population sizing, estimated time for each function evaluation and predicted convergence time analysis. Idealized one- and two-dimensional experiments and an inverse groundwater application illustrate the computational savings to be achieved from using discretization scheduling.     

The Ising genetic algorithm with Gibbs distribution sampling: Application to FIR filter design

In this paper the design of maximally flat linear phase finite impulse response (FIR) filters is considered. The problem with using the genetic algorithm (GA) in this kind of problems is the high cost of evaluating the fitness for each string in the population. The designing of optimum FIR filters under given constraints and required criteria includes exhaustive number of evaluations for filter coefficients, and the repetitive evaluations of objective functions that implicitly constitutes construction of the filter transfer functions. This problem is handled here with acceptable results utilizing Markov random fields (MRF's) approach. We establish a new theoretical approach here and we apply it on the design of FIR filters. This approach allows us to construct an explicit probabilistic model of the GA fitness function forming what is called the “Ising GA” that is based on sampling from a Gibbs distribution. Ising GA avoids the exhaustive design of suggested FIR filters (solutions) for every string of coefficients in every generation and replace this by a probabilistic model of fitness every gap (period) of iterations. Experimentations done with Ising GA of probabilistic fitness models are less costly than those done with standard GA and with high quality solutions.     

Microgenetic algorithms as generalized hill-climbing operators forGA optimization

We investigate the potential of a microgenetic algorithm (MGA) as a generalized hill-climbing operator. Combining a standard GA with the suggested MGA operator leads to a hybrid genetic scheme GA-MGA, with enhanced searching qualities. The main GA performs global search while the MGA explores a neighborhood of the current solution provided by the main GA, looking for better solutions. The MGA operator performs genetic local search. The major advantage of MGA is its ability to identify and follow narrow ridges of arbitrary direction leading to the global optimum. The proposed GA-MGA scheme is tested against 13 different schemes, including a simple GA and GAs with different hill-climbing operators. Experiments are conducted on a test set including eight constrained optimization problems with continuous variables. Extensive simulation results demonstrate the efficiency of the proposed GA-MGA scheme. For the same number of fitness evaluations, GA-MGA exhibited a significantly better performance in terms of solution accuracy, feasibility percentage of the attained solutions, and robustness     

基于遗传算法的Peer to Peer路由算法R GA*

路由算法是制约PeertoPeer 系统整体性能的关键因素之一。目前大多数路由算法无法保证全局收敛,而链路延迟、费用、网络带宽等现实制约因素往往在选路时被忽略。针对上述问题,提出了基于遗传算法的RGA路由算法。通过适度函数和遗传因子,RGA可以快速地实现全局收敛。同时将链路的延迟、费用、带宽等参数插入到适度函数中, 避免了盲目路由。仿真试验的结果表明,RGA路由算法在大规模PeertoPeer系统中是高效和可扩展的。     

Redundancy allocation problems considering systems with imperfect repairs using multi-objective genetic algorithms and discrete event simulation

This paper considers a multi-objective genetic algorithm (GA) coupled with discrete event simulation to solve redundancy allocation problems in systems subject to imperfect repairs. In the multi-objective formulation, system availability and cost may be maximized and minimized, respectively; the failure-repair processes of system components are modeled by Generalized Renewal Processes. The presented methodology provides a set of compromise solutions that incorporate not only system configurations, but also the number of maintenance teams. The multi-objective GA is validated via examples with analytical solutions and shows its superior performance when compared to a multi-objective Ant Colony algorithm. Moreover, an application example is presented and a return of investment analysis is suggested to aid the decision maker in choosing a solution of the obtained set.     

A Model of Co-evolutionary Design

Computational evolution provides a mechanism for searching a space of potential solutions according to a specified fitness function. In design, the search for potential solutions is often interleaved with changes in the specifications of the solution. We have developed a model of design that uses a co-evolutionary process. Specifically, design is modelled as a parallel search for both design requirements and design solutions. Further, we have developed a co-evolutionary process in which the interaction between requirements and solution redefine the current fitness function. The concepts of fitness and convergence in computational evolution do not necessarily have the same meanings in a co-evolutionary process in which the fitness function changes. An additional consideration not present in compu-tational evolution is the interaction between the parallel search spaces. We demonstrate how the design model can be implemented for structural system layout.     

Constraint handling in genetic algorithms using a gradient-based repair method

Constraint handling is one of the major concerns when applying genetic algorithms (GAs) to solve constrained optimization problems. This paper proposes to use the gradient information derived from the constraint set to systematically repair infeasible solutions. The proposed repair procedure is embedded into a simple GA as a special operator. Experiments using 11 benchmark problems are presented and compared with the best known solutions reported in the literature. Our results are competitive, if not better, compared to the results reported using the homomorphous mapping method, the stochastic ranking method, and the self-adaptive fitness formulation method.     

基于区间适应值交互式遗传算法的加权多输出高斯过程代理模型

融合了用户认知和智能评价的交互式遗传算法（Interactive genetic algorithm,IGA）是解决一类定性性能指标优化问题的有效方法,但是,评价不确定性和易疲劳性极大地限制了该算法解决实际问题的能力. 基于用户已评价信息,采用合适的机器学习方法,构建用户认知代理模型是解决上述问题的常用方法之一. 但是,现有研究成果均没有考虑用户评价不确定性对学习样本、代理模型的影响,以及模型拟合不确定性对基于适应值的进化操作有效性的影响. 针对上述问题,本文提出基于加权多输出高斯过程（Gaussian process,GP）代理模型的交互式遗传算法. 首先,在区间适应值评价模式下,提取学习样本的噪声特性,以确定相应学习样本对代理模型的影响度权重系数,构建两输出高斯过程代理模型;然后,利用代理模型提供的预测值及预测置信水平,给出一种新的个体适应值估计方法和个体选择方法;基于模型预测信息,实现模型更新管理. 将所提算法分别应用于含噪函数和服装设计问题中,所得结果表明本文算法可更好地拟合和跟踪用户认知,减小对进化搜索的误导,更快找到用户满意解.     

Noise analysis compact differential evolution

This article proposes a compact algorithm for optimisation in noisy environments. This algorithm has a compact structure and employs differential evolution search logic. Since it is a compact algorithm, it does not store a population of solutions but a probabilistic representation of the population. This kind of algorithmic structure can be implemented in those real-world problems characterized by memory limitations. The degree of randomization contained in the compact structure allows a robust behaviour in the presence of noise. In addition the proposed algorithm employs the noise analysis survivor selection scheme. This scheme performs an analysis of the noise and automatically performs a re-sampling of the solutions in order to ensure both reliable pairwise comparisons and a minimal cost in terms of fitness evaluations. The noise analysis component can be reliably used in noise environments affected by Gaussian noise which allow an a priori analysis of the noise features. This situation is typical of problems where the fitness is computed by means of measurement devices. An extensive comparative analysis including four different noise levels has been included. Numerical results show that the proposed algorithm displays a very good performance since it regularly succeeds at handling diverse fitness landscapes characterized by diverse noise amplitudes.     

A dynamic vehicle routing problem with time-dependent travel times

In this paper we present a formulation for the dynamic vehicle routing problem with time-dependent travel times. We also present a genetic algorithm to solve the problem. The problem is a pick-up or delivery vehicle routing problem with soft time windows in which we consider multiple vehicles with different capacities, real-time service requests, and real-time variations in travel times between demand nodes.The performance of the genetic algorithm is evaluated by comparing its results with exact solutions and lower bounds for randomly generated test problems. For small size problems with up to 10 demands, the genetic algorithm provides almost the same results as the exact solutions, while its computation time is less than 10% of the time required to produce the exact solutions. For the problems with 30 demand nodes, the genetic algorithm results have less than 8% gap with lower bounds.This research also shows that as the uncertainty in the travel time information increases, a dynamic routing strategy that takes the real-time traffic information into account becomes increasingly superior to a static one. This is clear when we compare the static and dynamic routing strategies in problem scenarios that have different levels of uncertainty in travel time information. In additional tests on a simulated network, the proposed algorithm works well in dealing with situations in which accidents cause significant congestion in some part of the transportation network.     

新的鲁棒粒子群算法在电磁场逆问题中应用研究

提出了一种搜索鲁棒优化解的粒子群算法。为解决期望适值函数计算需要大量新采样点而导致的计算效率过低问题,提出了一种期望适值赋值的新机制。该机制只对每一代粒子中的个体最优解和整体最优解分配期望适值。此外,为便于算法搜索鲁棒优化解,重新定义了粒子的邻域关系。最后,通过两个实例计算证明了新算法求解电磁场逆问题鲁棒优化解的可行性和优点。     

An investigation of genetic algorithms for the optimization of multi-objective fisheries bioeconomic models

The use of genetic algorithms (GA) for optimization problems offers an alternative approach to the traditional solution methods. GA follow the concept of solution evolution, by stochastically developing generations of solution populations using a given fitness statistic, for example the achievement function in goal programs. They are particularly applicable to problems which are large, non-linear and possibly discrete in nature, features that traditionally add to the degree of complexity of solution. Owing to the probabilistic development of populations, GA do not distinguish solutions, e.g. local optima from other solutions, and therefore cannot guarantee optimality even though a global optimum may be reached. In this paper, a non-linear goal program of the North Sea demersal fisheries is used to develop a genetic algorithm for optimization. Comparisons between the GA approach and traditional solution methods are made, in order to measure the relative effectiveness. General observations of the use of GA in multi-objective fisheries bioeconomic models, and other similar models, are discussed.     

基于遗传算法的Peer-to-Peer路由算法R-GA

路由算法是制约Peer-to-Peer 系统整体性能的关键因素之一.目前大多数路由算法无法保证全局收敛,而链路延迟、费用、网络带宽等现实制约因素往往在选路时被忽略.针对上述问题,提出了基于遗传算法的R-GA路由算法.通过适度函数和遗传因子,R-GA可以快速地实现全局收敛.同时将链路的延迟、费用、带宽等参数插入到适度函数中, 避免了盲目路由.仿真试验的结果表明,R-GA路由算法在大规模Peer-to-Peer系统中是高效和可扩展的.     

Variations in the application of a budget of uncertainty optimization approach

It is possible to consider uncertainty simultaneously with the design process. In fact, a Budget of Uncertainty(BoU) can be determined alongside the design solution, allowing the determination of uncertainty intervals for selected design variables and problem parameters. This paper presents a new strategy for optimization under uncertainty which provides for this simultaneous design and uncertainty determination. To test the theory, a simple Taylor series expansion strategy is used to propagate uncertainty in a design problem’s objectives and constraints and a new BoU design algorithm is formulated. Due to the need for competing objectives, nominal performance and robust design, the new formulation is a multiobjective problem with primary and secondary weights to allow for lexicographic weights of uncertain parameters and variation between optimal and robust solutions. This paper compares and contrasts three different Goal Programming techniques as solutions to the multiobjective problem. Within the paper, the term Budget of Uncertainty (BoU) is used to describe the fundamental idea of uncertainty allocation across design variables and problem parameters as well as for a shorthand to describe the presented formulation. An engineering design problem, that of a helical spring, is presented to further illustrate the new method, and an uncertainty budget is considered which trades uncertainty in coil diameter against uncertainty in wire diameter.     

Minimizing position uncertainty for under-ice autonomous underwater vehicles

Localization underwater has been known to be challenging due to the limited accessibility of the Global Positioning System (GPS) to obtain absolute positions. This becomes more severe in the under-ice environment since the ocean surface is covered with ice, making it more difficult to access GPS or to deploy localization infrastructure. In this paper, a novel solution that minimizes localization uncertainty and communication overhead of under-ice Autonomous Underwater Vehicles (AUVs) is proposed. Existing underwater localization solutions generally rely on reference nodes at ocean surface or on localization infrastructure to calculate positions, and they are not able to estimate the localization uncertainty, which may lead to the increase of localization error. In contrast, using the notion of external uncertainty (i.e., the position uncertainty as seen by others), our solution can characterize an AUV’s position with a probability model. This model is further used to estimate the uncertainty associated with our proposed localization techniques. Based on this uncertainty estimate, we further propose algorithms to minimize localization uncertainty and communication overhead. Our solution is emulated and compared against existing solutions, showing improved performance.     

Implicit representation in genetic algorithms using redundancy

A new representation combining redundancy and implicit fitness constraints is introduced that performs better than a simple genetic algorithm (GA) and a structured GA in experiments. The implicit redundant representation (IRR) consists of a string that is over-specified, allowing for sections of the string to remain inactive during function evaluation. The representation does not require the user to prespecify the number of parameters to evaluate or the location of these parameters within the string. This information is obtained implicitly by the fitness function during the GA operations. The good performance of the IRR can be attributed to several factors: less disruption of existing fit members due to the increased probability of crossovers and mutation affecting only redundant material; discovery of fit members through the conversion of redundant material into essential information; and the ability to enlarge or reduce the search space dynamically by varying the number of variables evaluated by the fitness function. The IRR GA provides a more biologically parallel representation that maintains a diverse population throughout the evolution process. In addition, the IRR provides the necessary flexibility to represent unstructured problem domains that do not have the explicit constraints required by fixed representations.     

A modified distance method for multicriteria optimization, using genetic algorithms

The common application areas of Genetic Algorithms (GAs) have been to single criterion difficult optimization problems. The GA selection mechanism is often dependent upon a single valued scalar objective funtion. In this paper, we present results of a modified distance method. The distance method was proposed earlier by us, for solving multiple criteria problems with GAs. The Pareto set estimation method, which is fundamental to multicriteria analysis, is used to perform the multicriteria optimization using GAs. First, the Pareto set is found out from the population of the initial generation of the GA. The fitness of a new solution, is calculated by a distance measure with reference to the Pareto set of the previous runs. We calculate the distances of a solution from all the Pareto solutions found since the previous run, but the minimum of these distances is taken under consideration while evaluating the fitness of the solution. Thus the GA tries to maximize the distance of future Pareto solutions from present Pareto solutions in the positive Pareto space of the given problem. Here we modify distance method, by using an improved algorithm to assign and make use of the latent potential of the Pareto solutions which are found during the runs. Two detailed numerical examples and computer generated results are also presented.