مقاله الگوریتمهای ژنتیک

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

فرمت فایل : WORD (قابل ویرایش)

تعداد صفحات:30

فهرست مطالب:

مقدمه
Biological Background1-
Biological Background1-1
Reproduction-2-1
Genetic Algorithm 1-3-
Outline of the basic Genetic Algorithm-2-3-1
Some comments-3-3-1
Operators of GA -4-1
Encoding-1-4-1
Crossover-2-4-1
Mutation-3-4-1
Parameters of GA-5-1
-1-5-1احتمالcrossover
-2-5-1احتمال Mutation
Other parameters-3-5-1        
Selection-2
Selection-1-2
Roulette Wheel -1-1-2
Selection-2-1-2 Rank
Steady State-3-1-2
Elitism-4-1-2
Encoding-3
Encoding-1-3
Encoding Binary-1-1-3
Permutation Encoding-2-1-3  
Value Encoding-3-1-3
Tree Encoding-4-1-3
Crossover & Mutation-4
Crossover & Mutation-1-4
Binnary Encoding -2-4
Single Point Crossover-1-2-4
Two Point Crossover-2-2-4
Uniform Crossover-3-2-4
Arithmetic Crossover-4-2-4  
Mutastion-5
Mutastion-1-5
Permutation Encoding-2-5
Value Encoding -3-5
Tree Encoding -4-5
Recommendations-5-5
Application of GA-6-5
 5-7- The Traveling Salesman Problem
5-8- TSP with genetic algorithm
5-9-  مقایسه روشهای مختلف الگوریتم ژنتیک برای TSP
نتیجه گیری

مقدمه

الگوریتمهای ژنتیک قسمتی از محاسباتهایی هستند که رشد سریعی از تکامل هوش مصنوعی است. همانطور که می توانید حدس بزنید الهامی از تئوری تکاملی داروین می باشد به سادگی می توان گفت، مسائل توسط یک فرآیند تکاملی ناشی از بهترین(مناسبترین) راه حل(بازمانده) حل می شود. به عبارتی دیگر راه حل استنتاج می شود. تا به حال فرمهای مختلفی از رمز گذاری ها encoding و عملگرهای crossover وmutation را در حل مساله tsp به روش الگوریتم ژنتیک دیدیم. این حالتها می توانند با هم ترکیب شوند و منجر به رسیدن به راه حلهای متفاوتی برای tsp به روش الگوریتم ژنتیک شوند. ولی از آنجایی که متدهای crossover روی encoding های خاصی عمل می کند در نتیجه الگوریتمهای ژنتیک خیلی متفاوتی برای جستجو نداریم حال به بررسی الگوریتمهای ژنتیک مغز یعنی بدون استفاده ازheuristic information می پردازیم.

فرض کنید که pmx crossover را انتخاب کرده ایم و هیچ عملگری را برای mutation اتخاذ نکرده ایم. با این شرایط در 33 شهر به جوابی می رسیم که طول آن % 10 از جواب بهینه بیشتر است و برای 100 شهر این میزان به%210 می رسد. اگر در یک مساله که از 30 شهر تشکیل شده است اگر از pmx استفاده کنیم بهترین طول 498 و اگر از  order crossover استفاده کنیم این میزان به 425 کاهش می یابد در حالی که cycle crossover نتیجه ای برابر 517 می دهد. از آنجایی که می دانیم در این مساله خاص(30 شهر) بهترین جواب طولی برابر 420 دارد به نظر می رسد که order crossover جوابی بهتر از بقیه می گیرد.

حال به بررسی matrix crossover می پردازیم. اگر از یک crossover دونقطه استفاده کنیم مشاهده می شود که برای 30 و 50 و75و100 و318 دورهایی با طول 420 و426و535و629و42154 را ارائه می کند. که همه این جوابها کمتر از % 2 بیشتر از جواب بهینه هستند.

پس احتمالاً استفاده از یالها بسیار امیدوارکننده تر از استفاده از راسها به عنوان متغیر است.

توجه کنید که به هر حال نمایش ماتریس فضای بیشتری را برای ذخیره کردن نسبت به نمایش به صورت عدد صحیح و crossover ساده می خواهدودر ضمن محاسبات crossover و mutation در ماتریس پیچیده تر و زمانبرتر است.

همچنین روش دیگری که تست شده این است که ما از(2-opt) برای mutation استفاده کنیم و از crossover استفاده نکنیم.

این روش نیز جواب خوبی ارائه می دهد ولی جواب قبلی بهتر از این روش است. در ضمن برای وقتی که n را زیاد فرض می کنیم این روش جوابی مناسب ارائه نمی دهد.

