# A Variable Neighborhood MOEA/D for Multiobjective Test Task Scheduling Problem

Authors: Hui Lu; Zheng Zhu; Xiaoteng Wang; Lijuan Yin
Journal: Mathematical Problems in Engineering
 (2014)

---

## Abstract

Test task scheduling problem (TTSP) is a typical combinational optimization scheduling problem. This paper proposes a variable neighborhood MOEA/D (VNM) to solve the multiobjective TTSP. Two minimization objectives, the maximal completion time (makespan) and the mean workload, are considered together. In order to make solutions obtained more close to the real Pareto Front, variable neighborhood strategy is adopted. Variable neighborhood approach is proposed to render the crossover span reasonable. Additionally, because the search space of the TTSP is so large that many duplicate solutions and local optima will exist, the Starting Mutation is applied to prevent solutions from becoming trapped in local optima. It is proved that the solutions got by VNM can converge to the global optimum by using Markov Chain and Transition Matrix, respectively. The experiments of comparisons of VNM, MOEA/D, and CNSGA (chaotic nondominated sorting genetic algorithm) indicate that VNM performs better than the MOEA/D and the CNSGA in solving the TTSP. The results demonstrate that proposed algorithm VNM is an efficient approach to solve the multiobjective TTSP.


---

## Body

## 1. Introduction

During recent decades, the manufacturing of electronic devices has become highly integrated and increasingly complex. As a result, the resource and time consumption expended on the test of electronic devices became a crucial problem in engineering application. Therefore, the research for improving the test efficiency is a topic that has attracted extensive attention. To address this situation, the objective of this research is to solve the test task scheduling problem (TTSP) more efficiently.The goal of the TTSP is to arrange the execution ofn tasks on m instruments. It is a difficult nondeterministic polynomial (NP) problem [1] for optimization. TTSP has some similarities with flexible job shop scheduling problem (FJSP) [2, 3], but the resource configuration of the TTSP is more flexible. For example, in the TTSP, one task can be performed on more than one instrument at a time. The precedence relationships in the TTSP resemble a network. One task can have one or more former or latter tasks in the TTSP. Generally speaking, feasible solutions are more difficult to be obtained in the TTSP than that in the FJSP.TTSP, FJSP, and most scheduling problems belong to combinational optimization problems. For combinational optimization problems, the search space is too large that the best solution cannot be obtained by adopting the method of enumeration for even small-scale problem. Therefore, the intelligent algorithms based on integer programming model are devoted to solving these kinds of problems. Take FJSP as the example; genetic algorithm (GA) [4–7], simulated annealing (SA) [8–10], and the tabu search (TS) [11] have been successfully applied in solving scheduling optimization problem. FJSP receives extensive attention and researches, and many hybrid intelligent algorithms are invented for improving the performance of the solutions. For example, a combination of shuffled frog leaping and fuzzy logic is proposed to solve FJSP [12]. A particle swarm optimization (PSO) algorithm and TS algorithm are combined to solve the multiobjective FJSP [13]. A biogeography-based optimization (BBO) algorithm [14] was proposed for FJSP for finding optimum or near-optimum solution. Hybrid discrete particle swarm optimization for multiobjective flexible job-shop scheduling problem was proposed in article [15] especially for large-scale problems. The objective functions are different in each literature, but the makespan, the total tardiness, the critical machine workload, and the total workload of machines are frequently considered factors in those researches.Different from the research of FJSP, the research of TTSP is relatively few because of the development of automatic test system. However, there are still some achievements in TTSP. Xia et al. [16] proposed a method that combined GA and simulated SA to optimize the parallel efficiency and speed up ratio of the multi-UUT parallel test. Genetic Algorithm-Ant Colony Algorithm (GA-ACA) [17], hybrid particle swarm and tabu search [18] and Ant Colony Algorithm [19] are used to solve parallel test tasks scheduling to obtain the minimum makespan. A chaotic nondominated sorting genetic algorithm is proposed to solve multiobjective TTSP [20]. The chaotic operations are combined with NSGA-II [21] in this approach. Those algorithms have shown excellent property in decreasing costs and improving efficiencies in automatic test system.There are also some intelligent algorithms used to solve power dispatch problems and other scheduling problems. For example, opposition-based learning is employed in opposition-based gravitational search algorithm (OGSA) to solve optimal reactive power dispatch [22]. A fuzzified multiobjective PSO (FMOPSO) algorithm is proposed and implemented to dispatch the electric power [23]. An interactive artificial bee colony algorithm was proposed for the multiobjective environmental/economic dispatch problem [24].In summary, most of the researches of scheduling problems focus on the single-objective problem or adopt weighted sum approach to convert the multiobjective problem into a single-objective problem. However, the weighting coefficients are difficult to choose, and human factors will greatly impact the performance of the algorithms. In fact, there are another two kinds of methods for solving the multiobjective problem. One method is the non-Pareto approach utilizing operators for processing the different objectives in a separated way. Another is the Pareto approaches which are directly based on the Pareto optimality concept. They aim at satisfying two goals: converging towards the Pareto front and also obtaining diversified solutions scattered all over the Pareto front. Those two kinds of methods mainly rely on the performance and strategies of the algorithms used in the multiobjective problems.In this paper, the method based on Tchebycheff decomposition for multiobjective functions was adopted and the algorithm named MOEA/D is used to solve TTSP. MOEA/D is a typical evolutionary algorithm based on decomposition proposed by Zhang and Li [25]. This method decomposes a multiobjective optimization problem into a number of scalar optimization subproblems and optimizes them simultaneously. The results show that MOEA/D has a good performance for the ZDT and DTLZ test problems. MOEA/D is very efficient in solving multiobjective problems. Research on MOEA/D has also been performed in recent years. For example, Tan et al. [26] proposed a new version of MOEA/D with a uniform design to deal with the multiobjective problem in higher-dimensional objective spaces. This method can render the distribution of the weighting vectors more uniform, especially for problems with high dimension. Chen et al. [27] introduced a guided mutation operator and priority update to enhance the ability of MOEA/D. Stochastic ranking and constraint-domination principle are adopted in MOEA/D to improve the ability of the algorithm to deal with constrained multiobjective optimization problems [28]. Although these studies have improved the ability of MOEA/D for solving multi-objective problems, MOEA/D is mainly used to solve standard test cases like ZDT, DTLZ, and F1. However, MOEA/D is rarely used to solve combinational optimization problems such as FJSP, TTSP. Peng et al. applied MOEA/D to solve Travelling Salesman Problem (TSP) [29]. However, there is no special improvement for MOEA/D according to the feature of MOEA/D and the property of TSP.The scheduling problems, such as TTSP, FJSP, and TSP, and power dispatching problem are a branch of combinational optimization problems. Because of the properties of the combinational optimization problems, the final best solutions only account for a rather small subset of the search space. How to avoid the solutions obtained being trapped in local optima is the key to improve the ability of algorithms to deal with combinational optimization problems. Considering the fact that the size of the neighborhood is important in MOEA/D [25], too large size will lead to degradation and too small size will weaken the effect of evolutionary process. Moreover, there will be many duplicate solutions due to the influence of neighborhood updating of MOEA/D [25]. The population diversity will decrease obviously. Based on the analyses above, variable neighborhood based on a quadratic curve is adopted to ensure that the crossover span is more reasonable, and Gauss mutation is adopted at the beginning of iteration to maintain the diversity of the population. These two improvements can efficiently enhance the ability of MOEA/D for avoiding the solutions obtained from being trapped in local optima. The proposed approach cannot only solve TTSP but also deal with other scheduling problems, because the feasible solutions of TTSP are more difficult to obtain than most scheduling problems such as FJSP, TSP.The organization of this paper is as follows. A brief introduction of TTSP is introduced in Section2. The new method for TTSP, variable neighborhood MOEA/D (VNM), is proposed in Section 3. The convergence analysis of VNM is also presented in Section 4. A large number of experimental results and discussions are covered in Section 5. Conclusions are given in Section 6.


## 2. The Formulation of TTSP

### 2.1. The Mathematical Model for TTSP

The goal of the TTSP is to arrange the execution ofn tasks on m instruments. There are three main mathematical models for TTSP. One model is based on Petri net. The second is based on Graph theory. And the third model is based on integer programming. Our work in this paper is mainly based on the integer programming proposed by us in paper [20].


#### 2.1.1. The Petri Net Model for TTSP

