فاخته

now browsing by tag

 
 

موضوع مقاله - دانلود پژوهش

1 -4- فرضیات تحقیق ........................................................................................... 3
1 -5- اهمیت و ضرورت تحقیق ................................................................................ 3
1 -6- خلاصه فصل های آتی.................................................................................... 4
2- ادبیات و پیشینه تحقیق ............................................................................................ 5
2-1- مقدمه ...................................................................................................... 6
2-2- مرور ادبیات الگوریتم های فرا ابتکاری ................................................................... 6
2-3- جمع بندی ................................................................................................. 15
3- زمینه های علمی تحقیق .......................................................................................... 16
3-1- مقدمه ...................................................................................................... 17
3-2- مسائل بهینه سازی ........................................................................................ 17
3-3- بررسی روش‌های جستجو و بهینه‌سازی ................................................................. 18
3-3-1- روش‌های شمارشی ........................................................................... 19
3-3-2- روش‌های محاسباتی .......................................................................... 20
3-3-3- روش‌های ابتکاری و فرا ابتکاری ............................................................. 21
3-4- مسائل بهینه‌سازی ترکیبی ................................................................................. 21
3-5- روشهای حل مسائل بهینه‌سازی ترکیبی .................................................................. 23
3-5-1- روش های ابتکاری ........................................................................... 24
3-5-1-1- آزاد‌سازی ..................................................................... 24
3-5-1-2- تجزیه ......................................................................... 25
3-5-1-3- تکرار .......................................................................... 25
3-5-1-4- روش تولید ستون ............................................................ 25
3-5-1-5- جستجوی سازنده ............................................................ 26
3-5-1-6- جستجوی بهبود یافته ........................................................ 26
3-5-1-7- روش جستجوی همسایه ..................................................... 27
3-5-2- روش‌های فرا ابتکاری برگرفته از طبیعت ...................................................... 28
3-6- جمع بندی ................................................................................................. 29
4- ارائه الگوریتم جدید پیشنهادی ................................................................................... 30
4-1- مقدمه ...................................................................................................... 31
4-2- الگوریتم جستجوگر تکاملی............................... (Seeker Evolutionary Algorithm) 31
4-3- اعتبار سنجی الگوریتم جستجوگر تکاملی................................................................. 42
4-3-1- مسائل مورد استفاده برای ارزیابی الگوریتم پیشنهادی ........................................ 43
4-3-2- عملکرد الگوریتم جستجوگر تکاملی ......................................................... 55
4-3-3- مقایسه عملکرد الگوریتم جستجوگر تکاملی باICA, OICA , CICA3 ................ 65
4-3-4- مقایسه عملکرد الگوریتم جستجوگر تکاملی با RGA, PSO , GSA ................... 67
4-3-5- مقایسه عملکرد الگوریتم جستجوگر تکاملی با HS, IBA , ABS ....................... 68
4-3-6- مقایسه عملکرد الگوریتم جستجوگر تکاملی با BA, CS, LFA, FA ................... 70
4-4 فرایند تکاملی الگوریتم های فرا ابتکاری .................................................................. 72
4-5 جمع بندی .................................................................................................. 75
5- نتیجه گیری و پیشنهادها ......................................................................................... 76
5-1- نتیجه گیری ............................................................................................... 77
5-2- پیشنهادها ................................................................................................. 77
مراجع ................................................................................................................... 78
پیوست 1- کد MATLAB حلقه اصلی الگوریتم جستجوگر تکاملی ................................................ 82
پیوست 2- کد MATLAB حلقه فرعی الگوریتم جستجوگر تکاملی ................................................ 86

متن کامل در سایت امید فایل 

