وبینار رایگان سه ماه مهم تا کنکور ارشد مهندسی کامپیوتر و IT
مشاهده وبینار
کنکور کامپیوتر

الگوریتم ژنتیک از 0 تا 100، آموزش الگوریتم ژنتیک در متلب

این صفحه الگوریتم ژنتیک (Genetic Algorithm) را از 0 تا 100 بررسی کرده، همین طور به پیاده سازی و آموزش الگوریتم ژنتیک در متلب (MATLAB) پرداخته است.

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

این تصویر دبیانگر مفهوم الگوریتم ژنتیک است.

مانند تکامل، بسیاری از فرآیندهای الگوریتم ژنتیک تصادفی هستند، اما این تکنیک بهینه‌سازی به فرد اجازه می‌دهد تا سطح تصادفی‌سازی و سطح کنترل را تعیین کند.

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

تاریخچه الگوریتم های ژنتیک

محاسبات تکاملی در دهه ۱۹۶۰ توسط اینگو رِشِنبرگ معرفی شد. جان هالند در سال ۱۹۷۵ اولین کتاب در مورد الگوریتم های ژنتیک را با عنوان انطباق در سیستم های طبیعی و مصنوعی نوشت. در سال ۱۹۹۲ جان کوزا از الگوریتم ژنتیک برای تکامل برنامه ها برای انجام وظایف خاص استفاده کرد. او روش خود را برنامه ریزی ژنتیکی نامید.

در این تصویر نقل‌قولی از چارلس داروین است.

اصطلاحات طبیعت و معادل کامپیوتری آن ها

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

مولفه ها، ساختار و اصطلاحات

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

  • یک تابع برازندگی (Fitness Function) برای بهینه سازی
  • جمعیتی از کروموزوم ها (Chromosomes)
  • انتخاب (Selection) کروموزوم هایی که تکثیر خواهند شد
  • ترکیب (Crossover) برای تولید نسل (Generation) بعدی کروموزوم ها
  • جهش (Mutation) تصادفی کروموزوم ها در نسل جدید

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

این تصویر بیانگر مفهموم تابع برازندگی است.

واژه کروموزوم به یک مقدار یا مقادیر عددی اشاره دارد که نشان دهنده یک راه حل کاندیدا برای مسئله ای است که الگوریتم ژنتیک سعی در حل آن دارد. هر راه حل کاندیدا به عنوان آرایه ای از مقادیر پارامتر کدگذاری می شود، فرآیندی که در سایر الگوریتم های بهینه سازی نیز یافت می شود. اگر یک مسئله دارای ابعاد Npar باشد، معمولاً هر کروموزوم به عنوان یک آرایه با Npar عضو مانند chromosome = [p1,p2,…,pNpar] کدگذاری می‌شود که در آن هر pi مقدار خاصی از پارامتر i امین است. این به استفاده کننده الگوریتم ژنتیک بستگی دارد که چگونه فضای نمونه راه حل های کاندیدا را به کروموزوم ترجمه کند.

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

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

این تصویر حاوی فرمول  احتمال انتخاب کروموزوم برای تولید مثل است.

توجه داشته باشید که عملگر انتخاب کروموزوم ها را با جایگزینی انتخاب می کند، بنابراین یک کروموزوم می تواند بیش از یک بار انتخاب شود. عملگر ترکیب شبیه ترکیب بیولوژیکی و ترکیب مجدد کروموزوم ها در میوز سلولی است. این عملگر دنباله ای از دو کروموزوم انتخابی را برای ایجاد دو فرزند تعویض می کند. به عنوان مثال، اگر کروموزوم های والد [11010111001000] و [01011101010010]، پس از بیت چهارم ترکیب شوند، [01010111001000] و [11011101010010] فرزندان آنها خواهند بود. عملگر جهش به طور تصادفی تک تک بیت ها را در کروموزوم های جدید ورق می زند (تبدیل 0 به 1 و بالعکس). به طور معمول جهش با احتمال بسیار کم مانند 0.001 اتفاق می افتد. برخی از الگوریتم‌ها عملگر جهش را قبل از عملگرهای انتخاب و ترکیب پیاده‌سازی می‌کنند.

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

