[Amin_Mansouri]

تولباکس برنامه ریزی ژنتیک - Genetic Programming Toolbox

برنامه ریزی ژنتیک (Genetic Programming) و یا به اختصار GP، یکی از روش های قدرتمند در حوزه الگوریتم های تکاملی است و اصول آن مبتنی بر الگوریتم ژنتیک است. اما طرز نمایش جواب ها در این روش، به صورت ساختارهای درختی است که برای حل مسائل مختلف می تواند مورد استفاده قرار بگیرد. ساختار درختی کروموزوم ها در روش برنامه ریزی ژنتیک، این الگوریتم را به ابزاری قوی و مناسب برای حل مسائل مدل سازی تبدیل می کند.

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

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

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

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

الگوریتم ژنتیک ترکیب شده با الگوریتم پرندگان



الگوریتم ژنتیک، شناخته شده تربن و پرکاربرد ترین ابزار بهینه سازی تکاملی است. این الگوریتم در اغلب مسائل بهینه سازی به ویژه بهینه سازی گسسته، کارایی بالایی از خود نشان داده است. اما در حل مسائل پیوسته آنچنان که باید و شاید، کاراریی این الگوریتم نشان داده نشده است. در مقابل الگوریتم بهینه سازی انبوه ذرات که در داخل ایران به الگوریتم پرندگان نیز شناخته می شود، در حل مسائل گسسته بسیار موفق عمل کرده است. بنابراین یک ایده برای افزایش کارایی الگوریتم ژنتیک در حل مسائل پیوسته می تواند ترکیب آن با الگوریتم پرندگان (Hybrid Genetic and Particle Swarm Optimization) باشد.



متلب سایت در راستای رسالت علمی خود بر آن است تا مراجعین محترم را نه تنها با ابزارهای استاندارد در حوزه هوش مصنوعی آشنا کند، بلکه دریچه ای نیز به سوی جدیدترین متدهای مطرح شده در این حوزه برای مراجعین باز نماید. در این راستا متخصصین بخش بهینه سازی هوشمند متلب سایت، کد Hybrid Genetic and Particle Swarm Optimization را بر مبنای یکی از جدیدترین مقالات منتشر شده تهیه کرده و برای دانلود در اختیار مراجعین محترم قرار داند. بررسی و مطالعه این کد را به همه مراجعین که با الگوریتم های ژنتیک اآشنا هستند، توصیه می کنیم. به همراه کدها مقاله ای که مبنای پیاده سازی بوده است نیز قرار داده شده است.



حل مسئله کوله پشتی توسط الگوریتم ژنتیک



مسئله کوله پشتی چیست؟ فرض کنید که جهانگردی می خواهد کوله پشتی خود را با انتخاب حالتهای ممکن از بین وسائل گوناگونی که بیشترین راحتی را برایش فراهم می سازند پر کند. این مسئله می تواند با شماره گذاری این وسائل از 1 تا n و تعریف برداری از متغیرهای دودویی(Binary) (j = 1,2,…n) بصورت ریاضی فرمول بندی شود. به این معنی که: اگر شیء j ام انتخاب شود در غیر اینصورت وقتی میزان راحتی باشد که وسیله j ا م فراهم می آورد و وزن آن و c اندازه کوله پشتی باشد. مسئله ما انتخاب برداری از بین بردارهای دودویی x است،که محدودیت را بر آورده کند. بطوریکه تابع هدف ماکزیمم مقدار خود را بگیرد.

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

فرض کنید که شما مایل به سرمایه گذاری همه یا قسمتی ازسرمایه تان باشید. اگر مبلغی که برای سرمایه گذاری در نظر گرفتید c دلار باشد و n مورد برای سرمایه گذاری ممکن باشد ، اجازه دهیدکه سود حاصل از سرمایه گذاری j ام و مقدار دلارهایی باشد که آن سرمایه گذاری لازم دارد . بدین ترتیب جواب بهینه مسئله کوله پشتی که تعریف کردیم به ما این امکان را می دهدکه بهترین حالت ممکن را از بین حالتهای مختلف سرمایه گذاری انتخاب کنیم.

