معرفی سیستم ایمنی مصنوعی(Artificial Immune System)

ایمنی از مولکول ها،سلول ها و قوانینی تشکیل شده که از آسیب رساندن عواملی مانند پاتوژن ها(Pathogens) به بدن جلوگیری می کند، قسمتی از پاتوژن به نام آنتی ژن(Antigen) که توسط این سیستم قابل شناسایی و موجب فعال شدن پاسخ سیستم ایمنی می شود. یک نمونه ای از پاسخ سیستم ایمنی ترشح آنتی بادی توسط سلول های B ،که آنتی بادی ها مولکول های شناساگری به شکل Y هستند که به سطح سلول های B متصل است و با یکسری قوانین از پیش تعریف شده آنتی ژن را شناسایی می کنند. مولکول های آنتی بادی قسمتی از آنتی ژن را به نام اپیتوپ شناسایی می کنند،ناحیه ای از آنتی بادی که وظیفه شناسایی و اتصال به آنتی ژن را دارد پاراتوپ گویند که با نام V شناخته می شود، که به منظور ایجاد بیشترین میزان تطابق با آنتی ژن ها می توانند شکل خود را تغییر دهند و به همین دلیل ناحیه متغیر نامیده می شود.

سیستم ایمنی مصنوعی

 

سطوح سیستم ایمنی

     1. اولين سطح – پوست

     2. دومین سطح – ايمني فيزيولوژيکي

  • اشک چشم ، بزاق دهان ، عرق و …

     3. سومین سطح – ایمنی ذاتی

  • پاسخ عمومی به آنتی ژن ها
  • بسیار کند

4. چهارمین سطح – ایمنی اکتسابی

  • پاسخ اختصاصی به آنتی ژن ها
  • بسیار سریع

سیستم ایمنی مصنوعی

ایمنی ذاتی(Innate Immunity)

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

 

واکنش دستگاه ایمنی ذاتی نسبت به عفونت

واکنش دستگاه ایمنی ذاتی نسبت به عفونت

 

ایمنی اکتسابی (Adaptive Immunity)

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

لنفسیت ها (Lymphocytes)

شناسایی آنتی ژن ها برعهده گلبول های سفید خون که لنفسیت نام دارد و دو نوع لنفسیت B و لنفسیت T داریم و در ادامه در مورد هر کدام توضیح خواهیم داد.

 لنفسیت های نوع B

 سلول های بنیادی که در مغز استخوان تولید می شوند و هر سلول B تعداد گیرنده سلولی (B-Cell Receptor) یا آنتی بادی(Antibody) در سطح خود دارد و هرکدام از این آنتی بادی ها دارای اشکال متفاوتی هستند که هر شکلی شبیه به سلول B را دارند و در نتیجه آنتی بادی هایی که توسط سلول B ساخته شده اند به مجموعه مشابهی از الگوهایی مولکولی متصل می شوند. آنتی بادی های سلول B دو ارزشی و دو عملکردی هستند، دو ارزشی به این دلیل که از طریق دو بازوی Fab به دو آنتی ژن متصل می شوند و از طریق قسمت FC به پذیرنده خاص روی سطح سلول های ایمنی دیگر وصل می شوند. اتصال به آنتی ژن دو نقش را بازی می کند که نقش اصلی آن برچسب زدن به آنتی ژن به عنوان یک مخرب تا مابقی سلول های سیستم ایمنی آن را تخریب کنند به این عملیات آماده مرگ می گویند، این کار با اتصال نواحی Fab آنتی بادی به آنتی ژن صورت می گیرد و ناحیه FC دستنخورده باقی می ماند تا اتصال با سلول های ایمنی دیگر مانند ماکروفاژها(Macrophages) صورت می پذیرد، یک آنتی بادی از دو زنجیره سبک مشابه (L) و دو زنجیره سنگین مشابه (H) تشکیل شده است که در شکل زیر نشان داده شده است.

 

سیستم ایمنی مصنوعی

 

لنفسیت های نوع T

یکی از چالش های سیستم ایمنی تشخیص سلول های خودی از غیر خودی (عوامل بیماری زا) است زیرا در سطح خارجی سلول های خودی آنتی ژن وجود دارد و وظیفه سلول T تشخیص آنتی ژن های سلول های خودی که به آنها آنتی ژن خودی گفته می شود از آنتی ژن های عوامل بیماری زا که به آن آنتی ژن های غیر خودی گفته می شود. سلول های T از سلول های بنیادی مغز استخوان تولید و وارد خون می شوند سلول های T نابالغ گفته می شود که این سلول های نابالغ از طریق جریان خون وارد غده تیموس می شوند و در این غده بخشی محافظت شده وجود دارد که در آن تنها سلول های خودی وجود دارد که نمی تواند هیچ عامل بیماری زایی در بدن وجود داشته باشد.

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

لنفسیت های نوع T

ویژگی های سیستم ایمنی بدن

سیستم ایمنی بدن شامل خصوصیاتی که بالطبع سیستم ایمنی مصنوعی از آن پیروی می کند که به صورت خلاصه در مورد هر کدام توضیح داده شده است:

1- قابلیت تشیخص الگو توسط آنتی بادی ها: این تشخیص الگو با استفاده از یک آستانه انجام می شود و زمانی که تحریک الگویی از یک آستانه بالاتر رفت به عنوان یک سلول خودی شناخته می شود.

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

3- قابلیت یادگیری: سیستم ایمنی بدن قادر است که ویروس های جدیدی را که مشاهده می کند به خاطر می سپارد.

4- همکاری گروهی: در سیستم ایمنی سلول ها به صورت گروهی، موازی و توزیع شده برای تشخیص و انهدام همکاری دارند.

5- چند لایه ای بودن: هیچ موجودیتی در سیستم ایمنی بدن انسان یک مکانیزم کامل امنیتی و دفاعی را فراهم نمی کند بلکه هر لایه سیستم ایمنی به صورت مستقل عمل کرده و با بقیه لایه ها در ارتباط است.

6- تنوع و گوناگونی: سیستم ایمنی بدن در برابر انواع مختلفی از نفوذها مقاومت کرده و تسلیم نمی شود.

7- بهینه بودن منابع: در سیستم ایمنی با ایجاد مرگ سلولی و تکثیر سلولی، یک نمونه فضای کوچکی از فضای جستجوی آنتی ژن ها در هر زمان نگه داری می کنند.

8- پاسخ انتخابی: در سیستم ایمنی بدن پس از شناسایی یک آنتی ژن پاسخ های متفاوتی داده می شود که به یک شکل عمل نمی کنند.

9- تنظیم تعداد سلول های ایمنی توسط سیستم ایمنی

 سیستم ایمنی مصنوعی

یک الگویی برای یادگیری ماشین است و یادگیری ماشین یعنی توانایی کامپیوتر برای انجام یک کار با یادگیری داده ها از روی تجربه است.

کاربردهای سیستم ایمنی مصنوعی

AIS یکی از الگوریتم های الهام گرفته از سیستم ایمنی بدن انسان است و راه حل هایی را برای مسائل پیچیده ارائه داده اند و از جمله کاربردهای آن عبارتند از:

خوشه بندی (Clustering)

زمانبندی (Scheduling)

تشخیص عیب (Fault Detection)

تشخیص ناهنجاری (َAnomaly Detection)

امنیت اطلاعات (Security Infrmation)

مسائل بهینه سازی (Optimization problems)

دسته بندی الگوها (Patterns Classification)

سیستم های یادگیرنده (Learning system)

تشخیص نفوذ (Intrusion Detection)

مراحل سیستم ایمنی مصنوعی

 برای حل مساله با استفاده از  AIS باید 3 مرحله زیر انجام پذیرد:

1- نحوه نمایش داده های مساله (تعریف فضای شکل)

2- معیار اندازه گیری میل ترکیبی

3-انتخاب یک الگوریتم ایمنی مصنوعی برای حل مساله

فضای شکل (Shape Space)

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

نحوه محاسبه و میل ترکیبی آنتی بادی با آنتی ژن

هر چه آنتی بادی میل ترکیبی بیشتری با آنتی ژن داشته باشد یعنی هر چه فاصله آنتی بادی و آنتی ژن کمتر شود مکمل بهتری برای آنتی ژن است و میل ترکیبی را می توان به صورت شباهت آرایه ها در نظر گرفت. که بر همین اساس در الگوریتم AIS از فاصله به عنوان معیار ارزیابی خوب یا بد بودن یک آنتی بادی استفاده می شود.

الگوریتم های AIS

الگوریتم های AIS به 3 دسته تقسیم می شوند:

1- دسته اول الگوریتم هایی که بر مبنای انتخاب کلونی سلول های B ایجاد شده اند.

2- دسته دوم الگوریتم هایی که بر مبنای انتخاب معکوس سلول های T ایجاد شده اند.

3- دسته سوم بر مبنای تئوری شبکه ایمنی ایجاد شده اند.

انتخاب کلونی (Clonal Selection)

زمانی که سلول B آنتی ژن را شناسایی می کند و سلول های B شروع به تکثیر شدن می کنند و تعداد زیادی سلول B یکسان و مشابه تولید می شود، 12 ساعت طول می کشد که یک سلول B رشد کرده و به دو سلول تبدیل شود و بعد از تحریک شدن دوره تکثیر حدودا یک هفته طول می کشد و از یک سلول 2 به توان 14 (16000) سلول مشابه تولید می شود و هر چه میل پیوندی بین سلول B و آنتی ژن بیشتر شود نرخ تکثیر بیشتر خواهد شد، در نتیجه سلول های B با میل پیوندی بالاتر، کلونی بیشتری تولید می کنند که اصل انتخاب کلونی نام دارد.

اصل انتخاب کلونی در AIS الگوریتم خاص خودش را دارد که بعد از تکثیر شدن سلول های B شروع به بالغ شدن می کنند که این فرایند در 3 مرحله صورت می پذیرد:

1- دگرگونی ایزوتایپ

2- بلوغ میل پیوندی

3- تصمیم گیری بین حافظه یا پلاسما شدن سلول B

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

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

انتخاب کلونی (Clonal Selection)

انتخاب معکوس (Negative Selection)

میل ترکیبی سلول های T نابالغ با سلول های موجود در تیموس بررسی می شود و هرکدام از سلول های T نابالغ میل ترکیبی زیادی با یکی از سلول ها داشته باشند حذف می شوند و سایر سلول های T وارد جریان خون می شوند که  به این گونه انتخاب در آن برای حدف شدن انتخاب می شود انتخاب معکوس گویند.

 

انتخاب معکوس (Negative Selection)

 

تئوری شبکه ایمنی (Immune Network Theory)

آنتی بادی های موجود بر روی B-Cell ها می توانندعلاوه بر تشخیص آنتی ژن، آنتی بادی را هم می توانند تشخیص بدهند و باعث می شود سیستم ایمنی رفتاری پویا داشته که از آن در AIS استفاده می شود، و بر اساس این تئوری هر آنتی بادی قسمتی به نام ایدوتوپ دارد که توسط آنتی بادی دیگر قابل شناسایی است که در نتیجه آنتی بادی ها با شناسایی کردن یکدیگر سیگنال هایی را ارسال می کنند که می توانند یکدیگر را تحریک کنند و بدین ترتیب این شناسائی و تاثیر گذاری بر روی یکدیگر باعث پویایی شبکه ایمنی مصنوعی می شود. به مجموعه آنتی بادی ها که یکدیگر را شناسایی می کنند شبکه ایمنی یا ایدوتوپی گفنه می شود.

 

تئوری شبکه ایمنی (Immune Network Theory)

 

در هر الگوریتم AIS باید به 3 نکته توجه داشت:

1- در هر الگوریتم AIS باید حداقل یک جزء ایمنی مانند لنفسیت باشد.

2- در هر الگوریتم AIS باید ایده ای برگرفته از بیولوژی نظری یا تجربی باشد.

3- الگوریتم AIS که طراحی می شود باید به حل مسئله کمک کند.

مقایسه سیستم ایمنی طبیعی و الگوریتم های ایمنی مصنوعی

 

مقایسه سیستم ایمنی طبیعی و الگوریتم های ایمنی مصنوعی

 

برگرفته از پایان نامه بنت الهدی حلمی – دانشگاه علم و صنعت – تحت عنوان استخراج قوانین انجمنی با استفاده از سیستم ایمنی مصنوعی

استخراج قوانین انجمنی با استفاده از سیستم ایمنی مصنوعی

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

کاهش معناگری داده با استفاده از سیستم های ایمنی مصنوعی

 

منبع

به عنوان یک قانون کلی که در مقالهOptimum population size and mutation rate for a simple real genetic algorithm that optimizes array factors  به آن اشاره شده (لینک مقاله در انتها آورده شده) اندازه جمعیت به تعداد ژن ها بستگی دارد. بنابراین ۹ ژن  به ۱۶ کروموزوم نیاز دارد و ۱۶ ژن به ۳۲ کروموزوم. معمولا با انتخاب اندازه حمعیتی معادل با ۱٫۵ تا ۲ برابر تعداد ژن ها شروع می شود تا به ماکزیمم اندازه جمعیت ۱۰۰ برسیم.

برای فضاهای حالت پیچیده احتمال crossover بالاتر (بیش از ۰٫۵) به جستجو در ابتدای کار کمک می کند. با این وجود در ادامه باید به مقادیری نزدیک به ۰٫۱ یا ۰٫۲ کاهش یابد. احتمال میوتیشن باید پایین نگه داشته شود (۰٫۰۱ – ۰٫۱). در غیر اینصورت همگرایی بی دلیل به تعویق می افتد.

پس برای مسائل مختلف و نحوه پیاده سازی مختلف الگوریتم ها تنظیم پارامترها متفاوت است و نمی توان به یک روال خاص در رابطه با کوچک یا بزرگ در نظر گرفتن جمعیت یا احتمالات میوتیشن و crossover اکتفا کرد. و بهترین راه تنظیم این پارامترها معمولا سعی و خطا و بازی با پارامترهاست.

ولی به عنوان یک قانون کلی:

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

اگر احتمال crossover بسیار بزرگ باشد: جمعیت هیچ گاه همگرا نمی شود

در ادامه الگوریتم مورد استفاده برای مسئله ۸ وزیر بارها وبارها با پارامترهای مختلف اجرا شده است تا بهترین پارامترها در نظر گرفته شود.

به این صورت عمل شده است که از آنجایی که تعداد ژن ها برابر با ۸ است ابتدا از ۱٫۵ برابر آن یعنی ۱۲ شروع شده است. یعنی مقدار جمعیت برای بار اول برابر با ۱۲ قرار داده شده است. تعداد نسل ها برابر با تعداد تکرار است. تعداد نسل را نصف تعداد جمعیت قرار می دهیم و از احتمال میویتش ۰٫۰۱ و احتمال crossover 0.5 استفاده می کنیم. لینک دانلود مرجع کد برنامه در انتها آورده شده است.

همان طور که مشاهده می شود نتیجه خوب نیست

تغییر تعداد جمعیت به دو برابر تعداد ژن ها:

هنوز به فیتنس ۲۸ یعنی تعداد برخوردهای ۰ نرسیده ایم.

در محله بعدی تکرار افزایش می یابد:

حال برای مقایسه مقدار crossover افزایش می یابد:

در این حالت هم به global maximum نرسیدیم و در دام بهینه محلی افتادیم.

مقدار crossover را مجددا کمتر کرده و مقدار میوتیشن را کمی افزایش می دهم:

نتیجه بدتر شد. مجددا به حالت قبل بر می گردانیم:

مشاهده می شود این بار نتیجه از بار قبل که با همین مقادیر اجرا شد بهتر است. چون الگوریتم ژنتیک احتمالاتی است هر بار اجرای آن نتیجه متفاوتی دارد. مثلا ژنی که برای میوتیشن انتخاب می شود تغییر می کند و کروموزوم حاصل در نسل بعدی نتیجه را تغییر می دهد.

در مرحله بعد تعداد جمعیت را به ۲۰ افزایش میدهیم:

نتیجه تغییر چندانی ندارد.

همان طور که در شکل بالا مشاهده می شود اندازه نسل نیز افزایش یافت ولی تغییر چندانی حاصل نشد.

به نظر می رسد تعداد جمعیت باید تغییر زیادی داشته باشد تا نتیجه بیشتر تغییر کند:

در این مرحله تعداد جمعیت را برابر با تعداد ژنها به توان ۲ در نظر می گیریم (در تحقیقی ثابت شده بهتر است همواره جمعیت بیشتر از دوبرابر تعداد ژنها باشد که این طور که از نتایج مشخص است این روش خوبی است).

حال می توان میتویشن و crossover را تغییر داد:

کاهش crossover در این حالت نتیجه را خراب کرد

در حالت فوق میوتیشن کمی افزایش داده شد

در حالت فوق جمعیت و تکرار را افزایش می دهیم که ابتدا به دو راه حل بهینه می رسد و البته سرعت اجرا بسیار کند می باشد ولی بعد از افزایش میوتیشن تعداد راه حل های بهینه افزایش پیدا کرده و سرعت کندتر می شود. یعنی هزینه اجرایی بالا می رود.

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

در تصویر فوق مشاهده می شود که به علت قرار گیری عدد بزرگ در crossover به هیچ وجه همگرا نمی شود

تا کنون بهترین حالتی که مشاهده شد تصویر فوق است. که با در نظر گرفتن جمعیت نرمال ۱۰۰ ، تعداد تکرار نصف جمعیت یعنی ۵۰ و مقدار احتمال میوتیشن ۰,۰۱ و crossover برابر با ۰٫۰۷ به ۶ جواب بهینه رسیدیم. یعنی ۶ کروموزومی پیدا شدند که فیتنس ۲۸ و ماکزیمم دارند.

اجرای ۸ وزیر در متلب:

در کد زیر که با الهام از الگوریتم تپه نوردی نوشته شده پس از اجرا برای جمعیت برابر با ۱۰۰۰ و تعداد تکراری برابر با ۱۰۰ به ۲۰ جواب بهینه رسیدیم. در اینجا نیز تنظیم پارامترها دست شما است و می توان به جواب بهتری رسید


pop=1000;                                         %total population always

gen=100;                                           %total generations

n=8;

max_fitness=(((n-1)*n)/2);

initpop=zeros(pop,n);                            %initial population

pop_fitness=zeros(pop,1);                        %population fitness matrix

pop_fitness_sorted=zeros(pop,1);                 %for sorted fitness

fitness_temp=0;                                  %fitness temporary variable used in fitness loops between k and j

actual_pop_temp=zeros(1,n);

actual_pop_sorted=zeros(pop,n);

z=0;                                             %temporary variable used for simplicity

s=1;

w=0;

solution=zeros(1000,n);                           % solution matrix

cross_over_temp_mat=zeros(pop/2,n);              %cross-over variables

cross_over_ready_pop=zeros(pop,n);

cross_over_pop_final=zeros(pop,n);

cross_over_point=0;

cross_over_pop_temp_one=zeros(1,n);

cross_over_pop_temp_two=zeros(1,n);

cross_over_pop_temp_adjust=0;

cross_over_child_two_flipped=zeros(1,n);

cross_over_child_one=zeros(1,n);

cross_over_child_two=zeros(1,n);

mutation_temp_one=0;                             %mutation variables

mutation_temp_two=0;

mutation_temp_data=0;

for i=1:pop

initpop(i,:)=randperm(n);   %random initial population –indicates queen position on board

end;

actual_pop=initpop;                                 %duplication for working on this variable and keeping initial population intact

%generations loop

for q=1:gen

%for one generation

for i = 1:pop

fitness_temp=0;

%fitness calculation loop

for k=1:(n-1)                                               %calculates fitness by position manipulation

for j=k+1:n                                         %queen movements have been covered using j and k manipulation

z=abs(actual_pop(i,k)-actual_pop(i,j));          % for example   : when one queen is at (3,1)–(row,column)

if (ne(z,0)&& ne(z,(j-k)))                      %                next queens cant be at {(2,2),(3,2),(4,2) } {(1,3),(3,3),(5,3)}

fitness_temp=fitness_temp+1;               %                now you can observe that subtraction of each queen position and next

end                                             %                column queen position tells us a lot of information.

end                                                 %                remember the actual pop contains queen position dont confuse them with ‘i’ & ‘j’

end

pop_fitness(i,1)=fitness_temp;

end

%sort for individuals with good fitness

pop_fitness_sorted=pop_fitness;

actual_pop_sorted=actual_pop;

for i=1:(pop-1)

for j=i+1:pop

if(pop_fitness_sorted(i,1)<pop_fitness_sorted(j,1))

fitness_temp=pop_fitness_sorted(i,1);

pop_fitness_sorted(i,1)=pop_fitness_sorted(j,1);

