遺傳算法

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

1. 基本概念

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

2. 算法流程

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

• 初始化. 隨機生成一個規(guī)模為N的種群首装，設(shè)置最大進化次數(shù)以及停止進化條件.
• 計算適應(yīng)度. 適應(yīng)度被用來評價個體的質(zhì)量创夜，且適應(yīng)度是唯一評判因子.計算種群中每個個體的適應(yīng)度，得到最優(yōu)秀的個體.
• 選擇. 選擇是用來得到一些優(yōu)秀的個體來產(chǎn)生下一代.選擇算法的好壞至關(guān)重要仙逻，因為在一定程度上選擇會影響種群的進化方向.常用的選擇算法有：隨機抽取驰吓、競標賽選擇以及輪盤賭模擬法等等.
• 交叉. 交叉是兩個個體繁衍下一代的過程，實際上是子代獲取父親和母親的部分基因系奉，即基因重組.常用的交叉方法有：單點交叉檬贰、多點交叉等.
• 變異. 變異即模擬突變過程.通過變異，種群中個體變得多樣化.但是變異是有一個概率的.

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

3. java實現(xiàn)

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

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

計算適應(yīng)度

/**
 * 通過和solution比較 疼约，計算個體的適應(yīng)值
 * @param individual 待比較的個體
 * @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;
}

選擇算子

/**
 * 隨機選擇一個較優(yōu)秀的個體卤档。用于進行交叉
 * @param pop 種群
 * @return
 */
private static Individual tournamentSelection(Population pop) {
    Population tournamentPop = new Population(tournamentSize, false);
    // 隨機選擇 tournamentSize 個放入 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;
}

交叉算子

/**
 * 兩個個體交叉產(chǎn)生下一代
 * @param indiv1 父親
 * @param indiv2 母親
 * @return 后代
 */
private static Individual crossover(Individual indiv1, Individual indiv2) {
    Individual newSol = new Individual();
    // 隨機的從兩個個體中選擇
    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;
}

變異算子

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

4. 測試結(jié)果

測試結(jié)果如下圖

遺傳算法與自動組卷

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

1. 對遺傳算法的改進

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

1.1 染色體編碼方式的改進

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

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

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

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

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

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

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

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

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

1.4 選擇算子與交叉算子的改進

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

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

1.5 變異算子的改進

基因變異的出現(xiàn)增加了種群的多樣性.在本系統(tǒng)中购披，每個個體的每個基因都有變異的機會杖挣，如果隨機概率小于變異概率，那么基因就可以突變.突變基因的原則為：與原題的同題型刚陡、同分數(shù)且同知識點的試題.有研究表明惩妇，對于變異概率的選擇，在0.1-0.001之間最佳橘荠，本例中選取了0.085作為變異概率.

1.6 組卷規(guī)則

組卷規(guī)則是初始化種群的依賴屿附。組卷規(guī)則由用戶指定郎逃，規(guī)定了用戶期望的試卷的條件：試卷總分哥童、包含的題型與數(shù)量、期望難度系數(shù)褒翰、期望覆蓋的知識點贮懈。在本例中將組卷規(guī)則封裝為一個JavaBean

2. java實現(xiàn)

2.1 試卷個體

個體，即試卷.本例中將試卷個體抽象成一個JavaBean优训，其有id朵你，適應(yīng)度、知識點覆蓋率揣非、難度系數(shù)抡医、總分、以及個體包含的試題集合這6個屬性早敬，以及計算知識點覆蓋率和適應(yīng)度這幾個方法.在計算適應(yīng)度的時候忌傻，知識點權(quán)重為0.20，難度系數(shù)權(quán)重為0.80.

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