در این رابطه باید روشی برای حل این مسئله پیدا کرد . یک روش ابتدایی که در نگاه اول توجه ما را به خود جلب می کند ، عبارت از برنامه نویسی برای کامپیوتر به منظور امتحان کردن تمامی بردارهای دودویی ممکن x است، تا از بین بردارهایی که محدودیت مسئله را ارضاء می کنند بهترین را انتخاب کند. متاسفانه تعداد چنین بردارهایی است.بطوریکه یک کامپیوتر فرضی که می تواند یک بیلیون بردار را در یک ثانیه امتحان کند؛برای n = 60 بیش از 30 سال وقت لازم دارد و بیش از 60 سال برای n = 61 و دهها قرن برای n = 65 والی اخر.

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

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

لیست مقالات ژنتیک تا به اینجا:

1. مکان یابی avr در شبكه های توزیع شعاعی با استفاده از میكرو- الگو ریتم ژنتیک
2. بهبود الگوریتم ژنتیكی با استفاده از روال جستجوی محلی در مساله تخصیص سلاح-هدف
3. مدلی مبتنی بر الگوریتم ژنتیك برای انتخاب/استخراج ویژگی و بهینه سازی پارامترهای svm
4. خوشه بندی گرهها در شبكه های سنسور بی سیم با استفاده از الگوریتم ژنتیك
5. طراحی و پیاده سازی یك الگوریتم ژنتیك موازی مبتنی بر عامل ها برای مذاكره های خودكار چند-خصیصه ای
6. طراحی طبقه بندی كننده ی چند كلاسه با استفاده از برنامه نویسی ژنتیك
7. بهبود الگوریتم بهینه سازی اجتماع ذرات با استفاده از عملگرهای الگوریتم ژنتیک
8. شناسایی پارامترهای مجهول سیستم آشوبی به منظور سنكرون سازی توسط الگوریتم ژنتیك
9. بهبود كارایی الگوریتم های ژنتیك كوانتومی با استفاده از جستجوی محلّی Simulated Annealing
10. استفاده از یك روش تقسیم حل برای تعیین مقدار اولیه مناسب برای الگوریتم های ژنتیك كوانتوم
11. طراحی فیلتر دیجیتال آزمونهای دینامیكی در تونل باد و بهینه سازی آن بر اساس الگوریتم ژنتیك
12. بهینه سازی شکل سازه فضا کار چلیک دو لایه با استفاده از الگوریتم ژنتیک
13. مدیریت بهینه شبکه های توزیع آب از طریق تعیین میزان بهینه تزریق کلر با استفاده از مدل تحلیل کیفی epanet و الگوریتم ژنتیک
14. بهینه سازی طراحی تراكم دینامیكی بوسیله الگوریتم ژنتیك
15. كاربرد الگوریتم ژنتیك در تعیین عمق بحرانی در كانالهای باز
16. استفاده از الگوریتم ژنتیك در محاسبه معكوس روسازی انعطاف پذیر
17. طراحی بهینه سیستم كنترل سیلاب عسلویه با استفاده از الگوریتم ژنتیك
18. بهینه سازی كمی – كیفی بهره برداری از چاههای نزدیك ساحل با استفاده از الگوریتم ژنتیك
19. ارائه یك روش جدید درتشخیص خطاهای بارز بر مبنای بكارگیری مفاهیم الگوریتم‌های ژنتیكی
20. كاربرد الگوریتم ژنتیك در مكان یابی بهینه مهاربندهای ضربدری در قابهای فلزی دو بعدی
21. تعیین زمان بهینه تعویض لوله ها در شبکه های توزیع آب شهری با استفاده ار الگوریتم ژنتیك
22.تعیین اندازه محموله سفارش موجودی در زنجیره تامین و انتخاب تامین کننده با رویکرد الگوریتم ژنتیک

کاربردهای شبکه عصبی در OCR


این گزارش به بررسی كاربردهای شبكه های عصبی مصنوعی در بازشناسی شناسه های دستنویس اختصاص دارد. این كاربردها را میتوان به سه دسته تقسیم كرد: كاربرد در پیش پردازش، كاربرد در بخش بندی و كاربرد در دسته بندی. بعضی از كاربردهای پیش پردازشی مربوط به یادگیری فیلترهای مناسب برای بهبود تصویر، تعیین زاویه چرخش شناسه یا سند حاوی شناسه ها برای اصلاح آن و خوشه بندی پیكسل های مربوط به شناسه، برای باریك سازی آن است. در بخش بندی، از شبكه عصبی برای تعیین تعداد شناسه های موجود در تصویر ورودی و جداسازی آنها از هم استفاده می شود. در مهم ترین كاربرد یعنی دسته بندی، از شبكة عصبی برای تعیین دستة مربوط به الگوها استفاده می شود. علاوه بر استفاده از شبكه های عصبی جهت دسته بندی به صورت منفرد، از آنها به صورت تركیبی نیز استفاده می شود. بعضی روش ها، شبكة عصبی را برای تركیب خروجی بدست آمده از دسته بندهای منفرد به كار گرفته اند.

