تکامل یعنی اینکه انسانها از نسل میمون ها هستند. این ابتدائی ترین و خام ترین برداشتی است که ممکن است شخصی از تکامل داشته باشد و متاسفانه تنها اطلاعی که بسیاری از
افراد از تکامل دارند همین است، که یک آدمی به نام داروین پیدا شده است و ثابت کرده است انسانها قبلاً میمون بوده اند.

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

فلاسفه ای مثل تالس تکامل را بصورت فرضیه های طبیعی برای توضیح علمی حیات مطرح کردند اما بررسی علمی و دقیق تکامل در دوران اخیر شکل گرفته است. پیشاز داروین چند دانشمند دیگر مانند لامارک شخصی که زیست شناسی را به معنی امروزی اش بنا نهاد نیز در مورد تکامل مطالعاتی داشتند و نظریاتی را نیز ارائه داده بودند. تفاوت اصلی میان نظریه

تکامل لامارک با نظریه داروین در این بود که داروین تکامل را امری گروهی و مربوط به گونه های جانوری میداند ولی لامارک آنرا امری انفرادی میدانسته است، اما با این وجود، این داروین است که پدر تکامل خوانده میشود زیرا درک مدرن ما از تکامل به تئوری گزینش طبیعی بر میگردد که چارلز داروین و آلفرد راسل والاس آنرا در سال ١٨۵٨ در کتاب “مشاء انواع یا ریشه مطرح کردند. (Origin of species) ” گونه ها

تعریف گزینش طبیعی:

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

تعریف تکامل:

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

بر اساس تئوری تکامل موجودات جدید تر همگی اجداد مشترکی دارند، و برای نشان دادن این شراکت استفاده میشود، بعنوان مثال (Phylogenetic tree) در اجداد، معمولا از درختواره های فیلوژنتیکی ارتباط حیوانات با گیاهان و سایر موجودات را نشان میدهد.

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

تکامل هنوز تنها یک نظریه است:

این اعتراض از رایج ترین اعتراضاتی است که عوام نسبت به تکامل مطرح میکنند. این افراد نمیدانند که در دنیای علم هیچ مفهومی بالاتر از تئوری نمیرود و تئوری بالاترین مرحله ایست که یک نظر علمی
میتواند داشته باشد. بسیاری از سایر مفاهیم علمی همچون جاذبه نیوتون، سرعت نور، بیگ بنگ و غیره تماما تئوری هستند، اساساً هرچیز که بر مشاهده مبتنی باشد نمیتواند از مرحله تئوری بالاتر

است، مفاهیمی وجود دارند که Science رود. در برخی از شاخه های علم منظور از علم همان گفته (Theorem) مشتق شده از اصول قطعی ریاضیات هستند به آن دسته از مفاهیم قضیه یا تئورم میشود مثلا روابط فیثاغورس و تالسدو نمونه از قضایا هستند، سایر چیز ها نمیتوانند چیزی جز تئوری باشند. پیرامون این مسئله در نوشتاری با فرنام علم چیست؟ توضیحات بیشتری آورده شده است.

نتیجه آنکه تئوری بودن تکامل نمیتواند از ارزشو درستی آن بکاهد و کسانی که این ایراد را وارد میکنند مفهوم کلمه “تئوری” را در فلسفه علم درک نمیکنند. از این گذشته هر تئوری برای توضیح یک واقعیت
شکل میگیرد، مثلاً تئوری جاذبه نیوتون برای توضیح واقعیت جاذبه شکل گرفته است، دقیقاً همین ارتباط میان تئوری تکامل و خود تکامل بعنوان یک واقعیت وجود دارد.

 

تکامل تصادفی است و احتمال آن پایین است، پس محال است:

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

تغییراتی که بر اساس تحولات تصادفی ژنتیکی (جهش ژنتیکی) انجام میگیرند.

تغییراتی که قدرت و احتمال نجات یافتن و تکثیر موجود را بالا میبرند، که عدم تحقق این تغییرات موجب حذف آن موجود توسط گزینشطبیعی میشود.
کسانی که این اعتراض را بیان میکنند درکی بسیار ضعیف از تئوری احتمالات دارند، اینکه احتمال وقوع یک اتفاق پایین باشد هرگز و هرگز به این معنی نیست که آن اتفاق محال است، لذا این اعتراض نیز از
پایه غلط است. در این مورد در نوشتاری با فرنام “مگر میشود همه چیز بطور تصادفی بوجود آمده باشد؟” توضیحات کافی داده شده است.

AI به دو مکتب فکري تقسيم مي شود:
AI قراردادي (Coventional AI) : توسط رسمي سازي (formalism)، تحليل آماري، تعاريف و اثبات مشخص مي گردد (مثل يادگيري ماشين و سيستم هاي خبره).
هوش محاسباتي: با ويژگي هاي غيررسمي، غيراحتمالي و اغلب با رويکردهاي آزمون و خطا شناخته مي شود. هوش محاسباتي به سه بخش اصلي تقسيم مي گردد:
شبکه هاي عصبي
سيستم هاي فازي
محاسبه تکاملي

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

