Asymptotic convergence of a simulated annealing algorithm for multiobjective optimization problems

In this paper we consider a simulated annealing algorithm for multiobjective optimization problems. With a suitable choice of the acceptance probabilities, the algorithm is shown to converge asymptotically, that is, the Markov chain that describes the algorithm converges with probability one to the Pareto optimal set.     

A new multiobjective simulated annealing algorithm

A new multiobjective simulated annealing algorithm for continuous optimization problems is presented. The algorithm has an adaptive cooling schedule and uses a population of fitness functions to accurately generate the Pareto front. Whenever an improvement with a fitness function is encountered, the trial point is accepted, and the temperature parameters associated with the improving fitness functions are cooled. Beside well known linear fitness functions, special elliptic and ellipsoidal fitness functions, suitable for the generation on non-convex fronts, are presented. The effectiveness of the algorithm is shown through five test problems. The parametric study presented shows that more fitness functions as well as more iteration gives more non-dominated points closer to the actual front. The study also compares the linear and elliptic fitness functions. The success of the algorithm is also demonstrated by comparing the quality metrics obtained to those obtained for a well-known evolutionary multiobjective algorithm.     

A simulated annealing technique for multi-objective simulation optimization

In this paper, we present a simulated annealing algorithm for solving multi-objective simulation optimization problems. The algorithm is based on the idea of simulated annealing with constant temperature, and uses a rule for accepting a candidate solution that depends on the individual estimated objective function values. The algorithm is shown to converge almost surely to an optimal solution. It is applied to a multi-objective inventory problem; the numerical results show that the algorithm converges rapidly.     

Global optimization and simulated annealing

In this paper we are concerned with global optimization, which can be defined as the problem of finding points on a bounded subset of ⁿ in which some real valued functionf assumes its optimal (maximal or minimal) value.We present a stochastic approach which is based on the simulated annealing algorithm. The approach closely follows the formulation of the simulated annealing algorithm as originally given for discrete optimization problems. The mathematical formulation is extended to continuous optimization problems, and we prove asymptotic convergence to the set of global optima. Furthermore, we discuss an implementation of the algorithm and compare its performance with other well-known algorithms. The performance evaluation is carried out for a standard set of test functions from the literature.     

A survey of recent developments in multiobjective optimization

Multiobjective Optimization (MO) has many applications in such fields as the Internet, finance, biomedicine, management science, game theory and engineering. However, solving MO problems is not an easy task. Searching for all Pareto optimal solutions is expensive and a time consuming process because there are usually exponentially large (or infinite) Pareto optimal solutions. Even for simple problems determining whether a point belongs to the Pareto set is -hard. In this paper, we discuss recent developments in MO. These include optimality conditions, applications, global optimization techniques, the new concept of epsilon Pareto optimal solution, and heuristics.     

Robust optimization with simulated annealing

Complex systems can be optimized to improve the performance with respect to desired functionalities. An optimized solution, however, can become suboptimal or even infeasible, when errors in implementation or input data are encountered. We report on a robust simulated annealing algorithm that does not require any knowledge of the problems structure. This is necessary in many engineering applications where solutions are often not explicitly known and have to be obtained by numerical simulations. While this nonconvex and global optimization method improves the performance as well as the robustness, it also warrants for a global optimum which is robust against data and implementation uncertainties. We demonstrate it on a polynomial optimization problem and on a high-dimensional and complex nanophotonic engineering problem and show significant improvements in efficiency as well as in actual optimality.     

Continuous optimization by a variant of simulated annealing

A variant of the simulated annealing algorithm, based on the generalized method of Bohachevsky et al., is proposed for continuous optimization problems. The algorithm automatically adjusts the step sizes to reflect the local slopes and function values, and it controls the random directions to point favorably toward potential improvements. Computational results on some well known functions show substantial improvements both in solution quality and efficiency.     

A simulated annealing algorithm for transient optimization in gas networks

In this paper we present a simulated annealing approach for the gas network optimization problem. A gas network consists of a set of pipes to transport the gas from the sources to the sinks whereby gas pressure gets lost due to friction. Further on there are compressors, which increase gas pressure, and valves. The aim is to minimize fuel gas consumption of the compressors whereas demands of consumers have to be satisfied. The problem of transient (time-dependent) optimization of gas networks results in a highly complex mixed integer nonlinear program. We relax the equations describing the gas dynamic in pipes by adding these constraints combined with appropriate penalty factors to the objective function. A suitable neighborhood structure is developed for the relaxed problem where time steps as well as pressure and flow of the gas are decoupled. Our approach convinces with flexibility and very good computational results.     

