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.     

基于代理模型的差分进化约束优化

针对耗时计算目标函数的约束优化问题,提出用代理模型来代替耗时计算目标函数的方法,并结合目标函数的信息对约束个体进行选择,从而提出基于代理模型的差分进化约束优化算法。首先,采用拉丁超立方采样方法建立初始种群,用耗时计算目标函数对初始种群进行评估,并以此为样本数据建立目标函数的神经网络代理模型。然后,用差分进化方法为种群中的每一个亲本产生后代,并对后代使用代理模型进行评估,采用可行性规则来比较后代与其亲本并更新种群,根据替换机制将种群中较劣的个体替换为备用存档中较优的个体。最后,当达到最大适应度评估次数时算法停止,给出最优解。该算法与对比算法在10个测试函数上运行的结果表明,该算法得出的结果更精确。将该算法应用于工字梁优化问题的结果表明,相较于优化前的算法,该算法的适应度评估次数减少了80%;相对于FROFI（Feasibility Rule with the incorporation of Objective Function Information）算法,该算法的适应度评估次数减少了36%。运用所提算法进行优化可以有效减少调用耗时计算目标函数的次数,提升优化效率,节约计算成本。     

Analytical and numerical comparisons of biogeography-based optimization and genetic algorithms

We show that biogeography-based optimization (BBO) is a generalization of a genetic algorithm with global uniform recombination (GA/GUR). Based on the common features of BBO and GA/GUR, we use a previously-derived BBO Markov model to obtain a GA/GUR Markov model. One BBO characteristic which makes it distinctive from GA/GUR is its migration mechanism, which affects selection pressure (i.e., the probability of retaining certain features in the population from one generation to the next). We compare the BBO and GA/GUR algorithms using results from analytical Markov models and continuous optimization benchmark problems. We show that the unique selection pressure provided by BBO generally results in better optimization results for a set of standard benchmark problems. We also present comparisons between BBO and GA/GUR for combinatorial optimization problems, include the traveling salesman, the graph coloring, and the bin packing problems.     

Toward Global Optimization of Case-Based Reasoning Systems for Financial Forecasting

This paper presents a simultaneous optimization method of a case-based reasoning (CBR) system using a genetic algorithm (GA) for financial forecasting. Prior research proposed many hybrid models of CBR and the GA for selecting a relevant feature subset or optimizing feature weights. Most research used the GA for improving only a part of architectural factors of the CBR model. However, the performance of the CBR model may be enhanced when these factors are simultaneously considered. In this study, the GA simultaneously optimizes multiple factors of the CBR system. Experimental results show that a GA approach to simultaneous optimization of the CBR model outperforms other conventional approaches for financial forecasting.     

GA-PARSIMONY: A GA-SVR approach with feature selection and parameter optimization to obtain parsimonious solutions for predicting temperature settings in a continuous annealing furnace

This article proposes a new genetic algorithm (GA) methodology to obtain parsimonious support vector regression (SVR) models capable of predicting highly precise setpoints in a continuous annealing furnace (GA-PARSIMONY). The proposal combines feature selection, model tuning, and parsimonious model selection in order to achieve robust SVR models. To this end, a novel GA selection procedure is introduced based on separate cost and complexity evaluations. The best individuals are initially sorted by an error fitness function, and afterwards, models with similar costs are rearranged according to model complexity measurement so as to foster models of lesser complexity. Therefore, the user-supplied penalty parameter, utilized to balance cost and complexity in other fitness functions, is rendered unnecessary. GA-PARSIMONY performed similarly to classical GA on twenty benchmark datasets from public repositories, but used a lower number of features in a striking 65% of models. Moreover, the performance of our proposal also proved useful in a real industrial process for predicting three temperature setpoints for a continuous annealing furnace. The results demonstrated that GA-PARSIMONY was able to generate more robust SVR models with less input features, as compared to classical GA.     

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.     

结合特征扰动与分配策略的集成辅助多目标优化算法

代理模型利用近似预测代替算法对多目标优化问题的真实评价,大幅减少了算法寻优所需的真实适应度评估次数。为提高代理模型在求解高维问题时的准确性并降低计算开销,提出一种基于特征扰动与分配策略的集成辅助多目标优化算法。将径向基函数网络代理模型与支持向量机回归代理模型作为集成过程中的基模型,降低算法在高维问题上的计算开销。结合特征扰动与基于记忆的影响因子分配策略构建集成代理模型,提高集成准确性。使用集成预测值与不确定信息加权辅助管理集成代理模型,平衡全局搜索与局部探索,增强算法在目标空间中的寻优能力。实验结果表明,该算法在ZDT1~ZDT3和ZDT6测试问题上所得解集的分布性与收敛性相比经典算法更好,并且当决策变量维数增加时,使用集成代理模型相比于Kriging代理模型约减少了90%的适应度评估次数,同时可获得更准确的预测结果。     

Backward-chaining evolutionary algorithms

