Astaraki

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


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

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

2- داستان كوتاه
در ادامه سعي مي‌كنم كاركرد الگوريتم ژنتيك را با داستاني خيالي برايتان تشريح كنم. در سال‌هاي بسيار دور در يك غار تاريك و نم‌دار كه راهي به فضاي بيرون نداشت، موجوداتي به نام سوتك زندگي مي‌كردند. سوتك‌هاي داستان ما زندگي بسيار راحت و آرامي داشتند. آن‌ها فقط داراي حس لامسه و شنوايي بودند. بدين‌ترتيب آن‌ها در گوشه و كنار غار حركت مي‌كردند و سعي مي‌كردند در قسمت‌هاي نم‌دار غار از جلبك‌ها تغذيه كنند و البته آن‌ها جلبك‌ها را بسيار دوست داشتند و هر گاه بيكار مي‌شدند، به سوت زدن سوتك‌هاي ديگر گوش مي‌كردند.

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

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

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

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

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

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

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

بدين ترتيب تركيب ژن‌ها اين امكان را به وجود ميآورد تا ارگانيزم‌هاي جديدتري به دست آوريم كه تركيبي از مزاياي هر دو والد باشد.

3- الگوريتم ژنتيك در دنياي كامپيوتر

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

1011011010000101011111110

‌يا

1264196352478923455548216

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

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

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

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



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




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



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

4- نكات مهم در الگوريتم هاي ژنتيك
1- شرايط جمعيت اوليه مي‌تواند در سرعت رسيدن به جواب بسيار تأثيرگذار باشد. يعني اگر جمعيت اوليه مناسب‌تر باشد، بسيار سريع‌تر به جواب مي‌رسيم. بنابراين گاهي در بعضي از مسئله‌ها به جاي آن كه جمعيت اوليه به صورت تصادفي ايجاد شود، از اعمال شرايط خاص مسئله به جمعيت اوليه نيز استفاده مي‌شود.

2- با توجه به وجود پارامترهاي تصادفي در الگوريتم مسئله حتي در صورت استفاده از جمعيت اوليه يكسان ممكن است در اجراهاي مختلف الزاماً جواب‌هاي يكسان به دست نيايد و البته در صورت استفاده از جمعيت اوليه متناوت اين پديده ملموس‌تر خواهد بود.

3- تابع ارزش در اين‌گونه از الگوريتم‌ها از اهميت بسزايي برخوردار است؛ چرا كه معمولاً در اكثر مسائل در اثر تركيب، حالت‌هايي رخ مي‌دهد كه منطبق بر شرايط مسئله نيست و حتي فاقد معني و مفهوم است. بنابراين تابع ارزش بايد به گونه‌اي طراحي شود كه به ازاي اين حالات مقادير بسيار كمي برگرداند و از طرفي بايد براي نزديك شدن به هدف بسيار خوب تخمين بزند.

4- يكي از پديده‌هاي جالب اين است كه ممكن است در نسل‌هاي مياني نمونه‌هايي بروز كنند كه از نظر تابع ارزش و خوب بودن بسيار مناسب باشند. يك روش اين است كه اينگونه موارد را شناسايي كنيم و در نسل بعدي نيز از آن‌ها استفاده كنيم. به اين تكنيك نخبه‌گرايي مي‌گويند كه عملاً تأثير بسزايي در رسيدن به جواب مسئله دارد.

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

__________________

تعرفه ارزان تبلیغات در اولین و بزرگترین سایت هوش مصنوعی ایران !
با بیش از صد و چهل هزار کاربر!