واژه های كلیدی

پیش پردازش، بخش بندی، دسته بندی، استخراج ویژگی، رمزگذاری ورودی.



1- مقدمه

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


2- پیش‎پردازش

عملیات پیش‎پردازش، فرآیندی برای ارتقای تصویر ورودی است که آن را برای تحلیل و بازشناسی در مراحل بعد مهیا می‎سازد. از مهمترین مراحل پیش‎پردازش می‎توان به دوسطحی‎سازی (binarization)، بهبود تصویر و اصلاح چرخش (skew correction) اشاره کرد.
2-1- بهبود تصویر

رهیافت متداول در کاهش نویز و ترمیم تصویر، استفاده از فیلترهای مختلف نظیر فیلترهای ریخت‎شناسی است. نکته مهم در مورد این نوع فیلترها آن است که معمولاً برای انواع خاصی از نویز مناسبند و سازگارسازی آنها برای حذف نویزهای دیگر به سادگی ممکن نیست. یک گزینة مناسب برای سازگار نمودن فیلترها جهت مواجه با منابع نویز جدید، استفاده از شبکه عصبی است. شبکه عصبی می‎تواند فیلترهای مناسب را با استفاده از تعدادی الگو یاد بگیرد. تنها با در اختیار داشتن یک یا چند تصویر و تخریب شدة آنها توسط یک منبع نویز، می‎توان شبکة عصبی را آموزش داد.
در مرجع (۱)، یک روش وفق‎پذیر برای بهبود تصاویر اسناد چاپی با استفاده از پرسپترون چند لایه پیشنهاد شده است. در این روش، ابتدا شناسه‎ها به صورت جداگانه تعیین مکان و بازشناسی می‎شوند و سپس تصویر اصلی آنها با استفاده از اطلاعات تصویری بازسازی می‎شود. در مرحلة بعد، شبکة عصبی با استفاده از تصویر اصلی و بازسازی شدة شناسه‎ها آموزش داده می‎شود. در نهایت، فیلتر بدست آمده روی کل تصویر اعمال می‎شود. نحوة آموزش به این صورت است که یک پنجرة مربعی روی تصویر تخریب شده حرکت داده می‎شود و پیکسل‎هایی که در این پنجره قرار می‎گیرند به عنوان ورودی شبکه و پیکسل متناظر با مرکز پنجره از تصویر اصلی به عنوان خروجی مطلوب در نظر گرفته می‎شوند (به شکل 1-1 توجه کنید).




شکل 1-1) بهبود تصویر با استفاده از شبکة عصبی

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

2-2- اصلاح چرخش

در بسیاری موارد تصویر سند با محورهای تصویر تراز نیست که می‎تواند در نرخ بازشناسی تاثیر قابل ملاحظه‎ای بگذارد. در چنین مواردی، چرخش تصویر ضروری به نظر می‎آید. برای حل این مشکل، روش‎هایی هم برای کل تصویر صفحه (۲) و هم برای شناسه‎های منفرد (۳) ارائه شده است که مبتنی بر شبکة عصبی هستند. در هر دو مورد، تعدادی ویژگی از از تصویر استخراج می‎شود و به عنوان ورودی به پرسترون چند لایه داده می‎شود تا شبکه میزان چرخش را در تنها نرون خروجی‎اش مشخص کند.

2-3- باریک‎سازی

