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

یکی از مهم ترین این پردازش ها که در فناوری اطلاعات و ارتباطات مورد نیاز است، دسته­بندی خودکار این اطلاعات می باشد. دسته بندی در مسائل متنوعی در فناوری اطلاعات به کار گرفته می شود، در مسائلی مانند امنیت اطلاعات، شناسایی نفوزگری در شبکه، دسته بندی کاربران بر اساس اطلاعات شخصی، پردازش تصویر و در واقع شناسایی هر گونه الگو بر اساس نمونه­ها و اطلاعات پیشین. این پردازش می تواند دسته[1]­ی نمونه­های جدید که به مجموعه اطلاعات اضافه می شود را پیش بینی نماید. از این رو در هوش مصنوعی توجه خاصی به توسعه انواع روش­های دسته­بندی هوشمند و خودکار شده است.

 روش­های دسته­بندی

دسته­بندی یکی از مهم­ترین شاخه‌های یادگیری ماشین[2] است. دسته­بندی به پیش ­بینی برچسب دسته[3] نمونه[4] بدون برچسب، بر اساس مجموعه نمونه­های آموزشی برچسب­دار (که قبلا به با کمک یک کارشناس دسته­بندی  شده ­اند) گفته می­ شود. درواقع دسته­بندی روشی است که هدف آن، گروه­بندی اشیا به تعدادی دسته یا گروه می­باشد. در روش‌های دسته­بندی، با بهره گرفتن از اطلاعات بدست آمده از مجموعه نمونه­های آموزشی، از فضای ویژگی­ها[5] به مجموعه برچسب دسته­ها نگاشتی بدست می آید که بر اساس آن، نمونه­های بدون برچسب به یکی از دسته­ها نسبت داده می­ شود.

تفاوت روش­ها دسته­بندی در چگونگی طراحی نگاشت است. در بعضی از آن­ها با بهره گرفتن از داده ­های آموزشی مدلی ایجاد می­ شود که بر اساس آن فضای ویژگی­ها به قسمت ­های مختلف تقسیم می­ شود که در آن، هر قسمت نشان دهنده یک دسته است. در این گونه روش­های دسته­بندی از مدل برای پیش ­بینی دسته­ی­ نمونه بدون برچسب استفاده شده و از نمونه­­های آموزشی به طور مستقیم استفاده نمی شود. یک نمونه از این دسته­بندها، دسته­بندهای احتمالی[8] می­باشد. این گونه الگوریتم­ها، از استنتاج آماری برای پیدا کردن بهترین دسته استفاده می­ کنند؛ برخلاف سایر دسته­بند­ها که فقط بهترین کلاس را مشخص می­ کنند الگوریتم­های احتمالی به ازای هر دسته موجود یک احتمال را به عنوان تعلق نمونه به آن مشخص می­ کنند و کلاس برنده، بر اساس بیشترین احتمال انتخاب می­ شود. روش­های احتمالی در یادگیری ماشین معمولا با نام الگوریتم­های آماری نیز شناخته می­شوند. در گروهی دیگر از روش­های دسته بندی، نمونه براساس خود مجموعه نمونه­ها و بدون ساختن مدل، به پیش ­بینی دسته­ی نمونه مورد نظر می ­پردازد. به این گونه الگوریتم های دسته­بندی، نمونه- بنیاد[9] گفته می­ شود.

تاکنون الگوریتم­های متفاوتی به عنوان دسته­بند ارائه شده ­اند. از جمله­ی­ آن­ها می­توان به الگوریتم نزدیک ترین همسایه­ها[10] [1] ، دسته­بند بیز[11][2]، ماشین بردار پشتیبان[3] و شبکه عصبی[12][4] اشاره کرد.

• ارزیابی دسته­بند

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

 هوش مصنوعی، روش­های متنوعی وجود دارد که در این قسمت بررسی شده ­اند.

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

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

نرخ دسته­بندی[14] یا صحت[15] پرکاربردترین و ساده­ترین معیار اندازه ­گیری کارایی هر دسته­بند است. این معیار برابر است با نسبت تعداد نمونه­های درست دسته­بندی شده به تعداد کل نمونه­ها. براساس این تعریف، نرخ خطای دسته­بندی از رابطه زیر بدست می­آید:

 مقادیر دقت[16] و بازخوانی[17] نیز معیارهای مناسبی برای ارزیابی دسته­بندها می­باشند. که اخیرا برای ارزیابی رقابت[18] بین اشتباه-مثبت[19] و درست-مثبت[20] استفاده می­ شود. در ادامه این معیار­ها معرفی می­ شود.

