Multi-objective Optimization of Graph Partitioning using Genetic Algorithm
Graph partitioning is a NP-hard problem with multiple
conflicting objectives. The graph partitioning should minimize the
inter-partition relationship while maximizing the intra-partition
relationship. Furthermore, the partition load should be evenly
distributed over the respective partitions. Therefore this is a multiobjective
optimization problem (MOO). One of the approaches to
MOO is Pareto optimization which has been used in this paper. The
proposed methods of this paper used to improve the performance are
injecting best solutions of previous runs into the first generation of
next runs and also storing the non-dominated set of previous
generations to combine with later generation's non-dominated set.
These improvements prevent the GA from getting stuck in the local
optima and increase the probability of finding more optimal
solutions. Finally, a simulation research is carried out to investigate
the effectiveness of the proposed algorithm. The simulation results
confirm the effectiveness of the proposed method.
[1] Nguyen Thang, Ro Moon Byung, "Genetic Algorithm and Graph
Partitioning", IEEE Transaction on Computers 1996.
[2] E. Zitzler, K. Deb, and L. Thiele, "Comparison of multiobjective
evolutionary algorithms: Empirical results.,"Evolutionary Computation,
vol. 8, pp. 173-195, 2000.
[3] Coello Coello, Carlos A. A Comprehensive Survey of Evolutionary-
Based Multiobjective Optimization Techniques, Knowledge and
Information Systems, Vol. 1, No. 3, pp. 269-308, August 1999.
[4] D.Goldberg. Genetic Algorithms in search, optimization and machine
learning. Reading, Mass., Addison-Wesley, 1989.
[5] K. Deb, S. Agrawal, A. Pratab, and T. Meyarivan, "A Fast Elitist Non-
Dominated Sorting Genetic Algorithm for Multi-Objective Optimization:
NSGA-II," presented at Parallel Problem Solving from Nature VI
Conference, Paris, France, 2000.
[6] Songerwala, M., 1994. Efficient solutions to the network division
problem. Ph.D. Thesis, Department of Computer Science, Curtin
University of Technology.
[7] Holland, J. H. 1975. Adaptation in Natural and Artificial Systems. Ann
Arbor: University of Michigan Press.
[8] K.Bryant, Genetic Algorithms and the Traveling Salesman Problem,
Thesis, Harvey Mudd College, Dept. of Mathematics, 2000.
[9] E. Cantu-Paz, A Survey of Parallel Genetic Algorithms, IlliGAL Report
No. 97003, May 1997.
[10] Philipp Limbourg and Daniel E. Salazar Aponte. An Optimization
Algorithm for Imprecise Multi-Objective Problem Functions, IEEE
Congress on Evolutionary Computation, CEC2005, 2005.
[11] Krommenacker, N.; Rondeau, E.; Divoux, T.Factory Communication
Systems, 2002. 4th IEEE International Workshop on Volume, Issue,
2002 Page(s): 149 - 156.
[12] Salcedo-Sanz, S.; Xin Yao Systems, Man, and Cybernetics, Part B, IEEE
Transactions on Volume 34, Issue 6, Dec. 2004 Page(s):2343 - 2353.
[1] Nguyen Thang, Ro Moon Byung, "Genetic Algorithm and Graph
Partitioning", IEEE Transaction on Computers 1996.
[2] E. Zitzler, K. Deb, and L. Thiele, "Comparison of multiobjective
evolutionary algorithms: Empirical results.,"Evolutionary Computation,
vol. 8, pp. 173-195, 2000.
[3] Coello Coello, Carlos A. A Comprehensive Survey of Evolutionary-
Based Multiobjective Optimization Techniques, Knowledge and
Information Systems, Vol. 1, No. 3, pp. 269-308, August 1999.
[4] D.Goldberg. Genetic Algorithms in search, optimization and machine
learning. Reading, Mass., Addison-Wesley, 1989.
[5] K. Deb, S. Agrawal, A. Pratab, and T. Meyarivan, "A Fast Elitist Non-
Dominated Sorting Genetic Algorithm for Multi-Objective Optimization:
NSGA-II," presented at Parallel Problem Solving from Nature VI
Conference, Paris, France, 2000.
[6] Songerwala, M., 1994. Efficient solutions to the network division
problem. Ph.D. Thesis, Department of Computer Science, Curtin
University of Technology.
[7] Holland, J. H. 1975. Adaptation in Natural and Artificial Systems. Ann
Arbor: University of Michigan Press.
[8] K.Bryant, Genetic Algorithms and the Traveling Salesman Problem,
Thesis, Harvey Mudd College, Dept. of Mathematics, 2000.
[9] E. Cantu-Paz, A Survey of Parallel Genetic Algorithms, IlliGAL Report
No. 97003, May 1997.
[10] Philipp Limbourg and Daniel E. Salazar Aponte. An Optimization
Algorithm for Imprecise Multi-Objective Problem Functions, IEEE
Congress on Evolutionary Computation, CEC2005, 2005.
[11] Krommenacker, N.; Rondeau, E.; Divoux, T.Factory Communication
Systems, 2002. 4th IEEE International Workshop on Volume, Issue,
2002 Page(s): 149 - 156.
[12] Salcedo-Sanz, S.; Xin Yao Systems, Man, and Cybernetics, Part B, IEEE
Transactions on Volume 34, Issue 6, Dec. 2004 Page(s):2343 - 2353.
@article{"International Journal of Information, Control and Computer Sciences:60364", author = "M. Farshbaf and M. R. Feizi-Derakhshi", title = "Multi-objective Optimization of Graph Partitioning using Genetic Algorithm", abstract = "Graph partitioning is a NP-hard problem with multiple
conflicting objectives. The graph partitioning should minimize the
inter-partition relationship while maximizing the intra-partition
relationship. Furthermore, the partition load should be evenly
distributed over the respective partitions. Therefore this is a multiobjective
optimization problem (MOO). One of the approaches to
MOO is Pareto optimization which has been used in this paper. The
proposed methods of this paper used to improve the performance are
injecting best solutions of previous runs into the first generation of
next runs and also storing the non-dominated set of previous
generations to combine with later generation's non-dominated set.
These improvements prevent the GA from getting stuck in the local
optima and increase the probability of finding more optimal
solutions. Finally, a simulation research is carried out to investigate
the effectiveness of the proposed algorithm. The simulation results
confirm the effectiveness of the proposed method.", keywords = "Graph partitioning, Genetic algorithm, Multiobjective
optimization, Pareto front.", volume = "3", number = "5", pages = "1413-6", }