Advanced Genetic Programming Based Machine Learning

A Genetic Programming based approach for solving classification problems is presented in this paper. Classification is understood as the act of placing an object into a set of categories, based on the object’s properties; classification algorithms are designed to learn a function which maps a vector of object features into one of several classes. This is done by analyzing a set of input-output examples (“training samples”) of the function. Here we present a method based on the theory of Genetic Algorithms and Genetic Programming that interprets classification problems as optimization problems: Each presented instance of the classification problem is interpreted as an instance of an optimization problem, and a solution is found by a heuristic optimization algorithm. The major new aspects presented in this paper are advanced algorithmic concepts as well as suitable genetic operators for this problem class (mainly the creation of new hypotheses by merging already existing ones and their detailed evaluation). The experimental part of the paper documents the results produced using new hybrid variants of Genetic Algorithms as well as investigated parameter settings. Graphical analysis is done using a novel multiclass classifier analysis concept based on the theory of Receiver Operating Characteristic curves. The work described in this paper was done within the Translational Research Project L282 “GP-Based Techniques for the Design of Virtual Sensors” sponsored by the Austrian Science Fund (FWF).     

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.     

Reliability and Performance of UEGO, a Clustering-based Global Optimizer

UEGO is a general clustering technique capable of accelerating and/or parallelizing existing search methods. UEGO is an abstraction of GAS, a genetic algorithm (GA) with subpopulation support, so the niching (i.e. clustering) technique of GAS can be applied along with any kind of optimizers, not only genetic algorithm. The aim of this paper is to analyze the behavior of the algorithm as a function of different parameter settings and types of functions and to examine its reliability with the help of Csendes' method. Comparisons to other methods are also presented.     

A hybrid method for solving multi-objective global optimization problems

Real optimization problems often involve not one, but multiple objectives, usually in conflict. In single-objective optimization there exists a global optimum, while in the multi-objective case no optimal solution is clearly defined but rather a set of optimums, which constitute the so called Pareto-optimal front. Thus, the goal of multi-objective strategies is to generate a set of non-dominated solutions as an approximation to this front. However, most problems of this kind cannot be solved exactly because they have very large and highly complex search spaces. The objective of this work is to compare the performance of a new hybrid method here proposed, with several well-known multi-objective evolutionary algorithms (MOEA). The main attraction of these methods is the integration of selection and diversity maintenance. Since it is very difficult to describe exactly what a good approximation is in terms of a number of criteria, the performance is quantified with adequate metrics that evaluate the proximity to the global Pareto-front. In addition, this work is also one of the few empirical studies that solves three-objective optimization problems using the concept of global Pareto-optimality.     

Self-adaptive velocity particle swarm optimization for solving constrained optimization problems

Particle swarm optimization (PSO) is originally developed as an unconstrained optimization technique, therefore lacks an explicit mechanism for handling constraints. When solving constrained optimization problems (COPs) with PSO, the existing research mainly focuses on how to handle constraints, and the impact of constraints on the inherent search mechanism of PSO has been scarcely explored. Motivated by this fact, in this paper we mainly investigate how to utilize the impact of constraints (or the knowledge about the feasible region) to improve the optimization ability of the particles. Based on these investigations, we present a modified PSO, called self-adaptive velocity particle swarm optimization (SAVPSO), for solving COPs. To handle constraints, in SAVPSO we adopt our recently proposed dynamic-objective constraint-handling method (DOCHM), which is essentially a constituent part of the inherent search mechanism of the integrated SAVPSO, i.e., DOCHM + SAVPSO. The performance of the integrated SAVPSO is tested on a well-known benchmark suite and the experimental results show that appropriately utilizing the knowledge about the feasible region can substantially improve the performance of the underlying algorithm in solving COPs.     

An empirical study on similarity-based mating for evolutionary multiobjective combinatorial optimization

We have already proposed a similarity-based mating scheme to recombine extreme and similar parents for evolutionary multiobjective optimization. In this paper, we examine the effect of the similarity-based mating scheme on the performance of evolutionary multiobjective optimization (EMO) algorithms. First we examine which is better between recombining similar or dissimilar parents. Next we examine the effect of biasing selection probabilities toward extreme solutions that are dissimilar from other solutions in each population. Then we examine the effect of dynamically changing the strength of this bias during the execution of EMO algorithms. Computational experiments are performed on a wide variety of test problems for multiobjective combinatorial optimization. Experimental results show that the performance of EMO algorithms can be improved by the similarity-based mating scheme for many test problems.     

