Metaheuristic methods in hybrid flow shop scheduling problem

Memetic algorithms are hybrid evolutionary algorithms that combine global and local search by using an evolutionary algorithm to perform exploration while the local search method performs exploitation. This paper presents two hybrid heuristic algorithms that combine particle swarm optimization (PSO) with simulated annealing (SA) and tabu search (TS), respectively. The hybrid algorithms were applied on the hybrid flow shop scheduling problem. Experimental results reveal that these memetic techniques can effectively produce improved solutions over conventional methods with faster convergence.     

Self-Adaptive Multimethod Search for Global Optimization in Real-Parameter Spaces

Many different algorithms have been developed in the last few decades for solving complex real-world search and optimization problems. The main focus in this research has been on the development of a single universal genetic operator for population evolution that is always efficient for a diverse set of optimization problems. In this paper, we argue that significant advances to the field of evolutionary computation can be made if we embrace a concept of self-adaptive multimethod optimization in which multiple different search algorithms are run concurrently, and learn from each other through information exchange using a common population of points. We present an evolutionary algorithm, entitled A Multialgorithm Genetically Adaptive Method for Single Objective Optimization (AMALGAM-SO), that implements this concept of self adaptive multimethod search. This method simultaneously merges the strengths of the covariance matrix adaptation (CMA) evolution strategy, genetic algorithm (GA), and particle swarm optimizer (PSO) for population evolution and implements a self-adaptive learning strategy to automatically tune the number of offspring these three individual algorithms are allowed to contribute during each generation. Benchmark results in 10, 30, and 50 dimensions using synthetic functions from the special session on real-parameter optimization of CEC 2005 show that AMALGAM-SO obtains similar efficiencies as existing algorithms on relatively simple unimodal problems, but is superior for more complex higher dimensional multimodal optimization problems. The new search method scales well with increasing number of dimensions, converges in the close proximity of the global minimum for functions with noise induced multimodality, and is designed to take full advantage of the power of distributed computer networks.     

Multimodal optimization using a bi-objective evolutionary algorithm

In a multimodal optimization task, the main purpose is to find multiple optimal solutions (global and local), so that the user can have better knowledge about different optimal solutions in the search space and as and when needed, the current solution may be switched to another suitable optimum solution. To this end, evolutionary optimization algorithms (EA) stand as viable methodologies mainly due to their ability to find and capture multiple solutions within a population in a single simulation run. With the preselection method suggested in 1970, there has been a steady suggestion of new algorithms. Most of these methodologies employed a niching scheme in an existing single-objective evolutionary algorithm framework so that similar solutions in a population are deemphasized in order to focus and maintain multiple distant yet near-optimal solutions. In this paper, we use a completely different strategy in which the single-objective multimodal optimization problem is converted into a suitable bi-objective optimization problem so that all optimal solutions become members of the resulting weak Pareto-optimal set. With the modified definitions of domination and different formulations of an artificially created additional objective function, we present successful results on problems with as large as 500 optima. Most past multimodal EA studies considered problems having only a few variables. In this paper, we have solved up to 16-variable test problems having as many as 48 optimal solutions and for the first time suggested multimodal constrained test problems which are scalable in terms of number of optima, constraints, and variables. The concept of using bi-objective optimization for solving single-objective multimodal optimization problems seems novel and interesting, and more importantly opens up further avenues for research and application.     

Finite element based hybrid evolutionary optimization approach to solving rigid pavement inversion problem

This paper focuses on the development of a new backcalculation method for concrete road structures based on a hybrid evolutionary global optimization algorithm, namely shuffled complex evolution (SCE). Evolutionary optimization algorithms are ideally suited for intrinsically multi-modal, non-convex, and discontinuous real-world problems such as pavement backcalculation because of their ability to explore very large and complex search spaces and locate the globally optimal solution using a parallel search mechanism as opposed to a point-by-point search mechanism employed by traditional optimization algorithms. SCE, a type of evolutionary optimization algorithms based on the tradeoff of exploration and exploitation, has proved to be an efficient method for many global optimization problems and in some cases it does not suffer the difficulties encountered by other evolutionary computation techniques. The SCE optimization approach is hybridized with a neural networks surrogate finite-element based forward pavement response model to enable rapid computation of global or near-global pavement layer moduli solutions. The proposed rigid pavement backcalculation model is evaluated using field non-destructive test data acquired from a full-scale airport pavement test facility.     

