This article has been accepted for inclusion in a future issue of this journal. Content is final as presented, with the exception of pagination.
IEEE TRANSACTIONS ON CYBERNETICS

1

A Novel Integer-Coded Memetic Algorithm for the
Set k-Cover Problem in Wireless Sensor Networks
Chien-Chih Liao and Chuan-Kang Ting, Senior Member, IEEE

Abstract—The Set k-Cover problem aims to partition a set ofnodes for the maximal number of covers. This problem is crucial for extending the lifetime of wireless sensor networks (WSNs)
under the constraint of covering all targets. More specifically, theSet k-Cover problem enables partitioning the set of sensors into
several covers over all targets and activating the covers by turns
to effectively extend the WSN lifetime. To resolve this problem,
we propose a novel memetic algorithm (MA) based on integercoded genetic algorithm and local search. This paper adapts the
crossover and mutation operators to integer representation and,furthermore, designs a new fitness function that considers boththe number of covers and the contribution of each sensor tocovers. A local improvement method, called the recycling operator, is developed to enhance the performance on the Set k-Coverproblem. Experimental results show that the proposed MA significantly outperforms five evolutionary algorithms in terms ofthe number of covers obtained, hit rate (HR), and running time.
In particular, the new MA increases 38.1% HR and saves 78.7%
running time of state-of-the-art MA on average. The preferable
results validate the effectiveness and efficiency of the proposed
MA for the Set k-Cover problem.
Index Terms—Evolutionary computation, genetic algorithm (GA), lifetime extension, local search, memetic
algorithm (MA), wireless sensor networks (WSNs).

I. I NTRODUCTION
IRELESS sensor networks (WSNs) have been widely
applied to home security, surveillance, and environmental monitoring [3], [4], [21], [34]. The WSNs are composed of tiny, cheap, and wirelessly connected sensors thatare ordinarily powered by batteries. In WSNs, sensors are
deployed in a random or systematical manner to gather information within their sensing range. The sensors can transmit
and even process the gathered information wirelessly. A crucial consideration to WSNs is the energy efficiency for longnetwork lifetime. The various aspects of energy efficiency in
WSNs include sensor scheduling [7], [31], [33], sensor deployment [6], [23], [35], data aggregation [15], [18], [19], [24],and routing protocol [16], [25], [28]. Akyildiz et al. [3]W

Manuscript received November 14, 2016; revised April 21, 2017; accepted
July 8, 2017. This paper was recommended by Associate Editor Y. S. Ong.
(Corresponding author: Chuan-Kang Ting.)
The authors are with the Department of Computer Science and Information
Engineering, National Chung Cheng University, Chiayi 621, Taiwan (e-mail:lcch97p@cs.ccu.edu.tw; ckting@cs.ccu.edu.tw).
Color versions of one or more of the figures in this paper are available
online at http://ieeexplore.ieee.org.
Digital Object Identifier 10.1109/TCYB.2017.2731598

conducted a survey on the related problems and applicationsof WSNs.
Coverage is another key design factor in WSNs, which
requires the sensors to cover all targets [6], [38]. However,
due to the limited battery-powered energy, extending the WSN
lifetime with full coverage is greatly needed [7], [9], [37].
An effective way to extend the WSN lifetime under thecoverage constraint is to partition the set of sensors into several covers over all targets and then activate the covers one
by one, where a cover is defined as a set of sensors that
includes all targets [27], [29], [32]. By this way, the WSN
lifetime can ideally be extended k times through the sequential activation of k covers under the coverage constraint. The
Set k-Cover problem is formulated to optimize the schedule of sensor activities for maximal lifetime extension [31].
This problem aims to find the optimal partition of sensor
set for maximal number of covers so as to maximize the
WSN lifetime. The Set k-Cover problem has been proved to
be NP-complete. Heuristic and metaheuristic algorithms are
therefore proposed to deal with this problem. For example, themost constrained-minimally constraining covering (MCMCC)
algorithm [31] explores the covers according to a heuristic
based on the coverage of sensors, while the maximum covers using mixed integer programming (MCMIP) [7] conducts
an implicit exhaustive search for covers. These algorithms,
nevertheless, encounter the tradeoff between solution quality
and efficiency: the approaches like MCMCC take only polynomial time but the results are unsatisfactory; on the other
hand, the algorithms like MCMIP can achieve the optimal
solution but are computationally very expensive. Some evolutionary algorithms (EAs) are further developed to address
this issue [10], [17], [20], [33], [39].
Memetic algorithm (MA) hybridizes EA with local search
operator to enhance the search ability of EA. This hybridization has shown to be very effective for superior solution
quality and convergence speed [11]–[14]. In this paper, we
propose an MA for the Set k-Cover problem. Specifically,
the MA is based on integer-coded genetic algorithm (GA)and a local search operator. This paper devises mix crossoverand mutation operators for the MA and presents a new
fitness function that considers both the number of covers
obtained and the contribution of sensors to formation of covers. The recycling operator is further developed to enhance
the local search capability of the MA. This paper carries
out experiments and performance comparison to examine theadvantages of the MA in solution quality and convergence
speed.

c 2017 IEEE. Personal use is permitted, but republication/redistribution requires IEEE permission.
2168-2267 
See http://www.ieee.org/publications_standards/publications/rights/index.html for more information.

This article has been accepted for inclusion in a future issue of this journal. Content is final as presented, with the exception of pagination.
2

IEEE TRANSACTIONS ON CYBERNETICS

Fig. 2.

Fig. 1.

Example WSN.

