گراف لایه الگوریتم درخت پوشای مینیمم

گراف لایه الگوریتم درخت پوشای مینیمم – ایران ترجمه – Irantarjomeh

مقالات ترجمه شده آماده گروه کامپیوتر

مقالات ترجمه شده آماده کل گروه های دانشگاهی

مقالات

چگونگی سفارش مقاله

الف – پرداخت وجه بحساب وب سایت ایران ترجمه(شماره حساب)ب- اطلاع جزئیات به ایمیل irantarjomeh@gmail.comشامل: مبلغ پرداختی – شماره فیش / ارجاع و تاریخ پرداخت – مقاله مورد نظر --مقالات آماده سفارش داده شده پس از تایید به ایمیل شما ارسال خواهند شد.

www.irantarjomeh.com

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

چکیده

این مقاله نسبت به بررسی مشکل درخت پوشای مینیمم با محدودیت – جهش تعمیم یافته (GHMSTP) با قابلیت کاربرد در طراحی شبکه بکبون / ستون فقرات و در عین حال مقید به محدودیت های کیفیت سرویس (QOS)، که خود سبب محدود شدگی تعداد حداکثری مسیر یاب های سطح میانی در هر مسیر ارتباطاتی می شود، اقدام می نماید. احتمالات مختلف جهت مدل سازی GHMSTP، همانند برنامه خطی عدد صحیح و تقویت ناتساوی های معتبر نیز مورد بررسی قرار می گیرند. فرمول های حاصله به صورت تئوریکی، یعنی با استفاده از ویژگی راحت سازی برنامه نویسی خطی آن ها مورد مقایسه قرار می گیرند. بعلاوه، رویکردهای شاخه – و – برش بر مبنای این فرمول بندی ها ارائه شده و بر مبنای یک مطالعه محاسباتی مقایسه می شوند.

کلمات کلیدی: برنامه نویسی عدد صحیح، شاخه و برش، طراحی شبکه تعمیم یافته، محدودیت های جهش، گراف لایه ای

گراف لایه الگوریتم درخت پوشای مینیمم

۱- مقدمه

مشکلات طراحی شبکه تعمیم یافته (GNDPs) با توجه به کاربردهای آن در طراحی شبکه بکبون یا ستون فقرات با جزئیات مربوطه در خلال سالیان اخیر مورد بررسی قرار گرفته اند (همانند [۵،۶،۱۷،۲۶] و مراجع مربوطه) و ویژگی های دقیق و همچنین راه حل های ابتکاری مرتبط با آنها نیز ارائه گردیده اند. با توجه به یک گراف بدون جهت G = (V, E) با هزینه های یال غیر منفی c_e،، یک  با در نظرگیری این حقیقت توصیف می شود که مجموعه گره V به یک سری از K خوشه مجزا، ، تقسیم می شوند. یک راه حل محتمل  به صورت یک زیر گراف یا گراف فرعی G ارائه می شود که به طور دقیق اقدام به انتخاب یک گره از هر خوشه نموده و آن گره ها را بر مبنای ضروریات صرف GNDP، همانند ویژگی های مشخص شده به وسیله درخت پوشا در مورد مشکل درخت پوشای کمینه تعمیم یافته (GMSTP)، متصل می نماید،  برای کسب اطلاعات بیشتر در این خصوص به مراجع [۶،۸،۲۵،۲۷] رجوع شود، و یا همانند یک دور همیلتونی در مسئله فروشنده دوره گرد تعمیم یافته (GTSP)، برای کسب اطلاعات بیشتر در این خصوص به مراجع [۷،۲۰،۳۱] رجوع شود. هدف غالب مشخص سازی یک راه حل برای حاصل آوردن هزینه های یال حداقلی / کمینه  می باشد.

