IEEE TRANSACTIONS ON SYSTEMS, MAN, AND CYBERNETICS—PART B: CYBERNETICS, VOL. 39, NO. 4, AUGUST 2009

945

Wireless Heterogeneous Transmitter Placement
Using Multiobjective Variable-Length
Genetic Algorithm
Chuan-Kang Ting, Member, IEEE, Chung-Nan Lee, Hui-Chun Chang, and Jain-Shing Wu

Abstract—The problem of placing wireless transmitters to meetparticular objectives, such as coverage and cost, has proven to
be NP-hard. Furthermore, the heterogeneity of wireless networks
makes the problem more intractable to deal with. This paper
presents a novel multiobjective variable-length genetic algorithm
to solve this problem. One does not need to determine the numberof transmitters beforehand; the proposed algorithm simultaneously searches for the optimal number, types, and positions ofheterogeneous transmitters by considering coverage, cost, capacity, and overlap. The proposed algorithm can achieve the optimal
number of transmitters with coverage exceeding 98% on average for six benchmarks. These preferable experimental results
demonstrate the high capability of the proposed algorithm for thewireless heterogeneous transmitter placement problem.
Index Terms—Multiobjective (MO) optimization, variablelength genetic algorithm, wireless heterogeneous transmitter
placement.

I. I NTRODUCTIONW

ITH THE advent of heterogeneous networks, such as
the integration of Wi-Fi and WiMAX [1]–[3], the infrastructure layout becomes very flexible but thorny. Heterogeneity suggests that many factors must be considered; forexample, Wi-Fi and WiMAX networks have different spectrums, coverage ranges, and base station costs. The wirelesstransmitter (or base station) placement problem is to construct
an optimal infrastructure, that is, to identify the optimal placement of transmitters when considering particular factors suchas coverage, cost, capacity, interference, and handover. These
factors are commonly formulated as objectives, constraints, orboth in the problem model, and are subject to the type of
wireless networks, e.g., datacom or telecom. The problem isknown to be NP-hard.
This paper focuses on datacom networks, specifically, Wi-Fi
and WiMAX networks. The wireless transmitter placement
Manuscript received November 7, 2007; revised March 27, 2008, July 10,
2008, and November 6, 2008. First published April 7, 2009; current version
published July 17, 2009. This work was supported by the National Science
Council of Taiwan under Contract NSC97-2221-E-194-035. This paper wasrecommended by Associate Editor H. Ishibuchi.
C.-K. Ting is with the Department of Computer Science and Information
Engineering, National Chung Cheng University, Chiayi 621, Taiwan (e-mail:ckting@cs.ccu.edu.tw).
C.-N. Lee, H.-C. Chang, and J.-S. Wu are with the Department of Computer
Science and Engineering, National Sun Yat-Sen University, Kaohsiung 80424,
Taiwan (e-mail: cnlee@cse.nsysu.edu.tw; m943040019@student.nsysu.edu.
tw; wujs@cse.nsysu.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/TSMCB.2008.2010951

problem addressed in this paper is to find the optimal placement of transmitters for four objectives: 1) maximum coverage, 2) minimum cost, 3) maximum capacity satisfaction, and4) minimum overlap. To solve this wireless transmitter placement problem, three issues are of paramount importance but
remain open: the number of transmitters, the heterogeneity of
networks, and the multiplicity of objectives.
The first issue is to determine the appropriate number oftransmitters. An intuitive method is to manually assign thisnumber prior to optimizing transmitter placement. Nevertheless, the optimal number of transmitters, i.e., the number oftransmitters that can achieve full coverage at the lowest cost,is unknown and ordinarily difficult to assess. An inappropriate
number of transmitters may cause bad or no results. To prevent
such a situation, the problem of how many transmitters to use
must be solved before dealing with the placement. Several
methods have used an upper bound for the number of transmitters [4]–[7]. However, if additional transmitters are required,
then a poor upper bound will restrict the search space and resultin a local optimum. Some methods have been developed toovercome drawbacks associated with predefining the numberof transmitters or an upper bound. The most successful way is
to regard the adopted number of transmitters as an objective
to be minimized [8]–[10]. Consequently, the number can optimally be determined along with other objectives. This paper
employs this method to determine the optimum number oftransmitters.
The second issue is the heterogeneity of wireless networks.
Hardware technology has improved, and most laptops and mobile computers now start to support different wireless protocols,such as the 802.11 family (Wi-Fi) and 802.16d (WiMAX)[11]. Restated, a receiver can be covered by transmitters thatdiffer in, for example, power radius, cost, and frequency
spectrum. Such heterogeneity in transmitter types makes theplacement problem, which is an NP-hard problem, even more
intractable.
Fig. 1 illustrates a wireless heterogeneous transmitter placement problem. Two transmitter types exist: the large circle
denotes the first transmitter type, which has a large power
radius, such as WiMAX base stations, and the small circle
signifies the second type, which has a small power radius
resembling Wi-Fi access points. The triangle is the area to becovered. Notably, the required number of transmitters of eachtype is unknown, and here, the heterogeneous transmitters in
protocol can correspond to homogeneous transmitters with differing powers. To intuitively solve this problem, one can divide

1083-4419/$25.00 © 2009 IEEE

946

IEEE TRANSACTIONS ON SYSTEMS, MAN, AND CYBERNETICS—PART B: CYBERNETICS, VOL. 39, NO. 4, AUGUST 2009

II. R ELATED W ORK

Fig. 1.

(a) Two-stage placement. (b) Counterexample of two-stage placement.

the planning into multiple stages. The first stage plans theplacement of transmitters with large power, and the second
stage plans that for small transmitters [Fig. 1(a)]. The primarydrawback of this method is that the resultant placement may
not be optimal. For instance, given that the big transmitters cost$120 and the small ones cost $10, using only small transmitters[Fig. 1(b)] is better than mixed transmitters [Fig. 1(a)] in termsof cost. A method that simultaneously considers the number
and positions of transmitters can overcome this drawback andis relatively more likely to obtain optimal solutions.
The third issue in wireless transmitter placement is themultiplicity of objectives that must be considered for placement optimization. Many existing methods for the placement
problem use single-objective (SO) optimization. Wireless transmitter placement, however, frequently considers more than one
objective. For instance, one may seek maximal coverage withthe minimal number of transmitters. SO schemes solve thisproblem by combining all the objectives into a weighted objective. Although a possibility exists that SO methods can solve themultiobjective (MO) optimization problem, the performanceof SO methods is typically sensitive to the weights, and,even worse, determining appropriate weights is itself anotheroptimization problem. MO methods, on the other hand, do
not weight each objective. Instead, they provide a bunch ofsolutions for each objective on demand. For example, an MO
method gives two solutions: one for 98% coverage with fourtransmitters and another for 88% coverage with three transmitters. A company may choose the second solution based on its
budget, rather than the solution with the higher coverage rate.
In consideration of these three issues, this paper presents
a novel multiobjective variable-length genetic algorithm tosolve the wireless heterogeneous transmitter placement problem. This algorithm integrates a variable-length scheme, an MO
genetic algorithm, and a new crossover approach to solve thewireless heterogeneous transmitter placement problem without
predetermining the number of transmitters or its upper bound.
The rest of this paper is organized as follows. Section II
recapitulates related work. Section III gives the definitionof the wireless heterogeneous transmitter placement problem.
Section IV sheds light on the proposed MO variable-length
genetic algorithm. Simulation and results are presented in
Section V. Finally, conclusions are drawn in Section VI.

