Premium
Graph planarization problem optimization based on triple‐valued gravitational search algorithm
Author(s) -
Gao Shangce,
Todo Yuki,
Gong Tao,
Yang Gang,
Tang Zheng
Publication year - 2014
Publication title -
ieej transactions on electrical and electronic engineering
Language(s) - English
Resource type - Journals
SCImago Journal Rank - 0.254
H-Index - 30
eISSN - 1931-4981
pISSN - 1931-4973
DOI - 10.1002/tee.21934
Subject(s) - heuristics , population , benchmark (surveying) , algorithm , mathematical optimization , planar graph , graph , position (finance) , mathematics , embedding , computer science , theoretical computer science , artificial intelligence , demography , geodesy , finance , sociology , economics , geography
Abstract This article presents a triple‐valued gravitational search algorithm (TGSA) to tackle the graph planarization problem (GPP). GPP is one of the most important tasks in graph theory, and has proved to be an NP‐hard problem. To solve it, TGSA uses a triple‐valued encoding scheme and models the search space into a triangular hypercube quantitatively based on the well‐known single‐row routing representation method. The agents in TGSA, whose interactions are driven by the gravity law, move toward the global optimal position gradually. The position updating rule for each agent is based on two indices: one is a velocity index which is a function of the current velocity of the agent, and the other is a population index based on the cumulative information in the whole population. To verify the performance of the algorithm, 21 benchmark instances are tested. Experimental results indicate that TGSA can solve the GPP by finding its maximum planar subgraph and embedding the resulting edges into a plane simultaneously. Compared with traditional algorithms, a novelty of TGSA is that it can find multiple optimal solutions for the GPP. Comparative results also demonstrate that TGSA outperforms the traditional meta‐heuristics in terms of the solution qualities within reasonable computational times. Published by John Wiley & Sons, Inc.