وبلاگ

شکل ۵-۵: ساختار کشورها در الگوریتم NLICA مقدار ویژگی میانگین غیرمحلی
همان­طور که اشاره شد، مقادیر هر کدام از خانه­های کشور عددی در بازه ۰ و ۱ بوده و اگر در زمان اجرای الگوریتم مقدار ویژگی غیرمحلی خانه­ای از یک کشور، کمتر از صفر گردد، مقدار خانه متناظر را صفر و اگر مقدار ویژگی مربوط به خانه­ای بیشتر از یک شود، مقدارش را برابر یک قرار می­دهیم.
۵-۳-۲ عملگر جذب
در طی اجرای الگوریتم رقابت استعماری، مستعمرات به سمت استعمارگرهای خود، با اندازه و زاویه تصادفی حرکت می­ کنند و راه ­حل کاندید جدید (موقعیت جدید مستعمره)، با حرکت راه ­حل قدیمی (موقعیت قبلی مستعمره) به سمت یکی از استعمارگرهای انتخاب ­شده با یک شعاع یکنواخت، تولید می شود. عملگر جذب در الگوریتم NLICA مشابه الگوریتم رقابت استعماری استاندارد بوده و بدین شرح پیاده­سازی می­گردد؛ اختلاف تمامی خانه­های مستعمره از خانه­های متناظرشان در کشور استعمارگر محاسبه شده و هر کدام از این اختلافات به دست ­آمده، در اعداد تصادفی جداگانه­ ای که دارای توزیع یکنواخت^[۳۹] و مقادیر در بازه ۰ و ۱ هستند، ضرب شده و سپس هر کدام از خانه­های بردار نتیجه در عدد β که معمولاً عددی بزرگتر از یک است و در این پژوهش مقدار آن ۲ در نظرگرفته شده، ضرب و بردار حاصل به بردار کشور مستعمره مورد نظر اضافه می­گردد (مقادیر خانه­های متناظر با هم جمع می­شوند) و در آخر مقادیر هر یک از خانه­های مستعمره بررسی و در صورت کمتر از صفر بودن، مقدار آن صفر و در حالتی که بیشتر از یک باشد، برابر یک قرار
می­گیرد و به­ این­ ترتیب مکان جدید مستعمره به دست می ­آید. در شکل ۵-۶ نمونه ­ای از حرکت مستعمره به سمت استعمارگر در الگوریتم NLICA به نمایش درآمده است.
۰٫۸۷ ۱ ۰٫۴۳ ۰٫۳ ۰٫۲
۰٫۸ ۰٫۹۵ ۰٫۷ ۰٫۸ ۱
محاسبه اختلاف بین کشور مستعمره و استعمارگر
کشور استعمارگر کشور مستعمره
۰٫۱۴ ۰٫۸۳ ۰٫۳۴ ۰٫۰۵ ۰٫۱
۰٫۰۷- ۰٫۰۵- ۰٫۲۷ ۰٫۵ ۰٫۸
برداری از اعداد تصادفی به طول تعداد خوشه ­ها بردار اختلاف مستعمره و استعمارگر
ضرب اعضای بردار قبلی در عدد۲
حاصلضرب نظیربه­نظیر خانه­های بردار اعداد تصادفی و بردار اختلاف مستعمره و استعمارگر
اضافه­کردن بردار تولیدشده به مستعمره
۰٫۰۲- ۰٫۰۸۳- ۰٫۱۸۴ ۰٫۰۵ ۰٫۱۶
۰٫۰۱- ۰٫۰۴۱۵- ۰٫۰۹۲ ۰٫۰۲۵ ۰٫۰۸
۰٫۸۵ ۰٫۹۱۷ ۰٫۶۱۴ ۰٫۳۵ ۰٫۳۶
اصلاح بردار مکان جدید مستعمره
۰٫۸۵ ۰٫۹۱۷ ۰٫۶۱۴ ۰٫۳۵ ۰٫۳۶
شکل ۵-۶: نمونه ­ای از حرکت مستعمره به سمت استعمارگر در الگوریتم NLICA
۵-۳-۳ عملگر انقلاب^[۴۰]
عملگر انقلاب به مفهوم تغییر ناگهانی در موقعیت یک مستعمره بوده و انقلاب از دیدگاه الگوریتمی باعث
می­ شود کلیت حرکت تکاملی از گیر­کردن در دره­های محلی بهینگی نجات یابد که در بعضی موارد باعث بهبود موقعیت یک کشور شده و آن را به یک محدوده بهینگی بهتری می­برد. در الگوریتم NLICA عملگر انقلاب به این صورت اجرا می­ شود که یکی از خانه­های مستعمره به تصادف انتخاب و عددی تصادفی با توزیع یکنواخت، در بازه ۰ و ۱ تولید شده و به جای محتوای قبلی، در آن خانه قرار می­گیرد. این عملگر برای همه مستعمره­ها با احتمال یکسانی اجرا می­ شود؛ یعنی برای هر مستعمره عددی تصادفی تولید شده و اگر این عدد کمتر مساوی یک حدآستانه^[۴۱] مشخصی باشد، آن مستعمره دچار انقلاب می­ شود. مقدار حدآستانه در الگوریتم پیشنهادی ۰٫۰۱ گرفته شده است. شکل زیر مثالی از عملگر انقلاب در الگوریتم NLICA را نشان می­دهد.

