IRE: Inductive Rule Extraction

معرفی کتاب "الگوریتم های ژنتیک کاربردی"



کتاب "الگوریتم‌های ژنتیک کاربردی" توسط رندی ال هاپت و سو الن هاپت از پژوهشگران ارشد آزمایشگاه تحقیقات کاربردی دانشگاه ایالتی پنسیلوانیا به رشته تحریر درآمده و ویرایش نخست آن در سال 1997 توسط انتشارات وایلی منتشر شده است. همچنین ویرایش دوم این کتاب در سال 2004 عرضه شده است؛ که مهمترین به روز رسانی آن نسبت به ویرایش نخست، کدهای متلبی است که همراه متن آمده‌اند.


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


این کتاب در 7 فصل به انضمام چندین ضمیمه، سازماندهی شده است.

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

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

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

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

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

فصل ششم به مسائل فنی سخت‌تر یورش می‌برد.

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

همچنین ضمیمه1 برخی روتین‌های الگوریتم ژنتیک را به صورت شبه برنامه لیست می‌کند.


در پایان، خواندن کتاب بسیار خوب "الگوریتم‌های ژنتیک کاربردی" توصیه می‌گردد. 

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



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




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

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

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

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

نمایش دودویی متغیر‌ها 
در مقایسه با تکامل بیولوژیک، الگوریتم ژنتیک دودویی نیز با یک جمعیت اولیه از اعضای تصادفی شروع به کار می‌کند. هر رشته باینری(کروموزوم)، ویژگی‌های انتخاب شده‌ی(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}})$$
اغلب تابع هزینه بسیار پیچیده است. کاربر بایستی تصمیم بگیرد کدام متغیر‌های مسئله مهم‌تر هستند. متغیر‌هایِ بیش از حد، الگوریتم ژنتیک را به دردسر می‌اندازند. برخی اوقات، تعداد صحیح و انتخاب متغیر‌ها از تجربه یا اجراهای بهینه‌سازی آزمایشی  به دست می‌آیند؛ اوقات دیگر، یک تابع هزینه تحلیلی برای این کار وجود دارد. بیشتر مسائل بهینه‌سازی نیاز به محدودیت‌ها یا مرزهای برای متغیر دارند.

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