On the effect of selection in genetic algorithms

To study the effect of selection with respect to mutation and mating in genetic algorithms, we consider two simplified examples in the infinite population limit. Both algorithms are modeled as measure valued dynamical systems and are designed to maximize a linear fitness on the half line. Thus, they both trivially converge to infinity. We compute the rate of their growth and we show that, in both cases, selection is able to overcome a tendency to converge to zero. The first model is a mutation‐selection algorithm on the integer half line, which generates mutations along a simple random walk. We prove that the system goes to infinity at a positive speed, even in cases where the random walk itself is ergodic. This holds in several strong senses, since we show a.s. convergence, L^p convergence, convergence in distribution, and a large deviations principle for the sequence of measures. For the second model, we introduce a new class of matings, based upon Mandelbrot martingales. The mean fitness of the associated mating‐selection algorithms on the real half line grows exponentially fast, even in cases where the Mandelbrot martingale itself converges to zero. © 2001 John Wiley & Sons, Inc. Random Struct. Alg., 18: 185–200, 2001     

混合遗传算法收敛性分析

针对遗传算法爬山能力弱但合局搜索能力强的特点 ,本文将遗传算法嵌入到基入传统优化的拟下降算法中 ,并对算法的拟下降步骤做了一定的改进 ,使得整个算法具有全局收敛性 .本文采用马尔可夫的观点进一步证明了算法的全局收敛性 ,并用极难优化的测试函数给出了数值算例 ,证明了本文算法为一种可行的全局优化算法 .     

An evolutionary artificial immune system for multi-objective optimization

In this paper, an evolutionary artificial immune system for multi-objective optimization which combines the global search ability of evolutionary algorithms and immune learning of artificial immune systems is proposed. A new selection strategy is developed based upon the concept of clonal selection principle to maintain the balance between exploration and exploitation. In order to maintain a diverse repertoire of antibodies, an information-theoretic based density preservation mechanism is also presented. In addition, the performances of various multi-objective evolutionary algorithms as well as the effectiveness of the proposed features are examined based upon seven benchmark problems characterized by different difficulties in local optimality, non-uniformity, discontinuity, non-convexity, high-dimensionality and constraints. The comparative study shows the effectiveness of the proposed algorithm, which produces solution sets that are highly competitive in terms of convergence, diversity and distribution. Investigations also demonstrate the contribution and robustness of the proposed features.     

Local elimination algorithms for solving sparse discrete problems

The class of local elimination algorithms is considered that make it possible to obtain global information about solutions of a problem using local information. The general structure of local elimination algorithms is described that use neighborhoods of elements and the structural graph describing the problem structure; an elimination algorithm is also described. This class of algorithms includes local decomposition algorithms for discrete optimization problems, nonserial dynamic programming algorithms, bucket elimination algorithms, and tree decomposition algorithms. It is shown that local elimination algorithms can be used for solving optimization problems.     

Multidimensional Optimization with a Fuzzy Genetic Algorithm

We present a new heuristic method to approximate the set of Pareto-optimal solutions in multicriteria optimization problems. We use genetic algorithms with an adaptive selection mechanism. The direction of the selection pressure is adapted to the actual state of the population and forces it to explore a broad range of so far undominated solutions. The adaptation is done by a fuzzy rule-based control of the selection procedure and the fitness function. As an application we present a timetable optimization problem where we used this method to derive cost-benefit curves for the investment into railway nets. These results show that our fuzzy adaptive approach avoids most of the empirical shortcomings of other multiobjective genetic algorithms.     

多种分布下选择后变量显著性分析及其在CEPS数据中的应用

