جا مكتوبة في جافا

Question

أحاول كتابة خوارزمية وراثية تستند إلى التقنيات التي التقطتها من كتاب "تقنيات الذكاء الاصطناعى لمبرمجي الألعاب" التي تستخدم اختيارًا ثنائيًا للترميز ولياقة (المعروف أيضًا باسم اختيار عجلة الروليت) على جينات السكان تم إنشاؤه عشوائيًا داخل البرنامج في صفيف ثنائي الأبعاد.

لقد صادفت مؤخرًا قطعة من الرمز الكاذب وحاولت تنفيذها ، ولكن صادفت بعض المشكلات مع تفاصيل ما أحتاج إلى القيام به. لقد راجعت عددًا من الكتب وبعض الشفرة المفتوحة وما زلت أعاني من أجل التقدم. أتفهم أنه يتعين علي الحصول على مجموع اللياقة البدنية للسكان ، واختيار رقم عشوائي بين المبلغ والصفر ، ثم إذا كان الرقم أكبر من الوالدين للكتابة فوقه ، لكنني أواجه تنفيذ هذه الأفكار .

أي مساعدة في تنفيذ هذه الأفكار سيكون موضع تقدير كبير لأن جافا بلدي صدئ.

Answer 1

فيما يلي مخطط كامل لـ GA. لقد حرصت على أن تكون مفصلة للغاية بحيث يمكن ترميزها بسهولة إلى C/Java/Python/..

/* 1. Init population */
POP_SIZE = number of individuals in the population
pop = newPop = []
for i=1 to POP_SIZE {
    pop.add( getRandomIndividual() )
}

/* 2. evaluate current population */
totalFitness = 0
for i=1 to POP_SIZE {
    fitness = pop[i].evaluate()
    totalFitness += fitness
}