یکی از مراحل پیش‎پردازش که معمولاً پیش از استخراج ویژگی انجام می‎شود، باریک‎سازی است. انجام باریک‎سازی قبل از استخراج ویژگی سبب حذف بخش عمده‎ای از اطلاعات اضافه و باقی ماندن اطلاعات ساختاری می‎شود. یکی از رهیافت‎های باریک‎سازی، استفاده از خوشه‎بندی است. بعضی از شبکه‎های عصبی، به عنوان ابزاری برای خوشه‎بندی، امکان پیاده‎سازی این گونه روش‎های باریک‎سازی را فراهم می‎آورند. در (۴)، روشی برای باریک‎سازی با استفاده از شبکه‎های خودسازمانده SOM پیشنهاد شده است. نحوة کار به این ترتیب است که ابتدا، پیکسل‎های مربوط به شناسه خوشه‎بندی می‎شوند و سپس مراکز خوشه‎ها به هم وصل می‎شوند. از آنجا که نحوة اتصال خوشه‎ها که هر کدام متناظر با تجمعی از پیکسل‎های شناسه است، شبیه یک گراف می‎باشد و از قبل نمی‎توان آن را پیش‎بینی کرد، لذا در روش پیشنهادی همسایگی نرون‎های خروجی هنگام یادگیری تغییر می‎کنند.

3- بخش بندی

بخش‎بندی، عبارت است از تقسیم تصویر یک کلمه یا تعدادی شناسة متصل به تعداد زیر تصویر که معمولاً هر کدام یک شناسه است. شبکة عصبی می‎تواند برای بخش‎بندی به کار گرفته شد. کاربرد اول تشخیص شناسه‎های به هم چسبیده است و دومی تعیین مکان برش برای جداسازی آنها از هم.
در (۵)، روشی برای تمیز دادن شناسه‎های منفرد از شناسه‎های به هم چسبیده پیشنهاد شده است، که مشخص می‎کند تصویر ورودی‎اش مربوط به یک شناسه است یا از دو شناسة به هم چسبیده تشکیل شده است (شکل 2-1 الف را ببینید). شبکة مورد استفاده در این روش، یک پرسپترون چند لایه است که در لایة خروجی دو نرون دارد. ورودی شبکه پیکسل‎های مربوط به تصویر نرمال شده ورودی به صورت یک تصویر با ابعاد ثابت است. مجموعه‎ای که برای آموزش شبکه مورد نظر ایجاد شده است، شامل 17000 تصویر مربوط به شناسه‎های تک و جفت می‎باشد که به صورت مصنوعی با استفاده از بیش از 30 فونت مختلف ایجاد شده بودند. نکتة قابل توجه در مورد سیستم ایجاد شده با استفاده از این روش، قابلیت تعمیم خوب این روش برای تشخیص جفت شناسه‎هایی بود که به صورت مصنوعی به هم متصل نشده بودند.
این روش را می‎توان توسعه بخشید و از آن برای تشخیص تعداد شناسه‎های به هم چسبیدة بیشتری استفاده کرد. در (۶)، روش مشابهی پیشنهاد شده است که برای تعیین تعداد ارقام موجود در تصاویر مربوط به اعداد می‎باشد. در این روش، شبکة عصبی باید تعیین کند که عدد ورودی یک رقمی، دو رقمی، سه رقمی و یا چهار رقمی است.
کاربرد دوم شبکة عصبی، تعیین نقطة برش جهت جداسازی شناسه‎ها از هم است. در (۷)، از یک پرسپترون چند لایه برای تعیین نقاط برش در کلمات دست‎نویس استفاده شده است. در این روش، یک پنجره نازک به صورت افقی روی تصویر کلمه جابجا می‎شود و شبکه تعیین می‎کند که مکان فعلی پنجره برای برش مناسب است یا خیر (به شکل 2-1 ب توجه کنید). از هر پنجره تعدادی ویژگی استخراج می‎شود و به ورودی شبکه اعمال می‎شود و خروجی تعیین می‎کند برش صورت گیرد یا خیر.



شکل 2-1) استفاده از شبکة عصبی برای بخش‎بندی. الف) تعیین تک شناسه یا جفت شناسة به هم چسبیده. ب) تعیین اینکه آیا یک نقطه برای برش مناسب است یا خیر. ج) تعیین مقطع برش عمودی از میان هشت گزینة ممکن.