在使用变量选择方法选出模型后,如何评价模型中变量系数的显著性是统计学重点关注的前沿问题之一.文章从适应性Lasso变量选择方法的选择结果出发,在考虑实践中误差分布多样性的前提下,基于选择事件构造了模型保留变量系数的条件检验统计量,并给出了该统计量的一致收敛性质的证明过程.模拟研究显示,在多种误差分布下所提方法均可进一步优化变量选择结果,有较强的实用价值.应用此方法对CEPS学生数据进行了实证分析,最终选取了学生认知能力等10个变量作为影响中学生成绩的主要因素,为相关研究提供了有益的参考.     

Chaos optimization algorithms based on chaotic maps with different probability distribution and search speed for global optimization

Chaos optimization algorithms (COAs) usually utilize the chaotic map like Logistic map to generate the pseudo-random numbers mapped as the design variables for global optimization. Many existing researches indicated that COA can more easily escape from the local minima than classical stochastic optimization algorithms. This paper reveals the inherent mechanism of high efficiency and superior performance of COA, from a new perspective of both the probability distribution property and search speed of chaotic sequences generated by different chaotic maps. The statistical property and search speed of chaotic sequences are represented by the probability density function (PDF) and the Lyapunov exponent, respectively. Meanwhile, the computational performances of hybrid chaos-BFGS algorithms based on eight one-dimensional chaotic maps with different PDF and Lyapunov exponents are compared, in which BFGS is a quasi-Newton method for local optimization. Moreover, several multimodal benchmark examples illustrate that, the probability distribution property and search speed of chaotic sequences from different chaotic maps significantly affect the global searching capability and optimization efficiency of COA. To achieve the high efficiency of COA, it is recommended to adopt the appropriate chaotic map generating the desired chaotic sequences with uniform or nearly uniform probability distribution and large Lyapunov exponent.     

An empirical study on similarity-based mating for evolutionary multiobjective combinatorial optimization

We have already proposed a similarity-based mating scheme to recombine extreme and similar parents for evolutionary multiobjective optimization. In this paper, we examine the effect of the similarity-based mating scheme on the performance of evolutionary multiobjective optimization (EMO) algorithms. First we examine which is better between recombining similar or dissimilar parents. Next we examine the effect of biasing selection probabilities toward extreme solutions that are dissimilar from other solutions in each population. Then we examine the effect of dynamically changing the strength of this bias during the execution of EMO algorithms. Computational experiments are performed on a wide variety of test problems for multiobjective combinatorial optimization. Experimental results show that the performance of EMO algorithms can be improved by the similarity-based mating scheme for many test problems.     

父代种群参与竞争遗传算法几乎必然收敛

熟知,标准遗传算法如不采用“杰出者记录策略”则必不收敛。本文发现：允许父代种群参与竞争是标准遗传算法几乎必然收敛的条件。特别地,我们运用鞅收敛定理证明：允许父代种群参与竞争型遗传算法能以概率1确保在限步内达到全局最优解,且收敛与种群规模无关。所获结果对该类遗传算法的应用奠定了可靠基础。     

Trajectory-following algorithms for min-max optimization problems

In this paper, we consider a class of nonlinear minimum-maximum optimization problems subject to boundedness constraints on the decision vectors. Three algorithms are developed for finding the min-max point using the concept of solving an associated dynamical system. In the first and third algorithms, solutions are obtained by solving systems of differential equations. The second algorithm is a discrete version of the first algorithm. The trajectories generated by the first and second algorithms may move inside or on the boundary of the constraint set, while the third algorithm ensures that any trajectory that begins inside the constraint region remains in its interior. Sufficient conditions for global convergence of the two algorithms are also established. For illustration, four numerical examples are solved.This work was partially supported by a research grant from the Australian Research Committee.     

Maximization of submodular functions: Theory and enumeration algorithms

Submodular functions are powerful tools to model and solve either to optimality or approximately many operational research problems including problems defined on graphs. After reviewing some long-standing theoretical results about the structure of local and global maxima of submodular functions, Cherenin’s selection rules and his Dichotomy Algorithm, we revise the above mentioned theory and show that our revision is useful for creating new non-binary branching algorithms and finding either approximation solutions with guaranteed accuracy or exact ones.     

