بخشی از مقاله
چکیده– امروزه بکارگیری الگوریتم های ابتکاری در حل مسائل بهینه سازی، گسترش چشم گیری داشته است. اساس کار این الگوریتم ها اغلب بر پایه الهام از طبیعت می باشد. الگوریتم جستجوی گرانشی از الگوریتم های نوین هوش جمعی است که با استفاده از قانون گرانش و مفهوم جرم ایجاد شده است. در این مقاله با استفاده از یکی دیگر از پدیده های طبیعی در عالم نجوم به نام سیاهچاله، عملگر جدیدی ارائه می شود. الگوریتم گرانشی با استفاده از عملگر سیاهچاله می تواند به کاوش بهتر و دقیق تری در فضای جستجو بپردازد. الگوریتم پیشنهادی بر روی 7 تابع محک تک مدی استاندارد آزمایش شده است که در قیاس با الگوریتم گرانشی و نیز الگوریتم گرانشی مجهز به عملگر فروپاشی عملکرد بهتری در حل مسائل تک مدی نشان داده است.
-1 مقدمه
بسیاری از مسایلی که به طور روزمره در صنعت، علوم و محیط اطراف ما یافت می شود، نیازمند بهینه سازی هستند. یکی از روش های بهینه سازی، استفاده از الگوریتم های جستجوی ابتکاری است. این الگوریتم ها بر پایه تصادف بنا نهاده شده اند و از نوع جمعیتی هستند و جستجوی فضا را به صورت موازی انجام می دهند که این مورد وجه تمایز این الگوریتم ها با الگوریتم های کلاسیک است.
در این الگوریتم ها از مفاهیم طبیعی مانند قانون ترمودینامیک، تکامل در موجودات زنده، پیدا کردن کوتاهترین مسیر بین غذا ولانه به وسیله مورچه ها، پیداکردن غذا توسط پرندگان و ماهی ها، قوانین گرانش و نظایر آن استفاده شده است.از جمله روش های جستجوی ابتکاری می توان به الگوریتم های تکاملی 1 - EA - - شامل: الگوریتم وراثتی، برنامه ریزی وراثتی، راهبرد تکاملی،برنامه ریزی تکاملی - ، ذوب شبیه سازی شده، جمعیت مورچگان، گروه ذرات، ،سیستم ایمنی و جستجوی گرانشی اشاره کرد.
در این الگوریتم ها تعادل میان کاوش2 و بهره گیری3 یکی از موضوعات مهم و چالشی است. هر عملگر خاص در این الگوریتم ها وظیفه خاصی در اجرای کاوش و بهره گیری دارند و در واقع ایجاد چنین عملگرهایی به کاوش یا بهره گیری بیشتر در مسأله کمک می کند. از این رو تلاش در ایجاد و اصلاح عملگرها در الگوریتم های ابتکاری اهمیت پیدا کرده است. مثلا در الگوریتم وراثتی انواع عملگرهای همبری و جهش ساخته شده است. مثلا در مرجع [1] عملگرهای جهش چندگانه، جهش متمرکز شده ، همبری دوتایی طراحی شده است.
یکی دیگر از الگوریتم های ابتکاری مهم الگوریتم بهینه سازی جمعیت ذرات4 می باشد. این الگوریتم با الهام از حرکت پرندگان و رفتار آنها در جستجوی غذا ساخته شده است. برای این الگوریتم نیز برای برقراری تعادل بین کاوش و بهره گیری توپولوژی ها و عملگر های خاصی ایجاد شده است. مثلا در مرجع [2] یک عملگر جهش جدید بر پایه موجک برای افزایش کارایی الگوریتم PSO در مسایل مختلف ایجاد شده است. جایگزینی ذرات بهتر بر معیار شایستگی برای تولید نسل جدید در [3] پیشنهاد شده است .
همچنین طرح های توپولوژی همسایگی مختلفی برای ذرات مورد بحث قرار گرفته است. مثلا در 4]و[5، 4 توپولوژی همسایگی ذرات شامل ستاره، چرخ، حلقه و لبه های اتفاقی مورد ارزیابی قرار گرفتند. الگوریتم جستجوی گرانشی5 یکی از الگوریتم های جدید ابتکاری استکه بر مبنای قانون جاذبه، اجرام گرانشی اخیرا توسط راشدی و نظام آبادی [8] معرفی شده است. آزمایش های انجام شده بر روی این الگوریتم نشان از توانایی بالای آن در همگرایی و یافتن جواب بهینه می باشد.
[6-9] اما امکان همگرایی زودرس در این الگوریتم نیز وجود دارد. چرا که نیروی هدایتگر اجرام آنها را به سمت یکدیگر جذب می کند و اگر اجرام به جواب غیر بهینه ای همگرا شوند، کارایی الگوریتم را پایین می آورد. به همین دلیل ضروری است که به ایجاد عملگرهایی پرداخته شود که قدرت کاوش را زیاد کنند. ما نیز با الهام از پدیده نجومی سیاهچاله6 به ایجاد عملگری برای افزایش قدرت کاوش در مسایل تک مدی پرداخته ایم. در این مقاله در بخش 2، مروری بر الگوریتم گرانشی انجام می شود و در بخش 3، سیاهچاله در طبیعت معرفی می گردد. در بخش 4، شبیه سازی عملگر سیاهچاله شرح داده می شود و در بخش 5 و 6 به ترتیب به نتایج آزمایش ها و جمع بندی پرداخته می شود.
-2 الگوریتم جستجوی گرانشی
در این الگوریتم عامل های جستجو کننده، مجموعه ای از اجرام می باشند که می توان آنها را به صورت سیاره های یک منظومه در نظر گرفت. این اجرام با استفاده از قانون گرانش نیوتن و قانون حرکت با یکدیگر در تبادل اطلاعات و جابجایی هستند. اجرای این الگوریتم به صورت دو مرحله کلی است:
الف- تشکیل یک سیستم مصنوعی با زمان گسسته در یک محیط مسأله، موقعیت یابی اولیه برای اجرام، وضع قوانین حاکم وتنظیم پارامترها.
ب- گذر زمان، حرکت اجرام و به روز رسانی پارامترها تا رویدادن زمان توقف. محیط سیستم همان محدوده تعریف مساله می باشد . همان طور که گفته شد طبق قانون گرانش هرجرم محل و وضعیت سایر اجرام راازطریق نیروی جاذبه گرانشی درک می کند. هر نقطه از فضا، یک جواب از مسأله است.
-3 سیاهچاله در طبیعت
جهان اطراف ما سرشار از پدیده هایی شگرف می باشد. یکی از چنین پدیده های طبیعی در عالم ستارگان، سیاهچاله است. بنا به نظریه فضا-زمان گرانش انیشتین، فضا-زمانهایی وجود دارند که دارای یک سطح محدود و گرانشی بسیار قوی هستند که حتی فوتون هم نمی تواند از آن بگریزد. در سال 1783 یک منجم انگلیسی، تئوری ذره ای بودن نور را تحقق بخشید. اگر نور واقعا یک جریان ذره ای بود، باید تحت تأثیر گرانش قرار گیرد. وی حدس زد که تحت شرایطی ستاره ای می تواند وجود داشته باشد که حتی نور هم نتواند از آن بگریزد.
فروریزش یک ستاره و تبدیل آن به سیاهچاله در تئوری نسبیت عام انیشتین مورد بحث قرار گرفت و پس از آن اثبات شد که وقتی ستاره بزرگی سوخت هسته ای اش به اتمام برسد، شروع به فروریزش می کند و بنا به شرایطی تبدیل به سیاهچاله می شود .[17] فضای اطراف سیاهچاله تا فاصله ای از مرکزش تحت تأثیر جاذبه ای بسیار قوی قرار دارد. این فاصله، شعاع شوارتزشیلد7 نام دارد که مقدار آن - 6 - × است که M جرم سیاهچاله، G شتاب گرانشی و c سرعت نور می باشد.
پس از اینکه یکی از اجرام به سیاهچاله تبدیل شد، اجرام دیگر را تحت تأثیر گرانش خود قرار می دهد . این تأثیرپذیری بستگی به فاصله آن اجرام تا سیاهچاله دارد که با شعاع Rs سنجیده می شود . بدین صورت که اگر جرم به اندازه کافی به سیاهچاله نزدیک باشد، با توجه به حرکت مارپیچی ذرات درطی افتادن درون سیاهچاله ، نیروهای مواج و همچنین طبق رابطه - 8 - ، روابط - 10و - 11 پیاده سازی شده است. این روابط باعث می شود که عامل جستجو کننده به جواب دقیق-تری همگرا شود. شبه کد الگوریتم پیشنهادی در شکل 2 آورده شده است.
1. تعیین محیط سیستم و مقدار دهی اولیه.
2. جابجایی اولیه اجرام.
3. ارزیابی اجرام.
4. به روز رسانی پارامترهای G، best، worst و .M
5. محاسبه نیروی وارد بر هر جرم.
6. محاسبه شتاب و سرعت هر جرم.
7. بروز رسانی موقعیت اجرام بر اساس روابط 10و.11
8. اگر شرط توقف برآورده نشده است به مرحله 3 برو.
9. پایان.
