اولین اشارات به موضوع الگوریتم ژنتیک در اوایل دهه ۶۰ است زمانی که Lawrence J.Fogel مقاله ی مهم “on the organization of intellect” را منتشر کرد. که جرقه اولین تلاش ها را در محاسبات تکاملی ایجاد کرد. اوایل دهه ۷۰ با ارایه اولین کار ابتدایی که توسط Ingo Rechenber , John heavy Holland ارایه شد شاهد هجوم بیشتری به این حوزه هستیم. محاسبات تکاملی در دنیای خارج از برنامه نویس ها محبوبیتی بدست نیاورد تا زمانی که کتاب Richard Dawkins با عنوان “The Blind watchmaker” در سال ۱۹۸۶ انتشار یافت. که این کتاب همراه با نرم افزار کوچکی بود که جریانی به ظاهر ناپایان از طرح های بدن که “Bio-Morphs” نامیده می شود را ایجاد میکرد که اینکار بر اساس انتخاب انسانی بود. دهه ۸۰  زمانی است که ظهور کامپیوتر های شخصی این اماکن را فراهم کرد که افراد بدون نیاز به حمایت های دولتی بتوانتد اصول تکاملی را در پروژه ای خود به کار ببندند و اینگونه آنها این مبحث را رواج داداند.

مزایا و معایب

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

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

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

و از آنجایی که زمان اجرا پیش رونده هست جواب های میانه میتوانند در هر زمان خاصی برداشت شوند.

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

و در نهایت حل کنند های تکاملی درجه بالایی از تعادل با کاربر را در “اصول” اجازه می دهند. که این یک قابلیت منحصر به فرد است. مخصوصا در توجه به طیف گسترده ی کاربرد های احتمالی.

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

روند

در این بخش به اختصار روند اجرای حل کننده تکاملی شرح داده شده است:

---

مدل شامل دو متغیر است به این معنی که دو مقدار مجاز هستند که تغییر کنند. در محاسبات تکاملی ما متغیر ها را ژن می نامیم.هنگامی که ما ژن A را تغییر میدهیم حالت مدل تغییر میکند و ممکن است حالت آن بهتر یا بدتر شود. (بسته به چیزی که ما به دنبال آن هستیم) بنابراین وقتی ژن A تغییر میکند مطلوبیت کل مدل بالا یا پایین می رود ( بدتر یا بهتر می شود). اما برای هر مقدار A ما می تواینم ژن B را نیز تغییر دهیم و باعث بدتر شدن یا بهتر شدن نتیجه شویم البته با ترکیب با نتیجه ژن A,B . هر ترکیبی از A,B باعث نتیجه مشخصی در مطلوبیت خواهد داشت و این مطلوبیت بصورت ارتفاع فضای مطلوبیت بیان شده است. پیدا کردن بالاترین مقدار برای مطلوبیت در فضای مطلوبیت بر عهده حل کننده است. البته بسیاری از مسائل با بیشتر از دو ژن (متغیر) تعریف می شوند که در این صورت نمی توان از لغت “Landscape” استفاده کرد.

برای مثال یک مدل با ۱۲ متغیر (ژن) دارای ۱۲ جهت برای مقدار مطلوبیت است که بصورت ۱۳ بعدی باید تعریف شود. بجای اینکه مانند مثال قبل با ۲ ژن و ۲ بعد برای مقدار مطلوبیت با ۳ بعد تعریف شود. کاملا مشهورد است که امکان تصویر سازی از یک فضای ۱۳ بعدی امکان پذیر نیست ولی در مثال ها و تصاویر ما از یک مدل با ۲ بعد استفاده میکنیم که فرایند مسله را تعریف کنیم. پس در هنگام استفاده از لغت “Landscape” مفهوم ما ممکن است چیزی بسیار پیچیده تر از معنی آن باشد. وقتی که حل کننده شروع به کار میکند هیچ تعریف واقعی از فضای مطلوبیت ندارد. پس در  قدم اول حل کننده باید جمعیت اولیه لنداسکیپ را یا “فضای مدل” را ایجاد کند این کار با استفاده از انتخاب رندم افراد یا “ژنوم ها” انجام میشود. ژنوم چیزی نیست بجز مقدار مشخص  برای هرکدام و همه ژن ها. در مثال بالا برای مثال ژنوم می تواند بصورت {A=0.2, B=0.5} باشد. سپس حل کننده مطلوبیت را برای هرکدوم و همه آن ژنوم های رندوم ارزیابی می کند و پخش شدگی زیر را نشان مید هد.

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

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

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

به منظور اجرای این روند، حل کننده تکاملی نیازمند ۵ قسمت بهم پیوسته است که میتوان آن را آناتومی حل کننده نامید :

1. تابع مطلوبیت Fitness Function
2. مکانیسم انتخاب selection algorithm
3. الگوریتم ادغام coalescence Algorithm
4. ضریب جهش Mutation Factory