A New Semidefinite Programming Bound for Indefinite Quadratic Forms Over a Simplex

The paper describes a method for computing a lower bound of the global minimum of an indefinite quadratic form over a simplex. The bound is derived by computing an underestimator of the convex envelope by solving a semidefinite program (SDP). This results in a convex quadratic program (QP). It is shown that the optimal value of the QP is a lower bound of the optimal value of the original problem. Since there exist fast (polynomial time) algorithms for solving SDP's and QP's the bound can be computed in reasonable time. Numerical experiments indicate that the relative error of the bound is about 10 percent for problems up to 20 variables, which is much better than a known SDP bound.     

几何规划问题的一种分枝定界方法

本文通过指数函数变换，把解几何规划GP（Ω）等价地转化为另外一个非线优化问题NLP（－↑Ω），根据问题（－↑Ω）的结构特征，构造它的一个线性规划松驰上确定它的最优值的一个下界，由此给出问题GP（Ω）的一个新的分枝定界算法。最后证明了这个算法是收敛的。     

一种改进的进化规划算法

本对于全局优化问题提出一个改进的进化规划算法，该算法以概率p接收基于电磁理论求出合力方向作为随机搜索方向，以概率1-p接收按正态分布产生的随机搜索方向。改进算法不仅克服了传统进化规划算法随机搜索的盲目性，而且保留了传统进化规划算法全局搜索性。本算法应用于几个典型例题，数值结果表明本算法是可行的，有效的。     

A New Way of Using Semidefinite Programming with Applications to Linear Equations mod p

We introduce a new method of constructing approximation algorithms for combinatorial optimization problems using semidefinite programming. It consists of expressing each combinatorial object in the original problem as a constellation of vectors in the semidefinite program. When we apply this technique to systems of linear equations mod p with at most two variables in each equation, we can show that the problem is approximable within (1 − κ(p))p, where κ(p) > 0 for all p. Using standard techniques, we also show that it is NP-hard to approximate the problem within a constant ratio, independent of p.     

A real-coded biogeography-based optimization with mutation

Biogeography-based optimization (BBO) is a new biogeography inspired algorithm for global optimization. There are some open research questions that need to be addressed for BBO. In this paper, we extend the original BBO and present a real-coded BBO approach, referred to as RCBBO, for the global optimization problems in the continuous domain. Furthermore, in order to improve the diversity of the population and enhance the exploration ability of RCBBO, the mutation operator is integrated into RCBBO. Experiments have been conducted on 23 benchmark problems of a wide range of dimensions and diverse complexities. The results indicate the good performance of the proposed RCBBO method. Moreover, experimental results also show that the mutation operator can improve the performance of RCBBO effectively.     

Extending a class of continuous estimation of distribution algorithms to dynamic problems

In this paper, a class of continuous Estimation of Distribution Algorithms (EDAs) based on Gaussian models is analyzed to investigate their potential for solving dynamic optimization problems where the global optima may change dramatically during time. Experimental results on a number of dynamic problems show that the proposed strategy for dynamic optimization can significantly improve the performance of the original EDAs and the optimal solutions can be consistently located.     

Test examples for nonlinear programming codes

The increasing importance of nonlinear programming software requires an enlarged set of test examples. The purpose of this note is to point out how an interested mathematical programmer could obtain computer programs of more than 120 constrained nonlinear programming problems which have been used in the past to test and compare optimization codes.     

An Evolutionary Algorithm With Applications to Statistics

Evolutionary algorithms are used to find maxima of functions. Their claim to fame is an ability to find a global maximum in the presence of local maxima. The computations do not require derivatives or convexity, but still may be fairly computationally intensive in larger dimensions. This article presents a new type of evolutionary algorithm that works well in many dimensions, with the added advantage that linear equality constraints are implemented in a natural way. Bounds on the coordinates of the solution are also easy to implement. Several examples are presented and the new algorithm is compared with standard versions of evolutionary algorithms. The first group consists of functions in one or two dimensions, chosen to be difficult to maximize by gradient or simplex-based methods. The second set of examples are from statistics problems that are known to be computationally difficult. The first is least absolute deviations nonlinear regression with bootstrapped confidence bounds on the mean response, the second is smoothed nonparametric unimodal density estimation requiring both a linear equality constraint and linear inequality constraints. The Fortran subroutine is available for the user.     

A Hybrid Multiobjective Evolutionary Algorithm for Solving Vehicle Routing Problem with Time Windows

