بهبود نتایج درخت پوشای کمینه با الگوریتم ژنتیک تطبیقی در متلب

بهبود نتایج درخت پوشای کمینه با الگوریتم ژنتیک تطبیقی

در این پست پروژه بهبود نتایج درخت پوشای کمینه با الگوریتم ژنتیک تطبیقی (Adaptive Genetic Algorithm) در متلب را آماده کرده ایم که به توضیحاتی در رابطه با درخت پوشای کمینه پرداخته و فیلم خروجی این پروژه قرار داده شده است.

درخت های پوشای کمینه (Minimum Spanning Trees):

فرض کنید که در برنامه ریزی احداث جاده بین شهرها، می خواهیم تعدادی شهر را با جاده به هم وصل کنیم تا امکان رفتن از هر شهر به شهر دیگر با جاده های احداث شده ممکن شود. چنانچه بحث محدودیت بودجه ای مطرح باشد، بنابراین در این برنامه ریزی می خواهیم حداقل جاده را از نظر طولی احداث کنیم. در ادامه به دنبال الگوریتمی هستیم که مسائلی از این قبیل را حل کند.

اگر ارتباط بین شهرها را با گراف نمایش دهیم، گراف حاصل جهت دار (directed) نیست. چرا که با احداث یک جاده بین هر دو شهر امکان رفت و آمد از هر دو شهر در این جاده وجود دارد. در هر گراف بدون جهت، مسیر عبارت است از دنباله ای از راس ها که بین هر راس و راس بعدی آن یالی وجود داشته باشد. به گراف بدون جهت داری متصل (connected) گفته می شود که مسیری بین هر دو جفت راس وجود داشته باشد.

توضیحات بیشتر و مشاهده فیلم خروجی پروژه بهبود نتایج درخت پوشای کمینه با الگوریتم ژنتیک تطبیقی در ادامه مطلب.

چرخه ساده در درخت پوشای کمینه (simple cycle):

در هر گراف بدون جهت، مسیری از یک راس به خودش است، چنانچه حداقل شامل سه راس باشد و هیچ راس میانی تکراری نباشد.

گراف فاقد چرخه در درخت پوشای کمینه (Acyclic):

گراف فاقد چرخه گرافی غیرجهت دار است که هیچ چرخه ساده ای در آن وجود نداشته باشد. درخت (Tree) گرافی است، غیرجهت دار (undirected)، متصل (connected) و فاقد چرخه (acyclic).

این مساله به این صورت بیان می شود:

حذف یال هایی از یک گراف متصل، وزن دار و غیرجهت دار که زیرگرافی بدست آید تا همچنان تمامی راس ها متصل به هم باقی بمانند و مجموع وزن یال های باقی مانده کمینه گردد.

این مساله می تواند کاربردهای متعددی داشته باشد، مانند: ساخت جاده، ایجاد شبکه های مخابراتی، ایجاد شبکه های لوله گذاری و …

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