The infrastructure setup for placement can be categorized
into the base station placement problem and the antenna placement problem. The former is concerned with the placement ofbase stations, whereas the latter is concerned with the allocationof antennas to certain candidate base stations. The wirelesstransmitter placement problem addressed in this paper is a basestation problem. Both the base station placement problem andthe antenna placement problem are known to be NP-hard; thatis, under the assumption P = N P , no exact algorithm existsthat can solve this problem in polynomial time.
Some heuristic methods have been developed for solving thebase station placement problem. Unbehaun and Kamenetsky[12] selected a set of candidate wireless local area network(WLAN) access points using the pruning method and refinedthese access points via neighborhood search and simulated annealing. Lee and Kang [13] utilized tabu search to increase thecapacity of code-division multiple access (CDMA). In focusing
on the universal mobile telecommunications system (UMTS)
uplink, Amaldi et al. [14] developed a randomized greedy
method with tabu search to avoid local optima for WLAN
coverage planning. In addition, several approaches based on
evolutionary computation have shown their power in effectively
tackling the transmitter placement problem. Weicker et al.
[15] proposed the steady-state evolutionary algorithm with
Pareto tournaments (stEAPT), which considers frequency assignment and channel interference for base station placement.
Zhang et al. [7] designed an MO particle swarm optimizationon coverage and cost objectives. Park et al. [5], [6] applied agenetic algorithm to optimize the total number of transmittersand their positions. Experimental results show the utility of thegenetic algorithm on the base station placement problem.
The antenna placement problem is to assign antennas to certain sites selected from a set of predefined candidate sites anddetermine the parameters of antennas for particular objectives
and constraints. Reininger and Caminada [16] formulated theantenna placement problem for cellular networks. Their modelhas three objectives—minimum cost, maximum traffic capacity,and minimal overlapping criteria—and three constraints—link
budget, handover, and connectivity. To address this problem,
Vasquez and Hao [17] proposed a three-stage heuristic approach. The preprocess filters out poor solutions, the tabu
search optimizes the configuration, and the postprocess improves the results through tabu search. The simulation results
for urban and highway networks demonstrated the capability of
the heuristic approach. Hurley [18] considered traffic, handover,and transmitter, and proposed an algorithm based on simulated
annealing. Zimmermann et al. [19] integrated multiple objectives using scalarization; that is, they combined three objectives
into one weighted objective. The (1 + 1) evolution strategy(ES) has been adopted to solve the constrained SO optimization
problem. Beyond scalarization, Raisanen and Whitaker [20]addressed the problem using several prominent MO optimization algorithms, including simple evolutionary algorithm for
multiobjective optimization (SEAMO), strength Pareto evolutionary algorithm 2 (SPEA2), non-dominated sorting genetic
algorithm II (NSGA II), and Pareto envelope-based selection

TING et al.: WIRELESS TRANSMITTER PLACEMENT USING MO VARIABLE-LENGTH GENETIC ALGORITHM

algorithm (PESA). They concluded that NSGA II [21] canachieve the best performance. Raisanen [10] further employeda permutation-coded representation for the problem concerning
the objectives of service coverage, cost, traffic capacity, handover, and interference. The experimental results for three realistic simulated environments showed that NSGA II, using the
permutation-coded strategy, outperforms that using common
binary-coded representation or integer-based representation.
As for the problems that have a changeable number ofvariables for a solution, a common way to address it is tolimit the number with a known upper bound, and then theclassic fixed-length representation is applicable. For example,
Ripon et al. [22] observed the transposon phenomenon [23]and proposed the jumping-gene genetic algorithm (JGGA).
Chan et al. [24] used additional control genes in JGGA todetermine the employment of certain transmitters and received
preferable results for optimizing factory WLAN network. However, this manner requires a predefined and assumed upperbound for the length of chromosome. To eliminate this requirement, some variable-length genetic algorithms [25]–[27]have been proposed. Recently, Ripon et al. [28] have devised
MO evolutionary clustering using a variable-length real-coded
JGGA to solve a clustering problem without knowing the number of clusters. In this paper, we propose a new variable-length
MO genetic algorithm based on variable-length representation
with uniform and one-point crossover.
III. P ROBLEM S TATEMENT
This section defines the wireless heterogeneous transmitter placement problem. Note that this paper focuses on theplacement of transmitters for Wi-Fi and WiMAX networks.
First, Section III-A formulates the planning model for the map,transmitters, and receivers based on the model of Park et al.
[5], [6]. Section III-B introduces the propagation model. The
objectives are given in Section III-C, and a formal definition of
the problem is presented in Section III-D.
A. Planning Model
The planning model describes the environment of the wireless transmitter placement problem.
1) Map: The map for transmitter placement has two regions: covered regions and placement regions. The former,
which is denoted by CG, represents regions that must becovered (e.g., roads and buildings). The latter, i.e., placement
regions P G, are regions where transmitters can be placed whenconstructing the wireless network. Notably, both covered andplacement regions are predefined and can differ. A common
method of dealing with these regions is to divide them into
several grids with a resolution δ; consequently, for a 2-D map,CG ⊆ Z2 , and P G ⊆ Z2 .
2) Receiver: A receiver gains wireless signals from transmitters. Wireless connectivity is assessed by a signal thresholdθ and a data rate demand σ to maintain quality of service. This
paper uses a large set R of receivers as test points for coverage:a receiver r ∈ R has a position (xr , yr ) ∈ CG with thresholdθr ∈ R∗ and demand σr ∈ R∗ .

947

