# A Tabu Search-Based Memetic Algorithm for Hardware/Software Partitioning

Authors: Geng Lin; Wenxing Zhu; M. Montaz Ali
Journal: Mathematical Problems in Engineering
 (2014)

---

## Abstract

Hardware/software (HW/SW) partitioning is to determine which components
of a system are implemented on hardware and which ones on software. It is one of the most
important steps in the design of embedded systems. The HW/SW partitioning problem is an
NP-hard constrained binary optimization problem. In this paper, we propose a tabu search-based
memetic algorithm to solve the HW/SW partitioning problem. First, we convert the
constrained binary HW/SW problem into an unconstrained binary problem using an adaptive
penalty function that has no parameters in it. A memetic algorithm is then suggested
for solving this unconstrained problem. The algorithm uses a tabu search as its local search
procedure. This tabu search has a special feature with respect to solution generation, and
it uses a feedback mechanism for updating the tabu tenure. In addition, the algorithm integrates
a path relinking procedure for exploitation of newly found solutions. Computational
results are presented using a number of test instances from the literature. The algorithm
proves its robustness when its results are compared with those of two other algorithms. The
effectiveness of the proposed parameter-free adaptive penalty function is also shown.


---

## Body

## 1. Introduction

The embedded systems have become omnipresent in a wide variety of applications and typically consist of application specific hardware components and programmable components. With the growing complexity of embedded systems, hardware/software codesign has become an effective way of improving design quality, in which the HW/SW partitioning is the most critical step.HW/SW partitioning decides which tasks of an embedded system should be implemented in hardware and which ones should be in software. A task implemented with a hardware module is faster but more expensive, while a task implemented with a software module is slower but cheaper. For this reason, the main target of HW/SW partitioning is to balance all the tasks to optimize some objectives of the system under some constraints [1].In recent years, there has been an increasing interest in the study of the HW/SW partitioning problem. Several exact approaches [2–5] to the problem have been developed. However, since most of the exact formulations of the HW/SW partitioning problem are NP-hard [6], the practical usefulness of these approaches is limited to fairly small problem instances only. For larger instances, a number of heuristic algorithms, both traditional and general purpose, have been proposed.There are two traditional families of heuristics: the software-oriented heuristic and the hardware-oriented heuristic. The software-oriented heuristic starts with a complete software solution and parts of the system are migrated to hardware until all constraints are satisfied. On the other hand, the hardware-oriented heuristic starts with a complete hardware solution and moves parts of the system to software until a constraint is violated.Up to now, many general-purpose heuristics or metaheuristics have also been applied to solve the HW/SW partitioning problem. These include simulated annealing [7–9], genetic algorithm [10–12], tabu search [8, 13–15], artificial immune [16], and the Kernighan-Lin heuristic [17, 18]. There are also some other methods for solving the problem; see [19] for details.It must be mentioned that the HW/SW partitioning problem is to minimize a cost while satisfying some design constraints. In fact, the problem is a discrete constrained optimization problem, and the optimal solutions usually lie on the boundary of the feasible region. Hence, it is necessary to develop effective techniques in handling the constraints.This paper presents a tabu search-based memetic algorithm (TSMA) for solving the HW/SW partitioning problem. The TSMA uses an adaptive penalty function to convert the original problem into an equivalent unconstrained integer programming problem; both problems have the same discrete global minimizers. The TSMA is then applied to unconstrained integer programming problem in order to solve the original problem. The TSMA integrates a tabu search procedure, a path relinking procedure, and a population updating strategy. These strategies achieve a balance between intensification and diversification of the search process. The algorithm has been tested on four benchmark test instances in the literature. Experimental results and comparisons show that the proposed algorithm is effective and robust.The remaining part of this paper is organized as follows. Section2 gives the system model and problem formulation. Section 3 presents the parameter-free adaptive penalty function used in converting the original problem into the unconstrained problem. Section 3 also presents some theoretical properties of the resulting unconstrained problem. In Section 4, a full description of TSMA is presented. Experimental results on four benchmark test instances are presented in Section 5. Final remarks are given in Section 6.


## 2. Hardware/Software Partitioning Model and Formulation

The HW/SW partitioning model discussed in this paper is similar to that presented in [16]. In order to make the paper self-contained, this section briefly reviews the description of the HW/SW partitioning model considered in [16].


### 2.1. Function Description

The main function of the system is usually described by a high-level programming language, and then the function will be mapped into a control-data flow graph (CDFG). The CDFG is composed of nodes and arcs [20, 21]. Generally, the CDFG is a directed acyclic graph (DAG). In the DAG, the nodes are determined by the model granularity, that is, the semantic of a node. A node can represent a short sequence of instructions, a basic block, a function, or a procedure [12]. The arcs between nodes denote their relationship. Each node in DAG can receive data from its previous nodes and can send data to its next nodes.


### 2.2. Binary Integer Programming Formulation

In a directed acyclic graph (DAG)G=(V,E) with node set V={1,2,…,n} and arc set E, every node is labeled with several attributes. The attributes for a node i are defined as follows.(i)
asi denotes the cost of i in software implementation.(ii)
tsi denotes the executing time of i in software implementation.(iii)
ahi denotes the cost of i in hardware implementation.(iv)
thi denotes the executing time of i in hardware implementation.(v)
ri is an array, which denotes the set of incoming nodes of i and stores the set of corresponding communication times.(vi)
wi is an array, which denotes the set of outgoing nodes of i and stores the set of corresponding communication times.(vii)
pci denotes the number of times that node i is executed.Figure1 [16] shows the partition model used in this paper, where “HA1”,“HA2”,…,and“HAm” denote the m hardware nodes implemented by application specific integrated circuit (ASIC) or field programmable gate array (FPGA). The software nodes are executed in a programmable processor (CPU). All the nodes exchange data through a shared bus, and they share the common memory to store the interim data. All the hardware nodes without dependency can be executed concurrently [16].Figure 1
The partition model discussed in this paper [16].After all nodes are determined to be implemented by hardware or software, all the nodes are scheduled. The total executing timeT can be evaluated by the list schedule algorithm [11, 22], and the cost of the design can be evaluated. The detailed steps of the list schedule algorithm are shown in Algorithm 1.Algorithm 1:List schedule algorithm [16, 22].
(1) Initialization. Set two attributes for every node,start and finish, which are used for recording the node’s
starting time and finishing time. Choose all nodes without data dependency from the node set and put them
into a ready queue. Choose one software node from the queue to be executed by CPU, and all hardware nodes
to be executed at the same time. Set 0 as the values of thestart attributes for the running nodes. Set the sum
of the executing time and the communication time as the values of thefinish attributes. If there is a software
node being executed byCPU, set CPU = BUSY.
(2)repeat
(3) Select the node with the minimal finish time from the ready queue, mark it as i.
(4) Remove node i from the queue. If i is a software node, set CPU=FREE.
(5) If CPU=FREE, choose one software node j from the queue to execute and set CPU=BUSY.
Setstart[j]=finish[i], finish[j]=start[j]+tsj+comm[j], where comm[j] denotes the communication
time of nodej with other nodes.
(6) Choose all hardware nodes to execute concurrently. Set theirstart and finish attributes as in Line (5).
(7)until The ready queue is empty
(8)return Choose the maximal finish time of all the nodes as the system executing time, denoted as T.In this paper, the objective is to minimize the total cost of the system under the time constraint. Since the cost of software is usually negligible, the HW/SW partitioning problem can be described as follows [11]:
(P)min⁡∑i∈H‍ahis.t.ikT≤TimeReq,
where i∈H means that node i is implemented by hardware, T denotes the total executing time, and TimeReq denotes the required time which is given in advance by the designer.Letx=(x1,…,xn)T∈{0,1}n denote a solution of the problem (P). xi=1(xi=0) indicates that node i is implemented by hardware (software). Then problem (P) can be formulated as the following constrained binary programming problem:
(IP)min⁡f(x)=∑i=1n‍xiahis.t.iiit(x)≤TimeReqiikxi∈{0,1},i=1,…,n,
where t(x) denotes the total executing time of x which can be evaluated by the list schedule algorithm, that is, Algorithm 1. We suppose without loss of generality that asi, tsi, ahi, thi, ri, wi, pci, and TimeReq are nonnegative integers.


## 2.1. Function Description

The main function of the system is usually described by a high-level programming language, and then the function will be mapped into a control-data flow graph (CDFG). The CDFG is composed of nodes and arcs [20, 21]. Generally, the CDFG is a directed acyclic graph (DAG). In the DAG, the nodes are determined by the model granularity, that is, the semantic of a node. A node can represent a short sequence of instructions, a basic block, a function, or a procedure [12]. The arcs between nodes denote their relationship. Each node in DAG can receive data from its previous nodes and can send data to its next nodes.


