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

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

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

• جمعیت اولیه
• تابع برازندگی
• انتخاب
• ترکیب (آمیزش)
• جهش

مرحله اول: جمعیت اولیه

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

یک موجود با مجموعه‌ای از پارامترها (متغیرها) شناخته می‌شه که بهشون میگیم ژن. ژن‌ها به هم متصل می‌شن تا یک کروموزوم رو تشکیل بدن (که در واقع همون راه‌حله) توی الگوریتم ژنتیک ما اطلاعات ژن‌های یک موجود رو به شکل یک رشته از حروف نمایش میدیم. معمولا از سیستم دودویی استفاده می‌شه (یعنی رشته‌ای از صفر و یک). اینطوری می‌تونیم بگیم ژن‌ها رو توی یک کروموزوم کدگذاری می‌کنیم.”

مرحله دوم: تابع برازندگی (تابع شایستگی)

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

مرحله سوم: انتخاب

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

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

مرحله چهارم: ترکیب (آمیزش)

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

مثلا فرض کنیم نقطه آمیزش رو عدد ۳ در نظر بگیریم، مثل چیزی که پایین نشون داده شده.

[نمونه و توضیح بصری از نقطه آمیزش]

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

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

مرحله پنجم: جهش

جهش در بعضی از فرزندان جدیدی که به وجود میان، امکان داره یک سری از ژن‌هاشون با احتمال تصادفی پایین دچار جهش بشن. این یعنی ممکنه بعضی از بیت‌ها در رشته بیتی (کروموزوم) برعکس بشن (از ۰ به ۱ یا برعکس).

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

پایان

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

توضیحات

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

این ترتیب و توالی مراحل مرتب تکرار می‌شه تا در هر نسل، موجودات بهتری نسبت به نسل قبل تولید بشن.

Pseudocode

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

مثالی از پیاده‌سازی در جاوا

در زیر یک مثال از پیاده‌سازی الگوریتم ژنتیک به زبان جاوا رو می‌بینید. می‌تونید به کد نگاهی بندازید و تغییرات بدید.

فرض کنید ۵ تا ژن داریم که هر کدوم می‌تونن مقدار دودویی ۰ یا ۱ رو بگیرن. مقدار برازندگی به عنوان تعداد ۱ هایی که در ژنوم وجود دارن محاسبه می‌شه. اگه پنج تا ۱ وجود داشته باشه، یعنی حداکثر برازندگی رو داریم. اگه هیچ ۱ وجود نداشته باشه، یعنی کمترین میزان برازندگی رو خواهیم داشت.

هدف این الگوریتم ژنتیک اینه که تابع برازندگی رو به حداکثر برسونه و جمعیتی رو بسازه که شامل قوی‌ترین موجودات میشن ( یعنی موجوداتی که پنج تا ژن با مقدار ۱ دارن)

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

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();
    }

}