The influence of the fitness evaluation method on the performance of multiobjective search algorithms

In this paper we are concerned with finding the Pareto optimal front or a good approximation to it. Since non-dominated solutions represent the goal in multiobjective optimisation, the dominance relation is frequently used to establish preference between solutions during the search. Recently, relaxed forms of the dominance relation have been proposed in the literature for improving the performance of multiobjective search methods. This paper investigates the influence of different fitness evaluation methods on the performance of two multiobjective methodologies when applied to a highly constrained two-objective optimisation problem. The two algorithms are: the Pareto archive evolutionary strategy and a population-based annealing algorithm. We demonstrate here, on a highly constrained problem, that the method used to evaluate the fitness of candidate solutions during the search affects the performance of both algorithms and it appears that the dominance relation is not always the best method to use.     

A parallel competitive colonial algorithm for JIT flowshop scheduling

This paper proposes two parallel algorithms which are improved by heuristics for a bi-objective flowshop scheduling problem with sequence-dependent setup times in a just-in-time environment. In the proposed algorithms, the population will be decomposed into the several sub-populations in parallel. Multiple objectives are combined with min–max method then each sub-population evolves separately in order to obtain a good approximation of the Pareto-front. After unifying the obtained results, we propose a variable neighborhood algorithm and a hybrid variable neighborhood search/tabu search algorithm to improve the Pareto-front. The non-dominated sets obtained from our proposed algorithms, a genetic local search and restarted iterated Pareto greedy algorithm are compared. It is found that most of the solutions in the net non-dominated front are yielded by our proposed algorithms.     

A simulated annealing based genetic local search algorithm for multi-objective multicast routing problems

This paper presents a new hybrid evolutionary algorithm to solve multi-objective multicast routing problems in telecommunication networks. The algorithm combines simulated annealing based strategies and a genetic local search, aiming at a more flexible and effective exploration and exploitation in the search space of the complex problem to find more non-dominated solutions in the Pareto Front. Due to the complex structure of the multicast tree, crossover and mutation operators have been specifically devised concerning the features and constraints in the problem. A new adaptive mutation probability based on simulated annealing is proposed in the hybrid algorithm to adaptively adjust the mutation rate according to the fitness of the new solution against the average quality of the current population during the evolution procedure. Two simulated annealing based search direction tuning strategies are applied to improve the efficiency and effectiveness of the hybrid evolutionary algorithm. Simulations have been carried out on some benchmark multi-objective multicast routing instances and a large amount of random networks with five real world objectives including cost, delay, link utilisations, average delay and delay variation in telecommunication networks. Experimental results demonstrate that both the simulated annealing based strategies and the genetic local search within the proposed multi-objective algorithm, compared with other multi-objective evolutionary algorithms, can efficiently identify high quality non-dominated solution set for multi-objective multicast routing problems and outperform other conventional multi-objective evolutionary algorithms in the literature.     

Heuristics for a coupled-operation scheduling problem

In this paper, we study a strongly NP-hard single machine scheduling problem in which each job consists of two operations that are separated by a time delay which lies within a specified range. The objective is to minimize the makespan. Determining the feasibility and, if applicable, makespan of any proposed permutation of the operations is non-trivial, requiring a longest path algorithm with O(n²) complexity for each permutation. Several heuristic algorithms are proposed: a deterministic and randomized construction algorithm, three descent algorithms and two reactive tabu search algorithms. The local search algorithms use a first improvement neighbourhood and mainly visit only feasible solutions within the search space. Results of extensive computational tests are reported, showing that the heavy computational burden of testing potential solutions renders the local search algorithms uncompetitive in comparison to the construction algorithms. The iterated descent algorithm performs least well.     

Multicriteria optimization with a multiobjective golden section line search

This work presents an algorithm for multiobjective optimization that is structured as: (i) a descent direction is calculated, within the cone of descent and feasible directions, and (ii) a multiobjective line search is conducted over such direction, with a new multiobjective golden section segment partitioning scheme that directly finds line-constrained efficient points that dominate the current one. This multiobjective line search procedure exploits the structure of the line-constrained efficient set, presenting a faster compression rate of the search segment than single-objective golden section line search. The proposed multiobjective optimization algorithm converges to points that satisfy the Kuhn-Tucker first-order necessary conditions for efficiency (the Pareto-critical points). Numerical results on two antenna design problems support the conclusion that the proposed method can solve robustly difficult nonlinear multiobjective problems defined in terms of computationally expensive black-box objective functions.     

