遺傳算法

遺傳算法(Genetic Algorithm)是一種模擬自然界的進(jìn)化規(guī)律-優(yōu)勝劣汰演化來的隨機(jī)搜索算法，其在解決多種約束條件下的最優(yōu)解這類問題上具有優(yōu)秀的表現(xiàn).

1. 基本概念

在遺傳算法中有幾個(gè)基本的概念：基因、個(gè)體、種群和進(jìn)化.基因是個(gè)體的表現(xiàn)，不同個(gè)體的基因序列不同；個(gè)體是指單個(gè)的生命，個(gè)體是組成種群的基礎(chǔ)；而進(jìn)化的基本單位是種群，一個(gè)種群里面有多個(gè)個(gè)體；進(jìn)化是指一個(gè)種群進(jìn)過優(yōu)勝劣汰的自然選擇后，產(chǎn)生一個(gè)新的種群的過程，理論上進(jìn)化會(huì)產(chǎn)生更優(yōu)秀的種群.

2. 算法流程

一個(gè)傳統(tǒng)的遺傳算法由以下幾個(gè)組成部分：

• 初始化. 隨機(jī)生成一個(gè)規(guī)模為N的種群，設(shè)置最大進(jìn)化次數(shù)以及停止進(jìn)化條件.
• 計(jì)算適應(yīng)度. 適應(yīng)度被用來評(píng)價(jià)個(gè)體的質(zhì)量，且適應(yīng)度是唯一評(píng)判因子.計(jì)算種群中每個(gè)個(gè)體的適應(yīng)度，得到最優(yōu)秀的個(gè)體.
• 選擇. 選擇是用來得到一些優(yōu)秀的個(gè)體來產(chǎn)生下一代.選擇算法的好壞至關(guān)重要，因?yàn)樵谝欢ǔ潭壬线x擇會(huì)影響種群的進(jìn)化方向.常用的選擇算法有：隨機(jī)抽取、競(jìng)標(biāo)賽選擇以及輪盤賭模擬法等等.
• 交叉. 交叉是兩個(gè)個(gè)體繁衍下一代的過程，實(shí)際上是子代獲取父親和母親的部分基因，即基因重組.常用的交叉方法有：?jiǎn)吸c(diǎn)交叉、多點(diǎn)交叉等.
• 變異. 變異即模擬突變過程.通過變異，種群中個(gè)體變得多樣化.但是變異是有一個(gè)概率的.

經(jīng)典的遺傳算法的流程圖如下所示：

3. java實(shí)現(xiàn)

為了防止進(jìn)化方向出現(xiàn)偏差，在本算法中采用精英主義，即每次進(jìn)化都保留上一代種群中最優(yōu)秀的個(gè)體。

• 個(gè)體適應(yīng)度：通過比較個(gè)體與期望值的相同位置上的基因，相同則適應(yīng)度加1
• 選擇策略：隨機(jī)產(chǎn)生一個(gè)淘汰數(shù)組，選擇淘汰數(shù)組中的最優(yōu)秀個(gè)體作為選擇結(jié)果，即模擬優(yōu)勝劣汰的過程
• 交叉策略：對(duì)于個(gè)體的每個(gè)基因，產(chǎn)生一個(gè)隨機(jī)數(shù)，如果隨機(jī)數(shù)小于交叉概率，則繼承父親該位置的基因，否則繼承母親的該位置的基因
• 變異策略：個(gè)體的基因序列上的每個(gè)基因都有變異的機(jī)會(huì)，如果隨機(jī)概率大于變異概率，則進(jìn)行基因突變，本例中的突變策略是：隨機(jī)產(chǎn)生一個(gè)0或者1

計(jì)算適應(yīng)度

/**
 * 通過和solution比較 ，計(jì)算個(gè)體的適應(yīng)值
 * @param individual 待比較的個(gè)體
 * @return  返回適應(yīng)度
 */