در (۸) نیز روش دیگری برای تعیین نقطه برش پیشنهاد شده است. در این روش، فرض بر آن است که حداکثر دو شناسه در تصویر وجود دارد. نحوة کار به این صورت است که ابتدا، ابعاد تصویر به 60×30 تغییر می‎یابد. سپس تعداد پیکسل‎های سیاه در هر پنجرة 5×5 شمرده می‎شود و به عنوان یک ویژگی در نظر گرفته می‎شود. در مجموع 72 ویژگی از هر تصویر استخراج می‎شود و شبکه بر اساس آنها تعیین می‎کند محل برش کدام یک از مقاطع عمودی است. شبکه به تعداد مقاطع عمودی، خروجی دارد و نقطة برش با توجه به بیشترین مقدار خروجی مشخص می‎شود. پس از برش، شناسه‎ها به صورت جداگانه به یک دسته‎بند برای دسته‎بندی داده می‎شود. چنانچه شناسه‎ها در دسته‎بندی رد شوند، نقطة برش بعدی در نظر گرفته شده و فرآیند تکرار می‎شود. این روش مستلزم ایجاد نمونه‎های آموزشی به صورت دستی است.
توسعه سیستم‎هایی که بتوانند بیش از یک نقطة برش را تشخیص دهند، با دشواری‎هایی مواجه است. این مشکل از آنجا ناشی می‎شود که گاهی در یک مکان از کلمه، 3 حرف با روی هم افتادگی دارند و 3 حرف ده‎ها هزار ترکیب مختلف را ایجاد می‎کنند که مستلزم یک مجموعة آموزشی بسیار بزرگ است. از سوی دیگر، برچسب زدن نمونه‎های آموزشی (تعیین نقاط برش) کار دشواری است و باید به صورت دستی انجام گیرد. به همین دلیل، در بیشتر موارد از مجموعه‎هایی که به صورت مصنوعی ایجاد شده‎اند، استفاده می‎شود.
با وجود مشکلاتی که برای روش‎های مبتنی بر شبکه‎های عصبی گفته شد، این روش‎ها دارای مزایای قابل توجهی نسبت به سایر روش‎های متداول هستند. اول آنکه، قادر به مواجه با سطوح مختلفی از روی‎هم افتادگی هستند. مورد دوم مربوط به زمان اجرای کمتر آنها نسبت به روش‎های پیچیده‎تر است.

4- دسته‎بندی

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

4-1- بازنمایی الگو و رمزگذاری

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



کل 4-1) توصیف یک شکل توسط گراف بر مبنای ویژگی‎های مرزی و ساختار پردازشی مربوط به آن

شکل 4-1) توصیف یک شکل توسط گراف بر مبنای ویژگی‎های مرزی و ساختار پردازشی مربوط به آن



در (۱۰)، روشی برای بازشناسی الگوهایی که توسط گراف‎های جهت‎دار مرتب بدون دور توصیف می‎شوند، ارائه شده است. مبنای این روش، ایجاد یک توصیف گرافی مناسب برای هر الگوی معین است. شکل 4-1، یک الگو را همراه با گراف توصیف کننده و ساختار پردازشی مربوط به آن را نشان می‎دهد. نحوة ایجاد گراف به این صورت است که به هر مرز یک گره نسبت داده می‎شود. تمام مرزهای داخلی مربوط به هر مولفه از تصویر، به عنوان فرزندان مرز خارجی آن در نظر گرفته می‎شود. این کار به صورت بازگشتی برای مولفه‎های متداخل تکرار می‎شود. الگوهای پیچیده‎تر را می‎توان توسط گراف‎های عمومی‎تر نمایش داد، اما معماری شبکه‎های عصبی کلاسیک و الگوریتم‎های یادگیری مربوط به آنها ناکاراتر می‎شوند.

مورد دیگری که هنگام استفاده از شبکه‎های عصبی مطرح می‎‎شود، نحوة رمزگذاری خروجی است. رمزگذاری خروجی، شیوة تعبیر از خروجی‎های شبکه جهت اعمال به مسئله را مشخص می‎کند و با توجه به الزامات مسئله تعیین می‎شود. در مورد شبکة عصبی پرسپترون چند لایه، رمزگذاری خروجی معمولاً به این صورت است که به ازای هر دسته، یک خروجی در نظر گرفته می‎شود و دستة الگوی ورودی متلعق به دسته‎ای است که خروجی متناظر با آن بیشترین مقدار را داشته باشد. این نحوة رمزگذاری خروجی همواره ممکن نیست. به عنوان مثال، زمانی که از شبکه‎های خودانجمنی استفاده می‎شود، خروجی شبکه یک الگوست و نمی‎تواند به صورت گفته شده باشد. در (۹) یک روش رمزگذاری خروجی برای شبکه‎های خودانجمنی پیشنهاد شده است. در این روش، یک شبکه به هر دسته اختصاص دارد و تعدادی از الگو‎های متعلق به آن دسته را یاد می‎گیرد. هنگام دسته‎بندی، الگوی ورودی مربوط به دسته‎ای است که خروجی شبکة متناظر با آن، فاصلة کمتری با الگوی ورودی داشته باشد ( به شکل 4-2 توجه کنید).


