JACIII Vol.22 No.2 pp. 236-241
doi: 10.20965/jaciii.2018.p0236


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

August 20, 2017
January 11, 2018
March 20, 2018
Estimation of Distribution Algorithms, graph kernel, Order/Degree problems

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:
  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, [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.

*This site is desgined based on HTML5 and CSS3 for modern browsers, e.g. Chrome, Firefox, Safari, Edge, IE9,10,11, Opera.

Last updated on Aug. 17, 2018