pop_fitness_sorted(j,1)=fitness_temp;

actual_pop_temp(1,:)=actual_pop_sorted(i,:);

actual_pop_sorted(i,:)=actual_pop_sorted(j,:);

actual_pop_sorted(j,:)=actual_pop_temp(1,:);

end

end

end

% for unique solution gathering

%specified a vector of 100 rows ‘n’ columns

for i=1:pop

if(pop_fitness_sorted(i,1)==max_fitness)

for j=1:s

if actual_pop_sorted(i,:)==solution(j,:)

w=w+1;

else

w=w;

end

end

if w==0

solution(s,:)=actual_pop_sorted(i,:);

s=s+1;

else

continue;

end

end

w=0;

end

%selection

for i=1:(pop/2)

cross_over_temp_mat(i,:)=actual_pop_sorted(i,:);

end

cross_over_ready_pop=repmat(cross_over_temp_mat,2,1);

cross_over_pop_final=cross_over_ready_pop;

%cross over part begins

%for detail explaination cross over logic refer to the pdf attached

%logic—get random crossover point–then cross over at that point

%if two same values of rows in one individual..then adjust crossover

%according to the logic give in the pdf

while 1,

cross_over_point=floor(n*rand(1));

if cross_over_point~=0

break;

end

end

i=1;

while i<(pop-1),

cross_over_pop_temp_one(1,:)=cross_over_ready_pop(i,:);         %copied parents

cross_over_pop_temp_two(1,:)=cross_over_ready_pop(i+1,:);       %copied parents

%for child one

for j=1:cross_over_point

for k=j:n

if (cross_over_pop_temp_one(1,j)==cross_over_pop_temp_two(1,k))

cross_over_pop_temp_adjust=cross_over_pop_temp_two(1,j);

cross_over_pop_temp_two(1,j)=cross_over_pop_temp_two(1,k);

cross_over_pop_temp_two(1,k)=cross_over_pop_temp_adjust;

break;

end

end

end

for j=1:cross_over_point

cross_over_child_one(1,j)=cross_over_pop_temp_one(1,j);

end

for j=cross_over_point:n

cross_over_child_one(1,j)=cross_over_pop_temp_two(1,j);

end

%for child two

cross_over_pop_temp_two(1,:)=cross_over_ready_pop(i,:);         %copied parents

cross_over_pop_temp_one(1,:)=cross_over_ready_pop(i+1,:);       %copied parents

for j=1:cross_over_point

for k=j:n

if (cross_over_pop_temp_one(1,j)==cross_over_pop_temp_two(1,k))

cross_over_pop_temp_adjust=cross_over_pop_temp_two(1,j);

cross_over_pop_temp_two(1,j)=cross_over_pop_temp_two(1,k);

cross_over_pop_temp_two(1,k)=cross_over_pop_temp_adjust;

break;

end

end

end

for j=1:cross_over_point

cross_over_child_two(1,j)=cross_over_pop_temp_one(1,j);

end

for j=cross_over_point:n

cross_over_child_two(1,j)=cross_over_pop_temp_two(1,j);

end

cross_over_pop_final(i,:)=cross_over_child_one(1,:);

cross_over_child_two_flipped=wrev(cross_over_child_two);                 %flipped

cross_over_pop_final(i+1,:)=cross_over_child_two_flipped(1,:);

i=i+2;

end

%mutation introduced

%mutation occours  :at every 5th individual..swapping of two random

%                   column values(that is queen positions)

i=5;

while i<pop,

mutation_temp_one=floor(rand(1)*n/2);

mutation_temp_two=floor(2*(rand(1)*n/2));

if (mutation_temp_one==0 || mutation_temp_two==0)

continue;

else

mutation_temp_data=cross_over_pop_final(i,mutation_temp_one);

cross_over_pop_final(i,mutation_temp_one)=cross_over_pop_final(i,mutation_temp_two);

cross_over_pop_final(i,mutation_temp_two)=mutation_temp_data;

end

i=i+5;

end

i=0;

actual_pop=cross_over_pop_final;%the most important statement for my code

end

f=figure(‘Position’,[50 100 1000 600]);

cnames = {‘1′,’2′,’3′,’4′,’5′,’6′,’7′,’8′,’9′,’10’,’11’,’12’};

rnames = {‘solution’,’solution’,’solution’,’solution’,’solution’,’solution’,’solution’,’solution’,’solution’,…

‘solution’,’solution’,’solution’,’solution’,’solution’,’solution’,’solution’,’solution’,’solution’,’solution’,…

‘solution’,’solution’,’solution’,’solution’,’solution’,’solution’,’solution’,’solution’,’solution’,’solution’,…

‘solution’,’solution’,’solution’,’solution’,’solution’,’solution’,’solution’,’solution’,’solution’,’solution’,…

‘solution’,’solution’,’solution’,’solution’,’solution’,’solution’,’solution’,’solution’,’solution’,…

‘solution’,’solution’,’solution’,’solution’,’solution’,’solution’,’solution’,’solution’,’solution’,…

‘solution’,’solution’,’solution’,’solution’,’solution’,’solution’,’solution’,’solution’,’solution’,…

‘solution’,’solution’,’solution’,’solution’,’solution’,’solution’,’solution’,’solution’,’solution’,…

‘solution’,’solution’,’solution’,’solution’,’solution’,’solution’,’solution’,’solution’,’solution’,…

‘solution’,’solution’,’solution’,’solution’,’solution’,’solution’,’solution’,’solution’,’solution’,…

‘solution’,’solution’,’solution’,’solution’};

t = uitable(‘Parent’,f,’Data’,solution,’ColumnName’,cnames,…

‘RowName’,rnames,’Position’,[10 100 1000 500]);

 
 

با تغییر جمعیت به ۱۰۰ و تکرار به ۵۰:

به ۳ جواب بهینه رسیدیم:

با اجرای کد زیر ۹۲ کروموزوم به عنوان خروجی برگردانده می شود یعنی ۸ وزیر ۹۲ جواب دارد که ۱۲ جواب آن منحصر به‌فرد است یعنی بقیه جواب‌ها از تقارن جواب‌های اصلی به‌دست می‌آید.


function queen

clc;

counter = 0;

n = 8;

board = zeros(1,n);

[board,counter] = back(1, board,counter);

fprintf(‘Solution count: %d\n’,counter);

%%

function value =  isSolution(board)

for  i = 1:length(board)

for  j = (i+1): length(board)

if abs(board(i) – board(j)) == abs(i-j)

value = false;

return;

end

end

end

value = true;

%%

function [board,counter] =  back(depth, board,counter)

if  (depth == length(board)+1) && isSolution(board)

counter = counter + 1;

disp(board);

end

if ( depth <= length(board))

for  i = 1:length(board)

if ~any(board==i)

board(1,depth) = i;

[~,counter] = back(depth+1, board,counter);

end

end

end

 

بخشی از جواب ها بصورت زیر است:

۱     ۵     ۸     ۶     ۳     ۷     ۲     ۴

۱     ۶     ۸     ۳     ۷     ۴     ۲     ۵

۱     ۷     ۴     ۶     ۸     ۲     ۵     ۳

۱     ۷     ۵     ۸     ۲     ۴     ۶     ۳

۲     ۴     ۶     ۸     ۳     ۱     ۷     ۵

۲     ۷     ۵     ۸     ۱     ۴     ۶     ۳

۲     ۸     ۶     ۱     ۳     ۵     ۷     ۴

۳     ۱     ۷     ۵     ۸     ۲     ۴     ۶

۳     ۵     ۲     ۸     ۱     ۷     ۴     ۶

۳     ۵     ۲     ۸     ۶     ۴     ۷     ۱

۳     ۵     ۷     ۱     ۴     ۲     ۸     ۶

۳     ۵     ۸     ۴     ۱     ۷     ۲     ۶

۳     ۶     ۲     ۵     ۸     ۱     ۷     ۴

۳     ۶     ۲     ۷     ۱     ۴     ۸     ۵

۳     ۶     ۲     ۷     ۵     ۱     ۸     ۴

۳     ۶     ۴     ۱     ۸     ۵     ۷     ۲

۳     ۶     ۴     ۲     ۸     ۵     ۷     ۱

۳     ۶     ۸     ۱     ۴     ۷     ۵     ۲

۳     ۶     ۸     ۱     ۵     ۷     ۲     ۴

۳     ۶     ۸     ۲     ۴     ۱     ۷     ۵

۳     ۷     ۲     ۸     ۵     ۱     ۴

Solution count: 92

منبع

مسئله چند وزیر قسمت 1
مسئله چند وزیر قسمت 2
مسئله چند وزیر قسمت 3
مسئله چند وزیر قسمت 4

فانکش استفاده از میوتیشن برای نسل فعلی:

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

همان طور که گفته شد ژن عددی از ۰ تا ۷ است که به معنی شماره سطری است که وزیر در آن قرار گرفته است. موقعیت ژن در یک کروموزوم به معنی شماره ستون قرار گیری وزیر است. مشخص کردن مکان قرار گیری هر وزیر را باید حتما در هر سطر و ستون مشخص کرد.

کروموزوم نیز مجموعه ای از ۸ ژن است. و این طور فرض می شود که هیچ ژنی در یک کروموزوم دوبار تکرار نشود. برای مثال اگر کروموزوم ما ۰|۱|۴|۲|۳|۶|۷|۵ باشد یعنی ۸ وزیر در خانه های زیر از ماتریس قرار گرفته اند.

(۰,۰), (۱,۱), (۲,۴), (۳,۲), (۴,۳), (۵,۶), (۶,۷), (۷,۵)

در اینجا میوتیشن با swap کردن ژنی که باید mutate شود با یک ژن تصادفی (به جز ژنی که می خواهیم میوتیشن را روی آن انجام دهیم) از همان کروموزوم انجام می شود.

در crossover ژن ها از کروموزوم های دو والدین با احتمال ۰٫۵ گرفته می شود. یک ژن از یکی از والدین گرفت می شود و به کروموزوم فرزند اضافه می شود. ژنی که تولید می شود در پرنت دیگر پاک می شود. این مرحله انقدر ادامه می یابد تا کروموزوم های پدر و مادر هر دو، خالی شود و فرزند آنها همه ژن ها را داشته باشد.

تابع فیتنس: زمانی که دو وزیر طوری قرار بگیرند که یکدیگر را تهدید کنند یعنی در یک سطر، ستون یا قطر مشابه باشند. از آنجایی که کروموزوم ها ژن های تکراری ندارند بنابراین این اطمینان وجود دارد که هیچ دو وزیری در یک ستون قرار نمی گیرند. پس تنها باید برخوردهای قطری را بررسی و محاسبه کرد. بنابراین ماکزیمم تعداد برخوردها می تواند ۲۸ باشد. تابع فیتنس مقدارش هر چه بیشتر باشد بهتر است بنابراین اگر یک راه حل ۰ برخورد (تهدید دو وزیر) داشته باشد فیتنس آن ۲۸ است که با تفریق مقدار برخوردهایی که در حالت فعلی رخ می دهند از ۲۸ به دست می آید.

در کد c# مورد استفاده :

class GeneticAlgo: کلاسی است که مسئولیت همه عملیات الگوریتم ژنتیک را بر عهده دارد.

class FitnessComparator: یک کلاس مقایسه کننده است که کروموزوم ها را با fitness value مرتب می کند تا جمعیت نهایی را در جدول نشان دهد. بیشترین فیتنس در بالای جدول قرار می گیرد و کمترین آنها در پایین جدول.

struct Chromosome: ساختاری است که کروموزومی که حاوی ژنهااست، فیتنس و مجموع میانگین فیتنس ها را نشان می دهد.

class MainFrame: این کلاس موظف به کنترل اینترفیس کاربر و ایجاد جمعیت اولیه به منظور انتقال آن به الگوریتم ژنتیک است.

class Board: این کلاس گرافیک و عملیات صفحه شطرنج را بر عهده دارد.

متغیر private const int MAX_FIT = ۲۸ بیشترین مقدار فیتنس را دارد.

توابع:


private List<chromosome> GetInitialPopulation(int population)

{

List<chromosome> initPop = new List<chromosome>();

GeneticAlgo RandomGen = new GeneticAlgo();

for (int i = 0; i < population; i++)

{

List<int> genes = new List<int>(new int[] {0, 1, 2, 3, 4, 5, 6, 7});

Chromosome chromosome = new Chromosome();

chromosome.genes = new int[8];

for (int j = 0; j < 8; j++)

{

int geneIndex = (int)(RandomGen.GetRandomVal

(۰,genes.Count-1)+0.5);//randomly select a gene

chromosome.genes[j] = genes[geneIndex];

genes.RemoveAt(geneIndex);//remove selected gene

}

initPop.Add(chromosome);

}

return initPop;

}

 

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


public void DoMating(ref List<Chromosome> initPopulation,

int generations, double probCrossver, double probMutation)

{

int totalFitness = 0;

CalcFitness(ref initPopulation, ref totalFitness);

for (int generation = 0; generation < generations; generation++)

{

PrepareRuletteWheel(ref initPopulation,totalFitness);

Crossover(ref initPopulation, probCrossver);

Mutate(ref initPopulation, probMutation);

CalcFitness(ref initPopulation, ref totalFitness);

if (initPopulation[initPopulation.Count – 1].fitness == 28)

break;

if (progress != null)

{

progress(generation + 1);

}

}

initPopulation.Sort(new FitnessComparator());

}
 

این تابع لیست کروموزوم ها را به عنوان جمعیت اولیه ، تعداد نسل هایی که می خواهیم در الگوریتم پخش شوند، احتمال crossover و احتمال mutation را به عنوان پارامتر می گیرد. مسئولیت این تابع هندل کردن پخش جمعیت به نسل مورد نیاز با فراخوانی توابع CalcFitness،PrepareRuletteWheel،CrossoverوMutate است.

 

public void CalcFitness(ref List<Chromosome> chromosome, ref int totalFitness)

{

int collisions = 0;

totalFitness = 0;

for (int k = 0; k < chromosome.Count; k++)

{

for (int i = 0; i < chromosome[k].genes.Length – 1; i++)

{

int x = i;

int y = chromosome[k].genes[i];

for (int j = i + 1; j < chromosome[k].genes.Length; j++)

{

if (Math.Abs(j – x) == Math.Abs

(chromosome[k].genes[j] – y))

collisions++;

}

}

Chromosome temp = chromosome[k];

temp.fitness = MAX_FIT – collisions;

chromosome[k] = temp;

totalFitness += chromosome[k].fitness;

collisions = 0;

}

}

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


private void PrepareRuletteWheel(ref List<Chromosome> parents,int total)

{

int currentTotalFitness=0;

for (int i = 0; i < parents.Count; i++)

{

currentTotalFitness += parents[i].fitness;

Chromosome temp = parents[i];

temp.cumAvgFitness = currentTotalFitness / (double)total;

parents[i] = temp;

}

}

rulette wheel که بر مبنای فیتنس کروموزوم است برای انتخاب والدین برای جفت گیری برای ایجاد نسل جدید استفاده می شود. این تابع مسئول آماده سازی rulette wheel بوده و لیستی از کروموزوم ها را به عنوان جمعیت فعلی و فیتنس کلی جمعیت می گیرد. این تابع نرخ فیتنس هر کروموزوم تا فیتنس کلی را محاسبه می کند سپس مجموع آن را برای اختصاص به مشخصه cumAvgFitness  کروموزوم محاسبه می کند.

با تابع RuletteWheel می توان احتمال انتخاب را بر اساس نرخ فیتنس تعیین کرد. با این روش کروموزم هایی با fitness value بالاتر احتمال بیشتری برای انتخاب در ساخت نسل بعدی دارند در حالی که کروموزم هایی با fitness value پایین تر با احتمال کمتری شرکت داده می شوند


public void Crossover(ref List<Chromosome> parents, double probability)

{

List<Chromosome> offspring = new List<Chromosome>();

for (int i = 0; i < parents.Count; i++)

{

if (Assay(probability)) //if the chance is to crossover

{

Chromosome parentX = AssayRuletteWheel(parents);

Chromosome parentY = AssayRuletteWheel(parents);

List<int> child = new List<int>();

for (int j = 0; j < 8; j++)

{

if (Assay(0.5)) //select from parentX

{

for (int k = 0; k < parentX.genes.Length; k++)

{

if (!child.Contains

(parentX.genes[k]))//instead of

//deleting the similar genes

//from parents select the

//next non-contained number

{

child.Add(parentX.genes[k]);

break;

}

}

}

else //select from parentY

{

for (int k = 0; k < parentY.genes.Length; k++)

{

if (!child.Contains

(parentY.genes[k]))//instead of

//deleting the similar genes from

//parents select the next

//non-contained number

{

child.Add(parentY.genes[k]);

break;

}

}

}

}

Chromosome offSpr = new Chromosome();

offSpr.genes = child.ToArray();

offspring.Add(offSpr);

}

else //else the chance is to clone

{

Chromosome parentX = AssayRuletteWheel(parents);

offspring.Add(parentX);

}

}

while (offspring.Count > parents.Count)

{

offspring.RemoveAt((int)GetRandomVal(0, offspring.Count – 1));

}

parents = offspring;

}

 

تابع فوق مسئول انجام عمل cross over است. تابع لیستی از کروموزم ها را به عنوان جمعیت فعلی و احتمال crossover را به عنوان پارامتر می گیرد. تابع Assay(int probability) با احتمال داده شده true بر می گرداند بنابراین با احتمال crossover برای تعیین اینکه عملیات crossover است یا cloning استفاده می شود.

if (Assay(probability)) //if the chance is to crossover

{

Chromosome parentX = AssayRuletteWheel(parents);

Chromosome parentY = AssayRuletteWheel(parents);

List<int> child = new List<int>();

for (int j = 0; j < 8; j++)

{

if (Assay(0.5)) //select from parentX

{

for (int k = 0; k < parentX.genes.Length; k++)

{

if (!child.Contains(parentX.genes[k]))//instead of

//deleting the similar genes from parents

//select the next non-contained number

{

child.Add(parentX.genes[k]);

break;

}

}

}

else //select from parentY

{

for (int k = 0; k < parentY.genes.Length; k++)

{

if (!child.Contains(parentY.genes[k]))//instead of

//deleting the similar genes from parents

//select the next non-contained number

{

child.Add(parentY.genes[k]);

break;

}

}

}

}

Chromosome offSpr = new Chromosome();

offSpr.genes = child.ToArray();

offspring.Add(offSpr);

}

این بخش از کد مسئول crossover دو پرنت parentX  و parentY می باشد. به منظور ایجاد فرزند، ژنها از دو والدین با احتمال ۰٫۵ انتخاب می شوند در حالیکه از تکرار ژنها در کروموزوم ها اجتناب می شود. در عملیات cloning یکی از والدین مستقیما به نسل بعدی آورده می شود.


public void Mutate(ref List&amp;lt;Chromosome&amp;gt; parents, double probability)

{

List&amp;lt;Chromosome&amp;gt; offsprings = new List&amp;lt;Chromosome&amp;gt;();

for (int i = 0; i &amp;lt; parents.Count; i++)

{

Chromosome offspring = parents[i];

for (int mutatePosition = 0; mutatePosition &amp;lt; 8; mutatePosition++)

{

if (Assay(probability)) //if the chance is to mutate

{

int newGeneIndex = (int)(GetRandomVal(0,6)+0.5);

if (newGeneIndex&amp;gt;=mutatePosition)

{

newGeneIndex += 1;

}

int swapTemp = offspring.genes[mutatePosition];

offspring.genes[mutatePosition] =

offspring.genes[newGeneIndex];

offspring.genes[newGeneIndex] = swapTemp;

}

}

offsprings.Add(offspring);

}

parents = offsprings;

}
 

این تابع اپراتور mutation را با احتمال داده شده استفاده می کند. این تابع تغییر میوتیش را در حین انتقال ژن ها در جمعیت فعلی بررسی می کند. اگر باید برای ژنی از میوتیشن استفاده شود آنگاه مقدار آن با یک ژنی که بصورت تصادفی انتخاب شده در همین کروموزوم (ژنی به جز خود ژنی که می خواهیم روی آن میوتیشن انجام دهیم)  swap می شود.

زمانی که به یک راه حل می رسیم آرایه ژن های کروموزومی که شامل راه حل هستند را میتوان به پراپرتی به نام Genes  در کلاس Board اختصاص داد.

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

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

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

