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.     

Unbiased Recursive Partitioning: A Conditional Inference Framework

Recursive binary partitioning is a popular tool for regression analysis. Two fundamental problems of exhaustive search procedures usually applied to fit such models have been known for a long time: overfitting and a selection bias towards covariates with many possible splits or missing values. While pruning procedures are able to solve the overfitting problem, the variable selection bias still seriously affects the interpretability of tree-structured regression models. For some special cases unbiased procedures have been suggested, however lacking a common theoretical foundation. We propose a unified framework for recursive partitioning which embeds tree-structured regression models into a well defined theory of conditional inference procedures. Stopping criteria based on multiple test procedures are implemented and it is shown that the predictive performance of the resulting trees is as good as the performance of established exhaustive search procedures. It turns out that the partitions and therefore the models induced by both approaches are structurally different, confirming the need for an unbiased variable selection. Moreover, it is shown that the prediction accuracy of trees with early stopping is equivalent to the prediction accuracy of pruned trees with unbiased variable selection. The methodology presented here is applicable to all kinds of regression problems, including nominal, ordinal, numeric, censored as well as multivariate response variables and arbitrary measurement scales of the covariates. Data from studies on glaucoma classification, node positive breast cancer survival and mammography experience are re-analyzed.     

Exact algorithms for the traveling salesman problem with draft limits

This paper deals with the Traveling Salesman Problem (TSP) with Draft Limits (TSPDL), which is a variant of the well-known TSP in the context of maritime transportation. In this recently proposed problem, draft limits are imposed due to restrictions on the port infrastructures. Exact algorithms based on three mathematical formulations are proposed and their performance compared through extensive computational experiments. Optimal solutions are reported for open instances of benchmark problems available in the literature.     

A Computational Study of Shifting Bottleneck Procedures for Shop Scheduling Problems

We examine the performance of Shifting Bottleneck (SB) heuristics for shop scheduling problems where the performance measure to be minimized is makespan (C _max) or maximum lateness (L _max). Extensive computational experiments are conducted on benchmark problems from the literature as well as several thousand randomly generated test problems with three different routing structures and up to 1000 operations. Several different versions of SB are examined to determine the effect on solution quality and time of different subproblem solution procedures, reoptimization procedures and bottleneck selection criteria. Results show that the performance of SB is significantly affected by job routings, and that SB with optimal subproblem solutions and full reoptimization at each iteration consistently outperforms dispatching rules, but requires high computation times for large problems. High quality subproblem solutions and reoptimization procedures are essential to obtaining good solutions. We also show that schedules developed by SB to minimize L _max perform well with respect to several other performance measures, rendering them more attractive for practical use.     

Eigenvalues and switching algorithms for Quasi-Newton updates

Two switching algorithms QNSWl and QNSW2 are proposed in this paper. These algorithms are developed based on the eigenvalues of matrices which are inertial to the symmetric rank-one (SR1) updates and the BFGS updates. First, theoretical results on the eigenvalues and condition numbers of these matrices are presented. Second, switch-ing mechanisms are then developed based on theoretical results obtained so that each proposed algorithm has the capability of applying appropriate updating formulae at each iterative point during the whole minimization process. Third, the performance of

each of the proposed algorithms is evaluated over a wide range of test problems with variable dimensions. These results are then compared to the results obtained by some well-known minimization packages. Comparative results show that among the tested methods, the QNSW2 algorithm has the best overall performance for the problems examined. In some cases, the number of iterations and the number function/gradient calls required by certain existing methods are more than a four-fold increase over that required by the proposed switching algorithms     

Grey prediction evolution algorithm for global optimization

This article uses the grey prediction theory to structure a new metaheuristic: grey prediction evolution algorithm based on the even grey model. The proposed algorithm considers the population series of evolutionary algorithms as a time series, and uses the even grey model as a reproduction operator to forecast the next population (without employing any mutation and crossover operators). It is theoretically proven that the reproduction operator based on the even grey model is adaptive. Additionally, the algorithmic search mechanism and its differences with other evolutionary algorithms are analyzed. The performance of the proposed algorithm is validated on CEC2005 benchmark functions and a test suite composed of six engineering constrained design problems. The comparison experiments show the effectiveness and superiority of the proposed algorithm.The proposed algorithm can be regarded as the first case of structuring metaheuristics by using the prediction theory. The novel algorithm is anticipated to influence two future works. The first is to propose more metaheuristics inspired by prediction theories (including some statistical algorithms). Another is that the theoretical results of these prediction systems can be used for this novel type of metaheuristics.     

Handling equality constraints in evolutionary optimization

Over the last few decades several methods have been proposed for handling functional constraints while solving optimization problems using evolutionary algorithms (EAs). However, the presence of equality constraints makes the feasible space very small compared to the entire search space. As a consequence, the handling of equality constraints has long been a difficult issue for evolutionary optimization methods. This paper presents a Hybrid Evolutionary Algorithm (HEA) for solving optimization problems with both equality and inequality constraints. In HEA, we propose a new local search technique with special emphasis on equality constraints. The basic concept of the new technique is to reach a point on the equality constraint from the current position of an individual solution, and then explore on the constraint landscape. We believe this new concept will influence the future research direction for constrained optimization using population based algorithms. The proposed algorithm is tested on a set of standard benchmark problems. The results show that the proposed technique works very well on those benchmark problems.     