public static int getFitness(Individual individual) {
    int fitness = 0;
    for (int i = 0; i < individual.size() && i < solution.length; i++) {
        if (individual.getGene(i) == solution[i]) {
            fitness++;
        }
    }
    return fitness;
}

選擇算子

/**
 * 隨機(jī)選擇一個(gè)較優(yōu)秀的個(gè)體。用于進(jìn)行交叉
 * @param pop 種群
 * @return
 */
private static Individual tournamentSelection(Population pop) {
    Population tournamentPop = new Population(tournamentSize, false);
    // 隨機(jī)選擇 tournamentSize 個(gè)放入 tournamentPop 中
    for (int i = 0; i < tournamentSize; i++) {
        int randomId = (int) (Math.random() * pop.size());
        tournamentPop.saveIndividual(i, pop.getIndividual(randomId));
    }
    // 找到淘汰數(shù)組中最優(yōu)秀的
    Individual fittest = tournamentPop.getFittest();
    return fittest;
}

交叉算子

/**
 * 兩個(gè)個(gè)體交叉產(chǎn)生下一代
 * @param indiv1 父親
 * @param indiv2 母親
 * @return 后代
 */
private static Individual crossover(Individual indiv1, Individual indiv2) {
    Individual newSol = new Individual();
    // 隨機(jī)的從兩個(gè)個(gè)體中選擇
    for (int i = 0; i < indiv1.size(); i++) {
        if (Math.random() <= uniformRate) {
            newSol.setGene(i, indiv1.getGene(i));
        } else {
            newSol.setGene(i, indiv2.getGene(i));
        }
    }
    return newSol;
}

變異算子

/**
 * 突變個(gè)體。突變的概率為 mutationRate
 * @param indiv 待突變的個(gè)體
 */
private static void mutate(Individual indiv) {
    for (int i = 0; i < indiv.size(); i++) {
        if (Math.random() <= mutationRate) {
            // 生成隨機(jī)的 0 或 1
            byte gene = (byte) Math.round(Math.random());
            indiv.setGene(i, gene);
        }
    }
}

4. 測(cè)試結(jié)果

測(cè)試結(jié)果如下圖

遺傳算法與自動(dòng)組卷

隨著軟件和硬件技術(shù)的發(fā)展，在線考試系統(tǒng)正在逐漸取代傳統(tǒng)的線下筆試。對(duì)于一個(gè)在線考試系統(tǒng)而言，考試試卷的質(zhì)量很大程度上代表著該系統(tǒng)的質(zhì)量，試卷是否包含足夠多的題型、是否包含指定的知識(shí)點(diǎn)以及試卷整體的難度系數(shù)是否合適等等，這些都能作為評(píng)價(jià)一個(gè)在線測(cè)評(píng)系統(tǒng)的指標(biāo).如果單純的根據(jù)組卷規(guī)則直接從數(shù)據(jù)庫(kù)中獲取一定數(shù)量的試題組成一套試卷，由于只獲取一次，并不能保證這樣的組卷結(jié)果是一個(gè)合適的結(jié)果，而且可以肯定的是，這樣得到的結(jié)果基本不會(huì)是一個(gè)優(yōu)秀的解.顯而易見，我們需要一個(gè)優(yōu)秀的自動(dòng)組卷算法，遺傳算法就非常適合解決自動(dòng)組卷的問題，其具有自進(jìn)化、并行執(zhí)行等特點(diǎn)

1. 對(duì)遺傳算法的改進(jìn)

使用傳統(tǒng)的遺傳算法進(jìn)行組卷時(shí)會(huì)出現(xiàn)一些偏差，進(jìn)化的結(jié)果不是非常理想.具體表現(xiàn)為：進(jìn)化方向出現(xiàn)偏差、搜索后期效率低、容易陷入局部最優(yōu)解等問題.針對(duì)這些問題，本系統(tǒng)對(duì)傳統(tǒng)的遺傳算法做了一些改進(jìn)，具體表現(xiàn)為：使用精英主義模式(即每次進(jìn)化都保留上一代種群的最優(yōu)解)、實(shí)數(shù)編碼以及選擇算子的優(yōu)化.

