عنوان:

ارائه مدلی برای حل مسائل ارضاء محدودیت با بهره گیری از سیستمهای چند عامله

استاد راهنما:

دکتر اقبال منصوری

برای رعایت حریم خصوصی نام نگارنده پایان نامه درج نمی گردد

تکه هایی از متن پایان نامه به عنوان نمونه :

(ممکن می باشد هنگام انتقال از فایل اصلی به داخل سایت بعضی متون به هم بریزد یا بعضی نمادها و اشکال درج نشود اما در فایل دانلودی همه چیز مرتب و کامل می باشد)

چکیده:

سیستمهای چند عامله سیستمهای محاسباتی هستند که در آن چندین عامل جهت رسیدن به یک هدف خاص با هم در تعامل هستند و با هم کار می کنند. دلیل پیدایش اینگونه سیستمها وجود موقعیتهایی می باشد که در آن یک مسأله بایستی در یک مد توزیع شده حل گردد. به عنوان مثال در شرایطی که بهره گیری از یک کنترل کننده مرکزی ممکن نیست و یا اینکه می­خواهیم بهره گیری مناسبی از منابع توزیع شده و یا امکانات محاسباتی داشته باشیم. با اینکه زمان زیادی از معرفی این گونه سیستم‌ها نمی‌گذرد اما بهره گیری از روش‌های طراحی بر اساس عامل یکی از موفق‌ترین راه‌حل‌های موجود بوده و حاصل این شیوه طراحی یعنی سیستم‌ حل مسائل به صورت توزیع‌شده از بهترین سیستم‌ها به شمار می‌آید و به عنوان ابزار جدیدی برای حل انواع فرآیندهای انسانی شناخته می گردد. مسأله ارضاء محدودیت توزیع شده سالهاست که در حوزه پژوهش سیستمهای چند عامله مورد توجه زیادی قرار گرفته می باشد. و این مسأله به آن علت می باشد که بسیاری از مسائل اعم از مسائل کلاسیکی همانند مسأله n-وزیر و رنگ آمیزی گراف گرفته و تا مسائل کاربردی بزرگ دنیای واقعی همچون زمانبندی و برنامه ریزی و تخصیص منابع می­توانند برای حل شدن به عنوان یک مسأله مسأله ارضاء محدودیت توزیع شده فرموله شوند. پس ارائه یک شیوه جدید و یا اصلاح شیوه های فعلی تاثیر زیادی بر دامنه تحقیقاتی این فیلد می­گذارد. آن چیز که در این پایان­نامه ارائه می­گردد ارائه تکنیکی جدید برای حل مسائل ارضاء محدودیت توزیع شده می باشد. این تکنیک جدید محدودیتها را در یک سیستم که ترکیبی از سیستمهای توزیع شده و متمرکز می باشد اداره و کنترل می­کند که با بهره گیری از یک سری ویژگیهای خاص تعریف شده از سیستمهای ترکیبی دیگر موجود متمایز می­گردد. نتایج حاصله نشان می دهد که این الگوریتم در مسائل با مقیاس بزرگ کارایی خوبی خواهد داشت و تقریبا یک پیچیدگی زمانی خطی را با افزایش مقیاس مسأله به دست می­آورد. همچنین مقایسه این روش با چند روش دیگر بهبود عملکرد این روش را در پارامترهای مختلف نسبت به دیگر روشها نشان می­دهد.

فصل اول

مقدمه:

از سال 1974، مسائل ارضاء محدویت (CSP[1]) در مسأله پردازش تصویر[2] پیشنهاد گردید. پس از آن CSP به گونه گسترده در بسیاری از حوزه های هوش مصنوعی و علوم کامپیوتر به عنوان یک روش حل مهم مورد بهره گیری قرار گرفته می باشد. از مسأله چند وزیر[3] و رنگ آمیزی گراف[4] گرفته و دیگر مسائل کلاسیک گرفته تا زمانبندی[5] و تخصیص منابع[6] و دیگر مسائل کاربردی بزرگ می­توانند برای حل شدن به عنوان یک مسأله CSP فرموله شوند. بعد از سال 1990 با جایگزین شدن زبان برنامه نویسی عمومی به جای زبان برنامه نویسی منطقی مسأله ارضاء محدودیت کاربرد CSP برای حل مسائل بسیار بهبود پیدا نمود [1]. یک CSP، با یک مجموعه از متغیرها، دامنه ای برای هر یک از آنها و محدودیتهایی در مقادیری که متغیرها ممکن می باشد به صورت همزمان به خودشان بگیرند، تعریف می­شوند. تأثیر الگوریتمهای ارضاء محدودیت، نسبت دادن مقادیری به متغیرهاست به نحوی که با تمام محدودیتها سازگاری داشته باشد یا مشخص کند که هیچ انتسابی امکانپذیر نیست. امروزه تکنیکهای ارضاء محدودیت در حوزه های مختلفی مانند بینایی ماشین، پردازش زبانهای طبیعی، اثبات قضایا، زمانبندی و… به کار می­طریقه [4].