The main contributions of this paper are summarized asfollows.
1) We propose a novel integer-coded MA for the Set
k-Cover problem. A tight upper bound is derived forthe integer representation of sensor assignment. The
crossover and mutation operators are designed to maintain the separation of critical sensors.
2) A new fitness function is devised considering the contribution of sensors in addition to the number of covers.
The fitness evaluation can hence distinguish the utilization of sensors.
3) The recycling operator provides an effective local
improvement by rearranging sensors to squeeze morecovers without destroying the covers formed.
4) Comprehensive experiments are carried out to investigate the performance and advantages of the proposed
MA in comparison with state-of-the-art methods. In
addition, the experiments explore the effects of sensor
range, the number of sensors, and the number of targets,upon the solution quality and running time.
The remainder of this paper is organized as follows. Section II
gives the formulation of Set k-Cover problem and recapitulates its application to WSN lifetime extension. The proposed
MA and its associated operators are described in Section III.
Section IV presents the experimental results and performancecomparison. Finally, the conclusions are drawn in Section V.
II. S ET k-C OVER P ROBLEM
Given n sensors S = {s1 , . . . , sn } randomly distributed tomonitor m targets T = {t1 , . . . , tm }, a target tj is said to becovered if it locates in the sensing range of at least one sensor.
Fig. 1 illustrates a WSN consisting of seven sensors and fourtargets. The relationship between sensors and targets can be
represented by a bipartite graph G = (V, E), where V = S ∪ T
and eij ∈ E if si covers tj . For example, Fig. 2 demonstrates the
bipartite graph of the WSN in Fig. 1, where s1 = {t1 , t2 , t3 },s2 = {t2 , t4 }, and so on. In this example, the maximum number
k of covers is three and the covers are C1 = {s1 , s2 }, C2 ={s4 , s7 }, and C3 = {s3 , s5 , s6 }.
The Set k-Cover problem is to find the maximal number ofcovers from the sensors for WSN lifetime extension. That is,
this problem aims to partition all sensors into several groups

Bipartite graph of a WSN.

for the covers, where a cover is defined as a group that cansense all targets. The Set k-Cover problem has been proved
to be NP-complete [7], [31]. The formal definition is given
below.
Definition 1 (Set k-Cover Problem): Given a collection
S = {s1 , . . . , sn } of subsets of a finite set T = {t1 , . . . , tm },find the maximum number, k, of covers C1 , . . . , Ck ⊆ S with
Ci ∩ Cj = ∅ for i = j, such that every element of T belongs
to at least one element of Ci .
Slijepcevic and Potkonjak [31] formulated the Set k-Coverproblem to extend WSN lifetime. They designed a polynomialtime heuristic method, called the MCMCC heuristic, for the
Set k-Cover problem. However, the solutions obtained from
MCMCC are often unsatisfactory. Cardei and Du [7] presented
an equivalent problem, i.e., the disjoint set cover (DSC)
problem, for WSN lifetime extension. They transformed the
DSC problem into the maximum flow problem and solved itby the MCMIP. The MCMIP method guarantees the optima
but requires exponential running time due to its exhaustive
search, which is impractical for large-scale WSNs.
Furthermore, Cardei et al. [8] extended the DSC problem
by allowing a sensor being assigned to multiple sensor
covers. Berman et al. [5] considered the energy consumption rate and relaxed the constraint of disjoint covers in thescheduling of sensor activation. The problem is designatedthe sensor network life problem. This paper develops the(1 + ln(1 − q)−1 )-approximation algorithm guaranteeing thata q-portion of the monitored area is covered; for example,
the lifetime obtained from the schedule must be at most 5.6
times shorter than the optimum lifetime for covering 99% ofmonitor area. Abrams et al. [1] considered maximization of
network coverage rather than lifetime. They developed a randomized algorithm with an expected fraction 1 − 1/e to the
optimum; moreover, they designed two greedy algorithms: one
is a distributed (1 + 1/2)-approximation algorithm, and theother is a centralized (1 + (1 − 1/e))-approximation algorithm.
Ai et al. [2] modeled the problem of maximizing coverage
under the consideration of lifetime guarantee. The authors
proposed a distributed, robust, asynchronous algorithm to findthe near-optimal coverage.
In the light of the success in resolving various optimization
problems, some studies attempt applying EAs to deal with
the Set k-Cover problem recently. Lai et al. [20] proposeda GA for maximum disjoint set covers (GAMDSC), whichuses integer-coded representation to indicate the grouping of
sensors. In addition, a scattering operator is performed on

This article has been accepted for inclusion in a future issue of this journal. Content is final as presented, with the exception of pagination.
LIAO AND TING: NOVEL INTEGER-CODED MA FOR SET k-COVER PROBLEM IN WSNs

each offspring to dispatch the critical sensors to different
groups. The GAMDSC achieves significantly more covers than
MCMCC does and requires less time than MCMIP. Liao andTing [22] presented an order-based GA that conceptualizes
partitioning the sensor set for covers as a process of collecting covers from sensors. Furthermore, Ting and Liao [33]designed an order-based MA for the Set k-Cover problem. The
simulation results show that their MA outperforms MCMCC,
integer-coded GA, order-coded GA, in the number of covers obtained, and is therefore viewed as a state-of-the-art EA
for the Set k-Cover problem. Chen et al. [10] considered the
dynamics of sensor activities and proposed a hybrid memetic
framework to optimize disjoint set covers and dynamic coverage maintenance simultaneously. Zhang et al. [39] proposeda parallel GA using Kuhn–Munkres algorithm to address the
Set k-Cover problem in large-scale WSNs.
The above studies show promising results on the Set
k-Cover problem; however, there exist some issues at
the approaches. Regarding the chromosome representation,
integer-coded representation [20] provides a straightforward
way to group sensors but cannot ensure that a group canform a cover. The required upper bound for the number ofcovers is another issue to address in the integer-coded representation. By contrast, the order-based representation proposedin [22] and [33] removes the need for the upper bound andcan guarantee the completeness of covers. Nevertheless, orderbased representation requires extra cost to examine every
sensor to see if it achieves a cover. Aside from representation, the design and computational cost of fitness evaluation
are essential to the performance. The hybrid memetic framework in [10] needs to repeat the MA several times tocollect all covers, thereby aggravating the computational cost.
The Kuhn–Munkres scheduled parallel genetic approach [39]applies the divide-and-conquer strategy to separate the target
area into numerous subareas for the parallel GA to tackle, andthen merges the feasible solutions from all subproblems. The
evaluation on the number of covers obtained, however, requires
several matching combinations with high time complexity.
This paper aims to design an effective and efficient MA
to address the above issues and improve the performance on
the Set k-Cover problem in order to extend WSN lifetime.
More details about the problem formulation and the proposed
algorithm are given below.

3Fig. 3. Integer-coded chromosome. The number in the circle indicates theindex of group. Gray circles mark the selected critical sensors.

Algorithm 1 Memetic Algorithm
1: Initialize population
2: Evaluate population
3: while (not terminated) do
4:
Select from population as parents
5:
Crossover the parents to generate offspring
6:
Mutate offspring
7:
Local improvement on offspring
8:
Evaluate offspring
9:
Survive from parents and offspring as population
10: end while

