دانشگاه شیراز

دانشکده  مهندسی برق و کامپیوتر

پایان نامه کارشناسی ارشد در رشته مهندسی کامپیوتر(نرم افزار)

گسترش ابزارهای خودکار شناسایی الگوهای طراحی با عملیات پالایش و تصحیح برچسب

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

دکتر اشکان سامی

اسفند 1392

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

(در فایل دانلودی نام نویسنده موجود است)

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

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

چکیده

الگوهای طراحی، راه­حل­های اثبات شده و قابل اطمینانی هستند که، برای پاسخ به برخی از مسائل با رخداد مکرر در طراحی نرم افزار شی­گرا، ارائه شده­اند.‌ شناسایی آنها درکد، به منزله بازیابی طرح و هدف مخفی طراح و سهولت در امر نگهداشت­­پذیری است. از آنجاییکه سهولت در نگهداشت­­پذیری سیستم بسیار مهم و اجتناب ناپذیر است، لذا تولید ابزارهای خودکار برای شناسایی الگوها، مورد توجه قرار گرفت. اکثر ابزارهای شناسایی کنونی درصد بازیابی بالایی دارند. اما در شناسایی الگوها، به ویژه با ساختار و عملکرد مشابه، مثبت کاذب بالایی تولید می­کنند. از اینرو عملگر پالایش نیز پیشنهاد شد. پالایش، سعی بر شناسایی مثبت­­های کاذب، و حذف آنها  دارد. در این کار، یک عملگر جدید به نام “تصحیح برچسب” ارائه شده است. این عملگر ابتدا مثبت­های کاذب را شناسایی، سپس بجای اینکه آنها را از خروجی حذف کند، هویت صحیح  آنها را به کمک یک مجموعه معیارجدید معرفی شده در این کار، تشخیص و برچسب مثبت کاذب را تصحیح می­کند­­. خودکارسازی عملگر با داده­کاوی است. نتایج حاصل از روش ارائه شده، با دقت یادگیری 97.8%  در دسته­بندی “چندبرچسبه”، با متوسط 99.3% در دسته­بندی “یکی درمقابل همه”و متوسط 99.6% در دسته­بندی “دو به دو” خروجی ابزارها را تصحیح می­کند.

فهرست مطالب

         عنوان                                                                                                   صفحه                                                                                            

• مقدمه………………………………………………………………………………………………8         
  • فرضیات و محدودیت های مساله……………………………………………………………..12
  • ضرورت انجام تحقیق………………………………………………………………………………..13
  • هدف از انجام تحقیق………………………………………………………………………………..13
  • سرفصل مطالب…………………………………………………………………………………………14
• تعاریف و مفاهیم اولیه…………………………………………………………………………17
  • مقدمه………………………………………………………………………………………………………17
  • تکنیک های طبقه بندی…………………………………………………………………………18
  • معیارهای ارزیابی کارایی…………………………………………………………………………19
  • جمع بندی………………………………………………………………………………………………21
• مروری بر تحقیقات پیشین………………………………………………………………..23
  • مقدمه…………………………………………………………………………………23
  • مطالعات قبلی در شناسایی خودکار و نیمه خودکار الگوهای طراحی و محدودیت هایشان………………………………………………………………………………..24
  • جمع بندی……………………………………………………………………………………………28
• تولید مجموعه داده …………………………………………………………………………..30
  • مقدمه…………………………………………………………………………………………………..30
  • معیارهای استخراج شده……………………………………………………………………..31
  • چارچوب آنالیز جهت شناسایی اولیه و تصحیح برچسب الگوهای طراحی…………………………………………………………………………………………..48
  • جمع بندی……………………………………………………………………………50
• آزمایشات و نتایج عددی…………………………………………………………………….51
  • مقدمه……………………………………………………………………………………………52
  • کارایی یادگیری……………………………………………………………………………52
  • جمع بندی…………………………………………………………………………………….56
• نتیجه گیری و کارهای آتی…………………………………………………………………..58
• فهرست منابع و مآخذ………………………………………………………………………….59

چکیده به زبان انگلیسی ……………………………………………………………………..62

فهرست جدول ها

               عنوان                                                                                               صفحه

جدول2-1ماتریس درهم……………………………………………………………………………………………….19

جدول 4-1بخش کوچکی از مجموعه داده برای عملگر تصحیح برچسب……………………49

جدول4-2 بخش کوچکی از مجموعه داده  برای عملگر پالایش…………………………………50

جدول 5-1ارزیابی دقت بکارگیری معیارها و روش داده­کاوی C5.0 با روش یکی در مقابل همه………………………………………………………………………………………………………………………………………..53

جدول 5-2 ارزیابی دقت بکارگیری روش داده­کاوی  SVMو معیارها با روش یکی در مقابل همه………………………………………………………………………………………………………………………………………..53

جدول 5-3 ارزیابی دقت بکارگیری روش داده­کاویBoosting  و معیارها با روش یکی در مقابل همه……………………………………………………………………………………………………………………………..54

جدول 5-4 ارزیابی دقت بکارگیری روش داده­کاوی SVM و معیارها با روش دو در دو…………………………………………………………………………………………………………………………………………..55

جدول 5-5 ارزیابی دقت بکارگیری روش داده­کاوی Boosting و معیارها با روش دو در دو…………………………………………………………………………………………………………………………………………..55

جدول 5-6 ارزیابی دقت بکارگیری روش­های داده­کاوی و معیارها با روش چند برچسب………………………………………………………………………………………………………………………………….55

فهرست شکل ها

                  عنوان                                                                                      صفحه

شکل4-1الگوی استراتژی………………………………………………………………………………32

شکل4-2یک نمونه الگوی استراتژی حقیقی………………………………………………32

شکل4-3 رابط های یک نمونه الگوی استراتژی حقیقی……………………………..33

شکل4-4ترتیب فراخوانی از رابط های یک استراتژی حقیقی………………………33

شکل 4-5 الگوی وضعیت…………………………………………………………………………….35

شکل 4-6الگوی تطبیق دهنده شی…………………………………………………………..37

شکل4-7الگوی کارخانه انتزاعی……………………………………………………………….39

شکل4-8الگوی فرمان………………………………………………………………………………40

شکل4-9شباهت ساختاری الگوی فرمان و تطبیق دهنده شی………………..41

شکل4-10 الگوی ملاقات کننده……………………………………………………………….42

شکل4-11 الگوی میانجی………………………………………………………………………….43

             شکل4-12الگوی آذیین کننده……………………………………………………………………44

شکل4-13الگوی ترکیب…………………………………………………………………………..46

شکل 4-14 مراحل ایجاد مدل­های تصمیم­گیری……………………………………..49

شکل 5-1   بهبود روی ابزار شناسایی خودکار الگوهای طراحی ” SSA”…..55

شکل 5-2 بهبود روی ابزار شناسایی خودکار الگوهای طراحی ” PINOT “…56

مقدمه

اگرچه طراحی یک نرم­افزار شی­گرا دشواری­های خاص خود را دارد، دشوار­تر از آن، طراحی یک نرم­افزار شی­گرا با قابلیت استفاده مجدد است. الگوهای طراحی، استفاده از طراحی­ها و معماری­های موفق را آسان می­کنند [1]. الگوهای طراحی راه­حل­های اثبات شده و قابل اطمینان هستند که به منظور حل مسائلی که به طور مکرر در طراحی یک نرم افزار شی­گرا رخ می­دهد، مورد استفاده قرار می­گیرند. یک الگوی طراحی هدف و ساختار واحد خودش را دارد. الگوها نقش­ها، مسئولیت­ها، نحوه­ همکاری کلاس­ها و نمونه­های شرکت کننده در این همکاری را توصیف می­کنند. بنابراین با استخراج الگو­های طراحی از کد منبع، قادر به آشکار کردن هدف و طرح یک سیستم نرم­افزاری هستیم [5].

بکارگیری صحیح الگو­های طراحی در توسعه یک نرم­افزار شی­گرا، می­تواند به طور چشمگیری کیفیت کد منبع را بر حسب نگهداشت پذیری و قابلیت استفاده مجدد بهبود دهد. مهمترین مساله­ نگهداشت­پذیری سیستم­های نرم­افزاری خصوصا سیستم­های قدیمی این است که فاقد سند کامل از طرح سیستم و اهداف آن هستند. بنابراین شناسایی الگوهای طراحی به صورت خودکار یا نیمه خودکار، سندسازی سیستم،  نگهداشت­پذیری و قابلیت استفاده مجدد آن را تسهیل می­کند.

برای دانلود متن کامل پایان نامه اینجا کلیک کنید

لینک بالا اشتباه است

برای دانلود متن کامل اینجا کلیک کنید

       

:: بازدید از این مطلب : 789

دانشگاه شیراز

دانشکده برق و کامپیوتر

پایان‌نامه کارشناسی ارشد در رشته هوش مصنوعی

شناسایی تشکل‌های پنهان بر اساس لینک و محتوا

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

دکتر ستار هاشمی

31 شهریور ماه ۱۳۹3

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

(در فایل دانلودی نام نویسنده موجود است)

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

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

چکیده

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

واژگان کلیدی: شبکه­های اجتماعی، تشکل، شناسایی تشکل ها، پیمایش متن

فهرست مطالب

عنوان                                                                                              صفحه

فصل 1- مقدمه.. 7

1-1- شبکه های اجتماعی.. 7

1-2- تقسیمبندی شبکههای اجتماعی.. 9

1-3- اهمیت شبکههای اجتماعی.. 10

1-4- تحلیل شبکههای اجتماعی.. 11

1-5- شبکهها و ویژگی آنها 11

1-6- تشکلها در شبکههای اجتماعی.. 13

1-7- اهمیت شناسایی تشکلها 16

1-8- انگیزه از انجام این پایان نامه. 17

1-9- نگاه کلی به فصول رساله. 19

فصل 2- فصل دوم: مروری بر کارهای انجام شده. 21

2-1- مقدمه. 21

2-2- روشهای ارائه شده 22

2-3- روشهای مبتنی بر لینک… 22

2-3-1- بهینه کردن یک هدف سراسری.. 22

2-3-2- بدون بهینه سازی هیچ معیاری.. 27

2-3-3- روشهای مبتنی بر مدل.. 27

2-4- روشهی مبتنی بر محتوا 29

2-4-1- روش CUT. 29

2-4-2- روش LTCA. 30

فصل 3- ارائه راه حل و روشهای پیشنهادی… 32

3-1- مقدمه. 32

3-2- روش SBM… 34

3-3- روش LDA.. 37

3-4- روش پیشنهادی.. 40

3-4-1- روش CDBLC.. 41

3-5- جمعبندی.. 51

فصل 4- نتایج… 53

4-1- مقدمه. 53

4-2- مجموعه دادهها 54

4-2-1- مجموعه دادهی Cora. 54

4-2-2- مجموعه دادهی Twitter 55

4-3- معیارهای ارزیابی.. 56

4-3-1- معیار Modularity. 57

4-3-2- معیار Normalized Mutual Information. 58

4-3-3- معیار Perplexity. 59

4-4- نتایج و تحلیلها 60

4-4-1- مجموعه دادهی Cora. 61

