مقالات ترجمه شده دانشگاهی ایران

مسیریابی کانال بر مبنای مدل رفتار تطبیقی کلونی مورچه ها

مسیریابی کانال بر مبنای مدل رفتار تطبیقی کلونی مورچه ها

مسیریابی کانال بر مبنای مدل رفتار تطبیقی کلونی مورچه ها – ایران ترجمه – Irantarjomeh

 

مقالات ترجمه شده آماده گروه کامپیوتر
مقالات ترجمه شده آماده کل گروه های دانشگاهی

مقالات رایگان

مطالعه 20 الی 100% رایگان مقالات ترجمه شده

1- قابلیت مطالعه رایگان 20 الی 100 درصدی مقالات 2- قابلیت سفارش فایل های این ترجمه با قیمتی مناسب مشتمل بر 3 فایل: pdf انگیسی و فارسی مقاله همراه با msword فارسی -- تذکر: برای استفاده گسترده تر کاربران گرامی از مقالات آماده ترجمه شده، قیمت خرید این مقالات بسیار کمتر از قیمت سفارش ترجمه می باشد.  

چگونگی سفارش

الف – پرداخت وجه بحساب وب سایت ایران ترجمه (شماره حساب) ب- اطلاع جزئیات به ایمیل irantarjomeh@gmail.com شامل: مبلغ پرداختی – شماره فیش / ارجاع و تاریخ پرداخت – مقاله مورد نظر -- مقالات آماده سفارش داده شده عرفا در زمان اندک یا حداکثر ظرف مدت چند ساعت به ایمیل شما ارسال خواهند شد. در صورت نیاز فوری از طریق اس ام اس اطلاع دهید.

قیمت

قیمت این مقاله: 32000 تومان (ایران ترجمه - Irantarjomeh)

توضیح

بخش زیادی از این مقاله بصورت رایگان ذیلا قابل مطالعه می باشد.

مقالات ترجمه شده کامپیوتر - ایران ترجمه - irantarjomeh

www.irantarjomeh.com

مسیریابی کانال بر مبنای مدل رفتار تطبیقی کلونی مورچه ها

شماره       
192
کد مقاله
COM192
مترجم
گروه مترجمین ایران ترجمه – irantarjomeh
نام فارسی
مسیریابی کانال بر مبنای مدل رفتار تطبیقی کلونی مورچه ها
نام انگلیسی
Channel Routing Based on Ant Colony Adaptive Behavior Model
تعداد صفحه به فارسی
57
تعداد صفحه به انگلیسی
16
کلمات کلیدی به فارسی
مسیریابی, رفتار تطبیقی, کلونی مورچه ها
کلمات کلیدی به انگلیسی
Channel Routing,  Ant Colony, Adaptive Behavior Model
مرجع به فارسی
هوش مصنوعی
دانشگاه سادرن فدرال، روستو، روسیه
ژورنال کامپیوتر و علوم سیستم ها
مرجع به انگلیسی
Journal of Computer and Systems Sciences International; Southern Federal University, Rostov on Don, Russia
سال
2015
کشور
روسیه

مسیریابی کانال بر مبنای مدل رفتار تطبیقی کلونی مورچه ها

 

مسیریابی کانال بر مبنای مدل رفتار تطبیقی کلونی مورچه ها
چکیده
بر مبنای تحلیل تطبیقی رویکردها و روش های موجود برای حل مسایلی نظیر مسیریابی، تکمیل فرآیند مسیریابی و مسیریابی مجدد اتصالات در VLSI، روش های بهینه سازی هوش چند عامله مورد استفاده قرار گرفته اند. آنها بر مبنای شبیه سازی رفتار تطبیقی کلونی مورچه ها می باشند. مسئله مورد بررسی در این مقاله بر مبنای مجموعه ای از مؤلفه های مرتبط با الگوریتم کلونی مورچه ها است. در این راستا یکسری از ویژگی های اکتشافی حاصل شده اند که بر مبنای مولفه های حاکم بر رفتار مورچه ها، با توجه به حرکت آنها در نمودار جستجو، می باشند. یک ویژگی متمایز الگوریتم پیشنهادی قابلیت آن جهت به حساب آوردن برخی از ویژگی های خاص، نظیر توزیع منابع، تأثیرات بازدارندگی (بلوکه شدگی) ، تعداد گذارهای بین لایه ها، تعداد انحراف ها و موارد دیگر،  می باشد، که با توجه به این موضوع به حساب آوردن کلیه این ویژگی ها به هنگام محاسبه چگونگی انتشار موج بسیار مشکل می باشد. الگوریتم مسیریابی مرتبط آزمایش شده و با دیگر الگوریتم های شناخته شده با توجه به ارائه برخی از معیارها و ویژگی های محک سنجی خاص مورد بررسی قرار می گیرد. در مقایسه با الگوریتم های موجود، کیفیت راه حل ها تا میزان 3% ارتقاء یافته است. یکی از مسیرهای قابل توجه در این مبحث ارتقای الگوریتم کاربرد دامنه مسیریابی بصورت گسترده می باشد که صرفاً سبب افزایش اندکی در طول مسیر خواهد شد اما در عین حال موجب به حداقل رسانی موانع و مشکلات موجود می گردد. کارایی چنین الگوریتمی را می توان با استفاده از فرآیند کنترل تطبیقی پارامترهای الگوریتم ارتقا داد.