operator then exchanges partial information of two parents to
produce offspring. The MA determines a probability, named
crossover rate, to perform the crossover operator. Similarly, themutation operator is performed with a predetermined mutation
rate to change some genes in the offspring. After crossoverand mutation, the recycling operator is performed on the offspring to improve its quality. The reproduction process, to wit,
selection, crossover, mutation, and recycling, repeats until theoffspring population is filled. Acting on the Darwinian theory “survival of the fittest,” the survivor operator subsequently
chooses the fittest chromosomes to survive into the next generation. Algorithm 1 presents the framework of the proposed
MA. The following sections elucidate the MA components indetail.

III. P ROPOSED M EMETIC A LGORITHM
EAs have shown their effectiveness on various search andoptimization problems. MA is an emerging dialect of EAs. To
enhance the search efficiency, MA performs local improvement on the candidate solutions generated by EA in theevolution process [26], [30], [36]. Restated, MA combines EA
and local search for performance enhancement.
This paper proposes a novel MA based on integer-coded
GA and the recycling operator for the Set k-Cover problem.
Following the framework of GA, the MA initializes the
population by randomly generating chromosomes. Next, theselection operator chooses some chromosomes from the population to serve as parents for reproduction. The crossover

A. Representation
The candidate solutions in the MA are encoded as chromosomes to be evolved. This paper adopts integer representation
for the grouping of sensors in the Set k-Cover problem. The
gene value c at locus i indicates that sensor si is assigned
to the group number Gc ; a chromosome therefore designates
the group composition. Fig. 3 illustrates an example chromosome with groups G1 = {s1 , s2 }, G2 = {s3 , s5 , s6 }, andG3 = {s4 , s7 }.
The integer representation requires an upper bound ub forthe valid range of the number of covers. A gene in a chromosome is therefore represented by c ∈ {1, 2, . . . , ub}. A naive

This article has been accepted for inclusion in a future issue of this journal. Content is final as presented, with the exception of pagination.
4

Fig. 4.

IEEE TRANSACTIONS ON CYBERNETICS

Crossover operation. The critical sensors are marked in gray.

upper bound can be determined by the least covered targets,
namely mint∈T |S(t)|, where S(t) denotes the set of sensors
covering target t. This upper bound, nonetheless, disregards
the amount of sensors required to form a cover and thus resultsin overestimated number of covers. For example, the instancein Fig. 2 has mint∈T |S(t)| = 4 and yet can form only threecovers.
To address this issue, we derive a tighter upper bound,which considers both the least covered targets and the minimal number of sensors needed. Let T(s) denote the set oftargets covered by sensor s. For calculation of the latter, weseparate the sensor set S into two subsets Sf and Sp , whereSf = {s ∈ S|s ≡ T} contains the sensors that can cover all
targets and Sp = S − Sf . Dividing the total amount of targets|T| by the maximum number of targets monitored by a sensor s ∈ Sp assists in estimating the least number of sensors
required for forming a cover, that is


|T|
cover
|Sp | =.
(1)maxs∈Sp |T(s)|Considering both the naive bound and the tighter boundpresented in (1), the new upper bound is defined by



|Sp |
ub = min min |S(t)|, |Sf | +
.
(2)
t∈T
|Spcover |The example in Fig. 2 illustrates the utility of this new upperbound. According to (2), the upper bound is calculated by
⎧
⎢
⎥⎫
⎢
⎥
⎨
⎢ 7 ⎥⎬⎣ ⎦ = min(4, 3.5 ) = 3
ub = min 4, 0 +⎭⎩4

B. Variation Operators
The crossover operator exchanges partial information of theparents to produce offspring. Various crossover operators, suchas 1-point, n-point, and uniform crossover, have been proposed
for integer-coded representation. These operators, nevertheless, are unable to keep critical sensors separated. This paper
designs a crossover operator to deal with this issue: an offspring inherits the group indexes of critical sensors from one
parent and then fills the remaining loci with the genes of theother parent. By this way, the proposed mix crossover operator can recombine the parental information without destructing
separation of critical sensors. Fig. 4 illustrates the crossover
operation, where the offspring inherits the critical sensors fromparent 2 and the other sensors from parent 1.
To introduce small variation, the mutation operator slightly
alters the genes of chromosomes. An adequate mutation operator, as well as crossover operator, needs to change the groupcomposition under the constraint of separating critical sensors.
This paper presents the mix mutation that applies different
mutation operators for the two types of sensors (genes). The
mutation first changes the group indexes of either critical sensors or the noncritical ones with equal probability. Then theswap mutation and the random resetting mutation are conducted regarding critical and noncritical sensors, respectively.
Restated, the swap mutation randomly exchanges two critical sensors, while the random resetting mutation reassigns
the group index of noncritical sensors. Both mutation operators infuse diversity into group composition; in particular,
the swap mutation caters to change the arrangement of critical sensors. Fig. 5 presents an example of these two mutation
operators.

3

which provides a bound tighter than mint∈T |S(t)| = 4, thereby
reducing the search space.
The proposed MA randomly picks one of the least covered targets and regards its corresponding sensors as criticalsensors. The optimal solution, in essence, must assign thesensors that monitor the same least covered target to distinct groups for more covers. Note that the number of criticalsensors (i.e., mint∈T |S(t)|) is greater than or equal to thenumber of groups ub. Based on these observations, the MA
randomly selects ub critical sensors and distributes them tothe ub groups for each chromosome. To summarize, theproposed representation considers two characteristics of WSN
lifetime extension through recycling redundant sensors andcompulsorily separating critical sensors.

C. Recycling Operator
Considering the fact that some sensors are made redundantfrom the groups, moving these sensors to other groups is apromising task for gaining more covers. This paper develops
the recycling operator to reallocate the redundant sensors toearn covers. The recycling operation is performed on eachoffspring after mutation.
The recycling operator includes two key steps. The firstis to discover the redundant sensors from all groups. A
redundant sensor is defined as a noncritical sensor that,once removed, will not shrink the coverage of its present
group. The second key step is to randomly dispatch redundant sensors to the groups that have not formed covers
yet. In this way, the recycling operator will not destroy aThis article has been accepted for inclusion in a future issue of this journal. Content is final as presented, with the exception of pagination.
LIAO AND TING: NOVEL INTEGER-CODED MA FOR SET k-COVER PROBLEM IN WSNs

Fig. 5.

5

Mutation operation including the swap mutation and the random resetting mutation. The critical sensors are marked in gray.