فصل 5- بحث و نتیجه‌گیری… 67

5-1- نتیجه گیری.. 67

5-2- پیشنهادات برای کارهای آتی.. 71

فهرست منابع.. 72

فهرست شکل‌ها

عنوان                                                                                  صفحه

شکل 1-1- تشکلها. 14

شکل2-1- افراز گراف. 25

شکل 2-2-  الف) خوشه‌بندی سلسله مراتبی. ب) خوشه‌بندی توده‌ای.. 26

شکل 2-3- نمایش گرافیکی مدل GSB. 30

شکل 2-4- نمایش گرافیکی روش CUT. 31

شکل 3-1- نمایش گرافیکی روش مدل بلوک تصادفی (SBM). 37

شکل 3-2- نمایش گرافیکی روش LDA. 39

شکل3-3- روند کشف تشکلهای پنهان در CDBLC. 43

شکل 3-4- گراف مبتنی بر لینک برای شبکه مثال. 43

شکل 3-5- اعمال روش SBM بر روی گراف شبکه. 44

شکل 3-6- انتساب اسناد به تشکلها. 45

شکل 3-7- اعمال روش LDA بر روی اسناد درون هر تشکل. 45

شکل 3-8- محاسبه شباهت محتوای اسناد در دیگر تشکلها با عناوین یک تشکل به خصوص. 46

شکل 3-9- همگرایی الگوریتم CDBLC. 47

شکل 3-10- تمایش گرافیکی قدم دوم از الگوریتم CDBLC . 48

شکل 3-11- فلوچارت الگوریتم CDBLC.. 51

…………………………………………………………………………………………………………………………………………………………. 62

شکل 4-1- کارایی الگوریتم با توجه به معیار MI بر روی مجموعه دادهی Cora. 62

شکل 4-2- Perplexity تمام تشکلها در تمام مراحل بر روی مجموعه داده Cora. 63

شکل 4-3- خروجی Perplexity برای هر تشکل در مراحل مختلف بر روی مجموعه داده Cora . 64

شکل 4-4- نمودار مقایسه Perplexity روش LDA و CDBLC برای T=50 و K=5. 65

شکل 4-5- نمودار مقایسه Perplexity روش LDA و CDBLC برای T=30 و K=10. 65

شکل 4-5- نمودار مقایسه Perplexity روش LDA و CDBLC برای T=100 و K=20. 66

فهرست جدول‌ها

عنوان                                                                                 صفحه

جدول 3-1 علائم و تعاریف بکار رفته. 33

فصل 1- مقدمه

1-1- شبکه های اجتماعی

تعامل انسان با کامپیوتر[1] از زمان ایجاد اولین کامپیوتر­ها همواره مورد توجه بوده است و شامل مطالعه، برنامه­ریزی و طراحی رابطه بین کاربران و رایانه­ها است. معمولا از HCI به عنوان نقطه تقاطع علوم کامپیوتر، علوم رفتاری[2]، علم طراحی و چند زمینه دیگر یاد می­شود. این اصطلاح برای اولین بار توسط کارد و همکارانش در کتاب “روانشناسی تعامل انسان با کامپیوتر” مطرح شده است و دلالت ضمنی بر این مطلب دارد که رایانه دارای کاربرد­های بیشماری است که بدون مرز بین آن و کاربر اعمال می­شود[1].

متخصصان این حوزه در ابتدا به دنبال راهکاری برای تولید سخت افزار­هایی با ارگونومی مناسب بودند. طی دهه­ی 1980 تمرکز اصلی به تولید نرم افزار های کاربر پسند معطوف شد اما طولی نکشید که در دهه­ی 1990 دیدگاه جدیدی مطرح شد که در آن، به رایانه به عنوان ابزاری برای ایجاد تعاملات انسانی نگاه می­شد. با توجه به این رویکرد، شبکه­های اجتماعی اینترنتی عامل ایجاد تعامل میان انسان­ها در فضای مجازی گشتند و اهمیت به سزایی پیدا کردند[2].

برای دانلود متن کامل پایان نامه اینجا کلیک کنید

لینک بالا اشتباه است

برای دانلود متن کامل اینجا کلیک کنید

       

:: بازدید از این مطلب : 792

دانشگاه صنعتی اصفهان

دانشکده برق و کامپیوتر

زمان‌بندی وظیفه‌ها در سیستم‌های بی‌درنگ نهفته چند‌هسته‌ای با هدف بهبود انرژی مصرفی و کارایی

پایان نامه کارشناسی ارشد مهندسی کامپیوتر – معماری سیستم های کامپیوتری

استاد راهنما

دکتر محمدعلی منتظری

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

(در فایل دانلودی نام نویسنده موجود است)

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

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

عنوان

فهرست مطالب……………………………………………………………………………………………………………………………………………هشت

چکیده 1

فصل اول :مقدمه

1-1 پیشگفتار 2

1-2 توصیف مسئله 3

1-3 ساختار پایان نامه 4

فصل دوم :مفاهیم اولیه

2-1 سیستم های تعبیه‌شده 6

2-1-1 مصرف انرژی در سیستم‌های تعبیه‌شده 8

2-2 سیستم های تعبیه‌شده بی‌درنگ 9

2-2-1  انواع سیستم های بی‌درنگ از نظر محدودیت زمانی 11

2-2-2 تابع بهره‌وری در سیستم‌های بی‌درنگ 12

2-3  وظیفه 13

2-3-1  مدل وظیفه بی‌درنگ 14

2-3-2 دسته‌بندی وظایف بی‌درنگ 15

2-4 سررسید 16

2-5  هسته پردازنده 18

2-6  منابع 18

2-7  مفاهیم زمانبندی 19

2-7-1 تعاریف مربوط به مبحث زمانبندی 20

2-8  سیستم های چندهسته‌ای 21

2-9  نتیجه‌گیری 22

فصل سوم : مرور منابع و کارهای انجام‌شده

3-1  طبقه بندی روش‌های زمانبندی 23

3-2  الگوریتم‌های زمانبندی بی‌درنگ تک پردازنده 26

3-3  طبقه‌بندی معماری سیستم‌های چندهسته‌ای 29

3-4  زمانبندی بیدرنگ چندهسته‌ای 30

3-4-1  معایب روش‌های زمانبندی عمومی و جزبندی 32

3-5  زمانبندی چند هسته‌ای مبتنی بر DVFS 34

3-6  بررسی کارهای گذشته 37

3-6-1  الگوریتم توزیع بار غیر تعادلی LU-McEP 37

3-6-2  الگوریتم زمانبندی غیرتعادلی جزبندی با RBound 42

3-6-3  الگوریتم زمانبندی چند سطحی PDAMS 47

3-6-4  الگوریتم زمانبندی پیشنهادی در مرجع ]37[ 59

3-7  نتیجه‌گیری 65

فصل چهارم : الگوریتم پیشنهادی

4-1 جایگاه الگوریتم پیشنهادی 66

4-2  کلیات الگوریتم پیشنهادی 68

4-3  مدل وظیفه الگوریتم پیشنهادی 68

4-4  مدل سیستم الگوریتم پیشنهادی 69

4-5  شرح کامل الگوریتم پیشنهادی 71

4-5-1 بخش اول الگوریتم پیشنهادی (تفکیک وظایف و هسته‌ها) 71

4-5-2  بخش دوم الگوریتم پیشنهادی (توزیع وظایف بین هسته‌ها) 72

4-5-3  الگوریتم پیشنهادی تنظیم فرکانس سررسید محور (بخش سوم الگوریتم پیشنهادی) 83

4-6  نتیجه‌گیری 88

فصل پنجم :شبیه‌سازی و ارزیابی الگوریتم پیشنهادی

5-1  تنظیمات اولیه شبیه‌سازی 89

5-2  محیط شبیه‌سازی 91

5-3  ارزیابی انرژی مصرفی 92

5-4  ارزیابی کارایی 97

5-4-1  ارزیابی نرخ نقض سررسید 97

5-4-2  ارزیابی متوسط زمان پاسخ وظایف غیرتناوبی 99

5-4-3  ارزیابی متوسط زمان انتظار وظایف غیرتناوبی 101

5-5  نتیجه‌گیری 102

فصل ششم : نتیجه‌گیری و پیشنهادات

6-1  نتیجه‌گیری 103

6-2  پیشنهادات 104

مراجع 105

واژگان اختصاری 108

فهرست شکل­ها

شکل 2-1- تابع بهره‌وری u(t) برای انواع مختلف وظایف بی‌درنگ 13

شکل 2-2-  نمودار گذار حالت یک وظیفه 14

شکل 2-3  سررسید متناظر و سررسید مطلق یک وظیفه 17

شکل 3-1  تفسیم‌بندی انواع روش‌های زمانبندی 26

شکل 3-2 مثالی از کاربرد زمانبندی تک هسته‌ای با استفاده از الگوریتم EDF 27

شکل 3-3  بررسی اجمالی معماری پردازنده AMP   و SMP 30

شکل 3-4   مثالی از زمانبندی تولید شده امکان‌پذیر، از الگوریتم : الف) جزءبندی ب) کاملا مهاجرتی ج) مهاجرتی محدودشده 32

شکل 3-5  مثالی کمی متفاوت از مثال قبلی ، که با رویکرد جزءبندی، قابل زمانبندی نیست 33

شکل 3-6  طبقه‌بندی الگوریتم‌های زمانبندی چندهسته‌ای 34

شکل 3-7 نمونه‌ای از تنظیم فرکانس و ولتاژ در زمان سکون وظیفه، الف) بدون   DVFS ب) با DVFS 36

شکل 3-8 شبه کد الگوریتم تخصیص وظایف 40

شکل 3-9   الگوریتم ScaleTaskSet 43

شکل 3-10  شبه کد الگوریتم RBound-FF 45

شکل 3-11  الگوریتم اختصاص دادن وظایف در مرجع [35] 46

شکل 3-12     مدل سیستم مرجع [36] 50

شکل 3-13  شبه کد الگوریتم ED3VFS 54

شکل 3-14  مثالی از بارگذاری غیرتعادلی 55

شکل3-15  مثالی از توزیع وظایف بی‌درنگ 56

شکل 3-16  شبه کد الگوریتم توزیع وظایف TLDHLB 59

شکل 3-17  شبه‌کد الگوریتم جزبندی با WFD 61

شکل 3-18  شبه کد زمانبند پیشنهادی در [37] 62

شکل 3-19 شبه‌کد سیاست اجرای EDF 62

شکل 3-20 شبه‌کد سیاست زمانبندی TBS و EDF 63

شکل 3-21 شبه‌کد روش مهاجرت وظایف غیرتناوبی در [37] 63

شکل 3-22  نمودار زمانی مثال مربوطه در [37] 65

شکل 4-1  ساختار کلی زمانبندی سیستم پیشنهادی 67

شکل 4-2  مدل سیستم پیشنهادی 70

شکل 4-3    شبه‌کد الگوریتم توزیع وظایف تناوبی 76

شکل 4-6   شبه‌کد الگوریتم پیشنهادی توزیع وظایف غیرتناوبی 80

