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

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

الگوریتم ژنتیک جستجوی مکاشفه‌ای است که از نظریه تکامل طبیعی چارلز داروین الهام گرفته است. این الگوریتم بازتاب‌دهنده فرایند انتخاب طبیعی است که در آن افراد با برازش بیشتر برای تولید مثل انتخاب می‌شوند تا فرزندان نسل بعد را تشکیل دهند.

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

مفهوم انتخاب طبیعی

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

فیلم آموزش تولباکس الگوریتم ژنتیک متلب در فرادرس

کلیک کنید

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

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

• جمعیت اولیه
• تابع برازش
• انتخاب
• تقاطع
• جهش

جمعیت اولیه

این فرایند با مجموعه‌ای از افراد آغاز می‌شود که «جمعیت» (Population) نامیده می‌شوند. هر فرد یک راه‌حل برای مسئله‌ای است که می‌خواهیم حل کنیم. هر فرد بر اساس مجموعه‌ای از پارامترها (متغیرها) به نام ژن‌ها شناسایی می‌شود. ژن‌ها به یک رشته ملحق می‌شوند تا یک کروموزوم (راه‌حل) را تشکیل دهند.

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

تابع برازش

تابع برازش (Fitness Function) میزان مناسب بودن یک فرد را تعیین می‌کند. به بیان دیگر توانایی فرد برای رقابت با افراد دیگر را مشخص می‌کند. این تابع یک امتیاز برازش به هر فرد می‌دهد. احتمال این که یک فرد برای تولید مثل انتخاب شود، بر اساس امتیاز برازش وی است.

فیلم آموزش ترکیب الگوریتم ژنتیک و PSO و پیاده سازی در متلب MATLAB در فرادرس

کلیک کنید

انتخاب

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

تقاطع

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

برای نمونه، فرض کنید نقطه تقاطع در تصویر زیر در 3 باشد.

فرزندان از طریق مبادله ژن‌های والدین در میان خودشان تا رسیدن به نقطه تقاطع متولد می‌شوند.

فرزندان جدید به جمعیت اضافه می‌شوند.

جهش

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

جهش جهت حفظ تنوع درون جمعیت و جلوگیری از همگرایی زودهنگام ضروری است.

خاتمه

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

توضیحات

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

شبه کد

START
Generate the initial population
Compute fitness
REPEAT
Selection
Crossover
Mutation
Compute fitness
UNTIL population has converged
STOP

پیاده‌سازی ساده در جاوا

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

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

کلیک کنید

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

import java.util.Random;

/**
 *
 * @author Vijini
 */

//Main class
public class SimpleDemoGA {

    Population population = new Population();
    Individual fittest;
    Individual secondFittest;
    int generationCount = 0;

    public static void main(String[] args) {

        Random rn = new Random();

        SimpleDemoGA demo = new SimpleDemoGA();

        //Initialize population
        demo.population.initializePopulation(10);

        //Calculate fitness of each individual
        demo.population.calculateFitness();

        System.out.println("Generation: " + demo.generationCount + " Fittest: " + demo.population.fittest);

        //While population gets an individual with maximum fitness
        while (demo.population.fittest < 5) {
            ++demo.generationCount;

            //Do selection
            demo.selection();

            //Do crossover
            demo.crossover();

            //Do mutation under a random probability
            if (rn.nextInt()%7 < 5) {
                demo.mutation();
            }

            //Add fittest offspring to population
            demo.addFittestOffspring();

            //Calculate new fitness value
            demo.population.calculateFitness();

            System.out.println("Generation: " + demo.generationCount + " Fittest: " + demo.population.fittest);
        }

        System.out.println("\nSolution found in generation " + demo.generationCount);
        System.out.println("Fitness: "+demo.population.getFittest().fitness);
        System.out.print("Genes: ");
        for (int i = 0; i < 5; i++) {
            System.out.print(demo.population.getFittest().genes[i]);
        }

        System.out.println("");

    }

    //Selection
    void selection() {

        //Select the most fittest individual
        fittest = population.getFittest();

        //Select the second most fittest individual
        secondFittest = population.getSecondFittest();
    }