Algorithm 2 Recycling Operator
1: procedure R ECYCLE
2:for i ∈ {1, . . . , ub} do3:for s ∈ Gi do
4:
if T(Gi − {s}) = T(Gi ) then5:
Gj ← RandomPick(U)U: collection of non-cover groups6:
Gj ← Gj + {s}7:Gi ← Gi − {s}8:end if
9:end for10:
end for
11: end procedure

cover while extracting redundant sensors from it. In addition, reallocation of redundant sensors helps the groups
to grow as covers. Algorithm 2 presents the procedureof recycling
operator. Its time complexity is O(|S|) inthat ubi=1 |Gi | = |S|.
D. Fitness Evaluation
Considering the objective of the Set k-Cover problem, an
intuitive fitness evaluation is to count the number of covers
formed by the group partition indicated in the chromosome.
However, such fitness evaluation fails to distinguish the different arrangements of sensors that achieve an identical numberof covers. Furthermore, it renders no information about thesensor utilization, which is closely associated with the room
for improvement by the recycling operator. In this paper, we
design a novel fitness function considering both the number of covers and the sensor utilization, where the latter ismeasured by the average contribution of all groups to the formation of covers. The fitness value of a chromosome x isdefined by
f (x) = k +

ub
1 
ci
ub

(3)

i=1

where k denotes the number of covers formed by the groups
determined in x, ub stands for the upper bound determinedby (2), and ci represents the proportion of contribution calculated by
ci =

(1 +



|T(Gi )|s∈Gi |T(s)|) + p(4)in which |T(Gi )| and |T(s)| denote the numbers of targets
covered by group Gi and sensor s, respectively; and penalty
0
Gi forms a coverp=|T| otherwise.
Note that the constant 1 in (4) ensures the decimal fraction
ci ∈ [0, 1), where a larger ci implies better sensor utilization.
The proposed fitness evaluation can accordingly guide the evolutionary search toward maximization of the number of covers
as well as sensor utilization.
IV. E XPERIMENTAL R ESULTS
This paper conducts a series of experiments to evaluate
the performance of the proposed MA (denoted by iMA) in
comparison with state-of-the-art EAs, including integer-coded
GA (iGA), GAMDSC [20], and order-based MA (oMA) [33],on the Set k-Cover problem for WSN lifetime extension.
Additionally, to investigate the effects of the proposed fitness
function and recycling operator, we examine three variants ofinteger-coded GA: iGA1, iGA2, and iGA3. The iGA1 uses
the naive fitness function defined by the number of covers,
whereas iGA2 and iGA3 adopt the proposed fitness functionthat additionally considers the average proportion of contribution (denoted by APoC). The iGA3 further uses the proposedmix crossover and mix mutation operators. Table I summarizes
the parameter setting for the test EAs. Notably, the mutation
rate for the oMA is defined by the parameter of Poissondistributed random generator for the times of swapping thegenes [33]. The mix mutation in iGA3 and iMA consists ofswap and random resetting mutation. The mutation rate forswap mutation is 1.0 and that for random resetting is 1/l,
where l denotes the number of noncritical sensors. The termination criterion is set to 100 000 fitness evaluations for all test
algorithms.
The test instances of the Set k-Cover problem are generated by simulation of WSNs, which randomly distributes
sensors and targets over a 500 × 500 area. Each experimental setting includes 100 instances1 and the test algorithms run
once on each instance. The performance of test algorithms isevaluated according to three measures: the number of covers
obtained, hit rate (HR), and running time. The number of covers obtained serves as the objective of the Set k-Cover problem
and reflects the level of WSN lifetime extension. The experiments use the ub defined in Section III-A as the baseline since
1 The test instances can be downloaded via http://cilab.cs.ccu.edu.tw/
WSNdata.zip.

This article has been accepted for inclusion in a future issue of this journal. Content is final as presented, with the exception of pagination.
6

IEEE TRANSACTIONS ON CYBERNETICSTABLE IS ETTING OF O PERATORS AND PARAMETERS FOR THE I GA S , GAMDSC, O MA, AND I MA

TABLE II
AVG AND HR OF C OVERS O BTAINED F ROM I GA S , GAMDSC, O MA, AND I MA FOR D IFFERENT S ENSING R ANGE r W ITH |S| S ENSORS AND |T|
TARGETS . B OLDFACE I NDICATES THE M OST C OVERS O BTAINED A MONG THE C OMPARING A LGORITHMS

the maximal k is unknown. The HR represents the ratio of thenumber of runs achieving ub covers to that of all runs. The
running time accounts for the average running time to the hits,
which is measured on Intel Xeon E5-2620 machines. The following sections present and discuss the experimental resultswith different sensing range r, number of targets |T|, andnumber of sensors |S|.
A. Experiments With Different Sensing Ranges
The first experiment examines the performance of the
proposed iMA with the five test EAs for different sensing ranges r on two problem scales: one with 90 sensors
and 10 targets; the other with 300 sensors and 500 targets.
Specifically, we look into the influences of iMA’s components,
including the fitness function using the average proportion of
sensor contribution, mix crossover and mix mutation operators,
and the recycling operator.
Table II compares the average number (Avg) of covers andHR obtained from the six EAs; furthermore, Table III presents
the results of t-test with confidence level α = 0.05. The
tables show that iGA2 achieves significantly more covers andhigher HR than iGA1 does on all test cases, validating themerit of the proposed fitness function for the Set k-Coverproblem. The iGA3 surpasses iGA2 in both the number ofcovers obtained and HR on 16 out of 18 cases. These results
show the advantages of mix crossover and mix mutation overuniform crossover and random resetting mutation. Meanwhile,iMA performs better or equally than iGA3 does on the small
cases, and significantly betters on all the large cases. The
superior performance of iMA demonstrates the effectivenessof the recycling operator on squeezing covers out of groups.
Comparing the three MAs, iMA outperforms GAMDSC andoMA on 17 and 9 cases (14 and 5 cases with statisticalsignificance), respectively.
Regarding the HR on the test instances of 90 sensors and 10
targets, iMA, iGA3, and oMA gain the highest HR, GAMDSC
follows with small deficiency, and iGA1 has the lowest HR(see Fig. 6). As the problem scale increases to 300 sensors and
500 targets, the difference of test algorithms in HR becomes
more significant. The iMA can maintain high HR; nonetheless, the others all result in a substantial decrease in HR on thelarge cases. These results show the robustness of iMA and confirm the utility of the proposed fitness function and recycling
operator in performance improvement. In addition, although
GAMDSC and iMA both apply the notion of scattering critical

