基于统计引导和多项式差分学习的樽海鞘优化算法

樽海鞘优化算法相较于传统的群体智能优化算法,具有较好的鲁棒性和寻优能力。但仍存在全局寻优能力有限、执行效率不够高、易陷入局部极值的缺陷。针对上述问题,本文提出一种新的多项式差分学习策略,以区分和改进传统的线性差分方法;并设计一种随机种群划分方式,使得信息可以在邻域拓扑内均匀传递;另外,本文定义多项式差分学习的全局探索算子和局部开发算子,引入统计引导系数A,开启不同的多项式学习方法,从而进一步提高算法的全局搜索能力和寻优精度。最后,本文通过标准测试函数和实际应用问题的对比检验,证实了改进算法的优越性和鲁棒性,拓展和丰富了原算法的应用范围。     

基于免疫算法的组合预测方法

利用免疫算法搜索全局最优解能力,提出了一种其于免疫算法的组合预测权系数确定的新方法,并给出了具体算法.仿真实验结果表明了免疫算法在组合预测方面具有很好的可行性和有效性.     

Lamarckian memetic algorithms: local optimum and connectivity structure analysis

Memetic algorithms (MAs) represent an emerging field that has attracted increasing research interest in recent times. Despite the popularity of the field, we remain to know rather little of the search mechanisms of MAs. Given the limited progress made on revealing the intrinsic properties of some commonly used complex benchmark problems and working mechanisms of Lamarckian memetic algorithms in general non-linear programming, we introduce in this work for the first time the concepts of local optimum structure and generalize the notion of neighborhood to connectivity structure for analysis of MAs. Based on the two proposed concepts, we analyze the solution quality and computational efficiency of the core search operators in Lamarckian memetic algorithms. Subsequently, the structure of local optimums of a few representative and complex benchmark problems is studied to reveal the effects of individual learning on fitness landscape and to gain clues into the success or failure of MAs. The connectivity structure of local optimum for different memes or individual learning procedures in Lamarckian MAs on the benchmark problems is also investigated to understand the effects of choice of memes in MA design.     

Hybrid evolutionary algorithm with Hermite radial basis function interpolants for computationally expensive adjoint solvers

In this paper, we present an evolutionary algorithm hybridized with a gradient-based optimization technique in the spirit of Lamarckian learning for efficient design optimization. In order to expedite gradient search, we employ local surrogate models that approximate the outputs of a computationally expensive Euler solver. Our focus is on the case when an adjoint Euler solver is available for efficiently computing the sensitivities of the outputs with respect to the design variables. We propose the idea of using Hermite interpolation to construct gradient-enhanced radial basis function networks that incorporate sensitivity data provided by the adjoint Euler solver. Further, we conduct local search using a trust-region framework that interleaves gradient-enhanced surrogate models with the computationally expensive adjoint Euler solver. This ensures that the present hybrid evolutionary algorithm inherits the convergence properties of the classical trust-region approach. We present numerical results for airfoil aerodynamic design optimization problems to show that the proposed algorithm converges to good designs on a limited computational budget.     

Customized simulated annealing based decision algorithms for combinatorial optimization in VLSI floorplanning problem

Modern very large scale integration technology is based on fixed-outline floorplan constraints, mostly with an objective of minimizing area and wirelength between the modules. The aim of this work is to minimize the unused area, that is, dead space in the floorplan, in addition to these objectives. In this work, a Simulated Annealing Algorithm (SAA) based heuristic, namely Simulated Spheroidizing Annealing Algorithm (SSAA) has been developed and improvements in the proposed heuristic algorithm is also suggested to improve its performance. Exploration capability of the proposed algorithm is due to the mechanism of reducing the uphill moves made during the initial stage of the algorithm, extended search at each temperature and the improved neighborhood search procedure. The proposed algorithm has been tested using two kinds of benchmarks: Microelectronics Center of North Carolina (MCNC) and Gigascale Systems Research Center (GSRC). The performance of the proposed algorithm is compared with that of other stochastic algorithms reported in the literature and is found to be efficient in producing floorplans with very minimal dead space. The proposed SSAA algorithm is also found more efficient for problems of larger sizes.     

