Premium
A multi‐teacher learning automata computing model for graph partitioning problems
Author(s) -
Ikebo Shigeya,
Qian Fei,
Hirata Hironori
Publication year - 2004
Publication title -
electrical engineering in japan
Language(s) - English
Resource type - Journals
SCImago Journal Rank - 0.136
H-Index - 28
eISSN - 1520-6416
pISSN - 0424-7760
DOI - 10.1002/eej.10310
Subject(s) - computer science , simulated annealing , graph partition , graph , learning automata , cellular automaton , heuristic , scheduling (production processes) , automaton , theoretical computer science , algorithm , mathematical optimization , artificial intelligence , mathematics
Graph partitioning is an important problem that has extensive applications in many areas, including VLSI design, scientific computing, data mining, geographical information systems, and job scheduling. The graph partitioning problem (GPP) is NP‐complete. There are several heuristic algorithms developed for finding a reasonably good solution. The most famous partitioning methods are simulated annealing (SA) and the mean field algorithm (MFA), both known to produce good partitioning for a wide class of problems, and they are used quite extensively. However, these methods are very expensive in terms of time and very sensitive to parameter tuning methods. In this paper, a new parameter‐free algorithm for GPP has been proposed. The algorithm has been constructed using the S‐model learning automata with multi‐teacher random environments. As shown in our experiments, the proposed algorithm has some advantages over SA, MFA, and ParMeTiS. © 2004 Wiley Periodicals, Inc. Electr Eng Jpn, 148(1): 46–53, 2004; Published online in Wiley InterScience ( www.interscience.wiley.com ). DOI 10.1002/eej.10310