This article has been accepted for inclusion in a future issue of this journal. Content is final as presented, with the exception of pagination.
LIAO AND TING: NOVEL INTEGER-CODED MA FOR SET k-COVER PROBLEM IN WSNs

Fig. 6.

7

HRs of iGAs, GAMDSC, oMA, and iMA for different sensing ranges with (left) |S| = 90, |T| = 10 and (right) |S| = 300, |T| = 500.

TABLE IIIR ESULTS OF O NE -TAILED PAIRED t-T EST ON THE N UMBERS OF C OVERS O BTAINED F ROM X AND Y A LGORITHMS (D ENOTED BY X V ERSUS Y )FOR D IFFERENT S ENSING R ANGES r W ITH |S| S ENSORS AND |T| TARGETS . S YMBOL “+” I NDICATES T HAT X I S S UPERIOR TO Y .
B OLDFACE S IGNIFIES S TATISTICAL S IGNIFICANCE W ITH C ONFIDENCE L EVEL α = 0.05

TABLE IVRUNNING T IME OF I GA S , GAMDSC, O MA, AND I MA FOR D IFFERENT S ENSING R ANGE r W ITH |S| S ENSORS
AND |T| TARGETS . DASH D ENOTES T HAT THE A LGORITHM FAILS TO ACHIEVE ub C OVERS

sensors, the advanced design of iMA in the variation operators
leads to its significant improvement in the number of covers
obtained and HR.
Table IV lists the running time of the six algorithms fordifferent sensing ranges. The table shows that iMA generally requires much less time than the other five algorithms.

The results also reflect that the local search operators enhancethe efficiency of iMA and oMA, in comparison with GAs.
Comparing the three MAs, the proposed iMA shortens
70.8%–97.5% running time of GAMDSC and 71.2%–94.9%
of oMA on the large cases. Fig. 7 shows the variation of
the number of covers obtained from the six test EAs against

This article has been accepted for inclusion in a future issue of this journal. Content is final as presented, with the exception of pagination.
8

IEEE TRANSACTIONS ON CYBERNETICS

(a)

(b)

(c)

(d)

Fig. 7. Anytime behavior of iGAs, GAMDSC, oMA, and iMA for different sensing range r ∈ {100, 400} with (left) |S| = 90, |T| = 10 and (right) |S| = 300,
|T| = 500. (a) r = 100, |S| = 90, |T| = 10. (b) r = 100, |S| = 300, |T| = 500. (c) r = 400, |S| = 90, |T| = 10. (d) r = 400, |S| = 300, |T| = 500.

Fig. 8.

HRs of iGAs, GAMDSC, oMA, and iMA for different numbers of targets with (left) |S| = 90, r = 250 and (right) |S| = 300, r = 400.

running time for different sensing ranges. The results indicate that iMA converges fastest, oMA follows, then iGA3,
GAMDSC~iGA2, and lastly iGA1. The advantage of iMA inconvergence speed is especially apparent on the large cases.
These outcomes validate the effectiveness of the proposed
representation, fitness function, and recycling operator on

improving evolutionary optimization for the Set k-Coverproblem.
B. Experiments With Different Numbers of Targets
The second experiment evaluates the performance of the test
algorithms for different numbers of targets on two scales ofThis article has been accepted for inclusion in a future issue of this journal. Content is final as presented, with the exception of pagination.
LIAO AND TING: NOVEL INTEGER-CODED MA FOR SET k-COVER PROBLEM IN WSNs

9

TABLE VAVG AND HR OF C OVERS O BTAINED F ROM I GA S , GAMDSC, O MA, AND I MA FOR D IFFERENT N UMBERS OF TARGETS |T| W ITH |S| S ENSORS AND
S ENSING R ANGE r. B OLDFACE I NDICATES THE M OST C OVERS O BTAINED A MONG THE C OMPARING A LGORITHMSTABLE VIR ESULTS OF O NE -TAILED PAIRED t-T EST ON THE N UMBERS OF C OVERS O BTAINED F ROM X AND Y A LGORITHMS (D ENOTED BY X V ERSUS Y ) FOR
D IFFERENT N UMBERS OF TARGETS |T| W ITH |S| S ENSORS AND S ENSING R ANGE r. S YMBOLS + AND “–” I NDICATE T HAT X I S S UPERIOR AND
I NFERIOR TO Y , R ESPECTIVELY. B OLDFACE S IGNIFIES S TATISTICAL S IGNIFICANCE W ITH C ONFIDENCE L EVEL α = 0.05

TABLE VIIRUNNING T IME OF I GA S , GAMDSC, O MA, AND I MA FOR D IFFERENT N UMBERS OF TARGETS |T| W ITH |S| S ENSORS AND
S ENSING R ANGE r. DASH D ENOTES T HAT THE A LGORITHM FAILS TO ACHIEVE ub C OVERS

problem instances: the small one with 90 sensors and sensing
range r = 250; the large one with 300 sensors and sensing
range r = 400. According to Table V, iGA2 obtains morecovers than iGA1 does on 15 out of 18 cases; moreover, iGA3
betters iGA2 on all test cases. These results verify the efficacy of the proposed fitness evaluation as well as crossoverThis article has been accepted for inclusion in a future issue of this journal. Content is final as presented, with the exception of pagination.
10

IEEE TRANSACTIONS ON CYBERNETICS

(a)

(b)

(c)

(d)

Fig. 9. Anytime behavior of iGAs, GAMDSC, oMA, and iMA for different numbers of targets |T| ∈ {10, 500} with (left) |S| = 90, r = 250 and (right)|S| = 300, r = 400. (a) |T| = 10, |S| = 90, r = 250. (b) |T| = 10, |S| = 300, r = 400. (c) |T| = 500, |S| = 90, r = 250. (d) |T| = 500, |S| = 300, r = 400.

