Search

Classification algorithms can suffer from performance degradation when the class distribution is unbalanced. This paper develops a two-step approach to evolving ensembles using genetic programming (GP) for unbalanced data. The first step uses multiobjective (MO) GP to evolve a Pareto-approximated front of GP classifiers to form the ensemble by trading-off the minority and the majority class against each other during learning. The MO component alleviates the reliance on sampling to artificially rebalance the data. The second step, which is the focus this paper, proposes a novel ensemble selection approach using GP to automatically find/choose the best individuals for the ensemble. This new GP approach combines multiple Pareto-approximated front members into a single composite genetic program solution to represent the (optimized) ensemble. This ensemble representation has two main advantages/novelties over traditional genetic algorithm (GA) approaches. First, by limiting the depth of the composite solution trees, we use selection pressure during evolution to find small highly-cooperative groups of individuals for the ensemble. This means that ensemble sizes are not fixed a priori (as in GA), but vary depending on the strength of the base learners. Second, we compare different function set operators in the composite solution trees to explore new ways to aggregate the member outputs and thus, control how the ensemble computes its output. We show that the proposed GP approach evolves smaller more diverse ensembles compared to an established ensemble selection algorithm, while still performing as well as, or better than the established approach. The evolved GP ensembles also perform well compared to other bagging and boosting approaches, particularly on tasks with high levels of class imbalance. [ABSTRACT FROM AUTHOR]

Multiobjective evolutionary algorithm based on decomposition (MOEA/D) decomposes a multiobjective optimization problem into a set of scalar optimization subproblems and optimizes them in a collaborative manner. Subproblems and solutions are two sets of agents that naturally exist in MOEA/D. The selection of promising solutions for subproblems can be regarded as a matching between subproblems and solutions. Stable matching, proposed in economics, can effectively resolve conflicts of interests among selfish agents in the market. In this paper, we advocate the use of a simple and effective stable matching (STM) model to coordinate the selection process in MOEA/D. In this model, subproblem agents can express their preferences over the solution agents, and vice versa. The stable outcome produced by the STM model matches each subproblem with one single solution, and it tradeoffs convergence and diversity of the evolutionary search. Comprehensive experiments have shown the effectiveness and competitiveness of our MOEA/D algorithm with the STM model. We have also demonstrated that user-preference information can be readily used in our proposed algorithm to find a region that decision makers are interested in. [ABSTRACT FROM AUTHOR]

Decision-tree induction algorithms are widely used in machine learning applications in which the goal is to extract knowledge from data and present it in a graphically intuitive way. The most successful strategy for inducing decision trees is the greedy top-down recursive approach, which has been continuously improved by researchers over the past 40 years. In this paper, we propose a paradigm shift in the research of decision trees: instead of proposing a new manually designed method for inducing decision trees, we propose automatically designing decision-tree induction algorithms tailored to a specific type of classification data set (or application domain). Following recent breakthroughs in the automatic design of machine learning algorithms, we propose a hyper-heuristic evolutionary algorithm called hyper-heuristic evolutionary algorithm for designing decision-tree algorithms (HEAD-DT) that evolves design components of top-down decision-tree induction algorithms. By the end of the evolution, we expect HEAD-DT to generate a new and possibly better decision-tree algorithm for a given application domain. We perform extensive experiments in 35 real-world microarray gene expression data sets to assess the performance of HEAD-DT, and compare it with very well known decision-tree algorithms such as C4.5, CART, and REPTree. Results show that HEAD-DT is capable of generating algorithms that significantly outperform the baseline manually designed decision-tree algorithms regarding predictive accuracy and F-measure. [ABSTRACT FROM AUTHOR]

The author responds to the paper "The Loading Problem," by Eilon and Christofides. He focuses on suggesting a solution to the problem. The recommended solution involves a heuristic algorithm that allegedly requires fewer computations than the one proposed by Eilon and Christofides. It is suggested that the simpler algorithm offered by the author reaches mathematical optimization as often as the aforementioned algorithm. It is further proposed that the algorithm presented by Eilon and Christofides cannot be used to solve multi-dimensional programming problems. The author goes on to discuss a numerical analysis that can be used for the allocation of industrial resources. Related mathematical models are discussed in detail. A table comparing the results of the two algorithms is also presented.

In the field of service management plays a decisive role the location of the facilities to improve the quality of services. The maximal covering location problem allows locating a known number of facilities in order to maximize the demand covered. An important aspect to take into account is the varying of demand of the nodes with respect to the time (multi-period model). In addition, each facility could be of different types. A model that takes into account the existence of different types of facilities in order to cover the demand in multi-period environments has not been found in the literature. In this paper we propose a new generalization of the dynamic maximal covering location problem where different types of facilities (with different radius of coverage) could be open in each location. In this work we used the model on case study with the objective to locate the police patrol. [ABSTRACT FROM AUTHOR]

