مقاله کاربرد مالی الگوریتم تکاملی ازدحام ذرات

بخشی از مقاله

*** این فایل شامل تعدادی فرمول می باشد و در سایت قابل نمایش نیست ***

کاربرد مالی الگوریتم تکاملی ازدحام ذرات
خلاصه
تقلید از موجودات زنده براي استفاده در الگوریتمهاي قدرتمند براي مسائل بهینه سازي مورد توجه قرار گرفت که "روشهاي محاسبات تکاملی" نام گرفتند. اکثر روشهاي کلاسیک بهینهیابی داراي این اشکال عمده هستند که به محض رسیدن به اولین نقطهي بهینه موضوعی متوقف شده و توانایی خروج از این نقطه و حرکت به سوي نقطه بهینه مطلق را ندارند. به این مفهوم که الگوریتمهاي تکاملی معمولا ماکزیمم (مینیمم) ساز هستند . الگوریتم تکاملی ازدحام ذرات از روشهاي ناپارامتریک مبتنی بر هوش مصنوعی انبوه زیان میباشد که در علوم کاربرد زیادي یافته است. در این مقاله به طور خلاصه به معرفی الگوریتم تکاملی ازدحام ذرات و کاربرد مالی آن پرداخته شده است.
کلمات کلیدي: الگوریتم تکاملی ازدحام ذرات، کاربرد مالی، عامل فشار، جمعیت اولیه، تابع برازندگی.

.1 مقدمه
از سال 1960 تقلید از موجودات زنده براي استفاده در الگوریتمهاي قدرتمند براي مسائل بهینه سازي مورد توجه قرار گرفت که "روشهاي محاسبات تکاملی" نام گرفتند. اکثر روشهاي کلاسیک بهینهیابی داراي این اشکال عمده هستند که به محض رسیدن به اولین نقطهي بهینه موضوعی متوقف شده و توانایی خروج از این نقطه و حرکت به سوي نقطه بهینه مطلق را ندارند. منظور از نقطه بهینه محلی و مطلق، نقطه ماکزیمم (مینیمم) محلی و مطلق میباشد. به این مفهوم که الگوریتمهاي تکاملی معمولا ماکزیمم (مینیمم) ساز هستند.
وجه مشترك روشهاي تکاملی آن است که برخلاف روشهاي کلاسیک مرسوم براي حرکت به سوي پاسخ بهینه مسئله به اطلاعات گرادیان مرتبه اول یا مرتبه دوم تابع هدف و محدودیتها، نیازي ندارند. این الگوریتمها براي حل مسائلی با فضاي پاسخ غیرمحدب نیز مناسب میباشند.
روش بهینه سازي اجتماع ذرات (PSO) براي اولین بار در سال 1995 توسط ابرهارت* و کندي معرفی شد .[4] ایده این روش برگرفته از نتایج بدست آمده از شبیهسازي رفتار اجتماعی موجوداتی است که به صورت گروهی زندگی میکنند.
در این الگوریتم حرکت هر یک از اعضاء در راستاي بردار سرعتی است که در هر مرحله با توجه به بهترین تجربه آن عضو و بهترین تجربه اعضاي همسایگی آن عضو اصلاح میشود. به این ترتیب امکان تجربه مکانهاي بهینهتر در فضاي پاسخ مسئله میسر میگردد.
بهطور کلی میتوان گفت ساختار الگوریتم PSO از دو بخش تشکیل شده است: الف) قوانین حرکت و یا جستجو در فضاي پاسخ مسئله.
ب) حافظه الگوریتم که اطلاعات لازم را براي تصمیمگیري هر عضو در انتخاب مسیر بهینه فراهم میکند.

.2 الگوریتم تکاملی ازدحام ذرات
روش بهینه سازي اجتماع ذرات، یکی از روشهاي ابتکاري است که از حرکت جمعی پرندگان یا انواع ماهیان براي یافتن غذا اقتباس شده است. به این ترتیب که تغییر مسیر یا جهتگیري هر عضو از این دسته از حیوانات براساس کسب آگاهی از دو منبع صورت میگیرد. یکی بهترین مکانی که هر عضو به تنهایی تجربه کرده است و در حافظهي خود دارد و دیگري بهترین مکانی است که اعضاء واقع در همسایگی او در طی مسیر تجربه کرده اند. لذا در هر لحظه از زمان، مسیر حرکت بعدي هر عضو از ترکیب دو کمیت فوق تعیین میشود. مفاهیم فوق را میتوان به صورت زیر فرموله کرد .[1]
فرض کنید X و V به ترتیب بردارهاي مختصات مکانی و سرعت هر یک از اعضاي یک گروه باشد. بنابراین میتوان i امین عضو گروه را در یک فضاي n بعدي با دو مشخصه زیر معرفی کرد:
X i  xi1 , xi 2 ,..., xin 
Vi vi1 ,vi2 ,...,vin 

هر عضو داراي حافظهاي است که بهترین مکان تجربه شده خود را در آن نگهداري میکند. حافظهي مربوط به بهترین مکان اعضاي گروه را میتوان بصورت زیر نشان داد:
Pi  Pi1 , Pi2 ,..., Pin 
فرض کنید اجتماع مورد مطالعه داراي h ذره باشد. هر عضو این اجتماع از بهترین مکان که هر یک از اعضاي همسایگی خود تجربه کردهاند اطلاع دارد. این مختصات با بردار Pg مشخص میشود. سرعت و مکان بعدي اعضاء گروه از رابطه زیر بدست میآید:

در روابط فوق داریم
: h تعداد کل اعضاء گروه
: t شمارشگر تعداد حرکت انجام شده در فضاي جستجو
: w(t ) یک ضریب وزنی
ϕ2 ،:ϕ1 ضریب وزنی شتاب دهنده به سوي نقاط بهینه
: rand تابع تولید عدد تصادفی بین 1، 0 با توزیع احتمال یکنواخت استاندارد
بردار سرعت ذره ي i ام در حرکت t ام
بردار مکان ذره ي i ام در حرکت t ام
همانطور که از روابط (1) و (2) مشخص است جهتگیري هر عضو به سوي نقاط بهینه محلی و سراسري توسط ضرایب ϕ2 ،ϕ1 مشخص میگردد. به کمک مقادیر ϕ2 ،ϕ1 میتوان جهتگیري به سوي این نقاط را تنظیم کرد. تجارب مختلف تخصیص عدد 2 را براي این دو پارامتر پیشنهاد میکند .[7] از طرف دیگر ضریب ( w (t در رابطه سرعت به نوعی حافظهي پیشین هر عضو را تبیین میکند. از این رو پیشنهاد میگردد که با حرکت به سوي نقطه سراسري، از تاثیر این ضریب به تدریج کاسته شود. روند کاهش این ضریب را میتوان به صورت خطی از رابطهي زیر تعیین کرد:

که در رابطه فوق tmax حداکثر تعداد تکرار یا تلاش براي یافتن نقطه بهینه میباشد. معمولا wmax  0.9 ،wmin  0.4 انتخاب میشوند .[9]
الگوریتم شبه برنامه الگوریتم بهینه سازي به صورت زیر میباشد:
گام:1 جمعیت اولیه ذرات (بردار سرعت و بردار مکان) را به طور تصادفی مقداردهی کنید. گام:2 برازندگی هر ذره را ارزیابی کنید.
گامPi :3 ، Pg را براي هر ذره محاسبه کنید. گام:4 مراحل زیر تا برقراري معیار توقف اجرا کنید.
گام:1-4 سرعت هر ذره را با استفاده از رابطه (1) محاسبه کنید. گام:2-4 موقعیت (مکان) هر ذره را با استفاده از رابطه (2) بهنگام کنید. گام:3-4 مقدار برازندگی هر ذره را محاسبه کنید.
گام:4-4 اگر مقدار برازندگی در مرحله جاري بهتر از Pi است، Pi را بهنگام کنید.
گامPg :5-4 را بهنگام کنید یعنی از بین ذرههاي همسایگی، ذره ي داراي بهترین برازندگی را به عنوان Pg انتخاب کنید.
گام:5 (پایان) اگر معیار توقف برقرار است.
عامل فشار k

در الگوریتم PSO مقدار بردار سرعت براي ذرات دور از Pg بزرگ بوده و در نتیجه ذره از محدودة ناحیه جستجو خارج میشود. براي کنترل افزایش بردار سرعت، بردار سرعت را به کران بالاي Vd max محدود میکنیم. قبلا مقادیرضریب وزنی شتاب دهنده به سوي نقاط بهینه یعنی ϕ2 و ϕ1 را برابر 2 در نظر میگرفتند تا به نتایج بهتري برسیم .[7]
اما موریس* در سال 1999 استفاده از عامل فشار k را پیشنهاد داد .[8] در این الگوریتم که مدل عامل فشار (CFM) نامیده میشود به جاي معادله (1) از معادله (4) استفاده میکنیم.


که هدف از بکارگیري عامل فشار جلوگیري از پیشروي بردار سرعت به خارج از محدوده مجاز میباشد. ابرهارت و شی* در سال 2000 نشان دادهاند که با استفاده از عامل فشار به همراه محدود کردن بردار سرعت نتایج بهتري حاصل میشود .[6]

.3 کاربردهاي مالی الگوریتم تکاملی ازدحام ذرات
تخصیص بهینه منابع مالی در بازار سرمایه یکی از اصلیترین موضوعات در خوزه تصمیمات سرمایهگذاري است. هدف در این پژوهش آن است که بهترین چیدمان را از نوع سهام در بازار داشته باشیم که تابع بازده پورتفو ماکزیمم شود و تابع ریسک پورتفو مینیمم شود. از جمله تحقیق در این زمینه با الگوریتمهاي تکاملی میتوان به کارهاي دنور (2001)، ونگ و یانگ (2009) و فرقاندوست و کاظمی (2012) اشاره کرد.

اندازه جمعیت
در حالت کلی هر الگوریتم جستجوي تکاملی با اندازه جمعیت بزرگ برازندگی بهتري دارد ولی اندازه جمعیت خیلی بزرگ هزینه بیشتري از لحاظ ارزیابی تابع برازندگی دارد. به عبارت دیگر اندازه جمعیت کوچکتر کارایی بیشتر داشته و از طرفی براي یافتن نتایج معتبر نیازمند کافی بودن آن اندازه نیز هستیم.

مقداردهی اولیه جمعیت
در این الگوریتم بردار موقعیت هر ذره که هر سهم در پورتفو را نشان میدهد بردارهایی هستند که ضریبی از 0 تا k را میتوانند بپذیرند که میزان هر سهم در پورتفو است. در اینجا ماتریس ذرات را داریم که شامل n ستون به تعداد انواع سهام بازار و m