این سوال ها سالها مطرح بوده است که بین crossover و mutation کدامیک بهتر است؟ کدامیک لازم است؟ کدامیک اصلی است؟ پاسخی که تاکنون بیشتر از بقیه پاسخها مورد قبول بوده این است که هر کدام نقش مخصوص خود را دارد. در حالت کلی بهتر است از هر دو استفاده شود. میتوان الگوریتمی داشت که فقط از mutation استفاده کند ولی الگوریتمی که فقط ازcrossover   استفاده کند کار نخواهد کرد. Crossover خاصیت جستجوگرانه و یا explorative دارد. میتواند با انجام پرشهای بزرگ به محل هائی دربین والدین رفته و نواحی جدیدی را کشف نماید. Mutation خاصیت گسترشی و یا  exploitive  دارد. میتواند با انجام تغییرات کوچک تصادفی به نواحی کشف شده وسعت ببخشد.  Crossoverاطلاعات والدین را ترکیب میکند درحالیکه mutation  میتواند اطلاعات جدیدی اضافه نماید. رسیدن به یک پاسخ بهینه در mutation شانسی است.

نتایج اجرای این الگوریتم نشان می دهد که جمعیت عامل بسیاری مهمی بوده و تاثیر زیادی دارد و crossover probability و mutation rate تاثیر غیر قابل انکاری بر اجرای الگوریتم ژنتیک دارند زیرا با هر بار تغییر در هر یک از این پارامترها نتایج به شدت تغییر می کند. در حقیقت نحوه انتخاب اپراتورهای GA یک تریدآف بین همگرایی سریع تر و حفظ قابلیت اکتشافی بودن الگوریتم (برای جلوگیری از همگرایی اشتباه) است. Crossover پارامتری است که به تنظیم رفتار الگوریتم ژنتیک کمک می کند. کم کردن احتمال crossover باعث می شود در نسل بعدی افراد بیشتری بدون تغییر باقی بمانند. بسته به مسئله کاهش یا افزایش مقدار احتمال crossover می تواند تاثیر مثبت یا منفی داشته باشد.

پس از اجراهای متوالی الگوریتم می توان دید که هیچ جوابی وجود ندارد گه به طور قطع بتوان گفت از بقیه بهتر است و بتوان گفت که مقدار تنظیم شده برای پارامترهای الگوریتم ژنتیک در این حالت از همه بهتر است. این بهترین مقادیر به عوامل زیادی وابسته هستند. برای مثال اگر الگوریتم شما generational است میخواهید احتمالی را برای این در نظر بگیرید که برخی از والدین بدون تغییر باقی بمانند. در غیر اینصورت برخی راه حل های خوب را از دست خواهید داد. بنابراین بهتر است crossover rate را نزدیک به ۰٫۷ تنظیم کرد. برخی از الگوریتم ها نیز هستند که به طور کامل به mutation وابسته اند و برای آنها crossover rate مساوی با ۰ در نظر گرفته می شود. اگر crossover probability برابر با ۱۰۰درصد باشد همه فرزندان توسط crossover ایجاد می شوند. اگر ۰ درصد باشد همه نسل جدید کپی دقیقی از کروموزوم فعلی جمعیت قدیمی است ولی به این معنی نیست که نسل جدید دقیقا همان نسل قبلی است.

انتخاب اپراتورهای الگوریتم توازنی میان سرعت و دقت همگرایی است یعنی exploration در مقابل exploitation.

اینطور که گفته شده بهتر است mutation بین ۰٫۰۱۵ تا ۰٫۰۲ باشد. چرا؟

Exploration یعنی جستجوی فضای حالت در حد امکان در حالی که exploitation یعنی تمرکز بر یک نقطه که امیدواریم global optimum باشد.

در GA اپراتورهای mutation اغلب برای exploration و اپراتور های Crossover اغلب برای exploitation یعنی هدایت جمعیت به سوی همگرایی به یک راه حل خوب استفاده می شوند. در نتیجه وقتی Crossover سعی در همگرایی به یک نقطه مشخص دارد mutation سعی خود را می کند که همگرایی صورت نگیرد و فضای بیشتری کاوش شود.

در ابتدای فرایند جستجو ترجیح ما بر این است که جستجوی بیشتری به منظور اکتشاف فضا صورت گیرد. از طرف دیگر در انتهای فرایند جستجو exploitations بیشتری ترجیح داده می شود که همگرایی جمعیت به سمت global optimum تضمین شود. تنها یک استثناء وجود دارد؛ زمانی که جمعیت به سمت بهینه محلی همگرا می شود اگر بتوانیم باید پراکندگی حمیت را افزایش دهیم تا فضای بیشتری جستجو شود و در دام بهینه محلی نیفتد. با توجه به این نکته mutation rate بالا باعث افزایش احتمال جستجوی فضای بیشتری از فضای جستجو می شود با این حال از همگرایی جمعیت به یک جواب بهینه جلوگیری می کند. از طرف دیگر اگر mutation rate خیلی کوچک باشد باعث همگرایی زودهنگام و نارس می شود و به حای رسیدن به global optimum در دام بهینه محلی گرفتار می شود.مقداری که انتخاب می شود به ماهیت مسئله و نحوه پیاده سازی الگوریتم بستگی دارد. پس mutation rate های بسیار بالا از همگرایی الگوریتم جلوگیری کرده و رسیدن به راه حل بهینه را تضمین نمی کنند. بنابراین عاقلانه تر این است که از mutation rate های کوچک تر استفاده شود. مقدار کوچک برای mutation rate تضمین می کند که میوتیشن های زیادی در آن واحد اتفاق نیفتد ولی این نیز به تعداد ژن های موجود در هر کروموزوم از جمعیت بستگی دارد. بهتر این است که با مقادیر کم شروع کرده و به تدریج آنها را افزایش داد و کارایی هر یک را بررسی کرد مثلا به ترتیب: ۰٫۰۰۱، ۰٫۰۱، ۰٫۰۵، ۰٫۱، ۰٫۲ و … . در رابطه با جستجو در فضای حالت در مقایسه با mutation rate بالاتر، جمعیت بزرگتر ترجیح داده می شود.

در مقابل استفاده از mutation rate مناسب منجر به رسیدن سریع به نتایج خوب می شود و استفاده از mutation rate های بیش از حد کوچک فرایند را بسیار کند می کند زیرا کوناگونی را کم کرده و در نهایت ممکن است حتی همگرایی به درستی صورت نگیرد. mutation rate های بسیار بزرگ نیز همگرا شدن را بسیار سخت می کنند زیرا باعث می شوند جواب صحیح به راحتی از دست برود. بهترین راه تغییر تدریجی mutation rate است. مثلا به عنوان راه حل دیگر می توان با mutation rate های بزرگ شروع کرد تا گوناگونی بیشتری تزریق کرده از افتادن در دام بهینه محلی جلوگیری کرد سپس با انتها رسیدن الگوریتم یعنی تکرار آخر، این مقدار را کاهش داده و بهترین راهکار پیدا شود.

Exploitation = (crossover +  انتخاب بر اساس فیتنس) ما را به جواب بهینه نهایی می رساند.

این طور گفته می شود که اندازه جمعیت کوچکتر سرعت همگرایی بیشتری به الگوریتم می دهد ولی الگوریتم راحتتر در بهینه محلی گرفتار می شود. احتیاط بر این است که از جمعیت های بیش از حد کوچک استفاده نشود. معمولا به احتمال crossover و mutation بسیار بزرگ نیاز نخواهید داشت و جمعیتی با اندازه متوسط مناسب است.

است.
مسئله چند وزیر قسمت 1
مسئله چند وزیر قسمت 2
مسئله چند وزیر قسمت 3
مسئله چند وزیر قسمت 4

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

  • نحوه نمایش مسئله:

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

برای نمایش مسئله در کروموزوم‌ها از این ویژگی استفاده کرده و به صورت زیر عمل می‌کنیم:

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

۸ , ۷ , ۶ , ۵ , ۴ , ۳ , ۲ , ۱

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

  • تولید جمعیت اولیه:

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

برای محاسبه میزان بهینگی جواب تعداد جفت وزیرهایی را که به هم گارد می‌دهند، محاسبه می‌کنیم. برای مسئله ۸ وزیر در بدترین حالت هر وزیر با همه وزیرهای دیگر گارد می‌دهد (فرض کنید همه وزیرها در یک سطر قرار گیرند). در این حالت حداکثر تعداد جفت وزیرهایی که به همگدیکر کارد می‌دهند ۲۸ جفت است:

۷ + ۶ + ۵ + ۴ +۳ + ۲ + ۱

در حالت کلی برای مسئله n وزیر حداکثر تعداد جفت وزیرهایی که به همدیگر گارد می‌دهند به صورت زیر محاسبه می‌شود:

۱+ ۲ +.. +(n-۱) = (n * (n-۱)) /۲
  • برای محاسبه میزان بهینگی هر کروموزوم از فرمول زیر استفاده می‌کنیم:
Fitness[i] =1 – (Guard(chromosome[i])) / MaxGuards
  • حداکثر تعداد گاردها:
MaxGuards
  • تعداد جفت وزیرهایی که در کروموزوم ام همدیگر را گارد می‌دهند:
 Guard(chromosome[i])

 

منبع

 


پیاده سازی الگوریتم ۸ وزیر با استفاده از الگوریتم ژنتیک

راهکاری که برای حل یک مسئله با الگوریتم ژنتیک استفاده می شود تکامل می یابد. الگوریتم ژنتیک مثل هر الگوریتم بهینه سازی دیگر با تعریف متغیرهای بهینه سازی آغاز می شود و مانند الگوریتم های بهنیه سازی دیگر نیز خاتمه می یابد یعنی با تست همگرایی.

یک الگوریتم GA دارای پارامترهای زیر است:

  • : Fitnessتابعی برای ارزیابی یک فرضیه  که مقداری عددی به هر فرضیه نسبت میدهد
  • : Fitness_threshold مقدار آستانه که شرط پایان را معین میکند
  • : population تعداد فرضیه هائی که باید در جمعیت در نظر گرفته شوند
  • : crossover rate  در صدی از جمعیت که در هر مرحله توسط الگوریتم crossover  جایگزین میشوند
  • :mutation rate  نرخ mutation

الگوریتم GA  به صورت زیر کار می کند:

  • : Initializeجمعیت را با تعداد population فرضیه بطور تصادفی مقدار دهی اولیه کنید.
  • : Evaluateبرای هر فرضیه h در population مقدار تابع Fitness(h) را محاسبه نمائید.
  • تا زمانیکه[maxh Fitness(h)] < Fitness_threshold یک جمعیت جدید ایجاد  کنید.
  • فرضیه ای که دارای بیشترین مقدار Fitness است را برگردانید.

روش های مختلف crossover:

Single-point crossover

  • یک نقطه تصادفی در طول رشته انتخاب میشود.
  • والدین در این نقطه به دوقسمت میشوند.
  • هر فرزند با انتخاب تکه اول از یکی از والدین و تکه دوم از والد دیگر بوجود میاید.

روشهای دیگر Crossover

در crossover یکنواخت بیتها بصورت یکنواخت از والدین انتخاب می شوند.

اپراتورهای ژنتیکی Mutation :

  • اپراتور mutation برای بوجود آوردن فرزند فقط از یک والد استفاده میکند. اینکار با انجام تغییرات کوچکی در رشته اولیه  بوقوع میپیوندد.
  • با استفاده از یک توزیع یکنواخت یک بیت بصورت تصادفی اتنخاب و مقدار آن تغییر پیدا میکند.
  • معمولا mutation بعد از انجام crossover اعمال میشود.

تابع fitness  معیاری برای رتبه بندی فرضیه هاست که کمک میکند تا فرضیه های برتر برای نسل بعدی جمعیت انتخاب شوند. نحوه انتخاب این تابع بسته به کاربر مورد نظر دارد

در روش معرفی شده در الگوریتم ساده GA احتمال انتخاب یک فرضیه برای استفاده در جمعیت بعدی بستگی به نسبت fitness  آن به fitness  بقیه اعضا دارد. این روش Roulette Wheel selectionنامیده میشود.

روش جستجوی GA با روشهای دیگر مثل شبکه های عصبی تفاوت دارد:

در شبکه عصبی روش Gradient descent بصورت  هموار از فرضیه ای به فرضیه  مشابه دیگری حرکت میکند در حالیکه GA  ممکن است بصورت ناگهانی فرضیه والد را با فرزندی جایگزین نماید که تفاوت اساسی با والد آن داشته باشد.از اینرو احتمال گیر افتادن GA در مینیمم محلی کاهش می یابد. با این وجود GA با مشکل دیگری روبروست که crowding  نامیده میشود crowding پدیده ای  است که در آن  عضوی که سازگاری بسیاربیشتری از بقیه افراد جمعیت دارد بطور مرتب تولید نسل کرده و با تولید اعضای مشابه درصد عمده ای از جمعیت را اشغال میکند. راه حل رفع مشکل Crowdingاستفاده از ranking  برای انتخاب نمونه ها است، با اختصاص رتبه به فرضیه ای که بسیار بهتر از بقیه عمل میکند.

مسئله ۸ وزیر:

بدین ترتیب دیدیم که مسیر میان اجزای الگوریتم ژنتیک به ترتیب زیر است:

  1. تعریف توابع و متغیرها
  2. تولید جمعیت اولیه
  3. دیکد کردن کروموزوم ها
  4. پیدا کردن هزینه برای هر کروموزوم
  5. انتخاب جفت ها
  6. جفت گیری
  7. میوتیشن
  8. بررسی همگرایی
  9. خاتمه یا بازگشت به مرحله دیکد کردن کروموزوم ها

ژن عددی از ۰ تا n-1 است در ۸ وزیر n برابر با ۸ است بنابراین ژن عددی از ۰ تا ۷ می شود و کروموزوم آرایه ای از ژن هاست. که می تواند پاسخ مسئله باشد.

جمعیت هر نسل می تواند  تعداد کروموزوم ها را تعیین کند.

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

برای پیدا کردن هزینه مربوط به هر کروموزوم یک تابع هزینه تعریف می شود. نتیجه تابع هزینه یک cost value است که در نهایت میانگین cost valueهای هر نسل به نتیجه مطلوب نزدیک می شود.

کروموزوم هایی که فیتنس بالاتری (هزینه پایین تر) دارند برای تولید نسل بعدی استفاده می شوند.

در فرایند cross over فرزندان توسط والدین تولید می شوند که ترکیب آنها شامل ترکیب ژن های آنهاست. اگر نسل جدید حاوی کروموزومی باشد که نزدیک یا برابر با نتایج مطلوب باشد آنگاه مسئله حل شده است. در غیر اینصورت فرایند قبلی در نسل جدید هم پیاده سازی می شود مانند فرایندی که برای والدین آنها اتفاق افتاد. تا زمانی که به راه حل مناسب برسیم این روال ادامه دارد.

در شطرنج وزیر می تواند هر طور که مایل بود حرکت کند افقی عمودی یا در قطر. صفحه شطرنج ۸ در ۸ است یعنی ۸ سطر و ۸ ستون دارد . در مسئله ۸ وریز استاندارد به دنبال این هستیم که چگونه ۸ وزیر در خانه های جدول به گونه ای قرار بگیرند که هیچ یک دیگری را تهدید نکنند. در اینجا با الگوریتم ژنتیک این کار را انجام می دهیم.

برای تولید فرزندان از والیدن نیاز به crossover داریم که تصمیم می گیرد از دو والدین کدام ژن باید انتخاب شود.

 

مسئله چند وزیر قسمت 1
مسئله چند وزیر قسمت 2
مسئله چند وزیر قسمت 3
مسئله چند وزیر قسمت 4

مسئله چند وزیر یک معمای شطرنجی و ریاضیاتی است که بر اساس آن باید n وزیر شطرنج در یک صفحه n×n شطرنج به‌گونه‌ای قرار داده شوند که هیچ‌یک زیر ضرب دیگری نباشند. با توجه به اینکه وزیر به‌صورت افقی، عمودی و اُریب حرکت می‌کند، باید هر وزیر را در طول، عرض و قطر متفاوتی قرار داد.

اولین و مشهورترین شکل این مسئله معمای هشت وزیر است که برای حل آن باید ۸ وزیر را در یک صفحهً معمولی (۸×۸) شطرنج قرار داد. این مسئله ۹۲ جواب دارد که ۱۲ جواب آن منحصر به‌فرد است یعنی بقیه جواب‌ها از تقارن جواب‌های اصلی به‌دست می‌آید.

مسئله n وزیر در صورتی جواب دارد که n مساوی ۱ یا بیشتر از ۳ باشد. یعنی مسئله دو وزیر و سه وزیر راه حلی ندارند.

تاریخچه

این مسئله در سال ۱۸۴۸ توسط شطرنج بازی به نام Max Bezzel عنوان شد و ریاضی دانان بسیاری ازجمله Gauss و Georg Cantor بر روی این مسئله کار کرده و در نهایت آن را به n وزیر تعمیم دادند. اولین راه حل توسط Franz Nauck در سال ۱۸۵۰ ارائه شد که به همان مسئله n وزیر تعمیم داده شد. پس از آن Gunther راه حلی با استفاده از دترمینان ارائه داد که J.W.L. Glaisher آن را کامل نمود. در سال ۱۹۷۹، Edsger Dijkstra Nauck این مسئله را با استفاده از الگوریتم عقب‌گرد حل کرد.

حل مسئله

هشت وزیر را می‌توان با الگوریتم‌های مختلفی مانند تپه نوردی و روش ارضای محدودیت(csp) حل کرد که در زیر روش ارضای محدودیت را بررسی می‌کنیم. هر وزیری در هر ستونی هدفی دارد که همان مکانش در هرستون می‌شود یک گره .در کد زیر تعریف مکان‌ها را داریم:

Variables: { Q1, Q2, Q3, Q4 }

Domain: { (1, 2, 3, 4), (1, 2, 3, 4), (1, 2, 3, 4), (1, 2, 3, 4) }

Constraints: Alldifferent( Q1, Q2, Q3, Q4 ) and 
for i = 0...n and j = (i+1)...n, k = j-i, Q[i] != Q[j] + k and Q[i] != Q[j] - k

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

min-conflicts(csp, max):
initial := complete assignment ;jamiyate avaliye
for 1..max do: ;az 1 .. akharin khane
if initial is a solution: ;if jamiyate tolide javab bod 
return initial ;barmigardanad
var := nextVar() ;da ghire indorat yek motaghair be jelo
value := leastConflicts( var ) ;taeein meghdar
var := value in initial ;gharar dadan meghdar dar motaghair
return failure ;bargash be ebtedaye algoritm

صورت مسئله

هدف از مسئله n وزیر، چیدن n مهره وزیر در یک صفحه شطرنج(n*n) است، به‌طوری‌که هیچ دو وزیری یکدیگر را گارد ندهند، یعنی هیچ دو مهره‌ای نباید در یک سطر، ستون یا قطر یکسان باشند. وزیر در خانه‌های شطرنج به صورت عرضی، طولی و قطری می‌تواند حرکت کند. مسئله n وزیر از جمله مسائل NP در هوش مصنوعی است که روش‌های جستجوی معمولی قادر به حل آن‌ها نخواهد بود

شمردن تعداد جواب‌ها

جدول زیر تعداد راه حل‌ها برای قرار دادن n وزیر بر روی صفحه n × nنشان می‌دهد. هر دو منحصر به فرد و متمایز، برای تعداد ۱-۱۴،۲۴-۲۶ است.

مسئله ی چند وزیر

  • توجه:

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

روش‌های حل مسئله

الگوریتم عقبگرد

از تکنیک عقبگرد Backtracking برای حل مسائلی استفاده می‌شود که در آن‌ها دنباله‌ای از اشیاء از یک مجموعه مشخص انتخاب می‌شود، به‌طوری‌که این دنباله، ملاکی را در بر می‌گیرد. عقبگرد حالت اصلاح شدهٔ جستجوی عمقی یک درخت است. این الگوریتم همانند جستجوی عمقی است، با این تفاوت که فرزندان یک گره فقط هنگامی ملاقات می‌شوند که گره امید بخش باشد و در آن گره حلی وجود نداشته باشد. با توجه به اینکه هیچ ۲ وزیری نباید همدیگر را گارد کنند و در یک سطر نمی‌توانند باشند، تعداد کل حالت‌ها برای n=۴ برابر ۴*۴*۴*۴=۲۵۶ است. در شطرنج یک وزیر می‌تواند به مهره‌هایی که در خانه‌های عمود یا مورب به وی قرار دارند حمله کند. یا به عبارت ریاضی، اگر ردیفها و ستونهای شطرنج را از یک تا هشت شماره‌گذاری کنیم و وزیر در خانه (i، j) قرار داشته باشد، مهره‌هایی که در خانه‌های (i، m) یا (m، j) یا (i ± m، j ± m) قرار دارند توسط وزیر تهدید می‌شوند.

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

