Order statistics and region-based evolutionary computation

Trust region algorithms are well known in the field of local continuous optimization. They proceed by maintaining a confidence region in which a simple, most often quadratic, model is substituted to the criterion to be minimized. The minimum of the model in the trust region becomes the next starting point of the algorithm and, depending on the amount of progress made during this step, the confidence region is expanded, contracted or kept unchanged. In the field of global optimization, interval programming may be thought as a kind of confidence region approach, with a binary confidence level: the region is guaranteed to contain the optimum or guaranteed to not contain it. A probabilistic version, known as branch and probability bound, is based on an approximate probability that a region of the search space contains the optimum, and has a confidence level in the interval [0,1]. The method introduced in this paper is an application of the trust region approach within the framework of evolutionary algorithms. Regions of the search space are endowed with a prospectiveness criterion obtained from random sampling possibly coupled with a local continuous algorithm. The regions are considered as individuals for an evolutionary algorithm with mutation and crossover operators based on a transformation group. The performance of the algorithm on some standard benchmark functions is presented.     

Heuristic methods for evolutionary computation techniques

Evolutionary computation techniques, which are based on a powerful principle of evolution—survival of the fittest, constitute an interesting category of heuristic search. In other words, evolutionary techniques are stochastic algorithms whose search methods model some natural phenomena: genetic inheritance and Darwinian strife for survival.Any evolutionary algorithm applied to a particular problem must address the issue of genetic representation of solutions to the problem and genetic operators that would alter the genetic composition of offspring during the reproduction process. However, additional heuristics should be incorporated in the algorithm as well; some of these heuristic rules provide guidelines for evaluating (feasible and infeasible) individuals in the population. This paper surveys such heuristics and discusses their merits and drawbacks.An abridged version of this paper appears in the volume entitled META-HEURISTICS: Theory & Application, edited by Ibrahim H. Osman and James P. Kelly, to be published by Kluwer Academic Publishers in March 1996.     

A review on probabilistic graphical models in evolutionary computation

Thanks to their inherent properties, probabilistic graphical models are one of the prime candidates for machine learning and decision making tasks especially in uncertain domains. Their capabilities, like representation, inference and learning, if used effectively, can greatly help to build intelligent systems that are able to act accordingly in different problem domains. Evolutionary algorithms is one such discipline that has employed probabilistic graphical models to improve the search for optimal solutions in complex problems. This paper shows how probabilistic graphical models have been used in evolutionary algorithms to improve their performance in solving complex problems. Specifically, we give a survey of probabilistic model building-based evolutionary algorithms, called estimation of distribution algorithms, and compare different methods for probabilistic modeling in these algorithms.     

Distributing evolutionary computation in a networked multi-agent environment

It has become increasingly popular to employ evolutionary algorithms to solve problems in different domains, and parallel models have been widely used for performance enhancement. Instead of using parallel computing facilities or public computing systems to speed up the computation, we propose to implement parallel evolutionary computation models on networked personal computers (PCs) that are locally available and manageable. To realize the parallelism, a multi-agent system is presented in which mobile agents play the major roles to carry the code and move from machine to machine to complete the computation dynamically. To evaluate the proposed approach, we use our multi-agent system to solve two types of time-consuming applications. Different kinds of experiments were conducted to assess the developed system, and the preliminary results show its promise and efficiency.     

A local linear embedding module for evolutionary computation optimization

A Local Linear Embedding (LLE) module enhances the performance of two Evolutionary Computation (EC) algorithms employed as search tools in global optimization problems. The LLE employs the stochastic sampling of the data space inherent in Evolutionary Computation in order to reconstruct an approximate mapping from the data space back into the parameter space. This allows to map the target data vector directly into the parameter space in order to obtain a rough estimate of the global optimum, which is then added to the EC generation. This process is iterated and considerably improves the EC convergence. Thirteen standard test functions and two real-world optimization problems serve to benchmark the performance of the method. In most of our tests, optimization aided by the LLE mapping outperforms standard implementations of a genetic algorithm and a particle swarm optimization. The number and ranges of functions we tested suggest that the proposed algorithm can be considered as a valid alternative to traditional EC tools in more general applications. The performance improvement in the early stage of the convergence also suggests that this hybrid implementation could be successful as an initial global search to select candidates for subsequent local optimization.     

The theory and computation of evolutionary distances: Pattern recognition

A method of finding pattern similarities between two sequences is given. Two portions, one from each sequence, are similar if they are close in the metric space of evolutionary distances. The method allows a complete list to be made of all pairs of intervals, one from each of two given sequences, such that each pair displays a maximum local degree of similarity, and, if the lengths of the given sequences are m and n, then the procedure takes on the order of mn computational steps. This result lends itself to finding similarities by computer between pairs of biological sequences, such as proteins and nucleic acids.     

Solving multiobjective vehicle routing problem with stochastic demand via evolutionary computation

This paper considers the routing of vehicles with limited capacity from a central depot to a set of geographically dispersed customers where actual demand is revealed only when the vehicle arrives at the customer. The solution to this vehicle routing problem with stochastic demand (VRPSD) involves the optimization of complete routing schedules with minimum travel distance, driver remuneration, and number of vehicles, subject to a number of constraints such as time windows and vehicle capacity. To solve such a multiobjective and multi-modal combinatorial optimization problem, this paper presents a multiobjective evolutionary algorithm that incorporates two VRPSD-specific heuristics for local exploitation and a route simulation method to evaluate the fitness of solutions. A new way of assessing the quality of solutions to the VRPSD on top of comparing their expected costs is also proposed. It is shown that the algorithm is capable of finding useful tradeoff solutions for the VRPSD and the solutions are robust to the stochastic nature of the problem. The developed algorithm is further validated on a few VRPSD instances adapted from Solomon’s vehicle routing problem with time windows (VRPTW) benchmark problems.     

