Distributed asynchronous deterministic and stochastic gradient optimization algorithms

We present a model for asynchronous distributed computation and then proceed to analyze the convergence of natural asynchronous distributed versions of a large class of deterministic and stochastic gradient-like algorithms. We show that such algorithms retain the desirable convergence properties of their centralized counterparts, provided that the time between consecutive interprocessor communications and the communication delays are not too large.     

A hyper-heuristic approach to aircraft structural design optimization

The conceptual design of an aircraft is a challenging problem in which optimization can be of great importance to the quality of design generated. Mass optimization of the structural design of an aircraft aims to produce an airframe of minimal mass whilst maintaining satisfactory strength under various loading conditions due to flight and ground manoeuvres. Hyper-heuristic optimization is an evolving field of research wherein the optimization process is continuously adapted in order to provide greater improvements in the quality of the solution generated. The relative infancy of hyper-heuristic optimization has resulted in limited application within the field of aerospace design. This paper describes a framework for the mass optimization of the structural layout of an aircraft at the conceptual level of design employing a novel hyper-heuristic approach. This hyper-heuristic approach encourages solution space exploration, thus reducing the likelihood of premature convergence, and improves the feasibility of and convergence upon the best solution found. A case study is presented to illustrate the effects of hyper-heuristics on the problem for a large commercial aircraft. Resulting solutions were generated of considerably lighter mass than the baseline aircraft. A further improvement in solution quality was found with the use of the hyper-heuristics compared to that obtained without, albeit with a penalty on computation time.     

A review of procedures to evolve quantum algorithms

There exist quantum algorithms that are more efficient than their classical counterparts; such algorithms were invented by Shor in 1994 and then Grover in 1996. A lack of invention since Grover’s algorithm has been commonly attributed to the non-intuitive nature of quantum algorithms to the classically trained person. Thus, the idea of using computers to automatically generate quantum algorithms based on an evolutionary model emerged. A limitation of this approach is that quantum computers do not yet exist and quantum simulation on a classical machine has an exponential order overhead. Nevertheless, early research into evolving quantum algorithms has shown promise. This paper provides an introduction into quantum and evolutionary algorithms for the computer scientist not familiar with these fields. The exciting field of using evolutionary algorithms to evolve quantum algorithms is then reviewed.

基于微分进化算法的多阶段投资组合优化

投资组合优化问题就是决定每个具有特定风险和回报的投资资产在总投资价值中的分配比例。在不断变化的金融市场中,多阶段投资组合优化就是通过周期性重新平衡投资资产比例管理投资组合以达到投资风险最小或投资回报最大。研究了基于微分进化算法在多阶段投资组合优化中制定投资决策的方法,目标函数是最大化个人经济效益或最大化周期结束时个人财富。通过比较用微分进化算法和遗传算法(GA)优化同样的资产对象所得到的期望收益率均值与方差,该文所提出的方法的优越性被美国标准普尔指数100的不同股票和现金分配优化所证实。     

Genetic algorithms (GAs) to evolve multiple-agent cooperative systems

In this paper, a microrobot soccer-playing game, such as that of MIROSOT (Microrobot World Cup Soccer Tournament), is adopted as a standard test bed for research on multiple-agent cooperative systems. It is considerably complex and requires expertise in several difficult research topics, such as mobile microrobot design, motor control, sensor technology, intelligent strategy planning, etc., to build up a complete system to play the game. In addition, because it is an antagonistic game, it appears ideal to test whether one method is better than other. To date there have been two different kinds of architecture for building such system. One is called vision-based or centralized architecture, and the other is known as robot-based or decentralized architecture. The main difference between them lies in whether there exists a host computer system which responds to data processing and strategy planning, and a global vision system which can view the whole playground and transfer the environment information to the host computer in real time. We believe that the decentralized approach is more advanced, but in the preliminary step of our study, we used the centralized approach because it can lighten any overload of the microrobot design. In this paper, a simplified layer model of the multiple-agent cooperative system is first proposed. Based on such a model, a system for a microrobot soccer-playing game is organized. At the same time a simple genetic algorithm (SGA) is used for the autonomous evolution of cooperative behavior among microrobots. Finally, a computer simulation system is introduced and some simulated results are explained. This work was presented, in part, at the Third International Symposium on Artificial Life and Robotics, Oita, Japan, January 19–21, 1998.     

Multi-objective optimization of a stacked neural network using an evolutionary hyper-heuristic