and mutation operators. Additionally, iMA obtains ub covers
on all small instances; oMA achieves similar solution quality on the small instances but performs worse than iMA on
the large instances. Table VI further indicates that iGA3 gains
significantly more covers than iGA2 does in both problem
scales. Notably, iMA performs significantly better than all test
EAs on the large instances (|S| = 300, r = 400), validatingthat iMA benefits from the recycling operator in collection ofcovers.
Fig. 8 compares the HRs of the six test algorithms fordifferent numbers of targets. The figure exhibits that iMA andoMA have ≥ 0.99 HRs for all test numbers of targets on
the small instances. However, as the problem scale increases,
the HRs of oMA and GAMDSC deteriorate seriously and areeven lower than that of iGA3, which reveals their sensitivity
to the problem scale. The proposed iMA, on the other hand,
can retain high HRs and increases 16%–77% that of oMA
on the large instances. This outcome shows the robustnessof iMA.
Regarding the computational efficiency, Table VII and Fig. 9
demonstrate that iMA converges faster than the other fiveEAs in both problem scales, which validates the advantagesof the proposed fitness function and recycling operator. The
results of oMA reconfirm its sensitivity to the number of targets: although it requires less time on the small instances,oMA needs much more time than the integer-coded EAs(i.e., iGAs, GAMDSC, and iMA) and converges slower thaniMA and iGA3 on the large instances. Precisely, iMA reduces
59.6%–85.9% running time of oMA. As stated in Section II,
the higher complexity of order-based representation is a potential reason for the inefficiency of oMA in comparison to iMA.
In addition, iGA3 converges faster than iGA2 does, whileiGA2 surpasses iGA1. This outcome reflects the utility of the
proposed variation operators and the contribution-based fitness
evaluation in improving search efficiency for the Set k-Coverproblem.
C. Experiments With Different Numbers of Sensors
Finally, we look into the performance of the test algorithms
for different numbers of sensors. Likewise, the experiment
includes two problem scales: 1) the small one with |T| = 10
targets and sensing range r = 250 and 2) the large one with
|T| = 500 targets and sensing range r = 400. Table VIII

This article has been accepted for inclusion in a future issue of this journal. Content is final as presented, with the exception of pagination.
LIAO AND TING: NOVEL INTEGER-CODED MA FOR SET k-COVER PROBLEM IN WSNs

11

TABLE VIII
AVG AND HR OF C OVERS O BTAINED F ROM I GA S , GAMDSC, O MA, AND I MA FOR D IFFERENT N UMBERS OF TARGETS |S| W ITH |T| TARGETS AND
S ENSING R ANGE r. B OLDFACE I NDICATES THE M OST C OVERS O BTAINED A MONG THE C OMPARING A LGORITHMSTABLE IXR ESULTS OF O NE -TAILED PAIRED t-T EST ON THE N UMBERS OF C OVERS O BTAINED F ROM X AND Y A LGORITHMS (D ENOTED BY X V ERSUS Y ) FOR
D IFFERENT N UMBERS OF S ENSORS |S| W ITH |T| TARGETS AND THE S ENSING R ANGE r. S YMBOLS + AND – I NDICATE T HAT X I S S UPERIOR AND
I NFERIOR TO Y , R ESPECTIVELY. B OLDFACE S IGNIFIES S TATISTICAL S IGNIFICANCE W ITH C ONFIDENCE L EVEL α = 0.05

Fig. 10.

HRs of iGAs, GAMDSC, oMA, and iMA for different numbers of sensors with (left) |T| = 10, r = 250 and (right) |T| = 500, r = 400.

TABLE XRUNNING T IME OF I GA S , GAMDSC, O MA, AND I MA FOR D IFFERENT N UMBERS OF S ENSORS |S| W ITH |T| TARGETS AND S ENSING R ANGE r. DASHD ENOTES T HAT THE A LGORITHM FAILS TO ACHIEVE ub C OVERS

lists the average number of covers obtained and HRs of thecomparing algorithms, and Table IX examines their statisticalsignificance. Moreover, Fig. 10 plots the HRs of the six algorithms for different numbers of sensors. In general, the numberof covers obtained increases while the HR decreases with thegrowing number of sensors. The superior performance of iGA2
to iGA1 verifies the effectiveness of average proportion of
sensor contribution in enhancing fitness evaluation. The iGA3

This article has been accepted for inclusion in a future issue of this journal. Content is final as presented, with the exception of pagination.
12

IEEE TRANSACTIONS ON CYBERNETICS

(a)

(b)

(c)

(d)

Fig. 11. Anytime behavior of iGAs, GAMDSC, oMA, and iMA for different numbers of sensors |S| ∈ {90, 300} with (left) |T| = 10, r = 250 and (right)|T| = 500, r = 400. (a) |S| = 90, |T| = 10, r = 250. (b) |S| = 90, |T| = 500, r = 400. (c) |S| = 300, |T| = 10, r = 250. (d) |S| = 300, |T| = 500, r = 400.

achieves more covers and higher HR than iGA2. These results
show the advantages of the proposed mix crossover and mix
mutation operators. In addition, iGA3 outperforms GAMDSC
on all test cases and does oMA on 6 out of 8 cases. The
proposed iMA further betters iGA3, validating the benefitof the recycling operator. The oMA performs comparably
to iGA3 and iMA on the small instances; nevertheless, its
performance worsens drastically with the increase in the number of sensors. This deterioration reveals the vulnerability ofoMA to the number of sensors. The iMA, by contrast, canmaintain high HR (11%–69% higher than oMA) and large
number of covers against the growing number of sensors on
the large instances. These results indicate the advantages of the
proposed iMA for the Set k-Cover problem in WSN lifetime
extension.
Table X presents the running time of the test algorithms fordifferent numbers of sensors. Increasing the number of sensors
generally results in longer running time. Fig. 11 shows the anytime behavior of the six algorithms for different numbers of
sensors. On the small cases, iMA and oMA obtain faster convergence than the other test algorithms. As the problem scale
increases, iMA still performs best, whereas oMA deteriorates

and converges slower than iGA3 and even GAMDSC. The
results reflect the sensitivity of oMA to the number of sensors:
its required running time increases rapidly with the number of
sensors on the large instances. According to the comparative
results, the iMA holds the highest efficiency among the six
test algorithms in both problem scales; notably, iMA saves
28.6%–65.1% running time of oMA on small test cases and
85.9%–88.7% on large test cases. Comparing the three iGAvariants, iGA3 requires only 50.6% running time of iGA2,
while iGA2 needs merely 53.2% running time of iGA1 on
average. Fig. 11 shows the same preference in convergence
speed: iGA3, iGA2, and then iGA1. The convergence speedof GAMDSC lies between that of iGA2 and iGA3. These
outcomes reconfirm the merits of the proposed fitness function, variation operators, and recycling operator in algorithmic
efficiency for the Set k-Cover problem.
V. C ONCLUSIONThe Set k-Cover problem renders an important formulationfor extending the WSN lifetime with a full coverage of targets. In this paper, we design an effective integer-coded MA

