چکيده - يافتن مسيرهايي به چند مقصد متحرک در محيطي پويا با کمترين هزينه، کمترين تاخير زماني و بيشترين پهناي باند يکي از مسائل مهم در شبکه هاي کامپيوتري تلقي مي شود. از جمله روشهاي بکار رفته براي بهينهسازي در اين زمينه ميتوان به الگوريتمهاي ژنتيک اشاره نمود که داراي کارايي نسبتا خوبي ميباشد. مراحل کار به صورتي ميباشد که ابتدا جدول مسيريابي بوسيله جستجويي محلي ساخته شده سپس بوسيله الگوريتمهاي ژنتيک، الگوريتم تبريد تدريجي و استراتژي Multi Niche Crowding و همچنين ترکيب ابتکاري آنها با يکديگر نتايجي بهتر از روشهاي قبل و همچنين هر يک از روشها به تنهايي بدست آمده است. شبيه سازي انجام شده براساس محيطي پويا به يافتن بهترين مسيرها به مقصدها مي پردازد. نتايج نشان دهنده بهينه شدن روشهاي ترکيبي ارائه شده ميباشد. کارايي روشهاي مذکور از لحاظ مقدار برازندگي، زمان اجراي الگوريتم و تغييراتي در پارامترهاي دخيل در هر روش مورد بررسي قرار گرفته است.
كليد واژه- مسيريابي چند مقصدي پويا، الگوريتم ژنتيک، الگوريتم تبريد تدريجي،Multi Niche Crowding .
مقدمه
مهمترين نوع آدرسدهي به شکل تحويل بسته به يک مقصد تحت عنوان آدرس دهي Unicast مي باشد که بين منبع و مقصد ارتباط يک به يک برقرار مي کند. علاوه بر اين نوع آدرس، سه شکل ديگر آدرس دهي نيز وجود دارد که در آدرس دهي چند مقصدي به کار مي روند که شامل : Broadcast و Multicast و Anycast مي باشد. عملکرد اين آدرسدهي ها در آورده شده است :
شکل 1: روشهاي تحويل ديتاگرام ها
نوعي از مسيريابي چند مقصدي مورد توجه اين مقاله، پويايي شبکه بوسيله جابجايي گرهها طي زمان اجراي الگوريتمهاي بهينهسازي مي باشد. تحقيقات انجام شده بيانگر شکلي از مسئله با هدف پيدا کردن مسيرهايي بهينه به گره هاي مقصد با کمترين هزينه و تاخير ارسال بسته هاي پيغام مي باشد.
استراتژي مورد استفاده براي بهبود الگوريتم ژنتيک تغييراتي در نرخ عملگرهاي جهش به صورتي مي باشد که تنوع جمعيت در ابتدا افزايش يافته و در انتها اين تنوع کم شده و سرعت همگرايي با نرخ بالاي عملگر تقاطع افزايش يابد ]1[. روشهايي ترکيب الگوريتم هاي ژنتيک و الگوريتم تبريد تدريجي مبتني بر همين ايده مي باشند يعني به نحوي عمل مي شود که نرخ تنوع و همگرايي به جواب در الگوريتمهاي ژنتيک طي نسلها موجب بهينگي کلي شود. الگوريتم تبريد تدريجي داراي يک پارامتر مهم به نام دما مي باشد که هر چه کمتر شود به جواب بهينه نزديک خواهد شد .
يک تابع مکاشفه اي براي ترکيب اين دو الگوريتم استفاده از تناسب کاهش دما و کاهش نرخ عملگر جهش تا رسيدن به جواب بهينه مي باشد ]4[ ]5[. يکي ديگر از راه هاي ترکيب اين دو روش استفاده از زمانبندي مناسب خنک کنندگي پارامتر دما براي توليد فرد مناسب براي نسل جديد و همچنين استفاده از ايده اي ديگر با توجه به تناسب تابع محاسبه دما در الگوريتم تبريد تدريجي و تابع برازندگي در الگوريتم هاي ژنتيک مي باشد ]3[ ]7[.
از روشهاي ديگر مورد استفاده براي حفظ تنوع در جمعيت استراتژي Crowding در انتخاب و جايگزيني کروموزومها مي باشد. اين استراتژي مبتني بر انتخاب گروهي کروموزومها مي باشد به طوريکه، به تعداد Cs فرد از جمعيت به شکل تصادفي انتخاب شده و شبيه ترين عضو از داخل جمعيت با فردي از خارج جمعيت به عنوان والد انتخاب شده و عملگرهاي جهش و تقاطع روي آنها اعمال شده و دو فرزند توليد شده مي شوند. Niching ايده ديگري مبتني بر انتخاب اعضايي از کل جمعيت که شامل چند گروه بوده و شبيه ترين عضو از هر گروه با بدترين مقدار برازندگي، کانديدي براي جايگزيني خواهد بود. اکثر تحقيقات انجام شده در ترکيب اين استراتژي با الگوريتم هاي ژنتيک نشان دهنده حفظ تنوع در جمعيت مي باشد ]8[ ]9[.
در اين کار از بروز مسيرهاي منحرف از اهداف جلوگيري شده و آنچه که به عنوان هدف اين پروژه تلقي مي شود اجراي الگوريتم ژنتيک، الگوريتم تبريد تدريجي و استفاده از ايده Multi Niche Crowding و همچنين ترکيب روشهاي مذکور براي رسيدن به کوتاه ترين مسيرها به هدفها مي باشد که در نهايت کارايي اين روشهاي با يکديگر مقايسه شده است.
ساخت جدول مسيريابي
مسيرهاي منتهي به هدفها توسط يک جدول مسيرياب نگهداري مي شود، که فرايند ساخت آن بوسيله يک جستجوي محلي صورت مي پذيرد. اين جدول شامل ستونهايي براي هر هدف و سطرهايي به منظور نگهداري هر درخت مي باشد.
جدول 1: جدول مسيريابي
الگوريتم ژنتيک
الگوريتمهاي ژنتيک براساس فرايند انتخاب طبيعي و بقاء برازندگي مي باشد]7[. در بهينه سازي مسيرهاي منتهي به هدفها يک جدول مسيريابي تشکيل کروموزومي مي دهد که نشان دهنده شبکه ايجاد شده مي باشد. در اين مسئله يراي هر مسير يک کروموزوم در نظر گرفته مي شود که اولين ژن گره مبدا و آخرين آن مشخص کننده گره مقصد مي باشد.
ساختار کروموزوم
طول کروموزوم در نظر گرفته شده در اين مسئله به اندازه طولاني ترين مسير منطقي که شامل 39 ژن مي باشد .
2 * (سطر يا ستون) -1 = 39
شکل 2: ساختار کروموزوم
بنابراين مسير منتهي به اهدف، کروموزومي شامل ترتيبي از ارقام مي باشد که نمونه اي از آنها به صورت زير مي باشد:
شکل3: نمونه هايي از مسيرهاي منتهي به اهداف از مبدا يکسان
جمعيت
جمعيت در نظر گرفته شده براي اين مسئله همان جدول مسيريابي مي باشد که ساختار آن به صورت جدول1 در نظر گرفته شده است و طي نسلهاي متوالي اين جدول به سمت بهينه شدن پيش خواهد رفت. تعداد اين جمعيت برابر 100 فرض شده است .
تابع برازندگي
با توجه به اينکه مايليم برازندگي مقدار بيشتري پيدا کند، بنابراين از عکس هزينه در اين رابطه استفاده مي کنيم تا اينکه هزينه مسيرها نرخ کاهشي داشته باشد .
(1) 
CostT : مجموع هزينه مسيرهاي منتهي به هدفها از مبدا براي رکورد T از جدول مسيريابي، DelayT : مجموع تاخير زماني مسيرهاي منتهي به هدفها از مبدا براي رکورد T از جدول مسيريابي]2[. BandWidthT: مجموع پهناي باند]6[ مسيرهاي منتهي به هدفها از مبدا براي رکورد T از جدول مسيريابي.
عملگر تقاطع
نحوه عملکرد اين عملگر بر روي دو والد منتخب براي توليد فرزند به طوري مي باشد که نيمه دوم کروموزومهاي دو والد با هم تعويض مي شود با اين شرط که مسيرهاي منتتهي به اهداف دچار انحراف نشوند. بنابراين براي تعويض هر ژن کروموزوم والد، ژنهاي ماقبل و ما بعد کروموزوم والد ديگر بررسي شده تا سبب انحراف از مسير نشود. شکل ذيل نشان دهنده اعمال اين عملگر روي دو کروموزوم والد مي باشد .
شکل 4: نحوه عملکرد عملگر تقاطع
از آنجائيکه مايليم ابتدا تنوع در جمعيت حفظ شود و در انتهاي نسلها سرعت همگرايي افزايش يابد، در نيمه اول نسلها نرخ عملگر تقاطع 0.05 و در نيمه دوم اين نرخ برابر 0.44 فرض شده است .
عملگر جهش
با استفاده از اين عملگر که با نرخ معين احتمالي يک ماسک باينري را ايجاد کرده و به کل جمعيت اعمال مي نمايد, به طوريکه مقدار صفر نشان دهنده عدم تغيير ژن مورد نظر و مقدار يک سبب تغيير آن ژن خواهد شد. نکته جالب توجه در اين پروژه تغيير هدايت شده ژن ها مي باشد. از آنجائيکه مقدار هر ژن عددي بين يک تا هشت مي باشد و جهش ايجاد شده بايد با مقدار قبلي ژن متفاوت باشد و همچنين بايد رقمي انتخاب شود که سبب انحراف مسير منتهي به مقصد نشود. اين استراتژي در نشان داده شده است .
شکل 5 : نحوه عملکرد عملگر جهش
با توجه به اينکه عملگر جهش سبب تنوع در جمعيت خواهد شد و از آنجائيکه مايليم در ابتدا تنوع جمعيت حفظ شود و در انتها سرعت همگرايي افزايش يابد، نرخ عملگر جهش در نيمه اول جمعيت 0.54 و در نيمه دوم 0.15 بکار برده شده است.
استراتژي Multi Niche Crowding در الگوريتمهاي ژنتيک
برطبق اين استراتژي مراحل انتخاب و جايگزيني اصلاح شده و به صورت گروهي انجام مي شود. اين راهکار شامل دو مرحله مي باشد به طوريکه ابتدا به تعداد Cs کروموزم از جمعيت انتخاب مي شوند، از خارج اين گروه يک کروموزوم به عنوان والد اول انتخاب شده و بر اساس بيشترين شباهت با عضوي از گروه والد دوم نيز انتخاب مي شود، سپس عملگر هاي جهش و تقاطع روي اين دو والد اعمال شده و دو فرزند توليد مي شوند. مرحله دوم براي هر يک از فرزندان توليد شده انجام مي پذيرد.
همانطور که در شکل6 نشان داده شده است، کل جمعيت به Cf گروه تقسيم مي شود، شبيه ترين فرد در هر گروه با يکي از فرزند توليدي مرحله قبل انتخاب مي شود به طوريکه برداري شامل f فرد ايجاد شده که کمترين مقدار برازندگي فردي را مشخص مي کند که بايد با فرزند توليدي مرحله قبل جايگزين گردد .
شکل 6 : جايگزيني والديني با بيشترين شباهت و کمترين برازندگي
فردی براي جايگزيني انتخاب ميشود که داراي کمترين برازندگي و بيشترين شباهت (فرزند، هر يک از f گروه ) باشد.
شباهت کروموزومها بر اساس فاصله اقليدوسي کروموزوم هاي آنها به صورت تابع زير مي باشد :
X = ( x1 , x2 , . . . , xn ) , Y= ( y1 , y2 , . . . ,yn ) , n = طول کروموزوم
(2) 
براي نرمال نمودن فاصله d(x,y) مقادير اختلاف هر ژن بر طول کروموزوم تقسيم مي شود.
اين استراتژي براي حفظ تنوع در جمعيت بسيار مفيد بوده و همچنين همگرايي را تا ميزان مناسبي بهبود مي بخشد. نکته قابل توجه در اين استراتژي تنظيم مقدار کمي براي نرخ عملگر جهش بدليل عدم فرار جمعيت از هر Niche مي باشد.
الگوريتم تبريد تدريجي
براي استحکام دادن فلز و يا شيشه را تا دماي بالايي گرما داده و سپس دما را به آهستگي کاهش داده تا اينکه سبب توليد حالت کريستالي با انرژي پايين ماده شود. از همين ايده استفاده کرده و بر اساس پارامتر دما الگوريتمي به شرح زير ارائه داده مي شود. در الگوريتم زير Move Set همان جدول مسيريابي در نظر گرفته شده است.
ايجاد ليستي کاهشي از دما با مقادير بين صفر و يک . (Annealing Cooling schedule)
مقدار دهي اوليه جمعيت با عنوان Path0 و انتساب بيشترين (برازندگي Objective function) به Path0 .
ايجاد تغييري در جمعيت و ايجاد Path . (Generating Function)
اگر برازندگي Path بزرگتر از بيشتريي برازندگي باشد آنگاه برو به 5 در غير اين صورت برو به 6 .
New Path برابر Path0 مي باشد و بيشترين برازندگي مربوط به Path .
اگر (مقداري تصادفي بين صفرويكT[i] >) آنگاه Path0 برابر Path مي باشد . (Acceptance Function)
اگر نسلها به پايان رسيد برو به8 در غير اين صورت برو به3.
پايان الگوريتم تبريد تدريجي.
الگوريتم تبريد تدريجي بدليل رهايي از جواب بهينه محلي روش مناسبتري از الگوريتمهاي ژنتيک تلقي مي شود. ضمن اينکه سرعت اجراي اين الگوريتم خيلي کمتر از الگوريتم ژنتيک نيز مي باشد .
ترکيب الگوريتمهاي ژنتيک و تبريد تدريجي
ترکيب اين دو الگوريتم با يکديگر بدليل باقي ماندن ويژگيهاي خوب آنها عملي منطقي به نظر مي رسد. راهي که براي ترکيب اين دو استفاده شده است، در نظر گرفتن تناسب نرخ عملگر جهش در الگوريتم ژنتيک و همچنين پارامتر خنک کنندگي دما در الگوريتم تبريد تدريجي مي باشد. جزئيات مربوط به ترکيب اين دو الگوريتم به شرح زير مي باشد:
جمعيت و دما مقداردهي اوليه مي شوند و به تعداد نسلها گامهاي بعدي تکرار مي شوند. زوجي از والدين اتنخاب مي شوند و عملگرهاي جهش و تقاطع روي آنها اعمال مي شود. دو فرزند براي جايگزيني توليد مي شوند که با شرط زير هر يک از فرزندان مي توانند جايگزين والدي با بدترين مقدار برازندگي شوند.
(3) 
در پايان هر نسل دما با ضريب α کم شده و همچنين نرخ عملگر جهش نيز در هر ده نسل با ضريب α کم مي شود .
الگوريتم ترکيب به صورت زير مي باشد:
1: t = 0
2: initialize P(t) and temperature Tt
3: evaluate P(t)
4: while not termination-condition do
5: t = t + 1
6: select P(t) from P(t-1)
7: select individuals for reproduction from P(t)
8: repeat
9: select two unused individuals P1, P2
10: crossover & mutation; generate two children C1,C2
11: evaluate C1,C2
12: for all i = 1 to 2 do
13: if min{1,exp((fi-fworst)/Tt)}> random[0,1) then
14: accept Ci and replace the corresponding parent
15: update the new best and worst points
16: end if
17: end for
18: until all selected parents finish reproduction
19: Tt+1 = Tt × α; 0 <α <>
20: if (t%10 == 0)&& (pm > 1/n) then
21: pm = pm×α
22: end if
23: end while
T : پارامتر دما، P(t): جمعيتي از افراد در نسل t ، α : ضريب کاهش دما و نرخ عملگر جهش ، Pm: نرخ عملگر جهش .
ترکيب الگوريتمهاي ژنتيک و تبريد تدريجي با استراتژي Multi Niche Crowding
الگوريتم MNC GA با توجه به فرضيات MNC در انتخاب والدين و اعمال عملگرهاي جهش و تقاطع و همچنين توليد دو فرزند و جايگزيني با والدين و ادامه الگوريتم همانطور که در الگوريتم ژنتيک آمده است .
در الگوريتم MNC GSA روش ترکيب الگوريتمهاي ژنتيک و تبريد تدريجي مانند بخش قبل بوده و تفاوت اصلي آن در نحوه انتخاب والدين براي جايگزيني مي باشد. طبق استراتژي MNC که براساس گروهي از اعضا بوده است، در مرحله دوم الگوريتم ترکيبي ارائه شده ابتدا دو والد با استفاده از روش MNC انتخاب مي شود سپس عملگرهاي جهش و تقاطع روي آنها اعمال شده و الگوريتم ادامه مي يابد .
طبق ويژگي مهم الگوريتم MNC هر دو روش ترکيب منجر به حفظ تنوع در جمعيت طي نسلها مي شود .
نتايج
با استفاده از شبيه سازي انجام شده و بر اساس فرضيات بيان شده کارايي روشها بکار رفته از چند جنبه قابل مطالعه مي باشد که از آن جمله مي توان به مواردي اشاره نمود :
مقادير كمترين، متوسط و بيشترين برازندگي بدست آمده طي نسلها
زمان اجراي الگوريتمها
مقايسه نتايج با تغيير پارامترهاي الگوريتمها
مقدار برازندگي ميانگين طي چند بار اجرا
ابتدا به مقدار برازندگي بدست آمده طي نسلها مي پردازيم:
شکل 7: کمترين، متوسط و بيشترين مقادير برازندگي طي نسلها اجراي الگوريتم ژنتيک
شکل 8: کمترين، متوسط و بيشترين مقادير برازندگي طي نسلها اجراي الگوريتم سخت شدن تبريد تدريجي
شکل 9: کمترين، متوسط و بيشترين مقادير برازندگي طي نسلها اجراي الگوريتم ترکيبي ژنتيک و MNC
يکي ديگر از معيارهاي بررسي کارايي در ترکيب MNC و الگوريتم ژنتيک، فاکتور MNC و يا تعداد گروه مي باشد که با سه مقدار 5 ، 10 و 15 ميتوان مقادير برازندگي با هم مقايسه نمود.
شکل 10: مقايسه مقادير برازندگي براساس تعداد گروه بندي در روش MNC
شکل 11: کمترين، متوسط و بيشترين مقادير برازندگي طي نسلها اجراي الگوريتم ترکيبي ژنتيک و تبريد تدريجي
شکل 12: کمترين، متوسط و بيشترين مقادير برازندگي طي نسلها اجراي الگوريتم ترکيبي ژنتيک، تبريد تدريجي و MNC
شکل 13: مقايسه زمان اجراي الگوريتمها
شکل 14: مقايسه بهترين مقادير برازندگي روشهاي مختلف
پس از 30 بار اجراي نرم افزار شبيه سازي شده بهترين ميانگين برازندگي مربوط به روش MNC GA با مقدار 0.16 و بعد از آن روش GSA با مقدار 0.15 و روشهاي بعدي داراي برازندگي کمتري مي باشند .
نتيجه گيري
همانطور كه در اين مقاله آمده است با استفاده از الگوريتمهاي تكاملي نيز مي توان شبكه هاي كامپيوتري و يا سيستمهاي مشابه را به يك سيستم هوشمند تبديل نمود كه بهترين مسيرها را به مقصدها پيدا كند. نسخه هاي مختلف الگوريتم ژنتيك داراي خواص خوبي مي باشد اما مشكل بهينه محلي به عنوان مسئله اي جدي در آن بشمار مي رود كه انتخاب تابع برازندگي، عملگرهاي جهش، تقاطع و نحوه عملكرد هريك موجب توسعه اين الگوريتم و استفاده آن در محيطهاي پويا مي شود.
بنابر نتايج بدست آمده ترکيب الگوريتمهاي ژنتيک ، تبريد تدريجي و استراتژي Multi Niche Crowding موجب يافتن بهترين مسيرها با کمتربن هزينه، بيشترين پهناي باند و کمترين تاخير زماني خواهد شد. در واقع ترکيب اين الگوريتمها، ويژگيهاي خوب آنها را نيز تجميع مي کند. در اين راستا الگوريتم تبريد تدريجي موجب رهايي الگوريتم ژنتيک از جواب بهينه محلي مي شود و ايده Multi Niche Crowdig سبب حفظ تنوع در جمعيت خواهد شد.
مراجع
M.S. Zahrania, M.J. Loomesb, J.A. Malcolma, A.Z.M. Dayem Ullahc, K. Steinhِfeld and A.A. Albrechta,”Genetic local search for multicast routing with pre-processing by logarithmic simulated annealing”, Computers & Operations Research 35 (2008) 2049 – 2070.
Walter Cedeño and V. Rao Vemuri,” Analysis of Speciation and Niching in the Multi-Niche Crowding GA”,HEWLETT-PACKARD Research and Development 2850 Centerville Road MS-2C10 Wilmington, DE 19808-1610, Department of Applied Science University of California, Davis and Lawrence Livermore National Laboratory Livermore, CA 94550.
پست‌ها