مراحل جستجو برای یافتن جواب را به این صورت دنبال می‌کنیم که: وزیر اول را در ردیف اول و ستون اول قرار می‌دهیم.

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

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

دوباره در ردیف سوم اولین خانه‌ای را میابیم که مورد تهدید دو وزیر قبلی نباشد. این بار خانه را می‌یابیم و وزیر سوم را در آن قرار می‌دهیم.

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

در ردیف دوم اولین خانه‌ای را میابیم که مورد تهدید وزیر اول نباشد و وزیر دوم را در آن خانه قرار می‌دهیم.

در ردیف سوم اولین خانه‌ای را میابیم که مورد تهدید وزیران اول و دوم نباشد و وزیر سوم را در آن خانه می‌گذاریم.

در ردیف چهارم اولین خانه‌ای را میابیم که مورد تهدید وزیران پیشین نباشد. این بار خانه را می‌یابیم و وزیر چهارم را در آن خانه قرار می‌دهیم.

به یک جواب می‌رسیم. حال اگر فرض کنیم که این خانه جواب نیست و به مسیر خود ادامه دهیم، احتمالاً” می‌توانیم جوابهای دیگری نیز بیابیم.

شبه کد پیاده‌سازی الگوریتم عقبگرد برای مسئله n وزیر

void queens (index i)
{
	index j;
	if (promising(i))
		if (i == n)
			cout &amp;amp;amp;amp;lt;&amp;amp;amp;amp;lt; col[1] through col[n];
		else
			for (j = 1; j &amp;amp;amp;amp;lt;= n; j++) {
				col[i + 1] = j;
				queens(i + 1);
			}
}
bool promising (index i)
{
	index k;
	bool Switch;
	k = 1;
	Switch = true ;
	while (k &amp;amp;amp;amp;lt; i &amp;amp;amp;amp;amp;&amp;amp;amp;amp;amp; switch) {
		if (col[i] == col[k] || abs(col[i] – col[k] == i - k))
			switch = false;
		k++;
	}
	return Switch;
}

برنامه زبان C به صورت غیر بازگشتی

# include &amp;amp;amp;amp;lt;stdio.h&amp;amp;amp;amp;gt;

int b[8];

inline static int unsafe(int y) {
        int i, t, x;
        x = b[y];
        for (i = 1; i &amp;amp;amp;amp;lt;= y; i++) {
                t = b[y - i];
                if ((t == x) ||
                     (t == x - i) ||
                     (t == x + i)) {
                        return 1;
               }
       }

        return 0;
}

static void putboard(void) {
        static int s = ۰;
        int x, y;
        printf("\n\nSolution #٪i\n", ++s);
        for (y = 0; y &amp;amp;amp;amp;lt; 8; y++) {
                for (x = 0; x &amp;amp;amp;amp;lt; 8; x++) {
                        printf((b[y] == x) ? "|Q": "|_");
               }
                printf("|\n");
       }
}

int main(void) {
        int y = ۰;
        b[۰] = -۱;
        while (y &amp;amp;amp;amp;gt;= ۰) {
                do {
                        b[y]++;
               } while ((b[y] &amp;amp;amp;amp;lt; 8) &amp;amp;amp;amp;amp;&amp;amp;amp;amp;amp; unsafe(y));
                if (b[y] &amp;amp;amp;amp;lt; 8) {
                        if (y &amp;amp;amp;amp;lt; 7) {
                                b[++y] = -۱;
                       } else {
                                putboard();
                       }
               } else {
                        y--;
               }
       }

        return 0;
}

برنامه زبان ++C به صورت بازگشتی

  • برنامه زیر برای هشت وزیر نوشته شده‌است با انتخاب اعداد دیگر به جای هشت در define MAXSIZE 8 # می‌توان برای تعداد دیگری وزیر نیز استفاده کرد.
# include &amp;amp;amp;amp;lt;assert.h&amp;amp;amp;amp;gt;
# include &amp;amp;amp;amp;lt;stdio.h&amp;amp;amp;amp;gt;

# define MAXSIZE 8
class EightQueens
{
    int m_size;				
    int m_solution_count;		
    int m_attempt_count;		
    int m_queen[MAXSIZE];		
    bool m_row_inuse[MAXSIZE]; 		
    bool m_diag_rise[MAXSIZE*2];	
    bool m_diag_fall[MAXSIZE*2];	

public:

    EightQueens(int size, bool is_alt) {

	assert(size &amp;amp;amp;amp;lt;= MAXSIZE);

	m_size = size;
	m_solution_count = 0;
	m_attempt_count = 0;

	for (int i = 0; i &amp;amp;amp;amp;lt; m_size; i++) {
	    m_queen[i] = i;
	    m_row_inuse[i] = 0;
	}

	for (int j = 0; j &amp;amp;amp;amp;lt; m_size*2; j++) {
	    m_diag_rise[j] = 0;
	    m_diag_fall[j] = 0;
	}

	if (is_alt) SearchAlt(0);
	else        Search(0);

   }

    int GetSolutionCount() {
	return m_solution_count;
   }

    int GetAttemptCount() {
	return m_attempt_count;
   }

private:

    void SearchAlt(int col){

	if (col == m_size) {
	    m_solution_count++;
	    return;
	}

	for (int row = 0; row &amp;amp;amp;amp;lt; m_size; row++) {
	    m_attempt_count++;
	    if (m_row_inuse[row] == 0 &amp;amp;amp;amp;amp;&amp;amp;amp;amp;amp; IsDiagValid(col, row)) {
		m_queen[col] = row;
		m_row_inuse[row] = 1;
		SetDiags(col, 1);
		SearchAlt(col+1);
		SetDiags(col, 0);
		m_row_inuse[row] = 0;
		m_queen[col] = -1;
	   }
	}

   }

    void Search(int col) {
	if (col == m_size) {
	    m_solution_count++;
	    return;
	}

	for (int i = col; i &amp;amp;amp;amp;lt; m_size; i++) {
	    if (SwapQueenIfDiagValid(col, i)) {
		Search(col+1);
		UnSwapQueen(col, i);
	   };
	}
   }

    void SwapQueenBasic(int i, int j) {
	    int hold = m_queen[i];
	    m_queen[i] = m_queen[j];
	    m_queen[j] = hold;
   }

    void SetDiags(int col, int val) {
	assert(m_diag_rise[m_queen[col] + col]!= val);
	       m_diag_rise[m_queen[col] + col] =  val;
	assert(m_diag_fall[m_queen[col] - col + m_size]!= val);
	       m_diag_fall[m_queen[col] - col + m_size] =  val;
   }

    bool IsDiagValid(int col, int row) {
	return (m_diag_rise[row + col] == 0 &amp;amp;amp;amp;amp;&amp;amp;amp;amp;amp;
		m_diag_fall[row - col + m_size] == 0);
   }

    bool SwapQueenIfDiagValid(int i, int j) {
	m_attempt_count++;
	if (IsDiagValid(i, m_queen[j])) {
	    SwapQueenBasic(i, j);
	    SetDiags(i, 1);
            return true;
	}
        return false;
   }

    void UnSwapQueen(int i, int j) {
	SetDiags(i, 0);
	SwapQueenBasic(i, j);
   }

};

void
do_work(bool is_alt)
{
    int size = 8;

    EightQueens puzzle(size, is_alt);
    int soln = puzzle.GetSolutionCount();
    int attempt = puzzle.GetAttemptCount();
    assert(size!= 8 || soln == 92);
    const char* style = is_alt ? "cartesian": "permutation";
    printf("EightQueens[%d] has %d solutions found in %5d attempts using %s search. \n", size, soln, attempt, style);
}

int main()
{
    printf("We should have 92 solutions for 8x8. \n");
    do_work(0);
    do_work(1);
}

انیمیشن روش بازگشتی

 

مسئله چند وزیر

 

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

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

شبه کد پیاده‌سازی الگوریتم مونت کارلو برای الگوریتم عقبگرد مسئله n وزیر

  int ostimate _ n_ queens (int n)
   {
          index i , j , col [1..n];
          int m , mprod , numnodes ;
          set _of_ index  prom _children;
          i = ۰;
          numnodes =۱ ;
          m = ۱;

        mprod  = ۱ ;
        while  (m!= 0 &amp;amp;amp;amp;amp;&amp;amp;amp;amp;amp; i!= n) {
        mprod = mprod * m ;
        numnodes  = numnodes + mprod * n;
        i ++;
        m = ۰ ;
        prom_childern  = Ø;
        for (j = 1 ; j ≤ n ; j++;) {
                col [i]  = j ;
                if (promising(i)) {

         m++;
         prom_children = prom _ children U {i};
                }
            }
             if (m!= ۰)  {
                 j = random selection from prom _childeren;
                 col [i];
             }
        }
         return numnodes;
     }

روش مکاشفه‌ای

برای حل این مسئله که دارای ۹۲ جواب است، باید تکنیکهایی جهت کاهش حالات، روش Brute Force یا امتحان تک تک جواب‌ها انجام شود. تعداد همه حالاتی که می‌تواند در روش Brute Force چک شود برابر ۱۶٬۷۷۷٬۲۱۶ یا هشت به توان هشت است! یکی از روش‌های حل این مسئله برای n>=4 یا n=1 استفاده از روش مکاشفه‌ای ( heuristic)است:

1- عدد n را بر عدد ۱۲ تقسیم کن و باقی‌مانده را یادداشت کن

۲- به ترتیب اعداد زوج ۲ تا n را در لیستی بنویس

۳- اگر باقی‌مانده ۳ یا ۹ بود، عدد ۲ را به انتهای لیست انتقال بده.

۴- به لیست اعداد فرد ۱ تا n را به ترتیب اضافه کن، اما اگر باقی‌مانده ۸ بود اعداد را دو به دو باهم عوض کند (مثلاً ۱و۳و۵و۷و۹ تبدیل به ۳و۱و۷و۵و۹ میشه)

۵- اگر باقی‌مانده ۲ بود جای ۱ و۳ را با هم عوض کن و ۵ را به انتهای لیست ببر.

۶- اگر باقی‌مانده ۳ یا ۹ بود، اعداد ۱ و ۳ را به انتهای لیست ببر.

۷- حال با استفاده از لیست بدست آمده وزیرها در صفحه شطرنج چیده می‌شوند، به‌طوری‌که جای وزیر ستون اول، اولین عدد لیست، جای وزیر ستون دوم، دومین عدد لیست و…

این الگوریتم یک راه حل برای حل این مسئله‌است، برای بدست آوردن همه حالات از روش‌های دیگری می‌توان استفاده کرد. روش حل مسئله ۱۲ راه حل یکتا دارد که با در نظرگیری تقارن و چرخش به ۹۲ حالت قابل تبدیل است.

روش‌های جستجوی محلی

می‌توان به مسئله ۸ وزیر به عنوان یک مسئله بهینه‌سازی نیز نگریست که در آن هدف بهینه کردن تعداد گاردهای جفت وزیرها می‌باشد.

به عنوان مثال فرض کنید در صفحه شطرنج معمولی، ۸ وزیر را به دو روش زیر قرار دهیم:

مسئله ی چند وزیرمسئله ی چند وزیر

در روش چینش سمت چپ ۳ وزیر و در روش چینش سمت راست ۴ وزیر همدیگر را گارد می‌دهند. بنابراین روش چینش قبلی بهینه تر از روش چینش فعلی است. در واقع می‌توان مسئله بهینه‌سازی را به صورت زیر تعریف کرد. فرض کنید S مجموعه همه جواب‌های ممکن برای مسئله باشد. در صورتی S* می‌تواند جواب مسئله باشد که به ازای همه جواب‌های موجود در S، S* بهینه تر از دیگر جواب‌ها باشد. در مسئله ۸ وزیر دیدیم که جوابی بهینه‌است که تعداد گاردهای جفت وزیر آن کمتر باشد.

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

نحوه پیاده‌سازی و طراحی الگوریتم برای انتخاب حالت هسایه در این روش‌های جستجو از اهمیت ویژه‌ای برخوردار است. به عنوان مثال برای مسئله ۸ وزیر می‌توان به شکل‌های زیر حالت‌های همسایگی را تولید کرد:

۱) دو وزیر به تصادف انتخاب شده و جای آن دو باهم عوض گردد.

۲) یکی از وزیرها به تصادف انتخاب شده و شماره سطر آن به تصادف تغییر کند.

۳) ویزیری به تصادف انتخاب شده و یک خانه به سمت بالا یا پایین حرکت کند

مسئله چند وزیر قسمت 1
مسئله چند وزیر قسمت 2
مسئله چند وزیر قسمت 3
مسئله چند وزیر قسمت 4

9.آشکار سازی صورت با استفاده فیلترهای گابور و شبکه های عصبی

ﭼﻜﻴﺪه: در این مقاله، روشی قدرتمند برای آشکارسازی صورت از زوایای مختلف با استفاده از ترکیب فیلترهای گابور و شبکه ی عصبی بیان می شود. در ابتدا رابطه ی ریاضی تولید فیلتر گابور ورد بررسی قرار می گیرد و در مرحله بعد با برسسی 75 بانک فیلتر مختلف، محدوده مقادیر پارامترهای مؤثر در تولید فیلتر گابور مشخص شده و سپس بهترین مقدار برای آنها به دست می آید. شبکه ی عصبی مورد استفاده در این نوع مقاله از نوع پیش خور با روش بازگشتی است و بردار ورودی این شبکه عصبی از کانوالو تصویر با تنها یک فیلتر گابور با زاویه  و فرکانس  در خوزه فرکانس به دست می آید. الگوریتم پیشنهادی در این مقاله روی 550 تصویر از 2 پایگاه تصویر فرت با پس زمینه ساده و مارکوس وبر با پس زمینه پیچیده آزمایش شده و دقت آشکارسازی آن به ترتیب 98/4% و 95% است. همچنین به کمک الگوریتم ویولا جونز ناحیه صورت را در 550 نمونه تصویر به دست آورده و مقایسه ای بین نتایج به دست آمده از الگوریتم ویولاجونز و آلگوریتم پیشنهادی آورده می شود.
کلمات کلیدی: آشکار سازی صورت، شبکه عصبی، فیلتر گابور، ویژگی های گابور

فایل PDF – در 13 صفحه- نویسنده : ﻣﺤﻤﻮد ﻣﺤﻠﻮﺟﻲ و رضا محمدیان

آشکار سازی صورت با استفاده فیلترهای گابور و شبکه های عصبی

پسورد فایل : behsanandish.com


10.بهبود روش های ناحیه بندی تصاویر MRI مغز انسان با استفاده از عملگر گابور

 

فایل PDF – در 15 صفحه- نویسنده : فرزاد فلاحی

بهبود روش های ناحیه بندی تصاویر MRI مغز انسان با استفاده از عملگر گابور

پسورد فایل : behsanandish.com


11. بهبود سیستم های ایمنی برای تشخیص اجسام در تصویرهای پرتونگاری بار

 

چکیده: بازرسی چشمی بار در فرودگاهها و مراکز حساس مستلزم صرف زمان زيادی است و اجسام در بسياری از موارد خصوصاً زمانی که در موقعيت و زاويههای خاصی قرار گرفته باشند قابل شناسايی با بازرسیهای سريع چشمی نيستند. امروزه از دستگاههای تصويربرداری پرتو ايکس برای تشخيص اجسام در بار استفاده میشود. تصاوير پرتونگاری حاصل به علت پراکندگی فوتونی دارای ميزانی از مهآلودگی هستند و گاهی تشخيص دقيق اجسام با مشکل مواجه میشود. روشهای پردازش تصوير میتوانند به بهبود کنتراست و در نتيجه بهتر شدن قابليت تشخيص اجسام کمک کنند. در پرتونگاری بار سطح نويز و پراکندگی در تصويرهای مختلف با هم تفاوت زيادی دارند که اين موضوع ضرورت استفاده از روشهای پردازش تصوير خودکار را ايجاب میکند. در اين پژوهش از دو روش موجک و صافی گابور با سطح آستانهی خودکار استفاده شده است. نتايج حاصل نشان میدهد تصويرهای بازسازی شده اگرچه در جزييات دارای اختلافاتی هستنند ولی در ميزان تشخيص اجسام توسط افراد تفاوت زيادی ندارند. در هر دو روش کنتراست و قابليت تشخيص اجسام نسبت به تصويرهای اوليه بهبود قابل ملاحظهای يافته است. زمان اجرای الگوريتم موجک گسسته حدود يک هشتم زمان اجرای صافی گابور است که با توجه به اهميت سرعت پردازش تصوير در بازرسی بار برتری قابل ملاحظهای است.

کلید واژهها: پرتونگاری بار،سیستم بازرسی بار،پرتو ایکس، روش موجک گسسته، فیلتر گابور

 

فایل PDF – در 13 صفحه- نویسندگان : سمانه شیخ ربیعی، بهروز رکرک، عفت یاحقی، بهنام آرضابک

بهبود سیستم های ایمنی برای تشخیص اجسام در تصویرهای پرتونگاری بار

پسورد فایل : behsanandish.com


12. ﺑﻬﺒﻮد کیفیت تصویر اﺛﺮاﻧﮕﺸﺖ ﺑﺎ اﺳﺘﻔﺎده از فیلتر بانک ﮐﻤﺎﻧﯽ گابور

ﭼﮑﯿﺪه: ﺗﺄﯾﯿﺪ و ﺷﻨﺎﺳﺎﯾﯽ ﻫﻮﯾﺖ از روی ﺗﺼﻮﯾﺮ اﺛﺮاﻧﮕﺸﺖ ارﺗﺒﺎط ﻣﺴﺘﻘﯿﻤﯽ ﺑﺎ ﮐﯿﻔﯿﺖ اﯾﻦ ﺗﺼـﻮﯾﺮ دارد. در اﯾـﻦ ﻣﻘﺎﻟـﻪ روش ﺟﺪﯾـﺪی ﺑﺮای ﺑﻬﺒﻮد ﮐﯿﻔﯿﺖ ﺗﺼﻮﯾر اﺛﺮ اﻧﮕﺸﺖ ﺑﺎ اﺳﺘﻔﺎده از ﻓﯿﻠﺘﺮ ﺑﺎﻧﮏ اﺳـﺖ ﮐﻤﺎﻧﯽ ﮔـﺎﺑﻮر اراﺋـﻪ ﺷـﺪه است. ﻓﯿﻠﺘـﺮ ﺑﺎﻧـﮏ ﮐﻤـﺎﻧﯽ ﮔـﺎﺑﻮر در ﺣﻘﯿﻘﺖ ﻧﻮﻋﯽ ﻓﯿﻠﺘﺮ ﺑﺎﻧﮏ ﮔﺎﺑﻮر اﺳﺘﺎﻧﺪارد ﻣﺘﺒﺤﺮ ﺷﺪه ﺑﺮای اﺳﺘﻔﺎده روی ﺗﺼﺎوﯾﺮ اﺛﺮ اﻧﮕﺸﺖ می ﺑﺎﺷﺪ. ارزﯾﺎﺑﯽ ﻣﯿـﺰان ﺗﻮﻓﯿـﻖ روش در بهبود ﮐﯿﻔﯿﺖ ﺗﺼﺎوﯾﺮ اﺛﺮ اﻧﮕﺸﺖ ﺑﻪ دو روش اﻧﺠﺎم ﺷﺪه است. در روش اول، ﻣﻘﺎﯾﺴﻪ ﺑﯿﻦ ﺗﺼﺎوﯾﺮ اﺻـﻠﯽ و ﺗﺼـﺎوﯾﺮ ﺑﻬﺒﻮد ﯾﺎﻓﺘﻪ ﺑﺮاﺳﺎس ﻧﺘﺎﯾﺞ ﺑﺪﺳﺖ آﻣﺪه از ارزﯾﺎﺑﯽ ﺗﺄﯾﯿﺪ و ﺷﻨﺎﺳﺎﯾﯽ ﻫﻮﯾﺖ ﺻﻮرت ﭘﺬﯾﺮﻓﺘﻪ اﺳﺖ که ﺳﯿﺴﺘﻢ ﺗﺸﺨﯿﺺ ﻫﻮﯾـﺖ ﭘﯿﺸﻨﻬﺎدی ﻣﺒﺘﻨﯽ ﺑﺮ معیار ﻫﻤﺒﺴﺘﮕﯽ ﻫﯿﺴﺘﻮﮔﺮام ﻧﺮﻣﺎﻟﯿﺰه ﺷﺪه ویژگی های تصویر آماری باینری شده (BSIF) است. در روش دوم، از ﻣﻌﯿﺎر ﻧﺴﺒﺖ ﺳﯿﮕﻨﺎل ﺑﻪ ﻧﻮﯾﺰ ﺑﯿﺸﯿﻨﻪ (PSNR) به منظور ارزﯾﺎﺑﯽ میزان بهبود ﮐﯿﻔﯿﺖ، اﺳﺘﻔﺎده ﺷـﺪه است. دو ﭘﺎﯾﮕـﺎه DBI و DBII برای اجرای روش و ارزیابی نتایج مورد استفاده ﻗﺮار گرفته اﻧﺪ .ﻧﺮخ ﺗﺴﺎوی ﺧﻄﺎی (EER) ﺗﺄﯾﯿﺪ ﻫﻮﯾـﺖ ﺑﺮای ﺗﺼﺎوﯾﺮ اﺻﻠﯽ از (ﺑﻪ ترتیب % ۱۵/۸۹ و  ۱۱/۷۰%) به ( % ۱۱/۳۵ و  ۸/۰۰%) ﺑـﺮای ﺗﺼـﺎوﯾﺮ ﺑﻬﺒـﻮد ﯾﺎﻓﺘـﻪ کاهش ﯾﺎﻓﺘﻪ اﺳﺖ .ﺑﺮای ﺗﺸﺨﯿﺺ ﻫﻮﯾﺖ ﻧﯿﺰ ﻧﺮخ ﻣﺮﺗﺒﻪ اول ﻣﯿﺰان ﺑﺎزﺷﻨﺎﺳـﯽ ﺻـﺤﯿﺢ ﺑـﺮای ﺗﺼـﺎوﯾﺮ اصلی از مقادیر( ۶۹/۲۸% و ۷۱/۱۶ %) به (۷۸/۸۰% و ۸۱/۷۰ %) ﺑﺮای ﺗﺼﺎوﯾﺮ ﺑﻬﺒﻮد ﯾﺎﻓﺘﻪ اﻓﺰاﯾﺶ ﯾﺎﻓﺘﻪ است.  ﻣﯿﺰان متوسط PSNR ﻣﺮﺑﻮط ﺑﻪ ﺗﺼﺎوﯾﺮ ﺑﻬﺒﻮد ﯾﺎﻓﺘﻪ ﻧﯿﺰ از ﻣﻮرد ﻣﺸﺎﺑﻪ ﺑﺮای ﺗﺼﺎوﯾﺮ اﺻﻠﯽ ﺑﯿﺸﺘﺮ اﺳﺖ.

