Francisco Luna

Juan J Durillo

Antonio J Nebro

Enrique Alba

Evolutionary Algorithms for Solving the Automatic Cell Planning Problem: A Survey

Keywords: Evolutionary Algorithms, Automatic Cell Planning, Survey Evolutionary algorithms, automatic cell planning, survey

Automatic Cell Planning (ACP) is an optimization problem from the mobile telecommunication domain that addresses finding the location of the network antennae as well as their parameter settings in order to satisfy several cellular operator requirements. Due to its NP-hard complexity, evolutionary techniques have become popular to solve ACP instances. This paper presents a survey of evolutionary algorithms (EAs) engineered for addressing ACP problems, analyzing both the features of the considered ACP problem and the main aspects of the EAs used to solve them. The survey provides an up-to-date overview that is not limited to any particular kind of evolutionary approach, and comprises advanced algorithmic enhancements like hybridization and parallelization. The paper ends by addressing some important issues and open questions that can be the subject of future research.

Introduction

Planning and managing a cellular phone system means engineers have to face many challenging optimization problems (Resende and Pardalos (2006)). Assuming that the business planning activities are already completed, i.e., choosing customer segments, network technology to be used, etc., one of the most significant technical optimization problems is the radio network planning [START_REF] Mishra | Fundamentals of Cellular Network Planning and Optimisation: 2G/2[END_REF]), also known as the Automatic Cell Planning (ACP) problem, the network dimensioning problem, or the capacity planning problem. Indeed, the foundation of a well-performing cellular network is the basic radio platform since it is the part of the network which is closest to mobile users. Also, it has clear benefits for the operators since they reduce the infrastructure costs and, at the same time, increase revenue and user satisfaction.

In the initial deployment of a cellular network, the ACP problem addresses selecting the locations of base stations (BTSs) from a set of candidate sites, as well as their parameter settings, in such a way that a number of network requirements are satisfied. These requirements include maximizing the area covered and the traffic capacity, while minimizing the infrastructure cost. Configuring BTSs is not a simple task, since it implies setting up many configuration parameters, such as the antenna type, the emission power, and/or the tilt and azimuth angles. However, cellular networks need to be adapted to the highly competitive telecommunications industry: new services, new equipment technologies, increasing system capacity, etc. Even in relatively mature cellular markets, these issues force the deployment of additional sites, not only to enhance the system capacity but also to provide increased levels of in-building coverage as mobile users expect to be offered service in all geographical area. The ACP problem therefore holds both for the second generation of cellular phone systems, GSM (Global System for Mobile communication, [START_REF] Mouly | The GSM System for Mobile Communications[END_REF]), and its enhanced releases GPRS [START_REF] Granbohm | GPRS -General Packet Radio Service[END_REF]) and EDGE [START_REF] Furuskar | EDGE -Enhanced Data Rates for GSM and TDMA/136 Evolution[END_REF]), as well as for the current third generation networks, UMTS (Universal Mobile Telecommunication System, [START_REF] Rapeli | UMTS: Targets, System Concept, and Standardization in a Global Framework[END_REF]).

The simplest version of the ACP problem, as an extension of the classical minimum cost set covering problem, has NP-hard complexity [START_REF] Glasser | The complexity of base station positioning in cellular networks[END_REF]). In more complex and realistic versions in which BTSs have to be dimensioned, the high number of configurations for each of these BTSs has to be taken into consideration. Even when the inherently continuous BTS parameters such as emission power, tilt and azimuth are discretized into a small subset of possible values, the search space becomes huge. However, an additional issue emerges in this optimization problem: changing the configuration setting of any BTS may affect other BTSs. For instance, if the maximum emission power of a BTS b is reduced to decrease the signal interference in a given area of the network, other BTSs should hold the traffic capacity that has been left unsupported by b. If these other BTSs are already operating at their full capacity, the network would simply start dropping calls of mobile users. This means that making small local changes would require most of the network predictions to be recomputed.

In general, two kinds of techniques can be applied to solve hard optimization problems, such as ACP: exact and approximate. Exact methods such as brand and bound or the A* algorithm are effective for problems of small sizes; when problems become larger, usually because of their NP-hard complexity, approximate algorithms are mandatory. Among these approximate optimization techniques, metaheuristics [START_REF] Glover | Handbook of Metaheuristics[END_REF]), has become a highly active research area. Although there is not a commonly accepted definition of metaheuristics, they can be considered as high-level strategies that [START_REF] Blum | Metaheuristics in Combinatorial Optimization: Overview and Conceptual Comparison[END_REF]). Evolutionary algorithms (EAs, Bäck et al. (1997)) are one of these techniques and they are, by far, the most popular metaheuristics. They are based on maintaining a population of tentative solutions that are competitively manipulated by applying variation operators (selection, recombination, mutation). EAs have been widely used to address ACP problems. Indeed, they can provide this complex optimization problem with very accurate results, even when little knowledge is used in the exploration of the search space. As discussed before, achieving a satisfactory radio network design requires consideration of a number of issues which are contradictory to each other. For example, the cost of the entire network infrastructure can be reduced by using a small number of omnidirectional antennae operating at a maximum power. This would provide a wide coverage with small cell overlapping and, as a consequence, low interference. However, the network might not be able to satisfy the traffic demand of each cell. This issue can be tackled by adding more antennae, leading to a cost increment and potentially greater interference. As a consequence, it is mandatory to find trade-off solutions for these conflicting goals. The ACP problem is therefore multiobjective in nature. This fact has made EAs even more popular for solving ACP. Indeed, when using a multiobjective formulation of a given optimization problem (e.g., ACP), the goal does not lie in finding one single solution, but a set of trade-off solutions. The point is that EAs are particularly well suited to solve multiobjective problems. Their main advantage is that they are able to find such a set of trade-off solutions in one single run [START_REF] Coello | Evolutionary Algorithms for Solving Multi-Objective Problems[END_REF], [START_REF] Deb | A Fast and Elitist Multiobjective Genetic Algorithm: NSGA-II[END_REF]), what has promoted their utilization for addressing the ACP problem even more. This paper is aimed at providing a survey of work related to EAs used to solve ACP. To the best of our knowledge, it is the first attempt at covering this gap. The goal is that an interested researcher will be able to find references on relevant studies using EAs applied to different formulations of the ACP problem and define new strategies for improving the current state of the art. An up-to-date overview that is not limited to any particular kind of evolutionary approach is provided. More than 40 works have been revised and summarized in this overview, which analyzes both the features of the ACP problem addressed and the main aspects of the EAs used for their resolution. Important aspects of the evolutionary search are considered, such as the encoding and genetic operators, as well as advanced algorithmic enhancements like hybridization and parallelization.

The rest of the paper is organized as follows. In the next section, the basic concepts of EAs and the different models used for solving the ACP problem in the literature are described. The survey of related works is provided in Section 3. Finally, the main conclusions of this paper are given in Section 4, which also addresses some important issues for future research.

