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

تاریخ دریافت مقاله: 24/11/1394
تاریخ پذیرش نهایی مقاله: 05/11/1395 نویسنده مسئول مقاله: محمد قانعی استاد
E-mail: m.ghanei1992@gmail.com
مقدمه
امروزه در بیشتر سازمانها، دادهها به سرعت جمعآوری و ذخیره می شوند، امامیتـوان ادعـا کـرد علیرغم این حجم انبوه داده، سازمانها با فقر دانش در تصـمیم گیـری روبـه رو هسـتن د ( هـان و کمبر، 2006). همچنین با توجه به ذخیره دهها، صـدها یـا حتـی هـزاران ویژگـی در پایگـاه دادهبرنامههای کاربردی، بحث کاهش ویژگی در جهت تحلیل این دادهها، امر ضروری و انکارناپـذیراست (گایون و الیزف، 2003؛ یو، 2005). در بررسـی پایگـاههـای داده، گـاهی بـا سیسـتمهـایاطلاعاتی ناقص1 مواجه ایم. سیستم اطلاعاتی ناقص به جدول هایی از دادهها اطلاق میشود کـهبرخی درایههای صفات آن بی مقدارند (اورلاسکا و پاولاک، 1984). یکی از رویکردهـا ی تحلیـلاین سیستمها، این است که سطر مربوط به مقادیر ناقص را حذف کنـیم (کمیلسـکی، گ ریزمـالا،پترسن و تان، 1993)؛ اما این رویکرد مناسب نیست، زیرا اندازه دادهها را کاهش می دهد و امکان حذف اطلاعات مفید وجود دارد. روش دیگر برای تحلیل این نوع سیسـتم هـای اطلاعـاتی ایـناست که دادههای ناموجود را به صورتهای مختلف مقداردهی کنیم. برای مثـال از تحلیـلهـایآماری استفاده کرده و داده های ناموجود را حدس بزنیم (گونلان، 1986؛ کمیلسـکی و همکـاران ، 1993). هر دو رویکرد برای کامل شدن سیستمهای اطلاعاتی کاربرد دارند، اما به کـارگیری روشمناسب برای کامل کردن سیستمهای اطلاعاتی ناقص، خود یک موضوع تحقیـق پیچیـده اسـت(منگ و ژی، 2009).
در سالهای اخیر تئوری مجموعه راف2 به یکی از راهحلهای قدرتمند در حل مسائل هـوشمصنوعی همچون دادهکاوی تبدیل شده است (پاولاک و اسکورن، 2007). یکـی از راهکارهـایاساسی برای استخراج دانش و کشف الگوهای پنهان از سیستمهای اطلاعاتی3 بزرگ، استفاده از دادهکاوی4 است (هان و کمبر، 2006). کاهش ویژگی5 که همان انتخاب ویژگی6 نامیده میشود، یکی از موضوعات مهم در تئوری مجموعه راف است، اما نسخه کلاسیک تئوری مجموعـه رافبرای بحث کاهش ویژگی در سیستمهای اطلاعاتی ناقص چندان مناسب نیست (کیـان، لیانـگ،پدریک و دانگ، 2011). برای کاهش ویژگی، دو استراتژی کلی به نام بستهبنـدی 7 (کوهـاوی وجان، 1997) و فیلتر8 مطرح شده است. در گذشته، یک الگوریتم یادگیری برای ارزیابی مجموعـه
ــــــــــــــــــــــــــــــــــــــــــــــــــــــــــــــــــــــــــــــــــــــــــــــــــــــــــــــــــــ
Incomplete Information System
Rough Set Theory
Information System
45. Data Mining . Attribute Reduction
Feature Selection
Wrapper
Filter
ویژگیهای انتخاب شده به کار میرفت، اما به مرور زمان مجموعه ویژگیها به وسیله معیارهای بـا معنی ای همچون افزایش اطلاعات1 (لی و لی، 2006؛ کـونلان، 1986)، سـازگاری (داش و لیـو،2003؛ کوین، لیانگ و دانگ، 2008)، مسافت (کـایرا و رنـدل، 1992)، وابسـتگی (مورزجسـکی،
1992) و غیره بررسی میشوند. این معیارها به دو دسـته کلـی مبتنـی بـر مسـافت و مبتنـی بـرسازگاری، طبقه بندی شدهاند (هو، ژیو و یو، 2007).
اغلب روشهای بهینهسازی مبتنی بر هوش مصنوعی همانند الگوریتم ژنتیـک، شـبیهسـازیفرایندهای طبیعی هستند. یکی از دلایل این امر ملمـوس بـودن، سـادگی فرمولـهکـردن و درکتکامل این الگوریتمهاست. الگوریتم رقابت استعماری2، با الهامگیری از نوعی فراینـد اجتمـاعی ـ سیاسی نسبت به سایر روشهای مطرح شده در این زمینه توانایی زیادی دارد و از سرعت مناسبی نیز برخوردار است (آتش پز و لوکاس، 2007؛ صفوی، پورجعفریان و صفوی، 1393: 104).
راهحل نوین ارائهشده در این مقاله، ترکیبی از الگوریتم رقابت استعماری و منطق فازی اسـتکه در حل مسئله کاهش ویژگی سیستمهای اطلاعاتی ناقص مبتنـی بـر تئـوری مجموعـه رافکاربرد دارد. استفاده از منطق فازی در کنترل پارامترهای الگوریتم رقابت استعماری بسـیار مفیـداست و در مقایسه با نسخه بدون فازی الگوریتم، جوابهای بهینهای مـی دهـد . منطـق فـازی ازاجزای محاسبات نرم3 است که روش محاسباتی جدیدی محسوب میشود و تواناییهای شاخص ذهن انسان را برای استدلال و یادگیری در محیط نامعین و نادقیق گرد هم مـی آورد (لطفـی زاده، 1992). الگوریتم رقابت استعماری فازی هوشمندانه عمل می کند و روی سیستمهـای اطلاعـاتیناقص نتایج مناسبی ارائه می دهد.
بخشهای مختلـف ایـن مقالـه بـدین شـرح اسـت؛ ابتـدا پیشـینه پـژوهش بررسـی شـده و پژوهش های موفق در زمینه کاهش ویژگی مبتنی بر تئوری مجموعه راف مرور میشوند. بخـشروششناسی پژوهش، به توضیح روند اجرای پروژه اختصاص دارد. در قسمت یافتههای پژوهش، نتایج به دست آمده از اجرای روش، ب هصورت مقایسهای مطرح می شود و در نهایت نتیجهگیـری وپیشنهادها ارائه خواهد شد.
پیشینه پژوهش
در دو دهه گذشته، تعداد زیادی از روشهای کاهش ویژگی مبتنی بر تئوری مجموعـه راف ارائـهشده است (لی، ژانگ و لیونگ، 2004؛ می، وا و ژانـگ، 2003؛ وا، ژانـگ، و لـی، 2005؛ شـاو و
ــــــــــــــــــــــــــــــــــــــــــــــــــــــــــــــــــــــــــــــــــــــــــــــــــــــــــــــــــــ
Information gain
Imperialist Competitive Algorithm (ICA)
Soft Computing
ژانگ، 2005؛ کیان، لیانگ و دانگ، 2008). یکی از مشکلات اساسی این روشها، زمان زیـادیاست که صرف پردازش مجموعه دادههای بـزرگ مـیشـود . در ادامـه تعـدادی از تحقیـقهـایانجام شده در این حوزه پژوهشی بررسی می شود.
پیشینه نظری
در بررسی پیشینه نظری کاهش ویژگی بر مبنای تئوری مجموعه راف، دو رویکـرد اساسـی را درمقابل داریم. ابتدا رویکردهایی که کلاسیک هستند و از همان نسخه اصلی تئوری مجموعه راف استفاده میکنند. رویکرد دوم، توسعه یافته رویکرد قبلی است که الگوریتم های اکتشـافی کـاهشویژگی را ارائه میکند. نکته مهم در رویکردهای مختلف کاهش ویژگی بر مبنای تئوری مجموعه راف، نوع سیستمهای اطلاعاتی است. در اغلب پژوهش های اجراشده بر سیستمهـای اطلاعـاتیکامل تمرکز شده است؛ اما در دنیای واقعی، مجموعه دادههـای جمـعآوری شـده همیشـه کامـلنیستند. پس چالش اساسی کاهش ویژگی مبتنی بر تئوری مجموعه راف، کار روی سیسـتم هـایاطلاعاتی ناقص است.
پیشینه تجربی
در بررسی پیشینه تجربی، تعدادی از پروژههای موفق در زمینه کاهش ویژگی مبتنـی بـر تئـوریمجموعه راف مرور میشوند. این پژوهشها در همان قالب توضیح داده شده در بخش قبـل ار ائـهشدهاند.
یکی از تحقیقات ابتدایی انجام شده، روی چند روش مبتنی بر تئـوری مجموعـه راف تمرکـزدارد که برای استخراج قوانین از جدول های تصمیم به کار میروند. معمولاً این روشها با استفاده از ماتریسهای عینی عمل مـی کننـد (اسـکورن، 1995). در ایـن پـژوهش، کـارایی روشهـایمطرح شده و دقت استخراج قوانین پایین بود.
برای افزایش کارایی عملکـرد کـاهش ویژگـی در تئـوری مجموعـه راف، چنـدین الگـوریتماکتشافی توسعه داده شده است (ها و همکاران، 2007؛ ها، یو و ژیو، 2006؛ ها و سرکون، 1995؛ لیانگ، چین، دانگ و ریچد، 2002؛ کیان و لیانگ، 2008؛ اسـلزاک، 2002؛ وانـگ، ژو و یانـگ،2002؛ وانگ، ژائو و آن، 2005؛ وا، لی، هانگ و لیو، 2004). هر یک از این الگوریتمها در حفـظویژگیهای خاص سیستم اطلاعاتی داده شده کمک میکنند.
برای کاهش ویژگی در سیستمهای اطلاعاتی ناقص، مشابه تحقیقات ابتدایی، یک مـاتریسعینی به صورت کلی مطرح شده که بحث کاهش ویژگی را روی جدول های تصمیم ناقص انجـاممیدهد (کریزکیوسز، 1998). برای افزایش کارایی در بحث کاهش ویژگی روی دادههای ناقص، چندین الگوریتم اکتشافی ارائه شده که در ادامه تعدادی از آنها بررسی میشود.
ایده کاهش نواحی مثبت بدین صورت مطرح شد که یک الگوریتم کاهش ویژگی اکتشـافی، روی جدول های تصمیم ناقص اعمال میشود. روش آن به این شکل است که ناحیه مثبت هدف تصمیم را بدون تغییر نگه مـی دارد (یانـگ و شـو، 2006). همچنـین تعریـف جدیـد از درگاشـتاطلاعات1، برای اندازهگیری اجمالی از سیستمهای اطلاعاتی ناقص عنوان شد (لیانگ، شی، لی و وایرمن، 2006). علاوه بر این، اعمال متنـاظر درگاشـت شـرطی2 در کـاهش ویژگـیهـای دارایافزونه، شامل این تعریف بود (لیانـگ و ژو، 2002). دو دانشـمند دیگـر ترکیـب درگاشـت بـرایاندازه گیری اجمالی از یک سیستم اطلاعاتی ناقص و همچنین استفاده از درگاشت شـرطی بـرایدستیابی به زیرمجموعهای از ویژگیها را پیشنهاد دادند (کیـان، لیانـگ و وانـگ، 2009). بعـد ازدرگاشت اطلاعات که برای کاهش ویژگی در تئوری مجموعه راف به صـورت کلاسـیک مطـرحشد، نمونه توسعه یافته ای از آن برای تکمیل روش قبلی ارائه گردید (اسلزاک، 2002).
در یکی از پژوهشهای انجام شده به بحث بهینهسازی و اثربخشی3 الگوریتمهـای اکتشـافیکاهش ویژگی در سیستمهای اطلاعاتی ناقص پرداخته شده است. چارچوب جدیدی کـه در ایـنپژوهش برای تئوری مجموعه راف ارائه شد، »تقریب مثبت«4 در سیستمهای اطلاعـاتی نـاقصنامیده میشود. یکی از نتایج این چارچوب، این است که میتواند ساختار ناقص تئوری مجموعـهراف را شناسایی کند (کیان، لیانگ، پدریک و دانگ، 2011).
اما یکی از چالشهای اساسی پژوهشهای انجام شده در این حوزه، صرف زمـان زیـاد بـرایپردازش دادههای ناقص با حجم بالاست. نکته دیگری که در تحقیقات پیشین همواره بـه عنـوانیک چالش مطرح است، کارایی کم روشهای ارائه شده است.
روششناسی پژوهش
در این بخش، پس از تعریف مفاهیم اساسی همچـون سیسـتمهـای اطلاعـاتی نـاقص، تئـوریمجموعه راف، الگوریتم رقابت استعماری و قواعد فـازی ، مجموعـه داده ایـن پـژوهش، تشـریحمی شود.
ــــــــــــــــــــــــــــــــــــــــــــــــــــــــــــــــــــــــــــــــــــــــــــــــــــــــــــــــــــ
Information Entropy
Conditional Entropy
Efficiency
Positive Approximation
سیستمهای اطلاعاتی ناقص
یک سیستم اطلاعاتی معمولاً به فرم زیر ارائه میشود.
رابطه 1) ⋴(,{} ,,) =
که در آن، U تعداد متناهی از اشیای دارای مقدار و A تعداد محدودی از ویژگیهای دارای مقدار است. مجموعه مقادیر ویژگیها و ، یک تابع اطلاعاتی از سیستم اطلاعات است کـه را به U نگاشت میکند. اگر در سیستم اطلاعاتی یک شیء x و یک ویژگی به نام a وجـود داشـتهباشد که در تابع (x) مقداری نداشته باشد، به آن سیستم اطلاعـاتی نـاقص گفتـه مـی شـود.
معمولاً مقادیر ناموجود را با * و به فرم ذیل نمایش می دهند:
= (U, A,

(2 رابطه
مثال: جدول شماره 1 نمونهای از سیستم اطلاعاتی ناقص را نشـان مـیدهـد . ایـن سیسـتمشامل اطلاعات مربوط به چند فرد با ویژگیهای قد، وزن و سن است. هر یک از مقادیر مربـوطبه این ویژگیها با مقادیر کیفی مشخص شده اند.
جدول 1. نمونهای از سیستم اطلاعاتی ناقص
سن وزن قد افراد
خیلی بالا زیاد بلند شماره 1
بالا زیاد کوتاه شماره 2
پایین کم * شماره 3
خیلی بالا زیاد بلند شماره 4
خیلی بالا * خیلی بلند شماره 5
* متوسط بلند شماره 6

تئوری مجموعه راف
تئوری مجموعه راف در سال 1980 ارائه شد. این ابزار ریاضی برای بیان و بررسی مسائلی اسـتکه در آنها عدم قطعیت و ابهام وجود دارد و معمـولاً بـرای پیـدا کـردن نـاهمگونی در مجموعـهداده ها به کار میرود. همان طور که در جدول 1 مشخص است، فرد 1 و 4 مقادیر ویژگی مشابهی دارند و با این مقادیر از هم تفکیک نمی شوند (پاولاک، 1998؛ کیانا، ژانگـب، سـانگب و لیانـگ،2014).
رابطه زیر را رابطه تفکیکناپذیر میگویند:
رابطه 3) {( )= ( ),∈∀|×∈ (, )}=
اگر x و y دو شیء باشند و برای هر ویژگی در مجموعـ ه B، مقـدار آن ویژگـی در دو شـیء یکسان باشـد ، Iرا رابطـ ه تفکیـک ناپـذیر B مـی نامنـد . همچنـین برچسـب کـلاس، ویژگـیتصمیم گیری تعریف می شود و هر به سیستم اطلاعاتی کـه حـاوی ایـن ویژگـی باشـد، سیسـتمتصمیم گیری میگویند.
جدول 2. نمونهای از سیستم اطلاعاتی کامل
درآمد سن وزن قد افراد
کم خیلی بالا زیاد بلند شماره 1
متوسط بالا متوسط کوتاه شماره 2
زیاد خیلی بالا زیاد بلند شماره 3
زیاد خیلی بالا خیلی کم خیلی بلند شماره 4
کم پایین زیاد بلند شماره 5
خیلی کم بالا کم متوسط شماره 6

در جدول 2 ستون درآمد، ویژگی تصمیمگیری است. در این جدول افراد 1 و 3 ویژگـی هـاییکسانی دارند، اما از نظر درآمد وضعیت مشابهی ندارند. به بیان دیگر، ویژگی تصمیمگیـری آنهـا متفاوت است. مجموعه توانی ویژگی ها عبارت اند از{(قد)، (وزن)، (سن)، (قد و وزن)، (قد و سن)، (وزن و سـن)، (قـد، وزن، سـن)}. حـال اگـر مجموعـه (قـد و وزن) را در نظـر بگیـریم، رابطـه تفکیک ناپذیری آن به صورت رابطه 4 است.
رابطه 4) {{6} ,{4} ,{2} ,{5 ,3 ,1}}={وزنوقد}|
با توجه به رابطه 4، مجموعه {1، 3، 5} در رابطه 4، توسط قد و وزن تفکیک ناپذیرنـد و بـهیک کلاس هم ارزی تعلق دارند. در یک رابطه همارزی به نام x، کلاس همارزی مربوط به عضو a شامل اعضایی است که باa ارتباط دارند. نمایش کلاس هم ارزی به صورت [ ] است.
فرض کنید یک سیستم اطلاعاتی S= (U, A) داشته باشیم که در آن U مجموعه اشیا و A ویژگیهاست. همچنین X⊆U و B⊆A را داریم و دو مجموعه به شرح زیر تعریف میشوند:

در این سایت فقط تکه هایی از این مطلب با شماره بندی انتهای صفحه درج می شود که ممکن است هنگام انتقال از فایل ورد به داخل سایت کلمات به هم بریزد یا شکل ها درج نشود

شما می توانید تکه های دیگری از این مطلب را با جستجو در همین سایت بخوانید

ولی برای دانلود فایل اصلی با فرمت ورد حاوی تمامی قسمت ها با منابع کامل

اینجا کلیک کنید

رابطه 5) { []| }=

= {x|[ ] X} (6 رابطه
با توجه به تعریف B، مجموعههای X

و X احتمالاً دارای اشیایی متعلق بـهX هسـتند .
محدوده مرزی روی X به صورت زیر تعریف میشود و حاوی اشیایی است که قطعاً در X نیستند.
(X) =

X- X (7 رابطه
یک مجموعه در صورتی راف است که با توجه به B، مجموعه مرزی آن تهی نباشـد . بـرایمثال، X برابر است با افرادی که درآمد زیادی دارنـد ، یعنـی {4 , 3} = X و مجموعـهB برابـر{قد، وزن و سن} فرض شود، آنگاه داریم:

X ={4}, X ={1, 3, 4}, BN (X) = {1, 3}, U-BN (X) = {2, 5, }6
همان طور که مشخص است، مجموعه مـرزی تهـی نیسـت. افـراد 1 و 3 دارای درآمـد بـالاهستند، افراد 4، 3 و 1 احتمالاً درآمد بالایی دارند. افراد 3 و 1 را نمی توان بـاB تعیـین تکلیـف کرد. همچنین افراد 2، 5 و 6 قطعاٌ درآمد بالایی ندارند. میزان دقت مجموعه راف را مـی تـوان از رابطه 8 تعیین کرد.
X
534162-95734

رابطه 8) = (X)
X
درجه تعلق x به X را می توان با تابع تعلق راف بیان کرد. این تابع تعلق، درجه هـم پوشـانیمجموعه X و کلاس همارزی [] را تعیین میکند. در مثال بالا کلاسهای همارزی به شـرحزیر هستند:
{6}= [6] ,{5}= [5] ,{4}= [4] ,{2}= [2] ,{3 ,1}= [3]= [1]رابطه زیر تابع تعلق را مشخص میکند:
|[ ]∩|
: U → [0, 1]and(x) =

|[ ] | (9 رابطه
در بررسی دادهها، یافتن رابطه بین ویژگیهای شرطی و تصمیم اهمیـت دارد . بـا اسـتفاده ازهمین وابستگی بین ویژگیها میتوان آنهایی که اهمیت ندارند را حذف کرد. اگـرTd مجموعـه ویژگیهای تصمیمگیری و Tc مجموعه ویژگیهای شرطی باشد، وابسـتگی بـین آنهـا بـه ایـنشکل بیان میشود Tc≤Td؛ به این معنا که تمام مقادیر تصمیمگیری از مقادیر شرطی ب هدسـتمیآیند و البته حالت جزئی هم میتواند داشته باشد.
تعریف رسمی برای این خاصیت بدین صورت است کـه اگـرC و D زیـر مجموعـههـایA باشند، به طوری که اشتراک C و D تهی و اجتماع آنها A باشد، میگوییم D وابسته به C اسـت .
و به شکل C⇒D نمایش داده میشود، اگر رابطه 10 برقرار باشد.
X
رابطه 10) ||

اگر k برابر 1 باشد، یعنی D کاملاً به C وابسته است. در مثال قبلـی ویژگـی تصـمیمگیـری درآمد با درجه

به مجموعه ویژگیهای {قد، وزن و سن} وابسته است.
با توجه به تشریح تئوری مجموعه راف، کاربردهای مختلف آن قابـل درک خواهـد بـود کـهبحث کاهش ویژگی یکی از کاربردهای مهم آن است.
الگوریتم رقابت استعماری
الگوریتم رقابت استعماری در سال 2007، به عنوان روش جست وجوی فرامکاشفهای مطـرح شـدکه از پدیده اجتماعی ـ انسانی الهام میگیرد (آتشپز و لوکاس، 2007). این الگـوریتم بـا تعـدادیجمعیت اولیه آغاز میشود که هر عنصر جمعیـت یـک کشـور نـام دارد و کشـورها بـه دو گـروهاستعمارگر و مستعمره دسته بندی مـی شـوند . هـر اسـتعمارگر بسـته بـه قـدرت خـود تعـدادی ازکشورهای مستعمره را به سلطه درمـی آورد و آنهـا را کنتـرل مـیکنـد . سیاسـت جـذب، رقابـتاستعماری و انقلاب، هسته اصلی این الگوریتم را تشکیل میدهند (صنیعی آباده و جبـل، 1392).
رویه اجرای این الگوریتم به صورت زیر است (حاجی حسنی، ارمغانی و مارتو، 2015):
شکلدهی امپراتوریهای اولیه: تعـدادی از بهتـرین عناصـر جمعیـت بـه عنـوا ن اسـتعمارگرانتخاب می شوند و باقی مانده جمعیت نیز مستعمره در نظر گرفتـه مـی شـوند . اسـتعمارگرانبسته به قدرتشان، این مستعمرات را با روند خاصی به سمت خود می کشند. در بهینه سـازی،هدف، یافتن یک جواب بهینه بر حسب متغیرهای مسـئله اسـت . مـا آرایـه ای از متغیرهـا ی مسئله را که باید بهینه شوند، ایجـاد مـی کنـیم و آن را یـک کشـور مـی نـامیم . در مسـئل ه بهینه سازی Nvarبعدی، یک کشور، آرایهای به طـول 1 * Nvarاسـت . ایـن آرایـه بـه ایـنصورت تعریف مـی شـود : [p1, p2, …, pNvar] = کشـور . مقـادیر متغیرهـا در یـک کشـور،به صورت اعداد اعشـاری نمـایش داده مـی شـوند. از دیـدگاه تـاریخی و فرهنگـی، اجـزایتشکیل دهنده یک کشور را میتوان ویژگی هـای اجتمـاعی ـ سیاسـی آن کشـور، همچـونفرهنگ، زبان، ساختار اقتصادی و سایر ویژگی ها در نظر گرفت.
ناوریدورهبهار
سیاست جذب (همگون سازی): این سیاست با هـدف تحلیـل فرهنـگ و سـاختار اجتمـاعیمستعمرات در فرهنگ حکومت مرکزی اجرا می شد. کشورهای استعمارگر برای افزایش نفوذ خود، شروع به ایجاد زیرساخت های حمل و نقل، تأسیس دانشگاه و غیره می کردند. در واقع، حکومت مرکزی با اعمال سیاست جذب تلاش می کرد کشور مستعمره را در راسـتای ابعـادمختلف اجتماعی ـ سیاسی به خود نزدیک کند.
انقلاب: روند انقلاب تغییرات ناگهانی را در ویژگیهای اجتماعی ـ سیاسی یک کشور ایجـادمیکند. در الگوریتم رقابت استعماری، انقلاب با جابه جایی تصادفی یک کشور مستعمره بـهموقعیت تصادفی جدید، مدلسازی میشود.
جابه جایی موقعیت مستعمره و اسـتعمارگر: در حـین حرکـت مسـتعمرات بـه سـمت کشـوراستعمارگر، ممکن است بعضی از این مستعمرات به موقعیتی بهتـر از اسـتعمارگر برسـند . در این حالت، کشور استعمارگر و کشور مستعمره، جای خود را با یکدیگر عوض میکنند.
رقابت استعماری: قدرت امپراتوری، به صورت قدرت کشور استعمارگر به اضـاف ه درصـدی ازقدرت کل مستعمرات آن تعریف میشود. هر امپراتوری که نتواند بـر قـدرت خـود بیفزایـد وقدرت رقابت خود را از دست بدهد، در جریان رقابت های استعماری، به تدریج سقوط می کنـد و مستعمراتش به دست امپراتوری های قوی تر میافتد.
در شکل 1 نمودار الگوریتم رقابت استعماری مشاهده میشود.

شکل 1. فلوچارت الگوریتم رقابت استعماری
در ادامه به معرفی پارامترهای الگوریتم رقابت استعماری پرداخته می شود.
جدول 3. معرفی پارامترهای الگوریتم رقابت استعماری
نام متغیرها توضیح
Nvar تعداد متغیرها
Npop تعداد اعضای جمعیت
Nimp تعداد استعمارگران
Maxdecades تعداد تکرار
Beta ضریب جابه جایی
Prevolve ضریب انقلاب (شبیه جهش در ژنتیک)
Zeta ضریب میانگین قدرت کلونیهای یک استعمارگر

در هر بار تکرار الگوریتم، مقادیر اولیه مختلفی را برای پارامترهای آن انتخاب کـردیم کـه درنهایت، بهترین مقادیر آنها به صورت تجربی به این ترتیب مشخص شد: تعداد تکرار برابر بـا 100 تا 200، تعداد اعضای جمعیت 50 تا 100، تعداد استعمارگران بسته به تعداد اعضای جمعیت بـین5 تا 10، با توجه به پیشنهاد ارائه دهندگان الگوریتم ضریب جابه جایی مقدار 2/0، ضریب انقـلاب
1/0 و ضریب میانگین قدرت کلونیها بین 05/0 تا 005/0.
قوانین فازی تعریفشده
استفاده از قواعد فازی در اجرای الگوریتم باعث شد بتوانیم پارامترهای کلیـدی الگـوریتم رقابـتاستعماری را بهتر کنترل کنیم. مجموعه قواعد فازی برای این برنامه به صورت زیر تعریف شد:

.1 If (UN is not L) and (I is not L) then (Prevolve is M) (zeta is L) (Beta is H)
.2 If (nimp is M) and (I is M) then (Prevolve is L) (zeta is M) (Beta is M)
.3 If (I is H) then (Prevolve is M) (Beta is L)
.4 If (I is L) then (Prevolve is L) (Beta is H)
.5 If (I is M) then (Prevolve is M) (Beta is M)
.6 If (nimp is not H) and (I is H) then (Prevolve is L) (zeta is M) (Beta is L) .ورودیها و خروجیهای مجموعه قواعد در جدول 4 مشخص شدهاند
ناوریدورهبهارجدول 4. توضیح ورودیها و خروجیهای قوانین فازی تعری فشده
توضیح خروجیها خروجیها توضیح ورودیها ورودیها
ضریب انقلاب (جهش) Prevolve تعداد تکرارها I
ضریب میانگین قدرت کلونیهای یک استعمارگر zeta تعداد اجراهایی که جواب تغییر نمیکند UN
ضریب جابه جایی Beta تعداد استعمارگران Nimp

همچنین در مشخص کردن مقدار ورودیها و خروجیها، L بـه معنـای کـم 1، M بـه معنـای متوسط2 و H به معنای زیاد3 است. در شکل 2، نمودارهای مربـوط بـه قـوانین نشـان داده شـده است.

شکل 2. نمودار ورودیها و خروجیهای قوانین فازی
با توجه به بررسی شکل 2، هنگامی که ورودیهای قواعد فازی را متوسط (M) فرض کنیم،
خروجیهای آن به صورتPrevolve برابر 242/0، zeta برابـر 04776/0 و Beta برابـر 613/0 است.

ــــــــــــــــــــــــــــــــــــــــــــــــــــــــــــــــــــــــــــــــــــــــــــــــــــــــــــــــــــ
Low
Medium
High
ویژگیاطلاعاتیبرتئوری…
مجموعه داده در دست بررسی
همان طور که در قسمت مقدمه مقاله اشاره کردیم، کـار روی داده هـای نـاقص انجـام مـی شـود .
داده های ناقص به جدول هایی از دادهها گفته می شود که برخی درایـه هـای صـفات آن مقـداریندارند. در روند انجام این پروژه، هیچ تغییری روی دادههای ناقص اعمال نکردیم و آن را سیستم اطلاعاتی کامل فرض کردیم. مجموعه داده در دست بررسـی در جـدول 5 معرفـی شـده اسـت .
(کیان، لیانگ، پدریک و دانگ، 2011؛ یو. سی. آی، 2016).
جدول 5. معرفی مجموع داده مورد بررسی
شماره ستون تصمیم تعداد ستونها تعداد سطرها نام مجموعه دادهها ردیف
57 57 32 Lungcancer 1
35 35 366 Dermatology 2
11 11 699 Wisconsin_Breast_Cancer 3
20 20 155 Hepatitis 4
3 30 194 Flag 5

در مجموعه داده معرفی شده، داده شماره 1 مربوط به سرطان ریه، داده شـماره 2 مربـوط بـهمشخصات پوست، داده شماره 3 مربوط به سرطان سینه، داده شماره 4 مربوط به هپاتیـت و دادهشماره 5 مربوط به مشخصات پرچمهاست.
یافتههای پژوهش
شکل 3 چارچوب سادهای از اجرای این پژوهش را نشان میدهد که نقش قواعد فازی در تعیـینپارامترهای الگوریتم و نحوه ارتباط آن با تئوری مجموعه راف را تعیین میکند. همچنین در ایـنچارچوب، ورودی و خروجی مشخص شده است.

شکل 3. چارچوب پژوهش
ناوریدورهبهار
دو نسخه الگوریتم رقابت استعماری و رقابت استعماری فازی طراحیشـده، بـه دفعـات زیـادروی مجموعه دادهها اجرا شد. بهترین جوابهای به دست آمده از اجرای دو نسخه الگوریتم رقابت استعماری با بهترین جوابهای به دست آمده تاکنون در جدول 6 آمده است (کیان، لیانگ، پدریک و دانگ، 2011؛ کی، ژو و گیانگ، 2008). همان طور که در جـدول مشـاهده مـیشـود، بهتـرینجوابهای به دست آمده از هر دو نسخه الگوریتم برای مجمو عـه داده 2 تـا 5، بهتـر یـا برابـر بـابهترین جوابهای به دست آمده تاکنون است. از سویی، نسخه فازی الگوریتم نتایج بهینـه تـری راارائه کرده اسـت . نتیجـه اجـرای نسـخه فـازی الگـوریتم روی مجموعـه داده 1 بهتـر از نسـخهکلاسیک آن است، اما بهینهتر از بهترین جواب به دست آمده تاکنون نبود.

جدول 6. بهترین جوابهای به دست آمده از دو نسخه الگوریتم با بهترین جوابهای به دست آمده تاکنون
بهترین جواب به دست آمده تاکنون الگوریتم رقابت استعماری الگوریتم رقابت استعماری فازی مجموعه دادهها
شماره ستونها بهترین جواب شماره ستونها بهترین جواب 4 ،35 ،28 ،11 ،7 ،3 39 6 ،36 ،28 ،11 ،3 41 5 1
10 ،16 ،9 ،8 ،5 ،4 ،3 ،2 28 ،22 ،18 10 ،16 ،9 ،4 ،3 ،2 28 ،19 ،17 8 2
4 6 ،3 1، 3 6 ،1 2 3
5 16 ،8 2، 3 17 ،6 ،2 3 4
2 11 ،9 4، 3 4 1 5

با مقایسه دو نسخه الگوریتم رقابت استعماری روی مجموعه داده مشخص شده، درمـی یـابیمکه نسخه فازی، راهحلهای بهینهتری را ارائه کرده است. بهترین جـواب هـای بـه دسـت آمـده ازالگوریتم رقابت استعماری فازی برای پنج داده تعیین شده، بهترتیـب {5، 8، 2، 3، 1} و بـدترینپاسخ های به دست آمده شامل {10، 11، 4، 5، 6} است، اما بهترین پاسخهـای بـه دسـت آمـده ازاجرای الگوریتم رقابت استعماری برای مجموعه دادههـا بـهترتیـب {6، 10، 3، 3، 3} و بـدترینجوابها به صورت {9، 14، 4، 5، 5} هستند. در جدول 7 مقایسه ریز نتایج دو نسـخه الگـوریتم درج شده است.
ویژگیاطلاعاتیبرتئوری…
جدول 7. مقایسه بهترین و بدترین جواب های به دست آمده از دو نسخه الگوریتم
Fuzzy-ICA
واریانس بهترین جواب ها میانگین بهترین جواب ها بدترین
جواب بهترین جواب شماره ستونها مجموعه
داده
2/6667 7 10 5 41 ،36 ،28 ،11 ،3 1
0/7667 9/9 11 8 28 ،19 ،17 ،16 ،9 ،4 ،3 ،2 2
0/4889 2/6 4 2 6 ،1 3
4/4889 3/6 5 3 17 ،8 ،2 4
2/8444 2/7 6 1 4 5
ICA
0/9889 6/9 9 6 39 ،35 ،28 ،11 ،7 ،3 1
1/9556 11/2 14 10 28 ،22 ،18 ،16 ،9 ،8 ،5 ،4 ،3 ،2 2
0/2333 3/2 4 3 6 ،3 ،1 3
0/5444 3/9 5 3 16 ،8 ،2 4
0/4444 4 5 3 11 ،9 ،4 5

در بررسی نتایج این مقاله، دو نسخه الگوریتم رقابـت اسـتعماری طراحـی شـده بـا الگـوریتمژنتیک مقایسه شدند. با توجه به بهترین نتایج به دست آمده، مشاهده می شـود کـه نسـخه فـازیالگوریتم رقابت استعماری از الگوریتم ژنتیک جوابهای بهینهتری را ارائه میکند. در شکل هـای4 تا 8 نمودارهای همگرایی این نتایج مشاهده میشود.

شکل 4. نمودار همگرایی برای داده 1شکل 5. نمودار همگرایی برای داده 2
ناوریدورهبهار


پاسخ دهید