• معیاردقت : احتمال مثبت بودن نمونه­هایی که مثبت اعلام شده ­اند.

                  معیار بازخوانی : احتمال مثبت اعلام کردن نمونه­های دسته مثبت.

   معیار اختصاص[21]: احتمال منفی اعلام کردن  نمونه­های دسته منفی.

که در این معیارها، دسته مثبت، دسته مورد بررسی است و دسته منفی به سایر دسته­ها گفته می­ شود.

• تصدیق متقابل[22]

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

در ادامه روش­های مختلف تطبیق متقابل توضیح داده می­ شود.

• تصدیق زیر گروه تصادفی[24]: در این روش، نمونه­ها به صورت تصادفی به دو گروه آموزشی[25] و آزمایشی[26] تقسیم می­شوند. سپس دسته­بند به وسیله­­ نمونه­های آموزشی، آموزش داده می­ شود و با بهره گرفتن از مجموعه دیگر آزمایش شده و کارایی محاسبه می­ شود. این عملیات چندین بار انجام می­گیرد و در نهایت میانگین آن­ها به عنوان کارایی دسته­بند ارائه می­ شود. با توجه به تصادفی انتخاب شدن مجموعه­های آموزشی و آزمایشی، مهم­ترین مشکل این روش امکان عدم انتخاب بعضی از نمونه­ها به عنوان عضو یکی از دو گروه و یا انتخاب بیش از یک بار بعضی از نمونه­ها می­باشد.

• تصدیق متقابل k قسمت[27]: در روش ابتدا مجموعه نمونه­ها به K دسته تقسیم می­شوند. در هر مرحله نمونه­های k-1 دسته به عنوان مجموعه آموزشی در نظر گرفته می­ شود و با بهره گرفتن از یک دسته دیگر کارایی سیستم دسته­بند ارزیابی می­ شود. در نهایت کارایی سیستم برابر با میانگین کارایی در همه مراحل می­ شود. در این روش از همه نمونه­ها برای آموزش و آزمایش استفاده می­ شود.

• تصدیق یکی در مقابل بقیه[28]: یک روش دیگر، تصدیق یکی در مقابل بقیه است. در این روش، هر نمونه یک بار به عنوان نمونه آزمایشی انتخاب می­ شود و از سایر نمونه­­ها برای آموزش استفاده می­شوند. این روش بر روی تمامی نمونه­ها انجام می­ شود. در پایان، کارایی الگوریتم برابر نسبت تعداد نمونه­های درست دسته­بندی شده به کل است.

  • الگوریتم نزدیک­ترین همسایه

یکی از الگوریتم­های معروف دسته­بندی، الگوریتم نزدیک همسایه است؛ با این که از معرفی آن چندین دهه می­گذرد، این روش همچنان محبوب بوده و کاربرد بسیاری در مسائل مختلف دارد. دلیل این موضوع سادگی پیاده­سازی و کارایی بالا این روش است. به علاوه، این الگوریتم را به سادگی می­توان در مسائل مختلف به کار برد. الگوریتم نزدیک­ترین همسایه از یک قانون بسیار ساده در عمل دسته­بندی استفاده می­ کند. نمونه­هایی که شباهت بیشتری با یکدیگر دارند(در فضای ویژگی­ها در نزدیکی یکدیگر قرار گرفته­اند)، به احتمال بالا در یک دسته قرار دارند. بر طبق این، در الگوریتم نزدیک­ترین­ همسایه، برای بدست آوردن دسته­ی­ نمونه­ی­ پرس­و­جو شده[29]، بر اساس یک معیار شباهت(تفاوت)[30]، نزدیک­ترین­ نمونه، از مجموعه­ی­ نمونه­های آموزشی تعیین می­ شود. سپس الگوریتم دسته­ی­ این نمونه را به عنوان دسته­ی­ نمونه­ پرس­و­جو شده اعلام می­ کند.

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

 در این فصل ابتدا به توضیح مصرف برق در رایانه پرداخته می‌شود. سپس مصرف انرژی در مراکز داده و در نهایت مجازی سازی شرح داده می‌شوند.

1-1-      مصرف انرژی در رایانه

مصرف برق در رایانه را می‌توان به دو بخش تقسیم نمود:

ایستا: بخشی از انرژی مصرفی رایانه است که تنها صرف روشن بودن سیستم می‌گردد و به میزان کاری که سیستم انجام می‌دهد ارتباطی ندارد. این سطح از مصرف انرژی سبب روشن و آماده به کار نگاه داشتن سیستم شده و از لحظه‌ای که سیستم روشن می‌شود مصرف می‌گردد. بخش زیادی از این انرژی در واقع اتلاف به طرق مختلف و در سطوح مختلف سخت افزار است؛ مانند نشت جریان در مدارات مجتمع[1].

پویا: بخشی از انرژی مصرفی رایانه است که صرف انجام فعالیت‌های سیستم می‌گردد و با توجه به میزان بار[2] روی بخشهای مختلف یک سیستم (مانند: پردازنده، حافظه[3]، دیسک سخت[4]، کارت گرافیکی[5] و …) متغیر است.

شاید تصور شود که مصرف حالت بیکار یک رایانه کم یا قابل چشم پوشی است زیرا این سهمی از انرژی است که در زمانی که رایانه کار مفیدی انجام نمی‌دهد مصرف می‌کند، ولی بر خلاف تصور، یک سرور هنگام بیکاری حدود60 تا 70 درصد از بیشینه‌ی توان[6] مصرفی خود را مصرف می‌کند   [Barroso, 2007] و [Fan, 2007] و [Lefurgy, 2007]. بیشینه توان مصرفی یک رایانه هنگامی است که با حداکثر توان پردازشی[7] خود کار می‌کند.

1-2-      مراکز داده و مصرف انرژی در آنها

یک مرکز داده ساختمانی است، شامل تعداد زیادی رایانه (سرور) و قطعات مورد نیاز آنها مانند سوئیچ‌های شبکه و منابع انرژی پشتیبان [Kumar, 2009].

مصرف انرژی یک مرکز داده حاصل مجموع مصرف انرژی سرورهای موجود در آن به علاوه‌ی مصرف انرژی امکانات دیگر مانند سرورهای ذخیره سازی[8] ، سیستم‌های خنک کننده، تجهیزات شبکه و … است.

نکته‌ی قابل توجه در این مورد، سهم تقریباً 50 درصدی سرورها در مصرف انرژی مرکز داده است. به بیان دیگر تنها نیمی از انرژی مصرفی یک مرکز داده صرف پردازش و پاسخ به درخواست‌ها می‌گردد و مابقی صرف موارد دیگر که مهمترین آن سیستم‌های خنک کننده هستند می‌گردد. شکل 1-1 که نمایش تفکیک انرژی مصرفی یک مرکز داده است، به خوبی گویای این مسئله است:

شکل 1-1 نمودار تفکیکی انرژی مصرفی مرکز داده [Iyengar, 2010]

در مورد میزان مصرف انرژی در مراکز داده آمارها نشان می‌دهند علاوه بر چشمگیر بودن این مقدار، روند رو به رشدی از لحاظ مقدار و سهم از مصرف کل انرژی جامعه دارد [Koomey, 2011]. شکل‌ 1-2 نمایانگر این موضوع است.

شکل 1-2 نمودار میزان(محور عمودی) و سهم (درصدهای بالای ستون‌ها) مصرف انرژی مراکز داده در سطح جهان (سمت راست) و ایالات متحده (سمت چپ) در سالهای 2000، 2005 و 2010 میلادی [Koomey, 2011].

 بر اساس تحقیقات انجام شده [Barroso, 2007]  ، [Boher, 2002] ، [Rangan, 2008] و [Siegele, 2008]، متوسط بکارگیری[9] سرورها در یک مرکز داده کمتر از 30 درصد است و یک سرور تنها در 10 درصد اوقات بکارگیری نزدیک به بیشینه‌ دارد [Armbrust, 2010].

از اینرو با توجه به سهم مصرف انرژی یک سرور در حالت بیکاری، مشاهده می‌گردد که سهم قابل توجهی از انرژی مصرفی مراکز داده به هدر می‌رود.

1-3-      مجازی سازی

مجازی سازی ابتدا در سالهای 1970 میلادی برای استفاده‌ی همزمان چندین کاربر از یک سیستم ارائه شد [Bugnion, 1997]. طی سالهای گذشته کارهای زیادی در زمینه‌ی فن‌آوری مجازی سازی انجام شده است و به مرور توانایی‌هایی بر آن افزوده شده که شاید در ابتدای ارائه‌ ایده، جزء اهداف اصلی نبوده‌اند[Bugnion, 1997] و [Barham, 2003] و  [Clark, 2005] و [Walters, 1999].