3) Transmitter: The transmitters are characterized by various parameters. The proposed model takes power, cost, andcapacity into account; the transmitter type can, therefore, be
represented by a three-tuple τ = (p, c, s), where p ∈ R+ denotes the power, c ∈ R+ denotes the cost of transmitters, ands ∈ R+ denotes the capacity (bandwidth) provided by the transmitter. Let T P be the set of candidate transmitter types to beplaced, and let |T P | be the cardinality of T P . For |T P | = 1,
only one transmitter type exists, and the planning network
is homogeneous. For |T P | > 1, it turns out to be a wirelessheterogeneous transmitter network.
The transmitter placement problem is to create a set oftransmitters T = {t = (φt , τt )|φt ∈ P G, τt ∈ T P } and place
its elements, namely, transmitters, based on objectives such as
coverage and cost. A formal definition of the problem is given
in Section III-D.
B. Propagation Model
The signal strength Sr,t from a transmitter t ∈ T to a receiverr ∈ R can be evaluated using propagation models. This paper
adopts the free space propagation model, which is widely usedin the studies of placement problem [11]. The signal strength in
the free space propagation model is computed by
Sr,t =

pt Gr Gt λ2(4π)2 d2r,t(1)

where pt is the power of t, Gr and Gt are the antenna gains
of receiver r and transmitter t, respectively, λ is the carrier
wavelength, and dr,t is the Euclidean distance from r to t.
Moreover, the path loss due to obstructions is computed
using the following formula [24], [29]:
Lr,t = 20 log

4πdr,t
λ


+

M


Ni Li

(2)

i=1

where M denotes the number of obstruction types, Ni is thenumber of obstructions of type i, and Li is the penetration loss
for an obstruction of type i.
C. Objectives
Many factors affect wireless network planning. This paper
focuses on coverage, cost, capacity, and overlap, where coverage and overlap are concerned with the placement of transmitters, cost is associated with the type and number of transmitters,
and capacity is subject to the transmitter type.
1) Coverage: A receiver r is said to be covered by a transmitter t when the signal strength is greater than the threshold;formally
covered(r) =1,0,∃t ∈ T, Sr,t > θrotherwise(3)

where the value 1 indicates that the receiver r is covered byat least one transmitter. Accordingly, the coverage of a set of948

IEEE TRANSACTIONS ON SYSTEMS, MAN, AND CYBERNETICS—PART B: CYBERNETICS, VOL. 39, NO. 4, AUGUST 2009transmitters can be calculated by1 
covered(r).
|R|coverage(T ) =

(4)

r∈R

Note that the objective is to maximize coverage.
2) Cost: Another objective is to minimize cost in placing
the set of transmitters T . Here, cost is evaluated by summingthe individual costs of all transmitters, i.e.,
cost(T ) =
ct
(5)
t∈T

where ct denotes the cost of transmitter t with type τt =(pt , ct , st ) ∈ T P .
3) Capacity: This paper adopts the notion of data rate to assess the network capacity [30]. An ideal network design should
provide sufficient bandwidth (data rate) for users; both oversupply and shortage of bandwidth are not satisfactory. Thus,
the objective regarding capacity is formulated to minimize theabsolute difference between the transmitter bandwidth and thesum of the data rate demands of its covered receivers, i.e.,








(6)
σr 
Δcapacity(T ) =
st −

t∈T 
r∈R:Sr,t >θrwhere st is the data rate provided by transmitter t of type τt =(pt , ct , st ) ∈ T P , and σr is the data rate demand of receiver r.
4) Overlap: The coverage overlap between transmittersraises the issue of interference [15], [31]. To reduce the interference, we use an additional objective to minimize the overlap.
The objective function counts the number of receivers coveredby more than one transmitter asoverlapped(r)(7)
overlap(T ) =r∈R

Fig. 2.

Representation of chromosome and substring.

IV. P ROPOSED A LGORITHM
Three issues should be taken into account when solving
the wireless heterogeneous transmitter placement problem: thenumber of transmitters must be flexible, the transmitter infrastructure can be heterogeneous, and the problem solver must
consider multiple objectives.
To address these issues, this paper presents a novel variablelength representation and variation operators and integrates
them into an MO genetic algorithm based on NSGA II. The
algorithm NSGA II [21] is known for its effectiveness in dealing
with MO problems; in particular, Raisanen and Whitaker [20]validated that NSGA II performs best in comparison withSEAMO, SPEA2, and PESA on the antenna placement problem. This paper accordingly adopts NSGA II as the scheme
for MO optimization. Additionally, the proposed representationand crossover facilitate varying chromosome length and information, i.e., the number, positions, and types of transmitters.
Consequently, the proposed algorithm can automatically search
for the appropriate number of transmitters and optimize thepositions and types of transmitters for maximum coverage,
minimum cost, maximum capacity satisfaction, and minimum
overlap.
A. Representation

where the active set AS(r) represents the set of transmitters bywhich receiver r is covered.

The candidate solution, viz., a set of transmitters T , isencoded into a chromosome. Each transmitter t ∈ T is represented as a substring that consists of the position φt = (xt , yt )and its type τt . Fig. 2 presents a chromosome with n substrings,
each of which is composed of 22 bits indicating the position(2 × 10 bits) and type (2 bits). Although the substring lengthis fixed, the chromosome length is variable since the number ofsubstrings is variable.

D. Problem

B. Initialization

The wireless transmitter placement problem in this paper isformally defined as an MO minimization problem

The proposed initialization procedure introduces a temporary upper bound U B ∈ N, which is randomly generated, toinitialize the number of substrings for a particular transmittertype. For instance, suppose two transmitter types exist T P ={τ1 , τ2 }, and their respective U Bs are 2 and 3. When initializing a chromosome, the number of substrings (transmitters) for acertain type is randomly picked from {0, 1, . . . , U B}, e.g., {0,1, 2} for the first type τ1 . The corresponding position (xt , yt )of the transmitter is randomly generated afterward. Notably,
the temporary upper bound U B is used only at population
initialization. Section V-A shows that the performance of the
proposed algorithm is insensitive to U B.

with

overlapped(r) =1,
0,|AS(r)| > 1
otherwise

min(f1 , f2 , f3 , f4 )f1 = 1 − coverage(T )f2 = cost(T )f3 = Δcapacity(T )f4 = overlap(T ).

(8)

(9a)
(9b)
(9c)
(9d)
(9e)

To minimize the four objectives, (9b) transforms the objective
for maximum coverage into that for the minimum percentage
of areas that are not covered, namely, 1 − coverage(T ).

TING et al.: WIRELESS TRANSMITTER PLACEMENT USING MO VARIABLE-LENGTH GENETIC ALGORITHM

949

Fig. 4. Example of uniform crossover for substrings.

Fig. 3.

Hybrid crossover.

Fig. 5. Scheme of mapping substrings for applying the uniform crossover for
substrings.

