بخشی از مقاله
چکیده
در این مقاله مسئله گروهبندی تیمهای آموزشی - دانشجویان، دانش آموزان و ... - با استفاده از الگوریتم بهینهسازی ازدحام ذرات - PSO - برر سی و پیاده سازی شده ا ست. نحوه گروهبندی تیمهای آموز شی تاثیر زیادی در میزان کارایی گروهها و به تبع آن هر یک از اع ضا میگذارد. طی سالیان گذ شته از روشهای مختلف بهینه سازی برای ارائه راهحلی منا سب جهت گروهبندی ا ستفاده گردیده ا ست. یکی از روشهایی که مطالعه زیادی روی آن صورت گرفته شده، ا ستفاده از الگوریتم ژنتیک میبا شد. از اینرو، نتایج حا صل از ا ستفاده الگوریتم پی شنهادی مبتنی بر PSO با الگوریتم ژنتیک مقای سه گردیده است. نتایج آزمایشها عملکرد مناسب روش پیشنهادی را تایید کرده و برتری آنرا نسبت به روش ژنتیک نشان میدهد.
کلمات کلیدی: گروهبندی تیم آموزشی، الگوریتم بهینهسازی ازدحام ذرات - - PSO، الگوریتم ژنتیک
-1مقدمه
-1-1 بیان مسئله
یادگیری گروهی یکی از روشهای یادگیری میباشد که در ادبیات آکادمیک برای بهبود عملکرد افراد تحت آموزش بیان میشود.[12] گروهبندی افراد جهت یادگیری علاوه براینکه مهارتهای اجتماعی تک تک اعضای گروه را افزایش میدهد، کارایی جمعی و میزان ماندگاری مطالب را در ذهن افراد بالا میبرد.[4] از طرفی محققان ادعا کردهاند که بسیاری از نتایج غیرموفقیتآمیز کار گروهی، از فرآیند تشکیل گروهها ناشی میشود.[12] در این مقاله مسئله گروهبندی تیمهای آموزشی - دانشجویان، دانش آموزان و ... - مورد بررسی قرار گرفته و برای سادگی نگارش آن، موضوع گروهبندی دانشجویان مورد هدف قرار گرفته است.
سه روش کلی برای تقسیم دانشجویان یک کلاس به گروههای مختلف وجود دارد که عبارتنداز: گروهبندی توسط استاد، توسط دانشجو، و بصورت تصادفی. آزمایشها نشان داده است که روش گروهب ندی توسط خود دانشجو ها کمترین کارایی را حاصل میشود.[4,7] همچنین گروهبندی توسط استاد نیز زمانی مناسب است که اولاً تعداد دانشجویان کم باشد و ثانیاً استاد به تواناییها و مهارتهای همهی آنها آشنا باشد. از طرفی گروهبندی تصادفی با اینکه در زمانی کوتاه قابل انجام است، کارایی مناسبی را دربرندارد.[4]
در نتیجه به روشی نیاز پیدا میشود که علاوه بر حصول کارایی مناسب، در عمل قابل استفاده بوده و به صرف زمان کمی احتیاج داشته باشد. از آنجایی که بررسی تمامی ترکیبهای ممکن از دانشجویان برای گروهبندی، پیچیدگی زمانی زیادی - - NP-hard دارد[7]، از روش های مختلف بهینهسازی - از جمله الگوریتم ژنتیک، کلونی مورچه، PSO و... - برای حل این م سئله ا ستفاده شده ا ست. هر یک از روشهای قبلی از دیدگاهی متفاوت به برر سی م سئله گروهبندی دان شجویان نگریده و به ارائه راهحل میپردازند.[3,4,7,14,15]
[12] با تکیه بر چند ویژگی فردی، میزان خوبی گروه و انحراف معیار بین گروهها، م سئله گروهبندی تیمهای آموز شی را مدل سازی کرده و سعی به حل آن با الگوریتم کلونی مورچهها نموده ا ست. نتایج حا صل نشان داد که در برخی از موارد این الگوریتم بهتر از الگوریتم ژنتیک عمل میکند. بدلیل شباهت مسئله گروهبندی تیمهای آموزشی به مسائل خوشهبندی [7]، برخی از محققان مثل [10] و [5] سعی کردند از الگوریتمهای خوشهبندی نظیر K-means برای گروهبندی دانشجویان براساس شباهتها و تفاوتهایشان استغاده نمایند.
در [6] کارایی الگوریتم PSO با K-means برای حل یک مسئ له خوشهبندی مقایسه شده و نشان داده شد که الگوریتم PSO همگرایی بهتری دارد. [11] اثبات کرد که الگوریتم PSO عملکرد بهتری از لحاظ زمان اجرا، کارایی و دقت عمل در خوشهبندی، نسبت به الگوریتم ژنتیک داراست. [7] به بررسی عملکرد الگوریتمهای PSO، کلونی مورچه و کلونی زنبور ع سل در حل م سئله گروهبندی تیم آموز شی پرداخته و نتایج حا صل شده را با الگوریتمهای خو شهبندی مقای سه نموده ا ست.
آزمایشهای انجام شده کارایی و عملکرد بهتر الگوریتم PSO را نشان داد. تفاوت ا صلی الگوریتم PSO معرفی شده در این مقاله با روش پی شنهادی ما در تعریف و مدلسازی مسئله و راهحل آن و همچنین نحوه ارزیابی گروههای ایجاد شده است. الگوریتم معرفی شده در آن مقاله کل جمعیت1 را بهعنوان یک راه حل در نظر میگیرد. همچنین مسئله گروهبندی به عنوان یک الگوریتم خو شهبندی عنوان شده که هدف آن رسیدن به حداکثر ناهمگونی در گروههای تشکیل شده است. این فرض از آنجا ناشی میشود که گروههایی کارایی بهتری دارند که اعضای آن بیشترین ناهمگونی را با یکدیگر دارند.[3]
[14] مسئله گروهبندی را به یک مسئله ترکیبی بهینهسازی تبدیل کرده و از رو شی مرکب از الگوریتمهای ژنتیک و PSO2 - با فرض تعداد دلخواه از ویژگیهای دانشجویان - ، برای حل آن استفاده کرده است. [13] انواع گونههای مختلف معرفی شده برای الگوریتم PSO را برای حل مسئله گروهبندی تیمهای آموزشی با یک روش بهینه سازی خطی عدد صحیح بهنام CPLEX مقایسه نموده است. در مقاله حاضر، راهحل ارائه شده در [4] برای گروهبندی دانشجویان با استفاده از الگوریتم ژنتیک ارزیابی شده و از فرضیات آن برای حل مسئله با استفاده از الگوریتم بهینهسازی ازدحام ذرات - PSO - بهره گرفته شده است.
البته در پیاده سازی و آزمایشات صورت گرفته حالت تطابقی3 مقاله مذکور نادیده گرفته شده و الگوریتم ژنتیک بصورت اولیه و سنتی پیادهسازی گردیده است. دلیل این امر سربار پردازشی حاصل از اضافه شدن خاصیت تطابقی به الگوریتم ژنتیک است. از طرفی مزیت این روش، بالابردن فضای جستوجو و پیشگیری از گیر کردن در مقدار بی شینه محلی میبا شد که این مهم از طریق جایگزینی افراد حا صل از عملگرهای ترکیب و جهش، با افراد قبلی، در الگوریتم ژنتیک حاصل میشود.
در برخی مطالعههای صورت گرفته در مورد گروهبندی دانشجویان بوسیله الگوریتم PSO، کاربردهای آن در گروهبندی دانشجویان در روش CSCL4 - یکی از متدهای یادگیری الکترونیکی - بررسی شده و مفرو ضاتی برای آن شرایط و محیط در نظر گرفته می شود.[8] اما در روش پی شنهادی [4] هیچ پیشفر ضی وجود ندارد و ازاینرو در عمل و عموم قابل پیادهسازی میباشد. ما در این مقاله با استفاده از اساس استفاده شده در [4]، تغییرات کمی جهت بیان مسئله بصورت متغیرهای الگوریتم PSO اعمال کردهایم. سپس نتایج حاصل از روش خود را با نتایج اعمال الگوریتم آن مقاله - ژنتیک - مقایسه نمودهایم.
-1-2 الگوریتم بهینهسازی ازدحام ذرات - PSO -
"الگوریتم 5PSO یک الگوریتم جستجوی اجتماعی است که از روی رفتار اجتماعی دستههای پرندگان مدل شده است. در ابتدا این الگوریتم به منظور کشف الگوهای حاکم بر پرواز همزمان پرندگان و تغییر ناگهانی مسیر آنها و تغییر شکل بهینهی دسته به کار گرفته شد. درPSO، ذرات6 در ف ضای ج ستجو جاری می شوند. تغییر مکان ذرات در فضای جستجو تحت تأثیر تجربه و دانش خودشان و همسایگانشان ا ست. بنابراین موقعیت دیگر توده7 ذرات روی چگونگی ج ستجوی یک ذره اثر می گذارد . نتیجهی مدلسازی این رفتار اجتماعی فرایند جستجویی است که ذرات به سمت نواحی موفق میل میکنند.
ذرات از یکدیگر میآموزند و بر مبنای دانش بدست آمده به سمت بهترین همسایگان خود میروند اساس کار PSO بر این ا صل استوار است که در هر لحظه هر ذره مکان خود را در فضای جستجو با توجه به بهترین مکانی که تاکنون در آن قرار گرفته است و بهترین مکانی که در کل همسایگیاش وجود دارد، تنظیم میکند" .[2] PSO در سال [9]1995، برای اولین بار به عنوان یک روش جستجوی غیر قطعی برای بهینه سازی تابعی مطرح گشت. گروهی از پرندگان در ف ضایی به صورت ت صادفی دنبال غذا می گردند. تنها یک تکه غذا در ف ضای مورد بحث وجود دارد. هیچ یک از پرندگان محل غذا را نمیدانند. یکی از بهترین استراتژیها می تواند دنبال کردن پرندهای با شد که کمترین فا صله را تا غذا دا شته با شد .
این ا ستراتژی در واقع جانمایه الگوریتم است. در الگوریتم PSO هر راهحل که به آن یک ذره گفته میشود، معادل یک پرنده در مدل حرکت جمعی پرندگان میباشد. هر ذره یک مقدار شایستگی دارد که توسط یک تابع شایستگی محاسبه میشود. هر چه ذره در فضای جستجو به هدف - غذا در مدل حرکت پرندگان- نزدیکتر باشد، شایستگی بیشتری دارد. همچنین هر ذره دارای یک سرعت است که هدایت حرکت ذره را بر عهده دارد . هرذره با دنبال کردن ذرات بهینه در حالت فعلی، به حرکت خود در فضای مسئله ادامه میدهد. PSO به این شکل است که گروهی از ذرات در آغاز کار بهصورت تصادفی به وجود می آیند و با بهروز کردن نسلها سعی در یافتن راهحل بهینه مینمایند. در هر تکرار، هر ذره با استفاده از دو بهترین مقدار، بهروز میشود. اولین مورد، بهترین موقعیتی است که تاکنون ذره موفق به رسیدن به آن شده است .
موقعیت مذکور با نام pbest شناخته و نگهداری میشود. مقدار دیگری که تو سط الگوریتم مورد ا ستفاده قرار میگیرد، بهترین موقعیتی ا ست که تاکنون تو سط جمعیت ذرات بد ست آمده ا ست. این موقعیت با gbest نمایش داده می شود .[2] پس از یافتن این بهترین مقادیر، سرعت و مکان هر ذره با استفاده از معادلات - 1 - و - 2 - بهروز میشود. در فرمولهای بالا ، position مقدار فعلی ذره، pbest بهترین مقدار خود ذره تا بهحال، gbest بهترین مقدار سراسری بین کل ذرات، c1 و c2 فاکتورهای یادگیری در محدوده 4 - و - 0، - rand - اعداد ت صادفی در محدوده 1 - و - 0، و w ضریب وزن داخلی برای سرعت بخشیدن به همگرایی ذرات است.
سمت را ست معادله - 1 - از سه ق سمت ت شکیل شده ا ست که ق سمت اول، سرعت فعلی ذره است و قسمتهای دوم و سوم تغییر سرعت ذره و چرخش آن به سمت بهترین تجربه شخ صی و بهترین تجربه گروه را به عهده دارند. اگر قسمت اول را در این معادله درنظر نگیریم، آنگاه سرعت ذرات تنها با توجه به موقعیت فعلی و بهترین تجربه ذره و بهترین تجربه جمع تعیین میشود. به این ترتیب، بهترین ذره جمع، در جای خود ثابت میماند و سایرین به سمت آن ذره حرکت میکنند .[2]
-2روش پیشنهادی
برای حل م سئله گروهبندی دان شجویان بو سیلهی الگوریتم PSO ابتدا به بیان مسئله با پارامترهای این الگوریتم میپردازیم. الگوریتم PSO از بسیاری جهات شبیه الگوریتم ژنتیک بوده و علاوه بر کارایی، سادگی فهم و پیادهسازی آن موجب کاربرد زیاد آن شده است. در الگوریتم PSO تعداد مشخصی ذره به طور تصادفی در فضای N بعدی پخش میشوند. سپس هر ذره با توجه به بهترین موقعیتی که تابه حال داشته و بهترین موقعیتی که کل ذرات تابه حال گزارش دادهاند، در فضا حرکت میکند.
