(1) ? JC-ICIMAF Multiobjective Tabu Search for the zoning problem
Arnaldo Pérez Havana University, Cuba,
arnaldo.skywalker@gmail.com Abstract: This document describes a
tabu Search algorithm embedded in a multiobjective framework
capable of finding solutions to the zoning problem by allowing
the optimization of multiple objectives. The compactness meaning
the cluster given to the set of objects (territorial units for a
zoning problem) represents one of those objectives to be
optimize, the other, homogeneity meaning a balance in the
distribution of several variables that each object in the problem
possesses and are selected as input for the algorithm, both
objectives are being minimize. Keywords: clustering, compactness,
homogeneity, multiobjective optimization, tabu search, zoning.
2013 I. INTRODUCTION Zoning is a technique that belongs to the
area of urban studies; it appeared for the first time in the XIX
century to separate the residential areas from the industrials.
The main idea with this technique, the most popular in
urbanization, is to produce a partition of homogeneous regions
according to some criteria. In our case each variable matches a
criteria and each basic geostatical area possesses a collection
of values each representing the value for some variable. These
variables could be demographic, for instance people who are older
than twenty. A basic geostatical area (BGA) is the manner in
which will refer to a basic or primitive region to be clustered.
Any BGA consist of a pair (position, variables_values) where
position marks the location of the area in space (usually two
coordinates) and variables_values represent a list of values for
every variable in the problem. Tabu Search is a metaheuristic
created by Fred Glover that inherits from local search a popular
optimization method. It’s common to see it applied to
combinatory optimization in problems such as TSP (Travelling
Salesman Problem) or QAP (Quadratic Assignment Problem). The use
of metaheuristics to solve the zoning problem, as well as the TSP
is mandatory, because of their NP Complete nature. In fact most
of the time, we don’t find optimal solutions, but
approximations to these optimal solutions and sometimes if we are
lucky, this approximations might equaled some optimal solution.
Our tabu search is embedded in a multiobjective framework; this
implies that several objective functions are being optimized, all
at once. Because this is a multiobjective algorithm its main goal
is to find non dominated solutions. Any unknown definition
we’ve seen so far will be covered in II. PRELIMINARY AND
DEFINITIONS In this section we define theoretical aspects that we
considered relevant and necessary for understanding the contents
of this paper. Many optimization problems often involve multiple
objective functions such problems are known as Multiobjective
Optimization Problem (MOP). It can be stated as follows: min F (
x) ? ( f1 ( x), f 2 ( x),…, f m ( x)) x ? ? Where ? represents
the feasible space, that is the set of all valid solutions, the
solutions that fulfill every constraint of the problem. A vector
u ? (u1 , u2 ,…, um ) is said to dominated another vector v ?
(v1 , v2 ,…, vm ) , denoted u ? v if and only if ?i ?{1,.., m},
ui ? vi , u ? v . Having multiple objectives denotes an important
issue. The improvement of one objective function could lead to
the deterioration of another. Thus a solution that will optimize
every objective rarely exists, so instead of looking for that
solution a trade-off is searched. Pareto optimal solutions
represent this trade-off. A feasible solution x is said to be
Pareto optimal iff ?y ? ? such that F ( y) ? F ( x) . The set of
all Pareto optimal solutions is known as the Pareto set and its
image the Pareto frontier. The algorithm proposed in this paper
finds an approximation to a set of Pareto optimal solutions
forming a Pareto frontier. The next section describes the Tabu
Search with all of its components. the next section.
Dissimilarity matrixes 1
III. center. (2) (3) JC-ICIMAF 2013 In this work we considered
using two dissimilarity matrixes, one for the coordinates of each
region and another for the value of every variable in each
region. TABU SEARCH Tabu Search (TS) is a metaheuristic presented
by Glover which uses adaptive memory and responsive exploration.
Inherits from local search (LS); probably the oldest and simplest
metaheuristic method ever. It could be said that Tabu Search is
just a local search with some considerable improvements or
upgrades. Its core functionality is the same as LS; starts at a
given initial solution (usually generated randomly), it runs
until a stopping rule is reached and each iteration replaces the
current solution by another which improves the objective
function, and is found in the neighborhood of the current
solution. The stopping rule for LS is reached when no neighbor of
the current solution improves the objective function meaning we
have a local optimum. This the main disadvantage for LS; it only
finds local optimum, a disadvantage Tabu Search does not shared
as it includes mechanism for diversification which prevents it
from getting stuck into a local optimum. Encoding and
neighborhood A solution is encoded as a pair (elements, centers),
first an array of length n ? k , where n is the number of BGAs, k
the number of clusters and xi indicates that object (region in
our case) i is located at cluster xi . The other array centers of
length k , contains every center. The neighborhood of a given
solution x denoted N (x) is obtained by swapping all pairs of
solutions. In TS these mechanisms are expressed in the
medium-term memory and in the long-term memory or freq memory.
Intensification is managed by the medium-term memory, storing the
best solutions ever to be found. Diversification is handled by
the freq-memory showing how many times a given element has been
included in a solution as Our algorithm uses freq-memory to favor
objects (regions) with the lowest frequency as centers in a
diversification phase. Solving the optimal zoning problem Tabu
Search is embedded into a multiobjective framework, so in order
to solve the problem we have to take into account several
objective functions. The first of these functions minimizes the
intra-class distance that is, the distance of every object to the
center of its class or cluster. k min ? d (ci , e) ?e ? e(ci ) i
?1 In this formula d ( x, y) represents the Euclidean distance,
ci represents a center and e(ci ) the set of elements that belong
to a cluster with center ci . The second objective considers the
homogeneity of a solution. Homogeneity means that elements
belonging to the same cluster shared some characteristics, in
this case the value of some variables. When we partition under
the criteria of homogeneity the idea is to find a balance or
equilibrium in every cluster for each variable, so the actual
function to be optimize is the balance of homogeneity. To find
the balance of elements (i, j) , where, i is any center and j any
element, so a group with respect to some variable, we count the
number of having s ? ((e1 , e2 ,…, en?k ), (c1 ,…, ck )) as a
solution implies ((c1 , e2 ,…, en?k ), (e1 ,…, ck )) ? N (s)
. Adaptive memory This is probably the most important
characteristic of Tabu Search: its capacity to remember the
evolution of the search, accomplished through the use of data
structures. Tabu list, represents one of these data structures,
used to save pairs previously swapped, avoiding the possibility
of cycling around the same solutions, at least for some time (the
length of the list must be finite because memory is finite). The
term intensification refers to a mechanism that many
metaheuristic implement to favor the exploitation of the best
solutions found so far, in this case the more promising regions
are explored more thoroughly, diversification on the other hand
refers to exploration of the search space, trying to visit
unexplored 2 elements having the desired value for that variable
and subtract that amount from the ideal value; which occurs when
all of the elements in the group have the desired value. The sum
of every group balance represents the balance of homogeneity to
be minimized. For each variable we’d like to homogeneity a
balance of homogeneity function should be added to the
optimization model, so if we want to homogeneity three variables,
our model will have four objectives, the intra-class function and
one balance of homogeneity function for every variable. min ?[V
(ci ) ? V * (ci )] ?i ?{1,…, k} Where V (ci ) represents the
number of elements with the correct value on the variable being
homogeneity in group ci and V * (ci ) represents the ideal value.
Now that we stated the optimization model is time to
TABLE 1 JC-ICIMAF 2013 described TS’s strategy for finding
non dominated solutions and building a Pareto Frontier. The
strategy is divided into three different stages. 1. A clustering
of the regions is found (we optimize 2. Generate the neighborhood
of the current solution. 3. If there is a solution that improves
the current solution then select it as the new current solution.
If not then enter into a diversification phase. only the
intra-class objective). 4. Get the new solutions to PSET for
verification. 2. Once we have a clustering its homogeneity is
calculated. 3. We check to see whether this solution is
nondominated, if it’s, we added using PSET (we’ll see
what this means shortly) otherwise we do nothing. Seeing the
strategy in these steps makes it look very simple. We separate
the intra-class optimization from the homogeneity optimization
and then verify the nondominated nature of the new solutions.
PSET PSET (Pareto Set) is the component of the algorithm that
takes care of building the Pareto Set. Once a solution has been
found PSET will verify if this solution is “suitable”
to be consider in the set of solutions. Suitable means that is
not duplicated (already in PSET) and nondominated. If the
solution happens to be nondominated then we might need to remove
some old solutions in PSET that no longer classify as Pareto
optimal because they are now dominated by the incoming solution.
PSET has a tolerance rate ? (set to 0 by default) as a parameter
that could allow the inclusion of solutions in PSET that are
actually dominated, but very close to some nondominated solution
(their difference is less than or equal to ? ). Stopping Rule The
stopping rule, as the name suggests, defines the moment or
iteration when the algorithm should stop. In our case we’ve
fixed a number of iterations and if we reached that amount of
iterations the algorithm will stop. However there’s another
condition for stopping the algorithm and that is when new
nondominated solutions stopped coming also during a fixed number
of iterations. Algorithm This is a skeleton for the TS algorithm:
1. Randomly generate an initial solution. 3 5. Go to 3 until a
stopping rule is reached. IV. RESULTS In order to test the
algorithm, a real-world problem has been used. It’s
illustrated as follows: the BGAs of the metropolitan area of
Toluca Valley are going to be clustered into five homogeneous
groups that only include elements whose variables have values in
the ranges indicated below. ? Male Population under 6 years
(X001). ? Male population between 6 and 11 years (X003). ? Male
population between 15 and 17 (X007). The homogeneity will be
obtained in all three variables. Tabu Search has run several
iterations with this example getting the following results:
TOLUCA VALLEY TERRITORIAL DESIGN Toluca Valley results for
homogeneity and compactness. As we can appreciate from table 1
the results were rather satisfactory. V. CONCLUSIONS
Multiobjective problems arise in many real world problems; this
paper has focus on one of those problems namely the zoning
problem. Tabu Search proved to be an efficient method for solving
this problem by giving some interesting results in the
experiments. Among the different metaheuristics you might find
today we selected Tabu Search because of its extraordinary
condition as a method of intelligent search. We hope that future
work on the zoning problem would result in new methods, ideas and
comparisons with our TS.
[1] [2] [3] REFERENCES Bernábe Loranca B., Coello Coello
A.C., Osorio Lama M.,“A multiobjective approach for the
heuristic optimization of compactness and homogeneity in the
optimal zoning”. Beausoleil P. Ricardo,
“Multiobjective clustering using Tabu Search”,
Institute of Cybernetics, Mathematics and Physics. Talbi
El-Ghazali, Metaheuristics: from design to implementation. New
Jersey: Wiley and Sons, 2009, ch. 2. 4 JC-ICIMAF 2013