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

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

تعداد صفحات : 88

چکیده

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

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

در این پایان نامه، دو روش پیشنهادی، یکی برای افزایش کارایی تشخیص تشکل های همپوشان در شبکه های ایستا و دیگری برای شبکه های پویا به همراه نتایج آزمایش های متعدد انجام شده برای ارزیابی کارایی آنها ارائه شده است.

چکیده :

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

چکیده

 الگوریتم زمان بندی کار، که یک مسئله NP-کامل است، نقش کلیدی در سیستم ابرهای محاسباتی ایفا می کند. الگوریتم رقابت استعماری یکی از جدیدترین الگوریتم های بهینه سازی تکاملی است. همانگونه که از نام آن بر می آید، این الگوریتم بر مبنای مدل سازی فرایند اجتماعی- سیاسی پدیده استعمار بنا نهاده شده است.

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

پیاده سازی های الگوریتم پیشنهادی برای دو آزمایش 200 خادمی و 400 خادمی انجام گرفته است و کارها از تعداد 16 تا 4096 به سیستم وارد گردیده است، نتایج بدست آمده با نتایج زمان بندی کارهای بلادرنگ بر اساس الگوریتم ژنتیک مقایسه گردیده است و بهینه بودن الگوریتم پیشنهاد شده را بر اساس زمان انجام کار، تعداد کارهای انجام نشده در مهلت تعیین شده و تعداد خادم های مورد استفاده نتیجه می گیریم.

در این تحقیق با استفاده از الگوریتم رقابت استعماری در زمان بندی کارهای بلادرنگ در محیط ابرهای محاسباتی، استفاده از منابع بهینه شده است، نسبت بين زمان اجراي مورد انتظار و زمان اجرايي کمتر شده است و مقدار بهينه برازندگي نیز بهتر شده است.

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

ابرهای محاسباتی، کارهای بلادرنگ، الگوریتم ژنتیک، الگوریتم رقابت استعماری

چکيده

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

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

فرمت فایل دانلودی:.doc قابل ویرایش

تعداد صفحات: 84

چکیده:

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

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

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

پردازش ابر، محیط ابر ، زمانبندی، کلونی مورچه، جهش قورباغه

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

چکيده

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

چکیده

هدف این پژوهش بررسی رویکردهای به‌کار گرفته توسط اعضای هیأت علمی دانشکده فنی‌و‌مهندسی دانشگاه آزاد اسلامی واحد مشهد در هر یک از مراحل اطلاع‌یابی اينترنتي مطابق با مدل الیس است. روش پژوهش، پیمایشی و از نوع کاربردی و ابزار پژوهش، پرسشنامه‌ای محقق‌ساخته بر اساس شش ویژگی مدل رفتار اطلاع‌یابی الیس است. ویژگی‌های شروع، پیوندیابی، مرور، تمایزیابی، نظارت و استخراج که برای هر یک، گویه‌هایی طراحی و به پرسش گذاشته شد. از بین جامعه آماری 116 نفری اعضای هیأت علمی، تعداد 67 نفر(شامل 4 زن و 63 مرد) به پرسشنامه‌های ارسالی پاسخ دادند.

سوال اصلی این پژوهش، پرسش از تطابق رفتار اطلاع‌یابی اینترنتی جامعه پژوهش با الگوی رفتار اطلاع‌یابی الیس است. نتایج بدست آمده نشان داد که این تطابق برقرار بوده و يافته‌ها قويّاً آنرا تأييد و رویکردهای بکار گرفته شده توسط جامعه پژوهش منطبق بر ویژگی‌های رفتار اطلاع‌یابی الیس مي‌باشد. نتايج حاكي از تطابق بيش از 60 درصدي در سطح معني‌داري 5% و حتي 1% است. این یعنی جامعه پژوهش از مدل و الگویی نادانسته اما پذیرفته‌شده در رفتار اطلاع‌یابی اینترنتی تبعیت می‌کند و مبیّن رفتارها و رویکردهای هدفمند برای موفقیت در جستجوی اینترنتی و حصول به منابع و مدارک است. اطلاع از زمینه کلی نیازهای اطلاعاتی در ابتدای جستجو با نرخ 98 درصد موافق در مقابل 1 درصد مخالف، بررسی و مطالعه مرتب مجلات و کتاب‌های الکترونیکی با نرخ 49 درصد موافق در مقابل 19 درصد مخالف، آشنائی با معیارهای ارزیابی منابع و ملاک‌های اعتبار با نرخ 61 درصد در مقابل 16 درصد مخالف، استفاده از موتورهای جستجوی عمومی با نرخ 96 درصد در مقابل 2 درصد مخالف، استفاده از موتورهای جستجوی تخصصی با نرخ 66 درصد در مقابل 13 درصد مخالف، موفقیت در نائل شدن به هدف در جستجوی اینترنتی با نرخ 83 درصد در مقابل 4 درصد مخالف، داشتن بایگانی منظم از اطلاعات در صندوق پست الکترونیکی با نرخ 50 درصد در مقابل 37 درصد مخالف، گرایش به تهیه چاپ از اسناد و مدارک یافته شده در جستجوی اینترنتی با نرخ 49 درصد در مقابل 29 درصد مخالف از برخی آگاهی‌های فرعی پژوهش حاضر می‌باشد.

کلمات کلیدی:

رفتار اطلاع‌یابی، رفتار اطلاع‌یابی اینترنتی، اطلاع‌یابی، اعضای هیأت علمی، مدل رفتار اطلاع‌یابی الیس

چکیده

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

واژه‌های كلیدی:مسائل بهینه­ سازی پویا، الگوریتم­ های تکاملی و الگوریتم بهینه­ سازی فاخته