Globally convergent algorithms for solving unconstrained optimization problems

New algorithms for solving unconstrained optimization problems are presented based on the idea of combining two types of descent directions: the direction of anti-gradient and either the Newton or quasi-Newton directions. The use of latter directions allows one to improve the convergence rate. Global and superlinear convergence properties of these algorithms are established. Numerical experiments using some unconstrained test problems are reported. Also, the proposed algorithms are compared with some existing similar methods using results of experiments. This comparison demonstrates the efficiency of the proposed combined methods.     

On spectral radii of matrices governing some numerical estimating algorithms with incomplete data

Summary Many estimating procedures are carried out with incomplete data by means of different types of EM algorithms. They allow us to obtain maximum likelihood parameter estimates in classical inference and also estimates based on the posterior mode in Bayesian inference. This paper analyzes in detail the spectral radii of the Jacobian matrices algorithm as a possible way to evaluate convergence rates. The eigenvalues of such matrices are explicitly obtained in some cases and, in all of them, a geometric convergence rate is, at least, guaranteed near the optimum. Finally, a comparison between the leading eigenvalues of EM and direct and approximate EM-Bayes algorithms may suggest the efficiency of each case.     

On spectral radii of matrices governing some numerical estimating algorithms with incomplete data

Many estimating procedures are carried out with incomplete data by means of different types of EM algorithms. They allow us to obtain maximum likelihood parameter estimates in classical inference and also estimates based on the posterior mode in Bayesian inference. This paper analyzes in detail the spectral radii of the Jacobian matrices algorithm as a possible way to evaluate convergence rates. The eigenvalues of such matrices are explicitly obtained in some cases and, in all of them, a geometric convergence rate is, at least, guaranteed near the optimum. Finally, a comparison between the leading eigenvalues of EM and direct and approximate EM-Bayes algorithms may suggest the efficiency of each case.     

Exploratory analysis of benchmark experiments an interactive approach

Visualization can help a lot to understand the huge amounts of data created in computer simulations and benchmark experiments. In Eugster et al. (Technical report 30, Institut für Statistik, Ludwig-Maximilians-Universit?t München, Germany 2008) we presented a comprehensive toolbox for exploration and inference on benchmark data, including the bench plot. This plot visualizes the behavior of the algorithms on the individual drawn learning and test samples according to a specific performance measure. In this paper we show that an interactive version of the bench plot can help to uncover details and relations unseen with the static version.     

The modulus‐based matrix splitting algorithms for a class of weakly nonlinear complementarity problems

In this paper, we study a class of weakly nonlinear complementarity problems arising from the discretization of free boundary problems. By reformulating the complementarity problems as implicit fixed‐point equations based on splitting of the system matrices, we propose a class of modulus‐based matrix splitting algorithms. We show their convergence by assuming that the system matrix is positive definite. Moreover, we give several kinds of typical practical choices of the modulus‐based matrix splitting iteration methods based on the different splitting of the system matrix. Numerical experiments on two model problems are presented to illustrate the theoretical results and examine the numerical effectiveness of our modulus‐based matrix splitting algorithms. Copyright © 2016 John Wiley & Sons, Ltd.     

Three new stochastic local search algorithms for continuous optimization problems

This paper introduces three new stochastic local search metaheuristics algorithms namely, the Best Performance Algorithm (BPA), the Iterative Best Performance Algorithm (IBPA) and the Largest Absolute Difference Algorithm (LADA). BPA and IBPA are based on the competitive nature of professional athletes, in them desiring to improve on their best recorded performances. LADA is modeled on calculating the absolute difference between two numbers. The performances of the algorithms have been tested on a large collection of benchmark unconstrained continuous optimization functions. They were benchmarked against two well-known local-search metaheuristics namely, Tabu Search (TS) and Simulated Annealing (SA). Results obtained show that each of the new algorithms delivers higher percentages of the best and mean function values found, compared to both TS and SA. The execution times of these new algorithms are also comparable. LADA gives the best performance in terms of execution time.     

Genetic algorithm-based subproblem solution procedures for a modified shifting bottleneck heuristic for complex job shops

In this paper, we consider a modified shifting bottleneck heuristic for complex job shops. The considered job shop environment contains parallel batching machines, machines with sequence-dependent setup times and reentrant process flows. Semiconductor wafer fabrication facilities (Wafer Fabs) are typical examples for manufacturing systems with these characteristics. Our primary performance measure is total weighted tardiness (TWT). The shifting bottleneck heuristic uses a disjunctive graph to decompose the overall scheduling into scheduling problems for single tool groups. The scheduling algorithms for these scheduling problems are called subproblem solution procedures (SSPs). In previous research, only subproblem solution procedures based on dispatching rules have been considered. In this paper, we are interested in how much we can gain in terms of TWT if we apply more sophisticated subproblem solution procedures like genetic algorithms for parallel machine scheduling. We conduct simulation experiments in a dynamic job shop environment in order to assess the performance of the suggested subproblem solution procedures. It turns out that using near to optimal subproblem solution procedures leads in many situations to improved results compared to dispatching-based subproblem solution procedures.     

