تخفیف ویژه زمستانه پی استور
تا 60 درصد تخفیف
شامل پروژه‌ها و دوره‌های آموزشی
روز
ساعت
دقیقه
ثانیه
تخفیف ویژه زمستانه پی استور
الگوریتم بهینه سازی کلونی مورچگان تحت عنوان الگوریتم‌های هوش ازدحامی (هوش گروهی) شناخته شده و به مدل سازی رفتار مورچه‌های واقعی می‌پردازد. مورچه‌ها حشراتی هستند که می‌توانند گروه‌ها (کلونی‌ها) را شکل دهند. چنین رویکرد جمعیت محوری این امکان را برای الگوریتم ACO ایجاد می‌کند تا به حل مسائل بهینه سازی پویا به طور کاملا کارآمد بپردازد. مورچه‌ها به عنوان مخلوقات خودسازمانده می‌باشند. چنین ویژگی به عنوان هسته مسئله می‌باشد زیرا این ویژگی دقیقا همان چیزی است که باعث می‌شود حشرات به سرعت با شرایط متغیر محیطی شان به منظور دستیابی به اهداف از طریق تعامل سطح پایین، وفق یابند.
از آن‌جایی که مورچه‌ها اصلا چشم ندارند، تعاملات آن‌ها از طریق ماده شیمیایی فرومون Pheromone که از آن برای نشان گذاری مسیر استفاده می‌شود، اانجام می‌گیرد. هرچه فرومن‌های بیشتری در مسیر قرار گیرد؛ مابقی مورچه‌ها از این مسیر بیشتر استفاده می‌کنند؛ بنابراین، چنین کمیتی نشان می‌دهد که این مسیر به عنوان یکی از بهینه‌ترین و کوتاه‌ترین راه می‌باشد. اکنون نگاهی به یک نمونه عینی در شکل زیر می‌اندازیم. هدف پیدا کردن بهترین راه از نقطه آغازی N (آشیانه) به نقطه مقصد F (منبع غذا) می‌باشد.
ممکن است این حدس زده شود که احتمال برای مورچه‌ای که مسیر درست را می‌پیماید برابر با همان احتمالی می‌باشد که مسیر اشتباه را انتخاب کند. نکته در اینجا اینست که مورچه‌ای که کوتاه‌ترین مسیر را می‌پیماید، اولین مورچه‌ای است که به نقطه مقصد رسیده و سپس به آشیانه ( نقطه مبدا حرکت) بر می‌گردد، بنابراین در این کوتاه‌ترین مسیر فرمون‌های بیشتری وجود دارد. از این رو فرمون دقیقا همان چیزی است که نشان می‌دهد که مورچه باید از چه مسیری برود و در پایان کوتاه‌ترین راه، بهترین مسیر می‌باشد. تبخیر شدن فرومون و احتمال تصادف به مورچه‌ها امکان پیدا کردن کوتاه‌ترین مسیر را می‌دهد. این دو ویژگی باعث ایجاد انعطاف در حل هرگونه مسئله بهینه‌سازی می‌شوند.
مراحل الگوریتم کلونی مورچگان بصورت زیر است.
۱- ارزش دهی مورچه‌ها (مقداردهی اولیه)
در این مورد، می‌توانیم از دو رویکرد متفاوت استفاده کنیم: قرار دادن تمام مورچه‌ها در یک نقطه یا در نقطه‌های مختلف. اینکه از چه روشی می‌بایست استفاده شود بستگی به موقعیت خاص آن دارد. در این مرحله، این مقدار دهی اولیه به فرمون‌ها نیز انجام می‌شود. ارزش فرمون باید یک عدد صحیح کوچک باشد. این کار را باید به این منظور انجام داد تا از ماندن و حرکت نکردن مورچه‌ها در نقطه آغازی جلوگیری کرد.
چون الگوریتم ACO تلاش می‌کند تا به تقلید رفتار مورچه‌های واقعی با استفاده از فرآیند شبیه سازی بپردازد، از یک تابع احتمال برای توصیف مسیر استفاده می‌گردد. احتمال دسترسی به نقطه j از نقطه i (احتمال انتقال) بر طبق به فرمول زیر محاسبه می‌شود.
که در این فرمول τ_ij مقدار ماده شیمیایی فرومن در نقاط (i,j) می‌باشد. که حس مورچه نیز نامیده می‌شود. η_ij نسبت دید نقاط (i, j) است که چشم مورچه نامیده می‌شود و هیورستیک مسئله می‌باشد و بصورت η_ij=1⁄d_ij تعریف می‌شود که d_ij فاصله بین دو گره i و j است. α و β نیز پارامترهای سازگار، به معرفی اهمیت مسیر در برابر نسبت دید در زمان انتخاب نقطه بعدی برای حرکت می‌پردازد. tabuK فهرست گره‌های بازدید شده در مسیر کنونی که اصطلاحاً حافظه مورچه نامیده می‌شوند.
اگر α=۰ باشد، الگوریتم حریصانه شده، به صورتی که انتخاب گره بعدی، کمیت فرومون‌ها را مد نظر قرار نداده به این ترتیب انتخاب نزدیک‌ترین مسیر اولویت پیدا می‌کند. اگر β=۰ باشد الگوریتم تنها مقدار فرمون‌ها را بدون در نظر گرفتن طول مسیر، مد نظر قرار می‌دهد.
بروز رسانی فررمون‌ها
بعد از اینکه مورچه‌ها دنبال کردن مسیر را به پایان رساندند، کمیت و مقدار فرمون‌ها می‌بایست تغییر یابد. این فرآیند دو مرحله دارد. ابتدا، نیاز داریم تا مقدار تمام فرمون‌ها را کاهش داده. دوم، نیاز به بروزرسانی فرمون‌های متصل به نقاط بازدید شده از طریق افزایش مقدار و کمیت آن داریم. تبخیر مسیر به صورت فرمول زیر تعریف می‌گردد:
که در این فرمول ρ ضریب تبخیر فرمون می‌باشد. پارامتر ρ کمک می‌کند تا از انباشت نامحدود مسیر خلاص شویم. بنابراین این فرآیند مانع می‌شود تا مورچه‌ها مسیرهای بدی را که قبلا کشف کردند فراموش کنند. اگر نقطه‌ای که توسط مورچه‌ها بدون استفاده ماند، سپس سطح فرومن بعد از هر تکرار به طور تعریفی (نمایی) کاهش می‌یابد. به منظور مد نظر قرار دادن تبخیر، نیاز به بروزرسانی مقدار فرمون‌های مورچه‌ها داریم. بنابراین حجم (فزونی) مسیر توسط فرمول زیر بروزرسانی می‌گردد.
که در این فرمول τ_ij^k∆ کمیت فرومون‌های قرار داده شده بر روی نقاط پیموده شده (i, j) توسط مورچه k ام می‌باشد. و با استفاده از رابطه زیر قابل محاسبه است.
که در این فرمول Q مقدار ثابت، که به طور ساختگی فرمون‌ها را اضافه می‌کند و L طول کلی مسیر می‌باشد هر چه مسیر بهتر باشد، فرومون‌های بیشتری در این مسیر قرار می‌گیرد. در کل، نقاطی که توسط بسیاری از مورچه‌ها مورد استفاده قرار می‌گیرد و بخشی از مسیرهای کوتاه را شامل می‌گردد، فرومن‌های بیشتری را دریافت کرده و به این ترتیب به احتمال بیشتری توسط مورچه‌ها در تکرار آینده این مسیر الگوریتم انتخاب می‌گردد. فرآیند تکرار زمانی متوقف می‌شود که حداقل یکی از نیازها برآورده گردد.
در ادامه تعدادی از انواع الگوریتم کلونی مورچگان را معرفی می‌کنیم
۱- سیستم کلونی مورچه Ant System
که در بالا توضیحات کافی داده شده‌است.
۲- سیستم مورچه نخبگان Elitist Ant System
در این روش بهترین راه حل کلی در هر تکرار فرمون آزاد می‌کند. همچنین این روش برای تمام مورچه‌های مصنوعی باید انجام شود.
۳- سیستم مورچه ماکس – مین Min-Max Ant System
یک مقدار کمینه و بیشینه برای فرمون تعیین کرده و فقط در هر مرحله بهترین جواب این مقدار را آزاد می‌کند و تمام گره‌های مجاوران به مقدار فرمون بیشینه مقدار دهی اولیه می‌شوند.
۴- سیستم مورچه بر اساس رتبه Ranked Ant System
تمام راه حل‌های بدست آماده بر اساس طول جواب رتبه‌بندی می‌شوند و بر اساس همین رتبه‌بندی مقدار فرمون آزاد سازی شده توسط آن‌ها مشخص خواهد شد و راه حل با طول کمتر از راه حل دیگر با طول بیشتر مقدار فرمون بیشتری آزاد می‌کند.
۵- سیستم مورچه متعامد مداوم Best-Worst Ant System
در این روش مکانیزم تولید فرمون به مورچه اجازه می‌دهد تا برای رسیدن به جواب بهتر و مشترک با بقیه مورچه‌ها جستجو انجام دهد با استفاده از روش طراحی متعامد مورچه می‌تواند در دامنه تعریف شده خود به صورت مداوم برای بدست آوردن بهترین جواب جستجو کند که این عمل به هدف رسیدن به جواب بهینه و صحیح ما را نزدیک می‌کند. روش طراحی متعامد می‌تواند به دیگر روش‌های جستجو دیگر گسترش پیدا کنند تا به مزیت‌های این روش‌های جستجو اضافه کند.
3 پاسخ
مختصر و مفید
ممنون