A two-dimensional multilevel thresholding method for image segmentation

In this work, we develop a two-dimensional multilevel thresholding technique based on Rényi and Tsallis entropies. The formulation of the proposed method gives rise to an NP-hard combinatorial optimization problem. In order to solve efficiently this problem, two leading evolutionary algorithms, namely the quantum genetic algorithm (QGA) and the differential evolution (DE) have been employed and compared. The effectiveness of both the proposed method and the optimizers was demonstrated on a sample of real-world and synthetic images showing different types of gray-level distributions. Moreover, the contribution of the two-dimensional histogram to the segmentation quality has been highlighted on some images corrupted by noise and containing shadow or reflection effects. Experimental results demonstrated, first, that DE is less time consuming than QGA which is slightly more efficient on complex problems. Second, the Rényi and Tsallis entropies leads to similar image segmentation quality. Finally, we have shown that the proposed method is more appropriate than bilevel thresholding for multimodal and noisy images segmentation.     

An efficient algorithm for high-dimensional function optimization

To solve high-dimensional function optimization problems, many evolutionary algorithms have been proposed. In this paper, we propose a new cooperative coevolution orthogonal artificial bee colony (CCOABC) algorithm in an attempt to address the issue effectively. Cooperative coevolution frame, a popular technique in evolutionary algorithms for large scale optimization problems, is adopted in this paper. This frame decomposes the problem into several subcomponents by random grouping, which is a novel decomposition strategy mainly for tackling nonseparable functions. This strategy can increase the probability of grouping interacting variables in one subcomponent. And for each subcomponent, an improved artificial bee colony (ABC) algorithm, orthogonal ABC, is employed as the subcomponent optimizer. In orthogonal ABC, an Orthogonal Experimental Design method is used to let ABC evolve in a quick and efficient way. The algorithm has been evaluated on standard high-dimensional benchmark functions. Compared with other four state-of-art evolutionary algorithms, the simulation results demonstrate that CCOABC is a highly competitive algorithm for solving high-dimensional function optimization problems.     

改进的元启发式优化算法及其在图像分割中的应用

元启发式算法自20世纪60年代提出以后,由于其具有可以有效地减少计算量、提高优化效率等优点而得到了广泛应用.该类算法以模仿自然界中各类运行机制为特点,具有自我调节的特征,解决了诸如梯度法、牛顿法和共轭下降法等这些传统优化算法计算效率低、收敛性差等缺点,在组合优化、生产调度、图像处理等方面均有很好的效果.提出了一种改进的元启发式优化算法——NBAS算法.该算法通过将传统天牛须算法（BAS）离散化得到二进制离散天牛须算法（BBAS）,并与原始天牛须算法进行混合得出.算法平衡了局部与全局搜索,有效地弥补了算法容易陷入局部最优的不足.为了验证NBAS算法的有效性,将NBAS算法与二维K熵算法结合,提出了一种快速、准确的NBAS-K熵图像分割算法.该方法解决了优化图像阈值分割函数的优化算法易陷入局部最优、算法寻优个体数多、设计复杂度高所导致的计算量大、耗时长等问题.NBAS-K熵算法与BAS-K熵算法、BBAS-K熵算法、遗传K熵算法（GA-K熵）、粒子群K熵算法（PSO-K熵）和蚱蜢K熵算法（GOA-K熵）在Berkeley数据集、人工加噪图像以及遥感图像上的实验结果表明,该分割方法不仅具有较好的抗噪性能,而且具有较高的精度和鲁棒性,能够较为有效地实现复杂图像分割.     