پیوست 3- کد MATLAB مسائل ریاضی استفاده شده ............................................................. 90
فهرست جداول
جدول 4-1 مقدار پارامتر های الگوریتم برای حل f Gol و f Six و f Bra ............................................ 63
جدول 4-2 مقدار شاخص های ارزیابی عملکرد الگوریتم برای حل f Gol و f Six و f Bra ......................... 65
جدول 4-3 نتایج مقایسه عملکرد الگوریتم جستجوگر تکاملی با ICA, OICA , CICA3 ..................... 66
جدول 4-4 مقادیر برخی از پارامتر های الگوریتم جستجوگر تکاملی ................................................. 66
جدول 4-5 نتایج مقایسه عملکرد الگوریتم جستجوگر تکاملی با RGA, PSO , GSA ........................ 67
جدول 4-6 مقادیر برخی از پارامتر های الگوریتم جستجوگر تکاملی ................................................. 68
جدول 4-7 نتایج مقایسه عملکرد الگوریتم جستجوگر تکاملی با ABC, IBA, HS ............................. 69
جدول 4-8 مقادیر برخی از پارامتر های الگوریتم جستجوگر تکاملی ................................................. 70
جدول 4-9 نتایج مقایسه عملکرد الگوریتم جستجوگر تکاملی با LFA, FA, CS, BA ........................... 71
جدول 4-10 مقادیر برخی از پارامتر های الگوریتم جستجوگر تکاملی ............................................... 72
فهرست شکل ها
شکل 3-1 طبقه‌بندی انواع روش‌های بهینه‌سازی ....................................................................... 19
شکل 4-1 فلوچارت الگوریتم جستجوگر تکاملی ...................................................................... 33
شکل 4-2 نحوه حرکت جستجو گرها در ناحیه جواب ................................................................ 34
شکل 4-3 حرکت جستجو گر به سمت بهترین جستجو گر ........................................................... 39
شکل 4-4 شبه کد حلقه اصلی الگوریتم جستجوگر تکاملی ........................................................... 41
شکل 4-5 شبه کد حلقه اصلی الگوریتم جستجوگر تکاملی ........................................................... 42
شکل 4-6 نمودار سه بعدی تابع F1 ................................................................................... 44
شکل 4-7 نمودار سه بعدی تابع Goldstein-Price ............................................................... 45
شکل 4-8 نمودار سه بعدی تابع Six-hump camel back ....................................................... 46
شکل 4-9 نمودار سه بعدی تابع Branins ........................................................................... 47
شکل 4-10 نمودار سه بعدی تابع Rosenbrock ................................................................... 48
شکل 4-11 نمودار سه بعدی تابع Sphere .......................................................................... 49
شکل 4-12 نمودار سه بعدی تابع Schwefel ....................................................................... 50
شکل 4-13 نمودار سه بعدی تابع Ackley .......................................................................... 51
شکل 4-14 نمودار سه بعدی تابع Rastrigin ....................................................................... 52
شکل 4-15 نمودار سه بعدی تابع Easom .......................................................................... 53
شکل 4-16 نمودار سه بعدی تابع Griewank ...................................................................... 54
شکل 4-17 موقعیت مکانی جستجوگرها قبل از عملیات جستجو در تکرار اول ...................................... 56
شکل 4-18 موقعیت مکانی جستجوگرها بعد از عملیات جستجو در تکرار اول ...................................... 56
شکل 4-19 موقعیت مکانی جستجوگرها قبل از عملیات جستجو در تکرار دوم ...................................... 57
شکل 4-20 موقعیت مکانی جستجوگرها بعد از عملیات جستجو در تکرار دوم ...................................... 57
شکل 4-21 موقعیت مکانی جستجوگرها قبل از عملیات جستجو در تکرار سوم ..................................... 58
شکل 4-22 موقعیت مکانی جستجوگرها بعد از عملیات جستجو در تکرار سوم ..................................... 58
شکل 4-23 موقعیت مکانی جستجوگر ها قبل از عملیات جستجو در تکرار چهارم .................................. 59
شکل 4-24 موقعیت مکانی جستجوگر ها بعد از عملیات جستجو در تکرار چهارم .................................. 59
شکل 4-25 موقعیت مکانی جستجوگرها قبل از عملیات جستجو در تکرار پنجم ..................................... 60
شکل 4-26 موقعیت مکانی جستجوگرها بعد از عملیات جستجو در تکرار پنجم ..................................... 60
شکل 4-27 عملکرد الگوریتم جستجوگر تکاملی برای تابع F1 ........................................................ 62
شکل 4-28 عملکرد الگوریتم جستجوگر تکاملی برای تابع Six-hump camel back ........................... 63
شکل 4-29 عملکرد الگوریتم جستجوگر تکاملی برای تابع Branins ................................................ 64
شکل 4-30 عملکرد الگوریتم جستجوگر تکاملی برای تابع Goldstein-Price .................................... 64
شکل 4-31 نمایش سه بعدی حراررتی تابع F2 از نمای بالا.......................................................... 74
شکل 4-32 نمایش سه بعدی حراررتی تابع F2 ....................................................................... 74
شکل 4-33 نمایش سه بعدی حراررتی تابع F2 و نقطه بهینه این تابع ............................................... 75
فصل اول
کلیات تحقیق
1-1- مقدمه
در ریاضیات و علوم رایانه یک مسأله بهینه سازی، مسأله یافتن بهترین راه حل از میان همه راه حل های عملی می باشد. مسأله های بهینه سازی می تواند به دو دسته تقسیم شود که متغیرها پیوسته یا گسسته باشند. روش های حل متفاوتی برای این گونه مسائل وجود دارند که به سه دسته روش های سنتی ریاضی، روش های ابتکاری و روش های فرا ابتکاری تقسیم می شوند. در اکثر مسائل بهینه سازی با افزایش ابعاد مساله زمان حل آن نیز به صورت نمایی افزایش پیدا می کند. به این گونه مسائل، مسائل بهینه سازی ترکیبیاتی گفته می شود. به همین علت یکی از بهترین گزینه های برای حل مسائل بهینه سازی استفاده از الگوریتم های فرا ابتکاری است. مهمترین علت استفاده از الگوریتم های فرا ابتکاری، بدست آوردن یک جواب مناسب در زمان مناسب است. از همین رو است که توسعه و میزان استفاده از الگوریتم های فرا ابتکاری به شدت رشد داشته است.
1-2- تعریف مساله
هدف از بهینه‌سازی یافتن بهترین جواب قابل قبول با توجه به محدودیت‌ها و نیازهای مسأله است. بهینه‌سازی یک فعالیت مهم و تعیین‌کننده در بسیاری ار زمینه های علمی، اقتصادی، صنعتی و غیره است. بسیاری از مسائل بهینه‌سازی در مهندسی، طبیعتاً پیچیده‌تر و مشکل‌تر از آن هستند که با روش‌های مرسوم بهینه ‌سازی نظیر روش های برنامه‌ریزی ریاضی و نظایر آن قابل حل باشند. از جمله راه ‌حل‌های موجود در برخورد با این گونه مسائل، استفاده از الگوریتم‌های تکاملی است. دلیل دیگر استفاده از الگوریتم های تکاملی، زمان بسیار زیاد و غیر ممکن روش های دقیق ریاضی برای حل مسائلی با پارامتر های زیاد و پیچیده است. در سال‌های اخیر یکی از مهمترین و امیدبخش‌ترین تحقیقات، «روش‌های ابتکاری برگرفته از طبیعت» بوده است. این روش‌ها شباهت‌هایی با سیستم‌های اجتماعی و یا طبیعی دارند. ساختار ‌آنها برگرفته شده از روند تکاملی موجود در آن سیستم می باشد که در حل مسائل با ساختار پیچیده نتایج بسیار خوبی داشته است. در اکثر این گونه الگوریتم ها عملیات جستجو با تولید یک جمعیت تصادفی در ناحیه جستجو شروع می شود. سپس با استفاده هوش محاسباتی موجود در الگوریتم، جواب ها حرکت داده می شوند. این جابجایی به نحوی می باشد که بعد از گذشتن چند گام جمعیت به سمت نقطه بهینه همگرا می شوند. تفاوت اصلی الگوریتم های تکاملی در همین نحوه جابجایی جمعیت می باشد. در سال های اخیر توسعه و استفاده از الگوریتم های تکاملی رشد چشم گیری داشته است. هر یک از آن ها دارای نقاط ضعف و قوتی بوده است به طوری که هر از چند گاهی شاهد معرفی الگوریتمی جدید هستیم که برتری خود را نسبت به تعدادی از الگوریتم های قبلی نشان می دهد.
در این پایاننامه، یک الگوریتم جدید برای حل مسائل بهینه سازی پیوسته معرفی شده است. این الگوریتم مبتنی بر یک منطق ساده جستجو است. برای ارزیابی عملکرد الگوریتم های فرا ابتکاری از مسائل ریاضی موجود در ادبیات استفاده می شود. برای این الگویتم نیز از 11 مساله ریاضی برای مقایسه و ارزیابی عملکرد الگوریتم پیشنهادی استفاده شده است. در این مقایسات نتایج الگوریتم پیشنهادی با نتایج یازده الگوریتم فرا ابتکاری مقایسه شده است. این الگوریتم ها جزء پر رجوع ترین الگوریتم های فرا ابتکاری در این زمینه هستند.
1-3- هدف تحقیق
هدف از این پایان نامه معرفی یک الگوریتم فراابتکاری کارا برای حل مسائل بهینه سازی پیوسته است که بتواند نسبت به اغلب الگوریتم های فراابتکاری مشهور دارای برتری باشد.
1-4- فرضیات تحقیق
در این پایان نامه، فرضیات مسأله وجود ندارد و طراحی الگوریتم تکاملی جستجوگر فقط برای مسائل بهینه سازی پیوسته صورت میگیرد.
1-5- اهمیت و ضرورت تحقیق
گستره استفاده از الگوریتم های فراابتکاری در علوم مختلف به خصوص مهندسی صنایع در طی سال های گذشته بسیار زیاد بوده است. تعداد ارجاعات به مقالات اصلی این الگوریتم ها خود گواه این امر است. در ادامه به تعدادی از این موارد اشاره می شود.
الگوریتم تجمعی ذرات (1995) - 19927 ارجاع
الگوریتم هارمونی (2001) - 866 ارجاع
الگوریتم زنبور عسل (2007) - 590 ارجاع
الگوریتم فرهنگ (1994) - 517 ارجاع
الگوریتم رقابت استعماری (2007) - 195 ارجاع
الگوریتم گرانشی (2009) - 188 ارجاع
تعداد ارجاعات بسیار زیاد به مقالات الگوریتم های فراابتکاری نشان دهنده اهمیت فراوان این روش ها است. روش حل یا پدیده علمی که وسعت استفاده از آنها به این شکل باشد بسیار اندک است.
1-6- خلاصه فصل های آتی
در فصل دوم به مرور ادبیات الگوریتم های فرا ابتکاری پرداخته خواهد شد. الگوریتم هایی که در این فصل مرور می شود شامل الگوریتم ژنتیک، الگوریتم آنیلینگ شبیه‌سازی، الگوریتم ایمنی مصنوعی، الگوریتم جستجوی ممنوعه، الگوریتم بهینه‌سازی کلونی مورچه، الگوریتم اجتماع ذرات، تکامل تفاضلی، الگوریتم جستجوی هارمونی، جستجوی فاخته، الگوریتم دسته‌ی ماهی‌های مصنوعی، الگوریتم کرم شب تاب، الگوریتم خفاش، الگوریتم جستجوی گرانشی، الگوریتم کلونی زنبور عسل، الگوریتم رقابت استعماری، الگوریتم بهینه سازی فاخته است.
در فصل سوم به زمینه های علمی تحقیق پرداخته می شود. در این فصل روش های مختلف جستجو و بهینه سازی مورد بحث قرار می گیرد. مسائل بهینه سازی ترکیبیاتی و روش های حل آن شرح داده می شود.
در فصل چهارم ساختار الگوریتم جستجوگر تکاملی شرح داده خواهد شد و سپس با استفاده از چندین مساله ریاضی عملکرد آن با معروف ترین الگوریتم های فرا ابتکاری مورد مقایسه قرار خواهد گرفت.
فصل پنجم مربوط به نتیجه گیری و پیشنهادات آتی تحقیق خواهد بود.
فصل دوم
ادبیات و پیشینه تحقیق
2-1- مقدمه
در سالهای دهه 1950 برنامه نویسی کامپیوترهای اولیه توسط تغییر سیم ها و تنظیم هزاران کلید و سوییچ انجام می شد. بعد از آن افراد به دنبال ابزارهای سریع تر و راحت تری برای برنامه نویسی بودند. در اواخر دهه 1950 مفسرهای زبان های طبیعی و کامپایلرهای پا به عرصه ظهور گذاشتند. در این سال ها بود که زبان های برنامه نویسی به منظور استفاده در دنیای نرم افزارهای تجاری عرضه شدند. این امر باعث شد تا آشنایی با زبان های برنامه نویسی به صورت عام در بین متخصصان رواج پیدا کند. بعد از این رویداد مهم اکثر دانشمندان در زمینه های مختلف علمی سعی کردند از زبان برنامه نویسی استفاده کنند. یکی از موارد استفاده از زبان های برنامه نویسی، علم ریاضی و انجام محاسبات ریاضی بود. زمان حل بسیار کمتر این روش نسبت به حل دستی باعث شد تا سرعت استفاده از برنامه نویسی در شاخه های مختلف ریاضی یه شدت رشد کند. در دهه 1970 برای اولین بار دانشمندان برای حل مسائل بهینه سازی ترکیبیاتی از الگوریتم های فرا ابتکاری استفاده کردند. آن ها برای پیاده سازی الگوریتم ها از زبان برنامه نویسی استفاده کردند. نتیجه این کار بدست آمدن جواب های مناسب در زمان مناسب برای مسائل بهینه سازی ترکیبیاتی با اندازه بزرگ بود. تا آن زمان برای این گونه مسائل به دلیل زمان حل بسیار زیاد جواب مناسبی یافت نشده بود.
2-2- مرور ادبیات الگوریتم های فرا ابتکاری
در دهه هفتاد میلادی دانشمندی از دانشگاه میشیگان به نام جان هلند ایده استفاده از الگوریتم ژنتیک را در بهینه‌سازی‌های مهندسی مطرح کرد. ایده اساسی این الگوریتم انتقال خصوصیات موروثی توسط ژن‌هاست. الگوریتم ژنتیک نوع خاصی از الگوریتم های تکاملی است که از تکنیک های زیست‌شناسی فراگشتی مانند وراثت و جهش استفاده می‌کند. در واقع الگوریتم های ژنتیک از اصول انتخاب طبیعی داروین برای یافتن فرمول بهینه جهت پیش‌بینی یا تطبیق الگو استفاده می کنند. الگوریتم های ژنتیک اغلب گزینه خوبی برای تکنیک‌های پیش‌بینی بر مبنای رگرسیون هستند. مختصراً گفته می‌شود که الگوریتم ژنتیک یک تکنیک برنامه‌نویسی است که از تکامل ژنتیکی به عنوان یک الگوی حل مسئله استفاده می‌کند. در طبیعت، فرایند تکامل هنگامی ایجاد می‌شود که چهار شرط زیر برقرار باشد:
الف) یک موجود توانایی تکثیر داشته باشد (قابلیت تولید مثل).
ب) جمعیتی از این موجودات قابل تکثیر وجود داشته باشد.
پ) چنین وضعیتی دارای تنوع باشد.
ت) این موجودات به وسیله قابلیت‌هایی در زندگی از هم جدا شوند.
در طبیعت، گونه‌های متفاوتی از یک موجود وجود دارند که این تفاوت‌ها در کروموزوم‌های این موجودات ظاهر می‌شود و باعث تنوع در ساختار و رفتار این موجودات می‌شود.
این تنوع ساختار و رفتار به نوبه خود بر زاد و ولد تأثیر می‌گذارد. موجوداتی که قابلیت‌ها و توانایی بیشتری برای انجام فعالیت‌ها در محیط دارند (موجودات متکامل‌تر)، دارای نرخ زاد و ولد بالاتری خواهند بود و طبعاً موجوداتی که سازگاری کمتری با محیط دارند، از نرخ زاد و ولد پایین‌تری برخوردار خواهند بود. بعد از چند دوره زمانی و گذشت چند نسل، جمعیت تمایل دارد که موجوداتی را بیشتر در خود داشته باشد که کروموزوم‌هایشان با محیط اطراف سازگاری بیشتری دارد. در طی زمان، ساختار افراد جامعه به علت انتخاب طبیعی تغییر می‌کند و این نشانه تکامل جمعیت است [1,2,3] .
الگوریتم آنیلینگ شبیه‌سازی شده توسط متروپولیس و همکاران در سال 1953 پیشنهاد شده و جهت بهینه‌سازی در سال 1983 مورد بازبینی قرار گرفته است. این روش در مسائل تاکسی تلفنی کاربرد دارد.
الگوریتم آنیلینگ شبیه‌سازی شده در شکل عمومی، بر اساس شباهت میان سرد شدن جامدات مذاب و حل مسائل بهینه‌سازی ترکیبی به وجود آمده است. در فیزیک مواد فشرده، گرم و سرد کردن فرایندی است فیزیکی که طی آن یک ماده جامد در ظرفی حرارت داده می‌شود تا مایع شود؛ سپس حرارت آن بتدریج کاهش می‌یابد. بدین ترتیب تمام ذرات فرصت می‌یابند تا خود را در پایین‌ترین سطح انرژی منظم کنند. چنین وضعی در شرایطی ایجاد می‌شود که گرمادهی کافی بوده و سرد کردن نیز به آهستگی صورت گیرد. جواب حاصل از الگوریتم گرم و سرد کردن شبیه‌سازی شده، به جواب اولیه وابسته نیست و می‌توان توسط آن جوابی نزدیک به جواب بهینه به دست آورد. حد بالایی زمان اجرای الگوریتم نیز قابل تعیین است. بنابراین الگوریتم گرم و سرد کردن شبیه‌سازی شده، الگوریتمی است تکراری که اشکالات روش‌های عمومی مبتنی بر تکرار را ندارد.
در روش آنیلینگ شبیه‌سازی شده، به صورت پی در پی از جواب جاری به یکی از همسایه‌های آن انتقال صورت می‌گیرد. این سازوکار توسط زنجیره مارکوف به صورت ریاضی قابل توصیف است. در این روش، یک مجموعه آزمون انجام می‌گیرد؛ این آزمون‌ها به نحوی است که نتیجه هر یک به نتیجه آزمون قبل وابسته است. در روش آنیلینگ شبیه‌سازی شده، منظور از یک آزمون، انتقال به نقطه جدید است و روشن است که نتیجه انتقال به نقطه جدید تنها وابسته به مشخصات جواب جاری است.
روش جستجوی همسایه و روش آنیلینگ شبیه‌سازی شده، هر دو روش‌های تکراری هستند. در الگوریتم آنیلینگ شبیه‌سازی شده، هر بار که شاخص کنترل‌کننده به مقدار نهایی خود می‌رسد، در حقیقت یک عملیات تکراری انجام شده است. در الگوریتم جستجوی همسایه، هنگامی که تعداد تکرارها به سمت بی‌نهایت میل می‌کند، روش به جواب بهینه نزدیک می‌شود. اما عملکرد الگوریتم آنیلینگ شبیه‌سازی شده سریع‌تر است [4] .
دیکاسترو و تیمیس، اولین الگوریتم های ایمنی مصنوعی را در سال 1986 طراحی کردند. به طور کلی، سیستم‌های ایمنی مصنوعی جزء الگوریتم های الهام گرفته شده از بیولوژی هستند. این نوع الگوریتم‌ها، الگوریتم هایی کامپیوتری هستند که اصول و ویژگی‌های آنها نتیجه بررسی در خواص وفقی و مقاومت نمونه‌ها بیولوژیکی است. سیستم ایمنی مصنوعی نوعی الگو برای یادگیری ماشین است. یادگیری ماشین، توانایی کامپیوتر برای انجام یک کار با یادگیری داده‌ها یا از روی تجربه است. سیستم ایمنی مصنوعی توسط کاسترو به این صورت تعریف شده است:
سیستم های وفقی که با الهام از ایمونولوژی نظری و توابع، اصول و مدل های ایمنی سیستم بدن انسان مشاهده شده به وجود آمده‌اند و برای حل مسائل مورد استفاده قرار می‌گیرند [5] .
الگوریتم جستجوی ممنوعه برای اولین بار در سال 1986 توسط گلووِر معرفی شد. روش جستجوی ممنوع همانند روش آنیلینگ شبیه‌سازی شده بر اساس جستجوی همسایه بنا شده است. در این روش عملکرد حافظه انسان شبیه‌سازی شده است. حافظه انسان با به کارگیری ساختمانی مؤثر و در عین حال ساده از اطلاعات، آنچه را در قبل رؤیت شده، ذخیره می‌کند. این مرکز همچنین فهرستی از حرکات منع شده را تنظیم می‌کند و این فهرست همواره بر اساس آخرین جستجوها منظم می‌شود. این روش از انجام هر گونه عملیات مجدد و تکراری جلوگیری می‌کند.
شکل نوین جستجوی ممنوع توسط گلوور مطرح شده است. روش جستجوی مبتنی بر منع، با ایجاد تغییری کوچک در روش جستجوی همسایه به وجود می‌آید. هدف این روش آن است که بخش‌هایی از مجموعه جواب که پیش از این بررسی نشده است، مد نظر قرار گیرد. بدین منظور حرکت به جواب‌هایی که اخیراً جستجو شده، ممنوع خواهد بود.
ساختار کلی روش جستجوی ممنوع بدین صورت است که ابتدا یک جواب اولیه امکان‌پذیر انتخاب می‌شود؛ سپس برای جواب مربوط، بر اساس یک معیار خاص مجموعه‌ای از جواب‌های همسایه امکان‌پذیر در نظر گرفته می‌شود.
در گام بعد، پس از ارزیابی جواب‌های همسایه تعیین شده، بهترین آنها انتخاب می‌شود و جابه‌جایی از جواب جاری به جواب همسایه انتخابی صورت می‌گیرد. این فرایند به همین ترتیب تکرار می‌شود تا زمانی که شرط خاتمه تحقق یابد.
در روش جستجوی ممنوع، فهرستی وجود دارد که جابه‌جایی‌های منع شده را نگهداری می‌کند و به فهرست تابو معروف است و کاربرد اصلی آن، پرهیز از همگرا شدن به جواب‌های بهینه محلی است. به عبارت دیگر، به کمک فهرست تابو جابه‌جایی به جواب‌هایی که اخیراً جستجو شده‌اند، ممنوع خواهد شد. فقط بخش‌هایی از مجموعه جواب که پیش از این مورد بررسی قرار نگرفته، مد نظر خواهند بود. در واقع جابه‌جایی از جواب جاری به جواب همسایه امکان‌پذیر زمانی انجام می‌شود که در فهرست تابو قرار نداشته باشد. در غیر این صورت، جواب همسایه دیگری که در ارزیابی جواب‌های همسایه در رده بعدی قرار گرفته است، انتخاب شده و جابه‌جایی به آن صورت می‌گیرد.
در روش جستجوی ممنوع بعد از هر جابه‌جایی، فهرست تابو بهنگام می‌شود، به نحوی که جابه‌جایی جدید به آن فهرست اضافه شده و جابه‌جایی که تا n تکرار مشخص در فهرست بوده است، از آن حذف می‌شود. نحوه انتخاب می‌تواند با توجه به شرایط و نوع مسأله متفاوت باشد .[6]
الگوریتم بهینه‌سازی کلونی مورچه‌ها در سال 1991 توسط دوریگو و همکاران پیشنهاد شده است که در حل مسأله فروشنده دوره‌گرد و مسائل تخصیص چندوجهی کاربرد دارد. الگوریتم بهینه ‌سازی کلونی مورچه‌ها از عامل‌های ساده‌ای که مورچه نامیده می‌شوند، استفاده می‌کند تا به صورت تکراری جواب‌هایی تولید کند. مورچه‌ها می توانند کوتاه‌ترین مسیر از یک منبع غذایی به لانه را با بهره‌گیری از اطلاعات فرمونی پیدا کنند. مورچه‌ها در هنگام راه رفتن، روی زمین فرمون می‌ریزند و با بو کشیدن فرمون ریخته شده بر روی زمین راه را دنبال می‌کنند؛ چنانچه در طی مسیر به سوی لانه به یک دوراهی برسند، از آن جایی که هیچ اطلاعی درباره راه بهتر ندارند، راه را به تصادف برمی‌گزینند. انتظار می‌رود به طور متوسط نیمی از مورچه‌ها مسیر اول و نیمی دیگر مسیر دوم را انتخاب کنند.
فرض می‌شود که تمام مورچه‌ها با سرعت یکسان مسیر را طی کنند. از آنجا که یک مسیر کوتاه‌تر از مسیر دیگر است، مورچه‌های بیشتری از آن می‌گذرند و فرمون بیشتری بر روی آن انباشته می‌شود. بعد از مدت کوتاهی مقدار فرمون روی دو مسیر به اندازه‌ای می رسد که روی تصمیم مورچه‌های جدید برای انتخاب مسیر بهتر تأثیر می‌گذارد. از این به بعد، مورچه‌های جدید با احتمال بیشتری ترجیح می‌دهند از مسیر کوتاه‌تر استفاده کنند، زیرا در نقطه تصمیم‌گیری مقدار فرمون بیشتری در مسیر کوتاه‌تر مشاهده می‌کنند. بعد از مدت کوتاهی تمام مورچه‌ها این مسیر را انتخاب خواهند کرد .[7]
الگوریتم اجتماع ذرات که به آن الگوریتم پرندگان نیز گفته می شود برای اولین بار توسط کندی و ابرهارت در سال 1995 مطرح شد. این الگوریتم محاسبه ای تکاملی الهام گرفته از طبیعت و براساس تکرار می‌باشد. منبع الهام این الگوریتم، رفتار اجتماعی حیوانات، همانند حرکت دسته جمعی پرندگان و ماهی‌ها بود. الگوریتم اجتماع ذرات نیز با یک ماتریس جمعیت تصادفی اولیه، شروع می‌شود. الگوریتم اجتماع ذرات از تعداد مشخصی از ذرات تشکیل می شود که به طور تصادفی، مقدار اولیه می گیرند. برای هر ذره دو مقدار وضعیت و سرعت، تعریف می شود که به ترتیب با یک بردار مکان و یک بردار سرعت، مدل می‌شوند. این ذرات، بصورت تکرارشونده ای در فضای n‌بعدی مسئله حرکت می کنند تا با محاسبه مقدار بهینگی به عنوان یک ملاک سنجش، گزینه‌های ممکن جدید را جستجو کنند.[8,9]
تکامل تفاضلی یک روش جست و جوی احتمالی بر پایه جمعیت است که در سال 1995 توسط ستورن و پرایس ابداع گردید. تفاضل تکاملی در حالی که تشابهاتی با سایر الگوریتم های تکاملی دارد اما استفاده از اطلاعات فاصله و جهت از جمعیت فعلی برای پیش بردن عملیات جست و جو آن را از سایر الگوریتم های تکاملی متمایز کرده است. الگوریتم تکامل تفاضلی اولیه برای مسائل فضای پیوسته به وجود آمدند ولی در ادامه برای مسائل فضای گسسته نیز تعمیم یافتند .[10]
الگوریتم جستجوی هارمونی توسط گیم و همکاران در سال 2001 معرفی شد. بعد ها در سال 2007 این الگوریتم توسعه داده شد. این الگوریتم با الهام از نحوه شکل گیری و چگونگی عملکرد یک ارکستر موسیقی به دنبال راه حل بهینه و یا به عبارت ملموس تر، بهترین هماهنگی بین اجزا دخیل در راهبری یک پروسه است. همان طور که نوازنده ها در یک ارکستر قطعات موسیقایی را می نوازند تا از بین آنها بهترین ترکیب، محصول نهایی را پدید آورد الگوریتم هارمونی نیز از بررسی نتیجه عملکرد اجزا به دنبال هماهنگی مطلوب است . الگوریتم هارمونی برای حل مسائل به دنبال یافتن بهترین مسیر است تا بوسیله آن هزینه توابع محاسباتی را کاهش دهد (کوتاهتر) نماید.[11]
روش جستجوی فاخته در سال 2009 توسط یانگ  و دب پیشنهاد شده است. این الگوریتم یک روش بهینه‌سازی فرااکتشافی است که رویکردی تکاملی در جستجوی راه‌حل بهینه دارد. این روش از رفتار جالب توجه گونه‌هایی از پرنده‌ی فاخته در پرورش تخم الهام گرفته است و آن را با پرواز لووی که نوعی گشت تصادفی است ترکیب می‌کند. برخی از گونه‌های فاخته به جای ساختن لانه، تخم‌های خود را در لانه‌ی پرنده‌ای از گونه‌های دیگر می‌گذارند و آن‌ها را با تقلید از شکل تخم‌ها و جوجه‌های پرنده‌ی میزبان وادار به مشارکت در بقای نسل خود می کنند.[12]
الگوریتم کرم شب تاب در سال 2009 توسط یانگ معرفی شد. دو کاربرد اساسی  پرتوتابی حشره های شب تاب جفت‌یابی و جذب طعمه است. به علاوه، پرتوتابی ممکن است به صورت مکانیزم هشداری برای محافظت‌ به کار رود. پرتوتابی ریتمیک، نرخ چشمک ها و مدت هر یک از آن ها، سیستم ارتباط جفت‌ها با یکدیگر را شکل می دهد. ماده‌ها به الگوی یکسان نرها در گونه‌های یکسان پاسخ می دهند، در حالی که در تعدادی از گونه‌ها حشره های شب‌تاب ماده می توانند الگوی تابشی جفت‌های گونه‌های دیگر را نیز تقلید کنند و با فریب حشره های شب‌تاب نر که ممکن است اشتباه کنند، آن‌ها را به سمت خود جذب و شکار کنند. شدت تابش نور می تواند به طریقی فرموله شود که با تابع هدف در ارتباط باشد و بدین صورت مقدار این تابع بهینه شود.[13,14]
الگوریتم خفاش نیز در سال 2010 توسط یانگ معرفی شد. این الگوریتم بر مبنای زندگی خفاش ها توسعه داده شده است.[15]
الگوریتم جستجوی گرانشی در سال 2009 توسط راشدی و همکاران معرفی شده است. این الگوریتم که با الهام از قانون گرانش طبیعت، پیشنهاد شده است یک روش جدید از دسته الگوریتم های جستجو ابتکاری میباشد. در این روش عامل های جستجو، اجرامی هستند که با توجه به نیروی جاذبه ای که از سایر اجرام به آنها وارد می شود، درکی از فضای جستجو پیدا می کنند و با توجه به این درک به جستجوی فضای اطراف خود می گردند .[16]
الگوریتم کلونی زنبور عسل در سال 2007 توسط کارابوگ و باشتورگ معرفی شده است. الگوریتم زنبور عسل هر نقطه را در فضای پارامتری، متشکل از پاسخ‌های ممکن به عنوان منبع غذا تحت بررسی قرار می دهد. زنبورهای دیده‌بان، کارگزاران شبیه‌سازی شده، به صورت تصادفی فضای پاسخها را ساده می کنند و به وسیلهی تابع شایستگی کیفیت موقعیتهای بازدید شده را گزارش می دهند. جواب‌های ساده شده رتبه بندی می‌شوند و دیگر زنبورها نیروهای تازهای هستند که فضای پاسخ‌ها را در پیرامون خود برای یافتن بالاترین رتبه محل‌ها جستجو می کنند که گلزار نامیده می‌شود. الگوریتم به صورت گزینشی دیگر گلزارها را برای یافتن نقطهی بیشینهی تابع شایستگی جستجو می‌کند.[17,18]
الگوریتم رقابت استعماری در سال 2007 توسط اتش پز و همکاران معرفی شده است. روشی در حوزه محاسبات تکاملی است که به یافتن پاسخ بهینه مسائل مختلف بهینه سازی می‌پردازد. این الگوریتم با مدلسازی ریاضی فرایند تکامل اجتماعی، سیاسی، الگوریتمی برای حل مسائل ریاضی بهینه سازی ارائه می دهد. الگوریتم رقابت استعماری نیز مجموعه اولیه ای از جوابهای احتمالی را تشکیل می دهد. الگوریتم رقابت استعماری با روند خاصی جوابهای اولیه (کشور ها) را به تدریج بهبود داده و در نهایت جواب مناسب مسئله بهینه سازی (کشور مطلوب) را در اختیار می گذارد. پایه‌های اصلی این الگوریتم را سیاست همسان سازی، رقابت استعماری و انقلاب تشکیل می دهند. این الگوریتم با تقلید از روند تکامل اجتماعی، اقتصادی و سیاسی کشورها و با مدلسازی ریاضی بخشهایی از این فرایند، عملگرهایی را در قالب منظم به صورت الگوریتم ارائه می دهد که می توانند به حل مسائل پیچیده بهینه سازی کمک کنند. در واقع این الگوریتم جوابهای مسئله بهینه سازی را در قالب کشورها نگریسته و سعی می‌کند در طی فرایندی تکرار شونده این جواب‌ها را رفته رفته بهبود داده و در نهایت به جواب بهینه مسئله برساند.[19,20,21]
الگوریتم بهینه سازی فاخته در سال 2011 توسط رجبیون معرفی شده است. همانند سایر الگوریتمهای تکاملی این الگوریتم هم با یک جمعیت اولیه کار خود را شروع می کند. این جمعیت از فاخته ها، تعدادی تخم دارند که آنها را در لانه تعدادی پرنده ی میزبان خواهند گذاشت. تعدادی از این تخم ها که شباهت بیشتری به تخم های پرنده میزبان دارند شانس بیشتری برای رشد و تبدیل شدن به فاخته بالغ خواهند داشت. سایر تخم ها توسط پرنده میزبان شناسایی شده و از بین می روند. میزان تخم های رشد کرده مناسب بودن لانه های آن منطقه را نشان می دهند. موقعیتی که در آن بیشترین تعداد تخمها نجات یابند پارامتری خواهد بود که الگوریتم قصد بهینه سازی آن را دارد. فاخته ها برای بیشینه کردن نجات تخم های خود دنبال بهترین منطقه می گردند. پس از آنکه جوجه ها از تخم در آمدند و تبدیل به فاخته بالغ شدند، جوامع و گروه هایی تشکیل می دهند. هر گروه منطقه سکونت خود را برای زیست دارد. تمام گروهها به سمت بهترین منطقه موجود فعلی مهاجرت می کنند. هر گروه در منطقه ای نزدیک بهترین موقعیت فعلی ساکن می شود. با در نظر گرفتن تعداد تخمی که هر فاخته خواهد گذاشت و همچنین فاصله فاخته ها از منطقه بهینه فعلی برای سکونت تعدادی شعاع تخم گذاری محاسبه شده و شکل می گیرد. سپس فاخته ها شروع به تخم گذاری تصادفی در لانه هایی داخل شعاع تخم گذاری خود می کنند. این پروسه تا رسیدن به بهترین محل برای تخم گذاری  (منطقه با بیشترین سود) ادامه می یابد. این محل بهینه جایی است که بیشترین تعداد فاخته ها در آن گرد می آیند.[22]
الگوریتم دسته‌ی ماهی‌های مصنوعی یکی از الگوریتم‌های هوش جمعی است که بر اساس جمعیت و جستجوی تصادفی کار می‌کند. این الگوریتم در سال 2003 توسط لی ارائه گردید. اساس کار این الگوریتم از روی رفتارهای اجتماعی ماهی‌ها برگرفته شده و بر مبنای جستجوی تصادفی، جمعیت و رفتارگرایی کار می‌کند. این الگوریتم دارای خصوصیاتی از جمله سرعت همگرایی بالا، حساس نبودن به مقادیر اولیه‌ی ماهی‌های مصنوعی، انعطاف‌پذیری و تحمل‌پذیری خطا می باشد که آن را برای حل مسائل بهینه‌سازی قابل قبول می‌کند. اساس کار این الگوریتم بر پایه‌ی توابعی است که از رفتارهای اجتماعی دسته‌ی ماهی‌ها در طبیعت برگرفته شده‌اند. در دنیای زیر آب، ماهی‌ها می توانند مناطقی را پیدا کنند که دارای غذای بیشتری است، که این امر با جستجوی فردی یا گروهی ماهی‌ها محقق می‌شود. مطابق با این ویژگی، مدل ماهی مصنوعی با رفتارهای حرکت آزادانه، جستجوی غذا، حرکت گروهی و دنباله‌روی ارائه شده است که به وسیله‌ی آنها فضای مسئله جستجو می‌شود.[23]
2-3- جمع بندی
در این فصل به مرور الگوریتم های فرا ابتکاری پرداخته شد. اکثر الگوریتم ها در مرحله اول خود جمعیت تصادفی تولید می کنند. سپس در تکرار های بعد آن جمعیت اولیه را حرکت می دهند. تفاوت الگوریتم ها در همین نوع حرکت دادن جواب ها است. در الگوریتم ژنتیک به وسیله اپراتور های تقاطع و جهش، در الگوریتم جستجوی ممنوعه به وسیله جستجوی تپه نوردی و لیست ممنوعه، در الگوریتم شبیه سازی تبرید به وسیله جستجوی تبه نوردی و تابع احتمالی بولتزمان و برای الگوریتم های دیگر به روش های گوناگون این عمل صورت می گیرد. در انتها نیز همین حرکت هدایت شده جواب ها باعث پیدا شدن جواب بهتر می شود.
فصل سوم
زمینه های علمی تحقیق
3-1- مقدمه
بهینه‌سازی یک فعالیت مهم و تعیین‌کننده در طراحی ساختاری است. طراحان زمانی قادر خواهند بود طرح‌های بهتری تولید کنند که بتوانند با روش‌های بهینه‌سازی در صرف زمان و هزینه طراحی صرفه‌جویی نمایند. بسیاری از مسائل بهینه‌سازی در مهندسی، طبیعتاً پیچیده‌تر و مشکل‌تر از آن هستند که با روش‌های مرسوم بهینه‌سازی نظیر روش برنامه‌ریزی ریاضی و نظایر آن قابل حل باشند.
3-2- مسائل بهینه سازی
هدف از بهینه‌سازی یافتن بهترین جواب قابل قبول، با توجه به محدودیت‌ها و نیازهای مسأله است. برای یک مسأله، ممکن است جواب‌های مختلفی موجود باشد که برای مقایسه آنها و انتخاب جواب بهینه، تابعی به نام تابع هدف تعریف می‌شود. انتخاب این تابع به طبیعت مسأله وابسته است. به عنوان مثال، زمان سفر یا هزینه از جمله اهداف رایج بهینه‌سازی شبکه‌های حمل و نقل می‌باشد. به هر حال، انتخاب تابع هدف مناسب یکی از مهمترین گام‌های بهینه‌سازی است. گاهی در بهینه‌سازی چند هدف به طور همزمان مد نظر قرار می‌گیرد؛ این گونه مسائل بهینه‌سازی را که دربرگیرنده چند تابع هدف هستند، مسائل چند هدفی می‌نامند. ساده‌ترین راه در برخورد با این گونه مسائل، تشکیل یک تابع هدف جدید به صورت ترکیب خطی توابع هدف اصلی است که در این ترکیب میزان اثرگذاری هر تابع با وزن اختصاص یافته به آن مشخص می‌شود. هر مسأله بهینه‌سازی دارای تعدادی متغیر مستقل است که آنها را متغیرهای طراحی می‌نامند که با بردار n بعدی x نشان داده می‌شوند. هدف از بهینه‌سازی تعیین متغیرهای طراحی است، به گونه‌ای که تابع هدف کمینه یا بیشینه شود.
مسائل مختلف بهینه‌سازی به دو دسته زیر تقسیم می‌شود:
الف) مسائل بهینه‌سازی بی‌محدودیت: در این مسائل هدف، بیشینه یا کمینه کردن تابع هدف بدون هر گونه محدودیتی بر روی متغیرهای طراحی می‌باشد.
ب) مسائل بهینه‌سازی با محدودیت: بهینه‌سازی در اغلب مسائل کاربردی، با توجه به محدودیت‌هایی صورت می‌گیرد؛ محدودیت‌هایی که در زمینه رفتار و عملکرد یک سیستم می‌باشد و محدودیت‌های رفتاری و محدودیت‌هایی که در فیزیک و هندسه مسأله وجود دارد، محدودیت‌های هندسی یا جانبی نامیده می‌شوند.
معادلات معرف محدودیت‌ها ممکن است به صورت مساوی یا نامساوی باشند که در هر مورد، روش بهینه‌سازی متفاوت می‌باشد. به هر حال محدودیت‌ها، ناحیه قابل قبول در طراحی را معین می‌کنند.
به طور کلی مسائل بهینه‌سازی با محدودیت را می‌توان به صورت زیر نشان داد:
Minimize or Maximize : F(X) (3.1)
Subject to : I = 1,2,3,…,p
j = 1,2,3,…,q
k = 1,2,3,…,n
که در آن X={ بردار طراحی و رابطه‌های (3.1) به ترتیب محدودیت‌های نامساوی، مساوی و محدوده قابل قبول برای متغیرهای طراحی می‌باشند.
3-3- بررسی روش‌های جستجو و بهینه‌سازی
پیشرفت کامپیوتر در طی پنجاه سال گذشته باعث توسعه روش‌های بهینه‌سازی شده، به طوری که دستورهای متعددی در طی این دوره تدوین شده است. در این بخش، مروری بر روش‌های مختلف بهینه‌سازی ارائه می‌شود.
شکل 3-1 روش‌های بهینه‌سازی را در چهار دسته وسیع دسته‌بندی می‌کند. در ادامه بحث، هر دسته از این روش‌ها مورد بررسی قرار می‌گیرند.

شکل 3-1 طبقه‌بندی انواع روش‌های بهینه‌سازی
3-3-1- روش‌های شمارشی
در روش‌های شمارشی، در هر تکرار فقط یک نقطه متعلق به فضای دامنه تابع هدف بررسی می‌شود. این روش‌ها برای پیاده‌سازی، ساده‌تر از روش‌های دیگر می‌باشند؛ اما به محاسبات قابل توجهی نیاز دارند. در این روش‌ها سازوکاری برای کاستن دامنه جستجو وجود ندارد و دامنه فضای جستجو شده با این روش خیلی بزرگ است. برنامه‌ریزی پویا مثال خوبی از روش‌های شمارشی می‌باشد. این روش کاملاً غیرهوشمند است و به همین دلیل امروزه به ندرت به تنهایی مورد استفاده قرار می‌گیرد.
3-3-2- روش‌های محاسباتی
این روش‌ها از مجموعه شرایط لازم و کافی که در جواب مسأله بهینه‌سازی صدق می‌کند، استفاده می‌کنند. وجود یا عدم وجود محدودیت‌های بهینه‌سازی در این روش‌ها نقش اساسی دارد. به همین علت، این روش‌ها به دو دسته روش‌های با محدودیت و بی‌محدودیت تقسیم می‌شوند.
روش‌های بهینه‌سازی بی‌محدودیت با توجه به تعداد متغیرها شامل بهینه‌سازی توابع یک متغیره و چند متغیره می‌باشند.
روش‌های بهینه‌سازی توابع یک متغیره، به سه دسته روش‌های مرتبه صفر، مرتبه اول و مرتبه دوم تقسیم می‌شوند. روش‌های مرتبه صفر فقط به محاسبه تابع هدف در نقاط مختلف نیاز دارد؛ اما روش‌های مرتبه اول از تابع هدف و مشتق آن و روش‌های مرتبه دوم از تابع هدف و مشتق اول و دوم آن استفاده می‌کنند. در بهینه‌سازی توابع چند متغیره که کاربرد بسیار زیادی در مسائل مهندسی دارد، کمینه‌سازی یا بیشینه‌سازی یک کمیت با مقدار زیادی متغیر طراحی صورت می‌گیرد.
یک تقسیم‌بندی، روش‌های بهینه‌سازی با محدودیت را به سه دسته برنامه‌ریزی خطی، روش‌های مستقیم و غیرمستقیم تقسیم می‌کند. مسائل با محدودیت که توابع هدف و محدودیت‌های آنها خطی باشند، جزو مسائل برنامه‌ریزی خطی قرار می‌گیرند. برنامه‌ریزی خطی شاخه‌ای از برنامه‌ریزی ریاضی است و کاربردهای فیزیکی، صنعتی و تجاری بسیاری دارد.
در روش‌های مستقیم، نقطه بهینه به طور مستقیم جستجو شده و از روش‌های بهینه‌یابی بی‌محدودیت استفاده نمی‌شود. هدف اصلی روش‌های غیرمستقیم استفاده از الگوریتم‌های بهینه‌سازی بی‌محدودیت برای حل عمومی مسائل بهینه‌سازی با محدودیت می‌باشد.
در اکثر روش‌های محاسباتی بهینه‌یابی، از گرادیان تابع هدف برای هدایت جستجو استفاده می‌شود. اگر مثلاً به علت ناپیوستگی تابع هدف، مشتق آن قابل محاسبه نباشد، این روش‌ها اغلب با مشکل روبه‌رو می‌شوند.
3-3-3- روش‌های ابتکاری و فرا ابتکاری (جستجوی تصادفی)
یک روش ناشیانه برای حل مسائل بهینه‌سازی ترکیبی این است که تمامی جواب‌های امکان‌پذیر در نظر گرفته شود و توابع هدف مربوط به آن محاسبه شود و در نهایت، بهترین جواب انتخاب گردد. روشن است که شیوه شمارش کامل، نهایتاً به جواب دقیق مسأله منتهی می‌شود؛ اما در عمل به دلیل زیاد بودن تعداد جواب‌های امکان‌پذیر، استفاده از آن غیرممکن است. با توجه به مشکلات مربوط به روش شمارش کامل، همواره بر ایجاد روش‌های مؤثرتر و کاراتر تأکید شده است. در این زمینه، الگوریتم‌های مختلفی به وجود آمده است که مشهورترین نمونه آنها، روش سیمپلکس برای حل برنامه‌های خطی و روش شاخه و کرانه برای حل برنامه‌های خطی با متغیرهای صحیح است. برای مسائلی با ابعاد بزرگ، روش سیمپلکس از کارایی بسیار خوبی برخوردار است، ولی روش شاخه و کرانه کارایی خود را از دست می‌دهد و عملکرد بهتری از شمارش کامل نخواهد داشت. به دلایل فوق، اخیراً تمرکز بیشتری بر روش‌های ابتکاری یا فرا ابتکاری یا جستجوی تصادفیصورت گرفته است.
روش‌های جستجوی ابتکاری، روش‌هایی هستند که می‌توانند جوابی خوب (نزدیک به بهینه) در زمانی محدود برای یک مسأله ارائه کنند. روش‌های جستجوی ابتکاری عمدتاً بر مبنای روش‌های شمارشی می‌باشند، با این تفاوت که از اطلاعات اضافی برای هدایت جستجو استفاده می‌کنند. این روش‌ها از نظر حوزه کاربرد، کاملاً عمومی هستند و می‌توانند مسائل خیلی پیچیده را حل کنند. عمده این روش‌ها، تصادفی بوده و از طبیعت الهام گرفته شده‌اند.
3-4- مسائل بهینه‌سازی ترکیبی
در طول دو دهه گذشته، کاربرد بهینه‌سازی در زمینه‌های مختلفی چون مهندسی صنایع، برق، کامپیوتر، ارتباطات و حمل و نقل گسترش یافته است.
بهینه‌سازی خطی و غیرخطی (جستجو جهت یافتن مقدار بهینه تابعی از متغیرهای پیوسته)، در دهه پنجاه و شصت از اصلی‌ترین جنبه‌های توجه به بهینه‌سازی بود.
بهینه‌سازی ترکیبی عبارت است از جستجو برای یافتن نقطه توابع با متغیرهای گسسته و در دهه 70 نتایج مهمی در این زمینه به دست آمد. امروزه بسیاری از مسائل بهینه‌سازی ترکیبی (مانند مسأله فروشنده دوره‌گرد) که اغلب از جمله مسائل NP-hard هستند، به صورت تقریبی (نه به طور دقیق) در کامپیوترهای موجود قابل حل می‌باشند.
به طور رسمی یک بهینه سازی ترکیبی A یک چهارتایی است به طوری که:
مجموعه نمونه هاست.
برای یک نمونه داده شده، مجموعه راه حل های امکان پذیر است.
برای یک مورد داده شده و راه حل ممکن برای ، اندازه را مشخص می کند که معمولاً یک عدد حقیقی مثبت است.
هدف تابع است که یا برابر کمینه و یا بیشینه است.
هدف این است که برای یک نمونه ، یک راه حل بهینه پیدا کنیم که یک راه حل ممکن است با این شرط که
(2.3)
برای هر مسأله بهینه سازی ترکیبی، یک مسأله تصمیم متناظر وجود دارد که می پرسد ببیند آیا یک راه حل ممکن برای مقدار خاص وجود دارد یا نه. به عنوان مثال یک گراف وجود دارد که شامل رئوس و است. یک مسأله بهینه سازی ممکن است «یافتن یک مسیر از به که از کمترین یال ها بگذرد» باشد. این مسأله ممکن است یک جواب مثلاً ۴ داشته باشد. یک مسأله تصمیم متناظر این خواهد بود که «آیا یک مسیر از به با استفاده از 10 یال یا کمتر وجود دارد؟» این مسأله با یک بله یا خیر ساده جواب داده می شود. در زمینه الگوریتم های تخمین، الگوریتم ها برای مسائل سخت برای یافتن راه حل های نزدیک بهینه طراحی می شوند. بنابراین یک نسخه معمول تصمیم، یک توصیف ناکافی از مسأله است زیرا فقط راه حل های قابل قبول را مشخص می کند. اگرچه می توانیم مسائل تصمیم مناسبی مطرح کنیم، این مسائل دیگر بیشتر به طور طبیعی، یک مسأله بهینه سازی می شوند.
3-5- روشهای حل مسائل بهینه‌سازی ترکیبی
روشن است که شیوه شمارش کامل، نهایتاً به جواب دقیق مسأله منجر می‌شود؛ اما در عمل به دلیل زیاد بودن تعداد جواب‌های امکان‌پذیر، استفاده از آن بی‌نتیجه است. برای آنکه مطلب روشن شود، مسأله مشهور فروشنده دوره‌گرد (TSP) را در نظر می‌گیریم.
این مسأله یکی از مشهورترین مسائل در حیطه بهینه‌سازی ترکیبی است که بدین شرح می باشد:
تعیین مسیر حرکت یک فروشنده بین N شهر به گونه‌ای که از هر شهر تنها یکبار بگذرد و طول کل مسیر به حداقل برسد، بسیار مطلوب است. تعداد کل جواب‌ها برابر است با . فرض کنید کامپیوتری موجود است که می‌تواند تمام جواب‌های مسأله با بیست شهر را در یک ساعت بررسی کند. بر اساس آنچه آورده شد، برای حل مسأله با 21 شهر، 20 ساعت زمان لازم است و به همین ترتیب، زمان لازم برای مسأله 22 شهر، 5/17 روز و برای مسأله 25 شهر، 6 قرن ا ست!
به دلیل همین رشد نمایی زمان محاسبه، شمارش کامل روشی کاملاً نامناسب است.
همان طور که گفته شد، با توجه به مشکلات مربوط به روش شمارش کامل، همواره بر ایجاد روش‌های مؤثرتر و کاراتر تأکید شده است. در این زمینه، الگوریتم‌های مختلفی به وجود آمده که مشهورترین آنها، الگوریتم سیمپلکس برای حل برنامه‌های خطی و روش شاخه و کران برای حل برنامه‌های خطی با اعداد صحیح است.
بنابراین در سال‌های اخیر توجه بیشتری بر روش‌های ابتکاری برگرفته از طبیعت که شباهت‌هایی با سیستم‌های اجتماعی یا طبیعی دارد، صورت گرفته است و نتایج بسیار خوبی در حل مسائل بهینه‌سازی ترکیبی NP-hard به دنبال داشته است. در این الگوریتم‌ها هیچ ضمانتی برای آنکه جواب به دست آمده بهینه باشد، وجود ندارد و تنها با صرف زمان بسیار می‌توان جواب نسبتاً دقیقی به دست آورد؛ در حقیقت با توجه به زمان صرف شده، دقت جواب تغییر می‌کند.
3-5-1- روش های ابتکاری
برای روش‌های ابتکاری نمی‌توان تعریفی جامع ارائه کرد. با وجود این، در اینجا کوشش می‌شود تعریفی تا حد امکان مناسب برای آن عنوان شود:
روش جستجوی ابتکاری، روشی است که می‌تواند جوابی خوب (نزدیک به بهینه) در زمانی محدود برای یک مسأله ارائه کند. هیچ تضمینی برای بهینه بودن جواب وجود ندارد و متأسفانه نمی‌توان میزان نزدیکی جواب به دست آمده به جواب بهینه را تعیین کرد.
در اینجا مفاهیم برخی از روش‌های اصلی ابتکاری بدون وارد شدن به جزییات معرفی می‌شود.
3-5-1-1- آزاد‌سازی
آزادسازی یکی از روش‌های ابتکاری در بهینه‌سازی است که ریشه در روش‌های قطعی بهینه‌سازی دارد. در این روش، ابتدا مسأله به شکل یک مسأله برنامه‌ریزی خطی عدد صحیح یا مختلط (و گاهی اوقات کمی غیر خطی)، فرموله می‌شود. سپس با برداشتن محدودیت‌های عدد صحیح بودن، یک مسأله آزاد شده به دست آمده و حل می‌شود. یک جواب خوب (و نه لزوماً بهینه) برای مسأله اصلی می‌تواند از روند کردن جواب مسأله آزاد شده (برای رسیدن به یک جواب موجه نزدیک به جواب مسأله آزاد شده)، به دست آید؛ اگر چه روند کردن جواب برای رسیدن به یک جواب لزوماً کار آسانی نیست، اما در مورد بسیاری از مدل‌های معمول، به آسانی قابل انجام است.
3-5-1-2- تجزیه
بسیاری اوقات آنچه که حل یک مسأله را از روش‌های قطعی بسیار مشکل می‌کند، این است که بیش از یک مورد تصمیم‌گیری وجود دارد، مانند موقعیت ماشین‌آلات و تخصیص کار، تخصیص بار به وسائل نقلیه و مسیریابی. هر یک از این موارد تصمیم‌گیری ممکن است به تنهایی پیچیده نباشند، اما در نظر گرفتن همه آنها در یک مدل به طور همزمان، چندان آسان نیست. روش ابتکاری تجزیه می‌تواند در چنین مسائلی مفید واقع شود. در این روش، جواب به دو یا چند بخش (که فرض می‌شود از هم مستقل هستند) تجزیه شده و هر یک جداگانه حل می‌شوند؛ سپس یک روش برای هماهنگ کردن و ترکیب این جواب‌های جزیی و به دست آوردن یک جواب خوب ابتکاری، به کار گرفته می‌شود.
3-5-1-3- تکرار
یکی از روش‌های تجزیه، تکرار است. در این روش، مسأله به زیرمسأله‌های جداگانه‌ای تبدیل می‌شود و در هر زمان یکی از زیرمسأله‌ها با ثابت در نظر گرفتن متغیرهای تصمیم موجود در سایر زیرمسأله‌ها در بهترین مقدار شناخته شده‌شان، بهینه می‌شود؛ سپس یکی دیگر از زیرمسأله‌ها در نظر گرفته می‌شود و این عمل به طور متناوب تا رسیدن به یک جواب رضایت‌بخش، ادامه می‌یابد.
3-5-1-4- روش تولید ستون
این نیز یکی از روش‌های تجزیه است که عموماً برای مسائلی که دارای عناصر زیادی هستند (مانند مسأله کاهش ضایعات برش با تعداد الگوهای زیاد) کاربرد دارد. در این روش، حل مسأله به دو بخش تقسیم می‌شود:
یافتن ستون‌ها (یا عناصر) جواب (مثلاً در مسأله کاهش ضایعات برش و یافتن الگوهای برش).
یافتن ترکیب بهینه این عناصر، با توجه به محدودیت‌ها (در مسأله کاهش ضایعات برش و یافتن ترکیب مناسب الگوها). یکی از روش‌های معمول برای یافتن ستون‌ها، مقدار متغیرهای دوگانه مسأله اصلی است، اما هر روش دیگری نیز می‌تواند مورد استفاده قرار گیرد.
3-5-1-5- جستجوی سازنده
در این روش، با شروع از یک جواب تهی، تصمیم‌ها مرحله به مرحله گرفته می‌شود تا یک جواب کامل به دست آید. هر تصمیم، یک تصمیم آزمند است؛ یعنی قصد دارد با استفاده از اطلاعات به دست آمده از آنچه که تا کنون انجام شده است، بهترین تصمیم را بگیرد.
آنچه که یک الگوریتم سازنده و یک الگوریتم آزمند را از هم متمایز می‌کند، نحوه ساختن جواب‌ها می‌باشد. یک الگوریتم سازنده، جواب را به هر طریق ممکن تولید می‌کند، اما در یک الگوریتم آزمند، جواب مرحله به مرحله و با توجه به یافته‌ها، ساخته می‌شود (در هر مرحله، بخشی از جواب ساخته می‌شود). جستجوی سازنده در مسائلی مانند زمانبندی ماشین و بودجه‌بندی سرمایه کاربرد داشته است. در اینجا مثال مسیریابی کامیون مطرح می‌شود. در این مسأله کالا باید به نقاط مشخصی (هر یک با میزان مشخصی از تقاضا برای کالا) حمل شود؛ مسأله، سازماندهی این نقاط در مسیرهای مشخص با توجه به محدودیت ظرفیت کامیون است.
3-5-1-6- جستجوی بهبود یافته
بر خلاف روش جستجوی سازنده، این روش با جواب‌های کامل کار می‌کند. جستجو با یک یا چند جواب (مجموعه‌ای از مقادیر متغیرهای تصمیم) شروع می‌شود و در هر مرحله، حرکت‌ها یا تغییرات مشخصی در مجموعه فعلی در نظر گرفته می‌شود و حرکت‌هایی که بیشترین بهبود را ایجاد می‌کنند، انجام می‌شود و عمل جستجو ادامه می‌یابد. یک مسأله در طراحی این روش، انتخاب جواب اولیه است. گاهی اوقات جواب اولیه یک جواب تصادفی است و گاهی نیز برای ساختن یک جواب اولیه، از روش‌هایی نظیر جستجوی سازنده استفاده می‌شود. مسأله دیگر، تعیین حرکت‌ها یا به عبارتی، تعریف همسایگی (مجموعه جواب‌هایی که با یک حرکت از جواب فعلی قابل دسترسی هستند) در مسأله است.
3-5-1-7- روش جستجوی همسایه
استفاده از الگوریتم مبتنی بر تکرار مستلزم وجود یک سازوکار تولید جواب است. سازوکار تولید جواب، برای هر جواب i یک همسایه به وجود می‌آورد که می‌توان از i به آن منتقل شد. الگوریتم‌های تکراری به عنوان جستجوی همسایه یا جستجوی محلی نیز شناخته می‌شوند. الگوریتم بدین صورت بیان می‌شود که از یک نقطه (جواب) شروع می‌شود و در هر تکرار، از نقطه جاری به یک نقطه همسایه جابه‌جایی صورت می‌گیرد. اگر جواب همسایه مقدار کمتری داشته باشد، جایگزین جواب جاری می‌شود (در مسأله حداقل‌سازی) و در غیر این صورت، نقطه همسایه دیگری انتخاب می‌شود. هنگامی که مقدار جواب از جواب تمام نقاط همسایه آن کمتر باشد، الگوریتم پایان می‌یابد.
مفهوم روش جستجوی همسایه از حدود چهل سال پیش مطرح شده است. از جمله اولین موارد آن، کارهای کرز می‌باشد که برای حل مسأله فروشنده دوره‌گرد از مفهوم جستجوی همسایه استفاده کرده است. در کارهای اخیر ریوز نیز جنبه‌هایی از این شیوه یافت می‌شود.
اشکالات الگوریتم فوق بدین شرح است:
ممکن است الگوریتم در یک بهینه محلی متوقف شود، اما مشخص نباشد که آیا جواب به دست آمده یک بهینه محلی است یا یک بهینه سراسری.
بهینه محلی به دست آمده به جواب اولیه وابسته است و در مورد چگونگی انتخاب جواب اولیه هیچ راه حلی در دسترسی نیست.
به طور معمول نمی‌توان یک حد بالا برای زمان اجرا تعیین کرد.
البته الگوریتم‌های مبتنی بر تکرار مزایایی نیز دارند؛ از جمله اینکه یافتن جواب اولیه، تعیین مقدار تابع و سازوکار تولید جواب همسایه به طور معمول ساده است.
با وجود آنکه تعیین حد بالای زمان اجرا امکان‌پذیر نیست، ولی با اطمینان می‌توان گفت که یک تکرار از الگوریتم در زمان مشخص قابل اجراست.

دانلود پایان نامه - دانلود پایان نامه

شکل 1-1 : یک سیکل از سیگنال ECG
پتانسیل عمل عضله قلبفرآیند انقباض هماهنگ بخش‌های مختلف قلب توسط پتانسیل عمل در سلول‌های موجود در بافت قلب انجام می‌گیرد. در ادامه مراحل مختلف پتانسیل عمل در یک سلول قلبی جهت ایجاد انقباض ماهیچه قلب بررسی می‌گردد[8].
مرحله استراحت : پیش از وقوع پتانسیل عمل، مرحله استراحت بر غشا حاکم است. در این مرحله گفته می‌شود که غشا پلاریزه یا قطبی است. زیرا پتانسیل آن 90- میلی‌ولت است.
مرحله دپلاریزاسیون :در این مرحله غشا ناگهان نسبت به یون سدیم نفوذپذیر می‌شود و اجازه می‌دهد تا تعداد بی‌شماری یون مثبت سدیم به درون آکسون جاری شود. حالت طبیعی پلاریزه با پتانسیل 90- میلی‌ولت از بین می‌رود و پتانسیل به سرعت در جهت مثبت بالا می‌رود. به‌این حالت دپلاریزاسیون می‌گویند.
مرحله رپلاریزاسیون : در چند ده‌هزارم ثانیه بعد از اینکه غشا به شدت نسبت به سدیم نفوذپذیر گردید،‌کانال‌های سدیم شروع به بسته شدن می‌کنند و کانال‌های پتاسیمی به میزان بیشتری نسبت به حالت طبیعی بازمی‌گردند. سپس انتشار سریع یون‌های پتاسیم به خارج، مجددا پتانسیل غشا را به حالت منفی زمان استراحت می‌رساند؛ به‌این حالت رپلاریزاسیون غشا می‌گویند.
موج P :انتشار پتانسیل تحریک از طریق دهلیز، باعث انقباض دهلیز میشود )دپلاریزاسیون( و موج P را تولید می‌کند. دامنه موج P به طور نرمال کم است.
منحنی QRS :منحنی QRS مربوط به دوره زمانی انقباض یا دپلاریزاسیون بطنی است. سیگنال رپلاریزاسیون دهلیزی مغلوب سیگنال بسیار بزرگتر بطنی می شود. این سیگنال حاصل دپلاریزاسیون بطنی است. منحنی QRS به دلیل حجم بافت بطنی که درگیر است سیگنال بسیار بزرگتری نسبت به موج P است.
موج T :موج T نتیجه انبساط یا رپلاریزاسیون بطن‌ها است و دارای طول زمانی بیشتری نسبت به منحنی QRS است، زیرا رپلاریزاسیون بطنی بسیار آهسته تر از دپلاریزاسیون اتفاق می‌افتد.
قطعه ST :بخش ST زمان بین دپلاریزاسیون و رپلاریزاسیون بطنی را نشان میدهد. بخش ST از پایان کمپلکس QRS شروع می‌شود و در آغاز موج T پایان مییابد. در حالت نرمال، بخش ST به‌اندازه 0.12 ثانیه یا کمتر است.
بازه QT:بازه QT از آغاز موج (Qi) Q شروع می‌شود و در نقطه پایان موج (Ti) Tتمام می‌شود، که نشان دهنده طول زمان سیکل دپلاریزاسیون یا رپلاریزاسیون است. اندازه نرمال زمانی بازه QTحدود 0.38 ثانیه است، و اندازه ‌آن در مردان و زنان و در سنین مختلف، متفاوت است. به عنوان یک قانون کلی، فاصله زمانی QT باید حدود 0.40 درصد فاصله زمانی R-R اندازه‌گیری شده باشد.
بیماریهای ضربان قلب :از تحلیل تغییرات ایجاد شده درشکل سیگنال نرمال الکتروکاردیوگرام می‌توان برای تشخیص بسیاری از انواع آریتمی و بیماری‌های قلبی استفاده شود. سیگنال الکتروکاردیوگرام می‌تواند به بخش‌ها و فواصل زمانی گوناگون تقسیم شود که با تعیین محدوده برای این بخش‌ها، ضربان‌های غیر نرمال تشخیص داده شوند. سیگنالهای ECG با توجه به شکل آنها و نوع آریتمی‌ها به گروه‌های مختلف تقسیم می شوند. انواع ضربان‌های قلبی با توجه به پایگاه داده MIT-BIH در جدول 1-1 نشان داده شده‌اند]6[.
Beat type Label
Normal beat N
Left bundle branch block L
Right bundle branch block R
Atrial premature beat A
Abberated atrial premature beat A
Nodal(junctional) premature beat J
Supraventricular premature beat S
Ventricular premature beat V
Fusion of ventricular and normal beat F
Ventricular flutter beat b or I
Nodal(junctional) escape beat J
Ventricular escape beat E
Fusion of paced and normal beat F
جدول 1-1 : ضربان های قلبی
در این تحقیق به طبقه‌بندی شش شکل مختلف سیگنال ECG که دارای بیشترین اهمیت هستند، پرداخته شده است. این ضربان‌ها عبارتند از:
نرمال (N)، بلوک شاخه دسته ای چپ (L یا LBBB)، بلوک شاخه دسته‌ای راست (R یا RBBB) و انقباض زودرس بطنی (V یا PVC) و ضربان زودرس دهلیزی (A) و تپش قلب (Pace beat).
بلوک شاخه دسته‌ای چپ (LBBB) و بلوک شاخه دسته‌ای راست (RBBB):
دسته‌ای از آریتمی‌ها مربوط به نارسایی‌های دسته‌ای هادی مختلف می باشند (بلوک شاخه دسته‌ای راست و بلوک شاخه دسته‌ای چپ). بلوکهای شاخه دسته‌ای (BBB) در اثر تأخیر در هدایت یکی از بخش‌های چپ (LBBB) یا راست (RBBB) سیستم هدایت بطنی رخ می‌دهد. به دلیل اینکه سیگنال در یکی از نیمه‌های بطن تأخیر یافته است، شکل QRS پهنتر می‌شود و گاهی نیز فرورفته می‌شود. این انسدادها معمولاً تاثیر بسیار کمی در عملکرد و کارآیی پمپاژ دارند و اما می‌توانند تغییر قابل ملاحظه‌ای در مسیر بردار قلبی و در نتیجه در شکل ظاهری ECG به وجود آورند. به همین دلیل این ضربان‌های قلبی غیر نرمال می‌توانند تغییرات دیگر ECG را که مشخص کننده بیماری‌ها (مثلا ایسکمی) می‌باشند را بپوشانند. در برخی موارد، این ناهنجاری‌های رسانش(LBBB و RBBB) نشانگر برخی از دیگر آسیب‌های بسیار مهم پنهان می باشند. برای نمونه، انسداد رگ های ریوی می‌تواند موجب یک بلوک شاخه دسته‌ای راست جدید و ایسکمی حاد پیشین می‌تواند موجب یک بلوک شاخه دسته‌ای چپ جدید شود. معمولاً هیچ درمانی برای بلوک شاخه دسته‌ای انجام نمی‌شود.
انقباض زودرس دهلیزی یا اکستراسیستول (APC):
گاهی اوقات ممکن است یک ریتم به وسیله ایمپالس‌هایی‌که از خارج گره سینوسی– دهلیزی‌SA سرچشمه گرفته باشند، متوقف شود. این ایمپالس‌ها قبل از اینکه یک دشارژ SA نرمال رخ دهد، اتفاق می‌افتند و در سراسر قلب انتشار پیدا می‌کنند، اگر میوکاردیوم (ماهیچه قلب) مقاوم نباشد، سبب می‌شوند تا به صورت زودرس منقبض شود. اکستراسیستول‌ها ممکن است از بالا (بالابطنی) یا از پایین (بطنی) گره دهلیزی بطنی سرچشمه بگیرند. اکستراسیستول‌ها ممکن است به صورت تکی یا در ردیف‌های کوتاه یا بلند اتفاق بیافتند.
انقباض زودرس بطنی(PVC):
ضربان‌های PVC یک شکل بسیار رایج از آریتمی‌ها می‌باشند. آنها یک شکل ضربان‌های قلبی غیر معمولی هستند که در آنها بطن به طور زودرس انقباض پیدا می‌کند. در طول یکPVC ، بطن قبل از اینکه دشارژ الکتریکی نرمال از گره SA فرا برسد، از نظر الکتریکی زودتر دشارژ شده و منقبض می‌گردد. این دشارژهای زودرس به دلیل تحریک‌پذیری الکتریکی عضله های قلبی بطن‌ها هستند. بعد از PVC سیستم الکتریکی قلب فوراً به حالت اولیه باز می‌گردد. این بازگردانی سبب یک توقف مختصر در ضربان قلبی می شود. ضربان PVC به وسیله منحنی‌های QRS پهن و گسترده شناخته می‌شود]5[.
ساختار کلی تحقیقدر این تحقیق ابتدا به بیان کلیات و روش انجام تحقیق به صورت خلاصه پرداخته شده است. در فصل دوم به مرور پژوهش‌های انجام شده در زمینه طبقه بندی سیکنال‌های قلبی و بیان روش کار آنها و مقایسه نتایج بدست آمده، پرداخته خواهد شد. در فصل سوم روش پیشنهادی به همراه توضیحات دقیق و فرمول آنها تشریح خواهد شد. در فصل چهارم مراحل شبیه‌سازی به صورت بخش به بخش بیان می‌شود. در فصل پنجم نتایج شبیه‌سازی و همچنین مقایسه با نتایج تحقیقات قبلی که در فصل دوم تشریج شده اند بیان می‌شود.

فصل دومپیشینه ‌پژوهش
2-1- مقدمههوشمند‌سازی فرآیند تشخیص بیماری‌های قلبی سالها است مورد بحث پژوهشگران تمامی کشور‌ها قرار گرفته است. این فرآیند شامل مراحلی است که طی آن سیگنال ECG به عنوان ورودی نرم افزار انتخاب می‌شود و انتظار این است که نرم افزار با دقت قابل قبولی سلامت یا بیماری و حتی نوع بیماری قلبی را تشخیص دهد. تمامی این نرم افزار‌ها پس از دریافت سیگنال، ویژگی‌های مناسب آن را استخراج و انتخاب کرده، سپس به تشخیص نوع بیماری می‌پردازد. در هر یک از مراحل بیان شده روش های گوناگونی وجود دارد که در این فصل به تحقیقات پیشین و روشی که مورد استفاده قرار گرفته است پرداخته خواهد شد.
معرفی پایگاه داده:سیگنال‌های نارسائی قلبی که از پایگاه داده MIT-BIH گرفته شده است، شامل 48 سیگنال قلب دوکاناله متشکل از 25 مرد از سنین 32-89 سال و 22 زن در سنین 23-89 سال با فرکانس نمونه‌برداری 360 هرتز و رزولوشن 12 بیت، که حدودا حاوی 650000 نمونه و تقریبا 2750 ضربان قلب در مدت زمان 30 دقیقه برای هر سیگنال می‌باشد. بیش از 109000 ضربان قلب در پایگاه فوق در قالب 15 نارسائی برچسب‌گذاری شده‌اند. از این سیگنال‌ها 45 سیگنال دارای lead II می‌باشند [11،24].
2-2- طبقه‌بندی سیگنال ECG با استفاده از موجک و شبکه عصبیپس از چند مرحله پیش پردازش از تبدیل موجک پیوسته برای استخراج ویژگی های سیگنال می‌شود. به دلیل زیاد بودن تعداد بردارهای استخراج شده توسط موجک از آنالیز PCA جهت کاهش ابعاد و به عبارتی انتخاب بهترین نمونه‌ها استفاده شده است.
شبکه عصبی چند لایه، طبقه‌بندی را بر روی شش کلاس که شامل سیگنال نرمال و 5 اریتمی قلبی که از گروهی خاص از سیگنال ECG بیماران پایگاه داده MIT-BIH انجام داده است. نمودار گرافیکی روش به کار رفته در این تحقیق در شکل 2-1 نشان داده شده است]7[.

شکل 2-1 :مراحل طبقه بندی 6 آریتمی
2-3- طبقه‌بندی سیگنال ECG با استفاده ازموجک و خواص مورفولوژیک و شبکه عصبیدر این پژوهش پس از پیش‌پردازش، 15 ویژگی زمانی و 15 ویژگی از تبدیل موجک انتخاب شده است و برای کاهش ابعاد این ویژگی ها از روش PCA استفاده شد که نتیجه آن انتخاب 8 ویژگی از بهترین ویژگی‌های هر کلاس بوده است. شبکه عصبی پرسپترون چند لایه و شبکه عصبی پایه شعاعی به صورت ترکیبی طبقه‌بندی را انجام می دهد. در این تحقیق نشان داده شده است که ساختار ترکیبی شبکه عصبی دارای نتایجی به مراتب بهتر از شبکه عصبی MLP می‌باشد]4[.
2-4- طبقه‌بندی سیگنال ECG با استفاده از تبدیل موجک و شبکه عصبی فازیدر این پژوهش از استخراج ویژگی موجک به همراه شبکه عصبی فازی برای شناسایی انقباضات زودرس بطنی PVC استفاده کرده‌اند. ایده اصلی و مزیت مهم این تحقیق استفاده مجدد از اطلاعات تولید شده در مرحله تشخیصQRS ، که یک مرحله اساسی برای بیشتر الگوریتم های طبقه بندی ECG است، می باشد. طول مدت زمان کمپلکس QRS در مقیاس سه و سطح زیر کمپلکس QRS در مقیاس چهار به عنوان ویژگی های مشخصه انتخاب شده اند. پس از نرمالیزاسیون، طبقه بندی PVC با استفاده از شبکه عصبی فازی روی سیگنال ECG تعدادی خاص از بیماران انجام شده است. دو مزیت اولیه استفاده از موجک یکسان برای دو مرحله تشخیص QRS و طبقه‌بندی PVC، محاسبات کمتر و پیچیدگی کمتر در هنگام پیاده سازی واقعی است]9[.
2-5- طبقه‌بندی سیگنال ECG با استفاده از تبدیل ویولت و شبکه عصبی مصنوعی و الگوریتم پرندگانویژگی‌های شکلی تبدیل موجک، با استفاده از آنالیز PCA به یک فضای ویژگی با ابعاد کمتر نگاشت داده شده اند، و همچنین ویژگی‌های زمانی از داده های ECG استخراج شده اند. برای قسمت تشخیص الگو از شبکه‌های عصبی مصنوعی رو به جلو که هر کدام با استفاده از تکنیک الگوریتم پرندگان چند هدفه استفاده شده است. در این تحقیق،‌سیستم طبقه‌بندی ارائه شده می تواند با آموزش ساختارهای شبکه بهینه به تغییرات اساسی در الگوهای ECG یک بیمار خاص سازگار شده و بنابراین می‌تواند به درصد دقت‌های بالاتری در دسته داده‌های بزرگ دست پیدا کند.
بر روی کل داده‌های پایگاه داده میزان میانگین معیار عملکردهای دقت حساسیت برای روش پیشنهادی برای شناسایی ضربان‌های اکتوپیک بطنی (VEB) و ضربان‌های اکتوپیک بالابطنی (SVEB) انجام شده است]10[.
2-6- طبقه‌بندی آریتمی‌های قلبی با استفاده از SVMدر این پژوهش با تحلیل سیگنال ECG، ویژگی‌های آن با ترکیبی از تبدیل ویولت و مدل AR استخراج شده اند. با چنین تلفیقی روش های رایج در تشخیص بیماری‌های قلبی بهینه شده‌اند. سپس از یک طبقه‌بندی‌کننده ماشین بردار پشتیبان با هسته گوسین به منظور طبقه‌بندی خودکار پنج نوع آریتمی قلبی استفاده شده است]2[.
2-7- طبقه‌بندی آریتمی دهلیزی بطنیدر این پژوهش یک الگوریتم کارآمد تشخیص و طبقه‌بندی ECG تک کاناله مبتنی بر تبدیل موجک را اجرا نموده و به منظور تشخیص و طبقه‌بندی برخی آریتمی‌های خطرناک بطنی به کار گرفته و بهبود داده شده است. در اولین مرحله، کمپلکس‌های QRS تشخیص داده می‌شوند. سپس مشخصات هر QRS با شناسایی و تعیین قله‌های مو ج های تشکیل دهنده آن و نیز نقاط شروع و پایان کمپلکس QRS تکمیل می‌گردد. در ادامه قله‌های موج هایT ، P و نیز نقاط شروع و پایان هر یک تعیین می‌شود . این الگوریتم را با استفاده از داده‌های حاشیه نویسی شده معروف MIT/BIH Arrhythmia Database و QT Database ارزیابی شده اند. در الگوریتم پیشنهادی با بکارگیر‌ی موجک اسپلاین درجه دوم (quadratic spline)، کمپلکس QRS و همچنین موجهای T و P از انواع نویزها و تداخل‌های ناخواسته تفکیک شده و تشخیص آریتمی‌های حاد در بانک اطلاعاتی سیگنال‌های الکتروکاردیوگرام استاندارد حتی در حضور نویز و تداخل‌های ناخواسته نیز امکان پذیر می‌گردد. با استفاده از الگوریتم پیشنهادی تشخیص آریتمی‌های تاکیکاردی بطنی VT، تاکیکاردی فوق بطنی SVT، فیبریلاسیون بطنی VFIB، فلاتر بطنی VFL، فلاتر دهلیزی AFL، و آریتمی فیبریلاسیون دهلیزی AFIB، انجام شده است]12[.
2-8- طبقه‌بندی سیگنال الکترو‌کاردیو‌گرام با طبقه‌بند ماشین بردار پشتیبان و الگوریتم PSOدر این پژوهش از ویژگی‌های زمانی و مورفولوژیک استفاده شده است. آزمایش از روش‌های طبقه بند RBF و kNN و SVM به عمل آمده که نتایج برتری طبقه‌بند SVM با هسته گوسی را نشان می‌دهد. همچنین برای تنظیم پارامترهای SVM از الگوریتم بهینه‌ساز PSO استفاده شده است که باعث بهبود عملکرد طبقه‌بندی SVM می شود. در این مقاله از 250 و500و750 ضربان اموزش استفاده شده که با توجه به نتایج آزمایش عملکرد طبقه‌بند با 750 داده اموزش دقت 93.27% است]3[.
2-9- طبقه‌بندی آریتمی‌های قلبی با استفاده از PSOدر این پژوهش یک سیستم جدید برای طبقه‌بندی سه نوع ضربان قلب شامل ضربان نرمال و دو آریتمی قلبی ارائه شده است. این سیستم شامل سه ماژول اصلی - یک ماژول استخراج ویژگی، یک ماژول طبقه بندی و یک ماژول بهینه‌سازی‌ است. در ماژول استخراج ویژگی ترکیبی مناسب از ویژگی‌های شکلی و زمانی ایجاد می‌شود. در ماژول طبقه بندی یک کلاس بند چند طبقه بر پایه ماشین بردار پشتیبان ارائه شده است. در ماژول بهینه‌سازی از الگوریتم اجتماع ذرات برای یافتن بهترین ویژگی‌ها استفاده شده است. نتایج شبیه سازی دقت مناسبی داشت و این در حالی است که در بدست آمدن این سطح دقت،فقط مقدار کمی از ویژگی‌ها استفاده شده است]14[.
2-10- رویکرد ترکیبی در طبقه‌بندی سرطانمدلی مبتنی بر فیلتر و رپر را جهت دسته‌بندی نشان گر سرطان برای انتخاب ژن در داده‌های ریز آرایه ارائه شده است. نتایج مدل ترکیبی ان‌ها که از نرخ فیشر به عنوان فیلتر استفاده می‌کند،روی چندین مجموعه داده واقعی دقت کلاس‌بندی بسیار بهتری نسبت به مدل تنها رپر، نشان می‌دهد. مدل ترکیبی دو مرحله‌ای ارائه شده در این پژوهش ویژگی‌های مناسب را بر اساس معیار اماری حداکثر وابستگی و حداقل افزونگی انتخاب می‌کند. در مرحله اول مدل از معیار حداکثر ارتباط و حداقل افزونگی برای انتخاب زیر مجموعه بهینه ویژگی‌ها بهره می‌برد. در مرحله دوم از الگوریتم‌های کلاسیک رو به جلو وعقب گرد برای جستجو در زیر مجموعه‌های مرحله اول استفاده می‌کند. نتایج تجربی مدل آنها حاکی از عملکرد بهتر این روش نسبت به روش فیلتر حداکثر وابستگی می‌باشد]15[.
2-11- دسته‌بندی آریتمی‌های قلبی بر مینای تبدیل موجک و SVMدر این پژوهش یک روش برای دسته‌بندی آریتمی‌های قلبی ارائه شده است که تعداد 5 آریتمی از بانک اطلاعاتی Physionet انتخاب شده و آریتمی‌ها به زمان های 6 ثانیه تقسیم شده و برای هر قطعه زمانی ضرایب تبدیل موجک به عنوان بردار ویژگی آن قطعه محاسبه شده و از ماشین بردار پشتیبان SVM برای دسته‌بندی آریتمی‌ها استفاده شده است. دسته‌بندی‌کننده‌های SVM را با بردارهای ویژگی قطعات آموزش داده و برای دسته‌بندی یک آریتمی مجهول، بردارهای ویژگی زمانی آن به SVM ها اعمال می‌شود]16[.
2-12- طبقه‌بندی سیگنال ECG با استفاده از خواص مورفولوژیدر این پژوهش یک روش جهت کلاس‌بندی ضربان از یک مجموعه داده بزرگ با آموزش شبکه عصبی و استفاده از موجک و ویژگی‌های زمان‌بندی ارائه داده اند. آنها دریافتند که مقیاس چهارم از تبدیل ویولت دوتایی با ویولت مرتبه دوم همراه با نرخ فاصله قبل و بعد از R-R در تمایز نرمال و PVC دیگر ضربان‌ها بسیار مؤثر است]17[.
2-13- انتخاب ویژگی با استفاده از الگوریتم فاخته باینریدر این پژوهش،انتخاب ویژگی جدید به نام جستجو فاخته دودویی، که در رفتار پرندگان فاخته است پیشنهاد شده است. آزمایش‌های انجام شده در زمینه تشخیص سرعت در سیستم‌های توزیع قدرت در دو مجموعه داده به دست آمده از یک شرکت برق برزیل انجام شدو توانایی این روش در برابر با چندین تکنیک بهینه‌سازی دیگر را نشان می‌دهد]18[.
2-14- انتخاب ویژگی با استفاده از الگوریتم فاختهمعمولا برای پیدا کردن مجموعه داده‌ها با مقدار زیادی از ویژگی‌ها روبرو هستیم که برخی از این ویژگی های مناسب نیستند. در این زمینه، یکی از استراتژی‌های مورد استفاده برای مقابله با این مشکل،انجام یک فرآیند انتخاب ویژگی به منظور ساخت یک زیر مجموعه از ویژگی‌های است که می تواند بهترین مجموعه داده را نشان دهد. مطالعات متعددی با استفاده از تکنیک‌های بهینه‌سازی الهام گرفته از طبیعت وجود دارد. در این پژوهش، ما از الگوریتم جستجو فاخته (CS) در زمینه انتخاب ویژگی استفاده می‌کنیم. برای این منظور، یک نسخه باینری از جستجو فاخته، یعنی BCS، بکار گرفته می‌شود. شبیه‌سازی و مقایسه BCS با نسخه‌های باینری از بت الگوریتم، الگوریتم کرم شب‌تاب و ذرات بهینه‌سازی انجام شده است که BCS نتایج منطقی و مناسب‌تری را نشان می‌دهد]19[.

فصل سوممعرفی الگوریتم‌ها و روش‌های پردازش سیگنال ECG
3-1- مقدمهدر این فصل به بررسی تئوری روش پیشنهادی، جزئیات و تشریح فرمول‌های مربوطه خواهیم پرداخت که شامل تکنیک‌ها و فیلترهای موجود در بخش پیش پردازش، روش‌های استخراج ویژگی از سیگنال پیش پردازش شده، روش انتخاب ویژگی‌ها و طبقه‌بند می‌باشد.
3-2- آنالیز موجکموجک یک شکل موج با طول موثر محدود و متوسط صفر است. شکل 3-1 موجک را با موج سینوسی که مبنای آنالیز فوریه است مقایسه می‌کند. موج سینوسی طول محدود ندارد و همواره قابل پیش بینی است، اما موجک‌ها تمایل دارند که نامنظم و نامتقارن باشند.
center0
00

شکل 3-1: سیگنال سینوسی و موجک
آنالیز فوریه تجزیه یک سیگنال به موجهای سینوسی از فرکانسهای مختلف است. به شکل مشابه، آنالیز موجک تجزیه یک سیگنال به نسخه‌های شیفت یافته و مقیاس شده از موجک اصلی یا مادر می‌باشد. با توجه به شکل‌های موجک و موج سینوسی، می توان دید که سیگنال‌های با تغییرات شدید بهتر می تواند با موجک نامنظم آنالیز شوند. همچنین مشخصه‌های محلی نیز توسط موجک بهتر توصیف می شوند، چون موجک‌ها محدوده محلی دارند. تبدیل موجک پیوسته (CWT) و تبدیل موجک گسسته (DWT) دو تبدیل مهم در آنالیز موجک می باشد]20[.
3-2-1- تبدیل موج پیوسته (CWT)تبدیل پیوسته موجک روی تابع پیوسته و انتگرال پذیر f(x) نسبت به موجک حقیقی Ψ(x) از رابطه زیر حاصل می‌شود:
527301126035(3-1)
020000(3-1)
WΨs, τ=-+fx Ψs,τx dx , Ψs,τ(x)=1sΨ(x-τs)
τ , s به ترتیب بیانگر مقیاس و زمان هستند]20[.
3-2-2- تبدیل موجک گسستهضرایب موجک در هر مقیاس ممکن، مقادیر بسیار زیادی عدد تولید می‌کند. راه حل کاهش تعداد آنها را می توان از تبدیل گسسته موجک (DWT) بدست آورد.
یک راه مناسب، استفاده از فیلترها در سال 1988 توسط مالات ارایه شد و توسعه یافت]21[.
3-3-2-2- تجزیه چند سطحیفرایند تجزیه می‌تواند با تقریب‌های متوالی که به نوبت تجزیه می‌شوند، تکرار شود.این عمل منجر به ایجاد درخت تجزیه موجک می‌باشد.شکل 3-2 یک درخت تجزیه موجک سه سطحی را نمایش می‌دهد]21[.

شکل 3-2: نمایی از تحلیل موجک چند وضوحی با ساختار سلسله مراتبی توسط ضرایب تقریبی و جزیی تا سطح تجزیه 3 که در آن، A مبین ضرایب تقریب و D نیز ضرایب جزئی را نشان میدهد.
شکل (3-3) ساختار فیلتری را نشان میدهد که به آن بانک فیلتری میگویند. در این ساختار بعد از اعمال هر فیلتر با کاهش نمونههای زمانی، رزولوشن فرکانسی را افزایش میدهند. بدین ترتیب که بعد از اعمال فیلتر پایینگذر در هر مرحله، با کاهش رزولوشن زمانی به میزان نصف مرحله قبل، رزولوشن فرکانسی را دو برابر میشود.

شکل 3-3: شمایی از ساختار فیلتر بانک را برای تولید ضرایب جزیی و تقریب تبدیل موجک توسط فیلترهای پایینگذر (g) و بالاگذر (h) تا سطح تجزیه سوم نشان میدهد.
3-2-4- انتخاب موجک مادرضرایب تبدیل موجک تحت تاثیر فیلترهای اعمال شده به سیگنال هستند، که این فیلترها توسط موجک مادر و تابع مقیاس بدست میآیند. از اینرو، ضرایب تبدیل موجک با توجه به تابع موجک مادر میتواند دارای شدت و اندازههای مختلف باشد. هریک از موجکهای مادر دارای خواصی هستند که آنها را از یکدیگر جدا میسازد. یکی از پرکاربردترین توابع موجک، تابع موجک مادر دابیچیز است .که برخی توابع مادر مانند سیملت و کافلت از روی آن ساخته میشود و دارای ویژگیهای متفاوت نسبت به دابیچیز هستند. از آنجاییکه توابع موجک مادر از لحاظ نوع و مرتبه متفاوت میباشند، لذا ضرایب موجک آنها از لحاظ زمانی و اندازه دامنه متفاوت است. این نکته قابل ذکر است که ضرایب خروجی فیلتر پائین گذر(g(n)) شکل اولیه سیگنال را دنبال میکنند، یعنی کلیات سیگنال معادل فرکانسهای پایین را دربردارند و ضرایب تقریب نام گرفتند. همچنین ضرایب خروجی فیلتر بالاگذر(h(n))، جزئیات سیگنال را دربردارند، به همین دلیل به این ضرایب، جزییات گفته میشود و نماینده فرکانسهای بالا میباشند[37].
انتخاب موجک مادر نقش مهمی در استخراج ویژگی سیگنال ها به خصوص سیگنال ECG دارد. از این رو ما از بین موجک‌های مختلف، موجکی را انتخاب می‌نماییم که بیشترین شباهت به سیگنال ECG داشته باشد.در شکل 3-6 انواع دابیچیزها نشان داده شده است در بین موجک‌های مادر، موجک دابیچیز 6 بیشترین شباهت به سیگنال ECG را دارد که در شکل 3-7 سیگنال ECG با 8 سطح تجزیه و 8 سیگنال جزییات نشان داده شده است[36].
-40420531215

020000

شکل 3-6: انواع دابیچیز

شکل 3-7: سیگنال ECG به همراه 8 سطح تجزیه با db6 ]36[
3-2-4- ویژگی‌های استخراج شده از ویولتاستفاده از پارامترهای جدول3-1 به جای استفاده از ضرایب ویولت توصیه شده است]35] [23[.
ویژگی های موجک استخراج شده
انرژی
درصد انرژی طول سیگنال
واریانس ضرایب ویولت
انحراف معیار ضرایب ویولت
مقدار حداکثرتوزیع داده ها
انحراف داده ها
انحراف استاندارد
میانگین داده ها
جدول 3-1 ویژگی ویولت برای تشخیص مولفه های شناختی از ECG
3-3- ویژگی زمانیتشخیص پزشک به طور عمده مبتنی بر اطلاعات زمانی‌ و ریخت‌شناسی استخراج شده از سیگنال الکتروکاردیوگرافی است. این در حالی است که در برخی از شرایط ویژگی‌های به دست آمده از تحلیل موجک بر روی سیگنال‌های قلبی، به تنهایی از تمایز کافی برای طبقه‌بندی برخوردار نیستند. از این رو، استفاده از دیگر مشخصه‌های موجود در سیگنال‌های قلبی به جهت طبقه‌بندی بیمار‌یهای قلبی ضروری به نظر می‌رسد.
برای توصیف کاملتر سیگنال الکتروکاردیوگرافی، علاوه بر ویژگی‌های موجک از ویژگی‌های زمانی نیز در این تحقیق استفاده شده است. ویژگی‌های زمانی مورد استفاده شامل نه ویژگی زمانی برای تشخیص مولفه‌های شناختی از سیگنال ECG هستند که نماد اختصاری آ نها در جدول 3-2 بیان شده است]4[.

جدول 3-2 : ویژگی زمانی برای تشخیص مولفه‌های شناختی از ECG
ویژگی نماد اختصاری
دامنه ماکزیمم سیگنال AMP
دامنه مینیمم سیگنال -AMP
ناحیه مثبت PAR
ناحیه منفی NAR
قدر مطلق ناحیه منفی NANR
مجموع ناحیه TAR
قدر مطلق مجموع ناحیه ATAR
قدر مطلق مجموع ناحیه TAAR
پیک تا پیک سیگنال PP
3-4- استخراج ویژگی با مدل خودبازگشتی(AR)55016401019175(3-2)
020000(3-2)
روش مدلسازی خود بازگشتی یکی از مدل‌های اتفاقی است که برای نمایش سیگنال‌های غیر ایستا بسیار مورد استفاده می‌باشد. در این مدل، مقادیر جاری سیگنال به صورت جمع خطی از تعداد محدودی از مقادیر قبلی بعلاوه خطای e(n) بیان می‌شود. بنابر این پردازش به صورت 3-2 مدل می‌شود:
xn=i=1pai.xn-1+e[n]
به طوری‌که می توان گفت x(n) سیگنال مورد نظر، e(n) نویز سفید با میانگین صفر و واریانس مجهول، ai ها ضرایب و p مرتبه مدل AR می‌باشد. در این معادله متغیر x(n) به مقادیر قبلی خودش وابسته است. روشهای متعددی بطور رایج برای تخمین ضرایب AR استفاده می‌شود]2[.
3-5- استراتژی انتخاب ویژگیانتخاب ویژگی فرآیندی است که ویژگی‌های با قدرت تشخیص بالاتر و موثرتر را از مجموعه‌های داده برای انجام اعمال داده کاوی انتخاب می‌کند. مرحله مقدماتی فرایند انتخاب ویژگی عبارتند از: شناسایی مجموعه ویژگی‌ها و جستجو برای بهترین زیر مجموعه. مجموعه پارامترها اغلب شامل الگوریتم‌های یادگیری الگوریتم های انتخاب و فرآیندهای تخمین خطا می‌باشند. البته این مسئله کاملا روشن است که هیچ مجموعه ویژگی به تنهایی برای کلیه‌ی مسائل داده کاوی کارا نمی‌باشد.
الگوریتم‌های انتخاب ویژگی به طور کلی به سه دسته تقسیم می‌شوند: مدل‌های فیلتر، مدل‌های رپر و مدل‌های ترکیبی]13[. مدل‌های فیلتر از مشخصات ذاتی یا آماری ویژگی‌های مجموعه‌های داده استفاده می کنند و از هر گونه الگوریتم یادگیری مستقل اند. چنین رویه‌هایی شامل ماشین یادگیری نمی‌باشند و برای مجموعه داده‌های با ابعاد بالا موثر بوده و پیشنهاد می‌شوند. در مقابل مدل‌های رپر از ماشین‌های یادگیری استفاده کرده و زیرمجموعه ویژگی‌ها را بر اساس تخمین کارایی انتخاب می‌کنند. در مقایسه با فیلتر‌ها رپرها دارای زمان و هزینه‌های محاسباتی بالاتری بوده و برای مجموعه داده‌های با ابعاد بالا مناسب نمی‌باشد. مزیت اصلی رپرها در دقت بالای پیش‌بینی آنها است. نتایج جستجوی رپرها برای یافتن بهترین زیر مجموعه ویژگی بسیار بالاتر از فیلتر‌ها گزارش شده است. برای انتخاب ویژگی خوب،تلاش اصلی فرایند جستجو باید شناخت ویژگی‌های موثر و غیر افزونه باشد]25[. اغلب روش‌های ترکیبی فیلتر و رپر از فیلترها جهت رتبه‌بندی ویژگی‌ها و کاهش تعداد ویژگی‌های کاندید استفاده می‌کنند. به طور کلی مدل‌های ترکیبی بر اساس رویه‌های ترتیبی دو مرحله‌ای کار می‌کنند.در مرحله اول معمولا براساس فیلترها تعداد ویژگی‌های مورد نظر برای مرحله دوم کاهش می‌یابند. سپس با استفاده از مجموعه کاهش یافته یک رویه رپر در مرحله دوم جهت انتخاب ویژگی‌های مطلوب اعمال می‌شود.
3-6- تحلیل مولفه اصلی (PCA)در روش تحلیل مؤلفه‌های اصلی، محور‌های مختصات جدیدی برای داده‌ها تعریف می‌شود به گونه ای که نخستین محور در جهتی قرار می‌گیرد که واریانس داده‌ها بیشینه است و دومین محور نیز عمود بر محور اول و در جهتی که واریانس داده ها بیشینه باشد،در نظر گرفته می‌شود و به همین ترتیب، محورهای بعدی عمود بر تمامی محورهای قبلی به گونه‌ای قرار می‌گیرند که واریانس داده‌ها در آن جهت بیشینه باشد]4[.تحلیل مولفه اصلی یکی از روش‌های مرسوم استخراج ویژگی است که در بسیاری از پژوهش‌ها به دلیل سادگی و سرعت بالا در پردازش از آن استفاده می‌شود]26[. تکنیک PCA بهترین روش برای کاهش ابعاد داده به صورت خطی می‌باشد یعنی با حذف ضرایب کم اهمیت بدست آمده از این تبدیل،اطلاعات از دست رفته نسبت به روشهای دیگر کمتر است.
فرض کنید ماتریس ورودی X دارای NT نمونه و n ویژگی است و NT نمونه باید در C گروه قرار گیرند، میانگین و کوواریانس داده با توجه به روابط (3-3) و (3-4) محاسبه میشوند [38]:
md=1NTi=1cj=1Nixi,j(3-3) COV=1NTi=1cj=1Ni(xi,j-md)(xi,j-md)T (3-4)
در مرحلهی بعد، مقادیر ویژه و بردارهای ویژه از روی ماتریس کواریانس محاسبه می‌شوند. سپس، تعداد k مقدار ویژه بزرگتر از n مقدار ویژه انتخاب می‌شوند. حال ماتریس ورودی X تحت ماتریس بردار ویژه P با تعداد k ویژگی، به فضای تحلیل مولفه‌اصلی تبدیل می‌شود:
(3-5) Yij=[P1,P2,…,Pk]TXij3-7- روش بیشترین وابستگی و کمترین افزونگی (mRMR)در بسیاری از کاربرد‌های شناسایی آماری الگو، انتخاب زیرمجموعه‌ای از مجموعه ویژگی‌ها می‌تواند سبب کاهش خطای دقت طبقه‌بندی گردد. هدف روش بیشترین وابستگی و کمترین افزونگی، انتخاب زیرمجموعه از فضای ویژگی مبتنی بر مفهوم همبستگی و کاهش افزونگی اطلاعات می‌باشد. فرض کنید فضای داده ورودی D، شامل N نمونه و M ویژگی است و c نیز برچسب مربوط به هر گروه باشد. در این حالت، هدف انتخاب بهینه m ویژگی از فضای M بعدی است بطوریکه هر نمونه متعلق به گروه c باشد. از آنجاییکه تعداد زیرمجموعه‌های ممکن 2M بوده و تعداد زیرمجمو ع‌هایی که ابعادشان کوچکتر از m باشد نیز i=1mMi می‌باشد جستجوی کامل زیرمجموعه‌های ویژگی بسیار دشوار است. از اینرو، روش‌های جستجوی ترتیبی مانند پیش رو ترتیبی و شناور پیش رو ترتیبی، برای جستجوی فضای کامل زیرمجموعه‌ها در فضای ویژگی پیشنهاد می‌شوند]29[. شرط توصیف بهینه معادل با کمترین خطای دقت طبقه‌بندی درنظر گرفته می‌شود، بطوریکه در طبقه‌بندی بی سرپرست،‌کمترین خطا زمانی رخ می‌دهد که بیشترین وابستگی آماری دادگان در زیر فضای Rm گروه هدف c پیدا شود. از این شیوه به عنوان شرط بیشترین وابستگی یاد می‌شود. یکی از روش‌های رایج برای بررسی مفهوم بیشترین وابستگی، روش بیشترین ارتباط است که مقصود آن بالاترین ارتباط هر ویژگی با گروه هدف c می‌باشد. بطور عام، ارتباط برحسب همبستگی و یا اطلاعات متقابل دو متغیر معرفی می‌شود. اطلاعات متقابل دو متغیر x و y، بر حسب توابع چگالی احتمال بصورت زیر تعریف می‌شود:
5196205-1905(3-6)
4000020000(3-6)
IX,Y=xyp(X,Y)log2p(X,Y)pYp(X)
در انتخاب ویژگی بر اساس بیشترین ارتباط، بیشترین اطلاعات متقابل I(xi,c) بین ویژگی‌های منتخب xi گروه هدف c صورت می‌گیرد که مبین بیشترین وابستگی ویژگی به هدف مربوط می‌باشد. در روش‌های جستجوی متوالی، m بهترین ویژگی انفرادی، یعنی آن‌هایی که بیشترین مقدار وابستگی را دارند به عنوان ویژگی‌های منتخب برگزیده می‌شوند. ولی همواره ترکیبی از بهترین ویژگی‌های منفرد به عنوان یک زیرمجموعه بهینه نیست، به عبارت دیگر m بهترین ویژگی همیشه بهترین m ویژگی نیستند. از اینرو، در کنار بیشترین همبستگی ویژگی‌ها با گروه هدف c، روش هایی جهت کاهش افزونگی وجود دارد که ویژگی هایی با کمترین افزونگی را برمی‌گزیند. لذا روش انتخاب ویژگی با معیار بیشترین وابستگی و کمترین افزونگی، یکی از روش‌هایی است که مبتنی بر سه اصل بیشترین وابستگی، بیشترین ارتباط و کمترین افزونگی بنا شده است. بر اساس اطلاعات متقابل بین دو نمونه، هدف از انتخاب ویژگی با بیشترین وابستگی به هدف گروه c، یافتن یک مجموعه ویژگی S با m عضو است که بطور مشترک بیشترین وابستگی را به هدف مربوطه داشته باشد. از دید ریاضی این مفهوم به شکل زیر بیان می‌شود]31[:
5029584-1609(3-7)
4000020000(3-7)
max DS,c, D=I(xi,i=1,…,m;c)
هنگامی که m برابر 1 باشد، مساله به یافتن ویژگی تبدیل می‌شود که Ixj,c,(I≤j≤M) را بیشینه کند و زمانی که m بزرگتر از 1 باشد، یک روش جستجوی ترتیبی ساده می‌تواند افزودن یک متغیر در هر لحظه باشد. در حالتی که مجموعه شامل m-1 ویژگی Sm-1 دردست باشد، m امین ویژگی بصورت ویژگی‌ای که بیشترین افزایش را در I(Sm,c) ایجاد می‌کند، تعریف می‌شود:
ISm,c=Smcp(Sm,c)log2p(Sm,c)pSmp(c)
=Smxmccp(Sm-1,xm,c)log2p(Sm-1,xm,c)pSm-1,xmp(c)
510640433301(3-8)
4000020000(3-8)
=…p(x1,…,xm,c)log2p(x1,…,xm,c)p(x1,…,xm)p(c)
51003641336040(3-9)
4000020000(3-9)
از آنجایی‌که تخمین دقیق از توابع چگالی چند متغیره p(x1,…,xm) و p(x1,…,xm,c) بدلیل کافی نبودن تعداد نمونه‌ها و دشواری محاسبه ابعاد بالای ماتریس کوواریانس، مشکل است، بنابراین بجای استفاده از بیشترین وابستگی از معیار بیشترین ارتباط استفاده می‌کنیم. این معیار، DS,c را با استفاده از میانگین مقادیر اطلاعات متقابل میان ویژگی‌های انفرادی xi و گروه c تخمین می زند:
max DS,c, D=1Sxi∈SI(xi,c)
51034061323975(3-10)
4000020000(3-10)
ویژگی‌هایی که براساس بیشترین ارتباط انتخاب می‌شوند دارای افزونگی بالایی هستند، یعنی وابستگی میان آن ها زیاد است. هنگامی که دو ویژگی به شدت به هم وابسته باشند، در صورت حذف یکی از آن‌ها قدرت مجزاسازی مربوط به آن ها تغییر زیادی نخواهد کرد]37[. بنابراین معیار کمترین افزونگی برای انتخاب ویژگی‌های مستقل بصورت زیر است:
minRS, R=1S2xi,xj∈SI(xi,xj)
5103702377190(3-11)
4000020000(3-11)
برای ترکیب D و R از عملگر ΦD,R استفاده کرده و در ساده ترین حالت داریم:
5110642241300(3-12)
4000020000(3-12)
max ΦD,R, Φ=D-R
max ΦD,R, Φ=D/R
در عمل از روش‌های جستجوی ترتیبی می توان به‌منظور انتخاب ویژگی‌های زیربهینه منتخب توسط عملگر Φ استفاده کرد. اگر فرض شود که مجموعه ویژگی Sm-1 از مجموعه X انتخاب شده و هدف انتخاب ویژگی m ام باشد، آنگاه این ویژگی باید تابع Φ0 را بیشینه کند:
510393813970(3-13)
4000020000(3-13)
maxxj∈X-Sm-1Ixj;c-1m-1xi∈Sm-1I(xj,xi)
3-8- الگوریتم فاخته COAالگوریتم فاخته یکی از جدیدترین و قوی ترین روش‌های بهینه سازی تکاملی می باشد که تا کنون معرفی شده است. الگوریتم فاخته با الهام از روش زندگی پرنده‌ای به نام فاخته است که در سال 2009 توسط شین اویانگ ودب ساش، توسعه یافته است. این الگوریتم توسط پرواز levy به جای پیاده روی ایزوتروپیک تصادفی ساده توسعه یافته است. الگوریتم فاخته بعدها در سال 2011 توسط رامین رجبیون به طور کامل با جزئیات بیشتر مورد بررسی قرار گرفت]30[.
اکثر پرندگان لانه‌های خود را به صورت جدا شده، نامعلوم و مستتر در پوشش گیاهی ایجاد می‌کنند تا از شناسایی توسط شکارچیان جلوگیری نمایند.در این میان برخی از پرندگان خود را از دردسر هر گونه لانه سازی و وظایف والدین رهانیده و به نوعی زیرکی جهت پرورش جوجه های خود متوسل شدند. این پرندگان هرگز برای خود لانه نمی‌سازند و به جای آن تخم‌های خود را در داخل لانه سایر انواع پرندگان قرار داده و صبر می‌کنند تا آنها در کنار تخم‌های خود به تخم‌های این پرندگان نیز رسیدگی نمایند.
فاخته مشهورترین پرنده‌ای می‌باشد که به نوعی یک متخصص در زمینه فریبکاری است. فاخته به جای ساختن لانه و تخم‌گذاری در لانه خود،لانه یک پرنده را انتخاب کرده و یکی از فاخته‌ها لانه های انواع پرنده ها را آلوده به تخم خود می‌کنند و این کار را با دقت و با تقلید از رنگ و الگوی تخم‌های موجود در هر لانه انجام می‌دهند تا تخم‌های جدید لانه شبیه تخم های تخم‌های پرنده میزبان را از بین می‌برد و تخم خود را لابه لای تخم‌های آن پرنده قرار می‌دهدو از آن محل دور می‌شود. با این عمل نگهداری تخم خود را به پرنده میزبان واگذار می‌کند.کل این فرآیند به زحمت 10ثانیه طول می‌کشد.‌ فاخته لانه های انواع پرندگان را برای این کار انتخاب می‌کند و این کار را با دقت و با توجه به رنگ و الگوی تخم‌های هر لانه انجام می‌دهد تا تخم‌های جدید شبیه تخم‌های قبلی لانه باشند. هر‌گروه‌ از فاخته‌ها،روی میزبان خاصی تخصص می‌یابند.ثابت شده که هر گروه متخصص از فاخته ها به صورت ژنتیکی با گروه دیگر اختلاف دارند.در این بین برخی پرندگان میزبان تخم‌های فاخته را در لانه خود تشخیص داده و تخم‌های فاخته را بیرون می‌اندازند و برخی لانه را ترک کرده و یک لانه جدید می‌سازند.فاخته‌ها تقلید خود را در لانه میزبان بهبود می‌بخشند و پرندگان میزبان هم روش شناسایی تخم‌های بیگانه را یاد می‌گیرند.این تلاش و مبارزه برای بقا بین پرندگان مختلف و فاخته ها مدام و پیوسته است.
جوجه‌های فاخته زودتر از تخمهای پرنده میزبان بیرون می‌آیند و زودتر هم رشد می‌کنند. در اکثر موارد جوجه‌ی فاخته تخم‌ها و یا جوجه‌های پرنده میزبان را از لانه بیرون می‌اندازند. این مساله کاملا غریزی می باشد.
3-8-2- جزییات الگوریتم بهینه‌سازی فاختههمانند سایر الگوریتم‌های تکاملی COA هم با جمعیت اولیه کار خود را شروع می‌کند و جمعیتی متشکل از فاخته‌ها. این جمعیت از فاخته‌ها تعدادی تخم دارند که آنها را در لانه تعدادی پرنده میزبان خواهند گذاشت. تعدادی از این تخم‌ها که شباهت بیشتری به تخم‌های پرنده میزبان دارند شانس بیشتری برای رشد و تبدیل شدن به فاخته بالغ را خواهند داشت. سایرتخم‌ها توسط پرنده میزبان شناسایی شده و از بین میروند. میزان تخم‌های رشد کرده، مفید بودن لانه را نشان میدهد. هر چه تخم‌های بیشتری در یک ناحیه قادر به زیست باشند و نجات یابند به همان اندازه سود (تمایل) بیشتری به آن منطقه اختصاص می‌یابد. بنابراین موقعیتی که در آن بیشترین تعداد تخم‌ها نجات یابند پارامتری خواهد بود که COA قصد بهینه سازی آن را دارد.

230505097790شروع
00شروع

4105275346075002733675346075002733675257175003457575476250تعیین شعاع تخمگذاری برای هر فاخته
00تعیین شعاع تخمگذاری برای هر فاخته
2085975476250تعیین پارامترها و ورودی ها
00تعیین پارامترها و ورودی ها
2085975933450تخم گذاری در لانه های مختلف
00تخم گذاری در لانه های مختلف
3457575933450حرکت تمامی فاخته ها به سمت بهترین محل
00حرکت تمامی فاخته ها به سمت بهترین محل
34575751390650مشخص نمودن جوامع فاخته ها
00مشخص نمودن جوامع فاخته ها
20859751390650بعضی از تخم ها کشته یا از بین می روند
00بعضی از تخم ها کشته یا از بین می روند

410527533464500273367533464500
410527526987500273367526987500
1609725461645خیر
00خیر
1962150290195جمعیت از ماکزیموم مقدار کوجکتر است؟
00جمعیت از ماکزیموم مقدار کوجکتر است؟
410527520447000273367520447000
171450027495500171450027495500
2790825237490بله
00بله
41052751122045001714500417195002733675283845002028825626745محاسبه سود (چک نمودن احتمال بقا هر تخم)
00محاسبه سود (چک نمودن احتمال بقا هر تخم)
1714500487045004105275417195003438525741045پرورش تخم ها
00پرورش تخم ها
343852536195یافتن لانه ها با بهترین نوع زیست
00یافتن لانه ها با بهترین نوع زیست
106680036195از بین بردن فاخته ها در نواحی مختلف
00از بین بردن فاخته ها در نواحی مختلف

273367548514000

متن کامل در سایت امید فایل 

198120029845شرط توقف برقرار است؟
00شرط توقف برقرار است؟

347662515240002038350328930بله
00بله
372427552705خیر
00خیر

27336754445002305050138430توقف
00توقف

شکل 3-8 : فلوچارت الگوریتم بهینه سازی فاخته]30[.
فاخخته‌ها برای نجات تعداد بیشتری از تخم‌های خود دنبال بهترین منطقه می‌گردند.پس از انکه جوجه ها از تخم درامدندو بالغ شدند جوامع و گروه‌هایی تشکیل می‌دهند.هر گروه محل سکونت خود را برای زندگی دارد.تمام گروه‌ها به سمت بهترین منطقه مهاجرت می‌کنند و هر گروه نزدیک بهترین منطقه ساکن می شوند.شعاع تخم‌گذاری فاخته در بهترین منطقه فعلی با توجه به در نظر گرفتن تعداد تخم‌هایی که هر فاخته می‌گذارد و فاصله فاخته‌ها از منطقه بهینه فعلی شکل می‌گیرد.سپس فاخته ها در لانه های مو جود در این شعاع تخم‌گذاری می‌کنند.این فرآیند تا رسیدن به بهترین محل تخم‌گذاری ادامه می‌یابد.محل بهینه جایی است که بیشترین تعداد فاخته در آن مکان گرد می‌آیند.]30[.
3-8-2-1- تولید محل‌های سکونت اولیه فاخته‌ها (جمعیت اولیه‌ی جواب‌های کاندید)برای حل یک مساله بهینه‌سازی لازم است تا مقادیر متغیر‌های مساله به فرم یک آرایه شکل گیرند. دراین آرایه‌ها با نام‌های کروموزوم و موقعیت ذرات مشخص می‌شوند. ولی در الگوریتم بهینه‌سازی فاخته این آرایه habitat یا محل سکونت نام دارند.
در یک مساله بهینه‌سازی Nvar بعدی یک habitat آرایه 1*Nvar خواهد بود که موقعیت فعلی زندگی فاخته‌ها را نشان می‌دهد. این آرایه به شکل زیر تعریف می‌شود:
50755556867(3-14)
020000(3-14)

میزان مناسب بودن (یا مقدار سود) در habitat فعلی با ارزیابی تابع سود fp) )در habitat به دست می آید. بنابراین:
496769326242(3-15)
020000(3-15)