    //Crossover
    void crossover() {
        Random rn = new Random();

        //Select a random crossover point
        int crossOverPoint = rn.nextInt(population.individuals[0].geneLength);

        //Swap values among parents
        for (int i = 0; i < crossOverPoint; i++) {
            int temp = fittest.genes[i];
            fittest.genes[i] = secondFittest.genes[i];
            secondFittest.genes[i] = temp;

        }

    }

    //Mutation
    void mutation() {
        Random rn = new Random();

        //Select a random mutation point
        int mutationPoint = rn.nextInt(population.individuals[0].geneLength);

        //Flip values at the mutation point
        if (fittest.genes[mutationPoint] == 0) {
            fittest.genes[mutationPoint] = 1;
        } else {
            fittest.genes[mutationPoint] = 0;
        }

        mutationPoint = rn.nextInt(population.individuals[0].geneLength);

        if (secondFittest.genes[mutationPoint] == 0) {
            secondFittest.genes[mutationPoint] = 1;
        } else {
            secondFittest.genes[mutationPoint] = 0;
        }
    }

    //Get fittest offspring
    Individual getFittestOffspring() {
        if (fittest.fitness > secondFittest.fitness) {
            return fittest;
        }
        return secondFittest;
    }


    //Replace least fittest individual from most fittest offspring
    void addFittestOffspring() {

        //Update fitness values of offspring
        fittest.calcFitness();
        secondFittest.calcFitness();

        //Get index of least fit individual
        int leastFittestIndex = population.getLeastFittestIndex();

        //Replace least fittest individual from most fittest offspring
        population.individuals[leastFittestIndex] = getFittestOffspring();
    }

}


//Individual class
class Individual {

    int fitness = 0;
    int[] genes = new int[5];
    int geneLength = 5;

    public Individual() {
        Random rn = new Random();

        //Set genes randomly for each individual
        for (int i = 0; i < genes.length; i++) {
            genes[i] = Math.abs(rn.nextInt() % 2);
        }

        fitness = 0;
    }

    //Calculate fitness
    public void calcFitness() {

        fitness = 0;
        for (int i = 0; i < 5; i++) {
            if (genes[i] == 1) {
                ++fitness;
            }
        }
    }

}

//Population class
class Population {

    int popSize = 10;
    Individual[] individuals = new Individual[10];
    int fittest = 0;

    //Initialize population
    public void initializePopulation(int size) {
        for (int i = 0; i < individuals.length; i++) {
            individuals[i] = new Individual();
        }
    }

    //Get the fittest individual
    public Individual getFittest() {
        int maxFit = Integer.MIN_VALUE;
        int maxFitIndex = 0;
        for (int i = 0; i < individuals.length; i++) {
            if (maxFit <= individuals[i].fitness) {
                maxFit = individuals[i].fitness;
                maxFitIndex = i;
            }
        }
        fittest = individuals[maxFitIndex].fitness;
        return individuals[maxFitIndex];
    }

    //Get the second most fittest individual
    public Individual getSecondFittest() {
        int maxFit1 = 0;
        int maxFit2 = 0;
        for (int i = 0; i < individuals.length; i++) {
            if (individuals[i].fitness > individuals[maxFit1].fitness) {
                maxFit2 = maxFit1;
                maxFit1 = i;
            } else if (individuals[i].fitness > individuals[maxFit2].fitness) {
                maxFit2 = i;
            }
        }
        return individuals[maxFit2];
    }

    //Get index of least fittest individual
    public int getLeastFittestIndex() {
        int minFitVal = Integer.MAX_VALUE;
        int minFitIndex = 0;
        for (int i = 0; i < individuals.length; i++) {
            if (minFitVal >= individuals[i].fitness) {
                minFitVal = individuals[i].fitness;
                minFitIndex = i;
            }
        }
        return minFitIndex;
    }

    //Calculate fitness of each individual
    public void calculateFitness() {

        for (int i = 0; i < individuals.length; i++) {
            individuals[i].calcFitness();
        }
        getFittest();
    }

}

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

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

کلیک کنید

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

==