Global Convergence Analysis of Algorithms for Finding Feasible Points in Norm-Relaxed MFD

This paper introduces two new algorithms for finding initial feasible points from initial infeasible points for the recently developed norm-relaxed method of feasible directions (MFD). Their global convergence is analyzed. The theoretical results show that both methods are globally convergent; one of them guarantees finding a feasible point in a finite number of steps. These two methods are very convenient to implement in the norm-relaxed MFD. Numerical experiments are carried out to demonstrate their performance on some classical test problems and to compare them with the traditional method of phase I problems. The numerical results show that the methods proposed in this paper are more effective than the method of phase I problems in the norm-relaxed MFD. Hence, they can be used for finding initial feasible points for other MFD algorithms and other nonlinear programming methods.     

GRASP and path relinking for project scheduling under partially renewable resources

Recently, in the field of project scheduling problems the concept of partially renewable resources has been introduced. Theoretically, it is a generalization of both renewable and non-renewable resources. From an applied point of view, partially renewable resources allow us to model a large variety of situations that do not fit into classical models, but can be found in real problems in timetabling and labor scheduling. In this paper, we develop some preprocessing techniques and several heuristic algorithms for the problem. Preprocessing significantly reduces the dimension of the problems, therefore improving the efficiency of solution procedures. Heuristic algorithms based on GRASP and Path relinking are then developed and tested on existing test instances, obtaining excellent results.     

Constrained global optimization of multivariate polynomials using Bernstein branch and prune algorithm

We propose an algorithm for constrained global optimization to tackle non-convex nonlinear multivariate polynomial programming problems. The proposed Bernstein branch and prune algorithm is based on the Bernstein polynomial approach. We introduce several new features in this proposed algorithm to make the algorithm more efficient. We first present the Bernstein box consistency and Bernstein hull consistency algorithms to prune the search regions. We then give Bernstein contraction algorithm to avoid the computation of Bernstein coefficients after the pruning operation. We also include a new Bernstein cut-off test based on the vertex property of the Bernstein coefficients. The performance of the proposed algorithm is numerically tested on 13 benchmark problems. The results of the tests show the proposed algorithm to be overall considerably superior to existing method in terms of the chosen performance metrics.     

Evaluation of the multiobjective ant colony algorithm performances on biobjective quadratic assignment problems

The difficulty of resolving the multiobjective combinatorial optimization problems with traditional methods has directed researchers to investigate new approaches which perform better. In recent years some algorithms based on ant colony optimization (ACO) metaheuristic have been suggested to solve these multiobjective problems. In this study these algorithms have been reported and programmed both to solve the biobjective quadratic assignment problem (BiQAP) instances and to evaluate the performances of these algorithms. The robust parameter sets for each 12 multiobjective ant colony optimization (MOACO) algorithms have been calculated and BiQAP instances in the literature have been solved within these parameter sets. The performances of the algorithms have been evaluated by comparing the Pareto fronts obtained from these algorithms. In the evaluation step, a multi significance test is used in a non hierarchical structure, and a performance metric (P metric) essential for this test is introduced. Through this study, decision makers will be able to put in the biobjective algorithms in an order according to the priority values calculated from the algorithms’ Pareto fronts. Moreover, this is the first time that MOACO algorithms have been compared by solving BiQAPs.     

Theoretical rate of convergence for interval inclusion functions

Geometric branch-and-bound methods are commonly used solution algorithms for non-convex global optimization problems in small dimensions, say for problems with up to six or ten variables, and the efficiency of these methods depends on some required lower bounds. For example, in interval branch-and-bound methods various well-known lower bounds are derived from interval inclusion functions. The aim of this work is to analyze the quality of interval inclusion functions from the theoretical point of view making use of a recently introduced and general definition of the rate of convergence in geometric branch-and-bound methods. In particular, we compare the natural interval extension, the centered form, and Baumann’s inclusion function. Furthermore, our theoretical findings are justified by detailed numerical studies using the Weber problem on the plane with some negative weights as well as some standard global optimization benchmark problems.     

����ά�ɹ��̲���Ӧ�������˻�����Ŀ͹۱�Ҷ˹����

Step-stress accelerated degradation test (SSADT) is a useful tool for assessing the lifetime distribution of highly reliable products when the available test items are very few. In this paper, we discuss multiple-steps step-stress accelerated degradation models based on Wiener process, and we apply the objective Bayesian method for such analytically intractable models to obtain the noninformative priors (Jefferys prior and two Reference priors). Moreover, we show that their posterior distributions are proper, and we propose Gibbs sampling algorithms for the Bayesian inference based on the Jefferys prior and two Reference priors. Finally, we present some simulation studies to compare the objective Bayesian estimates with the other Bayesian estimate and the maximum likelihood estimates (MLEs). Simulation results demonstrate the superiority of objective Bayesian analysis method.