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

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

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

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

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

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

در ادامه مطلب ، بخش چهارم ( بخش آخر) از این مطالب را بخوانید .

ادامه ی مطلب

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

یکی از این الگوریتم ها، الگوریتم ژنتیک است . بهترین راه برای یادگیری الگوریتم ژنتیک حل یک مساله نمونه به کمک آن است.

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