امروزه مجازی سازی به انضمام ابزارهایی که به آن افزوده شده است ویژگی‌هایی مانند افزایش امنیت کاربران به خصوص درفضاهای غیر همکار، افزایش بهره‌وری سرورها، ایجاد بستر مناسب برای اجزای نرم افزارهای مختلف تحت سیستم عامل‌های متفاوت و به صورت همزمان، ساده‌ سازی سرویس و نگه‌داری سیستم‌ها در مراکز داده، ایجاد امکان توازن بار[10] بین سرورهای مختلف و … را عرضه می‌کند که سبب شده است بیشتر صنعت به خصوص مراکز داده به سمت استفاده از این فن‌آوری سوق پیدا کنند آنگونه که امروزه تقریباً تمامی مراکز داده در جهان از این فن‌آوری بهره می‌گیرند [Armbrust, 2010]. چنین محیط‌هایی متشکل از مجموعه‌ای از رایانه‌ها که برای ارائه سرویس‌های خود از فن‌آوری مجازی سازی استفاده می‌کنند را “ابرواره”[11] می‌نامیم. در واقع ابرواره همان مراکز داده هستند که سرویس‌های خود را روی شبکه و در در قالب بسته‌هایی از سخت افزار که به واسطه‌ی مجازی سازی شکل گرفته‌اند ارائه می‌دهند [Armbrust, 2010] و [Armbrust,2009]. این بسته‌های سخت افزار را به انضمام سیستم عامل درون خود “ماشین مجازی”[12] می‌نامیم.

مهاجرت ماشین مجازی[13] جزء قابلیت‌هایی است که مدتی پس از ظهور مجازی سازی به آن اضافه شد و به طور خلاصه عبارت است از

 انتقال ماشین مجازی از روی یک سرور به سرور دیگر. مهاجرت ماشین مجازی می تواند به صورت زنده[14] باشد به شکلی که کاربر نهایی[15] که از ماشین مجازی مهاجرت کننده سرویس می گیرد متوجه هیچگونه اختلالی در دریافت سرویس نشود و به عبارتی اصلاً جابجایی ماشین مجازی سرویس دهنده خود را متوجه نشود [Clark, 2005]. در شکل 1-3 طرحی از مهاجرت ماشین مجازی بین دو سرور فعال نمایش داده شده است.

شکل 1-3 نمایی از مهاجرت ماشین مجازی [Clark, 2005]

 اگر بخواهیم مهاجرت ماشین مجازی به صورت زنده را دقیق‌‌تر بررسی نماییم، در واقع وقفه‌ای در ارائه سرویس پیش می‌آید که این تاخیر بین 60 تا 300 میلی ثانیه خواهد بود [Clark, 2005]. به هر حال از دید کاربر و پاسخ به درخواست‌ها مهم این است که می توان بدون بروز مشکل یا پرداخت هزینه‌ی زمانی و مصرف انرژی بالا ماشین‌های مجازی را بین سرورهای مختلف جابجا نمود [Liu, 2011].

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

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

2-          پیشینه‌تحقیق

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

2-1-      صرفه جویی در انرژی مصرفی رایانه

روش‌های صرفه جویی در انرژی مصرفی یک رایانه، با توجه به اینکه کدام بخش از انرژی مصرفی را هدف صرفه جویی قرار می‌دهند به دو بخش تقسیم می‌شوند.

2-1-1.  صرفه جویی در انرژی پویا

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

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

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

از جمله مهمترین روش های این دسته می‌توان از “مقیاس سازی پویای ولتاژ و فرکانس[17]” (DVFS) نام برد [Weiser, 1995] و [Semeraro, 2002] . در این روش با بهره گرفتن از پشتیبانی در نظر گرفته شده در پردازنده‌ی اصلی، فرکانس کار پردازنده با توجه به حجم بار پردازشی آن در هر لحظه تغییر می‌کند. این کار باعث می‌گردد تا در زمان هایی که نیازی به حداکثر توان پردازنده وجود ندارد، فرکانس کاری آن پایین بیاید و از آنجا که این کار با کاهش ولتاژ صورت می‌گیرد، عملاً توان مصرفی پردازنده با نسبت توان سوم فرکانس کم می‌شود. امروزه تمامی پردازنده‌های جدید از این قابلیت برخوردارند ولی از آنجا که مصرف پردازنده بخش کمی از مصرف کل یک سرور را تشکیل می‌دهد (و این سهم با پیشرفت فناوری رو به کاهش است) [Fan, 2007] علیرغم بهره گیری از این روش هنوز میزان اتلاف انرژی چشمگیری در سرورها وجود دارد.

