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

نام و نام خانوادگي : امين محبي فر

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

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

تاريخ دفاع : 29/3/86

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

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

يك راه حل موازي مبتني بر عامل براي مسأله‌ي فروشنده‌ي دوره‌گرد با استفاده از الگوريتم‌هاي ژنتيكي

چکيده

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

از آنجايي كه، الگوريتم‌هاي ژنتيكي ماهيتي موازي‌شدني دارند و به آساني به صورت موازي پياده‌سازي‌شدني هستند (الگوريتم‌هاي ژنتيكي موازي)، براي مبحث موازي‌سازي به كمك عامل‌ها، به بررسي نحوه‌ي موازي‌سازي اين الگوريتم‌ها پرداخته شده است. افزون بر آن، خود الگوريتم‌هاي ژنتيكي نيز مورد توجه قرار گرفته است و به ارائه‌ي پيشنهادهايي درباره‌ي فازهاي گوناگوني از اين الگوريتم‌ها پرداخته شده است.

الگوريتم‌هاي ژنتيكي، از زمره‌ي شيوه‌هاي مکاشفه‌اي هستند كه بيشتر براي مسايل بهينه‌سازي بكار مي‌روند. از مهم‌ترين و مشهورترين مسايل بهينه‌سازي، مسأله‌ي معروف فروشنده‌ي دوره‌گرد را مي‌توان نام برد، كه از مسايل چندجمله‌اي غيرقطعي است. اين مسأله به عنوان بررسي موردي، در نظر گرفته شده و آزمايش‌ها بر روي نمونه‌هاي استانداردي از آن انجام شده است.

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

در بخش راهكار‌هاي آينده نيز به ارائه‌ي پيشنهادهايي براي بهبود روش‌هاي مورد بررسي و يا جنبه‌هاي تازه‌اي از آن مباحث پرداخته شده است.