بخشی از مقاله
خلاصه
بی شک طراحی مدار چاپی از چالش هاي اجرایی صنعت الکترونیک بوده و در این خصوص پیشرفت هاي عظیمی نیز حاصل شده است. وجود نرمافزارهاي متعدد طراحی مدار چاپی به نوعی اهمیت موضوع را از یکسو و همچنین وجود پسخورد انسانی را در این چرخه نشان میدهد. این نرمافزارها جهت طراحی مدارچاپی از الگوریتمهاي معین و از پیش تعیین شده که توسط قواعد طراحی مشخص میشوند، استفاده مینمایند.
در این مقاله بکارگیري الگوریتم کلونی مورچگان و راهکارهاي بهینه نمودن این الگوریتم به عنوان روشی فراابتکاري مورد بررسی قرار خواهد گرفت. استفاده از الگوریتم S-ACO جهت طراحی مدار چاپی و حل مسئله مسیریابی اتصالات پایههاي قطعات الکترونیکی و در مواردي تغییر در این الگوریتم، منجر به یافتن روش مسیریابی خودکار - antPCB - می گردد که میتواند به عنوان هسته طراحی PCB در نرمافزارهاي طراحی مدارچاپی مورد استفاده قرار گیرد.
.1 مقدمه
برد مدار چاپی از فیبر عایق به عنوان زیرساخت، قطعات الکترونیکی، خطوط اتصالی، سوراخ هاي محل قرارگیري پایه هاي قطعات و دیگر اجزاء مکانیکی تشکیل شده است که تقریباً در تمامی محصولات الکترونیکی مورد استفاده قرار میگیرد. با توجه به اینکه فناوري مدارهاي مجتمع روز به روز پیشرفت میکند، پیچیدگی مدار چاپی نیز بیشتر میشود. بنابراین جهت بهینه سازي مدارات الکترونیکی، مسیریابی در طراحی PCB معمولا با ابزارهاي اتوماسیون الکترونیک - EDA - انجام میگردد .[1]
با توجه به گستردگی مسائل صنعت ساخت مدارات الکترونیکی این پژوهش، بر یافتن راه حل مناسب براي مسیریابی اتصالات بین پایه هاي قطعات الکترونیکی روي برد تمرکز دارد و در این خصوص الگوریتمهاي متنوعی مورد آزمایش قرار گرفته و استفاده از هوش مصنوعی و الگوریتم هاي تکاملی به عنوان راهکارهاي فراابتکاري مورد توجه قرار میگیرد. ما به عنوان یک موجود هوشمند، در مسائل روزمره، با استفاده از روش هاي جستجو، اقدام به یافتن راهحلی براي مسئله میکنیم. در حل مسئله مسیریابی مدارچاپی از ترکیب روش جستجوي A* که خود تلفیقی از روش جستجوي هزینه یکنواخت و روش جستجوي حریصانه است و الگوریتم بهینهسازي کلونی مورچگان1استفاده میگردد که منجر به ایجاد الگوریتم antPCB خواهد شد.
.2 برد مدار چاپی - PCB - 2
طرح PCB تعریف کننده مسیرهاي الکتریکی بین اجزاء می باشد. این طرح از روي یک طرح شماتیکی مدار ترسیم می شود. زمانی که این رسم انجام شد، در واقع سمبل هاي شماتیکی و کتابخانه ها تبدیل به اتصالات و قطعات فیزیکی می شوند. بطور کلی به فرآیند انتقال نقشه شماتیک و چیدمان قطعات بر روي برد با ابعاد لازم و ضخامت لازم و مسیریابی و اتصال نت هاي یکسان به هم با استفاده از سطوح مسی رو و پشت برد و رعایت مسائل تکنیکی ساخت شامل قطر سوراخ کاري و مقدمات لحیم کاري و چاپ راهنما و محافظ، طراحی برد مدار چاپی گفته می شود.
در این پژوهش مسیریابی بهینه که یکی از فرآیندهاي ساخت بوده و از پیچیدگی بسیاري برخوردار است با استفاده از روش تکاملی کلونی مورچگان مورد بررسی و تحلیل قرار می گیرد. از این پس منظور از طراحی مدار چاپی، طراحی مسیر هاي ارتباطی نت ها می باشد. بطور نمونه یک نت لیست که در شکل 1 مورد استفاده قرار گرفته است و مدار یک تقویت کننده امیتر مشرك را توصیف می کند، آورده شده است. اطلاعات استخراج شده از نت لیست در واقع راه حل مدار چاپی و خلاصه اي از اجزاء مدار را به ما اطلاع می دهد که در ادامه با استفاده از رابط کاربري و رسم طرح برد مدارچاپی توسط کاربر این نت لیست تهیه و به صورت ماتریس گراف مسیر و موانع در الگوریتم مورد استفاده قرار می گیرد.
.3 روش جستجوي A*
روش جستجويA* تلفیقی از روش جستجوي هزینه یکنواخت و روش جستجوي حریصانه است. در جستجوي هزینه یکنواخت بر اساس هزینه تا گره فعلی،کم هزینهترین گره را انتخاب میکنیم و توسعه میدهیم. جستجوي هزینه یکنواخت بهینه است، یعنی جواب بهینهي مدار را پیدا میکند، ولی در مقابل بسیار زمانبر است. جستجوي حریصانه نیز بر اساس هزینه تا مقصد، کم هزینهترین گره را براي گسترش انتخاب میکند. یافتن جواب با استفاده از جستجوي حریصانه به سرعت انجام میگیرد. ولی این روش نیز با مشکلاتی همچون بهینه نبودن جواب مواجه است. روش جستجوي A* سرعت روش حریصانه در رسیدن به جواب و بهینهگی روش هزینه یکنواخت در پیدا کردن جواب را با هم ترکیب میکند و به جستجوي هدف خود میپردازد .[2]
.4 الگوریتم بهینه سازي کلونی مورچگان
الگوریتم کلونی مورچه براي اولین بار توسط دوریگو و همکارانش به عنوان یک راه حل چندعامله براي حل مسائل بهینه سازي ارائه شد. یکی از مهمترین و جالب ترین رفتار مورچه ها رفتار آنها براي یافتن غذا و به ویژه چگونگی پیدا کردن کوتاهترین مسیر میان منابع غذایی و آشیانه است .[2] درحقیقت، مورچههاى واقعی توائایی پیداکردن کوتاهترین مسیر از لانه به منبع غذایی را بدون داشتن حس بینایی دارند و براى این کار، فقط ازحس بویایی خود استفاده میکنند. به طورى که هر مورچه از خود مایعی به نام فرمون به جاى میگذارد که این مایع به مرور زمان بخار میشود و مورچه ها هم به احتمال زیادتر مسیرى را انتخاب میکنند که فرمون بیشترى در آن باشد. همچنین مورچهها میتوانند سازگاري لازم براى مواجه با تغییرات در محیط اطرافشان را داشته باشند. به عنوان مثال سناریوى زیر را در نظر بگیرید .[3]
فرض بر این است همه مورچهها در گره آغازین وجود دارند. مورچهها گره بعدي را بر طبق قواعد انتقال انتخاب می کنند. مورچهها پس از رسیدن به مقصد و در راه برگشت، فرمون خود را آزاد مینماید و مورچههاي دیگر آن را به عنوان نشانه و سیگنالی درك نموده و فرمون آزاد شده از این مورچه، کارآیی فرمون مورچهي قبلی را افزایش میدهد. پس هر چه مورچهها بیشتر از یک مسیر بگذرند. این امکان که این مسیر توسط دیگر مورچهها انتخاب شود، بیشتر خواهد شد. این فرآیند تقرًیبا تمامی مورچهها را متعهد میسازد تا از کوتاهترین مسیر عبور کنند .[3]
واضح است که در مدلسازى رفتار مورچهها باید تفاوتهایی را براى مورچههاى مصنوعی و حقیقی در نظر گرفت: مورچههاى طبیعی به صورت موازى حرکت مینمایند و همه با هم و به صورت پیوسته فرمون ترشح میکنند. در صورتی که در شبیهسازى، مورچههاى مصنوعی یکی پس از دیگرى حرکت نموده و عمل فرمون پاشی هم بعد از اینکه یک مورچه به هدف رسید، انجام میشود. مورچههاى طبیعی در یک دنیاى پیوسته حرکت میکنند، در صورتی که مورچههاى مصنوعی در یک دنیاى گسسته عمل مینمایند.
مورچههاى مصنوعی حافظهى خیلی خوبی دارند و خانههاى تکرارى که قبلا از آن عبور کردهاند را نمیپیمایند. مورچههاى مصنوعی مقدار فرمونی که از خود به جاى میگذارند بستگی به کیفیت جوابی دارد که ساختهاند. البته در حالت واقعی هم بعضی از مورچههاى حقیقی رفتار مشابهی دارند و در مسیرهایی که مقدار غذاى زیادترى وجود دارد فرمون زیادترى از خود به جاى میگذارند. در ادامه نحوه به کارگیري الگوریتم بهینه سازي کلونی مورچگان - ساده - S-ACO - را در طراحی مدار چاپی بیان مینماییم.
.5 جزئیات الگوریتم کلونی مورچگان
در این قسمت با بررسی جزئیات الگوریتم S-ACO نشان می دهیم که رفتار مورچههاي واقعی با راه حل مسائل مسیرهایی با هزینه کمینه در گراف ها تطبیق پیدا میکند. به هر یال - i,j - از گراف G= - N,A - یک متغیر , با نام مسیر فرمون مصنوعی اختصاص می دهیم که این مسیرهاي فرمون، توسط مورچه ها خوانده و نوشته میشوند. شدت فرمون، متناسب با کیفیتی است که توسط مورچهها در استفاده از یک یال در ساخت جوابهاي خوب تخمین زده میشود.
نحوهي مسیریابی توسط مورچهها به این شکل است که هر مورچه با شروع از گره مبدأ، با اجراي یک سیاست تصمیم گیري گام به گام، یک راه حل براي مسئله به وجود میآورد. در هر گره، اطلاعات محلی ذخیره شده در خود گره و یا در یالهاي خروجی آن، توسط مورچه خوانده - حس - میشود و در یک حالت تصادفی براي انتخاب گره بعدي استفاده میگردد. رابطهي - 1 - احتمال حضور مورچه در هر گره را بیان می کند.
