اشتراک گذاری یک تجربه : الگوریتم ژنتیک برای مبتدیان – بخش سوم

مسائلی وجود دارند که الگوریتم های دقیق آنها مدت زمان بسیار زیادی طول می کشد تا به جواب برسد .

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

مساله فروشنده دوره گرد یکی از این مسائل است .تا بحال کسی نتوانسته است الگوریتم سریعی ( الگوریتم زمانی چند جمله ای) برای آن پیدا کند ، البته کسی هم نتوانسته است وجود نداشتن چنین الگوریتمی را اثبات کند.

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

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

 الگوریتم های اکتشافی:

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

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

(( هدف ما این است که در فضای جواب های ممکن به دنبال بهترین جواب بگردیم )) 

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

چندین الگوریتم اکتشافی وجود دارند مثل :

۱- Simulated Annealing

۲- Ant Colony

۳- Random Cost

۴-Evolution Strategy

۵- Genetic Algorithm 6- Cellular Automata

الگوریتم ژنتیک یکی از الگوریتم های اکتشافی است .

الگوریتم ژنتیک :

۱)  الگوریتم ژنتیک یک روش جستجوی موثر در فضاهای بسیار وسیع و بزرگ است که در نهایت منجر به جهت گیری به سمت پیدا کردن یک جواب بهینه می گردد که شاید نتوان در مدت زمان زندگی یک فرد به آن جواب بهینه دست یافت .

۲) ایده اصلی الگوریتم های تکاملی ( Evolutionary) در سال ۱۹۶۰ توسط ریچنبرگ (Ingo Rechenberg) مطرح گردید . الگوریتم های ژنتیک که منشعب از این نوع الگوریتم ها است ، در حقیقت روش جستجوی کامپیوتری بر پایه الگوریتم های بهینه سازی و بر اساس ساختار ژن ها و کروموزوم هاست که توسط پروفسور هولاند (Holland)  در دانشگاه میشیگان مطرح شد و پس از وی توسط جمعی از دانشجویانش مثل گولدبرگ توسعه یافت .

۳) همه ی ارگانیسم های زنده از سلول ها تشکیل شده اند . در هر سلول مجموعه ای از کروموزوم ها به شکل رشته ای از DNA وجود دارند که به صورت یک مدل از کل ارگانیسم تعبیر می شوند .هر کروموزوم از یک سری ژن در بلوک های DNA تشکیل شده که در شکل زیر تعدادی از ژن های سازنده ی کروموزوم نشان داده شده است .

 

هر ژن یک الگوی خاصی را رمزگشایی می کند . به عبارت دیگر هر ژن یک صفت را دیکود می کند . مثلا رنگ چشم یک فرد به عنوان یک صفت است . هر ژن دارای موقعیت مشخصی در کروموزوم است . تا همینجا کافیست .

۴) الگوریتم ژنتیک هم مانند سایر الگوریتم های اکتشافی از میان مجموعه ای از راه حل های ممکن مساله ، بهترین راه حل را انتخاب می کند .قبل از اینکه مساله فروشنده دوره گرد را با الگوریتم ژنتیک حل کنیم ، توضیح مختصری در مورد مفاهیم اصلی الگوریتم ژنتیک ارائه خواهیم داد .

هر راه حل مساله را یک کروموزوم می نامیم ، هر کروموزوم از قسمت های کوچکتری به نام ژن تشکیل شده است.

در مرحله اول ، مجموعه عظیمی از راه حل ها را به صورت تصادفی ایجاد می کنیم ، در الگوریتم ژنتیک به این مجموعه راه حل ها ، جمعیت (Population) گفته می شود .

 در یک جمعیت (به زبان ساده)باید بتوانیم مشخص کنیم که یک راه حل چه قدر خوب است ،

به زبان دیگر ، پس از تشکیل هر نسل باید مشخص گردد کروموزوم های آن نسل تا چه حد به جواب بهینه نزدک هستند ؟ این کار توسط تابع برازش صورت می گیرد . به کمک تابع برازش می توانیم بهترین راه حل هر نسل را انتخاب کنیم  .

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

عملگر انتخاب :

ایجاد نسل جدید از طریق تولید مثل صورت می گیرد. برای تولید مثل نیاز به پدر و مادر داریم . پدر و مادر از جمعیت فعلی ، توسط عملگر انتخاب، تعیین می شوند.  این عملگر از بین کروموزوم های موجود در یک جمعیت ، بهترین ها را برای ایجاد نسل جدید انتخاب می کند . روش های انتخاب مختلفی وجود دارند :

۱-روش چرخ رولت

۲- روش رتبه بندی

۳- روش مسابقه

عملگر نخبه گرایی :

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

عملگر تقاطع :

ترکیب دو کروموزوم و ایجاد یک کروموزوم فرزند از طریق عملگر تقاطع ایجاد می شود . امیدواریم عملگر تقاطع ، راه حل بهینه تری ایجاد کند . دو نوع رایج این عملگر ، تقاطع یک نقطه ای و تقاطع دو نقطه ای هستند .

عملگر جهش :

یک تغییر کوچکی در یکی از ژن ها منجر به جهش خواهد شد . توجه داشته باشید که احتمال جهش خیلی پایین است .

پس از ایجاد نسل جدید ، دوباره بهترین راه حل ( کروموزوم) این نسل را انتخاب می کنیم و با بهترین راه حل موجود مقایسه می کنیم . این کار ( ساخت نسل ) را آنقدر ادامه می دهیم تا الگوریتم به شرط پایانی خود برسد . مثلا جواب بهینه یافت شود و یا زمان انجام الگوریتم به پایان برسد .

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

 

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


منابع :

۱- وفایی جهان،مجید ،مبانی مدل سازی و شبیه سازی کامپیوتری ، انتشارات خط اول ،ص ۱۱۵-۱۳۵ ،سال ۱۳۹۲

۲- نیپولیتان ، جعفر نژاد قمی ، طراحی الگوریتم ها ، انتشارات علوم رایانه ، سال ۱۳۹۰

۳- http://www.theprojectspot.com/tutorial_post/creating-a-genetic-algorithm-for-beginners

 

پاسخ دهید

*