با این حال، برخی از الگوریتم‌ها به اعضای بسیار مناسب نسل اول اجازه می‌دهند تا در نسل دوم زنده بمانند. اکنون نسل دوم با عملکرد تابع برازندگی آزمایش می شود و چرخه تکرار می شود. ثبت کروموزوم با بالاترین برازندگی (همراه با ارزش برازندگی آن) از هر نسل یا کروموزوم بهترین تاکنون(best-so-far) یک روش معمول است. الگوریتم های ژنتیک تا زمانی تکرار می شوند که ارزش برازندگی کروموزوم بهترین تاکنون تثبیت شود و برای چندین نسل تغییر نکند. این بدان معناست که الگوریتم به یک راه حل (های) همگرا شده است. کل فرآیند تکرارها را اجرا(run) می گویند. در پایان هر مرحله معمولاً حداقل یک کروموزوم وجود دارد که راه حل بسیار مناسبی برای مشکل اصلی است.

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

یک الگوریتم ژنتیک ساده

با توجه به یک مسئله به وضوح تعریف شده که باید حل شود و یک نمایش رشته بیتی برای راه حل های کاندیدا، یک الگوریتم ژنتیک ساده به صورت زیر عمل می کند:

  1. با جمعیتی از کروموزوم‌های nبیتی که به‌طور تصادفی تولید می‌شوند (راه‌حل‌های نامزد برای یک مسئله) شروع کنید.
  2. تابع برازندگی f(x) هر کروموزوم xدر جمعیت را محاسبه کنید.
  3. مراحل زیر را تکرار کنید تا n فرزند ایجاد شود:
    1. یک جفت کروموزوم والد را از جمعیت فعلی انتخاب کنید، که احتمال انتخاب تابعی از برازندگی است. انتخاب با جایگزینی انجام می شود، به این معنی که همان کروموزوم را می توان بیش از یک بار برای تبدیل شدن به والد انتخاب کرد.
    2. با احتمال p("احتمال ترکیب" یا "نرخ ترکیب")، جفت را در یک نقطه به طور تصادفی انتخاب شده (انتخاب شده با احتمال یکسان) ترکیب کنید تا دو فرزند تشکیل شود. اگر تلاقی صورت نگرفت، دو فرزند تشکیل دهید که کپی دقیقی از والدین مربوطه خود هستند. (توجه داشته باشید که در اینجا نرخ ترکیب به عنوان احتمال ترکیب والدین در یک نقطه تعریف می‌شود. همچنین نسخه‌های ترکیب چند نقطه‌ای از الگوریتم ژنتیک وجود دارد که در آن نرخ ترکیب برای والدین عدد نقاطی است که در آن یک تلاقی اتفاق می افتد.)
    3. دو فرزند را در هر مکان با احتمال pm (احتمال جهش یا نرخ جهش) جهش دهید و کروموزوم های حاصل را در جمعیت جدید قرار دهید. اگر n فرد باشد، یک عضو جدید جمعیت را می توان به طور تصادفی کنار گذاشت.
  4. جمعیت فعلی را با جمعیت جدید جایگزین کنید.
  5. به مرحله 2 بروید.

 

Simple_Genetic_Algorithm() {

        Initialize the Population;

        Calculate Fitness Function;

        While(Fitness Value != Optimal Value) {

              Selection;

              Crossover;

              Mutation;

              Calculate Fitness Function;

        }

 }

این تصویر چیستی الگوریتم ژنتیک را نشان داده شده است.

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

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