مسیریابی کانال بر مبنای مدل رفتار تطبیقی کلونی مورچه ها

 

مقدمه
بخش مهم توسعه سیستم های هوشمند طراحی به وسیله کامپیوتر (CADs) که در ارتباط با VLSI می باشد خصیصه مسیریابی اتصالات است. به واسطه کاهش یکنواخت اندازه هندسی المان ها و در نتیجه افزایش تعداد اجزای مرتبط بر روی یک تراشه، مسئله مسیریابی پیچیدگی بیشتر و بیشتری می یابد. گذار به سمت فناوری های نانومتری تولید مدار انتگرال خود سبب ایجاد محدودیت های جدیدی در خصوص چنین معضلی می شود [1، 2]. تاکنون، اکثریت روش های مسیریابی موجود از یک رویکرد دو فازه متشکل از مسیریابی متمرکز و مسیریابی تفصیلی [1، 4] استفاده نموده اند. مسیریابی کلی قابلیت تقسیم دامنه یا حوزه ارتباطاتی به زیرحوزه های مسیریابی (سلول ها) را داشته و بر این مبنا اتصالات بین آنها مسیر یابی می شود.
انواع کاملاً شناخته شده مسیریابی تفصیلی شامل مسیریابی کانال [4 ـ 6] ، مسیریابی سوئیچ ـ جعبه [7، 8] و مسیریابی آنچه تحت عنوان تراشه ـ کامل خوانده شده می باشد. مسیریابی تراشه ـ کامل به عنوان یکی از قابل توجه ترین موارد از نقطه نظر توسعه الگوریتم های جدید به حساب می آید [9 ـ 12] .
شاخص عملکرد اصلی که می بایست قابلیت بهینه سازی آن وجود داشته باشد را می توان ویژگی های مربوط به مسیریابی (بخشی از اتصالات مسیر داده شده بر مبنای تعداد کل اتصالات و با توجه به ویژگی های مبنایی درصدی) دانست. به طور ایده آل، چنین موردی را می بایست در یک حالت صد در صدی مد نظر قرار داد [13، 14]. هیچ کدام از رویکردهای موجود جهت مسیریابی فناوری های تولیدی VLSI مدرن (علی الخصوص، برای فناوری 35 نانومتری)، قابلیت تضمین مسیریابی 100% را ارائه نمی نمایند. در چنین موردی، راهکار محتمل بکارگیری یک رویه مسیریابی دو فازه می باشد. در اولین فاز، مسیریابی تحت محدودیت های مشخص و با توجه به شکل اتصالات انجام می گردد. به طور مثال، در این زمینه می توان به مسیریابی کانال یا مسیریابی سوئیچ ـ جعبه اشاره داشت. در مورد مسیریابی تراشه کامل، الگوهای اتصال مورد استفاده قرار می گیرند. مسیریابی با استفاده از الگوهای دارای شکل ساده (شکل ـ L و شکل ـ Z) انجام می شود. الگوریتم ها (غالباً از نوع ترکیبی) در فاز اول بکار گرفته شده که سبب خواهند شد تا قابلیت مسیریابی اکثریت (و نه همگی) اتصالات به وجود آید. با این وجود، به واسطه محدودیت ها در زمینه شکل اتصال، برخی از اتصالات ممکن است از نقطه نظر عملی یا حتی به طور کامل بدون مسیر باقی بمانند، با وجود آنکه منابع مشخصی برای کلیه آنها وجود دارد. این اتصالات در فاز دوم با استفاده از الگوریتم های تکمیل مسیریابی موجی مسیردهی خواهند شد. یک ویژگی متمایز الگوریتم های موجی آن است که آنها قابلیت یافتن یک مسیر در صورت وجود آن را خواهند داشت [1، 2].
تکمیل مسیریابی در حقیقت یک مشکل مهم به شمار می آید که در این رابطه هیچ یک از راهکارهای متعارف قابلیت تضمین حاصل آوردن نتایج بهینه را نخواهند داشت [1]. بنابراین، ایجاد الگوریتم های جدید برای این مسئله مهم خواهد بود. در حال حاضر، جهت گیری تحقیقاتی تحت عنوان محاسبه طبیعی در حال رشد و گسترش قابل توجه و گسترده ای می باشد. این جهت گیری از روش های ریاضیاتی بر مبنای اصول تصمیم گیری مبتنی بر الهام از طبیعت بهره می جوید. چنین موردی شامل فرآیندهای آنیلینگ شبیه سازی شده و روش های شبیه سازی تکاملی، الگوریتم های ژنتیک (GAs)، روش های تطبیقی تکاملی، الگوریتم های هوشمند ازدحام، الگوریتم بهینه سازی کلونی مورچه (ACO)، و الگوریتم های بهینه سازی کلونی زنبور عسل (BCO) می باشند [12 ـ 20]. در عین حال تلاش هایی [1، 15، 21 ـ 23] جهت بکارگیری شبیه سازی تکاملی برای مسیریابی کانال نیز توأم با موفقیت حاصل شده است. با این حال، ساختارهای GA پیشنهادی به صورت ساختارهای جستجوی “کور” می باشند و از نقص های ذاتی همانند ارائه راه حل های نامحتمل برخوردار هستند، که خود نیازمند تایید بیشتر و ایجاد تعداد زیادتری از راه حل های مشابه و همچنین تولید تعداد زیادی از راه حل های “بد” است.
افزایش شدید در پیچیدگی کاربردی VLSI سبب توسعه روش های کارآمد جدید و ابزارهای مرتبط برای طراحی شده است. در این مقاله، ما نسبت به ارائه فناوری ها، اصول و روش های راه حل مناسب برای مسیریابی کانال، تکمیل مسیریابی، و مسیریابی مجدد بر مبنای شبیه سازی رفتار تطبیقی کلونی مورچه ها اقدام خواهیم نمود [24 ـ 27] . رویکرد پیشنهادی را می توان برای مسیریابی بدون گرید اتصالات با پهنای مختلف بکار گرفت. در مقایسه با الگوریتم های موجود، نتایج حاصله بنظر ارتقاء یافته می باشند.