A quantum-behaved simulated annealing algorithm-based moth-flame optimization method

This study develops an improved moth-flame optimization algorithm, which is a recently proposed optimizer based on moth behavior in nature. It has achieved favorable results in medical science, educational evaluation, and other fields. However, the convergence rate of the original moth-flame optimization algorithm is too fast in the running process, and it is prone to fall into local optimum, which leads to the failure to produce the high-quality optimal result. Accordingly, this paper proposes a reinforced technique for the moth-flame optimization algorithm. Firstly, the simulated annealing strategy is introduced into the moth-flame optimization algorithm to boost the advantage of the algorithm in the local exploitation process. Then, the idea of the quantum rotation gate is integrated to enhance the global exploration ability of the algorithm and ameliorate the diversity of the moth. These two steps maintain the relationship between exploitation and exploration as well as strengthen the performance of the algorithm in both phases. After that, the method is compared with ten well-regarded and ten alternative algorithms on benchmark functions to verify the effectiveness of the approach. Also, the Wilcoxon signed rank and Friedman assessment were performed to verify the significance of the proposed method against other counterparts. The simulation results reveal that the two introduced strategies significantly improve the exploration and exploitation capacity of moth-flame optimization algorithm. Finally, the algorithm is utilized to feature selection and two engineering problems, including pressure vessel design and multiple disk clutch brake problems. In these practical applications, the novel algorithm also achieves particularly notable results, which also illustrates that the algorithm is qualified is an effective auxiliary appliance in solving complex optimization problems.     

A simulated annealing driven multi-start algorithm for bound constrained global optimization

A derivative-free simulated annealing driven multi-start algorithm for continuous global optimization is presented. We first propose a trial point generation scheme in continuous simulated annealing which eliminates the need for the gradient-based trial point generation. We then suitably embed the multi-start procedure within the simulated annealing algorithm. We modify the derivative-free pattern search method and use it as the local search in the multi-start procedure. We study the convergence properties of the algorithm and test its performance on a set of 50 problems. Numerical results are presented which show the robustness of the algorithm. Numerical comparisons with a gradient-based simulated annealing algorithm and three population-based global optimization algorithms show that the new algorithm could offer a reasonable alternative to many currently available global optimization algorithms, specially for problems requiring ‘direct search’ type algorithm.     

Investigating a hybrid simulated annealing and local search algorithm for constrained optimization

Constrained Optimization Problems (COP) often take place in many practical applications such as kinematics, chemical process optimization, power systems and so on. These problems are challenging in terms of identifying feasible solutions when constraints are non-linear and non-convex. Therefore, finding the location of the global optimum in the non-convex COP is more difficult as compared to non-convex bound-constrained global optimization problems. This paper proposes a Hybrid Simulated Annealing method (HSA), for solving the general COP. HSA has features that address both feasibility and optimality issues and here, it is supported by a local search procedure, Feasible Sequential Quadratic Programming (FSQP). We develop two versions of HSA. The first version (HSAP) incorporates penalty methods for constraint handling and the second one (HSAD) eliminates the need for imposing penalties in the objective function by tracing feasible and infeasible solution sequences independently. Numerical experiments show that the second version is more reliable in the worst case performance.     

Theory and application of multiobjective optimization in China — A survey

The study of multiobjective optimization (MOO) in China began at the beginning of the seventies, when some researchers in Beijing and Shanghai adopted techniques in this field to deal with practical problems arising from industrial designs and management sciences for achieving good results. Subsequently, theoretical studies began. A seminar on MOO was organized by members of the Institute of Mathematics of the Chinese Academy of Sciences in 1977. Meanwhile, studies of the theory and applications of MOO were developed in many universities. Related seminars were held and courses were offered to graduate students at these universities. At the same time, many managers and industrial designers had tried to use the techniques of this branch of OR to solve practical problems arising in a variety of fields. In 1981, 1984, 1987 and 1989, national symposiums on MOO were held, each of which had approximately 100 participants; about 300 papers and reports were presented. Up to the present time, about 200 papers on MOO by Chinese scholars have been published in China or abroad. The sphere of application becomes broader and the scale of problems being solved becomes larger. In China today, there are groups of experienced researchers working in this field, in particular at the Institute of System Sciences of the Chinese Academy of Sciences, the Jiangxi University, the Jilin Technical University, the People's University, and the Shanghai Jiao Tong University. In this paper, we will give a sketch of the results obtained by our colleagues since 1979. The paper consists of seven parts.     

