ساختارهای ممتیکی موازی

مقاله: ساختارهای ممتیکی موازی

این مقاله در سال 2012 با موضوع "ساختارهای ممتیکی موازی" توسط Fabio Caraffini,  Ferrante Neri, Giovanni Iacca , Aran Mol در مجله دانش های اطلاعاتی چاپ شده است. ساختارهای محاسباتی ممتیک، الگوریتم هایی با ترکیبی از عملگرهای ناهمگن بنام meme برای حل مسائل بهینه سازی می باشند. به منظور حل این گونه مسائل، در این مقاله یک ساختار موثر ساده بنام ساختار ممتیکی موازی (PMS) پیشنهاد می شود. PMS یک الگوریتم حل بهینه سازی ساده است که با عملگرهای درختی ترکیب شده است. یکی از آنها جستجوی تصادفی سراسری است که کل فضا را برای یافتن مناطق امیدوارکننده اکتشاف می کند.

در مقایسه با شبکه های برقی، جریان پایین از مولفه جستجو سراسری یک توازی از دو مولفه  جایگزین وجود دارد. منظور دو الگوریتم با جستجوی محلی با ویژگی های مختلف از لحاظ منطق جستجو می باشد، که هدف آن پالایش جستجو در نواحی ای که توسط عنصر جریان بالا کشف شده است، می باشد. اولین جستجو محلی فضای در امتداد محورها را کشف می کند، در حالی که دومین الگوریتم حرکت موربی با شیب تخمینی را انجام می دهد.

الگوریتم ساختار ممتیکی موازی، علی رغم سادگی آن، کارائی قابل قبولی را در مقایسه با الگوریتم های فراابتکاری محبوب و الگوریتم های بهینه سازی مدرن که وضعیت state-of-the-art در این زمینه می باشند را نشان می دهد. با توجه به ساختار ساده این الگوریتم، الگوریتم خیلی انعطاف پذیر برای ویژگی های مسائل مختلف و مقادیر عددی می باشد. برخلاف الگوریتم مدرن که برای بعضی از مسائل Benchmark و بعضی از مقادیر عددی مشخص شده اند. الگوریتم ساختار ممتیکی موازی راه حل هایی با کیفیت بالا در زمینه های مختلف و متنوع ارائه می دهد. به عنوان مثال برای مسائل با ابعاد کم و مقیاس بزرگ کارائی دارد. یک مثال کاربردی در زمینه سنسورهای مغناطیسی عملکرد مناسب الگوریتم پیشنهادی را نشان می دهد. این مقاله تائید اعتباری را از Ockham’s Razor in MC دارد.

استراتژی یایین به بالا

همان طور که در شکل 1 نشان داده شده است استراتژی پایین به بالا در هر مرحله با مم های مختلف به نتایج مطلوب تر می رسد.

شکل 1 : استراتژی پایین به بالا

اخیراً علاوه بر الگوریتم های ممتیکی، که از ترکیب الگوریتم ژنتیک با جستجوی محلی ایجاد می شود، مفهومی بنام  محاسبات ممتیکی (MC) مطرح می شود که در آن در کنار الگوریتم های تکاملی و جستجوی محلی از عملگر هایی برای کنترل شرایط استفاده می شود. در واقع الگوریتم بهینه سازیی که از MC استفاده می کند مرسوم به دیدگاه MC می باشد. در ادامه این مقاله به معرفی چند عملگر و الگوریتم در این راستا پرداخته شده است.

الگوریتم 3SOME :

ترکیب استراتژی پایین به بالا با Ockham’s Razor منجر به الگوریتم 3SOME شده است. این الگوریتم سه عامل فاصله اکتشاف بلند، متوسط و کوتاه پیشنهاد داده است. در ابتدای بهینه سازی فاصله اکتشاف بلند یک راه حل اولیه را ارائه می دهد. این روال تا رسیدن به راه حل بهتر ادامه می یابد. سپس، راه حل جدید کشف شده توسط فاصله اکتشاف متوسط پردازش می شود. عملگر دوم تا جائی که امکان دارد راه حل را بهبود می بخشد. پس از آن، فاصله اکتشاف کوتاه فعالیتش آغاز می شود. اگر این عملگر موفق به بهبود راه حل آزمایشی شد آنگاه فاصله اکتشاف متوسط برای پیشرفت بیشتر فعال می شود. در مقابل، اگر فاصله اکتشاف کوتاه موفق به بهبود راه حل نشود آنگاه بهینه سازی فاصله اکتشاف بلند آغاز می شود. ساختار ترتیبی ممتیک محاسباتی 3SOME در شکل 2 نشان داده شده است.

