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

پردازش تصویر [ ویرایش ]

الگوریتم ACO در پردازش تصویر برای تشخیص لبه تصویر و اتصال لبه استفاده می شود. [73] [74]

تشخیص لبه:

گراف در اینجا تصویر دو بعدی است و مورچه ها از یک پیکسل رسوب فرومون عبور می کنند. حرکت مورچه ها از یک پیکسل به دیگری با تغییرات محلی مقدار شدت تصویر انجام می شود. این جنبش باعث می شود که بیشترین تراکم فرومون در لبه ها قرار گیرد.

مراحل مربوط به تشخیص لبه با استفاده از ACO زیر است: [75] [76] [77]

مرحله 1: راه اندازی:
به طور تصادفی محل $کی$ مورچه ها در تصویر $I_ {M_ {1} M_ {2}}$ جایی که $K = (M_ {1} * M_ {2}) ^ {\ tfrac {1} {2}}$ . ماتریکس فرومون $\ tau _ {(i، j)}$ با مقدار تصادفی مقدار دهی اولیه می شوند. چالش اصلی در فرایند آغازین تعیین ماتریس اکتشافی است.

روش های مختلفی برای تعیین ماتریس اکتشافی وجود دارد. برای مثال زیر، ماتریس اکتشافی بر اساس آمار محلی محاسبه شد: آمار محلی در موقعیت پیکسل (i، j).

$\ eta _ {(i، j)} = {\ tfrac {1} {Z}} * Vc * I _ {(i، j)}$

جایی که $من$ تصویر از اندازه است $M_ {1} * M_ {2}$
$Z = \ sum_ {i = 1: M_ {1}} \ sum_ {j = 1: M_ {2}} Vc (I_ {i، j})$ ، که یک عامل عادی است

${\ displaystyle {\ begin {aligned} Vc (I_ {i، j}) = & f \ left (\ left \ vert I_ {(i-2، j-1)} - I_ {(i + 2، j + 1 )} \ right \ vert + \ left \ vert I_ {(i-2، j + 1)} - I_ {(i + 2، j-1)} \ right \ vert \ right. \\ & + \ left \ I_ {(I-1، J-2)} - I_ {(I + 1، J + 2)} \ Right \ vert + \ left \ vert I_ {(I-1، J-1)} - I_ { (i + 1، j + 1)} \ right \ vert \\ و + \ left \ vert I_ {(i-1، j)} - I_ {(i + 1، j)} \ right \ vert + \ left \ vert I_ {(i-1، j + 1)} - I_ {(i-1، j-1)} \ right \ vert \\ و + \ left. \ left \ vert I_ {(i-1، j + 1)} - I _ {(i-1، j-2)} \ right \ vert + \ left \ vert I_ {(i، j-1)} - I_ {(i، j + 1)} \ right \ vert \ right) \ end {aligned}}}$