ﮐﻠﯿﺪ واژهﻫﺎ: ﮐﯿﻔﯿﺖ ﺗﺼﻮﯾﺮ، ﻓﯿﻠﺘﺮﺑﺎﻧﮏ اﺛﺮاﻧﮕﺸﺖ، ﺑﻬﺒﻮد ﮐﻤﺎﻧﯽ ﮔﺎﺑﻮر

 

فایل PDF – در 17 صفحه- نویسندگان : مهران تقی پور گرجی کلایی، سید محمد رضوی و ناصر مهرشاد

ﺑﻬﺒﻮد کیفیت تصویر اﺛﺮاﻧﮕﺸﺖ ﺑﺎ اﺳﺘﻔﺎده از فیلتر بانک ﮐﻤﺎﻧﯽ گابور

پسورد فایل : behsanandish.com


13. تشخیص چهره با استفاده از PCA و فیلتر گابور

 

فایل PDF – در 8 صفحه- نویسندگان : حمیدرضا قجر، محسن سریانی و عباس کوچاری

تشخیص چهره با استفاده از PCA و فیلتر گابور

پسورد فایل : behsanandish.com


14. تعیین توزیع دانه بندی سنگ دانه های بتن و آسفالت با استفاده از استخراج ویژگی های گابور و شبکه های عصبی

چکیده: توزیع ابعادی سنگدانه های تشکیل دهنده بتن و آسفالت، از مهمترین پارامترها در کنترل طرحهای اختلاط بتن و آسفالت است که میتواند بر کیفیت نهایی، مقاومت و دوام بتن و آسفالت تاثیر گذار باشد. بهمنظور ارزیابی درصد اختلاط سنگدانه ها، روش پردازش تصویری دیجیتال یک روش غیر مستقیم، سریع و قابل اعتماد است. در این تحقیق بر پایه یکی از روشهای استخراج ویژگیهای دیداری تصویر (فیلترهای گابور) و استفاده از شبکه های عصبی، الگوریتمی جهت تعیین توزیع دانه بندی تصاویر سنگدانه های تشکیل دهنده بتن و آسفالت ارائه شده است. تعداد 100 تصویر از سنگدانه های تشکیل دهنده بتن و آسفالت برای آموزش شبکه عصبی به کار برده شد. سپس نتایج حاصله با نتایج تخمین خودکار دانه بندی سنگدانه ها در نرم افزار Split-Desktop و همچنین تجزیه سرندی مقایسه شد.نتایج به دست آمده بیانگر یک بهبود کلی در ارزیابی توزیع اندازه سنگدانه های تشکیل دهنده بتن و آسفالت و کاهش خطای 67% با استفاده از روش پیشنهادی نسبت به تخمین خودکار نرم افزار Split-Desktop است. همچنین در ارزیابی اندازه های F10 تا F100، روش پیشنهادی بهبود 62% را نشان داد.

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

 

فایل PDF – در 14 صفحه- نویسندگان : هادی یعقوبی، حمید منصوری، محمد علی ابراهیمی فرسنگی و حسین نظام آبادی پور

تعیین توزیع دانه بندی سنگ دانه های بتن و آسفالت با استفاده از استخراج ویژگی های گابور و شبکه های عصبی

پسورد فایل : behsanandish.com


15. خوشه بندی سبک نگارش دست نوشته برون خط فارسی

 

چکیده– ﻫﺪﻑ ﺍﻳﻦ ﭘﺎﻳﺎﻥ ﻧﺎﻣﻪ، ﻳﺎﻓﺘﻦ ﻭ ﺍﺳﺘﺨﺮﺍﺝ ﻭﻳﮋﮔﻲ ﻫﺎﻳﻲ ﺍﺳﺖ ﮐﻪ ﺑﺮ ﻣﺒﻨﺎﻱ ﺁﻥ ﺑﺘﻮﺍﻥ ﺩﺳﺖ ﺧﻂ ﻓﺎﺭﺳﻲ ﺭﺍ ﺧﻮﺷﻪ ﺑﻨﺪﻱ ﮐﺮﺩ .ﺩﺭ ﺍﻳﻦ ﮐﺎﺭ، ﺩﺭ ﺍﺑﺘﺪﺍ ﺑﺮ ﺭﻭﻱ ﻭﻳﮋﮔﻲ ﻫﺎﻱ ﻣﺒﺘﻨﻲ ﺑﺮ ﺑﺎﻓﺖ، ﺗﻤﺮﮐﺰ ﺷﺪﻩ ﺍﺳﺖ .ﺍﻳﻦ ﻭﻳﮋﮔﻲ ﻫﺎ ﺷﺎﻣﻞ ﺩﻭ ﺩﺳﺘﻪ ﻭﻳﮋﮔﻲ ﺁﻣﺎﺭﻱ ﻣﺎﺗﺮﻳﺲ ﺑﺎﻫﻢ ﺁﻳﻲ ﻭ ﻭﻳﮋﮔﻲ ﻣﺒﺘﻨﻲ ﺑﺮ ﺗﺒﺪﻳﻞ ﮔﺎﺑﻮﺭ ﺍﺳﺖ .ﺑﺮﺍﻱ ﺍﺳﺘﺨﺮﺍﺝ ﺍﻳﻦ ﻭﻳﮋﮔﻲﻫﺎ، ﻳﮏ ﺑﺎﻓﺖ ﻣﻨﺎﺳﺐ ﺩﺭ ﺍﺑﻌﺎﺩ ۱۰۲۴×۱۰۲۴ ﻣﺴﺘﻘﻞ ﺍﺯ ﻣﺤﺘﻮﺍﻱ ﺳﻨﺪ، ﺍﺯ ﺗﺼﻮﻳﺮ ﺩﺳﺘﻨﻮﺷﺘﻪ ﺍﻳﺠﺎﺩ ﻣﻲ ﺷﻮﺩ .ﺍﺯ ﻭﻳﮋﮔﻲ ﻫﺎﻱ ﺩﻳﮕﺮﻱ ﮐﻪ ﺩﺭ ﺍﻳﻦ ﮐﺎﺭ ﺍﺯ ﺁﻥ ﻫﺎ ﺍﺳﺘﻔﺎﺩﻩ ﺷﺪﻩ ﺍﺳﺖ، ﺗﻌﺪﺍﺩﻱ ﻭﻳﮋﮔﻲ ﺳﺎﺧﺘﺎﺭﻱ ﻣﺒﺘﻨﻲ ﺑﺮ ﻣﻨﺤﻨﻲ ﭘﻴﺮﺍﻣﻮﻧﻲ ﺍﺳﺖ .ﺍﻳﻦ ﻭﻳﮋﮔﻲ ﻫﺎ ﺭﺍ ﺍﺯ ﻫﺮ ﻳﮏ ﺍﺯ ﺗﺼﺎﻭﻳﺮ ﻣﻮﺟﻮﺩ ﺩﺭ ﻳﮏ ﻣﺠﻤﻮﻋﻪ ﺩﺍﺩﻩ ﺍﺯ 97 ﺩﺳﺘﻨﻮﺷﺘﻪ ﻓﺎﺭﺳﻲ ﮐﻪ ﺩﺍﺭﺍﻱ ﻣﺘﻮﻥ ﻣﺘﻔﺎﻭﺗﻲ ﺑﻮﺩﻧﺪ، ﺍﺳﺘﺨﺮﺍﺝ ﮐﺮﺩﻳﻢ ﻭ ﺍﺯ ﺍﻟﮕﻮﺭﻳﺘﻢ k ﻣﻴﺎﻧﮕﻴﻦ ﻭ ﺷﺒﮑﻪ ﻋﺼﺒﻲ ﻧﮕﺎﺷﺖ ﻭﻳﮋﮔﻲ ﺧﻮﺩ ﺳﺎﻣﺎﻥ، ﺑﺮﺍﻱ ﺧﻮﺷﻪ ﺑﻨﺪﻱ ﺍﻳﻦ ﻭﻳﮋﮔﻲ ﻫﺎ ﺍﺳﺘﻔﺎﺩﻩ ﺷﺪﻩ ﺍﺳﺖ.

ﺑﺮﺍﻱ ﺍﺭﺯﻳﺎﺑﻲ ﺍﻳﻦ ﻭﻳﮋﮔﻲ ﻫﺎ، ﻳﮏ ﺭﻭﺵ ﺍﺭﺯﻳﺎﺑﻲ ﺑﺮ ﻣﺒﻨﺎﻱ ﺍﻟﮕﻮﺭﻳﺘﻢ ﺧﻮﺷﻪ ﺑﻨﺪﻱ k ﻣﻴﺎﻧﮕﻴﻦ، ﻃﺮﺍﺣﻲ ﮐﺮﺩﻩ ﺍﻳﻢ .ﺩﺭ ﺍﻳﻦ ﺍﻟﮕﻮﺭﻳﺘﻢ ﺍﺯ ﻣﻌﻴﺎﺭ ﻣﻘﺎﻳﺴﻪ ﺑﺎﻳﻨﺮﻱ ﮊﺍﮐﺎﺭﺩ ﺍﺳﺘﻔﺎﺩﻩ ﮐﺮﺩﻩ ﺍﻳﻢ، ﻫﻢ ﭼﻨﻴﻦ ﺑﺮﺍﻱ ﻣﺤﺎﺳﺒﻪ ﻣﺮﺍﮐﺰ ﺧﻮﺷﻪ ﺩﺭ ﻫﺮ ﺩﻭﺭﻩ ﺗﮑﺮﺍﺭ ﺍﺯ ﺍﻟﮕﻮﺭﻳﺘﻢ k ﻣﻴﺎﻧﮕﻴﻦ، ﺍﺯ ﺭﻭﺵ ﺍﻧﺘﺨﺎﺏ ﺩﺍﺩﻩ ﭼﺮﺥ ﺭﻭﻟﺖ، ﺑﻬﺮﻩ ﮔﺮﻓﺘﻪﺍﻳﻢ.

ﻧﺘﺎﻳﺞ ﺑﺪﺳﺖ ﺁﻣﺪﻩ، ﻧﺸﺎﻥ ﻣﻲ ﺩﻫﺪ ﺑﺎ ﺗﺮﮐﻴﺐ ﺩﻭ ﻧﻮﻉ ﺍﺯ ﻭﻳﮋﮔﻲ ﻫﺎﻱ ﻣﺒﺘﻨﻲ ﺑﺮ ﻣﻨﺤﻨﻲ ﭘﻴﺮﺍﻣﻮﻧﻲ، ﻧﺮﺥ ﺧﻮﺷﻪ بندی 75 ﺩﺭﺻﺪ ﺍﺳﺖ ﮐﻪ ﻧﺴﺒﺖ ﺑﻪ ﺳﺎﻳﺮ ﺭﻭﺵﻫﺎﻱ ﻣﻮﺭﺩ ﺍﺳﺘﻔﺎﺩﻩ ﺩﺭ ﺍﻳﻦ ﮐﺎﺭ، ﻧﺮﺥ ﺑﻬﺘﺮﻱ ﺭﺍ ﺩﺭ ﺑﺮﺩﺍﺷﺘﻪ ﺍﺳﺖ .

ﮐﻠﻴﺪ ﻭﺍﮊﻩ: ﺳﺒﮏ ﻧﮕﺎﺭﺵ، ﺧﻮﺷﻪ ﺑﻨﺪﻱ، ﺑﺎﻓﺖ، ﻓﻴﻠﺘﺮ ﮔﺎﺑﻮﺭ، ﻣﺎﺗﺮﻳﺲ ﺑﺎ ﻫﻢ ، ﺁﻳﻲ، ﻣﻨﺤﻨﻲ ﭘﻴﺮﺍﻣﻮﻧﻲ، ﮊﺍﮐﺎﺭﺩ ﭼﺮﺥ ﺭﻭﻟﺖ

فایل PDF – در 20 صفحه- نویسنده : فاطمه ولایتی

خوشه بندی سبک نگارش دست نوشته برون خط فارسی

پسورد فایل : behsanandish.com


16. شاخص گذاری بر روی تصاویر با استفاده از موجک های گابور و ممان های لژاندر

 

چکیده- در این مقاله، یک سیستم جدید شاخص گذاری و بازیابی تصاویر (CBIR) با استفاده از موجک های گابور و ممان های لژاندار پیشنهاد گردیده است. از انجائیکه موجک های گایور قادر به استخراج مطلوب اطلاعات خطوط و لبه های تصاویر در مقیاس ها و درجات تفکیک مختلف می باشند و از طرف دیگر، این تبدیل تنها تابعی است که می تواند حد تئوری دقت تفکیک توأم اطلاعات در هر حوزه مکان و فرکانس را حاصل نماید، در اینجا از آن به منظور تشخیص محتوای بصری تصاویر به کار گرفته شده است. هم چنین ممانهای لژاندار جهت بهبود نتایج حاصل از عمل بازیابی الگوریتم استفاده شده اند. کوچکی نسبی طول بردار ویژگی (58)، از مزایای این روش می باشد که عمل بازیابی را تسریع می بخشد. همچنین به دلیل آنکه اطلاعات رنگ تصاویر مورد استفاده قرار نمی گیرند، الگوریتم قادر به تشخیص تصاویر مشابه با رنگ های متفاوت نیز خواهد بود. نتایج حاصل از اجرای این سیستم، راندمان بالای آن را در تشخیص تصاویر مشابه مورد تأییید قرار می دهد.

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

 

فایل PDF – در 8 صفحه- نویسندگان : اسماعیل فرامرزی، ابوالقاسم صیادیان، علیرضا احمدیان

شاخص گذاری بر روی تصاویر با استفاده از موجک های گابور و ممان های لژاندر

پسورد فایل : behsanandish.com


17. طراحی بخش دریافت و پردازش تصویر برای یک پروتز بینایی

 

ﭼﮑﯿﺪه ﺗﻼش ﻫﺎ ﺑﺮاي ﺗﺤﻘﻖ ﭘﺮوﺗﺰﻫﺎي ﺑﯿﻨﺎﯾﯽ از دﻫﻪ ﮔﺬﺷﺘﻪ آﻏﺎز ﺷﺪه اﺳﺖ. ﭘﺮوﺗﺰﻫﺎي ﺑﯿﻨﺎﯾﯽ ﺟﺎﻧﺸﯿﻨﯽ ﺑﺮاي ﺳﯿﺴﺘﻢ ﺑﯿﻨﺎﯾﯽ ﻣﻌﯿﻮب ﻫﺴﺘﻨﺪ ﺗﺎ ﺑﺘﻮاﻧﻨﺪ ﺑﯿﻨﺎﯾﯽ را ﺑﻪ اﻓﺮاد ﻧﺎﺑﯿﻨﺎ ﺑﺎزﮔﺮداﻧﻨﺪ. ﺑﺎ وﺟﻮد اﯾﻦ ﺗﻼش ﻫﺎ، داﻧﺸﻤﻨﺪان ﻣﻮﻓﻖ ﺑﻪ ﺳﺎﺧﺖ ﭘﺮوﺗﺰ ﺑﯿﻨﺎﯾﯽ ﮐﻪ ﺑﺘﻮاﻧﺪ ﺟﺎﻧﺸﯿﻦ ﻣﻨﺎﺳﺒﯽ ﺑﺮاي ﺳﯿﺴﺘﻢ ﺑﯿﻨﺎﯾﯽ ﺷﻮد، ﻧﺸﺪه اﻧﺪ.
ﭘﺮدازش ﺗﺼﻮﯾﺮ در ﭘﺮوﺗﺰﻫﺎي ﺑﯿﻨﺎﯾﯽ ﺑﺮاي اﻓﺰاﯾﺶ درك ﺗﺼﻮﯾﺮي ﻓﺮد ﻧﺎﺑﯿﻨﺎ از ﻣﺤﯿﻂ اﻃﺮاف ﻫﻨﮕﺎم اﺳﺘﻔﺎده از ﭘﺮوﺗﺰ ﺑﯿﻨﺎﯾﯽ ﮐﺎرﺑﺮد دارد. در اﯾﻦ رﺳﺎﻟﻪ ﯾﮏ روش ﺟﺪﯾﺪ ﺑﺮ ﻣﺒﻨﺎي ﻓﯿﻠﺘﺮ ﮔﺎﺑﻮر و ﺗﺒﺪﯾﻞ ﮐﺴﯿﻨﻮﺳﯽ ﮔﺴﺴﺘﻪ ﺑﺮاي اﺳﺘﻔﺎده درﯾﮏ ﺳﯿﺴﺘﻢ ﭘﺮوﺗﺰ ﺑﯿﻨﺎﯾﯽ ﻣﻌﺮﻓﯽ ﺷﺪه اﺳﺖ. در اداﻣﻪ اﻟﮕﻮرﯾﺘﻢ ﻫﺎي ﺟﺪﯾﺪ و ﭘﺮدازش ﺗﺼﻮﯾﺮ ﭘﯿﺸﻨﻬﺎد ﺷﺪه در اﯾﻦ رﺳﺎﻟﻪ ارزﯾﺎﺑﯽ و ﻣﻘﺎﯾﺴﻪ ﺷﺪه اﻧﺪ و اﻟﮕﻮرﯾﺘﻢ ﭘﯿﺸﻨﻬﺎد ﺷﺪه ﺑﺎ 78 % ﻧﺮخ ﺑﺎزﺷﻨﺎﺳﯽ، ﮐﺎراﯾﯽ ﺑﻬﺘﺮي ﻧﺴﺒﺖ ﺑﻪ دﯾﮕﺮ روش ﻫﺎ داﺷﺘﻪ اﺳﺖ. ﺑﻪ ﻣﻨﻈﻮر ارزﯾﺎﺑﯽ اﻟﮕﻮرﯾﺘﻢ ﻫﺎي ﭘﯿﺸﻨﻬﺎدي و ﻫﻤﭽﻨﯿﻦ ﺑﺮاي ﺑﻪ ﮐﺎر ﮔﯿﺮي در ﻧﻤﻮﻧﻪ اوﻟﯿﻪ ﺳﯿﺴﺘﻢ ﭘﺮوﺗﺰ ﺑﯿﻨﺎﯾﯽ، اﯾﻦ ﭘﺮدازش ﻫﺎ ﺑﻪ ﺻﻮرت ﺳﺨﺖ اﻓﺰاري ﭘﯿﺎده ﺳﺎزي و آزﻣﺎﯾﺶ ﺷﺪه اﻧﺪ. ﺑﺮاي ﭘﯿﺎده ﺳﺎزي ﺳﺨﺖ اﻓﺰاري اﻟﮕﻮرﯾﺘﻢ ﻫﺎي ﭘﺮدازﺷﯽ از ﺑﺮد MINI2440 اﺳﺘﻔﺎده ﺷﺪه اﺳﺖ. ﺑﺮاي آزﻣﺎﯾﺶ ﻫﺎي ﻣﺮﺑﻮﻃﻪ، ﻣﺠﻤﻮﻋﻪ اي از اﻧﻮاع ﻣﺨﺘﻠﻒ ﺗﺼﺎوﯾﺮ ﺛﺎﺑﺖ و ﻫﻤﭽﻨﯿﻦ ﺗﺼﺎوﯾﺮ متحرک درﯾﺎﻓﺖ ﺷﺪه ﺗﻮﺳﻂ ﯾﮏ دورﺑﯿﻦ ﻣﻮرد اﺳﺘﻔﺎده ﻗﺮار ﮔﺮﻓﺘﻪ اﺳﺖ. تصاویر ﺑﺎ ﻧﺮخ 15 ﻓﺮﯾﻢ در ثانیه درﯾﺎﻓﺖ، ﭘﺮدازش و ﺑﺎ ﭘﺮوﺗﮑﻞ ﻣﻌﺮﻓﯽ ﺷﺪه و ﮐﺪﯾﻨﮓ ﻣﻨﭽﺴﺘﺮ ﺑﻪ ﭘﺮوﺗﺰ ﺑﯿﻨﺎﯾﯽ ارﺳﺎل ﻣﯽ ﺷﻮﻧﺪ.