基于免疫记忆克隆算法的指数化投资组合优化构建策略

本文基于克隆选择学说及基于克隆选择学说及生物免疫响应过程的相关机理,提出用于指数化投资的免疫记忆克隆算法,并将其应用于指数化投资组合优化构建模型的求解,旨在探索指数化投资的优化构建策略。文章首先提出多目标的指数化投资组合构建模型。其次,分别设计了适用于指数化投资组合构建策略的抗原、抗体、亲和度函数、克隆选择算子、免疫记忆算子和相应的进化算法。该算法有效避免了传统遗传算法所存在的计算后期解的多样性差、易早熟以及收敛速度慢等缺点。同时,提出了限制投资组合中股票数量的启发式算法。最后,使用包括上证180指数在内的6组世界主要股票市场指数及其成份股的历史数据对模型及算法进行测算,结果表明算法具有良好的求解能力和收敛速度,所建模型的合理性和有效性亦被论证,模型和算法均具有很强的实践价值;     

Fireworks algorithm framework for Big Data optimization

This paper presents a novel optimization framework based on the Fireworks Algorithm for Big Data Optimization problems. Indeed, the proposed framework is composed of two optimization algorithms. A single objective Fireworks Algorithm and a multi-objective Fireworks Algorithm are proposed for solving the Big Optimization of Signals problem “Big-OPT” which belongs to the Big Data Optimization problems class. The single objective Fireworks Algorithm adopts a modified search mechanism to ensure rapidity and preserve the explorative capacities of the basic Fireworks Algorithm. Afterward, the algorithm is extended to handle multi-objective optimization of Big-OPT with a supplementary special sparks phase and a novel strategy for next generation selection. To validate the performance of the framework, extensive tests on six EEG datasets are performed. The framework is also compared with several approaches from recent state of the art. The study concludes the competitive performance of the proposed framework in comparison with the other techniques reported in this paper.     

A tabu search scheme for abstract problems, with applications to the computation of fixed points

We present a general tabu search iterative algorithm to solve abstract problems on metric spaces. At each iteration, if the current solution turns out to be unacceptable then a neighborhood of unacceptable solutions is determined and excluded for further exploration, in such a way that, under mild assumptions, an acceptable solution is asymptotically reached. Thus our algorithm makes a crucial use of memory to avoid visiting unacceptable solutions more than once. We also present a specialization of our general method to the computation of fixed points.     

Square-root variable-metric methods for minimization

Variable-metric methods are presented which do not need an accurate one-dimensional search and eliminate roundoff error problems which can occur in updating the metric for large-dimension systems. The methods are based on updating the square root of the metric, so that a positive-definite metric always results. The disadvantage of intentionally relaxing the accuracy of the one-dimensional search is that the number of iterations (and hence, gradient evaluations) increases. For problems involving a large number of variables, the square-root method is presented in a triangular form to reduce the amount of computation. Also, for usual optimization problems, the square-root procedure can be carried out entirely in terms of the metric, eliminating storage and computer time associated with computations of the square root of the metric.     

Dynamic algorithm selection for pareto optimal set approximation

This paper presents a meta-algorithm for approximating the Pareto optimal set of costly black-box multiobjective optimization problems given a limited number of objective function evaluations. The key idea is to switch among different algorithms during the optimization search based on the predicted performance of each algorithm at the time. Algorithm performance is modeled using a machine learning technique based on the available information. The predicted best algorithm is then selected to run for a limited number of evaluations. The proposed approach is tested on several benchmark problems and the results are compared against those obtained using any one of the candidate algorithms alone.     

An improved partial enumeration algorithm for integer programming problems