CHESS—Changing Horizon Efficient Set Search: A Simple Principle for Multiobjective Optimization

This paper presents a new concept for generating approximations to the non-dominated set in multiobjective optimization problems. The approximation set A is constructed by solving several single-objective minimization problems in which a particular function D(A, z) is minimized. A new algorithm to calculate D(A, z) is proposed.No general approach is available to solve the one-dimensional optimization problems, but metaheuristics based on local search procedures are used instead. Tests with multiobjective combinatorial problems whose non-dominated sets are known confirm that CHESS can be used to approximate the non-dominated set. Straightforward parallelization of the CHESS approach is illustrated with examples.The algorithm to calculate D(A, z) can be used in any other applications that need to determine Tchebycheff distances between a point and a dominant-free set.     

New simulation-based frameworks for multi-objective reliability-based design optimization of structures

In the present study, two new simulation-based frameworks are proposed for multi-objective reliability-based design optimization (MORBDO). The first is based on hybrid non-dominated sorting weighted simulation method (NSWSM) in conjunction with iterative local searches that is efficient for continuous MORBDO problems. According to NSWSM, uniform samples are generated within the design space and, then, the set of feasible samples are separated. Thereafter, the non-dominated sorting operator is employed to extract the approximated Pareto front. The iterative local sample generation is then performed in order to enhance the accuracy, diversity, and increase the extent of non-dominated solutions. In the second framework, a pseudo-double loop algorithm is presented based on hybrid weighted simulation method (WSM) and the Non-dominated Sorting Genetic Algorithm II (NSGA-II) that is efficient for problems including both discrete and continuous variables. According to hybrid WSM-NSGA-II, proper non-dominated solutions are produced in each generation of NSGA-II and, subsequently, WSM evaluates the reliability level of each candidate solution until the algorithm converges to the true Pareto solutions. The valuable characteristic of presented approaches is that only one simulation run is required for WSM during entire optimization process, even if solutions for different levels of reliability be desired. Illustrative examples indicate that NSWSM with the proposed local search strategy is more efficient for small dimension continuous problems. However, WSM-NSGA-II outperforms NSWSM in terms of solutions quality and computational efficiency, specifically for discrete MORBDOs. Employing global optimizer in WSM-NSGA-II provided more accurate results with lower samples than NSWSM.     

Multiobjective big data optimization based on a hybrid salp swarm algorithm and differential evolution

This paper developed a multiobjective Big Data optimization approach based on a hybrid salp swarm algorithm and the differential evolution algorithm. The role of the differential evolution algorithm is to enhance the capability of the feature exploitation of the salp swarm algorithm because the operators of the differential evolution algorithm are used as local search operators. In general, the proposed method contains three stages. In the first stage, the population is generated, and the archive is initialized. The second stage updates the solutions using the hybrid salp swarm algorithm and the differential evolution algorithm, and the final stage determines the nondominated solutions and updates the archive. To assess the performance of the proposed approach, a series of experiments were performed. A set of single-objective and multiobjective problems from the 2015 Big Data optimization competition were tested; the dataset contained data with and without noise. The results of our experiments illustrated that the proposed approach outperformed other approaches, including the baseline nondominated sorting genetic algorithm, on all test problems. Moreover, for single-objective problems, the score value of the proposed method was better than that of the traditional multiobjective salp swarm algorithm. When compared with both algorithms, that is, the adaptive DE algorithm with external archive and the hybrid multiobjective firefly algorithm, its score was the largest. In contrast, for the multiobjective functions, the scores of the proposed algorithm were higher than that of the fireworks algorithm framework.     

Helper-objectives: Using multi-objective evolutionary algorithms for single-objective optimisation

This paper investigates the use of multi-objective methods to guide the search when solving single-objective optimisation problems with genetic algorithms. Using the job shop scheduling and travelling salesman problems as examples, experiments demonstrate that the use of helper-objectives (additional objectives guiding the search) significantly improves the average performance of a standard GA. The helper-objectives guide the search towards solutions containing good building blocks and help the algorithm escape local optima. The experiments reveal that the approach works if the number of simultaneously used helper-objectives is low. However, a high number of helper-objectives can be used in the same run by changing the helper-objectives dynamically. The experiments reveal that for the majority of problem instances studied, the proposed approach significantly outperforms a traditional GA.The experiments also demonstrate that controlling the proportion of non-dominated solutions in the population is very important when using helper-objectives, since the presence of too many non-dominated solutions removes the selection pressure in the algorithm.     