ﮐﻠﻤﺎت ﮐﻠﯿﺪي: ﭘﺮوﺗﺰ ﺑﯿﻨﺎﯾﯽ، ﭘﺮدازش ﺗﺼﻮﯾﺮ، ﻓﯿﻠﺘﺮ ﮔﺎﺑﻮر، ﺗﺒﺪﯾﻞ ﮐﺴﯿﻨﻮﺳﯽ ﮔﺴﺴﺘﻪ، MINI2440

 

فایل PDF – در 20 صفحه- نویسنده : علی شاکر

طراحی بخش دریافت و پردازش تصویر برای یک پروتز بینایی

پسورد فایل : behsanandish.com

مجموعه مقالات فیلتر گابور (Gabor Filter) قسمت 1
مجموعه مقالات فیلتر گابور (Gabor Filter) قسمت 2

1.A GABOR FILTER TEXTURE ANALYSIS APPROACH FOR HISTOPATHOLOGICAL BRAIN TUMOUR SUBTYPE DISCRIMINATION

Abstract Meningioma brain tumour discrimination is challenging as many histological patterns are mixed between the different subtypes. In clinical practice, dominant patterns are investigated for signs of specific meningioma pathology; however the simple observation could result in inter- and intra-observer variation due to the complexity of the histopathological patterns. Also employing a computerised feature extraction approach applied at a single resolution scale might not suffice in accurately delineating the mixture of histopathological patterns. In this work we propose a novel multiresolution feature extraction approach for characterising the textural properties of the different pathological patterns (i.e. mainly cell nuclei shape, orientation and spatial arrangement within the cytoplasm). The patterns’ textural properties are characterised at various scales and orientations for an improved separability between the different extracted features. The Gabor filter energy output of each magnitude response was combined with four other fixed-resolution texture signatures (2 model-based and 2 statistical-based) with and without cell nuclei segmentation. The highest classification accuracy of 95% was reported when combining the Gabor filters’ energy and the meningioma subimage fractal signature as a feature vector without performing any prior cell nuceli segmentation. This indicates that characterising the cell-nuclei self-similarity properties via Gabor filters can assists in achieving an improved meningioma subtype classification, which can assist in overcoming variations in reported diagnosis.
Keywords – texture analysis, Gabor filter, fractal dimension, meningioma histopathology, brain tumours

فایل PDF – در 14 صفحه- نویسنده : Omar Sultan Al-Kadi

A GABOR FILTER TEXTURE ANALYSIS APPROACH FOR HISTOPATHOLOGICAL BRAIN TUMOUR SUBTYPE DISCRIMINATION

پسورد فایل : behsanandish.com


2.A Review Paper on Gabor Filter Algorithm & Its Applications

Abstract— In applications of image analysis and computer vision, Gabor filters have maintained their popularity in feature extraction. The reason behind this is that the resemblance between Gabor filter and receptive field of simple cells in visual cortex. Being successful in applications like face detection, iris recognition, fingerprint matching; where, Gabor feature based processes are amongst the best performers. The Gabor features can be derived by applying signal processing techniques both in time and frequency domain. The models like human preattentive texture perception have been proposed which involves steps like convolution, inhibition and texture boundary detection. Texture features are based on the local power spectrum obtained by a bank of Gabor filters. The concept of sparseness to generate novel contextual multiresolution texture descriptors are described. In this paper we present the detailed study about the Gabor filter and its application.
Index Terms— Gabor filter, Gabor energy, image quality assessment, Gabor features, multiresolution techniques, segmentation, textured images..

فایل PDF – در 5 صفحه- نویسنده : Neelu Arora , Mrs. G. Sarvani

A Review Paper on Gabor Filter Algorithm & Its Applications

پسورد فایل : behsanandish.com


3.Comparison of texture features based on Gabor filters

 

Abstract -The performance of a number of texture feature operators is evaluated. The features are all based on the local spectrum which is obtained by a bank of Gabor filters. The comparison is made using a quantitative method which is based on Fisher’s criterion. It is shown that, in general, the discrimination effectiveness of the features increases with the amount of post-Gabor processing.

فایل PDF – در 6 صفحه- نویسنده : P. Kruizinga, N. Petkov and S.E. Grigorescu

Comparison of texture features based on Gabor filters

پسورد فایل : behsanandish.com


4.Evolutionary Gabor Filter Optimization with Application to Vehicle Detection

 

Abstract—Despite the considerable amount of research work on the application of Gabor filters in pattern classification, their design and selection have been mostly done on a trial and error basis. Existing techniques are either only suitable for a small number of filters or less problem-oriented. A systematic and general evolutionary Gabor filter optimization (EGFO) approach that yields a more optimal, problem-specific, set of filters is proposed in this study. The EGFO approach unifies filter design with filter selection by integrating Genetic Algorithms (GAs) with an incremental clustering approach. Specifically, filter design is performed using GAs, a global optimization approach that encodes the parameters of the Gabor filters in a chromosome and uses genetic operators to optimize them. Filter selection is performed by grouping together filters having similar characteristics (i.e., similar parameters) using incremental clustering in the parameter space. Each group of filters is represented by a single filter whose parameters correspond to the average parameters of the filters in the group. This step eliminates redundant filters, leading to a compact, optimized set of filters. The average filters are evaluated using an application-oriented fitness criterion based on Support Vector Machines (SVMs). To demonstrate the effectiveness of the proposed framework, we have considered the challenging problem of vehicle detection from gray-scale images. Our experimental results illustrate that the set of Gabor filters, specifically optimized for the problem of vehicle detection, yield better performance than using traditional filter banks.

 

فایل PDF – در 8 صفحه- نویسنده : Zehang Sun, George Bebis and Ronald Miller

Evolutionary Gabor Filter Optimization with Application to Vehicle Detection

پسورد فایل : behsanandish.com


5.Expression-Invariant Face Recognition via 3D Face Reconstruction Using Gabor Filter Bank from a 2D Single Image

Abstract— In this paper, a novel method for expression- insensitive face recognition is proposed from only a 2D single image in a gallery including any facial expressions. A 3D Generic Elastic Model (3D GEM) is used to reconstruct a 3D model of each human face in the present database using only a single 2D frontal image with/without facial expressions. Then, the rigid parts of the face are extracted from both the texture and reconstructed depth based on 2D facial land-marks. Afterwards, the Gabor filter bank was applied to the extracted rigid-part of the face to extract the feature vectors from both texture and reconstructed depth images. Finally, by combining 2D and 3D feature vectors, the final feature vectors are generated and classified by the Support Vector Machine (SVM). Favorable outcomes were acquired to handle expression changes on the available image database based on the proposed method compared to several state-of-the-arts in expression-insensitive face recognition.

Keywords—Face recognition; 3D shape recovery; Gesture and Behavior Analysis.

 

فایل PDF – در 6 صفحه- نویسنده : Ali Moeini, Hossein Moeini, Karim Faez

Expression-Invariant Face Recognition via 3D Face Reconstruction Using Gabor Filter Bank from a 2D Single Image

پسورد فایل : behsanandish.com


6.IMAGE RETRIEVAL BASED ON HIERARCHICAL GABOR FILTERS

Content Based Image Retrieval (CBIR) is now a widely investigated issue that aims at allowing users of multimedia information systems to automatically retrieve images coherent with a sample image. A way to achieve this goal is the computation of image features such as the color, texture, shape, and position of objects within images, and the use of those features as query terms. We propose to use Gabor filtration properties in order to find such appropriate features. The article presents multichannel Gabor filtering and a hierarchical image representation. Then a salient (characteristic) point detection algorithm is presented so that texture parameters are computed only in a neighborhood of salient points. We use Gabor texture features as image content descriptors and efficiently emply them to retrieve images.
Keywords: Gabor filters, image retrieval, texture feature extraction, hierarchical representation

فایل PDF – در 10 صفحه- نویسنده : TOMASZ ANDRYSIAK, MICHAŁ CHORA´ S

IMAGE RETRIEVAL BASED ON HIERARCHICAL GABOR FILTERS

پسورد فایل : behsanandish.com


7.Iris Recognition Based On Adaptive Gabor Filter

Abstract. Aiming at the problem of multi-category iris recognition, there proposes a method of iris recognition algorithm based on adaptive Gabor filter. Use DE-PSO to adaptive optimize the Gabor filter parameters. DE-PSO is composed of particle swarm optimization and differential evolution algorithm. Use 16 groups of 2D-Gabor filters with different frequencies and directions to process iris images. According to the direction and frequency of maximum response amplitude, transform iris features into 512-bit binary feature encoding. Calculate the Hamming distance of feature code and compare with the classification threshold, determine iris the type of iris. Experiment on a variety of iris databases with multiple Gabor filter algorithms, the results showed that this algorithm has higher recognition rate, the ROC curve is closer to the coordinate axis and the robustness is better, compare with other Gabor filter algorithm.

Keywords: Iris recognition Gabor filter Particle swarm optimization Differential evolutionFeature encodingHamming distance

 

فایل PDF – در 8 صفحه- نویسنده : Shuai Liu, Yuanning Liu, Xiaodong Zhu, Guang Huo, Jingwei Cui, and Yihao Chen

 

Iris Recognition Based On Adaptive Gabor Filter

پسورد فایل : behsanandish.com


8.USE OF GABOR FILTERS FOR TEXTURE CLASSIFICATION OF AIRBORNE IMAGES AND LIDAR DATA

KEY WORDS: Texture analysis, LIDAR, Algorithm, Urban and Vegetation Detection, Automated Classification
ABSTRACT: In this paper, a texture approach is presented for building and vegetation extraction from LIDAR and aerial images. The texture is very important attribute in many image analysis or computer vision applications. The procedures developed for texture problem can be subdivided into four categories: structural approach, statistical approach, model based approach and filter based approach. In this paper, different definitions of texture are described, but complete emphasis is given on filter based methods. Examples of filtering methods are Fourier transform, Gabor and wavelet transforms. Here, Gabor filter is studied and its implementation for texture analysis is explored. This approach is inspired by a multi-channel filtering theory for processing visual information in the human visual system. This theory holds that visual system decomposes the image into a number of filtered images of a specified frequency, amplitude and orientation.  The main objective of the article is to use Gabor filters for automatic urban object and tree detection. The first step is a definition of Gabor filter parameters: frequency, standard deviation and orientation. By varying these parameters, a filter bank is obtained that covers the frequency domain almost completely. These filters are used to aerial images and LIDAR data. The filtered images that possess  a significant information about analyzed objects are selected, and the rest are discarded.  Then, an energy measure is defined on the filtered images in order to compute different texture features. The Gabor features are used to image segmentation using thresholding.  The tests were performed using set of images containing very different landscapes: urban area and vegetation of varying configurations, sizes and shapes of objects. The performed studies revealed that textural algorithms have the ability to detect buildings and trees. This article is the attempt to use texture methods also to LIDAR data, resampling into regular grid cells. The obtained preliminary results are interesting.

 

فایل PDF – در 12 صفحه- نویسنده : Urszula Marmol


USE OF GABOR FILTERS FOR TEXTURE CLASSIFICATION OF AIRBORNE IMAGES AND LIDAR DATA

پسورد فایل : behsanandish.com

 

تاريخچه

الگوريتم SVM اوليه در ۱۹۶۳ توسط Vladimir Vapnik ابداع شد و در سال ۱۹۹۵ توسطVapnik و Corinna Cortes براي حالت غيرخطي تعميم داده شد.

ماشين بردار پشتيباني (Support vector machines) يکي از روش‌هاي يادگيري بانظارت(Supervised learning) است که از آن براي طبقه‌بندي و رگرسيون استفاده مي‌کنند.

اين روش از جمله روش‌هاي نسبتاً جديدي است که در سال‌هاي اخير کارايي خوبي نسبت به روش‌هاي قديمي‌تر براي طبقه‌بندي از جمله شبکه‌هاي عصبي پرسپترون نشان داده است. مبناي کاري دسته‌بنديکنندة SVM دسته‌بندي خطي داده‌ها است و در تقسيم خطي داده‌ها سعي مي‌کنيم خطي را انتخاب کنيم که حاشيه اطمينان بيشتري داشته باشد. حل معادلة پيدا کردن خط بهينه براي داده‌ها به وسيله روش‌هايQP (Quadratic Programming) که روش‌هاي شناخته شده‌اي در حل مسائل محدوديت‌دار هستند صورت مي‌گيرد.

SVM از يک تکنيک که kernel trick ناميده مي شود، براي تبديل داده هاي شما استفاده مي کند و سپس بر اساس اين تبديل، مرز بهينه بين خروجي هاي ممکن را پيدا مي کند. به عبارت ساده تبديلات بسيار پيچيده را انجام مي دهد، سپس مشخص مي کند چگونه داده هايتان را بر اساس برچسب ها يا خروجي هايي که تعريف کرده ايد، جدا کنيد.

يکي از روش هايي که در حال حاضر به صورت گسترده براي مسئله دسته بندي (Classification) مورد استفاده قرار مي گيرد، روش ماشين بردار پشتيبان (SVM) است. شايد به گونه اي بتوان محبوبيت کنوني روش ماشين بردار پشتيبان را با محبوبيت شبکه هاي عصبي در دهه گذشته مقايسه کرد. علت اين قضيه نيز قابليت استفاده اين روش در حل مسائل گوناگون مي باشد، در حاليکه روش هايي مانند درخت تصميم گيري را نمي توان به راحتي در مسائل مختلف به کار برد.

کاربردهاي SVM

الگوريتم  SVM، جز الگوريتم هاي تشخيص الگو دسته بندي مي شود. از الگوريتم SVM، در هر جايي که نياز به تشخيص الگو يا دسته بندي اشيا در کلاس هاي خاص باشد مي توان استفاده کرد. در ادامه به کاربرد هاي اين الگوريتم به صورت موردي اشاره مي شود:

سيستم آناليز ريسک، کنترل هواپيما بدون خلبان، رديابي انحراف هواپيما، شبيه سازي مسير، سيستم راهنمايي اتوماتيک اتومبيل، سيستمهاي بازرسي کيفيت، آناليز کيفيت جوشکاري، پيش بيني کيفيت، آناليز کيفيت کامپيوتر، آناليز عملياتهاي آسياب، آناليز طراحي محصول شيميايي، آناليز نگهداري ماشين، پيشنهاد پروژه، مديريت و برنامه ريزي، کنترل سيستم فرايند شيميايي و ديناميکي، طراحي اعضاي مصنوعي، بهينه سازي زمان پيوند اعضا، کاهش هزينه بيمارستان، بهبود کيفيت بيمارستان، آزمايش اتاق اورژانس، اکتشاف روغن و گاز، کنترل مسير در دستگاههاي خودکار، ربات، جراثقال، سيستمهاي بصري، تشخيص صدا، اختصار سخن، کلاسه بندي صوتي، آناليز بازار، سيستمهاي مشاوره اي محاسبه هزينه موجودي، اختصار اطلاعات و تصاوير، خدمات اطلاعاتي اتوماتيک، مترجم لحظه اي زبان، سيستمهاي پردازش وجه مشتري، سيستمهاي تشخيص ترمز کاميون، زمانبندي وسيله نقليه، سيستمهاي مسيريابي، کلاسه بندي نمودارهاي مشتري/بازار، تشخيص دارو، بازبيني امضا، تخمين ريسک وام، شناسايي طيفي، ارزيابي سرمايه، کلاسه بندي انواع سلولها، ميکروبها و نمونه ها، پيش بيني فروشهاي آينده، پيش بيني نيازهاي محصول، پيش بيني وضعيت بازار، پيش بيني شاخصهاي اقتصادي، پيش بيني ملزومات انرژي، پيش بيني واکنشهاي دارويي، پيش بيني بازتاب محصولات شيميايي، پيش بيني هوا، پيش بيني محصول، پيش بيني ريسک محيطي، پيش بيني جداول داوري، مدل کردن کنترل فرآيند، آناليز فعاليت گارانتي، بازرسي اسناد، تشخيص هدف، تشخيص چهره، انواع جديد سنسورها، دستگاه کاشف زير دريايي بوسيله امواج صوتي، رادار، پردازش سيگنالهاي تصويري شامل مقايسه اطلاعات، پيگيري هدف، هدايت جنگ افزارها، تعيين قيمت وضعيت فعلي، جلوگيري از پارازيت، شناسايي تصوير /سيگنال، چيدمان يک مدار کامل، بينايي ماشين، مدل کردن غير خطي، ترکيب صدا، کنترل فرآيند ساخت، آناليز مالي، پيش بيني فرآيندهاي توليد، ارزيابي بکارگيري يک سياست، بهينه سازي محصول، تشخيص ماشين و فرآيند، مدل کردن کنترل سيستمها، مدل کردن ساختارهاي شيميايي، مدل کردن سيستمهاي ديناميکي، مدل کردن سيگنال تراکم، مدل کردن قالبسازي پلاستيکي، مديريت قراردادهاي سهام، مديريت وجوه بيمه، ديريت سهام، تصويب چک بانکي، اکتشاف تقلب در کارت اعتباري، ثبت نسيه، بازبيني امضا از چکها، پيش بيني ارزش نسيه، مديريت ريسک رهن، تشخيص حروف و اعدا، تشخيص بيماري و…..

ايده اصلي SVM

l      با فرض اينکه دسته ها بصورت خطي جداپذير باشند، ابرصفحه هائي با حداکثر حاشيه(maximum margin)  را بدست مي آورد که دسته ها را جدا کنند.

l      در مسايلي که داده ها بصورت خطي جداپذير نباشند، داده ها به فضاي با ابعاد بيشتر نگاشت پيدا مي کنند تا بتوان آنها را در اين فضاي جديد بصورت خطي جدا نمود.

l      در يک فرايند يادگيري که شامل دو کلاس مي­باشد، هدف SVM پيدا کردن بهترين تابع براي طبقه­بندي مي­باشد به نحوي که بتوان اعضاي دو کلاس را در مجموعه داده­ها از هم تشخيص داد. معيار بهترين طبقه­بندي به­صورت هندسي مشخص مي­شود، براي مجموعه داده­هايي که به­صورت خطي قابل تجزيه هستند. به­طور حسي آن مرزي که به­صورت بخشي از فضا تعريف مي­شود يا همان تفکيک بين دو کلاس بوسيله hyperplane تعريف مي­شود. همين تعريف هندسي به ما اجازه مي­دهد تا کشف کنيم که چگونه مرزها را بيشينه کنيم ولو اينکه تعداد بيشماري hyperplane داشته باشيم و فقط تعداد کمي، شايستگي راه حل براي SVM دارند.

مسئله جداسازي خطي: Linear Discrimination

اگر دو دسته وجود داشته باشند که بصورت خطي از هم جداپذير باشند، بهترين جدا کننده اين دو دسته چيست؟

الگوريتم هاي مختلفي از جمله  پرسپترون ميتوانند اين جداسازي را انجام دهند.

آيا همه اين الگوريتمها بخوبي از عهده اين کار بر مي آيند؟

 

آشنايي با مفاهيم ابتدايي

خط يا ابر صفحه جدا کننده:

هدف: پيدا کردن بهترين خط ( ابر صفحه) که دو دسته را از هم جدا کند. در حالت دو بعدي معادله اين خط بصورت زير است:

در حالت n  بعدي خواهيم داشت:

حداکثر حاشيه (maximum margin)

بر طبق قضيه اي در تئوري يادگيري اگر مثالهاي آموزشي بدرستي دسته بندي شده باشند، از بين جداسازهاي خطي، آن جداسازي که حاشيه داده هاي آموزشي را حداکثر مي کند، خطاي تعميم را حداقل خواهد کرد.

چرا حداکثر حاشيه؟

¢     به نظر مي رسد که مطمئن ترين راه باشد.

¢     تئوري هائي برمبناي VC dimension وجود دارد که مفيد بودن آنرا اثبات مي کند.

¢     بطور تجربي اين روش خيلي خوب جواب داده است.

¢     دليل اينکه SVM روي بزرگ­ترين مرز براي hyperplane پافشاري مي­کند اين­ست که قضيه قابليت عموميت بخشيدن به الگوريتم را بهتر تامين مي­کند. اين نه تنها به کارايي طبقه­بندي و دقت  آن روي داده­هاي آزمايشي کمک مي­کند، فضا را نيز براي طبقه­بندي بهتر داده­هاي آتي مهيا مي­کند.

بردار پشتيبان

نزديکترين داده هاي آموزشي به ابر صفحه هاي جدا کننده بردار پشتيبان ناميده مي شوند.

ماشين بردار پشتيبان خطي

ماشين بردار پشتيبان يک روش يادگيري نسبتا جديد است که اغلب براي کلاسبندي باينري مورد استفاده واقع مي شود. فرض کنيد L مشاهده داريم که هر مشاهده مشتمل بر زوج هاي است که در آن . بردار ورودي و  يک مقدار دو وضعيتي (1- يا 1+) است. ايده ي ماشين بردار پشتيبان مي کوشد، ابرصفحاتي در فضا رسم کند که عمل تمايز نمونه هاي کلاس هاي مختلف داده ها را بطور بهينه انجام دهد. مي توان يک ابرصفحه را از طريق رابطه زير نشان داد:

براي يک بردار خطي b با وزن w ، حاشيه جداسازي عبارتست از فاصله ي بين ابرصفحه تعريف شده توسط رابطه ي فوق و نزديکترين ويژگي به آن. هدف ماشين بردار پشتيبان يافتن ابرصفحه اي ست که بيشترين حاشيه ي جداسازي را داشته باشد. مهمترين وظيفه SVM ، يافتن پارامترهاي w0 و b0 بر اساس بردارهاي آموزشي داده شده، براي اين ابرصفحه بهينه است. براي يک بردار ويژگي X، فاصله تا ابرصفحه بهينه به صورت زير است:

از رابطه بالا نتيجه مي شود که ماکزيموم کردن حاشيه جداسازي بين الگوها و ابرصفحه، معادلست با مينيموم کردن فرم اقليدسي بردار وزن w. بنابراين مساله بهينه سازي مقيد را مي توان به صورت زير تعريف کرد:

براي حل اين مساله، تابع لاگرانژ زير را تشکيل داده و حل مي کنيم:

لاگرانژين L بايد نسبت به متغيرهاي اوليه  bو w مينيموم و نسبت به متغيرهاي دوگان ماکزيموم شود. با مساوي صفر قراردادن مشتق L نسبت به b،w:

به معادلات زير خواهيم رسيد:

مجموعه جواب، بسطي از نمونه هاي آموزشي است که مقدار  متناظر با آن ها، يک مقدار غير صفر است. اين نمونه هاي آموزشي خاص به بردارهاي پشتيبان مشهورند. بردارهاي پشتيبان روي مرز حاشيه قرار دارند. مابقي نمونه هاي آموزشي در اين قسمت نقشي ندارند.

تمايز نمونه هاي دو کلاس با ابرصفحه ي بهينه

با قرار دادن 7 و 8 در  به مساله دوگان ولف زير خواهيم رسيد:

حل اين مساله دوگان ضرايب لاگرانژ را به ما مي دهد. تابع ابرصفحه متمايز کننده را مي توان به صورت زير نوشت:

ماشين بردار پشتيبان براي بردارهاي ورودي جدايي ناپذير:

اغلب در عمل، يافتن يک ابرصفحه متمايز کننده به راحتي امکان پذير نيست. زيرا مثلا يک نويز قوي مي تواند باعث ايجاد رويهم افتادگي کلاس ها شود. در اين حالت از متغير هايي به نام متغيرهاي کمبود(Slack Variables) استفاده مي کنيم. به گونه اي که شرايط زير برقرار باشند:

حال يک تعميم خوب براي ابرصفحه ي متمايز کننده، با کنترل ظرفيت کلاسبند (از طريق ) و همچنين تعداد خطاهاي مرحله آموزش بدست مي آيد. مساله بهينه سازي به صورت زير تعريف خواهد شد:

مساله دوگان به فرم زير خواهد بود:

ماشين بردار پشتيبان غيرخطي:

ابرصفحه جداکننده بهينه اولين بار توسط Vapnik در سال ۱۹۶۳ ارائه شد که يک دسته کننده خطي بود. در سال ۱۹۹۲ ،Bernhard Boser ،  Isabelle GuyonوVapnik راهي را براي ايجاد دسته بند غيرخطي، با استفاده قرار دادن هسته براي پيدا کردن ابرصفحه با بيشتر حاشيه، پيشنهاد دادند. الگوريتم نتيجه شده ظاهرا مشابه است، به جز آنکه تمام ضرب هاي نقطه اي با يک تابع هسته غيرخطي جايگزين شده اند. اين اجازه مي دهد، الگوريتم، براي ابرصفحه با بيشترين حاشيه در يک فضاي ويژگيِ تغييرشکل داده، مناسب باشد. ممکن است، تغييرشکل غيرخطي باشد و فضاي تغيير يافته، داراي ابعاد بالاتري باشد. به هر حال دسته کننده، يک ابرصفحه در فضاي ويژگي با ابعاد بالا است، که ممکن است در فضاي ورودي نيز غيرخطي باشد.

در حالت غيرخطي، مي توان با اعمال پيش پردازش داده ها، مساله را به فضايي برد که در آن جا با يک ابرصفحه ساده قابل حل باشد. براي اين منظور يک نگاشت  تعريف مي کنيم که بردار ورودي d بعدي x را به بردار d’ بعدي z تبديل مي کند.