Petri net [30, 31] was proposed in 1962. Petri net focuses on the changes of the system, the conditions for changes, the influence of changes, and the relationships between changes. We assume that there is one test task t1 in TTSP. The instruments occupied for t1 are r1, r2, and r3. The Petri net model for this TTSP can be shown as Figure 1. In this model, there are four places (p1, p2, p3, and p4), one transition (t1), three tokens (r1, r2, and r3), three variables (v1,v2, and v3), four arc expressions (v1, v2, v3, and (v1,v2,v3)), and a guard ([r1,r2,r3]), where v1, v2, and v3 are bound to r1, r2, and r3.Figure 1
The Petri net model for one task TTSP.In Figure1, at the beginning, test resources r1, r2, and r3 are vacant. The corresponding tokens for three places p1, p2, and p3 are r1, r2, and r3, respectively. Therefore, r1, r2, and r3 can be allocated to t1. When the t1 is finished, the tokens in p1, p2, and p3 will be transferred to place p4. The tokens in p4 are v1, v2, and  v3. This means that resources r1, r2, and r3 are released. The Petri net can describe the relationships between tasks by the places and transitions, but the complex models are needed to be established. The process will increase the development cost and extend the development cycle.


#### 2.1.2. The Graph Theory Model for TTSP

Graph theory [32] is an important branch of mathematics. By adopting the Graph theory, the complex project planning and processing can be described using “graphs.” In TTSP, the vertexes of the graph represent the test tasks, and the lines between vertexes mean that some test instruments are common for these two tasks. For example, there are four test tasks (t1, t2, t3, and t4) and four test instruments (r1, r2, r3, and  r4). The instruments set needed by t1, t2, t3, t4 are {r1,r2}, {r2,r4}  {r3,r4}, and {r1,r3}, respectively. The graph for this TTSP example is shown in Figure 2.Figure 2
The Graph model for TTSP.Graph theory model can only be adopted by typical optimization methods. With the increment of the scale of TTSP, the computation expense will greatly increase, but typical optimization methods are not suitable for large-scale TTSP problem. Therefore, Graph theory model cannot solve large-scale TTSP also.


#### 2.1.3. The Integer Programming Model for TTSP