شکل 4-2) استفاده از چند شبکة عصبی انجمنی برای دسته‎بندی



4-2- استخراج ویژگی مبتنی بر بردار

شبکه‎های عصبی کلاسیک به خوبی با روش‎های استخراج ویژگی مبتنی بر بردار سازگار هستند. زمانی که ویژگی‎های استخراج شده از تصویر ورودی به صورت یک بردار با طول ثابت باشند، طیف وسیعی از انواع مختلف شبکه‎های عصبی را می‎توان مورد استفاده قرار داد. پرکاربرد ترین شبکة عصبی را می‎توان پرسپترون چندلایه دانست. در کنار آن، شبکه‎های عصبی دیگر نظیر RBF، LVQ، SVM و ... نیز در کاربردهای دسته‎بندی مورد استفاده قرار می‎گیرند. در این میان، بکارگیری SVM روند رو به رشدی دارد و در بسیاری حوزه‎ها عملکرد بهتری را نسبت به پرسپترون چند لایه نشان داده است.
فرآیند بکارگیری این شبکه‎ها (استفاده از آنها به تنهایی و نه به صورت ترکیبی) روشن است. بیشتر مقالاتی که از این گونه از شبکه‎ها بهره گرفته‎اند، تمرکز اصلی آنها روی استخراج ویژگی‎ها مناسب، ایجاد ترکیبی از دسته‎بندها (classifier) و انتخاب ویژگی جهت بهبود سرعت و کارایی تمرکز دارند. در (۱۱) و (۱۲)، استفاده از پرسپترون چند لایه برای دسته‎بندی شناسه مورد نظر قرار گرفته است. در (۱۳)، روشی برای بازشناسی شناسه‎های دست‎نویس پیشنهاد شده است که ابتدا از یک شبکة عصبی خودسازمانده کوهنن و به دنبال آن از یک شبکة LVQ استفاده کرده است. در (۱۴) نیز روشی برای هرس لایه مخفی یک شبکة عصبی شبه RBF پیشنهاد شده است و از آن برای بازشناسی ارقام دست‎نویس فارسی استفاده شده است. در (۱۵)، روشی سریع برای آموزش SVM پیشنهاد شده است و از آن برای بازشناسی شناسه‎های چینی استفاده شده است. در (۱۶) نیز روشی برای بازشناسی شناسه‎های دست‎نویس با استفاده از SVM ارائه شده است که از تبدیل موجک (wavelet) برای استخراج ویژگی بهره می‎برد.

4-3- رمزگذاری ویژگی‎های ساختاری

منظور از ویژگی‎های ساختاری، ویژگی‎هایی هستند که شناسه‎ها را به صورت یک مجموعه از اجزا و رابطة بین آنها توصیف می‎کنند. دو راه برای استفاده از این نوع ویژگی‎ها با استفاده از شبکه‎های عصبی متداول وجود دارد. روش اول، تبدیل آنها از قالب اطلاعات طول متغیر به برداری با طول ثابت است که به سادگی قابل اِعمال به شبکه‎های معرفی شده در بخش 4-2 هستند. روش دوم، استفاده از شبکه‎های عصبی بازگشتی است.
یکی از روش‎های توصیف شناسه‎های دست‎نویس، استفاده از مرزها و اسکلت آن است. در (۱۷) روشی پیشنهاد شده است که در آن شناسه بوسیلة یک گراف توصیف می‎شود، بطوریکه گره‎های این گراف مربوط به زیرالگوهای استخراج شده از شناسه و یال‎ها مربوط به موقعیت مکانی بین آنهاست. جهت رمزگذاری این گراف به صورت یک بردار با طول ثابت، به هر گره و یال از گراف، یک موقعیت از پیش تعیین شده در بردار ویژگی نسبت داده شده است. این روش زمانی مناسب است که بیشینه طول بردار از مشخص باشد. یکی از مزایای این روش، نگاشت گراف به یک بردار طول ثابت بدون از دست رفتن اطلاعات است. در (۱۰) روشی پیشنهاد شده است که از یک شبکة عصبی بازگشتی برای پردازش گراف استفاده می‎شود (در بخش 4-1 به آن اشاره شد).

