Paper:

# 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

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.

*J. Adv. Comput. Intell. Intell. Inform.*, Vol.22, No.2, pp. 236-241, 2018.

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