پيشروي، رشد يا توسعه تکراري
مبني بر جمعيت

جستجوي تصادفي هدايت شده
پردازش موازي
ملهم از زيست شناسي

محاسبات تکاملي اغلب شامل الگوريتم هاي بهينه سازي فرااکتشافي است مانند:
الگوريتم هاي تکاملي (شامل الگوريتم ژنتيک، برنامه نويسي تکاملي، استراتژي تکاملي، برنامه نويسي ژنتيک و سيستم هاي طبقه بندي کننده يادگير (
هوش گروهي (شامل بهينه سازي گروه مورچگان و بهينه سازي گروه ذرات)
و تا حد کمتري شامل:
خودسازماندهي (نقشه هاي خودسازمانده ، گاز عصبي در حال رشد، يادگيري رقابتي)
تکامل تفاضلي (ديفرانسيلي)
زندگي مصنوعي
الگوريتم هاي فرهنگ
سيستم هاي ايمني مصنوعي
مدل تکاملي قابل يادگيري

هوش گروهي (SI) يک تکنيک هوش مصنوعي مبني بر بررسي رفتار جمعي در سيستم هاي غير متمرکز و خودسازمانده است . اين واژه توسط Wang و Beni در سال ۱۹۸۹ و در مبحث سيستم هاي رباتي سلولي مطرح شد.
SI معمولا از جمعيتي از عاملهاي ساده تشکيل شده که به طور محلي با يکديگر و محيطشان تعامل دارند. با اينکه ساختار کنترلي متمرکزي براي تحميل رفتار عاملها وجود ندارد، تعاملات محلي بين عاملها اغلب منجر به بروز يک رفتار سراسري مي گردد. مثال:گروه مورچگان، ازدحام پرندگان و دسته حيوانات.

سيستم هاي نمونه:

ACO:
يک الگوريتم بهينه سازي فرااکتشافي است که مي تواند راه حلهاي تقريبي را براي مسايل بهينه سازي ترکيبي مشکل بيابد. در ACO، مورچه هاي مصنوعي با حرکت روي گراف مساله راه حلها را مي سازند و با تقليد از مورچه هاي حقيقي، روي گراف فرومون مصنوعي به جا مي گذارند، به نحوي که مورچه هاي مصنوعي آينده راه حلهاي بهتري بيابند. ACO مي تواند با موفقيت بر روي مسايل بهينه سازي زيادي اجرا شود.

الگوریتم کلونی مورچه ها:
انسان هميشه براي الهام گرفتن به جهان زنده پيرامون خود نگريسته است. يکي از بهترين طرح هاي شناخته شده، طرح پرواز انسان است که ابتدا لئورناردو داوينچي(۱۵۱۹-۱۴۵۲) طرحي از يک ماشين پرنده را بر اساس ساختمان بدن خفاش رسم نمود. چهار صد سال بعد کلمان آدر ماشين پرنده اي ساخت که داراي موتور بود و بجاي بال از ملخ استفاده مي کرد.
هم اکنون کار روي توسعه سيستم هاي هوشمند با الهام از طبيعت از زمينه هاي خيلي پرطرفدار هوش مصنوعي است. الگوريتمهاي ژنتيک که با استفاده از ايده تکاملي دارويني و انتخاب طبيعي مطرح شده، روش بسيار خوبي براي يافتن مسائل بهينه سازيست. ايده تکاملي دارويني بيانگر اين مطلب است که هر نسل نسبت به نسل قبل داراي تکامل است و آنچه در طبيعت رخ مي دهد حاصل ميليون ها سال تکامل نسل به نسل موجوداتي مثل مورچه است.

الگوريتم کلوني مورچه براي اولين بار توسط دوريگو (Dorigo) و همکارانش به عنوان يک راه حل چند عامله (Multi Agent) براي مسائل مشکل بهينه سازي مثل فروشنده دوره گرد (TSP :Traveling Sales Person) ارائه شد.

عامل هوشند(Intelligent Agent) موجودي است که از طريق حسگر ها قادر به درک پيرامون خود بوده و از طريق تاثير گذارنده ها مي تواند روي محيط تاثير بگذارد.

الگوريتم کلوني مورچه الهام گرفته شده از مطالعات و مشاهدات روي کلوني مورچه هاست. اين مطالعات نشان داده که مورچه ها حشراتي اجتماعي هستند که در کلوني ها زندگي مي کنند و رفتار آنها بيشتر در جهت بقاء کلوني است تا درجهت بقاء يک جزء از آن. يکي از مهمترين و جالبترين رفتار مورچه ها، رفتار آنها براي يافتن غذا است و بويژه چگونگي پيدا کردن کوتاهترين مسير ميان منابع غذايي و آشيانه. اين نوع رفتار مورچه ها داراي نوعي هوشمندي توده اي است که اخيرا مورد توجه دانشمندان قرار گرفته است.بايد تفاوت هوشمندي توده اي(کلوني) و هوشمندي اجتماعي را روشن کنيم.

در هوشمندي اجتماعي عناصر ميزاني از هوشمندي را دارا هستند. بعنوان مثال در فرآيند ساخت ساختمان توسط انسان، زماني که به يک کارگر گفته ميشود تا يک توده آجر را جابجا کند، آنقدر هوشمند هست تا بداند براي اينکار بايد از فرغون استفاده کند نه مثلا بيل!!! نکته ديگر تفاوت سطح هوشمندي افراد اين جامعه است. مثلا هوشمندي لازم براي فرد معمار با يک کارگر ساده متفاوت است.

در هوشمندي توده اي عناصر رفتاري تصادفي دارند و بين آن ها هيچ نوع ارتباط مستقيمي وجود ندارد و آنها تنها بصورت غير مستقيم و با استفاده از نشانه ها با يکديگر در تماس هستند. مثالي در اين مورد رفتار موريانه ها در لانه سازيست.
جهت علاقه مند شدن شما به اين رفتار موريانه ها وتفاوت هوشمندي توده اي و اجتماعي توضيحاتي را ارائه مي دهم :
فرآيند ساخت لانه توسط موريانه ها مورد توجه دانشمندي فرانسوي به نام گرس قرار گرفت. موريانه ها براي ساخت لانه سه فعاليت مشخص از خود بروز مي دهند. در ابتدا صدها موريانه به صورت تصادفي به اين طرف و آن طرف حرکت مي کنند. هر موريانه به محض رسيدن به فضايي که کمي بالاتر از سطح زمين قرار دارد شروع به ترشح بزاق مي کنند و خاک را به بزاق خود آغشته مي کنند. به اين ترتيب گلوله هاي کوچک خاکي با بزاق خود درست مي کنند. عليرغم خصلت کاملا تصادفي اين رفتار، نتيجه تا حدي منظم است. در پايان اين مرحله در منطقه اي محدود تپه هاي بسيار کوچک مينياتوري از اين گلوله هاي خاکي آغشته به بزاق شکل مي گيرد. پس از اين، همه تپه هاي مينياتوري باعث مي شوند تا موريانه ها رفتار ديگري از خود بروز دهند. در واقع اين تپه ها به صورت نوعي نشانه براي موريانه ها عمل مي کنند. هر موريانه به محض رسيدن به اين تپه ها با انرژي بسيار بالايي شروع به توليد گلوله هاي خاکي با بزاق خود مي کند. اين کار باعث تبديل شدن تپه هاي مينياتوري به نوعي ستون مي شود. اين رفتار ادامه مي يابد تا زماني که ارتفاع هر ستون به حد معيني برسد. در اين صورت موريانه ها رفتار سومي از خود نشان مي دهند. اگر در نزديکي ستون فعلي ستون ديگيري نباشد بلافاصله آن ستون را رها مي کنند در غير اين صورت يعني در حالتي که در نزديکي اين ستون تعداد قابل ملاحظه اي ستون ديگر باشد، موريانه ها شروع به وصل کردن ستونها و ساختن لانه مي کنند.
تفاوتهاي هوشمندي اجتماعي انسان با هوشمندي توده اي موريانه را در همين رفتار ساخت لانه مي توان مشاهده کرد. کارگران ساختماني کاملا بر اساس يک طرح از پيش تعيين شده عمل مي کنند، در حالي که رفتار اوليه موريانه ها کاملا تصادفي است. علاوه بر اين ارتياط مابين کارگران سختماني مستقيم و از طريق کلمات و … است ولي بين موريانه ها هيچ نوع ارتباط مستقيمي وجود ندارد و آنها تنها بصورت غير مستقيم و از طريق نشانه ها با يکديگر در تماس اند. گرس نام اين رفتار را Stigmergie گذاشت، به معني رفتاري که هماهنگي مابين موجودات را تنها از طريق تغييرات ايجاد شده در محيط ممکن مي سازد.
بهينه سازي مسائل بروش کلوني مورچه(ACO) :
همانطور که مي دانيم مسئله يافتن کوتاهترين مسير، يک مسئله بهينه سازيست که گاه حل آن بسيار دشوار است و گاه نيز بسيار زمانبر. بعنوان مثال مسئله فروشنده دوره گرد(TSP). در اين مسئله فروشنده دوره گرد بايد از يک شهر شروع کرده، به شهرهاي ديگر برود و سپس به شهر مبدا بازگردد بطوريکه از هر شهر فقط يکبار عبور کند و کوتاهترين مسير را نيز طي کرده باشد. اگر تعداد اين شهرها n باشد در حالت کلي اين مسئله از مرتبه (n-1)! است که براي فقط ۲۱ شهر زمان واقعا زيادي مي برد:
روز۱۰۱۳*۷/۱ = S1016*433/2 = ms10*1018*433/2 = !20
با انجام يک الگوريتم برنامه سازي پويا براي اين مسئله ، زمان از مرتبه نمايي بدست مي آيد که آن هم مناسب نيست. البته الگوريتم هاي ديگري نيز ارائه شده ولي هيچ کدام کارايي مناسبي ندارند. ACO الگوريتم کامل و مناسبي براي حل مسئله TSP است.
مورچه ها چگونه مي توانند کوتاهترين مسير را پيدا کنند؟

مورچه ها هنگام راه رفتن از خود ردي از ماده شيميايي فرومون(Pheromone) بجاي مي گذارند البته اين ماده بزودي تبخير مي شد ولي در کوتاه مدت بعنوان رد مورچه بر سطح زمين باقي مي ماند. يک رفتار پايه اي ساده در مورچه هاي وجود دارد :

آنها هنگام انتخاب بين دو مسير بصورت احتمالاتي( Statistical) مسيري را انتخاب مي کنند که فرومون بيشتري داشته باشد يا بعبارت ديگر مورچه هاي بيشتري قبلا از آن عبور کرده باشند. حال دقت کنيد که همين يک تمهيد ساده چگونه منجر به پيدا کردن کوتاهترين مسير خواهد شد :
همانطور که در شکل ۱-۱ مي بينيم مورچه هاي روي مسير AB در حرکت اند (در دو جهت مخالف) اگر در مسير مورچه ها مانعي قرار ديهم(شکل ۲-۱) مورچه ها دو راه براي انتخاب کردن دارند. اولين مورچه ازA مي آيد و بهC مي رسد، در مسير هيچ فروموني نمي بيند بنابر اين براي مسير چپ و راست احتمال يکسان مي دهد و بطور تصادفي و احتمالاتي مسير CED را انتخاب مي کند. اولين مورچه اي که مورچه اول را دنبال مي کند زودتر از مورچه اولي که از مسير CFD رفته به مقصد مي رسد. مورچه ها در حال برگشت و به مرور زمان يک اثر بيشتر فرومون را روي CED حس مي کنند و آنرا بطور احتمالي و تصادفي ( نه حتما و قطعا) انتخاب مي کنند. در نهايت مسير CED بعنوان مسير کوتاهتر برگزيده مي شود. در حقيقت چون طول مسير CED کوتاهتر است زمان رفت و برگشت از آن هم کمتر مي شود و در نتيجه مورچه هاي بيشتري نسبت به مسير ديگر آنرا طي خواهند کرد چون فرومون بيشتري در آن وجود دارد.
نکه بسيار با اهميت اين است که هر چند احتمال انتخاب مسير پر فرومون ت توسط مورچه ها بيشتر است ولي اين کماکان احتمال است و قطعيت نيست. يعني اگر مسير CED پرفرومون تر از CFD باشد به هيچ عنوان نمي شود نتيجه گرفت که همه مورچه ها از مسيرCED عبور خواهند کرد بلکه تنها مي توان گفت که مثلا ۹۰% مورچه ها از مسير کوتاهتر عبور خواهند کرد. اگر فرض کنيم که بجاي اين احتمال قطعيت وجود مي داشت، يعني هر مورچه فقط و فقط مسير پرفرومون تر را انتخاب ميکرد آنگاه اساسا اين روش ممکن نبود به جواب برسد. اگر تصادفا اولين مورچه مسيرCFD(مسير دورتر) را انتخاب مي کرد و ردي از فرومون بر جاي مي گذاشت آنگاه همه مورچه ها بدنبال او حرکت مي کردند و هيچ وقت کوتاهترين مسير يافته نمي شد. بنابراين تصادف و احتمال نقش عمده اي در ACO بر عهده دارند.
نکته ديگر مسئله تبخير شدن فرومون بر جاي گذاشته شده است. برفرض اگر مانع در مسير AB برداشته شود و فرومون تبخير نشود مورچه ها همان مسير قبلي را طي خواهند کرد. ولي در حقيقت اين طور نيست. تبخير شدن فرومون و احتمال به مورچه ها امکان پيدا کردن مسير کوتاهتر جديد را مي دهند.

۱-۱

۲-۱

۳-۱

۴-۱

مزيتهاي ACO :
همانطور که گقته شد «تبخير شدن فرومون» و «احتمال-تصادف» به مورچه ها امکان پيدا کردن کوتاهترين مسير را مي دهند. اين دو ويژگي باعث ايجاد انعطاف در حل هرگونه مسئله بهينه سازي مي شوند. مثلا در گراف شهرهاي مسئله فروشنده دوره گرد، اگر يکي از يالها (يا گره ها) حذف شود الگوريتم اين توانايي را دارد تا به سرعت مسير بهينه را با توجه به شرايط جديد پيدا کند. به اين ترتيب که اگر يال (يا گره اي) حذف شود ديگر لازم نيست که الگوريتم از ابتدا مسئله را حل کند بلکه از جايي که مسئله حل شده تا محل حذف يال (يا گره) هنوز بهترين مسير را داريم، از اين به بعد مورچه ها مي توانند پس از مدت کوتاهي مسير بهينه(کوتاهترين) را بيابند.
کاربردهاي ACO :
از کاربردهاي ACO مي توان به بهينه کردن هر مسئله اي که نياز به يافتن کوتاهترين مسير دارد ، اشاره نمود :
۱٫ مسير يابي داخل شهري و بين شهري
۲٫ مسير يابي بين پست هاي شبکه هاي توزيع برق ولتاژ بالا
۳٫ مسير يابي شبکه هاي کامپيوتري
مسير يابي شبکه هاي کامپيوتري با استفاده از ACO :
در ابتدا مقدمه اي از نحوه مسير يابي در شبکه هاي کامپيوتري را توضيح خواهيم داد :
اطلاعات بر روي شبکه بصورت بسته هاي اطلاعاتي کوچکي (Packet) منتقل مي شوند. هر يک از اين بسته ها بر روي شبکه در طي مسير از مبدا تا مقصد بايد از گره هاي زيادي که مسيرياب (Router) نام دارند عبور مي کنند. در داخل هر مسيرياب جدولي قرار دارد تا بهترين و کوتاهترين مسير بعدي تا مقصد از طريق آن مشخص مي شود، بنابر اين بسته هاي اطلاعاتي حين گذر از مسيرياب ها با توجه به محتويات اين جداول عبور داده مي شوند.
روشي بنام : Ant Colony Routering

ACR پيشنهاد شده که بر اساس ايده کلوني مورچه به بهينه سازي جداول مي پردازيد و در واقع به هر مسيري با توجه به بهينگي آن امتياز مي دهد. استفاده از ACR به اين منظور داراي برتري نسبت به ساير روش هاست که با طبيعت ديناميک شبکه سازگاري دارد، زيرا به عنوان مثال ممکن است مسيري پر ترافيک شود يا حتي مسير يابي (Router) از کار افتاده باشد و بدليل انعطاف پذيري که ACO در برابر اين تغييرات دارد همواره بهترين راه حل بعدي را در دسترس قرار مي دهد.

بهينه سازي گروه ذرات :

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

جستجوي پخشي احتمالي :

SDS يک جستجوي سراسري مبني بر عامل و تکنيک بهينه سازي است که براي مسايلي که تابع هدف مي تواند به چندين تابع جزئي مستقل تجزيه شود مناسب است. هر عامل يک فرضيه را نگهداري مي کند که به طور مکرر با يک تابع هدف جزئي که به طور تصادفي انتخاب مي شود ارزيابي مي شود که پارامترهاي آن با فرضيه فعلي عامل تعيين مي گردد. اطلاعات فرضيه ها از طريق ارتباط بين عاملي در جمعيت پخش مي گردد. برخلاف ارتباط stigmergetic مورد استفاده در ACO، در SDS عاملها فرضيه ها را از طريق استراتژي ارتباطي يک به يک، مبادله مي کنند. SDS هم الگوريتم جستجو و هم Optimisation قدرتمند و موثري است که به خوبي به بيان رياضي توصيف مي گردد.
کاربرد تکنيکهاي مبني بر هوش گروهي : کنترل خودروهاي بدون سرنشين، نقشه برداري نجومي.

EP:

اولين بار در ۱۹۶۰ توسط Lawrence J.Fogel براي تکامل شبيه سازي شده به عنوان يک فرايند يادگيري با هدف توليد هوش مصنوعي به کار رفت. Fogel ماشينهاي حالت متناهي را به عنوان پيشگويي کننده به کار برد و آنها را تکامل داد.
امروزه EP برخلاف ساير گويشها، گويشي از محاسبه تکاملي با ساختار (نمايش) غيرثابت است و به سختي از استراتژي هاي تکاملي شناخته مي شود.
عملگر تغيير اصلي در آن جهش است، اعضاي يک جمعيت به جاي اعضاي يک species به عنوان بخشي از species خاص درنظر گرفته مي شوند، پس هر والد با استفاده از يک انتخاب بازمانده ( ) يک فرزند توليد مي کند.

برنامه نويسي ژنتيک(GP) :

يک متدولوژي خودکار الهام گرفته شده از تکامل زيستي است براي يافتن برنامه هاي کامپيوتري که الگوريتمي تکاملي را براي بهينه کردن جمعيتي از برنامه هاي کامپيوتري برحسب چشم انداز شايستگي تعيين شده توسط توانايي برنامه براي انجام وظيفه محاسباتي داده شده به کار مي رود.
در ابتدا دستورات برنامه و مقادير داده در قالب ساختارهاي درختي سازماندهي مي شدند بنابراين از زبانهايي استفاده مي شد که به طور طبيعي داراي چنين ساختارهايي بودند مانند Lisp، اما امروزه برنامه¬هاي کامپيوتري در GP مي توانند با زبانهاي متنوعي نوشته شوند.

الگوريتم ژنتيک(Genetic Algorithm – GA) :

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

همانطور که در شکل بالا مشاهده می کنید شمای کلی از نحوهٔ عملکرد این الگوریتم را به شما نشان می‌دهد. در ادامه به توضيح بيشتري در باره الگوريتم ژنتيك خواهيم پرداخت .

روش جستجوی تکاملی
روش های جستجوی ناآگاهانه ، اگاهانه و متاهیوریستیک برای حل مسائل هوش مصنوعی بسیار کارآمد می‌باشند. همچنین می دانیم که در مورد مسائل بهینه سازی اغلب روش های آگاهانه و ناآگاهانه جوابگوی نیاز ما نخواهند بود. چرا که بیشتر مسائل بهینه سازی در رده مسائل NP قرار دارند. بنابراین نیاز به روش جستجوی دیگری داریم که بتواند در فضای حالت مسائل NP به طرف جواب بهینه سراسری حرکت کند. بدین منظور روش های جستجوی متاهیوریستیک را مطرح می کنیم,این روش های جستجو می‌توانند به سمت بهینگی های سراسری مسئله حرکت کنند. در کنار روش های جستجوی متاهیوریستیکی ، روش های جستجوی دیگری نیز وجود دارند که به روش های تکاملی معروفند. در ادامه با این نوع الگوریتم بیشتر آشنا می شویم.(لازم به ذکر است که در نگاه کاربردی به الگوریتم های ژنتیکی, اولین قدم در فهم آن, تفهیم الگوریتم های تکامل و تفاوت آن با دیگر الگوریتم های مشابه است.)

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

الگوريتم تكاملي

الگوريتم هاي تكاملي كه الهام گرفته از مكانيزم تكامل طبيعي و بنا شده بر اصل انتخاب طبيعي داروين مي باشد، در مسائل بهينه سازي و جستجو هاي تطبيقي مورد استفاده قرار مي گيرند. پارامتر هاي تعريف شده دراين الگوريتم ها شامل مواردي مانند : جمعيت، نحوه نمايش اعضاي جمعيت، تابع ارزيابي، تابع انتخاب والدين، عملگر هاي تكاملي بازتركيبي، جهش و تابع انتخاب بازماندگان مي باشد [۱]. جمعيت، متشكل از اعضاي جمعيت بوده كه به هر يك از اين اعضاء، كروموزوم گفته مي شود. هر كروموزوم بازنمايي از يك راه حل مسئله در غالب ژن ها مي باشد. به بياني هر كروموزوم از تعدادي ژن كه كد كننده راه حل مسئله بوده تشكيل شده كه مقدار ژن ها بر پايه نوع الگوريتم تكاملي مورد استفاده مي تواند باينري، حقيقي و يا حتي از نوع گراف باشد. هر كروموزوم موجود در جمعيت بر پايه تابع ارزيابي مسئله، ارزيابي مي شود.

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

جمعيت اوليه به صورت تصادفي انتخاب شده و با اعمال پارامتر هاي مناسب الگوريتم تكاملي بر روي جمعيت م ي توان به را هحل بهينه مسئله دست يافت . بر مبناي اصل شايسته سالاري داروين، همگرايي كروموزوم ها به راه حل بهينه بوده كه اين امر در بردارنده مفهوم تكامل مي باشد. قابل توجه است كه چون الگوريتم هاي تكاملي از نوع جستج و هاي خلاقانه در فضاي جستجو بوده و تمامي فضاي جستجو مورد ارزيابي و كاوش قر ار نمي گيرد، تظميني براي يافتن بهينه سراسري وجود ندارد .

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

بازتركيبي از نوع رياضي ساده با ضريب ۰,۵

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

انواع مختلف الگوریتم های تکاملی
انواع مختلف الگوریتم های تکاملی که تا بحال مطرح شده اند، به شرح زیر می‌باشد :
Genetic Algorithm
Genetic Programming
Evolutionary Strategies
Evolutionary Programming
Differential Evolution
Cultural Evolution
Co-evolution
الگوریتمهای تکاملی به سه دسته اصلی تقسیم می شوند:
الگوریتم ژنتیک
استراتژیهای تکاملی
برنامه ریزی تکاملی

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

الگوريتم ژنتيک که به‌عنوان يکي از روشهاي تصادفي بهينه يابي شناخته شده, توسط جان هالند در سال ۱۹۶۷ ابداع شده‌است. بعدها اين روش با تلاشهاي گلدبرگ ۱۹۸۹, مکان خويش را يافته و امروزه نيز بواسطه تواناييهاي خويش , جاي مناسبي در ميان ديگر روشها دارد. روال بهينه يابي در الگوريتم ژنتيک براساس يک روند تصادفي- هدايت شده استوار مي‌باشد. اين روش , بر مبناي نظريه تکامل تدريجي و ايده‌هاي بنيادين داروين پايه گذاري شده‌است.در اين روش , ابتدا براي تعدادي ثابت که جمعيت ناميده مي‌شود مجموعه‌اي از پارامترهاي هدف بصورت اتفاقي توليد مي‌شود , پس از اجراي برنامه شبيه ساز عددي را که معرف انحراف معيار و يا برازش آن مجموعه از اطلاعات است را به آن عضو از جمعيت مذکور نسبت مي‌دهيم. اين عمل را براي تک تک اعضاي ايجاد شده تکرار مي‌کنيم , سپس با فراخواني عملگرهاي الگوريتم ژنتيک از جمله لقاح , جهش و انتخاب نسل بعد را شکل مي‌دهيم و اين روال تا ارضاي معيار همگرايي ادامه داده خواهد شد.

در تعريفي ديگر الگوریتم ژنتیک یکی از الگوریتمهای تکاملی است که اگرچه به شکلهای مختلفی ارائه شده است اما پایه تمام این شکلها چهار فرایند است که در ادامه به آنها پرداخته می شود. الگوریتم ژنتیک یک بهینه سازی غیر جبری است که مناسب برای توابعی است که بهینه سازی آنها با روشهای جبری کاری طاقت فرسا است. الگوریتم ژنتیک برای مسایلNP-Hard بسیار مناسب می باشد. همچنین این الگوریتمها قادر به حل مسایلی هستند که در فضای حلشان ناپیوستگی وجود دارد. یکی دیگر از مزایای این روش، توانایی اعمال آن به مسایلی است که دارای متغیرهای زیاد می باشند.

از طرف دیگر، الگوریتم ژنتیک ضعفهایی نیز دارد. این روش غیر جبری است بنابراین پاسخ دقیق مساله را نمی یابد و حتی ممکن است برای یک مساله مشخص با هر بار بکارگیری پاسخی متفاوت ارائه دهد. اگرچه تمامی این پاسخها می توانند پاسخهایی باشند که دقت مورد نیاز را برآورده کنند. الگوریتمهای ژنتیک قابل اعمال به تمام مسایل بهینه سازی هستند اما در مسایلی این روشها نسبت به سایر روشها بسیار کندتر عمل می کنند. بنابراین ژنتیک، روشی عمومی برای تمام جستجوها نمی باشد.
با این وجود این الگوریتم (و سایر الگوریتمهای تکاملی) فضای پاسخ را به صورت موازی و خوشه به خوشه و نه به صورت عضو به عضو می کاوند به همین دلیل امکان رخ دادن اپتیمم های محلی از بین می رود. این روشها نیازی به اطلاعات مربوط به مشتقات تابع هدف ندارند. تنها شکل اصلی تابع مورد نیاز می باشد.
چهار فرایند اصلی در الگوریتم ژنتیک عبارتند از :
ایجاد جمعیت کروموزومها (تبدیل مجموعه ای از پاسخهای ممکن به شکل کروموزوم و ژن
انتخاب (جفت یابی) (Selection)
ترکیب (CrossOver)
جهش (Mutation)
در شکل چگونگی مراحل الگوریتم ژنتیک، نشان داده شده است.

قبل از ادامه بحث لازم است قسمتی بسیار مهم از الگوریتم ژنتیک، تابع تطابق يا تابع هدف (Fitness function – Objective function) را معرفی کنیم. این تابع شاید قلب الگوریتم ژنتیک باشد. انتخاب اعضاء بهتر یا به عبارتی زنده ماندن ژنهای بهتر با این تابع کنترل می شود.

الگوریتمهای ژنتیک اگرچه در شکلهای مختلفی وجود دارند اما حداقل شامل چهار قسمت زیر می باشند:
• جمعیتی از جوابهای ممکن که به کروموزوم و ژن تبدیل شده اند.
• عملگر انتخاب
• عملگر ترکیب
• عملگر جهش

طراحی یک الگوریتم ژنتیک برای مساله ای خاص دارای سه مرحله است:
• طراحی شیوه کدگذاری
• طراحی تابع تطابق

 

 

 

 

 

 

 

 

 

 

• طراحی عملگرهای ژنتیک
در ادامه هر کدام از این عناصر مورد بررسی قرار می گیرد.

 

 

 

 

 

عملگرهاي يک الگوريتم ژنتيک
در هر مسئله قبل از آنکه بتوان الگوريتم ژنتيک را براي يافتن يک پاسخ به کار برد به دو عنصر نياز است: اول روشي براي ارائه يک جواب به شکلي که الگوريتم ژنتيک بتواند روي آن عمل کند لازم است. به شکل سنتي يک جواب به صورت يک رشته از بيتها، اعداد يا نويسه ها.نمايش داده مي‌شود.دوم روشي لازم است که بتواند کيفيت هر جواب پيشنهاد شده را با استفاده از توابع تناسب محاسبه نمايد. مثلاً اگر مسئله هر مقدار وزن ممکن را براي يک کوله پشتي مناسب بداند بدون اينکه کوله پشتي پاره شود، (مسئله کوله پشتي را ببينيد) يک روش براي ارائه پاسخ مي‌تواند به شکل رشته اي از بيتهاي ۰ و۱ در نظر گرفته شود, که ۱ يا ۰ بودن نشانه اضافه شدن يا نشدن وزن به کوله پشتي است.تناسب پاسخ، با تعيين وزن کل براي جواب پيشنهاد شده اندازه گيري مي‌شود.

فرضيه با جمعيتي کاملاً تصادفي منحصر بفرد آغاز مي‌شود و در نسلها ادامه مي‌يابد. در هر نسل گنجايش تمام جمعيت ارزيابي مي‌شود، چندين فرد منحصر در فرايندي تصادفي از نسل جاري انتخاب مي‌شوند (بر اساس شايستگيها) و براي شکل دادن نسل جديد، اصلاح مي‌شوند (کسر يا دوباره ترکيب مي‌شوند) و در تکرار بعدي الگوريتم به نسل جاري تبديل مي‌شود.

 

کدگذاری و نحوه نمایش
نحوه نمایش جواب مسئله و ژن ها در موفقیت الگوریتم و نحوه پیاده سازی الگوریتم ژنتیک تاثیر بسیار مهمی دارد. در بیشتر مسائل نیز روش های مختلفی برای نشان دادن جواب مساله می‌توان طراحی کرد. به عنوان مثال در مسئله ۸ وزیر به جای استفاده از بردار( آرایه یک بعدی ) ۸ عنصری می‌توان از یک ماتریس ۸ * ۸ استفاده کرد که در آن هر وزیر می‌تواند در هریک از ۶۴ خانه صفحه شطرنج قرار گیرد. هنگام استفاده از این روش نمایش ، در یک خانه ممکن است بیش از یک وزیر قرار گیرد بنابراین هنگام پیاده سازی الگوریتم باید از بروز چنین مسئله‌ای جلوگیری کنیم.

جمعیت

مفهوم جمعیت در الگوریتم ژنتیک شبیه به چیزی است که در زندگی طبیعی وجود دارد. برای مساله گزاره هایی وجود دارند که می توانند به عنوان پاسخ، چه درست، چه غلط در نظرگرفته شوند. به این گزاره ها پاسخهای ممکن یا شدنی می گوییم. مثلا اگر مساله یافتن ماکزیمم یک تابع در مجموعه اعداد صحیح باشد، تمام اعداد صحیح می توانند به عنوان پاسخ شدنی مساله در نظر گرفته شوند.

در الگوریتم ژنتیک به عنوان اولین مرحله لازم است مجموعه ای از جوابهای شدنی به عنوان جمعیت اولیه ایجاد شود. اعضای این مجموعه معمولا به صورت تصادفی انتخاب می شوند اما در الگوریتمهای بهینه، از قیدهایی استفاده می شود تا جمعیت پراکندگی بیش از حد نداشته باشد. تعداد اعضای جمعیت به نوع مساله بستگی دارد. در واقع تعداد اعضا، پارامتری است که با تغییر آن می توان دقت جوابها و سرعت همگرایی جستجو را بهبود بخشید. در برخی مسایل یک جمعیت ۸ عضوی کاملا مناسب است در حالی که در برخی یک جمعیت ۱۰۰ عضوی نیز کافی نیست. بر اساس تجربه بهتر است تعداد اعضای جمعیت عددی بین ۱۰ تا ۱۶۰ باشد.

 

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

 

انتخاب

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

يك عضو با تطابق پايين اگرچه در نسل خودش عضو مناسبي نميباشد اما ممكن است
شامل ژنهايي خوب باشد و اگر شانس انتخاب شدنش ۰ باشد، اين ژنهاي خوب نميتوانند به

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

روشهاي متداول انتخاب عبارتند از:

• انتخاب چرخ رولت
• انتخاب ترتيبي
• انتخاب بولتزمن
• انتخاب حالت پايدار
• نخبه سالاري
• انتخاب رقابتي