بخشی از مقاله
چکیده
الگوریتم ژنتیک, یکی از مهمترین الگوریتمهاي ابتکاري میباشد که از آن براي بهینه سازي توابع مختلف استفاده میشود و بر اساس الگوي تکامل طبیعی شکل گرفتهاند. در این الگوریتم اطلاعات گذشته با توجه به خاصیت موروثی بودن الگوریتم استخراج شده ودر روند جستجو مورد استفاده قرار میگیرد. از مزایاي استفاده الگوریتم ژنتیک در مسائل بهینه سازي این است که قسمتهاي مختلف فضاي جستجو مورد کاوش قرار گرفته بنابراین امکان محدود شدن فضاي جستجو وجود ندارد, همچنین این روش بسیار ساده و قابل درك است .
در هر مرحله از اجراي الگوریتم ژنتیکی, یک دسته از نقاط فضاي جستجو مورد پردازشهاي تصادفی قرار میگیرند. به این صورت که به هر نقطه دنبالهاي از کاراکترها نسبت داده میشود و بر روي این دنبالهها, عملگرهاي ژنتیکی اعمال میشود سپس دنبالههاي بدست آمده دیکد میگردد تا نقاط جدیدي در فضاي جستجو بدست آید در آخر براساس این که تابع هدف در هر یک از نقاط چه مقدار باشد, احتمال شرکت نمودن آنها در مرحله بعد تعیین میگردد.
کشف دانش با استفاده از الگوریتمهاي ژنتیک الگوریتم هاي ژنتیک براي کشف قانون به دو روش گسترده تقسیم میشود. مبنی بر اینکه چگونه قانونها در جمعیت افراد - کروموزومها - کد میشوند در روش Michigan هر فرد یک قانون پیشگوئی تنها را کد میکند در حالیکه در روش Pittsburghهر فرد مجموعهاي از قانونهاي پیشگوئی را کد میکند.
انتخاب بین این دو روش وابسته به این است که کدام نوع قانون را میخواهیم کشف کنیم که این مرتبط است به اینکه کدام یک از تکنیکهاي دادهکاوي را دنبال میکنیم. فرض کنید وظیفه طبقهبندي است . معمولا کیفیت مجموعه قانونها را نسبت به کیفیت یک قانون ساده ارزیابی میکنیم. به عبارت دیگر اثر متقابل میان قانونها مهم است در این مورد روش Pittsburgh طبیعیتر به نظر میرسد، از طرف دیگر روشMichigan در انواع دیگر از وظایف دادهکاوي ممکن است طبیعیتر باشد.
در یک کلام طرفداران و مخالفین هر دیدگاه به شرح زیر هستند روش Pittsburgh مستقیما اثر متقابل قانون را زمان محاسبه تابع برازندگی فرد شرح میدهد. هر چند این قانون از نظر نحوي افراد طولانیتر را رهبري میکند که براي محاسبه برازندگی, هزینه محاسباتی خیلی زیاد میشود. در مجموع ممکن است نیاز داشته باشد برخی تغییرات را به عملگرهاي ژنتیک استاندارد تا از عهده نسبت افراد پیچیده برآید.
مثالهایی از الگوریتمهاي ژنتیک براي طبقهبندي که روشPittsburgh را دنبال میکنند .عبارتند از: .GIL, GABIL, HDPDCS در مقایسه با روشPittsburgh ، در روشMichigan افراد سادهتر هستند و از نظر قواعد نحوي کوتاهترند. Michigan زمان کمتري را میگیرد تا تابع برازندگی را حساب کند و استفاده عملگرهاي ژنتیک را ساده میکند به هر حال این مزایا همراه با هزینه است.
زمانیکه تابع برازندگی کیفیت هر قانون را جداگانه ارزیابی کرد اکنون مشکل است کیفیت مجموعه قانون را ارزیابی کنیم. دیگر مشکل زمانی است که قصد داریم مجموعهاي از قانونها را نسبت به یک قانون ساده کشف کنیم. اجازه نداریم جمعیت الگوریتم ژنتیک را ه یک فرد ساده همگرا کنیم. بنابراین نیاز برخی انواع را به روش گونهزایی1 نشان می دهد. واضح است که در روش Pittsburgh این مشکل را نداریم.
میتوانیم براي دوري از گونهزایی، در روش Michigan، چندین بار الگوریتم ژنتیک را اجرا کنیم که در هر بار قانون مختلفی را کشف کند. مشکل این روش این است که از نظر محاسباتی پر هزینه است .مثالهاي الگوریتم ژنتیک براي طبقهبندي که روش Michigan را دنبال می کنندREGAL وCOGIN میباشند. تا حال دیدیم یک فرد در الگوریتم ژنتیک نماینده یک قانون ساده یا مجموعهاي از قانونهاست اما نگفتیم چطور قانونها در ژنوم فرد کد می شوند. اکنون به این مساله میپردازیم.
نمایش مقدم قانون - ترکیب عطفی از شروط -
یک روش ساده کد کردن شرطهاي قانون به یک فرد استفاده کد کردن دودوئی است. فرض کنید یک مشخصه داده شده K مقدار گسسته را میگیرد. سپس شرطی را روي مقدار این مشخصه با استفاده K بیت میگیریم. i امین مقدار - i = 1,2,..., k - قلمرو خصیصه قسمتی از شرط قانون است اگر وفقط اگر i امین بیت “on” باشد. براي نمونه فرض کنید فرد مفروض مقدم قانون را با یک شرط مشخصه با مقدار ساده نمایش دهد. مشخصه Marital_Status است و مقادیرش“single”, “married”, “divorced” و “window”است.
شرط درگیر این مشخصه در ژنوم بوسیله چهار بیت کد می شود. مقدار “0110” مقدم قانون زیر را نمایش میدهد. IF - Marital_Status = “married” OR “divorced” - از اینرو این طرح کدگذاري به ما اجازه میدهد شرطهایی با ترکیب فصلی داخلی نمایش دهیم. با عملگر OR منطقی درون یک شرط بدیهی است این طرح کدگذاري به سادگی بسط داده میشود تا مقدم قانونها را با چندین شرط - اتصال با یکAND منطقی - با ضمیمه در ژنوم نمایش دهد تا مقدار بیتهایی که هر شرط مشخصه با مقدار را نشان می دهند اختصاصی کند.
توجه کنید اگر همه K بیت یک شرط قانون “on” هستند به این معنی است که متناظر خصیصه عامل موثري است که توسط مقدم قانون نادیده گرفته شده است. عملا مطلوب است توجه کنید قانونهایی که در برخی شرایط “turned off” هستند به منظور کاهش اندازه مقدم قانون همه بیتهایشان به "1" تنظیم میشوند. هر وقت بیش از نیمی از بیتها به "1" تنظیم شده باشند میتوانید بطور خودکار همه بیتهاي یک شرط را به "1" تنظیم کنید تکنیک دیگر براي رسیدن به همان اثر در آخر این بخش مطرح خواهد شد.
بحثهاي بالا درباره مشخصههاي گسسته1 بودند که همچنین - - Nominal یا - Discrete - نامیده میشوند در مورد مشخصههاي پیوسته2 مکانیزم کدگذاري دودوئی پیچیدهتر میشود یک روش متداول استفاده از بیتهاست تا مقدار یک مشخصه را در ثبت باینري نمایش دهد. براي نمونه رشته باینري “00001101” نمایش می دهد مقدار 13که به یک مشخصه با مقدار صحیح داده شده است.به جاي استفاده نمایش باینري براي ژنوم یک فرد این ژنوم میتواند در یک نمایش سطح بالا3 بیان شود که مستقیما شرطهاي قانون را کد میکند. یکی از مزیتهاي این نمایش این است که رفتار کاملا یکسانی را از مشخصه هاي پیوسته و گسسته در مقایسه با نمایش باینري منجر میشود.