به عنوان یک مثال دقیق تر از یک الگوریتم ژنتیک ساده، فرض کنید L (طول رشته) ۸ است،f(x)  برابر است با تعداد یک ها در رشته بیتی x (یک تابع برازندگی بسیار ساده، که در اینجا فقط برای مقاصد توضیحی استفاده می شود)است ، n (اندازه جمعیت) ۴ است،  pc= ۰.۷، و آن  pm= ۰.۰۰۱ است. (مانند تابع برازندگی، این مقادیر L و n برای سادگی انتخاب شدند. مقادیر معمولی بیشتر L و n در محدوده ۵۰-۱۰۰۰ هستند. مقادیر داده شده برای pc و pm نسبتاً معمولی هستند.)

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

FitnessChromosome stringChromosome label
2 00000110 A
6 11101110 B
1 00100000 C
3 00110100 D

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

یک روش ساده برای اجرای انتخاب متناسب با تابع برازندگی، نمونه برداری از چرخ رولت است (گلدبرگ ۱۹۸۹)، که از نظر مفهومی معادل دادن یک تکه از چرخ رولت دایره ای به هر فرد است که مساحتی برابر با برازندگی فرد دارد. چرخ رولت میچرخد، توپ روی یک تکه گوه ای شکل قرار می گیرد و فرد مربوطه انتخاب می شود. در مثال n = ۴ بالا، چرخ رولت چهار بار می چرخد. دو چرخش اول ممکن است کروموزوم های B و D را به عنوان والدین انتخاب کنند و دو چرخش دوم ممکن است کروموزوم های B و C را به عنوان والدین انتخاب کنند. (این واقعیت که ممکن است A انتخاب نشود فقط شانس قرعه کشی است. اگر چرخ رولت بارها بچرخد، میانگین نتایج به مقادیر مورد انتظار نزدیکتر خواهد بود.)

این تصویر یک آزمایش الگوریتم ژنتیک را نشان می‌دهد.

هنگامی که یک جفت از والدین انتخاب میشوند، با احتمال pc  از ترکیب می کنند تا دو فرزند تشکیل دهند. اگر آنها ترکیب نشوند، فرزندان نسخه‌های دقیقی از هر یک از والدین هستند. فرض کنید، در مثال بالا، والدین B و D پس از اولین موقعیت بیت با یکدیگر ترکیب شوند تا فرزندان E = 10110100 و F = 01101110 را تشکیل دهند، و والدین B و C با هم ترکیب نمی شوند، در عوض فرزندانی را تشکیل می دهند که کپی دقیقی از B و C هستند. سپس، هر فرزند در معرض جهش در هر مکان با احتمال pm است. به عنوان مثال، فرض کنید فرزندان E در جایگاه ششم جهش یافته اند تا E' = 10110000، فرزندان F و C به هیچ وجه جهش نداشته باشند و فرزندان B در جایگاه اول جهش یافته و B' = 01101110 را تشکیل دهند. جمعیت جدید به شرح زیر خواهد بود:

FitnessChromosome StringChromosome Label
3 1011000 E’
5 01101110 F
1 00100000 C
5 01101110 B’

توجه داشته باشید که در جمعیت جدید، اگرچه بهترین رشته (رشته با برازندگی ۶) از بین رفت، اما میانگین برازندگی از ۱۲.۴ به ۱۴.۴ افزایش یافت. تکرار این رویه در نهایت منجر به یک رشته می شود که همه بیت هایش ۱ باشد.

چه زمانی باید از الگوریتم ژنتیک استفاده کرد؟

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