رویه های کاربردی GNDPs به طور مثال در طراحی شبکه های ستون فقرات مورد استفاده قرار می گیرند. در این راستا، خوشه ها معرف نواحی مشخص شده (همانند شهرها) هستند که هر کدام از آن ها از طریق یک شبکه محلی و احتمالات مربوط به مدل گره ها به یکدیگر متصل گردیده تا قابلیت اتصال مناسب این شبکه های محلی به وجود آید. در مواردی نیز تحمل خطا به وسیله نصب اتصالات حشو یا زاید چندان جای تامل نداشته و این حوزه عملیاتی به طور طبیعی منجر به GMSTP از قبل ذکر شده خواهد شد که با توجه به آن تعداد گسترده ای از رویکردها و راه حل های اکتشافی و دقیق در مباحث علمی اخیر مطرح شده اند همانند [۶،۱۷] و مراجع مرتبط با آن ها .

در این تحقیق، ما نسبت به بررسی گونه های جدید GMSTP اقدام می نمائیم که قابلیت تعامل با محدودیت های جانبی را داشته و به ما اجازه محدود سازی تاخیر ارتباطاتی حاصله در شبکه های متمرکز را می دهد. چندین مطالعه این موضوع را پیشنهاد نموده اند که کاهش تعداد مسیر یاب های میانجی یا یال ها در امتداد یک مسیر ارتباطاتی سبب افزایش قابلیت دسترسی و پایایی یک شبکه و همچنین کیفیت سیگنال ارسالی می شود، همانند مراجع [۲۲،۳۳]، بعلاوه به مرجع [۴] نیز رجوع شود. بعلاوه این مورد نیز مشاهده شده است که چنین قیدهایی سبب کاهش احتمال شکست بدون نیاز به در نظر گیری جایگزین های کاملاً هزینه بر آن ها نظیر شبکه های مجزای – گره – یا یال خواهد شد .

…

گراف لایه الگوریتم درخت پوشای مینیمم

۲- مدل های گراف لایه ای

فرمول های ارائه شده در این بخش از گراف لایه ای G_L = (V_L, A_L) استفاده می نمایند که قابلیت مشخص سازی فاصله گره ها و قوس ها از گره ریشه انتخابی با توجه به ساختار خود را خواهند داشت. مجموعه گره V_L متشکل از کپی های کلیه گره های u از خوشه ریشه V₁ در لایه صفر و همچنین کپی های u_h کلیه گره های u Î V/V₁ بر روی لایه های ۱ £ h £ H می باشد. قوس های (u_h, v_h+1) در مجموعه قوس A_L ارائه شده اند که در آن یک قوس (u, v) در مجموعه قوس A شامل گردیده است. بنابراین، G_L که به طور رسمی به وسیله  و  تعریف شده است به صورت غیرمدور می باشد و دارای مسیرهای طولانی تر از محدوده جهش ارائه شده H نمی باشد. شکل ۲ نشان دهنده شاخص گراف لایه ای راه حل ارائه شده در شکل ۱ برای H = 3 است. علی الخصوص برای گراف های ورودی پراکنده و به هنگام کاربرد یک رویه ایجادی مناسب یا روتین پیش پردازشی، مجموعه گره V_L نوعاً کامل نمی باشد (یعنی آنکه برخی از گره ها ممکن است در کلیه لایه ها وجود نداشته باشند). جهت ساده سازی چنین ایده ای، ما یک مجموعه گره کامل را به شرح ذیل در نظر می گیریم.

گراف لایه الگوریتم درخت پوشای مینیمم

۳- مدل های گراف خوشه لایه ای

در عین آنکه فرمول های گراف لایه ای مشابه با مورد ارائه شده در بخش قبلی بوده و به نظر در ارتباط با حل نمونه های کوچک و متوسط مشکلات طراحی شبکه مختلف نیز کارآمد می باشند (به مراجع [۱۴ـ۱۶، ۲۳] به طور مثال رجوع شود)، نقص آنها تعداد بسیار بالای متغیرهای شامل شده می باشد که سبب می گردد تا قابلیت بکارگیری آنها برای نمونه های دارای مقیاس بزرگ وجود نداشته باشد.

