Loading [MathJax]/jax/output/HTML-CSS/config.js
A metaheuristic based on fusion and fission for partitioning problems | IEEE Conference Publication | IEEE Xplore

A metaheuristic based on fusion and fission for partitioning problems

Publisher: IEEE

Abstract:

Metaheuristics are very useful methods because they can find (approximate) solutions of a great variety of problems. One of them, which interests us, is graph partitionin...View more

Abstract:

Metaheuristics are very useful methods because they can find (approximate) solutions of a great variety of problems. One of them, which interests us, is graph partitioning. We present a new metaheuristic based on nuclear fusion and fission of atoms. This metaheuristic, called fusion fission, is compared to other classical algorithms. First, we present spectral and multilevel algorithms which are used to solve partitioning problems. Secondly, we present two metaheuristics applied to partitioning problems: simulated annealing and ant colony algorithms. We show that fusion fission gives good results, compared to the other algorithms. We demonstrate on a problem of air traffic control that metaheuristics methods can give better results than specific methods
Date of Conference: 25-29 April 2006
Date Added to IEEE Xplore: 26 June 2006
Print ISBN:1-4244-0054-6
Print ISSN: 1530-2075
Publisher: IEEE
Conference Location: Rhodes, Greece

1 The Partitioning Problem

Graph partitioning is a fundamental problem for many scientists. This problem arises in many graphs applications and consists in dividing the vertices into several sets of roughly equal “size” in such a way that the weight of edges between sets is as small as possible. A classical application of graph partitioning is parallel computing, to reduce the communication between processors. But applications of graph partitioning include also VLSI design, data clustering, image segmentation, and mesh partitioning of a 2D surface of an airfoil. A new partitioning problem consists of a new organization of the European airspace. This is the Functional Airspace Block Optimized Process (FABOP) project. We will see more precisely this subject in section 5.

References

References is not available for this document.