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.
International Journal of Big Data Intelligence, 2018 Vol.5 No.3, pp.143 - 155
Received: 19 Apr 2016
Accepted: 15 Jan 2017
Published online: 30 Oct 2017 *