در آمیزش تک نقطه‏ای, یک موقعیت تصادفی بین دو ژن در نظر گرفته می‏شود. سپس تمامی ژن‏های طرف راست یا طرف چپ این موقعیت در کروموزوم‏های والد با یکدیگر جابجا می‏شوند تا کروموزوم‏های جدید بدست آیند.
در آمیزش دو نقطه‏ای، دو موقعیت به صورت تصادفی انتخاب می‏شود و تمامی ژن‏های بین این دو موقعیت در کروموزوم‏های والد با یکدیگر جابجا می‏شوند.
لازم به ذکر است که آمیزش معمولاً بر روی همه زوج کروموزوم‏های انتخاب شده برای جفت‏گیری به کار برده نمی‏شود. معمولاً احتمال آمیزش برای هر زوج کروموزوم بین ۶/۰ تا ۹۵/۰ در نظر گرفته می‏شود که به این عدد نرخ آمیزش(Crossover Rate) یا احتمال آمیزش(Crossover Probability) گفته می‏شود و با Pc نمایش داده می‏شود. در صورتی که بر روی یک زوج کروموزوم عمل آمیزش صورت نگیرد, فرزندان با تکرار نمودن والدین تولید می‏شوند

جهش: پس از اتمام عمل آمیزش، عملگر جهش بر روی کروموزوم‏ها اثر داده می‏شود. این عملگر یک ژن از یک کروموزوم را به طور تصادفی انتخاب نموده و سپس محتوای آن ژن را تغییر می‏دهد. اگر ژن از جنس اعداد دودویی باشد، آن را به وارونش تبدیل می‏کند و چنانچه متعلق به یک مجموعه باشد، مقدار یا عنصر دیگری از آن مجموعه را به جای آن ژن قرار می‏دهد. در شکل۲-۹ چگونگی جهش یافتن پنجمین ژن یک کروموزوم نشان داده شده است.
شکل ‏۲‑۹ نمونه ای از انجام جهش بر روی یک کروموزوم
پایان: تولید نسل در الگوریتم ژنتیک تا رسیدن یه شرط پایان ادامه می یابد. از شروط پایان الگوریتم ژنتیک میتوان یه رسیدن به تعداد تولید نسل های معین و یا رسیدن یه بالاترین مقدار تابع شایستگی اشاره کرد.
طبقه بندی تصاویر
در پردازش تصویر جهت طبقه بندی تصاویر دو دسته کلی الگوریتم های طبقه بندی نظارت نشده و الگوریتم های طبقه بندی نظارت شده وجود دارند.
در طبقه بندی نظارت نشده، پیکسل ها با توجه به مقدار عددی آن ها DN)) گروه بندی می شوند. این گروه ها اصطلاحا خوشه نامیده می شوند. تعیین تعداد خوشه های طبقه بندی با انتخاب کاربر انجام می شود.الگوریتم های متنوعی برا ی طبقه بندی نظارت نشده از قبیل K-means و ISODATA وجود دارند.
در طبقه بندی نظارت شده ابتدا قسمت هایی از تصویر به عنوان نمونه های آموزشی^[۲۸] انتخاب می شوند و الگوریتم طبقه بندی نظارت شده با بهره گرفتن از این نمونه های آموزشی تصویر را در تعدادی کلاس برابر با تعداد نمونه های آموزشی طبقه بندی می کند. از جمله الگوریتم های طبقه بندی نظارت شده می توان به الگوریتم های بیشترین شباهت، کمترین فاصله و الگوریتم ماشین بردار پشتیبان اشاره کرد.
از جمله مهمترین الگوریتم های طبقه بندی نظارت شده می توان به الگوریتم SVM اشاره کرد الگوریتم SVM، که جزء الگوریتم های تشخیص الگو دسته بندی می شود. از الگوریتم SVM، در هر جایی که نیاز به تشخیص الگو یا دسته بندی اشیا در کلاس های خاص باشد می توان استفاده کرد.
طبقه بندی الگوریتم ماشین بردار پشتیبان (SVM)
الگوریتم SVM اولیه در ۱۹۶۳ توسط Vladimir Vapnik ابداع شد و در سال ۱۹۹۵ توسط Vapnik وCorinna Cortes برای حالت غیرخطی تعمیم داده شد[۲۸].
این روش از جمله روش‌های نسبتاً جدیدی است که در سال‌های اخیر کارایی خوبی نسبت به روش‌های قدیمی‌تر برای طبقه‌بندی از جمله شبکه‌های عصبی نشان داده است. مبنای کاری دسته‌بندی کننده SVM دسته‌بندی خطی داده‌ها است و در تقسیم خطی داده‌ها سعی می‌کند خطی را انتخاب کند که حاشیه اطمینان بیشتری داشته باشد. حل معادله پیدا کردن خط بهینه برای داده‌ها به وسیله روش‌های QP (Quadratic Programming) که روش‌های شناخته شده‌ای در حل مسائل محدودیت‌دار هستند صورت می‌گیرد.
SVM از یک تکنیک که kernel trick نامیده می شود، برای تبدیل داده ها استفاده می کند و سپس بر اساس این تبدیل، مرز بهینه بین خروجی های ممکن را پیدا می کند. به عبارت ساده تبدیلات بسیار پیچیده را انجام می دهد، سپس مشخص می کند چگونه داده ها را بر اساس برچسب ها یا خروجی هایی که تعریف شده، جدا کند.
ایده اصلی در SVM اینست که با فرض اینکه دسته ها بصورت خطی جداپذیر باشند، ابرصفحه هایی با حداکثر حاشیه (maximum margin) را بدست می آورد که دسته ها را جدا کنند[۲۹]. در مسایلی که داده ها بصورت خطی جداپذیر نباشند، داده ها به فضای با ابعاد بیشتر نگاشت پیدا می کنند تا بتوان آنها را در این فضای جدید بصورت خطی جدا نمود.
یک فرایند یادگیری که شامل دو کلاس می باشد، هدف SVM پیدا کردن بهترین تابع برای طبقه بندی می باشد به نحوی که بتوان اعضای دو کلاس را در مجموعه داده ها از هم تشخیص داد. معیار بهترین طبقه بندی به صورت هندسی مشخص می شود، برای مجموعه داده هایی که به صورت خطی قابل تجزیه هستند. به طور حسی آن مرزی که به صورت بخشی از فضا تعریف می شود یا همان تفکیک بین دو کلاس بوسیله Hyperplane تعریف می شود. همین تعریف هندسی به ما اجازه می دهد تا کشف کنیم که چگونه مرزها را بیشینه کنیم ولو اینکه تعداد بیشماریHyperplane داشته باشیم و فقط تعداد کمی، شایستگی راه حل برای SVM دارند.
روش طبقه بندی SVM، یک روش آماری غیرپارامتریک نظارت شده است و بر اساس این فرض عمل می کند که هیچ گونه اطلاعی از چگونگی توزیع مجموعه ها موجود نیست. ویژگی اصلی این روش توانایی بالا در استفاده از نمونه های تعلیمی کمتر و رسیدن به دقت بالاتر در مقایسه با سایر روش های طبقه بندی است.
ماشین بردار پشتیبان در واقع یک طبقه بندی کننده دودویی است که دو کلاس را با بهره گرفتن از یک مرز خطی از هم جدا میکند. و وابسته به خانواده طبقه بندی کننده های تعمیم یافته است[۳۰]. ماشین بردار پشتیبان، داده ها را با عبور یک صفحه (مرز خطی) و با بهره گرفتن از تمامی باندها و به کارگیری الگوریتم بهینه سازی طبقه بندی می کند. بدین ترتیب که ابتدا نمونه هایی که مرز کلاس ها را تشکیل می دهند، به دست می آیند. نقاطی که کمترین فاصله را تا مرز تصمیم گیری دارند به عنوان بردار پشتیبان در نظر گرفته می شوند. در این روش با افزایش بعد داده ها نتیجه بهتری بدست می آید. در واقع در صورتی که در فضای طیفی، کلاس ها تداخل داشته باشند، داده ها به فضایی با ابعاد بالاتر برده می شوند به گونه ای که تمایز آنها امکان پذیر گردد. هدف این الگوریتم یافتن بیشترین فاصله بین دو کلاس و در نتیجه افزایش دقت طبقه بندی است بگونه ای که خطای تعمیم تا حدامکان کاهش یابد.[۳۱] مولفه اساسی که SVM را از سایر الگوریتم های طبقه بندی نظارت شده متمایز می سازد، پیروی روند پردازش الگوریتم از قاعده ایست که به عنوان کاهش ریسک ساختاری (^[۲۹]SRM) شناخته می شود. در واقع الگوریتم SVM خطاهای کلاس بندی را در داده های مشاهده نشده بدون فرضیه قبلی از احتمال تخریب داده را به حداقل می رساند.[۳۲] برای محاسبه مرز تصمیم گیری دو کلاس کاملا مجزا از هم ، از روش حاشیه بهینه استفاده می شود [۳۳]. مرز خطی بین دو کلاس به گونه ای محاسبه می شود که: اولا تمام نمونه های کلاس ۱+ در یک طرف مرز و تمام نمونه های کلاس ۱- در طرف دیگر مرز مطابق شکل واقع شوند(شکل ۲-۱۰). و ثانیا مرز تصمیم گیری به گونه ای باشد که فاصله نزدیک ترین نمونه های آموزشی هر دو کلاس از یکدیگر ، در راستای عمود بر مرز تصمیم گیری تا جایی که ممکن است حداکثر شود.
شکل ‏۲‑۱۰ طبقه بندی به روش SVM در دوکلاس با بهره گرفتن از کرنل خطی
به عبارت دیگر، در این روش ابتدا فاصله نزدیکترین نمونه های تعلیمی دو کلاس در راستای عمود بر مرزها محاسبه شده و با حل مسئله بهینه سازی، مرز بهینه مشخص می شود. مرز بهینه مرزی است که بیشترین حاشیه را دارا باشد. دو صفحه موازی در دو طرف مرز تصمیم گیری تعریف می شوند، به گونه ای که صفحه مرز بیشترین فاصله مساوی بین دو صفحه موازی را ایجاد کند. هر چه فاصله بین دو صفحه موازی بیشتر باشد دقت کلاس بندی بیشتر خواهد شد.
همانطور که در شکل ۲-۱۱ مشاهده می شود هر دو ابرصفحه به درستی داده ها را از هم جدا کرده است اما ابر صفحه موجود در سمت راست شکل مرزهای بیشتری دارد و میتواند نتایج بهتری تولید کند.
شکل ‏۲‑۱۱ طبقه بندی بهینه دو کلاس با کرنل خطی بصورت بهینه
در حقیقت این الگوریتم در پی یافتن یک ابر صفحه است که بتواند به نحوی عمل کند تا ضمن سازگاری با داده های تعلیمی، توانایی تفکیک و جداسازی مجموعه داده از یکدیگر را نیز داشته باشند [۳۲]. یک ابر صفحه مناسب، صفحه یا جداکننده ای است که بتوان با آن یک همسایگی در اطراف آن ایجاد کرد که علیرغم بیشینه بودن پهنا، پیکسلی داخل آن قرار نگیرد (قاسمیان, ۱۳۸۴). منظور از اصطلاح ابرصفحه جداکننده بهینه، محدوده ای است که بتواند با بهره گرفتن از داده های تعلیمی، پیکسل هایی که به نادرستی طبقه بندی می شوند را به حداقل رساند[۳۲].
برای تعریف این ابرصفحه های جداکننده از کرنل های مختلفی در الگوریتم می توان استفاده کرد. در صورتی که داده ها دارای تداخل زیادی باشند، می توان از کرنل های چند جمله ای و یا از کرنل شعاعی RBF استفاده کرد. روابط مورد استفاد برای کرنل های خطی،چندجمله ای و شعاعی به شرح زیر است.