بايد به گونه اي انتخاب شود که بردارهاي فضاي ويژگي جديد جدايي پذير باشند. در حالت کلي مي توان گفت که اگر  بردارهاي ورودي را به فضايي ببرد که تعداد ابعاد آن به اندازه کافي بزرگ باشد (

منبع


منابع

1.https://fa.wikipedia.org

2.http://www.bigdata.ir

3.www.barjoueian.com

4.http://fumblog.um.ac.ir

ماشین بردار پشتیبان (svm) قسمت 1
ماشین بردار پشتیبان (svm) قسمت 2
ماشین بردار پشتیبان (svm) قسمت 3

یادگیری ماشین – SVM یا ماشین بردار پشتیبان به زبان ساده

یکی از الگوریتم ها و روشهای بسیار رایج در حوزه دسته بندی داده ها، الگوریتم SVM یا ماشین بردار پشتیبان است که در این مقاله سعی شده است به زبان ساده و به دور از پیچیدگیهای فنی توضیح داده شود.

آشنایی با مفهوم دسته بندی

فرض کنید مجموعه داده ای داریم که ۵۰٪ افراد آن مرد و ۵۰٪ افراد آن زن هستند. این مجموعه داده می تواند مشتریان یک فروشگاه آنلاین باشد. با داشتن یک زیرمجموعه از این داده ها که جنسیت افراد در آن مشخص شده است، می خواهیم قوانینی ایجاد کنیم که به کمک آنها جنسیت بقیه افراد مجموعه را بتوانیم با دقت بالایی تعیین کنیم. تشخیص جنسیت بازدیدکنندگان فروشگاه، باعث می شود بتوانیم تبلیغات جداگانه ای را برای زنان و مردان نمایش دهیم و سودآوری فروشگاه را بالا ببریم . این فرآیند را در علم تحلیل داده، دسته بندی می نامیم .

برای توضیح کامل مسأله، فرض کنید دو پارامتری که قرار است جنسیت را از روی آنها تعیین کنیم، قد و طول موی افراد است . نمودار پراکنش قد و طول افراد در زیر نمایش داده شده است که در آن جنسیت افراد با دو نماد مربع (مرد) و دایره (زن) به طور جداگانه نمایش داده شده است .

SVM-1

 

با نگاه به نمودار فوق، حقایق زیر به سادگی قابل مشاهده است :

  1. مردان در این مجموعه، میانگین قد بلندتری دارند.
  2. زنان از میانگین طول موی بیشتری برخوردار هستند.

اگر یک داده جدید با قد ۱۸۰cm و طول موی ۴cm به ما داده شود، بهترین حدس ما برای ماشینی این شخص، دسته مردان خواهد بود .

بردارهای پشتیبان و ماشین بردار پشتیبان

بردارهای پشتیبان به زبان ساده، مجموعه ای از نقاط در فضای n بعدی داده ها هستند که مرز دسته ها را مشخص می کنند و مرزبندی و دسته بندی داده ها براساس آنها انجام می شود و با جابجایی یکی از آنها، خروجی دسته بندی ممکن است تغییر کند . به عنوان مثال در شکل فوق ، بردار (۴۵,۱۵۰) عضوی از بردار پشتیبان و متعلق به یک زن است . در فضای دوبعدی ،‌بردارهای پشتیبان، یک خط، در فضای سه بعدی یک صفحه و در فضای n بعدی یک ابر صفحه را شکل خواهند داد.

SVM یا ماشین بردار پشتیبان ، یک دسته بند یا مرزی است که با معیار قرار دادن بردارهای پشتیبان ، بهترین دسته بندی و تفکیک بین داده ها را برای ما مشخص می کند.

در SVM فقط داده های قرار گرفته در بردارهای پشتیبان مبنای یادگیری ماشین و ساخت مدل قرار می گیرند و این الگوریتم به سایر نقاط داده حساس نیست و هدف آن هم یافتن بهترین مرز در بین داده هاست به گونه ای که بیشترین فاصله ممکن را از تمام دسته ها (بردارهای پشتیبان آنها) داشته باشد .

چگونه یک ماشین بر مبنای بردارهای پشتیبان ایجاد کنیم ؟

به ازای داده های موجود در مثال فوق، تعداد زیادی مرزبندی می توانیم داشته باشیم که سه تا از این مرزبندی ها در زیر نمایش داده شده است.

 

SVM-2

 

سوال اینجاست که بهترین مرزبندی در این مسأله کدام خط است ؟

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

توزیع غیر خطی داده ها و کاربرد ماشین بردار پشتیبان

اگر داده ها به صورت خطی قابل تفکیک باشند، الگوریتم فوق می تواند بهترین ماشین را برای تفکیک داده ها و تعیین دسته یک رکورد داده، ایجاد کند اما اگر داده ها به صورت خطی توزیع شده باشند (مانند شکل زیر )، SVM را چگونه تعیین کنیم ؟

 

SVM-3

 

در این حالت، ما نیاز داریم داده ها را به کمک یک تابع ریاضی (Kernel functions) به یک فضای دیگر ببریم (نگاشت کنیم ) که در آن فضا، داده ها تفکیک پذیر باشند و بتوان SVM آنها را به راحتی تعیین کرد. تعیین درست این تابع نگاشت در عملکرد ماشین بردار پشتیبان موثر است که در ادامه به صورت مختصر به آن اشاره شده است.

با فرض یافتن تابع تبدیل برای مثال فوق،‌ فضای داده ما به این حالت تبدیل خواهد شد :

 

SVM-4

 

در این فضای تبدیل شده، یافتن یک SVM به راحتی امکان پذیر است .

نگاهی دقیق تر به فرآیند ساخت SVM

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

در شکل زیر داده ها در دو دوسته آبی و قرمز نمایش داده شده اند و خطوط نقطه چین ، بردار های پشتیبان متناظر با هر دسته را نمایش می دهند که با دایره های دوخط مشخص شده اند و خط سیاه ممتد نیز همان SVM است . بردار های پشتیبان هم هر کدام یک فرمول مشخصه دارند که خط مرزی هر دسته را توصیف می کند.

SVM-5

SVM‌ در پایتون

برای استفاده از ماشین بردار پشتیبان در پایتون، توصیه بنده استفاده از کتابخانه یادگیری ماشین پایتون به نام scikitlearn است که تمام کرنل ها و توابع نگاشت را به صورت آماده شده دارد. سه تا تابعSVC , NuSVC , LinearSVC وظیفه اصلی دسته بندی را برعهده دارند . (SVC = Support Vector Classifier) . نمونه ای از دسته بندی با این توابع را در زیر می توانید مشاهده کنید :

 

SVM-6

ماشین بردار پشتیبانی در عمل

برای استفاده از SVM در مورد داده های واقعی ، چندین نکته را باید رعایت کنید تا نتایج قابل قبولی را بگیرید

  1. ابتدا داده ها را پالایش کنید (نقاط پرت ،‌ داده های ناموجود و …..)
  2. داده را عددی و نرمال کنید . این مباحث را در مقالات پیش پردازش داده ها دنبال کنید. به طور خلاصه ، داده هایی مانند جنسیت، رشته تحصیلی و … را به عدد تبدیل کنید و سعی کنید مقادیر همه صفات بین یک تا منهای یک [۱,-۱] نرمال شوند تا بزرگ یا کوچک بودن مقادیر یک ویژگی داده ها،‌ ماشین را تحت تاثیر قرار ندهد .
  3. کرنل های مختلف را امتحان و به ازای هر کدام، با توجه به مجموعه داده آموزشی که در اختیار دارید و دسته بندی داده های آنها مشخص است، دقت SVM را اندازه گیری کنید و در صورت نیاز پارامتر های توابع تبدیل را تغییر دهید تا جواب های بهتری بگیرید. این کار را برای کرنل های مختلف هم امتحان کنید . می توانید از کرنل RBF شروع کنید .

نقاط ضعف ماشین بردار پشتیان

  • این نوع الگوریتم ها، محدودیت های ذاتی دارند مثلا هنوز مشخص نشده است که به ازای یک تابع نگاشت ، پارامترها را چگونه باید تعیین کرد.
  • ماشینهای مبتنی بر بردار پشتیبان به محاسبات پیچیده و زمان بر نیاز دارند و به دلیل پیچیدگی محاسباتی، حافظه زیادی نیز مصرف می کنند.
  • داده های گسسته و غیر عددی هم با این روش سازگار نیستند و باید تبدیل شوند.

با این وجود، SVM‌ ها دارای یک شالوده نظری منسجم بوده و جواب های تولید شده توسط آنها ، سراسری و یکتا می باشد. امروزه ماشینهای بردار پشتیبان، به متداول ترین تکنیک های پیش بینی در داده کاوی تبدیل شده اند.

سخن پایانی

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

ساختار اصلی این نوشتار از روی یک مقاله سایت آنالیتیکزویدیا برداشته شده است و برای دو بخش پایانی مقاله هم از کتاب «داده کاوی پیشرفته : مفاهیم و الگوریتم ها» دکتر شهرابی استفاده شده است .

منبع


آشنایی با ماشین بردار پشتیبان (SVM) – مرور کلی

SVM یک مدل یادگیری نظارت شده است.

پس قبل از این که به سراغ آن برویم باید یک مجموعه داده(Dataset) که از قبل برچسب‌گذاری شده(Labeled) را داشته باشیم.

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

من به دنبال راهی هستم که این ایمیل‌ها را هرچه سریع‌تر تشخیص بدهم(پیدا کنم) و پاسخ آن‌ها را زودتر از بقیه ارسال کنم.

رویکرد اولمن می‌توانم برچسب‌هایی با عنوان‌های: اورژانسی، شکایت و راهنمایی در جیمیل(GMail) خود ایجاد کنم.

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

رویکرد دوممن می‌توانم از یک الگوریتم یادگیری ماشین نظارت شده استفاده کنم.

قدم اولبه تعدادی ایمیل نیاز دارم.(هرچه بیشتر بهتر)

قدم دومعنوان ایمیل‌های قدم اول رو می‌خوانم و آن‌ها را در یکی از دو گروه «شکایت است» و یا «شکایت نیست» طبقه‌بندی می‌کنم. اینجوری می‌توانم ایمیل‌ها را برچسب ‌گذاری کنم.

قدم سومروی این مجموعه داده، مدلی را آموزش می‌دهم.

قدم چهارمکیفیت یا صحت پیش‌بینی های مدل آموزش داده‌شده را ارزیابی می‌کنم.(با استفاده از روش Cross Validation)

قدم پنجماز این مدل برای پیش‌بینی این که ایمیل‌های جدیدی که رسیده‌اند، شکایت هستند یا نه، استفاده می‌کنم.

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

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

SVM یک مدل خطی را یاد می‌گیرد

در مثال قبل دیدیم که در قدم سوم یک الگوریتم یادگیری نظارت شده مثل SVM به کمک داده‌هایی که از قبل برچسب‌گذاری شده‌اند آموزشداده شد. اما برای چه چیزی آموزش داده شد؟ برای این که چیزی را یاد بگیرد.

چه چیزی را یاد بگیرد؟

در مورد SVM، یک مدل خطیرا یاد میگیرد.

مدل خطی چیست؟ اگر بخواهیم به زبان ساده بیان کنیم یک خط است.(و در حالت پیچیده‌تر یک ابر صفحه).

اگر داده‌های شما خیلی ساده و دو بعدی باشند، در این صورت SVM خطی را یاد می‌گیرد که آن خط می‌تواند داده‌ها را به دو بخش تقسیم کند.

 

svm

SVM قادر است که خطی را پیدا کند که داده‌ها را جدا می‌کند.

 

خب پس اگر SVM فقط یک خط است، پس چرا ما داریم راجع به مدل خطی صحبت می‌کنیم؟

برای این که ما همینطوری نمی‌توانیم به یک خط چیزی را آموزش بدهیم.

در عوض:

  1. در نظر می‌گیریم که داده‌هایی که می‌خواهیم طبقه‌بندی کنیم، می‌توانند به وسیله یک خط از هم تفکیک شوند.
  2. می‌دانیم که یک خط می‌تواند به کمک معادله y=wx+by=wx+b نمایش داده شود.(این همان مدل ما است)
  3. می‌دانیم با تغییر دادن مقدار w و b بی‌نهایت خط وجود خواهد داشت.
  4. برای تعیین این که کدام مقدار w و b بهترینخط جداکننده داده‌ها را به ما می‌دهد، از یک الگوریتم استفاده می‌کنیم.

SVM یکی از این الگوریتم‌ها هست که می‌تواند این کار را انجام دهد.

الگوریتم یا مدل؟

در شروع این پست من نوشتم که SVM یک مدل یادگیری نظارت شده است، و الآن می‌نویسم که آن یک الگوریتم است. چه شده؟ از واژه الگوریتم معمولا آزادانه استفاده می‌شود. برای نمونه، ممکن است که شما جایی بخوانید یا بشنوید که  SVM یک الگوریتم یادگیری نظارت شده است. اگر این نکته را در نظر بگیریم که الگوریتم مجموعه‌ای از فعالیت‌ها است که انجام می‌شوند تا به نتیجه مشخصی دست یابیم، می‌بینیم که استفاده از این واژه در اینجا صحیح نیست(منظور از واژه الگوریتم اینجا الگوریتمی است که برای آموزش از آن استفاده می‌کنیم). بهینه‌سازی متوالی کمینه(Sequential minimal optimization) پر استفاده ترین الگوریتم برای آموزش SVM است. با این حال می‌توان از الگوریتم‌های دیگری مثل کاهش مختصات(Coordinate descent) هم استفاده کرد. در کل بیشتر به جزییاتی مثل این علاقمند نیستند، در نتیجه ما هم برای ساده‌تر شدن فقط از واژه الگوریتم SVM استفاده می‌کنیم(بدون ذکر جزییات الگوریتم آموزشی که استفاده می‌کنیم).

SVM یا SVMها؟

بعضی وقت‌ها می‌بینیم که مردم راجع به SVM و بعضی وقت‌ها هم راجع به SVMها صحبت می‌کنند.

طبق معمول ویکی‌پدیا در روشن و شفاف کردن چیزها به ما کمک می‌کند:

در یادگیری ماشینی، ماشین‌های بردار پشتیبان (SVMsمدل‌های یادگیری نظارت شده به همراه الگوریتم‌های آموزش مربوطههستندکه در تحلیل داده‌های استفاده شده در  رگرسیون و طبقه‌بندی از آن‌ها استفاده می‌شود.(ویکی‌پدیا)

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

SVMها – ماشین‌های بردار پشتیبان

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

  • SVM برای طبقه‌بندی استفاده می‌شود.
  • SVR یا(Support Vector Regression) برای رگرسیون.

پس گفتن ماشین‌های بردار پشتیبان هم دیگه الآن منطقی به نظر میاد. با این وجود این پایان داستان نیست!

طبقه‌بندی

در سال ۱۹۵۷ یک مدل خطی ساده به نام پرسپترون توسط فردی به نام فرانک روزنبلت برای طبقه‌بندی اختراع شد(که در واقع اساس شبکه‌های عصبی ساده‌ای به نام پرسپترون چند لایه است).

چند سال بعد، واپنیک و چروننکیس مدل دیگری به نام «طبقه‌بندی کننده حداکث حاشیه» پیشنهاد دادند و همان‌جا بود که SVM متولد شد.

در سال ۱۹۹۲ واپنیک و همکارانش ایده‌ای داشتند که یک چیزی به نام کلک کرنل(Kernel Trick) را به روش قبلی اضافه کنند تا به آن‌ها اجازه دهد که حتی داده‌هایی که به صورت خطی تفکیک‌پذیر نیستند را هم طبقه‌بندی کنند.

سرانجام در سال ۱۹۹۵، کورتز و واپنیک، طبقه‌بندی کننده حاشیه نرم را معرفی کردند که به SVM اجازه می‌دهد تا بعضی از اشتباهات در طبقه‌بندی را هم بپذیرد.

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

  1. طبقه‌بندی کننده حاشیه حداکثر.
  2. نسخه‌ای که از کلک کرنل استفاده می‌کند.
  3. نسخه‌ای که از حاشیه نرم استفاده می‌کند.
  4. نسخه‌ای که ترکیب همه موارد قبلی است.

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

به همین دلیل است که وقتی از یک زبان برنامه‌‌نویسی استفاده می‌کنید می‌پرسید از کدام کرنل باید استفاده کنیم(بخاطر کرنل‌های مختلفی که وجود دارند) و یا کدام مقدار ابرپارامتر C را باید استفاده کنید(برای کنترل تاثیر حاشیه نرم).

رگرسیون

در سال ۱۹۹۶، واپنیک و همکارانش، نسخه‌ای از SVM را پیشنهاد دادند که به جای طبقه‌بندی، عمل رگرسیون را انجام می‌دهد. این مورد به Support Vector Regression یا SVR معروف است. همانند SVM در این مدل نیز از کلک کرنل و ابرپارامتر C  استفاده می‌شود.

در آینده مقاله ساده‌ای در مورد توضیح چگونگی استفاده از  SVR در زبان R خواهم نوشت و آدرس آن را همین‌جا قرار خواهم داد.

اگر علاقمند هستید که راجع به SVR بیشتر بدانیند، می‌توانید به این آموزش خوب که نوشته Smola and Schölkopft است، مراجعه کنید.

خلاصه تاریخچه

  • طبقه‌بندی کننده حاشیه حداکثر (۱۹۶۳ یا ۱۹۷۹)
  • کلک کرنل (۱۹۹۲)
  • طبقه‌بندی کننده حاشیه نرم (۱۹۹۵)
  • رگرسیون بردار پشتیبان (۱۹۹۶)

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

انواع دیگری از ماشین‌های بردار پشتیبان

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

  • ماشین بردار پشتیبان ساخت‌یافتهکه توانایی پیش‌بینی اشیای ساخت‌یافته را دارد.
  • ماشین بردار پشتیبان حداقل مربعکه در طبقه‌بندی و رگرسیون استفاده می‌شود.
  • خوشه‌بندی بردار پشتیبانکه در تحلیل خوشه استفاده می‌شود.
  • ماشین بردار پشتیبان هدایتیکه در یادگیری نیمه نظارت‌شده استفاده می‌شود.
  • SVM رتبه‌بندیبرای مرتب کردن نتایج.
  • ماشین بردار پشتیبان تک کلاسهکه برای تشخیص ناهنجاری استفاده می‌شود.

نتیجه‌گیری

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

امیدوارم این مقاله دید وسیع‌تری از چشم‌انداز  SVM به شما داده باشد و کمک کرده باشد که بهتر این ماشین‌ها را بشناسید و درک کنید.

اگه مایلید که بیشتر راجع به نحوه کار SVM در طبقه‌بندی بدانید، می‌توانید به آموزش‌های ریاضی مربوط به آن مراجعه کنید.

ماشین بردار پشتیبانی

ماشین بردار پشتیبان (Support vector machines – SVMs) یکی از روش‌های یادگیری بانظارت است که از آن برای طبقه‌بندی و رگرسیون استفاده می‌کنند.

این روش از جملهٔ روش‌های نسبتاً جدیدی است که در سال‌های اخیر کارایی خوبی نسبت به روش‌های قدیمی‌تر برای طبقه‌بندی از جمله شبکه‌های عصبی پرسپترون نشان داده است. مبنای کاریدسته‌بندی کنندۀ SVM دسته‌بندی خطی داده‌ها است و در تقسیم خطی داده‌ها سعی می‌کنیم خطی را انتخاب کنیم که حاشیه اطمینان بیشتری داشته باشد. حل معادله پیدا کردن خط بهینه برای داده‌ها به وسیله روش‌های QP که روش‌های شناخته شده‌ای در حل مسائل محدودیت‌دار هستند صورت می‌گیرد. قبل از تقسیمِ خطی برای اینکه ماشین بتواند داده‌های با پیچیدگی بالا را دسته‌بندی کند داده‌ها را به وسیلهٔ تابعِ phi به فضای با ابعاد خیلی بالاتر می‌بریم. برای اینکه بتوانیم مسئله ابعاد خیلی بالا را با استفاده از این روش‌ها حل کنیم از قضیه دوگانی لاگرانژ برای تبدیلِ مسئلهٔ مینیمم‌سازی مورد نظر به فرم دوگانی آن که در آن به جای تابع پیچیدهٔ phi که ما را به فضایی با ابعاد بالا می‌برد، تابعِ ساده‌تری به نامِ تابع هسته که ضرب برداری تابع phi است ظاهر می‌شود استفاده می‌کنیم. از توابع هسته مختلفی از جمله هسته‌های نمایی، چندجمله‌ای و سیگموید می‌توان استفاده نمود.

یکی از معروفترین خودآموزها مربوط به است.

کاربردهای SVM

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

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

تاریخچه

الگوریتم SVM اولیه در ۱۹۶۳ توسط Vladimir Vapnik ابداع شدو در سال ۱۹۹۵ توسط Vapnik و Corinna Cortes برای حالت غیرخطی تعمیم داده شد.

خلاصه استفاده عملی از SVM

ماتریس الگو را آماده می کنیم. تابع کرنلی را برای استفاده انتخاب می کنیم. پارامتر تابع کرنل و مقدار C را انتخاب می کنیم. برای محاسبه ی مقادیرα_i الگوریتم آموزشی را با استفاده از حل‌کننده‌های QP اجرا می کنیم. داده‌های جدید با استفاده از مقادیرα_i و بردارهای پشتیبان می‌توانند دسته بندی شوند.

مزایا و معایب SVM

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

ماشین بردار پشتیبان خطی

شکل 1

ما مجموعه داده‌های آزمایش {\displaystyle {\mathcal {D}}} شامل n عضو(نقطه)را در اختیار داریم که به صورت زیر تعریف می‌شود:

{\displaystyle {\mathcal {D}}=\left\{(\mathbf {x} _{i},y_{i})\mid \mathbf {x} _{i}\in \mathbb {R} ^{p},\,y_{i}\in \{-1,1\}\right\}_{i=1}^{n}}

جایی که مقدار y برابر ۱ یا -۱ و هر {\displaystyle \mathbf {x} _{i}} یک بردار حقیقی p-بعدی است. هدف پیدا کردن ابرصفحه جداکننده با بیشترین فاصله از نقاط حاشیه‌ای است که نقاط با {\displaystyle y_{i}=1} را از نقاط با {\displaystyle y_{i}=-1} جدا کند. هر ابر صفحه می‌تواند به صورت مجموعه‌ای از نقاط {\mathbf {x}} که شرط زیر را ارضا می‌کند نوشت:

{\displaystyle \mathbf {w} \cdot \mathbf {x} -b=0,\,} جایی که . علامت ضرب است. {\displaystyle {\mathbf {w} }} بردار نرمال است، که به ابرصفحه عمود است. ما می خواهیم {\displaystyle {\mathbf {w} }} و {\displaystyle {\mathbf {b} }} را طوری انتخاب کنیم که بیشترین فاصله بین ابر صفحه‌های موازی که داده‌ها را از هم جدا می‌کنند، ایجاد شود. این ابرصفحه‌ها با استفاده از رابطه زیر توصیف می‌شوند.
{\displaystyle \mathbf {w} \cdot \mathbf {x} -b=1\,}

و

شکل 2
{\displaystyle \mathbf {w} \cdot \mathbf {x} -b=-1.\,}
اگر داده‌های آموزشی جدایی پذیر خطی باشند، ما می‌توانیم دو ابر صفحه در حاشیه نقاط به‌طوری‌که هیچ نقطه مشترکی نداشته باشند، در نظر بگیریم و سپس سعی کنیم، فاصله آن‌ها را، ماکسیمم کنیم. با استفاده از هندسه، فاصله این دو صفحه {\displaystyle {\tfrac {2}{\|\mathbf {w} \|}}} است. بنابراین ما باید {\displaystyle \|\mathbf {w} \|} را مینیمم کنیم. برای اینکه از ورود نقاط به حاشیه جلوگیری کنیم، شرایط زیر را اضافه می کنیم: برای هر i
of the first class {\displaystyle \mathbf {w} \cdot \mathbf {x} _{i}-b\geq 1\qquad {\text{ for }}\mathbf {x} _{i}}

یا

of the second class {\displaystyle \mathbf {w} \cdot \mathbf {x} _{i}-b\leq -1\qquad {\text{ for }}\mathbf {x} _{i}}

این می‌تواند به صورت زیر نوشته شود:

{\displaystyle y_{i}(\mathbf {w} \cdot \mathbf {x} _{i}-b)\geq 1,\quad {\text{ for all }}1\leq i\leq n.\qquad \qquad (1)}

با کنار هم قرار دادن این دو یک مسئله بهینه‌سازی به دست می‌آید:

Minimize (in {\displaystyle {\mathbf {w} ,b}})

{\displaystyle \|\mathbf {w} \|}

subject to (for any {\displaystyle i=1,\dots ,n})

{\displaystyle y_{i}(\mathbf {w} \cdot \mathbf {x_{i}} -b)\geq 1.\,}

فرم اولیه

مسئله بهینه‌سازی مشاهده شده در قسمت قبل، مسئله سختی، برای حل کردن است، زیرا به||w|| وابسته است (نرم w ) . خوشبختانه می‌توانیم، بدون تغییر در مسئله||w|| را با{\displaystyle {\tfrac {1}{2}}\|\mathbf {w} \|^{2}}جانشین کنیم( عبارت ½ برای آسودگی در محاسبات ریاضی آورده شده). این یک مسئله بهینه سازی (OP)برنامه‌ریزی غیرخطی(QP) است. به‌طور واضح تر :

Minimize (in {\displaystyle {\mathbf {w} ,b}}) c

{\displaystyle {\frac {1}{2}}\|\mathbf {w} \|^{2}}

subject to (for any {\displaystyle i=1,\dots ,n})

{\displaystyle y_{i}(\mathbf {w} \cdot \mathbf {x_{i}} -b)\geq 1.}

می توان عبارت قبل را با استفاده از ضرایب نا منفی لاگرانژ به صورت زیر نوشت که در آن ضرایب لاگرانژ هستند {\displaystyle \alpha _{i}}:

{\displaystyle \min _{\mathbf {w} ,b,{\boldsymbol {\alpha }}}\{{\frac {1}{2}}\|\mathbf {w} \|^{2}-\sum _{i=1}^{n}{\alpha _{i}[y_{i}(\mathbf {w} \cdot \mathbf {x_{i}} -b)-1]}\}}

اما فرمول فوق اشتباه است . فرض کنید ما بتوانیم خانواده‌ای از ابرصفحات که نقاط را تقسیم می‌کنند پیدا کنیم . پس همه {\displaystyle y_{i}(\mathbf {w} \cdot \mathbf {x_{i}} -b)-1\geq 0} . بنا بر این ما می‌توانیم مینیمم را با فرستادن همه {\displaystyle \alpha _{i}} به{\displaystyle +\infty } پیدا کنیم. با این حال شرط پیش گفته می‌تواند به صورت پایین بیان شود:

{\displaystyle \min _{\mathbf {w} ,b}\max _{\boldsymbol {\alpha }}\{{\frac {1}{2}}\|\mathbf {w} \|^{2}-\sum _{i=1}^{n}{\alpha _{i}[y_{i}(\mathbf {w} \cdot \mathbf {x_{i}} -b)-1]}\}}

ما به دنبال نقاط saddle میگردیم.حالا می‌توان این مسئله را به کمک برنامه‌ریزی غیرخطی استاندارد حل کرد. جواب می‌تواند به صورت ترکیب خطی از بردارهای آموزشی بیان شود :

{\displaystyle \mathbf {w} =\sum _{i=1}^{n}{\alpha _{i}y_{i}\mathbf {x_{i}} }}

تنها چند{\displaystyle \alpha _{i}} بزرگتر از صفر خواهد بود.{\displaystyle \mathbf {x_{i}} } متناظر، دقیقاً همان بردار پشتیبان خواهد بود و به شرط را ارضا خواهد کرد. از این می‌توان نتیجه گرفت که بردارهای پشتیبان شرط زیر را نیز ارضا می‌کنند: {\displaystyle y_{i}(\mathbf {w} \cdot \mathbf {x_{i}} -b)=1} که اجازه می دهد مفدار b تعریف شود. در عمل الگوریتم مقاوم تر خواهد بود اگر از تمام {\displaystyle N_{SV}} بردار پشتیبان میانگین گرفته شود:

{\displaystyle b={\frac {1}{N_{SV}}}\sum _{i=1}^{N_{SV}}{(\mathbf {w} \cdot \mathbf {x_{i}} -y_{i})}}

فرم دوگان

استفاده از این واقعیت که {\displaystyle \|\mathbf {w} \|^{2}=w\cdot w} و جانشینی {\displaystyle \mathbf {w} =\sum _{i=1}^{n}{\alpha _{i}y_{i}\mathbf {x_{i}} }} می‌توان نشان داد که دوگان SVM به مسئله بهینه‌سازی زیر ساده می‌شود:

Maximize (in {\displaystyle \alpha _{i}} )

{\displaystyle {\tilde {L}}(\mathbf {\alpha } )=\sum _{i=1}^{n}\alpha _{i}-{\frac {1}{2}}\sum _{i,j}\alpha _{i}\alpha _{j}y_{i}y_{j}\mathbf {x} _{i}^{T}\mathbf {x} _{j}=\sum _{i=1}^{n}\alpha _{i}-{\frac {1}{2}}\sum _{i,j}\alpha _{i}\alpha _{j}y_{i}y_{j}k(\mathbf {x} _{i},\mathbf {x} _{j})}

subject to (for any}{\displaystyle i=1,\dots ,n})

{\displaystyle \alpha _{i}\geq 0,\,}

and to the constraint from the minimization in {\displaystyle b}

{\displaystyle \sum _{i=1}^{n}\alpha _{i}y_{i}=0.}

در اینجا هسته به صورت {\displaystyle k(\mathbf {x} _{i},\mathbf {x} _{j})=\mathbf {x} _{i}\cdot \mathbf {x} _{j}} تعریف می‌شود. عبارت \alpha  تشکیل یک دوگان برای بردار وزن‌ها مجموعه آموزشی می دهد:

{\displaystyle \mathbf {w} =\sum _{i}\alpha _{i}y_{i}\mathbf {x} _{i}.}

ماشین بردار پشتیبان چند کلاسی

SVM اساساً یک جداکننده دودویی است. در بخش قبلی پایه‌های تئوری ماشین‌های بردار پشتیبان برای دسته بندی دو کلاس تشریح شد. یک تشخیص الگوی چند کلاسی می‌تواند به وسیله ی ترکیب ماشین‌های بردار پشیبان دو کلاسی حاصل شود. به‌طور معمول دو دید برای این هدف وجود دارد. یکی از آن‌ها استراتژی “یک در مقابل همه ” برای دسته بندی هر جفت کلاس و کلاس‌های باقی‌مانده‌است. دیگر استراتژی “یک در مقابل یک” برای دسته بندی هر جفت است. در شرایطی که دسته بندی اول به دسته بندی مبهم منجر می‌شود.برای مسائل چند کلاسی٬رهیافت کلی کاهش مسئله ی چند کلاسی به چندین مسئله دودویی است. هریک از مسائل با یک جداکننده دودویی حل می‌شود. سپس خروجی جداکننده‌های دودویی SVM با هم ترکیب شده و به این ترتیب مسئله چند کلاس حل می‌شود.

ماشین‌های بردار پشتیبان غیرخطی

شکل 3

ابرصفحه جداکننده بهینه اولین بار توسط Vapnik در سال ۱۹۶۳ ارائه شد که یک دسته‌کننده خطی بود. در سال ۱۹۹۲ ،Bernhard Boser ، Isabelle GuyonوVapnik راهی را برای ایجاد دسته بند غیرخطی، با استفاده قرار دادن هسته برای پیدا کردن ابرصفحه با بیشتر حاشیه، پیشنهاد دادند. الگوریتم نتیجه شده ظاهراً مشابه است، به جز آنکه تمام ضرب‌های نقطه‌ای با یک تابع هسته غیرخطی جایگزین شداند. این اجازه می‌دهد، الگوریتم، برای ابرصفحه با بیشترین حاشیه در یک فضای ویژگی تغییرشکل داده، مناسب باشد. ممکن است، تغییرشکل غیرخطی باشد و فضای تغییر یافته، دارای ابعاد بالاتری باشد. به هر حال دسته‌کننده، یک ابرصفحه در فضای ویژگی با ابعاد بالا است، که ممکن است در فضای ورودی نیز غیرخطی باشد.

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

  • چندجمله‌ای (همگن): {\displaystyle k(\mathbf {x_{i}} ,\mathbf {x_{j}} )=(\mathbf {x_{i}} \cdot \mathbf {x_{j}} )^{d}}
  • چندجمله‌ای (ناهمگن): {\displaystyle k(\mathbf {x_{i}} ,\mathbf {x_{j}} )=(\mathbf {x_{i}} \cdot \mathbf {x_{j}} +1)^{d}}
  • گوسیین Radial Basis Function:  {\displaystyle k(\mathbf {x_{i}} ,\mathbf {x_{j}} )=\exp(-\gamma \|\mathbf {x_{i}} -\mathbf {x_{j}} \|^{2})}، for {\displaystyle \gamma >0.} Sometimes parametrized using {\displaystyle \gamma =1/{2\sigma ^{2}}}
  • تانژانت هذلولی: {\displaystyle k(\mathbf {x_{i}} ,\mathbf {x_{j}} )=\tanh(\kappa \mathbf {x_{i}} \cdot \mathbf {x_{j}} +c)}، for some (not every) {\displaystyle \kappa >0} and {\displaystyle c<0}

هسته با انتقال {\displaystyle \varphi (\mathbf {x_{i}} )} با تساوی {\displaystyle k(\mathbf {x_{i}} ,\mathbf {x_{j}} )=\varphi (\mathbf {x_{i}} )\cdot \varphi (\mathbf {x_{j}} )} در ارتباط است. همچنین مقدار wدر فضای انتقال یافته برابر{\displaystyle \textstyle \mathbf {w} =\sum _{i}\alpha _{i}y_{i}\varphi (\mathbf {x} _{i}).} است. ضرب نقطه‌ای با w می‌تواند توسط هسته محاسبه شود یعنی {\displaystyle \textstyle \mathbf {w} \cdot \varphi (\mathbf {x} )=\sum _{i}\alpha _{i}y_{i}k(\mathbf {x} _{i},\mathbf {x} )}. به هر حال در حالت عادی w’ وجود ندارد، به‌طوری‌که {\displaystyle \mathbf {w} \cdot \varphi (\mathbf {x} )=k(\mathbf {w'} ,\mathbf {x} ).}

 

منبع

 

 

ماشین بردار پشتیبان (svm) قسمت 1
ماشین بردار پشتیبان (svm) قسمت 2
ماشین بردار پشتیبان (svm) قسمت 3