به منظور کاهش معنی دار تعداد متغیرها و در عین حال حفظ مزیت اصلی (یعنی کاربرد ویژگی راحت سازی برنامه نویسی خطی (LP) به واسطه محدودیت های جهش) دو مدل ILP در این بخش ارائه می شوند که بر مبنای ایده گراف خوشه لایه ای هستند که در آن صرفاً مؤلفه کلی (یعنی اتصالات بین خوشه ای) بر روی گراف لایه ای مدل سازی می شوند. به طور رسمی، این نوع از گراف خوشه ای لایه ای  بر حسب مجموعه گره آن    تعریف می گردد، به شکل ۴ رجوع شود.

گراف لایه الگوریتم درخت پوشای مینیمم

۴- مقایسه چند وجهی

در این بخش، ما نسبت به مقایسه فرمول های پیشنهادی در بخش های دو و سه و گونه های آن در وضعیت تئوریکی، یعنی با توجه به مقادیر راحت سازی LP آنها اقدام می نماییم. بنابراین، از طریق فرمول بندی M ما با استفاده از P(M) چند وجهی حاصله بر مبنای راحت سازی LP آن را مشخص ساخته و با استفاده از آن تصویر متعامد چندوجهی آن بر روی فضای  P(M)  را تعیین می نماییم. مقدار بهینه استراحت LP در ارتباط با فرمول M بر حسب v(M) Î R مشخص می گردد. فرمول بندی M₁ به صورت حداقلی از قابلیت مناسبی در مقایسه با فرمول M₂ if v(M₁) ³ v(M₂) برخوردار بوده و کاملاً قدرتمندتر ازM₂ خواهد بود آن هم در صورتی که M₁ از نقطه نظر توان همانند M₂ تلقی شده و حداقل یک نمونه وجود دارد که برای آن v(M₁) > v(M₂) می تواند معتبر باشد. M₁ و M₂ در صورتی ناسازگار خواهند بود که نمونه هایی نظیر v(M₁) > v(M₂) و همچنین نمونه هایی مثل v(M₂) > v(M₁) وجود داشته باشند. کلیه گونه های مدنظر فرمول های مختلف در جدول ۱ خلاصه شده اند. نتایج حاصله نیز در شکل ۵ خلاصه شدند، که در آن یک یال نقطه ای معرف دو فرمول غیر قابل قیاس بوده و یک پیکان توپر معرف آن می باشد که این فرمول در هدف کاملاً قویتر از این مورد در مبدأ تلقی می گردد.

ما بر روی این موضوع تأکید می کنیم که علاوه بر مقایسه فرمول های پیشنهادی، نتایج ما همچنین معرف راه حل های کسری شامل شده در یک چند وجهی می باشند که به صورت مترادف با فرمول هایی هستند که از گراف خوشه ای G_C یا گراف لایه ای خوشه ای G_CL استفاده نموده که ممکن است حاوی مسیرهایی باشند که دربردارنده بیش از H قوس هستند (با توجه به تصویر مرتبط با فضای (x, z))، که در این رابطه می توان به اثبات قضیه های ۴ـ۳ و ۴ـ۵ رجوع کرد. مورد آخری برای فرمول هایی که از هیچ کدام  از  این  دو گراف  استفاده  نمی کنند صحت ندارد.

گراف لایه الگوریتم درخت پوشای مینیمم

۵- مطالعه محاسباتی

الگوریتم های شاخه و برش (B&C) برای کلیه فرمول های پیشنهادی در بخش های ۲ و ۳ با استفاده از زبان برنامه نویسی C + + و با بکارگیری سیستم BM CPLEX 12.6 حاصل آمده است. مجموعه های استاندارد CPLEX بکار گرفته شده و هر آزمایش بر روی یک هسته واحد در داخل خوشه از کامپیوترها اعمال گردید که هر کدام متشکل از ۲۰ هسته (۳/۲ گیگاهرتز) و ۶۴ گیگابایت رم می باشند. محدوده زمان مطلق ۱۰۰۰۰ ثانیه ـ CPU برای هر آزمایش بکار گرفته شد و CPLEX نیز جهت کاربرد تا بالاترین حد ۳ گیگابایت پیکربندی گردید.