Derivative-free simulated annealing and deflecting function technique for global optimization

A hybrid descent method based on simulated annealing (SA) algorithm and one modifying function technique, named deflecting function method, for global optimization is proposed. Unlike some previously proposed algorithms, the designed SA algorithm is executed repeatedly on the transformed function with respect to one prior-obtained local minimum instead of on the original objective function. Meanwhile, large scale searches at the beginning stages and small scale detections in the last stages are adopted. The global convergence is proved. Simulation demonstrates that the new method utilizes the obtained information effectively, so the convergence is significantly sped up and the success rate is greatly improved, compared with other existing methods. As an experimental result, how to combine SA and the deflecting function technique can make the new method more effective is discussed.     

Proposal adaptation in simulated annealing for continuous optimization problems

In recent years, adaptive Markov Chain Monte Carlo (MCMC) methods have become a standard tool for Bayesian parameter estimation. In adaptive MCMC, the past iterations are used to tune the proposal distribution of the algorithm. The same adaptation mechanisms can be used in Simulated Annealing (SA), a popular optimization method based on MCMC. The difficulty in using adaptation directly in SA is that the target function changes along the iterations in the annealing process, and the adaptation should keep up with the annealing. In this paper, a mechanism for automatically tuning the proposal distribution in SA is proposed. The approach is based on the Adaptive Metropolis algorithm of Haario et al. (Bernoulli 7(2):223–242, 2001), combined with a weighting mechanism to account for the cooling target. The proposed adaptation mechanism does not add any computational complexity to the problem in terms of objective function evaluations. The effect of adaptation is demonstrated using two benchmark problems, showing that the proposed adaptation mechanism can significantly improve optimization results compared to non-adaptive SA. The approach is presented for continuous optimization problems and generalization to integer and mixed-integer problems is a topic of future research.     

A subgradient method for multiobjective optimization

A method for solving quasiconvex nondifferentiable unconstrained multiobjective optimization problems is proposed in this paper. This method extends to the multiobjective case of the classical subgradient method for real-valued minimization. Assuming the basically componentwise quasiconvexity of the objective components, full convergence (to Pareto optimal points) of all the sequences produced by the method is established.     

A controlled search simulated annealing method for the single machine weighted tardiness problem

In this paper, a new controlled search simulated annealing method is developed for addressing the single machine weighted tardiness problem. The proposed method is experimentally shown to solve optimally 99% of fifteen job problems with less than 0.2 CPU seconds, and to solve one hundred job problems as accurately as any existing methods, but with far less computational effort. This superior performance is achieved by using controlled search strategies that employ a good initial solution, a small neighborhood for local search, and acceptance probabilities of inferior solutions that are independent of the change in the objective function value.     

A weighting subgradient algorithm for multiobjective optimization

We propose a weighting subgradient algorithm for solving multiobjective minimization problems on a nonempty closed convex subset of an Euclidean space. This method combines weighting technique and the classical projected subgradient method, using a divergent series steplength rule. Under the assumption of convexity, we show that the sequence generated by this method converges to a Pareto optimal point of the problem. Some numerical results are presented.     

A gap between multiobjective optimization and scalar optimization

We give an example to illustrate a gap between multiobjective optimization and single-objective optimization, which solves a problem proposed in Ref. 1.     

An adaptive simulated annealing algorithm for global optimization over continuous variables

A method is presented for attempting global minimization for a function of continuous variables subject to constraints. The method, calledAdaptive Simulated Annealing (ASA), is distinguished by the fact that the fixed temperature schedules and step generation routines that characterize other implementations are here replaced by heuristic-based methods that effectively eliminate the dependence of the algorithm's overall performance on user-specified control parameters. A parallelprocessing version of ASA that gives increased efficiency is presented and applied to two standard problems for illustration and comparison.This research was supported by the University Research Initiative of the U.S. Army Research Office.