بخشی از مقاله
*** این فایل شامل تعدادی فرمول می باشد و در سایت قابل نمایش نیست ***
استفاده از شبکه عصبی هاپفیلد جهت برچسب گذاري عوارض نقطه اي
چکیده
در این تحقیق از شبکه عصبی هاپفیلد١ جهت برچسبگذاري٢ عوارض نقطه اي استفاده میکنیم. این روش مزایا و معایبی نسبت به متدهاي رایج دارد. روشهاي ارائه شده در برچسبگذاري عوارض را به صورت خودکار انجام نمیدهند. زیرا در خودکار نمودن برچسبگذاري عوارض، باید اسامی از پایگاه داده خوانده شده و جایگذاري اسامی در نقشه به طریقه مشابه کسی که علم کارتوگرافی را آموزش دیده باشد، باید انجام شود. همچنین برخی از روشها که به صورت اتوماتیک اینکار را انجام میدهند در روي هم افتادن اسامی عوارض، نمیتوانند تصمیم درستی را براي موقعیت اسامی عوارض اتخاذ نمایند درصورتیکه شبکههاي عصبی با توجه به آموزشهاي که میبینند، میتوانند در انتخاب موقعیت اسامی عوارض تصمیم درستی اتخاذ نمایند. نتایج این تحقیق نشان میدهد که این الگوریتم اجراي خوب و سرعت بالا دارد. از معایب شبکه هاپفیلد میتوان به این مورد اشاره کرد که امکان دارد، شبکه به پاسخی همگرا شود که جزء الگوهاي ذخیره شده در آن نباشد.
کلمات کلیدي: آموزش شبکه عصبی، اصول برچسبگذاري عوارض نقطه اي، تعیین بهترین مکان برچسب عوارض نقطه اي، تابع معیار انرژي، شبکه عصبی هاپفیلد و کارتوگرافی.
١- مقدمه
اسامی نقشه یکی از مهمترین اجزاء نقشه تلقی میشوند. همچنین موقعیت قرار گرفتن بر چسبها نقش مهمی در خوانا بودن و مفید بودن نقشه، اهمیت به سزائی دارند. جایگذاري اسامی نقشه میتواند به صورت دستی انجام شود که یک کار وقتگیر بوده و انرژي زیادي میطلبد. در شیوه سنتی، وظیفه برچسبگذاري بر عهده یک متخصص کارتوگرافی میباشد که به علت زیاد بودن تعداد عوارض نقطه اي در یک نقشه، معمولا کاري دشوار و زمانبر است.[Beus and Crockett, 1994]
تاکنون الگوریتمهاي زیادي جهت انجام برچسبگذاري عوارض به صورت خودکار، ارائه دادهاند. در میان این الگوریتمها، میتوان به الگوریتمهاي پیشنهادي [Doerschler, 1989 and 1992], [Zoraster, 1986] [Yeoli ,1972], [Hirsch, 1982], [Christensen, 1995] اشاره کرد. برخی از روشهاي ارائه شده، برچسبگذاري عوارض را به صورت خودکار انجام نمیدهند. مساله یافتن بهترین آرایش برچسبگذاري جزء مسائل NP-hard میباشد که داراي حل تحلیلی یا ریاضی نمیباشند. راه حلهاي ممکن تلاش میکنند که این پیچیدگی را کاهش دهند و در جهت بهبود پیدا کردن موقعیت اسامی در نقشه حداقل زمان ممکن را بکار گیرند.
زیرا در خودکار نمودن برچسبگذاري عوارض باید اسامی از پایگاه داده خوانده شده و جایگذاري اسامی در نقشه به طریقه مشابه کسی که علم کارتوگرافی را آموزش دیده باشد، باید انجام شود. همچنین برخی از روشها که به صورت اتوماتیک اینکار را انجام میدهند در روي هم افتادن اسامی عوارض، نمیتوانند تصمیم درستی را براي موقعیت اسامی عوارض اتخاذ نمایند درصورتیکه شبکههاي عصبی با توجه به آموزشهاي که میبینند، میتوانند در انتخاب موقعیت اسامی عوارض تصمیم صحیحی اتخاذ نمایند.
در این تحقیق از شبکه عصبی هاپفیلد براي برچسبگذاري عوارض نقطه اي نقشه استفاده شده است. نتایج نشان میدهند که این روش در مقایسه با روشهاي پیچیده مذکور نتیجه مطلوب و موثري ارائه داده است.
٢- اصول برچسبگذاري عوارض نقطه اي
عوارض نقشه از نظر کارتوگرافی به سه بخش کلی نقطه، خط و سطح تقسیم میشوند، که از نظر قواعد برچسبگذاري با هم تفاوت دارند. در این مقاله فقط به بررسی قواعد برچسبگذاري عوارض نقطه اي خواهیم پرداخت. اصول برچسبگذاري عوارض نقطه اي در ذیل ارائه شده است:
برچسبها میبایستی عارضه مورد مراجعه را به درستی نشان دهند و یا به عبارت دیگر ارتباط بین برچسبها و عوارض مورد مراجعه میبایستی به آسانی تشخیص داده شوند.
یکی از هشت موقعیت نشان داده شده در شکل ١، میتواند محلی براي قرارگیري برچسب عارضه مورد نظر در نظر گرفته شود. لازم به ذکر است توسط وزنهاي که تعریف خواهد شد، وزنهاي بالاتر مقدمتر بر نواحی با وزنهاي پایینتر میباشند. در حقیقت موقعیتهاي با شماره شناسایی پایین داراي وزن بیشتري میباشند.
برچسبهاي عوارض نقطه اي نبایستی با برچسبهاي عوارض نقطه اي و خود عوارض نقطه اي تداخل داشته باشند.
٣- شبکه عصبی هاپفیلد
شبکه هاپفیلد جزء شبکههاي حافظه خود انجمنی٣ است که در سال ١٩٨٢ توسط جان هاپفیلد مطرح شد.
فرض کنیدN1 ,..., Nn نرونهاي شبکه و Wij وزن بین دو نرون Ni و N j باشد. اگر W ماتریس وزن بین همه گرهها با یکدیگر باشد، از آنجا که شبکه هاپفیلد متقارن است و نرونها در این شبکه به هم متصل نمیشوند، در نتیجه داریم:
در واقع وزنهاي Wij، شامل اطلاعات مربوط به الگوها هستند. ساختار کلی شبکه هاپفیلد مطابق شکل ٢ میباشد.
همانطور که از ساختار شبکه مشاهده میشود همه نرونها شبیه به یکدیگر عمل میکنند. هیچکدام از نرونها به عنوان ورودي یا خروجی از هم متمایز نمیشوند که این امر وجه بارز اختلاف شبکه هاپفیلد با دیگر شبکههاست و در واقع شبکه هاپفیلد یک شبکه بازگشتی میباشد، بطوریکه نرونها نخست توسط ورودي مقادیر اولیه میگیرند و آنگاه شبکه طوري خود را تکرار میکند که نتیجه نهایی، همگرایی شبکه به یکی از الگوهاي مرجع ذخیره شده در آن باشد، یعنی خروجیها در هر مرحله وروديهاي مرحله بعد را تشکیل میدهند. این فرآیند تا به آنجا ادامه مییابد که خروجیها تغییر نکند و شبکه پایدار شود. معادلاتی که رفتار شبکه هاپفیلد را تبیین میکند عبارتند از:
لازم به ذکر است که در شبکه هاپفیلد براي تابع فعالیت نرونها معمولا از تابع سیگموئید یا تابع تانژانت هیپربولیکی استفاده میشود. همچنین وزنهاي Wij شامل اطلاعات مربوط به الگوها هستند و یا به عبارت دیگر همه الگوها در تابع معیار انرژي منظور شدهاند. نکته حائز اهمیت این است که براي شبکه هاپفیلد، قدمهاي بینابین که به نقاط جذب منتهی میشوند از قبل مشخص نیستند، از این رو احتیاج است که اطلاعات موثر بیشتري علاوه بر ساختار شبکه در اختیار باشد. این اطلاعات در شاخصی به نام تابع معیار انرژي خلاصه میشود. تابع انرژي شبکه داراي حفرههاي است که میتواند به عنوان مکان ذخیرهسازي الگوهاي شبکه، مورد استفاده قرار گیرد در نتیجه میتوان با انتخاب تابع معیار مناسب، الگوها را متناظر با نقاط حداقل محلی تابع معیار قرار داد. در این صورت از طریق اجراي روشهاي متکی بر گرادیان نزولی روي تابع انرژي، شبکه به نقاطی که الگوها در آن ذخیره شدهاند، همگرا میشود.] منهاج، ١٣٧٩[
درحین فرآیند آموزش (قبل از پایدار شدن شبکه)، ثابت میشود که تابع انرژي نزولی است. حالت پایدار نهایی، در حقیقت یک مینیمم محلی تابع انرژي
میباشد. شبکه در حین فرآیند همگرایی داراي دینامیک زیر میباشد.(معادلات دیفرانسیل زیر برقرار است.)
شبکه هاپفیلد با دینامیک بالا قادر است خود را از محل اولیه در تابع انرژي به نزدیکترین مینیمم محلی ببرد.
بنابراین چنانچه هدف ما کمینه کردن تابع هدف باشد، کافی است ساختار شبکه را چنان بدست آوریم که معادلات دیفرانسیل بالا برقرار باشد در این حالت نیز میتوان انتظار داشت که شبکه در جهت کمینه کردن تابع هدف مورد نظرمان حرکت کند. در این تحقیق براي بهینه کردن موقعیت برچسبها در نقشه از چنین روشی استفاده شده است.
٤- بررسی شبکه عصبی هاپفیلد جهت برچسبگذاري عوارض نقطه اي
براي هر نقطه بر روي نقشه، هشت موقعیت براي برچسب در نظر گرفته شده است. هدف یافتن بهترین مکان براي برچسب از بین این مکانهاست. باید توجه کرد که موقعیت هر نقطه بر روي نقشه و همچنین ابعاد بلاك برچسب را میدانیم.
ساختار شبکه هاپفیلد براي مساله مورد نظر به صورت ذیل میباشد؛ براي هر نقطه هشت حالت داریم، یعنی هشت موقعیت که بر حسب اینکه بر چسب در آن محل قرار گیرد میتوان به آن یک و در غیر اینصورت صفر نسبت داد. بنابراین در شبکه مورد نظرمان باید براي هر نقطه هشت نرون در نظر بگیریم که هر یک هم ارز با یک موقعیت برچسب در صفحه است. خروجی هر یک از این نرونها اگر یک باشد بیانگر آن است که برچسب باید در محل نظیر آن نرون قرار گیرد. پس بدیهی است که از میان این هشت نرون باید تنها یکی خروجیاش یک باشد.(شکل ٤)