Vehicle routing problem with time windows (VRPTW) involves the routing of a set of vehicles with limited capacity from a central depot to a set of geographically dispersed customers with known demands and predefined time windows. The problem is solved by optimizing routes for the vehicles so as to meet all given constraints as well as to minimize the objectives of traveling distance and number of vehicles. This paper proposes a hybrid multiobjective evolutionary algorithm (HMOEA) that incorporates various heuristics for local exploitation in the evolutionary search and the concept of Pareto's optimality for solving multiobjective optimization in VRPTW. The proposed HMOEA is featured with specialized genetic operators and variable-length chromosome representation to accommodate the sequence-oriented optimization in VRPTW. Unlike existing VRPTW approaches that often aggregate multiple criteria and constraints into a compromise function, the proposed HMOEA optimizes all routing constraints and objectives simultaneously, which improves the routing solutions in many aspects, such as lower routing cost, wider scattering area and better convergence trace. The HMOEA is applied to solve the benchmark Solomon's 56 VRPTW 100-customer instances, which yields 20 routing solutions better than or competitive as compared to the best solutions published in literature.     

A Family of Stochastic Programming Test Problems Based on a Model for Tactical Manpower Planning

Ariyawansa and Felt (2001, 2004) have recently created a test problem collection for testing software for stochastic linear programs. This freely-available, web-based collection was originally created with 35 problem instances from 11 problem families representing a variety of application areas. The collection was created with plans for enriching it with problem instances based on different application areas from the research community. The work of Martel and Al-Nuaimi (1973) on manpower planning under uncertain demand represents an application area suitable for creating new problem instances to be added to the collection. The purpose of this paper is to describe the construction of a new family of stochastic programming test problems based on the work of Martel and Al-Nuaimi (1973). As part of our construction, we review the work of Martel and Al-Nuaimi (1973) leading to an extension of their models for which their solution procedure does not apply. The new test problems are based on this extension. We also present solutions to the test problems obtained using the software package CPA (2002) for stochastic programming developed by Ariyawansa, Felt and Sarich. Mathematics Subject Classifications (2000) 90C15, 90C90, 65K05. K. A. Ariyawansa: The work of this author was supported in part by the U.S. Army Research Office under Grant DAAD 19-00-1-0465.     

Evolutionary hybrid approaches for generation scheduling in power systems

Generation scheduling (GS) in power systems is a tough optimisation problem which continues to present a challenge for efficient solution techniques. The solution is to define on/off decisions and generation levels for each electricity generator of a power system for each scheduling interval. The solution procedure requires simultaneous consideration of binary decision and continuous variables. In recent years researchers have focused much attention on developing new hybrid approaches using evolutionary and traditional exact methods for this type of mixed-integer problems. This paper investigates how the optimum or near optimum solution for the GS problem may be quickly identified. A design is proposed which uses a variety of metaheuristic, heuristics and mathematical programming techniques within a hybrid framework. The results obtained for two case studies are promising and show that the hybrid approach offers an effective alternative for solving the GS problems within a realistic timeframe.     

On Nesterov's Approach to Semi-infinite Programming

We generalize Nesterov's construction for the reduction of various classes of semi-infinite programming problems to the semidefinite programming form. In this way, we are able to consider cones of squares of real-valued and matrix-valued functions as rather particular cases of a unifying abstract scheme. We also interpret from this viewpoint some results of M. Krein and A. Nudelman. This provides (in a way which probably has not been anticipated by these authors) a very powerful tool for solving various optimization problems.     

Solving Problems with Min-Type Functions by Disjunctive Programming

We consider applications of disjunctive programming to global optimization and problems with equilibrium constraints. We propose a modification of the algorithm of F. Beaumont for disjunctive programming problems and show its numerical efficiency.     

Minimization of the Ratio of Functions Defined as Sums of the Absolute Values

This paper addresses a new class of linearly constrained fractional programming problems where the objective function is defined as the ratio of two functions which are the sums of the absolute values of affine functions. This problem has an important application in financial optimization. This problem is a convex-convex type of fractional program which cannot be solved by standard algorithms. We propose a branch-and-bound algorithm and an integer programming algorithm. We demonstrate that a fairly large scale problem can be solved within a practical amount of time. The research of the first author was supported in part by the Grant-in-Aid for Scientific Research of the Ministry of Education, Science, Culture and Sports of the Government of Japan, B(2) 15310122 and 15656025.