دانلود مقاله َکاربرد الگوریتم مورچگان در مدل سازی مالی

بخشی از مقاله

کاربرد الگوریتم مورچگان در مدل سازی مالی

چکیده:
زندگی اجتماعی و رفتار پیچیده مورچه ها سال هاست که ذهن بسیاری از محققان و اندیشمندان را به خود مشغول داشته است. الگوریتم مورچگان به عنوان یکی از تکنیک های حل مسئله با مداقه در زندگی مورچه ها در سال 1992 توسط مارکو دوریگو مطرح گردید. این الگوریتم زیر گروهی از "هوش انبوه زی " است. رفتارهای شاخص غذا جویی، ازاله اجساد و دسته بندی لاروها، تخصیص کار و تعاون در کلونی و لانه سازی مورچه های طبیعی در طراحی این الگوریتم ها مورد استفاده قرار می گیرد. این الگوریتم ها را می توان به سه گروه "الگوریتم جمعیت مدار "، "الگوریتم بهینه ساز " و "الگوریتم دسته بندی " تقسیم نمود. از جمله محاسن این الگوریتم "بازخورد مثبت " و "پردازش توزیع یافته " است. با توجه به گسترش کاربرد این گونه الگوریتم ها، مقاله حاضر به معرفی و تشریح مدل سازی مسائل مالی با الگوریتم مورچگان و کاربردهای این روش در حوزه علوم مالی می پردازد.
واژه های کلیدی: هوش مصنوعی ، هوش انبوه زی، بهینه سازی ترکیبی ، الگوریتم مورچگان
مقدمه و هدف:
بشر همواره در صدد الگوبرداری از طبیعت بوده و اولین مرجع پاسخگو به سوالات این فرزند کنجکاو، "مادر طبیعت" بوده است. امروزه پیشرفت فن آوری اطلاعات و توانایی تقلید رایانه ها از قدرت تفکر و یادگیری بشر، الگوبرداری از طبیعت و شبیه سازی آن برای حل مسائل، را کاربردی نموده است. در این میان مداقه در رفتار حشرات اجتماعی تاثیر بسزایی بر راه حل مسائل پیچیده گذارده است. این راه حل ها با نام "هوش انبوه زی" معروفند (Kumar & Thulasiram, 2008). هوش انبوه زی به عنوان زیرگروهی از هوش مصنوعی در طراحی الگوریتم هایی مورد استفاده قرار می گیرد که می توانند فرآیند حل مسئله را با ایجاد یک "جمعیت حل کنندگان مسئله" با موفقیت انجام دهند (Brabozan & O’Nell, 2007).
در میان این جمعیت شاید مورچه ها، بدلیل دردسترس بودن و معاصر بودن با دوره های مختلف زندگی بشری، ذهن بسیاری از محققان و اندیشمندان را به خود مشغول داشته اند. . موریس مترلینگ در زمان خود در کتاب "مورچگان" اینگونه می نویسد: "ما برای کشف اسرار دنیا، امروز در وضع زندگی نژادهای اولیه بشر که صدها هزار سال و شاید میلیون ها سال، جلوتر از ما به دنیا آمده اند مطالعه می کنیم. در این صورت چرا از مطالعه در وضع زندگی موجوداتی که معاصر ما هستند و در عین حال می دانیم که میلیون ها و بلکه صدها میلیون سال از ما زودتر به دنیا آمده اند غفلت نماییم." (مترلینگ، 1386).
الگوریتم مورچگان به عنوان فن حل مسئله از رفتار مورچه های طبیعی الهام می گیرد. این الگوریتم که بر اساس میزان فرمون ترشح یافته توسط مورچه های مصنوعی بر اجزاء راه حل عمل می کند، با به هنگام رسانی راه حل اولیه در هر تکرار الگوریتم امکان دست یابی به جواب بهینه تر را فراهم می سازد (فرقاندوست حقیقی و کاظمی، 1389). با توجه به گسترش کاربرد این گونه الگوریتم ها، مقاله حاضر به معرفی و تشریح مدل سازی مسائل مالی با الگوریتم مورچگان و کاربردهای این روش در حوزه علوم مالی می پردازد.
الگوریتم مورچگان
الگوریتم مورچگان به عنوان یکی از فنون حل مسئله با مداقه در زندگی مورچه ها در سال 1992 توسط مارکو دوریگو مطرح گردید رفتارهای شاخص غذا جویی، ازاله اجساد و دسته بندی لاروها، تخصیص کار و تعاون در کلونی و لانه سازی مورچه های طبیعی در طراحی این الگوریتم ها مورد استفاده قرار می گیرد (Engelbrecht, 2007). این الگوریتم ها را می توان به سه گروه "الگوریتم جمعیت مدار"، "الگوریتم بهینه ساز" و "الگوریتم دسته بندی" تقسیم نمود. از جمله محاسن این الگوریتم "بازخورد مثبت" و "پردازش توزیع یافته" است. بازخورد مثبت موجب کشف سریع جواب مناسب می شود و پردازش توزیع یافته از همگرایی زودرس به جواب بهینه جلوگیری می نماید (فرقاندوست حقیقی و کاظمی، 1389).
رفتار غذاجویی مورچه ها و الگوریتم بهینه یابی:
حس بینایی مورچه ها بسیار ضعیف است به طوری که گروهی از آن ها کاملا نابینا هستند. به همین دلیل بیشتر مورچه ها از طریق ترشح ماده شیمیایی به نام فرمون با محیط و سایر اعضاء کلونی ارتباط برقرار می کنند. برخی انواع مورچه ها مانند مورچه های لاسیوس نیگر و مورچه های آرژانتینی از ماده فرمون برای علامت گذاری مسیر حرکت خود استفاده می کنند. مورچه ها با حس و درک نوار فرمون می توانند مسیر لانه تا منبع غذایی را ردیابی کنند. مفاهیم ترشح نوار فرمون، ردیابی و تعقیب مسیر فرمون ترشح شده توسط مورچه های دیگر، اساس الگوریتم بهینه یابی مورچگان را تشکیل می دهد (Dorigo& Stutzle, 2004).
هنگامی كه مورچه به دنبال يك منبع غذايي مي‌گردد، هريك از مورچه‌هاي عضو، نواري مستقیم از هورمون شيميايي فرمون را از لانه تا منبع غذاي از خود ترشح مي‌كنند (شکل A-1). زماني كه مانعی در مسير حركت مورچه‌ها قرار می گیرد، نوار فرمون را قطع می کند (شکل B-1). مورچه های پیشرو قادر به ردیابی نوار فرمون قبلی نخواهند بود لذا به طور اتفاقی یکی از دو مسیر کوتاه یا بلند را انتخاب می کنند. در این حالت می توان فرض کرد نیمی از مورچه ها مسیر کوتاه تر و نیمی دیگر مسیر بلندتر را طی خواهند نمود (شکل C-1). بدلیل تراکم بیشتر مورچه ها در مسیر کوتاه تر، فرمون با سرعت و قوت بیشتری ترشح می شود. در نتیجه غلظت فرمون ترشح شده در مسیر کوتاه تر در هر بازه زمانی بیشتر از غلظت فرمون ترشح شده در مسیر بلندتر خواهد بود. بدین ترتیب تعداد بیشتری از مورچه ها مسیر کوتاه تر را ترجیح داده و طی این بازخورد مثبت همه مورچه ها به سرعت به سمت مسیر کوتاه تر سوق داده می شوند (شکل D-1) (Dorigo& Gambardella, 1997).