Gradient projection and local region search for multiobjective optimisation

This paper presents a new method for multiobjective optimisation based on gradient projection and local region search. The gradient projection is conducted through the identification of normal vectors of an efficient frontier. The projection of the gradient of a nonlinear utility function onto the tangent plane of the efficient frontier at a given efficient solution leads to the definition of a feasible local region in a neighbourhood of the solution. Within this local region, a better efficient solution may be sought. To implement such a gradient-based local region search scheme, a new auxiliary problem is developed. If the utility function is given explicitly, this search scheme results in an iterative optimisation algorithm capable of general nonseparable multiobjective optimisation. Otherwise, an interactive decision making algorithm is developed where the decision maker (DM) is expected to provide local preference information in order to determine trade-off directions and step sizes. Optimality conditions for the algorithms are established and the convergence of the algorithms is proven. A multiobjective linear programming (MOLP) problem is taken for example to demonstrate this method both graphically and analytically. A nonlinear multiobjective water quality management problem is finally examined to show the potential application of the method to real world decision problems.     

A comparison of local search methods for flow shop scheduling

Local search techniques are widely used to obtain approximate solutions to a variety of combinatorial optimization problems. Two important categories of local search methods are neighbourhood search and genetic algorithms. Commonly used neighbourhood search methods include descent, threshold accepting, simulated annealing and tabu search. In this paper, we present a computational study that compares these four neighbourhood search methods, a genetic algorithm, and a hybrid method in which descent is incorporated into the genetic algorithm. The performance of these six local search methods is evaluated on the problem of scheduling jobs in a permutation flow shop to minimize the total weighted completion time. Based on the results of extensive computational tests, simulated annealing is found to generate better quality solutions than the other neighborhood search methods. However, the results also indicate that the hybrid genetic descent algorithm is superior to simulated annealing.     

A hybrid quantum-inspired immune algorithm for multiobjective optimization

This study suggests a novel quantum immune algorithm for finding Pareto-optimal solutions to multiobjective optimization problems based on quantum computing and immune system. In the proposed algorithm, there are distinct characteristics as follows. First, the encoding method is based on Q-bit representation, and thus a chaos-based approach is suggested to initialize the population. Second, a new chaos-based rotation gate and Q-gates are presented to perform mutation and improve the quality of the population, respectively. Finally, especially, a new truncation algorithm with similar individuals (TASI) is utilized to preserve the diversity of the population. Also, a new selection operator is proposed to create the new population based on TASI. Simulation results on six standard problems (ZDT6, CP, SP, VNT, OSY and KIT) show the proposed algorithm is able to find a much better spread of solutions and has better convergence near the true Pareto-optimal front compared to the vector immune algorithm (VIS) and the elitist non-dominated sorting genetic system (NSGA-II).     

On the structure of multiobjective combinatorial search space: MNK-landscapes with correlated objectives

The structure of the search space explains the behavior of multiobjective search algorithms, and helps to design well-performing approaches. In this work, we analyze the properties of multiobjective combinatorial search spaces, and we pay a particular attention to the correlation between the objective functions. To do so, we extend the multiobjective NK-landscapes in order to take the objective correlation into account. We study the co-influence of the problem dimension, the degree of non-linearity, the number of objectives, and the objective correlation on the structure of the Pareto optimal set, in terms of cardinality and number of supported solutions, as well as on the number of Pareto local optima. This work concludes with guidelines for the design of multiobjective local search algorithms, based on the main fitness landscape features.     

Using Efficient Anchoring Points for Generating Search Directions in Interior Multiobjective Linear Programming

This paper modifies the affine-scaling primal algorithm to multiobjective linear programming (MOLP) problems. The modification is based on generating search directions in the form of projected gradients augmented by search directions pointing toward what we refer to as anchoring points. These anchoring points are located on the boundary of the feasible region and, together with the current, interior, iterate, define a cone in which we make the next step towards a solution of the MOLP problem. These anchoring points can be generated in more than one way. In this paper we present an approach that generates efficient anchoring points where the choice of termination solution available to the decision maker at each iteration consists of a set of efficient solutions. This set of efficient solutions is being updated during the iterative process so that only the most preferred solutions are retained for future considerations. Current MOLP algorithms are simplex-based and make their progress toward the optimal solution by following an exterior trajectory along the vertices of the constraints polytope. Since the proposed algorithm makes its progress through the interior of the constraints polytope, there is no need for vertex information and, therefore, the search for an acceptable solution may prove less sensitive to problem size. We refer to the resulting class of MOLP algorithms that are based on the affine-scaling primal algorithm as affine-scaling interior multiobjective linear programming (ASIMOLP) algorithms.     

