混沌神经网络在组合优化问题中的研究和应用
|
摘要
人工神经网络是为了研究人类的认知过程而发展起来的，它的中心问题是面向研究对象的机器学习方法与学习机器的构造问题。混沌现象是非线性确定性系统的一种内在随机过程的表现，所以混沌型神经网络近年来受到了学者们的高度重视，取得了许多令人瞩目的研究成果。
混沌系统是一种非线性动力学系统，而Hopfield结构可以实现神经网络与非线性动力学行为的良好结合，因而它可以作为研究混沌神经网络的网络结构模型。
带有混沌特性的人工神经网络表现出更复杂的动力学特性，不同于常规的反馈型神经网络。混沌神经网络还具有全面的运动描述以及远离平衡点的动力学特性，同时存在各种吸引子。混沌神经网络的这种复杂的动力学特性能够在信息处理和优化计算等问题的应用方面有广泛的前景。
本文对混沌神经网络输出函数做了更深入一步的研究，系统地介绍了混沌特征、混沌神经网络基本特性，研究了混沌神经网络的构造方法和特点以及在组合优化领域的应用。
本文研究了暂态混沌神经网络，提出了离散和离散-连续的改进型输出函数，从理论上分析了算法的可行性，通过仿真研究了改进前后方法的优化率和计算成本之间的关系。
本文探讨了将上述离散型输出函数的混沌神经网络应用于组合优化领域代表问题TSP(Traveling salesman problem)的求解。首先介绍了旅行商问题在传统方法搜索下的工作量；其次给出了求解旅行推销商问题的混沌神经网络方法；最后利用混沌神经网络应用于求解TSPLIB中旅行商问题，仿真研究的结果表明，离散输出函数降低了计算时间，适合应用于城市数目较多的TSP问题。
在多媒体通信等高速包交换计算机网络中，具有端到端时延及时延抖动限制的QoS(Quality of Service)组播路由问题属于组合优化问题，如何保证服务质量要求以及实现多媒体数据的组播通信是多媒体通信发展的方向。本文研究了如何将混沌神经网络应用于QoS组播路由问题中，提出了一种新的时延和时延抖动约束的能量函数，并将采用了新能量函数进行迭代的混沌神经网络应用于时延及时延抖动QoS组播路由问题。仿真结果表明，新的能量函数具有非常好的优化效果，能高效的引导神经网络进入一个与问题最优解相对应的能量最小点，提高了寻优质量。
Artificial neural network is to be developed for the study intelligence process of human, focus on the problems of learning method in object oriented machine and constructing learning machine. Chaos is an inside representation of stochastic process in nonlinear determinate system, so recently chaotic neural network has attracted much more attention of researcher, and made much more important progress in the field.
Chaos is a nonlinear dynamics system, and the Hopfield framework can be used to make the good combination of neural network and nonlinear dynamical behavior. So it can be used as basic network framework of chaotic neural networks.
Because an artificial neural network with chaotic character has more complicated dynamics property, which is different from the traditional neural network. The chaotic neural network has omnidirectional behavior and more complex dynamics property, and has diversified attractors. It is just the dynamics that make it possible for the network to be a technology with popularized application foreground for information processing and optimization computation.
The paper study the output function of chaotic neural network more carefully, introduced basic character of chaos and neural networks, research method of constructing chaotic neural networks and discussed its application in combinatorial optimization field.
At the same time, the paper study neural network with transient chaos, a kind of chaotic neural network pattern, proposed an adapted discrete and continuous-discrete output functions, we analyzed the feasibility of the new algorithm in principle, compared it with former neural network and discussed the relationship of optimization rate and the time cost of them.
At last, the paper applied former chaotic neural network with discrete output function to solve Traveling salesman problem which is the representative question of the combinatorial optimization field. First, we introduced the workload of traditional method. Second, proposed chaotic neural network model which is adapt to TSP. At last, solved TSP with chaotic neural work, and the result illustrated that discrete output function can find global minimum within less time cost and is conformable to be applied in middle-scale TSP problem with much more cities.
In the multimedia communications and so on high speed packet-switched networks, the end-to-end delay and delay variation constrained least cost multicast routing problem is a combinatorial optimization problem. The direction of multimedia communications development is how to ensure the (QoS) quality of service of multimedia data and realize its multicast communication. So we study how to apply chaotic neural networks to QoS multicast routing question. We proposed a new delay and delay variation constrained energy function, and adopted it to chaotic neural networks to solve QoS multicast routing problem. The emulation verified that the energy function has an excellent optimization effect, can efficiently draw neural
network to an energy minimum which is corresponding to the optimal result of QoS multicast routing problem.
混沌系统是一种非线性动力学系统，而Hopfield结构可以实现神经网络与非线性动力学行为的良好结合，因而它可以作为研究混沌神经网络的网络结构模型。
带有混沌特性的人工神经网络表现出更复杂的动力学特性，不同于常规的反馈型神经网络。混沌神经网络还具有全面的运动描述以及远离平衡点的动力学特性，同时存在各种吸引子。混沌神经网络的这种复杂的动力学特性能够在信息处理和优化计算等问题的应用方面有广泛的前景。
本文对混沌神经网络输出函数做了更深入一步的研究，系统地介绍了混沌特征、混沌神经网络基本特性，研究了混沌神经网络的构造方法和特点以及在组合优化领域的应用。
本文研究了暂态混沌神经网络，提出了离散和离散-连续的改进型输出函数，从理论上分析了算法的可行性，通过仿真研究了改进前后方法的优化率和计算成本之间的关系。
本文探讨了将上述离散型输出函数的混沌神经网络应用于组合优化领域代表问题TSP(Traveling salesman problem)的求解。首先介绍了旅行商问题在传统方法搜索下的工作量；其次给出了求解旅行推销商问题的混沌神经网络方法；最后利用混沌神经网络应用于求解TSPLIB中旅行商问题，仿真研究的结果表明，离散输出函数降低了计算时间，适合应用于城市数目较多的TSP问题。
在多媒体通信等高速包交换计算机网络中，具有端到端时延及时延抖动限制的QoS(Quality of Service)组播路由问题属于组合优化问题，如何保证服务质量要求以及实现多媒体数据的组播通信是多媒体通信发展的方向。本文研究了如何将混沌神经网络应用于QoS组播路由问题中，提出了一种新的时延和时延抖动约束的能量函数，并将采用了新能量函数进行迭代的混沌神经网络应用于时延及时延抖动QoS组播路由问题。仿真结果表明，新的能量函数具有非常好的优化效果，能高效的引导神经网络进入一个与问题最优解相对应的能量最小点，提高了寻优质量。
Artificial neural network is to be developed for the study intelligence process of human, focus on the problems of learning method in object oriented machine and constructing learning machine. Chaos is an inside representation of stochastic process in nonlinear determinate system, so recently chaotic neural network has attracted much more attention of researcher, and made much more important progress in the field.
Chaos is a nonlinear dynamics system, and the Hopfield framework can be used to make the good combination of neural network and nonlinear dynamical behavior. So it can be used as basic network framework of chaotic neural networks.
Because an artificial neural network with chaotic character has more complicated dynamics property, which is different from the traditional neural network. The chaotic neural network has omnidirectional behavior and more complex dynamics property, and has diversified attractors. It is just the dynamics that make it possible for the network to be a technology with popularized application foreground for information processing and optimization computation.
The paper study the output function of chaotic neural network more carefully, introduced basic character of chaos and neural networks, research method of constructing chaotic neural networks and discussed its application in combinatorial optimization field.
At the same time, the paper study neural network with transient chaos, a kind of chaotic neural network pattern, proposed an adapted discrete and continuous-discrete output functions, we analyzed the feasibility of the new algorithm in principle, compared it with former neural network and discussed the relationship of optimization rate and the time cost of them.
At last, the paper applied former chaotic neural network with discrete output function to solve Traveling salesman problem which is the representative question of the combinatorial optimization field. First, we introduced the workload of traditional method. Second, proposed chaotic neural network model which is adapt to TSP. At last, solved TSP with chaotic neural work, and the result illustrated that discrete output function can find global minimum within less time cost and is conformable to be applied in middle-scale TSP problem with much more cities.
In the multimedia communications and so on high speed packet-switched networks, the end-to-end delay and delay variation constrained least cost multicast routing problem is a combinatorial optimization problem. The direction of multimedia communications development is how to ensure the (QoS) quality of service of multimedia data and realize its multicast communication. So we study how to apply chaotic neural networks to QoS multicast routing question. We proposed a new delay and delay variation constrained energy function, and adopted it to chaotic neural networks to solve QoS multicast routing problem. The emulation verified that the energy function has an excellent optimization effect, can efficiently draw neural
network to an energy minimum which is corresponding to the optimal result of QoS multicast routing problem.
引文
1 张汝波 编．计算智能基础．第一版．哈尔滨：哈尔滨工程大学出版社，2001：1-43
2 靳藩 编著．神经计算智能基础——原理，方法．第一版．成都：西安交通大学出版社，2000：1-70
3 王凌 著．智能优化算法及其应用．第一版．北京：清华大学出版社，2001：89-117
4 郭爱克著．计算神经科学．上海：上海科技教育出版社，2001：1-30
5 刘永红．神经网络理论的发展与前沿问题，信息与控制，1999，28(1)：9-12
6 焦李成 编著．神经网络计算．西安：西安电子科技大学出版社．1993：1-40
7 董军，胡上序．混沌神经网络研究进展与展望，信息与控制，1997．26(5)：359-367
8 Aihara, K., Takabe T., Touoda, M. Chaotic neural networks. Physics Letters A. 1990,144(6,7): 333-340.
9 Chen Luonan. Kazuyuki Aihara. Chaotic Simulated Annealing by a Neural Network Model with Transient Chaos, Neural Networks, 1995, 8(6): 915-930
10 Hubert Y., Chan. Chaotic neural fuzzy associative memory. International Journal of Bifurcation and Chaos. 1999, 9(8): 1597-1617
11 Lipo Wang, Kate Smith. On Chaotic Simulated Annealing. IEEE Transactions on neural networks. 1998, 9(4):716-718
12 Terence Kwork, Kate A. Smith. A unified framework for chaotic neural network approaches to combinatorial optimization. IEEE Transactions on Neural Networks. 1999, 10(4):978-981
13 HE Yuyao & WANG Lipo, Chaotic Neural Network and Their Application to Optimization Problems, Control Theory and Applications. 2000, 17(6): 826-830
14 M., Talavan, Javier Yanez. Parameter setting of Hopfield network applied to TSP, Neural Networks. 2002, 15:363-373
15 Mikio hasegawa, Tohru Ikeguchi & Kazuyki. Aihara Solving large scale traveling salesman problems by chaotic neurodynamics, Neural Networks, Volume, 2002, 15:271-283
16 J.J. Hopfield & D.W. Tank, "Neural" computation of decision in optimization problems, Biological Cybernetics, 1985,52:141-152
17 Wilson, G. V. & Pawley, G. S., On the stability of the TSP algorithm of Hopfield and Tank., Biological Cybernetics, 1988, 58:63-70
18 Yamada Y., Aihara K. & Kotani M., Chaotic Neural Network and Traveling Salesman Problem, Proceeding of 1993 International Joint Conference on Neural Networks, 1993: 1549-1552.
19 Wang L, Smith K. On Chaotic Simulated Annealing, IEEE Transactions on Neural Networks, 1998, 9(4): 716-718
20 Zhou ChangSong, Chen Tian Lun & Huang WuQun, Chaotic Neural Network with Nonlinear Self-feedback and its Application in Optimization., Neurocomputing, 1997, 14: 209-222.
21 Luonan Chen, Kazuyuki Aihara. Global searching ability of chaotic neural networks. IEEE Transactions on Circuits and Systems. 1999, 46(8):974-993
22 曾孝平．组播路由选择的流体神经网络电路模型．电路与系统学报．2001，(2)：74-77
23 Chotipat E, Goutam C. & Norio S. A Neural Network Approach to Multicast Routing in Real-time Communication Networks. International Conference on Network Protocols, 1995:332-339
24 谢传泉，何晨，诸鸿文．用改进的噪声混沌神经网络模型求解组合优化问题．上海交通大学学报．2002，36(3)：351-354
25 孙守宇，郑君．Hopfield网络求解TSP的一种改进算法和理论证明．电子学报．1995，23(1)：73-78
26 王凌，郑大钟．TSP及其基于Hopfield网络优化的研究．控制与决策．1999，14(6)：669-674
27 Sanjeev Verma., Rajesh K., etc. QoS based multicast routing algorithms for real time applications. Performance Evalution, 1998, 34:273-294
28 Y, Deng C, He Z Y. Chaotic annealing neural networks and its application to direction estimation of spatial signal sources. In: Proceeding IEEE Workshop on Neural Networks for Signal Processing, Florida, USA, 1997, 7: 541-550
29 王东生，曹磊．混沌、分形及其应用．中国科学技术大学出版社．1995，26(5)：1-13
30 Klotz A., Brauer K.. A small-size Neural Network for Computing with Strange Attractors. Neural Networks. 1999, 12:601-607
31 荆涛，宋健中，杨怀江．基于复合混沌映射的神经网络模型．光学精密工程．1999，7(1)：40-44
32 Michael Peter Kennedy. Three steps to Chaos. IEEE Transactions on Circuits and systems. 1993, 40(10):640-675
33 何振亚，谭营，王保云．一种新的混沌神经网络及其动力学分析．东南大学学报，1998，28(5)：122-127
34 王秀宏，王正欧 等．用具有混沌特性的神经网络解任务分配问题．系统工程学报．1999，9(11)：2157-2163
35 卢侃，孙建华 等 编著．混沌动力学．上海：上海翻译出版社．1990：1-36
36 简相超，郑君里．混沌神经网络预测算法评价准则与性能分析．清华大学学报(自然科学版)2001，41(7)：43-46
37 徐耀群．混沌神经网络研究及应用．哈尔滨工程大学博士学位论文，2002：1-30
38 焦李成 编著．神经网络系统理论．西安：西安电子科技大学出版社．1990：1-70
39 张素兵，刘泽民．一种新的基于混沌神经网络的组播路由算法．计算机学报．2001，
24(12)：1256-1261
40 冯久超，邱玉辉．一种混沌神经网络和动态联想记忆．计算机学报．1998，25(1)：57-60
41 徐建学，陈永红等．人工神经网络非线性动力学及应用．力学进展．1998，28(2)：145-162
42 Hwang F K, Richards D S. Steiner tree problem s. IEEE Network s, 1992, 22(1): 55-89
43 Gelenbe E., Ghanwani A., Srinivason V. Improved neural heuristics for multicast routing, IEEE Journal on Selected Areas in Comm, 1997, 15(2):147-155
44 Kou L., Markowsky G., Berman L., A fast algorithm for Steiner trees, A cta Information, 1981, 15:141-145
45 Rouskas G N, Baldine L. Multicast routing with end-to-end delay and delay variation constraints, IEEE Journal on Selected Areas in Communications, 1997, 15(3): 346-356
46 Sun WenSheng, Liu ZeMin. Multicast routing based neural networks. Journal of China Institute of Communications, 1998, 19(11): 1-6 (in Chinese)(孙文生，刘泽民．组播路由调度的神经网络方法．通信学报，1998，19(11)：1-6)
47 董庆阳．计算机通信网络组播路由算法和协议的研究．上海交通大学博士论文．1999：1-13
48 Haghighat A.T., Faez K. GA-Based Heuristic Algorithms for QoS Based Multicast Routing, Knowledge-Based Systems, 2003, 16:305-312
49 Waxman B. M., Routing of multipoint connections. IEEE Journal on Selected Areas in Communications, 1988, 6(9): 1617-1622
50 Kumar B.P.V. Venkataram P. Reliable multicast routing in mobile networks: a neural network approach. Communications, IEEE proceedings, 2003, 150(5): 377-384
51 INTERNET_DRAFT, Fine M., McCloghrie K., et al. Differentiated Services Quality of Service Policy Information Base, draft-ietf-diffserv-policy-info-base-03.txt,2001.3
52 Tode H., Sakai Y., Yamamoto M., et al., Multicast routing algorithm for nodal load balancing, IEEE INFOCOM'92,1992,2086-2095
53 Katahira, Sendai., A Neural Network Approach to Multicast Routing in Real-Time Communication Networks. Network Protocols 1995 Proceedings, 1995 International Conference on, 1995,(7-10): 332-339
54 何国光，曹志彤．混沌神经网络的控制．物理学报．2001，50(11)：2103-2105
55 谢传泉，何晨．混沌神经网络模型中的模拟退火策略．上海交通大学学报．2003，37(3)：323-326
56 胡世余 谢剑英．基于混沌神经网络的最短路径路由算法．计算机研究与发展．2003，40(8)：1181-1185
57 张学义 胡仕诚 谢荣生 等．一种混沌神经网络及其在优化计算中的应用．系统工程及电子技术．2000．22(7)：69-71
2 靳藩 编著．神经计算智能基础——原理，方法．第一版．成都：西安交通大学出版社，2000：1-70
3 王凌 著．智能优化算法及其应用．第一版．北京：清华大学出版社，2001：89-117
4 郭爱克著．计算神经科学．上海：上海科技教育出版社，2001：1-30
5 刘永红．神经网络理论的发展与前沿问题，信息与控制，1999，28(1)：9-12
6 焦李成 编著．神经网络计算．西安：西安电子科技大学出版社．1993：1-40
7 董军，胡上序．混沌神经网络研究进展与展望，信息与控制，1997．26(5)：359-367
8 Aihara, K., Takabe T., Touoda, M. Chaotic neural networks. Physics Letters A. 1990,144(6,7): 333-340.
9 Chen Luonan. Kazuyuki Aihara. Chaotic Simulated Annealing by a Neural Network Model with Transient Chaos, Neural Networks, 1995, 8(6): 915-930
10 Hubert Y., Chan. Chaotic neural fuzzy associative memory. International Journal of Bifurcation and Chaos. 1999, 9(8): 1597-1617
11 Lipo Wang, Kate Smith. On Chaotic Simulated Annealing. IEEE Transactions on neural networks. 1998, 9(4):716-718
12 Terence Kwork, Kate A. Smith. A unified framework for chaotic neural network approaches to combinatorial optimization. IEEE Transactions on Neural Networks. 1999, 10(4):978-981
13 HE Yuyao & WANG Lipo, Chaotic Neural Network and Their Application to Optimization Problems, Control Theory and Applications. 2000, 17(6): 826-830
14 M., Talavan, Javier Yanez. Parameter setting of Hopfield network applied to TSP, Neural Networks. 2002, 15:363-373
15 Mikio hasegawa, Tohru Ikeguchi & Kazuyki. Aihara Solving large scale traveling salesman problems by chaotic neurodynamics, Neural Networks, Volume, 2002, 15:271-283
16 J.J. Hopfield & D.W. Tank, "Neural" computation of decision in optimization problems, Biological Cybernetics, 1985,52:141-152
17 Wilson, G. V. & Pawley, G. S., On the stability of the TSP algorithm of Hopfield and Tank., Biological Cybernetics, 1988, 58:63-70
18 Yamada Y., Aihara K. & Kotani M., Chaotic Neural Network and Traveling Salesman Problem, Proceeding of 1993 International Joint Conference on Neural Networks, 1993: 1549-1552.
19 Wang L, Smith K. On Chaotic Simulated Annealing, IEEE Transactions on Neural Networks, 1998, 9(4): 716-718
20 Zhou ChangSong, Chen Tian Lun & Huang WuQun, Chaotic Neural Network with Nonlinear Self-feedback and its Application in Optimization., Neurocomputing, 1997, 14: 209-222.
21 Luonan Chen, Kazuyuki Aihara. Global searching ability of chaotic neural networks. IEEE Transactions on Circuits and Systems. 1999, 46(8):974-993
22 曾孝平．组播路由选择的流体神经网络电路模型．电路与系统学报．2001，(2)：74-77
23 Chotipat E, Goutam C. & Norio S. A Neural Network Approach to Multicast Routing in Real-time Communication Networks. International Conference on Network Protocols, 1995:332-339
24 谢传泉，何晨，诸鸿文．用改进的噪声混沌神经网络模型求解组合优化问题．上海交通大学学报．2002，36(3)：351-354
25 孙守宇，郑君．Hopfield网络求解TSP的一种改进算法和理论证明．电子学报．1995，23(1)：73-78
26 王凌，郑大钟．TSP及其基于Hopfield网络优化的研究．控制与决策．1999，14(6)：669-674
27 Sanjeev Verma., Rajesh K., etc. QoS based multicast routing algorithms for real time applications. Performance Evalution, 1998, 34:273-294
28 Y, Deng C, He Z Y. Chaotic annealing neural networks and its application to direction estimation of spatial signal sources. In: Proceeding IEEE Workshop on Neural Networks for Signal Processing, Florida, USA, 1997, 7: 541-550
29 王东生，曹磊．混沌、分形及其应用．中国科学技术大学出版社．1995，26(5)：1-13
30 Klotz A., Brauer K.. A small-size Neural Network for Computing with Strange Attractors. Neural Networks. 1999, 12:601-607
31 荆涛，宋健中，杨怀江．基于复合混沌映射的神经网络模型．光学精密工程．1999，7(1)：40-44
32 Michael Peter Kennedy. Three steps to Chaos. IEEE Transactions on Circuits and systems. 1993, 40(10):640-675
33 何振亚，谭营，王保云．一种新的混沌神经网络及其动力学分析．东南大学学报，1998，28(5)：122-127
34 王秀宏，王正欧 等．用具有混沌特性的神经网络解任务分配问题．系统工程学报．1999，9(11)：2157-2163
35 卢侃，孙建华 等 编著．混沌动力学．上海：上海翻译出版社．1990：1-36
36 简相超，郑君里．混沌神经网络预测算法评价准则与性能分析．清华大学学报(自然科学版)2001，41(7)：43-46
37 徐耀群．混沌神经网络研究及应用．哈尔滨工程大学博士学位论文，2002：1-30
38 焦李成 编著．神经网络系统理论．西安：西安电子科技大学出版社．1990：1-70
39 张素兵，刘泽民．一种新的基于混沌神经网络的组播路由算法．计算机学报．2001，
24(12)：1256-1261
40 冯久超，邱玉辉．一种混沌神经网络和动态联想记忆．计算机学报．1998，25(1)：57-60
41 徐建学，陈永红等．人工神经网络非线性动力学及应用．力学进展．1998，28(2)：145-162
42 Hwang F K, Richards D S. Steiner tree problem s. IEEE Network s, 1992, 22(1): 55-89
43 Gelenbe E., Ghanwani A., Srinivason V. Improved neural heuristics for multicast routing, IEEE Journal on Selected Areas in Comm, 1997, 15(2):147-155
44 Kou L., Markowsky G., Berman L., A fast algorithm for Steiner trees, A cta Information, 1981, 15:141-145
45 Rouskas G N, Baldine L. Multicast routing with end-to-end delay and delay variation constraints, IEEE Journal on Selected Areas in Communications, 1997, 15(3): 346-356
46 Sun WenSheng, Liu ZeMin. Multicast routing based neural networks. Journal of China Institute of Communications, 1998, 19(11): 1-6 (in Chinese)(孙文生，刘泽民．组播路由调度的神经网络方法．通信学报，1998，19(11)：1-6)
47 董庆阳．计算机通信网络组播路由算法和协议的研究．上海交通大学博士论文．1999：1-13
48 Haghighat A.T., Faez K. GA-Based Heuristic Algorithms for QoS Based Multicast Routing, Knowledge-Based Systems, 2003, 16:305-312
49 Waxman B. M., Routing of multipoint connections. IEEE Journal on Selected Areas in Communications, 1988, 6(9): 1617-1622
50 Kumar B.P.V. Venkataram P. Reliable multicast routing in mobile networks: a neural network approach. Communications, IEEE proceedings, 2003, 150(5): 377-384
51 INTERNET_DRAFT, Fine M., McCloghrie K., et al. Differentiated Services Quality of Service Policy Information Base, draft-ietf-diffserv-policy-info-base-03.txt,2001.3
52 Tode H., Sakai Y., Yamamoto M., et al., Multicast routing algorithm for nodal load balancing, IEEE INFOCOM'92,1992,2086-2095
53 Katahira, Sendai., A Neural Network Approach to Multicast Routing in Real-Time Communication Networks. Network Protocols 1995 Proceedings, 1995 International Conference on, 1995,(7-10): 332-339
54 何国光，曹志彤．混沌神经网络的控制．物理学报．2001，50(11)：2103-2105
55 谢传泉，何晨．混沌神经网络模型中的模拟退火策略．上海交通大学学报．2003，37(3)：323-326
56 胡世余 谢剑英．基于混沌神经网络的最短路径路由算法．计算机研究与发展．2003，40(8)：1181-1185
57 张学义 胡仕诚 谢荣生 等．一种混沌神经网络及其在优化计算中的应用．系统工程及电子技术．2000．22(7)：69-71