اگر یک فضا بزرگ نباشد، میتوان آن را به طور کامل جستجو کرد و می توان مطمئن بود که بهترین راه حل ممکن پیدا شده است، در حالی که یک الگوریتم ژنتیک ممکن است به جای بهترین راه حل جهانی، روی یک بهینه محلی همگرا شود. اگر فضا صاف (smooth) یا تک وجهی (unimodal) باشد، یک الگوریتم شیب صعود مانند تپه نوردی با شیب تند، بسیار کارآمدتر از الگوریتم ژنتیک در بهره برداری از صافی فضا خواهد بود. اگر فضا به خوبی درک شده باشد (مثلاً مانند فضای مسئله معروف فروشنده مسافرتی(traveling salesman))، روش‌های جستجو با استفاده از اکتشافات دامنه خاص اغلب می‌توانند به گونه‌ای طراحی شوند که از هر روش همه منظوره مانند الگوریتم ژنتیک بهتر عمل کنند. اگر عملکرد تابع برازندگی نویزی باشد (به عنوان مثال، اگر شامل اندازه گیری های مستعد خطا از یک فرآیند واقعی مانند سیستم بینایی یک ربات باشد)، یک روش جستجوی یک راه حل در یک زمان(one−candidate−solution−at−a−time)، مانند تپه نوردی ساده ممکن است به طور غیر قابل جبرانی توسط نویز به بیراهه کشیده شود، اما الگوریتم های ژنتیک، از آنجایی که آنها با جمع آوری آمار برازندگی در طول نسل ها کار می کنند، تصور می شود که در حضور مقادیر کمی نویز عملکرد قوی دارند.

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

عملگرها و پارامترهای الگوریتم ژنتیک

  • رمزگذاری (Encoding) : رمزگذاری فرآیندی برای نمایش راه حل در قالب یک رشته است که اطلاعات لازم را منتقل می کند. همانطور که در یک کروموزوم، هر ژن یک ویژگی خاص از فرد را کنترل می کند، به طور مشابه، هر بیت در رشته نشان دهنده یک ویژگی راه حل است.
  • روش های رمزگذاری:

    • رمزگذاری دودویی (Binary Encoding) : رمزگذاری دودویی رایج ترین روش رمزگذاری است. کروموزوم ها رشته های 1 و 0 هستند و هر موقعیت در کروموزوم نشان دهنده ویژگی خاصی از مسئله است.
    • 10110010110011100101 Chromosome A
      11111110000000011111 Chromosome B
    • رمزگذاری جایگشت (Permutation Encoding) : برای مسائلی مانند مسئله فروشنده دوره گرد (TSP) مفید است. در فروشنده دوره گرد هر کروموزوم رشته ای از اعداد است که هر کدام نشان دهنده شهری است که باید بازدید کرد.
    • 8 9 7 4 6 2 3 5 1 Chromosome A
      9 4 1 3 2 7 6 5 8 Chromosome B
    • رمزگذاری ارزش (Value Encoding) : در مسائلی که از مقادیر پیچیده مانند اعداد واقعی استفاده می‌شود و کدگذاری دودویی کافی نیست استفاده می‌شود. برای برخی مشکلات خوب است، اما اغلب برای ایجاد برخی تکنیک های ترکیب و جهش خاص برای این کروموزوم ها ضروری است.
      2.454 2.321 0.454 5.323 1.235 Chromosome A
      (left) , (back) , (left) , (right) , (forward)  Chromosome B
  • تابع برازندگی : یک تابع برازندگی، بهینه بودن یک راه حل (کروموزوم) را کمی می کند، به طوری که آن راه حل خاص ممکن است در برابر همه راه حل های دیگر رتبه بندی شود. یک مقدار برازندگی به هر راه حل بسته به اینکه واقعاً چقدر به حل مسئله نزدیک است، اختصاص داده می شود. عملکرد تابع برازندگی ایده آل ارتباط نزدیکی با هدف دارد و به سرعت قابل محاسبه است. در TSP، تابعf(x) مجموع فواصل بین شهرها در راه حل است. هر چه مقدار کمتر باشد، راه حل مناسب تر است.
  • این تابع برازندگی را نشان می دهد.

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

    روش های ترکیب :

    • ترکیب تک نقطه ای : یک نقطه تصادفی روی هر کروموزوم (رشته) انتخاب می شود و ماده ژنتیکی در این نقطه مبادله می شود.
    • 00100110110 | 11011 Chromosome1
      11000011110 | 11011 Chromosome2
      11000011110 | 11011 Offspring1
      00100110110 | 11011 Offspring2
    • ترکیب دو نقطه ای : دو نقطه تصادفی روی هر کروموزوم (رشته) انتخاب می شود و ماده ژنتیکی در این نقاط رد و بدل می شود.
    • 110110| 00100 | 11011 Chromosome1
      011110| 11000 | 10101 Chromosome2
      011110| 00100 | 10101 Offspring1
      110110| 11000 | 11011 Offspring2
    • ترکیب یکنواخت : هر ژن (بیت) به طور تصادفی از یکی از ژن های مربوط به کروموزوم های والد انتخاب می شود. ترکیب یکنواخت فقط 1 فرزند تولید می کند.
    • 110110| 00100 | 11011 Chromosome1
      011110| 11000 | 10101 Chromosome2
      110110| 00000 | 10111 Offspring1
  • جهش : جهش فرآیندی است که طی آن یک رشته به طور عمدی تغییر می‌کند تا تنوع در مجموعه جمعیت حفظ شود. احتمال جهش تعیین می کند که هر چند وقت یکبار قسمت های کروموزوم جهش می یابند. برای کروموزوم هایی که از رمزگذاری دودویی استفاده می کنند، بیت های انتخاب شده به طور تصادفی معکوس می شوند.
  • 110110 0010 110110

    Offspring

    100110 00100 11010

    Mutated Offspring

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

    معکوس شدن بیت های برای جهش در این گیف به نمایش در آمده است.

