الگوریتم کولونی مورچگان:پایان نامه درباره جایابی بهینه خازن

دانلود پایان نامه

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

 

هوش حشره­ای، خاصیت سیستم­های متشکل از عوامل غیر هوشمند با توانایی­های فردی بسیار محدود است که در کنار یکدیگر و در قالب یک اجتماع، رفتار هوشمندی از خود نشان می­دهند. با چنین رویکردی منظور از یک عامل دراین تعریف، عبارت است از موجودیتی که می­تواند محیط خود را حس کرده، مشاهدات و محسوسات خود، از محیط را بصورت بسیار ساده و سطحی درک کند تا بتواند عملی از گزینه­های محدودی را که پیش روی دارد، انجام دهد. این اعمال شامل تغییر و اصلاح در محیطی است که عامل در آن فعالیت می­کند. اصولاً رفتار هوشمند چنین اجتماعی از عوامل، از طریق ارتباط غیر مستقیم بین عوامل صورت می- گیرد. مطالعات بیولوژیکی بر روی مورچگان و گونه­های مختلف آنها شرایط و خواص مشابهی را نشان می­دهد. پژوهش­های زیست شناسان در مورد رفتار مورچگان نشان داده است که این گونه از حشرات با وجود نابینایی مطلق، توانایی بسیار زیادی در یافتن کوتاه­ترین مسیر از لانه خود تا منبع غذا حتی با وجود موانع بسیار بر سر راه خود دارند. در واقع هر مورچه از لحاظ رفتاری یک حشره بسیار ساده با حافظه بسیار محدود است که رفتاری با خواص احتمالی از خود بروز می­دهد. درعین حال تعدادی از مورچگان در کنار هم و در قالب یک اجتماع قادرند از عهده انجام فعالیتهای بسیار پیچیده به خوبی برآیند. نمونه­ای از این توانایی مساله لانه­سازی است که هر مورچه یک سازه ایجاد شده توسط مورچه قبلی را حس می­کند و آن را توسعه می­دهد تا زمانی که یک لانه ساخته شود. نوع دیگری از ارتباط میان مورچگان از طریق بر جای گذاری اثر فرومون[1] است. مورچگانی که در جستجوی غذا هستند مقادیری از نوعی ماده شیمیایی به نام فرومون (نوع خاصی هورمون) از خود به جای می­گذارند و به این ترتیب مسیر حرکت خود را علامت گذاری می­کنند. مورچه دیگری که بطور مستقل در حال حرکت است به هنگام مواجه شدن با مسیری که آغشته به فرومون است آن را شناسایی کرده با احتمال بسیار زیادی تصمیم به دنبال کردن آن مسیر می­گیرد و به این ترتیب آن مسیر را به مقدار فرومون بیشتری آغشته می­کند. از آنجا که فرومون موجود در مسیرها پس از مدتی تبخیر می­شود مجموع تعامل میان فرومون بر جای گذاشته شده در یک مسیر، تعداد مورچگانی که از آن مسیر تردد می­کنند، شدت تبخیر فرومون و مسافت و طول مسیر باعث می­شود که پس از مدتی کوتاه ترین مسیر میان لانه مورچگان و منبع غذایی کشف شود

  منطقه آسیای مرکزی

(الف)تعدادی مورچه روی مسیر E-A در حال حرکت هستند. (ب) مانعی بطور ناگهانی بر سر راه مورچگان قرار می­گیرد و هر مورچه باید مسیری را برای دور زدن انتخاب کند. (ج) پس از مدتی مسیر کوتاهتر توسط مورچگان پیدا شده و بیشتر از آن مسیر تردد می­کنند.

 

شرایط این آزمایش که توسط Maniezzo , Dorigo , Colorn ارائه شده به شرح زیر است. مسیر مستقیمی میان یک منبع غذایی (A) و لانه مورچگان (E) را در نظر بگیرید که مورچگان بر روی این مسیر مستقیم در حال رفت و آمد هستند. سپس بطور ناگهانی یک مانع بر سر راه مورچگان قرار گرفته و مسیر مستقیم را قطع می­کند. بنابراین مورچگانی که از نقطه E به سمت A در حال حرکت هستند در نقطه D و آنان که از A به سمت E در حال حرکت هستند در نقطه B مجبور می­شوند برای ادامه مسیر یکی از جهات راست یا چپ را انتخاب نمایند. در لحظه نخست این انتخاب به تصادف صورت می­گیرد، یعنی نیمی از مورچگان به طرف راست و نیمی دیگر به سمت چپ حرکت خواهند کرد اما پس از مدتی این انتخاب در جهت شدت فرومون برجای مانده از مورچگان قبلی روی هر مسیر قرار خواهد گرفت. برای نخستین مورچه­ای که به نقطه B (یا D) می­رسد، انتخاب جهت از احتمال مساوی برخوردار است چرا که، هنوز هیچ فرومونی روی دو مسیر موجود نیست اما با توجه به اینکه مسیر BCD کوتاهتر از مسیر BHD است نخستین مورچه­ای که به تصادف از BCD عبور کند زودتر به نقطه D خواهد رسید. همین امر باعث می­شود که مورچه­ای که در همان لحظه از E به D رسیده از پیش روی خود مسیری دارای فرومون BCD را شناسایی کند و با احتمال زیادی از آن مسیر عبور کرده و شدت فرومون را در آن مسیر افزایش دهد. به همین ترتیب سایر مورچگان نیز مسیر کوتاهتری که لاجرم فرومون بیشتری بر آن جمع خواهد شد، را شناسایی کرده و با احتمال بیشتر آن را انتخاب می­کنند تا اینکه مانند شکل (4-1) کلیه مورچگان از مسیر کوتاهتر رفت­ و آمد نمایند. مشاهده این رفتار و شناسایی خاصیت فرومون مورچگان و باز خور مثبت این ماده شیمیایی در هدایت مورچگان موجب شد تا Dorigo و همکارانش در دانشگاه پلی تکنیک میلان در ایتالیا و دانشگاه آزاد بروکسل در بلژیک اقدام به شبیه­سازی این رفتار و طراحی عوامل بسیار ساده­ای تحت عنوان مورچه بنمایند که بتوانند رفتار مورچه­های واقعی را شبیه­سازی نمایند. به این ترتیب Dorigo و همکارانش موفق شدند در سالهای 1991 و 1992 یعنی کمتر از 20 سال پیش، این خواص را در قالب مورچگان مصنوعی شبیه­سازی کرده و با رویکردی ریاضی اقدام به حل مسائل پیچیده ریاضی بنمایند. در شکل (4-2) یک شمای کلی از نحوه شکل‌گیری کوتاه ترین مسیر توسط مورچگان به تصویر در آمده ­است.

  سابقه برند-"پایان نامه در مورد محبوبیت برند"

 

الف) گراف اولیه با طول فواصل میان نقاط

 

ب) در زمان 0t = هیچ اثری فرومون روی شاخه­های گراف موجود نیست.  در نتیجه 30 مورچه­ای که در این لحظه به نقطه B یا C رسیده­اند با احتمال مساوی یکی از مسیرها را انتخاب می­کنند.

 

ج) در زمان 1t = شدت اثر فرومون روی مسیر کوتاهتر بیشتر است که در مجموع مطلوبیت بیشتری برای مورچگان پیدا می­کند.( نشان دهنده میزان فرومون است)

 

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

 

1- Pheromone