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

مقدمه

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

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

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

در یک الگوریتم ژنتیک پنج فاز در نظر گرفته شده است.

1. جمعیت اولیه
2. عملکرد تناسب اندام
3. انتخاب
4. کراس اوور
5. جهش

جمعیت اولیه این فرآیند با مجموعه ای از افراد آغاز می شود که به آنها جمعیت می گویند. هر فردی راه حلی برای مشکلی است که می خواهید حل کنید. یک فرد با مجموعه ای از پارامترها (متغیرها) شناخته شده به عنوان ژن مشخص می شود. ژن ها به یک رشته متصل می شوند تا کروموزوم (محلول) را تشکیل دهند. در الگوریتم ژنتیک، مجموعه ژن های یک فرد با استفاده از یک رشته، بر حسب الفبا نمایش داده می شود. معمولاً از مقادیر باینری استفاده می شود (رشته های ۱ و ۰). ما می گوییم که ما ژن های یک کروموزوم را رمزگذاری می کنیم.

عملکرد تناسب اندام

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

انتخاب

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

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

کراس اوور

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

برای مثال نقطه متقاطع را مطابق شکل زیر ۳ در نظر بگیرید.

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

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

جهش

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

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

خاتمه دادن

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

نظرات

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

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

Pseudocode

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

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

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

با توجه به مجموعه ای از ۵ ژن، هر ژن می تواند یکی از مقادیر دوتایی ۰ و ۱ را داشته باشد.

ارزش تناسب به عنوان تعداد ۱s موجود در ژنوم محاسبه می شود. اگر پنج عدد ۱ وجود داشته باشد، پس حداکثر آمادگی را دارد. اگر ۱ وجود نداشته باشد، حداقل تناسب اندام را دارد.

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

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

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

	}