Multiobjective Tabu Search for Clustering and the Zoning Problem

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.

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 the next section.

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:

Where represents the feasible space, that is the set of all valid solutions, the solutions that fulfill every constraint of the problem.

A vector is said to dominated another vector, denoted if and only if .

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 is said to be Pareto optimal iff such that. 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.

Dissimilarity matrixes

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.

III. 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 , where is the number of BGAs, the number of clusters and indicates that object (region in our case) is located at cluster. The other array centers of length, contains every center. The neighborhood of a given solution denoted is obtained by swapping all pairs of elements, where, is any center and any element, so having as a solution implies.

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 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 center.

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.

In this formula represents the Euclidean distance, represents a center and the set of elements that belong to a cluster with center.

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 a group with respect to some variable, we count the number of 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.

Where represents the number of elements with the correct value on the variable being homogeneity in group and represents the ideal value.

Now that we stated the optimization model is time to 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 only the intra-class objective).
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.
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
4. Get the new solutions to PSET for verification.
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:

Table 1 - Toluca Valley territorial design 

We can appreciate from table 1 that the results were rather satisfactory. The Pareto Frontier of the previous solutions (Pareto Set) is represented in the next graphic.

V. Comparisons

The comparisons were made against a VNS (Variable Neighborhood Search) algorithm associated with the same problem. As the following results showed, Tabu Search is superior in a lot of aspects (homogeneity, compactness, number of solutions, etc.)

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.

References

[1]     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”.

[2]     Beausoleil P. Ricardo, “Multiobjective clustering using Tabu Search”, Institute of Cybernetics, Mathematics and Physics.

[3]     Talbi El-Ghazali, Metaheuristics: from design to implementation. New Jersey: Wiley and Sons, 2009, ch. 2.