تابع مطلوبیت

در تکامل بیولوژیکی کیفیت شناخت شده به عنوان “مطلوبیت” در واقع مانع انحراف (خطا) است. تعریف دقیق مطلوب بودن کمی سخت است. مطلوب بودن به معنی قویتر بودن یا سریعتر بودن و یا خشن تر بودن نیست. علت اینکه سگ های پرنده وجود ندارد این نیست که تکامل هنوز به مرحله ایجاد آن نرسیده است. این به علت آن است که نوع زندگی سگ با پرواز کردن ناسازگاری است. و افزودن ویژگی پرواز کردن نه تنها باعث افزایش مطلوبیت سگ نخواهد شد بلکه از آن خواهد کاست. مطلوبیت نتیجه میلیون ها نیروی درگیر باهم است. مطوبیت تکاملی، سازش نهایی است. یک فرد مناسب “مطلوب” در “حد متوسط” است، که می تواند فرزندان بیشتری را از افراد بدون مطلوبیت ایجاد کنند بنابراین ما میتوانیم بگوییم که مطلوبیت برابر با تعداد فرزندان ژنتیکی است. برای یک معیار بهتر تا اینجا تعداد نوه ها را در نظر میگیرم و یک معیار بهتر دیگر تا اینجا فرآوانی ژن ها را در داخل استخر ژن در نظر میگیرم که افراد مورد نظر را ایجاد میکند. حداقل در محاسبات تکاملی مطلوبیت یک مفهوم ساده و راحت است. ” مطلوبیت هر چیزی است که ما بخواهیم” ما سعی داریم مسئله خاصی را حل کنیم و ما میدانیم که مطولبیت برای آن چیست. برای مثال ما میخواهیم یک شکل را طوری قرار دهیم که حداقل مقدار اتلاف متریال  در تولید آن وجود داشته باشد. در این مثال حداقل سازی مقدار اتلاف ، مقدار مطلوبیت است. بار دیگر به فضای مطلوبیت نگاه کنیم و تصور کنیم که در آن ما میخواهیم یک مدل را داخل یک جعبه قرار داهیم که حداقل حجم را داشته باشد. جعبه در برگیرنده شکل، کوچکترین جعبه قائم الزاویه است که بطور کامل در برگیرنده هر شکل داده شده باشد. در تصویر زیر شکل سبز رنگ توسط ۲ مستطیل در برگرفته شده است. مستطیل B مساحت کمتری نسبت به A دارد که از این رو ” مطلوبتر ” است.

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

خب پس ژن A  محور چرخش x است و ژن B نیز محور چرخش حول محور y را نشان می دهد. نیاز به چرخش بیشتر از ۳۶۰ درجه نیست پس هر دو ژن یک محدوده دامنه دارند. ( در حقیقت چون ما در مورد جعبه قائم الزاویه حرف میزنیم حتی زاویه ۰-۹۰ درجه نیز کافی است.)

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

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

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

این مهم است که اشاره شود مساحت این حوضه مشخص کننده کیفیت قله نیست. در حقیقت ممکن است یک راه حل ضعیف دارای حوضه جذب بزگی باشد در حالی که یک راه حل خوب مساحت حوضه کوچکی داشته باشد. مشکلات مانند این معمولا برای حل شدن بسیار دشوار هستند. مانند زمانی که راه حل ها تمایل پیدا میکنن که در مقدار بهینگی محلی گیر کنند. اما بعدا به عملگرهای Problematic Fitness خواهیم پرداخت.

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

اولین چیزی که باید دقت شود این است که فضای مدل متناوبی است. یعنی خود را در هر ۹۰ درجه در هر دو جهت نمایش میدهد. همچنین این فضا هنگامی که برای حداقل حجم جستجو مکنیم برعکس است. بنابراین قله های نارنجی رنگ نشانگر بدترین راه حل ها برای این مسئله هستند. توجه کنید که ۱۶ قله در کل این محدود وجود دارند که آنها گرد شده اند. وقتی ما در تصویر به قسمت تحتانی فضا مطلوبیت نگاه میکنیم ما تصویر متفاوتی را مشاهد میکنیم.

مشهود است که مقادیر پایین تر در این فضای مطلوبیت (حداقل حجم جعبه) هم در تعداد و هم تفاوت نوع کمتر هستند. ما تنها ۸ راه حل بهینه بدست می آوریم که همه آنها کاملا تیز هستند. که نشانگر حالتی تا حدی شکننده است. تمامی راه حل ها دارای کیفیت یکسانی هستند و هیچ بهینگی محلی وجود ندارد. ما میتوانیم این فضای مطلوبیت را به گراف دو بعدی تعمیم دهیم.

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

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

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

حتی با وجود اینکه از بهینگی محلی هیچ سخنی نیست. همچنین هیچ پیشرفتی نیز بر روی فلات ( صفحه صاف) وجود نداد.

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

