بخشی از مقاله
*** این فایل شامل تعدادی فرمول می باشد و در سایت قابل نمایش نیست ***
انتخاب ویژگی با استفاده از الگوریتم جمعیت مورچگان باینري
چکیده: استفاده از الگوریتمهاي ابتکاري در حل مسایل بهینه سازي امري ضروري و اجتناب ناپذیر است. در این مقاله، الگوریتم جمعیت مورچگان باینري براي استفاده در حل مساله انتخاب ویژگی بکارگرفته شده و اصلاحاتی بر نسخههاي متداول آن پیشنهاد شده است. روشهاي پیشنهادي در کنار روشهاي متداول در طبقهبندي معنایی تصویر و بازشناسی ارقام دستنویس فارسی آزموده شده و نتایج حاصل از آزمایشها ارائه شده است. این نتایج نشاندهنده آن است که پیشنهادهاي ارائه شده، باعث بهبود کیفیت الگوریتم و تحصیل نتایج بهتر شده است.
کلمات کلیدي: انتخاب ویژگی، کاهش بعد ویژگی، الگوریتم مورچگان باینري، طبقهبندي.
.1مقدمه
پیدا کردن زیر مجموعهاي از ویژگیها، از یک مجموعه بزرگ مسئله اي است که در بسیاري از زمینه ها پیش میآید. از آنجایی که افزایش تعداد ویژگیها هزینه محاسباتی یک سیستم را افزایش میدهد، طراحی و پیاده سازي سیستمها با کمترین تعداد ویژگی ضروري به نظر میرسد. از طرف دیگر توجه به این موضوع بسیار مهم است که باید زیر مجموعه موثري از ویژگیها انتخاب شود که کارآیی قابل قبولی براي سیستم ایجاد کند. این موضوع ما را به سمتی هدایت میکند که از روشهاي جستجو براي پیدا کردن زیر مجموعه اي بهینه از ویژگیها استفاده کنیم.
همه طبقه بند ها در ابعاد پایین نتایج قابل قبولی ارائه میکنند در حالیکه در ابعاد بالا با مشکل شناخته شدهاي به نام curse of dimensionality روبرو هستند.[1] بنابراین، انتخاب ویژگی می تواند تاثیر قابل توجه اي بر نرخ بازشناسی درست الگوریتم طبقهبند، داشته باشد. در حالت عمومی مشخص نیست که کدام زیرمجموعه از ویژگیها بیشترین تمایز را براي کلاسهاي الگو مورد مطالعه ایجاد میکنند و از طرف دیگر
امکان بررسی تمام زیر مجموعه هاي موجود، از نظر صرف وقت، امکانپذیر و مقرون به صرفه نیست. هدف اصلی از انتخاب ویژگی، کاهش بعد بردار ویژگی در طبقه بندي است بطوریکه نرخ طبقهبندي قابل قبولی نیز حاصل شود.[2] در این شرایط ویژگیهایی که قدرت تمایز کمتري دارند، حذف شده و یکسري از ویژگیها که شامل اطلاعات مناسبی براي تمایز کلاسهاي الگو هستند، باقی میمانند.
تاکنون روشهاي زیادي براي استخراج و انتخاب ویژگی ارائه شده است. بسیاري از روشهاي متداول در مرجع[3] مرور و بررسی شدهاند. در دهه قبل استفاده از الگوریتم وراثتی براي انتخاب ویژگی به تفصیل مطالعه و بررسی شده است 2]، -4
.[8 در چند سال اخیر، انتخاب ویژگی با سایر الگوریتمهاي ابتکاري مانند الگوریتم اجتماع ذرات و مقایسه آن با توانایی الگوریتم وراثتی و سایر روشهاي کلاسیک مورد توجه محققان فعال در این زمینه قرار گرفته است1]و.[9
الگوریتم مورچگان، از دسته الگوریتمهاي جستجوي متاهیوریستیک است. این روش، مانند اکثر روشهاي جستجوي تکاملی با یک جمعیت، جستجو را به شکل موازي شروع می کند. سپس شایستگی هر یک از افراد جمعیت را بر اساس یک تابع هزینه تعیین میکند و با استفاده از مقادیر شایستگی، اطلاعات جمعیت را بروز میکند. این روند تا همگرایی الگوریتم ادامه مییابد. الگوریتم جمعیت مورچه در سال 1991 توسط مارکو دوریگو طراحی و معرفی شد.[10] این الگوریتم توانایی زیادي در حل مسایلی دارد که به شکل گراف قابل عرضه و نمایش هستند. براي حل مسائل انتخاب ویژگی با استفاده از این الگوریتم، باید از نسخه باینري الگوریتم استفاده کرد. تا کنون حل مساله انتخاب ویژگی با استفاده از الگوریتم جمعیت مورچه در حالت انتخاب زیر مجموعهاي از ویژگیها در جایی ارائه نشده است(تا جایی که مولفین تحقیق کرده اند). در این مقاله با استفاده از الگوریتمهاي جمعیت مورچه ابزاري مناسب در انتخاب ویژگی ارائه خواهد شد.
ادامه این مقاله اینگونه سازماندهی شده است که در بخش دوم الگوریتم جمعیت مورچگان باینري ارائه و معرفی خواهد شد.
در بخش سوم روشهایی بهبود یافتهاي از این الگوریتم معرفی و پیشنهاد میشود. در بخش چهارم، مساله انتخاب ویژگی با استفاده از الگوریتمهاي مورچه مورد کاوش و آزمایش قرار گرفته و نتایج آزمایشها عرضه میشودنهایتاً. در بخش پنجم مقاله جمع بندي و نتیجه گیري میشود.
.2الگوریتم مورچگان
1-2 مروري بر الگوریتم مورچگان
این الگوریتم، با الهام از رفتار مورچهها در طبیعت ایجـاد شـده است, چرا که قادرند با وجود کور و کم هوش بودن، کوتاهترین مسیر رفت و برگـشت از خانـه تـا غـذا را پیـدا کننـد. زیـست شناسان دریافتند این قابلیت مورچهها نتیجه ردپـاي فرمـونی1
است که آنها براي برقراري ارتباط با یکدیگر و انتقـال اطلاعـات مسیر از آن استفاده می کنند. این ردپا با ایجـاد یـک پـسخورد مثبت، مورچه ها را به سمت مسیرهاي هر چه کوتاهتر هـدایت می کند.
از جمله محاسن این الگوریتم که توجه محققان را جلب کرده است، می توان به پسخورد مثبت، محاسبات توزیع شده2 و
هیوریستیک آزمند سازنده3 اشاره کرد.[10] پسخورد مثبت، منجر به کشف سریع جوابهاي خوب می شود. محاسبات توزیع شده از همگرایی زودرس و بیموقع جلوگیري میکند و هیوریستیک آزمند سازنده نیز، به کشف جوابهاي قابل قبول در مراحل اولیه جستجو کمک میکند. این ویژگیهاي خاص در ACSA4، باعث شده است که الگوریتمی چند منظوره5،
نیرومند6 و قابل کنترل باشد. این الگوریتم قادر به حل مسائلی است که به شکل گراف قابل نمایش و عرضه باشند. در سال
2000 در مرجع [11] روشی براي حل مسایل فضاي پیوسته و فضاي گسسته باینري با استفاده از الگوریتم مورچه ارائه شد.
در زیر-بخش بعدي به این الگوریتم پرداخته میشود.
2-2 الگوریتم جمعیت مورچگان باینري
در مرجع [11] روشی براي حل مسایل فضاي پیوسته و گسسته باینري با نام TACO7 ارائه شد. در این روش، دو رشته موازي از صفر و یک در نظر گرفته میشود که مورچهها از بین آنها گذشته و یک مسیر از صفرها و یکها میسازند.
مورچهها در این فضا بعد از اتمام سفر خود با توجه به هزینهاي که مسیر طی شده بهمراه داشته است، مقداري رد پا از خود به جاي میگذارند. شکل 1 چگونگی روش مذکور را به تصویر کشیده است.
شکل1 الگوریتم TACO، رشته باینري بوسیله مسیري که مورچه از آن گذر کرده است، مشخص میکند.
در این روش، در قیاس با روش جمعیت مورچگان اصلی در مرحله تصمیم گیري براي انتخاب یک بیت، مورچه ها فقط از
اطلاعات فرمون استفاده میکنند. وقتیکه یک مورچه مرحله تصمیم گیري را براي همه بیتهاي رشته کامل می کند، به این معنی است که یک راه حل براي مساله تولید شده است. این راه حل با استفاده از یک تابع که تابع هزینه نامیده می شود، ارزیابی میشود که نشان دهنده مقدار عددي کیفیت راه حل است. سپس، فرمون مصنوعی مربوط به راه حلهاي متفاوت محاسبه میشود. پس از آن، فرمونهاي مسیرهاي بین بیتها به روز میشوند. این عمل، با تبخیر مقداري از فرمون قبلی و برجاي گذاشتن فرمون جدید در مسیرها همراه است. در این روش احتمال انتخاب موقعیت 1 براي مورچه k ام که در زمان t ام در موقعیت صفر قرار دارد، با رابطه 1 تعیین میشود.
در این رابطه τ01و τ00 به ترتیب بیـانگر ردپـاي فرمـونی روي مسیر متصل کننده 0) به (1 و ردپاي فرمونی روي مسیر 0) بـه
( 0 است. میزان ردپایی که توسط مورچه k ام روي مسیري که از آن گذشته با رابطه 2 تعین میشود.
که در آن Fk مقدار هزینه راه حل تولید شده توسط مورچـه k
ام و Q یک ضریب ثابت است. بعـد از اینکـه تمـام M مورچـه مسیرشان را انتخاب کردند مقدار فرمون برجا مانده برابر اسـت با:
سپس مقدار فرمون مسیر با توجه به فرمول زیر به روز میشود.
در این رابطه ρ ضریب ماندگاري است که مقدار آن بین صـفر و یک است .(0< ρ <1)
در سال 2004 در مرجع [12] روشی براي بهبود الگوریتم TACO ارائه شد. در این روش فرکانس تکرار کلیه زیر مسیرها
محاسبه میشود. چنانچه یک زیر مسیر از زیر مسیر همسایه خود به دفعات بیشتر انتخاب شود، احتمال انتخاب زیر مسیر همسایه 1 میشود. یعنی اینکه این زیر مسیر بطور قطع و یقین انتخاب میشود. از این به بعد به این روش MTACO8
گفته میشود.
-3 روشهاي پیشنهادي براي بهبود TACO
در روش TACO، تمام مورچه با توجه به شایستگیشان بر مسیرهایی که از آنها گذشتهاند، ردپا میگذارند. با اقتباس از روشهاي موجود در الگوریتم فضاي گسسته ACO، روشهایی براي بهبود TACO پیشنهاد میشود.
• پیشنهاد اول
پیشنهاد اول این است که از خصوصیت نخبهگرایی در این الگوریتم استفاده شود. یعنی اینکه علاوه بر آنکه تمام مورچهها در مسیرهاي گذرنده ردپا میگذارند، بهترین مورچه ردپاي بیشتري از خود برجاي بگذارد. از این به بعد به این روش، ETACO9 گفته میشود.
• پیشنهاد دوم
پیشنهاد میشود از ردپا گذاري متناسب با رتبه استفاده شود.
بنابراین، مورچهها براساس شایستگی شان مرتب شده و صرفا k مورچه با رتبه بهتر اجازه داده میشود که ردپا بگذارند. از این به بعد به این روش RTACO10 گفته میشود.
• پیشنهاد سوم
پیشنهاد میشود که مقدار مینیمم و ماکزیمم ردپاي مورچهها بین دو مقدار Tmin و Tmax محدود شود و صرفاٌ به مورچهاي که بهترین تور را پشت سر گذاشته است، اجازه داده میشود که از خود بر مسیر ردپا بگذارد. این روش از این به بعد روش BACO11 نامیده میشود.
-4 آزمایشها و نتایج
براي حل مـساله انتخـاب ویژگـی بـا اسـتفاده از روش مورچـه باینري، دو رشته از صفرها و یکها مانند شکل1 در نظـر گرفتـه
