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

الگوریتم‌ ژنتیک چیست؟

طبیعت همواره منبع عظیمی از دانش برای انسان بوده است. الگوریتم‌های ژنتیک (GAها)، الگوریتم‌های مبتنی بر جستجو هستند که بر اساس مفاهیم انتخاب طبیعی و علم ژنتیک کار می‌کنند. GAها زیر مجموعه‌ای از روش‌ محاسباتی دیگری هستند که محاسبات تکاملی نامیده می‌شود.
GA توسط John Holland و دانشجویان و همکاران او، به ویژه David E. Goldberg در دانشگاه میشیگان طراحی شده است؛ از آن زمان تا کنون این الگوریتم برای مسائل بهینه‌سازی مختلف بکار رفته است و به میزان موفقیت قابل توجهی دست یافته است.
در الگوریتم ژنتیک، مخزن یا جمعیتی از پاسخ‌های احتمالی برای یک مسئله‌ی مشخص داریم. این پاسخ‌ها سپس تحت فرآیند باز ترکیب {recombination} و جهش {mutation} (همچون علم ژنتیک) قرار می‌گیرند و فرزندان جدیدی تولید می‌کنند؛ این فرآیند بر روی نسل‌های مختلف تکرار می‌شود. به هر فرد (یا پاسخ‌ کاندیدا) یک مقدار صلاحیت (بر اساس مقدار تابع هدف) تخصیص داده می‌شود و به افراد شایسته‌تر شانس بالاتری جهت جفت‌گیری داده می‌شود، و در نتیجه افراد «شایسته‌تری» به وجود می‌آیند. این امر با نظریه‌ی داروین مبنی بر «بقای شایسته‌ترین» سازگار است.
بدین ترتیب، افراد یا پاسخ‌های شایسته‌تر «تکامل» در نسل‌های مختلف پیدا می‌کنند تا زمانی که ضابطه‌ی توقف برآورده شود.
الگوریتم‌های ژنتیک دارای ماهیت به اندازه‌ی کافی تصادفی هستند، اما بسیار بهتر از جستجوی محلی تصادفی کار می‌کنند (در جستجوی محلی تصادفی تنها پاسخ‌های تصادفی مختلف آزمایش می‌شوند، و بهترین پاسخ در نظر گرفته می‌شود)، زیرا در الگوریتم ژنتیک از اطلاعات تاریخی {سابقه} نیز استفاده می‌شود.

مزایای GA

الگوریتم ژنتیک مزایای مختلفی دارند که آنها را بسیار محبوب کرده است. این مزایا عبارتند از:
• به هیچ گونه اطلاعات مشتقه‌ای نیاز ندارند (چنین اطلاعاتی در بسیاری موارد در مسائل واقعی موجود نیست).
• الگوریتم ژنتیک در مقایسه با روش‌های سنتی‌تر سریع‌تر و کارامدتر هستند.
• آنها قابلیت‌های موازی‌کاری بسیاری خوبی دارند.
• الگوریتم ژنتیک توابع پیوسته و توابع گسسته، و همچنین مسائل چند هدفی را بهینه‌ می‌کند.
• بجای تنها یک پاسخ، لیستی از پاسخ‌های «مناسب» ارائه می‌دهد.
• همواره یک پاسخ برای مسئله پیدا می‌کند؛ این پاسخ با گذشت زمان بهتر می‌شود.
• وقتی فضای جستجو بسیار بزرگ است و تعداد زیادی پارامتر درگیر هستند، الگوریتم ژنتیک بسیار کارامد است.

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

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