Basics on EAs and ACP

This section provides the reader with a brief overview of the two main topics of this work, namely evolutionary algorithms (EAs) and automatic cell planning (ACP) problems.

F

Evolutionary Algorithms

EAs are stochastic search methods inspired by nature's capability to evolve individuals well adapted to their environment. Well-accepted subclasses of EAs are genetic algorithms (GAs), evolution strategies (ESs), and evolutionary programming (EP) [START_REF] Bäck | Evolutionary Algorithms in Theory and Practice: Evolution Strategies, Evolutionary Programming, Genetic Algorithms[END_REF]). The basic outline of a standard EA is shown in Figure 1. At each generation (iteration) t, an EA operates on a population of individuals P (t), each one encoding a tentative solution, thus searching in many regions of the problem space at the same time. Each individual is a string of symbols encoding a solution for the problem (genotype) and has an associated fitness value (phenotype) which is computed by the objective function. This fitness function is aimed at ranking the quality of the evaluated individual with respect to the rest of the population. The application of stochastic variation operators, such as mixing parts of two strings (crossover) or randomly changing their contents (mutation), leads this population towards the fittest regions in an iterative manner. The algorithm finishes when a stopping condition is met (e.g., an optimum is found or a number of function evaluations has been carried out).

Models for the ACP Problem

A number of different models have been defined in the literature to solve ACP problems (see [START_REF] Raisanen | Multi-objective site selection and analysis for GSM cellular network planning[END_REF]), ranging from pure abstract models (e.g., based on graph theory) to rather detailed ones (models considering specific areas, with known traffic and topologies). The intermediate models proposed move in two different directions. They either add real information to abstract models or they try to reduce the complexity of detailed models to reduce their computational demands. The three main models found in the literature -demand node, disk, and cell and test point-are described in the following sections.

Demand Node Model

The concept of demand nodes was introduced first by [START_REF] Gerlich | An integrated approach to cellular network planning[END_REF], and it has since been used in different works (e.g., [START_REF] Amaldi | Optimizing base station siting in UMTS networks[END_REF], [START_REF] Galota | A polynomial-time approximation scheme for base station positioning in UMTS networks[END_REF], [START_REF] Tutschku | Interference minimization using automatic design of cellular communication networks[END_REF], [START_REF] Weicker | Evolutionary multiobjective optimization for base station transmitter placement with frequency assignment[END_REF]). The basic idea is that the demand node represents the center of an area where the traffic is being generated by the users. The main advantage of this model is that by combining the traffic of a small region in a single point, the computational requirements are drastically reduced; the drawback is that the realism of the problem is also simplified. The demand nodes comprise a number of test points, hence the need fewer nodes; however, merging test points into a single demand node has the same effect as applying a lossy compression mechanism: the resolution is reduced. Most of the research works using this model also allow the total freedom as regards the positioning of candidate sites. This allows to uniformly distribute the sites over the full area to be covered, which usually is not possible in practice as a site cannot simply be placed anywhere, e.g., in the middle of a highway.

Disk Model

The first use of disk (circle) graphs in the design of cellular networks was in [START_REF] Hale | Frequency Assignment: Theory and Applications[END_REF], where it was applied to solve the frequency assignment problem. Later extensions to this model consider intersections among disks and non-uniform traffic distributions (Huang et al. (2000a,b,c)). The main advantage of the approach presented in Huang et al. (2000a) is that it is possible to take into account different goals related to the design of the network; thus, the problems of cell planning and frequency assignment can be addressed simultaneously. Furthermore, the computational costs are not high.

The main inconvenience of the disks model has to do with the fact that it assumes an ideal propagation model, so all the cells have the same shape. Even though the size of the cells can vary depending on a non-uniform traffic distribution (Huang et al. (2000b)), the shape is always a circle. Another issue is that sites may be located anywhere, so the same problems as in the demand node model arise.

Cell and Test Point Model

Although this model is known thanks to the works of [START_REF] Reininger | Multi-stage optimization for mobile radio network planning[END_REF]Caminada (1998a,b, 2001), it appeared first in [START_REF] Hao | A hierarchical optimization network resource planning approach[END_REF]. In it, the working area is discretized into a set of test points which are spread over the whole area. These test points are used to measure the amount of signal strength in the region where the network operator intends to service the traffic demand of a set of customers.

Three subsets of test points are defined: Reception Test Points (RTPs), where the signal quality is tested; Service Test Points (STPs), where the signal quality must exceed a minimum threshold to be usable by the customers; and the Traffic Test Points (TTPs), where a certain traffic amount is associated to the customers (measured in Erlangs).

In this model, the set of candidate site locations does not have to be uniformly distributed in the terrain, so it is a better representation of the scenarios presented by the operators. Its main advantage is that it allows measuring all the network objectives (such as coverage and capacity). Notwithstanding, there is a clear inconvenience: the computational cost increases because a high number of points is usually used to face the problem (e.g., test points every 200 meters) in order to increase the realism. This realism is the main reason that this model is widely adopted in the literature, e.g., [START_REF] Hurley | Planning Effective Cellular Mobile Radio Networks[END_REF], [START_REF] Raisanen | A comparison of randomized and evolutionary approaches for optimizing base station site selection[END_REF], Raisanen andWhitaker (2005, 2003), [START_REF] Talbi | Designing cellular networks using a parallel hybrid metaheuristic on the computational grid[END_REF], [START_REF] Talbi | Hierarchical parallel approach for GSM mobile network design[END_REF], [START_REF] Vasquez | A heuristic approach for antenna positioning in cellular networks[END_REF], Zimmermann et al. (2003b).

The Survey

EAs, and more concretely GAs, have been widely used to tackle most of the ACP models proposed. This section includes detailed analysis of more than 40 works that show the different EA approaches developed to address this complex optimization problem. It starts by giving an overview of the literature, focusing on the main features of the particular ACP problem solved in each research work. Next, a more in depth review based on algorithmic details (encoding schemes, genetic operators, hybridization, and parallelization) is provided.

ACP Problems Addressed by EAs

Tables 1, 2 and 3 summarize the main characteristics of the ACP problems addressed by EAs in the literature. For each row, they show the following information:

• Ref.: Bibliographic reference. The publication year of the first work of the series is used to rank the entries. • Alg.: Particular EA used for solving the problem (see [START_REF] Bäck | Evolutionary Algorithms in Theory and Practice: Evolution Strategies, Evolutionary Programming, Genetic Algorithms[END_REF] for the details).

Here, it distinguishes between:

(1) GA: simple GA. This keyword is used when not enough information is given in the paper for further specifications.

(2) genGA: generational GA.