C. Fitness Evaluation
The wireless transmitter placement problem is formulated asan MO problem that considers coverage, cost, capacity, andoverlap of transmitter placement in this paper. For multiple
objectives, this paper adopts the notion of dominance for fitness
evaluation. An individual a is said to dominate individual b if
a is better than b in one objective and not worse than b in all
the other objectives. In this case, a is assigned a superior rank.
If neither a nor b is dominant, the two individuals are said tonondominate each other and are given the same rank.
The proposed MO method is based on NSGA II [21].
Specifically, the proposed algorithm determines whether a chromosome survives or dies according to its rank and crowding
distance. In the wireless transmitter placement problem, rank
and crowding distance depend on a comparison of the four
objectives.
D. Selection
Several methods have been developed for selecting parents ingenetic algorithm (GA) [32]. Uniform selection picks chromosomes from the population with equal probability. In roulette
wheel selection, the probability that a chromosome will beselected is proportional to its fitness. The tournament selection
with tournament size k randomly picks k chromosomes tocompete. The winner, i.e., the fittest picked chromosome, isreserved for crossover. This paper uses binary (k = 2) tournament selection in the experiments for its accepted good
performance [33].
E. CrossoverThis paper devises a hybrid crossover method for the
crossover of chromosomes and substrings. Let Pc be thecrossover rate. The hybrid crossover has three ways of producing offspring (Fig. 3).
1) Perform only uniform crossover for substrings with aprobability Pc × Pc .
2) Perform only one-point crossover for chromosomes witha probability 1 − Pc .

Fig. 6. Example of one-point crossover for chromosomes.

3) Perform both uniform crossover for substrings and onepoint crossover for chromosomes with a probability Pc ×
(1 − Pc ).
More precisely, a pair of parents has a probability Pc to only
exchange the bits inside one substring, a probability 1 − Pc to
exchange several substrings without modifying the bits in each
substring, and a probability Pc × (1 − Pc ) to exchange bothbits and substrings. More details about the operation of thesecrossovers are given below.
1) Uniform Crossover for Substrings: The uniform crossover for substrings follows the operation of uniform crossover
but limits the scope of the crossover to a substring rather than
the whole chromosome. Fig. 4 presents an example of thecrossover, where the bits of offspring are equiprobably inheritedfrom parent 1 or parent 2. Notably, the crossover changes
transmitter position and type.
A special scheme is developed to perform uniform crossoveron chromosomes of different lengths. Fig. 5 illustrates this procedure. First, the lengths of both chromosomes are compared.
In the example, parent 1 has four substrings, whereas parent 2
has five substrings. To deal with the unequal chromosome
lengths, the shorter chromosome (parent 1) randomly maps its
substrings to the longer chromosome (parent 2). The uniform
crossover for substrings can then be performed on the four pairsof mapped substrings for parents 1 and 2.
2) One-Point Crossover for Chromosomes: Anothercrossover to apply is the one-point crossover for chromosomes.
First, a chromosome is divided into two parts at a random
point between substrings. Second, the two parts are exchanged
with each other. Fig. 6 shows parent 1 exchanging its part

950

IEEE TRANSACTIONS ON SYSTEMS, MAN, AND CYBERNETICS—PART B: CYBERNETICS, VOL. 39, NO. 4, AUGUST 2009

TABLE IPARAMETERS OF THE PROPOSED GA IN THE EXPERIMENTS

Fig. 7.

Map of benchmark 1.

TABLE IIRESULTS OF A NONDOMINATED FRONT FROM 30 TRIALS OF THE
PROPOSED ALGORITHM ON BENCHMARK 1 (FREQ: FREQUENCY,
AVG: AVERAGE, STD: STANDARD DEVIATION,
MIN: MINIMUM, MAX: MAXIMUM)

with parent 2. This strategy allows chromosomes to alter theirlengths.
F. Mutation
All mutation operators for binary-coded GAs are applicable to the proposed algorithm. This paper adopts the bit-flip
mutation with a mutation rate Pm = (1/substring_length);
therefore, each bit has a probability of Pm to be flipped.
V. S IMULATIONS AND R ESULTS
A series of simulations is conducted to evaluate the performance of the proposed algorithm. As mentioned, three issues
must be resolved: 1) predetermining the number of transmitters or an upper bound is not needed, 2) the transmittersfor placement can be homogeneous or heterogeneous, and3) optimization simultaneously considers coverage, cost, capacity, and overlap.
Six benchmarks are designed for the simulations. Benchmarks 1–5 consider the objectives of coverage and cost, andbenchmark 6 additionally takes capacity and overlap into account. The maps in benchmarks 1–4 are defined to have no
obstacles; thus, the free space propagation model is used tomeasure the signal strength. Benchmarks 5 and 6 include obstructions, and the path loss due to obstructions is additionallyconsidered. The grid resolution δ of the map is 0.1 m for benchmarks 1–4, 3 m for benchmark 5, and 1.76 m for benchmark 6.
All the transmitters are assumed to be omnidirectional. The
gains of transmitters Gt and receivers Gr are set to 1, andwavelength λ is 0.125 m. The threshold θr for all receivers is 0.
Table I lists the parameters for the proposed algorithm.
A. Benchmark 1
Fig. 7 presents benchmark 1. In a 102.3 × 102.3 m2 square,
only one transmitter type exists and has a power radius of 37 m.
In this benchmark, the optimal number of homogeneous transmitters is 4; Fig. 7 shows their optimal positions.
The proposed algorithm yields a series of nondominated results called nondominated front (or Pareto front). The nondominated fronts vary among the 30 trials. Hence, the frequency

Fig. 8. Results of a nondominated front on benchmark 1. The circles depict
the obtained nondominated solutions from a certain trial, and the green line
depicts the average coverage for the respective cost.

