×

A portable and scalable algorithm for a class of constrained combinatorial optimization problems. (English) Zbl 1068.90093

Summary: This paper presents a portable and scalable approach for a class of constrained combinatorial optimization problems (CCOPs) which requires to satisfy a set of constraints and to optimize and objective function simultaneously. In particular, this paper is focused on the class of CCOPs that admits a representation in terms of a square matrix of constraints C.
The algorithm consists of a hybrid neural-genetic algorithm, formed by a Hopfield Neural Network (HNN) which solves the problem’s constraints, and a Genetic Algorithm (GA) for optimizing the objective function. This separated management of constraints and optimization procedures makes the proposed algorithm scalable and robust. The portability of the algorithm is given by the fact that the HNN dynamics depends only on the matrix C of constraints.
We show these properties of scalability and portability by solving three different CCOPs with our algorithm, the frequency assignment problem in a mobile telecommunications network, the reduction of the interference in satellite systems and the design of FPGAs with segmented channel routing architecture. We compare our results with previous approaches to these problems, obtaining very good results in all of them.

MSC:

90C27 Combinatorial optimization
90C59 Approximation methods and heuristics in mathematical programming
PDFBibTeX XMLCite
Full Text: DOI

References:

[1] Wang, G.; Ansari, N., Optimal broadcast scheduling in packet radio networks using mean field annealing, IEEE Journal on Selected Areas in Communications, 15, 2, 250-259 (1997)
[2] Levine, D., Application of a hybrid genetic algorithm to airline crew scheduling, Computers & Operations Research, 23, 6, 547-558 (1996) · Zbl 0847.90097
[3] Funabiki, N.; Okutani, N.; Nishikawa, S., A three-stage heuristic combined neural-network algorithm for channel assignment in cellular mobile systems, IEEE Transactions on Vehicular Technology, 49, 2, 397-403 (2000)
[4] Lai, W. K.; Coghill, G. C., Channel assignment through evolutionary optimization, IEEE Transactions on Vehicular Technology, 55, 1, 91-95 (1996)
[5] Hao, J. K.; Dorne, R.; Galinier, P., Tabu search for frequency assignment in mobile radio networks, Journal of Heuristics, 4, 1, 47-62 (1998) · Zbl 1071.90578
[6] Smith, K.; Palaniswami, M., Static and dynamic channel assignment using neural networks, IEEE Journal on Selected Areas in Communications, 15, 2, 238-249 (1997)
[7] Sandalidis, H. G.; Stavroulakis, P. P.; Rodriguez-Tellez, J., An efficient evolutionary algorithm for channel resource management in cellular mobile systems, IEEE Transactions on Evolutionary Computation, 2, 4, 125-137 (1998)
[8] Kim, H.; Hayashi, Y.; Nara, K., An algorithm for thermal unit maintenance scheduling through combined use of GA, SA and TS, IEEE Transactions on Power Systems, 12, 1, 329-335 (1997)
[9] Salcedo-Sanz, S.; Bousoño-Calzón, C., A mixed neural-genetic algorithm for the broadcast scheduling problem, IEEE Transactions on Wireless Communications, 2, 2, 277-283 (2003)
[10] Smith, K.; Palaniswami, M.; Krishnamoorthy, M., A hybrid neural approach to combinatorial optimisation, Computers & Operations Research, 23, 6, 597-610 (1996) · Zbl 0847.90119
[11] Wang CJ, Tsang EPK, Solving constraint satisfaction problems using neural-networks. In: Proceedings of the IEE Second International Conference on Artificial Neural Networks, 1991. p. 295-9.; Wang CJ, Tsang EPK, Solving constraint satisfaction problems using neural-networks. In: Proceedings of the IEE Second International Conference on Artificial Neural Networks, 1991. p. 295-9.
[12] Tsang EPK, Wang CJ. A generic neural network approach for constraint satisfaction problems. In: Taylor G, editor. Neural network applications. Berlin: Springer; 1992. p. 12-22.; Tsang EPK, Wang CJ. A generic neural network approach for constraint satisfaction problems. In: Taylor G, editor. Neural network applications. Berlin: Springer; 1992. p. 12-22.
[13] Balicki, J.; Stateczny, A.; Zak, B., Genetic algorithms and Hopfield neural networks for solving combinatorial problems, Applied Mathematics and Computer Science, 7, 3, 568-592 (1997) · Zbl 0905.90141
[14] Watanabe, Y.; Mizuguchi, N.; Fujii, Y., Solving optimization problems by using a Hopfield neural network and genetic algorithm combination, Systems and Computers in Japan, 29, 10, 68-73 (1998)
[15] Voudouris C, Tsang EPK, Solving the radio link frequency assignment problem using guided local search proceedings. In: Proceedings of the NATO Symposium on Radio Length Frequency Assignment, Sharing and Conservation Systems (Aerospace), Aalborg, Denmark, October 1998.; Voudouris C, Tsang EPK, Solving the radio link frequency assignment problem using guided local search proceedings. In: Proceedings of the NATO Symposium on Radio Length Frequency Assignment, Sharing and Conservation Systems (Aerospace), Aalborg, Denmark, October 1998.
[16] Funabiki, N.; Yoda, M., A gradual neural-network approach for FPGA segmented channel routing problems, IEEE Transactions on System, Man and Cybernetics Part B, 29, 4, 481-488 (1999)
[17] Funabiki, N.; Nishikawa, S., A gradual neural-network approach for frequency assignment in satellite communication systems, IEEE Transactions on Neural Networks, 8, 6, 1359-1370 (1997)
[18] Mizuike, T.; Ito, Y., Optimization of frequency assignment, IEEE Transactions on Communications, 37, 10, 1031-1041 (1989)
[19] Huang, Y. M.; Chen, R. M., Scheduling multiprocessor job with resource and timing constraints using neural networks, IEEE Transactions on System, Man and Cybernetics Part B, 29, 4, 490-502 (1999)
[20] Hou, E. S.; Ansari, N.; Ren, H., A genetic algorithm for multiprocessor scheduling, IEEE Transactions on Parallel and Distributed Systems, 5, 2, 113-120 (1994)
[21] Goldberg, D. E., Genetic algorithm in search, optimization and machine learning (1989), Addison-Wesley: Addison-Wesley Reading, MA · Zbl 0721.68056
[22] Shrivastava, Y.; Dasgupta, S.; Reddy, S. M., Guaranteed convergence in a class of Hopfield networks, IEEE Transactions on Neural Networks, 3, 951-961 (1992)
[23] Funabiki, N.; Takefuji, Y., A neural network parallel algorithm for channel assignment problems in cellular radio networks, IEEE Transactions on Vehicular Technology, 41, 4, 430-437 (1992)
[24] Ramanathan, P.; Krisna, M. S.; Agrawal, P.; Kishore, S., Dynamic resource allocation schemes during handoff for mobile multimedia wireless networks, IEEE Transactions on Selected Areas in Communications, 17, 7, 1270-1283 (1999)
[25] Thakur, S.; Chang, Y. W.; Wong, D. F.; Muthukrishnan, S., Algorithms for an FPGA switch module and associated routing algorithm for high performance FPGA’s, IEEE Transactions on Computer Aided Design, 16, 1, 22-25 (1997)
[26] Kaushik, R., A bounded search algorithm for segmented channel routing for FPGA’s and associated channel architecture issues, Computer Aided Design, 12, 11, 1695-1705 (1993)
[27] Lau, T. L.; Tsang, E. P.K., Guided genetic algorithm and its application to radio link frequency assignment problems, Constraints, 6, 4, 373-398 (2001) · Zbl 0983.68241
[28] Smith, K.; Palaniswami, M.; Krishnamoorthy, M., Neural techniques for combinatorial optimization with applications, IEEE Transactions on Neural Networks, 9, 6, 1301-1318 (1998)
[29] Smith, K. A.; Potvin, J.-. Y.; Kwok, T., Neural network models for combinatorial optimization: deterministic, stochastic and chaotic approaches, Control and Cybernetics, 31, 2, 183-216 (2002) · Zbl 1031.93009
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.