(3) ssGA: steady state GA. (4) dGA: distributed GA. This kind of GA may appear combined with the two previous algorithms. That is, dssGA refers to a distributed GA in which each subpopulation evolves by using the steady state scheme. (5) ES: evolution strategy. ( 6) Concrete algorithms such as CHC, DE, NSGA-II, SPEA2, and others whose description can be found in the references provided. • Multi: this column points out whether the problem is addressed by using multiobjective techniques based on Pareto optimality. • ACP: ACP model used (see Section 2.2). Available values are Demand Node, Disk, and Test Points. • Sites: it shows whether the locations of the BTSs are chosen among a set of candidate sites (CSL or Candidate Site List) or they can be freely placed all over the geographic area. • Cell: this column indicates how the cell or service area of BTSs is computed. • P w, T i, and Az: these three columns show respectively whether the power, tilt, and azimuth of the BTSs are optimized. These are the most common settings adjusted when the BTS dimensioning is addressed. • Objectives: different aspects of the cellular network that are optimized.

• Constraints: aspects of the cellular network that are considered as constraints during the optimization process.

From the algorithmic point of view, classic GAs have been used in the literature for solving the ACP problem, both generational (genGA) and steady state ones (ssGA). Indeed, they are applied in almost 50% of the works reviewed. Rather specific evolutionary techniques such as CHC [START_REF] Eshelman | The CHC Adaptive Search Algorithm: How to Have Safe Search When Engaging in Nontraditional Genetic Recombination[END_REF]), Differential Evolution (DE, [START_REF] Storn | Differential Evolution -A Simple Efficient Adaptive Scheme for Global Optimization over Continuous Spaces[END_REF]), PBIL [START_REF] Baluja | Population-Based Incremental Learning: A Method for Integrating Genetic Search Based Function Optimization and Competitive Learning[END_REF]), or Artificial Immune Systems (AIS, de Melo Carvalho Filho and de Alencar ( 2008)) are also found. It can be seen that not only sequential approaches exist, but also parallel models deployed on standard parallel platforms such as clusters of computers (dGAs, [START_REF] Alba | On the Behavior of Parallel Genetic Algorithms for Optimal Placement of Antennae in Telecommunications[END_REF], [START_REF] Calégari | Combinatorial optimization algorithms for radio network planning[END_REF]) and even grid computing systems [START_REF] Talbi | Designing cellular networks using a parallel hybrid metaheuristic on the computational grid[END_REF]). If multiobjective approaches are considered, NSGA-II [START_REF] Deb | A Fast and Elitist Multiobjective Genetic Algorithm: NSGA-II[END_REF]) and SPEA2 [START_REF] Zitzler | SPEA2: Improving the Strength Pareto Evolutionary Algorithm[END_REF]), the two best known algorithms in the evolutionary multiobjective research community have been applied in eight of the analyzed works. Other specific multiobjective algorithms used are SEAMO [START_REF] Raisanen | Comparison and evaluation of multiple objective genetic algorithms for the antenna placement problem[END_REF]) and MOCHC (Nebro et al. (2007)). From the point of view of the formulation, the first proposals have adopted a single objective approach in which the different network aspects to be optimized are weighted into a single (aggregative) function [START_REF] Calégari | Parallel island-based genetic algorithm for radio network design[END_REF] objective EAs have meant that the number of works using this multiobjective formulation has increased in the last years (Cerri andRusso (2006), Nebro et al. (2007), [START_REF] Raisanen | A permutation-coded evolutionary strategy for multi-objective GSM network planning[END_REF], [START_REF] Talbi | Designing cellular networks using a parallel hybrid metaheuristic on the computational grid[END_REF]).

Number of works

Figure 2 summarizes the number of reviewed contributions that fall into different categories: mono/multi, ACP model, site selection, cell shape computation, and BTS parameter optimization. Now, each group of columns of the figure is analyzed. In the first group, from all the works in the literature reviewed, monoobjective formulations have been more widely used in spite of the fact that the ACP problem is naturally prone to the multiobjective ones. The additional complexity added by the Pareto optimality mechanisms makes the ACP researchers reluctant to adopt this kind of technique. However, the multiobjective approach may be the most appropriate because it can provide the decision maker (network designer) with a set of different configurations for the BTSs, none of which is better than the others (non-dominated). These configurations could be used in particular scenarios that may appear during the operational lifetime of the network.

The second group of columns shows the ACP models used in the analyzed contributions. It is clear that both the Demand Node and the Test Point are the most widely adopted models. The simplicity and low computational requirements, in the former case, and the realism, in the latter one, are the reasons that explain these facts. The Disk model has more to do with theoretical studies. Indeed, cellular networks composed exclusively of omnidirectional antennae are hardly found in the real world (vectorization allows the network capacity to be greatly increased). Looking at the third group of columns in Figure 2, it can be observed that using a candidate site list (CSL) instead of freely placing the BTSs in any location of the network is the most common option. This is because it is unlikely many network operators are granted such freedom (e.g., no BTS can be placed near schools or in the middle of a lake). The fourth group of columns also reflects the preferred choice for computing the cells (serving areas) of the BTSs: the propagation models such as free space, Okumura-Hata or Walfish-Ikegami model (COST231 (1991)). Selecting one or another depends mainly on the computational effort required (ITU (1997)). Omnidirectional and square cells also appear in several contributions (8 and 6 works, respectively). Tables 1, 2 and 3 include alternative methods for computing the cell associated to BTSs such as modern ray tracing techniques [START_REF] Laki | Cell planning in mobile communication systems using SGA optimization[END_REF]). Finally, the last group of columns summarizes the number of papers in which the power, tilt and azimuth are involved in the optimization process. That is, they are decision variables of the search space. Even though differences here are smaller, it can be seen that the power parameter is more often optimized than the other two. It applies to any kind of BTS (omnidirectional, directive, square, etc.) as the main setting to manage the cell size. The tilt and azimuth angles usually appear in very accurate ACP models. They normally lead to highly expensive computational tasks, which explains the lower incidence in the literature.

To conclude with this discussion about the analyzed works, the objective functions and the constraints used in the different approaches are now analyzed. On the objectives side, a clear trend exists in considering the network cost, measured in terms of number of installed sites, and the quality of services (QoS) provided by these sites. These two objective functions are clearly contradictory. The main difference between many contributions lies in the concept of QoS. Maximizing the network coverage is the most widely used option and it appears in 78% of the revised contributions. However, a more realistic approach is based on using such objective as a constraint (e.g., at least 90% of the network must be covered) so as to discard useless configurations. Indeed, it does not make any sense to deploy an expensive, fully operational network infrastructure just to cover a small percentage of a given target area. Other ways of measuring the network QoS in the literature have taken into consideration the interference caused by cell overlapping or the traffic capacity of the network. As to the constraints, the handover, or the capability of the network to guarantee continuous communication while the mobile user is moving from one cell to another, is the one that most appears.

Details on EAs for the ACP Problem

This section reviews the main features of the EAs found in the literature for solving the ACP problem. Potential advantages and drawbacks of each algorithm are analyzed in the light of their corresponding encoding schemes, genetic operators, local search, and parallelization. Table 4 includes a summary of all these EA aspects.