شکل 4-7  فلوچارت الگوریتم پیشنهادی توزیع وظایف غیرتناوبی 81

شکل 4-8  نمودار زمانی اجرای یک وظیفه با الگوریتم تنظیم فرکانس پیشنهادی 84

شکل 5-1  مقایسه انرژی مصرفی حالت‌های مختلف نسبت تفکیک هسته‌ها برای وظایف تناوبی و غیرتناوبی 93

شکل 5-2  انرژی مصرفی الگوریتم پیشنهادی در شش مجموعه وظیفه مختلف 94

شکل 5-3  مقایسه انرژی مصرفی الگوریتم پیشنهادی با الگوریتم‌های LU-McEP و PDAMS 95

شکل 5-4  مقایسه انرژی مصرفی الگوریتم پیشنهادی با الگوریتم‌های LU-McEP و PDAMS  در 6 مجموعه وظیفه مختلف 96

شکل 5-5  مقایسه نرخ نقض سررسید وظایف در همه حالت‌های ممکن الگوریتم پیشنهادی 97

شکل 5-6  مقایسه میزان نرخ نقض سررسید الگوریتم پیشنهادی با الگوریتم‌های LU-McEP  و PDAMS 98

شکل 5-7 مقایسه میزان نرخ نقض سررسید الگوریتم پیشنهادی ما با الگوریتم‌های LU-McEP  و PDAMS  را در تمام حالت‌ها 99

شکل 5-8  مقایسه زمان پاسخ وظایف غیرتناوبی الگوریتم ما با الگوریتم‌های LU-McEP و  PDAMS 100

شکل 5-9  مقایسه متوسط زمان پاسخ وظایف غیرتناوبی الگوریتم ما با الگوریتم‌های LU-McEP و  PDAMSدر همه حالت‌ها 101

شکل 5-10 مقایسه متوسط زمان انتظار وظایف غیرتناوبی الگوریتم پیشنهادی ما نسبت به الگوریتم‌های LU-McEP و PDAMS 102

فهرست جدول­ها

جدول 2-1 خلاصه‌ای از مشخصه‌های یک سیستم تعبیه‌شده بی‌درنگ 10

جدول 3-2 مشخصات وظایف تناوبی در مثال مربوطه در [37] 64

جدول 3-3 مشخصات وظایف غیرتناوبی در مثال مربوطه در [37] 64

جدول 4-1  فرکانسها و توان متناظر هر سطح فرکانسی 85

جدول 4-2  مثال عددی از الگوریتم تنظیم فرکانس سررسیدمحور پیشنهادی 86

جدول 5-1  مشخصات پردازنده چندهسته‌ای PowerPC 405PL شرکت IBM 89

چکیده

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

کلمات کلیدی :  زمان‌بندی، وظایف بی‌درنگ، پردازنده‌های چند هسته‌ای ، سیستم­های تعبیه‌شده

1 پیشگفتار

 سیستم‌های تعبیه‌شده[1] یکی از بخش‌های اصلی زندگی ما هستند و نقش مهمی در آسان نمودن زندگی مدرن ما ایفا می‌کنند. از تلفن‌های هوشمند[2] که امکانات متنوعی را در اختیار کاربران قرار‌‌می‌دهند گرفته تا لوازم منزل، آسانسورها، ترمز در یک خودرو و سیستم های هدایت موشک همگی نمونه هایی از سیستم های تعبیه‌شده هستند.

امروزه بیش از 98 درصد تمام پردازنده‌های تولیدشده در جهان در سیستم‌های تعبیه‌شده استفاده شده ‌است. این پردازشگرهای تعبیه‌شده در نگاه اول کاربر، قابل مشاهده نیستند؛ در هرصورت عملکرد صحیح آنها برای درست کار کردن هرسیستمی ضروری است. در اکثر مواقع عملیات در یک سیستم تعبیه‌شده باید در زمان کوتاه و مناسبی اجرا شوند. از این رو اکثر سیستم‌های تعبیه‌شده، بی‌درنگ[3] می‌باشند، بنابراین زمان پاسخ[4]  در سیستم های تعبیه‌شده بی‌درنگ از اهمیت بالایی برخوردار است. علاوه بر بی‌درنگ بودن و اهمیت زمان پاسخ، مصرف انرژی کم نیز یکی از مهم‌ترین ویژگی‌های یک سیستم تعبیه‌شده می باشد.از دیگر ویژگی‌های یک سیستم تعبیه‌شده می توان به تولید گرمای پایین و هزینه کم اشاره کرد. مبحث انرژی و توان مصرفی مانع از افزایش سرعت مخصوصا در سیستم‌های چندهسته‌ای[5] می‌شود. سیستم‌های بی‌درنگ می توانند بهره خوبی از پردازنده‌های چندهسته‌ای ببرند، یعنی وظیفه‌های[6] مستقل می‌توانند به طور همزمان اجرا شوند و خیلی سریع باهم بین هسته‌ها ارتباط برقرار کنند.

برای دانلود متن کامل پایان نامه اینجا کلیک کنید

لینک بالا اشتباه است

برای دانلود متن کامل اینجا کلیک کنید

       

:: بازدید از این مطلب : 1370

دانشگاه شیراز

پایان نامه کارشناسی ارشد در رشته مهندسی کامپیوتر – هوش مصنوعی

روشی انتخابی برای راه رفتن از بغل در روبات انسان­ نما

استاد راهنما

دکتر شهرام جعفری

اساتید مشاور

دکتر ستار هاشمی

دکتر علیرضا ذوالقدر اصلی

شهریور ماه 1392

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

(در فایل دانلودی نام نویسنده موجود است)

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

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

چکیده

امروزه راه رفتن روبات انسان نما یکی از حوزه­های جذاب تحقیق در زمینه روباتیک است. چالش­های موجود در کنترل روبات های انسان نما با درجات آزادی بالا، این مساله را در زمره مسائل دشوار در حوزه روباتیک قرار داده است به طوریکه راه رفتن روبات انسان نما را کماکان به عنوان مهمترین توانایی یک روبات طبقه­بندی می­کنند. در این پایان­نامه روشی جدید برای راه رفتن روبات انسان­نما از بغل مطرح شده است. در این روش بر روی هر یک از مفاصل موثر در راه رفتن روبات یک اتوماتای یادگیر متغیر سوار می­شود که طی فرآیند یادگیری بردارهای احتمال مربوط به اتوماتاها به روز می­شود و مقادیر مناسب مفاصل برای راه رفتن با توجه به این بردارها انتخاب می­شوند. در ادامه این روش یادگیری برای راه رفتن مستقیم و راه رفتن از بغل مورد استفاده قرار می­گیرد که نتایج حاصل از شبیه­سازی الگوریتم بر روی روبات انسان­نمای نائو در محیط شبیه­سازی فوتبال سه­بعدی نشان دهنده نتایج مناسب در راه رفتن مستقیم روبات در مقایسه با روش­های گذشته و همچنین مزایای فراوان بهبود توانایی راه رفتن از بغل در یک روبات انسان­نما می­باشد.

واژه های کلیدی

روبوکاپ ، فوتبال ربات ها، روبات های انسان نما، راه رفتن روبات نائو، اتوماتای یادگیر

فهرست مطالب

فهرست جداول

فهرست اشکال

• مقدمه

امروزه روباتیک[1] به عنوان یکی از رشته­های علوم ومهندسی، مورد توجه بسیاری از موسسه­­های تحقیقاتی قرار گرفته است و به یکی از حوزه های بسیار جذاب تحقیق و پژوهش بدل گشته است، به نحوی که تحقیقات در زمینه روباتیک در شاخه های مختلفی در حال پیگیری است. در زمینه روباتیک سه رویکرد کلی مورد توجه می باشد که تحقیقات در این سه حوزه گسترده رو به پیشرفت می­باشد. در رویکرد اول سعی بر ساخت روبات­های مصنوعی و هوشمند کردن آنها با استفاده از الگوریتم­های هوش مصنوعی[2] است، که این رویکرد بسیار پرطرفدار خود به شاخه های گوناگونی تقسیم می­شود که در ادامه به معرفی برخی از آنها خواهیم پرداخت. رویکرد دوم به استفاده از هوش طبیعی[3] برای کنترل روبات­های مصنوعی می­پردازد. روبات­هایی که با کنترل دستی هدایت می­شوند در این حیطه قرار می­گیرند و در نهایت رویکرد آخر استفاده از روبات­های طبیعی[4] و تربیت آنها برای دست یافتن به اهداف از پیش تعیین شده می­باشد. تربیت حیوانات برای انجام اعمال خاص، مثالی از رویکرد سوم می­باشد.

برای دانلود متن کامل پایان نامه اینجا کلیک کنید

لینک بالا اشتباه است

برای دانلود متن کامل اینجا کلیک کنید

       

:: بازدید از این مطلب : 988

دانشگاه صنعتی اصفهان

دانشکده برق و کامپیوتر

زمانبندی وظایف در سیستم­ های تعبیه­ شده بی­­ درنگ برداشت گر انرژی با هدف کاهش نرخ خطای سررسید و افزایش کارایی انرژی مصرفی

پایان‌نامه کارشناسی ارشد مهندسی کامپیوتر- معماری کامپیوتر

استاد راهنما

دکتر محمد علی منتظری

1394

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

(در فایل دانلودی نام نویسنده موجود است)

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

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

فهرست مطالب

صفحه

فهرست مطالب ……………………………………………………………………………………………………………………………………………هشت

چکیده. …………………………………………………………………………………………………………………………………………………………….1

فصل اول: توصیف مسئله

1-1 مقدمه. 2

1-2  ساختار پایان نامه. 4

فصل دوم : مفاهیم اولیه

2-1  مقدمه. 6

2-2 سیستمهای تعبیه شده. 6

2-3  سیستم بی درنگ….. 8

2-4  زمانبندی وظایف…. 9

2-4-1  انواع زمانبندی.. 9

2-5  تعاریف اولیه. 10

2-6  الگوریتمهای زمانبندی اولیه. 12

2-6-1  الگوریتم زمانبندی نزدیکترین سررسید اول (EDF). 12

2-6-2  الگوریتم زمانبندی نرخ یکنواخت (RMS). 13

2-7  برداشت انرژی محیطی.. 14

2-7-1  اجزای سیستم تعبیه شده مبتنی بر برداشت انرژی.. 15

2-7-2  انواع سیستم برداشتگر انرژی.. 16

2-8  مدیریت توان در سیستمهای تعبیه شده. 19

2-9  نتیجه گیری.. 20

فصل سوم : بررسی منابع و کارهای انجام شده

3-1 مقدمه. 21

3-2  الگوریتمهای زمانبندی سیستم تعبیه شده بدون برداشتگر انرژی.. 22

3-2-1  الگوریتم زمانبندی MILP وLEDF.. 23

3-3  عوامل مشترک در زمانبندی سیستمهای بیدرنگ برداشتگر انرژی.. 24

3-4  الگوریتمهای زمانبندی سیستم تعبیه شده مبتنی بر برداشتگر انرژی.. 25

3-4-1 روش زمانبندی LSA… 25

3-4-2  روش زمانبندی EA-DVFS.. 30

