"> استفاده از الگوریتم های ژنتیک برای چیدمان مدارهای چاپی

استفاده از الگوریتم های ژنتیک برای چیدمان مدارهای چاپی

الگوریتم های ژنتیک

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

الگوریتم های ژنتیک

الگوریتم های ژنتیک

شکل ۱ – چیدمان رایج اجزای مدار چاپی

نمودار UML این الگوریتم به صورت زیر در WithClass 2000 نشان داده شده است:

الگوریتم های ژنتیک

کلاس هایی که الگوریتم ژنتیک را پیاده سازی می کنند شامل کلاس های Population، Gnome و ListGnome می باشد. کلاس Node هر یک از اجزای الکترونیکی روی برد را نمایش می دهد. این کلاس برای مشخص کردن محل قرارگیری اجزا روی مدار چاپی دارای ویژگی های position و size  و ConnectingNode می باشد که تمام اجزای متصل شده را نگه می دارد. Gnomeهای این الگوریتم شامل یک لیست integer می باشد که یک گرید N X N که positionهای مرتبط را نگه می دارد، ارائه می کند. عدد integer اولی گوشه بالا سمت چپ و عدد دوم گوشه پایین سمت راست را مشخص می کند. هر integer می تواند هر عددی باشد که یک position خاص را مشخص می کند. برای مثال، Gnome ای به این شکل: ۱ ۴ ۳ ۵ ۹ ۲ ۷ ۸ ۶ ۱۱ ۱۴ ۱۰ ۱۲ ۱۶ ۱۵ ۱۳ به صورت جدول N X N زیر خواهد بود:

الگوریتم های ژنتیک

از متد TranslateNodeSetPositions برای مدیریت انتقال از آرایه به اجزای گرید استفاده می کنیم. متد TranslateNodeSetPositions در کلاس ListGnome اجزای integer آرایه را مانند شکل بالا به مجموعه ای از nodeها مرتبط در یک گرید دو بعدی تبدیل می کند. زمانی که نمایش دو بعدی nodeها را داریم، می توانیم از آن در تابع fitness برای تعیین فاصله بین nodeهای بهم متصل شده استفاده کنیم. با جمع کردن تمام فاصله های اتصال بین گره ها، به یک عدد واحد می رسیم که fitness مربوط به ژن مخصوص ما را مشخص می کند.

متد TranslateNodeSetPositions مربوط به ListGnome به شکل زیر نمایش داده می شود.


public static void TranslateNodeSetPositions(ListGenome g)
 {
 // first we need to translate the Gene array into node positions
 int currentX = 0;
 int currentY = 0;
 int maxHeight = 0; 
 // go through each item in the array and set the node collection in the form
 // to the relative position represented by the Genome Array
 for (int i = 0; i < Population.kXDimension ; i++)
 {
 for (int j = 0; j < Population.kYDimension ; j++)
 {
 // set the particular node specified by the Genome Item to the relative position on the 2D grid
 Node currentNode = ((Node)Form1.Nodes[(int)g.TheArray[i*Population.kYDimension + j]]);
 currentNode.X = currentX;
 currentNode.Y = currentY;
 currentX += currentNode.Width + 10; // now advance to next X position
 if (currentNode.Height > maxHeight)
 maxHeight = currentNode.Height;
 }
 // advance the Y Position
 currentY += maxHeight + 10;
 currentX = 0;
 maxHeight = 0; // reset max height
 }
 }

حالا که مجموعه Node Position را داریم، می توانیم براساس فاصله بین nodeهای متصل fitness را محاسبه کنیم. این کار با استفاده از متد CalculateSumNodeDistance مربوط به کلاس ListGnome انجام می شود. این متد همچنین بررسی می کند و nodeهای تکراری که بیش از یک بار در مجموع حساب شده اند، کم می کند. توجه داشته باشید که مجموع بیشتر نشانه fitness ضعیف تر می باشد.




public float CalculateSumNodeDistance()

{

TranslateNodeSetPositions(this);

// Now we can calculate sum of the distances

long sum = 0;

foreach (Node n in Form1.Nodes)

{

sum += n.SumOfSquareNodeConnections();

}

// check for unique nodes

int[] histogram = new int[Population.kLength];

foreach (int val in TheArray)

{

histogram[val]++;

}

foreach (int val in histogram)

{

// in any non unique number weight the sum heavily

if (val > 1)

sum += sum*val*val;

}

// compute the fitness of the Genome by inverting the sum (add a small value so we never get the 0 divisor error)

return 1/((float)sum + .0001f);

}

 

اولین مجموعه node ما یک مجموعه ۱۶تایی ساده است که هریک به دیگری متصل شده است:




protected void InitializeNodePopulation0()
 {
 // create 16 nodes and add them to the node collection
 Node node1 = new Node(0, 10, 50, 60, "1");
 Nodes.Add(node1);
 Node node2 = new Node(0, 10, 50, 60, "2");
 Nodes.Add(node2);
 Node node3 = new Node(0, 10, 50, 60, "3");
 Nodes.Add(node3);
 Node node4 = new Node(0, 10, 50, 60, "4");
 Nodes.Add(node4);
 Node node5 = new Node(0, 10, 50, 60, "5");
 Nodes.Add(node5);
 Node node6 = new Node(0, 10, 50, 60, "6");
 Nodes.Add(node6);
 Node node7 = new Node(0, 10, 50, 60, "7");
 Nodes.Add(node7);
 Node node8 = new Node(0, 10, 50, 60, "8");
 Nodes.Add(node8);
 Node node9 = new Node(0, 10, 50, 60, "9");
 Nodes.Add(node9);
 Node node10 = new Node(0, 10, 50, 60, "10");
 Nodes.Add(node10);
 Node node11 = new Node(0, 10, 50, 60, "11");
 Nodes.Add(node11);
 Node node12 = new Node(0, 10, 50, 60, "12");
 Nodes.Add(node12);
 Node node13 = new Node(0, 10, 50, 60, "13");
 Nodes.Add(node13);
 Node node14 = new Node(0, 10, 50, 60, "14");
 Nodes.Add(node14);
 Node node15 = new Node(0, 10, 50, 60, "15");
 Nodes.Add(node15);
 Node node16 = new Node(0, 10, 50, 60, "16");
 Nodes.Add(node16); 
 // connect the nodes one after another 1-->2-->3-->4--->5-->6-->etc.
 node1.ConnectNode(node2);
 node2.ConnectNode(node3);
 node3.ConnectNode(node4);
 node4.ConnectNode(node5);
 node5.ConnectNode(node6);
 node6.ConnectNode(node7);
 node7.ConnectNode(node8);
 node8.ConnectNode(node9);
 node9.ConnectNode(node10);
 node10.ConnectNode(node11);
 node11.ConnectNode(node12);
 node12.ConnectNode(node13);
 node13.ConnectNode(node14);
 node14.ConnectNode(node15);
 node15.ConnectNode(node16);
 }

 

زمانی که الگوریتم ژنتیک را اجرا می کنیم و بهترین ژن را پس از ۳۰۰۰ نسل نمایش می دهد، خروجی زیر را مشاهده خواهیم کرد. همان طور که می بینید، سالم ترین Gnome ممکن یک چیدمان node با کمترین فاصله بین nodeهای متصل را تولید می کند.

الگوریتم های ژنتیک

 

اگرچه حالا یک نتیجه مطلوب در اینجا داریم، اما generationها  لزوما همیشه بعد از همگرایی نتیجه مطلوبی ارائه نمی دهند، اما همان طور که در شکل بالا مشاهده می کنید همچنان تا حدودی قابل قبول هستند.

بهترین Gnome بعد از ۳۰۰۰ Generation:

۱۳ ۱۲ ۱۱ ۱۶ ۱ ۱۴ ۱۵ ۱۰ ۲ ۵ ۶ ۹ ۳ ۴ ۷ ۸ –>1.260784E-05

الگوریتم های ژنتیک

برای نشان دادن قدرت الگوریتم ژنتیک در چیدمان nodeها، کار را با مقداردهی متفاوت nodeها ادامه می دهیم. سناریوی بعدی همه nodeها را به node مرکزی یعنی شماره ۸ متصل می کند.




node1.ConnectNode(node8);
 node2.ConnectNode(node8);
 node3.ConnectNode(node8);
 node4.ConnectNode(node8);
 node5.ConnectNode(node8);
 node6.ConnectNode(node8);
 node7.ConnectNode(node8);
 node9.ConnectNode(node8);

 

بعد از اجرا برای ۳۰۰۰ Generation، تنظیمات ستاره ای را خواهیم داشت که node مرکزی را به همه nodeهای دیگر متصل کرده است.

بهترین Gnome بعد از ۳۰۰۰ Generation:

۲ ۷ ۱ ۱۰ ۴ ۸ ۳ ۱۲ ۹ ۵ ۶ ۱۵ ۱۶ ۱۴ ۱۳ ۱۱ –>1.960784E-05

الگوریتم های ژنتیک

به عنوان آخرین مثال، هر یک از دو node شماره ۱ و ۱۶ را به ۴ node دیگر متصل می کنیم.




node1.ConnectNode(node2);
 node1.ConnectNode(node3);
 node1.ConnectNode(node4);
 node1.ConnectNode(node5); 
 node16.ConnectNode(node12);
 node16.ConnectNode(node13);
 node16.ConnectNode(node14);
 node16.ConnectNode(node15);

 

این اجرا دو اسپایدر حول دو node گفته شده در صورت مسئله ایجاد می کند.

بهترین Gnome بعد از ۳۰۰۰ Generation:

۹ ۶ ۵ ۸ ۱۱ ۴ ۱ ۳ ۱۵ ۱۶ ۱۲ ۲ ۱۳ ۱۴ ۱۰ ۷ –>2.427185E-05

الگوریتم های ژنتیک

نتیجه گیری:

الگوریتم های ژنتیک ابزارهای قدرتمندی برای حل مسائل بهینه سازی هستند. چیدمان اجزای یک برد یک مثال ساده و کاربردی برای نمایش چگونگی استفاده از الگوریتم های ژنتیک می باشد. شما می توانید با اندازه گیری فاصله بین گوشه nodeها به جای فاصله بین مرکز nodeها تابع fitness را بهبود دهید. همچنین می توانید این کار را با nodeهایی با عرض و ارتفاع مختلف مانند IC های بزرگ یا ترانزیستورهای کوچک این کار را انجام دهید. کد استفاده شده در این پروژه هم می تواند با اندکی تغییر برای محیط سه بعدی نیز مورد استفاده قرار بگیرد.

  • پسورد: www.mspsoft.com
فاطمه زکایی

فاطمه زکایی هستم. فارغ التحصیل کارشناسی مهندسی نرم افزار، مدت سه سال هست که در زمینه توسعه اپلیکیشن های تحت وب و اندروید و همچنین تولید محتوای تخصصی برنامه نویسی تحت وب و اندروید در مجموعه mspsoft در خدمت شما هستم.

نوشته‌های مرتبط

دیدگاه‌ها

*
*

این سایت از اکیسمت برای کاهش هرزنامه استفاده می کند. بیاموزید که چگونه اطلاعات دیدگاه های شما پردازش می‌شوند.