Encoding Schemes

Several encoding schemes have been used, and some of them have been designed specially for solving ACP problems. In summary, they can be categorized into four types: binary, integer, real, and ACP-targeted.

3.2.1.1. Binary Encoding. The most widely adopted scheme is the classical binary encoding, i.e., the tentative solutions are bit strings. The information encoded by this bit string depends on the specific ACP problem addressed.

The first usage of this encoding scheme appears when the optimization task is simply to position the BTSs of the network by selecting a subset of sites from a CSL (Candidate Site List). Then, EAs work on bit strings of length N , where N is the total number of candidate sites. Each position of the bit string corresponds to a site, i.e., the ith position represents the ith site. The value of the ith is 1 if the ith site is selected, and zero otherwise. This approach is specially used when solving ACP problems that follow the Demand Node model (see Section 2.2.1): [START_REF] Alba | On the Behavior of Parallel Genetic Algorithms for Optimal Placement of Antennae in Telecommunications[END_REF], [START_REF] Alba | Evolutionary Algorithms for Optimal Placement of Antennae in Radio Network Design[END_REF] The binary encoding has also been used when the BTSs can be freely placed anywhere on the geographical area of the network (no CSL exists). In this case, the bit string encodes the binary representation of a list of real numbers that represent the (x, y) coordinates of the sites. However, in all the material analyzed, the tentative solutions also include one or more values that allow dimensioning of the BTS (i.e., allow the BTS service area to be configured). Indeed, in [START_REF] Brunetta | Optimization approaches for wireless network planning[END_REF], [START_REF] Chiara | Hybrid Meta-heuristic Methods in Parallel Environments for 3G Network Planning[END_REF]), the binary string has also considered the power level of emission. In the works of [START_REF] Cerri | Base-station network planning including environmental impact REFERENCES 21[END_REF][START_REF] Cerri | Base-station network planning including environmental impact control[END_REF], [START_REF] Cerri | Application of an Automatic Tool for the Planning of a Cellular Network in a Real Town[END_REF], the authors have not only included the encoding of the emission power, but also the tilt of the antennae. So, for each BTS, 24 bits are used: 9 + 9 bits for the coordinates, 3 bits for the radiated power, and 3 bits for the tilt. [START_REF] Laki | Cell planning in mobile communication systems using SGA optimization[END_REF] have just added the height of the BTSs.

The main advantage of this binary encoding is that it allows the evolutionary search to be performed by means of classical EA operators. These operators have been originally developed to manipulate binary genotypes [START_REF] Goldberg | Genetic Algorithms in Search, Optimization and Machine Learning[END_REF]), as will be further analyzed in Section 3.2.2.

Integer Encoding. Integer encoding has been used by Larry Raisanen, Roger

Witaker and Steve Hurley at Cardiff University in several works: [START_REF] Raisanen | A comparison of randomized and evolutionary approaches for optimizing base station site selection[END_REF], [START_REF] Raisanen | Comparison and evaluation of multiple objective genetic algorithms for the antenna placement problem[END_REF], [START_REF] Raisanen | A permutation-coded evolutionary strategy for multi-objective GSM network planning[END_REF], Whitaker et al. (2004a,b). Their approach is based on considering that each BTS is identified by an integer. Then, given n candidate BTSs, a permutation π of size n represents a solution to the ACP problem. That is, EAs manipulate integer permutations, so special care has to be taken with the genetic operators used. These BTS permutations are then translated into a cell plan by using a decoder. The decoder works by iteratively packing cells as densely as possible, subject to certain constraints not being violated. This cell plan is then used to compute the fitness function.

3.2.1.3. Real Encoding. The real encoding is mainly used for solving ACP problems based on freely positioning the BTSs in the working area of the cellular network. Therefore, the tentative solutions are made up of real numbers that represent the BTS coordinates. This scheme is mainly used in works dealing with the Disk model (see Section 2.2.2). Indeed, this is the approach used in [START_REF] Han | Genetic approach with a new representation for base station placement in mobile communications[END_REF], [START_REF] Park | The determination of base station placement and transmit power in an inhomogeneous traffic distribution for radio network planning[END_REF]. If K is the maximum number of BTS to be placed, solutions are encoded as arrays (c 1 , . . . , c K ), where c i = (x i , y i ) are the coordinates of the ith BTS. When a BTS is not supposed to be deployed, a special NULL value is used. This is the mechanism adopted in these three works to avoid using a variable-length representation and therefore special genetic operators have been developed.

ACP-targeted Encoding.

The encoding schemes shown in this section have been designed especially to deal with ACP problems, so they do not properly fall into any of the previously defined categories. The most widely used non-classical scheme in the EA literature encodes all the optimizable parameter settings of each BTS in the tentative solution. Let us call it network encoding. This encoding is usually aimed not only at positioning the BTSs but also at dimensioning them. Figure 3 displays an example in which the BTS type, the emission power, and the tilt and azimuth angles are to be optimized. It is worth mentioning here that, even though power tilt and azimuth are actually real-valued parameters, they are usually discretized into a rather small set of values in order to reduce the complexity of the optimization problem. This is the approach used in Altman et al. (2002a,b), [START_REF] Cahon | A parallel and hybrid multi-objective evolutionary algorithm applied to the design of cellular networks[END_REF], Jamaa et al. (2004aJamaa et al. ( ,b, 2006)), [START_REF] Jedidi | 2-objective optimization of cells overlap and geometry with evolutionary algorithms[END_REF], [START_REF] Meunier | A multiobjective genetic algorithm for radio network optimization[END_REF], [START_REF] Picard | Automatic cell planing strategies for UMTS networks[END_REF], [START_REF] Reininger | Multi-stage optimization for mobile radio network planning[END_REF], [START_REF] Talbi | Designing cellular networks using a parallel hybrid metaheuristic on the computational grid[END_REF], [START_REF] Talbi | Hierarchical parallel approach for GSM mobile network design[END_REF], [START_REF] Zimmermann | The antenna placement problem for mobile radio networks: an evolutionary approach[END_REF]Zimmermann et al. ( , 2003a,b),b). The main advantage of this encoding scheme is that EAs are put to work on real solutions so therefore problem-domain specific knowledge can be easily included in the search.

