تحصيلات تکميلي

نام و نام خانوادگي : محسن مومني

دانشکده : فني و مهندسي

استاد راهنما : دکتر کامران زماني فر

تاريخ دفاع : 21/10/87

رشته و گرايش : کامپيوتر- نرم افزار

استاد مشاور : -

به‌کارگيري سيستم چند عاملي توزيع‌شده در بهبود کارائي الگوريتم ژنتيک موازي

چکيده

تکنيک‌هاي محاسبات نرم، به هدف حل مسائل پيچيده با استفاده از روش‌هاي غيردقيق براي ارائه‌ي پاسخ‌هاي مفيد اما غيردقيق ارائه شده‌اند. برخلاف طرح‌هاي محاسبات سخت که پاسخ دقيق و کامل را جست‌وجو مي‌کنند، تکنيک‌هاي محاسبه‌ي نرم با راه‌دادن به روش‌هاي نادقيق، از پاسخ‌هايي نيمه‌درست و غيرقطعي براي مسائل خاص سود مي‌جويد. الگوريتم‌هاي ژنتيک که يکي از تکنيک‌هاي محاسبه‌ي نرم هستند، در اين سال‌ها به ابزارهاي محبوبي براي مسائل بهينه‌سازي تبديل شده‌اند.

با اين حال زمان زيادي که اين الگوريتم‌ها براي يافتن پاسخ نزديک‌به‌بهينه صرف مي‌کنند، همواره استفاده از آن‌ها را براي حل مسائل بهينه‌سازي دشوار مي‌سازد. بر خلاف روش‌هاي دقيق، که در آن‌ها کارائي زماني الگوريتم اصلي‌ترين معيار اندازه‌گيري ميزان موفقيت آن است، در الگوريتم ژنتيک و ساير محاسبات نرم دو موضوع اصلي، در ارزيابي مورد توجه قرار مي‌گيرند: اينکه پاسخ چه‌قدر سريع پيدا مي‌شود؟ واينکه از بهينه‌ي اصلي چه‌قدر فاصله دارد؟ موازي‌سازي الگوريتم‌هاي ژنتيک، يکي از اساسي‌ترين و بهترين راه‌هايي است که مي‌تواند زمان بسيار زياد مورد نياز براي انجام گرفتن محاسبات ژنتيکي و رسيدن به نتيجه‌ي مطلوب براي حل مسئله توسط آن‌ها را به حد قابل قبولي برساند و امکان استفاده از اين الگوريتم‌ها‌ را، در زمان قابل قبول، فراهم کند. الگوريتم‌هاي ژنتيک موازي چه به لحاظ دست‌يابي به برازندگي بهتر براي کروموزوم‌ها (نتيجه‌ي مطلوب‌تر) و چه به لحاظ دسترسي به تسريع بالاتر و مقياس‌پذيريِ بيشتر، بهتر از الگوريتم‌هاي ژنتيک ترتيبي و تک‌جمعيتي عمل مي‌کنند.

سيستم چند عاملي از اين جهت كه مي‌تواند به آساني با تغييرات و ناهمگوني‌هاي شبکه‌‌ي کامپيوتري (بستر محاسباتي)، خود را تطبيق دهد، قادر به به‌وجود آوردن شفافيت و مقياس پذيري در محاسبات توزيع شده است. علاوه بر اين، سيستم‌هاي چند عاملي براي انجام وظايفي كه ارتباط اندكي با يكديگر دارند و مي‌توانند به صورت محلي همگام شوند، به دليل عملكرد خودكار و هوشمند عامل­ها و هزينه‌ي كم ارتباط محلي بين آن‌ها، بسيار مناسب هستند. عامل­ها مي‌توانند به صورت خودكار، بستر خود را تغيير دهند و بدين صورت مي‌توانند مناسب‌ترين بستر را براي انجام كار خود در وضعيت كنوني و با توجه به ترافيك وظايف در گره‌هاي محاسباتي شبكه برگزينند. استفاده از اين ويژگي حركت‌پذيري در سيستم‌هاي چندعاملي مي‌تواند در بهبود كارآئي الگوريتم ژنتيك موازي تأثير بسزايي داشته باشد و علاوه بر اين قابليت اطمينان و تحمل پذيري سيستم را افزايش دهد. در راهبرد ارائه شده در اين پايان‌نامه، يک معماري چندعاملي جديد براي موازي‌سازي الگوريتم ژنتيک طراحي شده است، که درهر يک از عامل‌هاي محاسباتي آن، يک دسته‌ي جدا از جمعيت تکامل‌يابنده‌ي الگوريتم ژنتيک، مورد پردازش قرار مي‌گيرد.

مکانيسم انجام مهاجرت، بين اين دسته‌هاي جمعيتي، تاثير فراواني بر ميزان کارايي الگوريتم ژنتيک در محيط ناهمگن شبکه دارد. به همين دليل يک راهکار مهاجرتي مناسب، براي مديريت مهاجرت در بين عامل‌هاي محاسباتي در اين پايان‌نامه، ارائه شده است. اين راهبرد را، راهبرد مهاجرت "نيمه‌ناهمگام" ناميده‌ايم که سعي دارد از مزاياي دو روش همگام و ناهمگام برخوردار باشد و معايب مشهود در آن‌ها را، کمتر نمايد.

نتايج به‌دست‌آمده از ارزيابي کارائي مدل چندعاملي ارائه شده در اين پايان‌نامه، نشانگر مطلوبيت آن براي پردازش الگوريتم‌هاي ژنتيک موازي و استفاده از آن در کاربردهاي مختلف، بر روي شبکه‌هاي ناهمگن، محيط‌هاي پويا و دائماً در حال تغيير است.

واژه هاي کليدي: سيستم توزيع شده، سيستم چندعاملي، محاسبات نرم، الگوريتم ژنتيک موازي، شبکه هاي ناهمگن، مديريت مهاجرت، مهاجرت نيمه ناهمگام