در سطح نرم افزاری نیز در سیستم عامل‌های جدیدتر پیشبینی‌هایی برای بهره بردن از توانایی‌های سخت افزار و راه ‌های دیگر کاهش مصرف انرژی صورت گرفته است مانند کم کردن نور صفحه یا خاموش کردن نمایشگر[18] و یا قرار دادن کل سیستم در حالتی که سطح توان پردازشی و در نتیجه مصرف انرژی پایین‌تر باشد [Weiser, 1996] در مواقعی که نیازی به حداکثر توان پردازشی سیستم نیست.

2-1-2.   صرفه جویی در انرژی ایستا

روش‌هایی که حذف اتلاف ناشی از توان ایستا را هدف قرار داده‌اند، را می‌توان در دوسطح سخت افزاری و نرم افزاری طبقه بندی نمود.

یک سرور هنگامی که روشن است و صرف نظر از میزان کاری که انجام می‌دهد، توان ایستای خود را مصرف می‌کند. روش های نرم افزاری عموماً با قرار دادن سرور بیکار[19] در حالتی که مصرف انرژی کمی دارد (مانند خواب[20]) و یا خاموش نمودن آن سعی در حذف کل این بخش از مصرف انرژی دارند. البته بدیهی است که این روش فقط قابل استفاده در مورد سرورهای بیکار است و اگر سروری حتی به میزان بسیار کمی هم از منابعش استفاده نماید، این روش در مورد آن قابل انجام نیست (و یا باید با روشی مانند آنچه در این پایان نامه ارائه و پیاده سازی شده‌است، ابتدا سرور را به حالت بیکار برده و سپس اقدام به خاموش نمودن و یا به خواب بردن آن سرور شود).

روش‌های سخت افزاری با بهره گیری از فناوری جدیدتر و با انجام تغییرات و بهینه سازی در سطح معماری سخت افزار، منطق و یا الگوی مدارات سعی در کاهش نشتی‌های جریان و سایر اتلاف‌های انرژی موجود در مدارات دارند. در واقع با بهینه‌تر شدن و نیز با بکارگیری انواع روش‌های بسته‌بندی[21] مدارات سعی در کاهش حجم قطعات دخیل در انجام یک عمل خاص و همچنین اتلاف کمتر در سطح همین عده از قطعات الکترونیکی می‌شود که این عوامل باعث کاهش اتلاف توان ایستا در سرورها خواهند بود.

مزیت روش‌های سخت افزاری به نرم افزاری در این است که این روش‌ها در تمام حالات یک سرور کارایی خود را حفظ می‌کنند.

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

روش‌هایی که کاهش مصرف پویای انرژی را مد نظر قرار داده‌اند، به شرطی می‌توانند در سطح کل سیستم یا چند سیستم صرفه جویی قابل توجهی کنند که قطعه‌ی هدف آنها کسر بزرگی از کل انرژی مصرفی را به خود اختصاص دهد. در این میان پردازنده هم به خاطر میزان مصرف زیاد و هم به دلیل متغیر بودن زیاد سطح مصرف در عملکردهای گوناگون (آنگونه که در DVFS انجام می‌شود) بیشتر مورد توجه قرار گرفته است. اما نشان داده شده است که حتی پردازنده هم، الزاماً در هر سیستم و هر شرایط مصرف کننده‌ی غالب در سیستم نیست؛ سهم فعلی مصرف پردازنده از مصرف کل سیستم حدود 25 درصد است که این سهم رو به کاهش است [Laudon, 2006] ، [Fan, 2007] و [Lefurgy, 2003].