1.1 染色體編碼方式的改進(jìn)

染色體編碼是遺傳算法首先要解決的問題，是將個(gè)體的特征抽象為一套編碼方案.在傳統(tǒng)的遺傳算法解決方案中，二進(jìn)制編碼使用的最多，就本系統(tǒng)而言，二進(jìn)制編碼形成的基因序列為整個(gè)題庫(kù)，這種方案不是很合適，因?yàn)槎M(jìn)制編碼按照題庫(kù)中試題的相對(duì)順序?qū)㈩}庫(kù)編碼成一個(gè)01字符串，1代表試題出現(xiàn)，0代表沒有顯然這樣的編碼規(guī)模太大，對(duì)于一個(gè)優(yōu)秀的題庫(kù)而言，十萬的試題總量是很常見的，對(duì)于一個(gè)長(zhǎng)度為十萬的字符串進(jìn)行編碼和解碼顯然太繁瑣. 經(jīng)過查閱資料，于是決定采用實(shí)數(shù)編碼作為替代，將試題的id作為基因，試卷和染色體建立映射關(guān)系，同一類型的試題放在一起.比如，要組一套java考試試卷，題目總數(shù)為15：填空3道，單選10道，主觀題2道.那么進(jìn)行實(shí)數(shù)編碼后，其基因序列分布表現(xiàn)為：

1.2 初始化種群設(shè)計(jì)

初始化試卷時(shí)不采取完全隨機(jī)的方式.通過分析不難發(fā)現(xiàn)，組卷主要有題型、數(shù)量、總分、知識(shí)點(diǎn)和難度系數(shù)這五個(gè)約束條件，在初始化種群的時(shí)候，我們可以根據(jù)組卷規(guī)則隨機(jī)產(chǎn)生指定數(shù)量的題型，這樣在一開始種群中的個(gè)體就滿足了題型、數(shù)量和總分的約束，使約束條件從5個(gè)減少為2個(gè)：知識(shí)點(diǎn)和難度系數(shù).這樣算法的迭代次數(shù)被減少，收斂也將加快.

1.3 適應(yīng)度函數(shù)設(shè)計(jì)

在遺傳算法中，適應(yīng)度是評(píng)價(jià)種群中個(gè)體的優(yōu)劣的唯一指標(biāo)，適應(yīng)度可以影響種群的進(jìn)化方向.由于在初始化時(shí)，種群中個(gè)體已經(jīng)滿足了題型、數(shù)量和總分這三個(gè)約束條件，所以個(gè)體的適應(yīng)度只與知識(shí)點(diǎn)和難度系數(shù)有關(guān).

試卷的難度系數(shù)計(jì)算公式為：

n是組卷規(guī)則要求的題目總數(shù)，Ti，Ki分別是第i題的難度系數(shù)和分?jǐn)?shù).

本例中使用知識(shí)點(diǎn)覆蓋率來評(píng)價(jià)知識(shí)點(diǎn).即一套試卷要求包含N個(gè)知識(shí)點(diǎn)，而某個(gè)體中包含的知識(shí)點(diǎn)數(shù)目為M(去重后的結(jié)果，M<=N)，那么該個(gè)體的知識(shí)點(diǎn)覆蓋率為：M/N. 因此，適應(yīng)度函數(shù)為：

其中，M/N為知識(shí)點(diǎn)覆蓋率；EP為用戶輸入的整體期望難度，P為整體實(shí)際難度；知識(shí)點(diǎn)權(quán)重用t1表示，難度系數(shù)權(quán)重用t2表示.

1.4 選擇算子與交叉算子的改進(jìn)

本例中的選擇策略為：指定一個(gè)淘汰數(shù)組的大小(筆者使用的是5)，從原種群中隨機(jī)挑選個(gè)體組成一個(gè)淘汰種群，將淘汰種群中的最優(yōu)個(gè)體作為選擇算子的結(jié)果.

