A Study of Various Multi Objective Techniques in Simulated Annealing

A Study of Various Multi Objective Techniques in Simulated Annealing

Lalin L. Laudis

Post Graduate Scholar

Department of Electronics and Communication Engineering Vel Tech Dr.RR & Dr.SR Technical University

Avadi, Chennai

Abstract Simulated Annealing (SA) is a popular search algorithm used in generic optimization problems to find an optimized solution. Most of the NP hard problems are intractable, that is, exact solution cannot be found within a satisfactory period of time. In such cases it is enough to find an optimized solution rather than finding the exact solution. Because, in search space optimized solution lies nearer to the exact solution. In real life, most of the problems have more than one objectives. These can be solved by two methods, namely single objective optimization and multi-objective optimization method. The major difference between these two methods is that, the former method ends up with only one optimized solution, but the later method gives a set of optimized solution called pareto- optimal (PO) solution. Pareto-optimal set has several choices and so the user could go for a clear decision. Also in single objective technique, it is necessary to run the algorithm repeatedly to obtain the entire set of optimum solution (PO solution). This excessive computational time requirement can be avoided in the case of multi-objective optimization technique. This project works aims to study the various possibilities of multi-objective techniques related to simulated annealing. Eventhough several studies were made related to multi-objective techniques in SA, it requires a detailed study in certain areas like computational time, clustering in domination, exploration capability, trapping in local optima etc. Contribution towards this project work will address the above mentioned research gaps

Keywords Simulated Annealing, NP Hard problems, Pareto optimal solution. Multi objective optimization.

1. INTRODUCTION

   Optimization is a procedure of finding a feasible solution until no better solution can be found. The presence of multiple conflicting objectives is natural in many problems and makes the optimization problems interesting to solve. Hence these problems are referred to as multi objective optimization (MOO) problems. Since no one solution can be termed as an optimum solution to multiple conflicting objectives, the resulting MOO problem resorts to a number of trade-off optimal solutions. In classical optimization problems the several objectives of a MOO problem are made to a single objective problem and solved. In later there are several algorithms found to solve MOO problems more efficiently. One of such algorithms is simulated annealing (SA).

2. EVOLUTIONARY ALGORITHMS (EA) Evolutionary algorithms [5] were capable of finding multiple optimal solutions in one single simulation due to their population-approach. Thus EAs are ideal candidates for solving MOO problems. In classical based approach of solving a MOO problem a preference based approach is adopted

   where a relative based vector is used to scalarize multiple objectives. Since classical search and optimization methods use a point-by-point approach, where one solution in each iteration is modified to a different (hopefully better) solution, the outcome of using a classical optimization is called a single objective optimization. In a single objective optimization method only a single optimized solution could be found, it was therefore necessary to convert a task of finding a multiple trade-off solutions in a MOO to one of finding a single solution of a transformed single-objective optimization problem.

   The field of search and optimization has changed over a last few years by the introduction of a number of non- classical, unorthodox and stochastic search and optimization algorithms. One of these is EAs use evolutionary principles to drive its search towards an optimal solution. One of the most striking differences between classical methods and EAs is that EAs use a population of solution in each iteration, the outcome is also a population of solutions.

3. GENITIC ALGORITHMS (GA)

   Genetic algorithms (GAs) are an eective tool for uni-objective optimization. GAs perform in a manner similar to evolutionary strategies, but are characterized by their dierent methods for generating new solutions, and for selecting the population for subsequent generations. It is also usual to binary-encode the decision vector in a GA, although they may be left in their real form, as in an ES. Solutions may be generated through either mutation or crossover. Crossover occurs between two parents and involves the (random) recombination of their parameters, or sequences of their binary encoding to create ospring. Mutation usually occurs through the ipping of a random selection of the bits in a binary encoding, but can also occur through random perturbation of a real encoding. When a solution survives into a subsequent generation of a GA, it is considered to have undergone reproduction, as each solution in a generation is then a new individual, in common with natural evolution. The mutation operator is used to permit exploration of search space, while the crossover operator is intended to combine promising elements of solutions into a child. A genetic algorithm is considered to be Elitist if it maintains the best solutions located so far in the search, allowing these to participate in the generation of the new solutions, ensuring that the algorithm does not lose this information of good solutions. The selection method used in the GAs discussed here is binary tournament

   selection; when solutions are to be selected for the population of the next generation, they are paired o randomly and the lter of the two solutions survives into the next generation. A more extensive introduction to genetic algorithms is provided by Mitchell [1996].

4. MULTI OBJECTIVE OPTIMIZATION

   As the name suggests, a multi objective optimization problem (MOOP) [5] deals with more than one objective function. In most practical decision making problems, multiple objective or multiple criteria are evident. Because of a lack of suitable solution methodologies, an MOOP has been mostly cast and solved as a single objective optimization problem. However , there exist a number of fundamental difference between the working principles of single and multi objective optimization algorithms. In a single objective optimization problem, the task is to find one solution which optimizes the sole objective function. The idea can be extended in MOOP to find a range of multiple solution set called pareto optimal (PO) set.