همانطور که دیده می شود COA الگوریتمی است که تابع سود را ماکزیمم می‌‌کند. برای استفاده از COA برای حل مسایل کمینه‌سازی کافی است یک علامت منفی در تابع هزینه ضرب کنیم. برای شروع الگوریتم بهینه‌سازی یک ماتریس habitat به سایز Npop*Nvar تولید می‌شود. سپس برای هر کدام از این habitatها تعدادی تصادفی تخم تخصیص می‌یابد. در طبیعت هر فاخته بین 5 تا 20 تخم می‌گذارد. این اعداد به عنوان حد بالا و پایین تخصیص تخم به هر فاخته در تکرار‌های مختلف استفاده می‌شود. دیگر عادت هر فاخته حقیقی این است که آن در یک دامنه مشخص تخم‌های خود را می‌گذارند که به آن حداکثر دامنه تخم‌گذاری (ELR) گفته می‌شود. در یک مساله بهینه‌سازی ‌هر متغیر دارای حد بالا varhi و حد پایین varlow است که هر ELRبا استفاده از این حدود قابل تعریف خواهد بود. ELR متناسب است با تعداد کل تخم‌ها، تعداد تخم‌های فعلی فاخته و همچنین حد بالا و پایین متغیر‌های مساله. بنابراین ELR به صورت رابطه زیر تعریف می‌شود:
5351780141738(3-16)
020000(3-16)