4-4- ساختارهای ترکیبی

گاهی چند شبکة عصبی و یا به طور کلی دسته‎بند، در کنار هم بکار گرفته می‎شوند. در بخش 4-1 به یک نمونه از این ساختارها اشاره شد، که از چند حافظة انجمنی برای دسته‎بندی استفاده می‎کرد (شکل 4-2). قرار دادن چند شبکة انجمنی در کنار هم به دلیل آن است که نمی‎توان یکی از آنها را به تنهایی برای دسته‎بندی مورد استفاده قرار داد، زیرا این نوع از شبکه‎ها اصولاً به عنوان یک حافظه عمل می‎کنند. در بیشتر موارد، ساختارهای ترکیبی از تعدادی دسته‎بند تشکیل شده‎اند که در کنار هم کار می‎کنند و تصمیم نهایی در مورد الگوی ورودی، با توجه به برآیند خروجی آنها گرفته می‎شود.
در (۱۸)، روشی ارائه شده است که در آن سه شبکة عصبی برای شناسایی ارقام با هم ترکیب شده‎اند و رای اکثریت تعیین می‎کند، الگوی ورودی مربوط به چه رقمی است. دو تا از سه شبکة معماری مشابه دارند و تنها تفاوت آنها مربوط به مقداردهی اولیه به وزن‎هایشان است. سومین شبکه با ویژگی‎های متفاوتی تغذیه می‎شود.
روش‎های مختلفی برای ترکیب خروجی در یک سیستم که شامل چند دسته‎بند است، وجود دارد. به عنوان مثال، می‎توان به رای اکثریت، رای مطلق و رای‎گیری وزن‎دار (خروجی دسته‎بندها با یک درجات اهمیت مختلف مورد رسیدگی قرار می‎گیرند) اشاره کرد. البته روش‎های ترکیب محدود به این سه مورد نیست. در (۱۹)، روشی پیشنهاد شده است که در آن از یک شبکة عصبی برای ترکیب خروجی‎ها استفاده شده است. خروجی هر یک از دسته‎بندها، به صورت مستقیم با یک اتصال وزن‎دار به خروجی نهایی سیستم متصل شده است (شکل 4-3 الف). در (۲۰) روش مشابهی به کار گرفته شده است که در آن اجزای تشکیل دهندة سیستم، شامل دسته‎بند‎های منفرد و ترکیب‎کننده، همگی شبکة عصبی هستند (شکل 4-3 ب). این سیستم شامل ده دسته‎بند منفرد است که هر کدام مسئول تشخیص یک رقم خاص می‎باشد و به این ترتیب بردار خروجی هر کدام از آنها با بقیه متفاوت است.


شکل 4-3) استفاده از شبکة عصبی برای ترکیب خروجی‎ها. الف) سیستمی با ترکیب‎کنندة شبکة عصبی که از سه دسته‎بند منفرد تشکیل شده است. ب) مشابه الف با این تفاوت که دسته‎بندها هم شبکة عصبی‎اند

گاهی تعداد دسته‎ها زیاد است و می‎توان برای بهبود کارایی سیستم آنها را به چند دسته تقسیم کرد. به عنوان مثال، شناسه‎های زبان انگلیسی را می‎توان به سه دستة حروف بزرگ، حروف کوچک و ارقام تقسیم نمود. در ]21[، ساختاری با سه دسته‎بند ویژه برای هر یک از دسته‎های عمومی، پیشنهاد شده است (شکل 4-4). دسته‎بندی در این سیستم، در دو مرحله انجام می‎شود. ابتدا شبکة انتخاب کننده، دسته‎بند مناسب را فعال می‎کند و سپس، دسته‎بند انتخاب شده الگوی ورودی را دسته‎بندی می‎کند.


شکل 4-4) استفاده از یک دسته‎بند انتخابگر برای تعیین دسته‎بند مناسب جهت دسته‎بندی الگوی ورودی


5- جمع‎بندی و پیشنهادها

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

مراجع