5. SIMULATED ANNEALING

   Simulated annealing (SA) is a compact and robust technique, which provides excellent solutions to single and multiple objective optimization problems with a substantial reduction in computation time. It is a method to obtain an optimal solution of a single objective optimization problem and to obtain a Pareto set of solutions for a multi-objective optimization problem. It is based on an analogy of thermodynamics with the way metals cool and anneal. If a liquid metal is cooled slowly, its atoms form a pure crystal corresponding to the state of minimum energy for the metal. The metal reaches a state with higher energy if it is cooled quickly. SA has received signicant attention in the last two decades to solve optimization problems, where a desired global minimum/maximum is hidden among many poorer local minima/maxima. Kirkpatrick et al (1983) and Cerny (1985) showed that a model for simulating the annealing of solids, proposed byMetropolis et al (1953), could be used for optimization of problems, where the objective function to be minimized corresponds to the energy of states of the metal. These days SA has become one of the many heuristic approaches designed to give a good, not necessarily optimal solution. It is simple to formulate and it can handle mixed discrete and continuous problem with ease. It is also efficient and has low memory requirement. SA takes less CPU time than genetic algorithm (GA) when used to solve optimization problems, because it nds the optimal solution using point-by- point iteration rather than a search over a population of individuals. Initially, SA has been used with combinatorial optimization problems. Many combinatorial problems belong to a class known as NP-hard problems, which means that the computation time, giving an optimal solution, increases with

   N. Mafoli (1987) showed that SA can be considered as one type of randomized heuristic approaches for combinatorial optimization problems. The well-known travelling salesman problem belongs to thisclass. The salesman visits N cities (with given positions) only once and returns to his city of origin. The objective is to make the route as short as possible.

   Afterwards, SA has been extended to the single and multi- objective optimization problems with continuous N- dimensional control spaces. A summary of these approaches is given by Van Laarhoven and Aarts (1987). Glover and Greenberg (1989) summarized the approaches offered by GA, neural networks, tabu search, targeted analysis and SA. Surveys of the literature on different evolutionary and metaheuristic based methods and their applications are compiled by Coello Coello (1996, 1999) and van Veldhuizen and Lamont (1998, 1998). Despite the considerable volume of research in single and multi-objective algorithms based on SA in the last two decades, no survey has been published in the literature that includes the multi-objective framework. Surveys on single objective SA have been performed but few multi- objective algorithms to improve the performance of the SA have been proposed in the recent years.

6. CLUSTERING

   Clustering is an important technique used in the MOO process. [1]Clustering can be considered the most important unsupervised learning problem; so, as every other problem of this kind, it deals with finding a structure in a collection of unlabeled data. A loose definition of clustering could be the process of organizing objects into groups whose members are similar in some way[1]. A cluster is therefore a collection of objects which are similar between them and are dissimilar to the objects belonging to other clusters. We can show this with a simple graphical example:

   Fig : clustering illustrate

   In this case we easily identify the 4 clusters into which the data can be divided; the similarity criterion is distance: two or more objects belong to the same cluster if they are close according to a given distance (in this case geometrical distance). This is called distance-based clustering. Another kind of clustering is conceptual clustering: two or more objects belong to the same cluster if this one defines a concept common to all that objects. In other words, objects are grouped according to their fit to descriptive concepts, not according to simple similarity measures.

   Accept new solution

   Yes

   multi-objective optimization is their population based nature and ability of finding multiple optima simultaneously. Simulated Annealing (SA) another popular search algorithm, utilizes the principles of statistical mechanics regarding the behavior of a large number of atoms at low temperature, for finding minimal cost solutions to large optimization problems by minimizing the associated energy. In statistical mechanics investigating the ground states or low energy states of matter is of fundamental importance. These states are achieved at very low temperatures. However, it is not sufficient to lower the temperature alone since this results in unstable states. In the annealing process, the temperature is rest raised, then decreased gradually to a very low value (Tmin), while ensuring that one spends sufficient time at each temperature value. This process yields stable low energy states. Geman and Geman provided a proof that SA, if annealed sufficiently slowly, converges to the global optimum. Being based on strong theory SA has been applied in diverse areas by optimizing a single criterion. However there have been only a few attempts in extending SA to multi-objective optimization, primarily because of its search-from-a-point nature.. The problem in most problems here is how to choose the weights in advance. Some alternative approaches have also been used in this regard. In D. K. Nam and C. Parks work and E. L. Ulungu, J. Teghaem, P. Fortemps, and D. Tuyttenss work of different non-linear and stochastic composite energy functions have been investigated. In D. K. Nam and C. Parks work six different criteria for energy difference calculation are suggested and evaluated. These are (1) minimum cost criterion, (2) maximum cost criteria, (3) random cost criteria,

   Update stores

   Access new solution

   Generate new solution

   Estimate initial temperature

   Input and access initial solution

   (4) self cost criteria, (5) average cost criteria, and (6) axed cost criteria. Since each run of the SA provides just a single solution, the algorithm attempted to evolve the set of PO solutions by using multiple SA runs. As a result of the independent runs, the diversity of the set of solutions suffered. Multi-objective simulated annealing with a composite energy clearly converges to the true Pareto front if the objectives have

   ratios given by w -1 i , if such points, in general, exist. Here w

   Adjust temperature

   i i

   NO

   Stop

   yes

   is the weight assigned to the ith objective. In research, it has been proved that part of the front will be inaccessible with axed weights. In research several different schemes were explored for adapting the wis during the annealing process to encourage exploration along the front. However, a proper choice of the wis remains challenging task.

   Fig.: Simulated annealing algorithm

