الگوریتم ژنتیک برای حل مسئله تساوی ساده ریاضی

الگوریتم ژنتیک برای حل مسئله تساوی ساده ریاضی

چکیده

در این مقاله الگوریتم ژنتیک برای افراد مبتدی شرح داده شده است. سپس گام به گام محاسبات عددی الگوریتم ژنتیک برای حل مسئله تساوی ساده ریاضی به طور مختصر توضیح داده شده است.

فلسفه اصلی

الگوریتم ژنتیک به وسیله گلدبرگ که از تئوری تکامل داروین الهام گرفته شده است توسعه یافته است. باقی ماندن یک کروموزوم بستگی به قانون "افراد شایسته تر زنده بمانند" دارد. داروین همچنین اظهار داشت که بقای یک کروموزوم می تواند از طریق تولید مثل، تقاطع و جهش انجام شود.

مثال عددی

فرض کنید تساوی a+2b+3c+4d=30 وجود داشته باشد با استفاده از الگوریتم ژنتیک مقادیر a,b,c,d را به گونه ای یافت شود که تساوی برقرار باشد. در ابتدا باید تابع هدف فرمول بندی شود. که در این مثال هدف مینیم کردن تابع f(x)=a+2b+3c+4d-30 می باشد. چون چهار متغیر در معادله وجود دارد می توان کروموزوم را به شکل 1 ایجاد کرد. 

مقایسه الگوریتم ژنتیک و ممتیک

مقایسه الگوریتم ژنتیک و ممتیک

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

الگوریتم ممتیک با کمک گرفتن از ایده "مم" و پیاده کردن این مفهوم در جستجوهای محلی در ارائه جواب های فعلی در هر نسل سعی بر بهبود محلی این جواب ها می نماید حاصل این عملیات سرعت و کارائی بهتر در فرآیند جستجو می باشد. یکی از ایرادات الگوریتم های تکاملی بدون جستجوی محلی عدم بکارگیری دانش در فرآیند جستجو می باشد. الگوریتم های ترکیبی از جمله ممتیک این ویژگی را دارند که فرآیند جستجوی محلی آنها همراه با دانش می باشد.

لازم به توضیح می باشد که جستجوی محلی خود به تنهایی کارائی خوبی ندارد چون ممکن است راه حلی وجود داشته باشد که از مسیر فعلی و در نتیجه بهینه محلی دور باشد و هرگز با بهینه کردن محلی به آن نرسد. علت این امر این است که جستجوی محلی بر خلاف الگوریتم ژنتیک فقط یک راه حل را بهبود می دهد و روی کل جمعیت که به دنبال بهینه سراسری است اعمال نمی گردد. به همین دلیل است که الگوریتم ژنتیک با یک جستجوی محلی مناسب ترکیب می شود و تشکیل الگوریتم ممتیکی را می دهد. 

الگوریتم ممتیک چیست؟

الگوریتم ممتیک چیست؟

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