ساخت درخت اشتاینر هشت وجهی کارآمد با اجتناب از موانع به کمک الگوریتم های ژنتیک

درخت بهینه اشتاینر هشت وجهی اجتناب از مانع جدید (OAOSMTN) ابزاری در طراحی فیزیکی چیپهای مجتمع با ابعاد بزرگ (VLS1)است. در این مقاله یک الگوریتم موثر برای ساخت یک OAOSMTN مبتنی بر معماری X برای یک مجموعه از پین ها و موانع ارائه شده است. اول، یک نوع الگوریتم بهینه سازی ژنتیک کلاسیک با تابع برازندگی خاص پیشنهاد می شود که به خوبی توانایی های جستجوی خود را بهبود می بخشد. دوم،تعیین هوشمندانه میزان تغییر ژن ها است، بطوریکه با استفاده از حرکات تصادفی (عمل جهش) ممکن، سبب خروج از بهینه محلی شده و مناطق امیدبخشبهتر و دقیق تر جستجو می شوند و می توان بطور متوسط 8/64% کیفیت راه حل را بهبود بخشید. تا جایی که می دانیم، این اولین باری ست که مسئله اجتناب از مانع تک لایه در معماری X به شیوه هوشمندانه حل شده است. نتایج آزمایشی نشان می دهد که الگوریتم پیشنهادی می تواند طول سیم را درحضور موانع بیشتر کوتاه کند و به بهترین کیفیت راه حل در زمان اجرایی معقول نسبت به الگوریتم های کنونی برسد.

کلیدواژه ها:

ژنتیک ، درخت اشتاینر هشت وجهی ، مانع ، لیست انتخابی ، مدارات مجتمع