دانلود تحقیق الگوریتم اجتماع مورچه

Word 188 KB 11942 13
مشخص نشده مشخص نشده شیمی - زیست شناسی
قیمت قدیم:۷,۱۵۰ تومان
قیمت با تخفیف: ۵,۰۰۰ تومان
دانلود فایل
  • بخشی از محتوا
  • وضعیت فهرست و منابع
  • الگوریتم اجتماع مورچه (Ant Colony Algorithm)

    1- معرفی

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

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

    در این مطالعه مدل کاوش مورچه ها Meta-Heurestic انتخاب شده است و درابتدا الگوریتمهای ساده شرح داده می شود و سپس به مطالعه سیستم AS (ant system) و سیستمACS (ant colony system) وMMAS(max-min ant system) و..... شرح داده می شود.

     

    -2- رفتار طبیعی مورچه

    یک مورچه در حال حرکت مقداری فرومون دراندازه­های گوناگون از خود بر روی زمین باقی می­گذارد و بدین ترتیب مسیر را به­وسیله­ی بوی این ماده مشخص می­سازد. هنگامی که یک مورچه به­طور تصادفی  و تنها حرکت می­کند با روبه­رو شدن با مسیری که توسط مورچه یا مورچه­های قبلی انتخاب شده و دارای بوی فرومون است به احتمال زیاد آن را  انتخاب می­کند و با فرومونی که خود بر جای می­گذارد بوی آن را در مسیر مذکور تقویت می­نماید.

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

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

    الگوریتم های ACO   بر پایه مدل احتمال پارامتری(مدل فرومون) قرار دارند.

    مورچه های مصنوعی به طور افزایشی با اضافه کردن به جا و مناسب مولفه های راه حل تعریف شده به راه حل جزئی مورد نظر راه حلهایی را می سازند.

    A

    B

    در تصویر بالا مسیرهای متفاوت برای غذایابی دیده می شود.و  تعداد مورچه ها و A و B مسیرهای در زمان t جستجو برای یافتن مسیر آغاز و در زمان t+1 مسیر پیدا شده و فرمول مورد استفاده :

    C کمیتی غیر اکتشافی برای مقدار جذب فرمون است و تحت تاثیر فرمون ذخیره شده در فرآیند است.و باتعداد مورچه ها نسبت مستقیم دارد.در اثر تجربه مقدار برای =2 و c=20 است. اگر  پس مسیر A بهتر از B است.

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

    و شاخه قویتر مورد استفاده قرار میگیرد.الگوریتم زیر برای ایجاد مسیر کوتاهتر است:

    Let r~U(0,1)

          For each potential path A do

              Calculate Pa  using ,e.g.,equation (1.1)

                 If r<=Pa then

                      Follow path A;

                      Breack ;

               End

    End

    -3بهینه سازی کلونی مورچه ساده(SACO) :

     

    برای انجام این کار، مورچه های مصنوعی یک گام برداری تصادفی را روی گراف همبند کامل G=(C,L) انجام می دهند، که راسهای آن مولفه های راه حل C و مجموعهء L ، اتصالات است.این گراف، گراف ساخت[1] نام دارد.

     وقتی یک مسئله CO دارای محدودیت را در نظر می گیریم، محدودیتهای مسئله در رویه سازندهء مورچه ها ساخته می شوند به نحوی که در هر مرحله از فرایند ساخت فقط مولفه هایی از راه حل که عملی هستند می توانند به راه حل جزئی فعلی اضافه شوند. مولفه­های ci ЄC با پارامتر ردیابی فرومون  Ti متناظر می شوند و اتصالات  Lij ЄL  می توانند با پارامتر ردیابی فرومون Tij متناظر گردند.  مجموعهء کل این پارامترها با T نشان داده می­شود.

    مقادیر این پارامترها ( مقادیر فرومون) به ترتیب با  نشان داده می شوند.

    به علاوه مولفه ها و اتصالات به ترتیب می توانند با مقدار اکتشافی   متناظر گردند.

    مجموعهء همه مقادیر را با H نشان می دهیم. . این مقادیر برای تصمیمات احتمالی مورچه ها در مورد چگونگی حرکت در گراف ساخت استفاده می گردند.احتمالات مربوط به گراف ساخت، احتمالات انتقال نامیده می شود.

    بعد از مقدار دهی اولیه به مقادیر فرومون ، در هر مرحله ، هر مورچه یک راه حل را می سازد. سپس این راه حلها برای به روزرسانی مقادیر فرومون استفاده می گردند

    در ابتدا، کلیهء مقادیر فرومون با یک مقدار کوچک مشابه ph>0 مقداردهی می شوند. در فاز ساخت، یک مورچه با افزودن مولفه هایی به راه حل جزئی فعلی ، به تدریج یک راه حل را ایجاد می کند.اگر هیچ نودی وجود نداشته باشد =0 و در غیر اینصورت فرآیند انجام و به می رسد.ودر صورت افتادن در حلقه باید ان مسیر حذف و دوباره عملیات انجام گردد. در مقادیر بالا برای  مقدار فرمون را تقویت میکندو دراین حال گره های اصلی بدست آمده وحلقه ها از بین می روند.وبرای فرمون اضافه شده استفاده می گردد.                 

    وبرای هر مسیر پیموده شده  برای K مورچه : 

    و این بدین معنی است که تعداد عبور ومرور برای هر مسیر طی شده بصورت معمولی باشد در هر بار مقدار F(xk(t)) فرمون بدست می آید و اگر  برای همه یکسان باشد بنابراین تنها مسیری متفاوت خواهد بود که کوتاهتر باشد.و همچنین مقدار کاهش فرمون  F(xk(t))/1 خواهد بود.

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

    < >مقادیر ضمنی : رفتار مورچه ها در طول مسیر متفاوت تحت تاثیر بقیه مورچه ها قرار دارد.مقادیر صریح: مقادیر فرمون تولید شده متناسب با مقدار فرمون محیط است.   در الگوریتم باید شدت تکرار   قبل از استحکام مسیرهای جدید برای انها محاسبه شود.             با       

    مقدار نرخ تغییر  فرمون است زیرا  برای کنترل یادآوری مسیر قبلی است

    در مقادیر بالا فرمون بسرعت رشد می کند و اگر  کم شود نرخ رشد کاهش می یابد  =1 باشد جستجو کاملا تصادفی خواهد بود.برای مورچه ها انتخاب مسیر بعدی وابسته به اطلاعاتی است که مورچه های دیگر از طریق فرمون بجا گذاشته اند بنابراین در یک محیط محلی انتخاب مسیر بعدی تصادفی نخواهد بود.

    SACO:

    1)بطور معمول در گرافهای ساده نزدیکترین مسیر انتخاب می شوند.

    2) در گرافهای بزرگتر،اگر در پارامترهای انتخابی حساسیت کم باشد کارایی کم می شود :

              الف:همگرایی در مسیرهای کوتاه برای تعداد مشخص مورچه خوب                            است.

            ب:اگر =0 یعنی تغییرات نداریم و الگوریتم همگرا نیست.

              ج:اگر کم باشد در مسیر کوتاه همگرایی داریم برای مقادیر بالا باید رفتار همگرا داشته باشد.

     

     

    ص 374

     

     

     

     

    Early ant algorithm:

    در مطالعه الگوریتم ACO تصمیم گیری برای طول مسیر بود که با افزایش طول مسیر کارایی آن پایین می امدو تغییراتی نیز برای اضافه شدن اطلاعات(فرمون) و اکتشاف لینکهاو حافظه برای هر دوره و بروز زسانی لینکها باید داشته باشیم.

    Ant system:

    اولین الگوریتم پیشرفته بوسیله دوریگو مورد مطالعه قرار گرفت و این پیشرفت روی SACO ،بوسیله تغییرات در  وتغییرات در اکتشاف لینکها و اضافه نمودن حافظه می باشد.

    در AS تغییرات نود I  به j بصورت:  

     اولویت اثردر  محاسبه هیورستیک  به هنگام حرکت از نود I به j  در مقدار اثرگذار بوده ومقدار  کم میگردد.

    مقدار تمرکز فرمون در هنگام حرکت باید نگهداری شود.

    پس پارامترهای  و  در حفظ شده و باالگوریتم اکتشافی GREEDY مقدارآنها محاسبه می گردد.

    مسائلی که درآنها هزینه و یا فاصله کمینه  مورد نیاز است   با  محاسبه می شوند.

    وبرای طی نشدن مسیری خاص می توان یک لیست ممنوع تولید کرد(حلقه مانع که نباید توسط مورچه ها طی شود )ومورچه در هنگام دیدن یک نود جدید آن را با لیست ممنوع مقایسه وسپس تصمیم می گیرد که انرا طی کند یا نه؟

    و فرمول محاسبه حلقه مانع:

    پارامتر مقدار فرمون در اتصال   با مقدار  است.و برای مقادیر کم ، و پارامتر باید از آن بیرون رود.

     

     

    برای مورچه بعدی  با مقدار  محاسبه می گردد.برای تشخیص سیکل:

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

    برای آنکه بتوانیم تراکم مورچه ها را در سیکل محاسبه کنیم.

    فرمون در مسیر با تراکم بالا محاسبه می گرددو برای کمیت مورچه ها نیز چون اطلاعات بصورت محلی ذخیره می گردندباید بروز زسانی شوند

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

    ص 379

    T=0

    Initialize all parameters i.e.                                            

    Place all ants k=1 ,…, nk     

    For each link (I,j) do

    End

    Repeat

    For each ant k= 1,….,nk  do

    xk (t)=0

    repeat

    from current node  I , select next node j with probability as defined in equation (23.6)

    xk (t) = xk (t) {(I,j)}

    until  full path has been constructed;

    compute  f(xk (t));

    end

    for each link (I,j) do

    apply evaporation using equation

    [1] Construction graph

  • فهرست:

    ندارد.


    منبع:

    ندارد.

