Title: Hybrid neural network and bi-criteria tabu-machine: comparison of new approaches to maximum clique problem

Authors: Eduard Babkin; Tatiana Babkina; Alexander Demidovskij

Addresses: Department of Information Systems and Technologies, National Research University Higher School of Economics, Nizhny Novgorod, Russia ' Department of Applied Mathematics and Informatics, National Research University Higher School of Economics, Nizhny Novgorod, Russia ' Department of Information Systems and Technologies, National Research University Higher School of Economics, Nizhny Novgorod, Russia

Abstract: This paper presents two new approaches to solving a classical NP-hard problem of maximum clique problem (MCP), which frequently arises in the domain of information management, including design of database structures and big data processing. In our research, we are focusing on solving that problem using the paradigm of artificial neural networks. The first approach combines the artificial neuro-network paradigm and genetic programming. For boosting the convergence of the Hopfield neural network (HNN), we propose a specific design of the genetic algorithm as the selection mechanism for terms of the HNN energy function. The second approach incorporates and extends the tabu-search heuristics improving performance of network dynamics of so-called tabu machine. Introduction of a special penalty function in tabu machine facilitates better evaluation of the search space. As a result, we demonstrate the proposed approaches on well-known experimental graphs and formulate two hypotheses for further research.

Keywords: maximum clique problem; MCP; data structures; Hopfield network; genetic algorithm; tabu machine.

DOI: 10.1504/IJBDI.2018.092660

International Journal of Big Data Intelligence, 2018 Vol.5 No.3, pp.143 - 155

Received: 19 Apr 2016
Accepted: 15 Jan 2017
Published online: 27 Jun 2018 *

Full-text access for editors Full-text access for subscribers Purchase this article Comment on this article