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

فهرست مطالب

مقدمه                ۱
چکیده مقاله             ۲
چارچوب کلی الگوریتم ژنتیک       ۳
عملگرد های ژنتیک          ۴
الگوریتم ژنتیک و استراتژی تکاملی             ۹
اصول الگوریتم ژنتیک          ۱۵
Encoding-1          ۱۵
Evalution-2          ۱۶
Crossover-3          ۱۷
Mutation-4          ۱۸
Decoding-5          ۱۹
الگوریتم ژنتیک          ۲۲
حل مساله به روش الگوریتم ژنتیک             ۲۶
Encoding-1          ۲۶
Evaluation-2          ۲۷
Selection-3          ۲۷
Crossover – ۴          ۲۸
Mutation – ۵          ۲۸
The Traveling Salesman Problem 34
TSP with genetic algorithm 37
مقایسه روشهای مختلف الگوریتم ژنتیک برای TSP    ۵۱
فرم کلی الگوریتم های ژنتیک             ۵۶
مسئله فروشنده دوره گرد       ۵۷
انتخاب والدها (Select parents)           ۶۲
جهش ژنی (Mutation)       ۷۱
Random mutation       ۷۱
Swap                ۷۳
مزایا و معایب الگوریتم ژنتیک             ۷۸
مراجع                ۸۰

مراجع :

[۱] . kylie Bryant , Genetic Alogorithm and the traveling salesman problem , Hevey Mudd college , 2000

[۲] . Dr Alex Rogers , CM2408 – SYMBOLIC Al Lecture 8 –Introduction to Genetic Algorithm , December 2002

[۳] . Mehadad Dianati , Insop , Mark Treiber , An Introduction to Genetic Algorithms and Evolution strategise.University of waterloo , Canada , 2002

[۴] . Jean – philippe , ph.D , Genetic  Alogorithm Viewer : Demonstration of a Genetic Alogorithm , May 2000

[۵]. Eric crevice prebys , The Genetic Alogorithm in Computer Scince 1997

[۶] . Marcin L . Pilat and Tony white , Using Genetic Alogorithm to Optimize ACS – TSP , School of Computer Science. Carleton University , Canada , 2000

[۷] . Genetic Alogorithm , Beasly – Bull – Martin , October 2000

[۸] . Dr . George Magoulas , Some problems are too difficult to solve CS3018S

[۹]. Byung – In kim , Jea –IK Shim , Min Zhang , Comparison of TSP Alogorithm , December 1998

[۱۰] . Chia – Hsuan Yeh , Graduate Course An Introduction to Genetic Alogorithm , Goldberg , 1989

چکیده مقاله :

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

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

کلمات کلیدی :

Gene – Chromosome – Allele – Encoding – Population – Evaluation – Fitness – Selection – Crossover – Mutation – Decoding – Generation – Parent

مقدمه :

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

الگوریتم های ژنتیک با توجه به نظریه داروین در مورد تکامل ، جان گرفتند . سپس نظریه محاسبات تکاملی توسط ریچنبرگ در سال ۱۹۷۵ منجر به اختراع الگوریتم های ژنتیک توسط هالاند Holland و دانشجویان شد .

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

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

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

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

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

چارچوب کلی الگوریتم ژنتیک

در دهه هقتاد میلادی دانشمندی از دانشگاه شیان به نام جان هلند ایده استفاده از الگوریتم ژنتیک را در بهینه سازی مهندسی مطرح کرد.ایده اساسی این الگوریتم انتقال خصوصیات موروثی توسط ژن هاست.رض کنید مجموعه صوصیات انسان توسط کروموزوم هایاو به نسل عدی منتقل می شوند.هر ژن در این کروموزوم ها نماینده یک خصوصیات است.به عنوان مثال ژن ۱ می تواند رنگ چشم باشد،ژن ۲ طول قد، ژن ۳ رنگ مو الی آخر. حال اگر این کروموزوم به تمامی ،به نسل بعد انتقال یابد،تمامی خصوصیات نسل بعدی شبیه به خصوصیات نسل بعد خواهد بود.بدیهیست که در عمل چنین اتفاقی رخ نمی دهد. در واقع به صورت همزمن دو اتفاق برای کروموزوم ها می افتد.اتفاق اولموتاسیون(Mutation ) است. موتاسیون به این صورت است که بعضی ژن ها بصورت کاملا  تصادفی تغییر می کنند. البته تعداد این گونه ژن ها بسیار کم می باشد ام در هر حال این تغییر تصادفی همانگونه که بیشتر دیدیم بسیار مهم است.

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

