The optimum combination of chaotic neural network with self-feedback, Lyapunov exponent, and simulated annealing in solving of travelling salesman problem

Document Type : Research Article

Authors

1 Islamic Azad University, Mashhad Branch

2 Ferdowsi University of Mashhad

Abstract

This paper proposes a synergetic combination of chaotic neural network with self-feedback, Lyapunov exponent, and simulated annealing for combinatorial optimization problems such as travelling salesman problem (TSP). Unlike conventional neural networks only with point attractors, the chaotic neural network has more flexible dynamics, so that it can be expected to have higher ability of searching for optimal or near-optimal global solutions. One of the most important problems related to conventional neural networks is becomies trapped into the local minimums. Although chaotic neural networks can solve this problem, but they have difficulty due to convergence towards the equilibrium point. Therefore, we have tried to add the Lyapunov exponent and gradual cooling factor as a simulated annealing process, until network converges to the global optimal solutions quickly. In order to evaluate the proposed approach, TSP with different cities is used. Numerical experiments of the propsed approach on 10-TSP are shown that it has high efficiency to converge to global optimal solutions.

Keywords

Full Text

مختلف با درنظرگرفتن z(t) به‌صورت نمایی میراشونده

متوسط تکرارها برای همگرایی

نرخ پاسخ‎های نشدنی

نرخ کمینه محلی

نرخ کمینه سراسری

β

145

0/0

7/16

3/83

02/0

157

0/0

1/13

9/86

015/0

172

0/0

3/6

7/93

01/0

197

0/0

1/1

9/89

008/0

211

0/0

0

100

006/0

230

0/0

8/0

2/99

004/0

277

0/0

7/2

3/97

003/0

314

0/0

4/5

6/94

002/0

369

0/0

2/6

8/93

001/0

 

جدول (2): نمایش مقادیر نرخ کمینه سراسری، نرخ کمینه محلی، نرخ پاسخ‎های نشدنی و متوسط تکرارها برای همگرایی به ازای مقادیر βهای مختلف با درنظرگرفتن z(t) به‌صورت تانژانت هایپربولیک

متوسط تکرارها برای همگرایی

نرخ پاسخ‎های نشدنی

نرخ کمینه محلی

نرخ کمینه سراسری

β

139

0/0

3/13

7/89

02/0

161

0/0

1/12

9/87

015/0

189

0/0

9/10

1/89

01/0

215

0/0

9/9

1/90

008/0

249

0/0

8/4

2/95

006/0

287

0/0

0

100

004/0

350

0/0

9/5

1/94

003/0

417

0/0

4/9

6/90

002/0

430

0/0

7/13

3/86

001/0

 

 