This article has been accepted for inclusion in a future issue of this journal. Content is final as presented, with the exception of pagination.
LIAO AND TING: NOVEL INTEGER-CODED MA FOR SET k-COVER PROBLEM IN WSNs

for the Set k-Cover problem. The proposed MA uses integer
representation to indicate the group number assigned to a sensor; a chromosome therefore represents the arrangement of all
sensors for formation of covers. This paper presents a tighter
upper bound for the integer representation to reduce the search
space. The mix crossover and mix mutation operators are further adapted to the chromosome representation. Moreover, we
design a new fitness evaluation that considers both the numberof covers and the contribution of each sensor to covers. A local
search method, called the recycling operator, is developed toenhance the performance on the Set k-Cover problem.
This paper conducts a series of experiments with different
settings for the sensing range, number of targets, and numberof sensors, to evaluate the proposed MA. The experimental
results show that the integer-coded MA can outperform stateof-the-art EAs, including GAMDSC and order-based MA, in
terms of HR, the number of covers obtained, and running
time. The proposed iMA, on average, increases 38.1% HR
and reduces 78.7% running time of oMA on the 22 large test
instances. These satisfactory results show the advantages ofthe proposed fitness function and the recycling operator in
performance improvement. They also validate the effectiveness and efficiency of the proposed MA on the Set k-Coverproblem in WSNs.
Future work may further consider different aspects of EAs
and the Set k-Cover problem. The problem formulation can beextended to dynamic network environments. Design of effective EAs for the dynamic Set k-Cover problem provides animportant research direction and application to WSN lifetime
extension.
ACKNOWLEDGMENT
The authors would like to thank the editor and reviewers
for their valuable comments and suggestions.
R EFERENCES[1] Z. Abrams, A. Goel, and S. Plotkin, “Set K-cover algorithms for energy
efficient monitoring in wireless sensor networks,” in Proc. 3rd Int. Symp.
Inf. Process. Sensor Netw., Berkeley, CA, USA, 2004, pp. 424–432.
[2] X. Ai, V. Srinivasan, and C.-K. Tham, “DRACo: Distributed, robust
an asynchronous coverage in wireless sensor networks,” in Proc. 4th
Annu. IEEE Commun. Soc. Conf. Sensor Mesh Ad Hoc Commun. Netw.,
San Diego, CA, USA, 2007, pp. 530–539.
[3] I. F. Akyildiz, W. Su, Y. Sankarasubramaniam, and E. Cayirci, “Wirelesssensor networks: A survey,” Comput. Netw., vol. 38, no. 4, pp. 393–422,
2002.
[4] B. Badrinath, J. Scholtz, M. Srivastava, K. Mills, and V. Stanford,
Special Issue on Smart Spaces and Environments (IEEE PersonalCommunications). New York, NY, USA: IEEE Commun. Soc., 2000.
[5] P. Berman, G. Calinescu, C. Shah, and A. Zelikovsky, “Power efficientmonitoring management in sensor networks,” in Proc. Wireless Commun.
Netw. Conf., vol. 4. Atlanta, GA, USA, 2004, pp. 2329–2334.
[6] A. L. Buczak, Y. Jin, H. Darabi, and M. Jafari, “Genetic algorithm
based sensor network optimization for target tracking,” Intell. Eng. Syst.
Through Artif. Neural Netw., vol. 9, pp. 349–354, Dec. 1999.
[7] M. Cardei and D.-Z. Du, “Improving wireless sensor network lifetime through power aware organization,” Wireless Netw., vol. 11, no. 3,
pp. 333–340, 2005.
[8] M. Cardei, M. T. Thai, Y. Li, and W. Wu, “Energy-efficient target coverage in wireless sensor networks,” in Proc. IEEE INFOCOM, Miami,
FL, USA, 2005, pp. 1976–1984.
[9] M. Cardei and J. Wu, “Energy-efficient coverage problems in wireless ad-hoc sensor networks,” Comput. Commun., vol. 29, no. 4,
pp. 413–420, 2006.