URL
Otherwise, no classical well-known operators can be used and newly specific ones have to be developed. Other specific encodings are analyzed next. With the goal of minimizing the number of BTSs required to cover a given area, [START_REF] Créput | Automatic mesh generation for mobile network dimensioning using evolutionary approach[END_REF] have adaptively transformed the hexagonal cell shapes typically used in cellular networks. This adaptive meshing is performed according to a traffic density map and to geometrical constraints. Then, for each cell of the network, the encoding scheme includes six vertices (two real values) plus an attribute that indicates whether it is visible or not. This latter attribute is the particularity of this approach. [START_REF] Lee | Cell Planning with Capacity Expansion in Mobile Communications: A Tabu Search Approach[END_REF] have used group encoding [START_REF] Falkenauer | A New Representation and Operators for Genetic Algorithms Applied to Grouping Problems[END_REF]) to maximize the coverage of traffic demand areas (TDAs) using as few BTSs as possible. In this group encoding, each tentative solution has two parts: the TDA part and the BTS part. In the TDA part a BTS is assigned to each TDA. The BTSs used in the TDA part are then represented in the BTS part. Specific group-oriented operators have been applied. [START_REF] Maple | Parallel genetic algorithms for third generation mobile network planning[END_REF] have proposed a matrix encoding with size 3 × N , where N is the maximum number of BTSs. All the BTSs are labeled so that the ith column corresponds to the ith BTS. In this encoding, the three values of the ith BTS indicate whether the BTS is present or not in the network (BTS selection), the BTS height, and the BTS emission power. This encoding has many drawbacks but no further discussion is given since the authors only present their proposal in the paper, with no experimentation at all. Consequently, this paper will not be considered further in this survey.

The work of [START_REF] Weicker | Evolutionary multiobjective optimization for base station transmitter placement with frequency assignment[END_REF] presents an encoding that mixes real and integer values, as well as a set of frequencies. This specialized encoding is required because they address both the BTS positioning and the frequency assignment simultaneously. A candidate solution includes, for each BTS, two real values representing its coordinates, two integer values encoding the transmitting power and the number of available channels in the BTS, and the set of channels assigned to the BTS.

Operators

Several genetic operators have been investigated in the literature for solving ACP problems (Table 4). This section is only aimed at discussing the crossover and mutation operators since they are the ones which depend on the encoding schemes (selection and replacement operators are based on the fitness of the individuals). 3.2.2.1. Crossover. The classical Single Point Crossover (SPX) has been extensively used for solving ACP problems. Most of the existing work using binary encoding have adopted this approach (e.g., [START_REF] Calégari | A Parallel Genetic Approach to Transceiver Placement Optimisation[END_REF], [START_REF] Lieska | Radio coverage optimization with genetic algorithms[END_REF], [START_REF] Molina | The automatic location of basestations for optimised cellular coverage: a new combinatorial approach[END_REF]). With this encoding, other well-known operators such as Two Point Crossover [START_REF] Alba | Evolutionary Algorithms for Optimal Placement of Antennae in Radio Network Design[END_REF], [START_REF] Alba | On the Behavior of Parallel Genetic Algorithms for Optimal Placement of Antennae in Telecommunications[END_REF]) and uniform crossover [START_REF] Laki | Cell planning in mobile communication systems using SGA optimization[END_REF], [START_REF] Lin | Cell planning scheme for WCDMA systems using genetic algorithm and measured background noise floor[END_REF]) have been applied. It is also worth mentioning that algorithm-specific crossover operators also appear when particular algorithms have been used. The works of [START_REF] Alba | Optimal placement of antennae using metaheuristics[END_REF][START_REF] Mouly | Optimal Antenna Placement Using a New Multi-Objective CHC Algorithm[END_REF]), Vega-Rodríguez et al. (2007a,b) use the Highly Disruptive Crossover (HUX) designed for the CHC algorithm, whereas the two-fusion crossover [START_REF] Hifi | A Genetic Algorithm-Based Heuristic for Solving the Weighted Maximum Independent Set and Some Equivalent Problems[END_REF]) is applied in Huang et al. (2000a).

In the case of the integer encoding scheme, the cycle crossover has been used in the works of [START_REF] Raisanen | A comparison of randomized and evolutionary approaches for optimizing base station site selection[END_REF], [START_REF] Raisanen | Comparison and evaluation of multiple objective genetic algorithms for the antenna placement problem[END_REF], [START_REF] Raisanen | A permutation-coded evolutionary strategy for multi-objective GSM network planning[END_REF], Whitaker et al. (2004a,b). Since their algorithms work on integer permutations, this crossover operator is aimed at preserving the permutation, and as a result no repair mechanism is required. It is important to remark here that using the decoder procedure that translates the permutation of BTSs into a cell plan avoids the main concern of this representation: different permutations represent the same solution in the objective space.

Traditional recombination operators are not applied with the real encoding scheme since no pure real-valued strings have been used. Indeed, in the works of [START_REF] Han | Genetic approach with a new representation for base station placement in mobile communications[END_REF], [START_REF] Park | The determination of base station placement and transmit power in an inhomogeneous traffic distribution for radio network planning[END_REF] this operator has to deal with the special NULL value used in any given position to indicate that the corresponding BTSs are not deployed. This way, given two parents p 1 and p 2 , the operator returns one single child, c, in which the position of the ith BTS is computed as follows. If p 1 (i) = NULL and p 2 (i) = NULL, then c(i) = NULL; if either p 1 (i) = NULL or p 2 (i) = NULL, c(i) receives the genetic material of the non-NULL parent; otherwise, the ith BTS is placed somewhere near the BTS positions of the parents (sampling a Gaussian distribution).

The main disadvantages of all these crossover operators is that they just manipulate genes, without taking into account the links with other genes (epistasis). Indeed, as explained in the introduction, either activating, deactivating, or redimensioning one given BTS in a cellular network will surely affect the influence of other BTSs in the ACP problem at hand. It is therefore worth giving particular attention to the development of operators specially designed for ACP problems that use classical encoding schemes in their resolution.

When ACP-targeted encoding schemes are adopted, this crossover specialization is already addressed. Most of the works that use the network encoding (see previous section) apply the so-called geographical crossover defined in [START_REF] Meunier | A multiobjective genetic algorithm for radio network optimization[END_REF]). This operator is based on exchanging the configuration of the sites located within a given random radius around a randomly chosen site. Figure 4 shows an example of the working principles of the geographical crossover. The main advantage of this operator is that it considers somehow the connection between the sites in a topological way: only nearby sites are modified. However, under this encoding, the classical SPX crossover has also been used by [START_REF] Reininger | Multi-stage optimization for mobile radio network planning[END_REF].

Other specialized crossover operators have been defined for dealing with ACP-targeted encodings. [START_REF] Créput | Automatic mesh generation for mobile network dimensioning using evolutionary approach[END_REF] have proposed a mechanism in order to combine the vertices of the hexagonal cells used to cover the traffic demand in the cellular network. It works by selecting two individuals as follows. The first one, i 1 , is chosen by fitnessproportional probability (e.g., roulette-wheel selection), whereas the second, i 2 is picked randomly. Since it is assumed that the former will have a better fitness than the latter, the crossover operator generates a child in which i 1 attracts i 2 by using a weighted average sum. [START_REF] Lee | Cell Planning with Capacity Expansion in Mobile Communications: A Tabu Search Approach[END_REF], who have used the grouping GA, have adopted the grouping crossover operator defined by [START_REF] Falkenauer | A New Representation and Operators for Genetic Algorithms Applied to Grouping Problems[END_REF]. Finally, [START_REF] Weicker | Evolutionary multiobjective optimization for base station transmitter placement with frequency assignment[END_REF] have implemented a crossover operator based on the decomposition of the service area of the cellular network. Two halves along one of the dimensions are generated and then, for each half, the fitness of the parent individuals is evaluated. The offspring will inherit the configuration for each of the sub-areas from the fittest parent for that sub-area. The main drawback of this approach is that the operator may generate unfeasible individuals, therefore requiring that the authors apply a repair function.

