Win–win match using a genetic algorithm

As the service industries grow, tasks are not directly assigned to the skills but the knowledge of the worker which is to be valued more in finding the best match. The problem becomes difficult mainly because the match has to be seen with the objectives of both sides. Assignment methods fail to respond to a multi-objective, multi-constraint problem with complicated match; whereas, metaheuristics is preferable based on computational simplicity. A conditional genetic algorithm is developed in this study to propose both global and composite match using different fitness functions. This algorithm kills the infeasibilities to achieve the maximum number of matches. The proposed algorithm is applied on an academic problem of multi-alternative candidates and multi-alternative tasks (m × n problem) in two stages. In the first stage, four different fitness functions are evaluated and in the second stage using one of the fitness functions global and composite matching have been compared. The achievements will contribute both to the academic and business world.     

Optimization of container inspection strategy via a genetic algorithm

It is estimated that 90% of the world’s freight is moved as containerized cargo, with over 125 million TEUs (Twenty foot Equivalent Units) of container being shipped by 2010. To inspect this volume of cargo for explosives, drugs or other contraband is a daunting challenge. This paper presents an optimization technique for developing an inspection strategy that will provide a specified detection rate for containers containing contraband at a minimum cost. Nested genetic algorithms are employed to optimize the topology of an inspection strategy decision tree, the placement of sensors on the tree and the sensor thresholds which partition suspicious containers (containers believed to contain contraband) from innocuous containers (containers which are believed to be free of contraband). The results of this optimization technique are compared to previously published techniques.     

Nonnegative rank factorization—a heuristic approach via rank reduction

Given any nonnegative matrix $A \in \mathbb{R}^{m \times n}$ , it is always possible to express A as the sum of a series of nonnegative rank-one matrices. Among the many possible representations of A, the number of terms that contributes the shortest nonnegative rank-one series representation is called the nonnegative rank of A. Computing the exact nonnegative rank and the corresponding factorization are known to be NP-hard. Even if the nonnegative rank is known a priori, no simple procedure exists presently that is able to perform the nonnegative factorization. Based on the Wedderburn rank reduction formula, this paper proposes a heuristic approach to tackle this difficult problem numerically. Starting with A, the idea is to recurrently extrat, whenever possible, a rank-one nonnegative portion from the previous matrix while keeping the residual nonnegative and lowering its rank by one. With a slight modification for symmetry, the method can equally be applied to another important class of completely positive matrices. No convergence can be guaranteed, but repeated restart might help alleviate the difficulty. Extensive numerical testing seems to suggest that the proposed algorithm might serve as a first-step numerical means for exploring the intriguing problem of nonnegative rank factorization.     

Solving a bi-objective nurse rerostering problem by using a utopic Pareto genetic heuristic

Nurse rerostering arises when at least one nurse announces that she will be unable to undertake the tasks previously assigned to her. The problem amounts to building a new roster that satisfies the hard constraints already met by the current one and, as much as possible, fulfils two groups of soft constraints which define the two objectives to be attained. A bi-objective genetic heuristic was designed on the basis of a population of individuals characterised by pairs of chromosomes, whose fitness complies with the Pareto ranking of the respective decoded solution. It includes an elitist policy, as well as a new utopic strategy, introduced for purposes of diversification. The computational experiments produced promising results for the practical application of this approach to real life instances arising from a public hospital in Lisbon.     

On a parallel genetic–tabu search based algorithm for solving the graph colouring problem

In this paper, we are interested in a particular combinatorial optimisation problem (COP), namely the graph colouring problem (GCP). To solve the GCP, we present a parallel approach adopting an efficient strategy. A brief survey on known methods for solving the GCP enables us to justify our approach which is based on a hybrid method, starting from a set of solutions initialized by the so-called RLF colouring method and combining both a genetic algorithm and the tabu search. A parallelising strategy is then applied. The performances of our method were evaluated through a series of experimentations achieved on an IBM SP2 multiprocessor. The processed graphs were chosen from two benchmark sets. The first, taken from the Internet, involves graphs whose chromatic numbers are known and the second involves random generated graphs. The analysis of the results proves the interest of our approach.     

Interacting Fisher–Wright diffusions in a catalytic medium

We study the longtime behaviour of interacting systems in a randomly fluctuating (space–time) medium and focus on models from population genetics. There are two prototypes of spatial models in population genetics: spatial branching processes and interacting Fisher–Wright diffusions. Quite a bit is known on spatial branching processes where the local branching rate is proportional to a random environment (catalytic medium). Here we introduce a model of interacting Fisher–Wright diffusions where the local resampling rate (or genetic drift) is proportional to a catalytic medium. For a particular choice of the medium, we investigate the longtime behaviour in the case of nearest neighbour migration on the d-dimensional lattice. While in classical homogeneous systems the longtime behaviour exhibits a dichotomy along the transience/recurrence properties of the migration, now a more complicated behaviour arises. It turns out that resampling models in catalytic media show phenomena that are new even compared with branching in catalytic medium. Received: 15 November 1999 / Revised version: 16 June 2000 / Published online: 6 April 2001     

Mathematical model of liquid–liquid equilibrium for a ternary system using the GMDH-type neural network and genetic algorithm

A GMDH type-neural network was used to predict liquid phase equilibrium data for the (water + ethanol + trans-decalin) ternary system in the temperature range of 300.2–315.2 K. In order to accomplish modeling, the experimental data were divided into train and test sections. The data set was divided into two parts: 70% were used as data for “training” and 30% were used as a test set. The predicted values were compared with those of experimental values in order to evaluate the performance of the GMDH neural network method. The results obtained by using GMDH type neural network are in excellent agreement with the experimental results.     