/**
 * 計算試卷個體難度系數(shù) 計算公式： 每題難度*分數(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;
}
 /**
     * 計算知識點覆蓋率 公式為：個體包含的知識點/期望包含的知識點
     *
     * @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();
        }
    }

/**
 * 計算個體適應(yīng)度 公式為：f=1-(1-M/N)*f1-|EP-P|*f2
 * 其中M/N為知識點覆蓋率搞监，EP為期望難度系數(shù)水孩，P為種群個體難度系數(shù)，f1為知識點分布的權(quán)重
 * 琐驴，f2為難度系數(shù)所占權(quán)重俘种。當f1=0時退化為只限制試題難度系數(shù)，當f2=0時退化為只限制知識點分布
 *
 * @param rule 組卷規(guī)則
 * @param f1   知識點分布的權(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 種群初始化

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

/**
 * 初始種群
 *
 * @param populationSize 種群規(guī)模
 * @param initFlag       初始化標志 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);
                }
            }
            // 計算試卷知識點覆蓋率
            paper.setKpCoverage(rule);
            // 計算試卷適應(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);
        // 初始化分數(shù)
        singleArray[index].setScore(score);
        paper.addQuestion(singleArray[index]);
        // 保證不會重復添加試題
        tmpQuestion = singleArray[singleArray.length - j - 1];
        singleArray[singleArray.length - j - 1] = singleArray[index];
        singleArray[index] = tmpQuestion;
    }
}

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

選擇算子的實現(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();
}

交叉算子的實現(xiàn).本系統(tǒng)實現(xiàn)的算子為兩點交叉玉罐，在算法的實現(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之間的序列屈嗤，會被遺傳到下一代
    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)重復的元素
    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 變異算子的實現(xiàn)

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

/**
 * 突變算子 每個個體的每個基因都有可能突變
 *
 * @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) {
            // 進行突變，第i道
            tmpQuestion = paper.getQuestion(i);
            // 從題庫中獲取和變異的題目類型一樣分數(shù)相同的題目（不包含變異題目）
            list = QuestionService.getQuestionListWithOutSId(tmpQuestion);
            if (list.size() > 0) {
                // 隨機獲取一道
                index = (int) (Math.random() * list.size());
                // 設(shè)置分數(shù)
                list.get(index).setScore(tmpQuestion.getScore());
                paper.saveQuestion(i, list.get(index));
            }
        }
    }
}

2.5 進化的整體流程

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

// 進化種群
public static Population evolvePopulation(Population pop, RuleBean rule) {
    Population newPopulation = new Population(pop.getLength());
    int elitismOffset;
    // 精英主義
    if (elitism) {
        elitismOffset = 1;
        // 保留上一代最優(yōu)秀個體
        Paper fitness = pop.getFitness();
        fitness.setId(0);
        newPopulation.setPaper(0, fitness);
    }
    // 種群交叉操作，從當前的種群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);
        // 計算知識點覆蓋率與適應(yīng)度
        tmpPaper.setKpCoverage(rule);
        tmpPaper.setAdaptationDegree(rule, Global.KP_WEIGHT, Global.DIFFCULTY_WEIGHt);
    }
    return newPopulation;
}

3. 測試結(jié)果

組卷規(guī)則為：期望試卷難度系數(shù)0.82扭屁，共100分算谈，20道選擇題，2分一道料滥，10道填空題然眼，2分一道，4道主觀題葵腹，10分一道高每，要求囊括6個知識點.
外在的條件為：題庫試題總量為10950，期望適應(yīng)度值為0.98践宴，種群最多迭代100次.
測試代碼如下：

/**
 * 組卷過程
 *
 * @param rule
 * @return
 */
public static Paper generatePaper(RuleBean rule) {
    Paper resultPaper = null;
    // 迭代計數(shù)器
    int count = 0;
    int runCount = 100;
    // 適應(yīng)度期望值z
    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 + " 次進化鲸匿，適應(yīng)度為： " + population.getFitness().getAdaptationDegree());
        }
        System.out.println("進化次數(shù)： " + count);
        System.out.println(population.getFitness().getAdaptationDegree());
        resultPaper = population.getFitness();
    }
    return resultPaper;
}

測試結(jié)果如下：

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

參考資料

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

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