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

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

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

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

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

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

 تقسیم بندی مسائل :

مسائلی که قصد یافتن الگوریتمی برای آنها داریم در سه گروه کلی قرار می گیرند :

۱- مسائلی که الگوریتم های زمانی چند جمله ای برای آنها یافت شده است .

هر مساله ای که یک الگوریتم زمانی چند جمله ای برای آن یافته ایم در این گروه قرار داده می شود . برای مرتب سازی الگوریتم های n logn ، برای جست و جو رد یک آرایه مرتب ، یک الگوریتم از مرتبه زمانی log n ، برای ضرب ماتریس ها یک الگوریتم از مرتبه زمانی n۲.۳۸ یافته ایم .

چون n میزانی از مقدار داده در ورودی این الگوریتم هاست ، همگی زمان چند جمله ای دارند . این فهرست همچنان ادامه دارد و به آن افزوده می شود .

الگوریتم هایی با پیچیدگی زمانی چندجمله ای را ، الگوریتم های سریع در نظر می گیریم.

۲- مسائلی که کنترل ناپذیری آنها ثابت شده است .

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

۳- مسائلی که کنترل ناپذیری آنها اثبات نشده است ولی تاکنون هیچ الگوریتم زمانی چند جمله ای هم برای آنها پیدا نشده است .

این گروه شامل مسائلی می شود که هیچ الگوریتم زمانی چند جمله ای برای آنها یافت نشده است ولی هنوز کسی غیر ممکن بودن این چنین الگوریتمی را اثبات نکرده است . یکی از مساله های این گروه ، مساله فروشنده دوره گرد (Travelling Salesman Problem) است . در ادامه با این مساله آشنا خواهیم شد  .

 مساله فروشنده دوره گرد :

فرض کنید فروشنده ای در نظر دارد به یک سفر فروشندگی برود . این فروشنده دوره گرد می خواهد سفر خود را از یک شهر شروع کند و با یک بار عبور از همه ی شهرها به شهر اولیه برگردد.

هدف مساله پیدا کردن کوتاه ترین دور برای فروشنده دوره گرد است .

به شکل زیر دقت کنید . a و b و c و d و e پنج شهر ما هستند . از هر شهر به تمام شهرها راه وجود دارد .

فاصله هر شهر با شهر دیگر بر روی مسیر مربوطه  با یک عدد نوشته شده است . کوتاهترین مسیری که فروشنده دوره گرد می تواند انتخاب کند عبارت است از  : AEDBCA  که هزینه ای برابر ۵۵۰ را در بردارد .

اولین راه حلی که برای حل این مساله ذهن می رسد این است که تمام دورها را پیدا کنیم و پس از ردیف کردن آنها ، آن دوری را انتخاب کنیم که هزینه ی کمتری دارد .

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

اگر راس اول را ثابت در نظر بگیریم ، برای راس دوم n-1 حالت انتخاب ، برای راس سوم n-2 حالت و به همین ترتیب برای راس آخر ۱ حالت انتخاب خواهیم داشت پس :

نیمی از این حالت ها فقط برعکس بقیه هستند و لازم نیست آنها را دوباره محاسبه کنیم  ، پس تعداد دورهای ممکن در یک گراف کامل با n راس ،عبارت است از :

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

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

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

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

اینجاست که ردپای الگوریتم های اکتشافی پیدا می گردد  .

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


منابع :

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

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

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

 

پاسخ دهید

*