A Hybrid Genetic Algorithm with Boltzmann Convergence Properties

Stochastic global search algorithms such as genetic algorithms are used to attack difficult combinatorial optimization problems. However, genetic algorithms suffer from the lack of a convergence proof. This means that it is difficult to establish reliable algorithm braking criteria without extensive a priori knowledge of the solution space. The hybrid genetic algorithm presented here combines a genetic algorithm with simulated annealing in order to overcome the algorithm convergence problem. The genetic algorithm runs inside the simulated annealing algorithm and provides convergence via a Boltzmann cooling process. The hybrid algorithm was used successfully to solve a classical 30-city traveling salesman problem; it consistently outperformed both a conventional genetic algorithm and a conventional simulated annealing algorithm. This work was supported by the University of Colorado at Colorado Springs.     

基于种群自适应调整的多目标差分进化算法

为提高已有多目标进化算法在求解复杂多目标优化问题上的收敛性和解集分布性,提出一种基于种群自适应调整的多目标差分进化算法。该算法设计一个种群扩增策略,它在决策空间生成一些新个体帮助搜索更优的非支配解;设计了一个种群收缩策略,它依据对非支配解集的贡献程度淘汰较差的个体以减少计算负荷,并预留一些空间给新的带有种群多样性的扰动个体;引入精英学习策略,防止算法陷入局部收敛。通过典型的多目标优化函数对算法进行测试验证,结果表明所提算法相对于其他算法具有明显的优势,其性能优越,能够在保证良好收敛性的同时,使获得的Pareto最优解集具有更均匀的分布性和更广的覆盖范围,尤其适合于高维复杂多目标优化问题的求解。     

稳健L_q(0<q<1)正则化理论:解的渐近分布与变量选择一致性

本文提出稳健Lq(0q∞)正则化模型,证明该模型解的全局渐近分布定理.应用该定理可进一步证明当0q1时所提出的模型具有变量选择一致性,从而具有良好的变量选择能力.基于所获得的理论结果,提出一类求解该模型的无参量加权迭代算法,并给出相应的正则化参数选择策略.数值试验表明本文提出的模型与算法可行、有效,有广泛的应用价值.     

A hybrid method for solving multi-objective global optimization problems

Real optimization problems often involve not one, but multiple objectives, usually in conflict. In single-objective optimization there exists a global optimum, while in the multi-objective case no optimal solution is clearly defined but rather a set of optimums, which constitute the so called Pareto-optimal front. Thus, the goal of multi-objective strategies is to generate a set of non-dominated solutions as an approximation to this front. However, most problems of this kind cannot be solved exactly because they have very large and highly complex search spaces. The objective of this work is to compare the performance of a new hybrid method here proposed, with several well-known multi-objective evolutionary algorithms (MOEA). The main attraction of these methods is the integration of selection and diversity maintenance. Since it is very difficult to describe exactly what a good approximation is in terms of a number of criteria, the performance is quantified with adequate metrics that evaluate the proximity to the global Pareto-front. In addition, this work is also one of the few empirical studies that solves three-objective optimization problems using the concept of global Pareto-optimality.     

阶梯状黄土边坡稳定性分析的改进遗传算法及应用

阶梯状黄土边坡稳定性分析的关键是估算其稳定系数的最小值.稳定系数的求解涉及诸多因素且计算过程繁杂,传统优化算法往往不能有效地搜索到其全局最小解.为此,提出一种改进的自适应遗传算法.算法对基因变量空间进行网格状划分,采用迭代选优法建立均匀分布的初始种群,运用优质个体保留遗传策略,并按照特定的准则自适应地调整交叉概率和变异概率,提高算法的全局搜索能力和收敛速度.实例应用表明算法能够快速有效地收敛于土坡稳定系数的全局最小解,且计算结果与实际情况更加吻合.     

