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

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

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

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

تاريخ دفاع : 28/6/86

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

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

بهبود و توسعة الگوريتمAsynchronous Partial Overlay: الگوريتمي براي حل مسائل ارضاء محدوديت توزيع شده

چکيده

مسائل ارضاء محدوديت توزيع شده1 (DCSP) ، محدودة وسيعي از مسائل هوش مصنوعي2 و همچنين مسائل چندعامل3 را در بر مي گيرند. از آنجا که بسياري از مسائل مطرح در دنياي واقعي در قالب مسائل ارضاء محدوديت توزيع شده قرار مي گيرند، از سال 1991 تاکنون تلاش هاي بسياري در جهت حل اين دسته از مسائل انجام شده است. انجام يک بررسي کلي روي الگوريتم هاي ارائه شده در اين زمينه، نشان دهندة برتري الگوريتم (Asynchronous Partial Overlay (APO در مقايسه با ساير الگوريتم هاي موجود است. APO يک الگوريتم مبتني بر عمليات واسطه گري است. اين الگوريتم با انتخاب عامل هائي به عنوان عامل واسط4، سعي در متمرکز کردن بخش هائي از مسئلة توزيع شده دارد. هر عامل واسط با استفاده از روش هاي جستجوي تعريف شده، در جهت حل متمرکز و کارآمد زير مسئله تلاش مي کند. بنابراين به نظر مي رسد بخش انتخاب عامل واسط، يکي از کليدي ترين بخش هاي اين الگوريتم باشد و اعمال هرگونه تغيير در استراتژي انتخاب عامل واسط تأثير بسزائي درانتخاب بهترين راه حل داشته باشد.

اين پايان نامه، ارائه دهندة استراتژي جديد و مؤثري براي انتخاب عوامل واسط است که مبتني بر تعداد تناقضات عامل واسط مي باشد. بر اساس اين استراتژي با انتخاب عامل هاي با حداکثر تعداد تناقضات به عنوان عامل واسط، عامل هاي قدرتمندتر و مؤثرتري به عنوان عامل واسط انتخاب خواهند شد. ايدة اصلي موجود در پس اين استزاتژي اين حقيقت است که عامل هائي که بيشترين اطلاعات را نسبت به تناقضات موجود در زير مسئله داشته باشند مي توانند بهترين راه حل ها را انتخاب کنند. انتخاب چنين عامل هائي علاوه بر افزايش سرعت حل مسئله، تعداد پيغام هاي توليد شده را نيز به حداقل مقدار ممکن کاهش مي دهد. همچنين در اين پايان نامه، دو نسخة جديد از الگوريتم APO، به نام هاي MaxCAPO و MaxCIAPO ارائه شده اند که از استراتژي جديد معرفي شده استفاده مي کنند.

نتايج تجربي حاصل از آزمايشات انجام شده در اين پژوهش نشان دهندة اين مطلب است که انتخاب عامل واسط از ميان عامل هائي که حداکثر تعداد تناقضات را دارند، نه تنها منجر به کاهش قابل توجهي در پيچيدگي الگوريتم APO مي شود، بلکه مي تواند تاثير بسزائي در کاهش پيچيدگي الگوريتم هاي مشابه آن نظير الگوريتم IAPO داشته باشد. نتايج استفاده از روش مبتني بر تعداد تناقضات نشان دهندة بهبود سريع و دلخواه انواع پارامترهاي مطرح در اين زمينه نسبت به الگوريتم APO است.

کليد واژه: مسائل ارضاء محدوديت توزيع شده، خودمختاري، سيستم هاي چند عاملي، عمليات واسطه گري، هوش مصنوعي

1- Distributed Constraint Satisfaction Problems

2- Artificial Intelligence

3- Multi-agent

4- Mediator