3-4-3  روش  زمانبندی AS-DVFS.. 33

3-4-4  روش زمانبندی LM-APM…. 35

3-4-5  روش زمانبندی HA-DVFS.. 41

3-4-6   الگوریتم انتخاب فرکانس باتوجه به وضعیت سیستم.. 48

3-5  نتیجه گیری.. 54

فصل چهارم : الگوریتم پیشنهادی

4-1 مقدمه. 55

4-2  ذخیره ساز انرژی.. 56

4-2-1  مزایای ابرخازن در برابر باطری با قابلیت شارژ مجدد. 56

4-2-2  معایب ابرخازن در برابر باطری با قابلیت شارژ مجدد. 57

4-3  مدل سیستم.. 61

4-3-1  مدل برداشتگر انرژی.. 61

4-3-2  مدل پردازنده. 61

4-3-3  مدل ذخیره ساز انرژی.. 62

4-3-4  مدل وظیفه. 63

4-4  الگوریتم زمانبندی بیدرنگ….. 63

4-4-1  انتخاب بازه زمانی.. 65

4-4-2  محاسبه انرژی مورد نیاز برای اجرای وظایف موجود در بازه. 65

4-4-3  محاسبه موجودیت انرژی.. 66

4-5  نتیجه گیری.. 74

فصل پنجم : شبیه سازی و نتیجه گیری

5-1 مقدمه. 75

5-2 تنظیمات اولیه. 75

5-3  مقایسه نرخ خطای سررسید.. 78

5-4  کمترین ظرفیت ذخیره سازی برای داشتن نرخ خطای سررسید صفر. 85

5-5  سودمندی انرژی.. 87

5-6  نرخ خطای سررسید در حالت عدم وجود واحد ذخیره ساز انرژی.. 89

5-7 : بررسی سربار زمانبندی.. 89

5-8  نتیجه گیری.. 90

5-9  پیشنهادات… 91

مراجع. 92

فهرست شکل­ها

شکل 1-1 : نمودار مشخصات یک وظیفه. 11

شکل 2-1 : نوع اول سیستم برداشتگر انرژی.. 16

شکل3-1 : منحنی توان در روش LSA… 26

شکل 3-2 : مدل سیستم روش LM-APM… 36

شکل 3-3 :  شبه کد الگوریتم HA_DVFS قسمت تنظیم بارکاری پردازنده و انتخاب پویای ولتاژ و فرکانس…. 44

شکل 3-4 : زمانبندی دو وظیفه. 45

شکل 3-5 : شبه کد الگوریتم بهره وری از انرژی سرریز شده. 46

شکل 4-1 : اتصال دو باطری برای جداسازی فازهای شارژ و دشارژ. 59

شکل 4-2: مدل سیستم پیشنهادی.. 61

شکل 4-3: محاسبه dl در حالت Edemand = EH(tc , Dmax) + ES(tc). 68

شکل 4-4 : شبه کد الگوریتم پیشنهادی.. 73

شکل 5-1 : نمودار توان برداشت PH(t). 76

شکل 5-2 : مقایسه نرخ خطای سررسید الگوریتم پیشنهادی با سایر الگوریتم ها 79

شکل 5-3 نمودار خطی تغییرات نرخ خطای سررسید الگوریتم ها در مقادیر متفاوت بهره وری.. 80

شکل 5-4 :  4 نمونه گیری از انرژی خورشیدی.. 80

شکل 5-5 : مقایسه نرخ خطای سررسید برای 5000 مجموعه وظیفه. 81

شکل 5-6 : مقایسه نرخ خطای الگوریتم ها در مقادیر مختلف ظرفیت باطری و بهره وری.. 83

شکل 5-7 : مقایسه نرخ خطای سررسید در حالت ذخیره ساز دوگانه و باطری.. 84

شکل 5-8 : مقایسه نرخ خطای سررسید در مقادیر مختلف ذخیره سازی باطری و ابرخازن.. 85

شکل 5-9 : مقایسه حداقل ظرفیت واحد ذخیره سازی برای داشتن خطای سررسید صفر. 86

شکل 5-10: نمودار کارایی انرژی در مقادیر مختلف بهره وری.. 88

شکل 5-11 : مقایسه نرخ خطای سررسید در دو حالت صحت و حذف واحد ذخیره ساز انرژی.. 89

فهرست جدول­ها

جدول 4-1 : مقایسه باطری و ابرخازن.. 58

جدول 4-2 : حالات کاری باطری های شکل4-1. 59

جدول 5-1 : مشخصات پردازنده XScale اینتل.. 76

جدول 5-2: نرخ خطای سررسید الگوریتم HA-DVFS براساس شکل 5-4. 80

جدول 5-3 : محاسبه سربار زمانبندی الگوریتم ها 90

فصل اول

فصل اول: توصیف مسئله

1-1 مقدمه

در سالهای اخیر با رشد و توسعه کامپیوترها در همه جنبه­های زندگی بشر و افزایش نیازهای روزمره و گسترش برنامه‌های کاربردی[1]، نیاز به طراحی و توسعه سیستم­های تعبیه­شده[2] بیش از پیش مورد توجه قرار گرفته است. سیستم‌های تعبیه‌شده، ابزارهای محاسباتی هستند که درون بخش عظیمی از محصولات و کاربردهای روزمره جاسازی شده­اند. سیستم­های پردازش اطلاعات در تجهیزات ارتباط از راه دور، سیستم­های حمل و نقل، تلفن همراه، اسباب بازی، دوربین و… مثال­هایی از سیستم‌های تعبیه‌شده می­باشند. این سیستم­ها به دلیل خاص­منظوره بودن، جایگزین تجاری مناسب و ماندنی برای کامپیوترها و یا ابزارهای همه منظوره نیستند. همانطورکه برنامه‌های کاربردی بصورت تصاعدی پیچیده می­شوند با پیچیدگی ابزارهای محاسباتی تعبیه‌شده نیز مواجه می‌شویم. اکثر این سیستم­ها دارای محدودیت­های زمانی بوده و نیازمند اجرای وظایف[3] در بازه زمانی خاص می­باشند بنابراین وجود یک زمانبند[4] مناسب برای سیستم­های بی­درنگ[5] تعبیه شده، امری ضروری است. الگوریتم زمانبندی مناسب، یکی از قسمت­های مهم سیستم­های بی­درنگ می­باشد تا بتواند منابع مورد نیاز وظایف را در زمان مناسب در اختیار آن­ها قرار داده و وظایف بتوانند در زمان مناسب اجرا شوند. علاوه­ براین، محیط­های کاری این سیستم­ها، ضرورت استفاده از منبع انرژی مناسب را برای کاربردهای بی­درنگ ایجاب می­کند بنابراین در کنار محدودیت زمانی بحث مدیریت انرژی[6] و منبع انرژی نیز بسیار حائز اهمیت است. اغلب سیستم­های تعبیه شده، مبتنی بر باطری هستند و طول عمر این سیستم­ها نیز وابسته به طول عمر باطری می­باشد بنابراین در بسیاری از مواقع که منبع انرژی دائمی در دسترس نیست استفاده از منابع تجدیدپذیر انرژی[7] می­تواند مورد توجه قرار گیرد. بنابراین یکی از راهکارهای موجود پیش پای طراحان سیستم­های تعبیه­شده بی­درنگ، استفاده از منابع انرژی محیطی و برداشتگرهای انرژی[8] است. این منابع می­توانند شامل انرژی خورشیدی، حرارتی و شیمیایی باشند و یا حتی انرژی جنبشی حاصل از امواج دریا و یا حرکت دست و پای انسان و سایر موجودات زنده نیز می­تواند بعنوان منبع انرژی در اختیار سیستم­های تعبیه­شده قرار گیرد. در این سیستم­ها برخلاف سیستم­های مبتنی بر باطری سنتی که سیستم، بعد از اتمام انرژی موجود در باطری، دیگر قادر به ادامه عملیات خود نیست، می­توانند با استفاده از باطری با قابلیت شارژ مجدد[9]، انرژی را از محیط پیرامون خود دریافت کرده و در باطری و یا سایر ذخیره­سازهای انرژی همچون خازن، ذخیره و در اختیار سیستم قرار دهند. از جمله سیستم­های تعبیه­شده ­بی­درنگ که استفاده از انرژی محیطی می­تواند نقش بسیار مهمی در جهت افزایش کارایی این سیستم­ها داشته باشد عبارتند از : دستگاههای خودپرداز، سیستم­های تعبیه­شده موجود در اتوموبیل­ها (سیستم ضد قفل و دزدگیر و …)، سیستم­های تعبیه­شده موجود در اتاق عمل و موارد پزشکی، شبکه­های حسگر ، سیستم­های کنترل از راه دور و ربات­ها خصوصا ربات­های مین­یاب و امداد و نجات و … که در همه این موارد اجرای به موقع و صحیح عملیات سیستم بسیار مهم می­باشد. بنابراین طول عمر، پیوستگی عملیات و کارایی این سیستم­ها بسیار حائز اهمیت است که استفاده از تکنیک برداشت انرژی محیطی درجهت بهبود موارد گفته شده می­تواند نقش موثری  داشته باشد.

برای دانلود متن کامل پایان نامه اینجا کلیک کنید

لینک بالا اشتباه است

برای دانلود متن کامل اینجا کلیک کنید

       

:: بازدید از این مطلب : 775

دانشگاه شیراز

پایان نامه دوره کارشناسی ارشد مهندسی کامپیوتر(هوش مصنوعی)

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

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

جناب آقای دکتر منصور ذوالقدری جهرمی

تابستان92

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

(در فایل دانلودی نام نویسنده موجود است)

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

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

چکیده

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

فهرست مطالب

عنوان                                                                                                                صفحه

فصل 1 : مقدمه­……………………………………………………………………………………………………………………………1

1-1- پیشگفتار…………………………………………………………………………………………………………………………….2

1-2- موتورهای جستجوگر…………………………………………………………………………………………………………2

1-2-1- موتورهای جستجوگر پیمایشی……………………………………………………………………………………..3

1-2- 2- فهرست­های تکمیل دستی…………………………………………………………………………………………..3

1-2-3- موتورهای جستجوگر ترکیبی………………………………………………………………………………………..4

1-2-4- ابرجستجوگرها……………………………………………………………………………………………………………….4

1-3- سیستم­های پیشنهادگر……………………………………………………………………………………………………..5

1-3-1- سیستم پیشنهادگر بر اساس فیلترینگ اشتراکی…………………………………………………………7

1-3-2- سیستم پیشنهادگر بر اساس محتوا………………………………………………………………………………8

1-3-3- سیستم پیشنهادگر بر اساس آمار گیری……………………………………………………………………….8

1-3-4- سیستم پیشنهادگر بر اساس سود…………………………………………………………………………………9

1-3-5- سیستم پیشنهادگر بر اساس دانش………………………………………………………………………………9

1-3-6- سیستم پیشنهادگر ترکیبی…………………………………………………………………………………………..9

1-4- بررسی سایت MovieLens…………………………………………………………………………………………..10

1-5- اهداف پایان نامه……………………………………………………………………………………………………………..13

