الگوریتم ژنتیک دودویی و پاسخ به پنج سوال مهم درباره آن

قدرت انتخاب و تصمیم‌گیری مختص انسان است؛ اما من در عجبم که طبیعت به چه خوبی و بهتر از هر کسی دیگری در این عالم، از عهده آن برمی‌آید.

احمدرضا پاکرایی

مقدمه

طی سه پست آتی به توضیح الگوریتم ژنتیک دودویی پرداخته، به پنج سوال مهم در خصوص آن پاسخ می‌دهیم؛ یعنی

چه موضوع مهمی وجود دارد که الگوریتم ژنتیک دودویی را به دردسر می‌اندازد؟

دو دلیل مهم استفاده از عملگر جهش در الگوریتم ژنتیک دودویی چیست؟

در چه مرحله‌ای از اجرای الگوریتم ژنتیک دودویی نباید از عملگر جهش استفاده کرد؟

نخبه‌گرایی در الگوریتم ژنتیک دودویی، به چه موضوع مهمی اشاره دارد؟

نکات کلیدی در به‌کارگیری روش‌های مختلف انتخاب، در الگوریتم ژنتیک دودویی کدامند؟ 

و در آینده نزدیک به کمک این مطالب الگوریتم ژنتیک دودویی را در متلب پیاده سازی خواهیم کرد. با ما در ادامه همراه باشید.

الگوریتم ژنتیک: انتخاب طبیعی بر روی کامپیوتر

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

نمایش دودویی متغیر‌ها 

در مقایسه با تکامل بیولوژیک، الگوریتم ژنتیک دودویی نیز با یک جمعیت اولیه از اعضای تصادفی شروع به کار می‌کند. هر رشته باینری(کروموزوم)، ویژگی‌های انتخاب شده‌ی(Selected Characteristics) یکی از اعضای جمعیت را نشان می‌دهد. می‌توان دو رشته‌ای را که به تصادف انتخاب شد‌ه‌اند، با یکدیگر ترکیب کرد در این صورت دو رشته جدید به وجود می‌آیند که ترکیبی از ویژگی‌های دو رشته دیگر هستند؛ پس هر رشته‌ باینری جدید، بخش‌های از رشته‌های باینری والدین خود را شامل می‌شود.  

اجزای الگوریتم ژنتیک دودویی

الگوریتم ژنتیک همانند هر الگوریتم بهینه‌سازی دیگر با تعریف متغیر‌های بهینه‌سازی، تابع هزینه(Cost Function) و هزینه(Cost) شروع می‌شود و مانند سایر الگوریتم‌های بهینه‌سازی با آزمایش همگرایی(Convergence) به پایان می‌رسد. سلسه مراتب اجرای الگوریتم ژنتیک دودویی به صورت یک فلوچارت ساده، در شکل1 نشان داده شده است.

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

تابع هزینه و انتخاب متغیرها 

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

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

الگوریتم ژنتیک به وسیله تعریف یک کروموزوم یا آرایه‌ای از مقادیر متغیرها برای بهینه‌سازی شروع می‌شود. اگر یک کروموزوم $$N_{var}$$ متغیر داشته باشد که توسط$$P_{1},P_{2},P_{3},...,P_{N_{var}}$$   داده شده باشند؛ سپس کروموزوم به صورت یک بردار ردیفی $$N_{var}$$  عنصری نوشته می‌شود.

$$Chromosome=[P_{1},P_{2},P_{3},...,P_{N_{var}}]$$

   هر کروموزوم هزینه‌ای دارد که با ارزیابی تابع هزینه در $$P_{1},P_{2},P_{3},...,P_{N_{var}}$$   تعیین می‌شود.

  $$Cost=f(chromosome)=f(P_{1},P_{2},P_{3},...,P_{N_{var}})$$

اغلب تابع هزینه بسیار پیچیده است. کاربر بایستی تصمیم بگیرد کدام متغیر‌های مسئله مهم‌تر هستند. متغیر‌هایِ بیش از حد، الگوریتم ژنتیک را به دردسر می‌اندازند. برخی اوقات، تعداد صحیح و انتخاب متغیر‌ها از تجربه یا اجراهای بهینه‌سازی آزمایشی  به دست می‌آیند؛ اوقات دیگر، یک تابع هزینه تحلیلی برای این کار وجود دارد. بیشتر مسائل بهینه‌سازی نیاز به محدودیت‌ها یا مرزهای برای متغیر دارند.

به زودی در پست بعدی به ادامه مطلب خواهیم پرداخت با ما همراه باشید.

معیارهای ارزیابی قوانین در داده‌کاوی

به نام خدا

مقدمه