In this paper, we study an extension of the Linear Multiple Choice Knapsack (LMCK) Problem that considers two objectives. The problem can be used to find the optimal allocation of an available resource to a group of disjoint sets of activities, while also ensuring that a certain balance on the resource amounts allocated to the activity sets is attained. The first objective maximizes the profit incurred by the implementation of the considered activities. The second objective minimizes the maximum difference between the resource amounts allocated to any two sets of activities. We present the mathematical formulation and explore the fundamental properties of the problem. Based on these properties, we develop an efficient algorithm that obtains the entire nondominated frontier. The algorithm is more efficient than the application of the general theory of multiple objective linear programming (MOLP), although there is a close underlying relationship between the two. We present theoretical findings which provide insight into the behavior of the algorithm, and report computational results which demonstrate its efficiency for randomly generated problems. [ABSTRACT FROM AUTHOR]

Abstract  This article complements the paper (Jongen, Stein, Smoothing by mollifers part I: semi-infinite optimization J Glob Optim doi:10.1007/s10898-007-9232-3), where we showed that a compact feasible set of a standard semi-infinite optimization problem can be approximated arbitrarily well by a level set of a single smooth function with certain regularity properties. In the special case of nonlinear programming this function is constructed as the mollification of the finite min-function which describes the feasible set. In the present article we treat the correspondences between Karush–Kuhn–Tucker points of the original and the smoothed problem, and between their associated Morse indices. [ABSTRACT FROM AUTHOR]

The Linear Programming Problem is by far the most widely used optimization model. Its impact on economic and government modeling is immense. The Simplex Method for solving the Linear Programming (LP) Problem, due to George Dantzig, has been an extremely efficient computational tool for almost four decades. The method has been the subject of intense investigations for many years, but some major aspects of its behavior are not fully understood yet. The purpose of this paper is to survey the body of knowledge on the efficiency of the Simplex Method, from both practical and theoretical points of view. Adopting the number of iterations (pivot steps) as the yardstick for efficiency, we survey four aspects of the issue: 1. Reports on practical experience of the method's performance on real-life LP problems. 2. Results on controlled (Monte-Carlo) experiments solving LP problems which were randomly generated according to some predetermined distributions. 3. Complexity results, including theoretical analyses on both upper and lower bounds for the performance of the Simplex as well as non-Simplex algorithms for LP. 4. Results of recent theoretical studies using probabilistic analysis to derive bounds on the average behavior of the Simplex Method. We discuss the consequences and limitations of the various studies. Special emphasis is given to open questions. [ABSTRACT FROM AUTHOR]

This paper presents a quantitative planning model to determine the optimal characteristics (number, size and locations) of a regional health facility system. The system consists of a medical center, intermediate and local hospitals, and health centers. The quantitative model is based on the minimization of the total cost (sum of the transportation and facility costs) to the society. The optimal characteristics of the system are obtained using a heuristic method which includes both interactions of sublevel hospitals and environmental conditions as well. A numerical example is given to illustrate the computational procedure. [ABSTRACT FROM AUTHOR]

In this paper, we present a fuzzy semi-infinite optimization problem. Moreover, we will deduce the Fritz-John and Kuhn-Tucker necessary conditions of this problem. Finally, a numerical example is given to illustrate the results. [ABSTRACT FROM AUTHOR]

Abstract: The multi-objective optimization strategy called physical programming (PP) provides engineers with a flexible tool to express design preferences with a ‘physical’ meaning. For each objective or specification design, preferences are established through linguistic categories to which numerical values are assigned. In PP, this mapping is made using preference functions as piecewise splines whose curvatures are calculated with an expensive and iterative algorithm. However, mapping between design parameter space and objective space may be largely non-convex and is uninfluenced by the use of gradient-based methods for solving the optimization problem. In this paper, the philosophy of the PP method has been used, but two components have been totally redesigned: a simpler algorithm is used for the construction of preference functions; and the optimizer is replaced by a genetic algorithm that avoids possible local minima problems. Three engineering applications are shown to illustrate the value of this new method. [ABSTRACT FROM AUTHOR]

A new approach for obtaining the second order sufficient conditions for non-linear mathematical programming problems which makes use of second order derivative is presented. In the so-called second order η-approximation method, an optimization problem associated with the original nonlinear programming problem is constructed that involves a second order η-approximation of both the objective function and the constraint function constituting the original problem. The equivalence between the nonlinear original mathematical programming problem and its associated second order η-approximated optimization problem is established under second order invexity assumption imposed on the functions constituting the original optimization problem. [ABSTRACT FROM AUTHOR]

