Ant colony Optimization فصل چهارم: مجموعه الگوریتم‌های سیستم مورچگان

  فصل چهارم - مجموعه الگوریتم‌های سیستم مورچگان

در این فصل مدل‌های الگوریتم سیستم مورچگان معرفی شده و نحوه مدل سازی و حل مسیله فروشنده با استفاده از سه مدل این الگوریتم ارایه خواهد شد. به دلیل پایداری مجموعه الگوریتم‌های ACO، همین الگوریتم را با تغییرات کمی می‌توان برای انواع مختلف مسایل بهینه یابی مورد استفاده قرار داد.
مسیله فروشنده رهنورد: مسیله فروشنده رهنورد با شبکه N=(N,E) بیان می‌شود که در آن N مجموعه گره‌ها یا شهرها و E مجموعه یال‌های بین گره‌ها یا مسیرهای بین شهرها هستند. مقدار   بیان گر مسافت یال بین گره‌های i و j می‌باشد. هدف یافتن کوتاه ترین دور همیلتونی شبکه N می‌باشد.
فرض کنید تعداد مورچه‌های شهر I ام در لحظه t باشد. در این صورت تعادل کل مورچه‌های گراف خواهد بود. این مورچه‌ها دارای ویژگی‌های زیر می‌باشند:
هر مورچگان شهر بعدی که می‌خواهد به آن منتقل شود را با احتمالی که تابعی از فاصله بین دو شهر و میزان فرمون موجود بر یال بین دو شهر است، انتخاب می‌کند.
برای اطمینان از این که هر مورچه از هر شهری فقط و فقط یک بار عبور می‌کند، از یک فهرست استفاده می‌شود که در این فهرست اسامی تمامی شهرهایی را که مورچه تا به حال ملاقات کرده است؛ ثبت می‌شود.
پس از طی یک دور همیلتونی هر مورچه مقداری فرمون بر روی یال‌های مسیر طی شده از خود به جا می‌گذارد.
فرض کنید   میزان فرمون یال (i,j) در لحظه t باشد. هر مورچه در لحظه t+1 با یک تکرار از شهر فعلی به شهر بعدی متنقل خواهد شد. بنابراین یک تکرار الگوریتم شامل m حرکت توسط m مورچه در بازه زمانی (t,t+1) می‌باشد و یک دور کامل همیلتونی پس از n تکرار کامل الگوریتم حاصل خواهد شد.
بعد از یک تکرار میزان فرمول یال (i,j) از رابطه زیر به دست خواهد آمد:
رابطه ی 4- 1
که در این رابطه   ضریبی است که بیان گر نرخ پیداری فرمون موجود بر روی یال‌ها در فاصله زمانی (t,t+1) می‌باشد. پس   نیز بیان گر میزان تبخیر فمرون در همان فاصله زمانی است. برای جلوگیری از تجمع بیش از حد فرمون بر روی یال‌ها و نیز ایجاد امکا جستجوی مسیرهای جدید بایستی   کوچک تر از یک باشد.
رابطه 4-2
که مقدار فرمونی است که توسط مورچه kام روی یال (i,j) در فاصله زمانی (t,t+1) ترشح می‌شود.
برای اطمینان از این که مورچه‌ها دوره‌های همیلتنی طی می‌کنند، به هر مورچه یک فهرستی که فهرست ممنوع نام دارد، نسبت داده می‌شود. به محض ورود مورچه به یک شهر اسم آن شهر وارد این فهرست شده و بدین ترتیب به مورچه اجازه داده نمی‌شود که تا پایان آن دور، آن شهر را دوباره ملاقات نماید. زمانی که یک دوره همیلتونی کامل شد، فهرست ممنوع تمامی مورچه‌ها خالی شده و مورچه‌ها می‌توانند از نو در دوره‌های بعدی حضور داشته باشند. فرض کنید Tabuk فهرست ممنوع مورچه kام و Tabuk(s) درایه s ام این فهرست (s امین شهر ملاقت شده توسط مورچه kام) باشد.
مقدار   که با   نشان داده می‌شود را پدیداری گویند. این مقدار بیان گر اطلاعات خاص مسیله بوده و یکی از دو منبع اطلاعاتی مورد استفاده مورچه‌ها برای تصمیم گیری م باشد. این مقدار برخلاف رد پای فرمونی برای ابتدای شروع حل مسیله برای یال‌ها قابل محاسبه بوده و در حین اجرای الگوریتم نیز ثابت می‌باشد. با تعریف پارامترهای فوق می‌توان احتمال انتقال مورچه‌ها بین شهرها را به صورت زیر تعریف نمود:
احتمال انتقال مورچه kام از شهر iام از رابطه زیر به دست می‌آید:
رابطه 4-3 P
در این رابطه و و پارامترهایی هستند که میزان اهمیت نسبی ردپای فرمونی را در مقابل پدیداری کنرل می‌کنند. نکته جالب توجه این که احتمال انتقال از شهری به شهر دیگر توازنی بین پدیداری و میزان ردپای فرمونی در لحظه t است که عبارت پدیداری تاکید بر انتخاب شهرهای نزدیک تر با احتمال بالاتر را داشته و بخش ابتکاری کوته بینانه‌ی الگوریتم را تشکیل می‌دهد؛ در حالی که میزان ردپای فرمونی تاکید بر انتخاب یال‌هایی با شدت ترافکی بالا تا این لحظه را دارد و بخش خود کاالیست الگوریتم را می‌سازد.
چگونگی محاسبه و زمان به روز کردن سبب به وجود آمدن مدل‌های متفاوتی از الگوریتم AS شده است که در دو بخش بعدی این نوشته سه مدل کمیت مورچگان، چگالی مورچگان و چرخه مورچگان مورد بررسی قرار می‌گیرد.

برای دریافت فایل کامل PDF مقاله روی لینک زیر کلیک کنید:
فصل چهارم - مجموعه الگوریتم‌های سیستم مورچگان