طراحی الگوریتم ژنتیک در جاوا — به زبان ساده

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

1. سرآغاز

این مقاله را با توضیح مفهوم این الگوریتم‌ها با استفاده از مثالی از ساده‌ترین الگوریتم ژنتیک باینری آغاز می‌کنیم.

فیلم آموزش پیاده سازی الگوریتم ژنتیک در پایتون Python – مقدماتی در فرادرس

کلیک کنید

2. طرز کار الگوریتم‌های ژنتیک چگونه است؟

الگوریتم‌های ژنتیک بخشی از «محاسبات تکاملی» (Evolutionary Computing) هستند که زمینه‌ای با رشد سریع در حوزه هوش مصنوعی محسوب می‌شود.

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

افرادی که از جمعیت جدید انتخاب می‌شوند (offspring) بر اساس برازش (fitness) خود گزینش می‌شوند و هر چه مناسب‌تر باشند، احتمال بیشتری دارد که بازتولید یابند.

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

در این بخش به فرایند مقدماتی یک الگوریتم ژنتیک باینری نگاهی می‌کنیم.

3.1 مقداردهی اولیه

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

1SimpleGeneticAlgorithm.runAlgorithm(50,
2  "1011000100000100010000100000100111001000000100000100000000001111");

در مثال فوق اندازه جمعیت برابر با 50 است و راه‌حل صحیح به وسیله رشته بیت باینری نمایش یافته که هر زمان می‌تواند تغییر یابد.

در مرحله بعدی قصد داریم راه‌حل مطلوب خود را ذخیره کرده و یک جمعیت تصادفی بسازیم:

1setSolution(solution);
2Population myPop = new Population(populationSize, true);

اینک آماده اجرای حلقه اصلی برنامه خود هستیم.

3.2 بررسی برازش

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

1while (myPop.getFittest().getFitness() < getMaxFitness()) {
2    System.out.println(
3      "Generation: " + generationCount
4      + " Correct genes found: " + myPop.getFittest().getFitness());
5     
6    myPop = evolvePopulation(myPop);
7    generationCount++;
8}

کار خود را با توضیح دادن شیوه یافتن فرد دارای بالاترین برازش آغاز می‌کنیم:

1public int getFitness(Individual individual) {
2    int fitness = 0;
3    for (int i = 0; i < individual.getDefaultGeneLength()
4      && i < solution.length; i++) {
5        if (individual.getSingleGene(i) == solution[i]) {
6            fitness++;
7        }
8    }
9    return fitness;
10}

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

3.3 Offspring

در این مرحله باید یک جمعیت جدید ایجاد کنیم. ابتدا باید دو شیء والد را بر مبنای میزان برازششان از جمعیت انتخاب کنیم. توجه داشته باشید که بهتر است اجازه بدهیم بهترین فرد جمعیت حاضر بدون ایجاد هیچ تغییری به جمعیت بعدی انتقال یابد. این راهبرد به نام Elitism نامیده می‌شود:

1if (elitism) {
2    newPopulation.getIndividuals().add(0, pop.getFittest());
3    elitismOffset = 1;
4} else {
5    elitismOffset = 0;
6}

برای انتخاب دو مورد از بهترین افراد باید از «راهبرد انتخاب تورنمنت» (tournament selection strategy) استفاده کنیم:

1private Individual tournamentSelection(Population pop) {
2    Population tournament = new Population(tournamentSize, false);
3    for (int i = 0; i < tournamentSize; i++) {
4        int randomId = (int) (Math.random() * pop.getIndividuals().size());
5        tournament.getIndividuals().add(i, pop.getIndividual(randomId));
6    }
7    Individual fittest = tournament.getFittest();
8    return fittest;
9}

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

1private Individual crossover(Individual indiv1, Individual indiv2) {
2    Individual newSol = new Individual();
3    for (int i = 0; i < newSol.getDefaultGeneLength(); i++) {
4        if (Math.random() <= uniformRate) {
5            newSol.setSingleGene(i, indiv1.getSingleGene(i));
6        } else {
7            newSol.setSingleGene(i, indiv2.getSingleGene(i));
8        }
9    }
10    return newSol;
11}