ترجمه  itrans.ir 

 (سیارک) تکنیک های داده کاوی به شکل گسترده ای در سیستم های پشتیبانی تصمیم گیری درمانی برای پیش بینی و تشخیص بیماری های مختلف با دقت مناسب استفاده شده است. به دلیل توانایی آنها در شناسایی الگوها و روابط پنهان بین داده های پزشکی، این تکنیک ها در طراحی سیستم های پشتیبانی درمانی بسیار موثر واقع شده اند. یکی از مهمترین کاربردهای چنین سیستم هایی در شناسایی بیماری های قلبی نهفته است، چراکه این بیماری یکی از عوامل اصلی مرگ و میر در دنیا است. تقریبا تمام سیستم هایی که بیماری های قلبی را پیش بینی می کنند از مجموعه داده های درمانی با پارامترها و ورودی ها از آزمایش های پیچیده ی استفاده می کنند. هیچکدام از این سیستم ها، بیماری های قلبی را بر اساس عوامل خطر مثل سن، سابقه ی خانوادگی، دیابت، فشار خون بالا، کلسترول بالا، مصرف دخانیات، مصرف الکل، چاقی، و یا کم فعالیتی فیزیکی تشخیص نمی دهند. بیماران قلبی بسیاری از این عوامل خطر را در خود دارند که می توان از آنها برای شناسایی بیماری استفاده کرد. سیستم های مبتنی بر چنین عوامل خطری نه تنها به افراد متخصص کمک می کند، بلکه می تواند هشدار به موقعی برای بیماران در مورد حضور احتمالی بیماری قلبی در وی قبل از حضور در بیمارستان یا انجام چکاپ های پرهزینه فراهم سازد. از این رو، این مقاله به ارائه تکنیکی برای پیش بینی بیماری های قلبی بوسیله عوامل خطر می پردازد. این تکنیک حاوی دو مورد از موفق ترین ابزارهای داده کاوی، شبکه های عصبی و الگوریتم های ژنتیکی می باشد. سیستم ترکیبی پیاده سازی شده از مزیت بهینه سازی جهانی الگوریتم ژنتیک برای تشکیل بارهای شبکه عصبی بهره می برد. یادگیری این الگوریتم در مقایسه با انتشار به عقب، سریع تر، پایدارتر و دقیق تر است. این سیستم در Matlab پیاده سازی شده است و بیماری های قلبی را با دقت 89 درصد پیش بینی می کند.

بیماری های قلبی عامل اول مرگ و میر در سطح جهان است. در سال 2008، حدود 17.3 میلیون نفر به دلیل بیماری های قلبی مردند که 20 درصد تمام مرگ ومیر ها را تشکیل می داد. از این مقدار، حدود 7.3 میلیون مورد به دلیل بیماری عروق کرونر بود و 6.2 میلیون مورد نیر به دلیل سکته رخ داده بود. تحقیقات اخیر در زمینه ی داروی توانسته عوامل خطری را شناسایی کند که به توسعه بیماری های قلبی کمک می کنند؛ با این حال، تحقیقات بیشتری برای استفاده از این دانش در کاهش رخداد بیماری های قلبی لازم است. دیابت، فشار خون و کلسترول بالا به عنوان عوامل خطرزای اصلی در بیماری های قلبی شناسایی شده اند.

عوامل خطر مربوطه به سبک زندگی مثل عادات غذایی، کم تحرکی، مصرف الکل و دخانیات و چاقی نیز از عوامل مهم بیماری های قلبی به حساب می آیند. مطالعات متعددی نشان می دهند که کاهش این عوامل خطر می تواند در جلوگیری از بیماری های قلبی تاثیر زیادی داشته باشد. تحقیقات زیادی بر روی جلوگیری از خطر بیماری های قلبی وجود دارد. داده ها از مطالعات جمعیت شناختی در پیش بینی بیماری های قلبی بر اساس فشار خون، عادات دخانی، سطوح کلسترول و فشار خون و دیابت موثر واقع شده اند. محققان از این الگوریتم های پیش بینی در قالب های سازگاریافته از برگه های امتیازدهی ساده سازی شده استفاده کرده اند تا بیماران بتوانند ریسک بیماری های قلبی خود را محاسبه کنند. نمره خطر فرامینگهام (FRS) یک معیار پیش بینی خطر است که در الگوریتم های پیش بینی بیماری های قلبی استفاده شده است.
این مطالعه با هدف توسعه ی یک سیستم داده کاوی هوشمند بر اساس شبکه های عصبی بهینه شده با الگوریتم ژنتیک برای پیش بینی بیماری قلبی بر اساس دسته بندی های عوامل خطر انجام شده است. این سیستم بوسیله MATLAB R2012a پیاده سازی شده است.