مسیریابی کانال بر مبنای مدل رفتار تطبیقی کلونی مورچه ها

 

1- طرح مسئله مسیریابی کانال
یک کانال در حقیقت به عنوان ناحیه ای تلقی می شود که به وسیله دو خط ترمینال به یکدیگر متصل شده اند [1]. خط پایینی / تحتانی ترمینال ها بر حسب  و خط بالایی / فوقانی بر مبنای  مشخص می شوند. مجموعه مدارات  تا خط انتهای ترمینال ها گسترش یافته و مجموعه مدارات  نیز تا خط فوقانی ترمینال ها، ، گسترش می یابند. ناحیه مسیریابی با گرید متعامد مرجع مشخص گردیده و مسیرها بر روی خطوط این گرید طراحی می گردند. خطوط افقی تحت عنوان تراک ها خوانده می شوند. خطوط عمودی نیز در امتداد ترمینال ها حرکت می نمایند (شکل 1).
در مسیریابی کانال، هر مدار قابلیت اتصال ترمینال های هم ظرفیت را داشته که به وسیله مجموعه ای از قسمت ها (بخش ها) افقی و عمودی مشخص می گردند. بخش های افقی بر روی تراک ها قرار می گیرند. پیکربندی بخش های عمودی که قابلیت اتصال بخش های افقی با خط تحتانی و فوقانی ترمینال ها را دارند به طور کامل از طریق جابجایی بخش های افقی مشخص می گردند. بخش افقی نیز به عنوان یک قسمت افقی متصل به وسیله بخش های عمودی با ترمینال های منطبق همان مدار مدنظر می باشد. رویکردهای مختلفی در زمینه ایجاد بخش های افقی وجود دارند. در یک حالت ساده، یک مدار تنها دارای یک بخش افقی با قسمت های عمودی متلاقی می باشد. یک مسیر حاوی صرفاً یک بخش افقی تحت عنوان مورد بدون انحنا یا کجی خوانده می شود. در عمل، ممکن است انحراف هایی در مناطقی وجود داشته باشند که در آن بخش های عمودی و افقی در تماس با یکدیگر هستند، یعنی بخش های افقی بین جفتی از تماس های مجاور همان مدار پدیدار می شوند. در حالت کلی، مسئله مسیریابی کانال به عنوان مسئله جایگزینی به شمار می آیند که در معرض محدودیت هایی در ارتباط با مجموعه های بخش های افقی  و مجموعه های تراک های  می باشد [1]. چنین قیدها یا محدودیت هایی از هم پوشانی بخش های عمودی و افقی مدارات مختلف جلوگیری می نمایند. به منظور به حساب آوردن چنین قیدها یا محدودیت هایی، یک گراف محدودیت عمودی  و یک گراف محدودیت افقی بدون جهت  بکار گرفته شده است. در اینجا، V به عنوان مجموعه ای از رأس های منطبق با بخش های افقی به شمار می آید (شکل 2). یک یال جهت دار (قوسی)  صرفاً در صورتی وجود خواهد داشت که بخش vi را می بایست در بالای بخش vj قرار داد…