In this paper, we present an improved Partial Enumeration Algorithm for Integer Programming Problems by developing a special algorithm, named PE_SPEEDUP (partial enumeration speedup), to use whatever explicit linear constraints are present to speedup the search for a solution. The method is easy to understand and implement, yet very effective in dealing with many integer programming problems, including knapsack problems, reliability optimization, and spare allocation problems. The algorithm is based on monotonicity properties of the problem functions, and uses function values only; it does not require continuity or differentiability of the problem functions. This allows its use on problems whose functions cannot be expressed in closed algebraic form. The reliability and efficiency of the proposed PE_SPEEDUP algorithm has been demonstrated on some integer optimization problems taken from the literature.     

Algorithm robust for the bicriteria discrete optimization problem

We apply Algorithm Robust to various problems in multiple objective discrete optimization. Algorithm Robust is a general procedure that is designed to solve bicriteria optimization problems. The algorithm performs a weight space search in which the weights are utilized in min-max type subproblems. In this paper, we experiment with Algorithm Robust on the bicriteria knapsack problem, the bicriteria assignment problem, and the bicriteria minimum cost network flow problem. We look at a heuristic variation that is based on controlling the weight space search and has an indirect control on the sample of efficient solutions generated. We then study another heuristic variation which generates samples of the efficient set with quality guarantees. We report results of computational experiments.     

一种基于进化策略的化学方程式配平新方法

对标准进化策略算法作一改进,根据质量守恒定律和化学方程式左右两边的原子来建立数学模型,将化学方程式配平问题转化为最优化求解问题.改进后的进化策略算法用于最优化求解问题,提出了一种基于进化策略的化学方程式配平新算法.该算法中的初始群体中的个体为整数,通过对群体的进化,来求化学方程式各物质前的最简系数.实验结果表明,这种改进后的进化策略算法能够有效地确定出任意一化学方程式各物质前的最简系数,最终完成化学方程式配平,其目的为任意一化学方程式配平问题提供了一行之有效的新方法.     

Design of computer network topologies: A Vroom Inspired Psychoclonal Algorithm

In the prevailing era of network and communication technology, the problem pertaining to the determination of the most economic way to interconnect nodes while satisfying some reliability and quality of service constraints has been agnized as one of the most intricate and challenging problem for the modern day researchers and practitioners belonging to Communication and Networking community. Motivated by the improved performance of the concepts like proliferation, affinity maturation, receptor editing, etc., over the more prevalent generalized crossover and mutation; and by the application and effectiveness of Maslow’s need hierarchy in combinatorial optimization as well the more logical motivational concepts provided by Vroom’s valence expectancy theory, authors have proposed and investigated their applications to the topological design of distributed packet switched networks. The extensive computations over the problems of varying complexities and dimensions prove the superiority of the proposed methodology. It has been observed that the proposed Vroom Inspired Psychoclonal Algorithm (VIPA) outperforms the traditional well established random search algorithms (i.e. Genetic Algorithm, Simulated Annealing and Artificial Immune Systems) in the context of underlying problem; the performance being significantly improved as the problem complexity increases.     

A Novel Bat Algorithm based on Cross Boundary Learning and Uniform Explosion Strategy

Population-based algorithms have been used in many real-world problems. Bat algorithm(BA) is one of the states of the art of these approaches. Because of the super bat,on the one hand, BA can converge quickly; on the other hand, it is easy to fall into local optimum. Therefore, for typical BA algorithms, the ability of exploration and exploitation is not strong enough and it is hard to find a precise result. In this paper, we propose a novel bat algorithm based on cross boundary learning(CBL) and uniform explosion strategy(UES),namely BABLUE in short, to avoid the above contradiction and achieve both fast convergence and high quality. Different from previous opposition-based learning, the proposed CBL can expand the search area of population and then maintain the ability of global exploration in the process of fast convergence. In order to enhance the ability of local exploitation of the proposed algorithm, we propose UES, which can achieve almost the same search precise as that of firework explosion algorithm but consume less computation resource. BABLUE is tested with numerous experiments on unimodal, multimodal, one-dimensional, high-dimensional and discrete problems, and then compared with other typical intelligent optimization algorithms.The results show that the proposed algorithm outperforms other algorithms.     

Derivatives with respect to metrics and applications: subgradient marching algorithm

