نوع مقاله : مقاله علمی فارسی
نویسندگان
1 دانشجوی دکتری الکترونیک، دانشکده مهندسی- دانشگاه فردوسی- مشهد- ایران
2 دانشیار گروه مخابرات و الکترونیک، دانشکده مهندسی برق و کامپیوتر - دانشگاه بیرجند- بیرجند- ایران
چکیده
: در این مقاله یک ابزار بهینهسازی جدید در طراحی خودکار مدارات مجتمع آنالوگ مبتنی بر الگوریتم MOGSA ارائه میشود. ابزار بهینهسازی پیشنهادی در ابتدا با استفاده از یک نرمافزار شبیهساز مدار مورد نظر را شبیهسازی نموده، نتایج شبیه-سازی را به وسیله الگوریتم MOGSA تحت بهینهسازی قرار میدهد. سپس تا حصول نتیجه مطلوب این روند را ادامه خواهد داد. برنامههای اصلی این ابزار در Matlab پیادهسازی و شبیهسازی مدارات به وسیله نرمافزار Hspice انجام میشود. در این مقاله، به منظور بررسی توانایی ابزار پیشنهادی در بهینهسازی طراحی مدارات مجتمع آنالوگ عملکرد آن سنجش میشود. برای نمونه، یک مسأله سایزبندی مطرح میشود: «طراحی یک تقویت کننده عملیاتی مستقل از دما با استفاده از منبع جریان ویدلر کسکود». نتایج به دست آمده نه تنها مشخصات مورد نظر در طراحی را برآورده می‌سازد، بلکه با ارائه مجموعه جوابهای متنوع، حق انتخاب بیشتری را برای طراح با توجه به معیارهای مختلف طراحی فراهم می‌نماید. الگوریتم پیشنهادی MOGSA روش نوینی را در بهینهسازی چندهدفه مبتنی بر الگوریتم جستجوی گرانشی معرفی میکند که در آن از «بهینگی پَرِتو» برای شناسایی موقعیتهای «غیرغالب» و از یک «مخزن بیرونی» برای نگهداری این موقعیتها استفاده میشود. برای اطمینان از صحت عملکرد روش MOGSA، این الگوریتم به وسیله چندین تابع معتبر چند هدفه آزمایش قرارمی‌شود. نتایج نهایی نشان دهنده رقابت تنگاتنگ روش پیشنهادی با دیگر الگوریتمهای بهینهسازی چند هدفه رایج است.
کلیدواژه‌ها
عنوان مقاله [English]
A Novel Optimization Tool for Automated Design of Integrated Circuits based on MOSGA
نویسندگان [English]
- Maryam Dehbashian 1
- seyed Hamid Zahiri 2
1 Department of electrical engineering, Faculty of Engineering, Ferdowsi University of Mashhad, Mashhad, Iran
2 Department of electrical engineering, Faculty of Engineering, University of Birjand, Birjand, Iran
چکیده [English]
In this paper a novel optimization method based on Multi-Objective Gravitational Search Algorithm (MOGSA) is presented for automated design of analog integrated circuits. The recommended method firstly simulates a selected circuit using a simulator and then simulated results are optimized by MOGSA algorithm. Finally this process continues to meet its optimum result. The main programs of the proposed method have been implemented in MATLAB while analog circuits are simulated by HSPICE software. To show the capability of this method, its proficiency will be examined in the optimization of analog integrated circuits design. In this paper, an analog circuit sizing scheme -Optimum Automated Design of a Temperature independent Differential Op-amp using Widlar Current Source- is illustrated as a case study. The computer results obtained from implementing this method indicate that the design specifications are closely met. Moreover, according to various design criteria, this tool by proposing a varied set of answers can give more options to designers to choose a desirable scheme among other suggested results. MOGSA, the proposal algorithm, introduces a novel method in multi objective optimization on the basis of Gravitational Search Algorithm in which the concept of âPareto-optimalityâ is used to determine ânon-dominatedâ positions as well as an external repository to keep these positions. To ensure the accuracy of MOGSA performance, this algorithm is validated using several standard test functions from some specialized literatures. Final results indicate that our method is highly competitive with current multi objective optimization algorithms.
کلیدواژه‌ها [English]
- Gravitational Search Algorithm
- Multi Objective Optimization
- Pareto front
- Optimization Tool
- Analog Integrated Circuits Synthesis
- Automated Design
مدارات مجتمع الکترونیک با معرفی سیستم‌های متمرکز بر روی یک تراشه[1]، سیستم‌های آنالوگ و دیجیتال را در کنار هم ارائه کردهاند. با اینکه بخش آنالوگ درصد کمی از کلمدار را شامل میشود، اما جزو بخش‌های حیاتی مدارات مجتمع محسوب میشود. طراحی مداراتِ بخش آنالوگ در مقایسه با قسمتهای دیجیتال از پیچیدگی بالاتری برخوردار بوده، علاوه بر هزینه بالا و زمان بَر بودن، به مهارت بالایی نیز در طراحی نیاز دارد. از اینرو، طراحی بهینه مدارات مجتمع آنالوگ را گلوگاه طراحی مدارات مجتمع الکترونیک مینامند.
طراحی مدارات آنالوگ فقط شامل طراحی توپولوژی و طرح اولیه[2] نیست، بلکه سایزبندی و مقداردهی المانها را نیز شامل میشود. از این جهت، آن را فرایندی پیچیده و چالش برانگیز میدانند. روش سایزبندی المانها اغلب فرایندی کند، خستهکننده و تکرار شونده است که میزان موفقیت آن به دانش، فراست و تجربه طراح بستگی دارد. به همین علت روشهای متفاوتی در طراحی خودکار مدارات مجتمع آنالوگ از سوی محققین مطرح شده است.
روشهای طراحی خودکار مدارات مجتمع آنالوگ دارای دو جنبه مهم هستند: از دیدگاه جنبه اول با به کارگیری این روشها دیگر به روشهای مکررِ دستی، کند و خستهکننده گذشته نیازی نیست و به راحتی میتوان از آنها در طراحی مدارات آنالوگ در مقیاس بزرگ استفاده نمود. همچنین دقت بالا، استفاده آسان، عمومیت، انعطاف پذیری و زمان قابل قبول طراحی از دیگر مزایای آن است. اما از دیدگاه جنبه دوم میزان پیشرفت به کارگیری روشهای طراحی خودکار مدارات آنالوگ و ابزارهای CAD موجود در این زمینه در مقایسه با مدارات دیجیتال عقبتر است و تعداد بسیار کمی از این روشها تجاری شدهاند. از این رو توسعه ابزار‌ها و ابزارهای CAD جدید برای افزایش بهره‌وری طراحی، کاهش زمان عرضه به بازار[3] و کنترل هزینه‌های طراحی مدارات مجتمع آنالوگ و سیگنال مختلط امری ضروری می‌باشد.
ابزارهای جدید طراحی خودکار مدارات مجتمع آنالوگ از دو بخش اساسی تشکیل شدهاند: بخش سنتز[4] و بخش بهینهسازی. در بخش سنتز پاسخ یا پاسخهایی به عنوان خروجی معرفی میشود، اما معمولا پاسخ ارائه شده بهترین پاسخ ممکن نبوده، ممکن است با اندکی تغییرات در آن، نتایج بهتری به دست آید. از اینرو، در بخش بهینهسازی، پاسخهای به دست آمده از بخش قبل تا حد امکان به بهترین پاسخ ممکن نزدیک میشوند.
امروزه محققان از روشهای بهینهسازی متفاوتی در ابزارهای طراحی خودکار مدارات مجتمع آنالوگ استفاده میکنند. رویکرد جدید محققین در سالهای اخیر استفاده از الگوریتمهای ابتکاری، بویژه الگوریتمهای هوش جمعی است.
بارزترین مشخصه الگوریتمهای هوش جمعی رفتارهای اجتماعی آنهاست. این الگوریتمها از اعضایی تشکیل شدهاند که رفتارهای سادهای از خود بروز میدهند، اما اثر جمعی این رفتارها به گونهای است که هوشمندی جمعی[5] را نتیجه میدهد. در الگوریتمهای هوش جمعی اعضای گروه برای رسیدن به یک هدف نهایی با یکدیگر همکاری میکنند. به طور قطع، این روش مؤثرتر از زمانی است که اعضا به صورت جداگانه عمل میکنند. بهتازگی روشهای بهینهسازی هوشجمعی، بهدلیل مشخصات عملکردی کارامد ودارا بودن زمینههای بکر فراوان در کاربردهای طراحی مدار با استقبال فزایندهای مواجه شدهاند. از جمله جدیدترین الگوریتمهای هوش جمعی میتوان به الگوریتم جستجوی گرانشی (GSA) اشاره کرد. این الگوریتم، با الهام از مفاهیم جرم و نیروی جاذبه و با شبیهسازی قوانین مربوطه ارائه شده است.
اما از آنجا که طراحی آنالوگ یک مسأله چندهدفه بوده و شاخصهای مختلف مدارات همچون بهره، پهنای باند، حاشیه فاز و توان مصرفی با یکدیگر در تعارض هستند، به آسانی نمیتوان از میان جوابهای به دست آمده، بهترین پاسخ را یافت. از اینرو، باید میان جوابهای موجود مصالحهای شایسته برقرار نمود که این مصالحه با کمک چند هدفه ساختن الگوریتم بهینهسازی میسر میشود.
در این مقاله، روش نوینی در بهینهسازی چند هدفه مبتنی بر الگوریتم جستجوی گرانشی به نام الگوریتم جستجوی گرانشی چند هدفه (MOGSA) ارائه میشود. در الگوریتم MOGSA از روش «بهینگی پَرِتو»[6] برای شناسایی موقعیتهای «غیر غالب»[7] و از یک «مخزن بیرونی»[8] به عنوان حافظهای برای نگهداری این موقعیتها استفاده میشود. برای بررسی صحت عملکرد الگوریتم MOGSA در بهینهسازی توابع چند هدفه آن را به برخی توابع آزمون استاندارد که در مقالات معتبر مورد استفاده واقع شدهاند، اعمال نموده، نتایج حاصل از آن را با سه الگوریتم بسیار پرکاربرد در بهینهسازی چند هدفه مقایسه میکنیم.
در این مقاله یک ابزار بهینهسازی جدید در طراحی خودکار مدارات مجتمع آنالوگ مبتنی بر الگوریتم نوین MOGSA پیشنهاد میشود. این ابزار قابلیت جستجوی گستردهای در بازههای از پیش تعیین شده، برای هر یک از معیارهای طراحی دارد. ابزار فوق در ابتدا با استفاده از نرمافزار شبیهساز Hspice مدار مورد نظر را شبیهسازی میکند. سپس نتایج شبیهسازی به‌وسیله الگوریتم بهینهسازی MOGSA تحت بهینهسازی قرار میگیرند و تا حصول نتیجه مطلوب این روند ادامه مییابد.
برای بررسی توانایی ابزار پیشنهادی دربهینه‌سازی طراحی خودکار مدارات مجتمع آنالوگ عملکرد آن موردسنجش قرار میگیرد. برای نمونه، یک مسأله سایزبندی مطرح میشود: «طراحی یک تقویت کننده عملیاتی مستقل از دما با استفاده از منبع جریان ویدلر کسکود و با تکنولوژی CMOS افزایشی». هدف از طراحی یافتن سایزها و مقادیر المانهای مدار، با شرط بیشینه نمودن پارامترهای خروجیِ بهره ولتاژ، پهنای باند و حاشیه فاز ودرعین حال، کمینه نمودن توان مصرفی است.
در بخش دوم مقاله روشهای سنتز و در بخش سوم روشهای بهینهسازی در طراحی خودکار مدارات مجتمع آنالوگ معرفی میشود. بخش چهارم مروری کوتاه بر الگوریتم جستجوی گرانشی دارد، سپس در بخش پنجم الگوریتم MOGSA معرفی میشود. در بخش ششم توابع استاندارد آزمون برای ارزیابی عملکرد MOGSA معرفی و نتایج مقایسات انجام شده بیان میشوند. ابزار بهینهسازی پیشنهادی در طراحی خودکار مدارات مجتمع آنالوگ در بخش هفتم معرفی میشود و در بخش هشتم توانایی ابزار پیشنهادی با طرح یک مسأله طراحی ارزیابی میشود. در نهایت، بخش نهم ضمن بحث و نتیجهگیری درباره نتایج به دست آمده مقاله را به پایان میرساند.
1- روشهای سنتز در طراحی خودکار مدارات مجتمع آنالوگ
پیشینه طراحی خودکار مدارات مجتمع آنالوگ به حدود 23 سال قبل باز میگردد[1]. ابزارهای طراحی خودکار مدارات مجتمع آنالوگ با توجه به نوع کاربرد به سه گروه: ابزارهای طراحی توپولوژی، ابزارهای طراحی طرح اولیه و ابزارهای طراحی سایزبندی تقسیمبندی میشوند. روشهای طراحی خودکار مدارات مجتمع آنالوگ ممکن است شامل یک، دو یا هر سه گروه فوق باشد.
با بررسی تحقیقات انجام شده تا به امروز میتوان روشهای متفاوت در طراحی خودکار مدارات مجتمع آنالوگ را برحسب روشهای سنتز مورد استفاده مطابق شکل (1) دستهبندی نمود.
شکل (1): نمایش دستهبندی روشهای سنتز مورد استفاده در طراحی خودکار مدارات مجتمع آنالوگ
1-1- روشهای مبتنی بر دانش
روش مبتنی بر دانش[9]نخستین بار در برنامه‌هایی همچونBLADES ]2[، IDAC ]3[، OASYS ]4[، MDAC/ALSC [6-5] ارائه شد. روش مبتنی بر دانش با توجه به توپولوژیهای از پیش ذخیره شده در حافظه برنامه، چگونگی سایزبندی اجزای مداری را برای رسیدن به پاسخ بهینه مسأله طراحی، توصیف میکند. برای مثال ابزار IDAC یک ابزار طراحی متعامل[10] است که در آن کاربر این امکان را دارد تا از میان توپولوژیهای تعریف شده در برنامه، توپولوژی مورد نظر خود را انتخاب نماید. سپسIDAC مقادیر پارامترهای طراحی توپولوژی فوق را ارائه میدهد و کاربر می‌تواند بهترین مدار سایزبندی شده را انتخاب نماید، اما OASYS بر اساس کتابخانه‌ای از توپولوژیهای طراحی به شکل سلسله مراتبی ساخته شده است. در ابتدا یک توپولوژی مداری بر مبنای قوانین ابتکاری تعیین میشود، سپس توسط ابزار طراحی سایزبندی میگردد. چنانچه ابزار طراحی قادر نباشد با طراحی مدار فوق به مشخصات خواسته شده مدار دست یابد، برنامه توپولوژی دیگری را آزمایش میکند.
1-2- روشهای مبتنی بر بهینهسازی
روشهای مبتنی بر بهینهسازی[11] برای سنتز طراحی خودکار از یک موتور بهینهسازی به جای یک توپولوژی طراحی استفاده میکند. فرآیند بهینهسازی روالی تکرار شونده است که در هرتکرار متغیرهای طراحی بروزرسانی میشوند. این فرایند تا زمانی که آنها به یک نقطه تعادل برسند، ادامه مییابد. در باب ارزیابی عملکرد نیز، موتور ارزیابی معمولا با استفاده از روشهای بهینهسازی مبتنی بر معادله، بهینهسازی مبتنی بر شبیهسازی یا بهینهسازی مبتنی بر رفتار پیاده سازی میشود.
روشهای مبتنی بر معادله از معادلات طراحی تحلیلی برای ارزیابی عملکرد مدارات استفاده میکنند. این معادلات به صورت دستی یا خودکار توسط ابزارهای تحلیل نمادین[12] ایجاد میشوند. سپس مسأله به عنوان یک مسأله بهینهسازی فرمولبندی شده و معمولا با استفاده از روش الگوریتم عددی حل میشود. از معروفترین برنامههای طراحی خودکار مدارات آنالوگ که از روش مبتنی بر معادله در آنها استفاده شده است، میتوان به Opasyn ]7[، Stalk ]8[، Maulik ]9[، Astrx/Oblx ]10[، Amgie ]11[، GPCAD ]13-12[ و Sd-Opt ]14[ اشاره نمود.
روشهای بهینهسازی مبتنی بر شبیهسازی، همچون Fridge ]15[، Delight.Spice ]16[، FASY ]17[، Anaconda ]18[، Maelstrom ]19[ و Darwin ]20[ از اشکال مختلف شبیهسازی برای ارزیابی عملکرد مدار استفاده میکنند. به طورکلی، این دسته از روشها در تعیین عملکرد بهینه مدار، از نوعی ابزار تحلیلی مدار در حلقه داخلی پروسه بهینهسازی، استفاده میکنند.
1-3- مقایسه انواع روشهای سنتز
با توجه به نوع روش سنتز به کار رفته در ابزارهای طراحی خودکار مدارات مجتمع آنالوگ، میتوان آنها را از نظر کیفیت و کمیت معیارهای مورد نظر مقایسه کرد.
زمان محاسبات وابستگی شدیدی به طبیعت موتور ارزیابی دارد. در روشهای مبتنی بر دانش، با توجه به اینکه نقشه طراحی از قبل تعریف شده، سرعت اجرای آن از دیگر روشها بیشتر است. روشهای مبتنی بر مدلسازی که از معادلات عددی یا برخی روشهای یادگیری ماشین مصنوعی مشتق میشوند، قادرند خیلی سریع به پاسخ برسند اما کیفیت نتایج تخمین زده شده فقط به دقت مدلها وابسته است. در روشهای مبتنی بر شبیهسازی که از شبیهسازهای مداری خیلی دقیقی استفاده میکنند، نتایج با کیفیت بسیار خوبی ارائه میشود، اما زمان اجرا طولانی‌تر است [21].
2- روشهای بهینهسازی در طراحی خودکار مدارات مجتمع آنالوگ
پس از سنتز مدارات مجتمع آنالوگ به وسیله ابزارهای طراحی خودکار، پاسخ یا مجموعه پاسخهایی به عنوان خروجی ارائه میشود، اما معمولا پاسخ ارائه شده بهترین پاسخ ممکن نبوده، ممکن است با اندکی تغییرات در آن، نتایج بهتری به دست آید. از این رو، در سالهای اخیر محققان به این سو متمایل شدند تا با ورود روش های بهینهسازی به ابزارهای طراحی خودکار، پاسخهای به دست آمده را تا حدامکان به بهترین پاسخ ممکن نزدیک نمایند.
امروزه محققان از روشهای بهینهسازی متفاوتی در ابزارهای طراحی خودکار مدارات مجتمع آنالوگ استفاده میکنند. با توجه به مطالعات فراوان انجام شده در این زمینه میتوان آنها را به سه دسته کلی تقسیمبندی نمود]22[: روشهای ریاضی، روشهای ابتکاری و روشهای فازی. در شکل (2) روشهای بهینهسازی که تاکنون در طراحی خودکارمدارات مجتمع آنالوگ استفاده شده، نمایش داده شدهاند. در اینجا به فراخور موضوع بر روی روشهای ابتکاری که تاکنون در طراحی مدارات مجتمع آنالوگ استفاده واقع شدهاند، متمرکز و برخی از انجام شده معرفی میشوند (برای مطالعه جامع‌تر در این زمینه می‌توانید به مرجع ]22[ رجوع کنید)
|
|
شکل (2): نمایش تقسیمبندی روشهای بهینهسازی مورد استفاده در طراحی خودکار مدارات مجتمع آنالوگ
2-1- الگوریتمهای تکاملی در طراحی خودکار مدارات مجتمع آنالوگ
در ابتدا از الگوریتم ژنتیک فقط برای بهینهسازی مدارات خطی آنالوگ استفاده میشد، اما پس از مدتی الگوریتم ژنتیک به عنوان یک روش بهینهسازی کارامد در ابزارهای طراحی خودکار مدارات مجتمع آنالوگ استفاده شد که از آن جمله میتوان به Darwin ]20[، Menozzi ]23[،Rajagopal ]24[، DELIGHT.SPICE ]16[، Puhan ]25[ در گذشته و از جمله جدیدترین آنها میتوان به Nicosia ]26[، Popuri ]27[، Liu ]28[،Li ]29[، Barros ]21[،گلمکانی ]30[ و بابایان ]31[ اشاره کرد.
از برنامهنویسی ژنتیک نیز در بهینهسازی ابزارهایی چون Koza ]32[، Ryose ]33[، Wang ]34[ و Streeter ]35[ استفاده شده است. از دیگر الگوریتمهای تکاملی که در بهینهسازی طراحی خودکار مدارات مجتمع آنالوگ استفاده شدهاند، الگوریتم ایمنی مصنوعی است که از آن جمله میتوان به Kalinli ]36[ و Norihiro ]37[ اشاره نمود.
2-2- الگوریتمهای تصادفی در طراحی خودکار مدارات مجتمع آنالوگ
نخستین بار در سال 1990 برنامه بهینهسازی طراحی مدارات آنالوگ به نام Optiman ]38[ با استفاده از الگوریتم بازپخت شبیهسازی شده ارائه شد. از آن زمان به بعد، این الگوریتم به عنوان یک روش بهینهسازی در ابزارهای طراحی مدارات مجتمع آنالوگ استفاده شد. برنامههای Yang ]39[، Gbopcad ]40[، Girardi ]41[ وSevero ]42[ از آن جمله هستند.
برای نخستین بار در سال 1990 مقاله‌ای به نام «جستجوی تابو و بهینه سازی طراحی» ارائه شد [43] که مکانیسم جستجوی تابو را با استفاده از مثال‌های ساده توضیح داده و یک مسأله طراحی مدار الکترونیک ساده را بیان کرده است، اما پس از آن استفاده از الگوریتم جستجوی تابو در طراحی مدارات الکترونیک با استقبال بسیار کمی روبه‌رو شد.
2-3- الگوریتمهای هوش جمعی در طراحی خودکار مدارات مجتمع آنالوگ
سال 2001 برنامهای به نام جعبه ابزار MatlabTM ارائه شد که در آن از الگوریتم بهینهسازی کلونی مورچهها برای طراحی مدارات آنالوگ ساده استفاده میشد [44]. پس از آن، محققان تمایل چندانی به استفاده از الگوریتم ACO در طراحی مدارات آنالوگ از خود نشان ندادند.
سابقه اولین استفاده از PSO در طراحی مدارات مجتمع آنالوگ به سال 2003 بر میگردد و از آن زمان برای بهینهسازی جنبههای مختلف طراحی مدارات مجتمع VLSI، RF، تقویت کننده های CMOS با باند گسترده و ... در طراحی مدارات مجتمع مورد توجه قرار گرفته است، از آن جمله میتوان به Park ]45[، Min Chu ]46[، Mandal ]47[،Fakhfakh ]48[ و Thakker Rajesh ]49[ اشاره نمود.
2-4- مقایسه انواع الگوریتمهای ابتکاری
در سالهای اخیر از میان الگوریتمهای ابتکاری، الگوریتمهای تکاملی و بخصوص الگوریتم ژنتیک و نسخههای ارتقا یافته آن به طور گستردهای در طراحی خودکار مدارات مجتمع آنالوگ به کار رفته است. حجم وسیع تحقیقات انجام گرفته، پاسخهای قانع کننده و تجاری شدن برخی از این تحقیقات سندی گویا بر ادعای کارامدی استفاده از الگوریتم ژنتیک در بهینهسازی طراحی مدارات مجتمع آنالوگ است.
اما به علت پیچیدگیهای ساختاری الگوریتم ژنتیک، طراح به سادگی نمیتواند از آن استفاده نماید و گاه در تنظیم برخی پارامترهای آن دچار سردرگمی میشود. از این رو، ترجیح میدهد از الگوریتمهایی با ساختار داخلی ساده‌تر اما در عین حال کارا بهره گیرد.
تحقیقات جدید محققان در زمینه طراحی خودکار مدارات مجتمع آنالوگ نشان میدهد که تمایل به استفاده از الگوریتمهای هوش جمعی در حال افزایش است. ساختار ساده، همگرایی سریع و وجود زمینههای تحقیقی فراوان در این حوزه را شاید بتوان از جمله دلایل استقبال محققان از این نوع الگوریتمها دانست. از جمله جدیدترین الگوریت‌های هوش جمعی میتوان به الگوریتم جستجوی گرانشی (GSA) اشاره نمود.
3- الگوریتم جستجوی گرانشی
الگوریتم جستجوی گرانشی درسال 2009 از سوی خانم راشدی [50] معرفی شد. این الگوریتم با شبیهسازی قوانینی شبیه به قانون گرانش و حرکت نیوتن در محیطی با زمان گسسته در فضای جستجو، طراحی شده است.
مطابق قانون نیوتن هرجسم به جسم دیگر نیرویی وارد میکند که این نیرو با جرم خود جسم و معکوس مجذور فاصله تا جسم دیگر متناسب است. بنابراین، جرم‌های بزرگتر نیروی بیشتری بر جرم‌های کوچکتر وارد میکنند و برعکس جرم‌های کوچکتر نیروی کمتری بر جرم‌های بزرگتر وارد میکنند.
با توجه به قوانین فیزیکی هر جسم بر اثر نیرویی که به آن وارد میشود، دارای شتاب و در نتیجه سرعتی هم جهت با آن نیرو میشود. بنابراین، جرم‌های کوچکتر به علت آنکه نیروی اعمالی بر آنها بسیار بیشتر است، به سمت جرم‌های بزرگتر حرکت میکنند. بدین ترتیب، اگر نقاط بهینه را محل اجرام بزرگتر در نظر بگیریم، با استفاده از قانون گرانش می‌توانیم این اطلاعات را به بقیه اجرام منتقل کنیم و آنها را به سمت نقاط بهینه سوق دهیم.
ویژگیهای مثبت الگوریتم GSA همچون همگراییِ سریع، عدم توقف در بهینههای محلی، کاهش حجم محاسباتی نسبت به الگوریتمهای تکاملی و عدم نیاز به حافظه در مقایسه با دیگر الگوریتمهای خانواده هوش جمعی، بستر جدیدی از تحقیقات را فرا روی محققان قرار داده است. از اینرو، با توجه به زمینههای کاربردی مورد استفاده، نسخههای متفاوتی از الگوریتم GSA ارائه شده است که میتوان به الگوریتم جستجوی گرانشی باینری[13] (BGSA) ]51[ و الگوریتم جستجوی گرانشی نخبهگرای پیشرفته[14] (AEGSA) ]52[ اشاره کرد. از این الگوریتم در حوزههای مختلف بهینهسازی از جمله طراحی فیلتر]53[، انتخاب ویژگی ]54[، جبران سازی توان راکتیو ]55[، فشردهسازی تصاویر ]56[، طبقهبندی دادهها ]57[ و ... استفاده شده است. با توجه به مزایای الگوریتم GSA که در بالا به آن اشاره شد، بر آن شدیم تا از قابلیتهای این الگوریتم در بهینهسازی مسائل چند هدفه نیزاستفاده نماییم. در ادامه الگوریتم MOGSA معرفی میشود.
4- معرفی الگوریتم MOGSA
در الگوریتم MOGSA از بهینهسازی پَرِتو برای شناسایی موقعیتهای «غیر غالب» و از یک «مخزن بیرونی» برای نگهداری این موقعیتها استفاده میشود.
در این الگوریتم، ابتدا جمعیت اولیهای از اجرام به شکل تصادفی انتخاب میشود. در هر مرحله پس از محاسبه توابع برازندگی، بهترین اجرام در یک مخزن بیرونی شامل جوابهای پَرِتو نگهداری میشوند. سپس با توجه به موقعیت بهترین و بدترین اجرام در هر تکرار، موقعیت اجرام برای تکرار بعدی الگوریتم بروزرسانی میشود. این الگوریتم با نرمافزار Matlab پیادهسازی شده است.
الگوریتم MOGSA شامل مراحل زیر است :
1) مشخص نمودن ابعاد مسأله (n) و تعداد اجرام موجود در فضای پاسخ (m)
2) ایجاد جمعیت اولیه (Xi)
در این مرحله جمعیت اولیهای شامل موقعیت m جرم، به طور کاملا تصادفی ایجاد میشود:
|
(1) |
|
|
|
3) تعیین سرعت اولیه هر یک از اجرام: در این قسمت سرعت اولیه صفر برای هر یک از اجرام تعیین میشود:
|
(2) |
4) مقداردهی پارامترهای ثابت گرانش ( a وb ).
5) ایجاد حلقه جستجو for برای T مرتبه تکرار:
این حلقه مهمترین بخش اجرایی الگوریتم MOGSA است و به مدت T مرتبه تکرار اجرا میشود. شایان ذکر است در صورتی که بدترین موقعیت یک جرم با بهترین موقعیت آن برابر شود، اجرای این حلقه متوقف میشود.
- i. ارزیابی برازندگی هر یک از اجرام جمعیت توسط توابع برازندگی.
|
(3) |
|
|
|
F=تعداد اهداف مسأله |
- ii. اعمال شروط «بهینهسازی پَرِتو» و ذخیرهسازی موقعیتهای اجرام «غیر غالب» در یک مخزن.
- iii. تعیین موقعیت بهترین وبدترین جرم برای هر یک از توابع هدف.
|
(4) |
|
|
(5) |
|
- iv. نسبت دادن جرم سنگینتر به عاملهای با شایستگی بیشتر به تفکیک هر یک از توابع هدف.
|
(6) |
- v. نرمالیزاسیون اجرام به تفکیک هر یک از توابع هدف و تشکیل ماتریس اجرام.
- vi.
|
(7) |
- vii. محاسبه ماتریس شتاب اجرام.
- بروزرسانی سرعت اجرام: R1یک عدد تصادفی در بازه ]1-0[ است.
|
(8) |
- ix. موقعیتیابی جدید اجرام.
|
(9) |
- x. ذرات باید به گونهای در فضای جستجو نگهداری شوند تا خارج از حدود مرزهای فضای جستجو قرار نگیرند.
- xi. بروزرسانی محتویات مخزن: این بروزرسانیها شامل جادادن همه موقعیتهای غیرغالب فعلی در مخزن است. به طور همزمان «هر موقعیت مغلوب شده در فرایند از مخزن حذف میشود».
- xii. کنترل حجم مخزن: از آنجایی که ظرفیت مخزن محدود است، هر زمان که ظرفیت مخزن به حد نصاب رسید، لازم است «ابرمکعبهایی» در مناطق مرور شده فضای پاسخ تولید شوند و اجرام با توجه به مختصاتشان درون این ابرمکعبها قرار گیرند. سپس اَبرمکعب حاوی بیشترین تعداد اجرام شناسایی شده و نقاط مازاد برظرفیت مخزن به طورتصادفی حذف میشوند.
- پایان حلقه
5- سنجش عملکرد الگوریتم MOGSA و مقایسه نتایج
برای بررسی توانایی MOGSA در بهینهسازی توابع چندهدفه، آن را به برخی توابع آزمون استاندارد اعمال میکنیم. توابع آزمونی که در اینجا معرفی میشوند، توابعی هستند که توسط آقای CoelloCoello برای ارزیابی عملکرد الگوریتم MOPSO به کار رفتهاند ]58[. برای مقایسه الگوریتمها با یکدیگر ازمعیاری استفاده میکنیم که توسط Zitzler معرفی شده است]59[ :
|
(10) |
در رابطه بالا 12Y', Y Y "> مجموعه بردارهای هدف هستند که با یک جفت از بردارهای تصمیم غیر غالب به ترتیب 12X', X X"> متناظر هستند. Xنیز متناظر با متغیرهای تصمیمگیری مسأله است. فاصله میانگین را برای مجموعه بهینه پَرِتو میدهد. بنابراین، در بهینهسازی توابع چندهدفه در مواجه با توابع آزمون، هدف مینیمم کردن این مقدار است. از دیدگاه معیار الگوریتم MOGSA با سه الگوریتم بسیار پرکاربرد در بهینهسازی چند هدفه مقایسه شده است: الگوریتم MOPSO ]58[، الگوریتم NSGA-II ]60[ و الگوریتم PAES ]61[.[15] اما لازم است توضیح داده شود که در این مقاله از نظر زمان اجرا، الگوریتمها با یکدیگر مقایسه نشدهاند. چون الگوریتم MOGSA با کُد Matlab نوشته شده است، نمیتوان آن را با الگوریتمهای فوق که توسط کد C پیادهسازی شدهاند، مقایسه نمود. مشخصات الگوریتمهای مورد مقایسه در جدول (1) آمده است.
جدول (1): مشخصات الگوریتمهای مورد مقایسه
|
Value |
Specific |
Algorithm |
|
200 |
Population Size |
NSGA-II |
|
0.8 |
Crossover Rate |
|
|
tournament |
Selection Type |
|
|
1/vars (vars=number of decision variable) |
Mutation Rate |
|
|
5 |
Depth |
PAES |
|
200 |
Archive Size |
|
|
1/L (L=Length of the chromosomic string that encodes the decision variables) |
Mutation Rate |
|
|
40 |
Particles Population |
MOPSO |
|
200 |
Repository Size |
|
|
30 division |
Adaptive Grid |
|
|
40 |
Masses Population |
MOGSA |
|
200 |
Repository Size |
|
|
30 |
Adaptive Grid |
|
|
40 , 100 |
a , b |
- تابع آزمون 1
نخستین تابع آزمون در زیر بیان شده است:
|
(11) |
|
|
|
|
|
(12) |
|
|
(13) |
این مسأله جبهه پَرِتو ناپیوسته دارد و شامل چهار منحنی پَرِتو است. میانگین معیار حاصل از اجرای الگوریتمهای فوق در ستون اول جدول (2) آمده است. در این آزمون تمام نتایج برای 4000 بار تکرار هر الگوریتم آورده شده است.
- تابع آزمون 2
دومین تابع آزمون در زیر بیان شده است:
|
(14) |
|
|
(15) |
|
|
(16) |
این مسئله نیز جبهه پَرِتو ناپیوسته دارد. میانگین معیار حاصل از اجرای الگوریتمهای فوق در ستون دوم جدول (2) آمده است. در این آزمون تمام نتایج برای 1200 بار تکرار هر الگوریتم آورده شده است.
- تابع آزمون 3
سومین تابع آزمون در زیر بیان شده است:
|
(17) |
|
|
(18) |
|
|
(19) |
این مسأله 60 جبهه پَرِتو «محلی» دارد که به راحتی می‌تواند جمعیت عاملها را جذب کند (یعنی یک مسأله‌ای چند جبههای است). میانگین معیار حاصل از اجرای الگوریتمهای فوق در ستون سوم جدول (2) آمده است. در این آزمون تمام نتایج برای 3200 بار تکرار هر الگوریتم آورده شده است.
شکلهای (3-5) جبهه پَرِتو تولید شده توسط الگوریت‌های NSGA-II، PAES، MOPSO و MOGSA را بترتیب برای نخستین، دومین و سومین تابع آزمون نشان میدهند. این اشکال توانایی الگوریتم پیشنهادی MOGSA را در یافتن پاسخهای غیر غالب و در عین حال پراکندگی مناسب پاسخها را در کنار دیگر الگوریتمهای چندهدفه پرکاربرد نشان میدهند. جدول (2) نشان میدهد روش MOGSA از نظر میانگین معیار در هر سه تابع آزمون عملکرد بسیار بهتری از الگوریتمهای تکاملی چندهدفه NSGA-II و PAES و الگوریتم هوش جمعی MOPSO دارد. با توجه به تصادفی بودن الگوریتمهای فوق، نتایجِ حاصل، میانگین 20بار تکرار هر الگوریتم است.
شکل (3): جبهه پَرِتو تولید شده توسط الگوریتمهای NSGA-II، PAES، MOPSO و MOGSA برای نخستین تابع آزمون
شکل (4): جبهه پَرِتو تولید شده توسط الگوریتمهای NSGA-II، PAES، MOPSO و MOGSA برای دومین تابع آزمون
شکل (5): جبهه پَرِتو تولید شده توسط الگوریتمهای NSGA-II، PAES، MOPSO و MOGSA برای سومین تابع آزمون
جدول (2): مقایسه میانگین معیار حاصل از اجرای الگوریتمهای NSGA-II، PAES، MOPSO و MOGSA برای سه تابع آزمون
6- معرفی ابزار بهینهسازی پیشنهادی در طراحی خودکار مدارات مجتمع آنالوگ
|
تابع آزمون 3 |
تابع آزمون 2 |
تابع آزمون 1 |
|
|
094644/0 |
001594/0 |
002536/0 |
NSGA-II |
|
259664/0 |
070003/0 |
002881/0 |
PAES |
|
0011611/0 |
0014739/0 |
002057/0 |
MOPSO |
|
001112/0 |
000215/0 |
0016138/0 |
MOGSA |
در این مقاله یک ابزار بهینهسازی جدید در طراحی خودکار مدارات مجتمع آنالوگ پیشنهاد میشود. در این ابزار، ابتدا پاسخهای مورد نظر از طریق شبیهسازی به دست آمده، سپس به وسیله الگوریتم MOGSA تحت بهینهسازی قرار میگیرند.
فلوچارت کلی این ابزار در شکل (6) نشان داده شده است. برنامههای اصلی آن با نرمافزار Matlab نوشته شده و شبیهسازی مدارات توسط نرمافزار Hspice انجام شده است.
در ابزار پیشنهادی ابتدا توسط الگوریتم MOGSA ، به طور کاملا تصادفی تعدادی پاسخ کاندید از میان بازههای از پیش تعیین شده طراحی انتخاب و برای سایزبندی مدار مورد نظر ارائه میشود. سپس پاسخهای پیشنهادی توسط نرمافزار Matlab به فایل ورودی .sp نرمافزار Hspice منتقل میشود. نرمافزار Hspice مدار مورد نظر را با توجه به پاسخهای پیشنهاد شده به آن شبیهسازی و مقادیر خروجیِ بهره، پهنای باند، حاشیه فاز و توان مصرفی را در فایل خروجی .lis ذخیره میکند. سپس نرمافزار Matlab این مقادیر خروجی را از فایل .lis استخراج میکند.
|
خیر |
|
بله |
|
فایل .sp را باز کن و سایزهای پیشنهادی را وارد نما |
|
نرمافزار Hspice را اجرا کن |
|
مخزن |
|
فایل .lis را بازکن و مقادیر بهره، پهنای باند، حاشیهفاز و توان مصرفی را بخوان |
|
شروع |
|
مقداردهی اولیه سایز المانهای مدار مورد نظر به طور تصادفی |
|
اِعمال فرآیند بهینهسازی توسط الگوریتم MOGSA |
|
محاسبه سایزهای جدید برای تکرار بعدی الگوریتم |
|
اِعمال معیارهای طراحی بر محتویات مخزن |
|
ارائه محتویات موجود در مخزن |
|
آیا تعداد تکرارها به حد تعیین شده رسیده است؟ |
|
پایان |
|
بروز رسانی جبهه پَرِتو |
شکل (6): فلوچارت ابزار بهینهسازی پیشنهادی
در ادامه، مقادیر خروجی حاصل از شبیهسازی Hspice که در شرایط بهینگی پَرِتو صدق میکنند انتخاب و در یک مخزن بیرونی نگهداری میشوند. سپس الگوریتم MOGSA با اجرای فرایند بهینهسازی بر روی پاسخهای اولیه، پاسخهای جدیدی را برای تکرار بعدی الگوریتم آماده میکند. این فرایند برای تعداد معینی از تکرارها اجرا میشود تا در نهایت با توجه به مقادیر خروجی بهره، پهنای باند، حاشیه فاز و توان مصرفی به دست آمده به بهترین سایز بندی ممکن برای المانهای مدار مورد نظر دست یابیم.
7- ارزیابی ابزار پیشنهادی
برای بررسی توانایی ابزار پیشنهادی در طراحی خودکار مدارات مجتمع آنالوگ عملکرد آن سنجش میشود. در اینجا برای نمونه، یک مسأله سایزبندی مطرح میشود: «طراحی یک تقویت کننده عملیاتی مستقل از دما با استفاده از منبع جریان ویدلر کسکود با تکنولوژی CMOS افزایشی». برنامههای ابزار پیشنهادی توسط لپ‌تاپ Core™ 2 Due 2.26 GHz اجرا شده است.
7-1- شرایط مسأله نمونه
در مسأله نمونه طراحی، از ساختار پیشنهادی در شکل (7) استفاده میشود. در این تقویت کننده از یک منبعجریان ویدلر کسکود به عنوان منبع جریان بایاس ورودی، یک ترانزیستور (M11) در ناحیه Triode برای افزایش حاشیه فاز و پهنای باند، و خروجی کلاس AB برای افزایش ماکزیمم نوسان‌های متقارن در خروجی بهره گرفته شده است. مشخصات تقویت کننده عملیاتی مورد نظر در جدول (3) آمده است.
جدول (3): مشخصات طراحی تقویت کننده عملیاتی مسئله نمونه
|
Required |
Specification |
|
> 30K |
Dc Gain |
|
>10MHz |
Unity Gain Bandwidth |
|
>70 |
Phase Margin |
|
as low as possible |
Power Dissipation |
|
+5V & -5V |
VDD & VSS |
در طراحی مدار فوق فقط اندازه مقاومت و ترانزیستورهای مربوط به منبع جریان ویدلر کسکود ثابت در نظر گرفته شده است، اما مقادیر بقیه المانها جزو پارامترهای طراحی مدار هستند که توسط ابزار طراحی پیشنهادی به دست میآیند. این پارامترها عبارتند از:
* مقدار L و W/L ترانزیستورهای M1 و M2
* مقدار L و W/L ترانزیستورهای M3 و M4
ترانزیستورهای فوق دو به دو مشابه‌اند.
* مقدار L و W/L ترانزیستور M5-M13
* مقدار خازن جبران ساز CC
برای افزایش سرعت همگرایی الگوریتم بهینهسازی مناسب است که محدوده مجاز تغییرات پارامترها توسط طراح مشخص شود، زیرا در هنگام اجرای الگوریتم، پس از شبیهسازی مدار ابتدا بررسی میشود که تمام ترانزیستورها بجز M11 در ناحیه فعال حضور دارند. در غیر این صورت آن جواب در تکرارهای بعدی حذف میشود (ترانزیستور M11 در ناحیه Triode عمل میکند). پارامترهای خروجی مورد نظر عبارتند از: بهره ولتاژ، پهنای باند، حاشیه فاز و توان مصرفی که به عنوان توابع برازندگی در الگوریتم بهینهسازی چندهدفه استفاده میشوند.
7-2- نتایج طراحی ابزار پیشنهادی
مشخصات الگوریتم MOGSA در ابزار پیشنهادی برای بهینهسازی فرایند طراحی مسأله نمونه در جدول (4) آمده است.
پس از 200 بار تکرار اجرای الگوریتمِ بهینهسازی، تعداد کل پاسخهایی که توسط ابزار پیشنهادی بررسی شد، شامل 4000 پاسخ شد که از این میان 163 پاسخ دارای شرایط بهینگی پَرِتو بوده، وارد مخزن میشوند. از میان پاسخهای درون مخزن نیز 142 پاسخ محدودیتهای موجود در طراحی مدار مورد نظر را برآورده میکنند. مدت زمان مورد نیاز برای عملکرد ابزار پیشنهادی فقط به تعداد اجراهای Hspice وابسته بوده، حدود 1174 ثانیه (کمتر از 20 دقیقه) برآورد شد.
شکل (7) : ساختار پیشنهادی تقویت کننده مسأله نمونه طراحی
.جدول (4): مشخصات پارامترها در ابزار بهینهسازی پیشنهادی با الگوریتم MOGSA
|
Value |
Algorithm Setup |
|
20 |
Population of Masses |
|
21 |
Number of Input Parameters |
|
4 |
Number of Output Parameters |
|
200 |
Number of Iterations |
|
20 |
a |
|
100 |
b |
|
200 |
Content of Repository |
نتایج نهایی حاصل از عملکرد ابزار بهینهسازی پیشنهادی در سایزبندی خودکار المانهای مدار مورد نظر در جدول (5) آورده شده است. در شکلهای (10-8)، مقادیر توابع برازندگی اعضای جبهه پَرِتو و تمام پاسخهای موجود دو به دو نسبت به هم رسم شده است.
همان طور که ملاحظه میشود، جوابهای با پهنای باند بیشتر توان بیشتری مصرف میکنند (شکل (8)). تقابل میان پهنای باند و حاشیه فاز در شکل (9) و در شکل (10) نیز تقابل میان پهنای باند و بهره ولتاژ نشان داده شده است. شایان ذکر است که پاسخ 1 پاسخ به ازای بزرگترین بهره ولتاژ، پاسخ 2 پاسخ به ازای بزرگترین پهنای باند، پاسخ 3 پاسخ به ازای بزرگترین حاشیه فاز، پاسخ 4 پاسخ به ازای کوچکترین توان مصرفی و پاسخ 5 پاسخی به نسبت متناسب نسبت به تمام معیارها برای پارامترهای خروجی است.
8- نتیجهگیری
در این مقاله یک ابزار بهینهسازی جدید در طراحی خودکار مدارات مجتمع آنالوگ مبتنی بر الگوریتم MOGSA پیشنهاد شده است. این ابزار توانایی جستجوی وسیع و مؤثری در بازههای از پیش تعیین شده طراحی دارد. ابزار فوق در ابتدا با استفاده از شبیهساز Hspice مدار مورد نظر را شبیهسازی میکند، سپس نتایج شبیهسازی به وسیله الگوریتم MOGSA تحت بهینهسازی قرار میگیرند و تا حصول نتیجه مطلوب این روند ادامه مییابد.
برای بررسی توانایی ابزار پیشنهادی در بهینهسازی طراحی مدارات مجتمع آنالوگ عملکرد آن به عنوان نمونه در مسأله سایزبندی «طراحی تقویت کننده عملیاتی مستقل از دما با استفاده از منبع جریان ویدلر کسکود» مورد سنجش قرار گرفت. پاسخهای نهایی از پراکندگی مناسبی برخورداراند، همچنین، تنوع جوابهای ارائه شده که هر کدام از نظری بهینه هستند، دست طراح را در انتخاب گزینه مورد نظر باز خواهد گذاشت. یکی از ویژگیهای فوق‌العاده الگوریتم MOGSA جستجوی همه جانبه فضای مسأله است. از اینرو، در بین پاسخهای به دست آمده گاه با جواب‌هایی بسیار عالی مواجه میشویم که نسبت به دیگر الگوریتمهای بهینهسازی قابل مقایسه نیست. از دیگر ویژگیهای منحصر به فرد الگوریتم بهینهسازی MOGSA مدت زمان اجرای آن است. مدت زمان اجرای این الگوریتم نسبت به دیگر الگوریتمهای بهینهسازی در تحقیقات مشابه بسیار کوتاهتر است.
الگوریتم پیشنهادی MOGSA روش نوینی را در بهینهسازی چندهدفه مبتنی بر الگوریتم جستجوی گرانشی معرفی میکند که ضمن حفظ پراکندگی جوابها در حوزه توابع هدف از سرعت همگرایی بسیار بالایی نیز برخوردار است. این الگوریتم برای مسائل بهینهسازی که محاسبه توابع هزینه آن زمانبر است ( اکثر مسائل مبتنی بر شبیهسازی) روش مؤثرتری است. برای اطمینان از صحت عملکرد روش ارائه شده در مواجه با مسائل بهینهسازی چند هدفه، به وسیله چندین تابع استانداردِ معتبر آزمایش شده است. نتایج نهایی حاصل از مقایسه الگوریتم MOGSA با سه الگوریتم پرکاربرد نشان داد در تمام موارد الگوریتم پیشنهادی از توانایی بالاتری در بهینهسازی چند هدفه برخوردار است. از این رو، به جرأت میتوان ادعا کرد در آینده الگوریتم MOGSA رقیب سرسختی برای الگوریتمهای بهینهسازی در کاربردهای چند هدفه خواهد بود.
جدول (5): مقایسه میان محاسبات دستی و چند جواب ابزار بهینهسازی در سایزبندی خودکار مسأله نمونه
شکل (8): تقابل میان پهنای باند و توان مصرفی در مسأله طراحی، اعضای جبهه پَرِتو (الف) تمام پاسخهای موجود (ب)
شکل (9): تقابل میان پهنای باند و حاشیه فاز در مسأله طراحی، اعضای جبهه پَرِتو (الف) تمام پاسخهای موجود (ب)
شکل (10): تقابل میان پهنای باند و بهره ولتاژ در مسأله طراحی، اعضای جبهه پَرِتو (الف) تمام پاسخهای موجود (ب)
[1] System-on-Chip
[2] Layout
[3] Time-to-Market
[4] Synthesis
[5] Swarm Intelligence
[6] Pareto-Optimality
[7] Non-Dominated Positions
[8] External Repository
[9] Knowledge-based Approach
[10] Interactive
[11] Optimization-based Approach
[12] Symbolic Analysis
[13] Binary Gravitational Search Algorithm
[14] Advanced Elitist Gravitational Search Algorithm
[15] کد اصلی الگوریتمهای MOPSO، NSGA-II و PAES از نویسندگان اصلی را میتوان از مخزن نرمافزاری EMOO از آدرس زیر دانلود نمود:
)