مسیریابی کانال بر مبنای مدل رفتار تطبیقی کلونی مورچه ها

 

2- الگوی کلونی مورچه ها
ایده بنیادی در ارتباط با بهینه سازی کلونی مورچه ها (ACO) تقلید رفتار مورچه ها می باشد که به سرعت قابلیت یافتن کوتاه ترین مسیر از لانه خود به یک منبع غذایی را دارند. رفتار کلونی مورچه بر مبنای یک ویژگی خودسازماندهی شده می باشد که این تضمین را به وجود می آورد که اهداف کلی کلونی بر مبنای تعاملات سطح پایین حاصل می گردد و بر مبنای چنین رفتاری، کلونی مربوطه به عنوان یک هویت کلی در حقیقت نقش یک سیستم چند عامله هوشمند را بازی می نماید. ویژگی این الگو کاربرد تعاملات غیرمستقیم بین حشرات می باشد (که تحت عنوان استیگمرجی یا نشانه ورزی خوانده می شود). این نوع از کنش در الگوریتم های ACO بکار گرفته می شود [24، 25]. فرآیند نشانه ورزی در حقیقت به عنوان یک تعامل یا کنش توزیع شده در خلال زمان به شمار می آید. در مورد چنین تعاملی، یک فرد اقدام به بررسی و شناخت یک ناحیه از محیط پیرامونی نموده و افراد دیگر از این اطلاعات به هنگام حضور در چنین ناحیه ای استفاده می نمایند. تعامل پیشنهادی از یک ماده شیمیایی خاص تحت عنوان فرومون استفاده می نماید. غلظت فرومون در یک مسیر مشخص کننده ترجیح چنین مسیری می باشد. به هنگامی که یک مورچه در امتداد یک مسیر حرکت می نماید، قابلیت علامت گذاری آن به وسیله فرومون را خواهد داشت و چنین اطلاعاتی به وسیله مورچه های دیگر جهت انتخاب یک مسیر بکار گرفته می شود. غلظت یا تراکم فرومون مشخص کننده تمایل یک مورچه جهت انتخاب یک مسیر یا مسیر دیگر می باشد. با این وجود، چنین الگوریتمی ناچاراً در آپتیمای محلی گیر خواهد افتاد. این مسئله را می توان با استفاده از تبخیر فرومون حل نمود که نقش بازخورد منفی را ایفا می نماید.
ایده اصلی الگوریتم های ACO را در نظر بگیرید [27]. مورچه های یک کلونی حرکت خود از آشیانه به سمت غذا به صورت ترتیبی و به دنبال یکدیگر را شروع می نمایند. پس از دسترسی به غذا، مورچه ها به آشیانه بر می گردند. در اینجا دو مسیر جایگزین Lr و Ll (شکل 3).  اولین مسیر Lr کوتاهتر می باشد ـ این مسیر از نقاط A، 1، 2 و B عبور می نماید. مسیر دوم Ll طولانی تر است ـ این مسیر از نقاط A، 3، 4 و B عبور می نماید. نقاط 3، A، و 1 به صورت منطبق می باشند. با این وجود، نقطه 1 صرفاً متعلق به مسیر Lr می باشد و نقطه 3 متعلق به مسیر Ll است. نقاط 4، B و 2 نیز به صورت منطبق با یکدیگر هستند. با این وجود، نقطه 2 متعلق صرفاً به مسیر Lr تلقی شده و نقطه 2 متعلق به صرفاً مسیر Ll می باشد. نقاط 1 و 2 در حقیقت به عنوان نقاط انتهایی Lr به شمار آمده و نقاط 3 و 4 نیز به عنوان نقاط انتهایی Ll محسوب می شوند. نقطه A به عنوان نقطه انتهایی بخش متصل به آشیانه بلوک (block Nest) می باشد، در حالی که نقطه B به عنوان نقطه  انتهایی بخش متصل به بلوک غذا (block Food) است. به طور اولیه، شاهد مقدار یکسانی از فرومون در نقاط 1 ـ 4 هستیم. به هنگامی که یک مورچه در امتداد نقاط 1 ـ 4 حرکت می نماید، اقدام به ترشح فرومون در آن ناحیه خواهد نمود. بنابراین به هنگامی که مورچه ها در امتداد نقاط 1 ـ4 عبور می نمایند، مقدار فرومون در آنها افزایش می یابد. پس از یک زمان t1، مورچه به نقطه A می رسد. احتمال آنکه یک مورچه اقدام به انتخاب نقطه 1 یا 3 نماید در تناسب با مقدار فرومون های رسوب شده در این نقاط می باشد. از آنجایی که مقدار فرومون ها در نقاط 1 و 3 در ابتدا یکسان است، جریان مورچه ها به دو بخش نسبتاً مساوی تقسیم می گردد و مقدار فرومون رسوب شده در این نقاط نیز تقریباً یکسان خواهد بود. پس از زمان t2، مورچه ها به نقطه 2 رسیده و پس از گذشت زمان t3 آنها به نقطه 4 می رسند. هر چه که تفاوت بین t3 و t2 بیشتر باشد، تفاوت بین مقدار فرومون انباشته شده در نقاط 2 و 4 نیز بیشتر خواهد بود.