with which a certain cost occurs in the nondominated front
and the statistics (average, standard deviation, minimum, andmaximum) for the coverage associated with cost are considered.
Table II summarizes the results of nondominated fronts onbenchmark 1, where cost is determined by the number oftransmitters (#BS). Fig. 8 depicts the nondominated solutions
obtained from 30 trials using the proposed algorithm and theiraverages with respect to each cost. Computational results indicate that the proposed algorithm always finds the optimal number of transmitters in the 30 trials. For the optimum #BS = 4,
the average coverage is 99.40%, and the best coverage is 100%,
which is very satisfactory.
Another contribution of the proposed method is that no needexists to preassign the number of transmitters or its upperbound. Although population initialization introduces parameter
U B, the computational results in Table III demonstrate that

TING et al.: WIRELESS TRANSMITTER PLACEMENT USING MO VARIABLE-LENGTH GENETIC ALGORITHM

951

TABLE IIIAVERAGE COVERAGE (%) OVER 30 TRIALS FORU B = 3, 10, 50, 100, AND 1000

Fig. 10. Results of a nondominated front on benchmark 2. The circles depict
the obtained nondominated solutions from a certain trial, and the green line
depicts the average coverage for the respective cost.

Fig. 9.

Map of benchmark 2.

TABLE IVRESULTS OF A NONDOMINATED FRONT FROM 30 TRIALS OF THE
PROPOSED ALGORITHM ON BENCHMARK 2

Fig. 11. Map of benchmark 3.

yields the optimal number of transmitters in 29 out of 30 trials,
demonstrating its capability in finding the optimal number oftransmitters. These simulation results further demonstrate thescalability of the proposed algorithm.
C. Benchmark 3

the performance of the proposed algorithm is not sensitive toa U B: The difference in performance between different U Bvalues (3–1000) is insignificant—the proposed algorithm canalways achieve coverage exceeding 99% with four transmitters,
regardless of the U B adopted.
B. Benchmark 2
Benchmark 2 uses the map of benchmark 1 but decreases
the transmitter power for more transmitters, which renders
benchmark 2 more difficult for placement optimization thanbenchmark 1. Fig. 9 shows that the power radius is reduced to
19 m; the other problem settings are the same as benchmark 1.
The optimum is 100% coverage with 16 transmitters.
Table IV and Fig. 10 present the simulation results of anondominated front in terms of coverage and cost. Generally,
coverage increases as cost increases, i.e., the number of transmitters adopted increases. With the optimal number of transmitters at 16, the proposed algorithm achieves 98.57% coverage on
average and 99.07% at best. Moreover, the proposed algorithm

Benchmark 3 has a more complex geography than benchmarks 1 and 2 and is similar to the benchmark adopted byPark et al. [5], [6]. The placement regions P G are spreadover the entire square (102.3 × 102.3 m2 ), whereas the covered
regions CG are seven identical hexagons with side lengths of
19 m inside the square (Fig. 11). The power radius of eachtransmitter is 19 m. Transmitters are of only one type with acost of 1; that is, they are homogeneous. The optimal solution
is 100% coverage with seven transmitters located at the centersof seven hexagons.
Table V and Fig. 12 show the simulation results of a nondominated front after 5000 generations. The proposed algorithm
achieves 99.05% coverage on average and 99.91% at bestwith seven transmitters, which is a near-optimal solution. Of
the 30 trials, the optimal number of transmitters is coveredin the nondominated front 29 times, whereas the others arecovered only five or nine times. This shows that the proposed
algorithm finds the optimal number of transmitters effectively
and robustly.
Compared with the approach of Park et al. [5], [6], the proposed algorithm overcomes the difficulty of tuning the weight
wt in the fitness function and the maximal number of transmitters K. Moreover, it produces a set of nondominated solutions

952

IEEE TRANSACTIONS ON SYSTEMS, MAN, AND CYBERNETICS—PART B: CYBERNETICS, VOL. 39, NO. 4, AUGUST 2009

TABLE VRESULTS OF A NONDOMINATED FRONT FROM 30 TRIALS OF THE
PROPOSED ALGORITHM ON BENCHMARK 3

Fig. 12. Results of a nondominated front on benchmark 3. The circles depict
the obtained nondominated solutions from a certain trial, and the green line
depicts the average coverage for the respective cost.

TABLE VIRESULTS OF A NONDOMINATED FRONT FROM 30 TRIALS OF THE
PROPOSED ALGORITHM ON BENCHMARK 4

Fig. 14. Best result of transmitter placement for the proposed algorithm(99.90% coverage with cost 12) on benchmark 4, where green marks covered
regions and red marks uncovered ones.

Fig. 13. Map of benchmark 4.

for combinations of coverage and cost rather than merging thetwo objectives into one via weighting. Hence, the proposed
algorithm provides designers with increased flexibility whenchoosing placement. In terms of solution quality, this approachand that by Park et al. [5], [6] achieve coverage exceeding 99%.
In summary, the proposed algorithm is flexible and capable ofnear-optimal solutions.

Fig. 15. Results of a nondominated front on benchmark 4. The circles depict
the obtained nondominated solutions from a certain trial, and the green line
depicts the average coverage for the respective cost.

D. Benchmark 4
Benchmark 4 is a wireless heterogeneous transmitter placement problem. The benchmark has two transmitter types forplacement. The first transmitter type has a power radius of
26.5 m and cost of 4. The second type has a power radius of
13.3 m and cost of 1. The map consists of a 102.3 × 102.3 m2

square for placement regions and six hexagons for coverage regions, where the two large hexagons have side lengths of 26.5 m
and the four small ones have side lengths of 13.3 m. Fig. 13
presents the optimal solution: 100% coverage with cost of 12(two transmitters of the first type and four transmitters of the

TING et al.: WIRELESS TRANSMITTER PLACEMENT USING MO VARIABLE-LENGTH GENETIC ALGORITHM

953

Fig. 16. Factory layout for benchmark 5 [24].

second type). The optimal positions for all the transmitters areat the hexagon centers.
In terms of chromosome representation, a substring has
21 bits owing to an additional bit for the transmitter type. The
simulation results for cost and coverage (Table VI) demonstrate that the proposed algorithm achieves 98.21% coverageon average and 99.90% at best, corresponding to the optimal
combination of transmitters (four of the first type and two of
the second type). Fig. 14 shows the placement of transmittersfor 99.90% coverage. These favorable outcomes verify that the
proposed algorithm can effectively tackle the heterogeneoustransmitter placement problem.
Fig. 15 depicts the nondominated solutions of the 30 trials
using the proposed algorithm and their averages with respect
to each cost. The irregular profile1 reveals that high costs(e.g., costs of 13 and 14) do not necessarily achieve highcoverage. This irregularity, arising from the heterogeneity oftransmitters, complicates the combination of transmitters andmakes the placement optimization very difficult. Experimental
results show that the proposed algorithm effectively overcomes
this difficulty and obtains near-optimal solutions.

TABLE VIIRESULTS OF A NONDOMINATED FRONT FROM 30 TRIALS OF THE
PROPOSED ALGORITHM ON BENCHMARK 5

tendency that coverage increases as the adopted transmitter
number increases. With six transmitters, the proposed algorithm always achieves 100% coverage out of the 30 trials.
Fig. 17 shows that the resultant placement of the six transmitters is very adequate. These outcomes confirm the effectiveness of the proposed algorithm on this realistic placement
problem.
F. Benchmark 6

E. Benchmark 5
Benchmark 5 is an indoor wireless transmitter placement
problem based on the factory WLAN optimization problem[24]. The map contains obstructions with different penetration loss: thin partition, cement, and thickened cement wall(Fig. 16). The parameters and the path loss of these obstructions
in our simulation follow those used in [24]. The transmitters
are homogeneous, and all have a power radius of 20 m in the
2.4-GHz band.
Table VII summarizes the simulation results of a nondominated front after 5000 generations. The results show the general
1 Some actual “dominated” solutions appear in Fig. 15 since the placementwith cost 13, for example, may result in higher coverage than that with cost 12
and then become nondominated in some trials.

Benchmark 6 is an outdoor wireless heterogeneous transmitter placement problem. The map of benchmark 6 is a realmap (Fig. 18) sampled from Google Earth for a 1.8 × 1.5 km2
division of the Kaohsiung city in Taiwan. The map includes
a natural barrier (the Shou Mountain) and an artificial barrier(the Kaohsiung harbor). Transmitters cannot be placed in theregions of the mountain and harbor. In addition, the mountainhas an altitude of 58 m, and no signal can penetrate themountain; on the other hand, the harbor allows signals to passthrough the region. There are three classes of data rate demands
among a total of 3057 receivers: 2478 receivers of 16 kb/s,
420 receivers of 128 kb/s, and 159 receivers of 1024 kb/s.
Simulating Wi-Fi and WiMAX networks, the benchmark has
two transmitter types for placement. The first transmitter typehas a power radius of 1500 m, a cost of 40 000, and a capability

954IEEE TRANSACTIONS ON SYSTEMS, MAN, AND CYBERNETICS—PART B: CYBERNETICS, VOL. 39, NO. 4, AUGUST 2009

Fig. 17. Resultant placement of six wireless transmitters from the proposed algorithm for benchmark 5. The color symbols denote the coverage range of therespective transmitters.

Fig. 19. Results on benchmark 6 in terms of coverage, cost, and capacity
objectives. The blue circles denote the nondominated solutions, and the redpoints represent their projection onto 2-D plane.
Fig. 18. Map of benchmark 6. The color points mark the receivers in different
data rate demands (blue: 16 kb/s, green: 128 kb/s, red: 1024 kb/s).

of 75 Mb/s. The second transmitter type has a power radius of
100 m, a cost of 2200, and a capability of 54 Mb/s.
Due to computation complexity, this paper conducts only one
trial of the proposed algorithm using a population size of 500
with 2000 generations on benchmark 6. The simulation resultsin Figs. 19 and 20 demonstrate that the proposed algorithm
can generate diverse solutions regarding the four objectives.
Moreover, the results reveal the tradeoffs between coverageand the other three objectives (cost, capacity difference, andoverlap increase with coverage). The other relationships, e.g.,
capacity versus overlap, are inconclusive. Fig. 21 plots the
distribution and coverage of the solution that achieves 98.69%
coverage using 12 first-type and two second-type transmitters.
The figure verifies that the proposed algorithm considers theobstruction of signal transmission and the restriction for placement. It also validates that the resultant placement for thetransmitters is very satisfactory for coverage, cost, capacity, andoverlap.

Fig. 20. Results on benchmark 6 in terms of coverage, capacity, and overlap
objectives. The blue circles denote the nondominated solutions, and the redpoints represent their projection onto 2-D plane.

G. Comparison With SO GA
This paper performed experiments to compare the performance of the SO and MO methods using both the proposed

TING et al.: WIRELESS TRANSMITTER PLACEMENT USING MO VARIABLE-LENGTH GENETIC ALGORITHM

Fig. 21. Resultant placement of wireless transmitters from the proposed
algorithm for benchmark 6. The color symbols denote the coverage range ofthe respective transmitters.

representation and the hybrid crossover. The elements of
NSGA II—dominance ranking and crowding distance—are
replaced with a weighted sum fitness function. The fitness
functions for SO are the following:• for benchmarks 1–4
f  (T ) = f1 + α · f2
= 1 − coverage(T ) + α · cost(T )(10a)• for benchmark 6f  (T ) =

4


αi fi

(10b)

i=1

where α and αi are the objective weights.
Table VIII(a)–(d) compares the nondominated front for the
SO and MO methods on benchmarks 1–4. Since the MO
method yields multiple results with different numbers of transmitters and the SO method produces only one result, forfairness, this paper compares the coverage of the MO method
corresponding to the number of transmitters that is nearest theresultant number of the SO method. Experimental results indicate that the SO method achieves the optimal number of transmitters with coverage > 95%, which depends upon the settingof α. This result reveals that a serious drawback exists whenusing SO methods for MO problems: performance is sensitive
to the weight α, and identifying a suitable weight value requires
an exhaustive effort. The MO method, conversely, overcomes
this shortcoming by rendering a set of nondominated solutions
for different combinations of coverage and cost. Furthermore,
the MO method with comparable number of transmitters outperforms the SO method in terms of coverage in most test cases.
In some cases, the coverage achieved by the MO method isless than that attained by the SO method. Such inferiority ispartly due to the undervaluation of the compared number oftransmitters for the MO method. For example, the SO method
in benchmark 3 with α = 0.06 has an average coverage of
92.40%, which is higher than the coverage of 89.08% achieved955

by the MO method using undervalued six transmitters, but
lower than the coverage of 99.05% obtained using overvalued
seven transmitters.
Moreover, we compare the performance for the SO and MO
methods on benchmark 6, which is a four-objective optimization problem. For the SO fitness function, the values of the four
objective functions are normalized to [0, 1]; in addition, thispaper applies the Taguchi method [34] with four levels, i.e.,
0.25, 0.5, 0.75, and 1.0 for each objective weight. Consequently,
the experiment for the SO method includes 16 combinations ofweights that follow Taguchi L16 orthogonal array. Table VIII(e)presents the results with respect to the 16 settings for four
objective weights. To compare the MO results with the SO
ones, we adopt the best fitness values of the nondominatedsolutions obtained from the MO method. The experimental
results show that there is no clear winner between the SO andMO methods on all the 16 combinations of weights. The MO
method achieves better fitness than the SO method does on six
out of eight combinations as α1 ≤ 0.50, but worse on all eightcombinations as α1 > 0.50. Fig. 22 depicts the nondominatedfront obtained from the MO method and the 16 solutions
obtained from the SO method. The figure demonstrates that
the SO method can lead to closer proximity to the true Paretooptimal set than the MO method does. This outcome confirms
that, as the number of objectives increases, the effectiveness of
Pareto-ranking methods, like NSGA II, deteriorates due to theaugmented likelihood of nondominance [35]–[37]. Although
the SO method can keep the search ability for proximity, thelimited range of results and the difficulty in choosing weights
greatly detract from its utility.
In general, both SO and MO methods using the proposed hybrid crossover effectively deal with the wireless heterogeneoustransmitter placement problem. Additionally, the MO method
has the advantages of obtaining better results on two-objective
benchmarks and broader results on all benchmarks than the SO
method. Restated, the proposed MO method can achieve widespread coverage with various numbers of transmitters without
suffering from sensitivity to the weights of objectives in thewireless transmitter placement problem.
VI. C ONCLUSION
This paper has presented an MO variable-length genetic
algorithm for solving the wireless heterogeneous transmitter
placement problem. Specifically, representation and crossover
were designed to fit the requirement of variable chromosome
length. The representation supports the placement of heterogeneous transmitters. Furthermore, the MO scheme enables
simultaneous optimization of coverage, cost, capacity, andoverlap.
The proposed algorithm has the following advantages.
1) It automatically determines an appropriate number oftransmitters for placement.
2) It deals with transmitter heterogeneity.
3) It simultaneously optimizes placement and considers
multiple objectives.
In evaluating the proposed algorithm, simulations were conducted using six benchmarks, including homogeneous and956

