Title :
A hybrid genetic algorithm for the minimum interconnection cut problem
Author :
Maolin Tang ; Shenchen Pan
Author_Institution :
Sch. of Electr. Eng. & Comput. Sci., Queensland Univ. of Technol., Brisbane, QLD, Australia
Abstract :
In the real world there are many problems in network of networks (NoNs) that can be abstracted to a so-called minimum interconnection cut problem, which is fundamentally different from those classical minimum cut problems in graph theory. Thus, it is desirable to propose an efficient and effective algorithm for the minimum interconnection cut problem. In this paper we formulate the problem in graph theory, transform it into a multi-objective and multi-constraint combinatorial optimization problem, and propose a hybrid genetic algorithm (HGA) for the problem. The HGA is a penalty-based genetic algorithm (GA) that incorporates an effective heuristic procedure to locally optimize the individuals in the population of the GA. The HGA has been implemented and evaluated by experiments. Experimental results have shown that the HGA is effective and efficient.
Keywords :
genetic algorithms; graph theory; HGA; NoN; graph theory; heuristic procedure; hybrid genetic algorithm; minimum cut problems; minimum interconnection cut problem; multiconstraint combinatorial optimization problem; multiobjective combinatorial optimization problem; network of networks; penalty-based genetic algorithm; Genetic algorithms; Graph theory; Multiprocessor interconnection; Optimization; Servers; Sociology; Statistics; hybrid genetic algorithm; minimum interconnection cut; optimization;
Conference_Titel :
Evolutionary Computation (CEC), 2013 IEEE Congress on
Conference_Location :
Cancun
Print_ISBN :
978-1-4799-0453-2
Electronic_ISBN :
978-1-4799-0452-5
DOI :
10.1109/CEC.2013.6557935