TTSP is a typical integer programming problem. For the integer programming model for TTSP, the TTSP can be described as follows [20]: assume that n tasks and m instrument are included in TTSP. There is a task set T={t1,t2,…,tj} (1≤j≤n) and an instrument set R={r1,r2,…,ri}  (1≤i≤m). Sji, Cji, and Pji represent the test start time, test finish time, and test consumed time of task tj tested on instrument ri, respectively. In the TTSP, one task can be tested on more than one instrument. A judgment matrix is used to express whether instrument ri is needed for tj. The judgment matrix is defined as the following:
(1)Oji={1iftjoccupiesri0others.In general, tasktj may have several possible test schemes. The set of test schemes for tj is defined as Wj={wj1,wj2,…,wjkj}  (kj is the number of test schemes for tj). The notation Pjk=max⁡ri∈wjk⁡Pji is used to express the test time of tj for wjk.The following describes the restriction of resources:(2)Xjj*kk*={1ifwjk∩wj*k*≠∅0others.Basic hypothesis includes three factors. At a given time, an instrument can only execute one task; each task must be completed without interruption once it starts. AssumePji=Pjk, Cji=Sji+Pji to simplify the problem.


### 2.2. The Objective Functions for TTSP

The objective functions are very important in the study of multiobjective optimization problem. The makespan is very important in scheduling problems such as TTSP and FJSP, because the completion time is an essential factor for scheduling problem in product process. In additional, for TTSP, the test instruments have high integration, and the test instruments have become increasingly expensive. Therefore, the demand for reducing the workload of the instruments and increasing the service life of the test instruments has great significance in TTSP. Therefore, our work focuses on two main objectives. One is to minimize the maximal test completion time, and the other is to minimize the mean workload of the instruments. These objectives are represented byf1(x) and f2(x).(1) The Maximal Test Completion Time
f
1
(
x
). The notification Cjk=max⁡ri∈wjk⁡Cji is the test completion time of tj for wjk. Thus, the maximal test completion time of all tasks can be defined as follows:
(3)f1(x)=max⁡1≤k≤kj1≤j≤nCjk.(2) The Mean Workload of the Instruments
f
2
(
x
). First, a new notation Q is introduced to describe the parallel steps. The initial value of Q is 1. Assign the instruments for all of the tasks, if Xjj*kk*=1, Q=Q+1. Therefore, the mean workload of the instruments can be defined as follows:
(4)f2(x)=1Q∑j=1n∑i=1mPjiOji.


## 2.1. The Mathematical Model for TTSP

The goal of the TTSP is to arrange the execution ofn tasks on m instruments. There are three main mathematical models for TTSP. One model is based on Petri net. The second is based on Graph theory. And the third model is based on integer programming. Our work in this paper is mainly based on the integer programming proposed by us in paper [20].


### 2.1.1. The Petri Net Model for TTSP

Petri net [30, 31] was proposed in 1962. Petri net focuses on the changes of the system, the conditions for changes, the influence of changes, and the relationships between changes. We assume that there is one test task t1 in TTSP. The instruments occupied for t1 are r1, r2, and r3. The Petri net model for this TTSP can be shown as Figure 1. In this model, there are four places (p1, p2, p3, and p4), one transition (t1), three tokens (r1, r2, and r3), three variables (v1,v2, and v3), four arc expressions (v1, v2, v3, and (v1,v2,v3)), and a guard ([r1,r2,r3]), where v1, v2, and v3 are bound to r1, r2, and r3.Figure 1
The Petri net model for one task TTSP.In Figure1, at the beginning, test resources r1, r2, and r3 are vacant. The corresponding tokens for three places p1, p2, and p3 are r1, r2, and r3, respectively. Therefore, r1, r2, and r3 can be allocated to t1. When the t1 is finished, the tokens in p1, p2, and p3 will be transferred to place p4. The tokens in p4 are v1, v2, and  v3. This means that resources r1, r2, and r3 are released. The Petri net can describe the relationships between tasks by the places and transitions, but the complex models are needed to be established. The process will increase the development cost and extend the development cycle.


### 2.1.2. The Graph Theory Model for TTSP

Graph theory [32] is an important branch of mathematics. By adopting the Graph theory, the complex project planning and processing can be described using “graphs.” In TTSP, the vertexes of the graph represent the test tasks, and the lines between vertexes mean that some test instruments are common for these two tasks. For example, there are four test tasks (t1, t2, t3, and t4) and four test instruments (r1, r2, r3, and  r4). The instruments set needed by t1, t2, t3, t4 are {r1,r2}, {r2,r4}  {r3,r4}, and {r1,r3}, respectively. The graph for this TTSP example is shown in Figure 2.Figure 2
The Graph model for TTSP.Graph theory model can only be adopted by typical optimization methods. With the increment of the scale of TTSP, the computation expense will greatly increase, but typical optimization methods are not suitable for large-scale TTSP problem. Therefore, Graph theory model cannot solve large-scale TTSP also.


### 2.1.3. The Integer Programming Model for TTSP

TTSP is a typical integer programming problem. For the integer programming model for TTSP, the TTSP can be described as follows [20]: assume that n tasks and m instrument are included in TTSP. There is a task set T={t1,t2,…,tj} (1≤j≤n) and an instrument set R={r1,r2,…,ri}  (1≤i≤m). Sji, Cji, and Pji represent the test start time, test finish time, and test consumed time of task tj tested on instrument ri, respectively. In the TTSP, one task can be tested on more than one instrument. A judgment matrix is used to express whether instrument ri is needed for tj. The judgment matrix is defined as the following:
(1)Oji={1iftjoccupiesri0others.In general, tasktj may have several possible test schemes. The set of test schemes for tj is defined as Wj={wj1,wj2,…,wjkj}  (kj is the number of test schemes for tj). The notation Pjk=max⁡ri∈wjk⁡Pji is used to express the test time of tj for wjk.The following describes the restriction of resources:(2)Xjj*kk*={1ifwjk∩wj*k*≠∅0others.Basic hypothesis includes three factors. At a given time, an instrument can only execute one task; each task must be completed without interruption once it starts. AssumePji=Pjk, Cji=Sji+Pji to simplify the problem.


## 2.1.1. The Petri Net Model for TTSP

Petri net [30, 31] was proposed in 1962. Petri net focuses on the changes of the system, the conditions for changes, the influence of changes, and the relationships between changes. We assume that there is one test task t1 in TTSP. The instruments occupied for t1 are r1, r2, and r3. The Petri net model for this TTSP can be shown as Figure 1. In this model, there are four places (p1, p2, p3, and p4), one transition (t1), three tokens (r1, r2, and r3), three variables (v1,v2, and v3), four arc expressions (v1, v2, v3, and (v1,v2,v3)), and a guard ([r1,r2,r3]), where v1, v2, and v3 are bound to r1, r2, and r3.Figure 1
The Petri net model for one task TTSP.In Figure1, at the beginning, test resources r1, r2, and r3 are vacant. The corresponding tokens for three places p1, p2, and p3 are r1, r2, and r3, respectively. Therefore, r1, r2, and r3 can be allocated to t1. When the t1 is finished, the tokens in p1, p2, and p3 will be transferred to place p4. The tokens in p4 are v1, v2, and  v3. This means that resources r1, r2, and r3 are released. The Petri net can describe the relationships between tasks by the places and transitions, but the complex models are needed to be established. The process will increase the development cost and extend the development cycle.


## 2.1.2. The Graph Theory Model for TTSP

Graph theory [32] is an important branch of mathematics. By adopting the Graph theory, the complex project planning and processing can be described using “graphs.” In TTSP, the vertexes of the graph represent the test tasks, and the lines between vertexes mean that some test instruments are common for these two tasks. For example, there are four test tasks (t1, t2, t3, and t4) and four test instruments (r1, r2, r3, and  r4). The instruments set needed by t1, t2, t3, t4 are {r1,r2}, {r2,r4}  {r3,r4}, and {r1,r3}, respectively. The graph for this TTSP example is shown in Figure 2.Figure 2
The Graph model for TTSP.Graph theory model can only be adopted by typical optimization methods. With the increment of the scale of TTSP, the computation expense will greatly increase, but typical optimization methods are not suitable for large-scale TTSP problem. Therefore, Graph theory model cannot solve large-scale TTSP also.


## 2.1.3. The Integer Programming Model for TTSP

TTSP is a typical integer programming problem. For the integer programming model for TTSP, the TTSP can be described as follows [20]: assume that n tasks and m instrument are included in TTSP. There is a task set T={t1,t2,…,tj} (1≤j≤n) and an instrument set R={r1,r2,…,ri}  (1≤i≤m). Sji, Cji, and Pji represent the test start time, test finish time, and test consumed time of task tj tested on instrument ri, respectively. In the TTSP, one task can be tested on more than one instrument. A judgment matrix is used to express whether instrument ri is needed for tj. The judgment matrix is defined as the following:
(1)Oji={1iftjoccupiesri0others.In general, tasktj may have several possible test schemes. The set of test schemes for tj is defined as Wj={wj1,wj2,…,wjkj}  (kj is the number of test schemes for tj). The notation Pjk=max⁡ri∈wjk⁡Pji is used to express the test time of tj for wjk.The following describes the restriction of resources:(2)Xjj*kk*={1ifwjk∩wj*k*≠∅0others.Basic hypothesis includes three factors. At a given time, an instrument can only execute one task; each task must be completed without interruption once it starts. AssumePji=Pjk, Cji=Sji+Pji to simplify the problem.


## 2.2. The Objective Functions for TTSP

The objective functions are very important in the study of multiobjective optimization problem. The makespan is very important in scheduling problems such as TTSP and FJSP, because the completion time is an essential factor for scheduling problem in product process. In additional, for TTSP, the test instruments have high integration, and the test instruments have become increasingly expensive. Therefore, the demand for reducing the workload of the instruments and increasing the service life of the test instruments has great significance in TTSP. Therefore, our work focuses on two main objectives. One is to minimize the maximal test completion time, and the other is to minimize the mean workload of the instruments. These objectives are represented byf1(x) and f2(x).(1) The Maximal Test Completion Time
f
1
(
x
). The notification Cjk=max⁡ri∈wjk⁡Cji is the test completion time of tj for wjk. Thus, the maximal test completion time of all tasks can be defined as follows:
(3)f1(x)=max⁡1≤k≤kj1≤j≤nCjk.(2) The Mean Workload of the Instruments
f
2
(
x
). First, a new notation Q is introduced to describe the parallel steps. The initial value of Q is 1. Assign the instruments for all of the tasks, if Xjj*kk*=1, Q=Q+1. Therefore, the mean workload of the instruments can be defined as follows:
(4)f2(x)=1Q∑j=1n∑i=1mPjiOji.


## 3. The Variable Neighborhood MOEA/D Algorithm

In this section, we proposed a variable neighborhood MOEA/D algorithm (VNM). To obtain solutions close to the real Pareto Front (PF) of the TTSP, two strategies are adopted. The variable neighborhood strategy helps to make the crossover span more reasonable. Moreover, Gauss mutation is adopted at the beginning of the iteration to maintain the diversity of the population.


### 3.1. The Main Strategy of the VNM

The VNM is an evolutionary algorithm based on decomposition. The main strategy of the VNM is to decompose a multiobjective optimization problem into a number of scalar optimization subproblems and optimize these subproblems simultaneously. The decomposition method used is the Tchebycheff approach [33]. Each subproblem is bound with a weight vector, and then each subproblem is updated by obtaining information from its neighborhood [25]. The neighborhood of each subproblem is determined by its weighting vector.Let{λ1,λ2,…,λN} be a set of weight vectors, and z*=(z1*,z2*,…,zm*)T is defined as the reference point. The problem of the Pareto Front approximation can be decomposed into N scalar optimization subproblems using the Tchebycheff approach, and the objective function of the jth subproblem is defined as
(5)gte(x∣λj,z*)=max⁡1≤i≤m{λij|fi(x)-zi*|},x∈Ω,
where Ω is the decision space and λj=(λ1j,λ2j,…,λmj)T, zi*=min⁡{fi(x)∣x⊂Ω} for each i=1,2,…,m. It is clear that the VNM is able to minimize all N objective functions simultaneously in a single run.The main procedure of the VNM can be described as shown in Figure3.Figure 3
The main procedure of the VNM.In the part of parameter setting, the iteration numberM, the subproblem number N, the size of neighborhood T (which ranges from beginning size B to stopping size S), and the population for saving the optimal solutions EP are set.The crossover operation in VNM is as follows.For each individualxit in generation t, the child xit+1 can be obtained by the following equation:
(6)xit+1={xit+F1×(xit-xi1t)+F2×(xit-xi2t)rand(1)<CRxitrand(1)≥CRCR, F1, and F2 are the three control variables for the crossover; xi1t and xi2t are two individuals chosen in the neighborhood of xit. This crossover method can make full use of the information from the neighborhood and render the information exchange more sufficient.The main idea of VNM is given above. Two improvements are involved in the VNM algorithm. Variable neighborhood strategy is adopted to make the crossover span more reasonable. Moreover, Starting Mutation is used to enhance the diversity of the population.


### 3.2. Variable Neighborhood

In the VNM, the size of the neighborhoodT has a high impact on the performance of the algorithm. If T is too large, the two solutions chosen (xl and xk) for the genetic operation may be unsuitable for the subproblem, and degradation may occur during the progress of the evolution. In contrast, if T is too small, the subproblems are all similar. The child individual will be so similar to its parents that the crossover operation will have a weak effect.T is the neighborhood size which determines the crossover and neighborhood updating span. Too large and too small T will both have a negative influence on VNM. Therefore, T should be large enough at the beginning of the evolution period to ensure sufficient information exchange of the solutions, and T should be sufficiently small in the latter portion of the evolution period such that degradation can be avoided. Motivated by this ideology, we designed and tested three curves to find the best T controlling curve.The three curves are shown in Figure4. In this figure, the abscissa is the number of iterations, and the ordinate is the size of the neighborhood. M1, M2, and M3 represent the straight line, the monotonic parabolic and the nonmonotonic parabolic curves, respectively. It is worth noting that in curve M2, the curvature will be 0 at the end of the evolution period. This means that the rate of change of curvature for M2 is the fastest of all of the concave monotone parabolas during the period of evolution. Because the curvature goes to 0 in the end, curve M2 is determined. Assume that if the number of iterations is 125, the neighborhood of curves M1, M2, and M3 are y1, y2, and y3, respectively, in accordance with the equation: y1-y2=y2-y3. Thus, curve M3 can be also determined. Curve M3 is a nonmonotonic parabolic curve. A series of experiments should be performed to compare the influence of the three curves on the algorithm to identify the best controlling curve.Figure 4
Three controlling curves for the neighborhood size.


### 3.3. Starting Mutation

The TTSP represents a typical combinational optimization problem. The final best solutions may be limited to only several points in the solution space. Because of the neighborhood updating effect of the VNM, there will be many duplicate solutions so that the crossover operation will have little effect. Therefore, how to maintain the diversity of the population is the key question for enhancing the algorithm effect.Motivated by the ideology above, a starting Gauss mutation is adopted at the beginning of the iteration. For a solutionxi=(x1i,x2i,…,xMi)   (M is the number of variables), Gauss mutation is described as the following:
(7)forj=1,2,…,M,xji*={normal(xji,σ)rand(1)<pxjirand(1)≥p.xi*=(x1i*,x2i*,....xMi*) represents the individual after mutation, p is the mutation probability, normal (xji,σ) is a number that obeys the normal distribution, xji is the mean value, and σ is the variance. With Starting Mutation, the problem with the initially invalid crossover operation can be resolved. Therefore, we can avoid the solutions from becoming trapped in local optima, and thus solutions with higher quality are obtained.


## 3.1. The Main Strategy of the VNM

The VNM is an evolutionary algorithm based on decomposition. The main strategy of the VNM is to decompose a multiobjective optimization problem into a number of scalar optimization subproblems and optimize these subproblems simultaneously. The decomposition method used is the Tchebycheff approach [33]. Each subproblem is bound with a weight vector, and then each subproblem is updated by obtaining information from its neighborhood [25]. The neighborhood of each subproblem is determined by its weighting vector.Let{λ1,λ2,…,λN} be a set of weight vectors, and z*=(z1*,z2*,…,zm*)T is defined as the reference point. The problem of the Pareto Front approximation can be decomposed into N scalar optimization subproblems using the Tchebycheff approach, and the objective function of the jth subproblem is defined as
(5)gte(x∣λj,z*)=max⁡1≤i≤m{λij|fi(x)-zi*|},x∈Ω,
where Ω is the decision space and λj=(λ1j,λ2j,…,λmj)T, zi*=min⁡{fi(x)∣x⊂Ω} for each i=1,2,…,m. It is clear that the VNM is able to minimize all N objective functions simultaneously in a single run.The main procedure of the VNM can be described as shown in Figure3.Figure 3
The main procedure of the VNM.In the part of parameter setting, the iteration numberM, the subproblem number N, the size of neighborhood T (which ranges from beginning size B to stopping size S), and the population for saving the optimal solutions EP are set.The crossover operation in VNM is as follows.For each individualxit in generation t, the child xit+1 can be obtained by the following equation:
(6)xit+1={xit+F1×(xit-xi1t)+F2×(xit-xi2t)rand(1)<CRxitrand(1)≥CRCR, F1, and F2 are the three control variables for the crossover; xi1t and xi2t are two individuals chosen in the neighborhood of xit. This crossover method can make full use of the information from the neighborhood and render the information exchange more sufficient.The main idea of VNM is given above. Two improvements are involved in the VNM algorithm. Variable neighborhood strategy is adopted to make the crossover span more reasonable. Moreover, Starting Mutation is used to enhance the diversity of the population.


## 3.2. Variable Neighborhood

In the VNM, the size of the neighborhoodT has a high impact on the performance of the algorithm. If T is too large, the two solutions chosen (xl and xk) for the genetic operation may be unsuitable for the subproblem, and degradation may occur during the progress of the evolution. In contrast, if T is too small, the subproblems are all similar. The child individual will be so similar to its parents that the crossover operation will have a weak effect.T is the neighborhood size which determines the crossover and neighborhood updating span. Too large and too small T will both have a negative influence on VNM. Therefore, T should be large enough at the beginning of the evolution period to ensure sufficient information exchange of the solutions, and T should be sufficiently small in the latter portion of the evolution period such that degradation can be avoided. Motivated by this ideology, we designed and tested three curves to find the best T controlling curve.The three curves are shown in Figure4. In this figure, the abscissa is the number of iterations, and the ordinate is the size of the neighborhood. M1, M2, and M3 represent the straight line, the monotonic parabolic and the nonmonotonic parabolic curves, respectively. It is worth noting that in curve M2, the curvature will be 0 at the end of the evolution period. This means that the rate of change of curvature for M2 is the fastest of all of the concave monotone parabolas during the period of evolution. Because the curvature goes to 0 in the end, curve M2 is determined. Assume that if the number of iterations is 125, the neighborhood of curves M1, M2, and M3 are y1, y2, and y3, respectively, in accordance with the equation: y1-y2=y2-y3. Thus, curve M3 can be also determined. Curve M3 is a nonmonotonic parabolic curve. A series of experiments should be performed to compare the influence of the three curves on the algorithm to identify the best controlling curve.Figure 4
Three controlling curves for the neighborhood size.


## 3.3. Starting Mutation

The TTSP represents a typical combinational optimization problem. The final best solutions may be limited to only several points in the solution space. Because of the neighborhood updating effect of the VNM, there will be many duplicate solutions so that the crossover operation will have little effect. Therefore, how to maintain the diversity of the population is the key question for enhancing the algorithm effect.Motivated by the ideology above, a starting Gauss mutation is adopted at the beginning of the iteration. For a solutionxi=(x1i,x2i,…,xMi)   (M is the number of variables), Gauss mutation is described as the following:
(7)forj=1,2,…,M,xji*={normal(xji,σ)rand(1)<pxjirand(1)≥p.xi*=(x1i*,x2i*,....xMi*) represents the individual after mutation, p is the mutation probability, normal (xji,σ) is a number that obeys the normal distribution, xji is the mean value, and σ is the variance. With Starting Mutation, the problem with the initially invalid crossover operation can be resolved. Therefore, we can avoid the solutions from becoming trapped in local optima, and thus solutions with higher quality are obtained.


## 4. The Convergence Analysis of VNM

The convergence analysis of VNM in this section provides the theory ground for its application. The convergence behavior of VNM is analyzed according to the Markov Chain and the transfer matrix, respectively.


### 4.1. Strong and Weak Convergence

This section proposes the basic theories of convergence and proves the strong and weak convergence of VNM from the perspective of Markov Chain.There is a global optimal solution setM for MOPs (multiobjective problem). M is defined as M={X;∀Y∈S,f(X)≥f(Y)}. It is assumed that X→(n) is the population in evolutionary algorithms.A detailed demonstration for the convergence of MOEA has been proposed in paper [34]. Based on it, the definitions are described as follows.Theorem 1.
α
n, βn, and rn are defined as
(8)αn=P{X→(n+1)∩M=∅/X→(n)∩M≠∅},βn=P{X→(n+1)∩M=∅/X→(n)∩M=∅},rn=β1β2~βn.
If lim⁡n→∞rn=0, X→(n) converges to global optimal solution weakly. It is defined as X→(n)→M(P.W.).Theorem 2.
α
-
n, β-n, and r-n are defined as
(9)α-n=P{X→(n+1)∩Mc≠∅/X→(n)∩Mc=∅},β-n=P{X→(n+1)∩Mc≠∅/X→(n)∩Mc≠∅},r-n=β-1β-2~β-n.
If lim⁡n→∞r-n=0, X→(n) converges to global optimal solution strongly. It is defined as X→(n)→M(P.S.).Based on Theorems1 and 2 above, the demonstration for the convergence of VNM is described in the following. Here, lim⁡n→∞βn=0, lim⁡n→∞⁡β-n=0 describe the evolutionary trend of VNM. There is lim⁡n→∞rn=0, lim⁡n→∞r-n=0.Proof.
It is defined asP(n)=P{X⇀(n)∩M=∅}.
Based on Bayesian, we have(10)P(n+1)=P{X→(n+1)∩M=∅}=P{X→(n+1)∩M=∅/X→(n)∩M≠∅}·P{X→(n)∩M≠∅}+P{X→(n+1)∩M=∅/X→(n)∩M=∅}·P{X→(n)∩M=∅}=αnP{X→(n)∩M≠∅}+βnP{X→(n)∩M=∅}.
Elitist strategy is adopted in VNM, αn=0. Hence
(11)P(n+1)=βnP(n).
Then,
(12)lim⁡n→∞P(n+1)=lim⁡n→∞βnP(n)=lim⁡n→∞rnP(0)=0,lim⁡n→∞P{X→(n)∩M≠∅}=1.
Therefore, we have
(13)X→(n)⟶M(P.W.).
It means that X→(n) converges to global optimal solution weakly.
Similarly, it is defined asP(n)=P{X→(n)∩Mc≠∅}.
By Bayesian formula, we have(14)P(n+1)=P{X→(n+1)∩Mc≠∅}=α-nP{X→(n)∩Mc=∅}+β-nP(n).
Elitist strategy is adopted in VNM, lim⁡n→∞⁡α-n=0. Hence
(15)lim⁡n→∞P(n+1)=lim⁡n→∞β-nP(n)=lim⁡n→∞r-nP(0)=0.
Then,
(16)lim⁡n→∞P{X→(n)∩Mc=∅}=1,lim⁡n→∞P{X→(n)∈M}=1.
Therefore, we have
(17)X→(n)⟶M(P.S.).
It means that X→(n) converges to global optimal solution strongly.


### 4.2. Convergence to Global Optimal

This part focuses on the elitist strategy and proves that the VNM converges to the global optimum from the perspective of transfer matrix.Theorem 3 (see [35]).
P
=
(
C
0
R
T
) is a reducible stochastic matrix, where C:m×m is primitive stochastic matrix and R,T≠0. Then,
(18)P∞=lim⁡k→∞Pk=lim⁡k→∞(Ck0∑i=0k-1TiRCk-iTk)=(C∞0R∞0),
where P∞ is a stable stochastic matrix with P∞=1′p∞. p∞=p0P∞ is unique regardless of the initial distribution. The matrix p∞ satisfies that pi∞>p for 1≤i≤m and pi∞=0 for m<i≤n.According to the previous description of VNM, the extended transition matrices for crossoverC+, mutation M1+, M2+, selection S+ can be written as block diagonal matrix and upgrade matrix U is lower triangular:
(19)C+=(C⋯0⋮⋱⋮0⋯C),M1+=(M1⋯0⋮⋱⋮0⋯M1),S+=(S⋯0⋮⋱⋮0⋯S),M2+=(M2⋯0⋮⋱⋮0⋯M2),U=(U11⋯0⋮⋱⋮U2nl1⋯U2nl2nl).C+, M1+, S+, M2+, and U are with 2nl square matrices. C, M1, M2, S, and Uab  (1≤a, b≤2nl) are all with the size of n×n  (n is the number of individuals and l is the number of individual attributes).a
,
b in Uab represents the population’s state sequence number (in the order of the populations of the pros and cons from 1 to 2nl). So U is used to represent population’s selection process. Each block matrix Uab is a selection of individuals. The details in Uab can be described as: there are some individuals to make uij=1 established in each row. Firstly, the first individual is compared with all other individuals, u1j=1 if jth individual is optimal (there may be several optima) or u11=1 if no one is better than it. Then, the second individual is compared with all other individuals except the first individual. The best individual, gth individual, is chosen; set u2g=1 if gth individual is optimal or u22=1 if there is no one better than the second individual. The sorting process continues until all individuals are sorted. To simplify the difficulty of the problem, assume that the there is only one global optimal solution set. Then, only U11 is a unit matrix, whereas all matrices Uaa with a≥2 are not unit matrices.In VNM, the populations go through Gauss mutationM1+, crossover C+, mutation M2+, selection S+, and EP upgrade matrix U. It is worth of noticing that (μ+λ) selection mode is not used in the evolutionary process of VNM and the number of individuals remains unchanged. This means that S+=I. The transition matrix P+ for VNM is
(20)P+=M1+C+M2+S+U=(M1⋯0⋮⋱⋮0⋯M1)(C⋯0⋮⋱⋮0⋯C)(M2⋯0⋮⋱⋮0⋯M2)×(S⋯0⋮⋱⋮0⋯S)(U11⋯0⋮⋱⋮U2nl1⋯U2nl2nl)=(M1CM2⋯0⋮⋱⋮0⋯M1CM2)(U11⋯0⋮⋱⋮U2nl1⋯U2nl2nl)=(M1CM2U1100⋮⋯0M1CM2U2nl1⋯M1CM2U2nl2nl)=(P11⋯0⋮⋱⋮P2nl1⋯P2nl2nl).
There is P11>0 in the transition matrix P+. The submatrices Pal which is with a≥2 may be gathered in a rectangular matrix R≠0 so that Theorem 3 can be used to prove that the corresponding VNM converges to the global optimum [36].


## 4.1. Strong and Weak Convergence

This section proposes the basic theories of convergence and proves the strong and weak convergence of VNM from the perspective of Markov Chain.There is a global optimal solution setM for MOPs (multiobjective problem). M is defined as M={X;∀Y∈S,f(X)≥f(Y)}. It is assumed that X→(n) is the population in evolutionary algorithms.A detailed demonstration for the convergence of MOEA has been proposed in paper [34]. Based on it, the definitions are described as follows.Theorem 1.
α
n, βn, and rn are defined as
(8)αn=P{X→(n+1)∩M=∅/X→(n)∩M≠∅},βn=P{X→(n+1)∩M=∅/X→(n)∩M=∅},rn=β1β2~βn.
If lim⁡n→∞rn=0, X→(n) converges to global optimal solution weakly. It is defined as X→(n)→M(P.W.).Theorem 2.
α
-
n, β-n, and r-n are defined as
(9)α-n=P{X→(n+1)∩Mc≠∅/X→(n)∩Mc=∅},β-n=P{X→(n+1)∩Mc≠∅/X→(n)∩Mc≠∅},r-n=β-1β-2~β-n.
If lim⁡n→∞r-n=0, X→(n) converges to global optimal solution strongly. It is defined as X→(n)→M(P.S.).Based on Theorems1 and 2 above, the demonstration for the convergence of VNM is described in the following. Here, lim⁡n→∞βn=0, lim⁡n→∞⁡β-n=0 describe the evolutionary trend of VNM. There is lim⁡n→∞rn=0, lim⁡n→∞r-n=0.Proof.
It is defined asP(n)=P{X⇀(n)∩M=∅}.
Based on Bayesian, we have(10)P(n+1)=P{X→(n+1)∩M=∅}=P{X→(n+1)∩M=∅/X→(n)∩M≠∅}·P{X→(n)∩M≠∅}+P{X→(n+1)∩M=∅/X→(n)∩M=∅}·P{X→(n)∩M=∅}=αnP{X→(n)∩M≠∅}+βnP{X→(n)∩M=∅}.
Elitist strategy is adopted in VNM, αn=0. Hence
(11)P(n+1)=βnP(n).
Then,
(12)lim⁡n→∞P(n+1)=lim⁡n→∞βnP(n)=lim⁡n→∞rnP(0)=0,lim⁡n→∞P{X→(n)∩M≠∅}=1.
Therefore, we have
(13)X→(n)⟶M(P.W.).
It means that X→(n) converges to global optimal solution weakly.
Similarly, it is defined asP(n)=P{X→(n)∩Mc≠∅}.
By Bayesian formula, we have(14)P(n+1)=P{X→(n+1)∩Mc≠∅}=α-nP{X→(n)∩Mc=∅}+β-nP(n).
Elitist strategy is adopted in VNM, lim⁡n→∞⁡α-n=0. Hence
(15)lim⁡n→∞P(n+1)=lim⁡n→∞β-nP(n)=lim⁡n→∞r-nP(0)=0.
Then,
(16)lim⁡n→∞P{X→(n)∩Mc=∅}=1,lim⁡n→∞P{X→(n)∈M}=1.
Therefore, we have
(17)X→(n)⟶M(P.S.).
It means that X→(n) converges to global optimal solution strongly.


## 4.2. Convergence to Global Optimal

This part focuses on the elitist strategy and proves that the VNM converges to the global optimum from the perspective of transfer matrix.Theorem 3 (see [35]).
P
=
(
C
0
R
T
) is a reducible stochastic matrix, where C:m×m is primitive stochastic matrix and R,T≠0. Then,
(18)P∞=lim⁡k→∞Pk=lim⁡k→∞(Ck0∑i=0k-1TiRCk-iTk)=(C∞0R∞0),
where P∞ is a stable stochastic matrix with P∞=1′p∞. p∞=p0P∞ is unique regardless of the initial distribution. The matrix p∞ satisfies that pi∞>p for 1≤i≤m and pi∞=0 for m<i≤n.According to the previous description of VNM, the extended transition matrices for crossoverC+, mutation M1+, M2+, selection S+ can be written as block diagonal matrix and upgrade matrix U is lower triangular:
(19)C+=(C⋯0⋮⋱⋮0⋯C),M1+=(M1⋯0⋮⋱⋮0⋯M1),S+=(S⋯0⋮⋱⋮0⋯S),M2+=(M2⋯0⋮⋱⋮0⋯M2),U=(U11⋯0⋮⋱⋮U2nl1⋯U2nl2nl).C+, M1+, S+, M2+, and U are with 2nl square matrices. C, M1, M2, S, and Uab  (1≤a, b≤2nl) are all with the size of n×n  (n is the number of individuals and l is the number of individual attributes).a
,
b in Uab represents the population’s state sequence number (in the order of the populations of the pros and cons from 1 to 2nl). So U is used to represent population’s selection process. Each block matrix Uab is a selection of individuals. The details in Uab can be described as: there are some individuals to make uij=1 established in each row. Firstly, the first individual is compared with all other individuals, u1j=1 if jth individual is optimal (there may be several optima) or u11=1 if no one is better than it. Then, the second individual is compared with all other individuals except the first individual. The best individual, gth individual, is chosen; set u2g=1 if gth individual is optimal or u22=1 if there is no one better than the second individual. The sorting process continues until all individuals are sorted. To simplify the difficulty of the problem, assume that the there is only one global optimal solution set. Then, only U11 is a unit matrix, whereas all matrices Uaa with a≥2 are not unit matrices.In VNM, the populations go through Gauss mutationM1+, crossover C+, mutation M2+, selection S+, and EP upgrade matrix U. It is worth of noticing that (μ+λ) selection mode is not used in the evolutionary process of VNM and the number of individuals remains unchanged. This means that S+=I. The transition matrix P+ for VNM is
(20)P+=M1+C+M2+S+U=(M1⋯0⋮⋱⋮0⋯M1)(C⋯0⋮⋱⋮0⋯C)(M2⋯0⋮⋱⋮0⋯M2)×(S⋯0⋮⋱⋮0⋯S)(U11⋯0⋮⋱⋮U2nl1⋯U2nl2nl)=(M1CM2⋯0⋮⋱⋮0⋯M1CM2)(U11⋯0⋮⋱⋮U2nl1⋯U2nl2nl)=(M1CM2U1100⋮⋯0M1CM2U2nl1⋯M1CM2U2nl2nl)=(P11⋯0⋮⋱⋮P2nl1⋯P2nl2nl).
There is P11>0 in the transition matrix P+. The submatrices Pal which is with a≥2 may be gathered in a rectangular matrix R≠0 so that Theorem 3 can be used to prove that the corresponding VNM converges to the global optimum [36].


## 5. Experimental Results and Analysis

Computational experiments are carried out to compare the approaches and to evaluate the efficiency of the proposed method. There are two objectives: to minimize the makespan and the mean workload of the instruments. In this section, the performance metric, coverage metricC, is introduced first. There are two experimental instances adopted in this section. They are instances of 30 tasks with 12 instruments and 40 tasks with 12 instruments which are real-world examples taken from a missile system. The instance of 40 tasks with 12 instruments is displayed in Table 1. The instance of 30 tasks with 12 instruments is the first 30 tasks in Table 1. The experiment of selection of controlling curve for neighborhood size is shown in Section 5.2. The verification of the improvements of the algorithm is displayed in Section 5.3. In Section 5.3, VNM is compared with MOEA/D. In Section 5.4, the proposed algorithm (VNM) is compared with the variations of CNSGA using real-world TTSP problems. All of the algorithms are executed using 50 independent runs. In all of the experiments, the better performances are denoted in bold. The basic algorithm parameter settings are displayed in Table 2. CR, F1, and F2 are the three control variables for the crossover. p is the mutation probability.Table 1
The instance of 40 tasks with 12 instruments.
Task
Scheme
Resource
Time
t
1
w
1
1
r
1
,
r
7
5
w
1
2
r
3
,
r
5
5
w
1
3
r
6
,
r
10
4
t
2
w
2
1
r
2
,
r
11
5
w
2
2
r
4
,
r
9
4
w
2
3
r
5
,
r
6
6
w
2
4
r
3
,
r
7
4
t
3
w
3
1
r
3
7
w
3
2
r
12
5
t
4
w
4
1
r
9
25
w
4
2
r
10
22
t
5
w
5
1
r
12
14
t
6
w
6
1
r
1
,
r
4
7
w
6
2
r
3
,
r
7
8
w
6
3
r
6
,
r
8
8
t
7
w
7
1
r
1
,
r
2
4
w
7
2
r
3
,
r
8
2
w
7
3
r
7
,
r
11
3
t
8
w
8
1
r
1
,
r
3
5
w
8
2
r
6
,
r
10
4
w
8
3
r
7
,
r
12
7
t
9
w
9
1
r
1
,
r
4
11
w
9
2
r
7
,
r
9
13
w
9
3
r
8
,
r
11
12
t
10
w
10
1
r
2
9
w
10
2
r
4
10
w
10
3
r
10
10
t
11
w
11
1
r
2
,
r
7
6
w
11
2
r
3
,
r
12
9
w
11
3
r
8
,
r
9
8
t
12
w
12
1
r
2
11
w
12
2
r
5
13
w
12
3
r
11
15
t
13
w
13
1
r
2
4
w
13
2
r
8
5
w
13
3
r
9
7
t
14
w
14
1
r
3
7
w
14
2
r
11
10
w
14
3
r
12
8
t
15
w
15
1
r
12
2
t
16
w
16
1
r
2
9
w
16
2
r
5
7
w
16
3
r
8
6
t
17
w
17
1
r
1
,
r
10
10
w
17
2
r
5
,
r
9
12
w
17
3
r
11
,
r
12
11
t
18
w
18
1
r
6
15
t
19
w
19
1
r
2
8
w
19
2
r
5
7
w
19
3
r
10
7
w
19
4
r
12
6
t
20
w
20
1
r
3
6
w
20
2
r
6
4
w
20
3
r
9
5
t
21
w
21
1
r
1
,
r
4
2
w
21
2
r
3
,
r
5
5
w
21
3
r
6
,
r
8
3
t
22
w
22
1
r
2
3
w
22
2
r
4
4
w
22
3
r
6
3
w
22
4
r
10
4
t
23
w
23
1
r
3
5
w
23
2
r
12
5
t
24
w
24
1
r
4
14
w
24
2
r
11
17
t
25
w
25
1
r
7
19
t
26
w
26
1
r
1
,
r
4
7
w
26
2
r
3
,
r
7
8
w
26
3
r
6
,
r
8
10
t
27
w
27
1
r
1
,
r
2
2
w
27
2
r
1
,
r
7
2
w
27
3
r
3
,
r
8
4
t
28
w
28
1
r
1
,
r
3
5
w
28
2
r
4
,
r
5
4
w
28
3
r
7
,
r
12
2
t
29
w
29
1
r
1
,
r
4
11
w
29
2
r
3
,
r
4
15
w
29
3
r
7
,
r
8
12
t
30
w
30
1
r
1
9
w
30
2
r
4
12
w
30
3
r
12
10
t
31
w
31
1
r
2
,
r
3
6
w
31
2
r
5
,
r
11
8
w
31
3
r
6
,
r
9
8
t
32
w
32
1
r
2
11
w
32
2
r
5
13
w
32
3
r
6
17
t
33
w
33
1
r
2
6
w
33
2
r
6
5
w
33
3
r
11
4
t
34
w
34
1
r
3
7
w
34
2
r
7
8
w
34
3
r
12
10
t
35
w
35
1
r
9
2
t
36
w
36
1
r
2
9
w
36
2
r
5
7
w
36
3
r
10
6
t
37
w
37
1
r
1
,
r
2
10
w
37
2
r
7
,
r
11
7
w
37
3
r
5
,
r
12
11
t
38
w
38
1
r
10
15
t
39
w
39
1
r
4
8
w
39
2
r
6
7
w
39
3
r
9
7
w
39
4
r
10
6
t
40
w
40
1
r
3
6
w
40
2
r
6
5
w
40
3
r
9
5Table 2
Parameters setting.
Population
Generation
CR
F
1
F
2
P
100
250
0.5
1
1
0.05


### 5.1. Performance Metric

For multiobjective optimization, the convergence to the Pareto-optimal set is the most important target to be considered. There are mainly two metrics to evaluate the convergence. One is convergence metricγ, and the other is convergence metric C. The true set of Pareto-optimal solutions is necessary for the calculation of γ. However, the solutions space of TTSP is so large that the true set of Pareto-optimal solutions cannot be obtained by enumeration. The metric C can be used to compare the performances of the two solutions sets obtained by different algorithms. The calculation of C needs only the information of the two solutions sets. Therefore, in this paper the convergence metric C is used to evaluate the performance of the proposed algorithm.Assume thatA and B are two sets of nondominated solutions, and C(A,B) is the ratio of the solutions in B that are dominated by at least one solution in A. Hence,
(21)C(A,B)=|{x∈B∣∃y∈A:ydominatesx}||B|,C(A,B)=1 means that all of the solutions in B are dominated by solutions in A, and C(A,B)=0 means that there is no solution in B dominated by a solution in A. Generally speaking, if C(A,B)>C(B,A), then solution set A is better than solution set B.


### 5.2. The Selection of Controlling Curve

In this section, three curves are designed and tested to identify the bestT controlling curve. M1, M2, and M3, respectively, represent the straight line, monotonic parabolic and nonmonotonic parabolic curves shown in Figure 4. In curve M2, the curvature will be 0 at the end of the evolution period. Because of the influence of neighboring updating in MOEA/D, many duplicate solutions will be presented in the final evolution process of MOEA/D. Therefore, Starting Mutation is applied to the beginning of the next iteration to maintain the population diversity. Tables 3 and 4 show the comparison of the influence of the three curves on the algorithm using two instances. The results show that the monotonic parabolic curve M2 has the best performance. This means that the monotonic curve with the fastest rate of change of curvature is the most useful for the algorithm. And the boxplots of three curves for 30*12 and 40*12 instances in Figures 5 and 6 also give the same conclusion.Table 3
Comparison of influence of three curves for30*12 instance.
Average
Times
C
(
M
1
,
M
2
)
0.2213
13
C
(
M
2
,
M
1
)
0.5196
37
C
(
M
2
,
M
3
)
0.4964
36
C
(
M
3
,
M
2
)
0.2069
14Table 4
Comparison of influence of three curves for40*12 instance.
Average
Times
C
(
M
1
,
M
2
)
0.244178
14
C
(
M
2
,
M
1
)
0.501508
36
C
(
M
2
,
M
3
)
0.533806
38
C
(
M
3
,
M
2
)
0.242146
12Figure 5
The boxplot of three curves for30*12 instance.Figure 6
The boxplot of three curves for40*12 instance.


### 5.3. Experiments for Comparisons of VNM and MOEA/D

In order to verify the improvement of VNM,30*12, and 40*12 instances are used to test the performance of VNM and MOEA/D. The monotonic parabolic curve M2 is selected as the controlling curve in VNM. The neighborhood size in MOEA/D is 20. V and M, respectively, represent VNM and MOEA/D. The results in Tables 5 and 6 show that the concave curve with the fastest rate of change of curvature obtained improvement for VNM. The selected curve renders the size of the neighborhood more suitable than before.Table 5
Comparison of VNM and MOEA/D for 30 * 12 instance.
Average
Times
C
(
V
,
M
)
0.4845
35
C
(
M
,
V
)
0.2104
15Table 6
Comparison of VNM and MOEA/D for 40 * 12 instance.
Average
Times
C
(
V
,
M
)
0.5256
40
C
(
M
,
V
)
0.1949
10The results of the two independent experiments for comparison of VNM and MOEA/D are shown in Figures7 and 8 for the 30*12 and 40*12 instances, respectively. As shown in the figures the solutions obtained by the VNM dominate most of the solutions obtained by MOEA/D. Variable neighborhood and Starting Mutation improve the performance of MOEA/D efficiently.The comparison of VNM and MOEA/D for30*12 instance.
(a)
(b)The comparison of VNM and MOEA/D for40*12 instance.
(a)
(b)Figures9 and 10 are the boxplots for comparison of VNM and MOEA/D. It shows that the data distribution of VNM is superior to MOEA/D. VNM has the better performance because of application of variable neighborhood and Starting Mutation.Figure 9
The boxplot of comparison of VNM and MOEA/D for30*12 instance.Figure 10
The boxplot of comparison of VNM and MOEA/D for40*12 instance.


### 5.4. Experiments for Comparisons of VNM and CNSGA

In this section, the VNM is compared with the CNSGA for TTSP. CNSGA is based on NSGA-II. NSGA-II has been successfully applied to job shop scheduling problems [37], reactive power dispatch problems [38], and many other applications. CNSGA has successfully been adopted to solve TTSP [20]. Therefore, a comparison of VNM and CNSGA is carried out to test the performance of the proposed algorithm VNM.There are two chaotic sequences, logistic map and cat map, and the chaotic sequences can be applied in three positions, population initialization, crossover, and mutation. Therefore, there are six combinations for CNSGA. The nomenclatures for six variants of CNSGA are shown in Table7. Tables 8 and 9 show the comparison of VNM and CNSGA for 30*12 and 40*12 instances. The VNM is represented by V. All the comparisons between VNM and the variations of CNSGA are based on 50 independent experiments. The average of C metric and better computational times are used for the performance analysis. The results from Tables 8 and 9 show that VNM provides the best performance not only for the average metric C but also in terms of better computational times than CNSGA.Table 7
Nomenclature for six variants of the CNSGA.
The logistic map
The cat map
Initial population
L
1
C
1
Crossover operator
L
2
C
2
Mutation operator
L
3
C
3Table 8
Comparison of VNM and six variations of CNSGA for 30 * 12 instance.
Average
Times
C
(
V
,
L
1
)
0.4206
36
C
(
L
1
,
V
)
0.2200
14
C
(
V
,
L
2
)
0.4077
34
C
(
L
2
,
V
)
0.2648
16
C
(
V
,
L
3
)
0.4182
36
C
(
L
3
,
V
)
0.2248
14
C
(
V
,
C
1
)
0.4638
35
C
(
C
1
,
V
)
0.2210
15
C
(
V
,
C
2
)
0.4602
34
C
(
C
2
,
V
)
0.2288
16
C
(
V
,
C
3
)
0.4128
35
C
(
C
3
,
V
)
0.2525
15Table 9
Comparison of VNM and six variations of CNSGA for 40 * 12 instance.
Average
Times
C
(
V
,
L
1
)
0.5243
37
C
(
L
1
,
V
)
0.2264
13
C
(
V
,
L
2
)
0.5359
36
C
(
L
2
,
V
)
0.2282
14
C
(
V
,
L
3
)
0.5218
38
C
(
L
3
,
V
)
0.2338
12
C
(
V
,
C
1
)
0.5044
36
C
(
C
1
,
V
)
0.2138
14
C
(
V
,
C
2
)
0.4844
35
C
(
C
2
,
V
)
0.2169
15
C
(
V
,
C
3
)
0.5116
37
C
(
C
3
,
V
)
0.2055
13Figures11 and 12 show the comparisons of VNM and the 6 variations of CNSGA for 30*12 instance. The figures show that the solutions obtained by the VNM dominate most of the solutions obtained by the 6 variations of CNSGA. Therefore, the VNM obtains the best performance.Figure 11
The comparison of VNM and three variations with logistic map for CNSGA for30*12 instance.Figure 12
The comparison of VNM and three variations with cat map for CNSGA for30*12 instance.The results of the comparison of VNM and CNSGA for the40*12 instance are shown in Figures 13 and 14. The results also show that the solutions obtained by VNM have higher quality.Figure 13
The comparison of VNM and three variations with logistic map for CNSGA for40*12 instance.Figure 14
The comparison of VNM and three variations with cat map for CNSGA for40*12 instance.In addition, box plots are used to display the performances of the algorithms. The box plots ofC metric for VNM and CNSGA with 30*12 and 40*12 instances are shown from Figures 15, 16, 17, and 18.Figure 15
The boxplot of VNM and three variations with logistic map for CNSGA for30*12 instance.Figure 16
The boxplot of VNM and three variations with cat map for CNSGA for TTSP30*12 instance.Figure 17
The boxplot of VNM and three variations with logistic map for CNSGA for40*12.Figure 18
The boxplot of VNM and three variations with cat map for CNSGA for40*12.From the box plots ofC metric, it is clear that the median of VNM is larger than that of the variations of CNSGA in both the 30*12 and 40*12 instances, and the data distribution of VNM is more reasonable as well. Additionally, the average of VNM is also superior. The results show that VNM demonstrates better performance than CNSGA in solving the multiobjective TTSP. The performance of solutions obtained by VNM is better than that obtained by CNSGA because that the variable neighborhood is adopted in VNM. The span of information exchange in VNM changes following the evolutionary process, but that in CNSGA stays the same. The information from the process of evolution helps VNM get better performance.The variable neighborhood provides a strategy to improve the performance of the algorithm. For different problems with different scales, the controlling curves for the neighborhood size will be different. The Starting Mutation can be also applied to solve other optimization problem in the evolution process. The strategies proposed in this paper can be investigated in other scheduling problem similar to TTSP.


## 5.1. Performance Metric

For multiobjective optimization, the convergence to the Pareto-optimal set is the most important target to be considered. There are mainly two metrics to evaluate the convergence. One is convergence metricγ, and the other is convergence metric C. The true set of Pareto-optimal solutions is necessary for the calculation of γ. However, the solutions space of TTSP is so large that the true set of Pareto-optimal solutions cannot be obtained by enumeration. The metric C can be used to compare the performances of the two solutions sets obtained by different algorithms. The calculation of C needs only the information of the two solutions sets. Therefore, in this paper the convergence metric C is used to evaluate the performance of the proposed algorithm.Assume thatA and B are two sets of nondominated solutions, and C(A,B) is the ratio of the solutions in B that are dominated by at least one solution in A. Hence,
(21)C(A,B)=|{x∈B∣∃y∈A:ydominatesx}||B|,C(A,B)=1 means that all of the solutions in B are dominated by solutions in A, and C(A,B)=0 means that there is no solution in B dominated by a solution in A. Generally speaking, if C(A,B)>C(B,A), then solution set A is better than solution set B.


## 5.2. The Selection of Controlling Curve

In this section, three curves are designed and tested to identify the bestT controlling curve. M1, M2, and M3, respectively, represent the straight line, monotonic parabolic and nonmonotonic parabolic curves shown in Figure 4. In curve M2, the curvature will be 0 at the end of the evolution period. Because of the influence of neighboring updating in MOEA/D, many duplicate solutions will be presented in the final evolution process of MOEA/D. Therefore, Starting Mutation is applied to the beginning of the next iteration to maintain the population diversity. Tables 3 and 4 show the comparison of the influence of the three curves on the algorithm using two instances. The results show that the monotonic parabolic curve M2 has the best performance. This means that the monotonic curve with the fastest rate of change of curvature is the most useful for the algorithm. And the boxplots of three curves for 30*12 and 40*12 instances in Figures 5 and 6 also give the same conclusion.Table 3
Comparison of influence of three curves for30*12 instance.
Average
Times
C
(
M
1
,
M
2
)
0.2213
13
C
(
M
2
,
M
1
)
0.5196
37
C
(
M
2
,
M
3
)
0.4964
36
C
(
M
3
,
M
2
)
0.2069
14Table 4
Comparison of influence of three curves for40*12 instance.
Average
Times
C
(
M
1
,
M
2
)
0.244178
14
C
(
M
2
,
M
1
)
0.501508
36
C
(
M
2
,
M
3
)
0.533806
38
C
(
M
3
,
M
2
)
0.242146
12Figure 5
The boxplot of three curves for30*12 instance.Figure 6
The boxplot of three curves for40*12 instance.


## 5.3. Experiments for Comparisons of VNM and MOEA/D

In order to verify the improvement of VNM,30*12, and 40*12 instances are used to test the performance of VNM and MOEA/D. The monotonic parabolic curve M2 is selected as the controlling curve in VNM. The neighborhood size in MOEA/D is 20. V and M, respectively, represent VNM and MOEA/D. The results in Tables 5 and 6 show that the concave curve with the fastest rate of change of curvature obtained improvement for VNM. The selected curve renders the size of the neighborhood more suitable than before.Table 5
Comparison of VNM and MOEA/D for 30 * 12 instance.
Average
Times
C
(
V
,
M
)
0.4845
35
C
(
M
,
V
)
0.2104
15Table 6
Comparison of VNM and MOEA/D for 40 * 12 instance.
Average
Times
C
(
V
,
M
)
0.5256
40
C
(
M
,
V
)
0.1949
10The results of the two independent experiments for comparison of VNM and MOEA/D are shown in Figures7 and 8 for the 30*12 and 40*12 instances, respectively. As shown in the figures the solutions obtained by the VNM dominate most of the solutions obtained by MOEA/D. Variable neighborhood and Starting Mutation improve the performance of MOEA/D efficiently.The comparison of VNM and MOEA/D for30*12 instance.
(a)
(b)The comparison of VNM and MOEA/D for40*12 instance.
(a)
(b)Figures9 and 10 are the boxplots for comparison of VNM and MOEA/D. It shows that the data distribution of VNM is superior to MOEA/D. VNM has the better performance because of application of variable neighborhood and Starting Mutation.Figure 9
The boxplot of comparison of VNM and MOEA/D for30*12 instance.Figure 10
The boxplot of comparison of VNM and MOEA/D for40*12 instance.


## 5.4. Experiments for Comparisons of VNM and CNSGA

In this section, the VNM is compared with the CNSGA for TTSP. CNSGA is based on NSGA-II. NSGA-II has been successfully applied to job shop scheduling problems [37], reactive power dispatch problems [38], and many other applications. CNSGA has successfully been adopted to solve TTSP [20]. Therefore, a comparison of VNM and CNSGA is carried out to test the performance of the proposed algorithm VNM.There are two chaotic sequences, logistic map and cat map, and the chaotic sequences can be applied in three positions, population initialization, crossover, and mutation. Therefore, there are six combinations for CNSGA. The nomenclatures for six variants of CNSGA are shown in Table7. Tables 8 and 9 show the comparison of VNM and CNSGA for 30*12 and 40*12 instances. The VNM is represented by V. All the comparisons between VNM and the variations of CNSGA are based on 50 independent experiments. The average of C metric and better computational times are used for the performance analysis. The results from Tables 8 and 9 show that VNM provides the best performance not only for the average metric C but also in terms of better computational times than CNSGA.Table 7
Nomenclature for six variants of the CNSGA.
The logistic map
The cat map
Initial population
L
1
C
1
Crossover operator
L
2
C
2
Mutation operator
L
3
C
3Table 8
Comparison of VNM and six variations of CNSGA for 30 * 12 instance.
Average
Times
C
(
V
,
L
1
)
0.4206
36
C
(
L
1
,
V
)
0.2200
14
C
(
V
,
L
2
)
0.4077
34
C
(
L
2
,
V
)
0.2648
16
C
(
V
,
L
3
)
0.4182
36
C
(
L
3
,
V
)
0.2248
14
C
(
V
,
C
1
)
0.4638
35
C
(
C
1
,
V
)
0.2210
15
C
(
V
,
C
2
)
0.4602
34
C
(
C
2
,
V
)
0.2288
16
C
(
V
,
C
3
)
0.4128
35
C
(
C
3
,
V
)
0.2525
15Table 9
Comparison of VNM and six variations of CNSGA for 40 * 12 instance.
Average
Times
C
(
V
,
L
1
)
0.5243
37
C
(
L
1
,
V
)
0.2264
13
C
(
V
,
L
2
)
0.5359
36
C
(
L
2
,
V
)
0.2282
14
C
(
V
,
L
3
)
0.5218
38
C
(
L
3
,
V
)
0.2338
12
C
(
V
,
C
1
)
0.5044
36
C
(
C
1
,
V
)
0.2138
14
C
(
V
,
C
2
)
0.4844
35
C
(
C
2
,
V
)
0.2169
15
C
(
V
,
C
3
)
0.5116
37
C
(
C
3
,
V
)
0.2055
13Figures11 and 12 show the comparisons of VNM and the 6 variations of CNSGA for 30*12 instance. The figures show that the solutions obtained by the VNM dominate most of the solutions obtained by the 6 variations of CNSGA. Therefore, the VNM obtains the best performance.Figure 11
The comparison of VNM and three variations with logistic map for CNSGA for30*12 instance.Figure 12
The comparison of VNM and three variations with cat map for CNSGA for30*12 instance.The results of the comparison of VNM and CNSGA for the40*12 instance are shown in Figures 13 and 14. The results also show that the solutions obtained by VNM have higher quality.Figure 13
The comparison of VNM and three variations with logistic map for CNSGA for40*12 instance.Figure 14
The comparison of VNM and three variations with cat map for CNSGA for40*12 instance.In addition, box plots are used to display the performances of the algorithms. The box plots ofC metric for VNM and CNSGA with 30*12 and 40*12 instances are shown from Figures 15, 16, 17, and 18.Figure 15
The boxplot of VNM and three variations with logistic map for CNSGA for30*12 instance.Figure 16
The boxplot of VNM and three variations with cat map for CNSGA for TTSP30*12 instance.Figure 17
The boxplot of VNM and three variations with logistic map for CNSGA for40*12.Figure 18
The boxplot of VNM and three variations with cat map for CNSGA for40*12.From the box plots ofC metric, it is clear that the median of VNM is larger than that of the variations of CNSGA in both the 30*12 and 40*12 instances, and the data distribution of VNM is more reasonable as well. Additionally, the average of VNM is also superior. The results show that VNM demonstrates better performance than CNSGA in solving the multiobjective TTSP. The performance of solutions obtained by VNM is better than that obtained by CNSGA because that the variable neighborhood is adopted in VNM. The span of information exchange in VNM changes following the evolutionary process, but that in CNSGA stays the same. The information from the process of evolution helps VNM get better performance.The variable neighborhood provides a strategy to improve the performance of the algorithm. For different problems with different scales, the controlling curves for the neighborhood size will be different. The Starting Mutation can be also applied to solve other optimization problem in the evolution process. The strategies proposed in this paper can be investigated in other scheduling problem similar to TTSP.


## 6. Conclusion

How to improve the test efficiency is more and more important in modern industry. TTSP has important application value in modern manufacturing process. TTSP is combinational optimization problem. The final best solutions only account for a rather small subset of the search space. In order to help the solutions avoid being trapped in local optima, this paper proposed a new genetic evolutionary multiobjective optimization algorithm (VNM) to solve the TTSP. The variable neighborhood and Starting Mutation strategies are adopted in VNM to make the crossover span more suitable and improve the diversity of population. Three controlling curves for neighborhood size are studied. The experimental results have shown that the monotonic parabolic has the best performance. From the experiment conducted for comparison of VNM and MOEA/D, we see that the improved algorithm has made great progress in solving the TTSP problem. And the experiment conducted for comparison of VNM and CNSGA also shows that the improved algorithm is superior to CNSGA in solving TTSP. VNM can also be applied to solve other combinational optimization problems such as FJSP and TSP. Future work will focus on two objectives: the precedence constraint will be added to the TTSP, and information regarding bottleneck tasks will be considered.



---

*Source: 423621-2014-04-01.xml*