遗传算法组卷系统实现（Java版）
下面是一个完整的遗传算法组卷系统的Java实现，包含题目表示、适应度计算、选择、交叉和变异等核心操作。
1. 核心类设计
1.1 题目实体类（Question.java）
public class Question {
private String id;
private String content;
private String type; // 题型：单选、多选、填空等
private double difficulty; // 难度系数 0-1
private double score; // 题目分值
private String knowledgePoint; // 知识点
// 构造函数、getter和setter省略...
}
1.2 试卷个体类（Paper.java）
import java.util.List;
public class Paper {
private List questions;
private double fitness; // 适应度
public Paper(List<Question> questionPool, int questionCount) {
// 随机初始化试卷
Collections.shuffle(questionPool);
this.questions = new ArrayList<>(questionPool.subList(0, questionCount));
this.fitness = 0;
}
public Paper(List<Question> questions) {
this.questions = questions;
this.fitness = 0;
}
// 计算试卷总分
public double getTotalScore() {
return questions.stream().mapToDouble(Question::getScore).sum();
}
// 计算试卷平均难度
public double getAverageDifficulty() {
return questions.stream().mapToDouble(Question::getDifficulty).average().orElse(0);
}
// getter和setter...
}
1.3 组卷规则类（PaperRule.java）
public class PaperRule {
private double totalScore; // 试卷总分
private double difficulty; // 期望难度
private int questionCount; // 题目数量
private Map<String, Integer> typeDistribution; // 题型分布
private Map<String, Integer> knowledgeDistribution; // 知识点分布
// 构造函数、getter和setter...
}
2. 遗传算法核心实现
2.1 遗传算法主类（GAExamPaper.java）
import java.util.*;
public class GAExamPaper {
private List<Question> questionPool; // 题库
private PaperRule rule; // 组卷规则
private int populationSize; // 种群大小
private double crossoverRate; // 交叉概率
private double mutationRate; // 变异概率
private int maxGeneration; // 最大迭代次数
private List<Paper> population; // 种群
public GAExamPaper(List<Question> questionPool, PaperRule rule,
int populationSize, double crossoverRate,
double mutationRate, int maxGeneration) {
this.questionPool = questionPool;
this.rule = rule;
this.populationSize = populationSize;
this.crossoverRate = crossoverRate;
this.mutationRate = mutationRate;
this.maxGeneration = maxGeneration;
initPopulation();
}
// 初始化种群
private void initPopulation() {
population = new ArrayList<>();
for (int i = 0; i < populationSize; i++) {
population.add(new Paper(questionPool, rule.getQuestionCount()));
}
}
// 运行遗传算法
public Paper evolve() {
for (int generation = 0; generation < maxGeneration; generation++) {
// 计算适应度
calculateFitnessForAll();
// 选择
List<Paper> newPopulation = selection();
// 交叉
crossover(newPopulation);
// 变异
mutation(newPopulation);
// 更新种群
population = newPopulation;
// 输出当前最优解
Paper best = getBestPaper();
System.out.printf("Generation %d: Best Fitness=%.4f%n",
generation, best.getFitness());
// 提前终止条件
if (best.getFitness() >= 0.95) {
break;
}
}
return getBestPaper();
}
// 计算所有个体的适应度
private void calculateFitnessForAll() {
for (Paper paper : population) {
paper.setFitness(calculateFitness(paper));
}
}
// 计算单个个体的适应度
private double calculateFitness(Paper paper) {
// 1. 总分差异（越小越好）
double scoreDiff = Math.abs(paper.getTotalScore() - rule.getTotalScore());
double scoreFitness = 1 - scoreDiff / rule.getTotalScore();
// 2. 难度差异（越小越好）
double difficultyDiff = Math.abs(paper.getAverageDifficulty() - rule.getDifficulty());
double difficultyFitness = 1 - difficultyDiff;
// 3. 题型分布符合度
double typeFitness = calculateTypeFitness(paper);
// 4. 知识点分布符合度
double knowledgeFitness = calculateKnowledgeFitness(paper);
// 综合适应度（权重可根据需要调整）
return 0.3 * scoreFitness + 0.2 * difficultyFitness +
0.25 * typeFitness + 0.25 * knowledgeFitness;
}
// 计算题型分布适应度
private double calculateTypeFitness(Paper paper) {
Map<String, Integer> actualCount = new HashMap<>();
for (Question q : paper.getQuestions()) {
actualCount.merge(q.getType(), 1, Integer::sum);
}
double fitness = 0;
for (Map.Entry<String, Integer> entry : rule.getTypeDistribution().entrySet()) {
int expected = entry.getValue();
int actual = actualCount.getOrDefault(entry.getKey(), 0);
fitness += 1 - (double) Math.abs(expected - actual) / expected;
}
return fitness / rule.getTypeDistribution().size();
}
// 计算知识点分布适应度
private double calculateKnowledgeFitness(Paper paper) {
// 类似题型分布的计算方法
// ...
}
// 选择操作（轮盘赌选择）
private List<Paper> selection() {
List<Paper> newPopulation = new ArrayList<>();
// 计算总适应度
double totalFitness = population.stream().mapToDouble(Paper::getFitness).sum();
// 轮盘赌选择
for (int i = 0; i < populationSize; i++) {
double slice = Math.random() * totalFitness;
double sum = 0;
for (Paper paper : population) {
sum += paper.getFitness();
if (sum >= slice) {
newPopulation.add(new Paper(new ArrayList<>(paper.getQuestions())));
break;
}
}
}
return newPopulation;
}
// 交叉操作（单点交叉）
private void crossover(List<Paper> newPopulation) {
for (int i = 0; i < newPopulation.size() - 1; i += 2) {
if (Math.random() < crossoverRate) {
Paper parent1 = newPopulation.get(i);
Paper parent2 = newPopulation.get(i + 1);
// 随机选择交叉点
int crossoverPoint = (int) (Math.random() * parent1.getQuestions().size());
// 执行交叉
List<Question> child1Questions = new ArrayList<>();
child1Questions.addAll(parent1.getQuestions().subList(0, crossoverPoint));
child1Questions.addAll(parent2.getQuestions().subList(crossoverPoint, parent2.getQuestions().size()));
List<Question> child2Questions = new ArrayList<>();
child2Questions.addAll(parent2.getQuestions().subList(0, crossoverPoint));
child2Questions.addAll(parent1.getQuestions().subList(crossoverPoint, parent1.getQuestions().size()));
// 替换原个体
newPopulation.set(i, new Paper(child1Questions));
newPopulation.set(i + 1, new Paper(child2Questions));
}
}
}
// 变异操作
private void mutation(List<Paper> newPopulation) {
for (Paper paper : newPopulation) {
if (Math.random() < mutationRate) {
// 随机选择变异位置
int mutationPos = (int) (Math.random() * paper.getQuestions().size());
// 从题库中随机选择一道不同的题目替换
Question oldQuestion = paper.getQuestions().get(mutationPos);
Question newQuestion;
do {
newQuestion = questionPool.get((int) (Math.random() * questionPool.size()));
} while (newQuestion.equals(oldQuestion));
paper.getQuestions().set(mutationPos, newQuestion);
}
}
}
// 获取当前种群中最优个体
private Paper getBestPaper() {
return Collections.max(population, Comparator.comparingDouble(Paper::getFitness));
}
}
3. 使用示例
public class Main {
public static void main(String[] args) {
// 1. 准备题库
List<Question> questionPool = prepareQuestionPool();
// 2. 设置组卷规则
PaperRule rule = new PaperRule();
rule.setTotalScore(100);
rule.setDifficulty(0.6);
rule.setQuestionCount(50);
Map<String, Integer> typeDistribution = new HashMap<>();
typeDistribution.put("单选", 30);
typeDistribution.put("多选", 10);
typeDistribution.put("填空", 10);
rule.setTypeDistribution(typeDistribution);
// 3. 创建遗传算法组卷实例
GAExamPaper ga = new GAExamPaper(questionPool, rule,
100, 0.8, 0.1, 200);
// 4. 执行组卷
Paper bestPaper = ga.evolve();
// 5. 输出结果
System.out.println("最佳试卷：");
System.out.println("总分：" + bestPaper.getTotalScore());
System.out.println("平均难度：" + bestPaper.getAverageDifficulty());
System.out.println("适应度：" + bestPaper.getFitness());
}
private static List<Question> prepareQuestionPool() {
// 这里应该从数据库或文件加载题目
List<Question> questions = new ArrayList<>();
// 添加各种题目...
return questions;
}
}
4. 算法优化建议
适应度函数优化：
可以根据实际需求调整各项指标的权重
加入对重复知识点的惩罚项
选择策略改进：
可以结合精英保留策略，确保最优个体不被淘汰
使用锦标赛选择代替轮盘赌选择
交叉和变异改进：
实现多点交叉或均匀交叉
变异时可以优先选择与当前题目相似的题目
并行计算：
适应度计算可以并行化以提高性能
动态参数调整：
随着迭代进行动态调整交叉率和变异率
这个实现提供了遗传算法组卷的核心框架，你可以根据具体需求进行调整和扩展。实际应用中，还需要考虑题库的存储和检索效率等问题。