$f (\ cdot)$ می تواند با استفاده از توابع زیر محاسبه شود:
$f (x) = \ lambda x، \ quad {\ text {برای x ≥ 0؛ (1)}}$
$f (x) = \ lambda x ^ {2}، \ quad {\ text {برای x ≥ 0؛ (2)}}$
$f (x) = {\ begin {cases} \ sin {{\ frac {\ pi x} {2 \ lambda}}) و {\ text {for 0 ≤ x ≤}} \ lambda {\ text {؛ (3)}} \\ 0، & {\ text {else}} \ end {cases}}$
$f (x) = {\ begin {cases} \ pi x \ sin {{\ frac {\ pi x} {2 \ lambda}}) و {\ text {برای 0 ≤ x ≤}} \ lambda {\ text {؛ (4)}} \\ 0، & {\ text {else}} \ end {cases}}$
پارامتر $\ lambda$ در هر یک از توابع فوق، اشکال مربوط به توابع را تنظیم می کند.
مرحله 2 روند ساخت و ساز:
جنبش مورچه بر اساس 4-متصل پیکسل یا 8-متصل پیکسل . احتمالاتی که مورچه ها از طریق معادله احتمال داده می شوند $P _ {{x، y}}$
مرحله 3 و مرحله 5 فرآیند به روز رسانی:
ماتریکس فرومون دوبار به روز می شود. در مرحله 3 دنباله ای از مورچه (با توجه به $\ tau _ {(x، y)}$ ) به روز شده است جایی که در مرحله 5 نرخ تبخیر دنباله به روز شده است که توسط معادله زیر داده شده است.
$\ tau _ {new} \ leftarrow (1- \ psi) \ tau _ {old} + \ psi \ tau _ {0}$ ، جایی که $\ psi$ ضریب فرونشینی فرومون است { $0 <\ tau <1$

مرحله 7 فرآیند تصمیم گیری:
هنگامی که کمانها یک فاصله ثابت L را برای تکرار N حرکت داده اند، تصمیم بر این است که آیا آن یک لبه یا نه بر اساس A آستانه T در ماتریس فرومون است. آستانه برای مثال زیر بر اساس روش اوسو محاسبه می شود .

لبه تصویر با استفاده از ACO تشخیص داده شده است:
تصاویر زیر با استفاده از توابع مختلف داده شده توسط معادله (1) تا (4) تولید می شوند. [78]

پیوند لبه: [79] ACO نیز در الگوریتم های اتصال لبه نیز اثبات شده است.

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

پیش بینی ورشکستگی [80]
طبقه بندی [81]
اتصال گرا مسیریابی شبکه [82]
مسیریابی بدون اتصال بی سیم [83] [84]
داده کاوی [81] [85] [86] [87]
جریان نقدی تخمین شده در برنامه ریزی پروژه [88]
بازیابی اطلاعات توزیع شده [89] [90]
طراحی شبکه برق و برق [91]
مشكل برنامه ریزی گردش كار Grid [92]
طراحی پپتیدی مهارکننده برای اثر متقابل پروتئین پروتئین [93]
سیستم تست هوشمند [94]
طراحی مدار الکترونیکی برق [95]
تاشو پروتئین [96] [97] [98]
شناسایی سیستم [99] [100]

دشواری تعریف [ ویرایش ]

با یک الگوریتم ACO، کوتاه ترین مسیر در یک گراف، بین دو نقطه A و B، از ترکیبی از چندین مسیر ساخته شده است. [101] تعریف دقیق از الگوریتمی که به صورت مستعمره یا مورچه نیست، آسان نیست، زیرا تعریف ممکن است بر اساس نویسندگان و کاربردها متفاوت باشد. به طور کلی، الگوریتم های کلونی مورچه به عنوان متهوریستی جمعیت شناخته می شوند و هر راه حل ارائه شده توسط یک مورچه در فضای جستجو است. [102] مورچه ها بهترین راه حل ها را نشان می دهند و از مارک های قبلی برای بهینه سازی جستجوی خود استفاده می کنند. آنها را می توان به عنوان الگوریتم های احتمال چند عامل با استفاده از توزیع احتمالی به منظور انتقال بین هر تکرار مشاهده کرد . [103] در نسخه های خود برای مشکلات ترکیبی، از ساختار تکراری راه حل استفاده می کنند. [104]بر طبق برخی از نویسندگان، چیزی که الگوریتم های ACO را از دیگر بستگان (مانند الگوریتم برای برآورد توزیع یا بهینه سازی ذرات چرخشی) متمایز می کند دقیقا جنبه سازنده آنها است. در مشکلات ترکیبی، ممکن است که بهترین راه حل در نهایت پیدا شود، حتی اگر هیچ مورچه اثبات مؤثر نباشد. بنابراین، در مثال مشکل فروشنده مسافر، ضروری نیست که یک مورچه در واقع کوتاهترین مسیر را طی کند: کوتاهترین مسیر را می توان از قوی ترین بخش های بهترین راه حل ها ساخت. با این حال، این تعریف می تواند در مورد مشکلات در متغیرهای واقعی مشکل ساز باشد، جایی که هیچ ساختار "همسایگان" وجود ندارد. رفتار جمعی حشرات اجتماعیهمچنان یک منبع الهام بخش برای محققان است. طیف گسترده ای از الگوریتم ها (برای بهینه سازی یا نه) به دنبال خودسازگاری در سیستم های بیولوژیکی منجر به مفهوم " هوش تازه " شده است، [9] که یک چارچوب بسیار کلی است که در آن الگوریتم های کلونی مورچه مناسب هستند.

الگوریتم های Stigmergy [ ویرایش ]

در عمل تعداد زیادی الگوریتم وجود دارد که ادعا می کنند "مستعمرات مورچه" هستند، و همیشه همیشه به اشتراک گذاری چارچوب کلی بهینه سازی توسط مستعمرات مورچه ای (COA) تقسیم می شوند. [105] در عمل، استفاده از تبادل اطلاعات بین مورچه ها از طریق محیط زیست (یک اصل به نام " نابسامانی ") به اندازه کافی برای الگوریتم متعلق به کلاس الگوریتم های کلونی مورچه مطرح می شود. این اصل برخی از نویسندگان را به ایجاد اصطلاح "ارزش" برای سازماندهی روش ها و رفتار مبتنی بر جستجوی غذا، مرتب سازی لارو، تقسیم کار و حمل و نقل تعاونی منجر شده است. [106]

روش های مرتبط [ ویرایش ]

الگوریتم های ژنتیکی (GA) یک مجموعه ای از راه حل ها را جایگزین می کنند. فرآیند یافتن راه حل های برتر، تکامل را نشان می دهد، با راه حل هایی ترکیب شده یا جهش می کند تا مجموعه ای از راه حل ها را تغییر دهد، با راه حل هایی که کیفیت پایین تر آنها را از بین می برد.
برآورد الگوریتم توزیع (EDA) یک است الگوریتم تکاملی است که جایگزین اپراتورهای تولید مثل سنتی توسط اپراتورهای مدل هدایت می شود. چنین مدل هایی از طریق استفاده از تکنیک های یادگیری ماشین آموخته شده و از مدل های گرافیکی احتمالی ارائه شده است که از آن می توان نمونه های جدید 107 [108] یا از طریق متقاطع هدایت شده تولید کرد. [109] [110]
آنالیز شبیه سازی شده (SA) یک روش بهینه سازی جهانی مرتبط است که فضای جستجو را با تولید راه حل های همسایه از راه حل فعلی بر میدارد. همسایه برتر همواره پذیرفته شده است. یک همسایه پایین تر به صورت احتمالی بر اساس تفاوت کیفیت و یک پارامتر دما پذیرفته می شود. پارامتر دما به عنوان الگوریتم پیشرفت می کند تا ماهیت جستجو را تغییر دهد.
بهینه سازی جستجوی واکنشی در ترکیب یادگیری ماشین با بهینه سازی، با اضافه کردن یک حلقه بازخورد داخلی به خود تنظیم پارامترهای آزاد الگوریتم به ویژگی های مشکل، نمونه و وضعیت محلی در اطراف راه حل فعلی متمرکز است.
جستجوی تابو (TS) شبیه سازی آنیلینگ است که در آن هر دو از راه حل فضایی عبور می کنند با آزمایش جهش های یک راه حل فردی. در حالی که انلینگ شبیه سازی تنها یک راه حل جهش یافته را تولید می کند، جستجوی tabu بسیاری از راه حل های جهش یافته را تولید می کند و به راه حل با پایین ترین تناسب تولید تولید می شود. برای جلوگیری از دوچرخه سواری و تشویق بیشتر حرکت از طریق فضای راه حل، لیست تابو از راه حل های جزئی یا کامل حفظ شده است. جابجایی به یک راه حل که حاوی عناصر لیست tabu است و به عنوان راه حل در فضای راه حل به روز می شود، ممنوع است.
الگوریتم های سیستم ایمنی مصنوعی (AIS) بر روی سیستم ایمنی بدن مهره دار مدل سازی می شوند.
بهینه سازی ازدحام ذرات (PSO)، یک هوش گروهی روش
قطره آب هوشمند (IWD)، یک الگوریتم بهینه سازی مبتنی بر رویارویی بر اساس قطرات آب طبیعی در رودخانه ها
الگوریتم جستجوی گرانشی (GSA)، یک هوش گروهی روش
روش خوشه بندي مورچه (ACCM)، روشي است که از روش خوشه بندي استفاده مي کند، گسترش ACO.
جستجوی توزیع تصادفی (SDS)، روش جستجو و بهینه سازی جهانی احتمال احتمالی مبتنی بر عامل، بهترین مناسب برای مشکلات که در آن تابع هدف را می توان به چندین توابع مستقل جزئی تقسیم کرد

تاریخچه [ ویرایش ]

مخترعان عبارتند از فرانس مایسون و برنارد مندریک . پیشگامان این زمینه عبارتند از: مارکو دوریگو ، لوکا ماریا گامباردلا . [111]

زمان سنجی الگوریتم های COA

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

1959، پیر پل گراس اختراع نظریه نشانهورزی به توضیح رفتار ساختمان لانه در موریانه ؛ [112]
1983، Deneubourg و همکارانش مورد مطالعه رفتار جمعی از مورچه ها ؛ [113]
1988، و Moyson Mandeick یک مقاله در مورد خود سازمان دهی در میان مورچه ها؛ [114]
1989، کار Goss، Aron، Deneubourg و Pasteels در رفتار جمعی مورچه های آرژانتین ، که ایده الگوریتم های بهینه سازی colony را ارائه می دهد؛ [115]
1989، پیاده سازی یک مدل رفتار برای غذا توسط ایبلیگ و همکارانش؛ [116]
1991، M. Dorigo پیشنهاد سیستم مورچه در پایان نامه دکترای خود (که در سال 1992 منتشر شد [6] ). یک گزارش تکنیکی که از پایان نامه استخراج شده و با همکاری نویسنده V. Maniezzo و A. Colorni [117] پنج سال بعد منتشر شد؛ [31]
اپلبی و استیوارد از شرکت مخابرات بریتانیا اولین کاربرد خود را در شبکه های مخابراتی منتشر کردند [118]
1996، انتشار مقاله در سیستم مورچه؛ [31]
1996 Hoos و Stützle اختراع سیستم حداکثر مین را نشان می دهند ؛ [24]
1997 Dorigo و Gambardella سیستم مستعمرات مورچه را منتشر می کنند ؛ [25]
1997 Schoonderwoerd و همکارانش یک برنامه بهبود یافته برای شبکه های مخابراتی را منتشر کردند؛ [119]
1998، Dorigo اولین کنفرانس اختصاص داده شده به الگوریتم های ACO را راه اندازی کرد؛ [120]
1998، Stützle پیشنهاد اجرای اولیه موازی ؛ [121]
1999، Bonabau، Dorigo و Theraulaz کتابی را به طور عمده با مورچه های مصنوعی منتشر می کنند [122]
2000، شماره خاصی از مجله سیستم های کامپیوتری نسل آینده در الگوریتم های مورچه [123]
2000، برنامه های اولیه برای برنامه ریزی ، توالی برنامه ریزی و رضایت از محدودیت ها ؛
2000، گوتهار اولین شواهد همگرایی برای الگوریتم مستعمرات مورچه را فراهم می کند [124]
2001، اولین استفاده از الگوریتم های COA توسط شرکت ها ( Eurobios و AntOptima )؛
2001، Iredi و همکارانش اولین الگوریتم چند هدفه را منتشر کردند [125]
2002، اولین برنامه های کاربردی در طراحی برنامه، شبکه های بیزی؛
2002، Bianchi و همکارانش اولین الگوریتم برای مشکل تصادفی را پیشنهاد کردند . [126]
2004، Dorigo و Stützle کتاب "بهینه سازی قلم مویی" را با MIT Press [127] منتشر می کنند.
2004، Zlochin و Dorigo نشان می دهد که برخی از الگوریتم ها معادل با تبادلات تصادفی تصادفی ، روش متقابل آنتروپی و الگوریتم برای تخمین توزیع [29]
2005، برنامه های کاربردی برای مشکلات تاخیری پروتئینی .
2012، Prabhakar و همکارانش تحقیقاتی راجع به عملیات مورچه ها در ارتباط با یک فروند بدون فرومون انجام دادند و به اصول سازمان شبکه کامپیوتری پاسخ دادند. مدل ارتباطی با پروتکل کنترل حمل و نقل مقایسه شده است . [128]
2016، اولین برنامه کاربردی برای طراحی توالی پپتید. [93]
2017، ادغام موفق چند روش تصمیم گیری PROMETHEE به الگوریتم ACO ( الگوریتم HUMANT ). [129]

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

ریاضیات

آموزش ریاضی