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. © 2004 IEEE.
|Number of pages
|IEEE Transactions on Systems, Man, and Cybernetics, Part B: Cybernetics
|Early online date
|15 Nov 2004
|Published - Dec 2004
Bibliographical noteThe work of S. Salcedo-Sanz was supported by a postdoctoral fellowship from the Ministerio de Educación Cultura y Deporte of Spain, under Fellowship Number EX2003-0463. This paper was recommended by Associate Editor E. Santos.
- Genetic algorithms (GA)
- Hopfield neural networks
- Terminal assignment (TA) problem