Starting from some simple observations on a popular selection method in Evolutionary Algorithms (EAs)—tournament selection—we highlight a previously-unknown source of inefficiency. This leads us to rethink the order in which operations are performed within EAs, and to suggest an algorithm—the EA with efficient macro-selection—that avoids the inefficiencies associated with tournament selection. This algorithm has the same expected behaviour as the standard EA but yields considerable savings in terms of fitness evaluations. Since fitness evaluation typically dominates the resources needed to solve any non-trivial problem, these savings translate into a reduction in computer time. Noting the connection between the algorithm and rule-based systems, we then further modify the order of operations in the EA, effectively turning the evolutionary search into an inference process operating in backward-chaining mode. The resulting backward-chaining EA creates and evaluates individuals recursively, backward from the last generation to the first, using depth-first search and backtracking. It is even more powerful than the EA with efficient macro-selection in that it shares all its benefits, but it also provably finds fitter solutions sooner, i.e., it is a faster algorithm. These algorithms can be applied to any form of population based search, any representation, fitness function, crossover and mutation, provided they use tournament selection. We analyse their behaviour and benefits both theoretically, using Markov chain theory and space/time complexity analysis, and empirically, by performing a variety of experiments with standard and back-ward chaining versions of genetic algorithms and genetic programming.     

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.     

异构集成代理辅助多目标粒子群优化算法

针对代理辅助进化算法在减少昂贵适应度评估时难以通过少量样本点构造高质量代理模型的问题,提出异构集成代理辅助多目标粒子群优化算法。该方法通过使用加权平均法将Kriging模型和径向基函数网络模型组合成高精度的异构集成模型,达到增强算法处理不确定性信息能力的目的。基于集成学习的两种代理模型分别应用于全局搜索和局部搜索,在多目标粒子群优化算法框架基础上,新提出的方法为每个目标函数自适应地构造了异构集成模型,利用其模型的非支配解来指导粒子群的更新,得出目标函数的最优解集。实验结果表明,所提方法提高了代理模型的搜索能力,减少了评估次数,并且随着搜索维度的增加,其计算复杂性也具有更好的可扩展性。     

Handling expensive multi-objective optimization problems with a cluster-based neighborhood regression model

This paper gives attention to multi-objective optimization in scenarios where objective function evaluation is expensive, that is, expensive multi-objective optimization. We firstly propose a cluster-based neighborhood regression model, which incorporates the linear regression technique to predict the descent direction and generate new potential offspring. Combining this model with the classical decomposition-based multi-objective optimization framework, we propose an efficient and effective algorithm for tackling computationally expensive multi-objective optimization problems. As opposed to the conventional approach of replacing the original time-consuming objective functions with the approximated ones obtained by surrogate model, the proposed algorithm incorporates the proposed regression model to serve as an operator producing higher-quality offspring so that the algorithm requires fewer iterations to reach a given solution quality. The proposed algorithm is compared with several state-of-the-art surrogate-assisted algorithms on a variety of well-known benchmark problems. Empirical results demonstrate that the proposed algorithm outperforms or is competitive with other peer algorithms, and has the ability to keep a good trade-off between solution quality and running time within a fairly small number of function evaluations. In particular, our proposed algorithm shows obvious superiority in terms of the computational time used for the algorithm components, and can obtain acceptable solutions for expensive problems with high efficiency.     

多维优化案例推理检索算法研究

案例检索是案例推理系统的中心环节,检索质量关系着整个系统的质量。利用遗传算法GA和层次分析法AHP相结合,从案例库,属性的约简,权值确定三方面对案例检索进行优化。利用遗传算法在搜索优化上的优势,使用两维的编码结合权值从而形成三维优化,并利用经验和权值中间表进行权值学习。从而提高检索命中率。并将这种模型运用到基于旅游的多策略数据挖掘系统进行实验,结果表明在案例检索的命中率上有明显提高。     

A comparison of predictive measures of problem difficulty inevolutionary algorithms

This paper studies a number of predictive measures of problem difficulty, among which epistasis variance and fitness distance correlation are the most widely known. Our approach is based on comparing the reference class of a measure to a number of known easy function classes. First, we generalize the reference classes of fitness distance correlation and epistasis variance, and construct a new predictive measure that is insensitive to nonlinear fitness scaling. We then investigate the relations between the reference classes of the measures and a number of intuitively easy classes. We also point out the need to further identify which functions are easy for a given class of evolutionary algorithms in order to design more efficient hardness indicators for them. We finally restrict attention to the genetic algorithm (GA), and consider both GA-easy and GA-hard fitness functions, and give experimental evidence that the values of the measures, based on random samples, can be completely unreliable and entirely uncorrelated to the convergence quality and convergence speed of GA instances using either proportional or ranking selection     

基于改进的遗传算法的有刷直流电机PID参数整定