交叉算子實(shí)際上是染色體的重組.本系統(tǒng)中采用的交叉策略為：在(0,N)之間隨機(jī)產(chǎn)生兩個(gè)整數(shù)n1，n2，父親基因序列上n1到n2之間的基因全部遺傳給子代，母親基因序列上的n1到n2之外的基因遺傳給子代，但是要確?；虿恢貜?fù)，如果出現(xiàn)重復(fù)(實(shí)驗(yàn)證明有較大的概率出現(xiàn)重復(fù))，那么從題庫(kù)中挑選一道與重復(fù)題的題型相同、分值相同且包含的知識(shí)點(diǎn)相同的試題遺傳給子代.所有的遺傳都要保證基因在染色體上的相對(duì)位置不變.

1.5 變異算子的改進(jìn)

基因變異的出現(xiàn)增加了種群的多樣性.在本系統(tǒng)中，每個(gè)個(gè)體的每個(gè)基因都有變異的機(jī)會(huì)，如果隨機(jī)概率小于變異概率，那么基因就可以突變.突變基因的原則為：與原題的同題型、同分?jǐn)?shù)且同知識(shí)點(diǎn)的試題.有研究表明，對(duì)于變異概率的選擇，在0.1-0.001之間最佳，本例中選取了0.085作為變異概率.

1.6 組卷規(guī)則

組卷規(guī)則是初始化種群的依賴。組卷規(guī)則由用戶指定，規(guī)定了用戶期望的試卷的條件：試卷總分、包含的題型與數(shù)量、期望難度系數(shù)、期望覆蓋的知識(shí)點(diǎn)。在本例中將組卷規(guī)則封裝為一個(gè)JavaBean

2. java實(shí)現(xiàn)

2.1 試卷個(gè)體

個(gè)體，即試卷.本例中將試卷個(gè)體抽象成一個(gè)JavaBean，其有id，適應(yīng)度、知識(shí)點(diǎn)覆蓋率、難度系數(shù)、總分、以及個(gè)體包含的試題集合這6個(gè)屬性，以及計(jì)算知識(shí)點(diǎn)覆蓋率和適應(yīng)度這幾個(gè)方法.在計(jì)算適應(yīng)度的時(shí)候，知識(shí)點(diǎn)權(quán)重為0.20，難度系數(shù)權(quán)重為0.80.

/**
 * 計(jì)算試卷總分
 *
 * @return
 */
public double getTotalScore() {
    if (totalScore == 0) {
        double total = 0;
        for (QuestionBean question : questionList) {
            total += question.getScore();
        }
        totalScore = total;
    }
    return totalScore;
}

/**
 * 計(jì)算試卷個(gè)體難度系數(shù) 計(jì)算公式： 每題難度*分?jǐn)?shù)求和除總分
 *
 * @return
 */
public double getDifficulty() {
    if (difficulty == 0) {
        double _difficulty = 0;
        for (QuestionBean question : questionList) {
            _difficulty += question.getScore() * question.getDifficulty();
        }
        difficulty = _difficulty / getTotalScore();
    }
    return difficulty;
}
 /**
     * 計(jì)算知識(shí)點(diǎn)覆蓋率 公式為：個(gè)體包含的知識(shí)點(diǎn)/期望包含的知識(shí)點(diǎn)
     *
     * @param rule
     */
    public void setKpCoverage(RuleBean rule) {
        if (kPCoverage == 0) {
            Set<String> result = new HashSet<String>();
            result.addAll(rule.getPointIds());
            Set<String> another = questionList.stream().map(questionBean -> String.valueOf(questionBean.getPointId())).collect(Collectors.toSet());
            // 交集操作
            result.retainAll(another);
            kPCoverage = result.size() / rule.getPointIds().size();
        }
    }