The root–unroot algorithm for density estimation as implemented via wavelet block thresholding

We propose and implement a density estimation procedure which begins by turning density estimation into a nonparametric regression problem. This regression problem is created by binning the original observations into many small size bins, and by then applying a suitable form of root transformation to the binned data counts. In principle many common nonparametric regression estimators could then be applied to the transformed data. We propose use of a wavelet block thresholding estimator in this paper. Finally, the estimated regression function is un-rooted by squaring and normalizing. The density estimation procedure achieves simultaneously three objectives: computational efficiency, adaptivity, and spatial adaptivity. A numerical example and a practical data example are discussed to illustrate and explain the use of this procedure. Theoretically it is shown that the estimator simultaneously attains the optimal rate of convergence over a wide range of the Besov classes. The estimator also automatically adapts to the local smoothness of the underlying function, and attains the local adaptive minimax rate for estimating functions at a point. There are three key steps in the technical argument: Poissonization, quantile coupling, and oracle risk bound for block thresholding in the non-Gaussian setting. Some of the technical results may be of independent interest.     

On typical sets in Banach spaces and a parametric Kuratowski–Ulam theorem

Further investigation is done on a phenomenon studied by Zamfirescu in finite dimensions. Among other results it is proved that for most closed bounded sets A in a separable Banach space Y and most ${u \in A}$ , the union of all rays from u that meet A\{u} (resp. do not meet A\{u}) is dense in Y. An infinite-dimensional extension of a theorem of Wieacker is obtained, viz most compacta in a separable Banach space have smooth closed convex hulls.     

Group extensions,fiber bundles,and a parametric Yang–Baxter equation

Theoretical and Mathematical Physics - We show that any extension of an Abelian group corresponds to a solution of the parametric Yang–Baxter equation. This statement is a generalization of...     

On a Feasible–Infeasible Two-Population (FI-2Pop) genetic algorithm for constrained optimization: Distance tracing and no free lunch

We explore data-driven methods for gaining insight into the dynamics of a two-population genetic algorithm (GA), which has been effective in tests on constrained optimization problems. We track and compare one population of feasible solutions and another population of infeasible solutions. Feasible solutions are selected and bred to improve their objective function values. Infeasible solutions are selected and bred to reduce their constraint violations. Interbreeding between populations is completely indirect, that is, only through their offspring that happen to migrate to the other population. We introduce an empirical measure of distance, and apply it between individuals and between population centroids to monitor the progress of evolution. We find that the centroids of the two populations approach each other and stabilize. This is a valuable characterization of convergence. We find the infeasible population influences, and sometimes dominates, the genetic material of the optimum solution. Since the infeasible population is not evaluated by the objective function, it is free to explore boundary regions, where the optimum is likely to be found. Roughly speaking, the No Free Lunch theorems for optimization show that all blackbox algorithms (such as Genetic Algorithms) have the same average performance over the set of all problems. As such, our algorithm would, on average, be no better than random search or any other blackbox search method. However, we provide two general theorems that give conditions that render null the No Free Lunch results for the constrained optimization problem class we study. The approach taken here thereby escapes the No Free Lunch implications, per se.     

Max–max,max–min,min–max and min–min knapsack problems with a parametric constraint

4OR - Max–max, max–min, min–max and min–min optimization problems with a knapsack-type constraint containing a single numerical parameter are studied. The goal is to present...     

Parallel random block-coordinate forward–backward algorithm: a unified convergence analysis

Mathematical Programming - We study the block-coordinate forward–backward algorithm in which the blocks are updated in a random and possibly parallel manner, according to arbitrary...     

Portfolio selection under possibilistic mean–variance utility and a SMO algorithm

In this paper, we propose a new portfolio selection model with the maximum utility based on the interval-valued possibilistic mean and possibilistic variance, which is a two-parameter quadratic programming problem. We also present a sequential minimal optimization (SMO) algorithm to obtain the optimal portfolio. The remarkable feature of the algorithm is that it is extremely easy to implement, and it can be extended to any size of portfolio selection problems for finding an exact optimal solution.     

Four-Operator Splitting via a Forward–Backward–Half-Forward Algorithm with Line Search

In this article, we provide a splitting method for solving monotone inclusions in a real Hilbert space involving four operators: a maximally monotone, a monotone-Lipschitzian, a cocoercive, and a monotone-continuous operator. The proposed method takes advantage of the intrinsic properties of each operator, generalizing the forward–backward–half-forward splitting and the Tseng’s algorithm with line search. At each iteration, our algorithm defines the step size by using a line search in which the monotone-Lipschitzian and the cocoercive operators need only one activation. We also derive a method for solving nonlinearly constrained composite convex optimization problems in real Hilbert spaces. Finally, we implement our algorithm in a nonlinearly constrained least-square problem and we compare its performance with available methods in the literature.

     

A primal–dual algorithm for minimizing a sum of Euclidean norms

We study the problem of minimizing a sum of Euclidean norms. This nonsmooth optimization problem arises in many different kinds of modern scientific applications. In this paper we first transform this problem and its dual problem into a system of strongly semismooth equations, and give some uniqueness theorems for this problem. We then present a primal–dual algorithm for this problem by solving this system of strongly semismooth equations. Preliminary numerical results are reported, which show that this primal–dual algorithm is very promising.