Keywords

1 Introduction

The Unconstrained Binary Quadratic Programming (UBQP) problem is a classic NP-hard combinatorial problem with a number of applications [15]. The UBQP problem is extended into multi-objective case in [13], where the multiple objectives are to be maximized simultaneously, then the multi-objective UBQP problem can mathematically be formulated as follows [14]:

$$\begin{aligned} f_k(x) = x'Q^kx=\sum _{i=1}^{n}\sum _{j=1}^{n}q^k_{ij}x_{i}x_{j} \end{aligned}$$
(1)

where \(Q^k=(q^k_{ij})\) is an \(n\times n\) matrix of constants and x is an n-vector of binary (zero-one) variables, i.e., \(x_{i} \in \{0, 1\} \ (i=1, \ldots , n), \ k \in \{1, \ldots , m\}\).

UBQP is notable for its ability to formulate a wide range of other practical problems in different fields, such as machine scheduling [1], traffic management [8], computer aided design [12], financial analysis [16], etc. Many heuristic and metaheuristic algorithms have been proposed to tackle UBQP in the literature [11], such as simulated annealing [2], scatter search [3], tabu search [9], memetic algorithms [17], etc.

Moreover, A. Liefooghe et al. [13] proposed a hybrid metaheuristic algorithm to solve the multi-objective UBQP problem, which combines an elitist evolutionary multi-objective optimization algorithm with an effective single-objective tabu search procedure based on the scalarizing function. In [14], they proposed the multi-objective local search algorithms with three different strategies to solve the bi-objective UBQP problem more efficiently.

In this paper, we propose a multi-objective genetic algorithm to solve the bi-objective UBQP problem. This algorithm integrates the uniform crossover within the hypervolume-based multi-objective optimization framework for further improvements. Actually, there are two main components: hypervolume contribution selection and genetic algorithm with uniform crossover. The hypervolume contribution selection procedure iteratively improve the Pareto approximation set until it can not be improved any more. Then, the uniform crossover is used to further improve the whole quality of the Pareto approximation set.

This paper is organized as follows. In the next section, we introduce the basic notations and definitions of multi-objective optimization. In Sect. 3, we briefly review the previous work related to the uniform crossover and the multi-parent crossover. Afterwards, we present our proposed multi-objective genetic algorithm in Sect. 4. Section 5 provides the computational results and analyze the behavior of the proposed algorithm. Finally, the conclusions are provided in the last section.

2 Multi-objective Optimization

In this section, we present the basic notations and definitions of multi-objective optimization. Let X denote the search space of the optimization problem under consideration and Z the corresponding objective space. Without loss of generality, we assume that \(Z = \mathfrak {R}^n\) and that all n objectives are to be maximized. Each \(x \in X\) is assigned exactly one objective vector \(z \in Z\) on the basis of a vector function \(f : X \rightarrow Z\) with \(z = f(x)\), and the mapping f defines the evaluation of a solution \(x \in X\) [7]. Actually, we are often interested in those solutions that are Pareto optimal with respect to f. The relation \(x_1 \succ x_2\) means that the solution \(x_1\) is preferable to \(x_2\). The dominance relation between two solutions \(x_1\) and \(x_2\) is often defined as follows [7]:

Definition 1

(Pareto Dominance). A decision vector \(x_1\) is said to dominate another decision vector \(x_2\) (written as \(x_1 \succ x_2\)), if \(f_i(x_1) \ge f_i(x_2)\) for all \(i \in \{1,\dots ,n\}\) and \(f_j(x_1)>f_j(x_2)\) for at least one \(j \in \{1,\dots ,n\}\).

Definition 2

(Pareto Optimal Solution). \(x \in X\) is said to be Pareto optimal if and only if there does not exist another solution \(x' \in X\) such that \(x' \succ x\).

Definition 3

(Pareto Optimal Set). S is said to be a Pareto optimal set if and only if S is composed of all the Pareto optimal solutions.

Definition 4

(Non-Dominated Solution). \(x \in S\) \((S \subset X)\) is said to be non-dominated if and only if there does not exist another solution \(x' \in S\) such that \(x' \succ x\).

Definition 5

(Non-Dominated Set). S is said to be a non-dominated set if and only if any two solutions \(x_1 \in S\) and \(x_2 \in S\) such that \(x_1 \nsucc x_2\) and \(x_2 \nsucc x_1\).

Since there does not exist the total order relation among all the solutions in multi-objective optimization, the aim is to generate the Pareto optimal set, which keeps the best compromise among all the objectives. Nevertheless, in most cases, it is impossible to generate the Pareto optimal set in a reasonable time. Therefore, we are interested in finding a non-dominated set which is as close to the Pareto optimal set as possible, and the whole goal is often to identify a good Pareto approximation set.