کلمات کلیدی: اجتماع - فرومون - مورچه

چکیده یکی از چالشهای نظام جمهوری اسلامی ایران امنیت غذایی است. نگاهی گذرا به روند واردات مواد غذایی از جمله گندم، تصویر نگران کننده ای از امنیت غذایی نزدیک به 70 میلیون نفر جمعیت حاضر را ارائه می کند. بنابراین مسلم می گردد که کاهش ضایعات به طور کاملاً مستقیم با امنیت غذایی به عنوان یکی از سیاستهای کلان نظام در برنامه های توسعه مرتبط است. سالانه مبلغ کلانی ارز صرف واردات گندم می ...

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

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

مقدمه: در اين مقاله، مدلي جهت تعيين مکان و اندازه DG را در يک سيستم توزيع معرفي مي گردد که حل با استفاده از بهينه سازي اجتماع مورچگان (ACO) به عنوان يک ابزار بهينه سازي صورت مي گيرد. در اين الگوريتم DGها به عنوان منابع توان ثابت(نظير پيلهاي سوختي)

گفتگو: شادي زندگي، غم انساني - مقدمتاً بگو چرا در تمامي عمر بي تاب بوده اي و چه حسي تو را به اين آشوب کشانيده است؟ محسن مخملباف : پرسه هاي من خيلي قابل تشبيه است به پرسه هاي سلمان فارسي. کسي که مدام تشنه حقيقت بود و با آغوش باز به سو