The present paper deals with the development and optimization of a stacked neural network (SNN) through an evolutionary hyper-heuristic, called NSGA-II-QNSNN. The proposed hyper-heuristic is based on the NSGA-II (Non-dominated Sorting Genetic Algorithm - II) multi-objective optimization evolutionary algorithm which incorporates the Quasi-Newton (QN) optimization algorithm. QN is used for training each neural network from the stack. The final global optimal solution provided by NSGA-II-QNSNN algorithm is a Pareto optimal front. It represents all the equally good compromises that can be made between the structural complexity of the stacked neural network and its modelling performance. The set of decision variables, which led to obtaining the set of points in the Pareto optimal front, represents the optimum values for the parameters of the stacked neural network: the number of networks in the stack, the weights for every output of the composing networks, and the number of hidden neurons in each individual neural network. Each stacked neural network determined through the optimization process was trained and tested by applying it to a real world problem: the modelling of the polyacrylamide-based multicomponent hydrogels synthesis. The neural modelling established the influence of the reaction conditions on the reaction yield and the swelling degree. The results provided by NSGA-II-QNSNN were superior, not only in terms of performance, but also in terms of structural complexity, to those obtained in our previous works, where individual or aggregated neural networks were used, but the stacks were developed manually, based on successive trials.     

Evolutionary algorithms with deterministic mutation operators used for the optimization of the trajectory of a four-bar mechanism

In this paper, we propose an Evolutionary Algorithm (EA) with a deterministic mutation operator which is a combination of EA with the Broyden, Fletcher, Goldfarb and Shanno (BFGS) method. The advantages of both optimization algorithms are retained and interconnected. The proposed algorithm shows faster convergence as well as increased reliability in the search for the global optimum. Results referring to the Fletcher and Powel test function in comparison with EA (Evolution Strategies, Evolutionary Programming, and Genetic Algorithms), provide sufficient indication for the performance of the new method. Finally, the proposed method is successfully implemented for the trajectory optimization of a four-bar mechanism.     

改进差异演化算法求解约束优化问题

在现实生活中许多实际问题都可以转化为约束优化问题,并且实际问题通常都很复杂,其函数形态各具特色,传统基于梯度信息的各种求解策略对于具有不可微、多峰及非凸的非线性函数约束优化问题很难凑效。而最近兴起的智能类算法却对这类问题的求解效果突出,在借鉴国外的差异演化算法研究成果基础上,运用改进差异演化算法来求解约束优化问题。最后通过实例进行仿真实验,结果表明改进差异演化算法在求解约束优化问题时具有一定的优越性。     

Two hybrid differential evolution algorithms for engineering design optimization

This paper presents two hybrid differential evolution algorithms for optimizing engineering design problems. One hybrid algorithm enhances a basic differential evolution algorithm with a local search operator, i.e., random walk with direction exploitation, to strengthen the exploitation ability, while the other adding a second metaheuristic, i.e., harmony search, to cooperate with the differential evolution algorithm so as to produce the desirable synergetic effect. For comparison, the differential evolution algorithm that the two hybrids are based on is also implemented. All algorithms incorporate a generalized method to handle discrete variables and Deb's parameterless penalty method for handling constraints. Fourteen engineering design problems selected from different engineering fields are used for testing. The test results show that: (i) both hybrid algorithms overall outperform the differential evolution algorithms; (ii) among the two hybrid algorithms, the cooperative hybrid overall outperforms the other hybrid with local search; and (iii) the performance of proposed hybrid algorithms can be further improved with some effort of tuning the relevant parameters.     

AMA: a new approach for solving constrained real-valued optimization problems

Memetic algorithms (MA) have recently been applied successfully to solve decision and optimization problems. However, selecting a suitable local search technique remains a critical issue of MA, as this significantly affects the performance of the algorithms. This paper presents a new agent based memetic algorithm (AMA) for solving constrained real-valued optimization problems, where the agents have the ability to independently select a suitable local search technique (LST) from our designed set. Each agent represents a candidate solution of the optimization problem and tries to improve its solution through co-operation with other agents. Evolutionary operators consist of only crossover and one of the self-adaptively selected LSTs. The performance of the proposed algorithm is tested on five new benchmark problems along with 13 existing well-known problems, and the experimental results show convincing performance.     

On using deterministic functions to reduce randomness in probabilistic algorithms

We show the existence of nonuniform schemes for the following sampling problem: Given a sample space with n points, an unknown set of size n/2, and s random points, it is possible to generate deterministically from them s + k points such that the probability of not hitting the unknown set is exponentially smaller in k than 2^−s. Tight bounds are given for the quality of such schemes. Explicit, uniform versions of these schemes could be used for efficiently reducing the error probability of randomized algorithms. A survey of known constructions (whose quality is very far from the existential result) is included.     

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     

Comparison of deterministic and stochastic approaches to global optimization

In this paper, we compare two different approaches to nonconvex global optimization. The first one is a deterministic spatial Branch‐and‐Bound algorithm, whereas the second approach is a Quasi Monte Carlo (QMC) variant of a stochastic multi level single linkage (MLSL) algorithm. Both algorithms apply to problems in a very general form and are not dependent on problem structure. The test suite we chose is fairly extensive in scope, in that it includes constrained and unconstrained problems, continuous and mixed‐integer problems. The conclusion of the tests is that in general the QMC variant of the MLSL algorithm is generally faster, although in some instances the Branch‐and‐Bound algorithm outperforms it.     