بر اساس آنچه ذکر شد می توانیم مراحل الگوریتم ژنتیک را به صورت زیرتوضیح دهیم.

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

در واقع هدف الگوریتم دستیابی به کروموزوم های بهینه) جواب ها) از طریق تولید مثل بهترین کروموزوم ها در هر نسل است. کروموزوم ها اغلب به صورت یک رشته از صفر و یک ها (مقادیر باینری) نمایش می یابند که هر بیت از این رشته می تواند نمایشگر یک ژن باشد. البته نمایش های دیگری از کروموزوم به شکل درخت(Tree) یا لیست وجود دارد که فعلاً به آنها نمی پردازیم.

پس از این کار باید معیاری برای تشخیص جواب های بهینه یا ارز یابی بهترین کروموزوم ها داشته باشیم. این معیار اغلب به صورت یک تابع ریاضی که بر کروموزوم ها اعمال می شود نشان داده می شود که به نام تابع هدف یا تابع بهینگی نامیده می شود.

این دو کار در واقع مراحل آماده سازی جهت اجرای الگوریتم ژنتیک است. پس انجام این دو کار یک جمعیت ابتدایی) نسل اولیه) از راه حل های ممکن داریم. برای شروع الگوریتم این نسل اولیه باید تولید مثل کند.تولید مثل در سه مرحله انجام می شود. مرحله اول انتخاب یا Selection  است.

در این مرحله بهترین کروموزوم ها (بر اساس تابع بهینگی) برای تولید مثل انتخاب می شوند.ذکر این نکته ضروریست که حتی در اینجا هم اندکی تصادف را باید دخیل کنیم. یعنی مثلاً بهترین کروموزوم ها را به احتمال ۹۰% انتخاب کنیم. این احتمالاتی انتخاب کردن بهترین ها اندکی شانس  بقا به کروموزوم های ضعیف تر می دهد.اما شاید بپرسید چرا نباید با اطمینان بهترین ها را اتخاب کرد و همه ضعیف تر ها را در هر نسل از بین برد؟

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

پس از مرحاه انتخاب نوبت به تولید مثل کروموزوم ههی انتخاب شده می رسد. این کار همان گونه که پیشتر گفتیم توسط دو عمل گر  CrossOver  و موتاسیون اجام می پذیرد.

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

در مرحله موتاسیون مقدار بعضی ژن ها به تصادف عوض می شود.یعنی مثلاً اگر کروموزوم های ما چنانکه گفتیم بوسیله رشته های صفر و یک نمایش داده می شوند در هر کروموزوم تعداد صفر یا بیشتر ژن (بیت) انتخاب شده ومقدار آنها از صفر به یک یا برعکس تغییر می یابد. برای موتاسیون نیز روش های دیگری وجود دارد که روش گفته شده ساده ترین و در عین حال معمول ترین آنها است.آنچه باید بدان دقت شود اینست که در صد موتاسیون معمولاً بسیار کم در نظر گرفته می شود.مثلاً چیزی کمتر از ۵% کروموزوم ها تحت تأثیر موتاسیون قرار می گیرند .

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

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

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

هنگامی که لغت تازع بقا به کار می رود اغلب بار ارزشی منفی آن بهذهن می آید . شاید همزمان قانون جنگل به ذهن برسد و حکم بقای قوی تر !

