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

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

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

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

   البته آنچه در بالا ذكر شد به تنهايی توصيف كننده آنچه واقعا در قالب تكامل در طبيعت اتفاق می‌افتد نيست. بهينه‌سازی و تكامل تدريجی به خودی خود نمی‌تواند طبيعت را در دسترسی به بهترين نمونه‌ها ياری دهد. اجازه دهيد تا اين مساله را با يك مثال شرح دهيم.

   پس از اختراع اتومبيل به تدريج و در طی سال‌ها اتومبيل‌های بهتری با سرعت‌های بالاتر و قابليت‌های بيشتر نسبت به نمونه‌های اوليه توليد شدند. طبيعيست كه اين نمونه‌های متاخر حاصل تلاش مهندسان طراح جهت بهينه‌سازی طراحی‌های قبلی بوده اند. اما دقت كنيد كه بهينه‌سازی يك اتومبيل تنها يك "اتومبيل بهتر" را نتيجه می‌دهد.

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

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

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

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

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

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

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

   به شكل زير توجه كنيد. اين منحنی دارای دو نقطه ماكزيمم می‌باشد. كه يكی از آنها تنها ماكزيمم محلی ست. حال اگر از روش‌های بهينه‌سازی رياضی استفاده كنيم مجبوريم تا در يك بازه بسيار كوچك مقدار ماكزيمم تابع را بيابيم. مثلا از نقطه 1 شروع كنيم و تابع را ماكزيمم كنيم. بديهيست اگر از نقطه 1 شروع كنيم تنها به مقدار ماكزيمم محلی دست خواهيم يافت و الگوريتم ما پس از آن متوقف خواهد شد. اما در روش‌های هوشمند خاصه الگوريتم ژنتيك بدليل خصلت تصادفی آنها حتی اگر هم از نقطه 1 شروع كنيم باز ممكن است در ميان راه نقطه A به صورت تصادفی انتخاب شود كه در اين صورت ما شانس دست‌يابی به نقطه بهينه كلی (Global Optima) را خواهيم داشت.

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

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

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

 شكل 2: عملگرهای ژنتيك (Genetic Operators)

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

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

   اين دو كار در واقع مراحل آماده سازی جهت اجرای الگوريتم ژنتيك است. پس از انجام اين دو كار يك جمعيت ابتدايی (نسل اوليه) از راه حل‌های ممكن داريم. برای شروع الگوريتم اين نسل اوليه بايد توليد مثل كند. توليد مثل در سه مرحله انجام می‌شود. مرحله اول انتخاب يا Selection است. در اين مرحله بهترين كروموزوم‌ها (بر اساس تابع بهينگی) برای توليد مثل انتخاب می‌شوند. ذكر اين نكته ضروريست كه حتی در اينجا هم اندكی تصادف را بايد دخيل كنيم. يعنی مثلا بهترين كروموزم‌ها را به احتمال 90% انتخاب كنيم. اين احتمالاتی انتخاب كردن بهترين‌ها اندكی شانس بقا به كروموزم‌های ضعيف‌تر می‌دهد. اما شايد بپرسيد چرا نبايد با اطمينان بهترين‌ها را انتخاب كرد و همه ضعيف‌ترها را در هر نسل از بين برد؟

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

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

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

   پس ازين كار در واقع نسل جديد كروموزم‌ها ايجاد شده است كه بر طبق آنچه تا كنون گفتيم در مجموع بهينه‌تر از نسل قبليست. تنها نكته باقی مانده اينست كه نسل قبلی چه می‌شود. آيا پس از ايجاد نسل جديد كروموزم‌ها تمامی نسل قبلی از بين می‌رود؟ يا اينكه هر كرموزوم پس از طول عمر مشخصی می‌ميرد؟ يا فقط تعدادی از بهترين كروموزوم‌های نسل قبلی در نسل جديد باقی می‌مانند و ....

   در حالت كلی از هريك از روش‌های فوق می‌توان درباره نسل پيشين كروموزم‌ها بهره گرفت، گرچه به نظر می‌رسد طول عمر داشتن كروموزم‌ها از لحاظ طبيعی قابليت تعمق بيشتری دارد.

مزايا و معايب الگوريتم ژنتيك

   تا كنون به كليت و نيز چگونگی پياده سازی الگوريتم ژنتيك اشاره كرديم. اينك می‌خواهيم يك جمع بندی از مزايا و معايب اين الگوريتم داشته باشيم. اولين خصوصيت مثبت اين الگوريتم دستيابی به نقطه بهينه كلی (Global Optima) به جای نقطه بهينه محلی ست. يعنی هميشه در حد بسيار مطلوبی می‌توان به پاسخ اين الگوريتم اعتماد كرد و اينكه پاسخی كه می‌يابد به احتمال زياد بهترين پاسخ ممكن است.

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

   هر چند خود الگوريتم ژنتيك برای حل مسائل بهينه‌سازی گسسته به كار می‌رود اما روش‌های مشابهی همچون استراتژی تكاملی و يا الگوريتم آب دادن فولاد(ُSimulated Annealing) وجود دارند كه عينا در مورد مسائل پيوسته می‌توانند به كار روند.

   نحوه تعريف و پياده‌سازی اين الگوريتم نيز به گونه‌ايست كه آن را بسادگی جهت اجرا بصورت موازی يا بر روی Multiprocessor ها مناسب می‌سازد.

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