کد الگوریتم ژنتیک در c++ بصورت رایگان و کاربردی

مقدمه مقاله کد الگوریتم ژنتیک در c++

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

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

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

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

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

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

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

کلیک کنید

فضای جستجو در الگوریتم ژنتیک

جمعیت افراد (Population) در فضای جستجو نگهداری می‌شود. هر فردی یک راه حل را در فضای جستجو برای مسئله معین نشان می‌دهد. هر فرد به عنوان یک بردار طول محدود (مشابه کروموزوم Chromosome) از اجزا کدگذاری می‌شود. این اجزای متغیر مشابه ژن‌ها هستند. بنابراین یک کروموزوم (فرد) از چندین ژن Gene (جزء متغیر) تشکیل شده است.

تابع تناسب یا فیتنس در الگوریتم ژنتیک

یک امتیاز به هر فرد یا همان کروموزوم داده می‌شود که نشان دهنده توانایی یک فرد برای “رقابت” است. افرادی که دارای امتیاز تناسب بهینه (یا نزدیک به مطلوب) هستند، جستجو می‌شوند.

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

هر نسل جدید به طور متوسط ​​«ژن‌های بهتر» بیشتری نسبت به افراد (راه حل) نسل‌های قبلی دارد. بنابراین هر نسل جدید “راه حل‌های جزئی” بهتری نسبت به نسل‌های قبلی دارد. هنگامی که فرزندان تولید شده تفاوت معنی داری با فرزندان تولید شده توسط جمعیت‌های قبلی نداشته باشند، جمعیت همگرا می‌شود. گفته می‌شود که الگوریتم به مجموعه‌ای از راه حل‌ها برای مسئله همگرا می‌شود.

پاورپوینت سیستم تشخیص چهره توسط الگوریتم ژنتیک

کلیک کنید

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

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

۱) عملگر انتخاب (Selection Operator): ایده این است که به افرادی که امتیازات تناسب خوبی دارند اولویت داده شود و به آن‌ها اجازه داده شود تا ژن‌های خود را به نسل‌های متوالی منتقل کنند.

۲) عملگر متقاطع (Crossover Operator): این عملگر نشان دهنده جفت گیری بین افراد است. دو نفر با استفاده از عملگر انتخاب و متقاطع به صورت تصادفی انتخاب می‌شوند. سپس ژن‌ها در این مکان‌های متقاطع مبادله می‌شوند و بنابراین یک فرد کاملاً جدید (فرزند جدید) ایجاد می‌شود.

۳) عملگر جهش (Mutation Operator): ایده کلیدی این است که ژن‌های تصادفی را در فرزندان وارد کنیم تا تنوع در جمعیت حفظ شود تا از همگرایی زودرس جلوگیری شود.

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

به صورت ساده کل الگوریتم را می‌توان به صورت زیر خلاصه کرد:

۱) Randomly initialize populations p
۲) Determine fitness of population
۳) Until convergence repeat:
      a) Select parents from population
      b) Crossover and generate new population
      c) Perform mutation on new population
      d) Calculate fitness for new population

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

می‌خواهیم در تعداد تکرارهای مختلفی یک رشته هدف یا Target را بدست آوریم. فرض کنید هدف به دست آوردن رشته “I like programstore” باشد خوب براحتی می‌توان دید برای به دست آوردن این رشته با روش جایگزینی معمولی تست و خطا تعداد تکرار خیلی زیادی خواهیم داشت که از مرتبه فاکتوریل است. ولی با تعریف یک تابع تناسب و اجرای الگوریتم ژنتیک خیلی راحت می‌توان در تعاد تکرار‌های به مراتب خیلی خیلی کم‌تری این رشته را دست آورد.

پس هدف تولید رشته Target است. در ابتدا از یک رشته تصادفی با همان طول شروع می‌کنیم. در اجرای الگوریتم ژنتیک با C++ زیر، قیاس‌های زیر انجام می‌شود:

• کاراکترهای A-Z، a-z، ۰-۹ و سایر نمادهای خاص به عنوان ژن در نظر گرفته می‌شوند.
• رشته ای که توسط این کاراکترها ایجاد می‌شود به عنوان کروموزوم در نظر گرفته می‌شود.
• تابع تناسب تعداد کاراکترهایی است که با کاراکترهای رشته Target در یک شاخص خاص متفاوت است. بنابراین به افرادی که ارزش تناسب کم‌تری دارند اولویت بیشتری داده می‌شود.
• 

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

  کلیک کنید

سورس کد الگوریتم ژنتیک با C++

// C++ program to create target string, starting from
// random string using Genetic Algorithm

#include <bits/stdc++.h>
using namespace std;

// Number of individuals in each generation
#define POPULATION_SIZE 100

// Valid Genes
const string GENES = "abcdefghijklmnopqrstuvwxyzABCDEFGHIJKLMNOP"\
"QRSTUVWXYZ 1234567890, .-;:_!\"#%&/()=?@${[]}";

// Target string to be generated
const string TARGET = "I like programstore";

// Function to generate random numbers in given range
int random_num(int start, int end)
{
     int range = (end-start)+1;
     int random_int = start+(rand()%range);
     return random_int;
}

// Create random genes for mutation
char mutated_genes()
{
     int len = GENES.size();
     int r = random_num(0, len-1);
     return GENES[r];
}