IEEE TRANSACTIONS ON SYSTEMS, MAN, AND CYBERNETICS—PART B: CYBERNETICS, VOL. 39, NO. 4, AUGUST 2009

TABLE VIIICOMPARISON OF A NONDOMINATED FRONT FOR THE SO AND MO METHODS. BOLDFACE MARKS THE SUPERIOR RESULTS. (THE NUMBER #BS
FOR THE MO M ETHOD C ORRESPONDS TO THE N UMBER FOR THE SO M ETHOD ). (a) B ENCHMARK 1. (b) B ENCHMARK 2.
(c) BENCHMARK 3. (d) BENCHMARK 4. (e) BENCHMARK 6

TING et al.: WIRELESS TRANSMITTER PLACEMENT USING MO VARIABLE-LENGTH GENETIC ALGORITHM

Fig. 22. Comparison of nondominated solutions for the SO and MO methods
on benchmark 6 in terms of coverage and cost. The red circles denote the SO
results, and the blue crosses denote the MO results.

heterogeneous transmitters. For all the benchmarks, the proposed algorithm yielded nondominated solutions that are very
close to the optima in terms of coverage, cost, capacity, andoverlap; precisely, it achieves higher than 98% coverage with
an optimal number of transmitters on all six benchmarks. Theseexperimental results validate the effectiveness of the proposed
algorithm in dealing with the wireless heterogeneous transmitter placement problem.
Future work includes some directions. First, the proposed
uniform crossover for substrings operates on a single substring
at a time, which may not be efficient enough for large-scale
problems that have long chromosomes. A possible way toaddress this issue is to extend the uniform crossover to operate
on multiple substrings. Second, more complicated constraints
and objectives should be taken into account in the problem
model. Additionally, application to mobile networks is an important direction for future work. Third, the performance evaluation should include a comparison to other MO optimization
algorithms, e.g., variable-length real jumping genes genetic
algorithm (VRJGGA) [28]. Enhancement in the search abilityof MO evolutionary algorithms [38], [39] will also be promising
to improve the performance on the wireless heterogeneoustransmitter placement problem with more than three objectives.
ACKNOWLEDGMENT
The authors would like to thank the reviewers and the
Associate Editor for their valuable comments and suggestions,and C.K. Huang for help with the simulation of the last twobenchmarks.
R EFERENCES[1] Y.-T. Chen, “Enhance emergency services by use of novel road management system in wireless city,” in Proc. IEEE Conf. Intell. Transp. Syst.,
2007, pp. 748–753.
[2] D. Niyato and E. Hossain, “Wireless broadband access: WIMAX andbeyond—Integration of WiMAX and WiFi: Optimal pricing for bandwidth sharing,” IEEE Commun. Mag., vol. 45, no. 5, pp. 140–146,
May 2007.
[3] M. Ibrahim, K. Khawam, A. Samhat, and S. Tohme, “Dimensioning hierarchical WiMax–WiFi networks,” in Proc. IEEE Conf. Consum. Commun.
Netw., 2008, pp. 48–53.