معیارهای بسیاری برای ارزیابی عملکرد در یادگیری ماشین و کشف دانش استفاده می‌شود. در استنتاج پیشگویانه (Predictive induction) مبتنی بر دسته‌بندی، اغلب معیار دقت(Accuracy) دسته‌بندی، استفاده می‌شود. در حالیکه سایر معیارهای استاندارد عبارتند از: دقت(Precision)، یادآوری(Recall)، حساسیت(Sensitivity) و اختصاصی کردن(Specificity).

در سایر عملیات‌های کشف دانش مانند قوانین انجمنی که از  جمله روش‌های استنتاج توصیفی(Descriptive Induction) است از معیارهای دیگری نظیر پشتیبانی(Support)، اعتماد(Confidence)، جذابیت(Interestingness) و قابلیت فهم(Comprehensibility) تعریف می‌شود.

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

معیارهای جالب در داده‌کاوی قوانین انجمنی

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

طی سالیان گذشته کارهای بسیاری در زمینه داده‌کاوی به ویژه در زمینه یافتن انجمن‌ها و همبستگی‌ها در میان آیتم‌ها در یک پایگاه داده از تراکنش‌های مشتریان انجام شده است. در زمینه تحلیل سبد خرید(Market Basket Analysis) قوانین انجمنی آیتم‌های را متمایز می‌کند که در اغلب موارد، بخش قابل توجهی از مشتریان، همراه با آیتم‌های خاص دیگری خریداری کرده‌اند. به عنوان مثال ممکن است ما متوجه شویم که 95 درصد از مشتریانی که نان خریده‌اند شیر نیز خریداری کرده‌اند.

هر قانون در داده‌کاوی قوانین انجمنی بایستی دو محدودیت مشخص شده کاربر را برآورده کند؛ یکی معیاری از اهمیت آماری است که پشتیبانی(Support) نامیده می‌شود و دیگری معیاری از خوب بودن قانون است که اعتماد(Confidence) نامیده می‌شود.

در ادامه به تعریف رسمی(Formal Definition) و برخی توضیحات در خصوص تعدادی از معیارهای ارزیابی قوانین انجمنی که در ابتدا معرفی شدند، خواهیم پرداخت.

 

پاسخ به 4 سوال در خصوص قوانین (Rules)

پرسش‌های در خصوص قوانین 

در ادامه بر برخی از پرسش‌ها در خصوص قوانین از ظن خودم پاسخ می‌دهم.

1) قوانین چگونه به وجود می‌آیند؟

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

2) قوانین کجا نگهداری می‌شوند؟

در خصوص انسان‌ها بیشتر قوانین در ضمیر خودآگاه ساخته و در ضمیر ناخودآگاه ساکن می‌شوند.

3)آیا قوانین ثابت هستند؟

خیر. قوانین متغیر هستند و ممکن است در طی زمان و به همراه تجربه‌های جدید تغییر کنند. ولی با توجه به قدرت یک قانون ممکن شواهد بیشتری برای تغییر نیاز باشد.

4) قوانین در کجا به کار گرفته می‌شوند؟

یک مجموعه قانون در موقعیت‌های مختلف به ما می‌گوید چه کاری باید انجام دهیم یا چه نتیجه‌ای بایستی بگیریم.

تفاوت Rule و Law در زبان انگلیسی

آیا شما تفاوت بین Rule و Law را در انگلیسی می‌دانید؟

 در دیکشنری آکسفورد چندین تعریف  برای لغات Rule و Law آورده شده است که در ادامه به چند مورد آن اشاره می‌کنیم.

تعریف Rule در زبان انگلیسی

1) مجموعه‌ای از مقررات یا اصول صریح یا درک شده، حاکم بر رفتار یا روش در یک حوزه خاص از فعالیت.

1-1) اصلی که در یک حوزه خاص از دانش عمل می‌کند، توصیف یا تجویز آنچه ممکن یا مجاز است.

2) کنترل یا حاکمیت بر یک منطقه یا مردم

3) حالت عادی یا معمولی چیزها

تعریف Law در زبان انگلیسی

نظامی از قوانین، که یک کشور  یا جامعه خاص به عنوان تعدیل کردن اعمال اعضایش به رسمیت شناخته که ممکن است به وسیله تحمیل مجازات، اعمال شود.

تفاوت بین Rule و Law

LAWs قواعد و دستورالعمل های هستند که توسط نهادهای اجتماعی برای مدیریت رفتار تنظیم شده‌اند. Law و Rule اگر چه از لحاظ لغوی دارای معنی یکسان «قانون» هستند ولی در زمینه‌های متفاوت به کار گرفته می‌شوند. Law مفهوم کلی‌تری از Rule است و می‌توان گفت Law بیشتر به تصویب قوانین کلی در مجالس قانون‌گذاری اشاره دارد در حالیکه که جزئیات اجرایی آن به وسیله قوانین اجرایی (Rules) مشخص می‌گردد. شکستن Law از شکستن Rule مجازات بیشتری به دنبال دارد.