حل مسئله 8 وزیر با الگوریتم ژنتیک

در سال ۱۸۴۸، یک شطرنج باز آلمانی به نام مکس بززل(Max Bezzel) مسئله 8 وزیر را ساخت که هدف آن قرار دادن ۸ وزیر در صفحه شطرنج به گونه ای است که هیچ دو وزیر نتوانند به یکدیگر حمله کنند. در سال ۱۸۵۰ فرانتس ناوک(Franz Nauck) اولین راه حل را برای این مسئله ارائه کرد و مسئله را به مسئله N-Queen برای N وزیر غیر مهاجم در صفحه شطرنج N x N تعمیم داد. پیچیدگی زمانی یک مسئله N وزیر، O(n!) است.

برای حل این مسئله ما هر راه حل را به صورت یک رشته ۸ بیتی در نظر می‌گیریم.

 این تصویر هشت وزیر را نشان می‌دهد.

تابع برازندگی : تعداد جفت وزیری است که همدیگر را تهدید نمی‌کنند. برای تصویر بالا این مقدار برابر است با ۲۴.

ترکیب : انتخاب بخشی از حالت از یک والدین و بقیه از دیگری.

تابع ابرزندگی در مسئله هشت وزیر در این تصویر نشان داده شده است.

جهش : تغییر قسمت کوچکی از یک حالت با احتمال کم.

به طور مثال برای گونه ای از این مسئله کروموزوم های زیر را داریم:

جهش در مسئله هشت وزیر در این تصویر نشان داده شده است.

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

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

 

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

#Constants, experiment parameters
NUM_QUEENS = 8
POPULATION_SIZE = 10
MIXING_NUMBER = 2
MUTATION_RATE = 0.05

def fitness_score(seq):
    score = 0
    
    for row in range(NUM_QUEENS):
        col = seq[row]
        
        for other_row in range(NUM_QUEENS):
            
            #queens cannot pair with itself
            if other_row == row:
                continue
            if seq[other_row] == col:
                continue
            if other_row + seq[other_row] == row + col:
                continue
            if other_row - seq[other_row] == row - col:
                continue
            #score++ if every pair of queens are non-attacking.
            score += 1
    
    #divide by 2 as pairs of queens are commutative
    return score/2
