بخشی از مقاله
چکیده
مسئله پیدا کردن درخت اشتاینر کمینه در یک گراف وزندار عبارت است از پیدا کردن یک درخت با کمترین هزینه بر روي گراف که شامل تعدادي از گره هاي خاص به نام ترمینال باشد. این مسئله از جمله مسائل 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]