در فضای مانند این پدر و مادر ممکن است هر دو بسیار شبیه هم باشند و بسیار هم مطلوب باشند. فضای مطلوبیت مانند این از جهت یابی تبعیت نمی کند.

مکانیزم انتخاب

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

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

مکانیزم های انتخاب در گالاپاگوس ( الگوریتم های اصلی)

Selection Mechanisms

مکانیزم انتخاب isotropic selection انتخاب هم گرایی

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

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

مکانیزم انتخاب Exclusive selection

 که در آن فقط N% بالای جمعیت موفق به جفت یابی می شوند.

افراد موفق که در N%  بالا بوده اند احتمالا موفق به چندین بار نسل آوری خواهند شد.

مکانیزم انتخاب Biased Selection

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

الگوریتم های جفت سازی

Coupling Algorithms

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

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

بنابراین فاصله بین دو ژنوم یک مقدار N  بعدی است که در آن N برابر تعداد ژن ها است.

در واقع غیر ممکن است که بتوان یک ابر نقطه ای N  بعدی را بر روی یک صفحه ۲ بعدی نشان داد بنابراین نقشه ژنوم یک تقریب نامناسب است.

همچنین محورهای این گراف نیز هیچ معنی ندارد. تنها اطلاعاتی که این گراف انتقال میدهد این است که کدام ژنوم کم یا زیاد نزدیک هم هستند ( شبیه هم هستند ) و کدام ژنوم کمتر یا بیشتر متفاوت تر است ( دورتر از هم است).

تصور کنید که شما فردی هستید که برای جفت گیری انتخاب می شوید. جمعیت به خوبی توزیع شده است و شما در جایی نزدیک به متوسط هستید ( مطلوبیت متوسط دارید)

در نقشه نقطه قرمز شما هستید 🙂 کدام ژنوم ها به شما جذب شده اند؟ البته میتوانید جستجوی خود را به همسایه های نزدیک خود محدود کنید. این بدین معنی است که شما به افرادی که بسیار به شما شبیه هستند جفت می شوید و فرزندان شما هم بسیار شبیه خواهند شد.

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

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

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

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

به نظر میرسد بهترین گزینه این است که بین تولید نسل از هم نسل ها و تولید نسل از غیر هم نسل ها تعادل ایجاد کرد. برای انتخاب افرادی که زیاد نزدیک هستند و نه زیاد دور. در گلاپاگوس شما میتوانید فاکتور inbreeding را مشخص کنید. بین -۱۰۰% تا +۱۰۰% به ترتیب کل outbreeding  در مقابل کل inbreeding که به شما امکان هدایت این آفست را میدهند

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

الگوریتم ادغام

Coalescence algorithm

 زمانی که یک همسر انتخاب می شود نیاز است که فرزندان تولید شوند. فرآینده بیولوژیکی دوباره ترکیب سازی ژن ها بسیار پیچیده است و خود موضوع تکامل است. ( برای مثال تقسیم میتوز)

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

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

در نظر بگیرد ما دو ژنوم داریم که هرکدام از ۴ ژن تشکیل شده اند هیچ مشخصات بر اساس جنسیت و نوع در حل کننده وجود ندارد. پس ترکیب M,D (مادر و پدر) بصورت بالقوه یک فرآیند متقارن است. مکانیزمی که تا حدودی شبیه به دوباره ترکیب ژن ها بصورت بیولوژیک است ادغام متقاطع است.

الگوریتم ادغام جفت سازی متقاطع

 Crossover coalescence

در جفت سازی متقاطع فرزند تعدادی ژن بصورت رندوم از مادر و باقی را از پدر به ارث میبرد. در این مکانیزم مقدار ژن ثابت است.

الگوریتم ادغام ادغام مخلوط

 blend coalescence

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

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

جهش

Mutation

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

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

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

وقتی ما جهش را به ژنوم می دهیم باید تغییر در گراف را ببینیم چون هر ژنوم مشخص یک گراف مشخص نیز دارد.

تغییرات بالا (تصویر بالا) جهش نقطه “Point Mutation” را نشان میدهد که در آن مقدار یک ژن تغییر میکند. در حال حاظر این تنها حالت جهش موجود در گالاپاگوس است. همچنین ما میتوانیم مقادیر دو ژن مجاور هم را عوض کنیم که در این حالت ما جهش وارونه خواهیم داشت.

جهش وارونه “inversion mutation”

جهش وارونه فقط زمانی مفید هست که ژن های متوالی دارای کی رابطه مشخص باشند. این جهش تمایل دارد یک ژنوم را بشدت ویرایش کند و بنابراین در بیشتر موارد نیز به شدت مطولبیت را نیز ویرایش میکند ( تغییر میدهد)

اغلب این یک عمل زیان آور است.

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

منابع:

۱. https://ieatbugsforbreakfast.wordpress.com/

استفاده از مطالب با ذکر منبع بلامانع است.
هسته فناور انرژی تبریز

دسته بندی متن:

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