مقاله کامل الگوریتم ژنتیک با جمعیت پویا برای حل مساله بهینه سازی همزمان چند دستور پرس و جو

الگوریتم ژنتیک با جمعیت پویا برای حل مساله بهینه سازی همزمان چند دستور پرس و جو
چکیده :هدف از بهینه سازی چند دستور پرس وجو، یافتن طرحهای اجرایی است بطوریکه هزینه کل اجرای دستورات پرس و جو با استفاده از این طرحها حداقل گردد. هر دستور پرس و جو بطور مجزا میتواند چندین طرح داشته باشد. از آنجا که هر طرح از یک سری وظایف تشکیل میشود، هدف از MQO پیدا کردن طرحهایی است که بیشترین اشتراک وظایف را با طرحهای دیگر داشته باشند. در حالت کلی این مساله جزو مسائل NP-Complete قرار می گیرد. تاکنون روشهای مختلفی برای این مساله پیشنهاد شده است. در این مقاله مساله بهینه -سازی چند دستور پرس و جو با استفاده از از الگوریتم ژنتیک با جمعیت پویا حل شده است. نتایج نشان میدهد که روش پیشنهادی، زمان اجرای کمتر و سرعت همگرایی بیشتری نسبت به روشهای موجود دارد.
واژه هایکلیدی: بهینه سازی چند پرس وجو، الگوریتم ژنتیک، ترتیب پیوندها
1- مقدمه:
یکی از مهمترین و پرهزینهترین بخشها در پایگاه داده، بهینهسازی دستورات پرس و جو است. چنانچه انجام چند دستور پرس و جو همزمان از پایگاه داده درخواست شود، بدست آوردن یک طرح اجرایی با حداقل هزینه انجام این دستورات، از وظایف بهینهساز پایگاهداده میباشد. بهینهسازهای سنتی در یک زمان تنها یک دستور پرس و جو را در نظر میگیرند و سعیمیکنند کمترین زمان اجرا را پیدا کنند[6]. اما برای حل چندین دستور پرس و جو بطور همزمان و شناسایی وظایف مشترک آنها، نیار است تمام مجموعه طرحهای اجرایی این پرس و جوها باید با هم اجرا شوند، زیرا وظایف پرهزینۀ طرح ممکن است منجر به اشتراک بیشتر
با پرس و جوهای دیگر شود و راه حل بهتری را برای مسئله MQO حاصل کند.
در مساله MQO ممکن است طرحی که کمتر از حد بهینه است نیز برای پرس و جو ترجیح داده شود، زیرا ممکن است این طرح اشتراک وظایف بیشتری با طرحهای دیگر داشته باشد و زمان اجرای کل دستورات کاهش یابد.
یکی از اولین فرمولبندیهایMQO را میتوان در [4] یافت. تحت این فرمولبندی، مسئله MQO میتواند به دو فاز تقسیم شود. اولین فاز در MQO وظایف مشترک بین دستورات پرس و جو را شناسایی میکند و مجموعۀ کوچکی از طرحهای اجرایی براییک پرس و جو ایجاد میشود.
معمولاً، فاز دوم MQO زمانبر ترین فاز در مسئله است. در فاز دوم، یک طرح اجرایی کلی و کارا برای مجوعه پرس و جوها تولید میشود، که طرحها و وظایف مشترک بین آنها در فاز یک مشخص شدند. در[4]، فاز دوم MQOبعنوان مسئله NP‐Complete نشان داده شده است. با استفاده از فرمول بندی [4]، فاز دوم مستقل از فاز اول مطالعه شده است. [6] و [5] فقط روی فاز دوم مساله کار کردهاند. در هر دو روش از تکنیکهای تکاملی مانند A_star استفاده شده است.
بخش 2 مروری بر چگونگی حل مسائل NP‐Complete توسط الگوریتم ژنتیک دارد. در بخش 3 نحوه مدلسازی مساله MQO توسط الگوریتم ژنتیک بررسی میشود. در بخش 4 به ارائه راه حل پیشنهادی برای مساله MQO پرداخته میشود. در بخش 5 نتایج بدست آمده با روش-های موجود مقایسه میشود و در بخش 6 نتیجه گیری و پیشنهاداتی برای کارهای آینده ارائه می شود.
2- مروری بر الگوریتم ژنتیک :
یکی از مشهورترین تکنیکهای اکتشافی استفاده شده برای بهینه سازی مسائل پیچیده، الگوریتم ژنتیک است. تعریفی از آن در [8] آورده شده است، الگوریتم ژنتیک برای حل بسیاری از مسائلNP-Complete استفاده شده است. گلدبری در[4] عملی بودن الگوریتم ژنتیک را با ارائهی خلاصه ای از کاربردهای الگوریتم ژنتیک، نشان داده است.
الگوریتم ژنتیک مفاهیم تکاملی زیست شناسی را شبیه سازی میکند. این شبیهسازی شامل روشهای احتمالی با استفاده از اصول تکاملی است[1]. در الگوریتم ژنتیک ساختار دادۀ اصلی بصورت برداری از ژنها است (که کروموزوم نامیده می شود). هر کروموزوم نمایش دهندۀ یک نمونه راه حل برای مسئله است. اعضای کروموزوم که (ژن ها نامیده می شوند) شامل بخشی از راه حل مسئله اند. کیفیت نمونه راهحل (یعنییک کروموزوم) با نزدیکی آن به راهحل بهینه(که تابع برازندگی نامیده می شود) تعریف می شود.
الگوریتم ژنتیک با استفاده از عملگرهای تکاملی (که عملگرهای ژنتیک هم نامیده میشوند) راه حل بهینه را جستجو میکند. در ابتدا با حالت تصادفی ضعیف، کروموزوم ها برای نمایش مجموعه راه حلهای مختلف تولید میشوند. سپس عملگرهای ژنتیک روی کروموزومهای ضعیف اعمال میشوند و کروموزومهای جدیدی را برای مرحلۀ بعد تولید می-کنند.
سه عملگر استفاده شده در الگوریتم ژنتیک بصورت زیر است:
عملگر تقاطع : در عملگر تقاطع، بخشی از کروموزوم والد برای ایجاد کروموزوم، فرزند تغییر میکند.
عملگرجهش: کروموزوم های جدید توسط اصلاح تصادفی تعداد کمی از ژنهای موجود در کروموزوم تولید میشود. عملگر جهش هیچ وقت بر روی بهترین راه حل در جمعیت اعمال نمی شود.
عملگر انتخاب: این عملگر تعیین میکند کدام کروموزوم برای نسل بعدی باید زنده بماند. سادهترین راه میتواند بدین صورت تعریف شود که کروموزومهای بهتر، شانس بیشتری را برای زنده ماندن در نسل بعدی دارند. این اتفاقی است که واقعاً در فرآیندهای تکاملی اتفاق میافتد. بهرحال، گاهی اعمال عملگر تقاطع یا جهشروییک کروموزوم نامناسب ممکن است کروموزوم مناسب تولید کند[3] . متداول ترین تکنیکهای انتخاب بصورت زیر هستند:
روش برش: ابتدا همه کروموزومها بر اساس عددی که تابع ارزیابی به آنها تخصیص داده بصورت نزولی (از بهترین به بدترین) مرتب می شوند. سپس n کروموزوم بالایی این لیست با احتمال یکسان به نسل بعد منتقل می شوند.
روش مسابقهای: عدد r بصورت تصادفی انتخاب می شود. سپس r کروموزوم از جمعیت انتخاب شده و کروموزوماز جمعیت انتخاب شده و کروموزوم با بهترین مقدار (زماناجرا) به نسل بعدی منتقل میشود. این روند ادامهمییابد تا به مقدار مناسب جمعیت نسل بعد رسیده شود. در این روشممکن است یک کروموزوم، چند بار انتخاب شود.
روش چرخ شانسی: در این روش کروموزومها بر حسب مقدار برازندگی-شان روی قسمتهایی از دایره قرار میگیرند. هرچه کروموزومهای داخلیک قسمت مقدار برازندگی بهتری داشته باشند، مساحت آن قسمت نیزبیشتر خواهد بود. سپس یک عدد تصادفی تولید شده و کروموزومهایقسمت متناسب با آن عدد تصادفی به نسل بعد منتقل میشوند. بران در[9] از این روش استفاده کرده است.
3-مدلسازی الگوریتم ژنتیک برایMQO:
الگوریتم ژنتیک به آسانی میتواند مساله MQO را مدلسازی کند. هر کروموزوم، یک راه حل برای این مساله است. هر ژن
در کروموزومها بیانگر یک طرح برای دستور پرس و جوی مربوط به آن می باشد.
هر کروموزوم Ci از تعدادی ژن Gj تشکیل شده است. هر ژن یک راه حل براییک دستور پرس و جو است. در یک نسل، بسته به میزان جمعیت مربوط به آن Pk نسل تعداد کروموزومها متغیر است.
عملگر انتخاب Σ : جمعیت مربوط به یک نسل را گرفته و تعدادی از آنها را جهت انتقال به نسل بعد انتخاب می کند.
عملگر جهش M : یک کروموزوم را بعنوان ورودی می گیرد و کروموزوم جدیدی ایجاد می کند.
برای انتخاب تعدادی از کروموزومها جهت انتقال به نسل بعد، کیفیت کروموزومها (که توسط تابع ارزیابی تعیین می شود) مدنظر قرار می-گیرد. یک انتخاب ساده برای تابع ارزیابی، معکوس کل زمان اجرای وظایف دستورات پرس و جو می باشد.
همچنین عملگرهای تقاطع و جهش را بسادگی میتوان برای مساله MQO تعریف کرد. این عملگرها باعث ایجاد راه حلهای جدید و معتبر میشوند. از آنجا که ژنهاییک کروموزوم بیانگر طرح انتخابی برای دستور پرس و جوی مربوط به آن ژن هستند،جایگزین کردن یک طرح با طرح فعلی باعث ایجاد یک راه حل جدید و معتبر می شود. این کار را عملگر جهش انجام می دهد.
برای عملگر تقاطع انواع مختلفی را میتوان در نظر گرفت: تک نقطهای، چند نقطهای و قطعهای. در روش ارائه شده همه این تکنیکها، راه حل-های معتبری را ایجاد می کنند. چنانچه دو کروموزوم، بیانگر دو راه حل معتبر برای مساله MQO باشند، هر عملگر تقاطع روی این دو کروموزوم، راهحلهای جدید و معتبر ایجاد خواهد کرد. صرفنظر از نوع
عملگر تقاطع و مکان انجام آن، از آنجا که تمام قطعاتی که در این عملگر جابجا می شوند بیانگر راهحلهای معتبر برای دستورات پرس و جوی مربوطه هستند، در نتیجه راهحلهای جدید نیز معتبر خواهند بود.
4-ارائه راه حل پیشنهادی: (الگوریتم ژنتیک با اندازه جمعیت پویا) (Dynamic Population GA (DP-GA
الگوریتم در مینیممهای محلی است و همچنین ازلحاظمحاسباتی پرهزینه هستند. از طرفی پدیده ازدحام نیز یکی از عوامل مخرب در کیفیت الگوریتم ژنتیک است[3] . زمانی که منابع به اندازه کافی در دسترس باشند و راه حلهای نسبتاً مناسب زیاد باشند، اندازه جمعیت افزایش مییابد و زمانی که تعداد راه حلهای مناسب در یک نسل کم باشند اندازه جمعیت کاهش مییابد. شاید در نگاه اول، روش پیشنهادی چندان موثر بنظر نرسد ولی آزمایشها نشان داده است که استفاده از این روش، دقت و سرعت اجرای الگوریتم ژنتیک را بهبود میبخشد. دلیل استفاده از این تکنیک، جلوگیری از گیرکردن الگوریتم در اکسترممهای محلی و افزایش سرعت آن است. در صورت پیدا شدن جواب مناسب، اندازه جمعیت افزایش مییابد. درحقیقت با این کار به الگوریتم اجازه داده می شود که راه حلهای بیشتری را منظور کند و از خطر مینیمم های محلی عبور کند. زمانی که اندازه بهترین جواب در یک نسل از مقدار آستانه ای کمترباشد، اندازه جمعیت کاهش مییابد.
با انجام این کار سرعت اجرای الگوریتم افزایش مییابد و می توان امید داشت که در نسلهای بعدی جوابهای بهترییافت شوند.
اگرچه در بعضی از نسلهای اجرای الگوریتم ممکن است بر میزان جمعیت و در نتیجه بر میزان محاسبات افزوده شود و موجب کم شدن سرعت الگوریتم گردد ولی انتخاب یک مقدار
آستانه مناسب برای چگونگی تغییر جمعیت باعث میشود که زمان اجرا در کل کاهش یابد.
یکی از مهمترین پارامترها در این روش چگونگی تغییر اندازه جمعیت است. برای این منظور ابتدا مساله با روش حریصانه حل می شود. دلیل این امر سرعت اجرای الگوریتم حریصانه می باشد. از عدد بدست آمده توسط الگوریتم حریصانه بعنوان یک مقدار آستانه استفاده میشود.درمرحله بعد با توجه به اختلاف بهترین جواب در هر نسل با جواببدست آمده توسط الگوریتم حریصانه، جمعیت نسل بعد تعیین می شود.در این مقاله جمعیت نسل جدید طبق فرمول زیر محاسبه شده است:
/
که در آن Pnew جمعیت نسل بعد، Pold جمعیت نسل فعلی Tgزمان محاسبه شده توسط الگوریتم حریصانه و Cbest ( (fitness زماناجرای بهترین راه حل در نسل فعلی است.
5- نتایج تجربی و تجزیه تحلیل:
در این قسمت نتایج تجربی مقایسه الگوریتم ژنتیک با جمعیت ثابت و الگوریتم ژنتیک پیشنهادی با جمعیت پویا ارائه شده است. آزمایشها بر روی کامپیوتری با پردازنده GHz 2.2 و 2Gحافظه اصلی انجام گرفته اند. زبان پیاده سازی الگوریتمها C است.برای تولید ورودی از پارامترهای جدول 1 استفاده شده و به ترتیب زیر عمل شده است:
در ابتدا وظیفه ها بصورت تصادفی تولید میشوند. برای تولید آنها از دوپارامتر تعداد وظایف(T) و کمترین و بیشترین مقدار برای زمان اجرای وظایف استفاده می شود. ابتدا به تعداد T وظیفه تولید میشود. سپس برای هر وظیفه تولید شده یک عدد در بازه MinET و MaxET بعنوان زمان اجرا، تخصیص مییابد. بعد از تولید وظایف، آنها در بین
طرحها پخش میشوند. برای این منظور از پارامترMinP و MaxP استفاده میشود. اگرچه ممکن است طرحهای زیادی از وظایف مشترک استفاده کنند، ولی از ایجاد دو طرح دقیقاً یکسان جلوگیری میشود. در نهایت، دستورات پرس و جو ایجاد میشوند. برای تولید آنها از پارامتر تعداد دستورات پرس و جو (Q) و MinQ و MaxQ استفاده میشود. هر دستور پرس و جو مجموعه ای از طرحهای مختص به خود، برای اجرا دارد. بنابراین یک طرح خاص، بیش از یک دستور پرس و جو را حل نمیکند. در عین حال از آنجا که هر دستور پرس و جو از طرح و هر طرح از وظایف تشکیل شده است، این وظایف می توانند بین دستورات پرس و جو به اشتراک گذاشته می شوند.
جدول 1- مقادیر استفاده شده برای شبیه سازی مساله MQO با الگوریتم ژنتیک
برای محاسبه اندازه ورودی، مقادیر میانگین(MinP,MaxP) و(MinQ,MaxQ)در این مقاله جمعیت نسل جدید طبق فرمول زیر محاسبه شده است:
Input size = Q ∗ QA ∗ PA(2)
در حقیقت اندازه ورودی، برابر با اندازه فضای جستجوی مساله MQO است. این عدد با مقدار بهینه راه حل ارتباطی با هم ندارند. با وجود اینکه یک دستور پرس و جو می تواند چند طرح اجرایی داشته باشد، در جواب نهایی تنها یکی از این طرحها به ازای هر دستور پرس و جو ظاهر خواهد شد. بنابراین مقدار بهینه راه حل، تنها با تعداد دستورات پرس و جو، تعداد وظایف در هر طرح و زمان اجرای وظایف ارتباط دارد.
برای مقایسه الگوریتمهای اکتشافی که برای حل مسائلNP‐Complete ارائه میشوند، معمولاً دو جنبه مد نظر قرار می گیرند: زمان اجرای الگوریتم و اختلاف جواب بدست
آمده توسط الگوریتم با جواب بهینه. Bayir در [6] نه حالت مختلف الگوریتم ژنتیک را بررسی کرده و نشان داده است که برای مساله بهینه سازی چند دستور پرس و جو، استفاده از عملگر انتخاب برشی و عملگر اندازه جمعیت اولیه تنها در اولین اجرای الگوریتم استفاده میشود. در نسلهای بعدی این مقدار با توجه به بهترین جواب یافته شده در هر نسل، کمتر یا بیشتر خواهد شد. نرخ جهش بیان میکند در هر نسل از اجرای الگوریتم، چند درصد از کروموزومهای آن نسل دچار جهش خواهند شد. در ادامه، از عبارت “زمان اجرای کروموزوم” بعنوان زمان اجرای وظایفی که به عنوان ورودی مساله MQO به الگوریتم ژنتیک داده می شود، استفاده می کنیم.
نتایجبدستآمدهدرنمودارهایشکل1و2 نشاندادهشده است.
الگوریتم DP_GA دقتبیشتریرادریافتنجواب نزدیکبهبهینهازخودنشانمیدهد .دلیلاینامراستفادهاز جمعیتمتغیراستکه اجازه میدهد الگوریتم از مینیمم های محلی عبور کرده و فضای بیشتری را جستجو کند. همچنین در نمودار شکل 2 مشخص است که سرعت اجرای الگوریتم پیشنهادی نیز بیشتر شده است. در مواردی که زمان اجرای کروموزومهاییک نسل اختلاف زیادی با جواب بهینه دارد، اندازه جمعیت کاهش مییابد. این کاهش جمعیت باعث افزایش سرعت الگوریتم میشود و همانطور که در بخش 4 ذکر شد سرعت همگرایی به جواب را در این موارد بیشتر می کند.
/
شکل1. نمودار زمان پاسخ
/
شکل 2. نمودار زمان اجرا
6- نتیجه گیری
در این مقاله راهکاری مبتنی بر الگوریتم ژنتیک با جمعیت متغیر ارائه شد. یکی از اشکالات اصلی الگوریتم ژنتیک زمانبر بودن محاسبات و گیرکردن در اکسترممهای محلی است. با روش ارائه شده، هر چند در برخی موارد میزان محاسبات در یک نسل از الگوریتم ممکن است بیشترشود، ولی در کل از میزان محاسبات کاسته شده و در نتیجه به سرعت اجرای الگوریتم افزوده خواهد شد. همچنین بدلیل زیاد شدن جمعیت در شرایط ذکرشده در مقاله، این اجازه به الگوریتم پیشنهادی داده میشود که از مینیممهای محلی عبور کرده و سرعت همگرایی بیشتری نسبت به الگوریتم ژنتیک پایه داشته باشد. از اشکالات این روش نیاز به تنظیم پارامترهای اولیه و نیز تعیین مقدار آستانه مناسب برای میزان تغییر جمعیت است. در این مقاله از جواب روش حریصانه بعنوان مقدار آستانه استفاده شد. بنظر میرسد استفاده از روشهای

فایل : 11 صفحه

فرمت : Word