مشاهدات نشان می‌دهد که در سرورهای مختلف میزان و سهم مصرف قطعات با یکدیگر متفاوت است و هیچ یک از قطعات مصرف کننده‌ی غالب نیست [Meisner, 2009]. شکل 2-1 نشان دهنده‌ی همین وضعیت است؛ این نمودار، تفکیک[22] مصرف انرژی قطعات مختلف سخت افزار متعلق به سرور IBM p670 [Lefurgy, 2003] و Sun UltraSparc T2000 [Laudon, 2006] و یک سرور نوعی مشخص شده توسط شرکت Google [Fan, 2007] می‌باشد. همانطور که در این نمودار مشاهده می‌شود، سهم مصرف قطعات مختلف سخت افزار در سرورهای مختلف متفاوت است و در عین حال هیچکدام از قطعات مصرف کننده‌ی غالب انرژی نیستند.

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

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

در بین مباحث متفاوتی که در زمینه­ پردازش زبان­های طبیعی موجود است، برای اینجانب ابهام معنایی[8] جذابیت بیشتری داشته که در این پایان نامه به این موضوع پرداخته­ام. ابهام معنایی یکی از مباحث پیچیده و در عین حال پراهمیت است که در شاخه­هایی نظیر ترجمه­ی ماشینی و بازیابی اطلاعات نیز مطرح بوده و بعنوان جزء جدایی ناپذیری از اینگونه سیستم­ها دارای ارزش و حائز اهمیت است.

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

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

1-2- پردازش زبان­های طبیعی

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

زبان طبیعی، زبانی است که ما در تعاملات اجتماعی روزمره با بهره گرفتن از آن می­نویسیم و صحبت می­کنیم. زبان­های طبیعی متنوع و فراوانی وجود دارند که ممکن است فرم گفتاری و نوشتاری متفاوتی داشته باشند و از هم مستقل باشند. پردازش زبان‌ها و مکالمات طبیعی یکی از اموری‌ست که با ورود فناوری رایانه‌ای به زندگی بشر مورد توجه بسیاری از دانشمندان قرار گرفته است. حتی اندیشه‌ای که آلن تورینگ[9] از ماشین هوشمند خود و تعریفی که او از هوش مصنوعی[10] داشت، در مرحله­ اول مربوط به پردازش زبان‌های طبیعی می­‌شد. بعلاوه تلاش‌های بسیاری توسط بشر برای پیگیری این امر صورت گرفته بود که به عنوان مثال ماشین لیزا یکی از محصولات این تلاش‌هاست. ماشین لیزا ماشینی بود که با تایپ از راه دور با یک انسان، جملات او را پردازش می‌کرد و جوابی درخور به او می‌داد.

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

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

1. یک زبان از چه کلماتی تشکیل شده است؟

1. چگونه کلمات ترکیب می­شوند تا جملات زبان تشکیل شوند؟

1. معنی کلمات زبان چیست؟

1. معانی کلمات چگونه به کار گرفته می­شوند تا معنی جملات ساخته شود؟

در حقیقت هدف اصلی در NLP، ماشینی کردن فرایند درک و برداشت مفاهیم بیان گردیده با یک زبان طبیعی انسانی می­باشد. به تعریف دقیق‌تر پردازش زبان‌های طبیعی عبارت است از استفاده از کامپیوتر برای پردازش زبان گفتاری و نوشتاری به نحوی که کامپیوترها از زبان طبیعی به عنوان ورودی و خروجی استفاده نمایند. بدین وسیله می‌توان به ترجمه­ی زبان‌ها پرداخت، از صفحات وب و بانک‌های اطلاعاتیِ نوشتاری جهت پاسخ دادن به پرسش‌ها استفاده کرد، یا با دستگاه‌ها مثلاً برای مشورت گرفتن به گفتگو پرداخت.

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

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