/**
 * 計(jì)算個(gè)體適應(yīng)度 公式為：f=1-(1-M/N)*f1-|EP-P|*f2
 * 其中M/N為知識(shí)點(diǎn)覆蓋率，EP為期望難度系數(shù)，P為種群個(gè)體難度系數(shù)，f1為知識(shí)點(diǎn)分布的權(quán)重
 * ，f2為難度系數(shù)所占權(quán)重。當(dāng)f1=0時(shí)退化為只限制試題難度系數(shù)，當(dāng)f2=0時(shí)退化為只限制知識(shí)點(diǎn)分布
 *
 * @param rule 組卷規(guī)則
 * @param f1   知識(shí)點(diǎn)分布的權(quán)重
 * @param f2   難度系數(shù)的權(quán)重
 */
public void setAdaptationDegree(RuleBean rule, double f1, double f2) {
    if (adaptationDegree == 0) {
        adaptationDegree = 1 - (1 - getkPCoverage()) * f1 - Math.abs(rule.getDifficulty() - getDifficulty()) * f2;
    }
}

public boolean containsQuestion(QuestionBean question) {
    if (question == null) {
        for (int i = 0; i < questionList.size(); i++) {
            if (questionList.get(i) == null) {
                return true;
            }
        }
    } else {
        for (QuestionBean aQuestionList : questionList) {
            if (aQuestionList != null) {
                if (aQuestionList.equals(question)) {
                    return true;
                }
            }
        }
    }
    return false;
}

2.2 種群初始化

種群初始化。將種群抽象為一個(gè)Java類Population，其有初始化種群、獲取最優(yōu)個(gè)體的方法，關(guān)鍵代碼如下

/**
 * 初始種群
 *
 * @param populationSize 種群規(guī)模
 * @param initFlag       初始化標(biāo)志 true-初始化
 * @param rule           規(guī)則bean
 */
public Population(int populationSize, boolean initFlag, RuleBean rule) {
    papers = new Paper[populationSize];
    if (initFlag) {
        Paper paper;
        Random random = new Random();
        for (int i = 0; i < populationSize; i++) {
            paper = new Paper();
            paper.setId(i + 1);
            while (paper.getTotalScore() != rule.getTotalMark()) {
                paper.getQuestionList().clear();
                String idString = rule.getPointIds().toString();
                // 單選題
                if (rule.getSingleNum() > 0) {
                    generateQuestion(1, random, rule.getSingleNum(), rule.getSingleScore(), idString,
                            "單選題數(shù)量不夠，組卷失敗", paper);
                }
                // 填空題
                if (rule.getCompleteNum() > 0) {
                    generateQuestion(2, random, rule.getCompleteNum(), rule.getCompleteScore(), idString,
                            "填空題數(shù)量不夠，組卷失敗", paper);
                }
                // 主觀題
                if (rule.getSubjectiveNum() > 0) {
                    generateQuestion(3, random, rule.getSubjectiveNum(), rule.getSubjectiveScore(), idString,
                            "主觀題數(shù)量不夠，組卷失敗", paper);
                }
            }
            // 計(jì)算試卷知識(shí)點(diǎn)覆蓋率
            paper.setKpCoverage(rule);
            // 計(jì)算試卷適應(yīng)度
            paper.setAdaptationDegree(rule, Global.KP_WEIGHT, Global.DIFFCULTY_WEIGHt);
            papers[i] = paper;
        }
    }
}

private void generateQuestion(int type, Random random, int qustionNum, double score, String idString,
                              String errorMsg, Paper paper) {
    QuestionBean[] singleArray = QuestionService.getQuestionArray(type, idString
            .substring(1, idString.indexOf("]")));
    if (singleArray.length < qustionNum) {
        log.error(errorMsg);
        return;
    }
    QuestionBean tmpQuestion;
    for (int j = 0; j < qustionNum; j++) {
        int index = random.nextInt(singleArray.length - j);
        // 初始化分?jǐn)?shù)
        singleArray[index].setScore(score);
        paper.addQuestion(singleArray[index]);
        // 保證不會(huì)重復(fù)添加試題
        tmpQuestion = singleArray[singleArray.length - j - 1];
        singleArray[singleArray.length - j - 1] = singleArray[index];
        singleArray[index] = tmpQuestion;
    }
}