This paper addresses the problem of optimizing a function over a finite or countably infinite set of alternatives, in situations where this objective function cannot be evaluated exactly, but has to be estimated or measured. A special focus is on situations where simulation is used to evaluate the objective function. We present two versions of a new iterative method for solving such discrete stochastic optimization problems. In each iteration of the proposed method, a neighbor of the "current" alternative is selected, and estimates of the objective function evaluated at the current and neighboring alternatives are compared. The alternative that has a better observed function value becomes the next current alternative. We show how one version of the proposed method can be used to solve discrete optimization problems where the objective function is evaluated using transient or steady-state simulation, and we show how the other version can be applied to solve a special class of discrete stochastic optimization problems and present some numerical results. A major strength of the proposed method is that it spends most of the computational effort at local minimizers of the objective function. In fact, we show that for both versions of the proposed method, the alternative that has been visited most often in the first m iterations converges almost surely to a local optimizer of the objective function as m goes to infinity. [ABSTRACT FROM AUTHOR]

The purpose of this paper is to demonstrate that a portfolio optimization model using the L[sub 1] risk (mean absolute deviation risk) function can remove most of the difficulties associated with the classical Markowitz's model while maintaining its advantages over equilibrium models. In particular, the L[sub 1] risk model leads to a linear program instead of a quadratic program, so that a large-scale optimization problem consisting of more than 1,000 stocks may be solved on a real time basis. Numerical experiments using the historical data of NIKKEI 225 stocks show that the L[sub 1] risk model generates a portfolio quite similar to that of the Markowitz's model within a fraction of time required to solve the latter. [ABSTRACT FROM AUTHOR]

Bilevel convex models are studied after being cast into a parametric programming form. This form has a lexicographic inner-outer structure where the optimal value of the outer model is optimized on the set of optimal solutions of the inner model. Optimal solutions are characterized using a Lagrangian saddle-point approach and a marginal value formula is given for the outer model. These are used to formulate a general method for finding an optimal solution by input optimization. [ABSTRACT FROM AUTHOR]

A non-interior point algorithm based on projection for second-order cone programming problems is proposed and analyzed. The main idea of the algorithm is that we cast the complementary equation in the primal-dual optimality conditions as a projection equation. By using this reformulation, we only need to solve a system of linear equations with the same coefficient matrix and compute two simple projections at each iteration, without performing any line search. This algorithm can start from an arbitrary point, and does not require the row vectors of A to be linearly independent. We prove that our algorithm is globally convergent under weak conditions. Preliminary numerical results demonstrate the effectiveness of our algorithm. [ABSTRACT FROM AUTHOR]

In the last time important results in multiobjective programming involving type-I functions were obtained (Yuan et al. in: Konnov et al. (eds) Lecture notes in economics and mathematical systems, 2007; Mishra et al. An Univ Bucureşti Ser Mat, LII(2): 207–224, 2003). Following one of these ways, we study optimality conditions and generalized Mond-Weir duality for multiobjective programming involving n-set functions which satisfy appropriate generalized univexity V-type-I conditions. We introduce classes of functions called ( ρ, ρ′)-V-univex type-I, ( ρ, ρ′)-quasi V-univex type-I, ( ρ, ρ′)-pseudo V-univex type-I, ( ρ, ρ′)-quasi pseudo V-univex type-I, and ( ρ, ρ′)-pseudo quasi V-univex type-I. Finally, a general frame for constructing functions of these classes is considered. [ABSTRACT FROM AUTHOR]

We analyse the convergence properties of the Longstaff-Schwartz algorithm for approximately solving optimal stopping problems that arise in the pricing of American (Bermudan) financial options. Based on a new approximate dynamic programming principle error propagation inequality, we prove sample complexity error estimates for this algorithm for the case in which the corresponding approximation spaces may not necessarily possess any linear structure at all and may actually be any arbitrary sets of functions, each of which is uniformly bounded and possesses finite VC-dimension, but is not required to satisfy any further material conditions. In particular, we do not require that the approximation spaces be convex or closed, and we thus significantly generalize the results of Egloff, Clement et al., and others. Using our error estimation theorems, we also prove convergence, up to any desired probability, of the algorithm for approximating sets defined using L2 orthonormal bases, within a framework depending subexponentially on the number of time steps. In addition, we prove estimates on the overall convergence rate of the algorithm for approximation spaces defined by polynomials. [ABSTRACT FROM AUTHOR]

The usefulness of group theoretic methods in solving integer programming (IP) problems is extended by procedures for controlling the size of the groups. The main procedure given shows how an optimal linear programming basis can be altered to reduce the magnitude of its determinant thereby reducing the size of the group induced by the basis. An adaption of Benders' mixed IP algorithm is given which uses these methods. Some limited computational experience is given. [ABSTRACT FROM AUTHOR]