Topological Active Models optimization with Differential Evolution

The Topological Active Model is an active model focused on segmentation tasks. It provides information about the surfaces and the inside of the detected objects in the scene. The segmentation process turns into a minimization task of the energy functions which control the model deformation. In this work we propose a new optimization method of the segmentation model that uses Differential Evolution as an alternative evolutionary method that minimizes the decisions of the designer with respect to others such as genetic algorithms. Moreover, we hybridized Differential Evolution with a greedy search to integrate the advantages of global and local searches at the same time that the segmentation speed is improved. We also included in the local search the possibility of topological changes to perform a better adjustment in complex surfaces, topological changes that introduce the necessary mechanism to divide the mesh in the case of the presence of several objects in the scene.     

Evolutionary algorithms,simulated annealing and tabu search: a comparative study

Evolutionary algorithms, simulated annealing (SA), and tabu search (TS) are general iterative algorithms for combinatorial optimization. The term evolutionary algorithm is used to refer to any probabilistic algorithm whose design is inspired by evolutionary mechanisms found in biological species. Most widely known algorithms of this category are genetic algorithms (GA). GA, SA, and TS have been found to be very effective and robust in solving numerous problems from a wide range of application domains. Furthermore, they are even suitable for ill-posed problems where some of the parameters are not known before hand. These properties are lacking in all traditional optimization techniques. In this paper we perform a comparative study among GA, SA, and TS. These algorithms have many similarities, but they also possess distinctive features, mainly in their strategies for searching the solution state space. The three heuristics are applied on the same optimization problem and compared with respect to (1) quality of the best solution identified by each heuristic, (2) progress of the search from initial solution(s) until stopping criteria are met, (3) the progress of the cost of the best solution as a function of time (iteration count), and (4) the number of solutions found at successive intervals of the cost function. The benchmark problem used is the floorplanning of very large scale integrated (VLSI) circuits. This is a hard multi-criteria optimization problem. Fuzzy logic is used to combine all objective criteria into a single fuzzy evaluation (cost) function, which is then used to rate competing solutions.     

Combinations of Estimation of Distribution Algorithms and Other Techniques

This paper summaries our recent work on combining estimation of distribution algorithms (EDA) and other techniques for solving hard search and optimization problems:a) guided mutation,an offspring generator in which the ideas from EDAs and genetic algorithms are combined together,we have shown that an evolutionary algorithm with guided mutation outperforms the best GA for the maximum clique problem,b)evolutionary algorithms refining a heuristic,we advocate a strategy for solving a hard optimization problem with complicated data structure,and c) combination of two different local search techniques and EDA for numerical global optimization problems,its basic idea is that not all the new generated points are needed to be improved by an expensive local search.     

Mumford–Shah and Potts Regularization for Manifold-Valued Data

Mumford–Shah and Potts functionals are powerful variational models for regularization which are widely used in signal and image processing; typical applications are edge-preserving denoising and segmentation. Being both non-smooth and non-convex, they are computationally challenging even for scalar data. For manifold-valued data, the problem becomes even more involved since typical features of vector spaces are not available. In this paper, we propose algorithms for Mumford–Shah and for Potts regularization of manifold-valued signals and images. For the univariate problems, we derive solvers based on dynamic programming combined with (convex) optimization techniques for manifold-valued data. For the class of Cartan–Hadamard manifolds (which includes the data space in diffusion tensor imaging (DTI)), we show that our algorithms compute global minimizers for any starting point. For the multivariate Mumford–Shah and Potts problems (for image regularization), we propose a splitting into suitable subproblems which we can solve exactly using the techniques developed for the corresponding univariate problems. Our method does not require any priori restrictions on the edge set and we do not have to discretize the data space. We apply our method to DTI as well as Q-ball imaging. Using the DTI model, we obtain a segmentation of the corpus callosum on real data.     

Multiobjective optimization using population-based extremal optimization