3 Previous Work

The Genetic Algorithms (GA) have a good potential of solving many different combinatorial optimization problems, which are often integrated into the hybrid metaheuristics as an important part for further improvements [7]. In this section, we provide a literature review of the studies related to the uniform crossover and the multi-parent crossover.

U. Benlic et al. [6] proposed a powerful population-based memetic algorithm for solving quadratic assignment problem, which integrates an effective local optimization algorithm within the evolutionary computing framework based on a uniform crossover. In this algorithm, the uniform crossover is used to further enforce the search capacity of the proposed algorithm. The extensive computational studies reveal that their proposed algorithm is very competitive.

E. D. Paolo et al. [10] proposed an efficient genetic algorithm with uniform crossover for solving the multi-objective airport gate assignment problem. In this algorithm, a new defined uniform crossover operator is used to generate high-quality offsprings, which is crucial to the successful implementations. The extensive simulation studies illustrate the advantages of the proposed GA scheme with the uniform crossover operator.

Zhipeng Lü et al. [15] presented a multi-parent hybrid genetic-tabu algorithm for dealing with unconstrained binary quadratic programming problem, which incorporates the tabu search procedure into the genetic algorithm framework. In this algorithm, a multi-parent crossover operator called MSX is jointly employed with the conventional uniform crossover to generate diversified new solutions. The computational results on 10 large benchmark instances indicate that the proposed algorithm is very effective.

Yang Wang et al. [18] integrated four multi-parent crossover operators (called MSX, Diagonal, U-Scan and OB-Scan) within the memetic algorithm framework for dealing with unconstrained binary quadratic programming problem. Their proposed algorithms apply these crossover operators to further improve the results generated by the tabu search procedure. The experimental results and the analysis on the behavior of the algorithm provide the evidences and the insights as to key role of the crossover operators.

4 Multi-Objective Genetic Algorithm

The Multi-Objective Genetic Algorithm (MOGA) is proposed to solve the bi-objective UBQP problem, which is composed of two main components: hypervolume contribution selection and genetic algorithm with the uniform crossover. The general scheme of this algorithm is described in Algorithm 1.

figure a

In MOGA, all the solutions in an initial population are randomly generated, i.e., each variable of one solution is randomly assigned a value 0 and 1 (Step 1). Then, each solution is computed a fitness value by the Hypervolume Contribution (HC) indicator defined in [5] (Step 3).

After realizing the fitness assignment, we optimize the initial population with the hypervolume contribution selection procedure in order to obtain a Pareto approximation set. Afterwards, we apply the uniform crossover operator to generate the offsprings, in order to update the Pareto approximation set A for further improvements.

4.1 Hypervolume Contribution Selection

In order to generate a set of efficient individuals used for generating high-quality offsprings with the uniform crossover operator, we apply the Hypervolume Contribution Selection (HCS) procedure presented in Algorithm 2 to the initial population.

figure b

For the UBQP problem, we flip the value 0 (or 1) of the \(k^{th}\) variable of each solution \(x \in P\) to 1 (or 0) to obtain a new solution \(x^*\) as the neighbor of x. Then, we compute the objective function values of this new solution with the fast incremental neighborhood evaluation formula [15] below:

$$\begin{aligned} \varDelta _{i}=(1-2x_{i})(q_{ii}+\sum _{j\in N, j\ne i,x_{j}=1}q_{ij}) \end{aligned}$$
(2)

Actually, the move value \(\varDelta _{i}\) can be computed in linear time, which makes the local search procedure more efficiently.

In the HCS procedure, one solution \(x^*\), which is one of the unexplored neighbors of x in the population P, is assigned to a fitness value by the HC indicator. If \(x^*\) is dominated, the fitness values of all the solutions in P keep unchanged. If \(x^*\) is non-dominated, we need to update the fitness values of non-dominated neighbors of \(x^*\) in the objective space.

Afterwards, the solution \(\omega \) with the worst fitness value is removed from the population P. If \(\omega \) is dominated, the fitness values of the other solutions keep unchanged. If \(\omega \) is non-dominated, the fitness values of the non-dominated neighbors of \(\omega \) need to be updated. The whole procedure will repeat until the termination criterion is satisfied.

4.2 Genetic Algorithm

The uniform crossover operator is widely used to solve many combinatorial optimization problems, such as quadratic assignment problem [6], gate assignment problem [10], single-objective UBQP problem [15], and so on. In this work, we employ the uniform crossover operator to improve the Pareto approximation set A generated by the HCS procedure. The exact steps are given in Algorithm 3.

figure c