13[10] C.-P. Chen et al., “A hybrid memetic framework for coverage optimization in wireless sensor networks,” IEEE Trans. Cybern., vol. 45, no. 10,
pp. 2309–2322, Oct. 2015.
[11] X. Chen, Y.-S. Ong, M.-H. Lim, and K. C. Tan, “A multi-facet survey
on memetic computation,” IEEE Trans. Evol. Comput., vol. 15, no. 5,
pp. 591–607, Oct. 2011.
[12] L. Feng, Y.-S. Ong, M.-H. Lim, and I. W. Tsang, “Memetic search withinterdomain learning: A realization between CVRP and CARP,” IEEE
Trans. Evol. Comput., vol. 19, no. 5, pp. 644–658, Oct. 2015.
[13] A. Gupta, Y.-S. Ong, L. Feng, and K. C. Tan, “Multiobjective multifactorial optimization in evolutionary multitasking,” IEEE Trans. Cybern.,
vol. 47, no. 7, pp. 1652–1665, Jul. 2017.
[14] W. E. Hart, N. Krasnogor, and J. E. Smith, Eds., Recent Advances in
Memetic Algorithms. Heidelberg, Germany: Springer, 2004.
[15] Z. He, B. S. Lee, and X. S. Wang, “Aggregation in sensor networks
with a user-provided quality of service goal,” Inf. Sci., vol. 178, no. 9,
pp. 2128–2149, 2008.
[16] W. R. Heinzelman, A. Chandrakasan, and H. Balakrishnan, “Energyefficient communication protocol for wireless microsensor networks,”
in Proc. 33rd Annu. Hawaii Int. Conf. Syst. Sci., 2000, pp. 1–10.
[17] X.-M. Hu et al., “Hybrid genetic algorithm using a forward encoding
scheme for lifetime maximization of wireless sensor networks,” IEEE
Trans. Evol. Comput., vol. 14, no. 5, pp. 766–781, Oct. 2010.
[18] C. Intanagonwiwat, R. Govindan, and D. Estrin, “Directed diffusion:
A scalable and robust communication paradigm for sensor networks,”
in Proc. 6th Annu. Int. Conf. Mobile Comput. Netw., Boston, MA, USA,
2000, pp. 56–67.
[19] L. Krishnamachari, D. Estrin, and S. Wicker, “The impact of data aggregation in wireless sensor networks,” in Proc. 22nd Int. Conf. Distrib.
Comput. Syst. Workshop, Vienna, Austria, 2002, pp. 575–578.
[20] C.-C. Lai, C.-K. Ting, and R.-S. Ko, “An effective genetic algorithm
to improve wireless sensor network lifetime for large-scale surveillance applications,” in Proc. Congr. Evol. Comput., Singapore, 2007,
pp. 3531–3538.
[21] D. Li, K. D. Wong, Y. H. Hu, and A. M. Sayeed, “Detection, classification, and tracking of targets,” IEEE Signal Process. Mag., vol. 19,
no. 2, pp. 17–29, Mar. 2002.
[22] C.-C. Liao and C.-K. Ting, “Extending wireless sensor network lifetime
through order-based genetic algorithm,” in Proc. IEEE Int. Conf. Syst.
Man Cybern., Singapore, 2008, pp. 1434–1439.
[23] X. Liu, “A deployment strategy for multiple types of requirements
in wireless sensor networks,” IEEE Trans. Cybern., vol. 45, no. 10,
pp. 2364–2376, Oct. 2015.
[24] F. Marcelloni and M. Vecchio, “Enabling energy-efficient and lossyaware data compression in wireless sensor networks by multi-objective
evolutionary optimization,” Inf. Sci., vol. 180, no. 10, pp. 1924–1941,2010.
[25] C. Ok, S. Lee, P. Mitra, and S. Kumara, “Distributed routing in wirelesssensor networks using energy welfare metric,” Inf. Sci., vol. 180, no. 9,
pp. 1656–1670, 2010.
[26] Y.-S. Ong, M. H. Lim, and X. Chen, “Memetic computation—Past,
present & future,” IEEE Comput. Intell. Mag., vol. 5, no. 2, pp. 24–31,
May 2010.
[27] V. Raghunathan, C. Schurgers, S. Park, and M. B. Srivastava, “Energyaware wireless microsensor networks,” IEEE Signal Process., vol. 19,
no. 2, pp. 40–50, Mar. 2002.
[28] P. S. Sausen, M. A. Spohn, and A. Perkusich, “Broadcast routing
in wireless sensor networks with dynamic power management andmulti-coverage backbones,” Inf. Sci., vol. 180, no. 5, pp. 653–663, 2010.
[29] C. Schurgers, V. Tsiatsis, S. Ganeriwal, and M. Srivastava, “Optimizing
sensor networks in the energy-latency-density design space,” IEEE
Trans. Mobile Comput., vol. 90, no. 1, pp. 70–80, Jan./Mar. 2002.
[30] V. A. Shim, K. C. Tan, and H. Tang, “Adaptive memetic computing forevolutionary multiobjective optimization,” IEEE Trans. Cybern., vol. 45,
no. 4, pp. 610–621, Apr. 2015.
[31] S. Slijepcevic and M. Potkonjak, “Power efficient organization of wireless sensor networks,” in Proc. IEEE Int. Conf. Commun., vol. 2.
Helsinki, Finland, 2001, pp. 472–476.
[32] J. A. Stine and G. D. Veciana, “Improving energy efficiency of centrally controlled wireless data networks,” Wireless Netw., vol. 8, no. 6,
pp. 681–700, 2002.
[33] C.-K. Ting and C.-C. Liao, “A memetic algorithm for extending wirelesssensor network lifetime,” Inf. Sci., vol. 180, no. 24, pp. 4818–4833,
2010.
[34] P. K. Varshney, Distributed Detection and Data Fusion. New York, NY,
USA: Springer-Verlag, 1996.

This article has been accepted for inclusion in a future issue of this journal. Content is final as presented, with the exception of pagination.
14

IEEE TRANSACTIONS ON CYBERNETICS[35] Y. Yoon and Y.-H. Kim, “An efficient genetic algorithm for maximum
coverage deployment in wireless sensor networks,” IEEE Trans. Cybern.,
vol. 43, no. 5, pp. 1473–1483, Oct. 2013.
[36] G. Zhang and Y. Li, “A memetic algorithm for global optimization ofmultimodal nonseparable problems,” IEEE Trans. Cybern., vol. 46, no. 6,
pp. 1375–1387, Jun. 2016.
[37] H. Zhang and J. C. Hou, “Maintaining sensing coverage and connectivity
in large sensor networks,” Int. J. Ad Hoc Sensor Wireless Netw., vol. 1,
nos. 1–2, pp. 89–124, 2005.
[38] X. Zhang, Y. Zhou, Q. Zhang, V. C. S. Lee, and M. Li,“Problem specific MOEA/D for barrier coverage with wireless sensors,” IEEE Trans. Cybern., to be published. [Online]. Available:
http://ieeexplore.ieee.org/document/7515224/[39] X.-Y. Zhang et al., “Kuhn–Munkres parallel genetic algorithm for theset cover problem and its application to large-scale wireless sensor
networks,” IEEE Trans. Evol. Comput., vol. 20, no. 5, pp. 695–710,
Oct. 2016.

Chien-Chih Liao received the Ph.D. degree incomputer science and information engineering from
National Chung Cheng University, Chiayi, Taiwan,
in 2016.
His current research interests include evolutionary computation, memetic algorithm, computational
intelligence, and their applications in wireless sensor
networks.

Chuan-Kang Ting (S’01–M’06–SM’13) received
the B.S. degree from National Chiao Tung
University, Hsinchu, Taiwan, in 1994, the M.S.
degree from National Tsing Hua University,
Hsinchu, Taiwan, in 1996, and the Dr. rer. nat.
degree from the University of Paderborn, Paderborn,
Germany, in 2005.
He is currently a Professor with the Departmentof Computer Science and Information Engineering,
National Chung Cheng University, Chiayi, Taiwan.
His current research interests include evolutionary
computation, computational intelligence, machine learning, and their applications in music, art, networks, and bioinformatics.
Dr. Ting is an Associate Editor of the IEEE Computational Intelligence
Magazine and the IEEE T RANSACTIONS ON E MERGING T OPICS INC OMPUTATIONAL I NTELLIGENCE, and an Editorial Board Member ofSoft Computing and Memetic Computing journals. He serves as the IEEE
Computational Intelligence Society (CIS) Newsletter Editor, the Vice Chair ofIntelligent Systems Applications Technical Committee, the Chair of Creative
Intelligence Task Force, and the Vice Chair of Intelligent Network Systems
Task Force, all in IEEE CIS. He is an Executive Board Member of Taiwanese
Association for Artificial Intelligence.