Asymmetric Hopfield-type networks: Theory and applications

The Hopfield-type networks with asymmetric interconnections are studied from the standpoint of taking them as computational models. Two fundamental properties, feasibility and reliability, of the networks related to their use are established with a newly-developed convergence principle and a classification theory on energy functions. The convergence principle generalizes that previously known for symmetric networks and underlies the feasibility. The classification theory, which categorizes the traditional energy functions into regular, normal and complete ones according to their roles played in connection with the corresponding networks, implies that the reliability and high efficiency of the networks can follow respectively from the regularity and the normality of the corresponding energy functions. The theories developed have been applied to solve a classical NP-hard graph theory problem: finding the maximal independent set of a graph. Simulations demonstrate that the algorithms deduced from the asymmetric theories outperform those deduced from the symmetric theory.