تولباکس برنامه ریزی ژنتیک - 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