شکل 1 – رفتار غذاجویی مورچه ها (Dorigo& Gambardella, 1997)
با عبور مورچه‌ها از مسير نزديك‌تر، فرمون اين مسير به عنوان مسير بهتر تقويت شده و بركيفيت و غلظت آن افزوده مي‌شود ولي فرمون مسير دورتر، تبخير شده و از كيفيت آن كاسته مي‌شود (فرقاندوست حقیقی و کاظمی، 1389). با الهام گرفتن از فرآیند فوق و با استفاده از آزمایشات و تحقیقات انجام شده توسط دنوبرگ می توان مورچه های مصنوعی طراحی کرد که با حرکت و ترشح فرمون بر روی یک مدل گراف از یک مسیر دوگانه، بتوانند کوتاهترین مسیر را بین دو نقطه لانه و منبع غذا پیدا کنند (دوریگو و اشتوتچل، 1386).
مدل سازی مسائل مالی با استفاده از الگوریتم مورچگان:
با توجه به رفتار غذاجویی و فرآیند بهینه یابی توسط جمعیت مورچگان می توان الگوریتم بهینه یابی مورچگان را یک الگوریتم ساختگرا تلقی کرد. این الگوریتم ها، حل مسئله را با یک جواب تهی اولیه آغاز کرده و طی تکرارهای متوالی بخش های مناسب جواب را به جواب اولیه اضافه می کنند. در این نوع الگوریتم ها باید رویه ای برای افزودن اجزاء مختلف جواب به جواب اولیه تعریف شود (سپهری و رحیمی مقدم، 1387). این فرآیند در مورد الگوریتم مورچگان که بر اساس ردیابی نوار فرمون طراحی می شود بروی فرمون ترشح شده اعمال می شود.
با توجه به مطالب ذکر شده می توان افزود كه اين الگوريتم شامل مراحل مقداردهي اوليه (ترشح فرمون اوليه)، انتخاب راه حل (مسير) مناسب و مرحله به هنگام رسانی در هر تکرار مي‌باشد. مرحله به هنگام رسانی نیز از دو فرآيند "ترشح" و "تبخير" نوار فرمون شکل می گیرد. نوار فرمون ترشح شده توسط مورچه‌ها در طول زمان منجر به ايجاد يك "حافظه جمعي " در ارتباط با بهینگی تابع هدف مي‌شود. به عبارت دیگر نوار فرمون عامل انتقال دهنده تجربه مورچه ها در مورد حل مسئله به یکدیگر طی تکرارهای متوالی الگوریتم می باشد.
در اين الگوريتم مجموعه ای از مورچه‌هاي مصنوعي به صورت اتفاقي راه ‌حل‌هایي برای مسئله طراحي مي‌كنند. اين مورچه‌ها براي طراحي راه حل از نوار مصنوعي فرمون استفاده مي‌كنند كه غلظت آن طی روند اجرای الگوريتم تغيير مي‌يابد. هر راه حل از قطعات جداگانه‌اي تشكيل شده است. طي مرحله مدل سازی، هر مورچه با استفاده از تركيب اين قطعات، راه حل كامل را طراحي مي كند. ماهيت اين قطعات به نوع مسئله بستگي دارد (Brabozan & O’Nell, 2007).
یکی از رویکردهای مورد استفاده جهت اعمال الگوریتم مورچگان برای حل مسائل پیچیده مالی، تعریف مسئله و فضای جواب به صورت گراف G=(N,A) می باشد که در آن N گره با A یال به یکدیگر متصل شده اند. ماهیت تابع هدف و محدودیت های مسئله، نحوه همسایگی گره ها را مشخص می کند.
هر یال، یک جزء از راه حل کامل مسئله را تشکیل می دهد که توسط مورچه های مصنوعی با هورمون فرمون علامت گذاری می شود. گره ها نماینده عناصر اساسی مسئله هستند. به عنوان مثال در مورد مسئله بهینه سازی سبد سهام، هر گره نماینده یک سهم از کل سهام موجود در بازار می باشد که هر گره نیز با یک یال به دیگری متصل شده است (Maringer, 2006).
فرآیند حل مسئله را می توان با تعریف ماتریس اولیه آغاز کرد. در این ماتریس N نماینده تعداد گره و ijτ نیز نماینده مقدار فرمون موجود روی یال میان دو گره i و j می باشد. ijτ اولیه، یک مقدار کوچک مثبت تعریف می شود. طی فرآیند حل مسئله مورچه ها به عنوان عوامل حل کننده در فضای جواب مسئله تزریق می شوند. هر یال نماینده یک مسیر پیش روی مورچه می باشد. گرهی که مورچه در آن مستقر است یک نقطه تصمیم برای مورچه است. این گره را گره مبدا می نامیم. گره های دیگری که در همسایگی گره مبدا قرار دارند و به گره مبدا متصل شده اند را گره مقصد می نامیم. مورچه مستقر در گره مبدا باید یکی از مسیرهای منتهی به یک گره مقصد را انتخاب نماید. این انتخاب، بر اساس كيفيت فرمون ترشح شده روي یال مربوطه انجام می گیرد. اگر مورچه روی گره i باشد، احتمال انتخاب گره j از ميان مجموعه گره های همسایه گره i با استفاده از معادله زير محاسبه مي‌شود:

معادله 1 – استراتژی تصمیم گیری (دوریگو و اشتوتچل، 1386)

در اینجا گره های موجود در همسایگی گره i است که مورچه K در این گره مستقر است. همسایگی گره i شامل تمام نقاطی است که به صورت مستقیم به i متصل شده اند.
یک مورچه به منظور تشکیل یک راه حل کامل به طور مرتب از گرهی به گره دیگر می رود تا با استراتژی تصمیم گیری بیان شده به گره نهایی برسد و محدودیت های مسئله را تامین کند. پس از آنكه تمام مورچه‌ها، يك راه حل براي مسئله طراحي كردند، فرمون ترشح شده روي هر یال، به هنگام رسانی مي‌شود. مرحله به هنگام رسانی شامل دو فرآیند ترشح و تبخیر فرمون است. این مرحله را نیز می توان بر اساس معادله زیر تشریح کرد:

معادله 2 – به هنگام سازی (Brabozan & O’Nell, 2007)

در این معادله، نماینده غلظت فرمون مسیر i به j در تکرار t ام الگوریتم، ρ نرخ تبخیر و نیز نماینده هورمون ترشح شده بروی مسیر راه حل طی تکرار1+t ام الگوریتم می باشد. طي فرآیند تبخير غلظت فرمون یال ij، با نرخ تبخير ρ كاهش مي‌يابد. ρ عددی است بین صفر و یک که نقش مهمی در همگرایی الگوریتم به جواب بهینه محلی دارد.
• اگر ρ به عدد 1 نزديك باشد، فرمون ترشح شده روي یال ها در تكرار t ام به مقدار زيادي تبخير مي‌شوند و از كيفيت آن ها به شدت کاسته می شود. در اين حالت شديداً به یا ترشح فرمون روي یال ij در تكرار 1+t ام بستگي دارد. در اين حالت تقريباً فرمون تمام یال ها تبخير مي‌شود و يك همانندي بين گره ها بوجود مي‌آيد. اين امر منجر به يك جستجوي موضعي پيرامون راه‌حل مناسب‌تر مي‌شود.
• اگر ρ كوچكتر باشد و به سمت صفر ميل كند، به كيفيت فرمون یال ij در تكرار t ام و هم به میزان فرمون ترشح شده روي مسیر ij در تكرار (1+ t) ام بستگي خواهد داشت.
میزان فرمون ترشح شده طی مرحله به هنگام سازی بسته به نوع الگوریتم متفاوت است. این فرآیند می تواند فقط بروی بهترین راه حل کشف شده در هر تکرار اعمال شود و یا با وزن های متفاوت بروی راه حل های مختلف اعمال شود. در این حالت وزن فرآیند ترشح لحاظ شده برای هر راه حل می تواند تابعی از کیفیت جواب هر یک از راه حل ها باشد (Brabozan & O’Nell, 2007). به عنوان مثال مارینگر در مقاله خود در مورد بهینه سازی سبد سهام، را به صورت تابعی از ریسک و بازده سبد انتخابی تعریف می کند:

معادله 3 – فرآیند ترشح در مسئله بهینه سازی سبد سهام (Maringer, 2006)
در اینجا Q یک عدد ثابت، pu سبد سهام تشکیل شده توسط مورچه u می باشد. نیز به صورت زیر تعریف می شود که در آن r نماینده بازده و نماینده ریسک سبد سهام می باشد:

معادله 4 – نسبت بازده به ریسک (Maringer, 2006)

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