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

الگوريتم‌هاي ژنتيك، به عنوان يكي از راه‌حل‌هاي يافتن جواب مسئله در بين روش‌هاي مرسوم در هوش مصنوعي مطرح است. در حقيقت بدين روش مي توانيم در فضاي حالت مسئله حركتي سريع‌تر براي يافتن جواب‌هاي احتمالي داشته باشيم؛ يعني مي توانيم با عدم بسط دادن كليه حالات، به جواب‌هاي مورد نظر برسيم.

در جهان اطراف ما همه ارگانيزم‌هاي حياتي از ساختارهاي قانونمندي تشكيل شده‌اند. ساختارهايي كه از سوي آفريدگار هستي در بطن مخلوقات قرار داده ‌شده است. همه اين ارگانيزم‌ها از بلوك‌هاي پايه‌اي از زندگي به نام سلول تشكيل به وجود آمده‌اند. قوانين مزبور در قالب ژن‌ها به صورت كد شده در هر ارگانيزم وجود دارند. از به هم وصل شدن اين ژن‌ها، رشته‌هايي طولاني به نام كروموزوم توليد مي‌شود. هر ژن نمايانگر يكي از خصوصيات آن ارگانيزم است.

مانند رنگ چشم يا رنگ مو و البته هر ژن مي‌تواند داراي مقادير مختلفي باشد. مثلاً در رابطه با رنگ چشم مي‌توانيم داراي مقاديري متناظر با مشكي، قهوه‌اي و آبي و سبز و… باشيم. هنگامي كه دو ارگانيزم به توليد مثل مي‌پردازند، در حقيقت ژن‌هاي خود را با يكديگر تركيب مي‌كنند. بدين صورت كه ارگانيزم توليد شده كه در اين متن از اين بعد آن را نوزاد مي‌ناميم، داراي نيمي از ژن‌هاي يك والد و نيم ديگر از والد ديگري است. اين عمل را تركيب مي‌ناميم. گاهي اوقات بعضي از ژن‌ها داراي جهش مي‌شوند. اين جهش تغييري در ساختار كروموزوم ايجاد نمي‌كند، اما با توجه به اين‌كه مقدار جديدي به يك ژن تخصيص مي‌يابد، موجب بروز خصوصيت جديدي مي‌شود. از اين اتفاق با نام جهش ياد مي‌كنيم.

کروموزوم

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

1011011010000101011111110

‌يا

1264196352478923455548216

‌

براي شروع فعاليت الگوريتم ژنتيك نيازمند جمعيتي از كروموزوم‌ها به صورت تصادفي هستيم. يعني در ابتدا به عنوان قدم اول، تعدادي كروموزوم به صورت تصادفي ايجاد مي كنيم. فرض كنيد N كروموزوم و اين N را جمعيت آغازين مي‌ناميم.

در ادامه تابعي به نام تابع ارزش تشكيل مي‌دهيم كه اين تابع به عنوان ورودي يك كرومزوم را دريافت مي‌كند (يك جواب مسئله) و به عنوان خروجي عددي را مبتني بر ميزان بودن كرومزوم نسبت به جواب نهايي بر مي‌گرداند. در حقيقت اين تابع ميزان خوب بودن جواب را مشخص مي‌كند. براي همه نمونه‌هاي جمعيت مقدار تابع ارزش را حساب مي‌كنيم.

در ادامه به صورت تصادفي دو نمونه از كرومزوم‌ها را انتخاب مي‌كنيم. بايد توجه داشته باشيم كه سيستم به گونه‌اي طراحي شود كه شانس انتخاب هر كرومزوم متناسب با مقدار تابع ارزش آن كروموزوم باشد. يعني اگر كرومزومي داراي مقدار تابع ارزشي بهتري بود، شانس انتخاب شدن آن بيشتر باشد (بدين وسيله سعي مي‌كنيم بيشتر روي پاسخ‌هاي بهتر مسئله پردازش انجام دهيم) اين عمل دقيقاً معادل انتخاب طبيعت در داستان ماست (موجودات قوي‌تر شانس بيشتري براي بقا دارند).

بعد از انتخاب دو كرومزوم، اكنون نوبت به تركيب مي‌رسد. براي انجام عمل تركيب، بايد يك نقطه (نقطه شكست) در جفت كروموزوم خود را به صورت تصادفي انتخاب كنيم. هر كرومووزم را به دو پاره تقسيم مي‌كنيم و در ادامه كمي جاي هر پاره از هر كروموزوم را با ديگري عوض مي‌كنيم. مانند شكل زير

بدين ترتيب دو كرومزوم جديد توليد مي‌شود (دو جواب جديد). راه ديگري نيز براي انجام عمل تركيب وجود دارد و آن انتخاب چند نقطه شكست است. مثلاً به شكل زير براي 2 نقطه شكست توجه كنيد

در هر حال ما بايد يك روش را انتخاب كنيم و در طول پروژه عمل تركيب خود را مبتني بر آن روش انجام دهيم. بعد از انجام عمليات انتخاب و تركيب، نوبت به عمل جهش ژن‌ها مي‌رسد. عمل جهش بايد با احتمال پايين رخ دهد. يعنيدر اكثر مواقع نبايد داراي جهش باشيم، اما احتمال آن نيز  نبايد صفر باشد. بنابراين اگر كرومزوم به دست آمده از عملگر تركيب دچار جهش شود، بايد يكي از بيت‌هاي آن كه متناظر با ژن‌هاي آن هستند، به صورت تصادفي انتخاب شود و سپس مقدار آن تغيير كند. اگر بخواهيم اين موضوع را به صورت كلاسيك نشان دهيم، به صورت زير خواهد بود:

اكنون يك مرحله را انجام داديم و يك كرومزوم جديد (جواب جديد) براي مسئله ايجاد كرديم. در ادامه دو مرتبه دو كرومزوم از جمعيت اوليه انتخاب مي‌كنيم و همه اعمال گفته‌شده را روي آن انجام مي دهيم تا كرومزوم ديگري ايجاد شود و اين‌كار را به قدري تكرار مي‌كنيم تا به تعداد كرومزوم‌هاي جمعيت اوليه، كرومزوم جديد داشته باشيم و اين مجموعه كرومزوم جديد در حقيقت نسل جديد ما خواهند بود و ما اين‌كار را به قدري ادامه مي‌دهيم تا نسل‌هاي بهتر و بهتري را ايجاد كنيم و هنگامي جواب نهايي به دست ميآيد كه تابع ارزشي ما، مقدار مطلوب ما را به ازاي مقدار مورد نظر ما از كروموزوم ها برگرداند.

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

فریلنسر هستم و مهارت انجام پروژه ای را دارم!

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

نحوه سفارش پروژه در سایت کافه پروژه :

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