2.3 選擇算子與交叉算子的實(shí)現(xiàn)

選擇算子的實(shí)現(xiàn)：

/**
 * 選擇算子
 *
 * @param population
 */
private static Paper select(Population population) {
    Population pop = new Population(tournamentSize);
    for (int i = 0; i < tournamentSize; i++) {
        pop.setPaper(i, population.getPaper((int) (Math.random() * population.getLength())));
    }
    return pop.getFitness();
}

交叉算子的實(shí)現(xiàn).本系統(tǒng)實(shí)現(xiàn)的算子為兩點(diǎn)交叉，在算法的實(shí)現(xiàn)過程中需要保證子代中不出現(xiàn)相同的試題.關(guān)鍵代碼如下：

/**
 * 交叉算子
 *
 * @param parent1
 * @param parent2
 * @return
 */
public static Paper crossover(Paper parent1, Paper parent2, RuleBean rule) {
    Paper child = new Paper(parent1.getQuestionSize());
    int s1 = (int) (Math.random() * parent1.getQuestionSize());
    int s2 = (int) (Math.random() * parent1.getQuestionSize());

    // parent1的startPos endPos之間的序列，會(huì)被遺傳到下一代
    int startPos = s1 < s2 ? s1 : s2;
    int endPos = s1 > s2 ? s1 : s2;
    for (int i = startPos; i < endPos; i++) {
        child.saveQuestion(i, parent1.getQuestion(i));
    }

    // 繼承parent2中未被child繼承的question
    // 防止出現(xiàn)重復(fù)的元素
    String idString = rule.getPointIds().toString();
    for (int i = 0; i < startPos; i++) {
        if (!child.containsQuestion(parent2.getQuestion(i))) {
            child.saveQuestion(i, parent2.getQuestion(i));
        } else {
            int type = getTypeByIndex(i, rule);
            QuestionBean[] singleArray = QuestionService.getQuestionArray(type, idString.substring(1, idString
                    .indexOf("]")));
            child.saveQuestion(i, singleArray[(int) (Math.random() * singleArray.length)]);
        }
    }
    for (int i = endPos; i < parent2.getQuestionSize(); i++) {
        if (!child.containsQuestion(parent2.getQuestion(i))) {
            child.saveQuestion(i, parent2.getQuestion(i));
        } else {
            int type = getTypeByIndex(i, rule);
            QuestionBean[] singleArray = QuestionService.getQuestionArray(type, idString.substring(1, idString
                    .indexOf("]")));
            child.saveQuestion(i, singleArray[(int) (Math.random() * singleArray.length)]);
        }
    }

    return child;
}

2.4 變異算子的實(shí)現(xiàn)

本系統(tǒng)中變異概率為0.085，對(duì)種群的每個(gè)個(gè)體的每個(gè)基因都有變異機(jī)會(huì).變異策略為：在(0,1)之間產(chǎn)生一個(gè)隨機(jī)數(shù)，如果小于變異概率，那么該基因突變.關(guān)鍵代碼如下：

/**
 * 突變算子 每個(gè)個(gè)體的每個(gè)基因都有可能突變
 *
 * @param paper
 */
public static void mutate(Paper paper) {
    QuestionBean tmpQuestion;
    List<QuestionBean> list;
    int index;
    for (int i = 0; i < paper.getQuestionSize(); i++) {
        if (Math.random() < mutationRate) {
            // 進(jìn)行突變，第i道
            tmpQuestion = paper.getQuestion(i);
            // 從題庫(kù)中獲取和變異的題目類型一樣分?jǐn)?shù)相同的題目（不包含變異題目）
            list = QuestionService.getQuestionListWithOutSId(tmpQuestion);
            if (list.size() > 0) {
                // 隨機(jī)獲取一道
                index = (int) (Math.random() * list.size());
                // 設(shè)置分?jǐn)?shù)
                list.get(index).setScore(tmpQuestion.getScore());
                paper.saveQuestion(i, list.get(index));
            }
        }
    }
}

