فروشگاه فایل BeigShop

چکيده مقاله :

در اين مقاله ابتدا الگوريتم های ژنتيک را معرفی کرده و مراحل انجام چنين الگوريتم هايی توضيح داده می شود.

بعد از اينکه يک ديد کلی نسبت به الگوريتم های ژنتيک پيدا کرديم به مساله Traveling Salesman Problem

می پردازيم.

ابتدا چند روشی که برای حل TSP ارائه شده است را بيان می کنيم و بعد سعی می کنيم الگوريتم های ژنتيک

مختلفی را برای اين مساله مطرح کنيم و سپس بررسی می کنيم که کدام يک از اين الگوريتم های ژنتيک بهتر از

بقيه روشها جواب می دهند. در پايان نيز مقايسه ای بين الگوريتمهای ژنتيک و ديگر الگوريتمها انجام می دهيم.

مقدمه:

الگوريتم های ژنتيك ابزاری می باشند که توسط آن ماشين می تواند مكانيزم انتخاب طبيعی را شبيه سازی نمايد.

اين عمل با جستجو در فضای مسئله جهت يافتن جواب برتر و نه الزاما بهينه صورت می پذيرد.

الگوريتم های ژنتيك با توجه به نظريه داروين در مورد تكامل، جان گرفتند . سپس نظريه محاسبات تكاملی، توسط

ريچنبرگ در سال 1960 معرفی شدند و اين نظريه توسط محققان ديگر توسعه يافت تا در سال 1975 منجر به اختراع

الگوريتم های ژنتيك توسط هالاند Holland و دانشجويانش شد.

در الگوريتم های ژنتيک يک سری تعاريف اوليه داريم که در زير آمده است:

1- ژن  :( gene ) واحد پايه ژنتيک است.

2- فرم :( allele ) حالتهای مختلف هر ژن را می گويند.

3- کروموزوم :(choromosome ) به گروهی از ژن ها اطلاق می شود.

بعد از تعاريف بالا مفاهيمی از قبيل , Encoding , Evaluation Crossover , Mutation مطرح می شود که بر اساس

سه تعريف بالا مطرح می شوند.

حال به شرح مراحل ذکر شده درمقدمه می پردازيم:

Encoding :

اين مرحله شايد مشکل ترين مرحله حل مساله به روش الگوريتم ژنتيک باشد. اين مرحله به اين مفهوم است که ما

بايد با ارائه يک شبيه سازی و جايگذاری (Representation ) خوب برای کليه جواب های ممکن مراحل بعدی را ادامه

دهيم. اهميت اين مرحله به اين دليل است که نحوه ادامه کار به اين مرحله بستگی دارد.

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

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

بعد از ساختار بندی برای هر جواب ممکن از کنار هم گذاشتن اين ساختارها جمعيت اوليه ما ( First Population )

ساخته می شود.

برای مثال برای شبيه سازی اعداد يک روش معمول که به کار می رود عبارتست از تبديل عدد به يک رشته باينری ( binary )

...