1-6- ساختار پایان نامه…………………………………………………………………………………………………………….14

فصل 2 : روش فیلترینگ اشتراکی……………………………………………………………………………………………15

2-1- پیشگفتار………………………………………………………………………………………………………………………….16

2-2- مروری بر کارهای انجام شده در این راستا……………………………………………………………………..16

2-3- مبانی فیلترینگ اشتراکی………………………………………………………………………………………………..21

2-4-  وظایف فیلترینگ اشتراکی…………………………………………………………………………………………….22

2-4-1- پیشنهاد……………………………………………………………………………………………………………………….23

2-4-2- پیش­بینی…………………………………………………………………………………………………………………….23

2-5- دسته بندی متدهای فیلترینگ اشتراکی……………………………………………………………………….23

2-5-1- فیلترینگ اشتراکی مبتنی بر حافظه…………………………………………………………………………24

2-5-1-1- فیلترینگ اشتراکی مبتنی بر حافظه با پیش­بینی بر اساس کاربران…………………….25

2-5-1-2- فیلترینگ اشتراکی مبتنی بر حافظه با پیش­بینی بر اساس اقلام…………………………25

2-5-1- 3- تفاوت فیلترینگ اشتراکی بر اساس کاربران و بر اساس اقلام……………………………..26

2-5-2- فیلترینگ اشتراکی مبتنی بر مدل……………………………………………………………………………..26

2-6- نحوه­ تشخیص علائق کاربران………………………………………………………………………………………….27

2-6-1- تشخیص علائق به صورت صریح…………………………………………………………………………………27

2-6-2- تشخیص علائق به صورت ضمنی……………………………………………………………………………….27

2-7- محاسبه­ شباهت……………………………………………………………………………………………………………….28

2-7-1- معیار همبستگی پیرسون……………………………………………………………………………………………28

2-7-2- معیار اندازه­گیری کسینوس………………………………………………………………………………………..29

2-8- انتخاب همسایه……………………………………………………………………………………………………………….30

2-8-1- استفاده از حد آستانه………………………………………………………………………………………………….30

2-8-2- انتخاب تعداد ثابتی از همسایگان……………………………………………………………………………….30

2-9- پیش­بینی و تخمین رتبه…………………………………………………………………………………………………31

2-9-1- استفاده از امتیازهای خام……………………………………………………………………………………………31

2-9-2- استفاده از امتیازهای نرمال شده………………………………………………………………………………..31

2-10- مشکلات فیلترینگ اشتراکی………………………………………………………………………………………..32

2-10-1- پراکنده بودن داده…………………………………………………………………………………………………….32

2-10-2- مقیاس پذیری………………………………………………………………………………………………………….32

2-10-3- اقلام مشابه……………………………………………………………………………………………………………….33

2-10-4- گری­شیپ…………………………………………………………………………………………………………………33

2-11- بررسی چگونگی کارکرد سایت آمازون…………………………………………………………………………33

فصل 3 : روش محتوا محور………………………………………………………………………………………………………36

3-1- پیشگفتار………………………………………………………………………………………………………………………….37

3-2- روند کار روش محتوا محور……………………………………………………………………………………………..37

3-2-1- تحلیل­گر محتوا…………………………………………………………………………………………………………..38

3-2-2- یادگیرنده نمایه …………………………………………………………………………………………………..39

3-2-3- جزء فیلترینگ…………………………………………………………………………………………………………….42

3-3- مزایای روش محتوا محور………………………………………………………………………………………………..42

3-3-1- استقلال کاربر……………………………………………………………………………………………………………..42

3-3-2- شفافیت……………………………………………………………………………………………………………………….42

3-3-3- قلم جدید…………………………………………………………………………………………………………………….43

3-4- معایب روش محتوا محور…………………………………………………………………………………………………43

3-4-1- کمبود محتوا……………………………………………………………………………………………………………….43

3-4-2- خصوصی سازی افزون…………………………………………………………………………………………………43

3-4-3- کاربر جدید………………………………………………………………………………………………………………….44

فصل 4 : روش پیشنهادی………………………………………………………………………………………………………….45

4-1- پیشگفتار………………………………………………………………………………………………………………………….46

4-2- مروری بر کارهای انجام شده در این راستا……………………………………………………………………..46

4-3- مقدمه­ای بر روش پیشنهادی…………………………………………………………………………………………..48

4-4- روش پیشنهادی………………………………………………………………………………………………………………48

4-4-1- پیش­ پردازش………………………………………………………………………………………………………………49

4-4-1-1- پیش پردازش بر روی پایگاه داده MovieLens………………………………………………..49

4-4-1-2- پیش پردازش بر روی پایگاه داده EachMovie………………………………………………..50

4-4-2- وزن­دهی به اقلام…………………………………………………………………………………………………………51

4-4-3- انتخاب­همسایگی…………………………………………………………………………………………………………53

4-4-4- پیش­بینی……………………………………………………………………………………………………………………54

فصل 5 : آزمایش­ها و نتایج……………………………………………………………………………………………………….56

5-1- پایگاه داده­های مورد استفاده…………………………………………………………………………………………..57

5-2- نحوه­ اجرای روش پیشنهادی روی پایگاه داده­ MovieLens……………………………………….57

5-3- نحوه­ اجرای روش پیشنهادی روی پایگاه داده ٍEachMovie……………………………………….58

5-4- معیارهای­ارزیابی………………………………………………………………………………………………………………58

5-4-1- میانگین خطای مطلق…………………………………………………………………………………………………58

5-4-2- دقت و فراخوانی………………………………………………………………………………………………………….59

5-4-3- معیار ارزیابیF1…………………………………………………………………………………………………………60

5-5- ارزیابی روش پیشنهادی توسط معیارهای معرفی شده…………………………………………………..61

فصل 6 : بحث و نتیجه­گیری…………………………………………………………………………………………………….66

6-1- بحث…………………………………………………………………………………………………………………………………67

6-2- نتیجه­گیری……………………………………………………………………………………………………………………..67

6-4- پیشنهادات……………………………………………………………………………………………………………………….68

مراجع………………………………………………………………………………………………………………………………………..69

فهرست جدول ها

عنوان و شماره                                                                                                   صفحه

جدول شماره­ 1 : نمونه­هایی از سیستم­های پیشنهادگر و اقلام پیشنهادی آنها…………………………7

جدول شماره­ 2 : مقایسه­ میانگین خطای مطلق روش پایه و روش پیشنهادی، اعمال شده بر MovieLens……………………………………………………………………………………………………………………………61

جدول شماره­ 3 : مقایسه­ میانگین خطای مطلق روش پایه و روش پیشنهادی، اعمال شده بر EachMovie……………………………………………………………………………………………………………………………61

جدول شماره­ 4 : مقایسه­ معیار دقت روش پایه و روش پیشنهادی، اعمال شده  بر 

MovieLens……………………………………………………………………………………………………………………………61

جدول شماره­ 5 : مقایسه_­ معیار دقت روش پایه و روش پیشنهادی، اعمال شده بر

EachMovie …………………………………………………………………………………………………………………………..62

جدول شماره­ 6 : مقایسه­ معیار فراخوانی روش پایه و روش پیشنهادی، اعمال شده بر MovieLens……………………………………………………………………………………………………………………………62

جدول شماره­ 7 : مقایسه­ معیار فراخوانی روش پایه و روش پیشنهادی، اعمال شده بر EachMovie………………...…………………………………………………………………………………………………………62

جدول شماره­ 8 : مقایسه­ معیارF1 روش پایه و روش پیشنهادی، اعمال شده بر MovieLens……………………………………………………………………………………………………………………………62

جدول شماره 9 : مقایسه­ معیارF1 روش پایه و روش پیشنهادی، اعمال شده بر

EachMovie……………………………………………………………………………………………………………………………62

جدول شماره 10 : مقایسه­ میانگین خطای مطلق روش پیشنهادی با روش­های[19]  و [20]…………………………………………………………………………………………………………………………………………..65

فهرست تصاویر

عنوان و شماره                                                                                                   صفحه

شکل شماره­ 1:  نمونه­هایی از موتورهای جستجوگر………………………………………………………………….5

شکل شماره­ 2 : نمونه صفحه­ای از سایت Movielens………………………………………………………….11

شکل شماره­ 3 : نمونه صفحه­ درخواست امتیازدهی Movielens از کاربر…………………………….12

شکل شماره­­ 4 : نمونه صفحه­ فیلم­های پیشنهادی از سوی Movielens  به کاربر………………13

شکل شماره­ 5 : نمونه ماتریس امتیازدهی کاربران – اقلام………………………………………………………22

شکل شماره­ 6:  فیلترینگ اشتراکی مبتنی بر اقلام………………………………………………………………..25

شکل شماره­ 7 : فیلترینگ اشتراکی مبتنی بر کاربران…………………………………………………………….25

شکل شماره­ 8 : روند تولید پیشنهاد در آمازون……………………………………………………………………….34

شکل شماره­ 9 : نمونه صفحه­ای از سایت آمازون…………………………………………………………………….35

شکل شماره ­10 : ارائه­ پیشنهاد بر اساس کارت خرید مشتری……………………………………………….35

شکل شماره­ 11 : روند کار روش محتوا محور………………………………………………………………………….38

شکل شماره 12 :  نمونه صفحه­ای از سایت آمازون…………………………………………………………………40

شکل شماره 13  :استفاده از روش محتوا محور در سایت آمازون…………………………………………..41

شکل شماره­ 14 : نمایش مفاهیم دقت و فراخوانی در حوزه بازیابی اطلاعات………………………..59

شکل شماره­ 15:  رابطه­ معیار فراخوانی با معیار دقت……………………………………………………………..60

شکل شماره­ 16:  مقایسه­ میانگین خطای مطلق روش پایه و روش پیشنهادی، اعمال شده بر

MovieLens……………………………………………………………………………………………………………………………63شکل شماره­ 17:  مقایسه­ میانگین خطای مطلق روش پایه و روش پیشنهادی، اعمال شده بر

EachMovie…………………………………………………………………………………………………………………………...63

شکل شماره­ 18:  مقایسه­ معیار دقت، فراخوانی و F روش پایه و روش پیشنهادی، اعمال شده بر EachMovie……………………………………………………………………………………………………………………...64

شکل شماره­ 19:  مقایسه­ معیار دقت، فراخوانی و F روش پایه و روش پیشنهادی، اعمال شده بر MovieLens………………………………………………………………………………………………………………………..64

مقدمه­

1-1- پیشگفتار

پیدایش اینترنت و وب جهان گستر[1] موجب شده است که در رابطه با هر موضوع قابل تصور، حجم بسیار زیادی از اطلاعات وجود داشته باشد که کاربران[2] بتوانند با استفاده از آن نیاز اطلاعاتی خود را برطرف سازند. افزایش روز افزون اطلاعات باعث شد که مشکل سربار اطلاعات[3] به وجود آید و کاربران به تنهایی قادر به برطرف کردن نیازهای خود نباشند. . زیرا کاربران مجبور بودند به صورت بر خط[4]  تمامی صفحات را جستجو کنند تا بتوانند آن قسمتی را که مورد نیازشان است پیدا کنند. به همین دلیل موتورهای جستجوگر[5]  به وجود آمدند تا کاربران بتوانند با استفاده از آنها بدون نیاز به بررسی تعداد زیادی از صفحات به اطلاعات مورد نظرشان دسترسی پیدا کنند.

