A hybrid Hopfield network - genetic algorithm approach for the terminal assignment problem

Research output: Contribution to journalArticle

Authors

Colleges, School and Institutes

Abstract

This paper presents a hybrid Hopfield network-genetic algorithm (GA) approach to tackle the terminal assignment (TA) problem. TA involves determining minimum cost links to form a communications network, by connecting a given set of terminals to a given collection of concentrators. Some previous approaches provide very good results if the cost associated with assigning a single terminal to a given concentrator is known. However, there are situations in which the cost of a single assignment is not known in advance, and only the cost associated with feasible solutions can be calculated. In these situations, previous algorithms for TA based on greedy heuristics are no longer valid, or fail to get feasible solutions. Our approach involves a Hopfield neural network (HNN) which manages the problem's constraints, whereas a GA searches for high quality solutions with the minimum possible cost. We show that our algorithm is able to achieve feasible solutions to the TA in instances where the cost of a single assignment in not known in advance, improving the results obtained by previous approaches. We also show the applicability of our approach to other problems related to the TA.

Details

Original languageEnglish
Pages (from-to)2343-2353
Number of pages11
JournalIEEE Transactions on Systems, Man, and Cybernetics, Part B (Cybernetics)
Volume34
Issue number6
Publication statusPublished - 1 Jan 2004

Keywords

  • genetic algorithms (GA), Hopfield neural networks, heuristics, terminal assignment (TA) problem