بخشی از مقاله
مقدمه ای بر شبکه های عصبی مصنوعی و کاربردهای آن
امروزه با شکسته شدن پی در پی استقلال ، شاخه های مختلف علوم و بهره وری شاخه ای از شاخه ی دیگر و پیشبرد مسائل پیچیده خود، پیوستگی و لاینفک بودن تمامی شاخه های علوم را نمایان تر می سازد که سرمنشأ تمامی آنها از یک حقیقت نشأت گرفته و آن ذات باری تعالی است.اولین تلاش ها به منظور ارائه ی یک مدل ریاضی برای سیستم عصبی انسان در دهه 40 توسط Mcculloch , pitts انجام شد ، که حاصل آن یک نورون ساده ی تک لایه ویک روش برای
آموزش آن بود . در ادامه ی این کار Hebb نتایج آزمایشات پاولف را در مورد شرطی شدن ،گسترش داد و یک روش برای یادگیری ارائه کرد . در سال 1958 ،Rossonblatt شبکه ی پرسپترون را ارائه کرد . بعد از مدتی اثبات شد شبکه ی عصبی پرسپترون تک لایه نمی تواند تابع ساده ای مانند EX-OR را بیاموزد .بنابراین تقریباً تا دهه ی 80 تلا ش ها برای گسترش شبکه ی عصبی بسیار کم بود.
سپس در طی یک مقاله اثبات شد که شبکه ی عصبی پرسپترون چند لایه می تواند به عنوان یک تخمین گر جهانی مطرح شود . بدین معنی که این شبکه قابلیت دارد هر تابع غیرخطی را با دقت دلخواه مدل سازی کند . از آن به بعد شبکه های عصبی مصنوعی گسترش یافتند و در زمینه های بسیاری از آنها استفاده شد .
سیستم شبکه ی عصبی مصنوعی از مغز وسیستم عصبی انسان الهام گرفته شده و مانند مغز انسان از تعداد زیادی نورون تشکیل شده است . این شبکه ها مانند مغز انسان دارای قابلیت یادگیری هستندکه از مزیت های عمده ی این سیستم هاست در مواردی که نتوانیم یک الگوریتم
حل به صورت فرمولی بیابیم یا تعداد زیادی مثال از ورودی و خروجی سیستم موردنظرمان در اختیار داشته باشیم و بخواهیم برای آن سیستم ، مدل ارائه کنیم یا اینکه یک ساختار از اطلاعات موجود بدست آوریم ، استفاده از شبکه های عصبی مصنوعی سودمند است . تاکنون برای شبکه های عصبی توپولوژی های مختلف همراه با کاربردهای متنوع ارائه شده است که طیف وسیعی از موضوعات را پوشش می دهد .
الهام از نورون واقعی :
سیستم عصبی انسان و مغز وی متشکل از ترکیب و به هم پیوستن تعداد زیادی سلول به نام نورون می باشد . تعداد نورون های مغز انسان به طور متوسط حدود 100 تریلیون می باشد . یک نورون دارای تعداد زیادی ورودی و یک خروجی است . خروجی می تواند دو حالت فعال یا غیرفعال را اختیار کند . در یک نورون ورودی ها تعیین می کنند که خروجی نرون فعال یا غیرفعال باشد . یک نرون از یک حجم سلولی ، تعداد زیادی « دنوریت » به عنوان ورودی و یک « اکسون » به عنوان خروجی تشکیل شده است.
به محل اتصال اکسون یک سلول به دنوریت های یک سلول دیگر نیز «سیناپس » می گویند که نقش بسزایی در سیستم عصبی ایفا می کند . سیناپس می تواند در طول دوره ی یادگیری نسبت به سیگنال های ورودی تغییر کند .در این قسمت به قانون یادگیری «هبی» اشاره می کنیم . این قانون به طور ساده به این صورت می باشد که اگر ورودی های یک نرون به طور مکرر منجر به فعال شدن خروجی شود ، یک تغییر متابولیک در سیناپس اتفاق می افتد که در طی آن مقاومت سیناپس نسبت به آن ورودی خاص کاهش می یابد.
مدل ریاضی نرون :
یک نرون مجموع وزن های ورودی را حساب کرده و براساس یک تابع فعالیت ( که در حالت ساده می تواند یک Threshold باشد ) خروجی را تعیین می کند . اگر این مجموع از ترشلد بیشتر باشد خروجی نرون « یک » می شود در غیر این صورت خروجی نرون منفی یک ( 1- ) خواهد شد .
به عنوان مثال یک شبکه عصبی ساده به نام perceptron را در نظر می گیریم این شبکه در شکل زیر نشان داده شده است در این شبکه چند ورودی وجود دارد که یکی از آنها مربوط به بایاس است . تابع فعالیت نورون نیز به صورت یک ترشلد خطی می باشد و شبکه دارای یک خروجی است . در این شبکه سیناپس ها به صورت وزن های اتصالات در نظر گرفته شده است . به عنوان مثال فرض کنید که می خواهیم یک OR منطقی را به وسیله ی این شبکه مدل کنیم. هدف از الگوریتم یادگیری ، بدست آوردن وزن های مناسب برای حل مسئله ی مورد نظر ما می باشد .
قانون یادگیری شبکه به صورت زیر است که بیان کننده ی تغییرات وزن ، نرخ سرعت یادگیری و یک عدد ثابت می باشد .D بیان کننده ی خروجی مطلوب است که در الگوهای آموزشی وجود دارد Y
بیان کننده ی خروجی به دست آمده از شبکه است و بیان کننده ورودی است .یادگیری همان طور که قبلاً اشاره شد ، از شبکه های عصبی مصنوعی برای مدل کردن سیستم هایی که غیرخطی یا جعبه سیاه هستند و ما از دینامیک داخلی سیستم خبری نداریم و فقط یک سری (ورودی – خروجی ) از سیستم داریم ، می توان استفاده کرد . بدین ترتیب که ابتدا یک توپولوژی مناسب از شبکه در نظر می گیریم، تعداد و نحوه ی اتصالات نورون ها را مشخص می کنیم و یک سری وزن
های ابتدایی برای اتصالات در نظر می گیریم . در مرحله ی آموزش، هدف این است که با اعمال مجموعه «ورودی – خروجی » های سیستم مورد نظر وزن های اتصالات را طوری تنظیم کنیم که بتوانیم با دادن ورودی هایی غیر از ورودی های مجموعه ی آموزشی مان خروجی متناسب با سیستم مورد نظر بدست بیاوریم . به بیان دیگر بتوانیم سیستم رامدل کنیم.
در شکل توپولوژی یک شبکه عصبی که دارای لایه های مختلفی است ، این شبکه ، ازلایه های مختلفی تشکیل شده که بیان کننده ی نحوه ی اتصال نورون ها به یکدیگر می باشد . لایه ی ورودی شامل نورون نبوده و فقط بیان کننده ی ورودی هاست . به نورون هایی که مستقیم ، به خروجی متصل می شوند، لایه ی خروجی گفته می شود .بقیه لایه ها - غیر از ورودی و خروجی - لایه های پنهان نام دارند . به طور کلی فرآیند یادگیری را می توان به 3 دسته تقسیم کرد.
1- یادگیری نظارت شده Supervised Learning در این روش همان طور که قبلاً اشاره شد یک مجموعه ی آموزشی در نظر گرفته می شود و یادگیرنده بر اساس یک ورودی عمل کرده و یک خروجی به دست می آورد . سپس این خروجی توسط یک معلم که می تواند خروجی مورد نظر ما باشد مورد ارزیابی قرار می گیرد و براساس اختلافی که با خروجی مطلوب دارد یک سری تغییرات در عملکرد یادگیرنده به وجود می آید . این تغییرات می تواند، وزن های اتصالات باشد . یک مثال برای این روش الگوریتم « پس انتشار خطا »Back propagation error می باشد که در شبکه های پرسپترون برای آموزش ، مورد استفاده قرار می گیرد.
2- یادگیری نظارت نشده unsupervised Learning در این روش، حین فرآیند یادگیری از مجموعه های آموزشی استفاده نمی شود و به اطلاعات در مورد خروجی مطلوب نیز نیاز ندارد . در این روش معلمی وجود ندارد . و معمولاً برای دسته بندی وفشرده سازی اطلاعات استفاده می شود . یک مثال برای این روش الگوریتم kohonen می باشد .
3- یادگیری تقویتی Rein forcement learning در این روش یک معلم به عنوان یاد دهنده وجود ندارد و خود یادگیرنده با سعی و خطا آموزش می بیند . در این روش یک استراتژی اولیه در نظر گرفته می شود . سپس این سیستم بر اساس همان رویه عمل می کند و یک پاسخ از محیطی که در آن فعالیت می کند، دریافت می کند. سپس بررسی می شود که آیا این پاسخ ، مناسب بوده یا خیر و با توجه به آن ، یادگیرنده یا مجازات می شود یا پاداش می گیرد . اگر مجازات شود عملی را که منجر به این مجازات شده در دفعات بعدی کمتر تکرار می شود و اگر پاداش بگیرد سعی می کند آن عملی که منجر به پاداش شده است ، بیشتر انجام دهد.
یک دیدگاه دیگر نسبت به یادگیری می تواند به تقسیم بندی زیر منجر شود :
1- یادگیری Off Line : در این روش وزن ها طی زمانی که سیستم در حال اجرای کار اصلی خودش می باشد ، ثابت هستند و تغییرات وزن ها درطول یادگیری صورت می پذیرد .
2- یادگیری On Line : در این روش وزن ها در دوره ی عملکرد واقعی سیستم نیز تغییر می کنند و دوره ی یادگیری و عملکرد سیستم از یکدیگر جدا نیستند . بدین ترتیب این سیستم دارای قابلیت بیشتری برای مقابله با تغییرات دینامیک محیط است . اما منجر به شبکه هایی با ساختار پیچیده تر می شود . چند نکته : ابتدا این که تعداد بهینه ی نورون های لایه های مخفی همچنین تعداد لایه های مخفی چقدر است؟ باید گفت به طور کلی برای این مسئله ، یک جواب تئوریک وجود ندارد بلکه به صورت تجربی و با توجه به کاربرد آن می توان به یک ساختار مناسب رسید . البته می توان از روش های بهینه سازی مانند « ژنتیک الگوریتم » برای حل این مسئله استفاده کرد . مسئله ی مهم دیگر بحث Overtraining می باشد که از اهمیت زیادی برخوردار است . این مورد بیان می کند که اگر تعداد داده های آموزش بسیار زیاد باشد شبکه بیشتر به عنوان حافظه عمل خواهد کرد و نمی تواند پاسخ مناسبی برای مدل سیستم ما باشد . از سوی دیگر اگر داده های آموزشی ما در تمام فضای مسئله پراکنده نباشد یا تعداد آنها کافی نباشد، شاید شبکه ی ما همگرا نشود .
کاربردها :
شبکه های عصبی در موارد زیر دارای کارایی زیادی می باشند :
1- پیداکردن الگوهای پیچیده از میان یک سری اطلاعات
2- درمسایلی که با اطلاعات غیر دقیق سروکار داریم.
3- در مسایلی که با اطلاعات نویزی سروکار داریم . مانند
1-prediction
2-Classification
3-Dataassociation
4-Dataconceptualizefion
5-filtering
6- planning
چند کاربرد عملی و مفید آن که تاکنون بر روی آنها فعالیت زیادی انجام شده عبارتند از :
1- پیشگویی prediction ) از اطلاعات بدست آمده در گذشته(
- پیش بینی وضعیت آب و هوا
- پیش بینی وضعیت سهام در بورس
- پیش بینی سری های زمانی
2- کلاسه بندی Classification
- پردازش تصویر
- دسته بندی اهداف در رادارها
3- تشخیص Recognition
- تشخیص نوع بمب درصنایع نظامی
- تشخیص حرو ف
- تشخیص امضاء
- تشخیص چهره
4- دیگر کاربردهای آن به صورت کلی شامل موارد زیر است :
Regularitydetection
- speechanalysis
- optimizationproblems
- Robotstearing
- Processing of inaccurate or in complteinputs
- Stock market forecasting simulation
به عنوان مثال کاربری می توان تخمین موقعیت کاربر مخابرات سیار در محیط شهری را بیان کرد . برای این کار می توان مکان کاربر را با تلفیق زاویه و زمان دریافت ، سیگنال را بهوسیله ی شبکه های پرسپترون چند لایه و RBF تخمین زد . بدین منظور دو روش مختلف در نظر گرفته شده است . در روش اول تنها از یک شبکه ی عصبی استفاده می شود . و در روش دوم که سلسله مراتبی
نامیده می شود عمل تخمین توسط بیش از یک شبکه ی عصبی صورت می پذیرد. به این ترتیب که نخست موقعیت کاربر به صورت تقریبی توسط شبکه ی لایه ی اول انجام می شود و سپس با استفاده از شبکه عصبی لایه ی دوم که برای ناحیه ی کوچکتری آموزش دیده است ، تخمین بهتری از موقعیت کاربر بدست می آید با افزایش تعداد لایه ها می توان به دقت بهتری دست یافت برای انتشار مسیر غیر خط دیده (NLOS ) امواج ، از دو روش استفاده شده است . در روش اول ( محیط غیر شهری ) دایره ای به مرکز فرستنده و شعاع مشخص به عنوان ناحیه ی پراکندگی در نظر
گرفته شده که امواج در این ناحیه پراکنده شده وبه گیرنده می رسند. در روش دوم ، از محیط های شهری که دارای ساختار مشخصی هستند ، استفاده شده است . برای شبیه سازی انتشار امواج در محیط های شهری ، نرم افزاری نوشته شده و پرتوهایی که از فرستنده ساطع می شوند را به صورت دو بعدی دنبال می کند . این عمل تا هنگامی که توان پرتو از یک مقدار آستانه کمتر
نشده و یا پرتو از محیط مورد نظر خارج نگردیده ادامه می یابد نتایج شبیه سازی نشان می دهد که در محیط غیر شهری با شعاع ناحیه ی پراکندگی 300 متر و نسبت سیگنال به نویز بی نهایت ، در صورت استفاده از یک ایستگاه پایه وپرسپترون با ساختار سلسله مراتبی در66 % موارد کاربر با
استفاده از پنج لایه ، احتمال خطای کمتر از 125 متر در تخمین موقعیت کاربر به 86% افزایش می یابد . در صورت استفاده از دو ایستگاه پایه ی این احتمال به 91% می رسد . نتایج حاصل از شبکه عصبی RBF نشان می دهد که دقت های مشابهی توسط این شبکه بدست می آید ضمن آنکه آموزش شبکه اخیر حدود پنجاه برابرسریع تر از شبکه پرسپترون است . این نتایج نشان می دهد دقت مورد نظر استاندارد E-911 باروش های پیشنهادی به دست می آید.{5}
تاریخچه :
شبکههای عصبی دهها سال است که جلب توجه می‌کنند وتاکنون راه حلهایی برای استفاده از هوش بشری ارائه شده است. اولین نرون مصنوعی درسال 1943 توسط نروفیزیولوژیست وارن‌مک‌کالوک و منطق دان والتر‌پیتز تولید شد.در دهه 60 به دلایلی که خارج از بحث این مقاله است مردم به‌سوی شبکههای عصبی متمایل شدند و تنها در دهه 80 دانشمندان توانایی‌های واقعی شبکههای عصبی را دیدند .
شبکه عصبی چیست؟
شبکه های عصبی مصنوعی (Artificial Neural Network) الگویی برای پردازش اطلاعات می باشند که با تقلید از شبکه های عصبی بیولوژیکی مثل مغز انسان ساخته شده اند.عنصر کلیدی این الگو ساختار جدید سیستم پردازش اطلاعات آن می باشد و از تعداد زیادی عناصر (نرون) با ارتباطات قوی داخلی که هماهنگ با هم برای حل مسائل مخصوص کار می کنند تشکیل شده اند. شبکه های عصبی مصنوعی با پردازش روی داده های تجربی، دانش یا قانون نهفته در ورای داده ها را به ساختار شبکه منتقل می کند که به این عمل یادگیری می گویند. اصولاً توانایی یادگیری
مهمترین ویژگی یک سیستم هوشمند است. سیستمی که بتواند یاد بگیرد منعطف تر است وساده تر برنامه ریزی میشود، بنابراین بهتر میتواند در مورد مسایل و معادلات جدید پاسخگو باشد. انسانها از زمانهای بسیار دور سعی بر آن داشتند که بیوفیزیولوژی مغز را دریابند چون همواره مسئله هوشمندی انسان و قابلیت یادگیری ،تعمیم،خلاقیت،انعطاف پذیری و پردازش موازی در مغز برای بشر جالب بوده و بکارگیری این قابلیتها در ماشینها بسیار مطلوب می نمود.روشهای
الگوریتمیک برای پیاده سازی این خصایص در ماشینها مناسب نمی باشند در نتیجه می بایست روشها مبتنی بر همان مدلهای بیولوژیکی باشد.ANN درست مثل انسانها با استفاده از مثالها آموزش می بیند ; همانطور که یک بچه با دیدن انواع مختلف از یک حیوان قادر به تشخیص آن می باشد.{6}
2- شبکههای عصبی مصنوعی:
2-1- شبکههای عصبی مصنوعی:
شبکههای عصبی شبیه به مغز انسان اطلاعاتی را پردازش می‌کنند. شبکه از تعداد زیادی سلولهای عصبی(Neuron ها) تشکیل شده با پردازشی بسیار بزرگ و به‌هم پیوسته که در حل موازی مسائل ویژه مشغول به کارند.یادگیری شبکههای عصبی از طریق مثالهاست. آنها برای انجام یک کار خاص برنامه‌ریزی نشده‌اند. مثالها باید با دقت بسیار بالایی انتخاب شوند والا زمان مفید هدر خواهد رفت و یا حتی ممکن است شبکه به طور ناقص دایر شود و در اینجا راهی برای فهمیدن اینکه سیستم معیوب است یا خیر وجود ندارد مگر اینکه خطایی رخ دهد.شبکههای عصبی
مصنوعی یک ترکیبی از مجموعه نرون‌هاست و البته نرونهای مصنوعی‌ای که بسیار شبیه به نرونهای زیستی کار می‌کنند. و بدین گونه است که ورودیهای زیادی با وزنهای مختلف می‌گیرد و یک خروجی که به ورودی وابسته است تولید می‌کند. نرونهای زیستی می‌توانند در حال برانگیزش باشند یا نباشند. (وقتی یک نرون برانگیخته میشود ضربه علائم خروجی آن مقداری کمتر از 100
هرتز است) شبکههای عصبی استفاده وسیعی در شناسایی الگوها دارند زیرا از خودشان قابلیت آن را دارند که بطور عمومی به ورودیهای غیر منتظره نیز پاسخ دهند. در طول ساخت نرونها می‌آموزند که چگونه الگوهای ویژه گوناگون را تشخیص دهند. اگر الگویی پذیرفته شود در حالی که در طول اجرا ورودی با خروجی مرتبط نباشد، نرون از مجموعهای از الگوهایی که سابقا آموخته خروجیی را که شبیه به الگو می‌باشد وکمترین تفاوت را با ورودی دارد انتخاب می‌کند. این روال عموما فراخوانی میشود.
مثال:
وقتی که ورودی نرون 1111 باشد چهار ورودی بر حسب برانگیزش مرتب شده‌اند و وقتی ورودیهای 0000 را داریم نرون برای برانگیزش مرتب نیست. قاعده عمومی این است که نرونها مایلند برانگیخته شوند وقتی که ورودی‌ها 0111 ، 1011 ، 1101 ، 1110 یا 1111 باشند و در صورتی که ورودی آنها 1000 ، 0001 ، 0010 ، 0100 یا 0000 باشند مایل به برانگیخته شدن نیستند.شناسایی الگوهای پیچیده سطح بالا میتواند به وسیله شبکه‌ای از نرونها انجام شود و
بدین ترتیب نام آن را شبکههای عصبی مصنوعی گذاشتند. اکنون شبکههای عصبی کاربردهای زیادی دارند(درمنطق وکلام و شناسایی عکسها)البته شناسایی الگوهامی‌تواند به‌طور موفقیت آمیز بر روی کامپیوترهای عمومی انجام شود. این شبکههای عمومی که برای شناسایی الگوها استفاده می‌شوندFeed-Forward نامیده می‌شدند زیرا آنها یک بازخورد (Feed-Back) داشتند. آنها به‌طور ساده ورودی‌ها را با خروجی‌ها می‌آمیختند. اما شناسایی الگوها به تدریج کاملتر شد
به‌طوریکه بر روی کامپیوترهای عمومی با سیستم خاص خودشان به‌سختی انجام می‌شد پس برای شناسایی الگوها شبکههای Feed-Forward کافی نبودند.در شبکههای عصبی خروجی هر نرون به ورودی نرونهای مجاورش متصل شده است. شبکههای عصبی نمی‌توانند معجزه کنند اما اگر به درستی استفاده شوند نتایج شگفت‌انگیزی خواهند داشت .
2-2- مشخصات مسائل در خور شبکههای عصبی مصنوعی Network) Artificial Neural
(ANN
تقلید از ساختارهای محاسباتی سیستم زیستی ممکن است ایده اصلی نمونه‌های محاسباتی برای ساخت کلاسهایی از مسائل باشد. از جمله این مسائل می‌توان از مسائل مشکل NP که شامل مسائل طبقه‌بندی شده، زمانبندی‌شده، جستجو وغیره نام برد، کلاس مسائل شناسایی الگوها، افراد و موضوعات مشخص را در دیدار و تماس با آنها می‌شناسد و کلاس مربوط به داده‌های ناقص، اشتباه، متناقض، فازی و احتمالی. این مسائل توسط همه یا برخی از موارد زیر توصیف می‌شوند :
یک فضای مسئله با بعد بزرگ، پیچیده، ناشناخته با اثرات متقابل پیچیده ریاضی‌وار بین متغییرها و یک فضای راه‌حل که ممکن است خالی باشد(شامل یک راه‌حل یکتا یا بیشتر ، شامل تعدادی از راه‌حلهای مفید)به نظر می‌رسد ANN ها راه‌حلهایی برای مسائلی که با ورودیهای حسی بیشتر درگیرند ارائه می‌دهد(صحبت‌کردن، دیدن، شناسایی دستخط و…).
2-3- کاربردهای شبکههای عصبی مصنوعی ANN :
می‌توان موارد زیر را از کاربردهای شبکههای عصبی مصنوعی ذکر کرد :
پردازش تصویر و دید : ( Image processing and computer vision )
پردازش علائم ( Signal processing ): شامل ریخت‌شناسی و تجزیه و تحلیل علائم مربوط به زمین‌لرزه‌ها و…
شناسایی الگوها( Pattern recognition ): شامل شناسایی چهره، اثر انگشت، تشخیص نوع صدا و نوع صحبت کردن، دستخط و …
پزشکی( Medicine ): شامل تجزیه و تحلیل و تشخیص علائم دستگاه ضربان‌نگار قلب
(الکتروکاردیوگرافیک)، تشخیص امراض گوناگون و …
سیستمهای نظامی( Military systems ): شامل ردیابی مین‌های زیردریایی، دسته‌بندی صداهای نابه‌هنجار و مخل در رادارها و شناسایی گوینده رزمی.
سیستمهای تجاری( Financial systems ): شامل تجزیه و تحلیل انبار مغازه‌ها، ارزیابی واقعی املاک و …
برنامه‌ریزی، کنترل و جستجو( Planning, control, and search ): شامل اجرای موازی مسائل و کنترل رباتها.
هوش مصنوعی( Artificial intelligence ): شامل برخی سیستمهای طبی و اجرای سیستمهای خبره.
سیستمهای قدرت( Power systems ): شامل برآورد وضعیت سیستم، ردیابی سریع و دسته‌بندی ردیابی، ردیابی خطا و ترمیم آن، پیشبینی و برآورد تخمین امنیت.
انواع یادگیری برای شبکه های عصبی:
1. یادگیری با ناظر:
در یادگیری با ناظر به قانون یاد گیری مجموعه ای از زوجهای داده ها به نام داده های یادگیری (Pi,Ti)i={1 … l } می دهند که در آن Pi ورودی به شبکه و Ti خروجی مطلوب شبکه برای ورودی Pi است. پس از اعمال ورودی Pi به شبکه عصبی در خروجی شبکه ai با Ti مقایسه شده و سپس خطای یادگیری محاسبه و از آن در جهت تنظیم پارامترهای شبکه استفاده می شود به گونه ای که اگر دفعه بعد به شبکه همان ورودی Pi اعمال شود خروجی شبکه به Ti نزدیکتر می گردد با توجه
به این نکته که معلم سیستمی است که بر محیط وقوف دارد ( مثلا می داند که برای ورودی Pi خروجی مطلوب Ti است ).توجه داریم که محیط برای شبکه عصبی مجهول است . در لحظه k بردار ورودی (Pik) با تابع توضیع احتمال معینی که برای شبکه عصبی نا معلوماست انتخاب و بطور همزمان به شبکه عصبی و معلم اعمال می شود . جواب مطلوب (Tik) نیز توسط معلم به شبکه عصبی داده می شود . در حقیقت پاسخ مطلوب پاسخ بهینه ای است که شبکه عصبی برای
ورودی مفروض باید به آن برسد . پارامترهای شبکه عصبی توسط دو سیگنال ورودی و خطا تنظیم می شود.به این صورت که پس از چند تکرار الگوریتم یادگیری که عموما توسط معادله تفاضلی بیان می شودبه پارامترهایی در فضای پارامترهای شبکه همگرا می شوند که برای آنها خطای یادگیری بسیار کوچک است و عملا شبکه عصبی شبکه عصبی معادل معلم می شود . یا به عبارتی دیگر اطلاعات مربوط به محیط (نگاشت بین TiوPi )که برای معلم روشن است به شبکه عصبی منتقل می شود و پس از این مرحله عملا می توان بجای معلم از شبکه عصبی استفاده کرد تا یادگیری تکمیل شود .
2. یادگیری تشدیدی:
یک اشکال یادگیری با ناظر این است که شبکه عصبی ممکن است بدون معلم نتواند مواضع جدیدی را که توسط مجموعه داده های جدید تجربی پوشانده نشده است یاد بگیرد . یادگیری از نوع تشدیدی این محدودیت را برطرف می کند . این نوع یادگیری بطور on-line صورت می گیرد در حالی که یادگیری با ناظر را به دو صورت on-line & off-line می توان انجام داد. در حالت off-line می توان از یک سیستم محاسب با در اختیار داشتن داده های یادگیری استفاده کرد و طراحی شبکه
عصبی را به پایان رساند . پس از مرحله طراحی و یادگیری شبکه عصبی به عنوان یک سیستم استاتیکی عمل می کند . اما در یادگیری on-line شبکه عصبی همراه با خود سیستم یادگیر در حال انجام کار است و از این رو مثل یک سیستم دینامیکی عمل می کند . یادگیری از نوع تشدیدی یک یادگیری on-line از یک نگاشت ورودی-خروجی است . این کار از طریق یک پروسه سعی و خطا به صورتی انجام می پذیرد که یک شاخص اجرایی موسوم به سیگنال تشدید ماکزیمم شود و بنابر این الگوریتم نوعی از یادگیری با ناظر است که در آن به جای فراهم نمودن جواب واقعی ، به شبکه
عددی که نشانگر میزان عملکرد شبکه است ارایه می شود. این بدین معنی است که اگر شبکه عصبی پارامترهایش را به گونه ای تغییر داد که منجر به یک حالت مساعد شد آنگاه تمایل سیستم یادگیر جهت تولید آن عمل خاص تقویت یا تشدید می شود . در غیر این صورت تمایل شبکه عصبی جهت تولید آن عمل خاص تضعیف می شود . یادگیری تقویتی مثل یادگیری با ناظر نیست و این الگوریتم بیشتر برای سیستمهای کنترلی کاربرد دارد .
3. یادگیری بدون ناظر:
در یادگیری بدون ناظر یا یادگیری خود سامانده پارامترهای شبکه عصبی تنها توسط پاسخ سیستم اصلاح و تنظیم می شوند . به عبارتی تنها اطلاعات دریافتی از محیط به شبکه را برداغرهای ورودی تشکیل می دهند. و در مقایسه با مورد بالا (یادگیری با ناظر) بردار جواب مطلوب به شبکه اعمال نمی شود . به عبارتی به شبکه عصبی هیچ نمونه ای از تابعی که قرار است بیاموزد داده نمی شود . در عمل می بینیم که یادگیری با ناظر در مورد شبکه هایی که از تعداد زیادی لایه های نرونی تشکیل شده باشند بسیار کند عمل می کند و در این گونه موارد تلفیق یادگیری با ناظر و بدون ناظر پیشنهاد می گردد .
2-4- زمینه‌ای درموردperceptron
Perceptron های ساده:
یک خانواده ساده از شبکههای عصبی مدل perceptron می‌باشد. در یک دسته‌بندی تک‌خروجی، تعداد n ورودی و یک خروجی دارد . با هر ورودی یک ضریب وزنی Wi و با هر خروجی یک مقدار آستانه q مرتبط است.
Perceptron به گونه زیر عمل می‌کند:
ورودیهای Perceptron یک بردار ورودی از n مقدار حقیقی است.
Perceptron مجموع وزنها را محاسبه می‌کند a= ه Wi.Xi. این مقدار با مقدار آستانه q مقایسه میشود. اگر این مقدار ازمقدار آستانه کوچکتر باشد خروجی 0 است و در غیر این صورت 1 است.
قدرت Perceptron:
به وسیله تنظیم اعداد ورودی، وزن آنها و مقدار آستانه می‌توان یک Perceptron برای انجام نسبتا خوب محاسبات گوناگون طراحی کرد. برای مثال توابع منطقی بولین مانند AND ، OR و NOT را می‌توان به وسیله Perceptron طراحی کرد و هر مدار منطقی دیگر را به وسیله گیتهای AND و NOT یا AND و OR طراحی کرد. دسته‌های زیادی از Perceptronها ممکن است خروجی‌های دسته‌های دیگر را به عنوان ورودی خود درخواست کنند.به عنوان مثالی ازPerceptron ها می‌توان یک تشخیص دهنده قالب متن را نام برد. حرفA درآرایه‌ای 5*5 به‌رمز درمی‌آید(encode میشود). این متن(حرف) بهوسیله یک Perceptron با 25 ورودی تشخیص داده میشود که در آن وزنها مقادیری برابر با مقادیر عددی داخل آرایه را می‌گیرند و مقدار آســتانه برابر است با: e-25 =q که در آن 0 < e < 1 .
خروجی Perceptron 1 است اگر و فقط اگر ورودی آن از 1 و 1- هایی باشد که عینا در آرایه آمده است.
دنباله‌های Perceptron:
یکی از خصوصیات جالب Perception این است که آنها می‌توانند به وسیله مثالهای مثبت و منفی ( صحیح و اشتباه) برای انجام توابع دسته‌بندی شده مخصوص بارها مرتب شوند.
حال به یک مثال ساده از Perceptron با دو ورودیX1 وX2 ، که تشخیص می‌دهد که کدام‌یک از دو کلاس، عناصر متعلق به خودش را دارد. ما فرض می‌کنیم که این Perceptron دو طرح از کارکترهای چاپ شده از یک متن را بررسی کند، خروجی 1 است اگر و فقط اگر کاراکتر رقم 8 باشد. فرض کنیم که X1 بیانگر تعداد حفره‌های کاراکتر است و X2 درجه راستی سمت چپ کاراکتر را نشان می‌دهد. ما با 4 ورودی .اگر ما perceptron را در اول کار با وزنهایی برابر 0 و مقدار آستانه را برابر 10 مقداردهی کنیم یک رده‌بندی از همه مثالهای منفی انجام داده‌ایم. با قرار دادن رده‌بندی‌های نادرست از 8 ، مقادیر ورودی از مثال 8 با بعضی فاکتورها مثل d جمع می‌شوند و تولیدات جدید با وزنهای متناظر با ایجاد می‌شوند.
فرض کنیم 1= d پس وزن ورودی‌ها از 0 به 1 و 2 رشد پیدا می‌کند. حال در اینجا 5 = a به دست می‌آید که هنوز از مقدار آستانه 10 کوچکتر است. مثال هنوز به رده‌بندی صحیحی نرسیده است واین قدم دنباله باید تکرار شود. بعد از دو قدم وزنها برابر 2 و 4 می‌شوند که مقدار 10 = a را نتیجه
می‌دهد که برابر مقدار آستانه است و مثال مثبت از 8 به طور صحیح دسته‌بندی شده است. از آنجا که ضرایب وزنی تغییر کرده بودند لازم است که در همه مثالها رده‌بندی‌ها بازنشان ( Reset ) شوند. این را می‌توان به سادگی دید که مثال B رده‌بندی نادرستی است زیرا با وزنهای 2 و 4 داریم 24 = a ولی این حرف مورد نظر ما نیست، چون این مرحله را پیش رفته‌ایم لازم است که d.1 از W1 و d.2 از W2 کم شود تا رده‌بندی نادرستی از B ثابت شود. به هر حال یک رده‌بندی از 8 را
دوباره بیرون می‌دهد.بعدها موقع بروز خطا ما وزنها را برای درست کردن خطاهای رده‌بندی اصلاح می‌کنیم. اگر مثالها دارای خاصیت صحیحی باشند وزنها در مجموعهای از مقادیری که به درستی روی هر ورودی کار می‌کنند قرار می‌گیرند.
قضیه بنیادی دنباله‌ها:
یک خصوصیت قابل توجه perceptron این است که آنها می‌توانند دنباله‌ای از رده بندی صحیح مثالهای مثبت ومنفی باشند.فرض کنیم: X = X+ ب X-
X+ : مجموعهای از مثالهای مثبت
X- : مجموعهای از مثالهای منفی
گوییم که رشته بی‌کران S x= X1 , X2 , …, Xk ,… یک رشته متوالی(ترتیبی) برای X است در صورتی که هر Xi یک
مثال در X است و هر عنصر از X اغلب به طور نامحدود در Sx رخ می‌دهد(نمایان میشود).
فرض کنیم Wk ضریب وزنی در سطح k دنباله باشد. وزن اولیه میتواند به صورت قراردادی باشد (برای مثال W1=0 ). حال
رشته استاندارد حاصله، وزنها را به صورت زیر ارتقا می‌دهد:
بسته به استرادژی مورد نظر ممکن است مقادیر C k همگی یکسان باشند یا ممکن است با k تغییر کنند.
قضیه 1):
باشد و یک بردار حل وزنها برای X وجود داشته باشد, در این صورت رویه رشته استاندارد باید بعد از یک تعداد فرض کنیم یک مجموعه از رشته نمونه X و هر رشته ترتیبی برای آن داریم, اگر Ck یک ثابت مثبت مراحل مشخص یک راه‌حل پیدا
کند به طوری که اگر برای بعضی k0 ها داشته باشیم:
WK0 = WK0+1 = WK0+2 = …
که WK0 یک راه‌حل برای X است. {7}
الگوریتم ژنتیک :
الگوریتم ژنتیک که بعنوان یکی از روشهای تصادفی بهینه یابی شناخته شده, توسط جان هالند در سال 1967 ابداع شده است. بعدها این روش با تلاشهای گلدبرگ 1989, مکان خویش را یافته و امروزه نیز بواسطه توانایی های خویش , جای مناسبی در میان دیگر روشها دارد. روال بهینه یابی در الگوریتم ژنتیک براساس یک روند تصادفی- هدایت شده استوار می باشد. این روش , بر مبنای نظریه تکامل تدریجی و ایده های بنیادین داروین پایه گذاری شده است.در این روش , ابتدا برای تعدادی ثابت که جمعیت نامیده می شود مجموعه ای از پارامترهای هدف بصورت اتفاقی تولید می شود , پس از اجرای برنامه شبیه ساز عددی را که معرف انحراف معیار و یا برازش آن مجموعه از اطلاعات است را به آن عضو از جمعیت مذکور نسبت می دهیم . این عمل را برای تک تک اعضای ایجاد شده تکرار می کنیم , سپس با فراخوانی عملگرهای الگوریتم ژنتیک از جمله لقاح , جهش و انتخاب نسل بعد را شکل می دهیم و این روال تا ارضای معیار همگرایی ادامه داده خواهد شد. هنگامي كه لغت تنازع بقا به كار مي‌رود اغلب بار ارزشي منفي آن به ذهن مي‌آيد. شايد همزم
ان قانون جنگل به ذهن برسد و حكم بقاي قويتر! البته براي آنكه خيالتان راحت شود مي‌توانيد فكر كنيد كه هميشه هم قوي‌ترين‌ها برنده نبوده‌اند. مثلا دايناسورها با وجود جثه عظيم و قويتر بودن در طي روندي كاملا طبيعي بازي بقا و ادامه نسل را واگذار كردند در حالي كه موجوداتي بسيار ضعيف‌تر از آنها حيات خويش را ادامه دادند. ظاهرا طبيعت بهترين‌ها را تنها بر اساس هيكل انتخاب
نمي‌كند! در واقع درست‌تر آنست كه بگوييم طبيعت مناسب ترين‌ها (Fittest) را انتخاب مي‌كند نه بهترين‌ها. قانون انتخاب طبيعي بدين صورت است كه تنها گونه‌هايي از يك جمعيت ادامه نسل مي‌دهند كه بهترين خصوصيات را داشته باشند و آنهايي كه اين خصوصيات را نداشته باشند به تدريج و در طي زمان از بين مي‌روند.
مثلا فرض كنيد گونه خاصي از افراد، هوش بسيار بيشتري از بقيه افراد يك جامعه يا كولوني دارند. در شرايط كاملا طبيعي اين افراد پيشرفت بهتري خواهند كرد و رفاه نسبتا بالاتري خواهند داشت و اين رفاه خود باعث طول عمر بيشتر و باروري بهتر خواهد بود(توجه كنيد شرايط طبيعيست نه در يك جامعه سطح بالا با ملاحظات امروزي يعني طول عمر بيشتر در اين جامعه نمونه با زاد و ولد بيشت
ر همراه است). حال اگر اين خصوصيت(هوش)ارثي باشد به طبع در نسل بعدي همان جامعه تعداد افراد باهوش به دليل زاد و ولد بيشتر اين‌گونه افراد بيشتر خواهد بود. اگر همين روند را ادامه دهيد خواهيد ديد كه در طي نسلهاي متوالي دائما جامعه نمونه ما باهوش و باهوش‌تر مي‌شود. بدين ترتيب يك مكانيزم ساده طبيعي توانسته است در طي چند نسل عملا افراد كم هوش را از جامعه
حذف كند علاوه بر اينكه ميزان هوش متوسط جامعه نيز دائما در حال افزايش است(البته امكان داشت اگر داروين بي‌عرضگي افراد باهوش امروزي را مي‌ديد كمي در تئوري خود تجديد نظر مي‌كرد اما اين مسئله ديگريست بدين ترتيب مي‌توان ديد كه طبيعت با بهره‌گيري از يك روش بسيار ساده(حذف تدريجي گونه‌هاي نامناسب و در عين حال تكثير بالاتر گونه‌هاي بهينه) توانسته است دائما هر نسل را از لحاظ خصوصيات مختلف ارتقا بخشد. البته آنچه در بالا ذكر شد به تنهايي توصيف كننده آنچه واقعا در قالب تكامل در طبيعت اتفاق مي‌افتد نيست. بهينه‌سازي و تكامل تدريجي به خودي خود نمي‌تواند طبيعت را در دسترسي به بهترين نمونه‌ها ياري دهد. اجازه دهيد تا اين مساله را با يك مثال شرح دهيم. پس از اختراع اتومبيل به تدريج و در طي سال‌ها اتومبيل‌هاي بهتري با سرعت‌هاي بالاتر و قابليت‌هاي بيشتر نسبت به نمونه‌هاي اوليه توليد شدند. طبيعيست كه اين نمونه‌هاي متاخر حاصل تلاش مهندسان طراح جهت بهينه‌سازي طراحي‌هاي قبلي بوده اند. اما دقت كنيد كه بهينه‌سازي يك اتومبيل تنها يك "اتومبيل بهتر" را نتيجه مي‌دهد. اما آيا مي‌توان گفت اختراع هواپيما نتيجه همين تلاش بوده است؟ يا فرضا مي‌توان گفت فضا پيماها حاصل بهينه‌سازي طرح اوليه هواپيماها بوده‌اند؟پاسخ اينست كه گرچه اختراع هواپيما قطعا تحت تاثير دستاورهاي صنعت اتومبيل بوده است اما به‌هيچ وجه نمي‌توان گفت كه هواپيما صرفا حاصل بهينه‌سازي اتومبيل و يا فضا پيما حاصل بهينه‌سازي هواپيماست. در طبيعت هم عينا همين روند حكم‌فرماست. گونه‌هاي متكامل‌تري وجود دارند كه نمي‌توان گفت صرفا حاصل تكامل تدريجي گونه قبلي هستند. در اين ميان آنچه شايد بتواند تا حدودي ما را در فهم اين مساله ياري كند
مفهوميست به نام : تصادف يا جهش به عبارتي طرح هواپيما نسبت به طرح اتومبيل يك جهش بود و نه يك حركت تدريجي. در طبيعت نيز به همين گونه‌است. در هر نسل جديد بعضي از خصوصيات به صورتي كاملا تصادفي تغيير مي‌يابند سپس بر اثر تكامل تدريجي كه پيشتر توضيح داديم در صورتي كه اين خصوصيت تصادفي شرايط طبيعت را ارضا كند حفظ مي‌شود در غير اين‌صورت به
شكل اتوماتيك از چرخه طبيعت حذف مي‌گردد. در واقع مي‌توان تكامل طبيعي را به اين‌صورت خلاصه كرد: جست‌وجوي كوركورانه)تصادف يا( Blind Search بقاي قويتر.
حال ببينيم كه رابطه تكامل طبيعي با روشهاي هوش مصنوعي چيست .هدف اصلي روشهاي هوشمند به كار گرفته شده در هوش مصنوعي يافتن پاسخ بهينه مسائل مهندسي ست. بعنوان مثال اينكه چگونه يك موتور را طراحي كنيم تا بهترين بازدهي را داشته باشد يا چگونه بازوهاي يك ربات را محرك كنيم تا كوتاه‌ترين مسير را تا مقصد طي كند(دقت كنيد كه در صورت وجود مانع يافتن كوتاه‌ترين مسير ديگر به سادگي كشيدن يك خط راست بين مبدا و مقصد نيست) همگي مسائل بهينه‌سازي هستند.
روشهاي كلاسيك رياضيات داراي دو اشكال اساسي هستند. اغلب اين روشها نقطه بهينه محليLocal) (Optima را بعنوان نقطه بهينه كلي در نظر مي‌گيرند و نيز هر يك از اين روشها تنها براي مساله خاصي كاربرد دارند. اين دو نكته را با مثال‌هاي ساده‌اي روشن مي‌كنيم.
به شكل زير توجه كنيد. اين منحني داراي دو نقطه ماكزيمم مي‌باشد. كه يكي از آنها تنها ماكزيمم محلي است. حال اگر از روشهاي بهينه‌سازي رياضي استفاده كنيم مجبوريم تا در يك بازه بسيار كوچك مقدار ماكزيمم تابع را بيابيم. مثلا از نقطه 1 شروع كنيم و تابع را ماكزيمم كنيم. بديهي است اگر از نقطه 1 شروع كنيم تنها به مقدار ماكزيمم محلي دست خواهيم يافت و الگوريتم ما پس از آن متوقف خواهد شد. اما در روشهاي هوشمند خاصه الگوريتم ژنتيك بدليل خصلت تصادفي آنها حتي اگر هم از نقطه 1 شروع كنيم باز ممكن است در ميان راه نقطه A به صورت تصادفي انتخاب شود كه در اين صورت ما شانس دست‌يابي به نقطه بهينه كلي (Global Optima) را خواهيم داشت.
در مورد نكته دوم بايد بگوييم كه روشهاي رياضي بهينه‌سازي اغلب منجر به يك فرمول يا دستورالعمل خاص براي حل هر مسئله ميشوند. در حالي كه روشهاي هوشمند دستورالعمل‌هايي هستند كه به صورت كلي مي‌توانند در حل هر مسئله‌اي به كار گرفته شوند. اين نكته را پس از آشنايي با خود الگوريتم بيشتر و بهتر خواهيد ديد.
الگوريتم ژنتيک چيست؟
الگوريتم هاي ژنتيک از اصول انتخاب طبيعي داروين براي يافتن فرمول بهينه جهت پيش بيني يا تطبيق الگو استفاده مي کنند.الگوريتم هاي ژنتيک اغلب گزينه خوبي براي تکنيک هاي پيش بيني بر
مبناي رگرسيون هستند.همان طور ساده،خطي وپارامتريک گفته مي شود،به الگوريتم هاي ژنتيک مي توان غير پارامتريک گفت.براي مثال اگر بخواهيم نوسانات قيمت نفت را با استفاده از عوامل خارجي وارزش رگرسيون خطي ساده مدل کنيم،اين فرمول را توليد خواهيم کرد:قيمت نفت در زمان t=ضريب 1 نرخ بهره در زمان t+ضريب 2 نرخ بيکاري در زمان t+ثابت 1 . سپس از يک معيار براي پيدا کردن بهترين مجموعه ضرايب و ثابت ها جهت مدل کردن قيمت نفت استفاده خواهيم کرد.در اين روش 2 نکته اساسي وجود دارد.اول اين روش خطي است و مسئله دوم اين است که ما به جاي اينکه در ميان "فضاي پارامترها"جستجو کنيم ،پارامترهاي مورد استفاده را مشخص کرده ايم.با استفاده از الگوريتم هاي ژنتيک ما يک ابر فرمول يا طرح تنظيم مي کنيم که چيزي شبيه"قيمت نفت در زمان t تابعي از حداکثر 4 متغير است"را بيان مي کند. سپس داده هايي براي گروهي از متغيرهاي مختلف،شايد در حدود 20 متغير فراهم خواهيم کرد.سپس الگوريتم ژنتيک اجرا خواهد شد که بهترين تابع و متغيرها را مورد جستجو قرار مي دهد.روش کار الگوريتم ژنتيک به طور فريبنده اي ساده،خيلي قابل درک وبه طور قابل ملاحظه اي روشي است که ما معتقديم حيوانات آنگونه تکامل يافته اند.هر فرمولي که از طرح داده شده بالا تبعيت کند فردي از جمعيت فرمول هاي ممکن تلقي مي شود خيلي شبيه به اين که بگوييم جرج بوش فردي از جمعيت انسان هاي ممکن است. متغير هايي که هر فرمول داده شده را مشخص مي کنند به عنوان يکسري از اعداد نشان داده شده اند که معادل دي ان اي آن فرد را تشکيل مي دهند.
موتور الگوريتم ژنتيک يک جمعيت آغاز از فرمول ايجاد مي کند.هر فرد در برابر مجموعه اي از داده ها ي مورد آزمايش قرار مي گيرند و مناسبترين آنها شايد 10 درصد از مناسبترين ها باقي مي مانند.بقيه کنار گذاشته مي شوند. مناسبترين افراد با هم جفتگيري (جابجايي عناصر دي ان
اي)وتغيير(تغيير تصادفي عناصر دي ان اي) کرده اند.مشاهده مي شود که با گذشت از ميان تعدد ريادي از نسلها،الگوريتم ژنتيک به سمت ايجاد فرمول هايي که بيشتر دقيق هستند،ميل مي کنند.در حالي که شبکه هاي عصبي هم غير خطي و غير پارامتريک هستند،جذابيت زياد الگوريتم هاي ژنتيک اين است نتايج نهايي قابل ملاحظه ترند.فرمول نهايي براي کاربر انساني قابل مشاهده خواهد بود،و براي ارائه سطح اطمينان نتايج مي توان تکنيک هاي آماري متعارف رابر روي اين فرمول ها اعمال کرد.فناوري الگوريتم هاي ژنتيک همواره در حال بهبود استفبراي مثال با مطرح کردن
معادله ويروس ها که در کنار فرمول ها وبراي نقض کردن فرمول ها ي ضعيف توليد مي شوندودر نتيجه جمعيت را کلاً قويتر مي سازند.مختصراً گفته مي شود که الگوريتم ژنتيک يا GA يک تکنيک برنامه نويسي است که از تکامل ژنتيکي به عنوان يک الگوي حل مسئله استفاده مي کند.مسئله اي که بايد حل شود ورودي است و راه حلها طبق يک الگو کد گذاري مي شودومتريک که تابع fitness هم نام دارد هر راه حل کانديد را ارزيابي مي کندکه اکثر آنها به صورت تصادفي انتخاب مي شوندالگوريتم ژنتيک GA يک تکنيک جستجو در علم کامپيوتربراي يافتن راه حل بهينه ومسائل جستجو است.الگوريتم هاي ژنتيک يکي از انواع الگوريتم هاي تکاملي اند که از علم زيست شناسي مثل وراثت، جهش،انتخاب ناگهاني ، انتخاب طبيعي و ترکيب الهام گرفته شده .عموماً راه حلها به صورت 2 تايي 0و1 نشان داده مي شوند ولي روشهاي نمايش ديگري هم وجود دارد.تکامل از يک مجموعه کاملاً تصادفي از موجوديت ها شروع مي شود و در نسلهاي بعدي تکرار مي شود.در هر نسل،مناسبترين ها انتخاب مي شوند نه بهترين ها.يک راه حل براي مسئله مورد نظر،با يک ليست از پارامترها نشان داده مي شود که به آنها کروموزوم يا ژنوم مي گويند.کروموزوم ها عموماً به
صورت يک رشته ساده از داده ها نمايش داده مي شوند،البته انواع ساختمان داده هاي ديگر هم مي توانند مورد استفاده قرار گيرند.در ابتدا چندين مشخصه به صورت تصادفي براي ايجاد نسل اول توليد مي شوند. در طول هر نسل ،هر مشخصه ارزيابي مي شود وارزش تناسب(fitness) توسط تابع تناسب اندازه گيري مي شود.گام بعدي ايجاد دومين نسل از جامعه است که بر پايه فرآيندهاي انتخاب ،توليد از روي مشخصه هاي انتخاب شده با عملگرهاي ژنتيکي است:اتصال کروموزوم ها به سر يکديگر و تغيير.
براي هر فرد ،يک جفت والد انتخاب مي شود.انتخابها به گونه اي اند که مناسبترين عناصر انتخاب شوند تا حتي ضعيفترين عناصر هم شانس انتخاب داشته باشند تا از نزديک شدن به جواب محلي جلوگيري شود.چندين الگوي انتخاب وجود دارد: چرخ منگنه دار(رولت)،انتخاب مسابقه اي (Tournament) ،... .
معمولاً الگوريتم هاي ژنتيک يک عدد احتمال اتصال دارد که بين 0.6و1 است که احتمال به وجود آمدن فرزند را نشان مي دهد.ارگانيسم ها با اين احتمال با هم دوباره با هم ترکيب مي شوند.اتصال 2 کروموزوم فرزند ايجاد مي کند،که به نسل بعدي اضافه مي شوند.اين کارها انجام مي شوند تا اين که کانديدهاي مناسبي براي جواب،در نسل بعدي پيدا شوند. مرحله بعدي تغيير دادن فرزندان جديد است.الگوريتم هاي ژنتيک يک احتمال تغيير کوچک وثابت دارند که معمولاً درجه اي در حدود 0.01 يا کمتر دارد. بر اساس اين احتمال ،کروموزوم هاي فرزند به طور تصادفي تغيير مي کنند يا جهش مي يابند.مخصوصاً با جهش بيتها در کروموزوم ساختمان داده مان.
اين فرآيند باعث به وجود آمدن نسل جديدي از کروموزوم ها يي مي شود، که با نسل قبلي متفاوت است.کل فرآيند براي نسل بعدي هم تکرار مي شود،جفتها براي ترکيب انتخاب مي شوند،جمعيت نسل سوم به وجود مي آيند و... .
اين فرآيند تکرار مي شود تا اين که به آخرين مرحله برسيم.
شرايط خاتمه الگوريتم هاي ژنتيک عبارتند از:
• به تعداد ثابتي از نسل ها برسيم .
• بودجه اختصاص داده شده تمام شود(زمان محاسبه/ پول)
• يک فرد(فرزند توليد شده) پيدا شود که مينيمم (کمترين)ملاک را برآورده کند.
• بيشترين درجه برازش فرزندان حاصل شود يا ديگر نتايج بهتري حاصل نشود.
• بازرسي دستي.
• ترکيبهاي بالا.
ايده اصلي :
در دهه هفتاد ميلادي دانشمندي از دانشگاه ميشيگان به نام جان هلند ايده استفاده از الگوريتم ژنتيك را در بهينه‌سازي‌هاي مهندسي مطرح كرد. ايده اساسي اين الگوريتم انتقال خصوصيات موروثي توسط ژن‌هاست. فرض كنيد مجموعه خصوصيات انسان توسط كروموزوم‌هاي او به نسل بعدي منتقل ميشوند. هر ژن در اين كروموزوم‌ها نماينده يك خصوصيت است. بعنوان مثال ژن 1 مي‌تواند رنگ چشم باشد ، ژن 2 طول قد، ژن 3 رنگ مو و الي آخر. حال اگر اين كروموزوم به تمامي، به نسل بعد انتقال يابد، تمامي خصوصيات نسل بعدي شبيه به خصوصيات نسل قبل خواهد بود. بديهيست كه در عمل چنين اتفاقي رخ نمي‌دهد. در واقع بصورت همزمان دو اتفاق براي كروموزوم‌ها مي‌افتد. اتفاق اول موتاسيون (Mutation) است. موتاسيون به اين صورت است كه بعضي ژن‌ها بصورت كاملا تصادفي تغيير مي‌كنند. البته تعداد اين گونه ژن‌ها بسيار كم مي‌باشد اما در هر حال اين تغيير تصادفي همانگونه كه پيشتر ديديم بسيار مهم است. مثلا ژن رنگ چشم مي‌تواند بصورت تصادفي باعث شود تا در نسل بعدي يك نفر داراي چشمان سبز باشد. در حالي كه تمامي نسل قبل داراي چشم قهوه‌اي بوده‌اند. علاوه بر موتاسيون اتفاق ديگري كه مي‌افتد و البته اين اتفاق به تعداد بسيار بيشتري نسبت به موتاسيون رخ مي‌دهد چسبيدن ابتداي يك كروموزوم به انتهاي يك كروموزوم ديگر است. اين مساله با نام Crossover شناخته مي‌شود. اين همان چيزيست كه مثلا باعث مي‌شود تا فرزند تعدادي از خصوصيات پدر و تعدادي از خصوصي
ات مادر را با هم به ارث ببرد و از شبيه شدن تام فرزند به تنها يكي از والدين جلوگيري مي‌كند.
در ابتدا تعداد مشخصي از ورودي ها،X1, X2,…, Xn که متعلق به فضاي نمونه X هستند را انتخاب مي کنيم و آنها را در يک عدد برداي X=(x1,x2,…xn) نمايش مي دهيم..در مهندسي نرم افزار اصطلاحاً به آنها ارگانيسم يا کروموزوم گفته مي شود.به گروه کروموزوم ها Colony يا جمعيت مي گوييم.در هر دوره Colony رشد مي کند و بر اساس قوانين مشخصي که حاکي از تکامل زيستي است تکامل مي يابند.
براي هر کروموزوم Xi ،ما يک ارزش تناسب(Fitness) داريم که آن را f(Xi) هم مي ناميم.عناصر قوي
تر يا کروموزوم هايي که ارزش تناسب آنها به بهينه Colony نزديکتر است شانس بيشتري براي زنده ماندن در طول دوره هاي ديگر و دوباره توليد شدن را دارند و ضعيفترها محکوم به نابودي اند. به عبارت ديگر الگوريتم ورودي هايي که به جواب بهينه نزديکترندرانگه داشته واز بقيه صرف نظر مي کند.
يک گام مهم ديگر درالگوريتم،تولد است که در هر دوره يکبار اتفاق مي افتد. محتويات دو کروموزومي که در فرآيند توليد شرکت مي کنند با هم ترکيب ميشوند تا 2 کروموزوم جديد که ما انها را فرزند مي ناميم ايجاد کنند.اين هيوريستيک به ما اجازه مي دهد تا 2 تا از بهترين ها را براي ايجاد يکي بهتر از آنها با هم ترکيب کنيم.(evolution) به علاوه در طول هر دوره،يک سري از کروموزوم ها ممکن است جهش يابند (Mutation)
الگوريتم :
هر ورودي x در يک عدد برداري X=(x1,x2,..,xn) قرار دارد .براي اجراي الگوريتم ژنتيک مان بايد هر ورودي را به يک کروموزوم تبديل کنيم.مي توانيم اين را با داشتن log(n) بيت براي هر عنصرو تبديل ارزش Xi انجام دهيم مثل شکل زير .
e(X1)
e(X1)
e(X1)
0111111 ... 1010111 1111011
(X1, X2,…,Xn)= (123, 87,…, 63)
مي توانيم از هر روش کد کردن براي اعداد استفاده کنيم.در دوره 0، يک دسته از ورودي هاي X را به صورت تصادفي انتخالب مي کنيم.بعد براي هر دوره iام ما ارزش مقدار Fitness را توليد،تغيير وانتخاب را اعمال مي کنيم.الگوريتم وقتي پايان مي يابد که به معيارمان برسيم.
سود و کد :
Choose initial population
Repeat
Evaluate the individual fit nesses of a certain proportion of the population
Select pairs of best-ranking individuals to reproduce
Apply crossover operator
Apply mutation operator
Until terminating condition
روش هاي نمايش :
قبل از اين که يک الگوريتم ژنتيک براي يک مسئله اجرا شود،يک روش براي کد کردن ژنوم ها به زبان کامپيوتر بايد به کار رود. يکي از روش هاي معمول کد کردن به صورت رشته هاي باينري است:رشته هاي 0و1. يک راه حل مشابه ديگر کدکردن راه حل ها در آرايه اي از اعداد صحيح يا اعشاري است ،که دوباره هر جايگاه يک جنبه از ويژگي ها را نشان مي دهد.اين راه حل در مقايسه با قبلي
پيچيده تر و مشکل تر است. مثلاً اين روش توسط استفان کرمر،براي حدس ساختار 3 بعدي يک پروتئين موجود در آمينو اسيد ها استفاده شد.الگوريتم هاي ژنتيکي که براي آموزش شبکه هاي عصبي استفاده مي شوند،از اين روش بهره مي گيرند.سومين روش براي نمايش صفات در يک GA يک رشته از حروف است،که هر حرف دوباره نمايش دهنده يک خصوصيت از راه حل است.خاصيت هر 3تاي اين روشها اين است که آنها تعريف سازنده ايي را که تغييرات تصادفي در آنها ايجاد مي
کنند را آسان مي کنند:0را به 1 وبرعکس،اضافه يا کم کردن ارزش يک عدد يا تبديل يک حرف به حرف ديگر.يک روش ديگر که توسط John Koza توسعه يافت،برنامه نويسي ژنتيک (Genetic programming)است.که برنامه ها را به عنوان شاخه هاي داده در ساختار درخت نشان مي دهد.در اين روش تغييرات تصادفي مي توانند با عوض کردن عملگرها يا تغيير دادن ارزش يک گره داده شده در درخت،يا عوض کردن يک زير درخت با ديگري به وجود آيند.
روش هاي انتخاب :
روش هاي مختلفي براي الگوريتم هاي ژنتيک وجود دارند که مي توان براي انتخاب ژنوم ها از آنها استفاده کرد.اما روش هاي ليست شده در پايين از معمولترين روش ها هستند.
انتخاب Elitist :مناسبترين عضو هر اجتماع انتخاب مي شود.
انتخاب Roulette: يک روش انتخاب است که در آن عنصري که عدد برازش(تناسب)بيشتري داشته باشد،انتخاب مي شود.
انتخاب Scaling :به موازات افزايش متوسط عدد برازش جامعه،سنگيني انتخاب هم بيشتر مي شودوجزئي تر.اين روش وقتي کاربرد دارد که مجموعه داراي عناصري باشد که عدد برازش بزرگي دارند وفقط تفاوت هاي کوچکي آنها را از هم تفکيک مي کند.
انتخاب Tournament : يک زير مجموعه از صفات يک جامعه انتخاب مي شوندواعضاي آن مجموعه با هم رقابت مي کنندو سرانجام فقط يک صفت از هر زير گروه براي توليد انتخاب مي شوند.
بعضي از روشهاي ديگر عبارتند از :
:Rank Selection, Generational Selection, Steady-State Selection .Hierarchical Selection
روش هاي تغيير:
وقتي با روش هاي انتخاب کروموزوم ها انتخاب شدند،بايد به طور تصادفي براي افزايش تناسبشان اصلاح شوند.2 راه حل اساسي براي اين کار وجود دارد.اولين وساده ترين جهش (Mutation) ناميده مي شود.درست مثل جهش در موجودات زنده که عبارت است از تغيير يک ژن به ديگري، در الگوريتم ژنتيک جهش تغيير کوچکي در يک نقطه از کد خصوصيات ايجاد مي کند.
دومين روش Crossover نام دارد و 2 کروموزوم براي معاوضه سگمنتهاي کدشان انتخاب مي شوند.اين فرآيند بر اساس فرآيند ترکيب کروموزوم ها در طول توليد مثل در موجودات زنده شبيه سازي شده. اغلب روش هاي معمول Crossover شامل Single-point Crossoverهستند ، که نقطه تعويض در جايي تصادفي بين ژنوم ها است.بخش اول قبل از نقطه ،و بخش دوم سگمنت بعد از آن ادامه پيدا مي کند،که هر قسمت برگرفته از يک والد است،که 50/50 انتخاب شده.
شکل هاي بالا تاثير هر يک از عملگر هاي ژنتيک را روي کروموزوم هاي 8 بيتي نشان مي دهد. شکل بالاتر 2 ژنوم را نشان مي دهد که نقطه تعويض بين 5امين و 6امين مکان در ژنوم قرار گرفته،ايجاد يک ژنوم جديد از پيوند اين 2 والد بدست مي آيند.شکل 2وم ژنومي را نشان مي دهد که دچار جهش شده و 0 در آن مکان به 1 تبديل شده .
تقاط قوت الگوريتم هاي ژنتيک:
اولين و مهمترين نقطه قوت اين الگوريتم ها اين است که الگوريتم هاي ژنتيک ذاتاً موازي اند .اکثر الگوريتم هاي ديگر موازي نيستند و فقط مي توانند فضاي مسئله مورد نظر را در يک جهت در يک لحظه جستجو کنند واگر راه حل پيدا شده يک جواب بهينه محلي باشدويا زير مجموعه اي از جواب اصلي باشد بايد تمام کارهايي که تا به حال انجام شده را کنار گذاشت ودوباره از اول شروع کرد.از آنجايي که GA چندين نقطه شروع دارد،در يک لحظه مي تواند فضاي مسئله را از چندجهت مختلف جستجو کند. اگر يکي به نتيجه نرسيد ساير راه ها ادامه مي يابند و منابع بيشتري را در اختيار شان قرار مي گيرد.در نظر بگيريد: همه 8 عدد رشته باينري يک فضاي جستجو را تشکيل مي دهند،که مي تواند به صورت ******** نشان داده شود.رشته 01101010 يکي از اعضاي اين فضاست.همچنين عضوي از فضاهاي
*******0و******01و0 ******0و*1*1*1*0و 0**01*01 والي آخر باشد.
به دليل موازي بودن واين که چندين رشته در يک لحظه مورد ارزيابي قرار مي گيرند GA ها براي مسائلي که فضاي راه حل بزرگي دارند بسيار مفيد است .اکثر مسائلي که اين گونه اند به عنوان"غير خطي" شناخته شده اند.در يک مسئله خطي، Fitness هر عنصر مستقل است،پس هر تغييري در يک قسمت بر تغيير وپيشرفت کل سيستم تاثير مستقيم دارد.مي دانيم که تعداد کمي از مسائل دنياي واقعي به صورت خطي اند.در مسائل غير خطي تغيير در يک قسمت ممکن است تاثيري ناهماهنگ بر کل سيستم ويا تغيير در چند عنصر تاثير فراواني بر سيستم بگذارد. خوشبختانه موازي بودن GA باعث حل اين مسئله مي شود ودر مدت کمي مشکل حل مي شود.مثلاً براي حل يک مسئله خطي 1000 رقمي 2000 امکان حل وجود دارد ولي براي يک غير خطي 1000 رقمي 21000 امکان .يکي از نقاط قوت الگوريتم هاي ژنتيک که در ابتدا يک کمبود به نظر مي رسد اين
است که :GA ها هيچ چيزي در مورد مسائلي که حل مي کنند نمي دانندو اصطلاحاً به آنها Blind Watchmakers مي گوييم . آنها تغييرات تصادفي را در راه حل هاي کانديدشان مي دهند وسپس از تابع برازش براي سنجش اين که آيا آن تغييرات پيشرفتي ايجاد کرده اند يا نه، استفاده مي کنند.مزيت اين تکنيک اين است که به GA اجازه مي دهند يا با ذهني باز شروع به حل کنند.از آنجايي که تصميمات آن اساساً تصادفي است،بر اساس تئوري همه راه حلهاي ممکن به روي مسئله باز است،ولي مسائلي که محدود به اطلاعات هستند بايد از راه قياس تصميم بگيرند ودر اين صورت بسياري از راه حلهاي نو وجديد را از دست مي دهند. يکي ديگر از مزاياي الگوريتم ژنتيک اين است که آنها مي توانند چندين پارامتر را همزمان تغييردهند.بسياري ازمسائل واقعي نمي توانند محدود به يک ويژگي شوند تا آن ويژگي ماکسيمم شود يا مينيمم و بايد چند جانبه در نظر گرفته شوندGAها در حل اين گونه مسائل بسيار مفيدند،و در حقيقت قابليت موازي کار کردن آنها اين خاصيت را به آنها مي بخشد.و ممکن است براي يک مسئله 2 يا چند راه حل پيدا شود،که هر کدام با در نظر گرفتن يک پارامتر خاص به جواب رسيده اند.
محدوديتهاي GAها :
يک مشکل چگونگي نوشتن عملگر Fitness است که منجر به بهترين راه حل براي مسئله شود.اگر اين کارکرد برازش به خوبي و قوي انتخاب نشود ممکن است باعث شود که راه حلي براي مسئله پيدا نکنيم يا مسئله اي ديگر را به اشتباه حل کنيم. به علاوه براي انتخاب تابع مناسب براي Fitness ،پارامترهاي ديگري مثل اندازه جمعيت،نرخ جهش وCrossover ، قدرت ونوع انتخاب هم بايد مورد توجه قرار گيرند.
مشکل ديگر،که آن را نارس مي ناميم اين است که اگر يک ژنوم که فاصله اش با ساير ژنوم هاي نسل اش زياد باشد(خيلي بهتر از بقيه باشد)و خيلي زود ديده شود(ايجاد شود)ممکن است محدوديت ايجاد کند و راه حل را به سوي جواب بهينه محلي سوق دهد.اين اتفاق معمولاً در جمعيت هاي کم اتفاق مي افتد.روش هاي Rank ,Scaling tournament selection بر اين مشکل غلبه مي کنند
چند نمونه از کاربرد هاي الگوريتم هاي ژنتيک :
نرم‌افزار شناسايي چهره با استفاده از تصوير ثبت شده به همت مبتکران ايراني طراحي و ساخته شد. در اين روش، شناسايي چهره براساس فاصله اجزاي چهره و ويژگي‌هاي محلي و هندسي صورت مي‌گيرد که تغييرات ناشي از گيم، تغييرات نور و افزايش سن کمتين تأثير را خواهد داشت. همچنين گراف‌ها براي چهره‌هاي جديد با استفاده از الگويتم‌هاي ژنتيک ساخته شده و با استفاده از يک تابع تشابه، قابل مقايسه با يکديگر هستند که اين امر تأثير به‌سزايي در افزايش سرعت شناسايي خواهد داشت.
توپولوژي هاي شبکه هاي کامپيوتي توزيع شده.
بهينه سازي ساختار ملکولي شِميايي(شيمي)
مهندسي برق براي ساخت آنتنهاي Crooked-Wire Genetic Antenna
مهندسي نرم افزار
بازي هاي کامپيوتري
مهندسي مواد
مهندسي سيستم
رباتيک(Robotics)
تشخيص الگوو استخراج داده(Data mining)
حل مسئله فروشنده دوره گرد
آموزش شبکه هاي عصبي مصنوعي
ياددهي رفتار به رباتها با GA
يادگيري قوانين فازي با استفاده از الگويتم هاي ژنتيک.
يک مثال ساده:
ما يک مربع 3*3 داريم که مي خواهيم اعدادي بين 1تا15 را در اين مربع قرار دهيم به طوري که جمع
اعداد در هر سطرو ستون برابر 24 شود.
=24
=24
=24N N N
N N N
N N N
ابن مسئله تا حدودي پيچيده است.ممکن است يک انسان بتواند آن را در مدت زماني مشخص حل کند ولي هيچ گاه يک کامپيوتر نخواهد توانست آن رادر مدت زمان کوتاهي با استفاده از اعداد تصادفي حل کند. ولي الگوريتم ژنتيک مي تواند اين مشکل را حل کند.
نسل اول :
اولين گام ايجاد کردن يک نسل ابتدايي براي شروع کار است که شامل تعدادي ژنوم تصادفي است.اين ژنوم ها به صورت باينري(0و1) نشان داده مي شوند. حالا مثال مان:
اول يکسري عدد به صورت تصادفي توليد مي شوند. هر ژنوم يا کروموزوم شامل اطلاعاتي براي هر 9 جاي خالي است .چون اين اعداد مقادير بين 0تا15 دارند مي توان آنها را با 4 بيت يا ژن داده نمايش داد. پس هر ژنوم شامل 36 بيت است.
يک نمونه ژنوم مي تواند به شکل زير باشد:
Bits (Genes) 0110 1100 1111 1011 0100 1010 0111 0101 1110
Values(Traits) 6 12 15 11 4 10 7 5 14
حالابايد به هر ژنوم در مجموعه يک عدد تناسب(Fitness) بنابر تاثير آن در حل مسئله نسبت داد.فرآيند وروش محاسبه اين عدد براي هر مسئله فرق مي کند.انتخاب الگوي مناسب براي مسئله مشکلترين و حساسترين بخش در حل مسئله ژنتيک است.دراين مثال ما اعداد را در مکان هايشان جايگذاري مي کنيم و بررسي مي کنيم که چقدر با جواب اصلي فاصله دارند.
33=
25=
26=
=33
=25
=2615 12 6
10 4 11
14 5 7
مقادير معادل عبارتند از 33و25و26و24و21و39.واضح است که اين مقادير مسئله را حل نمي کنند.پس بايد مقادير تناسب را براي اين ژنوم محاسبه کرد.براي اين کار ابتدا فاصله هرمجموع را از24 محاسبه کرده،سپس معکوس مجموع تفاصل آنها را محاسبه مي کنيم .بنابراين درجه تناسب براي اين ژنوم تقريباً برابر 0.033 است.هرچقدر که اعداد ما به جواب نزديکتر باشند عدد تناسب بزرگتر خواهد شد.اما اگر مخرج ما برابر 0شود چه اتفاقي مي افتد؟ دراين صورت همه اعداد ما برابر 24 شده اند وما به جواب رسيده ايم.
نسل بعدي :
دو ژنوم به طور تصادفي براي توليد نسل بعدي انتخاب مي شوند. اين اصلي ترين بخش الگوريتم ژنتيک است که از 3 مرحله تشکيل شده:
انتخاب :
دو ژنوم به طور تصادفي از نسل قبل انتخاب مي شوند.اين ژنوم ها داراي اعداد تناسب بزرگتري هستند و بعضي صفات آنها به نسل بعدي منتقل مي شوند. اين بدين معني است که عدد تناسب در حال افزايش خواهد بود.بهترين روش براي تابع انتخاب(Fitness) در اين مسئله روشي به نام رولت(Roulette) است.اول يک عدد تصادفي بين صفر وعدد تناسب نسل قبلي انتخاب مي شود. تابع انتخاب به صورت زير خواهد بود:
RouletteSelection()
{
float ball = rand_float_between(0.0, total_fitness);
float slice = 0.0;
for each genome in population
{
slice += genome. fitness;
if ball < slice
return genome;
}
}
تغيير از يک نسل به نسل بعدي(Cross over) :
حالا دو ژنوم بخشي از ژنهايشان را براي ايجاد نسل بعدي اهدا مي کنند. اگر آنها تغيير پيدا نکنند همانطور بي تغيير به نسل بعدي منتقل خواهند شد.درجه Crossover نشان دهنده اين است که هر چند وقت يکبار ژنوم ها تغيير پيدا خواهند کرد و اين عدد بايد در حدود 65-85% باشد.
عملگر تغيير در ژنوم هاي باينري مثال ما با انتخاب يک مکان تصادفي در ژنوم براي تغيير آغاز مي شود. بخش اول ژنهاي پدر و بخش دوم ژنهاي مادر با هم ترکيب مي شوند(و بالعکس) تا2 فرزند توليد شوند. در زيريک عمل تغيير را مي بينيم.
