بخشی از مقاله
*** این فایل شامل تعدادی فرمول می باشد و در سایت قابل نمایش نیست ***
حل مسئله درخت اشتاینر کمینه با استفاده از اتوماتای یادگیر توزیع شده
چکیده
مسئله پیدا کردن درخت اشتاینر کمینه در یک گراف وزندار عبارت است از پیدا کردن یک درخت با کمترین هزینه بر روي گراف که شامل تعدادي از گره هاي خاص به نام ترمینال باشد. این مـسئله از جملـه مـسائل NP-Complete مـیباشـد و بهمـین دلیـل الگوریتمهاي تقریبی متعددي مانند الگوریتمهاي ژنتیک و کلونی مورچهها براي آن گزارش شده اسـت. در ایـن مقالـه الگـوریتمی مبتنی بر آتاماتاي یادگیر توزیع شده براي حل مسئله درخت اشتاینر کمینه پیشنهاد میگردد. نتـایج حاصـل از آزمایـشها نـشان میدهد که الگوریتم پیشنهادي در مقایسه با روشهاي گزارش شده مانند الگوریتمهاي ژنتیکی و کلونی مورچه ها از کارایی بـالاتري بر خوردار است.
کلمات کلیدی: مسئله درخت اشتاینر کمینه، اتوماتای یادگیر ، اتوماتای یادگیر توزیع شده
-1 مقدمه
مسئله پیدا کردن درخت اشتاینر کمینه در یک گراف وزندار که از جمله مسائل NP-Complete میباشد عبارت اسـت از پیـدا کـردن یـک درخت با کمترین هزینه که شامل تعدادي از گره هاي خاص به نام ترمینال باشد. این مساله انواع مختلفی دارد. در یک نوع آن تعـدادي نقطـه بـر روي صفحه دو بعدي به عنوان ورودي ارائه میگردد و هدف، تولید درختی بر روي صفحه اقلیدسی است که داراي کمترین هزینه بوده و همه نقـاط را در بر بگیرد.[1] همین مسئله به صورت عمود بر هم1 نیز مطرح میشود که در آن باید خطوط درخت فقط به صورت عمودي یا افقی رسـم شـوند که این مسئله در طراحی فیزیکی مدارات VLSI کاربرد فراوانی دارد. شکل (1) نمونهاي از یک درخت اشتاینر کمینه عمودي- افقی را نشان مـی-دهد. نوع دیگر مسئله درخت اشتاینر در گراف است که در این مقاله نیز ما همین مسئله را مورد بررسی قرار دادهایـم. در ایـن مـسئله یـک گـراف وزندار G=(V,E) و یک زیرمجموعه از رئوس گراف (T⊆V) که مجموعه ترمینالها نام دارد ارائه میگردد و هدف پیدا کردن درخت GT=(V',E') با کمترین هزینه است که T⊆V'⊆V و . E'⊆E مسئله درخت اشتاینر داراي کاربردهـاي فراوانـی نظیـر مـسیریـابی یـک بـه چنـد در شـبکههـاي کامپیوتري,2 سیستمهاي حمل و نقل, پلیس امداد, ایستگاههاي پستی و کاربردهاي دیگر میباشد3]،.[2 شکل (2) نمونهاي از یک درخـت اشـتاینر کمینه بر روي گراف را نشان میدهد. خطوط خطچین درخت مورد نظر میباشند و رئوس توپر ترمینال هستند.
شکل (۱): درخت اشتاینر کمینه عمودی ‐ افقی
شکل (۲): درخت اشتاینر کمینه بر روی گراف
با توجه به اینکه مساله پیدا کردن درخت اشـتاینر کمینـه یـک مـساله NP-Complete میباشـد الگوریتمهـاي تقریبـی متعـددي از جملـه الگوریتمهاي ژنتیکی[4] و کلونی مورچه ها6]،[5 براي آن گزارش شده است.
در روشADH 3 از گرههاي ترمینال شروع میکنیم. هر گره ترمینال یال با کمترین هزینه مجاور خود را انتخاب میکند و با این کار جنگلـی از درختان تشکیل میشود که این جنگل در انتهاي الگوریتم شامل یک درخت خواهد بود.[3] در روش SPH4 از یک گره اولیه شروع کرده و هـر بـار یال با کمترین هزینه را به درخت موجود اضافه میکنیم. این عملیات براي همه رئوس گراف تکرار میشود و از بین درختان تولید شـده کـم هزینـه ترین درخت انتخاب میشود.[7] در روش ACS5 که مبتنی بر سیستم کولونی مورچهها است روي هر گره ترمینـال یـک مورچـه قـرار داده و هـر مورچه به صورت احتمالی یالهاي اطراف خود را انتخاب کرده و حرکت میکند. در صورت برخورد یک مورچه با مسیر مورچه دیگر آن دو مـسیر بـا هم پیوند خورده و کم کم جنگل حاصل از درختانی که مسیر مورچهها میباشد پیوند خورده و یک درخت باقی میماند6]،.[5
در این مقاله الگوریتمی مبتنی بر اتوماتاي یادگیر توزیع شده براي حل مساله درخت اشتاینر کمینه پیشنهاد میکردد. نشان داده میـشود کـه الگوریتم پیشنهادي در مقایسه با روشهاي گزارش شده مانندریتمهاي ژنتیکی، کلونی مورچه ها، روش ADH و روش SPH از کـارایی بـالاتري بـر خوردار است. آزمایشهاي بر روي یک مجموعه مسائل استاندارد که در [8] ارائه شده است انجام گرفته است..
ادامه مقاله بدین صورت سازماندهی شده است. در بخش 2 ابتدا اتوماتاهاي یادگیر و اتوماتاي یادگیر توزیع شده به طـور مختـصر شـرح داده میشود و سپس اتوماتاي یادگیر توزیع شده تعمیم یافته ارایه میگردد. در بخش 3 الگوریتم پیشنهادي شرح داده میشود و در بخـش 4 نتـایج آزمایشها ارایه میگردد. بخش نهایی مقاله نتیجه گیري میباشد.
-2 اتوماتاي یادگیر توزیع شده
در این بخش ابتدا اتوماتاهاي یادگیر و اتوماتاي یادگیر توزیع شده و سپس اتوماتاي یادگیر توزیع شده تعمیم یافته به طور مختصر شـرح داده میشود اتوماتاي یادگیر: یک اتوماتاي یادگیر یک مدل انتزاعی است که میتواند تعداد محدودي عمل یا اقدام6 را انجام دهد. هدف آتاماتـاي یـادگیر آن است که بتواند از بین یک سري اعمال مجاز, عمل بهینه را انتخاب کند. عمل بهینه عملی است که احتمال دریافت پاداش از محیط را بـه حـداکثر برساند. آتاماتا با یک محیط در تعامل است و هر عمل که توسط اتوماتاي یادگیر انتخاب میشود به محیط اعمال شده و نتیجـه آن عمـل در محـیط ارزیابی گردیده و به اتوماتاي یادگیر ارائه میگردد. اتوماتاي یادگیر از این پاسخ استفاده نموده و عمل بعدي خود را بهبود می بخشد. شکل (3) ایـن تعامل بین محیط و اتوماتاي یادگیر را نشان میدهد.
محیط: محیط را میتوان توسط سه تایی E=( α, β, c) نشان داد که در آن α = {α 1, α 2, … , α r} مجموعه ورودیها و β = {β1, β2, …, βm} مجموعه خروجیها و c = {c1, c2, … , cr} مجموعه احتمالهاي جریمه میباشد. هرگاه β مجموعـه دو عـضوي باشـد، محـیط از نـوع P میباشـد. در چنین محیطی β1=1 به عنوان جریمه و β2=0 به عنوان پاداش محسوب میشود. در محیط از نوع Q، β(n) میتواند به طور گسـسته یـک مقـدار از مقادیر محدود در فاصله [0,1] و در محیط از نوع S ، β(n) متغیر تصادفی در فاصله [0,1] است. ci احتمال آن است که عمل αi نتیجـه نـامطلوب داشته باشد. در محیط ایستا مقادیر ci بدون تغییر میمانند در حالیکه در محیط غیر ایستا ایـن مقـادیر در طـی زمـان تغییـر میکننـد. آتاماتاهـاي یادگیر به دو گروه ساختار ثابت و ساختار متغیر تقسیم بندي میگردند که به دلیل استفاده ما از آتاماتاي با ساختار متغیـر در ادامـه آن را بـه طـور مختصر شرح میدهیم.
اتوماتاهاي یادگیر با ساختار متغیر: این اتوماتاي یادگیر توسـط چهارتـایی (α, β, p, T) نـشان داده میـشود کـه در آن α = {α 1, α 2, … , α r}مجموعه عملهاي اتوماتا, β = {β1, β2, …, βm} مجموعـه ورودیهـاي اتوماتـا, p = {p 1, p 2, … , p r} بـردار احتمـال انتخـاب هـر یـک از عملهـا و p(n+1)=T[α(n), β(n), p(n)] الگوریتم یادگیري میباشد. در این نوع از اتوماتاهاي یادگیر اگـر عمـل αi در مرحلـه -nام انتخـاب شـود و پاسـخ مطلوب از محیط دریافت نماید, احتمال pi(n) افزایش یافته و سایر احتمالها کاهش مییابند و براي پاسخ نامطلوب احتمـال pi(n) کـاهش یافتـه و سایر احتمالها افزایش مییابند. در هر حال تغییرات به گونهاي صورت میگیرد که حاصل جمع pi(n) ها همواره برابر یک باقی بماند.
اتوماتاي یادگیر توزیع شده(:(DLA این آتاماتا شبکهاي از اتوماتاهاي یادگیر است که براي حل یک مسئله با یکدیگر همکاري میکنند. تعـداد اقدامهاي یک اتوماتاي یادگیر در DLA برابر با تعداد آتاماتاهاي متصل به آتاماتاي مورد نظر میباشد. انتخاب یـک اقـدام توسـط آتاماتـا در شـبکه,اتوماتاي متناطر با این اقدام را فعال میسازد. به عنوان مثال در شـکل (4) هـر اتوماتـا داراي دو اقـدام میباشـد. انتخـاب اقـدام α1 توسـط , LA 1 اتوماتاي یادگیر LA3 را فعال خواهد کرد. LA3 به نوبه خود یکی از اقدامهاي خود را انتخاب میکند که در نتیجـه آن یکـی از اتوماتاهـاي یـادگیر متصل به آن اتوماتا که متناظر با اقدام انتخاب شده میباشد فعال میشود. در هر زمان فقط یک اتوماتاي یادگیر در شبکه فعال میباشد. بطور رسمی DLA را میتوان توسط گراف DLA=(V,E) که V={LA1, LA2, …, LAn} مجموعه اتوماتاهاي یادگیر و n تعـداد آتاماتاهـا در DLA و E⊆VV مجموعه یالهاي گراف میباشد, تعریف کرد. یال (i,j) اقدام j آتاماتا LAi را نشان میدهد. LAj زمانی فعال خواهـد شـد کـه اقـدام j آتامـاتون LAi انتخاب شود. تعداد اقدامهاي آتوماتاي (k=1 ,…, n) LAk برابر درجه خروجی آن گره میباشد.[9]
شکل (۴): آتاماتای یادگیر توزیع شده
اتوماتاي یادگیر توزیع شده تعمیم یافته :(GDLA7) یک اتوماتاي یادگیر توزیع شده تعمیم یافته متناظر با یک گراف است کـه در آن مجموعه گره هاي گرافو E مجموعه یالهاي گراف و n تعداد گره هاي گراف میباشـد. هـر زیـر مجموعـه از V میتواند یک آتاماتاي یادگیر محسوب شود که در هر زمان تعدادي از این اتوماتونهاي یادگیر فعال و تعدادي غیر فعال هستند. هر آتاماتون را بـا T و مجموعه آتاماتونهاي فعال را با مجموعه S نمایش میدهیم. اگر تعداد آتاماتونهاي فعال Ti ، m باشد در ایـن صـورت کـه براي هر Ti ∈S خواهیم داشت . Ti v j1 ,v j2 ,...,v jki ; for i 1, 2,..., m
هر Ti داراي ki عضو است به طوریکه
براي هر اتوماتاي یادگیر Ti به تعداد یالهاي خروجی از مجموعـه Ti اقـدام وجـود دارد. مجموعـه اقـدامهاي هـر آتاماتـاي یـادگیر Ti بـصورت تعریف میشود.
در طول زمان هر یک از اتوماتونهاي فعال Ti (عناصر مجموعه (S یکی از اقدامهاي خود را انتخاب و سپس اعمال مینماید کـه در اثـر آن ممکن است یکی از دو حالت زیر رخ دهد.
• اعمال اقدام منجر به انتخاب راسی مانند v از گراف شود که آن راس داخل هیچ کدام از Tj هاي فعال قرار نداشته باشـد((j≠i و یـا به بیان دیگر ∀Tj ∈S ,v ∉Tj که در این حالت اتوماتاي یادگیر Ti غیر فعال شده و آتاماتایی که معادل Ti∪{v} اسـت فعـال میشود که در نتیجه تعداد عناصر مجموعه S تغییر نمیکند.
• اعمال اقدام منجر به انتخاب راسی مانند v از گراف شود که آن راس در داخل عناصر یک آتاماتاي فعال دیگر ماننـد Tj قـرار دارد و یا به بیان دیگر ∃Tj ∈S , v ∈Tj که در این حالت دو آتاماتاي Ti و Tj غیر فعال شـده و آتاماتـاي معـادل بـا Ti∪Tj فعـال میشود که در نتیجه تعداد عناصر مجموعه S یک واحد کاهش مییابد.
بدیهی است که اعضاي S در طول زمان تغییر میکنند و به مرور تعداد آنها کاهش مییابد تا بالاخره یک آتاماتاي فعال در S باقی میمانـد.
حال بسته به مناسب بودن اقدامهاي انجام شده آتاماتاها پاداش گرفته و یا جریمه میشوند. این عملیات آنقـدر تکـرار شـده تـا آتاماتاهـا بـه سـمت انتخاب اقدام بهینه همگرا شوند. شکل (5) یک اتوماتاي یادگیر توزیع شده تعمیم یافته را نشان میدهد. این سیستم میتواند داراي 211 اتوماتاي یادگیر باشد که از بین آنها سه اتوماتاي یادگیرT1 ، T2 و T3 فعال هستند و لازم است که ذخیره شوند. شکل (5) (الف) سیستم را قبلا از انتخاب اقـدام توسـط اتوماتاهـاي یـادگیر فعال و شکل (5) (ب) مجموعه
