
تعداد نشریات | 43 |
تعداد شمارهها | 1,712 |
تعداد مقالات | 14,033 |
تعداد مشاهده مقاله | 33,940,264 |
تعداد دریافت فایل اصل مقاله | 13,585,225 |
ترکیب بهینه شبکه عصبی آشوبگون با پسخوراند خودی، نمای لیاپانوف و تبرید تدریجی در حل مسئله فروشنده دوره گرد | |||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||
هوش محاسباتی در مهندسی برق | |||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||
مقاله 7، دوره 7، شماره 2 - شماره پیاپی 23، تیر 1395، صفحه 63-76 اصل مقاله (401.16 K) | |||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||
نوع مقاله: مقاله پژوهشی فارسی | |||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||
شناسه دیجیتال (DOI): 10.22108/isee.2016.20723 | |||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||
نویسندگان | |||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||
سید عابد حسینی* 1؛ محمد رضا اکبرزاده توتونچی2 | |||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||
1گروه مهندسی فناوری اطلاعات، دانشکدة مهندسی، دانشگاه آزاد اسلامی واحد مشهد – مشهد - ایران | |||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||
2گروههای مهندسی برق و کامپیوتر، قطب علمی رایانش نرم و پردازش هوشمند اطلاعات، دانشکدة مهندسی، دانشگاه فردوسی مشهد - مشهد - ایران. | |||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||
چکیده | |||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||
این مقاله یک ترکیب همافزای شبکه عصبی آشوبگون با پسخوراند خودی، نمای لیاپانوف و تبرید تدریجی را برای حل مسائل بهینهسازی ترکیبی نظیر فروشنده دورهگرد (TSP) پیشنهاد میدهد. برخلاف شبکههای عصبی مصنوعی که با دینامیک گرادیان نزولی به سمت نقطه تعادل پایدار همگرا میشوند، شبکههای عصبی آشوبی دینامیکهای فضایی - زمانی غنیتر و ساختار پیچیدهتری دارند؛ بنابراین انتظار میرود شبکه عصبی آشوبی توان زیادی برای یافتن نقطه بهینه سراسری و یا دستکم نزدیک به سراسری داشته باشد. یکی از مهمترین مشکلات شبکههای عصبی مصنوعی، گرفتاری آنها در کمینههای محلی است. اگرچه شبکههای عصبی آشوبگون تا حدی این مشکل را حل میکنند، ولی به لحاظ سرعت همگرایی در حرکت به سوی نقطه تعادل مشکل دارند؛ بنابراین در این مقاله به کمکِ نمای لیاپانوف و تبرید تدریجی، حضور شبکه در حالت آشوبگون، کنترل و شبکه به سمت نقطه بهینه سراسری هدایت میشود. بهمنظور ارزیابی این شبکه، TSP با تعداد شهرهای مختلف استفاده شده است. نتایج شبیهسازی نشان میدهد این شبکه میتواند جواب بهینه را در TSP با تعداد تکرار کمتر و سرعت بیشتر پیدا کند. | |||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||
کلیدواژهها | |||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||
بهینهسازی؛ تبرید تدریجی؛ نمای لیاپانوف؛ شبکه عصبی آشوب گون؛ فروشنده دوره گرد | |||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||
اصل مقاله | |||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||
مختلف با درنظرگرفتن z(t) بهصورت نمایی میراشونده
جدول (2): نمایش مقادیر نرخ کمینه سراسری، نرخ کمینه محلی، نرخ پاسخهای نشدنی و متوسط تکرارها برای همگرایی به ازای مقادیر βهای مختلف با درنظرگرفتن z(t) بهصورت تانژانت هایپربولیک
جدول (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[. در مقایسه با پژوهشهای گذشته مشاهده میشود متوسط زمان همگرایی و تعداد تکرارهای آن برای هر توزیع از شهرهای آزمایششده بهبود یافته است.
| |||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||
مراجع | |||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||
[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.
| |||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||
آمار تعداد مشاهده مقاله: 838 تعداد دریافت فایل اصل مقاله: 613 |