Comparative analysis of multiobjective evolutionary algorithms for random and correlated instances of multiobjective d-dimensional knapsack problems

This study analyzes multiobjective d-dimensional knapsack problems (MOd-KP) within a comparative analysis of three multiobjective evolutionary algorithms (MOEAs): the ε-nondominated sorted genetic algorithm II (ε-NSGAII), the strength Pareto evolutionary algorithm 2 (SPEA2) and the ε-nondominated hierarchical Bayesian optimization algorithm (ε-hBOA). This study contributes new insights into the challenges posed by correlated instances of the MOd-KP that better capture the decision interdependencies often present in real world applications. A statistical performance analysis of the algorithms uses the unary ε-indicator, the hypervolume indicator and success rate plots to demonstrate their relative effectiveness, efficiency, and reliability for the MOd-KP instances analyzed. Our results indicate that the ε-hBOA achieves superior performance relative to ε-NSGAII and SPEA2 with increasing number of objectives, number of decisions, and correlative linkages between the two. Performance of the ε-hBOA suggests that probabilistic model building evolutionary algorithms have significant promise for expanding the size and scope of challenging multiobjective problems that can be explored.     

A novel elitist multiobjective optimization algorithm: Multiobjective extremal optimization

Recently, a general-purpose local-search heuristic method called extremal optimization (EO) has been successfully applied to some NP-hard combinatorial optimization problems. This paper presents an investigation on EO with its application in numerical multiobjective optimization and proposes a new novel elitist (1 + λ) multiobjective algorithm, called multiobjective extremal optimization (MOEO). In order to extend EO to solve the multiobjective optimization problems, the Pareto dominance strategy is introduced to the fitness assignment of the proposed approach. We also present a new hybrid mutation operator that enhances the exploratory capabilities of our algorithm. The proposed approach is validated using five popular benchmark functions. The simulation results indicate that the proposed approach is highly competitive with the state-of-the-art multiobjective evolutionary algorithms. Thus MOEO can be considered a good alternative to solve numerical multiobjective optimization problems.     

Solving multiobjective,multiconstraint knapsack problems using mathematical programming and evolutionary algorithms

In this paper, we solve instances of the multiobjective multiconstraint (or multidimensional) knapsack problem (MOMCKP) from the literature, with three objective functions and three constraints. We use exact as well as approximate algorithms. The exact algorithm is a properly modified version of the multicriteria branch and bound (MCBB) algorithm, which is further customized by suitable heuristics. Three branching heuristics and a more general purpose composite branching and construction heuristic are devised. Comparison is made to the published results from another exact algorithm, the adaptive ε-constraint method [Laumanns, M., Thiele, L., Zitzler, E., 2006. An efficient, adaptive parameter variation scheme for Metaheuristics based on the epsilon-constraint method. European Journal of Operational Research 169, 932–942], using the same data sets. Furthermore, the same problems are solved using standard multiobjective evolutionary algorithms (MOEA), namely, the SPEA2 and the NSGAII. The results from the exact case show that the branching heuristics greatly improve the performance of the MCBB algorithm, which becomes faster than the adaptive ε -constraint. Regarding the performance of the MOEA algorithms in the specific problems, SPEA2 outperforms NSGAII in the degree of approximation of the Pareto front, as measured by the coverage metric (especially for the largest instance).     

Extending quick hypervolume

We extend the functionality of the quick hypervolume (QHV) algorithm. Given a set of d-dimensional points this algorithm determines the hypervolume of the dominated space, a useful measure for multiobjective evolutionary algorithms (MOEAs). We extend QHV in two ways: adapt it to compute the exclusive hypervolume of each point, and speed it up with parallel computation, that adjusts nicely to the divide and conquer methodology of QHV. The resulting algorithms are faster and more informative sub-routines, which can be used for MOEAs with a large number of objectives.     

Z3-invariants of real and imaginary quadratic fields

Let $\text{Q}$((?m)^{$\text{1}\text{2}$}) and $\text{Q}$((3m)^{$\text{1}\text{2}$}) be a pair of quadratic fields, m > 0, and let λ^?, μ^?; λ⁺, μ⁺ be the respective Iwasawa invariants of the basic $\text{Z}$₃-extensions of these fields. A generalization of a result of Scholz shows that λ^? ≥ λ⁺ and if μ^? = 0, then μ⁺ = 0.     

Some exact distributions of the number of one-sided deviations and the time of the last such deviation in the simple random walk

For every positive integer n, let S_n be the n-th partial sum of a sequence of independent and identically distributed random variables, each assuming the values +1 and −1 with respective probabilities p (0<p<1)) and q (= 1 −p) and having mean μ = p − q. For a fixed positive real number λ, let N⁺[N1] be the total number of values of n for which S_n > (μ + λ)n [S_n⩾(μ + λ)n] and let L⁺[L1] be the supremum of the values of n for which S_n > (μ + λ)n [S_n⩾(μ + λ)n], where sup Oslash; = 0. Explicit expressions for the exact distributions of N⁺, N1, L⁺ and L1 are given when μ + λ = ±k/(k + 2) for any nonnegative integer k.     