۵ـ۱٫ پیکربندی برش و شاخه

ما کلیه مدل ها را بر مبنای مجموعه های محدودیت های فشرده یا متراکم بکار گرفتیم و در عین حال گونه های مختلف مجموعه برشی جهت دار با استفاده از الگوریتم جریان ـ حداکثری Cherkassky و Goldberg مجزا شد [۲]. بنابراین، ما نسبت به اضافه نمودن برش های پشتی و تودرتو اقدام نموده و به علاوه جریان های خزش را جهت ایجاد ناتساوی های پراکنده مدنظر قرار دادیم، به مرجع [۲۱] رجوع شود. جهت اجتناب از تأثیرات متقابل در گره های شاخه و برش، ما صرفاً اقدام به جداسازی برش هایی نمودیم که قابلیت نقض گردیدن به وسیله یک مقدار حداقلی ۱/۰ در راه حل LP جاری را خواهند داشت.

۵ـ۲٫ نمونه های معیارسنجی

ما نسبت به ارزیابی عملکرد رویکرد خود با توجه به نمونه های حاصله از Fischetti و همکاران [۷] اقدام می نماییم که به طور ابتدا به ساکن برای مسئله فرشنده سیار دوره گرد پیشنهاد شده است، اما به طور گسترده ای به عنوان نمونه های محک سنجی یا معیار (به صورت مبنایی) به منظور ارزیابی عملکرد رویکردهای الگوریتمی برای مسایل مختلف طراحی شبکه تعمیم یافته نیز مورد استفاده قرار می گیرد، به مراجع [۱۸، ۱۹] رجوع شود. این مجموعه از معیارها خود حاصل آمده از TSPlib اقلیدوسی [۲۸] می باشد که برای آن دو روتین خوشه بندی مختلف (روتین جغرافیایی یا خوشه بندی گیرید) مدنظر می باشد. نمونه های دارای خوشه بندی جغرافیایی به وسیله انتخاب اولیه گره های  در فاصله حداکثری از یکدیگر ایجاد می شوند که قابلیت تعریف گره های دانه خوشه های K را خواهند داشت. کلیه گره های دیگر به خوشه حاوی نزدیک ترین گره دانه تخصیص می یابند. نمونه های مبتنی بر خوشه بندی گیرید بر مبنای مختصات گره ها در سطح مسطح (از طریق تقسیم این سطح به مستطیل ها)، و بر مبنای یک پارامتر ورودی μ، یعنی μ Î {۳, ۵, ۷, ۱۰}، ایجاد می شوند که مشخص کننده میانگین تعداد گره ها در خوشه می باشد، برای مشاهده جزئیات به مرجع [۵، ۷] رجوع شود. بنابراین، به طور کلی پنج نمونه برای هر نمونه TSPlib اصلی ایجاد شده است.

۵ـ۳٫ راه حل اولیه

آزمایشات اولیه نشان دهنده آن هستند که CPLEX قابلیت یافتن راه حل های مختلف در محدوده ۱۰۰۰۰ ثانیه ای، به جز چندین موارد نادر، را ندارد. ما همچنین مشاهده نمودیم که با توجه به یک راه حل اولیه با کیفیت منطقی، ویژگی های ابتکاری همه منظوره نوعاً از موفقیت بیشتری در ارتباط با یافتن راه حل های دارای کیفیت بالا (نزدیک به بهینه) برخوردار می باشند. بنابراین، ما در اینجا یک ویژگی صرف ابتکاری اولیه که به طور مکرر در طی دوره مرتبط با اگلوریتم شاخه و برش نام برده شده است را در نظر نگرفته، بلکه در مقابل اقدام به ایجاد یک راه محتمل (که به سیستم حل کننده تحویل خواهد شد) به شرح ذیل خواهیم نمود: در ابتدا یک گره از هر خوشه به صورت تصادفی انتخاب می گردد. متعاقباً، یک ویژگی ابتکاری نیز در نظر گرفته می شود که به صورت قابل توجه اقدام به اضافه نمودن گره برگزیده با کمترین هزینه بیشتر به درخت جزئی خواهد نمود، آن هم در صورتی که قابلیت دسترسی بدون نقض محدودیت های ـ جهشی را داشته باشد. این ویژگی برای سی بار تکرار شده و متعاقباً بهترین راه حل کلی برگزیده خواهد شد.