شکل 2 : ساختار ترتیبی 3SOME

در شکل 3 ساختار ترتیبی عمومی محاسبات ممتیکی نشان داده شده است. که در آن مقادیر سه عملگر پیشنهادی محدود نیستند.

شکل 3 : ساختار ترتیبی عمومی

ساختار ممتیک موازی

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

همان طور که در شکل 4 نشان داده شده است یک گره ممتیک (MN) مکانیزم تصمیم گیری است که اجازه انتخاب یک مم (عملگر) از میان چندین گزینه می دهد.

شکل 4 : گره ممتیکی

همانند گره های الکتریکی یک گره ممتیک می تواند به عنوان یک اتصال با حداقل سه عملگر یا مم یا مولفه مشاهده شود. که یکی از آنها فعالیت می کند و دو یا بیشتر آنها در قالب لیستی در مراحل بعد انتخاب می شوند. باید در نظر داشت که یک گره در ساختار ترتیبی زمانی ارائه می شود که قسمتی از حلقه در دو جهت ادامه داشته باشد. مم هایی که هم جهت با گره ممتیکی یکسان هستند می توانند موازی باشند. در این مقاله ساختار ممتیکی که فقط شامل یک گره ممتیکی است ساختار ممتیک موازی (PMS) نامیده می شود.

یک پیاده سازی از ساختار ممتیک موازی:

در این بخش از مقاله نحوه پیاده سازی از ساختار ممتیکی موازی مورد بررسی قرار گرفته شده است. بدین منظور، شبه کد الگوریتم فاصله اکتشاف بلند در شکل 5 نشان داده شده است. همچنین شبه کد الگوریتم اکتشاف فاصله کوتاه که یک روش جستجوی محلی است که یک راه حل تنها را با n محورش تحریک می کند، در شکل 6 نشان داده شده است.

شکل 5: شبه کد الگوریتم فاصله اکتشاف بلند

شکل 6: شبه کد الگوریتم فاصله اکتشاف کوتاه

الگوریتم rosenbrock

یک الگوریتم جستجوی محلی کلاسیک قطعی است که ثابت شده است که همیشه همگرا به بهینه محلی می باشد. در ابتدای بهینه سازی این مولفه، R شبیه به S می باشد که در آن هر یک از n جهت را کشف می کند. ماتریس A به عنوان ماتریس هویت مقداردهی اولیه می شود.

مثال کاربردی: مسیرهای وسیله مغناطیسی

الگوریتم ساختار ممتیکی موازی برای مسیرهای عبور ماشین مغناطیسی بکاربرده شده است که نشان از عملکرد مناسب الگوریتم دارد. نصب مسیرهای عبور ماشین مغناطیسی همانند نمودار 7 می باشد که اجزای مختلف آن به نمایش در آمده است.

شکل 7: نصب مسیرهای عبور ماشین مغناطیسی

نتایج:

در شکل 8 رفتار برازش (مقیاس برازش) الگوریتم های مختلف روی کاربرد ردپای مغناطیسی مورد بررسی قرار گرفته شده است.

شکل 8: مقایسه رفتار برازش (مقیاس لگاریتمی) الگوریتم های مختلف

در جدول 1 حداقل، متوسط و بهترین برازش ها به همراه انحراف معیار روی مسئله کاربردی مسیرهای مغناطیسی نشان داده شده است.

جدول 1: حداقل، متوسط و بهترین برازش ها به همراه انحراف معیار روی مسئله کاربرد ی مسیرهای مغناطیسی

داده های آزمایشی و مشخصات مغناطیسی بهینه در طول محورهای X,Y,Z با الگوریتم پیشنهادی PMS در شکل 9 نشان داده شده است.

شکل 9: داده های آزمایشی و مشخصات مغناطیسی بهینه با الگوریتم پیشنهادی

نتیجه گیری

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

  [1]. Fabio Caraffini, Ferrante Neri, Giovanni Iacca , Aran Mol ,”parallel memetic structures”, Elsevier, Information Sciences 227 (2013) 60–82,2012.