• انگیزه

 طبقه ­بندی­کننده­ های فازی دارای ویژگی منحصربفرد تفسیرپذیری هستند و قادرند دانش چگونگی تشخیص الگو­ها را برای یک فرد خبره بصورت یک دستورالعمل بازنمایی کنند. طبقه ­بندی­کننده­ های­ فازی چهار هدف اساسی را دنبال می­ کنند. دقت طبقه ­بندی­کننده را بیشینه کنند، طبقه ­بندی­کننده­ با بیش­ترین قابلیت تفسیر­پذیری را ایجاد نمایند، پایداری طبقه ­بندی­کننده را بیشینه کنند و حساسیت به نویز را کاهش دهند. تاکنون روش­های متفاوتی برای ایجاد قوانین، نحوه تخصیص زیرفضاها، نحوه استنتاج در هر قانون و در نهایت ادغام قوانین ارائه ­شده است. بدیهی است زبان طبیعی[6] محور بودن ساختار قوانین فازی علیرغم استخراج دانش، مشکل اثبات ریاضی کارایی طبقه ­بندی­کننده از جمله ارائه یک کران­ بالا[7] برای خطای آموزش[8] و خطای تست[9] است. به­عبارتی افزایش عمومی­سازی[10] این طبقه ­بندی­کننده­ها بصورت ریاضی مانند طبقه ­بندی کننده تقویتی گروهی[11] کار بسیار دشواری است. از این­رو اغلب از روش­های مکاشفه­ای[12] و فوق مکاشفه­ای[13] به­صورت سعی و خطا در تدوین قوانین و ادغام آن­ها استفاده می­گردد، به این دلیل که زیرفضا را برای به­دست­آوردن بهترین ترکیب قوانین جستجو می­ کنند [2]-[4] . ایشیبوشی[14][5] روشی را برای تخصیص فضا به­صورت تقسیم ­بندی منظم و تکراری ارائه کرد که می­توان از این روش به­عنوان یکی از موثرترین روش­های طبقه ­بندی­کننده فازی که مبنای بسیاری از تحقیقات بعدی در این زمینه نیز شد، نام برد.

• شرح مسئله

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

به طور کلی، هدف مسئله، فراهم کردن یک چارچوب کلی برای تکامل قوانین فازی است. راهکار­های بسیاری در این زمینه ارائه شده، اما

 همه آن­ها حداقل در یکی از موارد زیر تفاوت دارند، تعداد قوانینی که در هر عضو جمعیت کد می­ شود، نوع بیان قوانین کد­شده در هر عضو و نوع و هدف پروسه تکاملی .[7-8] این الگوریتم‌ها شامل الگوریتم‌های ژنتیک[15]، بهینه‌سازی گروه ذرات[16]، گداختگی شبیه‌سازی شده[17] و… می‌باشند.

از آنجایی که الگوریتم­های تکاملی[18] به­صورت چند­عاملی[19] جستجو را در فضای ویژگی انجام می­دهند، نحوه گردش آن­ها تا حد ممکن به­صورت تصادفی می­باشد. این خواص، الگوریتم­های تکاملی را به ابزار قوی برای انواع مسائل بهینه­سازی تبدیل نموده است.[2], [4]  از جمله مسائل مطرح در زمینه بهینه­سازی، بهینه­سازی ساختار و پارامتر­های طبقه ­بندی­کننده­ها می­باشد. بدیهی است هرچه یک طبقه ­بندی­کننده­ پارامتر­های بیش­تری داشته باشد، تنظیم بهینه این پارامتر­ها به­صورت دستی کاری بسیار دشوار، و در بعضی حالات­ غیرممکن می­باشد. بدین خاطر از الگوریتم­های تکاملی برای یادگیری پارامتر­ها و تعیین ساختار طبقه ­بندی­کننده­ های متفاوت به­صورت فراوان استفاده شده است. از جمله این تحقیقات می­توان به بهبود ساختار شبکه عصبی توسط الگوریتم ژنتیک اشاره کرد [9] که الگوریتم ژنتیک سعی در هرس کردن ارتباط بین نورون­ها و به­نوعی لایه­بندی آن­ها به منظور بهبود کارایی طبقه ­بندی، دارد.

مزیت ترکیب قوانین فازی و الگوریتم­های تکاملی این است که مجموعه قوانین ایجاد­شده دارای تفسیر­پذیری بیش­تری هستند و می­توانند با عدم قطعیت[20] و ابهام مقابله کنند و همچنین می­توانند به صورت اکتشافی فضای ویژگی را جستجو کنند. به عنوان مثال در بخش ورودی نحوه تخصیص­بندی فضاها و همچنین تعیین پارامتر­های توابع عضویت (مانند شیب و واریانس)، از الگوریتم­های تکاملی استفاده شده است[10].

چالش­ها

با توجه به این که اغلب روش های عمده و شناخته شده محاسبات تکاملی، شبیه‌سازی کامپیوتری فرایندهای طبیعی و زیستی هستند، در این نوشتار، از یک روش ترکیبی برای بهبود طبقه ­بندی­کننده­ های فازی ارائه می­ شود که برای بهبود یادگیری پارامتر­های آن الگوریتم تکاملی رقابت استعماری [11] اقتباس شده است. این پایان نامه ، الگوریتم رقابت امپریالیستی [21]را برای هدف استخراج کلاسه­بند­های عام و قابل فهم از داده در شکل یک سیستم قانون ارائه می­ کند. در این تحقیق سعی در ارائه ساختار جدیدی بر روی بستر فازی هستیم که در آن ساختار، توزیع قوانین از الگوریتم رقابت استعماری[22] اقتباس شده و لیکن روح قوانین به­صورت فازی است. ضمنأ به­ دلیل ایجاد هارمونی مناسب در بهینه­سازی ساختار قوانین و همچنین ادغام قوانین، استفاده از الگوریتم بهینه­سازی رقابت استعماری پیشنهاد می­ شود.

