الف – پرداخت وجه بحساب وب سایت ایران ترجمه(شماره حساب)ب- اطلاع جزئیات به ایمیل irantarjomeh@gmail.comشامل: مبلغ پرداختی – شماره فیش / ارجاع و تاریخ پرداخت – مقاله مورد نظر --مقالات آماده سفارش داده شده پس از تایید به ایمیل شما ارسال خواهند شد.
قیمت
قیمت این مقاله: 68000 تومان
(ایران ترجمه - Irantarjomeh)
توضیح
بخش زیادی از این مقاله بصورت رایگان ذیلا قابل مطالعه می باشد.
مسیریابی کانال بر مبنای مدل رفتار تطبیقی کلونی مورچه ها
نام انگلیسی
Channel Routing Based on Ant Colony Adaptive Behavior Model
تعداد صفحه به فارسی
۵۷
تعداد صفحه به انگلیسی
۱۶
کلمات کلیدی به فارسی
مسیریابی, رفتار تطبیقی, کلونی مورچه ها
کلمات کلیدی به انگلیسی
Channel Routing, Ant Colony, Adaptive Behavior Model
مرجع به فارسی
هوش مصنوعی
دانشگاه سادرن فدرال، روستو، روسیه
ژورنال کامپیوتر و علوم سیستم ها
مرجع به انگلیسی
Journal of Computer and Systems Sciences International; Southern Federal University, Rostov on Don, Russia
کشور
روسیه
مسیریابی کانال بر مبنای مدل رفتار تطبیقی کلونی مورچه ها
چکیده
بر مبنای تحلیل تطبیقی رویکردها و روش های موجود برای حل مسایلی نظیر مسیریابی، تکمیل فرآیند مسیریابی و مسیریابی مجدد اتصالات در VLSI، روش های بهینه سازی هوش چند عامله مورد استفاده قرار گرفته اند. آنها بر مبنای شبیه سازی رفتار تطبیقی کلونی مورچه ها می باشند. مسئله مورد بررسی در این مقاله بر مبنای مجموعه ای از مؤلفه های مرتبط با الگوریتم کلونی مورچه ها است. در این راستا یکسری از ویژگی های اکتشافی حاصل شده اند که بر مبنای مولفه های حاکم بر رفتار مورچه ها، با توجه به حرکت آنها در نمودار جستجو، می باشند. یک ویژگی متمایز الگوریتم پیشنهادی قابلیت آن جهت به حساب آوردن برخی از ویژگی های خاص، نظیر توزیع منابع، تأثیرات بازدارندگی (بلوکه شدگی) ، تعداد گذارهای بین لایه ها، تعداد انحراف ها و موارد دیگر، می باشد، که با توجه به این موضوع به حساب آوردن کلیه این ویژگی ها به هنگام محاسبه چگونگی انتشار موج بسیار مشکل می باشد. الگوریتم مسیریابی مرتبط آزمایش شده و با دیگر الگوریتم های شناخته شده با توجه به ارائه برخی از معیارها و ویژگی های محک سنجی خاص مورد بررسی قرار می گیرد. در مقایسه با الگوریتم های موجود، کیفیت راه حل ها تا میزان ۳% ارتقاء یافته است. یکی از مسیرهای قابل توجه در این مبحث ارتقای الگوریتم کاربرد دامنه مسیریابی بصورت گسترده می باشد که صرفاً سبب افزایش اندکی در طول مسیر خواهد شد اما در عین حال موجب به حداقل رسانی موانع و مشکلات موجود می گردد. کارایی چنین الگوریتمی را می توان با استفاده از فرآیند کنترل تطبیقی پارامترهای الگوریتم ارتقا داد.
مسیریابی کانال رفتار تطبیقی کلونی مورچه ها
مقدمه
بخش مهم توسعه سیستم های هوشمند طراحی به وسیله کامپیوتر (CADs) که در ارتباط با VLSI می باشد خصیصه مسیریابی اتصالات است. به واسطه کاهش یکنواخت اندازه هندسی المان ها و در نتیجه افزایش تعداد اجزای مرتبط بر روی یک تراشه، مسئله مسیریابی پیچیدگی بیشتر و بیشتری می یابد. گذار به سمت فناوری های نانومتری تولید مدار انتگرال خود سبب ایجاد محدودیت های جدیدی در خصوص چنین معضلی می شود [۱، ۲]. تاکنون، اکثریت روش های مسیریابی موجود از یک رویکرد دو فازه متشکل از مسیریابی متمرکز و مسیریابی تفصیلی [۱، ۴] استفاده نموده اند. مسیریابی کلی قابلیت تقسیم دامنه یا حوزه ارتباطاتی به زیرحوزه های مسیریابی (سلول ها) را داشته و بر این مبنا اتصالات بین آنها مسیر یابی می شود.
انواع کاملاً شناخته شده مسیریابی تفصیلی شامل مسیریابی کانال [۴ ـ ۶] ، مسیریابی سوئیچ ـ جعبه [۷، ۸] و مسیریابی آنچه تحت عنوان تراشه ـ کامل خوانده شده می باشد. مسیریابی تراشه ـ کامل به عنوان یکی از قابل توجه ترین موارد از نقطه نظر توسعه الگوریتم های جدید به حساب می آید [۹ ـ ۱۲] .
شاخص عملکرد اصلی که می بایست قابلیت بهینه سازی آن وجود داشته باشد را می توان ویژگی های مربوط به مسیریابی (بخشی از اتصالات مسیر داده شده بر مبنای تعداد کل اتصالات و با توجه به ویژگی های مبنایی درصدی) دانست. به طور ایده آل، چنین موردی را می بایست در یک حالت صد در صدی مد نظر قرار داد [۱۳، ۱۴]. هیچ کدام از رویکردهای موجود جهت مسیریابی فناوری های تولیدی VLSI مدرن (علی الخصوص، برای فناوری ۳۵ نانومتری)، قابلیت تضمین مسیریابی ۱۰۰% را ارائه نمی نمایند. در چنین موردی، راهکار محتمل بکارگیری یک رویه مسیریابی دو فازه می باشد. در اولین فاز، مسیریابی تحت محدودیت های مشخص و با توجه به شکل اتصالات انجام می گردد….
افزایش شدید در پیچیدگی کاربردی VLSI سبب توسعه روش های کارآمد جدید و ابزارهای مرتبط برای طراحی شده است. در این مقاله، ما نسبت به ارائه فناوری ها، اصول و روش های راه حل مناسب برای مسیریابی کانال، تکمیل مسیریابی، و مسیریابی مجدد بر مبنای شبیه سازی رفتار تطبیقی کلونی مورچه ها اقدام خواهیم نمود [۲۴ ـ ۲۷] . رویکرد پیشنهادی را می توان برای مسیریابی بدون گرید اتصالات با پهنای مختلف بکار گرفت. در مقایسه با الگوریتم های موجود، نتایج حاصله بنظر ارتقاء یافته می باشند.
مسیریابی کانال رفتار تطبیقی کلونی مورچه ها
۱- طرح مسئله مسیریابی کانال
یک کانال در حقیقت به عنوان ناحیه ای تلقی می شود که به وسیله دو خط ترمینال به یکدیگر متصل شده اند [۱]. خط پایینی / تحتانی ترمینال ها بر حسب و خط بالایی / فوقانی بر مبنای مشخص می شوند. مجموعه مدارات تا خط انتهای ترمینال ها گسترش یافته و مجموعه مدارات نیز تا خط فوقانی ترمینال ها، ، گسترش می یابند. ناحیه مسیریابی با گرید متعامد مرجع مشخص گردیده و مسیرها بر روی خطوط این گرید طراحی می گردند. خطوط افقی تحت عنوان تراک ها خوانده می شوند. خطوط عمودی نیز در امتداد ترمینال ها حرکت می نمایند (شکل ۱).
در مسیریابی کانال، هر مدار قابلیت اتصال ترمینال های هم ظرفیت را داشته که به وسیله مجموعه ای از قسمت ها (بخش ها) افقی و عمودی مشخص می گردند. بخش های افقی بر روی تراک ها قرار می گیرند. پیکربندی بخش های عمودی که قابلیت اتصال بخش های افقی با خط تحتانی و فوقانی ترمینال ها را دارند به طور کامل از طریق جابجایی بخش های افقی مشخص می گردند. بخش افقی نیز به عنوان یک قسمت افقی متصل به وسیله بخش های عمودی با ترمینال های منطبق همان مدار مدنظر می باشد. رویکردهای مختلفی در زمینه ایجاد بخش های افقی وجود دارند. در یک حالت ساده، یک مدار تنها دارای یک بخش افقی با قسمت های عمودی متلاقی می باشد. یک مسیر حاوی صرفاً یک بخش افقی تحت عنوان مورد بدون انحنا یا کجی خوانده می شود. در عمل، ممکن است انحراف هایی در مناطقی وجود داشته باشند که در آن بخش های عمودی و افقی در تماس با یکدیگر هستند، یعنی بخش های افقی بین جفتی از تماس های مجاور همان مدار پدیدار می شوند. در حالت کلی، مسئله مسیریابی کانال به عنوان مسئله جایگزینی به شمار می آیند که در معرض محدودیت هایی در ارتباط با مجموعه های بخش های افقی و مجموعه های تراک های می باشد [۱]. چنین قیدها یا محدودیت هایی از هم پوشانی بخش های عمودی و افقی مدارات مختلف جلوگیری می نمایند. به منظور به حساب آوردن چنین قیدها یا محدودیت هایی، یک گراف محدودیت عمودی و یک گراف محدودیت افقی بدون جهت بکار گرفته شده است. در اینجا، V به عنوان مجموعه ای از رأس های منطبق با بخش های افقی به شمار می آید (شکل ۲). یک یال جهت دار (قوسی) صرفاً در صورتی وجود خواهد داشت که بخش vi را می بایست در بالای بخش vj قرار داد…
مسیریابی کانال رفتار تطبیقی کلونی مورچه ها
۲- الگوی کلونی مورچه ها
ایده بنیادی در ارتباط با بهینه سازی کلونی مورچه ها (ACO) تقلید رفتار مورچه ها می باشد که به سرعت قابلیت یافتن کوتاه ترین مسیر از لانه خود به یک منبع غذایی را دارند. رفتار کلونی مورچه بر مبنای یک ویژگی خودسازماندهی شده می باشد که این تضمین را به وجود می آورد که اهداف کلی کلونی بر مبنای تعاملات سطح پایین حاصل می گردد و بر مبنای چنین رفتاری، کلونی مربوطه به عنوان یک هویت کلی در حقیقت نقش یک سیستم چند عامله هوشمند را بازی می نماید. ویژگی این الگو کاربرد تعاملات غیرمستقیم بین حشرات می باشد (که تحت عنوان استیگمرجی یا نشانه ورزی خوانده می شود). این نوع از کنش در الگوریتم های ACO بکار گرفته می شود [۲۴، ۲۵]. فرآیند نشانه ورزی در حقیقت به عنوان یک تعامل یا کنش توزیع شده در خلال زمان به شمار می آید. در مورد چنین تعاملی، یک فرد اقدام به بررسی و شناخت یک ناحیه از محیط پیرامونی نموده و افراد دیگر از این اطلاعات به هنگام حضور در چنین ناحیه ای استفاده می نمایند. تعامل پیشنهادی از یک ماده شیمیایی خاص تحت عنوان فرومون استفاده می نماید. غلظت فرومون در یک مسیر مشخص کننده ترجیح چنین مسیری می باشد. به هنگامی که یک مورچه در امتداد یک مسیر حرکت می نماید، قابلیت علامت گذاری آن به وسیله فرومون را خواهد داشت و چنین اطلاعاتی به وسیله مورچه های دیگر جهت انتخاب یک مسیر بکار گرفته می شود. غلظت یا تراکم فرومون مشخص کننده تمایل یک مورچه جهت انتخاب یک مسیر یا مسیر دیگر می باشد. با این وجود، چنین الگوریتمی ناچاراً در آپتیمای محلی گیر خواهد افتاد. این مسئله را می توان با استفاده از تبخیر فرومون حل نمود که نقش بازخورد منفی را ایفا می نماید.
مسیریابی کانال رفتار تطبیقی کلونی مورچه ها
۳- مسیریابی کانال بر مبنای الگوی کلونی مورچه ها
راه حل های این مسئله بر مبنای گراف کامل راه حل های R(F, E) جستجو می شوند، که در آن مجموعه رأس های F مترادف با مجموعه بخش ها می باشد و E به عنوان مجموعه ای از یال های گراف کامل به شمار می آید [۱۸]. راه حل مسئله مسیریابی کانال به وسیله مسیر Sk ارائه شده است که خود شامل کلیه رأس های گراف راه حل R(F, E) می باشد. تبالی رأس ها در مسیر Sk مشخص کننده آرایش المان های متناظر در لیست Fk می باشد. شکل ۴ نشان دهنده این مسیر در گراف مربوطه معادل جابجایی بخش ها در تراک های نشان داده شده در شکل ۱ می باشد. وظیفه هر مورچه ak ایجاد یک مسیر Sk در گراف R می باشد که خود به عنوان راه حل مسئله مسیریابی کانال به شمار آمده و در آن k به عنوان شاخص (عامل) مورچه محسوب می شود. جایگزینی المان های لیست Fk در تراک ها و محاسبه شاخص عملکرد مسیر ـ تعداد تراک ها ـ بر مبنای راهکار اصلی اعمال می شود. وظیفه کلونی مورچه یافتن در گراف R(F, E)، مسیر متناظر با جایگزینی بخش ها در تعداد حداقلی تراک ها می باشد.
از آنجایی که کانال به صورت متقارن است (به شکل ۱ رجوع شود)، شمارش تراک ها (TE) و پر کردن آنها با بخش های مختلف (FF) را می توان در چهار روش ارائه شده ذیل انجام داد:
TE از بخش فوقانی به تحتانی، FF از چپ به راست،
TE از بخش فوقانی به تحتانی، FF از راست به چپ،
TE از بخش تحتانی به فوقانی، FF از چپ به راست،
TE از بخش تحتانی به فوقانی، FF از راست به چپ.
در شکل ۱، اولین روش بکار گرفته شده است.
به منظور ارتقای کارایی، راه حل بر مبنای چهار گروه مورچه ها Z1–Z4 با استفاده از چهار روش مختلف دنبال می شود.
مسیریابی کانال رفتار تطبیقی کلونی مورچه ها
۴- تکمیل مسیریابی و الگوریتم های باز مسیریابی
به واسطه محدودیت ها از نظر شکل اتصالات مسیر داده شده در الگوریتم های مسیریابی کانال، برخی از اتصالات بدون مسیریابی باقی می مانند. برای این اتصالات، الگوریتم های مسیریابی تکمیل موج در فاز دوم مورد استفاده قرار می گیرند. یک ویژگی متمایز این الگوریتم ها آن است که آنها قابلیت یافتن یک مسیر در صورت وجود آن را خواهند داشت [۱]. در الگوریتم های مسیریابی موجی، فیلد تبدیل به سلول های دارای اندازه مساوی برای فواصل مجاز بین اتصالات تقسیم می شوند (شکل ۷). اتصالات می بایست به صورت عمود بر یال های سلول باشد. یک نشان بین ترمینال های A و B به عنوان مجموعه ای از سلول های مجاور تعریف می گردد (یعنی به صورت مربعات با یک یال معمول) که قابلیت اتصال سلول های A و B را خواهد داشت. الگوریتم مسیریابی موج کلاسیک متشکل از دو فاز می باشد. در اولین فاز، وجود یک مسیر به هدف از طریق انتشار یک موج در امتداد گراف تحلیل می شود. به هنگامی که این موج از منبع A به هدف B انتشار یافت، سلول های کاری گسسته اقدام به تخصیص وزن ها با توجه به تابع هدف می نمایند [۱]. انتشار موج و تخصیص وزن به شرح ذیل اعمال می شود (به شکل ۷ الف رجوع شود). در اولین مرحله، کلیه سلول های مجاور منبع A به وزن ۱ تخصیص داده می شوند. در مرحله دوم، کلیه سلول های مجاور به سلول های دارای وزن واحد به وزن ۲ تخصیص می یابند. در iامین مرحله، کلیه سلول های مجاور به این سلول ها با وزن (i – ۱) نیز دارای وزن i می گردند. این فرآیند تا زمانی تکرار می گردد که سلول هدف B حاصل شده باشد. به منظور ایجاد چنین مسیری، لازم است تا کار خود را از سلول هدف آغاز نموده و در مسیر متضاد با جهت انتشار موج، با حرکت از سلول به یک وزن بیشتر به سلول مجاور دارای وزن واحد کمتر تا زمان دسترسی به سلول منبع این رویه را دنبال نمود. سلول های فیلد کاری گسسته که با استفاده از این رویه انتخاب گردیده اند مشخص کننده اتصال بهینه خواهند بود (به شکل ۷ ب رجوع شود).
مسیریابی کانال رفتار تطبیقی کلونی مورچه ها
۵- تکمیل مسیریابی بر مبنای ترکیب الگوریتم های WAVE و ACO
در اولین فاز، ناحیه مسیریابی X بر مبنای انتشار موج در میدان کاری گسسته از منبع به هدف شکل می گیرد. ناحیه مسیریابی متشکل از مجموعه ای از سلول های فیلد کاری گسسته متصل می باشد که به وسیله موج دسترسی یافته و قابلیت تخصیص وزن را دارند. در فاز دوم، یک الگوریتم ACO اقدام به یافتن یک مسیر در ناحیه مسیریابی X خواهد نمود.
حال اجازه دهید تا به عنوان مجموعه ای از فیلد کاری گسسته در نظر گرفته شود که بر مبنای اتصال sk به وسیله عامل ak قرار گرفته است. برای سلول xi با وزن r(xi)، ما اقدام به تعریف درجه آزادی ω(xi) به عنوان تعداد سلول ها با وزن(r(xi)-1) می نماییم که مجاور با xi می باشد. بنابراین۱ £ ω(xi) £ ۳ معتبر خواهد بود. حال قابلیت تعریف درجه Ω(sk) آزادی اتصال sk وجود خواهد داشت که بر مبنای آن می توان نسبت به توصیف سطح مانع ایجادی به وسیله sk برای مسیریابی اتصالات دیگر اقدام نمود. در بین سلول های xiÎ Xk، سلول دارای حداقل درجه آزادی ω(xi)min یافت می شود.
…
مسیریابی کانال رفتار تطبیقی کلونی مورچه ها
۶- مطالعه آزمایشی
بررسی های آزمایشی بر روی کامپیوترهای شخصی (PC) شرکت IBM انجام شدند. هدف از این آزمایشات به شرح ذیل دنبال می شوند:
بررسی مکانیزم های کلونی مورچه در ارتباط با مشکل مسیریابی کانال. تاکنون، تأثیر پارامترهای کنترلی، نظیر اندازه جمعیت، تعداد تکرارها، تعداد اولیه فرومون های رسوب شده در رأس های گراف، و موارد دیگر از جمله مؤلفه های حایز توجه به شمار می آیند. در نتیجه، ترکیب این پارامترها فراهم آورنده بالاترین میزان کارایی رویه های تطبیقی در ارتباط با مسئله مسیریابی کانال می باشد.
…
مسیریابی کانال رفتار تطبیقی کلونی مورچه ها
نتیجه گیری
در این مقاله، فناوری های جدید، اصول و مکانیزم های نوین برای حل مسئله مسیریابی کانال ارائه شده اند. آنها بر مبنای شبیه سازی رفتار تطبیقی کلونی مورچه ها می باشند. در مقایسه با الگوریتم های موجود، نتایج بهتری در این زمینه حاصل شده است. رویکرد کنونی را می توان برای مسیریابی “بدون گرید” اتصالات با پهنای مختلف بکار گرفت. راهکار مسیریابی اصلاح شده به صورت ترتیبی اقدام به قرار دادن بخش ها نموده و آنها را به صورت “پرس شده” و تا حد ممکن نزدیک به یکدیگر قرار می دهد. در نتیجه، مختصات فیزیکی بخش های قرار گرفته نیز حاصل می شوند.
…
یک مسیر امید بخش برای ارتقای الگوریتم مسیریابی کانال کلونی مورچه ها پذیرش پارامترها با استفاده از مجموعه ای از قواعد فازی در ترکیب با الگوریتم های ژنتیک می باشد. چنین ترکیبی می تواند بر مبنای تبادل بهترین راه حل های جاری در بازه های زمانی خاص باشد. راهکار دیگر ارتقای این الگوریتم، کاربرد یک ناحیه مسیریابی گسترده می باشد که در عین افزایش اندک ناملموس در طول مسیر می تواند موانع را نیز به حداقل برساند. کارایی این الگوریتم را همچنین می توان بر حسب کنترل تطبیقی پارامترهای آن ارتقا داد.
لطفا به جای کپی مقالات با خرید آنها به قیمتی بسیار متناسب مشخص شده ما را در ارانه هر چه بیشتر مقالات و مضامین ترجمه شده علمی و بهبود محتویات سایت ایران ترجمه یاری دهید.