A Multiobjective Hybrid Metaheuristic Approach for GIS-based Spatial Zoning Model

This paper presents a multiobjective hybrid metaheuristic approach for an intelligent spatial zoning model in order to draw territory line for geographical or spatial zone for the purpose of space control. The model employs a Geographic Information System (GIS) and uses multiobjective combinatorial optimization techniques as its components. The proposed hybrid metaheuristic consists of the symbiosis between tabu search and scatter search method and it is used heuristically to generate non-dominated alternatives. The approach works with a set of current solution, which through manipulation of weights are optimized towards the non-dominated frontier while at the same time, seek to disperse over the frontier by a strategic oscillation concept. The general procedure and its algorithms are given as well as its implementation in the GIS environment. The computation has resulted in tremendous improvements in spatial zoning.     

A study of stochastic local search algorithms for the biobjective QAP with correlated flow matrices

This paper studies the performance of two stochastic local search algorithms for the biobjective Quadratic Assignment Problem with different degrees of correlation between the flow matrices. The two algorithms follow two fundamentally different ways of tackling multiobjective combinatorial optimization problems. The first is based on the component-wise ordering of the objective value vectors of neighboring solutions, while the second is based on different scalarizations of the objective function vector. Our experimental results suggest that the performance of the algorithms with respect to solution quality and computation time depends strongly on the correlation between the flow matrices. In addition, some variants of these stochastic local search algorithms obtain very good solutions in short computation time.     

A hybrid immune multiobjective optimization algorithm

In this paper, we develop a hybrid immune multiobjective optimization algorithm (HIMO) based on clonal selection principle. In HIMO, a hybrid mutation operator is proposed with the combination of Gaussian and polynomial mutations (GP-HM operator). The GP-HM operator adopts an adaptive switching parameter to control the mutation process, which uses relative large steps in high probability for boundary individuals and less-crowded individuals. With the generation running, the probability to perform relative large steps is reduced gradually. By this means, the exploratory capabilities are enhanced by keeping a desirable balance between global search and local search, so as to accelerate the convergence speed to the true Pareto-optimal front in the global space with many local Pareto-optimal fronts. When comparing HIMO with various state-of-the-art multiobjective optimization algorithms developed recently, simulation results show that HIMO performs better evidently.     

On local optima in multiobjective combinatorial optimization problems

In this article, local optimality in multiobjective combinatorial optimization is used as a baseline for the design and analysis of two iterative improvement algorithms. Both algorithms search in a neighborhood that is defined on a collection of sets of feasible solutions and their acceptance criterion is based on outperformance relations. Proofs of the soundness and completeness of these algorithms are given.     

Computing the nadir point for multiobjective discrete optimization problems

We investigate the problem of finding the nadir point for multiobjective discrete optimization problems (MODO). The nadir point is constructed from the worst objective values over the efficient set of a multiobjective optimization problem. We present a new algorithm to compute nadir values for MODO with \(p\) objective functions. The proposed algorithm is based on an exhaustive search of the \((p-2)\)-dimensional space for each component of the nadir point. We compare our algorithm with two earlier studies from the literature. We give numerical results for all algorithms on multiobjective knapsack, assignment and integer linear programming problems. Our algorithm is able to obtain the nadir point for relatively large problem instances with up to five-objectives.     

A new dominance rule to minimize total weighted tardiness with unequal release dates

We present a new dominance rule by considering the time-dependent orderings between each pair of jobs for the single machine total weighted tardiness problem with release dates. The proposed dominance rule provides a sufficient condition for local optimality. Therefore, if any sequence violates the dominance rule then switching the violating jobs either lowers the total weighted tardiness or leaves it unchanged. We introduce an algorithm based on the dominance rule, which is compared to a number of competing heuristics for a set of randomly generated problems. Our computational results indicate that the proposed algorithm dominates the competing algorithms in all runs, therefore it can improve the upper bounding scheme in any enumerative algorithm. The proposed time-dependent local dominance rule is also implemented in two local search algorithms to guide these algorithms to the areas that will most likely contain the good solutions.