برای دانلود متن کامل پایان نامه اینجا کلیک کنید

لینک بالا اشتباه است

برای دانلود متن کامل اینجا کلیک کنید

       

:: بازدید از این مطلب : 593

دانشگاه شیراز

دانشکده مهندسـی

پایان‌نامه کارشناسی ارشد در رشته مهندسی کامپیوتر (هوش مصنوعی)

ارائه یک شاخص نوین برای سنجش سطح خستگی مغزی در حین فعالیت ذهنی از روی سیگنال EEG

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

دکتر رضا بوستانی

شهریور 1390

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

(در فایل دانلودی نام نویسنده موجود است)

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

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

فهرست مطالب

عنوان                                                                                                              صفحه

عنوان                                                                                                              صفحه

فهرست جداول

عنوان و شماره                                                                                                   صفحه

فهرست شکل ها

عنوان                                                                                                                صفحه

فصل اول

1- مقدمه

• مقدمه

خستگی پدیده ای رایج در زندگی روزمره ماست. یک تعریف مشترک از خستگی این است که خستگی حالتی است که به دنبال یک بازه از فعالیت ذهنی یا بدنی ایجاد می‌شود که توسط کاهش در توانایی برای کار کردن مشخص می‌شود.

اولین بار مفهوم خستگی ذهنی توسط گرندجین[1] معرفی شد [1]، که به وضوح خستگی ذهنی را از خستگی فیزیکی متفاوت کرد. او خستگی بدنی را در اثر کاهش عملکرد سیستم عضلانی و خستگی ذهنی را با کاهش عملکرد ذهنی و احساس خستگی تعریف کرد.

خستگی دارای پیامدهای عمده ای در تلفات جاده و در حال حاضر یکی از مساﺋﻞ عمده در صنعت حمل و نقل است. با توجه به کار های اولیه در این مورد، خستگی راننده 35-45 درصد از تصادفات جاده را تشکیل می داده است [2]. علاوه بر این خستگی باعث کاهش کارایی ذهنی خصوصاً در افراد متخصصی که در حین کار فعالیت ذهنی بسیار بالایی دارند (برنامه نویسان حرفه‌ای کامپیوتر و طراحان سیستم‌های صنعتی که در قسمت‌های R&D شرکت‌ها کار می‌کنند) و همچنین باعث افزایش زمان پاسخ گویی در افراد می‌شود. در نتیجه علاوه بر اثراتی که خستگی ذهنی بر پایین آمدن کارایی افراد در موقعیت‌های شغلی مختلفی دارد، می‌تواند عامل مهمی در تصادفات جاده‌ها و سنجش کارایی افراد در کارخانجات باشد. در نتیجه، از آنجا که با خسته شدن، فرد در اجرای کار با قدرت عملکرد کافی دچار مشکل می‌شود و با توجه به رابطه‌ای که خستگی در افزایش احتمال تصادفات در جاده‌ها و کارخانجات دارد [3 و 4]، مشخص کردن میزان خستگی فرد، در کاهش چنین تصادفاتی و همچنین افزایش قدرت عملکرد افراد ضروری به نظر می‌رسد. در نتیجه ما در این تحقیق به بررسی خستگی ذهنی پرداخته‌ایم (در ادامه خستگی به معنی خستگی ذهنی استفاده شده است).

برای دانلود متن کامل پایان نامه اینجا کلیک کنید

لینک بالا اشتباه است

برای دانلود متن کامل اینجا کلیک کنید

       

:: بازدید از این مطلب : 616

دانشگاه شیراز

دانشکده‌ی مهندسی برق و کامپیوتر

پایان‌نامه کارشناسی ارشد در رشته­­ی

مهندسی کامپیوتر (نرم‌افزار)

بررسی الگوریتم های تخصیص مجدد در گریدهای محاسباتی و ارائه یک الگوریتم کارا

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

دکتر غلامحسین دستغیبی فرد

اسفند ماه 1392

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

(در فایل دانلودی نام نویسنده موجود است)

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

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

چکیده

شبکه­های تورین محاسباتی (گرید) زمینه‌ای را فراهم آورده است که بتوان از منابع ناهمگن در نقاط مختلف جغرافیایی برای حل مسائل پیچیده علمی، مهندسی و تجارت استفاده کرد. عملیات زمانبندی نقش کلیدی در عملکرد گرید ایفا می­کند. بدلیل پویایی منابع و تخمین نادقیق زمان اجرایی و … عملیات زمانبندی باید مکانیسم هایی را برای پشتیبانی از تحمل خطا، افزایش بهره وری از منابع و کاهش زمان اتمام کارها استفاده کند، که به آن زمانبندی مجدد گویند. در این پایان نامه دو الگوریتم زمانبندی کارهای مستقل و یک الگوریتم زمانبندی جریان کارها با در نظر گرفتن پویایی محیط ارائه شده که اهداف آنها کاهش زمان اجرا، افزایش بهره­وری از منابع، ایجاد توازن بار و پشتیبانی از تحمل خطا می باشد.

کلید واژه: گرید محاسباتی، زمانبندی، زمانبندی مجدد، جریان کار.

فهرست مطالب

عنوان                                                                                                                صفحه

1- مقدمه ………………………………………………………………………………………………………………  1

1-1 مقدمه………………………………………………………………………………………………………………………………………………. 1

1-2 ضرورت اجرا……………………………………………………………………………………………………………………………………. 2

1-3 هدف از اجرای پایان­نامه………………………………………………………………………………………………………………… 3

1-4 مراحل انجام پایان­نامه…………………………………………………………………………………………………………………….. 4

1-5 ساختار پایان­نامه………………………………………………………………………………………………………………………. 4

2- مفاهیم اولیه زمانبندی و مروری بر کارهای گذشته……………………………………………. 5

2-1 مقدمه……………………………………………………………………………………………………………………………………….. 5

2-2 ساختار متمرکز……………………………………………………………………………………………………………………….. 7

2-3 ساختار غیر متمرکز و یا توزیعی……………………………………………………………………………………………. 8

2-4 فرایند زمانبندی گرید و اجزای آن ………………………………………………………………………………………. 10

2-5 انواع زمانبند …………………………………………………………………………………………………………………………… 11

2-6 انواع کارها ………………………………………………………………………………………………………………………………. 12

2-7 نحوه­ی زمانبندی ……………………………………………………………………………………………………………………. 14

2-8 وظایف فرازمانبند …………………………………………………………………………………………………………………… 14

2-8-1 نگاشت کار …………………………………………………………………………………………………………………….. 15

2-9 گذری بر تحقیقات پیشین …………………………………………………………………………………………………….. 17

2-9-1 مفاهیم اولیه …………………………………………………………………………………………………………………. 17

2-9-2 الگوریتم ETF ……………………………………………………………………………………………………………….. 19

2-9-3 الگوریتم Myopic …………………………………………………………………………………………………………. 19

2-9-4 الگوریتم کمترین کمترین، بیشترین کمترین، حق رای ………………………………………….. 19

2-9-5 الگوریتم HLEFT ………………………………………………………………………………………………………… 20

2-9-6 الگوریتم hybrid …………………………………………………………………………………………………………… 20

2-9-7 الگوریتم GRASP ……………………………………………………………………………………………………….. 21

2-9-8 الگوریتم CPOP …………………………………………………………………………………………………………… 21

2-9-9 الگوریتم PETS …………………………………………………………………………………………………………….. 22

2-9-10 الگوریتم HLEFT با نگاه به جلو ……………………………………………………………………………… 23

2-9-11 الگوریتم FTBAR …………………………………………………………………………………………………….. 23

2-9-12  الگوریتم TSB ………………………………………………………………………………………………………….. 24

2-10  جمع بندی ………………………………………………………………………………………………………………………… 24

3- الگوریتم­های پیشنهادی ……………………………………………………………………………….. 25

3-1 مقدمه ……………………………………………………………………………………………………………………………………… 25

3-2 الگوریتم Asuffrage ……………………………………………………………………………………………………………… 27

3-3 الگوریتم MaxSuffrage ……………………………………………………………………………………………………….. 28

3-4 الگوریتم DHLEFT……………………………………………………………………………………………………………….. 30

4- نتایج حاصل از ارزیابی و مقایسه الگوریتم های پیشنهادی ………………………………… 34

4-1 مقدمه ……………………………………………………………………………………………………………………………………… 34

4-2 محک ارزیابی براون…………………………………………………………………………………………………………………. 34

4-3 ارزیابی الگوریتم  Asuffrage………………………………………………………………………………………………… 36

4-4  ارزیابی الگوریتم  MaxSuffrage…………………………………………………………………………………………. 38

4-5  ارزیابی زمانبند الگوریتم پیشنهادی برای جریان کار………………………………………………………….. 40

4-6 ارزیابی الگوریتم DHLEFT…………………………………………………………………………………………………… 43

4-7 نتیجه گیری و پیشنهادات برای آینده …………………………………………………………………………………. 49

5- منابع…………………………………………………………………………………………………………… 50

فهرست جدول­ها

عنوان                                                                                                                صفحه

جدول 4-1 حالات ماتریس ETC………………………………………………………………………………………………………. 36

جدول 4-2 نتایج زمان اتمام آخرین کار الگوریتم Asuffrage……………………………………………………….. 37

جدول 4-3 نتایج درصد بهره­وری از منابع الگوریتم Asuffrage…………………………………………………….. 37

جدول 4-4 نتایج زمان اتمام آخرین کار الگوریتم MaxSuffrage…………………………………………………. 39

جدول 4-5 نتایج درصد بهره­وری از منابع الگوریتم MaxSuffrage………………………………………………. 39

جدول 4-6 مقادیر پارامتر N………………………………………………………………………………………………………………. 41

جدول 4-7 مقادیر پارامتر Fat……………………………………………………………………………………………………………. 41

جدول 4-8  مقادیر پارامتر Density………………………………………………………………………………………………….. 41

جدول 4-9  درصد خطا در تخمین زمان اجرایی…………………………………………………………………………….. 42

جدول 4-10  زمان رخداد رویداد………………………………………………………………………………………………………. 43

جدول 4-11 میانگین نتایج  زمان اتمام آخرین کار الگوریتم DHLEFT…………………………………….. 48

جدول 4-12 میانگین نتایج درصد بهره­وری از منابع الگوریتم DHLEFT……………………………………. 48

فهرست شکل­ها

عنوان                                                                                                                صفحه

شکل‏2-1 معماری زمانبندی متمرکز ………………………………………………………………………………………………… ……. 7

شکل‏2-2 معماری زمانبندی سلسله مراتبی …………………………………………………………………………………….. ……. 9

شکل ‏2-3 معماری زمانبندی غیرمتمرکز ………………………………………………………………………………………… ……. 9

شکل ‏2-4 معماری زمانبندی گرید …………………………………………………………………………………………………… 10

شکل ‏2-5 جریان کار …………………………………………………………………………………………………………………………. 13