حَشَرات بزرگ‌ترين گروه را در بين گروه بندپايان به خود اختصاص مي‌‌دهند بندپايان حيواناتي هستند که داراي يک اسکلت خارجي بوده و اعضاي آنها به هم پيوسته مي‌‌باشند حشرات شش پا دارند و بيشتر آنها داراي بال هستندبدن يک حشره از 3 قسمت تشکيل مي‌شود: سر، سينه

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

شرح : زنگاري باشد که آهن و فولاد را ضايع کند.(برهان ). زنگاري که آهن و فولاد را ضايع مي کند به طوري که از صيقل کردن برطرف نشود. (ناظم الاطباء). مورانه . مورجانه . مورچانه . (غياث ) (آنندراج): بس که دنيارا کمر بستم چو مور دانه کش مدتي چون موريانه

چکيده در اين تحقيق ما به بررسي يکي از روش‌هاي بهينه‌سازي حل مسئله به نامSimulated Annealing مي‌پردازيم. SA در واقع الهام گرفته شده از فرآيند ذوب و دوباره سرد کردن مواد و به همين دليل به شبيه‌سازي حرارتي شهرت يافته است. در اين تحقيق ادعا نشده اس

کندو ( Hive ) : هر شانه ( Comb )در يک کندو ، عبارت از يک ورقه عمودي مومي است که به قسمت بالا و کناره‌هاي يک حفره بطور محکم چسبيده است . حجره‌هاي کارگر ( Worker cells ) که در آنها کارگران پرورش مي‌يابند و عسل يا گرده در آنها ذخيره مي‌شود ، عرض اي

ثبت سفارش
تعداد
عنوان محصول