## 2.2. Binary Integer Programming Formulation

In a directed acyclic graph (DAG)G=(V,E) with node set V={1,2,…,n} and arc set E, every node is labeled with several attributes. The attributes for a node i are defined as follows.(i)
asi denotes the cost of i in software implementation.(ii)
tsi denotes the executing time of i in software implementation.(iii)
ahi denotes the cost of i in hardware implementation.(iv)
thi denotes the executing time of i in hardware implementation.(v)
ri is an array, which denotes the set of incoming nodes of i and stores the set of corresponding communication times.(vi)
wi is an array, which denotes the set of outgoing nodes of i and stores the set of corresponding communication times.(vii)
pci denotes the number of times that node i is executed.Figure1 [16] shows the partition model used in this paper, where “HA1”,“HA2”,…,and“HAm” denote the m hardware nodes implemented by application specific integrated circuit (ASIC) or field programmable gate array (FPGA). The software nodes are executed in a programmable processor (CPU). All the nodes exchange data through a shared bus, and they share the common memory to store the interim data. All the hardware nodes without dependency can be executed concurrently [16].Figure 1
The partition model discussed in this paper [16].After all nodes are determined to be implemented by hardware or software, all the nodes are scheduled. The total executing timeT can be evaluated by the list schedule algorithm [11, 22], and the cost of the design can be evaluated. The detailed steps of the list schedule algorithm are shown in Algorithm 1.Algorithm 1:List schedule algorithm [16, 22].
(1) Initialization. Set two attributes for every node,start and finish, which are used for recording the node’s
starting time and finishing time. Choose all nodes without data dependency from the node set and put them
into a ready queue. Choose one software node from the queue to be executed by CPU, and all hardware nodes
to be executed at the same time. Set 0 as the values of thestart attributes for the running nodes. Set the sum
of the executing time and the communication time as the values of thefinish attributes. If there is a software
node being executed byCPU, set CPU = BUSY.
(2)repeat
(3) Select the node with the minimal finish time from the ready queue, mark it as i.
(4) Remove node i from the queue. If i is a software node, set CPU=FREE.
(5) If CPU=FREE, choose one software node j from the queue to execute and set CPU=BUSY.
Setstart[j]=finish[i], finish[j]=start[j]+tsj+comm[j], where comm[j] denotes the communication
time of nodej with other nodes.
(6) Choose all hardware nodes to execute concurrently. Set theirstart and finish attributes as in Line (5).
(7)until The ready queue is empty
(8)return Choose the maximal finish time of all the nodes as the system executing time, denoted as T.In this paper, the objective is to minimize the total cost of the system under the time constraint. Since the cost of software is usually negligible, the HW/SW partitioning problem can be described as follows [11]:
(P)min⁡∑i∈H‍ahis.t.ikT≤TimeReq,
where i∈H means that node i is implemented by hardware, T denotes the total executing time, and TimeReq denotes the required time which is given in advance by the designer.Letx=(x1,…,xn)T∈{0,1}n denote a solution of the problem (P). xi=1(xi=0) indicates that node i is implemented by hardware (software). Then problem (P) can be formulated as the following constrained binary programming problem:
(IP)min⁡f(x)=∑i=1n‍xiahis.t.iiit(x)≤TimeReqiikxi∈{0,1},i=1,…,n,
where t(x) denotes the total executing time of x which can be evaluated by the list schedule algorithm, that is, Algorithm 1. We suppose without loss of generality that asi, tsi, ahi, thi, ri, wi, pci, and TimeReq are nonnegative integers.


## 3. The Adaptive Penalty Function

In this section, we introduce the basic form of the penalty function for constrained optimization problem and present an adaptive penalty function to convert the problem(IP) into an unconstrained binary optimization problem.


### 3.1. The Basic Penalty Function

A variety of penalty functions have been proposed to deal with constraints. Of them, the exact penalty function and the quadratic penalty function are most basic and widely used [23–25]. Using these penalty functions problem (IP) can be converted into the following unconstrained problem:
(1)χ(x,R,q)=f(x)+R×ψ(x),
where ψ(x)=max⁡{0,t(x)-TimeReq}q, R is the penalty parameter, and q≥1. For q=1 (resp., q=2), the optimization method that uses (1) is known as the exact (the quadratic) penalty function method.LetS={0,1}n, and denote by S¯ the feasible solution space of (IP); that is, S¯={x∣x∈S,andt(x)≤TimeReq}. We construct the following auxiliary problem:
(UIP1)min⁡χ(x,R,q)=f(x)+R×ψ(x),s.t.kix∈S,
where (x)=max⁡{0,t(x)-TimeReq}q, R>0 is the penalty parameter, and q≥1.


### 3.2. The Proposed Adaptive Penalty Function