import random
from scipy import special as sc

def selection(population):
    parents = []
    
    for ind in population:
        #select parents with probability proportional to their fitness score
        if random.randrange(sc.comb(NUM_QUEENS, 2)*2) < fitness_score(ind):
            parents.append(ind)
            
    
    return parents
import itertools

def crossover(parents):
    
    #random indexes to to cross states with
    cross_points = random.sample(range(NUM_QUEENS), MIXING_NUMBER - 1)
    offsprings = []
    
    #all permutations of parents
    permutations = list(itertools.permutations(parents, MIXING_NUMBER))
    
    for perm in permutations:
        offspring = []
        
        #track starting index of sublist
        start_pt = 0
        
        for parent_idx, cross_point in enumerate(cross_points): #doesn't account for last parent
            
            #sublist of parent to be crossed
            parent_part = perm[parent_idx][start_pt:cross_point]
            offspring.append(parent_part)
            
            #update index pointer
            start_pt = cross_point
            
        #last parent
        last_parent = perm[-1]
        parent_part = last_parent[cross_point:]
        offspring.append(parent_part)
        
        #flatten the list since append works kinda differently
        offsprings.append(list(itertools.chain(*offspring)))
    
    return offsprings

def mutate(seq):
    for row in range(len(seq)):
        if random.random() < MUTATION_RATE:
            seq[row] = random.randrange(NUM_QUEENS)
    
    return seq

def print_found_goal(population, to_print=True):
    for ind in population:
        score = fitness_score(ind)
        if to_print:
            print(f'{ind}. Score: {score}')
        if score == sc.comb(NUM_QUEENS, 2):
            if to_print:
                print('Solution found')
            return True
    
    if to_print:
        print('Solution not found')
    return False

def evolution(population):
    #select individuals to become parents
    parents = selection(population)

    #recombination. Create new offsprings
    offsprings = crossover(parents)

    #mutation
    offsprings = list(map(mutate, offsprings))

    #introduce top-scoring individuals from previous generation and keep top fitness individuals
    new_gen = offsprings

    for ind in population:
        new_gen.append(ind)

    new_gen = sorted(new_gen, key=lambda ind: fitness_score(ind), reverse=True)[:POPULATION_SIZE]

    return new_gen

def generate_population():
    population = []

    for individual in range(POPULATION_SIZE):
        new = [random.randrange(NUM_QUEENS) for idx in range(NUM_QUEENS)]
        population.append(new)
    
    return population

#Running the experiment

generation = 0

#generate random population
population = generate_population()
    
while not print_found_goal(population):
    print(f'Generation: {generation}')
    print_found_goal(population)
    population = evolution(population)
    generation += 1

پیاده سازی الگوریتم ژنتیک در متلب

تابع ترکیب :

function children = crossover(parents)
    % Crossover Function
    children = zeros(2,8);
    p = randi([2, 7]);
    children(1,1:p) = parents(1,1:p);
    children(2,1:p) = parents(2,1:p);
    idx = p+1;
    for i = p+1:8
        if ismember(parents(2,i),children(1,1:p))==0
            children(1,idx) = parents(2,i);
            idx = idx + 1;
        end
    end
    for i = 1:p
        if ismember(children(2,i),children(1,1:p))==0
            children(1,idx) = children(2,i);
            idx = idx + 1;
        end
    end
    
    idx = p+1;
    for i = p+1:8
        if ismember(parents(1,i),children(2,1:p))==0
            children(2,idx) = parents(1,i);
            idx = idx + 1;
        end
    end
    for i = 1:p
        if ismember(children(1,i),children(2,1:p))==0
            children(2,idx) = children(1,i);
            idx = idx + 1;
        end
    end
    
end

تابع برازندگی :