مسیریابی کانال بر مبنای مدل رفتار تطبیقی کلونی مورچه ها

 

3- مسیریابی کانال بر مبنای الگوی کلونی مورچه ها
راه حل های این مسئله بر مبنای گراف کامل راه حل های R(F, E) جستجو می شوند، که در آن مجموعه رأس های F مترادف با مجموعه بخش ها می باشد و E به عنوان مجموعه ای از یال های گراف کامل به شمار می آید [18]. راه حل مسئله مسیریابی کانال به وسیله مسیر Sk ارائه شده است که خود شامل کلیه رأس های گراف راه حل R(F, E) می باشد. تبالی رأس ها در مسیر Sk مشخص کننده آرایش المان های متناظر در لیست Fk می باشد. شکل 4 نشان دهنده این مسیر در گراف مربوطه معادل جابجایی بخش ها در تراک های نشان داده شده در شکل 1 می باشد. وظیفه هر مورچه ak ایجاد یک مسیر Sk در گراف R می باشد که خود به عنوان راه حل مسئله مسیریابی کانال به شمار آمده و در آن k به عنوان شاخص (عامل) مورچه محسوب می شود. جایگزینی المان های لیست Fk در تراک ها و محاسبه شاخص عملکرد مسیر ـ تعداد تراک ها ـ بر مبنای راهکار اصلی اعمال می شود. وظیفه کلونی مورچه یافتن در گراف R(F, E)، مسیر متناظر با جایگزینی بخش ها در تعداد حداقلی تراک ها می باشد.
از آنجایی که کانال به صورت متقارن است (به شکل 1 رجوع شود)، شمارش تراک ها (TE) و پر کردن آنها با بخش های مختلف (FF) را می توان در چهار روش ارائه شده ذیل انجام داد:
  • TE از بخش فوقانی به تحتانی، FF از چپ به راست،
  • TE از بخش فوقانی به تحتانی، FF از راست به چپ،
  • TE از بخش تحتانی به فوقانی، FF از چپ به راست،
  • TE از بخش تحتانی به فوقانی، FF از راست به چپ.
در شکل 1، اولین روش بکار گرفته شده است.
به منظور ارتقای کارایی، راه حل بر مبنای چهار گروه مورچه ها Z1–Z4 با استفاده از چهار روش مختلف دنبال می شود.

مسیریابی کانال بر مبنای مدل رفتار تطبیقی کلونی مورچه ها

 