A comparison of global optimization algorithms applied to a ride comfort optimization problem

This study presents a comparison of global optimization algorithms applied to an industrial engineering optimization problem. Three global stochastic optimization algorithms using continuous variables, i.e. the domain elimination method, the zooming method and controlled random search, have been applied to a previously studied ride comfort optimization problem. Each algorithm is executed three times and the total number of objective function evaluations needed to locate a global optimum is averaged and used as a measure of efficiency. The results show that the zooming method, with a proposed modification, is most efficient in terms of number of objective function evaluations and ability to locate the global optimum. Each design variable is thereafter given a set of discrete values and two optimization algorithms using discrete variables, i.e. a genetic algorithm and simulated annealing, are applied to the discrete ride comfort optimization problem. The results show that the genetic algorithm is more efficient than the simulated annealing algorithm for this particular optimization problem.     

基于和声搜索算法的知识即服务动态组合优化

面向服务的云计算环境为制造领域的知识创新提供了新的思路。知识即服务的动态组合是知识创新过程中的关键技术之一。云计算服务资源的虚拟性和动态性为组合的知识即服务的服务质量提出了新的挑战。针对制造领域知识即服务组合的服务质量优化问题,提出一种改进的和声搜索算法(SLHS),SLHS算法利用Skyline方法对和声记忆库进行初始化以提高算法的运行效率,并采用理想点法选择制造知识即服务以确保解的有效性。仿真实验中引入了基本和声搜索算法作比较。实验结果表明SLHS算法在解的质量方面和算法性能方面均明显优于基本和声搜索算法。     

云和声搜索算法及其在知识服务组合中的应用

云计算环境下的知识服务是知识与服务的融合, 为知识管理、知识创新提供了新的发展方向。针对基于服务质量(QoS)的知识服务组合优化问题, 在云计算平台下实现和声搜索算法的并行化, 提出了云和声搜索算法。将Skyline方法和理想点法融入到云和声搜索算法中, 对云和声搜索算法进行改进, 提高了算法的运行效率, 确保了解的有效性。实验结果表明, 改进云和声搜索算法在求解知识服务组合优化问题上取得了较好的结果, 在解的质量以及算法的性能方面均有较好的表现。     

A new hyper-heuristic as a general problem solver: an implementation in HyFlex

This study provides a new hyper-heuristic design using a learning-based heuristic selection mechanism together with an adaptive move acceptance criterion. The selection process was supported by an online heuristic subset selection strategy. In addition, a pairwise heuristic hybridization method was designed. The motivation behind building an intelligent selection hyper-heuristic using these adaptive hyper-heuristic sub-mechanisms is to facilitate generality. Therefore, the designed hyper-heuristic was tested on a number of problem domains defined in a high-level framework, i.e., HyFlex. The framework provides a set of problems with a number of instances as well as a group of low-level heuristics. Thus, it can be considered a good environment to measure the generality level of selection hyper-heuristics. The computational results demonstrated the generic performance of the proposed strategy in comparison with other tested hyper-heuristics composed of the sub-mechanisms from the literature. Moreover, the performance and behavior analysis conducted for the hyper-heuristic clearly showed its adaptive characteristics under different search conditions. The principles comprising the here presented algorithm were at the heart of the algorithm that won the first international cross-domain heuristic search competition.     

An optimization approach to relaxation labelling algorithms

It is shown that the relaxation labelling process of Rosenfeld, Hummel and Zucker is a suboptimal minimization of a cost function measuring inconsistency and ambiguity. Two new algorithms which minimize this cost function more efficiently are introduced. Finally, some general comments on relaxation are presented.     

Grammatical evolution of shape and its application to structural shape optimisation

We propose an automated shape generative framework, which provides an alternative way of exploring the design space in a structural mechanics context. The framework presented uses “blind” evolutionary intelligence to synthesise shape grammar sentences i.e. Grammatical Evolution (GE), where rules are selected by a Genetic Algorithm (GA). This is a novel approach to automate the Shape Grammar (SG) formalism. We then present an application of a grammar based shape generative framework to solve a 2D design optimisation problem. This involves synthesis of parametric 2D curves where the shape grammar primitives are introduced as arcs represented by rotation and a radius. The efficacy of the proposed shape generative framework is then compared with that of Non-Uniform Rational B-Splines (NURBS) parametrisation for structural optimisation.     

Introducing assignment functions to Bayesian optimization algorithms

In this paper, we improve Bayesian optimization algorithms by introducing proportionate and rank-based assignment functions. A Bayesian optimization algorithm builds a Bayesian network from a selected sub-population of promising solutions, and this probabilistic model is employed to generate the offspring of the next generation. Our method assigns each solution a relative significance based on its fitness, and this information is used in building the Bayesian network model. These assignment functions can improve the quality of the model without performing an explicit selection on the population. Numerical experiments demonstrate the effectiveness of this method compared to a conventional BOA.