In recent years, a general-purpose local-search heuristic method called Extremal Optimization (EO) has been successfully applied in some NP-hard combinatorial optimization problems. In this paper, we present a novel Pareto-based algorithm, which can be regarded as an extension of EO, to solve multiobjective optimization problems. The proposed method, called Multiobjective Population-based Extremal Optimization (MOPEO), is validated by using five benchmark functions and metrics taken from the standard literature on multiobjective evolutionary optimization. The experimental results demonstrate that MOPEO is competitive with the state-of-the-art multiobjective evolutionary algorithms. Thus MOPEO can be considered as a viable alternative to solve multiobjective optimization problems.     

Evolutionary segmentation of texture image using genetic algorithms towards automatic decision of optimum number of segmentation areas

Segmentation of an image composed of different kinds of texture fields has difficulty in an exact discrimination of the texture fields and a decision of the optimum number of segmentation areas in an image when the image contains similar and/or unstationary texture fields. In this paper we formulate the segmentation problem upon such images as an optimization problem and adopt evolutionary strategy of genetic algorithms for the clustering of small regions in a feature space. The purpose of this paper is to demonstrate the efficiency of genetic algorithms to the texture segmentation and to develop the automatic texture segmentation method.     

A constrained, globalized, and bounded Nelder–Mead method for engineering optimization

One of the fundamental difficulties in engineering design is the multiplicity of local solutions. This has triggered much effort in the development of global search algorithms. Globality, however, often has a prohibitively high numerical cost for real problems. A fixed cost local search, which sequentially becomes global, is developed in this work. Globalization is achieved by probabilistic restarts. A spacial probability of starting a local search is built based on past searches. An improved Nelder–Mead algorithm is the local optimizer. It accounts for variable bounds and nonlinear inequality constraints. It is additionally made more robust by reinitializing degenerated simplexes. The resulting method, called the Globalized Bounded Nelder–Mead (GBNM) algorithm, is particularly adapted to tackling multimodal, discontinuous, constrained optimization problems, for which it is uncertain that a global optimization can be afforded. Numerical experiments are given on two analytical test functions and two composite laminate design problems. The GBNM method compares favorably with an evolutionary algorithm, both in terms of numerical cost and accuracy.     

从局部极小到全局最优

所有控制决策问题本质上均可归结为优化问题,但大部分存在多极小,因此如何摆脱局部极小以实现全局最优一直是理论界和工程界关注的热点课题。文章总结了若干全局优化技术的机制和特点,包括模拟退火、进化计算、禁忌搜索、变邻域搜索、噪声方法、巢分区、混沌搜索、隧道方法、平滑技术、混合算法等,力求为优化研究人员了解全局优化技术和开发高效算法提供指导。     

A harmony search algorithm for high-dimensional multimodal optimization problems

Harmony search (HS) and its variants have been found successful applications, however with poor solution accuracy and convergence performance for high-dimensional (≥200) multimodal optimization problems. The reason is mainly huge search space and multiple local minima. To tackle the problem, we present a new HS algorithm called DIHS, which is based on Dynamic-Dimensionality-Reduction-Adjustment (DDRA) and dynamic fret width (fw) strategy. The former is for avoiding generating invalid solutions and the latter is to balance global exploration and local exploitation. Theoretical analysis on the DDRA strategy for success rate of update operation is given and influence of related parameters on solution accuracy is investigated. Our experiments include comparison on solution accuracy and CPU time with seven typical HS algorithms and four widely used evolutionary algorithms (SaDE, CoDE, CMAES and CLPSO) and statistical comparison by the Wilcoxon Signed-Rank Test with the seven HS algorithms and four evolutionary algorithms. The problems in experiments include twelve multimodal and four complex uni-modal functions with high-dimensionality.Experimental results indicate that the proposed approach can provide significant improvement on solution accuracy with less CPU time in solving high-dimensional multimodal optimization problems, and the more dimensionality that the optimization problem is, the more benefits it provides.     

Immunity-based hybrid evolutionary algorithm for multi-objective optimization in global container repositioning

