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

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

 

الگوریتم ژنتیک شامل این مراحل است :

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

    package optimisation_GA;

    public class individual {
    int decimal;
    String binary;
    int fitnessFunction;
    int length;//length of binary representation
    individual(int value, int _length){
    decimal = value;
    length = _length;
    binary = "";
    decToBin(decimal);
    addZero();
    }
    //makes binary representation of each
    //decimal of equal length
    private void addZero() {
    // TODO Auto-generated method stub
    for(int i = binary.length(); i != length; ++i)
    binary = "0" + binary;

    }
    //convert from decimal number
    //to binary number
    private Object decToBin(int dec) {
    // TODO Auto-generated method stub
    int num;

    if (dec <=1) {
    binary +=dec;
    return null; // KICK OUT OF THE RECURSION
    }

    num= dec %2;
    decToBin(dec >>1);
    binary += num;
    return null;	
    }
    public individual crossover(individual pair){
    individual child;
    int crossoverPoint = (int)Math.random()*length;
    String newBinValue = "";
    for(int i = 0; i != crossoverPoint; ++i)
    newBinValue += binary.charAt(i);
    for(int i = crossoverPoint; i != length; ++i)
    newBinValue += binary.charAt(i);
    child = new individual(Integer.parseInt(newBinValue,2),length);
    return child;
    }

    }

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

    package optimisation_GA;

    import java.util.ArrayList;
    import java.util.Collections;
    import java.util.Comparator;

    import javax.script.ScriptEngine;
    import javax.script.ScriptEngineManager;
    import javax.script.ScriptException;
    import javax.swing.JOptionPane;

    public class population {
    int a;
    int b;
    int numberOfPopulation;
    int size;
    int timeLimit;
    int length;
    String function;

    ArrayList<individual> individuals;
    population(String _function,int _a,int _b,int _numberOfPopulation,int _size,int _timeLimit,int _length){
    individuals = new ArrayList<individual>();
    function = _function;
    a = _a;
    b = _b;
    numberOfPopulation = _numberOfPopulation;
    size = _size;
    timeLimit = _timeLimit;
    length = _length;
    initialPopulation();
    }
    private void initialPopulation() {
    // TODO Auto-generated method stub
    for(int i = 0; i != size; ++i){
    int rand = a + (int)(Math.random() * ((b - a) + 1));
    individuals.add(new individual(rand,length));
    }
    }
    public void calculateFitnessFunction(){
    for(int i = 0; i != individuals.size();++i){
    int x = individuals.get(i).decimal;
    String tempValue = function;
    String replaceSt = Integer.toString(x);

    String testValue = tempValue.replace("x", Integer.toString(x));
    ScriptEngineManager mgr = new ScriptEngineManager();
    ScriptEngine engine = mgr.getEngineByName("JavaScript");
    try {
    int y = ((Double)engine.eval(testValue)).intValue();
    individuals.get(i).fitnessFunction = y;
    } catch (ScriptException e1) {
    // TODO Auto-generated catch block

    }
    }
    }
    public void range(){
    Collections.sort(individuals, new Comparator<individual>() {
    public int compare(individual left, individual right) {
    return right.fitnessFunction - left.fitnessFunction;
    }
    });
    for(int i = 0; i != individuals.size();++i)
    System.out.println(individuals.get(i).decimal + " -- " + individuals.get(i).fitnessFunction );
    }
    public void selection() {
    // TODO Auto-generated method stub
    if(individuals.size() == size)
    return;
    while(individuals.size() > size)
    individuals.remove(individuals.size() - 1);

    }
    public void crossover() {
    // TODO Auto-generated method stub
    for(int i = 0; i != size;++i){
    individual child = individuals.get(i).crossover(getRandomIndividual());
    individuals.add(child);
    }

    }
    private individual getRandomIndividual(){
    return individuals.get((int)Math.random()*size);
    }
    public void printP() {
    // TODO Auto-generated method stub
    for(int i = 0; i != individuals.size();++i)
    System.out.println(i + " " + individuals.get(i).decimal + " -- " + individuals.get(i).fitnessFunction );
    }
    }

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

    workingPopulation = new population(functionString,a,b,nPopulation,size,time,length);
    int count = 0;
    long	startTime,
    endTime,
    workTime;
    startTime = System.currentTimeMillis()/1000;
    workingPopulation.calculateFitnessFunction();

    do{
    workingPopulation.selection();
    System.out.println("Selection passed");
    workingPopulation.crossover();
    System.out.println("crossover passed");
    workingPopulation.calculateFitnessFunction();

    workingPopulation.range();
    count++;
    endTime = System.currentTimeMillis()/1000;
    workTime = endTime - startTime;
    System.out.println("-------------------generation #" +count+1);
    workingPopulation.printP();

    }while((workTime < time) &&(count < nPopulation));
    workingPopulation.printP();

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



مطالب مرتبط
ديدگاه خود را ارسال کنيد


۵ دیدگاه رو شما می توانید ببینید
  1. با سلام خدمت شما
    من یک برنامه تشخیص اثر انگشت با سی شارپ میخوام بنویسم.لطفا راهنماییم کنید که برنامه به جه جیزهایی نیاز داره..
    خیلی ممنون

  2. خیلی جالب بود !‌
    بازم چنین مقالاتی منتشر کنید !‌

  3. ممنون از شما مطلب خوبی بود !!! 🙂

  4. باعرض سلا وخسته نباشید خدمت شما
    ببخشید امکان داره الگوریتم اجتماع ذرات یا کلونی موچه را به زبان جاوا در سایت قرار بدهید
    تشکر

محبوب ترين ويدئو هاي انلاين
دوره برنامه نویسی فروشگاه اینترنتی
  • تعداد اعضا 80k
  • قيمت دوره۱۰۰,۰۰۰ تومان
  • امتيازدهي
    1 vote, average: 5٫00 out of 51 vote, average: 5٫00 out of 51 vote, average: 5٫00 out of 51 vote, average: 5٫00 out of 51 vote, average: 5٫00 out of 5( 5٫00 از 1 رای )
    Loading...
دوره آموزشی سیستم ثبت سفارش آنلاین
  • تعداد اعضا 80k
  • قيمت دوره۵۰,۰۰۰ تومان
  • امتيازدهي
    1 vote, average: 5٫00 out of 51 vote, average: 5٫00 out of 51 vote, average: 5٫00 out of 51 vote, average: 5٫00 out of 51 vote, average: 5٫00 out of 5( 5٫00 از 1 رای )
    Loading...
دوره طراحی سیستم مدیریت مشتریان
  • تعداد اعضا 80k
  • قيمت دوره۵۰,۰۰۰ تومان
  • امتيازدهي
    1 vote, average: 5٫00 out of 51 vote, average: 5٫00 out of 51 vote, average: 5٫00 out of 51 vote, average: 5٫00 out of 51 vote, average: 5٫00 out of 5( 5٫00 از 1 رای )
    Loading...