[1] P. Stubberud, J. Kanai, and V. Kalluri, “Adaptive image restoration of text images that contain touching or broken characters”, in Proc. 3rd Int'l Conf. Doc. Anal. Rec., pp. 778-781, 1995.
[2] N. Rondel and G. Burel, “Cooperation of multilayer perceptrons for the estimation of skew angle in text document images”, in Proc. 3rd Int'l Conf. Doc. Anal. Rec., pp. 1141-1144, 1995.
[3] R. Palaniappan, P. Raveendran, and S. Omatu, “New invariant moments for non-uniformly scaled images”, Pattern Analysis and Applications, vol. 3, no. 2, pp. 78-87, 2000.
[4] P. Ahmed, “A neural network based dedicated thinning method”, Pattern Recognition Letters, vol. 16, no. 6, pp. 585-590, 1995.

[5] J. Wang and J. Jean, “Segmentation of merged characters by neural networks and shortest path”, Pattern Recognition, vol. 27, no. 5, pp. 649-658, 1994.

[6] Z. K. Lu, Z. Chi, and W. C. Siu, “Length estimation of digits strings using a neural network with structure based features”, SPIE/IS&T Journal of Electronic Imaging, vol. 7, pp. 79-85, January 1998.
[7] B. Eastwood, A. Jennings, and A. Harvey, “A low level feature based neural network segmenter for fully cursive handwritten words”, in Proc. 4th Int'l Conf. Doc. Anal. Rec., p. 523, 1997.
[8] J. H. Bae, K. Jung, J. Kim, and H. Kim, “Segmentation of touching characters using an MLP”, Pattern Recognition Letters, vol. 19, no. 8, pp. 701-709, 1998.
[9] D. E. Rumelhart, J. L. McClelland, and the PDP Research Group, Parallel Distributed Processing: Explorations in the Microstructure of Cognition, vol. 1. Cambridge: MIT Press, 1986.
[10] P. Frasconi, M. Gori, and A. Sperduti, “A general framework for adaptive processing of data structures”, IEEE Trans. Neural Networks, vol. 9, no. 5, pp. 768-786, 1998.
[11] M. Bishop (1995). Neural Networks for Pattern Recognition. Oxford Univ. Press, Oxford-U.K.
[12] Y. LeCun, L. Bottou, G. B. Orr, K. R. Muller (1998a). Eficient backprop. In G. Orr and K.Miller, editors, Neural Networks: Tricks of the Trade. Springer.
[13] K.V. Prema, N,V. Subba reddy, “Two-tier architecture for unconstrained handwritten character recognition”, Sadhana Vol. 27, Part 5, October 2002, pp. 585–594.
[14] م. زیارت‎بان، ر. صفابخش، م. ازوجی، "روشی سریع برای هرس لایة مخفی در شبکة عصبی NN-MLP به منظور بازشناسی ارقام دست‎نویس فارسی"، دوازدهمین کنفرانس بین‎المللی انجمن کامپیوتر ایران، اسفند 1385.
[15] J.X. Dong, A. Krzyzak, C.Y. Suen, “High accuracy handwritten Chinese character recognition using support vector machine”, Proc. Int. Workshop on Artificial Neural Networks for Pattern Recognition, Florence, Italy, 2003.
[16] A. Mowlaei, K. Faez, “Recognition of Isolated Handwritten Persian/Arabic Characters And Numerals Using Support Vector Machine”, IEEE workshop on Neural Networks for signal processing 2003.
[17] A. Amin, H. Al-sadoun, and S. Fischer, “Hand-printed Arabic character recognition system using an artificial network”, Pattern Recognition, vol. 29, no. 4, pp. 663-675, 1996.
[18] N. W. Strathy and C. Y. Suen, “A new system for reading handwritten zip codes”, in Proc. 3rd Int'l Conf. Doc. Anal. Rec., pp. 74-77, 1995.
[19] D. Lee and S. N. Srihari, “Dynamic classifier combination using neural network”, in Proc. SPIE-Doc. Rec. II, pp. 26-37, 1995.
[20] L. Mui, A. Agarwal, A. Gupta, and P. S.-P. Wang, “An adaptive modular neural network with application to unconstrained character recognition”, Int. Journal of Pattern Recognition and Artificial Intelligence, vol. 8, no. 5, pp. 1189-1204, 1994.

[21] J. Mao, K. Mohiuddin, and T. Fujisaki, “A two-stage multi-network OCR system with a soft pre-classifier and a network selector”, in Proc. 3rd Int'l Conf. Doc. Anal. Rec., pp. 78-81, 1995



http://intelligence2076.blogfa.com/post-12.aspx