ادامه الگوریتم بهینه سازی کلون مورچه

انتخاب لبه [ ویرایش ]

یک مورچه یک عامل محاسباتی ساده در الگوریتم بهینه سازی کلنی مورچه است. این یک تکرار راه حل برای مشکل در دست ساخت است. راه حل های متوسط می گویند به عنوان دولت راه حل. در هر تکرار الگوریتم، هر مورچه از یک حالت حرکت می کند $ایکس$ به دولت $ی$ ، مربوط به یک راه حل کامل تر میانجی است. بنابراین، هر مورچه $ک$ مجموعه ای را محاسبه می کند $A_ {k} (x)$ از امکان عملی شدن در هر تکرار به حالت فعلی آن و به احتمال زیاد به یکی از اینها حرکت می کند. برای مورچه $ک$ ، احتمالی $p_ {xy} ^ {k}$ از حرکت از دولت $ایکس$ به دولت $ی$ بستگی به ترکیبی از دو ارزش، یعنی جذابیت دارد $\ eta _ {xy}$ از حرکت، به عنوان محاسبه شده توسط برخی از اکتشافی نشان می دهد که پیش نیاز مطلوب این حرکت و سطح مسیر $\ tau _ {xy}$ از حرکت، نشان می دهد که چقدر مهارت در گذشته بوده است تا این حرکت خاص را انجام دهد.

سطح دنباله دار نشان دهنده یک نشانه پسینی از مطلوبیت که حرکت کند. مسیرهای به روز شده معمولا زمانی که تمام مورچه ها راه حل خود را کامل، افزایش یا کاهش سطح مسیرهای پیاده روی مربوط به حرکت که بخشی از "خوب" و یا "بد" راه حل، به روز شده است.

به طور کلی، $ک$ مین حرکت می کند از دولت $ایکس$ به دولت $ی$ با احتمالی

$p_ {xy} ^ {k} = {\ frac {{\ tau _ {xy} ^ {\ alpha}) (\ eta_ {xy} ^ {\ beta})} {\ sum_ {z \ in \ mathrm {اجازه} _ {x}} (\ tau _ {xz} ^ {\ alpha}) (\ eta _ {xz} ^ {\ beta})}}$

جایی که

$\ tau _ {xy}$ مقدار فرومون ذخیره شده برای انتقال از دولت است $ایکس$ به $ی$ $\ alpha$ یک پارامتر برای کنترل نفوذ است $\ tau _ {xy}$ ، $\ eta _ {xy}$ مطلوبیت انتقال دولت است $xy$ ( دانش پیشین ، به طور معمول $1 / d _ {{xy}}$ ، جایی که $د$ فاصله است) و $\ بتا$ ≥ 1 یک پارامتر برای کنترل نفوذ است $\ eta _ {xy}$ . $\ tau _ {xz}$ و $\ eta _ {xz}$ نشان دهنده سطح جذابیت و پیگیری برای سایر تغییرات ممکن دولت است.

به روز رسانی فرومون [ ویرایش ]

هنگامی که تمام مورچه ها یک راه حل را به اتمام رسانده اند، مسیرهای مسیر به روز شده اند $\ tau _ {xy} \ leftarrow (1- \ rho) \ tau _ {xy} + \ sum_ {k} \ Delta \ tau _ {xy} ^ {k}$

جایی که $\ tau _ {xy}$ مقدار فرومون ذخیره شده برای انتقال وضعیت است $\ rho$ است ضریب تبخیر فرمون و $\ Delta \ tau _ {xy} ^ {k}$ مقدار فرومون ذخیره شده توسط $ک$ ، به طور معمول برای یک مشکل TSP (با حرکت متناظر با قوس گراف) با

$\ Delta \ tau _ {xy} ^ {k} = {\ begin {cases} Q / L_ {k} & {\ mbox {if مورچه}} k {\ mbox {با استفاده از منحنی}} xy {\ mbox { تور}} \\ 0 & {\ mbox {در غیر این صورت}} \ end {cases}}$

جایی که $L_ {k}$ هزینه این است $ک$ تور مورچه (به طور معمول طول) و $سئوال$ یک ثابت است