3.2.2.2. Mutation. The analysis of the mutation operators in the literature for solving ACP problems with EAs is similar to that performed for the crossover operators. It depends greatly on the encoding used. The classical bit flip mutation is the preferred operator for binary encoding schemes (see Section 3.2.1). In the works using integer permutation encoding, a random swap that simply transposes two randomly chosen positions in the permutation is adopted (e.g., [START_REF] Raisanen | Comparison and evaluation of multiple objective genetic algorithms for the antenna placement problem[END_REF]). Again, this operator is safe and no repair function is needed.

The two works categorized with the real encoding, i.e., [START_REF] Han | Genetic approach with a new representation for base station placement in mobile communications[END_REF], [START_REF] Park | The determination of base station placement and transmit power in an inhomogeneous traffic distribution for radio network planning[END_REF], have to manage the NULL value which is used to represent that a BTS is not deployed in the network. This way, for each BTS, the mutation operator either randomly updates the current position of the deployed BTSs or it is assigned with a NULL value; otherwise, if the BTS is not deployed yet, it can remain the same or it is placed in an arbitrary position of the network.

Using the network encoding (ACP-targeted encoding), the mutation operator usually works by first selecting a given site and then updating the configuration of this site. It is called multilevel mutation since it operates at different levels of the encoding. Depending on the parameters of each site, the mutation may affect:

• Activation toggling. If the site is activated, then it is just deactivated. On the other hand, if L i is deactivated, then an entire random configuration for the site is generated. • BTS power tuning. It requires the site to be activated. It randomly chooses a BTS of the site and then the power is randomly changed to one of its discretized values. • BTS tilt tuning. The same as the power tuning, but changing the tilt angle.

• BTS azimuth tuning. The same as the power and tilt tuning, but modifying the azimuth angle.

• BTS diagram tuning. This mutation also requires the site to be activated. The goal of this operator is to change the BTS type, that is, from an omnidirectional BTS to several directive BTSs, or vice versa. The configuration for each newly generated BTS is randomly generated. This is the approach used in Altman et al. (2002a,b), [START_REF] Cahon | A parallel and hybrid multi-objective evolutionary algorithm applied to the design of cellular networks[END_REF], Jamaa et al. (2004aJamaa et al. ( ,b, 2006)), [START_REF] Jedidi | 2-objective optimization of cells overlap and geometry with evolutionary algorithms[END_REF], [START_REF] Meunier | A multiobjective genetic algorithm for radio network optimization[END_REF], [START_REF] Picard | Automatic cell planing strategies for UMTS networks[END_REF], [START_REF] Talbi | Designing cellular networks using a parallel hybrid metaheuristic on the computational grid[END_REF], [START_REF] Talbi | Hierarchical parallel approach for GSM mobile network design[END_REF].

On the other hand, the works of [START_REF] Zimmermann | The antenna placement problem for mobile radio networks: an evolutionary approach[END_REF]Zimmermann et al. ( , 2003b,a) ,a) have further detailed these mutations by defining more specialized search operators. The authors have distinguished between repair operators (RepairTraffic, RepairHole, DecreasePower, IncreasePower, ChangeAzimuth, ChangeTilt, DissipateTraffic) and climb operators (Re-moveWeakAntenna, RemoveAntenna, RemoveWeakSite, RemoveSite, IncreaseCompactness, ReduceIrregularities, and MinimizePower). They all are applied one each time by randomly choosing one of them. Because unfeasible solutions may be generated, a repair phase is used.

Other mutation operators used with ACP-targeted encoding schemes are described next. [START_REF] Créput | Automatic mesh generation for mobile network dimensioning using evolutionary approach[END_REF] have developed the macromutation operator. It is intended to perform simultaneous moves on the vertices of the cells that cover the cellular network, thus allowing these cells to exit or to reach to traffic demand areas. [START_REF] Lee | Cell Planning with Capacity Expansion in Mobile Communications: A Tabu Search Approach[END_REF] have adopted the grouping crossover operator defined by [START_REF] Falkenauer | A New Representation and Operators for Genetic Algorithms Applied to Grouping Problems[END_REF] for the grouping GA. Finally, [START_REF] Weicker | Evolutionary multiobjective optimization for base station transmitter placement with frequency assignment[END_REF] have applied both directed and random mutations. The former ones (6 different operators) include problem knowledge and feasibility is always guaranteed since several preconditions have to be met prior to their application. However, directed mutations find it difficult to explore the entire search space, so this is why the random mutations have been used. The goal is to promote exploration, but the drawback is that feasibility is no longer guaranteed and a repair function has to be applied.

Local Search

Adding ACP problem knowledge to the exploration performed by EAs can be further promoted with the usage of local search algorithms. That is, engineering hybrid algorithms [START_REF] Talbi | A Taxonomy of Hybrid Metaheuristics[END_REF]). So far, this problem specific knowledge has been added by using specific encoding schemes and genetic operators (as has been shown in the previous sections). However, there are several proposals in the literature in which EAs are endowed with highly tailored search methods, allowing the search to be intensified in promising regions of the search space.

When adaptively meshing the cell shapes of a cellular network, [START_REF] Créput | Automatic mesh generation for mobile network dimensioning using evolutionary approach[END_REF] have used a local search algorithm based on a Lamarckian adaptive process. This process applies small mutations on isolated vertices of the hexagonal cells which makes an individual evolves to a local minimum. The mutation operator, called micromutation, performs a small move on some randomly chosen vertex. [START_REF] Talbi | Designing cellular networks using a parallel hybrid metaheuristic on the computational grid[END_REF] have designed a multiobjective local search to be used with the network encoding explained above. It is an iterative process that starts from a set of nondominated solutions (or network configurations). Then, for each activated BTS of any network, it successively tests its removal, the updating of the power, azimuth and tilt with any of the available discretized values. By using the newly generated solutions, the set of nondominated solutions is continuously updated. Finally, the local search algorithm restarts from any newly inserted solution, and so on.

Finally, the decoder approach of [START_REF] Raisanen | A comparison of randomized and evolutionary approaches for optimizing base station site selection[END_REF], [START_REF] Raisanen | Comparison and evaluation of multiple objective genetic algorithms for the antenna placement problem[END_REF], [START_REF] Raisanen | A permutation-coded evolutionary strategy for multi-objective GSM network planning[END_REF], Whitaker et al. (2004a,b) for translating the integer permutation of BTSs into a cell plan can also be mentioned here. As its authors have indicated, this decoder can be considered a local search algorithm.