957[4] Q. Hao, B. H. Soong, E. Gunawan, J. T. Ong, C. B. Soh, and Z. Li, “A
low-cost cellular mobile communication system: A hierarchical optimization network resource planning approach,” IEEE J. Sel. Areas Commun.,vol. 15, no. 7, pp. 1315–1326, Sep. 1997.
[5] J. K. Han, B. S. Park, Y. S. Choi, and H. K. Park, “Genetic approach witha new representation for base station placement in mobile communications,” in Proc. Veh. Technol. Conf., 2001, vol. 4, pp. 2703–2707.
[6] B. S. Park, J. G. Yook, and H. K. Park, “The determination of base station
placement and transmit power in an inhomogeneous traffic distribution
for radio network planning,” in Proc. Veh. Technol. Conf., 2002, vol. 4,
pp. 2051–2055.
[7] Y. Zhang, C. Ji, P. Yuan, M. Li, C. Wang, and G. Wang, “Particle swarm
optimization for base station placement in mobile communication,” inProc. IEEE Int. Conf. Netw., Sens. Control, 2004, vol. 1, pp. 428–432.
[8] K. Tutschku, “Demand-based radio network planning of cellular
mobile communication systems,” in Proc. INFOCOM, 1998, vol. 3,
pp. 1054–1061.
[9] X. Huang, U. Behr, and W. Wiesbeck, “Automatic cell planning for a
low-cost and spectrum efficient wireless network,” in Proc. IEEE Global
Telecommun. Conf., 2000, vol. 1, pp. 276–282.
[10] L. Raisanen, “A permutation-coded evolutionary strategy for multiobjective GSM network planning,” J. Heuristics, vol. 14, no. 1, pp. 1–21,
Feb. 2008.
[11] K. Pahlavan and P. Krishnamurthy, Principles of Wireless Networks.
Englewood Cliffs, NJ: Prentice-Hall PTR, 2002.
[12] M. Unbehaun and M. Kamenetsky, “On the deployment of picocellular
wireless infrastructure,” Wireless Commun., vol. 10, no. 6, pp. 70–80,
Dec. 2003.
[13] C. Y. Lee and G. H. Kang, “Cell planning with capacity expansion in
mobile communications: A tabu search approach,” IEEE Trans. Veh.
Technol., vol. 49, no. 5, pp. 1678–1691, Sep. 2000.
[14] E. Amaldi, A. Capone, and F. Malucelli, “Planning UMTS base station
location: Optimization models with power control and algorithms,” IEEE
Trans. Wireless Commun., vol. 2, no. 5, pp. 939–952, Sep. 2003.
[15] N. Weicker, G. Szabo, K. Weicker, and P. Widmayer, “Evolutionary
multiobjective optimization for base station transmitter placement withfrequency assignment,” IEEE Trans. Evol. Comput., vol. 7, no. 2, pp. 189–
203, Apr. 2003.
[16] P. Reininger and A. Caminada, “Multicriteria design model for cellular
network,” Ann. Oper. Res., vol. 107, no. 1–4, pp. 251–265, Oct. 2001.
[17] M. Vasquez and J. K. Hao, “A heuristic approach for antenna positioningin cellular networks,” J. Heuristics, vol. 7, no. 5, pp. 443–472, Sep. 2001.
[18] S. Hurley, “Planning effective cellular mobile radio networks,” IEEE
Trans. Veh. Technol., vol. 51, no. 2, pp. 243–253, Mar. 2002.
[19] J. Zimmermann, R. Hons, and H. Mühlenbein, “ENCON: An evolutionary
algorithm for the antenna placement problem,” Comput. Ind. Eng., vol. 44,
no. 2, pp. 209–226, Feb. 2003.
[20] L. Raisanen and M. R. Whitaker, “Comparison and evaluation of multiple
objective genetic algorithms for the antenna placement problem,” Mobile
Netw. Appl., vol. 10, no. 1/2, pp. 79–88, Feb. 2005.
[21] K. Deb, A. Pratap, S. Agarwal, and T. Meyarivan, “A fast and elitist
multiobjective genetic algorithm: NSGA-II,” IEEE Trans. Evol. Comput.,vol. 6, no. 2, pp. 182–197, Apr. 2002.
[22] K. S. N. Ripon, S. Kwong, and K. F. Man, “A real-coding jumping gene
genetic algorithm (RJGGA) for multiobjective optimization,” Inf. Sci.,
vol. 177, no. 2, pp. 632–654, Jan. 2007.
[23] B. McClintock, “The origin and behavior of mutable loci in maize,” Proc.
Nat. Acad. Sci. U.S.A., vol. 36, no. 6, pp. 344–355, Jun. 1950.
[24] T. M. Chan, K. F. Man, K. S. Tang, and S. Kwong, “Jumping-genes paradigm for optimizing factory WLAN network,” IEEE Trans. Ind. Informat.,vol. 3, no. 1, pp. 33–43, Feb. 2007.
[25] D. E. Goldberg, K. Deb, and B. Korb, “Messy genetic algorithms: Motivation, analysis, and first results,” Complex Syst., vol. 3, pp. 493–530,
1989.
[26] “The SAGA cross: The mechanics of crossover for variable-length genetic
algorithms,” in Parallel Problem Solving from Nature, vol. 2, I. Harvey,
R. Männer, and B. Manderick, Eds. Amsterdam, The Netherlands: North
Holland, 1992, pp. 269–278.
[27] B. Hutt and K. Warwick, “Synapsing variable-length crossover: Meaningful crossover for variable-length genomes,” IEEE Trans. Evol. Comput.,vol. 11, no. 1, pp. 118–131, Feb. 2007.
[28] K. S. N. Ripon, C. H. Tsang, S. Kwong, and M. K. Ip, “Multiobjective evolutionary clustering using variable-length real jumping
genes genetic algorithm,” in Proc. 18th Int. Conf. Pattern Recog., 2006,
pp. 1200–1203.
[29] T. S. Rappaport, Wireless Communications: Principles and Practice.
Englewood Cliffs, NJ: Prentice-Hall, 2002.

