کد الگوریتم ژنتیک در c++ بصورت رایگان و کاربردی
در این پست از سری آموزش های پی استور در رابطه با پیاده سازی کد الگوریتم ژنتیک در c++ صحبت خواهیم کرد. قبل از اینکه از این کد استفاده کنید بهتر است مقدماتی در رابطه با الگوریتم ژنتیک بدانید تا درک پیاده سازی الگوریتم برای شما عزیزان آسان شود. پس با ادامه مطلب با ما همراه باشید.
مقدمه
الگوریتم ژنتیک GA جزو الگوریتمهای جستجوی اکتشافی تطبیقی هستند که به بخش بزرگتری از الگوریتمهای تکاملی تعلق دارند. الگوریتم ژنتیک مبتنی بر ایده های انتخاب طبیعی و ژنتیک است که برای بهره برداری هوشمندانه از جستجوی تصادفی ارائه شده با داده های گذشته برای هدایت جستجو به منطقه ای با عملکرد بهتر در فضای راه حل است. الگوریتم ژنتیک معمولاً برای تولید راه حل های با کیفیت بالا برای مسائل بهینه سازی و مسائل جستجو استفاده میشوند.
الگوریتم ژنتیک فرآیند انتخاب طبیعی در دنیای واقعی را شبیهسازی میکنند، به این معنی که آن دسته از گونههایی که میتوانند با تغییرات محیطی خود سازگار شوند، میتوانند زنده بمانند و تولید مثل کنند و به نسل بعدی بروند. به عبارت ساده، آنها “بقای شایسته” را در بین افراد نسل متوالی برای حل یک مسئله شبیه سازی می کنند. هر نسل از جمعیتی از افراد تشکیل شده است و هر فرد نشان دهنده یک نقطه در فضای جستجو و راه حل ممکن است. از دید برنامه نویسی هر فرد به صورت رشته ای از کاراکترها ، عدد صحیح، شناور و یا بیت نمایش داده می شود. این نوع نمایش مشابه کروموزوم در ژنتیک است.
اگر علاقه مند هستید الگوریتم ژنتیک را به صورت کامل و کاملاً تخصصی یاد بگیرید پیشنهاد می کنیم مقاله آموزش کامل و جامع ما را در این زمینه حتماً مطالعه کنید.
اساس الگوریتم ژنتیک
الگوریتم های ژنتیک بر اساس قیاس با ساختار ژنتیکی و رفتار کروموزوم های جمعیت است. در ادامه اساس الگوریتم ژنتیک GA بر اساس این قیاس آورده شده است:
- افراد در جمعیت برای منابع و جفت گیری رقابت می کنند.
- آن دسته از افراد موفق (مناسب) سپس جفت گیری می کنند تا فرزندان بیشتری نسبت به دیگران ایجاد کنند.
- ژنهای «مناسبترین» والدین در طول نسل تکثیر میشوند، یعنی گاهی والدین فرزندانی بهتر از هر یک از والدین ایجاد میکنند.
- بنابراین هر نسل متوالی برای محیط خود مناسب تر است.
فضای جستجو در الگوریتم ژنتیک
جمعیت افراد (Population) در فضای جستجو نگهداری می شود. هر فردی یک راه حل را در فضای جستجو برای مسئله معین نشان می دهد. هر فرد به عنوان یک بردار طول محدود (مشابه کروموزوم Chromosome) از اجزا کدگذاری می شود. این اجزای متغیر مشابه ژن ها هستند. بنابراین یک کروموزوم (فرد) از چندین ژن Gene (جزء متغیر) تشکیل شده است.
تابع تناسب یا فیتنس در الگوریتم ژنتیک
یک امتیاز به هر فرد یا همان کروموزوم داده می شود که نشان دهنده توانایی یک فرد برای “رقابت” است. افرادی که دارای امتیاز تناسب بهینه (یا نزدیک به مطلوب) هستند، جستجو می شوند.
الگوریتم جمعیت n کروموزومی را همراه با امتیاز تابع تناسب آنها حفظ می کند. به افرادی که نمرات تناسب بهتری دارند شانس بیشتری برای تولید مثل، نسبت به دیگران داده می شود. افرادی که امتیاز تناسب بهتری دارند انتخاب می شوند که با ترکیب کروموزوم های والدین جفت می شوند و فرزندان بهتری تولید می کنند. اندازه جمعیت ثابت است، بنابراین اتاق باید برای تازه واردان ایجاد شود. بنابراین، برخی از افراد می میرند و با تازه واردان جایگزین می شوند و در نهایت با تمام شدن فرصت جفت گیری جمعیت قدیمی، نسل جدیدی را ایجاد می کنند. امید است که در طول نسلهای متوالی راهحلهای بهتری به دست آید در حالی که کمترین تناسب را دارند.
هر نسل جدید به طور متوسط «ژن های بهتر» بیشتری نسبت به افراد (راه حل) نسل های قبلی دارد. بنابراین هر نسل جدید “راه حل های جزئی” بهتری نسبت به نسل های قبلی دارد. هنگامی که فرزندان تولید شده تفاوت معنی داری با فرزندان تولید شده توسط جمعیت های قبلی نداشته باشند، جمعیت همگرا می شود. گفته می شود که الگوریتم به مجموعه ای از راه حل ها برای مسئله همگرا می شود.
اپراتورهای الگوریتم ژنتیک
هنگامی که نسل اولیه ایجاد شد، الگوریتم با استفاده از عملگرهای زیر، نسل را تکامل میدهد:
1) عملگر انتخاب (Selection Operator): ایده این است که به افرادی که امتیازات تناسب خوبی دارند اولویت داده شود و به آنها اجازه داده شود تا ژن های خود را به نسل های متوالی منتقل کنند.
2) عملگر متقاطع (Crossover Operator): این عملگر نشان دهنده جفت گیری بین افراد است. دو نفر با استفاده از عملگر انتخاب و متقاطع به صورت تصادفی انتخاب می شوند. سپس ژنها در این مکانهای متقاطع مبادله میشوند و بنابراین یک فرد کاملاً جدید (فرزند جدید) ایجاد میشود.
3) عملگر جهش (Mutation Operator): ایده کلیدی این است که ژن های تصادفی را در فرزندان وارد کنیم تا تنوع در جمعیت حفظ شود تا از همگرایی زودرس جلوگیری شود.
شبه کد الگوریتم ژنتیک
به صورت ساده کل الگوریتم را می توان به صورت زیر خلاصه کرد:
1) Randomly initialize populations p 2) Determine fitness of population 3) 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، 0-9 و سایر نمادهای خاص به عنوان ژن در نظر گرفته می شوند.
- رشته ای که توسط این کاراکترها ایجاد می شود به عنوان کروموزوم در نظر گرفته می شود.
- تابع تناسب تعداد کاراکترهایی است که با کاراکترهای رشته Target در یک شاخص خاص متفاوت است. بنابراین به افرادی که ارزش تناسب کمتری دارند اولویت بیشتری داده می شود.
سورس کد الگوریتم ژنتیک با 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. // 0 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
الگوریتم هر زمان با رشته های تصادفی شروع می شود، بنابراین خروجی ممکن است متفاوت باشد. همانطور که در خروجی می بینیم، الگوریتم ما گاهی اوقات در یک راه حل بهینه محلی گیر می کند، این امر می تواند با به روز رسانی الگوریتم محاسبه امتیاز تناسب یا با بهینه سازی عملگرهای جهش و متقاطع بیشتر بهبود یابد.
چرا از الگوریتم ژنتیک استفاده کنیم؟
- الگوریتم ژنتیک یک الگوریتم قدرتمند در حل مسائل و بهینه سازی است.
- می تواند عمل بهینه سازی را در حالت فضای بزرگ انجام دهد.
- برخلاف هوش مصنوعی سنتی، با تغییر جزئی در ورودی یا وجود نویز شکسته نمی شوند.
مباحث پیشنهادی و مرتبط با موضوع
درباره امین جلیل زاده رزین
پایه گذار و موسس وب سایت آموزشی پی استور، مدرس دانشگاه فنی و حرفه ای، برنامه نویس و تحلیل گر سیستم، پژوهشگر در حوزه الگوریتم های ابتکاری، فرا ابتکاری، یادگیری ماشین، شبکه و پایگاه داده. ایشان در زبان های برنامه نویسی متعدد، نظیر ++C، سی شارپ، PHP ،Java، متلب MATLAB و Python تسلط و سابقه تدریس فعال دارند.