The development of evolutionary algorithms for optimization has always been a stimulating and growing research area with an increasing demand in using them to solve complex industrial optimization problems. A novel immunity-based hybrid evolutionary algorithm known as Hybrid Artificial Immune Systems (HAIS) for solving both unconstrained and constrained multi-objective optimization problems is developed in this research. The algorithm adopts the clonal selection and immune suppression theories, with a sorting scheme featuring uniform crossover, multi-point mutation, non-dominance and crowding distance sorting to attain the Pareto optimal front in an efficient manner. The proposed algorithm was verified with nine benchmarking functions on its global optimal search ability as well as compared with four optimization algorithms to assess its diversity and spread. Sensitivity analysis was also carried out to investigate the selection of key parameters of the algorithm. It is found that the developed immunity-based hybrid evolutionary algorithm provides a useful means for solving optimization problems and has successfully applied to the problem of global repositioning of containers, which is one of a constrained multi-objective optimization problem. The developed HAIS will assist shipping liners on timely decision making and planning of container repositioning operations in global container transportation business in an optimized and cost effective manner.     

Fuzzy programming for mixed-integer optimization problems

Mixed-integer optimization problems belong to the group of NP-hard combinatorial problems. Therefore, they are difficult to search for global optimal solutions. Mixed-integer optimization problems are always described by precise mathematical programming models. However, many practical mixed-integer optimization problems have inherited a more or less imprecise nature. Under these circumstances, if we take into account the flexibility of the constraints and the fuzziness of the objectives, the original mixed-integer optimization problems can be formulated as fuzzy mixed-integer optimization problems. Mixed-integer hybrid differential evolution (MIHDE) is an evolutionary search algorithm which has been successfully applied to many complex mixed-integer optimization problems. In this article, a fuzzy mixed-integer mathematical programming model is developed to formulate the fuzzy mixed-integer optimization problem. In addition the MIHDE is introduced to solve the fuzzy mixed-integer programming problem. Finally, the illustrative example shows that satisfactory results can be obtained by the proposed method. This demonstrates that MIHDE can effectively handle fuzzy mixed-integer optimization problems.     

An effective hybrid particle swarm optimization algorithm for multi-objective flexible job-shop scheduling problem

Flexible job-shop scheduling problem (FJSP) is an extension of the classical job-shop scheduling problem. Although the traditional optimization algorithms could obtain preferable results in solving the mono-objective FJSP. However, they are very difficult to solve multi-objective FJSP very well. In this paper, a particle swarm optimization (PSO) algorithm and a tabu search (TS) algorithm are combined to solve the multi-objective FJSP with several conflicting and incommensurable objectives. PSO which integrates local search and global search scheme possesses high search efficiency. And, TS is a meta-heuristic which is designed for finding a near optimal solution of combinatorial optimization problems. Through reasonably hybridizing the two optimization algorithms, an effective hybrid approach for the multi-objective FJSP has been proposed. The computational results have proved that the proposed hybrid algorithm is an efficient and effective approach to solve the multi-objective FJSP, especially for the problems on a large scale.     

Max-min surrogate-assisted evolutionary algorithm for robust design

Solving design optimization problems using evolutionary algorithms has always been perceived as finding the optimal solution over the entire search space. However, the global optima may not always be the most desirable solution in many real-world engineering design problems. In practice, if the global optimal solution is very sensitive to uncertainties, for example, small changes in design variables or operating conditions, then it may not be appropriate to use this highly sensitive solution. In this paper, we focus on combining evolutionary algorithms with function approximation techniques for robust design. In particular, we investigate the application of robust genetic algorithms to problems with high dimensions. Subsequently, we present a novel evolutionary algorithm based on the combination of a max-min optimization strategy with a Baldwinian trust-region framework employing local surrogate models for reducing the computational cost associated with robust design problems. Empirical results are presented for synthetic test functions and aerodynamic shape design problems to demonstrate that the proposed algorithm converges to robust optimum designs on a limited computational budget.