4- تکمیل مسیریابی و الگوریتم های باز مسیریابی
به واسطه محدودیت ها از نظر شکل اتصالات مسیر داده شده در الگوریتم های مسیریابی کانال، برخی از اتصالات بدون مسیریابی باقی می مانند. برای این اتصالات، الگوریتم های مسیریابی تکمیل موج در فاز دوم مورد استفاده قرار می گیرند. یک ویژگی متمایز این الگوریتم ها آن است که آنها قابلیت یافتن یک مسیر در صورت وجود آن را خواهند داشت [1]. در الگوریتم های مسیریابی موجی، فیلد تبدیل به سلول های دارای اندازه مساوی برای فواصل مجاز بین اتصالات تقسیم می شوند (شکل 7). اتصالات می بایست به صورت عمود بر یال های سلول باشد. یک نشان بین ترمینال های A و B به عنوان مجموعه ای از سلول های مجاور تعریف می گردد (یعنی به صورت مربعات با یک یال معمول) که قابلیت اتصال سلول های A و B را  خواهد داشت. الگوریتم مسیریابی موج کلاسیک متشکل از دو فاز می باشد. در اولین فاز، وجود یک مسیر به هدف از طریق انتشار یک موج در امتداد گراف تحلیل می شود. به هنگامی که این موج از منبع A به هدف B انتشار یافت، سلول های کاری گسسته اقدام به تخصیص وزن ها با توجه به تابع هدف می نمایند [1]. انتشار موج و تخصیص وزن به شرح ذیل اعمال می شود (به شکل 7  الف رجوع شود). در اولین مرحله، کلیه سلول های مجاور منبع A به وزن 1 تخصیص داده می شوند. در مرحله دوم، کلیه سلول های مجاور به سلول های دارای وزن واحد به وزن 2 تخصیص می یابند. در iامین مرحله، کلیه سلول های  مجاور به این سلول ها با وزن (i – 1) نیز دارای وزن i می گردند. این فرآیند تا زمانی تکرار می گردد که سلول هدف B حاصل شده باشد. به منظور ایجاد چنین مسیری، لازم است تا کار خود را از سلول هدف آغاز نموده و در مسیر متضاد با جهت انتشار موج، با حرکت از سلول به یک وزن بیشتر به سلول مجاور دارای وزن واحد کمتر تا زمان دسترسی به سلول منبع این رویه را دنبال نمود. سلول های فیلد کاری گسسته که با استفاده از این رویه انتخاب گردیده اند مشخص کننده اتصال بهینه خواهند بود (به شکل 7 ب رجوع شود).
در صورتی که هیچ مسیری قابلیت ایجاد نداشته باشد (به مرجع [16] رجوع شود) ، لازم است تا یک فرآیند باز مسیریابی اتصالات انجام پذیرد. ایده اصلی این باز مسیریابی یافتن اتصالاتی می باشد که از مسیریابی اتصالات مسیردهی نشده ممانعت نموده و متعاقباً آن را حذف کرده و متعاقباً اقدام به مسیردهی اتصالات بدون مسیر نماید.
به منظور حذف تعارضات بین اتصالات s2 و s1، روش پیرامونی در مرجع [28] ارائه شده است. در صورتی که مسیردهی اتصال s1 با شکست رو به رو شود، اتصال مسیر داده شده s2 که از مسیردهی s1 ممانعت می  نماید رجیستر خواهد شد. متعاقباً اتصال s2 شکسته شده و با استفاده از الگوریتم لابیرنت و با حذف موانع مسیردهی s1 رویه باز مسیریابی اعمال می گردد. با این وجود، اتصال قبلی غیر بهینه خواهد بود. در صورتی که هیچ مانعی از s2 وجود نداشته باشد اتصال s1 مسیردهی خواهد شد. در پی مسیردهی s1، اتصال s2 باز مسیردهی گردیده و در عین حال اقدام به بهینه سازی ویژگی های آن با توجه به این حقیقت خواهد شد که s1 قبلاً مسیردهی شده است. اتصال s2 ایجادی به وسیله الگوریتم غیربهینه لابیرنت حذف شده و مجدداً با استفاده از الگوریتم موجی ساخته خواهد شد.

مسیریابی کانال بر مبنای مدل رفتار تطبیقی کلونی مورچه ها

 