در روابط فوق T ماتریس ترانهاده ، g بیانگر گاما، d درجه چندجمله ای و و نشان دهنده برداز مولفه i ام و j ام است.
از مزایای اصلی الگوریتم طبقه بندی SVM نسبت به سایر الگوریتم ها طبقه بندی این است که برای داده های با ابعاد بالا طبقه بندی بهتری انجام میدهد و از طرفی نسبت به الگوریتم های دیگر نیاز با داده های آموزشی کمتر نتایج بهتری تولید می نماید.
در تحقیق حاضر نیز به دلیل مزایایی که برای الگوریتم SVM ذکر شد، از این الگوریتم برای طبقه بندی تصاویر استفاده میشود. بدین منظور دو دسته داده به عنوان داده های آموزشی^[۳۰] و داده های آزمایشی^[۳۱]، در محدوده تصویر مورد مطالعه انتخاب شده و به الگوریتم معرفی میشوند.
الگوریتم طبقه بندی SVM نیز برمبنای داده های آموزشی، محدوده داده های آزمایشی را طبقه بندی کرده و با مقادیر واقعی داده های آزمایشی مقایسه می نماید. در نهایت با تشکیل ماتریس خطا، دقت کلی و ضریب کاپا را محاسبه می نماید.
مروری بر مدل نقشه تخریب