جدول (2) نشان می­دهد به ازای βهای مختلف نرخ پاسخ‎های نشدنی مجددا صفر است. به ازای β=0.004 شبکه به نرخ کمینه سراسری 100 درصد و نرخ کمینه محلی صفر درصد رسیده است و متوسط تعداد تکرارها برای همگرایی 287 می‎شود. همچنین نرخ پاسخ­های نشدنی در ]37[ تقریباً صفر است. همچنین جدول‎های (1) و (2) نشان می­دهند، متوسط تعداد تکرارها برای همگرایی به ازای مقادیر مختلف β به ترتیب 230 و 270 است؛ بنابراین به نظر می‎رسد با درنظرگرفتن z(t) مطابق شکل (1) بتوان به تعداد تکرارهای کمتری دست یافت. به­منظور بررسی عملکرد شبکه برای حل TSP، پاسخ­های آن برای 5 توزیع 10 شهری، 5 توزیع 20 شهری و درنهایت 5 توزیع 150 شهری محاسبه شده است. ازآنجاکه طول مسیرها در هر توزیع وابسته به موقعیت شهرهاست، قبل از متوسط­گیری نتایج آن‌ها بهنجار می­شود. متوسط زمان همگرایی برای هر توزیع از شهرها در شکل (6) به نمایش گذاشته شده است.

 

شکل (6): متوسط زمان همگرایی برای هر توزیع از تعداد شهرهای مختلف

مرجع ]10[ نشان می­دهد زمانی‌که مقدار β از یک حدی افزایش می­یابد، فشار وارده بر سیستم در افزایش سرعت بیشتر می­شود. به طور خلاصه نتایج پژوهش در برخی موارد ]‎35،34،29،10،8 [بهبود خوبی را نسبت به پژوهش­های گذشته نشان می­دهد. در برخی موارد نتایج پژوهش­های گذشته ]36،29،28[ نتابج تحقیق را تأیید می‌کنند.

 

1- بحث و نتیجه‌گیری

در این پژوهش از ترکیب هم‎افزای شبکه عصبی آشوب­گون با پسخوراند خودی، نمای لیاپانوف و تبرید تدریجی به‎منظور حل بهینه‎ مسائل بهینه‎سازی ترکیبی نظیر TSP با تعداد شهرهای مختلف استفاده می­شود. شبکه‌های عصبی آشوبی دینامیک فضایی - زمانی غنی‌تر و ساختار پیچیده‎تری دارند؛ بنابراین انتظار می­رود توان بالایی برای یافتن نقطه بهینه سراسری و یا نزدیک به سراسری داشته باشند. از مهم‌ترین مشکلات شبکه‎های مصنوعیِ سنتی گرفتاری آن‌ها در کمینه‎های محلی و همگرایی به سمت نقطه تعادل مطلوب است؛ بنابراین در این مقاله سعی شده است با افزودن نمای لیاپانوف و یک پارامتر کنترلی z(t) به شبکه به‌عنوان تبرید تدریجی، نحوه خروج از دینامیک آشوبی به سمت نقطه تعادل پایدار و رفتار متناوب را کنترل کرد؛ البته اگرچه دینامیک شبکه عصبی آشوب‎گون دارای ویژگی حرکت آشوبی در فضای حالت با ساختار فرکتالی بوده است و سبب حلِ نسبی گرفتاری در کمینه محلی می‎شود، اما مشکل همگرایی دینامیک آشوبی هنوز به نحو مطلوبی حل نشده است. به‎منظور به‎دست‌آوردن دو مزیت دینامیک­های همگرایی و آشوبی، شبکه عصبی آشوبی با پسخوراند خودی استفاده شده است.

در این پژوهش پارامتر کنترلی z(t) به‌صورت نمایی میراشونده و تانژانت هایپربولیک در نظر گرفته شده است. شکل (3) نشان می­دهد عصب دارای رفتار دینامیکی آشوب‌گون است. واحد عصبی تکی ابتدا به‌صورت جستجوی آشوب­گون سراسری رفتار می­کند و با کاهش مقدار zi(t)‎ انشعاب معکوس به تدریج به حالت تعادل پایدار همگرا می‌شود. پس از اینکه رفتار دینامیکی آشوب گون از بین رفت، دینامیک­های گرادیان نزولی، رفتار دینامیکی واحد عصب تکی را کنترل می‌کند؛ هنگامی که رفتار واحد عصب تکی شبیه به هاپفیلد است، شبکه تمایل به همگرایی به نقطه تعادل پایدار را دارد. همان‎طور که در شکل (3) مشاهده می‎شود x(t) در حدود 800 تکرار اول رفتاری پیش‎بینی‌نشده دارد و سرانجام پس از حدود 1200 تکرار به سمت یک نقطه تعادل پایدار ازطریق یک انشعابِ دو برابر شدنِ متناوبِ معکوس، همگرا می‎شود. مطابق شکل (4) با توجه به اینکه نمای لیاپانوف در حدود 800 تکرارِ اول اغلب مثبت است، رفتار در این ناحیه به­صورت آشوبی و با پنجره­های متناوب ممکن شناخته می‎شود.

شکل­های (3) و (4) نشان می‎دهند که نوسان‌های آشوب به مرور با میرایی z(t) کاهش می‌یابند و سرانجام از بین می­روند؛ البته سرعت این تغییرات به ضریب میرایی β بستگی دارد. به‌طوری‌که هر چقدر β کوچک‌تر باشد، دینامیک آشوبی x(t) مدت زمان بیشتری تداوم می‌یابد. این ویژگی، نشان‌دهنده نوعی از دینامیک آشوبی است و هرگاه مقدار z(t) به اندازة کافی کاهش یابد، ساختار دینامیکی شبکه تقریباً بر شبکه عصبی هاپفیلد منطبق می‎شود.

روش جستجوی آشوبی شبکه‎های عصبی آشوب­گون در یافتن نقطه بهینه سراسری، وابستگی‌نداشتن به شرط اولیه است؛ بنابراین با هر شرط اولیه‎ای به جواب بهینه می‌رسند؛ البته مشکل اصلی در این شبکه‎ها حساسیت زیاد به تنظیم پارامترهای شبکه است و بنابراین ممکن است با تغییر در پارامترها باز هم در کمینه محلی گرفتار شوند،؛ اما احتمال گرفتارشدن آن‌ها نسبت به شبکه‎های سنتی کمتر است.

برای ارزیابی شبکه از TSP متقارن با 10 شهر مختلف استفاده شده است. نتایج نشان می‎دهد با درنظرگرفتن z(t) به‌صورت نمایی میراشونده و انتخاب β=0.006 به بیشترین نرخ کمینه سراسری 100 درصد و نرخ کمینه محلی صفر درصد رسیده و متوسط تعداد تکرارها برای همگرایی 211 است. مرجع ]29[ به ازای β=0.002 به نرخ کمینه سراسری تقریباً 100 درصد دست یافته است؛ درحالی‌که مقاله حاضر به نرخ کمینه سراسری 100 درصد رسیده است. تعداد تکرارها در ]8[ برای رسیدن به نرخ کمینه سراسری 100 درصد 398 است؛ بنابراین در این مقاله تعداد تکرارها کاهش یافته است و درنتیجه سرعت همگرایی بیشتر شده است. همچنین از نظر سرعت همگرایی نتایج این پژوهش بهتر از ]34،35 [است. همچنین نرخ پاسخ‎های نشدنی در ]36[ نیز صفر است که نتایج این پژوهش را تأیید می‎کند. همچنین نرخ پاسخ‌های نشدنی در ]37[ به جز یک مورد صفر است.

همچنین با درنظرگرفتن z(t) به‌صورت تانژانت هایپربولیک و انتخاب β=0.004 به بیشترین نرخ کمینه سراسری 100 درصد و نرخ کمینه محلی صفر درصد رسیده و متوسط تعداد تکرارها برای همگرایی 287 است. همچنین نرخ پاسخ­های نشدنی در ]37[ تقریباً صفر است. همچنین جدول‎های 1 و 2 نشان می‌دهند متوسط تعداد تکرارها برای همگرایی به ازای مقادیر مختلف β به ترتیب 230 و 270 است؛ بنابراین به نظر می‎رسد با درنظرگرفتن z(t) به‌صورت نمایی میراشونده بتوان به تعداد تکرارهای کمتری دست یافت.

همچنین به‎منظور بررسی عملکرد شبکه عصبی آشوب‎گون برای حل TSP، پاسخ­های آن برای 5 توزیع 10 شهری، 5 توزیع 20 شهری و درنهایت 5 توزیع 150 شهری در شکل (6) محاسبه شده است. نتایج شبیه‎سازی نشان می‎دهد، این شبکه‎ می‎تواند جواب بهینه را در مسائل بهینه‎سازی ترکیبی نظیر TSP پیدا کند. همچنین نتایج نشان می‎دهد در برخی موارد بهبود خوبی نسبت به پژوهش­های گذشته ]‎35،34،29،10،8 [حاصل شده است. در برخی نیز، نتایج پژوهش­های گذشته را تأیید می­کند ]36،29،28[. در مقایسه با پژوهش‎های گذشته مشاهده می‎شود متوسط زمان همگرایی و تعداد تکرارهای آن برای هر توزیع از شهرهای آزمایش‌شده بهبود یافته است.

 

References

[1]     Freeman, W. J., “Strange Attractors that Govern Mammalian Brain Dynamics Shown by Trajectories of Electroencephalographic (EEG) Potential,” IEEE Transaction on Circuits and systems, Vol. 35, No. 7, pp. 781-783, 1988.
[2]     Taherkhani, A., Mohammadi, A., Seyyedsalehi, S. A., Davande, H., “Design of a Chaotic Neural Network by using Chaotic Nodes and NDRAM Network,” IEEE International Joint Conference on Neural Networks (IEEE World Congress on Computational Intelligence), Hong Kong, pp. 3500-3504, 2008.
[3]     He, G., Shrimali, M. D., Aihara, K., “Threshold Control of Chaotic Neural Network,” Neural Networks, Vol. 21, No. 2-3, pp. 114-121, 2008.
[4]     Kim, S. H., Hong, S. D., Park, W. W., “An Adaptive Neurocontroller with Modified Chaotic Neural Networks,” International IEEE Joint Conference on Neural Networks, Washington, DC, Vol. 1, pp. 509-514, 2001.
[5]     Kwok, T., Smith K. A., “Experimental Analysis of Chaotic Neural Network Models for Combinatorial Optlmization under a Unifying Framework,” Neural Network, Vol. 13, No. 5, pp. 731-744, 2000.
[6]     Bersini, H., Sener, P., “The Connections between the Frustrated Chaos and the Intermittency Chaos in Small Hopfield Networks,” Neural Networks, Vol. 15, No. 10, pp. 1197–1204, 2002.
[7]     Hasegawa, M., Ikeguchi, T., Aihara, K., “Solving Large Scale Traveling Salesman Problems by Chaotic Neurodynamics Problems,” Neural Network, Vol. 15, No. l, pp. 271-283, 2002.
[8]     Chen, L., Aihara, K., “Chaotic Simulated Annealing by A Neural Network Model with Transient Chaos,” Neural Networks, Vol. 8, No. 6, pp. 915–930, 1995.
[9]     Zhao, L., Sun, M., Cheng, J., Xu, Y., “A Novel Chaotic Neural Network with the Ability to Characterize Local Features and its Application,” IEEE Transactions on Neural Networks, Vol. 20, No. 4, pp. 735-742, 2009.
[10]     Xu, Y., Yang, X., “Chaotic Neural Network with Sigmoid Function Self-Feedback,” 6th International Conference on Natural Computation, pp. 1605-1609, 2010.
[11]     Aihara, K., Takabe, T., Toyoda, M., “Chaotic Neural Networks,” Phys. Lett. A, Vol. 144, No. 6-7, pp. 333–340, 1990.
[12]     Chartier, S., Boukadoum, M., “A Chaotic Bidirectional Associative Memory,” Proceedings of Maghrebian Conference on Software Engineering and Artificial Intelligence, Agadir, Morocco, pp. 498-501, 2006.
[13]     Chartier, S., Renaud, P., Boukadoum, M., “A Nonlinear Dynamic Artificial Neural Network Model of Memory,” New Ideas in Psychology, Vol. 26, No. 2, pp. 252-277, 2007.
[14]     Weise, T., Chiong, R., Lassig, J., Tang, K., Tsutsui, S., Chen, W., Michalewicz, Z., Yao, X., “Benchmarking Optimization Algorithms: An Open Source Framework for the Traveling Salesman Problem,” Vol. 9, No. 3, pp. 40-52, 2014.
[15]     Fujimura, K., Fujiwaki, S., Kwaw, O. C., Tokutaka, H., “Optimization of Electronic Chip-mounting Machine using SOM-TSP Method with 5 Dimensional Data,” International Conferences on Info-tech and Info-net, Vol. 4, pp. 26-31, 2001.
[16]     Mehmet-Ali, M. K., Kamoun, F., “Neural Networks for Shortest Path Computation and Routing in Computer Networks,” IEEE Transactions on Neural Networks, Vol. 4, No. 6, pp. 941-954, 1993.
[17]     Saadatmand-Tarzjan, M., Khademi, M., Akbarzadeh-T., M. R., Abrishami-Moghaddam. H., “A Novel Constructive-Optimizer Neural Network for the Traveling Salesman Problem,” IEEE Transactions on Systems, Man, and Cybernetics, Part B, Vol. 37, No. 4, pp. 754 - 770, 2007.
[18]     Tian, F., Wang, L., “Chaotic Simulated Annealing with Augmented Lagrange for Solving Combinatorial Optimization Problems,” 26th Annual Conference of the IEEE Industrial Electronics Society, Vol. 4, pp. 2722 -2725, 2000.
[19]     Osaba, E., Diaz, F., “Comparison of a Memetic Algorithm and a Tabu Search Algorithm for the Traveling Salesman Problem,” Conference on Computer Science and Information Systems, pp. 131-136, 2012. 
[20]     Nguyen, H. D., Yoshihara, I., Yamamori, K., Yasunaga, M., “Implementation of an Effective Hybrid GA for Large-Scale Traveling Salesman Problems,” IEEE Transactions on Systems, Man, and Cybernetics, Part B, Vol.37 , No.1, pp. 92-99, 2007.
[21]     Li, M., “Efficiency Improvement of Ant Colony Optimization in Solving the Moderate LTSP,” Journal of Systems Engineering and Electronics, Vol. 26, No. 6, pp. 1300-1308, 2015. 
[22]     Kirkpatrick, S., Gelatt, C. D., Vecchi, M. P., “Optimization by Simulated Annealing,” Science, Vol. 220, No. 4598, pp. 671–680, 1983.
[23]     Akiyama, Y., Yamashira, A., Kajiura, M., Anzal, Y., Aiso, H., “The Ganssian Machine: a Stochastic Neural Network for Solving Assignment Problems,” Journal of Neural Network Computation, Vol. 2, pp. 43-51, 1991.
[24]     Nakagawa, M., “A Novel Chaos Associative Memory,” 6th International Conference on Neural Information Processing, Vol. 3, pp. 1106–1111, 1999.
[25]     Uwate, Y., Nishio, Y., Ikeguchi, T., “Associative Memory by Hopfield NN with Chaos Injection,” IEEE International Joint Conference on Neural Networks, Vol. 1, 2004.
[26]     Kanter, I., Sompolinsky, H., “Associative Recall of Memory without Errors,” Physical Review A, Vol. 35, No. 1, p. 380, 1987.
[27]      Taherkhani, A., Javadi, S., Moeini, S., “Design of a chaotic feed forward neural network,” ISEE  Computational Intelligence in Electrical Engineering, Vol. 2, No. 4, pp. 21- 34, 2012.
[28]     Xu, Y., Yang, X., “A class of Chaotic Neural Network with Morlet Wavelet Function Self-feedback,” in Bio-Inspired Computing and Applications, Springer, 7th International Conference on Intelligent Computing, pp. 32–40, 2012.
[29]     Ye, Y., “Bessel Function Self-Feedback Chaotic Neural Network Model and Applications,” International Journal of Hybrid Information Technology, Vol. 7, No. 4, pp. 19–28, 2014.
[30]     Xu, X., Tang, Z., Wang, J., “A Method to Improve the Transiently Chaotic Neural Network,” Neurocomputing, Vol. 67, pp. 456-463, 2005.
[31]     Kurths, J., Herzel, H., “An Attractor in Solar Time Series,” Physica D, Vol. 25, No. 1-3, pp. 165-172, 1987.
[32]     Wolf, A., Swift, J. B., Swinney, H. L., Vastano, J. A., “Determining Lyapunov Exponents from a Time Series,” Physica, Vol. 16, No. 3, pp. 285-317, 1985.
[33]     Wilson, G. V., Pawley, G. S., “On the Stability of the Traveling Salesman Problem Algorithm of Hopfield and Tank,” Biological Cybernetics, Vol. 58, No. 1, pp. 63-70, 1988.
[34]     Zhou, C.S., Chen, T. L., Huang, W.Q., “Chaotic Neural Network with Nonlinear Self-feedback and Its Application in Optimization,” Vol. 14, No. 3, pp. 209-222, 1997.
[35]     Zhou, C.S., Chen, T. L., “Chaotic Annealing for Optimization,” Phys. Rev. E, Vol. 55, No. 3, pp. 2580-2587, 1997.
[36]     Yang, L.J., Chen, T. L., Huang, W.Q., “Dynamics of Transiently Chaotic Neural Network and Its Application to Optimization,” Communications in Theoretical Physics, Vol. 35, No. 1, pp. 22-27, 2001.
[37]     Xu, Y., Zhao, T., “Chaotic Neural Network with Nonlinear Function Self-feedback,” 33rd Chinese Control Conference, pp. 5075 - 5079, 2014.
 

Files

History

  • Receive Date: 23 November 2016
  • Revise Date: 16 January 2017
  • Accept Date: 23 November 2016

Share

How to cite

Statistics