7. MOO USING SIMULATED ANNEALING

   The multi-objective optimization (MOO) problem has a rather different perspective compared to one having a single objective. In single-objective optimization there is only one global optimum, but in multi-objective optimization there is a set of solutions, called the Pareto-optimal (PO) set, which are considered to be equally important; all of them constitute global optimum solutions[2]. The main reason for the popularity of Evolutionary algorithms (EAs)[3] for solving

8. PROPOSED METHODOLOGY

   The AMOSA [7] algorithm was found to be more efficient but it is identified that the clustering part is the time consuming and the hardest part. It was realized that improving the clustering part would improve the efficiency of the algorithm and minimize the time consumption. Hence it was decided to concentrate on the clustering part. With this decision several clustering algorithms similar to Single linkage clustering was studied and the clustering part would be improved based on consumption of time. A better clustering

   algorithm would be identified and tested in the AMOSA algorithm and its efficiency would be found to be increased based on convergence and computational time. The proposed clustering time would be found to be reduced and the convergence was increased. The algorithm was implemented with k- means clustering technique. The proposed algorithm is given below.

9. CONCLUSION AND FUTURE ENHANCEMENT Finally the improved clustering technique named k-means

technique would find better results when compared with the previous results. The proposed algorithm has wide range of application in the field of engineering like VLSI, MIMO etc. The specified fields has seveal aspects to be optimized and that too has multi objectives. Hence this algorithms would be more sophisticated for engineering application. The algorithm can also be improvised in several means like computational time and other aspects like number of iteration. Implementation of AMOSA with unconstrained archive is another interesting area to pursue in future. An algorithm, unless analyzed theoretically, is good for only the experiments conducted. Thus a theoretical analysis of AMOSA needs to be performed in the future in order to study its convergence properties. there are no firm guidelines for choosing the parameters in an SA-based algorithm. Thus, an extensive sensitivity study of AMOSA with respect to its different

parameters, notably the annealing schedule, needs to be performed. Finally, application of AMOSA to several real life domains e.g., VLSI system design, remote sensing imagery, data mining and Bioinformatics , needs to be demonstrated.

REFERENCES

1. A. K. Jain and R. C. Dubes, 1988,Algorithms for Clustering Data.

   Englewood cliffs, NJ, prentice Hall

2. A. Suppapitnarm, K. A. Seffen, G. T. Parks, and P. Clarkson, .A simulated annealing algorithm for multiobjective optimization, 2000.. Engineering Optimization, vol. 33, pp. 59.85.

3. D. K. Nam and C. Park, 2000 .Multiobjective simulated annealing: a comparative study to evolutionary algorithms,. Int. J. Fuzzy Systems, vol. 2, no. 2, pp. 87.97.

4. E. L. Ulungu, J. Teghaem, P. Fortemps, and D. Tuyttens, 1999..MOSA method: a tool for solving multiobjective combinatorial decision problems, . J. multi-criteria decision analysis, vol. 8, pp. 221.236.

5. K. Deb, 2001Multi-objective Optimization Using Evolutionary Algorithms.England: John Wiley and Sons, Ltd,

6. M. Hapke, A. Jaszkiewicz, and R. Slowinski, 2000 .Pareto simulated annealing for fuzzy multi- objective combinatorial optimization,. Journal of Heuristics, vol. 6, no. 3, pp. 329.345.

7. Sanghamitra Bandyopadhyay1, Sriparna Saha, Ujjwal Maulik2 and Kalyanmoy Deb, Sept. 2011A simulated annealing based multiobjective optimization algorithm systems, man and cybernetics ,

   PART C: Application and reviews , IEEE transactions

8. S. Kirkpatrick, C. Gelatt, and M. Vecchi, 1983.Optimization by simulated annealing,. Science, vol. 220, pp. 671.680.