while not end_condition (best fitness, #iterations, no improvement...)
{
    // build new population
    // optional: Elitism: copy best K from current pop to newPop
    while newPop.size()<POP_SIZE
    {
        /* 3. roulette wheel selection */
        // select 1st individual
        rnd = getRandomDouble([0,1]) * totalFitness
        for(idx=0; idx<POP_SIZE && rnd>0; idx++) {
            rnd -= pop[idx].fitness
        }
        indiv1 = pop[idx-1]
        // select 2nd individual
        rnd = getRandomDouble([0,1]) * totalFitness
        for(idx=0; idx<POP_SIZE && rnd>0; idx++) {
            rnd -= pop[idx].fitness
        }
        indiv2 = pop[idx-1]

        /* 4. crossover */
        indiv1, indiv2 = crossover(indiv1, indiv2)

        /* 5. mutation */
        indiv1.mutate()
        indiv2.mutate()

        // add to new population
        newPop.add(indiv1)
        newPop.add(indiv2)
    }
    pop = newPop
    newPop = []

    /* re-evaluate current population */
    totalFitness = 0
    for i=1 to POP_SIZE {
        fitness = pop[i].evaluate()
        totalFitness += fitness
    }
}

// return best genome
bestIndividual = pop.bestIndiv()     // max/min fitness indiv

لاحظ أنك تفتقد حاليًا وظيفة اللياقة (يعتمد على المجال). سيكون التقاطع بسيطًا بسيطًا (نظرًا لأنك تستخدم تمثيلًا ثنائيًا). يمكن أن يكون الطفرة قلبًا بسيطًا بشكل عشوائي.

---

تعديل: لقد قمت بتطبيق رمز كاذب أعلاه في Java مع الأخذ في الاعتبار هيكل الرمز الحالي الخاص بك وتدوينه (ضع في اعتبارك أنني أكثر من AC/C ++ Guy من Java). لاحظ أن هذا ليس بأي حال من الأحوال التنفيذ الأكثر كفاءة أو كاملة ، أعترف أنني كتبته بسرعة:

فرد. جافا

import java.util.Random;

public class Individual
{
    public static final int SIZE = 500;
    private int[] genes = new int[SIZE];
    private int fitnessValue;

    public Individual() {}

    public int getFitnessValue() {
        return fitnessValue;
    }

    public void setFitnessValue(int fitnessValue) {
        this.fitnessValue = fitnessValue;
    }

    public int getGene(int index) {
        return genes[index];
    }

    public void setGene(int index, int gene) {
        this.genes[index] = gene;
    }

    public void randGenes() {
        Random rand = new Random();
        for(int i=0; i<SIZE; ++i) {
            this.setGene(i, rand.nextInt(2));
        }
    }

    public void mutate() {
        Random rand = new Random();
        int index = rand.nextInt(SIZE);
        this.setGene(index, 1-this.getGene(index));    // flip
    }

    public int evaluate() {
        int fitness = 0;
        for(int i=0; i<SIZE; ++i) {
            fitness += this.getGene(i);
        }
        this.setFitnessValue(fitness);

        return fitness;
    }
}

السكان

import java.util.Random;

public class Population
{
    final static int ELITISM_K = 5;
    final static int POP_SIZE = 200 + ELITISM_K;  // population size
    final static int MAX_ITER = 2000;             // max number of iterations
    final static double MUTATION_RATE = 0.05;     // probability of mutation
    final static double CROSSOVER_RATE = 0.7;     // probability of crossover

    private static Random m_rand = new Random();  // random-number generator
    private Individual[] m_population;
    private double totalFitness;

    public Population() {
        m_population = new Individual[POP_SIZE];

        // init population
        for (int i = 0; i < POP_SIZE; i++) {
            m_population[i] = new Individual();
            m_population[i].randGenes();
        }

        // evaluate current population
        this.evaluate();
    }

    public void setPopulation(Individual[] newPop) {
        // this.m_population = newPop;
        System.arraycopy(newPop, 0, this.m_population, 0, POP_SIZE);
    }

    public Individual[] getPopulation() {
        return this.m_population;
    }

    public double evaluate() {
        this.totalFitness = 0.0;
        for (int i = 0; i < POP_SIZE; i++) {
            this.totalFitness += m_population[i].evaluate();
        }
        return this.totalFitness;
    }

    public Individual rouletteWheelSelection() {
        double randNum = m_rand.nextDouble() * this.totalFitness;
        int idx;
        for (idx=0; idx<POP_SIZE && randNum>0; ++idx) {
            randNum -= m_population[idx].getFitnessValue();
        }
        return m_population[idx-1];
    }

    public Individual findBestIndividual() {
        int idxMax = 0, idxMin = 0;
        double currentMax = 0.0;
        double currentMin = 1.0;
        double currentVal;

        for (int idx=0; idx<POP_SIZE; ++idx) {
            currentVal = m_population[idx].getFitnessValue();
            if (currentMax < currentMin) {
                currentMax = currentMin = currentVal;
                idxMax = idxMin = idx;
            }
            if (currentVal > currentMax) {
                currentMax = currentVal;
                idxMax = idx;
            }
            if (currentVal < currentMin) {
                currentMin = currentVal;
                idxMin = idx;
            }
        }

        //return m_population[idxMin];      // minimization
        return m_population[idxMax];        // maximization
    }

    public static Individual[] crossover(Individual indiv1,Individual indiv2) {
        Individual[] newIndiv = new Individual[2];
        newIndiv[0] = new Individual();
        newIndiv[1] = new Individual();

        int randPoint = m_rand.nextInt(Individual.SIZE);
        int i;
        for (i=0; i<randPoint; ++i) {
            newIndiv[0].setGene(i, indiv1.getGene(i));
            newIndiv[1].setGene(i, indiv2.getGene(i));
        }
        for (; i<Individual.SIZE; ++i) {
            newIndiv[0].setGene(i, indiv2.getGene(i));
            newIndiv[1].setGene(i, indiv1.getGene(i));
        }

        return newIndiv;
    }


    public static void main(String[] args) {
        Population pop = new Population();
        Individual[] newPop = new Individual[POP_SIZE];
        Individual[] indiv = new Individual[2];

        // current population
        System.out.print("Total Fitness = " + pop.totalFitness);
        System.out.println(" ; Best Fitness = " + 
            pop.findBestIndividual().getFitnessValue());

        // main loop
        int count;
        for (int iter = 0; iter < MAX_ITER; iter++) {
            count = 0;

            // Elitism
            for (int i=0; i<ELITISM_K; ++i) {
                newPop[count] = pop.findBestIndividual();
                count++;
            }

            // build new Population
            while (count < POP_SIZE) {
                // Selection
                indiv[0] = pop.rouletteWheelSelection();
                indiv[1] = pop.rouletteWheelSelection();

                // Crossover
                if ( m_rand.nextDouble() < CROSSOVER_RATE ) {
                    indiv = crossover(indiv[0], indiv[1]);
                }

                // Mutation
                if ( m_rand.nextDouble() < MUTATION_RATE ) {
                    indiv[0].mutate();
                }
                if ( m_rand.nextDouble() < MUTATION_RATE ) {
                    indiv[1].mutate();
                }

                // add to new population
                newPop[count] = indiv[0];
                newPop[count+1] = indiv[1];
                count += 2;
            }
            pop.setPopulation(newPop);

            // reevaluate current population
            pop.evaluate();
            System.out.print("Total Fitness = " + pop.totalFitness);
            System.out.println(" ; Best Fitness = " +
                pop.findBestIndividual().getFitnessValue()); 
        }

        // best indiv
        Individual bestIndiv = pop.findBestIndividual();
    }
}

Answer 2

لماذا لا تستخدم إطار عمل مفتوح المصدر مثل JGAP: http://jgap.sf.net

Answer 3

لقد قمت بتطبيق هذه الخوارزمية من خلال إنشاء "صفيف اللياقة التراكمي" و بحث ثنائي, ، هكذا تقليل الحاجة إلى التكرار من خلال كل عنصر في المصفوفة أثناء الاختيار:

1. لحجم السكان n إنشاء مجموعة اللياقة التراكمية: ARR [n].
2. تعيين ARR [0]: = computefitness (فردي [0]).
3. ثم ، لكل عنصر لاحق: x ، arr [x] = arr [x-1] + computefitness (الفردية [x]).
4. قم بإنشاء رقم عشوائي بين 0 و ARR [n] (أي الكلي اللياقة).
5. استخدم بحثًا ثنائيًا (على سبيل المثال collections.binarySearch) لتحديد موقع الفهرس المناسب في صفيف اللياقة التراكمي ، واستخدم هذا الفهرس لتحديد الفرد.

لاحظ أنك تحتاج فقط إلى إنشاء مجموعة اللياقة البدنية في بداية مرحلة التكاثر ، ومن ثم يمكنك إعادة استخدامها عدة مرات لإجراء اختيارات في س (سجل ن) الوقت.

جانبا ، لاحظ أن اختيار البطولة أسهل بكثير في التنفيذ!

Answer 4

يسمى المفهوم الذي تبحث عنه "اختيار عجلة الروليت". ليس لديك وظيفة لياقة راسخة حتى الآن (قد تعني أن اللياقة البدنية لكل فرد هي القيمة المتكاملة للكروموسوم) ، ولكن عندما تقوم بخطة عامة هي:

1. جمع اللياقة البدنية من السكان.
2. احصل على رقم عشوائي (اتصل به X) بين 0 و Total Fitness.
3. تكرار من خلال السكان. لكل عضو:
   1. طرح لياقة العضو من X.
   2. إذا كان X الآن أقل أو يساوي الصفر ، فحدد العضو الحالي.

هناك تطبيقات مكافئة أخرى ، لكن الفكرة العامة هي اختيار الأعضاء ذوي الاحتمال المتناسب مع لياقتهم.

تحرير: بعض الملاحظات على وظائف اللياقة. إن تمثيل الكروموسوم (في حالتك كعدد صحيح 32 بت) مستقل عن وظيفة اللياقة المستخدمة لتقييمها. على سبيل المثال ، تعامل الترميزات الثنائية عادة الكروموسوم كمجموعة من حقول Bitfileds معبأة في قيمة متكاملة ذات الحجم المناسب. يمكن بعد ذلك تحقيق التقاطع والطفرة من خلال عمليات تخزين البتات المناسبة. إذا كنت مهتمًا ، فيمكنني نشر بعض رمز GA البسيط الذي أضعه (في C و Python) والذي يستخدم عمليات bitwise لتنفيذ هذه الوظائف. لست متأكدًا من مدى ارتياحك لهذه اللغات.

Answer 5

لقد قمت بتنفيذ قابلة للتمديد في Java ، حيث يتم تعريف المشغلين والهيكل الفردي جيدًا من خلال الواجهات التي تعمل معًا. جيثب ريبو هنا https://github.com/juanmf/ga

لديها تنفيذ قياسي لكل مشغل ، وتنفيذ مشكلة مثال مع بنية فردية/سكانية معينة ومقياس اللياقة البدنية. يتمثل تطبيق المشكلة في العثور على فريق كرة قدم جيد مع لاعبين من بين 20 فريقًا وتقييد الميزانية.

لتكييفها مع مشكلتك الحالية ، تحتاج إلى توفير تطبيقات لهذه الواجهات:

juanmf.ga.structure.Gen;
juanmf.ga.structure.Individual;
juanmf.ga.structure.IndividualFactory; 
juanmf.ga.structure.Population;  // Has a basic implementation already
juanmf.ga.structure.PopulationFactory;

في pkg juanmf.grandt لديك مثال فئات تنفيذ مشكلة ، وكيفية نشرها ، كما هو موضح في مقتطف الكود أدناه.

لنشر التطبيقات ، عليك فقط إرجاع الفصول المناسبة من حبوب الربيع هذه:

/**
 * Make sure @ComponentScan("pkg") in juanmf.ga.App.java includes this class' pkg 
 * so that these beans get registered.
 */
@Configuration
public class Config {

    @Bean(name="individualFactory")
    public IndividualFactory getIndividualFactory() {
        return new Team.TeamFactory();
    }

    @Bean(name="populationFactory")
    public PopulationFactory getPopulationFactory() {
        return new Team.TeamPopulationFactory();
    }

    @Bean(name="fitnessMeter")
    public FitnessMeter getFitnessMeter() {
        return new TeamAptitudeMeter();
    }
} 

لدى Crosser Operator تطبيقين لنفس التقنية ، واحدة متتابعة وواحدة واحدة تتفوق على التسلسل إلى حد بعيد.

يمكن تحديد حالة التوقف. إذا لم يتم إعطاء أي منها ، فإنه يحتوي على حالة إيقاف افتراضي تتوقف بعد 100 جيل بدون تحسينات (يجب أن تكون حذراً هنا مع النخبوي ، وليس لتفقد أفضل ما في كل جيل لدفع شرط التوقف هذا بفعالية).

لذلك إذا كان أي شخص على استعداد لتجربته ، سأكون سعيدًا للمساعدة. أي شخص مرحب به لتقديم الاقتراحات ، وأفضل تطبيقات للمشغل: D أو أي طلب سحب.

Answer 6

يجب أن تساعد هذه الأسئلة الأخرى حول اختيار عجلة الروليت:

• خوارزمية اختيار عجلة الروليت
• اختيار الروليت في الخوارزميات الوراثية

في الأول ، لقد حاولت أن أشرح كيف تعمل عجلة الروليت. في الثانية ، قدم Jarod Elliott بعض الرمز الكاذب. مدموج مع وصف آدمسكي للتنفيذ الفعال, ، يجب أن تكون هذه كافية للحصول على شيء يعمل.

Answer 7

مجرد نقطة تستحق الذكر. لن يعمل اختيار عجلة الروليت (كما هو موضح في الكود الزائف) لمشاكل التقليل - ومع ذلك ، فهو صالح لمشاكل التعظيم.

نظرًا للطريقة التي يتم بها اختيار الفرد الأكثر ملاءمة ، لن تكون حالة التقليل. يتم توفير التفاصيل في: الذكاء الحسابي: الطبعة الثانية