An estimation of distribution algorithm for nurse scheduling

Schedules can be built in a similar way to a human scheduler by using a set of rules that involve domain knowledge. This paper presents an Estimation of Distribution Algorithm (EDA) for the nurse scheduling problem, which involves choosing a suitable scheduling rule from a set for the assignment of each nurse. Unlike previous work that used Genetic Algorithms (GAs) to implement implicit learning, the learning in the proposed algorithm is explicit, i.e. we identify and mix building blocks directly. The EDA is applied to implement such explicit learning by building a Bayesian network of the joint distribution of solutions. The conditional probability of each variable in the network is computed according to an initial set of promising solutions. Subsequently, each new instance for each variable is generated by using the corresponding conditional probabilities, until all variables have been generated, i.e. in our case, a new rule string has been obtained. Another set of rule strings will be generated in this way, some of which will replace previous strings based on fitness selection. If stopping conditions are not met, the conditional probabilities for all nodes in the Bayesian network are updated again using the current set of promising rule strings. Computational results from 52 real data instances demonstrate the success of this approach. It is also suggested that the learning mechanism in the proposed approach might be suitable for other scheduling problems.     

Algorithms for solving nonlinear dynamic decision models

In this paper we discuss two Newton-type algorithms for solving economic models. The models are preprocessed by reordering the equations in order to minimize the dimension of the simultaneous block. The solution algorithms are then applied to this block. The algorithms evaluate numerically, as required, selected columns of the Jacobian of the simultaneous part. Provisions also exist for similar systems to be solved, if possible, without actually reinitialising the Jacobian. One of the algorithms also uses the Broyden update to improve the Jacobian. Global convergence is maintained by an Armijo-type stepsize strategy.The global and local convergence of the quasi-Newton algorithm is discussed. A novel result is established for convergence under relaxed descent directions and relating the achievement of unit stepsizes to the accuracy of the Jacobian approximation. Furthermore, a simple derivation of the Dennis-Moré characterisation of the Q-superlinear convergence rate is given.The model equation reordering algorithm is also described. The model is reordered to define heart and loop variables. This is also applied recursively to the subgraph formed by the loop variables to reduce the total number of above diagonal elements in the Jacobian of the complete system. The extension of the solution algorithms to consistent expectations are discussed. The algorithms are compared with Gauss-Seidel SOR algorithms using the USA and Spanish models of the OECD Interlink system.     

Parameter-setting-free harmony search algorithm

Various phenomenon-mimicking algorithms, such as genetic algorithm, simulated annealing, tabu search, ant colony optimization, and particle swarm optimization, have their own algorithm parameters. These parameters need to be skillfully assigned in order to obtain good results. It is burdensome, especially to novice users, to assign these parameters. The same is true for the harmony search algorithm which was inspired by music performance. Thus, this study proposes a novel technique to eliminate tedious and experience-requiring parameter assigning efforts. The new parameter-setting-free (PSF) technique which this study suggests contains one additional matrix which contains an operation type (random selection, memory consideration, or pitch adjustment) for every variable in harmony memory. Three examples illustrate that the PSF technique can find good solutions robustly.     

Box-constrained minimization reformulations of complementarity problems in second-order cones

Reformulations of a generalization of a second-order cone complementarity problem (GSOCCP) as optimization problems are introduced, which preserve differentiability. Equivalence results are proved in the sense that the global minimizers of the reformulations with zero objective value are solutions to the GSOCCP and vice versa. Since the optimization problems involved include only simple constraints, a whole range of minimization algorithms may be used to solve the equivalent problems. Taking into account that optimization algorithms usually seek stationary points, a theoretical result is established that ensures equivalence between stationary points of the reformulation and solutions to the GSOCCP. Numerical experiments are presented that illustrate the advantages and disadvantages of the reformulations. Supported by FAPESP (01/04597-4), CNPq, PRONEX-Optimization, FAEPEX-Unicamp.