صفحه 2 از 2 نخستنخست 12
نمايش نتايج 11 تا 16 از 16

تاپیک: آموزش الگوریتم مورچگان از صفر تا صد

  1. #11
    عضو آواتار MrMining
    رشته
    مهندسی کامپیوتر
    تاريخ عضويت
    2016/10
    امتیاز
    44
    پست ها
    38

    پيش فرض

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

    توی چند مطلب آینده قصد داریم یکی از مهمترین چالش های مربوط به الگوریتم کلونی مورچه ها در حل مسئله کوتاهترین مسیر در گراف رو بیان کنیم.مسئله کوتاهترین مسیر در گراف : فرض کنید ما یک گراف داریم که شامل چندین گره است و مسیرهای نیز بین این گره ها وجود دارد که آنها را یال می نامیم. هر یال در واقع فاصله بین دوتا گره است. در این گراف دو گره خاص وجود دارد ، گره مبدا (source ) و گره مقصد (destination). هدف مسئله این است که مسیری را از گره مبدا به گره مقصد پیدا کنیم که کمترین مسافت را داشته باشد. مسافت برابر است با مجموع طول یال های که از گره مبدا تا گره مقصد طی می کنیم. دقت داشته باشید ممکن است بین بعضی از گره ها در گراف مسیر (یالی) وجود نداشته باشدفرض کنید ما گراف زیر رو داریمتوی گراف بالا گره مبدا، گره مقصد و کوتاه ترین مسیر از مبدا به مقصد مشخص شده استاگر ما بخواهیم مسئله کوتاهترین مسیر در گراف رو با الگوریتم کلونی مورچگان حل کنیم، گره مبدا معادل لانه مورچه ها هستش و گره مقصد معادل غذا هستش. مورچه ها باید سعی کنن از بین مسیرهای زیادی که بین لانه تا غذا است کوتاهترین مسیر رو پیدا کنن.مهمترین تفاوت این مسئله با مثال های که قبلا بیان کردیم این بوده که توی اونا ما دو تا مسیر کاملا مجزا از هم داشتیم و این مسیر ها غیر از دو نقطه یعنی منبع و مقصد هیچ نقطه مشترکی با هم نداشتن. به عبارت دیگر مسیرها کاملا از هم مجزا بودند.همین تفاوت باعث میشه که یک سری چالش برای مورچه های که قصد دارن این مسئله رو حل کنن به وجود بیاد. مهمترین این چالش ها ایجاد حلقه است. یعنی ممکن است مورچه ها توی یک حلقه بیفتن ودور خودشون بچرخن.توی این مطلب خواستیم نگاشتی بین آزمایش های مرتبط با الگوریتم کلونی مورچه ها که قبلا بیان کردیم (آزمایش 1 ، آزمایش2، آزمایش 3) و مسئله کوتاهترین مسیر در گراف ، ایجاد کنیم و نیز یک چالش مهم در حل مسئه که گیر افتادن توی حلقه است رو یک اشاره بهش کنیم. به نظر شما این مسئله چطوری باید حل بشه؟

    منبع (اطلاعات بیشتر)
    [مشاهده ی لینک ها فقط برای اعضا امکان پذیر است. ]

  2. تشكر از اين پست


  3. #12
    عضو آواتار MrMining
    رشته
    مهندسی کامپیوتر
    تاريخ عضويت
    2016/10
    امتیاز
    44
    پست ها
    38

    پيش فرض

    ما در [مشاهده ی لینک ها فقط برای اعضا امکان پذیر است. ]مسئله ایجاد حلقه در پیدا کردن کوتاهترین مسیر در گراف با کمک الگوریتم کونی مورچه ها بررسی کردیم و راه حلی که پیشنهاد دادیم اضافه کردن یک قابلیت به مورچه ها بود. این قابلیت داشتن حافظه محدود در مورچه ها است. (ما این مورچه ها را مورچه های مصنوعی نام گذاری کردیم، این مورچه ها مهمترین ویژگی های مورچه های واقعی رو دارن بعلاوه یک سری قابلیت اضافه که باعث بهبود الگوریتم كلوني مورچه ها میشه)
    پیش از ادامه مطلب در صورتن نیاز مطلب که در مورد [مشاهده ی لینک ها فقط برای اعضا امکان پذیر است. ]را قبلا مطرح کردیم یک بار مرورو کنید تا ابهامی به وجود نیاید.
    خوب بریم سراغ سوال اصلی: چطوری اضافه کردن حافظه محدود، مسئله حلقه در کوتاهترین مسیر در گراف رو حل میکنه؟مورچه های مصنوعی از این حافظه برای نگهداری دو نوع اطلاعات استفاده میکنند
    • نگهداری مسیری که تا حالا آمده اند: از آنجایی که این حافظه محدود است ممکن است مورچه ها نتواند همه مسیر را در حافظه خود نگهداری در نتیجه مورچه های مصنوعی در هر لحظه بخشی از مسیری (نه لزوما همه مسیر) که تا کنون آمده اند را در حافظه خود ذخیره دارند.
    • نگهداری هزینه مسیر که تا حالا آمده اند: یک اطلاع دیگری که مورچه ها در حافظه نگهداری می کنند، هزینه ای مسیرهای است که تا کنون از آنها عبور کرده اند. مانند مسیر، این اطلاعات نیز ممکن است شامل هزینه تمام مسیر طی شده نباشد و ممکن است تنها هزینه های بخشی از مسیر را نگهداری کند.

    با توچه به این اطلاعات مورچه ها حلقه ها را شناسایی میکنند و با استفاده از حافظه ای که دارند مسیرهای که باعث ایجاد حلقه می شوند را انتخاب نخواهد کرد. حافظه محدود در مورچه های مصنوعی، آنها مجهز به یک سری قابلیت میکند که می توانند مسئله پیدا کرده کوتاهترین مسیر در گراف را با کیفیت بهتری حل کنند. این قابلیت ها عبارت است از :
    1. حذف کردن مسیرهای که در آنها حلقه وجود دارد.
    2. ارزیابی کیفیت مسیرهای که که توسط مورچه ها برای رسیدن به غذا (مقصد) ایجاد شده است – دقت داشته باشید این ارزیابی کاملا تخمینی است، و ممکن است دقیق نباشد. نکته مهم این است که این تخمین کمک می کند تا راه حل بهتری پیدا شود.

    اضافه کردن قابلیت حافظه محدود به مورچه ها و تبخیر فرمون ([مشاهده ی لینک ها فقط برای اعضا امکان پذیر است. ]) به الگوریتم ACO ، نسخه جدیدی از الگوریتم ACO می شود که با عنوان Simple ACO یا به اختصار S-ACO شناخته می شود. در مطلب بعدی این الگوریتم را با جزییات بیشتری توضیح می دهیم.
    منبع (اطلاعات بیشتر)
    [مشاهده ی لینک ها فقط برای اعضا امکان پذیر است. ]

  4. تشكر از اين پست


  5. #13
    عضو آواتار MrMining
    رشته
    مهندسی کامپیوتر
    تاريخ عضويت
    2016/10
    امتیاز
    44
    پست ها
    38

    پيش فرض

    آموزش الگوریتم کلونی مورچه گان S-ACO – قسمت اول

    در [مشاهده ی لینک ها فقط برای اعضا امکان پذیر است. ] الگوریتم S-ACO رو به عنوان یکی از پایه ای ترین الگوریتم های ACO معرفی کردیم. الگوریتم S-ACO به عنوان یکی از الگوریتم های آموزشی برای کسانی که می خواهند با الگوریتم کلونی مورچه گان آشنا شوند، ارائه می شوند. به همین منظور در این مطلب و چند مطلب آینده اجزاء این الگوریتم را به جزییات دقیق و کامل بررسی میکنیم.الگوریتم S-ACO دارای 4 گام است که عبارتند از:
    • حرکت مورچه از سمت لانه به سمت غذا برای پیدا کردن مسیر
    • حرکت مورچه از سمت غذا به سمت لانه و به روز رسانی فرمون مسیر
    • به روز رسانی فرمون ها بر اساس میزان کیفیت مسیر
    • تبخیر فرمون

    در این مطلب، بخش اول الگوریتم که “حرکت مورچه از سمت لانه به سمت غذا برای پیدا کردن مسیر” را بررسی می کنیم.
    در الگوریتم S-ACO مورچه ها دو نوع رفتار حرکتی دارند 1- حرکت رو به جلو و 2-حرکت رو به عقب. در حرکت رو به جلو مورچه ها سعی می کنند از لانه خود تا غذا یک مسیر را پیدا کنند، در حرکت رو به عقب مورچه های سعی می کنند از غذا تا لانه خود را برگردند. هر کدوم از این رفتارهای حرکتی را “مد حرکتی” نامگذاری میکنیم. یعنی وقتی مورچه در حال حرکت از لانه به سمت غذا است می گوییم مورچه در مد حرکتی رو به جلو است و وقتی مورچه در حال بازگشت از محل غذا به لانه است می گوییم مورچه در مد حرکتی برگشت هستند.
    به عبارت دیگر وقتی یک مورچه از لانه شروع به حرکت می کند در مد حرکتی رو به جلو، است تا زمانی که به غذا برسد و بخواهد برگردد در این لحظه، مد حرکتی مورچه عوض می شود و به مد حرکتی برگشت تغییر میکند و سعی می کند تا مسیر رفته را برگردد.
    الگوریتم کلونی مورچه گان : مسیر لانه تا غذا
    گراف بالا را در نظر گیرید: وقتی مورچه در مد حرکتی رو به جلو است، به صورت احتمالی یکی از گره های گراف که از مکان فعالی (گره فعلی) قابل دسترس است را انتخاب میکند. گره قابل دسترسی، گرهی است که مسیر مستقیم به آن وجود داشته باشد (به عبارت دیگر در گراف یک یال بین آنها موجود باشد).همانطورکه بیان شد انتخاب یکی از گره های قابل دسترسی، به صورت احتمالی می باشد که بر اساس میزان فرمون موجود در مسیرها می باشد که توسط مورچه ها بر روی آنها پاشیده شده است (اطلاعات کامل در مورد این بحت را می توانید در [مشاهده ی لینک ها فقط برای اعضا امکان پذیر است. ] مطالعه کنید).تا اینجا تمام اطلاعاتی که در مورد گام اول الگوریتم S-ACo به عنوان پایه ای ترین الگوریتم کلونی مورچه گان رو بیان کردیم در مطالب بعدی سایر گام ها را بررسی میکنیم.
    یک نکته که بد نیست بدونید اینه که : در الگوریتم S-ACO وقتی مورچه ها در مد حرکتی رو به جلو هستند بر روی مسیر فرمون نمی پاشند. عدم پاشیدن فرمون در مسیر لانه تا غذا (وقتی مورچه ها در مد حرکتی روبه جلو هستند) و مکانیزم تبخیر فرمون (که در مطالب بعدی توضیح میدهیم) کمک میکند تا از ایجاد حلقه در گراف جلوگیری شود. برای کسب اطلاعات کامل در مورد [مشاهده ی لینک ها فقط برای اعضا امکان پذیر است. ] رو مطالعه کنید.


    منبع (اطلاعات بیشتر)

    [مشاهده ی لینک ها فقط برای اعضا امکان پذیر است. ]

  6. تشكر از اين پست


  7. #14
    عضو آواتار MrMining
    رشته
    مهندسی کامپیوتر
    تاريخ عضويت
    2016/10
    امتیاز
    44
    پست ها
    38

    پيش فرض

    MrMining در جشنواره وب ایران

    امسال سایت MrMining.ir در جشنواره وب ایران شرکت کرده است. در این جشنواره هر ساله از میان سایت های فعال در تمامی حوزه های وب و در گروه های مختلف یک سایت را به عنوان سایت برتر سال معرفی می شود. سایت MrMining.ir در شاخه اطلاع رسانی و محتوا و زیر شاخه کامپیوتر و فناوری اطلاعات شرکت کرده است.برندگان این جشنواره به دو دسته هستند1- سایت های منتخب از دیدگاه کاربران2-سایت های منتخب از دیدگاه دوران (که متخصصین هر حوزه را شامل می شود)در صورت مفید بودن سایت و مطالب ارائه شده در سایت می توانید، می توانید با رای دادن به سایت MrMining.ir ما در ارائه محتوای هر چه بهتر یاری کنید. مراحل رای دادن به سایت MrMining.ir نمایش داده شده است.1- ابتدا بر روی بنر مشخص شده کلیک کنید (یا بر روی این لینک [مشاهده ی لینک ها فقط برای اعضا امکان پذیر است. ] کلیک کنید تا مستقیم به صفحه رای گیری وارد شوید)2- بر روی قلب مشخص شده در تصویر کلیک کنید3- برای رای دادن می توانید از طریق اکانت گوگل و یا یاهو خود اقدام کنید4- اطلاعات اکانت خود را وارد کنید5-در صورت نیاز دکمه Allow را فشار دهید6-رای شما ثبت شد

  8. تشكر از اين پست


  9. #15
    عضو آواتار MrMining
    رشته
    مهندسی کامپیوتر
    تاريخ عضويت
    2016/10
    امتیاز
    44
    پست ها
    38

    پيش فرض

    آموزش الگوریتم کلونی مورچگان S-ACO – قسمت دوم

    در [مشاهده ی لینک ها فقط برای اعضا امکان پذیر است. ] الگوریتم S-ACO رو به عنوان یکی از پایه ای ترین الگوریتم کلونی مورچگان ACO معرفی کردیم. همین طور گام اول این الگوریتم رو بررسی کردیم در این مطلب قصد داریم گام دوم اون رو مورد بررسی قرار بدیم.
    الگوریتم S-ACO دارای 4 گام است که عبارتند از:

    • حرکت مورچه از سمت لانه به سمت غذا برای پیدا کردن مسیر
    • حرکت مورچه از سمت غذا به سمت لانه و به روز رسانی فرمون مسیر
    • به روز رسانی فرمون ها بر اساس میزان کیفیت مسیر
    • تبخیر فرمون

    در این مطلب، بخش دوم الگوریتم کلونی مورچگان S-ACO که “حرکت مورچه از سمت غذا به سمت لانه و به روز رسانی فرمون مسیر” را بررسی می کنیم.همانطور که در بیان کردیم مورچه های مصنوعی ما، دارای یک حافظه کوچک هستند که ای حافظه ها با آنها کمک میکند تا از وقتی مسیر لانه تا غذا را پیدا کنند، از بعضی از مشکلات مانند ایجاد حلقه در مسیر جلوگیری کند. حذف حلقه کمک زیادی بهبود کارایی الگوریتم میکند. (مورچه مصنوعی و تفاوت اون با مورچه ها واقعی در [مشاهده ی لینک ها فقط برای اعضا امکان پذیر است. ] بیان شده است)
    وقتی مورچه ها به غدا می رسند و آماده برگشت به خانه می شوند، به عبارت دیگر مد حرکتی برگشت هستند. با استفاده از حافظه خود مسیری که از لانه تا غذا را طی کرده اند به یاد می آوند و با کمک آن مسیر برگشت را پیدا میکنند. مورچه ها مسیری که در مد حرکتی رو به جلو، طی کرده اند را در مد حرکتی برکشت برعکس طی میکنند تا به خانه برسند.(اطلاعات کامل در مورد انواع مد حرکتی مورچه ها در [مشاهده ی لینک ها فقط برای اعضا امکان پذیر است. ] می تونید مطالعه کنید)
    مهم ترین نکته در مورد مد حرکتی برگشت آن است که مورچه در مسیر برگشت خود بر روی مسیر فرمون می پاشند. (قبلا گفتیم که مورچه های مصنوعی در مسیر لانه تا غذا فرمونی بر روی مسیر نمی پاشند).در مطلب بعدی در مورد مکانیزم پاشیدن فرمون در مسیر بیشتر توضیح میدیم (گام سوم الگوریتم کلونی مورچگان S-ACO).

    منبع (اطلاعات بیشتر)
    [مشاهده ی لینک ها فقط برای اعضا امکان پذیر است. ]

  10. تشكر از اين پست


  11. #16
    عضو آواتار MrMining
    رشته
    مهندسی کامپیوتر
    تاريخ عضويت
    2016/10
    امتیاز
    44
    پست ها
    38

    پيش فرض

    آموزش الگوریتم کلونی مورچگان S-ACO – قسمت سوم

    همانطور که در مطالب قبلی بیان کردیم ، الگوریتم SACO دارای 4 گام است که عبارتند از:
    • حرکت مورچه از سمت لانه به سمت غذا برای پیدا کردن مسیر
    • حرکت مورچه از سمت غذا به سمت لانه و به روز رسانی فرمون مسیر
    • به روز رسانی فرمون ها بر اساس میزان کیفیت مسیر
    • تبخیر فرمون
    گام اول رو در [مشاهده ی لینک ها فقط برای اعضا امکان پذیر است. ]به تفصیل بهش پرداختیم و گام دوم را نیز در [مشاهده ی لینک ها فقط برای اعضا امکان پذیر است. ] کامل توضیح دادیم
    در این مطلب، گام سوم الگوریتم SACO که “به روز رسانی فرمون ها بر اساس میزان کیفیت مسیر” را بررسی می کنیم.
    همانطورکه بیان کردیم در الگویتم SACO مورچه های مصنوعی هنگام برگشت مسیری رو که از لانه تا غذا طی کرده اند را به یاد دارند (آن را در حافظه خود ذخیره کرده اند). مورچه های مصنوعی همچنین هزینه این مسیر را نیز محاسبه کرده اند و آن را نیز ذخیره کرده اند . (هزینه هر چیزی می تونه باشه، مثلا طول مسیر طی شده از لانه تا غذا)
    با استفاده از این داده ها مورچه های مصنوعی می توانند هزینه مربوط به مسیرهای متفاوتی که تا حالا طی نموده اند و به غذا رسیده اند را با یکدیگر مقایسه کنند و کیفیت یک مسیر را نسبت به بقیه مسیرهای که تا حالا کشف کرده اند را تعیین کنند. همانطور که قبلا بیان کردیم وقتی مورچه ها تنها در مد حرکتی برگشت هستند بر روی مسیر فرمون می پاشن. میزان پاشیدین فرمون روی مسیر به کیفیت مسیر که محاسبه کردن بستکی داره. هر چه کیفیت مسیر بهتر باشه میزان فرمونی که روی مسیر می پاشن بیشتر و برعکس هر چه کیفیت پایین تر باشه، میزان فرمون کمتری روی مسیر می پاشن. (اطلاعات کامل در مورد انواع مد حرکتی مورچه ها در [مشاهده ی لینک ها فقط برای اعضا امکان پذیر است. ] می تونید مطالعه کنید)
    از آنجایی که پاشیدن فرمون بر روی مسیر وابسته به کیفیت مسیر است، باعث می شود که مورچه های مصنوعی به سمت بهترین مسیر (کوتاه ترین مسیر) از لانه تا غذا متمایل شوند. به عبارت دیگر هر چه یک مسیر کوتاهتر باشد، در نتیجه کیفیت مسیر بهتر است و مقدار بیشتری فرمون روی آن می پاشند و در به تبع آن احتمال انتخاب آن مسیر توسط سایر مورچه های مصنوعی بیشتر می شود، که این امر باعث می شود که در نهایت کوتاه ترین مسیر توسط مورچه های مصنوعی انتخاب گردد.

    منبع (اطلاعات بیشتر)
    [مشاهده ی لینک ها فقط برای اعضا امکان پذیر است. ]

  12. تشكر از اين پست


صفحه 2 از 2 نخستنخست 12

تاپیک های مشابه

  1. دانلود فیلم آموزش الگوریتم PSO
    توسط aminaghta در تالار کتابخانه تخصصی مهندسی صنایع
    پاسخ ها: 0
    آخرین ارسال: 2013/5/09, 03:29 PM
  2. اشنایی کامل با الگوریتم مورچگان
    توسط Sarp در تالار هوش مصنوعی
    پاسخ ها: 1
    آخرین ارسال: 2012/9/21, 07:27 PM
  3. روش بهینه یابی الگوریتم مورچگان
    توسط amirhakimi در تالار بایگانی تالار صنایع
    پاسخ ها: 0
    آخرین ارسال: 2008/2/28, 06:04 PM

برچسب های اين تاپیک

ثبت اين صفحه

ثبت اين صفحه

قوانين ارسال

  • شما نمی‌توانيد تاپيک جديد ارسال كنيد
  • شما نمی‌توانيد پاسخ ارسال كنيد
  • شما نمی‌توانید فایل ضمیمه ارسال كنيد
  • شما نمی‌توانيدنوشته‌های خود را ويرايش كنيد
  •