This paper introduces a subgradient descent algorithm to compute a Riemannian metric that minimizes an energy involving geodesic distances. The heart of the method is the Subgradient Marching Algorithm to compute the derivative of the geodesic distance with respect to the metric. The geodesic distance being a concave function of the metric, this algorithm computes an element of the subgradient in O(N ² log(N)) operations on a discrete grid of N points. It performs a front propagation that computes a subgradient of a discrete geodesic distance. We show applications to landscape modeling and to traffic congestion. Both applications require the maximization of geodesic distances under convex constraints, and are solved by subgradient descent computed with our Subgradient Marching. We also show application to the inversion of travel time tomography, where the recovered metric is the local minimum of a non-convex variational problem involving geodesic distances.     

A diverse human learning optimization algorithm

Human Learning Optimization is a simple but efficient meta-heuristic algorithm in which three learning operators, i.e. the random learning operator, the individual learning operator, and the social learning operator, are developed to efficiently search the optimal solution by imitating the learning mechanisms of human beings. However, HLO assumes that all the individuals possess the same learning ability, which is not true in a real human population as the IQ scores of humans, one of the most important indices of the learning ability of humans, follow Gaussian distribution and increase with the development of society and technology. Inspired by this fact, this paper proposes a Diverse Human Learning Optimization algorithm (DHLO), into which the Gaussian distribution and dynamic adjusting strategy are introduced. By adopting a set of Gaussian distributed parameter values instead of a constant to diversify the learning abilities of DHLO, the robustness of the algorithm is strengthened. In addition, by cooperating with the dynamic updating operation, DHLO can adjust to better parameter values and consequently enhances the global search ability of the algorithm. Finally, DHLO is applied to tackle the CEC05 benchmark functions as well as knapsack problems, and its performance is compared with the standard HLO as well as the other eight meta-heuristics, i.e. the Binary Differential Evolution, Simplified Binary Artificial Fish Swarm Algorithm, Adaptive Binary Harmony Search, Binary Gravitational Search Algorithms, Binary Bat Algorithms, Binary Artificial Bee Colony, Bi-Velocity Discrete Particle Swarm Optimization, and Modified Binary Particle Swarm Optimization. The experimental results show that the presented DHLO outperforms the other algorithms in terms of search accuracy and scalability.     

免疫逃避型粒子群优化算法

针对基本粒子群优化算法容易陷入局部极值的缺陷,提出了一种免疫逃避型粒子群优化算法.其基本思想是将初始粒子群划分为寄生与宿主两个种群以模拟生物寄生行为,对寄生种群的粒子采用精英学习策略,对宿主群的粒子采用探索策略,再引入免疫系统的高频变异对寄生群采用相应的免疫逃避机制,以增强群体逃离局部极值、提高算法的全局寻优能力.采用标准测试函数的实验结果表明,该算法在收敛速度和求解精度方面均有显著改进.     

An efficient algorithm for the computation of the metric average of two intersecting convex polygons, with application to morphing

Motivated by the method for the reconstruction of 3D objects from a set of parallel cross sections, based on the binary operation between 2D sets termed “metric average”, we developed an algorithm for the computation of the metric average between two intersecting convex polygons in 2D. For two 1D sets there is an algorithm for the computation of the metric average, with linear time in the number of intervals in the two 1D sets. The proposed algorithm has linear computation time in the number of vertices of the two polygons. As an application of this algorithm, a new technique for morphing between two convex polygons is developed. The new algorithm performs morphing in a non-intuitive way.     

Serial and parallel simulated annealing and tabu search algorithms for the traveling salesman problem

This paper describes serial and parallel implementations of two different search techniques applied to the traveling salesman problem. A novel approach has been taken to parallelize simulated annealing and the results are compared with the traditional annealing algorithm. This approach uses abbreviated cooling schedule and achieves a superlinear speedup. Also a new search technique, called tabu search, has been adapted to execute in a parallel computing environment. Comparison between simulated annealing and tabu search indicate that tabu search consistently outperforms simulated annealing with respect to computation time while giving comparable solutions. Examples include 25, 33, 42, 50, 57, 75 and 100 city problems.