Parallelization

As early as in the first works published on EAs for solving the ACP problem, i.e., [START_REF] Calégari | A Parallel Genetic Approach to Transceiver Placement Optimisation[END_REF][START_REF] Calégari | Parallel island-based genetic algorithm for radio network design[END_REF], it was soon understood that this optimization problem involved tasks demanding high computational resources. With the aim of not only speeding up the computation but also improving the solution quality, most of the parallel EAs analyzed have adopted the coarse-grained scheme, also known as the island model [START_REF] Alba | Parallelism and Evolutionary Algorithms[END_REF]). They have also used a unidirectional ring topology: Alba and Chicano (2005), [START_REF] Alba | Evolutionary Algorithms for Optimal Placement of Antennae in Radio Network Design[END_REF], [START_REF] Calégari | A Parallel Genetic Approach to Transceiver Placement Optimisation[END_REF][START_REF] Calégari | Parallel island-based genetic algorithm for radio network design[END_REF][START_REF] Calégari | Combinatorial optimization algorithms for radio network planning[END_REF], Chamaret and Condevaux-Lanloy (1998), [START_REF] Lee | Cell Planning with Capacity Expansion in Mobile Communications: A Tabu Search Approach[END_REF]. The work of [START_REF] Créput | Automatic mesh generation for mobile network dimensioning using evolutionary approach[END_REF] has also used the island model with a unidirectional ring topology but, instead of subpopulations, each island runs a hybrid evolution strategy. [START_REF] Meunier | A multiobjective genetic algorithm for radio network optimization[END_REF] have used a master/slave approach for the parallel implementation of the function evaluation, i.e., each function evaluation is distributed to different processors. [START_REF] Talbi | Hierarchical parallel approach for GSM mobile network design[END_REF] have extended this work by using the master/slave scheme not only for the parallel evaluation of the function evaluation, but also for evaluating each tentative solution of the EA asynchronously in parallel. They have also used the island model in this work. Finally, the works of [START_REF] Cahon | A parallel and hybrid multi-objective evolutionary algorithm applied to the design of cellular networks[END_REF] and [START_REF] Talbi | Designing cellular networks using a parallel hybrid metaheuristic on the computational grid[END_REF] have again proposed extensions of these previous publications by deploying a parallel hybrid EA on a computational grid [START_REF] Berman | Grid Computing. Making the Global Infrastructure a Reality[END_REF]). This EA is hybrid because a local search is used to improve the solutions generated within the evolutionary loop. The parallelism is applied at different levels: the main EA model is an island model. Then, on each island, individuals undergo local search in parallel. The third level of parallelism considers each single function evaluation in parallel by decomposing the fitness function.

Conclusions and Future Work

Summary

This paper presents a survey on evolutionary algorithms for solving ACP problems. It shows the profile of this area by focusing on both the particular ACP problems tackled and the evolutionary approaches engineered to address them. The key issues on the design of EAs have been discussed: usually adopted representations, evolutionary operators, and advanced features such as hybridization and parallelism. Concretely, the crossover and mutation operators described in the literature have been analyzed, distinguishing between classical operators and ACP-targeted ones. Some hints on the advantages and disadvantages of several representation schemes have also been discussed.

In the next section which follows, some topics for future research to engineers interested in EAs for ACP problems are outlined. In the authors' opinion, these topics should deserve special attention so that the current state-of-the-art can be improved.

Future Trends

There are several research lines that can be explored to further address the ACP problem with EAs. At a lower algorithmic level, the design of new encodings and genetic operators for the problem, as well as the analysis of current existing ones, are of great interest. Concretely, the more complex encoding, the network encoding presented in Section 3.2, has only been evaluated with a few genetic operators (multilevel mutation and geographical crossover, mainly). Additional operator developments may take advantage of this ACP-targeted encoding. Evaluating this encoding and operators with the search engine of well-known algorithms such as NSGA-II or SPEA2 is also a matter of research.

At a higher algorithmic level, a promising research line is targeted to hybridizing EAs [START_REF] Talbi | A Taxonomy of Hybrid Metaheuristics[END_REF]), especially with other EAs. Up to now, EAs have been hybridized in the literature with local search algorithms (e.g., see [START_REF] Créput | Automatic mesh generation for mobile network dimensioning using evolutionary approach[END_REF], [START_REF] Talbi | Designing cellular networks using a parallel hybrid metaheuristic on the computational grid[END_REF]) or Tabu Search [START_REF] Chiara | Hybrid Meta-heuristic Methods in Parallel Environments for 3G Network Planning[END_REF]) to solve ACP problems, but hybrid algorithms involving two different EAs have not been found. The aim here would be to profit from the different search capabilities, for example, of a GA (diversification) and an evolution strategy (intensification). In the context of multiobjective EAs, hybridization is underexplored in the literature.

Checking whether other unused EAs can successfully address the ACP problem is a promising research topic as well. To the best of our knowledge, two main unused EAs have been left unexplored in the literature. On the one hand, no genetic programming approach has been found in the literature for ACP, even when this kind of EA performs well on other design problems [START_REF] Koza | Genetic Programming. On the Programming of Computers by Means of Natural Selection[END_REF], [START_REF] Koza | Invention and creativity in automated design by means of genetic programming[END_REF]). On the other hand, the cellular model of structured EAs [START_REF] Alba | Parallelism and Evolutionary Algorithms[END_REF]) has not been used either. Cellular EAs have been shown to be very effective in other domains [START_REF] Alba | Cellular Genetic Algorithms[END_REF]), so evaluating their enhanced search engine may lead to an improvement in the current state-of-the-art algorithms.

There are several additional studies whose conclusions may result in relevant outcomes especially for the telecommunication engineers that use EAs to solve their ACP problems. The analysis of both scalability and convergence speed of EAs on this problem also requires more investigations. The increasing size of cellular networks means EAs are faced with problem instances with thousand of decision variables. Therefore, evaluating the algorithms that perform better on very large instances is of great interest for cellular operators, since they can afford larger and more efficient network deployments. The study on how quickly EAs converge towards optimal solutions would also be of interest to the telecommunication industry. Indeed, execution time becomes a critical constraint for the operators and mainly for the software companies that are developing software for operators. Within commercial applications, reaching "good" solutions in a very short time is usually a must in order to provide operators with competitive software tools. These studies have to pay special attention to the statistical analysis of the results, which must be rigorously performed in order to draw useful conclusions. However, the works analyzed in this paper, for the most part lack such thorough analyses.

F

  of simpler techniques in the search of an optimum

  [START_REF] Chamaret | Graph based Modeling for automatic Transmitter location in Cellular Network[END_REF],[START_REF] Lieska | Radio coverage optimization with genetic algorithms[END_REF],[START_REF] Reininger | Multi-stage optimization for mobile radio network planning[END_REF]). However, the recent advances in multi-URL: http:/mc.manuscriptcentral.com/geno Email: A.B.Templeman@liverpool.ac.