958

IEEE TRANSACTIONS ON SYSTEMS, MAN, AND CYBERNETICS—PART B: CYBERNETICS, VOL. 39, NO. 4, AUGUST 2009[30] C. Prommak, J. Kabara, D. Tipper, and C. Charnsripinyo, “Next generation wireless LAN system design,” in Proc. Mil. Commun. Conf., 2002,
vol. 1, pp. 473–477.
[31] S. Bosio, A. Capone, and M. Cesana, “Radio planning of wireless local
area networks,” IEEE/ACM Trans. Netw., vol. 15, no. 6, pp. 1414–1427,
Dec. 2007.
[32] D. E. Goldberg, Genetic Algorithms in Search, Optimization and Machine
Learning. Norwell, MA: Kluwer, 1989.
[33] D. E. Goldberg and K. Deb, “A comparative analysis of selection schemes
used in genetic algorithms,” in Proc. 1st Workshop Found. Genetic
Algorithms, 1991, pp. 69–93.
[34] G. Taguchi, Introduction to Quality Engineering. Tokyo, Japan: Asian
Productivity Organization, 1986.
[35] R. C. Purshouse and P. J. Fleming, “Evolutionary many-objective optimisation: An exploratory analysis,” in Proc. IEEE Congr. Evol. Comput.,
2003, pp. 2066–2073.
[36] E. J. Hughes, “Evolutionary many-objective optimization: Many once or
one many?” in Proc. IEEE Congr. Evol. Comput., 2008, pp. 222–227.
[37] H. Ishibuchi, N. Tsukamoto, and Y. Nojima, “Evolutionary manyobjective optimization: A short review,” in Proc. IEEE Congr. Evol.
Comput., 2008, pp. 2419–2426.
[38] H. Ishibuch, N. Tsukamoto, Y. Hitotsuyanagi, and Y. Nojima, “Effectiveness of scalability improvement attempts on the performance of NSGA-II
for many-objective problems,” in Proc. 10th Annu. Conf. Genetic Evol.
Comput., 2008, pp. 649–656.
[39] X. Zu, Y. Chen, M. Liu, and L. Kang, “A new evolutionary algorithm forsolving many-objective optimization problems,” IEEE Trans. Syst., Man,
Cybern. B, Cybern., vol. 8, no. 5, pp. 1402–1412, Oct. 2008.

Chuan-Kang Ting (S’01–M’06) received the B.S.
degree from the National Chiao Tung University,
Hsinchu, Taiwan, in 1994, the M.S. degree from the
National Tsing Hua University, Hsinchu, Taiwan, in
1996, and the Ph.D. degree from the University ofPaderborn, Paderborn, Germany, in 2005.
He is currently an Assistant Professor with the
Department of Computer Science and Information
Engineering, National Chung Cheng University. His
research interests are in evolutionary computation,
memetic computing, metaheuristic algorithms, multiobjective optimization, and machine learning.

Chung-Nan Lee received the B.S. and M.S. degrees
in electrical engineering from the National Cheng
Kung University, Tainan, Taiwan, in 1980 and 1982,
respectively, and the Ph.D. degree in electrical engineering from the University of Washington, Seattle,
in 1992.
Since 1992, he has been with the National
Sun Yat-Sen University, Kaohsiung, Taiwan, where
he was an Associate Professor with the Departmentof Computer Science and Engineering from 1992
to 1999, was the Chairman of the Department ofComputer Science and Engineering from August 1999 to July 2001, and iscurrently a Professor. His current research interests include multimedia overwireless networks, bioinformatics, and evolutionary computing.

Hui-Chun Chang received the B.S. and M.S. degrees in computer science and engineering fromthe National Sun Yat-Sen University, Kaohsiung,Taiwan, in 2005 and 2007, respectively.

Jain-Shing Wu received the B.S. degree in computer and information science in 2000 from Soochow
University, Taipei, Taiwan, and the M.S. degree incomputer science and engineering in 2002 fromthe National Sun Yat-Sen University, Kaohsiung,Taiwan, where he is currently working toward the
Ph.D. degree.
His current research interests include bioinformatics, evolutionary computing, and information
retrieval.