گراف لایه الگوریتم درخت پوشای مینیمم

 ۶- نتایج محاسباتی

جداول ۳ و ۴ ارائه دهنده یک نمای اولیه در ارتباط با نتایج حاصله راجع به مطالعه محاسباتی ما در خصوص نمونه های کوچک تر و بزرگتر به ترتیب می باشد. بنابراین، نتایج بر مبنای چهار کلاس اصلی مدل های بحث شده در بخش های قبلی گروه بندی شده اند (یعنی آیا مفهوم خوشه و / یا گراف خوشه لایه ای استفاده شده است یا خیر). هر خط مرتبط با این دو جدول مشخص کننده این موضوع هستند که تعداد نمونه های حل شده به وسیله حداقل یکی از مدل ها از هر کلاس خاص (#_solved) به چه میزان است و همچنین به چه هنگامی یک مدل از هر کلاس قابلیت حاصل آوردن بهترین عملکرد (#_best) را خواهد داشت. بنابراین، ما یک گونه دارای بهترین عملکرد را در نظر می گیریم آن هم در صورتی که قابلیت حل نمونه خاص مرتبط جهت حاصل آوردن بهینگی مشابه با حداقل هر یک دیگر از نمونه های تست شده را داشته باشد. در موردی که قابلیت حل نمونه به وسیله هرگونه در محدوده مشخص شده ۱۰۰۰۰ ثانیه ای وجود نداشته باشد، کلیه گونه ها که برای آنها شکاف بهینگی حاصله قابلیت تحصیل یک ویژگی حداقلی را دارد به عنوان موردی که می تواند بهترین عملکرد را داشته باشد مشخص می گردد. جهت تسهیل این ویژگی با توجه به تأثیر پارامترهای مختلف، هر یک از دو جدولی که این نتایج را نشان می دهند بر حسب تمامی جفت های مرتبط با سه معیار اصلی طبقه بندی می شوند (یعنی نمونه اصلی، روش خوشه بندی، محدوده جهشی) که متعاقباً در مجموعه معیارسنجی ما قرار خواهند گرفت.

گراف لایه الگوریتم درخت پوشای مینیمم

۷- نتیجه گیری

در این مقاله، ما نسبت به بررسی مسئله درخت پوشای مینیمم با محدودیت ـ جهشی تعمیم یافته (GHMSTP) اقدام نمودیم که خود در زمینه طراحی شبکه های ارتباطاتی ستون فقرات، به هنگامی که طول حداکثری مسیر نباید فراتر از یک محدوده فوقانی از قبل تعیین شده گردد، مد نظر قرار می گیرد. مدل های مختلف عددی صحیح برنامه نویسی بر مبنای فرمول بندی گراف لایه ای مورد بحث قرار گرفته اند که شامل گونه هایی هستند که قابلیت تعمیم آن ها به مفهوم یک گراف خوشه ای وجود دارد [۲۶]. چندین مورد از ناتساوی های معتبر با قابلیت تقویت ویژگی های مربوطه نیز ارائه گردیده اند و در این زمینه ویژگی سلسله مراتبی نیز با توجه به توان تئوریکی فرمول های پیشنهادی ارائه گردیده است (یعنی مقادیر راحت سازی LP آنها). نتایج مطالعه محاسباتی ما که بر روی نمونه های معیارسنجی شده انجام شده است با توجه به مسایل طراحی شبکه تعمیم یافته معرف آن هستند که رویکرد شاخه و برش با قابلیت بکارگیری نگارش لایه ای گراف خوشه ای از عملکرد بهتری در مقایسه با دیگر گونه ها برخوردار است.