An algorithm for computing Jordan chains and inverting analytic matrix functions

We present an efficient algorithm for obtaining a canonical system of Jordan chains for an n × n regular analytic matrix function A(λ) that is singular at the origin. For any analytic vector function b(λ), we show that each term in the Laurent expansion of A(λ)⁻¹b(λ) may be obtained from the previous terms by solving an (n + d) × (n+d) linear system, where d is the order of the zero of det A(λ) at λ = 0. The matrix representing this linear system contains A(0) as a principal submatrix, which can be useful if A(0) is sparse. The last several iterations can be eliminated if left Jordan chains are computed in addition to right Jordan chains. The performance of the algorithm in floating point and exact (rational) arithmetic is reported for several test cases. The method is shown to be forward stable in floating point arithmetic.     

Extinction times for a birth–death process with weak competition

We consider a birth–death process with birth rates iλ and death rates iμ+i(i?1)θ, where i is the current state of the process. A positive competition rate θ is assumed to be small. In the supercritical case where λ > μ, this process can be viewed as a demographic model for a population with high carrying capacity around (λ?μ)/θ. The article reports in a self-contained manner on the asymptotic properties of the time to extinction for this logistic branching process as θ → 0. All three reproduction regimes λ > μ, λ < μ, and λ = μ are studied.     

Multicriteria scheduling optimization using an elitist multiobjective population heuristic: the h-NSDE algorithm

In today’s manufacturing industry more than one performance criteria are considered for optimization to various degrees simultaneously. To deal with such hard competitive environments it is essential to develop appropriate multicriteria scheduling approaches. In this paper consideration is given to the problem of scheduling n independent jobs on a single machine with due dates and objective to simultaneously minimize three performance criteria namely, total weighted tardiness (TWT), maximum tardiness and maximum earliness. In the single machine scheduling literature no previous studies have been performed on test problems examining these criteria simultaneously. After positioning the problem within the relevant research field, we present a new heuristic algorithm for its solution. The developed algorithm termed the hybrid non-dominated sorting differential evolution (h-NSDE) is an extension of the author’s previous algorithm for the single-machine mono-criterion TWT problem. h-NSDE is devoted to the search for Pareto-optimal solutions. To enable the decision maker for evaluating a greater number of alternative non-dominated solutions, three multiobjective optimization approaches have been implemented and tested within the context of h-NSDE: including a weighted-sum based approach, a fuzzy-measures based approach which takes into account the interaction among the criteria as well as a Pareto-based approach. Experiments conducted on existing data set benchmarks problems show the effect of these approaches on the performance of the h-NSDE algorithm. Moreover, comparative results between h-NSDE and some of the most popular multiobjective metaheuristics including SPEA2 and NSGA-II show clear superiority for h-NSDE in terms of both solution quality and solution diversity.     

Fast calculation of multiobjective probability of improvement and expected improvement criteria for Pareto optimization

The use of surrogate based optimization (SBO) is widely spread in engineering design to reduce the number of computational expensive simulations. However, “real-world” problems often consist of multiple, conflicting objectives leading to a set of competitive solutions (the Pareto front). The objectives are often aggregated into a single cost function to reduce the computational cost, though a better approach is to use multiobjective optimization methods to directly identify a set of Pareto-optimal solutions, which can be used by the designer to make more efficient design decisions (instead of weighting and aggregating the costs upfront). Most of the work in multiobjective optimization is focused on multiobjective evolutionary algorithms (MOEAs). While MOEAs are well-suited to handle large, intractable design spaces, they typically require thousands of expensive simulations, which is prohibitively expensive for the problems under study. Therefore, the use of surrogate models in multiobjective optimization, denoted as multiobjective surrogate-based optimization, may prove to be even more worthwhile than SBO methods to expedite the optimization of computational expensive systems. In this paper, the authors propose the efficient multiobjective optimization (EMO) algorithm which uses Kriging models and multiobjective versions of the probability of improvement and expected improvement criteria to identify the Pareto front with a minimal number of expensive simulations. The EMO algorithm is applied on multiple standard benchmark problems and compared against the well-known NSGA-II, SPEA2 and SMS-EMOA multiobjective optimization methods.     

Multiple positive solutions of nonhomogeneous elliptic systems with strongly indefinite structure and critical Sobolev exponents

In this paper, we study the existence of multiple positive solutions to some Hamiltonian elliptic systems −Δv=λu+u^p+εf(x), −Δu=μv+v^q+δg(x) in Ω;u,v>0 in Ω; u=v=0 on ∂Ω, where Ω is a bounded domain in R^N (N?3); 0?f, g∈L∞(Ω); 1/(p+1)+1/(q+1)=(N−2)/N, p,q>1; λ,μ>0. Using sub- and supersolution method and based on an adaptation of the dual variational approach, we prove the existence of at least two nontrivial positive solutions for all λ,μ∈(0,λ₁) and ε,δ∈(0,δ₀), where λ₁ is the first eigenvalue of the Laplace operator −Δ with zero Dirichlet boundary conditions and δ₀ is a positive number.     

The Rotation Number Approach to the Periodic Fuc caron ik Spectrum