5- تکمیل مسیریابی بر مبنای ترکیب الگوریتم های WAVE و ACO
در اولین فاز، ناحیه مسیریابی X بر مبنای انتشار موج در میدان کاری گسسته از منبع به هدف شکل می گیرد. ناحیه مسیریابی متشکل از مجموعه ای از سلول های فیلد کاری گسسته متصل می باشد که به وسیله موج دسترسی یافته و قابلیت تخصیص وزن را دارند. در فاز دوم، یک الگوریتم ACO اقدام به یافتن یک مسیر در ناحیه مسیریابی X خواهد نمود.
حال  اجازه دهید تا  به عنوان مجموعه ای از فیلد کاری گسسته در نظر گرفته شود که بر مبنای اتصال sk به وسیله عامل ak قرار گرفته است. برای سلول xi با وزن r(xi)، ما اقدام به تعریف درجه آزادی ω(xi) به عنوان تعداد سلول ها با وزن(r(xi)-1)  می نماییم که مجاور با xi می باشد. بنابراین1 £ ω(xi) £ 3 معتبر خواهد بود. حال قابلیت تعریف درجه Ω(sk) آزادی اتصال sk وجود خواهد داشت که بر مبنای آن می توان نسبت به توصیف سطح مانع ایجادی به وسیله sk برای مسیریابی اتصالات دیگر اقدام نمود. در بین سلول های xi Î Xk، سلول دارای حداقل درجه آزادی ω(xi)min یافت می شود.
درجه آزادی اتصال sk به شرح ذیل تعریف می گردد:
که در آن k1 و k2 ضرایب معنی دار به شمار می آیند. هر چه که Ω(sk) بیشتر باشد، میزان فضای آزاد بیشتری در اطراف sk وجود خواهد داشت و مانع بالقوه کمتری برای مسیریابی دیگر اتصالات مدنظر خواهد بود.
در هر تکرار الگوریتم ACO، استراتژی رفتار هر عامل از طریق ایجاد کوتاه ترین مسیر با تعداد حداقلی انحراف ها، تعداد حداقلی گذارهای بین لایه ای و درجه حداقلی آزادی مشخص می گردد. حال اجازه دهید تا مسیر sk به وسیله عامل ak یافت شود و همچنین دارای dk انحراف و tk گذار بین لایه ای باشد. به عنوان تابع هدف مسیر، ما از تابع ذیل استفاده می نماییم:

مسیریابی کانال بر مبنای مدل رفتار تطبیقی کلونی مورچه ها

 

6- مطالعه آزمایشی
بررسی های آزمایشی بر روی کامپیوترهای شخصی (PC) شرکت IBM انجام شدند. هدف از این آزمایشات به شرح ذیل دنبال می شوند:
  1. بررسی مکانیزم های کلونی مورچه در ارتباط با مشکل مسیریابی کانال. تاکنون، تأثیر پارامترهای کنترلی، نظیر اندازه جمعیت، تعداد تکرارها، تعداد اولیه فرومون های رسوب شده در رأس های گراف، و موارد دیگر از جمله مؤلفه های حایز توجه به شمار می آیند. در نتیجه، ترکیب این پارامترها فراهم آورنده بالاترین میزان کارایی رویه های تطبیقی در ارتباط با مسئله مسیریابی کانال می باشد.
  2. بررسی کارایی الگوریتم تطبیقی پیشنهادی و بررسی تأثیر پارامترهای مربوطه همانند تعداد مدارها در کانال. به همین منظور، راهکار ایجاد معیارهایی با توجه به ویژگی های شناخته شده بهینه و با قیاس با الگوریتم ایجاد مثال های جایگزینی کاملاً شناخته شده با استفاده از الگوریتم ایجاد کرانه های فوقانی شناخته شده بر روی طول سیم (PEKU) بکار گرفته شد [29 ـ 31].