// create chromosome or string of genes
string create_gnome()
{
     int len = TARGET.size();
     string gnome = "";
     for(int i = 0;i<len;i++)
          gnome += mutated_genes();
     return gnome;
}

// Class representing individual in population
class Individual
{
public:
     string chromosome;
     int fitness;
     Individual(string chromosome);
     Individual mate(Individual parent2);
     int cal_fitness();
};

Individual::Individual(string chromosome)
{
     this->chromosome = chromosome;
     fitness = cal_fitness();
};

// Perform mating and produce new offspring
Individual Individual::mate(Individual par2)
{
     // chromosome for offspring
     string child_chromosome = "";

     int len = chromosome.size();
     for(int i = 0;i<len;i++)
     {
          // random probability
          float p = random_num(0, 100)/100;

          // if prob is less than 0.45, insert gene
          // from parent 1
          if(p < 0.45)
               child_chromosome += chromosome[i];

          // if prob is between 0.45 and 0.90, insert
          // gene from parent 2
          else if(p < 0.90)
               child_chromosome += par2.chromosome[i];

          // otherwise insert random gene(mutate),
          // for maintaining diversity
          else
               child_chromosome += mutated_genes();
     }

     // create new Individual(offspring) using
     // generated chromosome for offspring
     return Individual(child_chromosome);
};


// Calculate fittness score, it is the number of
// characters in string which differ from target
// string.
int Individual::cal_fitness()
{
     int len = TARGET.size();
     int fitness = 0;
     for(int i = 0;i<len;i++)
     {
          if(chromosome[i] != TARGET[i])
               fitness++;
     }
     return fitness;
};

// Overloading < operator
bool operator<(const Individual &ind1, const Individual &ind2)
{
     return ind1.fitness < ind2.fitness;
}

// Driver code
int main()
{
     srand((unsigned)(time(0)));

     // current generation
     int generation = 0;

     vector<Individual> population;
     bool found = false;

     // create initial population
     for(int i = 0;i<POPULATION_SIZE;i++)
     {
          string gnome = create_gnome();
          population.push_back(Individual(gnome));
     }

     while(! found)
     {
          // sort the population in increasing order of fitness score
          sort(population.begin(), population.end());

          // if the individual having lowest fitness score ie.
          // ۰ then we know that we have reached to the target
          // and break the loop
          if(population[0].fitness <= 0)
          {
               found = true;
               break;
          }

          // Otherwise generate new offsprings for new generation
          vector<Individual> new_generation;

          // Perform Elitism, that mean 10% of fittest population
          // goes to the next generation
          int s = (10*POPULATION_SIZE)/100;
          for(int i = 0;i<s;i++)
               new_generation.push_back(population[i]);

          // From 50% of fittest population, Individuals
          // will mate to produce offspring
          s = (90*POPULATION_SIZE)/100;
          for(int i = 0;i<s;i++)
          {
               int len = population.size();
               int r = random_num(0, 50);
               Individual parent1 = population[r];
               r = random_num(0, 50);
               Individual parent2 = population[r];
               Individual offspring = parent1.mate(parent2);
               new_generation.push_back(offspring);
          }
          population = new_generation;
          cout<< "Generation: " << generation << "\t";
          cout<< "String: "<< population[0].chromosome <<"\t";
          cout<< "Fitness: "<< population[0].fitness << "\n";

          generation++;
     }
     cout<< "Generation: " << generation << "\t";
     cout<< "String: "<< population[0].chromosome <<"\t";
     cout<< "Fitness: "<< population[0].fitness << "\n";
}

Generation: 0 String: !,lx"bmQ4bq$V![tbs3 Fitness: 17
Generation: 1 String: & kG03 bT x0!#kJDfo Fitness: 17
Generation: 2 String: p-qw_cA(Nxq&e:stQ_! Fitness: 17
Generation: 3 String: p-qw_cA{1xq&e:stQ_! Fitness: 17
Generation: 4 String: !,lx"bmQ4bq$V![tbs3 Fitness: 17
Generation: 5 String: I-qw_cA.1xq&e:stQ_! Fitness: 16
Generation: 6 String: I-qw_cA.1xq&e:stQ_! Fitness: 16
Generation: 7 String: I-qw_cA.1xq&e:stQ_! Fitness: 16
Generation: 8 String: I-qw_cA.1xq&e:stQ_! Fitness: 16
Generation: 9 String: I-qw_(A.1Oq&e:stQ_! Fitness: 16
Generation: 10 String: I-qw_(An1xqge:stQ_! Fitness: 16
Generation: 11 String: I-qw_(A.1xq&e:sto_! Fitness: 15
Generation: 12 String: I-qw_(A.1xq&e:sto_! Fitness: 15
Generation: 13 String: I-qw_(A.1xq&e:sto_! Fitness: 15
Generation: 14 String: I-qw_(A.1xq&e:sto_! Fitness: 15
Generation: 15 String: I-qw_]A.1xq&e:sto_! Fitness: 15
Generation: 16 String: I-qw_(A.1xq&e:sto_! Fitness: 15
                           . 
                           . 
                           . 
Generation: 351 String: I like programstoEe Fitness: 1
Generation: 352 String: I like programsto3e Fitness: 1
Generation: 353 String: I like programstore Fitness: 0

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

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

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