2. تکنیک های داده کاوی

تکنیک های داده کاوی برای کاوش، تحلیل و شناسایی داده های پزشکی بوسیله ی الگوریتم ها پیچیده برای کشف الگوهای نامشخص استفاده شده است. محققان از تکنیک های داده کاوی برای شناسایی بسیاری از بیماری ها همچون بیماری های قلبی، سکته، دیابت و سرطان استفاده می کنند. بسیاری از تکنیک های داده کاوی برای شناسایی بیماری های قلبی با دقتی مناسب استفاده شده است. محققان از تکنیک های داده کاوی مختلفی مثل بیزی، شبکه عصبی، درخت تصمیم گیری، چگالی کرنل و ماشین بردار پشتیبانی برای پیش بینی و تشخیص بیماری های قلبی استفاده کرده اند. یکی از این سیستم ها از دسته بندی یادگیری عصبی برای دسته بندی وظیفه های داده کاوی و نشان داد که این سیستم دسته بندی عملکردی مشابه به سیستم دسته بندی نظارتی دارد. سیستم پیش بینی حمله قلب موثر و هوشمند (IEHPS) بر اساس شبکه های عصبی و داده کاوی ساخته شده است و استخراج الگوهای قابل توجه برای پیش بینی بیماری قلبی بوسیله خوشه بندی K ابزاری را در دستور کار قرار داد. این سیستم از الگوریتم MAFIA برای کاوش الگوهای فراوان استفاده می کند. پولاتت و همکاران، بوسیله فازی ترکیبی و رویکرد k نزدیک ترین همسایه، یک سیستم برای پیش بینی بیماری های قلبی طراحی کردند که 87 درصد در شناسایی دقت داشت. در یک سیستم دیگر، شبکه ی عصبی برای شناسایی بیماری های قلبی با دقت 89.01 درصد بکار گرفته شد. لاتا و سابرامایان در سال 2007 یک سیستم پیش بینی بیماری های قلبی بوسیله الگوریتم ژنتیک و CANFIS پیشنهاد کردند که خطای میانگین مربعات آن پایین بود. با تحلیل تکنیک های مطرح شده، این مقاله به معرفی یک سیستم جدید با استفاده از الگوریتم های ژنتیکی و شبکه عصبی برای پیش بینی خطر بیماری های قلب پرداخته است. الگوریتم ژنتیک برای بهینه سازی شبکه عصبی استفاده شده است. در این مقاله، برای اولین یک الگوریتم ترکیبی بر روی عوامل خطر برای بهبود دقت پیش بینی بیماری های قلبی استفاده شده است. در نتیجه، هدف اصلی در اینجا، استفاده از این سیستم در پشتیبانی تصمیم گیری درمانی به عنوان شاخص ریسک است تا افراد بتوانند این ریسک ها را بدون ابتلا به بیماری های قلبی در آینده کاهش دهند.این مقاله ادامه دارد........ترجمه  itrans.ir

الگوریتم های ژنتیکی

الگوریتم‌ های ژنتیک بر پایه نظریه تکامل است. آنها روند تکامل در ایجاد طرح های جدید را شبیه سازی می کنند. الگوریتم های ژنتیکی یاد می گیرند که چگونه بر اساس نتایج بدست آمده از ارزیابی طراحی های قبلی به سمت طرح بهتر حرکت کنند. از این رو الگوریتم های ژنتیک به هیچ دانش قبلی از فرآیند بهینه سازی نیاز ندارد.