It is a well-known fact that the penalty parameterR in (1) is sensitive and problem-dependent. Hence, it is difficult to choose a value for R [26] that can be used for a wide range of optimization problems. Therefore, a number of authors [27–31] have suggested parameter-free penalty functions to do away with the sensitive parameter R. Following the same reasonings, we propose the following param0065ter-free adaptive penalty function:
(2)L(x)={f(x)ifφ(x)=0;φ(x)+Uifφ(x)>0,f(x)≤U;φ(x)+f(x)ifφ(x)>0,f(x)>U,
where
(3)φ(x)=max⁡{0,t(x)-TimeReq}
and U is an upper bound on the global minimum value of problem (IP). Since the cost of the system is smaller than ∑i=1nahi, we can initialize U=∑i=1nahi. The value of U needs to be updated by the current best known objective function value at a feasible solution.Based on this adaptive penalty function, we construct the following problem:(UIP2)min⁡L(x),s.t.x∈S.Definition 1.
A solutiony∈S¯ is called a discrete local minimizer of problem (IP), if f(y)≤f(x), for all x∈N(y)∩S¯, where N(y) is a neighborhood of y. Furthermore, if f(y)≤f(x), for all x∈S¯, then y is called a discrete global minimizer of problem (IP).Theorem 2.
LetU be an upper bound on the discrete global minimum value of problem (IP); then problems (IP) and (UIP2) have the same discrete global minimizers and global minimal values.Proof.
Letx* be a discrete global minimizer of problem (IP); then φ(x*)=0, and f(x)≤f(x*), for  all x∈S¯. Consider two sets S¯ and S∖S¯.
For allx∈S¯, by (3), we have φ(x)=0, then
(4)L(x)=f(x)≥f(x*)=L(x*).
For allx∈S∖S¯, we have two cases: (i) φ(x)>0 and f(x)≤U, and (ii) φ(x)>0 and f(x)>U.
Case (i). By (2), we have
(5)L(x)=φ(x)+U≥φ(x)+f(x*)>f(x*)=L(x*).
Case (ii). By (2), we have L(x)=φ(x)+f(x). Since f(x)>U>f(x*)=L(x*), it holds
(6)L(x)=φ(x)+f(x)>U>L(x*).
From (4), (5), and (6), it is obvious that x* is a discrete global minimizer of problem (UIP2).
Conversely, letx* be a discrete global minimizer of problem (UIP2), then
(7)L(x)≥L(x*),∀x∈S.
Suppose that x*∉S¯; that is, φ(x*)>0. If f(x*)≤U, then
(8)L(x*)=φ(x*)+U>U≥f(y),
where y is a discrete global minimizer of problem (IP); that is, φ(y)=0. If f(x*)>U, then
(9)L(x*)=φ(x*)+f(x*)>U≥f(y).
Hence,
(10)L(x*)>f(y).
SinceL(y)=f(y), inequality (10) implies that L(x*)>L(y) which means that x* is not a discrete global minimizer of problem (UIP2). So x*∈S¯, and problems (IP) and (UIP2) have the same discrete global minimizers and global minimal values.Theorem 3.
Suppose thaty is a solution of problem (UIP2), and L(y)<U. Then y is a feasible solution of problem (IP).Proof.
Ify is an infeasible solution of problem (IP), then φ(y)>0. By (2), if f(y)≤U, we have L(y)=φ(x)+U>U. If f(y)>U, then L(y)=φ(y)+f(y)>U. So, it holds that L(y)>U, which contradicts the condition L(y)<U. Hence, the theorem holds.


## 3.1. The Basic Penalty Function

A variety of penalty functions have been proposed to deal with constraints. Of them, the exact penalty function and the quadratic penalty function are most basic and widely used [23–25]. Using these penalty functions problem (IP) can be converted into the following unconstrained problem:
(1)χ(x,R,q)=f(x)+R×ψ(x),
where ψ(x)=max⁡{0,t(x)-TimeReq}q, R is the penalty parameter, and q≥1. For q=1 (resp., q=2), the optimization method that uses (1) is known as the exact (the quadratic) penalty function method.LetS={0,1}n, and denote by S¯ the feasible solution space of (IP); that is, S¯={x∣x∈S,andt(x)≤TimeReq}. We construct the following auxiliary problem:
(UIP1)min⁡χ(x,R,q)=f(x)+R×ψ(x),s.t.kix∈S,
where (x)=max⁡{0,t(x)-TimeReq}q, R>0 is the penalty parameter, and q≥1.


## 3.2. The Proposed Adaptive Penalty Function

It is a well-known fact that the penalty parameterR in (1) is sensitive and problem-dependent. Hence, it is difficult to choose a value for R [26] that can be used for a wide range of optimization problems. Therefore, a number of authors [27–31] have suggested parameter-free penalty functions to do away with the sensitive parameter R. Following the same reasonings, we propose the following param0065ter-free adaptive penalty function:
(2)L(x)={f(x)ifφ(x)=0;φ(x)+Uifφ(x)>0,f(x)≤U;φ(x)+f(x)ifφ(x)>0,f(x)>U,
where
(3)φ(x)=max⁡{0,t(x)-TimeReq}
and U is an upper bound on the global minimum value of problem (IP). Since the cost of the system is smaller than ∑i=1nahi, we can initialize U=∑i=1nahi. The value of U needs to be updated by the current best known objective function value at a feasible solution.Based on this adaptive penalty function, we construct the following problem:(UIP2)min⁡L(x),s.t.x∈S.Definition 1.
A solutiony∈S¯ is called a discrete local minimizer of problem (IP), if f(y)≤f(x), for all x∈N(y)∩S¯, where N(y) is a neighborhood of y. Furthermore, if f(y)≤f(x), for all x∈S¯, then y is called a discrete global minimizer of problem (IP).Theorem 2.
LetU be an upper bound on the discrete global minimum value of problem (IP); then problems (IP) and (UIP2) have the same discrete global minimizers and global minimal values.Proof.
Letx* be a discrete global minimizer of problem (IP); then φ(x*)=0, and f(x)≤f(x*), for  all x∈S¯. Consider two sets S¯ and S∖S¯.
For allx∈S¯, by (3), we have φ(x)=0, then
(4)L(x)=f(x)≥f(x*)=L(x*).
For allx∈S∖S¯, we have two cases: (i) φ(x)>0 and f(x)≤U, and (ii) φ(x)>0 and f(x)>U.
Case (i). By (2), we have
(5)L(x)=φ(x)+U≥φ(x)+f(x*)>f(x*)=L(x*).
Case (ii). By (2), we have L(x)=φ(x)+f(x). Since f(x)>U>f(x*)=L(x*), it holds
(6)L(x)=φ(x)+f(x)>U>L(x*).
From (4), (5), and (6), it is obvious that x* is a discrete global minimizer of problem (UIP2).
Conversely, letx* be a discrete global minimizer of problem (UIP2), then
(7)L(x)≥L(x*),∀x∈S.
Suppose that x*∉S¯; that is, φ(x*)>0. If f(x*)≤U, then
(8)L(x*)=φ(x*)+U>U≥f(y),
where y is a discrete global minimizer of problem (IP); that is, φ(y)=0. If f(x*)>U, then
(9)L(x*)=φ(x*)+f(x*)>U≥f(y).
Hence,
(10)L(x*)>f(y).
SinceL(y)=f(y), inequality (10) implies that L(x*)>L(y) which means that x* is not a discrete global minimizer of problem (UIP2). So x*∈S¯, and problems (IP) and (UIP2) have the same discrete global minimizers and global minimal values.Theorem 3.
Suppose thaty is a solution of problem (UIP2), and L(y)<U. Then y is a feasible solution of problem (IP).Proof.
Ify is an infeasible solution of problem (IP), then φ(y)>0. By (2), if f(y)≤U, we have L(y)=φ(x)+U>U. If f(y)>U, then L(y)=φ(y)+f(y)>U. So, it holds that L(y)>U, which contradicts the condition L(y)<U. Hence, the theorem holds.


## 4. The Proposed Memetic Algorithm for HW/SW Partitioning

Memetic algorithms (MAs) are a kind of global search technique derived from Darwinian principles of natural evolution and Dawkins’ notion of memes [32]. They are genetic algorithms that use local search procedures to intensify the search [33]. MAs have been applied to solve a variety of optimization problems [34–40].In this section, a tabu search-based memetic algorithm, TSMA, is presented to solve the parameter-free unconstrained problem(UIP2). First, a general framework of TSMA is presented, followed by detailed descriptions of various components of the algorithm.


### 4.1. General Framework of the Hybrid Memetic Algorithm

The steps of the general framework of TSMA for solving(UIP2) is shown in Algorithm 2. Throughout its execution, the TSMA updates the upper bound U with the function value at the current best solution x*.Algorithm 2:General structure of TSMA.
Require: A directed acyclic graph;
Ensure: Approximate global maximal solution x*;
(1)    InitialU=∑i=1n‍ahi, x*=(1,…,1).
(2)    Generate randomly a populationP={x1,…,xp}.
(3)for  k={1,…,p}  do
(4)    Use the local search procedure (see Section4.3) to minimize problem (UIP2) from
every individualxk, also denote the obtained solution by xk.
(5)if  L(xk)<U  then
(6)      LetU=L(xk), and x*=xk.
(7)end if
(8)end for
(9)while termination criteria (see Section 4.6) do not meet do
(10)   Use the crossover operator (see Section4.2) to generate a new offspring x0, and
apply the local search procedure to refine x0, also denote it by x0.
(11)if  L(x0)<U  then
(12)    LetU=L(x0), and x*=x0.
(13)end if
(14)if  x0=x*  then
(15)y=x0.
(16)else
(17)  Use the path relinking procedure PR (see Section 4.4) to the solution
x0 and the current best solution x* to obtain a solution y.
(18)end if
(19)if  L(y)<U  then
(20)    LetU=L(y), and x*=y.
(21)end if
(22)  Use the population updating method (see Section4.5) to update the population that is
to decide if y∈P.
(23)end while
(24)return  x* and f(x*) as an approximate discrete global minimizer and global minimal
value of problem (IP), respectively.Before the TSMA begins, its iterative process performs three main steps; see Algorithm2. In step 1, it initializes the first upper bound U of (UIP2) with the known trivial solution where xi=1, i=1,2,…,n. In step 2, it generates the initial random population set of size p; that is, P={x1,…,xp}, xk∈S, k=1,2,…,p. In step 4, the TSMA refines each member of the initial population P by the local search, the tabu search, and treats P as the starting population set.As the iteration process begins, the TSMA repeatedly performs three main steps: crossover followed by tabu search, path relinking, and the updating ofP. In step 10, a new solution x0 is identified using the crossover operation followed by tabu search. In step 17, the path relinking procedure may be applied to x0 in an attempt to generate an improved solution y from x0. Finally, in step 22, the population updating process is performed to decide whether y∈P and which solution should be replaced, provided that such an improved y has been generated. The remaining steps of Algorithm 2 are used to update U and x*. This iterative process repeats itself until some stopping conditions are met.The main iterative components of TSMA, the crossover followed by the tabu search procedure, the path relinking procedure, and the population updating strategy are explained in the subsequent subsections.


### 4.2. Crossover Operator

We adopt the fixed crossover operator [41] to generate a new offspring. First, a pair of individuals are selected randomly from the population. Next, if two selected individuals have the same bit value, their offspring inherits it. Otherwise, it takes value 0 or 1 randomly. Suppose that x and y are two selected individuals from the population. The pseudocode of the crossover operator is given in Algorithm 3.Algorithm 3:Crossover operator.
Require: Two selected individuals x and y;
Ensure: A new offspring z;
(1)for  i={1,…,n}  do
(2) if  xi=yi  then
(3) Let zi=xi.
(4) else
(5) zi takes value 0 or 1 randomly.
(6) end if
(7)end for
(8)return  z as a new offspring.


### 4.3. The Tabu Search Procedure

Tabu search (TS) is a metaheuristic optimization that has been applied successfully to solve a number of combinatorial optimization problems [42–45]. It combines search strategies that are designed to avoid being trapped in a local minimizer and to present revisiting recently generated solutions [46]. The neighborhood structure and the tabu tenure with which TS is implemented are fundamental to achieving the above objectives. A new solution x0 is generated from the existing solution x, within a defined neighborhood of x, by the operation called a “move.” The solution x0 is not generated again for a number of iterations (tabu tenure).The tabu search procedure presented here differs mainly in solution generation. While we preserve the tabu tenure feature of TS, we do away with the neighborhood structure in generatingx0 from x. The solution generation procedure has been suggested here to conform to the problem at hand and to make the search greedier. In particular, a sequence of flips (each flip returns a solution) on the (allowed) components of x are carried out. The best solution from the sequence is considered as x0. More specific to the problem considered, a flip gain gain(i,x) of a node i (node i corresponds to the variable xi) is defined as follows:
(11)gain(i,x)=L(x)-L(x1,…,xi-1,1-xi,xi+1,…,xn).
A positive gain is a gain when the objective value of problem (UIP2) decreases if the component (variable) xi is flipped from the current value to its complement; that is, if xi=1, then its value is changed to xi=0. Therefore, for each variable xi we keep an associated tabu tenure Ti which prevents xi from being flipped again until Ti diminishes (Ti≤0). Hence, the ith gain (i=1,2,…,n) is calculated using (11) when it is permitted by the tabu tenure Ti or some aspiration criterion is satisfied.At the beginning of the tabu search procedure,Ti (i=1,2,…,n) are initialized by the user and if xi is flipped the corresponding Ti is updated, as suggested by Cai et al. [42], as follows:
(12)Ti={Ti+Ti×∑k=1pxikpifxi=1,Ti+Ti×p-∑k=1pxikpotherwise.
The updating rule (12) is called the feedback mechanism in Cai et al. [42], as this updating prevents Ti from being too large or too small.We have proposed a simple aspiration criterion that permits a variable to be flipped in spite of being tabu if it leads to a solution better than the best solutionxbest produced by the tabu search procedure thus far. There are a number of parameters which are needed to be initialized. These are the maximum numbers of iterations, Maxcount, and the Ti values (i=1,2…,n). The tabu search procedure we have suggested here is now summarized in Algorithm 4. Notice that the index j in step 4 denotes that the node j is not in the tabu list (tj=0) or when the aspiration criterion is met (which is a positive gain). The tabu search procedure process stops when Maxcount of iterations is reached and returns the best solution found in the process.Algorithm 4:The tabu search procedure.
Require: An initial solution x0.
Ensure: The best solution xbest.
(1)    Set the parametersMaxcount and Tj,j=1,…,n. Initiate count=0, ti=0,i=1,…,n, and xbest=x0.
(2)while  count<Maxcount  do
(3)   Calculate the flip gaingain(i,x0),i=1,…,n, using (11).
(4)j = argmax{gain(i,x0)|ti=0 or L(x0)-gain(i,x0)<L(xbest),i=1,…,n}.
(5)   Letxj0=1-xj0. Rename the solution corresponding to this change as x0 again. Calculate Tj by (12), let tj=Tj.
(6)if  L(x0)<L(xbest)  then
(7)    Letxbest=x0.
(8)end if
(9)count=count+1.
(10)for  i={1,…,n}  do
(11)if  ti>0  then
(12)  Let ti=ti-1.
(13)end if
(14)end for
(15)if  count>Maxcount  then
(16)  Break.
(17)end if
(18)end while
(19)return  xbest.


### 4.4. Path Relinking (PR) Procedure

The path relinking technique was originally proposed by Glover et al. [47] to explore possible trajectories connecting high quality solutions obtained by heuristics. It has been applied successfully to solve a number of optimization problems such as data mining [48], unconstrained binary quadratic programming [49], capacitated clustering [50], and multiobjective knapsack problem [51].The PR procedure presented here explores solution trajectories using two good solutions. Within the iteration process of TSMA, there are always two such solutions: the current best solutionx* and the x0 produced by the tabu search procedure. When x*≠x0, PR is executed in an attempt to improve the current best solution x*. At the beginning, PR identifies the number of variables whose values differ in x0 and x*. The indices of these variables are then kept in a set D. PR then starts its iteration process. For each index in D an iteration is executed. PR stops if an improved x* has been found during an iteration.An iteration starts with identifying the indexj corresponding to the highest gain; that is, j=argmax{gain(i,x0)∣foralli}. Let the solution corresponding to the flipping of xj0 be x_0. The following tasks are then performed to see (a) whether PR has obtained a new best solution or (b) whether PR is approaching towards the current x*.(a)
IfL(x_0)<L(x*), then PR stops as it has found a new best solution.(b)
Otherwise,x0 is modified by xj0=1-xj0 where j=argmax{gain(i,x0)∣i∈D}. The index j is then removed from D.PR then proceeds with next iteration for the next index in D. The pseudocode of the PR is illustrated in Algorithm 5.Algorithm 5:Path relinking (PR) procedure.
Require: An initiating solution x0, the current best solution x*.
Ensure: A solution y.
(1)    Initiatey=x*, D=∅.
(2)for  i={1,…,n}  do
(3)if  xi0≠xi*  then
(4)D=D∪{i}.
(5)end if
(6)end for
(7)while  D≠∅  do
(8)   Calculate the flip gainsgain(i,x0),i=1,…,n.
(9)j = argmax{gain(i,x0)|i=1,…,n}.
(10)if  L(x0)-gain(i,x0)<L(x*)  then
(11)   Letxj0=1-xj0, and x*=x0, y=x*.
(12)  Break.
(13)else
(14)j = argmax{gain(i,x0)|i∈D}.
(15)  Letxj0=1-xj0, D=D∖{j}.
(16)end if
(17)end while
(18)return  y.


### 4.5. Population Updating Strategy

A combination of intensification and diversification is essential for designing high quality hybrid heuristic algorithms [52, 53]. We have presented how the TSMA implements its search intensification strategies via the tabu search procedure and PR; we now present its search diversification strategies. This is achieved by updating the population set P with the solution y obtained by the tabu search procedure or PR. In this subsection, y will be referred to as the trial solution.Like any other algorithm [35, 38], the TSMA uses its population updating to cater for both quality and diversity of the member of P. A measure is needed to decide whether the trial solution y should be inserted into P and if so which solution should it replace. To this end, the following function is suggested when x∉P:
(13)g(x,P)={L(x)ifL(x)<L(x*),L(x)-L(x*)+d(x,P)nλotherwise,
where x*∈P is the current best solution and λ>0 is a parameter, which balances the relative importance of the solution quality and the diversity of the population. The function d(x,P), x∉P, is defined as
(14)d(x,P)=min⁡xk∈P⁡d(x,xk),
where
(15)d(x,xk)=∑i=1n‍|xik-xi|.In the updating process, we want to achieve two objectives: solution quality and population diversity. At early stages of TSMA, points inP are scattered and diversely distributed. Therefore, a further diversification is not needed. Hence, the decision whether y∈P and which solution deletes should be based on the contribution of the function value L(y) in g(y,P) and not purely be based on the location of y in the solution space with respect to the points in P (i.e., density of the points {y}∪P). Notice that this always holds in (13) when L(y)<L(x*). For L(y)≥L(x*) (y is likely to be far from x*), L(y)-L(x*) in (13) is likely to dominate d(y,P)/nλ in g(y,P).At later stages of TSMA, points inP are likely to be clustered together. Hence, diversification of the points in P is needed. Clearly, it is likely that L(y)-L(x*) (for y being more likely to be close to x*) is small ensuring less contribution from it and more from d(y,P)/nλ in g(y,P).With the functional form (13) of g(x,P), we now device a strategy to achieve both objectives. Central to this strategy is the comparison of p+1 measure values, namely, {g(xk,P^),g(y,P)}, P^=P∖{xk}∪{y}, k=1,2,…,p. Here g(xk,P^) (resp., g(y,P)) represents a measure with respect to the function value at xk (resp., the function value at y) and its distance (sparsity) with respect to P^ (sparsity of y with respect to P). The point with the minimum measure is then identified; denote it by xl. In particular, we find
(16)xl=argmin{L(xk)-L(x*)+d(xk,P)nλ,xk∈P^}∪{L(y)-L(x*)+d(y,P)nλ},∀xk∈P
(or xl=argmin{L(xk)-L(x*)+d(xk,P)/nλ,xk∈P^}∪{L(y)}, for all xk∈P, when L(y)<L(x*)). When xl≠y, we update P as P=P∖{xl}∪{y}.On the other hand, ifxl=y, then P is updated with y with a small probability. This is because inclusion of y in P with probability one will reduce the diversity of P. In particular, update P=P∖{xs}∪{y} is carried out with small probability, where xs=argmin{L(xk)-L(x*)+d(xk,P)/nλ,xk∈P^}, for all xk∈P. Here xs is replaced to increase the diversity in P. The pseudocode for the population updating procedure is presented with Algorithm 6.Algorithm 6:Population updating procedure.
Require: Population P={x1,…,xp}, the current best solution x*, and a solution x.
Ensure: Updated population P={x1,…,xp}.
(1)    Calculateg(x,P) according to (13);
(2)for  k=1,…,p  do
(3)   calculateg(xk,(P∖{xk})∪{x}) according to (13).
(4)end for
(5)   Letxl=argmin{g(x,P),g(xk,(P∖{xk})∪{x}), k=1,…,p}.
(6)if  xl≠x  then
(7)x is inserted into P, and xl is deleted from P.
(8)else
(9)if  rand(0,1)<pr  then
(10) Let xs=argmin{g(xk,(P∖{xk})∪{x})|k=1,…,p}.
(11)  x is inserted into P, and xs is deleted from P.
(12)end if
(13)end if
(14)return  P.Finally, we present the time required to update the setP. It needs O(n) to calculate the distance between y and xk∈P. The distance d(y,P) can be calculated in time O(pn), and it needs O(p2n) to calculate g(xk,P^). Moreover, it takes O(p) time to find the solution with the smallest and the second smallest values in {g(y,P)}∪{g(xk,P^}, k=1,…,p. Therefore, the total running time of the population updating procedure is bounded by O(p2n).


### 4.6. Termination Criteria

In this paper, we use two criteria to stop TSMA. If the maximum number of generationsGmax⁡ is reached, then we stop the algorithm. On the other hand, when the quality of the best solution from one generation to the next is not improved after Gno generations, then we stop the algorithm. Therefore, the TSMA stops when any of these two criteria is met.


## 4.1. General Framework of the Hybrid Memetic Algorithm

The steps of the general framework of TSMA for solving(UIP2) is shown in Algorithm 2. Throughout its execution, the TSMA updates the upper bound U with the function value at the current best solution x*.Algorithm 2:General structure of TSMA.
Require: A directed acyclic graph;
Ensure: Approximate global maximal solution x*;
(1)    InitialU=∑i=1n‍ahi, x*=(1,…,1).
(2)    Generate randomly a populationP={x1,…,xp}.
(3)for  k={1,…,p}  do
(4)    Use the local search procedure (see Section4.3) to minimize problem (UIP2) from
every individualxk, also denote the obtained solution by xk.
(5)if  L(xk)<U  then
(6)      LetU=L(xk), and x*=xk.
(7)end if
(8)end for
(9)while termination criteria (see Section 4.6) do not meet do
(10)   Use the crossover operator (see Section4.2) to generate a new offspring x0, and
apply the local search procedure to refine x0, also denote it by x0.
(11)if  L(x0)<U  then
(12)    LetU=L(x0), and x*=x0.
(13)end if
(14)if  x0=x*  then
(15)y=x0.
(16)else
(17)  Use the path relinking procedure PR (see Section 4.4) to the solution
x0 and the current best solution x* to obtain a solution y.
(18)end if
(19)if  L(y)<U  then
(20)    LetU=L(y), and x*=y.
(21)end if
(22)  Use the population updating method (see Section4.5) to update the population that is
to decide if y∈P.
(23)end while
(24)return  x* and f(x*) as an approximate discrete global minimizer and global minimal
value of problem (IP), respectively.Before the TSMA begins, its iterative process performs three main steps; see Algorithm2. In step 1, it initializes the first upper bound U of (UIP2) with the known trivial solution where xi=1, i=1,2,…,n. In step 2, it generates the initial random population set of size p; that is, P={x1,…,xp}, xk∈S, k=1,2,…,p. In step 4, the TSMA refines each member of the initial population P by the local search, the tabu search, and treats P as the starting population set.As the iteration process begins, the TSMA repeatedly performs three main steps: crossover followed by tabu search, path relinking, and the updating ofP. In step 10, a new solution x0 is identified using the crossover operation followed by tabu search. In step 17, the path relinking procedure may be applied to x0 in an attempt to generate an improved solution y from x0. Finally, in step 22, the population updating process is performed to decide whether y∈P and which solution should be replaced, provided that such an improved y has been generated. The remaining steps of Algorithm 2 are used to update U and x*. This iterative process repeats itself until some stopping conditions are met.The main iterative components of TSMA, the crossover followed by the tabu search procedure, the path relinking procedure, and the population updating strategy are explained in the subsequent subsections.


## 4.2. Crossover Operator

We adopt the fixed crossover operator [41] to generate a new offspring. First, a pair of individuals are selected randomly from the population. Next, if two selected individuals have the same bit value, their offspring inherits it. Otherwise, it takes value 0 or 1 randomly. Suppose that x and y are two selected individuals from the population. The pseudocode of the crossover operator is given in Algorithm 3.Algorithm 3:Crossover operator.
Require: Two selected individuals x and y;
Ensure: A new offspring z;
(1)for  i={1,…,n}  do
(2) if  xi=yi  then
(3) Let zi=xi.
(4) else
(5) zi takes value 0 or 1 randomly.
(6) end if
(7)end for
(8)return  z as a new offspring.


## 4.3. The Tabu Search Procedure

Tabu search (TS) is a metaheuristic optimization that has been applied successfully to solve a number of combinatorial optimization problems [42–45]. It combines search strategies that are designed to avoid being trapped in a local minimizer and to present revisiting recently generated solutions [46]. The neighborhood structure and the tabu tenure with which TS is implemented are fundamental to achieving the above objectives. A new solution x0 is generated from the existing solution x, within a defined neighborhood of x, by the operation called a “move.” The solution x0 is not generated again for a number of iterations (tabu tenure).The tabu search procedure presented here differs mainly in solution generation. While we preserve the tabu tenure feature of TS, we do away with the neighborhood structure in generatingx0 from x. The solution generation procedure has been suggested here to conform to the problem at hand and to make the search greedier. In particular, a sequence of flips (each flip returns a solution) on the (allowed) components of x are carried out. The best solution from the sequence is considered as x0. More specific to the problem considered, a flip gain gain(i,x) of a node i (node i corresponds to the variable xi) is defined as follows:
(11)gain(i,x)=L(x)-L(x1,…,xi-1,1-xi,xi+1,…,xn).
A positive gain is a gain when the objective value of problem (UIP2) decreases if the component (variable) xi is flipped from the current value to its complement; that is, if xi=1, then its value is changed to xi=0. Therefore, for each variable xi we keep an associated tabu tenure Ti which prevents xi from being flipped again until Ti diminishes (Ti≤0). Hence, the ith gain (i=1,2,…,n) is calculated using (11) when it is permitted by the tabu tenure Ti or some aspiration criterion is satisfied.At the beginning of the tabu search procedure,Ti (i=1,2,…,n) are initialized by the user and if xi is flipped the corresponding Ti is updated, as suggested by Cai et al. [42], as follows:
(12)Ti={Ti+Ti×∑k=1pxikpifxi=1,Ti+Ti×p-∑k=1pxikpotherwise.
The updating rule (12) is called the feedback mechanism in Cai et al. [42], as this updating prevents Ti from being too large or too small.We have proposed a simple aspiration criterion that permits a variable to be flipped in spite of being tabu if it leads to a solution better than the best solutionxbest produced by the tabu search procedure thus far. There are a number of parameters which are needed to be initialized. These are the maximum numbers of iterations, Maxcount, and the Ti values (i=1,2…,n). The tabu search procedure we have suggested here is now summarized in Algorithm 4. Notice that the index j in step 4 denotes that the node j is not in the tabu list (tj=0) or when the aspiration criterion is met (which is a positive gain). The tabu search procedure process stops when Maxcount of iterations is reached and returns the best solution found in the process.Algorithm 4:The tabu search procedure.
Require: An initial solution x0.
Ensure: The best solution xbest.
(1)    Set the parametersMaxcount and Tj,j=1,…,n. Initiate count=0, ti=0,i=1,…,n, and xbest=x0.
(2)while  count<Maxcount  do
(3)   Calculate the flip gaingain(i,x0),i=1,…,n, using (11).
(4)j = argmax{gain(i,x0)|ti=0 or L(x0)-gain(i,x0)<L(xbest),i=1,…,n}.
(5)   Letxj0=1-xj0. Rename the solution corresponding to this change as x0 again. Calculate Tj by (12), let tj=Tj.
(6)if  L(x0)<L(xbest)  then
(7)    Letxbest=x0.
(8)end if
(9)count=count+1.
(10)for  i={1,…,n}  do
(11)if  ti>0  then
(12)  Let ti=ti-1.
(13)end if
(14)end for
(15)if  count>Maxcount  then
(16)  Break.
(17)end if
(18)end while
(19)return  xbest.


## 4.4. Path Relinking (PR) Procedure

The path relinking technique was originally proposed by Glover et al. [47] to explore possible trajectories connecting high quality solutions obtained by heuristics. It has been applied successfully to solve a number of optimization problems such as data mining [48], unconstrained binary quadratic programming [49], capacitated clustering [50], and multiobjective knapsack problem [51].The PR procedure presented here explores solution trajectories using two good solutions. Within the iteration process of TSMA, there are always two such solutions: the current best solutionx* and the x0 produced by the tabu search procedure. When x*≠x0, PR is executed in an attempt to improve the current best solution x*. At the beginning, PR identifies the number of variables whose values differ in x0 and x*. The indices of these variables are then kept in a set D. PR then starts its iteration process. For each index in D an iteration is executed. PR stops if an improved x* has been found during an iteration.An iteration starts with identifying the indexj corresponding to the highest gain; that is, j=argmax{gain(i,x0)∣foralli}. Let the solution corresponding to the flipping of xj0 be x_0. The following tasks are then performed to see (a) whether PR has obtained a new best solution or (b) whether PR is approaching towards the current x*.(a)
IfL(x_0)<L(x*), then PR stops as it has found a new best solution.(b)
Otherwise,x0 is modified by xj0=1-xj0 where j=argmax{gain(i,x0)∣i∈D}. The index j is then removed from D.PR then proceeds with next iteration for the next index in D. The pseudocode of the PR is illustrated in Algorithm 5.Algorithm 5:Path relinking (PR) procedure.
Require: An initiating solution x0, the current best solution x*.
Ensure: A solution y.
(1)    Initiatey=x*, D=∅.
(2)for  i={1,…,n}  do
(3)if  xi0≠xi*  then
(4)D=D∪{i}.
(5)end if
(6)end for
(7)while  D≠∅  do
(8)   Calculate the flip gainsgain(i,x0),i=1,…,n.
(9)j = argmax{gain(i,x0)|i=1,…,n}.
(10)if  L(x0)-gain(i,x0)<L(x*)  then
(11)   Letxj0=1-xj0, and x*=x0, y=x*.
(12)  Break.
(13)else
(14)j = argmax{gain(i,x0)|i∈D}.
(15)  Letxj0=1-xj0, D=D∖{j}.
(16)end if
(17)end while
(18)return  y.


## 4.5. Population Updating Strategy

A combination of intensification and diversification is essential for designing high quality hybrid heuristic algorithms [52, 53]. We have presented how the TSMA implements its search intensification strategies via the tabu search procedure and PR; we now present its search diversification strategies. This is achieved by updating the population set P with the solution y obtained by the tabu search procedure or PR. In this subsection, y will be referred to as the trial solution.Like any other algorithm [35, 38], the TSMA uses its population updating to cater for both quality and diversity of the member of P. A measure is needed to decide whether the trial solution y should be inserted into P and if so which solution should it replace. To this end, the following function is suggested when x∉P:
(13)g(x,P)={L(x)ifL(x)<L(x*),L(x)-L(x*)+d(x,P)nλotherwise,
where x*∈P is the current best solution and λ>0 is a parameter, which balances the relative importance of the solution quality and the diversity of the population. The function d(x,P), x∉P, is defined as
(14)d(x,P)=min⁡xk∈P⁡d(x,xk),
where
(15)d(x,xk)=∑i=1n‍|xik-xi|.In the updating process, we want to achieve two objectives: solution quality and population diversity. At early stages of TSMA, points inP are scattered and diversely distributed. Therefore, a further diversification is not needed. Hence, the decision whether y∈P and which solution deletes should be based on the contribution of the function value L(y) in g(y,P) and not purely be based on the location of y in the solution space with respect to the points in P (i.e., density of the points {y}∪P). Notice that this always holds in (13) when L(y)<L(x*). For L(y)≥L(x*) (y is likely to be far from x*), L(y)-L(x*) in (13) is likely to dominate d(y,P)/nλ in g(y,P).At later stages of TSMA, points inP are likely to be clustered together. Hence, diversification of the points in P is needed. Clearly, it is likely that L(y)-L(x*) (for y being more likely to be close to x*) is small ensuring less contribution from it and more from d(y,P)/nλ in g(y,P).With the functional form (13) of g(x,P), we now device a strategy to achieve both objectives. Central to this strategy is the comparison of p+1 measure values, namely, {g(xk,P^),g(y,P)}, P^=P∖{xk}∪{y}, k=1,2,…,p. Here g(xk,P^) (resp., g(y,P)) represents a measure with respect to the function value at xk (resp., the function value at y) and its distance (sparsity) with respect to P^ (sparsity of y with respect to P). The point with the minimum measure is then identified; denote it by xl. In particular, we find
(16)xl=argmin{L(xk)-L(x*)+d(xk,P)nλ,xk∈P^}∪{L(y)-L(x*)+d(y,P)nλ},∀xk∈P
(or xl=argmin{L(xk)-L(x*)+d(xk,P)/nλ,xk∈P^}∪{L(y)}, for all xk∈P, when L(y)<L(x*)). When xl≠y, we update P as P=P∖{xl}∪{y}.On the other hand, ifxl=y, then P is updated with y with a small probability. This is because inclusion of y in P with probability one will reduce the diversity of P. In particular, update P=P∖{xs}∪{y} is carried out with small probability, where xs=argmin{L(xk)-L(x*)+d(xk,P)/nλ,xk∈P^}, for all xk∈P. Here xs is replaced to increase the diversity in P. The pseudocode for the population updating procedure is presented with Algorithm 6.Algorithm 6:Population updating procedure.
Require: Population P={x1,…,xp}, the current best solution x*, and a solution x.
Ensure: Updated population P={x1,…,xp}.
(1)    Calculateg(x,P) according to (13);
(2)for  k=1,…,p  do
(3)   calculateg(xk,(P∖{xk})∪{x}) according to (13).
(4)end for
(5)   Letxl=argmin{g(x,P),g(xk,(P∖{xk})∪{x}), k=1,…,p}.
(6)if  xl≠x  then
(7)x is inserted into P, and xl is deleted from P.
(8)else
(9)if  rand(0,1)<pr  then
(10) Let xs=argmin{g(xk,(P∖{xk})∪{x})|k=1,…,p}.
(11)  x is inserted into P, and xs is deleted from P.
(12)end if
(13)end if
(14)return  P.Finally, we present the time required to update the setP. It needs O(n) to calculate the distance between y and xk∈P. The distance d(y,P) can be calculated in time O(pn), and it needs O(p2n) to calculate g(xk,P^). Moreover, it takes O(p) time to find the solution with the smallest and the second smallest values in {g(y,P)}∪{g(xk,P^}, k=1,…,p. Therefore, the total running time of the population updating procedure is bounded by O(p2n).


## 4.6. Termination Criteria

In this paper, we use two criteria to stop TSMA. If the maximum number of generationsGmax⁡ is reached, then we stop the algorithm. On the other hand, when the quality of the best solution from one generation to the next is not improved after Gno generations, then we stop the algorithm. Therefore, the TSMA stops when any of these two criteria is met.


## 5. Computational Experiments

In this section, we present experiments performed in order to evaluate the performance of TSMA. The benchmark test instances used are introduced followed by the parameter settings for TSMA. Finally, computational results, comparisons, and analyses are reported. The algorithm is coded in C language and implemented on a PC with 2.11 GHz AMD processor and 1 G of RAM.


### 5.1. Test Instances

Task graphs for free (TGFF) [54] can create directed acyclic graphs (DAGs), that is, task graphs. Given identical parameters and input seeds, it can generate identical task graphs. We have used TGFF (Window Version 3.1) to generate four DAGs as hardware/software partitioning test instances. These DAGs were also used to test the performance of the artificial immune algorithm (ENSA-HSP) [16]. The TGFF (Window Version 3.1) can be obtained at the website (http://ziyang.eecs.umich.edu/~dickrp/tgff/), and the parameters are given in the Appendix. Since these DAGs do not contain cycles, all nodes in each DAG are executed only once; that is, pci=1.The characteristics of these test instances are given in Table1. These are the times when all nodes are implemented by software (TimeSw), the time when all nodes are implemented by hardware (TimeHw), the required time (TimeReq), and the cost when all nodes are implemented by hardware (CostHw).Table 1
The characteristics of four test instances.
No.
DAG
TimeSw
TimeHw
TimeReq
CostHw
1
30 nodes
9736
1782
4963
3039
2
60 nodes
19591
2279
9203
6085
3
90 nodes
28718
3060
13323
8399
4
120 nodes
37354
3056
16775
11187
5
300 nodes
92156
2940
39940
27819
6
500 nodes
155151
3094
66463
45171


### 5.2. The Parameter Settings

The tabu search procedure requires parametersTj, j=1,…,n and Maxcount. We have used Tj=10, j=1,…,n, and Maxcount=1.5×n. These values are different from those used by Cai et al. [42] for unconstrained binary quadratic programming. Justifications for these choices are that the tabu search procedure proposed here is different from [42], and the scale of test problems used in this paper is smaller than that of the test problems used in [42]. Moreover, we have chosen these values based on our numerical experiments.An important parameter of TSMA is the sizep of the population set P. The bigger the value of p is, the higher the CPU time is. This is because O(p2n) operations are needed to update P. The parameter λ in (13) is used by TSMA to diversify P, and as such it has an important significance in the performance of TSMA. We have chosen the values of these two parameters after some numerical experiments.We first conduct a number of preliminary experiments using the test instance number 3, that is, the instance with 90 nodes. We have fixedTj=10, j=1,…,n, Maxcount=1.5×n, Gmax⁡=200, and Gno=20 and run TSMA with various values of p and λ. This experiment was conducted to get suitable ranges for both parameters.With the values ofTj, Maxcount, Gmax⁡, and Gno chosen as above, we have then conducted another series of runs of TSMA using the test instance with 90 nodes. We have used p∈{10,20,30,40}. For each value of p, six values of λ, that is, λ∈{0.001,0.003,0.005,0.008,0.01,0.012}, are used to constitute (p,λ) pairs. Hence, there are 24 (p,λ) pairs. For each pair, TSMA was run 5 times, making a total of 120 runs. The average results of 5 runs on each (p,λ) pair are reported in Table 2.Table 2
Experimental results of our algorithm with tuning of valuesp and λ on the test instance with 90 nodes.
λ
,
p
10
20
30
40
Cost
Time (s)
Cost
Time (s)
Cost
Time (s)
Cost
Time (s)
0.001
3570
15.092
3568
19.531
3561
23.687
3560
23.735
0.003
3571
15.651
3562
18.265
3564
18.625
3559
20.127
0.005
3567
16.539
3561
20.283
3560
15.982
3561
21.077
0.008
3560
16.585
3561
15.617
3566
19.234
3559
20.524
0.01
3562
16.516
3568
15.681
3569
16.484
3558
20.437
0.012
3568
16.597
3556
18.421
3568
16.102
3560
19.511The results in Table2 show that p=20 and λ=0.008 are suitable values to choose. Hence, we have used these values throughout the numerical experiments. We present all parameter values used in TSMA in Table 3, where the column 2 presents the subsections where the corresponding parameter has been discussed.Table 3
Settings of parameters.
Parameters
Section
Value
p
4.1
20
T
j
4.3
10
M
a
x
c
o
u
n
t
4.3
1.5
×
n
λ
4.4
0.008
p
r
4.4
0.2
G
max
⁡
4.6
500
G
no
4.6
50


### 5.3. Numerical Comparisons

In order to show the effectiveness of TSMA, we compare its results with those of the evolutionary negative selection algorithm (ENSA-HSP) [16] and traditional evolutionary algorithm (EA) [16]. TSMA was run 20 times on each test instance in Table 1; hence, average results are used in the comparison. Results of ENSA-HSP and EA have been taken from [16]. Comparisons of results are presented in Table 4, where columns under the captions “best,” “mean,” and “worst” report the best cost, the average cost, and the worst cost, respectively. The column under the caption “time” reports the average CPU times for TSMA. We are unable to present the CPU times for the other two algorithms as this would require running these algorithms ourselves, since the CPU times of EA and ENSA-HSP were not reported in [16]. The last column of Table 4 reports the percentage of improvement on the best results by TSMA. The results obtained by all three algorithms on the first 4 test instances are further summarized in Figures 2, 3, 4, and 5.Table 4
Obtained results for EA, ENSA-HSP, and TSMA.
DAG
EA [16]
ENSA-HSP [16]
TSMA
Improve
Best
Mean
Worst
Best
Mean
Worst
Best
Mean
Worst
Time
30 nodes
1350
1409
1473
1335
1339
1350
1335
1335.0
1335
1.078
0%
60 nodes
2923
2980
3072
2884
2912
2931
2800
2806.1
2814
12.625
2.91%
90 nodes
3804
3915
4100
3617
3726
3761
3552
3557.1
3564
41.545
1.80%
120 nodes
5363
5506
5619
5177
5308
5346
5001
5005.2
5021
145.259
3.40%
300 nodes
12556
12581.6
12639
1456.672
500 nodes
20497
20578.8
20667
3204.913Figure 2
Experimental results on test instance with 30 nodes.Figure 3
Experimental results on test instance with 60 nodes.Figure 4
Experimental results on test instance with 90 nodes.Figure 5
Experimental results on test instance with 120 nodes.Figures3–5 clearly show the superiority of TSMA over the other two algorithms. Wide differences in costs are noticeable in these figures. Indeed, it can be seen from Table 4 that the TSMA has achieved 84, 65, and 176 less costs than the corresponding previous best obtained by ENSA-HSP for the instances numbers 2, 3, and 4, respectively. These improvements are quite significant.


### 5.4. Effectiveness of the Adaptive Penalty Function

In order to show the effectiveness of our proposed parameter-free adaptive penalty function, we have replaced the adaptive penalty functionL(x) in (2) with the exact penalty function χ(x,R,q)(q=1) in (1) and kept other ingredients of TSMA including the parameter values in Table 3 intact. We denote this implementation of TSMA by TSMA2. Since the parameter R in χ(x,R,q) is problem-dependent, we took R=50, 100,  and  200 and run TSMA2 20 times on each of the test instances, for each R value. Average results including average CPU times (in seconds) are summarized in Table 5. A number of observations and comparisons using the results in Table 4 are now presented below.(1)
Dependency onR: it can be clearly seen in Table 5 that results are very much dependent on R values. While results are comparable on instance number 1 for all R values, results for the other instance are not the same. To give an example, in terms of the “mean” value, the best result was obtained for R=200 on instance number 2, while, for the instance numbers 3 and 4, the best “mean” values were obtained using R=50.(2)
Comparison using “mean”: The TSMA performs better than TSMA2 for all instances, except for instance number 1 for which both perform the same.(3)
Comparison using “best”: The TSMA performs better than TSMA2 on the last instance while both are equally matched on the remaining instances. TSMA2 obtained these results for instances 1, 2, and 3 forR=50.(4)
Comparison using “time”: The best CPU times are different for differentR values in TSMA2. However, even if we take the best CPU times obtained by TSMA2 disregarding the R values then the results are still comparable between TSMA2 and TSMA.Table 5
Obtained results for TSMA2.
DAG
R
=
50
R
=
100
R
=
200
Best
Mean
Worst
Time
Best
Mean
Worst
Time
Best
Mean
Worst
Time
30 nodes
1335
1335.0
1335
0.986
1335
1335.0
1335
1.015
1335
1335.0
1335
0.906
60 nodes
2800
2811.7
2820
15.424
2805
2811.5
2818
14.804
2809
2811.0
2818
12.047
90 nodes
3552
3557.2
3570
41.592
3556
3559.4
3565
36.209
3556
3559.6
3565
37.491
120 nodes
5005
5028.1
5069
180.434
5018
5035.1
5068
161.848
5018
5029.2
5055
179.020A statistical view in terms of boxplot is now shown in Figures6, 7, and 8 using optimal values obtained by TSMA and TSMA2 over 20 runs. Three figures are presented since the standard deviation is zero for instance number 1. These boxplots show that ranges over which the best results obtained over 20 runs vary. All three figures clearly show that the boxplots of TSMA has less height than those of the corresponding boxplots obtained by TSMA2 for three R values. This clearly establishes the superiority of the adaptive penalty function L(x) presented in (2) over the exact penalty function (1).Figure 6
Boxplots of the test instance with 60 nodes.Figure 7
Boxplots of the test instance with 90 nodes.Figure 8
Boxplots of the test instance with 120 nodes.


## 5.1. Test Instances

Task graphs for free (TGFF) [54] can create directed acyclic graphs (DAGs), that is, task graphs. Given identical parameters and input seeds, it can generate identical task graphs. We have used TGFF (Window Version 3.1) to generate four DAGs as hardware/software partitioning test instances. These DAGs were also used to test the performance of the artificial immune algorithm (ENSA-HSP) [16]. The TGFF (Window Version 3.1) can be obtained at the website (http://ziyang.eecs.umich.edu/~dickrp/tgff/), and the parameters are given in the Appendix. Since these DAGs do not contain cycles, all nodes in each DAG are executed only once; that is, pci=1.The characteristics of these test instances are given in Table1. These are the times when all nodes are implemented by software (TimeSw), the time when all nodes are implemented by hardware (TimeHw), the required time (TimeReq), and the cost when all nodes are implemented by hardware (CostHw).Table 1
The characteristics of four test instances.
No.
DAG
TimeSw
TimeHw
TimeReq
CostHw
1
30 nodes
9736
1782
4963
3039
2
60 nodes
19591
2279
9203
6085
3
90 nodes
28718
3060
13323
8399
4
120 nodes
37354
3056
16775
11187
5
300 nodes
92156
2940
39940
27819
6
500 nodes
155151
3094
66463
45171


## 5.2. The Parameter Settings

The tabu search procedure requires parametersTj, j=1,…,n and Maxcount. We have used Tj=10, j=1,…,n, and Maxcount=1.5×n. These values are different from those used by Cai et al. [42] for unconstrained binary quadratic programming. Justifications for these choices are that the tabu search procedure proposed here is different from [42], and the scale of test problems used in this paper is smaller than that of the test problems used in [42]. Moreover, we have chosen these values based on our numerical experiments.An important parameter of TSMA is the sizep of the population set P. The bigger the value of p is, the higher the CPU time is. This is because O(p2n) operations are needed to update P. The parameter λ in (13) is used by TSMA to diversify P, and as such it has an important significance in the performance of TSMA. We have chosen the values of these two parameters after some numerical experiments.We first conduct a number of preliminary experiments using the test instance number 3, that is, the instance with 90 nodes. We have fixedTj=10, j=1,…,n, Maxcount=1.5×n, Gmax⁡=200, and Gno=20 and run TSMA with various values of p and λ. This experiment was conducted to get suitable ranges for both parameters.With the values ofTj, Maxcount, Gmax⁡, and Gno chosen as above, we have then conducted another series of runs of TSMA using the test instance with 90 nodes. We have used p∈{10,20,30,40}. For each value of p, six values of λ, that is, λ∈{0.001,0.003,0.005,0.008,0.01,0.012}, are used to constitute (p,λ) pairs. Hence, there are 24 (p,λ) pairs. For each pair, TSMA was run 5 times, making a total of 120 runs. The average results of 5 runs on each (p,λ) pair are reported in Table 2.Table 2
Experimental results of our algorithm with tuning of valuesp and λ on the test instance with 90 nodes.
λ
,
p
10
20
30
40
Cost
Time (s)
Cost
Time (s)
Cost
Time (s)
Cost
Time (s)
0.001
3570
15.092
3568
19.531
3561
23.687
3560
23.735
0.003
3571
15.651
3562
18.265
3564
18.625
3559
20.127
0.005
3567
16.539
3561
20.283
3560
15.982
3561
21.077
0.008
3560
16.585
3561
15.617
3566
19.234
3559
20.524
0.01
3562
16.516
3568
15.681
3569
16.484
3558
20.437
0.012
3568
16.597
3556
18.421
3568
16.102
3560
19.511The results in Table2 show that p=20 and λ=0.008 are suitable values to choose. Hence, we have used these values throughout the numerical experiments. We present all parameter values used in TSMA in Table 3, where the column 2 presents the subsections where the corresponding parameter has been discussed.Table 3
Settings of parameters.
Parameters
Section
Value
p
4.1
20
T
j
4.3
10
M
a
x
c
o
u
n
t
4.3
1.5
×
n
λ
4.4
0.008
p
r
4.4
0.2
G
max
⁡
4.6
500
G
no
4.6
50


## 5.3. Numerical Comparisons

In order to show the effectiveness of TSMA, we compare its results with those of the evolutionary negative selection algorithm (ENSA-HSP) [16] and traditional evolutionary algorithm (EA) [16]. TSMA was run 20 times on each test instance in Table 1; hence, average results are used in the comparison. Results of ENSA-HSP and EA have been taken from [16]. Comparisons of results are presented in Table 4, where columns under the captions “best,” “mean,” and “worst” report the best cost, the average cost, and the worst cost, respectively. The column under the caption “time” reports the average CPU times for TSMA. We are unable to present the CPU times for the other two algorithms as this would require running these algorithms ourselves, since the CPU times of EA and ENSA-HSP were not reported in [16]. The last column of Table 4 reports the percentage of improvement on the best results by TSMA. The results obtained by all three algorithms on the first 4 test instances are further summarized in Figures 2, 3, 4, and 5.Table 4
Obtained results for EA, ENSA-HSP, and TSMA.
DAG
EA [16]
ENSA-HSP [16]
TSMA
Improve
Best
Mean
Worst
Best
Mean
Worst
Best
Mean
Worst
Time
30 nodes
1350
1409
1473
1335
1339
1350
1335
1335.0
1335
1.078
0%
60 nodes
2923
2980
3072
2884
2912
2931
2800
2806.1
2814
12.625
2.91%
90 nodes
3804
3915
4100
3617
3726
3761
3552
3557.1
3564
41.545
1.80%
120 nodes
5363
5506
5619
5177
5308
5346
5001
5005.2
5021
145.259
3.40%
300 nodes
12556
12581.6
12639
1456.672
500 nodes
20497
20578.8
20667
3204.913Figure 2
Experimental results on test instance with 30 nodes.Figure 3
Experimental results on test instance with 60 nodes.Figure 4
Experimental results on test instance with 90 nodes.Figure 5
Experimental results on test instance with 120 nodes.Figures3–5 clearly show the superiority of TSMA over the other two algorithms. Wide differences in costs are noticeable in these figures. Indeed, it can be seen from Table 4 that the TSMA has achieved 84, 65, and 176 less costs than the corresponding previous best obtained by ENSA-HSP for the instances numbers 2, 3, and 4, respectively. These improvements are quite significant.


## 5.4. Effectiveness of the Adaptive Penalty Function

In order to show the effectiveness of our proposed parameter-free adaptive penalty function, we have replaced the adaptive penalty functionL(x) in (2) with the exact penalty function χ(x,R,q)(q=1) in (1) and kept other ingredients of TSMA including the parameter values in Table 3 intact. We denote this implementation of TSMA by TSMA2. Since the parameter R in χ(x,R,q) is problem-dependent, we took R=50, 100,  and  200 and run TSMA2 20 times on each of the test instances, for each R value. Average results including average CPU times (in seconds) are summarized in Table 5. A number of observations and comparisons using the results in Table 4 are now presented below.(1)
Dependency onR: it can be clearly seen in Table 5 that results are very much dependent on R values. While results are comparable on instance number 1 for all R values, results for the other instance are not the same. To give an example, in terms of the “mean” value, the best result was obtained for R=200 on instance number 2, while, for the instance numbers 3 and 4, the best “mean” values were obtained using R=50.(2)
Comparison using “mean”: The TSMA performs better than TSMA2 for all instances, except for instance number 1 for which both perform the same.(3)
Comparison using “best”: The TSMA performs better than TSMA2 on the last instance while both are equally matched on the remaining instances. TSMA2 obtained these results for instances 1, 2, and 3 forR=50.(4)
Comparison using “time”: The best CPU times are different for differentR values in TSMA2. However, even if we take the best CPU times obtained by TSMA2 disregarding the R values then the results are still comparable between TSMA2 and TSMA.Table 5
Obtained results for TSMA2.
DAG
R
=
50
R
=
100
R
=
200
Best
Mean
Worst
Time
Best
Mean
Worst
Time
Best
Mean
Worst
Time
30 nodes
1335
1335.0
1335
0.986
1335
1335.0
1335
1.015
1335
1335.0
1335
0.906
60 nodes
2800
2811.7
2820
15.424
2805
2811.5
2818
14.804
2809
2811.0
2818
12.047
90 nodes
3552
3557.2
3570
41.592
3556
3559.4
3565
36.209
3556
3559.6
3565
37.491
120 nodes
5005
5028.1
5069
180.434
5018
5035.1
5068
161.848
5018
5029.2
5055
179.020A statistical view in terms of boxplot is now shown in Figures6, 7, and 8 using optimal values obtained by TSMA and TSMA2 over 20 runs. Three figures are presented since the standard deviation is zero for instance number 1. These boxplots show that ranges over which the best results obtained over 20 runs vary. All three figures clearly show that the boxplots of TSMA has less height than those of the corresponding boxplots obtained by TSMA2 for three R values. This clearly establishes the superiority of the adaptive penalty function L(x) presented in (2) over the exact penalty function (1).Figure 6
Boxplots of the test instance with 60 nodes.Figure 7
Boxplots of the test instance with 90 nodes.Figure 8
Boxplots of the test instance with 120 nodes.


## 6. Conclusion

In this paper, we have presented a memetic algorithm for the hardware/software partitioning problem. The algorithm has three main components: a local tabu search, a path relinking procedure, and population updating. The local tabu search is a “controlled local search” procedure used for search intensification. The path relinking procedure uses further exploitation of solutions and population updating is used for diversification of solutions. Motivations for each of these components within the proposed memetic algorithm are provided.The hardware/software partitioning problem is converted into an equivalent unconstrained binary optimization problem by employing a parameter-free adaptive penalty function. We have motivated this penalty function first by theoretically and then by numerically comparing its performance with the exact penalty function. The memetic algorithm is then applied to this unconstrained problem, and robustness with respect to the quality of optimal solution is shown by comparing it with another two algorithms from the literature.



---

*Source: 103059-2014-07-13.xml*