function out = fitness(chromosome)
    % This function returns fitness which equals by the number of gaurds
    
    % Transform the input chromosome into the chess field 
    field = zeros(8,8);
    for i = 1:8
        field(chromosome(i),i) = 1;
    end
    
    % Counting number of gaurds
    temp = zeros(8,8);
    for i = 1:8
        temp(i,:) = field(:,8+1-i);
    end
    out = 0;
    for i = -7:7
        res1 = sum(diag(field,i));
        res2 = sum(diag(temp,i));
        if res1 > 1
            out = out + res1;
        end
        if res2 > 1
            out = out + res2;
        end
    end
    
end

تابع جهش :

function children = mutation(chroms)
    % Mutation Function
    for i = 1:2
        a = randi([1, 8]);
        b = randi([1, 8]);
        tmp = chroms(i,a);
        chroms(i,a) = chroms(i,b);
        chroms(i,b) = tmp;
    end
    children = chroms;
end

تابع انتخاب :

function selected = parent_selection(population,N,K)
    % This function returns the selected parents
    all_selected = population(randperm(8,N),:);
    fits = zeros(1,N);
    for i = 1:N
        fits(i) = fitness(all_selected(i,:));
    end
    [values idx] = sort(fits);
    selected = population(idx(1:K),:);
end

تابع انتخاب باقی مانده:

function selected = survival_selection(population, children)
    % This function returns the new population by replcing the worst ones
    fits = zeros(1,length(population));
    for i = 1:length(population)
        fits(i) = fitness(population(i,:));
    end
    [values idx] = sort(fits);
    population(idx(end-1),:) = children(1,:);
    population(idx(end),:)   = children(2,:);
    selected = population;
end

تابع نمایش:

function show(chrom)

    ground = [1 0 1 0 1 0 1 0
              0 1 0 1 0 1 0 1
              1 0 1 0 1 0 1 0
              0 1 0 1 0 1 0 1
              1 0 1 0 1 0 1 0
              0 1 0 1 0 1 0 1
              1 0 1 0 1 0 1 0
              0 1 0 1 0 1 0 1];

    items = zeros(8,8);
    for i = 1:8
        items(chrom(i),i) = 5;
    end
        
    board = ground+items;
    board(board>5) = 5;
    imagesc(board)
    axis equal
end

تابع اصلی(main) :

close all
clear
clc

% Population Size
pop_size = 100;

% Population Initialization
pop = zeros(pop_size,8);
for i = 1:pop_size
    pop(i,:) = randperm(8);
end

found = 0;
fits = zeros(100,1);
for iter = 1:1000
    
    if found == 1
        disp('Result is Found ...')
        show(result)
        result
        break
    end
    
    % Parent Selection
    parents = parent_selection(pop,5,2);
    
    % Crossover
    children = crossover(parents);
    
    % Mutation
    p = rand();
    if p <= 0.8
        children = mutation(children);
    end
    
    % Survival Selection
    pop = survival_selection(pop, children);
    
    % Finding The Best Solution
    for i = 1:length(pop)
        fits(i) = fitness(pop(i,:));
        if fits(i) == 0
            result = pop(i,:);
            found = 1;
        end
    end
end


آرایه در ساختمان داده چیست و چگونه در حافظه ذخیره می‌شود؟

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

چرا آرایه در برنامه نویسی اهمیت دارد؟

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

همچنین هر گونه سوالی در مورد کلاس‌های آنلاین کنکور کامپیوتر و یا تهیه فیلم‌ها و یا رزرو مشاوره تک جلسه‌ای تلفنی با استاد رضوی دارید می‌توانید به طرق زیر از تیم پشتیبانی بپرسید:

آی دی تلگرام تیم پشتیبانی:     konkurcomputer_admin@

تماس با پشتیبانی:   09378555200

امتیازدهی5 1 1 1 1 1 1 1 1 1 15.00 امتیاز (3 رای)
بارگذاری نظرات