Heuristic algorithm وقتی که با (2-opt) mutation ترکیب می شود بهترین جواب را در مقایسه با متدهایی که تا به حال گفتیم بر می گرداندبه طوری که این جواب بسیار نزدیک به مقدار بهترین جواب است. البته این روش فضای زیادی را اشغال می کند و نیز وزن هر یال در جایی ذخیره شود.

در نتیجه می بینیم که الگوریتم ژنتیک وقتی که از نمایش ماتریس برای encoding و از matrix crossover یا Heuristic crossover استفاده می کند بهترین جواب را برمیگرداندو بهتر از روشهای دیگر کار می کنند.

در هر دو روش crossover بالا ازmutation (2-opt) کیفیت الگوریتم را افزایش می دهد.

Biological Background1-

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

اگر بخواهیم یک مساله را حل کنیم راه حل هایی هست که نسبت به دیگر راه حل ها بهترین می باشند. فضای تمام راه حل های ممکن (مجموعه راه حلها که راه حل مورد نظر«بهترین» در آن نیزState search مجموعه وجود دارد) فضای جستجو خوانده می شود. اغلب حالت جستجو نامیده می شود. هر نقطه در فضای جستجو یک راه حل ممکن را نشان می دهد. هر راه حل ممکن آن برای مسئله نشان داده می شود . fittness می تواند توسط ما به دنبال بهترین راه حل میان شماری از راه حلهای ممکن هستیم که توسط یک نقطه GA با در فضای جستجو علامتگذاری می شود. جستجو برای یک راه حل برابر می شود با جستجو برای مقادیر اکسترمم(مینیمم یا ماکزیمم) در فضای جستجو است.

Biological Background1-1

یک کروموزم از ژنها تشکیل شده است. هر ژن یک پروتئین خاص را رمزگذاری می کند. کروموزم رشته هایی ازDNA می باشند.

به طور اساسی می توان گفت که هر ژن یک ویژگی یا خصیصه را رمزگذاری می کند به عنوان مثال رنگ چشمان. مجموعه های ممکن رای یک خصیصه(فرضاَ آبی، قهوه ای)، Alleles نامیده می شود.

هر ژن پوزیشن مخصوص به خود را در کروموزم دارد که به این پوزیشن locus یا مکان نامیده می شود.

نامیده می شود. مجموعه (Genome)مجموعه کاملی از ماده ژنتیک(همه کروموزمها) ژنوم دارای توسعه دیرتر از Genotype نامیده می شود. Genotype بخصوصی از ژنها در ژنوم ارگانیسم می باشد، که می توان به مشخصه های فیزیکی و روانی phenotype مبنای تولد مانند رنگ چشم ، هوش و غیره اشاره نمود.

Reproduction-2-1

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

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

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

و الگوریتم simulated annealing، tabu search ، hill climbingبعضی از این متدها ژنتیک است. راه حل هایی که از طریق این متدها پیدا می گردد، اغلب راه حل های خوبی به حساب می آیند، اغلب نمی توان ثابت کرد بهترین راه حل چیست.

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

مسائل خیلی مهم بسیاری وجود دارد که خیلی سخت است که یک راه حل را برای آنها پیدا کنیم ولی اگر آنها را داشته باشیم به آسانی می توانیم راه حل را با آنها چک کرد. این منتج به مسائل یا چند جمله ای غیر قطعی Non deterministic polynomid مخفف NP می شود. NPکامل می باشد و به این معنی است که این امکان وجود دارد که راه حل (توسط بعضی از الگوریتمهای غیر قطعی) حدس زد و سپس آن را با مساله چک کرد.

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

به سادگی می تواند محدود شود به مسائلی که جواب آنها می تواند بله یا خیر NP مطالعه مسائل باشد.

- NPبه دلیل اینکه مسائل با خروجی های پیچیده وجود دارد یک کلاس از مسائل به نامNP معرفی می شود این کلاس به محدودیت کلاس مسائل کامل نمی باشد. Hard prolems این است که یک الگوریتم ساده شاید در ابتدا مشاهده شود که بتوان NP یک خصیصه از مسائل برای پیدا کردن راه حل های مناسب می تواند استفاده شود. ولی این دیدگاه به طور کلی راه حل های ممکن بسیاری را تولید می کند فقط تلاش برای پیدا کردن راه حل های ممکن یک فرآیند می باشد. برای حتی مثالهای نسبتاَ بزرگتر این نوع از مسائل این دیدگاه O(2^n) بسیار کند با زمان کل قابل استفاده نیست.

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

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