در این الگوریتم چند نمونه که دارای میزان برازندگی[23] بالایی می­باشند (امپریالیست[24]) و مرکز امپراطوری­ها هستند، سعی در کشاندن بقیه نمونه­ها (مستعمره)[25] به سمت خود دارند. این الگوریتم را می­توان نوع بهبود یافته الگوریتم ازدحام ذرات در نظر گرفت. لازم به ذکر است که الگوریتم ازدحام ذرات علیرغم سرعت همگرایی بالای آن، احتمال بایاس شدن آن بسیار زیاد می­باشد. چون میزان تصادفی بودن[26] آن در حین جستجو پایین بوده و بسیار بایاس­دار حرکت می­ کند. درصورتیکه الگوریتم رقابت استعماری این مسئله را به این شیوه حل کرده است که هر نمونه به­جای حرکت در جهت برآیند دو نقطه با برازندگی­های مناسب، به یکی از چند نقطه­ای اختصاص داده می­ شود که بهینه محلی (امپریالیست) اطلاق می­شوند.

 از آن­جا که ساختار این الگوریتم به­صورت چند­حوزه­ای می­باشد، بکارگیری آن برای ساختار­بندی قوانین فازی این خاصیت را به­همراه خواهد داشت که یک مجموعه قوانین بر روی یک زیرفضا کار کند نه تنها روی یک قانون. به­عبارت دیگر استفاده از یک قانون برای تصمیم ­گیری درمورد یک زیرفضا حتی با داشتن هم­پوشانی[27] با زیرفضاهای همسایه باعث خاص[28] شدن آن قانون و به­نوعی بایاس قانون و آن زیرفضای خاص شده و در مورد سایر نمونه­هایی که دور از آن زیرفضا هستند، نمی ­تواند تصمیم ­گیری مناسبی را به­عمل آورد که همین امر باعث بیش­سازگاری[29]و کمبود عمومی­سازی توابع فازی می­گردد. در مقابل، الگوریتم یادگیری استعماری از تخصیص یک قانون به یک زیرفضای خاص جلوگیری کرده و حتی زیرفضاهایی که یک مستعمره از قوانین درباره آن تصمیم می­گیرند، دارای ابعاد بسیار وسیع­تری نسبت به زیرفضای تخصیص­شده به هر قانون در مقایسه با روش­های قبلی دارد. ضمنأ هنگامی­که قوانین به­صورت دسته­های مختلفی از مستعمره­های متفاوت بر روی کل فضا عمل می­ کنند، می­توان آن را جزو الگوریتم­های توزیع­شده در نظر گرفت. توانایی بهینه­سازی این الگوریتم نسبت به الگوریتم­های بهینه­سازی پیشین هم­تراز و یا حتی بالاتر است و سرعت رسیدن به جواب بهینه نیز مناسب است.

اهداف پایان نامه

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

• چندین طرح کلی کدگذاری برای نمایش قوانین به شکل رشته­ای از بیت­ها ارائه می­دهد.

• یک تابع برازش برای ارزیابی کارایی اعضا یا همان قوانین فازی تعریف می­ کند.

• تصحیحی در عملگر­های الگوریتم رقابت استعماری برای استفاده بهینه در سیستم­های فازی ارائه می­دهد.

• زیرفضای تخصیص­داده­شده برای هر قانون را توسعه می­دهد و درنتیجه افزایش نسبی عمومی­سازی را منجر می­ شود.

مطالب مربوط به این رساله در پنج فصل به شرح زیر می‌باشد.

فصل دوم. در این فصل تحقیقات انجام شده را بحث می­ کند و برای هر روش مزایا و معایب آن­ها را به­صورت جداگانه برمی­شمرد.‌

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

فصل چهارم. در فصل چهارم نتایج به­دست آمده ارائه می­ شود.

فصل پنجم. کار­های پیش رو و اهداف آینده بررسی می­ شود.