برای شبیه سازی فرآیند تکامل، الگوریتم ژنتیک از سه روش به نام ادغام، جهش و انتخاب استفاده
می کند. طرح های بهتر با ترکیب ویژگی های موفق از طرح های موجود بدست می آیند.
در اصطلاحات GA ، یک نقطه طراحی، که توسط ترکیبی از متغیرهای طراحی در فضای طراحی تشکیل شده است، راه حل کاندید نامیده می شود. مجموعه ای از راه حل های کاندید، که ما فرآیند بهینه سازی را با آنها شروع می کنیم، نشان دهنده نسل اول هستند. مجموعه ای از راه حل های کاندید که در هر نسل تولید شده، جمعیت و تعداد راه حل های کاندید در هر نسل، اندازه جمعیت نامیده می شود. تعداد
طرح های محفوظ مشخص می کند که چه تعداد از بهترین طرح های موجود را می خواهیم به نسل بعد منتقل کنیم.
نسل اول (والد) ،با انتخاب راه حل های کاندید به طور تصادفی در فضای طراحی تولید می شود. مقادیر تابع هدف برای کل جمعیت ارزیابی و به الگوریتم ژنتیک ارائه شده است. با یادگیری از این نتایج، GA با نگه داشتن برخی از بهترین طرح های به دست آمده از نسل قبلی، به نسل بعدی (فرزند) می رسد و طرح های باقی مانده با استفاده از ادغام و جهش در طرح به دست آمده از نسل قبلی ،به دست می آیند . مقادیر تابع هدف برای طراحی های هر دو نسل به دست آمده است. توانایی یک راه حل کاندید برای بقا و ظهورپیدا کردن در نسل بعدی، سازواری یا توانایی زیستی نامیده می شود. راه حل های کاندید با سازواری بالا برای نسل های بسیاری وجود دارد. در اینجا تابع سازواری ، تابع هدف است. در مورد یک مسئله بهینه سازی چند هدفه، سازواری یک راه حل کاندید با تمامی توابع هدف مرتبط است. هنگامی که مقادیر سازواری شناخته شده است ما هر دو جمعیت والد و فرزند را با توجه به مقادیر سازواری آنها مرتب می کنیم. ما می توانیم طرح های که برای نسل بعدی باقی می مانند را به دو روش پیدا کنیم. در روش اول ما بدترین طرح از جمعیت فرزندان را با بهترین طرح در جمعیت والد جایگزین می کنیم و این روش را انتخاب نخبه گرا نامیده می شود. در روش دیگر ما هر دوجمعیت والد و فرزند را ترکیب کرده و آنها را با توجه به ارزش های سازواریشان مرتب می کنیم. طرح ها با بهترین ارزش سازواری انتخاب می شوند و این روش، روش انتخاب متعدد نخبه گرا نامیده می شود.
با استفاده از روش نخبه گرا یا انتخاب متعدد نخبه گرا ما تعدادی از طرح ها را که برابر با تعداد طرح های محفوظ هستند، انتخاب می کنیم. بقیه جمعیت در نسل جدید با استفاده از فرآیندهای ادغام و جهش به دست می آیند که در مورد آنها بحث می کنیم. ما احتمال کاربرد هر دو روش ادغام و جهش را در آغاز فرآیند بهینه سازی فراهم می کنیم. کاربرد ادغام و یا جهش با مقایسه احتمال آنها با مقدار احتمال یک تولید تصادفی تعیین می شود. اگر احتمال ادغام یا جهش کمتر از ارزش احتمال تولید به طور تصادفی آن باشد، پس آن اپراتور (ادغام / جهش) به کار برده می شود. اجازه دهید ما فرآیندهای ادغام و جهش را ببینیم.
ادغام: فرض کنید که ما دو طرح با شش متغیر طراحی داریم. برای رسیدن به طراحی نسل بعدی با استفاده از این دو طرح با روش ادغام، ما دو طرح والد را تقسیم می کنیم. نقطه تقسیم به صورت تصادفی انتخاب شده است. اجازه بدهید بگوییم که ما آنها را به دو نیمه تقسیم می کنیم. نسل های جدید با ترکیب یک بخش از هر یک از این دو طرح تولید می شوند.
مثال: اجازه دهید طرحَA 4، 2، 3، 3، 2، 1 و طراح B 3، 4، 2، 2، 2، 1، باشد به طوریکه در آن، اعداد، گزینه انتخاب شده برای هر متغیر طراحی را بیان می کنند (با فرض اینکه گزینه های مختلفی برای هر متغیر طراحی در دست هستند).
با تقسیم هر یک از این طرح ها به دو نیمه ما 4، 2، 3 - 3، 2، 1 و 3، 4، 2 - 2، 2، 1 را خواهیم داشت. برای رسیدن به طرح های جدید با استفاده از ادغام ما بخش های مختلف از طرح های موجود را ترکیب می کنیم. بدین ترتیب ما طرح های جدید 4، 2، 3، 2، 2، 1 و 3، 4، 2، 3، 2، 1 را بدست می آوریم.
در این فرایند ما طرح های موجود را ترکیب می کنیم و این کار ما را به بخشی از فضای طراحی، که در آن والد حظور دارد، محدود می کند. از این رو اگر ما تنها از ادغام استفاده کنیم، بسیار سریع به نقطه همگرایی می رسیم که یک نقطه همگرایی محلی است. ما به این نقطه بدون جستجو در بخش های دیگر فضای طراحی رسیدیم. این کار ما را از پیدا کردن طرح های بهتر موجود در مناطق دیگر بازمی دارد و همچنین از رسیدن به نقطه همگرایی جهانی جلوگیری می کند. برای رفتن به مناطق مختلف در فضای طراحی ما باید مطمئن شویم که متغیرهای طراحی در بخش های مختلف فضای طراحی انتخاب شده اند.
جهش: از جهش برای معرفی طرح هایی در سایر بخش های فضای طراحی استفاده می شود. جهش پس از ادغام و با احتمال کمتر استفاده می شود. در جهش نقطه کاربرد به صورت تصادفی انتخاب می شود و در آن نقطه مقدار متغیر طراحی به طور تصادفی ازبین گزینه های موجود انتخاب شده است.
در ادغام ما طرح های جدید را با ترکیب بخش های مختلف از طرح های موجود تولید می کنیم. در این فرایند ما تنها طرح هایی را می توانیم تولید کنیم که توسط مقادیر متغیر طراحی در طرح های موجودشکل گرفته اند و در دسترس هستند. ما نمی توانیم هیچ طرحی را با داشتن برخی متغیرهای دیگر طراحی تولید کنیم. به عنوان مثال، در بحث ادغام ما دیدیم که 4، 2، 3، 3، 2، 1 و 3، 4، 2، 2، 2، 1 می تواند طرح های 4، 2، 3، 2، 2، 1 و 3، 4، 2، 3، 2،1 را تولید کند. اما ما نمی توانیم طرحی به صورت 4، 2، 3، 2، 5،1 تولید کنیم. ما می توانیم با استفاده از جهش به این طرح برسیم.
مثال: اجازه دهید طراحی اولیه 4، 2، 3، 2، 2،1 باشد. اگر نقطه تصادفی کاربردی جهش 5 باشد پس ما طراحی با مقدار متغیر پنجم را از گزینه های موجود انتخاب میکنیم. اگر گزینه های موجود 1،2،3،4،5،6 باشند و اگر ما 5 را به عنوان گزینه تصادفی انتخاب کنیم ، طراحی جدید 4، 2، 3، 2، 5،1 خواهد بود. بنابراین جهش به ما اجازه می دهد تا در میان فضای طراحی حرکت کنیم و در نتیجه مانع از همگرایی زودرس می شود.
بنابراین ما به نسل جدیدی از طرح ها با استفاده از الگوریتم ژنتیک می رسیم. این ما را به طرح هایی که به صورت یک مرز غالب است،می رساند. روند محاسبه ارزش سازواری برای طرح ها، انتخاب و تولید جمعیت جدید از طرح ها، تکرار می شود تا زمانی که GA بتواند مرز غالب را بهبود بخشد و یا تا زمانی که به تعداد اولیه ای از نسل ها برسد. نتیجه نهایی مجموعه ای از طرح های در سطح جهانی غالب خواهد بود.(سیارک)