Solving Order/Degree Problems by Using EDA-GK with a Novel Sampling Method

Ryoichi Hasegawa; Hisashi H; a

doi:10.20965/jaciii.2018.p0236

single-jc.php

« previous

JACIII Vol.22 No.2 pp. 236-241

doi: 10.20965/jaciii.2018.p0236

(2018)

Paper:

Views over last 60 days: 1,004

Solving Order/Degree Problems by Using EDA-GK with a Novel Sampling Method

Ryoichi Hasegawa and Hisashi Handa

Kindai University
3-4-1 Kowakae, Higashi-Osaka 577-8502, Japan

Received:

August 20, 2017

Accepted:

January 11, 2018

Published:

March 20, 2018

Keywords:

Estimation of Distribution Algorithms, graph kernel, Order/Degree problems

Abstract

The Estimation of Distribution Algorithms with Graph Kernels called EDA-GK is an extension of the Estimation of Distribution Algorithms that can work with graph-related problems. Individuals of the EDA-GK are represented by graphs. In this paper, the EDA-GK is applied to solve for the Order/Degree problems, which are an NP-hard problems and are a benchmark problem in graph theory studies. Moreover, we incorporate a new sampling method for generating offspring. Experimental results on several problem instances of Order/Degree problems show the effectiveness of the EDA-GK.

Cite this article as:

R. Hasegawa and H. Handa, “Solving Order/Degree Problems by Using EDA-GK with a Novel Sampling Method,” J. Adv. Comput. Intell. Intell. Inform., Vol.22 No.2, pp. 236-241, 2018.

Data files:

References

[1] H. Handa, “Use of graph kernels in Estimation of Distribution Algorithms,” Proc. of 2012 IEEE Congress on Evolutionary Computation (CEC), pp. 1-6, 2012.
[2] K. Maezawa and H. Handa, ”Estimation of Distribution Algorithms with Graph Kernels for Graphs with Node Types,” Proc. 20th Asia Pacific Symposium on Intelligent and Evolutionary Systems, pp. 251-261, 2016.
[3] P. Larrañaga and J. A. Lozano, “Estimation of Distribution Algorithms,” Kluwer Academic Publishers, 2003.
[4] T. Kitasuka and M. Iida, “A Heuristic Method of Generating Diameter 3 Graphs for Order/Degree Problems,” 2016 10th IEEE/ACM Int. Symposium on Networks-on-Chip, 2016.
[5] Graph Golf, http://research.nii.ac.jp/graphgolf/ [accessed May 1, 2017]
[6] E. Alba, and F. Chicano, “ACOhg: Dealing with huge graphs,” Proc. the 2007 ACM Genetic and Evolutionary Conf., pp. 10-17, 2007.
[7] F. Chicano and E. Alba, “Ant colony optimization with partial order reduction for discovering safety property violations in concurrent models,” Information Processing Letters, Vol.106, No.6, pp. 221-231, 2008.
[8] J. McDermott and U.-M. O’Reilly, “An executable graph representation for evolutionary generative music,” Proc. the 2011 ACM Genetic and Evolutionary Conf., pp. 403-412, 2011.
[9] T. E. Lewis and G. D. Magoulas, “Strategies to minimise the total run time of cyclic graph based genetic programming with GPUs,” Proc. the 2009 ACM Genetic and Evolutionary Conf., pp. 1379-1386, 2009.
[10] S. Shirakawa, and T. Nagao, “Graph structured program evolution with automatically defined nodes,” Proc. the 2009 ACM Genetic and Evolutionary Conf., pp. 1107-1115, 2009.
[11] S. Mabu, K. Hirasawa, and J. Hu, “A Graph-Based Evolutionary Algorithm: Genetic Network Programming (GNP) and Its Extension Using Reinforcement Learning,” Evolutionary Computation, Vol.15, No.3, pp. 369-398, 2007.
[12] H. Kashima, K. Tsuda, and A. Inokuchi, “Marginalized Kernels Between Labeled Graphs,” Proc. 20th Int. Conf. on Machine Learning, pp. 321-328, 2003.
[13] K. M. Borgwardt and H.-P. Kriegel, “Shortest-path kernels on graphs,” Proc. 5th Int. Conf. Data Mining, 2005.

This article is published under a Creative Commons Attribution-NoDerivatives 4.0 Internationa License.

[1] [1] H. Handa, “Use of graph kernels in Estimation of Distribution Algorithms,” Proc. of 2012 IEEE Congress on Evolutionary Computation (CEC), pp. 1-6, 2012.

[2] [2] K. Maezawa and H. Handa, ”Estimation of Distribution Algorithms with Graph Kernels for Graphs with Node Types,” Proc. 20th Asia Pacific Symposium on Intelligent and Evolutionary Systems, pp. 251-261, 2016.

[3] [3] P. Larrañaga and J. A. Lozano, “Estimation of Distribution Algorithms,” Kluwer Academic Publishers, 2003.

[4] [4] T. Kitasuka and M. Iida, “A Heuristic Method of Generating Diameter 3 Graphs for Order/Degree Problems,” 2016 10th IEEE/ACM Int. Symposium on Networks-on-Chip, 2016.

[5] [5] Graph Golf, http://research.nii.ac.jp/graphgolf/ [accessed May 1, 2017]

[6] [6] E. Alba, and F. Chicano, “ACOhg: Dealing with huge graphs,” Proc. the 2007 ACM Genetic and Evolutionary Conf., pp. 10-17, 2007.

[7] [7] F. Chicano and E. Alba, “Ant colony optimization with partial order reduction for discovering safety property violations in concurrent models,” Information Processing Letters, Vol.106, No.6, pp. 221-231, 2008.

[8] [8] J. McDermott and U.-M. O’Reilly, “An executable graph representation for evolutionary generative music,” Proc. the 2011 ACM Genetic and Evolutionary Conf., pp. 403-412, 2011.

[9] [9] T. E. Lewis and G. D. Magoulas, “Strategies to minimise the total run time of cyclic graph based genetic programming with GPUs,” Proc. the 2009 ACM Genetic and Evolutionary Conf., pp. 1379-1386, 2009.

[10] [10] S. Shirakawa, and T. Nagao, “Graph structured program evolution with automatically defined nodes,” Proc. the 2009 ACM Genetic and Evolutionary Conf., pp. 1107-1115, 2009.

[11] [11] S. Mabu, K. Hirasawa, and J. Hu, “A Graph-Based Evolutionary Algorithm: Genetic Network Programming (GNP) and Its Extension Using Reinforcement Learning,” Evolutionary Computation, Vol.15, No.3, pp. 369-398, 2007.

[12] [12] H. Kashima, K. Tsuda, and A. Inokuchi, “Marginalized Kernels Between Labeled Graphs,” Proc. 20th Int. Conf. on Machine Learning, pp. 321-328, 2003.

[13] [13] K. M. Borgwardt and H.-P. Kriegel, “Shortest-path kernels on graphs,” Proc. 5th Int. Conf. Data Mining, 2005.