شبکه‌های اسپینی بستری برای پردازش توزیع شده: مطالعه موردی حل مسئله انتخاب بهینه‌سبدسهام

نوع مقاله: مقاله پژوهشی

نویسندگان

1 دانشیار، گروه کامپیوتر، دانشکده فنی و مهندسی دانشگاه آزاد اسلامی واحد مشهد،ایران

2 استاد، گروه برق، دانشکده فنی و مهندسی، دانشگاه فردوسی مشهد

چکیده

امروزه خواص فیزیکی اجسام، دستاویزی برای حل مسائل بهینه‌سازی است تا پاسخ بهینه مسائل با تعداد حالات زیاد سریع‌تر و دقیق‌تر یافته شود. به‌عنوان نمونه می‌توان به الگوریتم‌‌های بهینه‌سازی مبتنی بر اسپین‌گلاس (شبکه‌های اسپینی)‌ اشاره کرد که به‌دلیل داشتن قابلیت جستجوی محلی و پردازش توزیع شده مورد توجه قرار دارند. از آنجایی که شبکه‌های اسپینی، بیشتر مبتنی بر الگوریتم‌های تصادفی - مونت‌کارلو همچون تبرید تدریجی (SA) برای یافتن حالت بهینه استفاده می‌کنند، از سرعت همگرایی پائینی برخورداند. بنابراین برای افزایش سرعت، از الگوریتم‌های بهینه‌سازی اکتشافی، تکاملی و غیره استفاده می‌شود. در این مقاله با در نظر گرفتن قابلیت شبکه‌اسپینی در حل مسائل بهینه‌سازی،کوشش شده است یکی از مسائل غیرچندجمله‌ای (NP) با عنوان مسئله انتخاب بهینه سبدسهام با استفاده از تبرید تدریجی حل شود؛ سپس با توجه به خواص توزیع‌شده‌گی اینگونه از شبکه‌ها، الگوریتم جدید مبتنی بر اتوماتای‌یادگیر(LA) بعنوان پردازش متمرکزو همچنین بهینه‌سازی‌اکسترمال (EO) بعنوان پردازش توزیع شده، ارائه گردیده است. نتایج آزمایش‌ها نشان می‌دهند که هرچند دو الگوریتم ارائه شده از حیث عملکرد، متفاوتند؛ ‌‌‌‌ولی هردو در محدوده پاسخ، تقریبا توزیع احتمال یکسانی برای انتخاب اسپین‌های برتر فراهم می‌کنند. به عبارت دیگر این دو روش از مرحله‌‌ای به بعد، شبیه هم عمل کرده و نتایج یکسانی تولید می‌کنند و کارایی شبکه‌های اسپینی از حیث سرعت همگرایی با حفظ دقت را به مقدار زیادی افزایش می‌دهند. همچنین دستاوردها نشان می‌دهد که انتخاب روش مبتنی بر LA یا EO  برای شبکه‌های با تعداد اسپین‌کم تفاوتی ندارد؛ اما برای شبکه‌های بزرگ، EO که توانایی پردازش توزیع شده منحصر بفردی دارد، بسیار بهتر از روش‌های مبتنی بر یادگیری پاسخ می‌دهد که نتایج آزمایش‌های حاصل بر 5 بورس معتبر دنیا این موضوع را تائید می‌کند.

کلیدواژه‌ها


عنوان مقاله [English]

Spin Glasses, the way to Distributed Processing Case Study on Stock Market Portfolio Selection

نویسندگان [English]

  • Majid Vafaei Jahan 1
  • mohammadreza Akbarzadeh Tutunchi 2
1 Associate Professor, Department of Computer Software, Faculty of Engineering and Engineering, Islamic Azad University, Mashhad Branch
2 Professor, Department of Electrical Engineering, Faculty of Engineering and Engineering, Ferdowsi University of Mashhad
چکیده [English]

The several heuristic algorithms have been proposed for portfolio selection. One of these algorithms is based on spin glasses that have local searching and parallel processing properties. Because of the spin glass algorithms are actually based on Monte Carlo simulation such as simulated annealing (SA) and have low convergence speed against other method, yet composing with other methods such as Learning Automata (LA) and genetic algorithms have been considered. In this paper, one of the composing methods based on SA and Exteremal Optimization (EO) has been proposed, this algorithm select and change the low order spins with higher probability and take the state of all spins into the better situation. After a sufficient number of steps, the system reaches a highly correlated that almost all species have reached fitness above a certain threshold. This co-evolutionary activity gives rise to chain reactions and every fluctuation that rearrange major parts of the system, potentially making any configuration accessible. Therefore any fluctuations allow escaping from local minima and efficiently explore the configuration space. The experimental results show this method is powerful paradigm for finding ground state of spin glass and better than other methods such as SA and LA for solving portfolio selection problem.

کلیدواژه‌ها [English]

  • Spin glass Model
  • Portfolio Selection
  • Simulated Annealing
  • Learning Automata
  • Extremal Optimization