البته برای آنکه خیالتان راحت شود می توانید فکر کنید که همیشه هم قوی ترین ها برنده نبوده اند مثلا” دایناسورها با وجود جثه عظیم و قوی تربودن در طی روندی کاملا” طبیعی بازی بقا و ادامه نسل را واگذار کردند در حالی که موجوداتی بسیار ضعیف تر از آنها حیات خویش را ادامه دادند . ظاهرا” طبیعت بهترین ها را تنها بر اساس هیکل انتخاب نمی کند ! در واقع درست تر آنست که بگوییم طبیعت مناسب ترین ها (Fittest) را انختاب می کند نه بهترین ها .

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

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

در شرایط کاملا” طبیعی این افراد پیشرفت بهتری خواهند کرد و رفاه نسبتا” بالایی خواهند داشت و این رفاه خود باعث طول عمر بیشترو باروری بهتر خواهد بود (توجه کنید شرایط طبیعی است نه در یک جامعه سطح بالا با ملاخظات امروزی یعنی طول عمر بیشتر در این جامعه نمونه با زاد و ولد بیشتر همراه است . ) حال اگر این خصوصیت (هوش ) ارثی باشد به طبع در نسل بعدی همان جامعه تعداد افراد باهوش به دلیل زاد و ولد بیشتر این گونه افراد بیشتر خواهد بود . اگر همین روند را ادامه دهید . خواهید دید که در طی نسل های متوالی دائما جامعه نمونه ما با هوش و با هوش تر می شود . بدین ترتیب یک مکانیزم ساده طبیعی توانسته است در طی چند نسل عملا” افراد کم هوش را از جامعه حذف کند علاوه بر اینکهع میزان هوش متوسط جامعه نیز دائما در حال افزایش است ( البته امکان داشت اگر داروین بی عرضگی افراد باهوش امروزی را می دید کمی در تئوری خود تجدید نظر می کرد اما این مسئله دیگر نیست !)

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

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

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

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

در این میان آنچه شاید بتواند تا حدودی ما را در فهم این مساله یاری کند مفهومیست به نام : تصادف یا جهش .

به عبارتی طرح واپیما نسبت به طرح اتومبیل یک جهش بود و نه یک حرکت تدریجی . در طبیعت نیز به همین گونه است . در هر نسل جدید بعضی از خصوصیات به صورتی کاملا” تصادفی تغییر می یابند سپس بر اثر تکامل تدریجی که بیشتر توضیح دادیم در صورتی که این خصوصیت تصادفی شرایط طبیعت را ارضا کند حفظ می شود در غیر این صورت به شکل اتوماتیک از چرخه طبیعت حذف می گردد .

در واقع می توان تکامل طبیعی را به این صورت خلاصه کرد: جست و جوی کورکورانه (تصادف یا Bind Search ) + بقای قوی تر .

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

روش های کلاسیک ریاضیات دارای دو اشکال اساسی هستند . اغلب این روش ها نقطه بهینه محلی (Local Optima) را به عنوان نقطه بهینه کلی در نظر می گیرند و نیز هر یک از این روش ها تنها برای مساله خاصی کاربرد دارند . این دو نکته را با مثال های ساده ای روشن می کنیم .

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

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

اما در روش های هوشمند خاصه الگوریتم ژنتیک بدلیل خصلت تصادفی آنها حتی اگر هم از نقطه ۱ شروع کنیم باز ممکن است در میان راه نقطه A به صورت تصادفی انتخاب شود که در این صورت ما شانس دست یابی به نقطه دست یابی به نقطه بهینه کلی (Global Optima) را خواهیم داشت .

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

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

تمام مقالات و پایان نامه و پروژه ها به صورت فایل دنلودی می باشند و شما به محض پرداخت آنلاین مبلغ همان لحظه قادر به دریافت فایل خواهید بود. این عملیات کاملاً خودکار بوده و توسط سیستم انجام می پذیرد.

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