چهار آزمایش با توجه به پهنای کانال بهینه شناخته شده Fopt ایجادی مناسب تشخیص داده شده اند. روش ذیل جهت انجام آزمایشات در نظر گرفته شد. در مرحله ورودی تعدادی از ترمینال ها و مدارها بکار گرفته شدند. متعاقباً، یک مثال مسئله مسیریابی کانال ایجاد شده که دارای پهنای کانال بهینه شناخته شده Fopt (تعداد تراک ها) می باشد. این پهنای کانال با استفاده از راهکار تشریح شده در مرجع [1] کمینه سازی شده است.
این آزمایشات نشان دهنده آن هستند که مقدار اولیه فرومون Ω می بایست بر حسب ضریب 10 ـ 12 بیشتر از مقدار میانگین فرومون τk(l) رسوب شده به وسیله مورچه ها در هر بار تکرار در نظر گرفته شوند. جهت یافتن بهترین ترکیب چنین پارامترهایی همانند اندازه جمعیت N و تعداد تکرارها I، آزمایشات مربوطه به شرح ذیل سازماندهی شده اند.
برای هر مثال، اندازه جمعیت N در ابتدا ثابت شده و مقدار تعداد تکرارهای I نیز مورد تحلیل قرار گرفت. یکسری از 10 مورد آزمایشی برای هر مجموعه ثابت پارامترها اعمال گردید.
نتیجه گیری
در این مقاله، فناوری های جدید، اصول و مکانیزم های نوین برای حل مسئله مسیریابی کانال ارائه شده اند. آنها بر مبنای شبیه سازی رفتار تطبیقی کلونی مورچه ها می باشند. در مقایسه با الگوریتم های موجود، نتایج بهتری در این زمینه حاصل شده است. رویکرد کنونی را می توان برای مسیریابی “بدون گرید” اتصالات با پهنای مختلف بکار گرفت. راهکار مسیریابی اصلاح شده به صورت ترتیبی اقدام به قرار دادن بخش ها نموده و آنها را به صورت “پرس شده” و تا حد ممکن نزدیک به یکدیگر قرار می دهد. در نتیجه، مختصات فیزیکی بخش های قرار گرفته نیز حاصل می شوند.
بر مبنای تحلیل مقایسه ای رویکردهای موجود و روش های مرتبط برای حل مسئله تکمیل مسیریابی و باز مسیریابی، روش های بهینه سازی هوشمند چند عامله با توجه به شبیه سازی رفتار تطبیقی کلونی های مورچه ها بکار گرفته شده است. مسئله مسیریابی کانال بر حسب مجموعه ای از مؤلفه های مربوط به الگوریتم بهینه سازی کلونی مورچه ها می باشد. بر این مبنا قواعد ابتکاری / اکتشافی حاکم بر رفتار مورچه ها با توجه به حرکت آنها در گراف جستجوی راه حل به دست آمده و توسعه یافته اند.
یک رویکرد جدید برای پیاده سازی فاز دوم مسیریابی موجی نیز ارائه شده است. در تمایز با رویکرد کلاسیک و در رابطه با اجرای این فاز، که بر مبنای استراتژی آزمندانه بدون عقب گرد می باشد، الگوریتم مسیریابی کلونی مورچه ها بر حسب ویژگی های تطبیقی و پذیرش رویه های جمعی اتخاذ شده است. بنابراین قابلیت به حساب آوردن فاکتورهای مختلف همانند توزیع منابع، موانع (بلوک بندی ها)، تعداد گذارهای بین لایه ها، تعداد انحراف ها و موارد دیگر وجود خواهد داشت که به حساب آوردن آنها در موقعیت های محلی با توجه به انتشار موج مشکل خواهد بود.
در مقایسه با الگوریتم های موجود، کیفیت راه حل ها به میزان 3% افزایش یافته است. الگوریتم مسیریابی کانال هوشمند ازدحام پیشنهادی در ترکیب با الگوریتم تکمیل مسیریابی قابلیت یافتن راه حل ها در زمینه مسایل بزرگ مقیاسی را خواهند داشت که  می توان آنها را با نتایج حاصله به وسیله الگوریتم های دیگر بر حسب کیفیت مقایسه نمود و حتی در بعضی از مواقع راه حل های بهتری را به دست آورد و در عین حال از زمان محاسباتی کمتری نیز استفاده نمود. به علاوه، این فرآیند قابلیت بهینه سازی طول اتصالات را نیز خواهد داشت.
یک مسیر امید بخش برای ارتقای الگوریتم مسیریابی کانال کلونی مورچه ها پذیرش پارامترها با استفاده از مجموعه ای از  قواعد  فازی در ترکیب  با  الگوریتم های  ژنتیک  می باشد. چنین ترکیبی می تواند بر مبنای تبادل بهترین راه حل های جاری در بازه های زمانی خاص باشد. راهکار دیگر ارتقای این الگوریتم، کاربرد یک ناحیه مسیریابی گسترده می باشد که در عین افزایش اندک ناملموس در طول مسیر می تواند موانع را نیز به حداقل برساند. کارایی این الگوریتم را همچنین می توان بر حسب کنترل تطبیقی پارامترهای آن ارتقا داد.

مسیریابی کانال بر مبنای مدل رفتار تطبیقی کلونی مورچه ها

 

دیدگاهتان را بنویسید

نشانی ایمیل شما منتشر نخواهد شد. بخش‌های موردنیاز علامت‌گذاری شده‌اند *

لطفا به جای کپی مقالات با خرید آنها به قیمتی بسیار متناسب مشخص شده ما را در ارانه هر چه بیشتر مقالات و مضامین ترجمه شده علمی و بهبود محتویات سایت ایران ترجمه یاری دهید.
تماس با ما

اکنون آفلاین هستیم، اما امکان ارسال ایمیل وجود دارد.

به سیستم پشتیبانی سایت ایران ترجمه خوش آمدید.