از طرف دیگر موقعیتهایی هست که در آن یک مسأله بایستی در یک مد توزیع شده حل گردد به عنوان مثال در شرایطی که بهره گیری از یک کنترل کننده مرکزی ممکن نیست و یا اینکه می­خواهیم بهره گیری مناسبی از منابع توزیع شده و یا امکانات محاسباتی داشته باشیم. در چنین مواقعی عاملها[7] برای رسیدن به یک هدف مشترک کوشش می­کنند. هر سیستم چند عامله یک سیستم محاسباتی می باشد که در آن چندین عامل جهت رسیدن به یک هدف خاص با هم در تعامل هستند و با هم کار می­کنند [4].

مسأله ارضاء محدودیت توزیع شده (DCSP[8]) در واقع حالت توزیع شده­ی مسأله­ی ارضاء محدودیت کلاسیک می باشد که در آن متغیرها بین عاملهای مستقل توزیع شده­اند. این محیط توزیع شده شامل تعدادی عامل هوشمند می باشد که هر کدام، یک یا چند متغیر را مالک می­شوند و مقدار آن را کنترل می­کنند. همه این عامل ها در تلاشند تا با حفظ استقلالشان به هدف مشترک دست یابند. هدف هنوز یافتن یک انتساب برای متغیرهاست که محدودیتها را هم در نظر داشته باشد اما هر عامل، برای مقدار متغیر مالکش با خودمختاری نسبی تصمیم می­گیرد. هر چند عاملها یک دید عمومی ندارند اما هر یک از آنها می­تواند با همسایه اش در گراف محدودیت ارتباط مستقر کند. هر عامل کوشش می­کند نه تنها با ارضاء محدودیتهای محلی خود بلکه با برقرای ارتباط با سایر عاملها به مقصود حل محدودیتهای خارجی به این هدف نزدیک و نزدیکتر گردد. به گونه کلی تمام مسائلی که در آنها هدف یافتن مقادیر مناسب برای انتساب به متغیرهای توزیع شده می باشد را می­توان جزء مسائل ارضاء محدودیت توزیع شده به حساب آورد. در یک سیستم چند عاملی به هر عامل یک یا چند متغیر از میان متغیرهای توزیع شده منتسب می­گردد. وظیفه این عامل خودمختار کنترل و مدیریت مقدار این متغیر می­باشد [4] و [22]. این مسأله عمومی کاربردهای زیادی در زندگی واقعی دارد. مثلا در بسیاری از مسائل تخصیص منابع: در شبکه های حس گر بی سیم، کنترل علائم راهنمایی شهری، شبکه های حس گر توزیع شده، مسائل نجات یافتن از فاجعه و بسیاری از مسائل مربوط به زمان بندی مثلا برای قطارها و دانشگاه ها. هدف معمول در حل همه این مسائل یافتن مقادیر مناسب برای تخصیص دادن به متغیر های توزیع شده می باشد. به بیانی دیگر هر مسأله ای که هدف آن یافتن مقدار مناسبی برای تخصیص به متغیرهای توزیع شده می باشد می­تواند به عنوان DCSP طرح ریزی گردد.

در این پژوهش به مسائل ارضاء محدودیت توزیع شده پرداخته می­گردد که در آن عاملها در یک مد توزیع شده برای یافتن یک راه حل ممکن برای مسأله کوشش می­کنند.

[1] Constraint Satisfaction Problem

[2] image processing

[3] n-queen

[4] graph coloring
دانلود متن کامل در سایت sabzfile.com
[5] scheduling

[6] recourse allocation

[7] agents

[8] Distributed Constraint Satisfaction Problem

تعداد صفحه : 99

قیمت : 14700 تومان

این مطلب رو هم توصیه می کنم بخونین:   پایان نامه ارشد رشته نرم افزار کامپیوتر: مدلی کارا برای ساخت پیکره متنی موازی از روی پیکره متنی تطبیقی

بلافاصله پس از پرداخت لینک دانلود فایل در اختیار شما قرار می گیرد

و در ضمن فایل خریداری شده به ایمیل شما ارسال می گردد.

جستجو در سایت :   

پشتیبانی سایت :       

****         serderehi@gmail.com