Convex hull-based multi-objective evolutionary computation for maximizing receiver operating characteristics performance

The receiver operating characteristics (ROC) analysis has gained increasing popularity for analyzing the performance of classifiers. In particular, maximizing the convex hull of a set of classifiers in the ROC space, namely ROCCH maximization, is becoming an increasingly important problem. In this work, a new convex hull-based evolutionary multi-objective algorithm named ETriCM is proposed for evolving neural networks with respect to ROCCH maximization. Specially, convex hull-based sorting with convex hull of individual minima (CH-CHIM-sorting) and extreme area extraction selection (EAE-selection) are proposed as a novel selection operator. Empirical studies on 7 high-dimensional and imbalanced datasets show that ETriCM outperforms various state-of-the-art algorithms including convex hull-based evolutionary multi-objective algorithm (CH-EMOA) and non-dominated sorting genetic algorithm II (NSGA-II).     

An efficient sensitivity computation strategy for the evolutionary structural optimization (ESO) of continuum structures subjected to self-weight loads

This work presents a modified version of the evolutionary structural optimization procedure for topology optimization of continuum structures subjected to self-weight forces. Here we present an extension of this procedure to deal with maximum stiffness topology optimization of structures when different combinations of body forces and fixed loads are applied. Body forces depend on the density distribution over the design domain. Therefore, the value and direction of the loading are coupled to the shape of the structure and they change as the material layout of the structure is modified in the course of the optimization process. It will be shown that the traditional calculation of the sensitivity number used in the ESO procedure does not lead to the optimum solution. Therefore, it is necessary to correct the computation of the element sensitivity numbers in order to achieve the optimum design. This paper proposes an original correction factor to compute the sensitivities and enhance the convergence of the algorithm. The procedure has been implemented into a general optimization software and tested in several numerical applications and benchmark examples to illustrate and validate the approach, and satisfactorily applied to the solution of 2D, 3D and shell structures, considering self-weight load conditions. Solutions obtained with this method compare favourably with the results derived using the SIMP interpolation scheme.     

A note on the computation of the CP-rank

The purpose of this note is to address the computational question of determining whether or not a square nonnegative matrix (over the reals) is completely positive and finding its CP-rank when it is. We show that these questions can be resolved by finite algorithms and we provide (non-polynomial) complexity bounds on the number of arithmetic/Boolean operations that these algorithms require. We state several open questions including the existence of polynomial algorithms to resolve the above problems and availability of algorithms for addressing complete positivity over the rationals and over {0, 1} matrices.     

关于镜面反射矩阵的注记

涉及到矩阵分解时,镜面反射矩阵起着非常重要的作用.讨论镜面反射矩阵的若干性质,给出了镜面反射矩阵一个重要性质的逆命题.即当n阶Hermite矩阵的特征值与镜面反射矩阵的特征值相同时,该Hermite矩阵恰好是一个镜面反射矩阵.     

Notes on the Jacobi equation

We discuss some properties of Jacobi fields that do not involve assumptions on the curvature endomorphism. We compare indices of different spaces of Jacobi fields and give some applications to Riemannian geometry.     

Notes on the bifurcation theorem

We reexamine bifurcation questions for potential operators. Based on the Conley index theory we present a unified approach to bifurcations both at the origin and at infinity. Our results provide improvements of the existing theory.     

Notes on the value function

The properties satisfied by the value function are given. These properties can be used to study the generalized Hamming weight and the relative generalized Hamming weight of certain linear codes.     

On the computation of a-invariants

Thea-invariant of a graded Cohen-Macaulay ring is the least degree of a generator of its graded canonical module. We compute thea-invariants of (i) graded algebras with straightening laws on upper semi-modular lattices and (ii) the Stanley-Reisner rings of shellable weighted simplicial complexes. The formulas obtained are applied to rings defined by determinantal and pfaffian ideals.     

Notes on the Sasaki metric

We survey on the geometry of the tangent bundle of a Riemannian manifold, endowed with the classical metric established by S. Sasaki 60 years ago. Following the results of Sasaki, we try to write and deduce them by different means. Questions of vector fields, mainly those arising from the base, are related as invariants of the classical metric, contact and Hermitian structures. Attention is given to the natural notion of extension or complete lift of a vector field, from the base to the tangent manifold. Few results are original, but finally new equations of the mirror map are considered.     

尺度函数的两个性质

Two properties are given in this paper about the scaling function: suppose Vj; j ∈ Z is a multiresolution analysis with a continuous scaling function φ which have compact support set and that φ the Fourier transform of φ is a continuous real function, compactly supported, then φ(0) ≠ 0 and when supp φ = [a1,b1]∪[a2,b2](b1 < a2,0 < a2), then we havea1 ≤ 0, 0 < b1, a1 < b2/2 ≤ b1, 2π < b2 - a1 ≤ 8π.     

Notes on “Notes on conditional previsions”

These notes comment on Williams’ fundamental essay Notes on Conditional Previsions, written as a research report in 1975 and published in the present issue. Basic aspects of that work are discussed, including historical background and relevance to the foundations of probability; examples are supplied to help understanding.     

Notes on the Duren-Leung conjecture

For the logarithmic coefficients γn of a univalent function f(z)=z+a₂z²+?∈S, the well-known de Branges' theorem shows that