A simulated annealing algorithm for the clustering problem pdf

To learn more, view our Privacy Policy. To browse Academia. Log in with Facebook Log in with Google. Remember me on this computer. Enter the email address you signed up with and we'll email you a reset link. Need an account? Click here to sign up. Download Free PDF. Hongmei He. A short summary of this paper. Box , FIN, Univ. Tampere, Finland Hongmei He, Dept. In a 1-page book drawing, all edges are placed on one side of the spine, and in a 2-page book drawing, all edges are placed either upon or below the spine.

The minimum number of edge crossings over all 1-page resp. The 1-page crossing number problem is to find a good order of vertices, and the 2-page crossing number problem is further to find a good edge distribution in the two pages. Both problems have been proved to be NP-hard [11, 12]. A lot of heuristic algorithms were designed for the 1-page and 2-page crossing number problem, see for instance [1, 6, 15, 16, 18] for the 1-page and [2, 3, 4, 8, 9, 13, 16] for the 2-page crossing number problem.

In this paper we design a simulated annealing algorithm starting with a good seed by the algorithm of Baur and Brandes [1] with the edge length strategy of dividing edges into two sets [3, 9]. The experimental data show that the simulated annealing algorithm achieves comparable or better results than evolution algorithms presented in the literature [7, 8]. Previous algorithms The best algorithm by Baur and Brandes [1] for the 1-page crossing number problem consists of greedy and sifting phases.

In the sifting phase, each vertex is moved along a fixed order of all other vertices. The vertex is then placed in its locally optimal position. The greedy and sifting phases can be implemented to run in O nm time for a graph with n vertices and m edges. Cimikowski [3] proposed an edge length heuristic for the fixed linear crossing number problem. Suppose that an initial permutation of the vertices is given.

The heuristic first orders all edges non-increasingly by their length in a list. Then edges are placed in the list order to a page where fewer crossings will be produced. By applying first the algorithm by Baur and Brandes to construct an initial permutation and then the edge length strategy to divide edges into two pages, gave good approximations in the experiments by He et al. Algorithm 1 A simulated annealing algorithm for the 2-page crossing number problem. Select a frozen temperature t1 and an equilibrium detection rate r.

The simulated annealing algorithm Simulated annealing SA optimisation method imitates the cooling process of material in a heat bath. The main principles of the SA were first introduced in an article by Metropolis et al. The basic idea behind the SA algorithms is to choose an initial solution, denoted by s0 , and then to try to improve this solution. Publication Type.

More Filters. View 1 excerpt, cites methods. Particle swarm optimization for mobile ad hoc networks clustering. An ant colony optimization algorithm for multi-objective clustering in mobile ad hoc networks.

Hence, for an energy efficient and stable communication to be … Expand. A probability collectives approach to weighted clustering algorithms for ad hoc networks.

Communications and Computer Networks. View 3 excerpts, cites background. Highly Influenced. View 4 excerpts, cites background and methods. View 2 excerpts, cites background and methods. View 3 excerpts, cites methods and background. Optimizing clustering algorithm in mobile ad hoc networks using genetic algorithmic approach. Global Telecommunications Conference, View 1 excerpt, references methods. Cluster Computing.

View 2 excerpts, references background and methods. An on-demand weighted clustering algorithm WCA for ad hoc networks. Globecom '00 - IEEE. Global Telecommunications Conference. Conference Record Cat. Thermodynamical approach to the traveling salesman problem: An efficient simulation algorithm. We present a Monte Carlo algorithm to find approximate solutions of the traveling salesman problem.

The algorithm generates randomly the permutations of the stations of the traveling salesman trip, … Expand. Adaption of simulated annealing to chemical optimization problems. Demonstrates the use of simulated annealing SA in a wide range of chemical problems, covering the potentiality of SA, GSA, and other modifications of SA to serve specific needs in a variety of … Expand.

View 1 excerpt. Thermodynamical approach to the traveling salesman problem.