برنامه های کاربردی [ ویرایش ]

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

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

اولین الگوریتم ACO سیستم مورچه نامیده شد [31] و هدف آن حل مسئله فروشندگان مسافرتی است که هدف آن یافتن کوتاه ترین سفر به منظور پیوند یک سری از شهرها است. الگوریتم عمومی نسبتا ساده است و براساس مجموعه ای از مورچه ها ساخته می شود که هر کدام از آنها ممکن است در سفرهای دور شهرها باشد. در هر مرحله، مورچه تصمیم می گیرد که از یک شهر به دیگری بر اساس برخی از قوانین حرکت کند:

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

برنامه ریزی مشکل [ ویرایش ]

مشکل برنامه ریزی شغلی (JSP) [32]
مشکل برنامه ریزی باز (OSP) [33] [34]
مساله جریان مجازی (PFSP) [35]
یک مشکل کامل ترد شدن ماشین (SMTTP) [36]
تنها مشکل ماشین مجاز ماشین (SMTWTP) [37] [38] [39]
مشکل برنامه ریزی پروژه با محدودیت منابع (RCPSP) [40]
مشکل برنامه ریزی گروه (GSP) [41]
مشکل تکینگی یک ماشین با زمان تنظیم تنظیم وابسته (SMTTPDST) [42]
مساله برنامه ریزی جریان چند مرحله ای (MFSP) با زمان تنظیم / تعویض وابسته به توالی [43]

مشکل مسیریابی خودرو [ ویرایش ]

مشکل مسیریابی ظرفیت (CVRP) [44] [45] [46]
مسائل مسیریابی چند راهه (MDVRP) [47]
مسائل مسیریابی مسافت (PVRP) [48]
مسائل مربوط به مسیریابی تقسیم تحویل (SDVRP) [49]
مسير تصادفي تصادفي (SVRP) [50]
مشکل رانندگی خودرو با وانت و تحویل (VRPPD) [51] [52]
مشکل مسیریابی خودرو با پنجره های زمان (VRPTW) [53] [54] [55]
مسائل مسیریابی وابسته به زمان با پنجره های زمان (TDVRPTW) [56]
مسائل مربوط به مسیریابی خودرو با پنجره های زمان و کارکنان خدمات مختلف (VRPTWMS)

مشکل تخصیص [ ویرایش ]

تنظیم مشکل [ ویرایش ]

مشکل پوشش مجموعه (SCP) [62] [63]
مشکل پارتیشن (SPP) [64]
مشکل پارتیشن درخت گرافیک محدود (WCGTPP) [65]
مشکل درخت درختی با وزن با وزن قوس (AWlCTP) [66]
مشکل چندگانه (MKP) [67]
حداکثر مشکل مجموعه مستقل (MIS) [68]

مشکل اندازه دستگاه در طراحی فیزیکی نانوالکترونیک [ ویرایش ]

بهینه سازی مونتاژ کلونیا (ACO) بر اساس 45 نانومتر تقویت کننده مدار حسگر مبتنی بر CMOS می تواند در زمان بسیار کم به راه حل های بهینه کمک کند. [69]
سنتز جریان برگشت پذیر بهینه سازی مورچه کلونی (ACO) می تواند به طور قابل توجهی بهبود کارایی را داشته باشد. [70]

بهینه سازی و سنتز آنتن [ ویرایش ]

ویبراتور Loopback 10 × 10، با استفاده از الگوریتم ACO [71]

ویبراتور Unloopback 10 × 10، با استفاده از الگوریتم ACO سنتز شده [71]

برای بهینه سازی فرم آنتن، می توان از الگوریتم های کلونی مورچه استفاده کرد. به عنوان مثال می توان بر اساس الگوریتم های colony colony (ACO)، RFID های آنتن ها [72]، وای فایر loopback و unloopback 10 × 10 [71]

+ نوشته شده در چهارشنبه نوزدهم تیر ۱۳۹۸ ساعت 23:21 توسط علی رضا نقش نیلچی |

ریاضیات

آموزش ریاضی