در Crossover بیت‌ها را از هر یک از افراد در نقطه انتخابی تصادفی عوض می‌کنیم. کل فرایند درون حلقه زیر صورت می‌گیرد:

1for (int i = elitismOffset; i < pop.getIndividuals().size(); i++) {
2    Individual indiv1 = tournamentSelection(pop);
3    Individual indiv2 = tournamentSelection(pop);
4    Individual newIndiv = crossover(indiv1, indiv2);
5    newPopulation.getIndividuals().add(i, newIndiv);
6}

همان طور که می‌بینید، پس از Crossover نسل جدید را در یک جمعیت تازه قرار می‌دهیم. این گام به نام Acceptance نامیده می‌شود.

در نهایت اقدام به اجرای «جهش» (Mutation) می‌کنیم. جهش برای حفظ تنوع ژنتیکی از یک نسل از جمعیت تا نسل بعدی صورت می‌پذیرد. ما از روش «معکوس سازی بیت» (bit inversion) برای اعمال جهش استفاده می‌کنیم که در آن بیت‌های تصادفی به سادگی معکوس می‌شوند:

1private void mutate(Individual indiv) {
2    for (int i = 0; i < indiv.getDefaultGeneLength(); i++) {
3        if (Math.random() <= mutationRate) {
4            byte gene = (byte) Math.round(Math.random());
5            indiv.setSingleGene(i, gene);
6        }
7    }
8}

در نهایت ما همه مراحل 3.2 تا 3.3 را تا زمانی که به شرایط نهایی که در واقع بهترین راه‌حل مورد نظر ما است برسیم، ادامه می‌دهیم.

4. نکات و ترفندها

برای پیاده‌سازی یک الگوریتم ژنتیک کارآمد باید برخی مجموعه پارامترها را تنظیم کنیم. در این بخش برخی پیشنهادهای پایه‌ای در مورد شیوه آغاز کار با مهم‌ترین پارامترها ارائه شده است:

فیلم آموزش برنامه نویسی جاوا Java در فرادرس

کلیک کنید

• نرخ Crossover – این نرخ باید بالا باشد و عددی بین 80 تا 95 درصد مطلوب است.
• نرخ جهش – این نرخ باید پایین باشد و عددی بین 0.5 تا 1 درصد مطلوب است.
• اندازه جمعیت – اندازه جمعیت مطلوب در حدود 20 تا 30 نفر است.
• انتخاب – می‌توانید از روش انتخاب «چرخ رولت مقدماتی» به همراه مفهوم «نخبه‌گرایی» (elitism) استفاده کنید.
• نوع Crossover و جهش – این پارامتر به نوع کدگذاری و مسئله وابسته هستند.

توجه داشته باشید که این پیشنهادها برای تنظیم دقیق در اغلب موارد نتیجه مطالعات عملی روی الگوریتم‌های ژنتیک هستند و ممکن است بر مبنای مسائل پیشنهادی متفاوت باشند

5. سخن پایانی

در این مقاله به معرفی مبانی الگوریتم‌های ژنتیک پرداختیم. شما می‌توانید بدون هیچ گونه دانش قبلی و صرفاً با بهره‌گیری از مهارت‌های مقدمتی برنامه‌نویسی رایانه، موارد زیادی را در این زمینه بیاموزید. کد کامل این راهنما را می‌توانید در این ریپازیتوری گیت‌هاب (+) ملاحظه کنید.

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

کلیک کنید

اگر این مطلب برای شما مفید بوده است، آموزش‌های زیر نیز به شما پیشنهاد می‌شوند:

• مجموعه آموزش های برنامه‌نویسی جاوا
• آموزش پیاده سازی الگوریتم های تکاملی و فراابتکاری در سی شارپ
•  مجموعه آموزش‌های الگوریتم ژنتیک و محاسبات تکاملی
• مقدمه‌ای بر الگوریتم ژنتیک
• مقدمه‌ای بر الگوریتم ژنتیک به همراه کد جاوا — به زبان ساده
• آموزش 2۵ الگوریتم بهینه سازی تکاملی و هوشمند در فرادرس

==