Figure 2 .

 2 Figure 2. Summary of related works that address the ACP problem using EAs.

  et al. (2007),[START_REF] Calégari | A Parallel Genetic Approach to Transceiver Placement Optimisation[END_REF][START_REF] Calégari | Parallel island-based genetic algorithm for radio network design[END_REF][START_REF] Calégari | Combinatorial optimization algorithms for radio network planning[END_REF],[START_REF] Chamaret | Graph based Modeling for automatic Transmitter location in Cellular Network[END_REF],[START_REF] Lieska | Radio coverage optimization with genetic algorithms[END_REF],[START_REF] Lin | Cell planning scheme for WCDMA systems using genetic algorithm and measured background noise floor[END_REF],[START_REF] Molina | The automatic location of basestations for optimised cellular coverage: a new combinatorial approach[END_REF][START_REF] Mouly | Optimal Antenna Placement Using a New Multi-Objective CHC Algorithm[END_REF]), Vega- Rodríguez et al. (2007a,b).

Figure 3 .

 3 Figure 3. ACP-targeted encoding: all the parameter settings of the BTSs.

Figure 4 .

 4 Figure 4. Geographic recombination: sites located within the radius are exchanged.

Table 1 .

 1 EA approaches in the literature for the ACP problem (I).

	ACP	Search Space

-

[START_REF] Meunier | A multiobjective genetic algorithm for radio network optimization[END_REF]

,

[START_REF] Cahon | A parallel and hybrid multi-objective evolutionary algorithm applied to the design of cellular networks[END_REF]

,

[START_REF] Talbi | Hierarchical parallel approach for GSM mobile network design[END_REF]

,

[START_REF] Talbi | Designing cellular networks using a parallel hybrid metaheuristic on the computational grid[END_REF]

URL: http:/mc.manuscriptcentral.com/geno Email: A.B.Templeman@liverpool.ac.uk

Table 2 .

 2 EA approaches in the literature for the ACP problem (II).

	ACP	Search space

URL: http:/mc.manuscriptcentral.com/geno Email: A.B.Templeman@liverpool.ac.uk

Table 3 .

 3 EA approaches in the literature for the ACP problem (and III).

	ACP	Search space

URL: http:/mc.manuscriptcentral.com/geno Email: A.B.Templeman@liverpool.ac.uk

Table 4 .

 4 Details of EAs used for solving ACP problems.

	Ref.	Alg.	Encoding	Crossover	Mutation	LS	Parallel
	Calégari et al. (1996, 1997, 2001)	dGA	Binary	SPX	Bit flip	•
	Chamaret and Condevaux-Lanloy (1998)	dssGA	Binary	SPX	Bit flip	•
	Lieska et al. (1998)	genGA	Binary	SPX	Bit flip	•	•
	Molina et al. (1999)	genGA	Binary	SPX	Bit flip	•	•
	Reininger et al. (1999)	genGA	Network	SPX	Random	•	•
	Meunier et al. (2000), Cahon et al. (2006), Talbi and Meunier (2006), Talbi et al. (2007)	ssGA, hybrid	Network	Geographical	Multilevel
	Huang et al. (2000b)	GA	Binary	Fusion	Bit Flip	•	•
	Zimmermann et al. (2000, 2003a,b)	ES	Network	•	Especialized	•	•
	Lee and Kang (2000)	dGA	Group-based	Group-oriented	Group-oriented	•
	Han et al. (2001)	ssGA	Real	Distance-based	Random	•	•
	Laki et al. (2001)	genGA	Binary	Uniform	Bit flip	•	•
	Altman et al. (2002a,b), Jamaa et al. (2006)	GA	Network	Geographical	Multilevel	•	•
	Park et al. (2002)	ssGA	Real	Distance-based	Random	•	•
	Cerri et al. (2003, 2004), Cerri and Russo (2006)	GA	Binary	SPX	Bit flip	•	•
	Weicker et al. (2003)	SPEA2, NSGA-II, stEAPT	ACP-targeted	Especialized	Several Especialized	•	•
	Alba (2004), Alba and Chicano (2005)	ssGA, dssGA	Binary	DPX	Bit flip	•
	Brunetta et al. (2004), Chiara et al. (2005)	GA, hybrid	Binary	SPX	Bit flip	•	•
	Jamaa et al. (2004a,b), Picard et al. (2005)	NSGA-II	Network	Geographical	Multilevel	•	•
	Jedidi et al. (2004)	MOGA	Network	•	Multilevel	•	•
	Lin et al. (2004)	GA	Binary	Uniform	Bit flip	•	•
	Raisanen et al. (2004), Whitaker et al. (2004a,b), Raisanen and Whitaker (2005)	SEAMO, SPEA2, NSGA-II,PESA	Permutation	Cycle	Random Swap		•
	Zhang et al. (2004)	MOGA, EMOGA	Real	Multipoint	Random	•	•
	Créput et al. (2005)	Hybrid dES	ACP-targeted	Several Especialized	Macro-mutation		•
	Alba et al. (2007)	CHC, ssGA, genGA	Binary	HUX	Bit flip	•	•
	Nebro et al. (2007)	MOCHC, NSGA-II	Binary	HUX, SPX	Bit flip	•	•
	Vega-Rodríguez et al. (2007a,b)	CHC, PBIL, DE	Binary	HUX	Bit flip	•	•
	Raisanen (2008)	NSGA-II	Permutation	Cycle	Random Swap		•

Page 16 of 24 URL

	October 6, 2009 11:42 Engineering Optimization acp
	Engineering Optimization
	F o r
	P
	e
	e r
	R
	e
	v i e
	w
	O n l
	y

: http:/mc.manuscriptcentral.com/geno Email: A.B.Templeman@liverpool.ac.uk

  Innovation and FEDER under contract TIN2008-06491-C04-01, the M* project (http://mstar.lcc.uma.es). Juan J. Durillo is supported by the grant AP-2006-03349 from the Spanish government. Francisco Luna acknowledges support from the grant ES-2006-13075 funded by the Spanish government.

	October 6, 2009 11:42 Engineering Optimization acp October 6, 2009 11:42 Engineering Optimization acp October 6, 2009 11:42 Engineering Optimization acp October 6, 2009 11:42 Engineering Optimization acp
	20	REFERENCES
	o r F o r F o r F o r F o r
	P P P P P
	e e e e e
	e r e r e r e r e r
		R R R R R
		e e e e e
		v i e v i e v i e v i e v i e
		w w w w w
		O n l O n l O n l O n l O n l
		y y y y y

URL: http:/mc.manuscriptcentral.com/geno Email: A.B.Templeman@liverpool.ac.uk Engineering Optimization

Acknowledgments

This work has been partially funded by the "Consejería de Innovación, Ciencia y Empresa", Junta de Andalucía under contract P07-TIC-03044, the DIRI-COM project (http://diricom.lcc.uma.es), and the Spanish Ministry of Science and