2.5 進(jìn)化的整體流程

本系統(tǒng)中采用精英策略，每次進(jìn)化都保留上一代最優(yōu)秀個(gè)體.這樣就能避免種群進(jìn)化方向發(fā)生變化，出現(xiàn)適應(yīng)度倒退的情況.關(guān)鍵代碼如下：

// 進(jìn)化種群
public static Population evolvePopulation(Population pop, RuleBean rule) {
    Population newPopulation = new Population(pop.getLength());
    int elitismOffset;
    // 精英主義
    if (elitism) {
        elitismOffset = 1;
        // 保留上一代最優(yōu)秀個(gè)體
        Paper fitness = pop.getFitness();
        fitness.setId(0);
        newPopulation.setPaper(0, fitness);
    }
    // 種群交叉操作，從當(dāng)前的種群pop 來 創(chuàng)建下一代種群 newPopulation
    for (int i = elitismOffset; i < newPopulation.getLength(); i++) {
        // 較優(yōu)選擇parent
        Paper parent1 = select(pop);
        Paper parent2 = select(pop);
        while (parent2.getId() == parent1.getId()) {
            parent2 = select(pop);
        }
        // 交叉
        Paper child = crossover(parent1, parent2, rule);
        child.setId(i);
        newPopulation.setPaper(i, child);
    }
    // 種群變異操作
    Paper tmpPaper;
    for (int i = elitismOffset; i < newPopulation.getLength(); i++) {
        tmpPaper = newPopulation.getPaper(i);
        mutate(tmpPaper);
        // 計(jì)算知識(shí)點(diǎn)覆蓋率與適應(yīng)度
        tmpPaper.setKpCoverage(rule);
        tmpPaper.setAdaptationDegree(rule, Global.KP_WEIGHT, Global.DIFFCULTY_WEIGHt);
    }
    return newPopulation;
}

3. 測(cè)試結(jié)果

組卷規(guī)則為：期望試卷難度系數(shù)0.82，共100分，20道選擇題，2分一道，10道填空題，2分一道，4道主觀題，10分一道，要求囊括6個(gè)知識(shí)點(diǎn).
外在的條件為：題庫(kù)試題總量為10950，期望適應(yīng)度值為0.98，種群最多迭代100次.
測(cè)試代碼如下：

/**
 * 組卷過程
 *
 * @param rule
 * @return
 */
public static Paper generatePaper(RuleBean rule) {
    Paper resultPaper = null;
    // 迭代計(jì)數(shù)器
    int count = 0;
    int runCount = 100;
    // 適應(yīng)度期望值z(mì)
    double expand = 0.98;
    if (rule != null) {
        // 初始化種群
        Population population = new Population(20, true, rule);
        System.out.println("初次適應(yīng)度  " + population.getFitness().getAdaptationDegree());
        while (count < runCount && population.getFitness().getAdaptationDegree() < expand) {
            count++;
            population = GA.evolvePopulation(population, rule);
            System.out.println("第 " + count + " 次進(jìn)化，適應(yīng)度為： " + population.getFitness().getAdaptationDegree());
        }
        System.out.println("進(jìn)化次數(shù)： " + count);
        System.out.println(population.getFitness().getAdaptationDegree());
        resultPaper = population.getFitness();
    }
    return resultPaper;
}

測(cè)試結(jié)果如下：

可以看到改進(jìn)后的遺傳算法具有較好的表現(xiàn)

參考資料

1. 實(shí)例講解遺傳算法——基于遺傳算法的自動(dòng)組卷系統(tǒng)【理論篇】
2. 遺傳算法-入門(demo java)

本文中的完整代碼可在github上下載.
你可以通過jslinxiaoli@foxmail.com聯(lián)系我.
歡迎在github或者知乎上關(guān)注我 ^_.
也可以訪問個(gè)人網(wǎng)站: https://jslixiaolin.github.io