针对有刷直流（DC）电机的比例积分微分（PID）参数整定工作复杂耗时的问题,提出了一种基于改进型遗传算法（GA）的PID参数整定方法。首先,提出了适应度增强淘汰法则,改进了传统GA的选择过程;然后,提出了基因感染交叉方法,保证了进化过程中平均适应度值的增加;最后,删除了传统GA中不必要的复制操作,提升了算法的运行速度。通过电机传递函数进行建模和仿真分析。实验结果表明,与常规整定方法相比,所提改进型GA能够显著提升PID参数整定效果,且改进型GA相较于传统GA,达到同样进化效果所需的进化代数减少了79%,算法运行速度提升了4.1%。所提出的改进型GA从选择和交叉两个关键操作步骤对GA进行了改进,并应用于PID参数整定使得上升时间更少、稳定时间更短、过冲更小。     

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

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

结合语义与事务属性的QoS感知的服务优化选择

服务级别协议（SLA）等级感知的服务选择是NP难题。针对服务选择中维度与粒度方面的问题,提出结合语义与事务属性的服务质量（QoS）感知的服务优化选择模型。该模型从语义链接匹配度、QoS与事务三个维度对服务进行优化选择,并设计了支持多粒度的编码策略。针对服务选择中时间复杂度高的问题,提出了克隆选择与遗传算法相结合的混合优化算法。该算法首先采用动态适应度函数,逐代淘汰不满足约束的个体;其次给出了事务属性的优先级,并根据优先级设计了知识启发式的交叉与变异算子,以保证个体满足事务属性要求;最后在遗传算法中对优秀个体进行克隆选择,以增强对最优解的搜索能力。仿真实验中,该算法在服务选择的精确度和成功率方面均优于遗传算法;在时间花费上稍高于遗传算法但远低于穷举法。实验结果表明,所提算法能在较少时间花费的基础上保证服务选择的质量。     

A genetic algorithm with memory for mixed discrete-continuous design optimization

This paper describes a new approach for reducing the number of the fitness function evaluations required by a genetic algorithm (GA) for optimization problems with mixed continuous and discrete design variables. The proposed additions to the GA make the search more effective and rapidly improve the fitness value from generation to generation. The additions involve memory as a function of both discrete and continuous design variables, multivariate approximation of the fitness function in terms of several continuous design variables, and localized search based on the multivariate approximation. The approximation is demonstrated for the minimum weight design of a composite cylindrical shell with grid stiffeners.     

序的分类预测在进化算法中的应用

昂贵优化问题的求解往往伴随着计算成本灾难, 为了减少目标函数的真实评估次数, 将序预测方法用于进化算法中候选解的选取. 通过分类预测直接得到候选解的相对优劣关系, 避免了对目标函数建立精确代理模型的需求, 并且设计了序样本集约简方法, 以降低序样本集的冗余性, 提高序预测模型的训练效率. 接下来, 将序预测与遗传算法相结合. 序预测辅助遗传算法在昂贵优化测试函数上的仿真实验表明, 序预测方法可有效降低求解昂贵优化问题时的计算成本.     

Improving surrogate-assisted variable fidelity multi-objective optimization using a clustering algorithm

Surrogate-assisted evolutionary optimization has proved to be effective in reducing optimization time, as surrogates, or meta-models can approximate expensive fitness functions in the optimization run. While this is a successful strategy to improve optimization efficiency, challenges arise when constructing surrogate models in higher dimensional function space, where the trade space between multiple conflicting objectives is increasingly complex. This complexity makes it difficult to ensure the accuracy of the surrogates. In this article, a new surrogate management strategy is presented to address this problem. A k-means clustering algorithm is employed to partition model data into local surrogate models. The variable fidelity optimization scheme proposed in the author's previous work is revised to incorporate this clustering algorithm for surrogate model construction. The applicability of the proposed algorithm is illustrated on six standard test problems. The presented algorithm is also examined in a three-objective stiffened panel optimization design problem to show its superiority in surrogate-assisted multi-objective optimization in higher dimensional objective function space. Performance metrics show that the proposed surrogate handling strategy clearly outperforms the single surrogate strategy as the surrogate size increases.     

自适应遗传退火算法优化BP神经网络及其应用

以提高预测软件老化趋势为应用背景,提出一种新型自适应遗传退火算法（NAGSA）优化BP神经网络模型,该模型采用轮盘赌选择法与精英保留策略相结合的选择算子,在迭代后期通过模拟退火算法对适应度函数进行拉伸,相比传统的自适应遗传算法（AGA）在个体适应度较低时,能够非线性地自适应调节交叉概率和变异概率,从而对BP神经网络的权值和阈值优化并进行网络训练.对在线售书网站注入内存泄漏的代码使之老化,收集实验所需的老化数据进行仿真训练,实验结果表明,NAGSA-BP模型相比于传统遗传算法（GA）、传统自适应遗传算法（AGA）、传统自适应遗传退火算法（NGSA）优化的BP神经网络模型提高了预测精度和取得了优良的收敛效果,在该应用领域验证了本文方法的有效性.