In the genetic algorithm, we randomly select two non-dominated solutions as two parents from the Pareto approximation set A. For the crossover process, we employ the standard uniform crossover operator to recombine the selected parents.

Fig. 1.
figure 1

An example of the uniform crossover for UBQP.

Full size image

Furthermore, the elements of the parents are scanned from left to right, and each element in the offspring keeps the value \(x_i\) (0 or 1) in either of these two parents with the equal probability. The unassigned variables in the offspring is given 0 or 1 randomly. An example of this crossover process is illustrated in Fig. 1.

Fig. 2.
figure 2

An example of the mutation for UBQP.

Full size image

Afterwards, we apply the mutation procedure to the generated offspring by randomly flipping the value of one variable to the opposite value (0 or 1), in order to generate a new offspring. An example of the mutation procedure is illustrated in Fig. 2. Then, we insert this new offspring into the Pareto approximation set A with the HC indicator for further improvements.

5 Experiments

In this section, we first present the parameter settings for the MOGA algorithm. Then, we introduce a performance assessment protocol used to evaluate the effectiveness of multi-objective optimization algorithm. Finally, we provide the computational results and the performance analysis.

5.1 Parameters Settings

The MOGA algorithm is programmed in C++ and compiled using Dev-C++ 5.0 compiler on a PC running Windows 7 with Core 2.50 GHz CPU and 4 GB RAM. In order to evaluate the efficiency of our proposed algorithm, we carry out the experiments on 10 benchmark instances of bi-objective UBQP problem, which are generated by the tools provided in [13].

Besides, this algorithm requires to set a few parameters, we mainly discuss two important ones: the running time and the population size. The precise information about the instances and the parameter settings is presented in Table 1.

Table 1. Parameter settings used for bi-objective UBQP instances: instance dimension (D), population size (P) and running time (T).
Full size table

5.2 Performance Assessment Protocol

In this paper, we evaluate the effectiveness of multi-objective optimization algorithms using a test procedure that has been undertaken with the performance assessment package provided by Zitzler et al.Footnote 1.

The quality assessment protocol works as follows: we first create a set of 20 runs with different initial populations for each algorithm and each benchmark instance. Afterwards, we calculate the reference set \(PO^*\) in order to determine the quality of k different sets \(A_0\dots A_{k-1}\) of non-dominated solutions. Furthermore, we define a reference point \(z=[w_1,w_2]\), where \(w_1\) and \(w_2\) represent the worst values for each objective function in \(A_0\cup \dots \cup A_{k-1}\). Then, the evaluation of a set \(A_i\) of solutions can be determined by finding the hypervolume difference between \(A_i\) and \(PO^*\) [19], and this hypervolume difference has to be as close as possible to zero.

5.3 Computational Results

In this subsection, we provide the computational results obtained by our proposed MOGA algorithm, the indicator-based multi-objective local search algorithm (IBMOLS) proposed in [4] and the hypervolume-based multi-objective local search algorithm (HBMOLS) proposed in [5].

The computational results are summarized in Table 2. Each line in this table contains a value both in bold and in grey box, which is the best result obtained on the considered instance. The another two values refer to that the corresponding algorithms are statistically outperformed by the algorithm which obtains the best result (with a confidence level greater than 95 %).

Table 2. The computational results on bi-objective UBQP problem obtained by the algorithms: IBMOLS, HBMOLS and MOGA
Full size table

According to Table 2, we can see that all the best results are obtained by MOGA, which statistically outperforms the algorithms IBMOLS and HBMOLS on all the instances. Moreover, the most significant result is achieved on the instance bubqp_5000_02, where the average hypervolume difference value obtained by MOGA is much smaller (about 15 times) than the values obtained by IBMOLS and HBMOLS.

Compared with IBMOLS and HBMOLS, we can see the evident contribution of the uniform crossover in MOGA. We assume that IBMOLS and HBMOLS could be often trapped in the local optima after a certain amount of running time, since they only focus on the local search procedure without any strategy used for jumping out of the local optima.

For MOGA, the uniform crossover is used to generate two new solutions, which are inserted into the Pareto approximation set for further improvements. In fact, these new generated solutions make MOGA have a chance to jump out of the local optima. The computational results indicate the uniform crossover evidently improve the quality of the Pareto approximation set. Therefore, MOGA has a better performance on all the instances.

6 Conclusion

In this paper, we have presented a simple and effective multi-objective genetic algorithm for the well-known bi-objective unconstrained binary quadratic programming problem. The proposed algorithm has combined the hypervolume-based optimization with the standard uniform crossover for the further improvements on the Pareto approximation set. We have evaluated this algorithm on the set of 10 benchmark instances, and the computational results indicate that the MOGA algorithm performs very well on these instances.