شکل ‏2-6 نمونه ماتریس ETC …………………………………………………………………………………………………………. 14

شکل ‏2-7 گراف جهت دار بدون دور(DAG) ………………………………………………………………………………….. 18

شکل ‏2-8 جدول زمان اجرایی تخمینی …………………………………………………………………………………………… 18

شکل 3-1 شبه کد الگوریتم DHLEFT ………………………………………………………………………………………….. 33

شکل 4-1 نتایج زمان اتمام آخرین کار الگوریتم DHLEFT با Fat=0.1………………………………………. 44

شکل 4-2 نتایج زمان اتمام آخرین کار الگوریتم DHLEFT با Fat=0.3………………………………………. 45

شکل 4-3 نتایج زمان اتمام آخرین کار الگوریتم DHLEFT با Fat=0.5………………………………………. 45

شکل 4-4 نتایج زمان اتمام آخرین کار الگوریتم DHLEFT با Fat=0.7………………………………………. 46

شکل 4-5 نتایج درصد بهره­وری از منابع الگوریتم DHLEFT با Fat=0.1……………………………………. 46

شکل 4-6 نتایج درصد بهره­وری از منابع الگوریتم DHLEFT با Fat=0.3……………………………………. 47

شکل 4-7 نتایج درصد بهره­وری از منابع الگوریتم DHLEFT با Fat=0.5……………………………………. 47

شکل 4-8 نتایج درصد بهره­وری از منابع الگوریتم DHLEFT با Fat=0.7……………………………………. 48

مقدمه

اصطلاح “گرید” در اواسط دهه 1990 مطرح شده و زیر ساخت محاسبات گرید (محاسبات شبکه) در زمینه علم و مهندسی پیشرفته پیشنهاد شد [1].  ایده اصلی محیط گرید به اشتراک گذاری منابع محاسباتی است. امروزه، اکثر مردم بیشتر از حد نیاز، قدرت محاسباتی بر روی سیستم­های کامپیوتری خود دارند. از این رو کشف منابع محاسباتی توزیع شده در سطح جغرافیایی و استفاده از آنها برای حل برنامه­های کاربردی که قدرت محاسباتی بالایی نیاز دارند و باید در مدت زمان معین با هزینه مشخص اجرا شوند، ترویج پیدا کرد. چنین زیر ساخت هایی گرید محاسباتی نامیده می شود، و منجر به محبوبیت حوزه­ای به نام محاسبات گرید شده است [1].

از اتصال منابع محاسباتی مانند رایانه­های شخصی، ایستگاه­های کاری، خوشه­ها، سرویس دهنده­ها، ابررایانه­ها و …، توزیع شده در مناطق مختلف جغرافیایی شبکه­های تورین محاسباتی (گرید) پدید آمده است که به عنوان یک سکوی محاسبات برای حل مسائل مقیاس بزرگ در دانشگاه، پژوهش و صنعت مورد استفاده قرار می­گیرد[2].

یکی از عملیات اصلی تضمین کننده­ی کارایی در شبکه­های تورین محاسباتی، تخصیص منابع به کارها می­باشد. عملیات تخصیص منابع باید مکانیسم­هایی را برای پشتیبانی از تحمل خطا، اطمینان از اجرای حتمی کارها، افزایش بهره­وری از منابع و کاهش زمان اتمام کارها ارائه دهد. زمانبندی در محیط گرید، با توجه به توزیع جغرافیایی منابع و کاربران، نوسانات منابع، الزامات کیفیت سرویس از برنامه­های کاربردی و محدودیت­های اعمال شده توسط صاحبان منابع، جزء مسائل NP-complete می باشد[3].

برای دانلود متن کامل پایان نامه اینجا کلیک کنید

لینک بالا اشتباه است

برای دانلود متن کامل اینجا کلیک کنید

       

:: بازدید از این مطلب : 723

 دانشگاه شیراز

دانشکده مهندسی

پایان نامه کارشناسی ارشد در رشته مهندسی کامپیوتر(نرم افزار)

ارائه یک مدل مبتنی بر خصیصه جهت تحلیل احساس موجود در نوشتجات

استاد راهنما

دکتر سید مصطفی فخراحمد

شهریور 1393

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

(در فایل دانلودی نام نویسنده موجود است)

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

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

فهرست مطالب

فصل اول پیشگفتار. 1

1-1- مقدمه. 2

1-3- تحلیل احساس در متن. 6

1-4- اهداف رساله. 8

1-5- روش کار. 9

1-6- ساختار پایان نامه. 9

فصل دوم کارهای انجام شده 10

2-1- مقدمه. 11

2-2- تعریف مسئله. 11

2-3- گام اول تحلیل احساس در متن. 12

2-4- روش‌های مبتنی بر خصیصه‌های N-gram.. 13

2-5- الگوریتم‌های انتخاب خصیصه. 18

فصل سوم روش پیشنهادی. 22

3-1- پیش گفتار. 23

3-2- منابع مورد نیاز. 23

3-3- روش پیشنهادی اول. 25

3-3-1.               پیش پردازش اسناد 26

3-3-2.               برچسب گذاری ادات سخن. 29

3-3-3.               استخراج بردار خصیصه‌ها و ترکیب خصیصه‌ها 30

3-3-4.                اعمال الگوریتم انتخاب خصیصه. 33

3-4- روش پیشنهادی دوم 34

3-5- روش پیشنهادی سوم 37

3-5-1.               استخراج پلاریته کلمات و فیلتر بردار خصیصه. 38

فصل چهارم پیاده سازی و نتایج گرفته شده 47

4-1- مقدمه. 48

4-2- مجموعه داده‌ها 48

4-3- طبقه‌بندی داده‌ها 48

4-4- نتایج روش اول. 49

4-5- نتایج روش دوم 52

4-6- نتایج روش سوم 53

4-7- مقایسه روش پیشنهادی با روش‌های قبل. 53

8-4- نتایج اعمال روش پیشنهادی برای زبان فارسی54

4-9- کارهای آینده 58

مراجع و منابع. 59

فهرست الگوریتم ها

Algorithm 1 Documents_To_model. 33

Algorithm 2 Documents_To_model2. 35

Algorithm 3 Polarity_Filter. 40

فهرست تصاویر

شکل 1-1 دسته بندی متون……………………………………………………………………….. 5

شکل 1-2 تحلیلگر احساس در سطح کلمه………………………………………………………… 7

شکل 1-3 تحلیلگر احساس در سطح جمله………………………………………………………… 7

شکل 1-4 تحلیلگر احساس در سطح سند…………………………………………………………. 8

شکل 2-1 مهمترین الگوریتم های انتخاب خصیصه تک متغیره………………………………… 19

شکل 2-2 مهمترین روش های انتخاب خصیصه چند متغیره…………………………………… 21

شکل 3-1 Sentiwordnet………………………………………………………………….. 22

شکل 3-2 شمای کلی روش پیشنهادی اول……………………………………………………… 26

شکل 3-3 شمای پیش پردازش اسناد……………………………………………………………. 27

شکل3-4 برچسب گذار استنفورد………………………………………………………………… 30

شکل3-5 مجموعه خصیصه‌های پیشنهادی برای تحلیل احساس……………………………….. 32

شکل 3-6 شمای کلی روش پیشنهادی دوم……………………………………………………… 36

شکل 3-7 شمای کلی روش سوم………………………………………………………………… 38

 شکل3-8  شمای کلی روش پیشنهادی………………………………………………………….. 43

شکل3-9 برچسب گذار زبان فارسی……………………………………………………………… 44

شکل3-10 مجموعه خصیصه‌های پیشنهادی برای تحلیل احساس متون فارسی………………. 45

فهرست جداول

جدول 2-1 مجموعه خصیصه‌ها N-gram و مثال برای هر خصیصه. 15

جدول 2-2 مجموعه کاملی از خصیصه ها N-gram.. 16

جدول 3-1 لیست Stopwords. 28

جدول 3-2 مثال برای رفع ابهام با استفاده از برچسب ادات سخن. 31

جدول 3-3 کلمات هم معنای great. 35

جدول 3-3 محاسبه تفاضل نسبی پلاریتی کلمات. 39

جدول 3-5  مثال خصیصه استخراج شده از متن. 45

جدول 4-1 مجموعه داده های مورد استفاده در این رساله. 49

جدول 4-2 تعداد خصیصه‌های پس از اعمال الگوریتم انتخاب خصیصه. 50

جدول 4-3 مقایسه روش های پیشنهادی. 50

جدول 4-4 مقایسه نتایج روش پیشنهادی با روش پیشین. 52

جدول 4-5 تعداد کل خصیصه ها بدون اعمال الگوریتم انتخاب خصیصه. 53

جدول 4-6 مقایسه نتایج روش پیشنهادی با روش ارائه شده توسط عباسی و همکارانش.. 54

جدول 4-7 مقایسه نتایج روش پیشنهادی با روش ارائه شده توسط آگاروال و میتال. 54

جدول4-8- نتایج طبقه‌بندی متون فارسی. 57

فصل اول پیشگفتار

مقدمه

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

متن کاوی = استخراج اطلاعات: در این تعریف متن کاوی متناظر با استخراج اطلاعات در نظر گرفته می‌شود (استخراج واقعیت‌ها از متن).

برای دانلود متن کامل پایان نامه اینجا کلیک کنید

لینک بالا اشتباه است

برای دانلود متن کامل اینجا کلیک کنید

       

:: بازدید از این مطلب : 950

دانشگاه شیراز

دانشکده مهندسـی برق و کامپیوتر

پایان‌نامه کارشناسی ارشد در رشته مهندسی کامپیوتر (هوش مصنوعی)

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

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

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

بهمن 1392

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

(در فایل دانلودی نام نویسنده موجود است)

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

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

چکیده

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

فهرست مطالب

عنوان                                                                                                                                        صفحه

فصل اول: مقدمه

• مسئله ارضاء محدودیت(CSP: Constraint Satisfaction Problem) …………………………………….. 3
  • تعریف مسئله ارضاء محدودیت(CSP: Constraint Satisfaction Problem):……………………………………….. 3
  • الگوریتمهای کلاسیک مسائل ارضاء محدودیت…………………………………………………………………………………………………….. 5
  • CSP به عنوان یک مسئله جستجو……………………………………………………………………………………………………………………..  7
  • بهبود کارآیی الگوریتمهای جستجوتوسط توابع اکتشافی یا به عبارتی هیوریستیک ها………………………………………. 8
  • محدودیتهای ویژه………………………………………………………………………………………………………………………………………………… 12
  • کاربرد جستجوهای محلی در حل مسائل ارضاء محدودیت……………………………………………………………………………….. 12
  • ساختار مسئله………………………………………………………………………………………………………………………………………………………. 12
• سیستمهای چند عامله………………………………………………………………………………………………………………………….. 14
• حل مسائل CSP توسط سیستمهای چند عامله؛(DCSP)………………………………………………………………. 16

فصل دوم: مروری بر تحقیقات پیشین

