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

الگوريتمهای ژنتيك[۱] ابزاری می باشند [۵,۶,۷,۸,۹]  که توسط آن ماشين می تواند مكانيزم انتخاب طبيعی را شبيه سازی نمايد. اين عمل با جستجو در فضای مسئله جهت يافتن جواب برتر و نه الزاما بهينه صورت می پذيرد.

خرید و دانلود متن کامل:

پایان نامه ارشد کامپیوتر - نرم افزار دانشگاه آزاد ساری:بهبود خوشه بندی شبکه های حسگر بیسیم با استفاده از ترکیب الگوریتم ژنتیک و کلونی مورچگان

بهبود خوشه بندی شبکه های حسگر بیسیم با استفاده از ترکیب الگوریتم ژنتیک و کلونی مورچگان

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

 

۲-۹-۱٫پیش زمینه ی بیولوژیکی ژن ها و کروموزوم ها

همه ی ارگانیسم های زنده از سلول ها تشکیل شده اند. در هر سلول مجموعه ای از کروموزوم ها به شکل رشته ای از DNA وجود دارد که به صورت مدلی از کل ارگانیسم تعبیر می شود. هر کروموزوم از یک سری ژن در بلوک های DNA تشکیل شده است.هر ژن یک الگوی خاصی را رمز گشایی[۳] می کند. به عبارت دیگر هر ژن یک صفت[۴] را دیکود می کند. مثلا رنگ چشم یک فرد به عنوان یک صفت است. مجموعه ای از صفت ها را Alleles می گوییم. از سوی دیگر هر ژن دارای موقعیت مشخصی در کروموزوم است که به این موقعیت لوکاس[۵] می گویند. مجموعه ی کامل ماده ی ژنتیکی را ژنوم[۶] می گویند و یک مجموعه ی به خصوصی از ژن ها را در ژنوم ژنو تابپ[۷] می نامند. که این Genotype اساس فنو تایپ[۸] بوده و ویژگی های فیزیکی و فکری مثل رنگ چشم و هوش و مثل آن را به وجود می آورد.

۲-۹-۲٫تولید سلول های جدید

در هنگام تولید سلول های جدید یک تلفیق[۹] توسط عمل ادغام [۱۰] صورت می گیرد.در این فرآیند ژن های والد، کروموزوم های جدید را شکل می دهد. این مولود های جدید جهش یافته،  یعنی DNA آنها تحول یافته است. این تغییرات ممکن است همراه با خطا در کپی شدن ژن های والد صورت بگیرد. Fitness Function یک ارگانیسم، با توجه به موفقیت این ارگانیسم در ادامه ی حیات آن تعیین می شود.

 

۲-۹-۳٫توضیحات پایه

روش الگوریتم ژنتیک با یک مجموعه از نقاط فضای جستجو[۱۱] آغاز می شود که جمعیت[۱۲] نامیده می شود و با کروموزوم ها نشان داده می شوند. هر نقطه از فضای جستجو با یک کروموزوم نشان داده می شود و مجموعه چند نقطه یک جمعیت را تشکیل می دهند. جواب های گرفته شده از یک جمعیت برای تولید جمعیت جدید به کار گرفته می شود. این کار با این امید صورت می گیرد که جمعیت جدید بهتر از جمعیت قبلی باشد. جواب هایی که برای تولید جواب های جدیدتر به کار گرفته می شوند بر اساس میزان شلیستگی انتخاب می شوند. بدین معنی که جواب های مناسب شانس بیشتری برای تولد مجدد خواهند یافت و این روند ادامه پیدا می کند تا آنکه بعضی از شرایط الگوریتم مانند تعداد دفعات تکرار یا بهبود جواب ها اقناع شود.

۲-۹-۴٫فضای جستجو

وقتی که مسئله ای را حل می کنیم هدف ما، پیدا کردن بهترین جواب از میان جواب های مختلف است. فضای همه ی حالت های ممکن در حل یک مسئله را فضای جستجو[۱۳] می نامند. هر جواب می تواند با مقداری که بیانگر مناسب بودن (Fitness) آن است، نشان داده شود. جستجو برای جواب یعنی، جستجو برای پیدا کردن اکسترمم (ماکسیمم یا مینیمم) در آن فضای جستجو.

پیچیده و بزرگ بودن فضاهای جستجو و اینکه نمی دانیم که از کجای این فضا باید عمل جستجو را انجام دهیم، ما را به استفاده از الگوریتم های ژنتیک سوق می دهد.

[۱] Genetic algorithm

[۲] Richen berg

[۳] Decode

[۴] Trait

[۵] Locus

[۶] Genome

[۷] Genotype

[۸] Phenotype

[۹] Recombition

[۱۰] Cross over

[۱۱] Search space

[۱۲] Population

[۱۳] Search Space