۰٫۳ ۰٫۵ ۰٫۶۲ ۰٫۲۱ ۰٫۹
۰٫۳ ۰٫۷۴ ۰٫۶۲ ۰٫۲۱ ۰٫۹
شکل ۵-۷: مثالی از عملگر انقلاب
۵-۳-۴ عملگر جدید حرکت استعمارگرها
در الگوریتم رقابت استعماری، کشورهای استعمارگر هیچ حرکتی انجام نداده و فقط مستعمراتشان به سمت آنها در حال حرکت هستند. به همین دلیل ممکن است الگوریتم در بهینه­های محلی تابع هدف قرار گیرد. برای افزایش قدرت الگوریتم، در الگوریتم NLICA، عملگر حرکت استعمارگرها به سمت قوی­ترین استعمارگر پیشنهاد شده است تا از طریق ایجاد پویایی در بین استعمارگرها، فضای اطراف آنها به خوبی مورد کاوش و بررسی قرار گیرد. استعمارگری که دارای کمترین هزینه باشد (در مسائل کمینه­سازی^[۴۲])، به عنوان قوی­ترین استعمارگر انتخاب شده و سایر استعمارگرها به سمت آن حرکت می­ کنند. حرکت استعمارگرها به سمت قوی­ترین استعمارگر، مشابه حرکت مستعمره­ها به سمت استعمارگر بوده و به این صورت است که اختلاف دو کشور استعمارگر محاسبه و هر یک از خانه­های بردار حاصل در برداری از اعداد تصادفی یکنواخت در بازه ۰ و ۱ ضرب عنصر به عنصر شده و بردار حاصل پس از ضرب همه اعضایش در یک عدد (مانند ۰٫۹۵)، به بردار کشور استعمارگر در حال حرکت افزوده می­گردد و به این ترتیب مکان جدید استعمارگر مشخص می­ شود. در شکل ۵-۸ نمونه ­ای از حرکت استعمارگر به سمت قوی­ترین استعمارگر نشان داده شده است.
شکل ۵-۸: حرکت استعمارگر به سمت قوی­ترین استعمارگر
۵-۳-۵ عملگر جدید جستجوی فضای اطراف قوی­ترین استعمارگر
به منظور کاوش محیط پیرامون قوی­ترین استعمارگر، جواب­های کاندیدی^[۴۳] در داخل شعاع معینی اطراف این استعمارگر تولید می­ شود و سپس اگر یکی از این جواب­ها دارای هزینه کمتری نسبت به هزینه قوی­ترین استعمارگر بود، مکان قوی­ترین استعمارگر به مکان بهترین جواب پیدا شده پیرامون قوی­ترین استعمارگر، در فضای متغیرهای مسئله انتقال می­یابد. اگر r شعاع تولید جواب باشد، برای تولید جواب­های کاندید برداری از اعداد تصادفی یکنواخت در بازه [-r,r]، به طول کشورها (تعداد خوشه ­ها) تولید و به کشور قوی­ترین استعمارگر اضافه می­گردد. سپس تابع هزینه کشور تولید شده جدید برای مقایسه با هزینه قوی­ترین استعمارگر مقایسه می­ شود. در این پژوهش به تعداد پنج جواب کاندید تولید و یکی از آنها در صورت بهتر بودن از قوی­ترین استعمارگر، جایگزین آن می­گردد. ضمناً شعاع تولید جواب، متغیر بوده و در ابتدای اجرای الگوریتم مقدار نسبتاً بزرگی (۰٫۵) داشته و تدریجاٌ در تکرارهای بعدی الگوریتم از مقدار آن کاسته
می­ شود. شکل ۵-۹ نمونه ­ای از عملکرد عملگر تولید جواب­های کاندید، پیرامون بهترین استعمارگر را نمایش می­دهد.
شکل ۵-۹: تولید جواب­های کاندید در اطراف بهترین استعمارگر
۵-۳-۶ تابع هزینه^[۴۴] الگوریتم NLICA
در الگوریتم­های تکاملی میزان مناسب ­بودن یک جواب با محاسبه تابع هزینه آن مشخص می­گردد. در انتخاب تابع هزینه الگوریتم NLICA از تابع هدف الگوریتم K-means الهام گرفته شده است. تابع هدف الگوریتم K-means برابر با مجموع فواصل داده ­ها از مراکز خوشه مربوطه­شان بوده و این الگوریتم در جهت
کمینه­سازی تابع هدف، مراکز خوشه ­ها را به صورت تکراری به ­روزرسانی می­ کند.
یکی از ویژگی­های خوشه­بندی مطلوب این است که خوشه ­ها و در نتیجه مراکزشان تا حد امکان از هم دور بوده و اصطلاحاً فاصله بین­ کلاسی بیشترین مقدار را داشته باشد. بنابراین به منظور افزایش کیفیت
خوشه­بندی، فاصله بین خوشه ­ها نیز به تابع هدف الگوریتم NLICA افزوده شده و این الگوریتم سعی در بیشینه­سازی فاصله بین ­مراکز خوشه ­ها دارد. اگر فاصله بین نزدیکترین دو خوشه بیشینه شود، فاصله سایر خوشه ­ها نیز از هم بیشترین مقدار را خواهد داشت و بنابراین در تابع هدف پیشنهادی، فاصله بین دو نزدیکترین مرکز خوشه­ گنجانده شده است. تابع هزینه الگوریتم NLICA به صورت زیر انتخاب شده که این الگوریتم با جستجوی مراکز بهینه خوشه ­ها در فضای ویژگی میانگین وزن­دار غیرمحلی پیکسل­ها، تابع هزینه را کمینه می­ کند.

در رابطه فوق K تعداد کل خوشه ­ها (در اینجا تعداد ناحیه­های تصویر)، N تعداد کل داده ­ها (تعداد