• مرور کلی………………………………………………………………………………………………………………………………………………. 19
• الگوریتمهای هرس دامنه……………………………………………………………………………………………………………………… 22
  • الگوریتم تصفیه…………………………………………………………………………………………………………………………………………………… 22
  • الگوریتم فرا استدلال………………………………………………………………………………………………………………………………………….. 25
• الگوریتمهای اکتشافی…………………………………………………………………………………………………………………………… 27
  • الگوریتم عقبگرد نامتقارن………………………………………………………………………………………………………………………………………. 28
  • الگوریتم الزام ضعیف نامتقارن…………………………………………………………………………………………………………………………………. 32
• الگوریتمهایی که از ترکیب روشهای متمرکز و توزیع شده استفاده می کنند…………………………………….. 33
  • الگوریتم APO……………………………………………………………………………………………………………………………………………………….. 33
• الگوریتمهای ناقص……………………………………………………………………………………………………………………………….. 37
  • الگوریتم DBA ……………………………………………………………………………………………………………………………………………………  37
  • الگوریتمهای مبتنی بر کلونی مورچه ها در حل مسائل ارضاء محدودیت توزیع شده…………………………………………. 37

فصل سوم: طراحی و پیاده سازی روشهای پیشنهادی برای مسائل DCSP و بررسی نتایج حاصله

• معیارهای ارزیابی کیفیت روشهای حل مسائل ارضاء محدودیت توزیع شده…………………………………. 44

3-1-1- میانگین زمان اجرای الگوریتم با افزایش مقیاس مسأله……………………………………………………………………………………….  45

3-1-2- میانگین تعداد چرخه های اجرا شده تا رسیدن به یک راه حل …………………………………………………………………………..  45

3-1-3- تعداد پیام های ارسال و دریافت شده…………………………………………………………………………………………………………………….  45

3-1-4- NCCC ……………………………………………………………………………………………………………………………………  45

3-1-5- قانونی و کامل بودن………………………………………………………………………………………………………………………………………………… 46

• محکها و مجموعه داده ای مورد استفاده برای آزمایشات………………………………………………………………. 45

3-2-1- مسأله n-وزیر ………………………………………………………………………………………………………………………………………………………..  46

3-2-2- مسأله رنگ­آمیزی گراف ………………………………………………………………………………………………………………………………………..  47

3-2-3- مسائل زمانبندی ……………………………………………………………………………………………………………………………………………………  48

3-2-4- مسائل ارضاء محدودیت باینری …………………………………………………………………………………………………………………………….  51

3-3- طراحی و پیاده سازی روشهای پیشنهادی و نتایج حاصله از آنها………………………………………………………. 52

3-3-1- استفاده از ترکیب الگوریتمهای تکاملی و سیستمهای چندعامله برای حل مسائل ارضاء محدودیت ………………  52

3-3-2- قدرت مورچه ها در حل مسائل ارضاء محدودیت توزیع شده………………………………………………………………………………  60

فصل چهارم: روش جدید ارائه شده

4-1- مروری بر مفاهیم و موضوعات مورد بحث دراین روش پیشنهادی…………………………………………………….. 69

• توصیف مسائل ارضاء محدودیت توزیع شده؛(DCSP) ………………………………………………………………………………..  69
• تعریف محدودیت Alldiff یا Alldifferent ………………………………………………………………………………………………. 70
• توابع اکتشافی …………………………………………………………………………………………………………………………………………………… 70

• تقسیم بندی الگوریتم های مطرح شده برای مسائل DCSP ……………………………………………………………. 71

4-3- توصیف روش جدید ارائه شده و جزئیات پیاده سازی آن…………………………………………………………………… 73

4-4- حل یک مثال با استفاده از این الگوریتم…………………………………………………………………………………………….. 80

4-5- ارزیابی و مقایسه الگوریتم ما با دیگر روشها……………………………………………………………………………………….  82

4-6- نتیجه گیری و برشمردن مزایا و معایب این روش……………………………………………………………………………..  84

فصل پنجم: نتیجه گیری

5-1- نتیجه گیری………………………………………………………………………………………………………………………………………  87

5-2- پیشنهادات و کارهای آینده……………………………………………………………………………………………………………….  89

فهرست منابع………………………………………………………………………………………………………………………..  90

 فهرست تصاویر

عنوان                                                                                                                                        صفحه

شکل 1-1  مثالی از مساله CSP [4] …………………………………………………………………………………………………………………. 4

شکل 1-2  یک طرح جامع از به کار بردن تکنیکهای ارضاء محدودیت برای حل مسائل [54] ……………………….. 5

شکل 1-3 (الف) نواحی استرالیا (ب) عملکرد توابع اکتشافی مختلف بر روی این نقشه [2] …………………………………………… 11 شکل 1-4 زیرمسأله های مستقل در گراف محدودیت [2] ……………………………………………………………………………… 13

شکل 1-5  کاهش گراف محدودیت به درخت توسط حذف گرهها [2] ………………………………………………………….. 13

شکل 1-6 کاهش گراف محدودیت به درخت توسط تجزیه گراف [2] ……………………………………………………………. 14

شکل 1-7 یک شبکه حسگر واقعی برای مانیتور کردن محیط داخلی یک ساختمان[4] ………………………………. 15

شکل 2-1 یک طبقه بندی از الگوریتمهای مطرح در حل مسائل DCSP ………………………………………………………. 20

شکل 2-2 چهار حالت مختلف از مسئله کلاسیک رنگ آمیزی گراف و نتیجه پیاده سازی الگوریتم تصفیه برای هر یک از این مسائل[4] ……………………………………………………………………………………………………………………………………. 24

شکل 2-3 سیکل 1 الگوریتم ABT بر روی مسئله 4 وزیر[4] ………………………………………………………………………… 29

شکل 2-4 سیکل 2 از الگوریتم ABT بر روی مسئله 4وزیر[4] ……………………………………………………………………… 29

شکل 2-5 سیکل 3 از الگوریتم ABT بر روی مسئله 4 وزیر[4] …………………………………………………………………….. 30

شکل 2-6 سیکل 4 و 5  از الگوریتم ABT بر روی مسئله 4وزیر[4] ……………………………………………………………… 30

شکل 2-7 سیکل 6 از الگوریتم ABT بر روی مسئله 4وزیر[4] ……………………………………………………………………… 31

شکل 2-8  سیکل 7  و 8  از الگوریتم ABT بر روی مسئله 4وزیر[4] ………………………………………………………….. 31

شکل 2-9 سیکل 9 از الگوریتم ABT بر روی مسئله 4وزیر[4] ……………………………………………………………………… 31

شکل 2-10 سیکل 10  از الگوریتم ABT بر روی مسئله 4وزیر [4] ……………………………………………………………… 32

شکل 2-11 الگوریتم APO  [22] ……………………………………………………………………………………………………………………. 35

شکل 2-12 مثالی از گراف ساختار [44] …………………………………………………………………………………………………………. 39

شکل 2-13 ساختن یک گراف برای یک مسأله با سه متغیر …………………………………………………………………………… 40

شکل 3-1 جهت حرکات ممکن یک مهره وزیر در یک صفحه شطرنج ……………………………………………………………. 46

شکل 3-2 یک جواب برای مسأله 8-وزیر …………………………………………………………………………………………………………. 47

شکل 3-3 مثالی از رنگ آمیزی گراف(یک رنگ آمیزی از گراف معروف پترسن) …………………………………………… 48

شکل 3-4 مثالی از مساله CSP [4] …………………………………………………………………………………………………………………. 52

شکل 3-5 مدل فرض شده از محیط شبکه مانند عاملها[3] ……………………………………………………………………………. 53

شکل 3-6 میانگین زمان اجرای الگوریتم MAEA-CSPs در حل مسأله n-وزیر [3] ……………………………………. 58

شکل 3-7 مقایسه الگوریتم MAEA-CSPs با 4 الگوریتم دیگر با معیارهای SR، ME و AES [4] ……………. 59

شکل 3-8 مقایسه دو الگوریتم DBA و ABT با الگوریتم پیشنهادی مورچه ها بر روی مساله رنگ آمیزی گرافی با تراکم 2 ، بر اساس نسبت تغییر سایز مسأله به تعداد پیامها ………………………………………………………………………… 63

شکل 3-9 مقایسه دو الگوریتم DBA و ABT با الگوریتم پیشنهادی مورچه ها بر روی مساله رنگ آمیزی گرافی با تراکم 2 ، بر اساس نسبت تغییر سایز مسأله به معیار مقایسه NCCC ………………………………………………………… 63

شکل 3-10 مقایسه دو الگوریتم DBA و ABT با الگوریتم پیشنهادی مورچه ها بر روی مساله رنگ آمیزی گرافی با تراکم .32 ، بر اساس نسبت تغییر سایز مسأله به تعداد پیامها …………………………………………………………. 63

شکل 3-11 مقایسه دو الگوریتم DBA و ABT با الگوریتم پیشنهادی مورچه ها بر روی مساله رنگ آمیزی گرافی با تراکم 2.3 ، بر اساس نسبت تغییر سایز مسأله به معیار مقایسه NCCC ………………………………………….. 64

شکل 3-12 مقایسه دو الگوریتم DBA و ABT با الگوریتم پیشنهادی مورچه ها بر روی مساله رنگ آمیزی گرافی با تراکم .72 ، بر اساس نسبت تغییر سایز مسأله به تعداد پیامها …………………………………………………………. 64

شکل 3-13 مقایسه دو الگوریتم DBA و ABT با الگوریتم پیشنهادی مورچه ها بر روی مساله رنگ آمیزی گرافی با تراکم 2.7 ، بر اساس نسبت تغییر سایز مسأله به معیار مقایسه NCCC ………………………………………….. 65

شکل 4-1 یک طبقه بندی از الگوریتمهای مطرح در حل مسائل DCSP ………………………………………………………. 72

شکل 4-2 مرحله 1 تا 4 از الگوریتم DACA ………………………………………………………………………………………………….. 80

شکل 4-3 مرحله 5 از الگوریتم DACA ………………………………………………………………………………………………………….. 81

شکل 4-4 مرحله پایانی الگوریتم DACA ……………………………………………………………………………………………………….. 82

شکل 4-5 میانگین زمان اجرای الگوریتم DACA در اجرای مسأله n-وزیر با افزایش n از 4 تا 10⁴ در گامهای 50 تایی ………………………………………………………………………………………………………………………………………………………………. 82

فهرست جداول

عنوان                                                                                                                                        صفحه

جدول 3-1 نتایج بدست آمده از آزمایش MAEA-CSPs بر روی مسائل ارضاء محدودیت باینری …………… 59

جدول 3-2 مقادیر متفاوت از تعداد مورچه ها برای سایزها و تراکم­های متفاوت …………………………………………….60

جدول4-1 مقایسه الگوریتم پیشنهادی ما با دو روش دیگر از لحاظ تعداد سیکلهای مورد نیاز برای حل ……… 82

جدول4-2 مقایسه روش پیشنهادی ما با روش ERA از لحاظ میانگین زمان اجرا ……………………………………….. 82

مقدمه

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

برای دانلود متن کامل پایان نامه اینجا کلیک کنید

لینک بالا اشتباه است

برای دانلود متن کامل اینجا کلیک کنید

       

:: بازدید از این مطلب : 603