In this paper, we study the Fu?ik spectrum of the problem: (^*) ?+(λ₊+q₊(t))x₊+(λ₋+q₋(t))x₋=0 with the 2π-periodic boundary condition, where q_±(t) are 2π-periodic. After introducing a rotation number function ρ(λ₊, λ₋) for (^*), we prove using the Hamiltonian structure and the positive homogeneity of (^*) that for any positive integer n, the two boundary curves of the domain ρ⁻¹(n/2) in the (λ₊, λ₋)-plane are Fu?ik curves of (^*). The result obtained in this paper shows that such a spectrum problem is much like that of the higher dimensional Fu?ik spectrum with the Dirichlet condition. In particular, it remains open if the Fu?ik spectrum of (^*) is composed of only these curves.     

Approximation of the semigroup generated by the Hamiltonian of Reggeon field theory in Bargmann space

The Reggeon field theory is governed by a non-self adjoint operator constructed as a polynomial in A, A^*, the standard Bose annihilation and creation operators. In zero transverse dimension, this Hamiltonian acting in Bargmann space is defined by

Hλ^′,μ=λ^′A*2A²+μA^*A+iλA^*(A^*+A)A,     

On exterior powers of endomorphisms

Let V be an n-dimensional vector space and T?Hom(V,V). The first result shows that if C_m(T), the mth compound of T, possesses a basis of eigenvectors, then it possesses a basis consisting of decomposable eigenvectors in the mth Grassman space over V. The paper also contains a simplified proof of a recent result of S. Belcerzyk on traces of compounds as well as conditions for the equality of fixed coefficients in the polynomials det(λA+μX) and det(λB+μX).     

The distance from a matrix polynomial to matrix polynomials with a prescribed multiple eigenvalue

For a matrix polynomial P(λ) and a given complex number μ, we introduce a (spectral norm) distance from P(λ) to the matrix polynomials that have μ as an eigenvalue of geometric multiplicity at least κ, and a distance from P(λ) to the matrix polynomials that have μ as a multiple eigenvalue. Then we compute the first distance and obtain bounds for the second one, constructing associated perturbations of P(λ).     

Construction of nonnegative symmetric matrices with given spectrum

Let σ = (λ₁, … , λ_n) be the spectrum of a nonnegative symmetric matrix A with the Perron eigenvalue λ₁, a diagonal entry c and let τ = (μ₁, … , μ_m) be the spectrum of a nonnegative symmetric matrix B with the Perron eigenvalue μ₁. We show how to construct a nonnegative symmetric matrix C with the spectrum

(λ₁+max{0,μ₁-c},λ₂,…,λ_n,μ₂,…,μ_m).     

A multiobjective immune algorithm based on a multiple-affinity model

This paper presents a new multiobjective immune algorithm based on a multiple-affinity model inspired by immune system (MAM-MOIA). The multiple-affinity model builds the relationship model among main entities and concepts in multiobjective problems (MOPs) and multiobjective evolutionary algorithms (MOEAs), including feasible solution, variable space, objective space, Pareto-optimal set, ranking and crowding distance. In the model, immune operators including clonal proliferation, hypermutation and immune suppression are designed to proliferate superior antibodies and suppress the inferiors. MAM-MOIA is compared with NSGA-II, SPEA2 and NNIA in solving the ZDT and DTLZ standard test problems. The experimental study based on three performance metrics including coverage of two sets, convergence and spacing proves that MAM-MOIA is effective for solving MOPs.     

Parallel multiobjective evolutionary algorithms for batch scheduling in heterogeneous computing and grid systems

This article presents six parallel multiobjective evolutionary algorithms applied to solve the scheduling problem in distributed heterogeneous computing and grid systems. The studied evolutionary algorithms follow an explicit multiobjective approach to tackle the simultaneous optimization of a system-related (i.e. makespan) and a user-related (i.e. flowtime) objectives. Parallel models of the proposed methods are developed in order to efficiently solve the problem. The experimental analysis demonstrates that the proposed evolutionary algorithms are able to efficiently compute accurate results when solving standard and new large problem instances. The best of the proposed methods outperforms both deterministic scheduling heuristics and single-objective evolutionary methods previously applied to the problem.     

Small eigenvalues of large Hermitian moment matrices

We consider an infinite Hermitian positive definite matrix M which is the moment matrix associated with a measure μ with infinite and compact support on the complex plane. We prove that if the polynomials are dense in L²(μ) then the smallest eigenvalue λn of the truncated matrix Mn of M of size (n+1)×(n+1) tends to zero when n tends to infinity. In the case of measures in the closed unit disk we obtain some related results.     

Explicit error terms for asymptotic expansions of Mellin convolutions

Explicit expressions are derived for the error terms associated with the asymptotic expansions of the convolution integral $\text{I(λ) = ∝}{}_0{}^{\mathrm{\infty }}\text{?(t) h(λt) dt}$, where h(t) and $\text{?(t)}$ are algebraically dominated at both 0⁺ and + ∞. Examples included are Fourier, Bessel, generalized Stieltjes, Hilbert and “potential” transforms.