用遗传算法做数独求解器

package com.marssoft.sudoku.evolution; import java.util.ArrayList; import java.util.Collections; import java.util.Comparator; import com.marssoft.sudoku.bean.Base; import com.marssoft.sudoku.bean.Member; import com.marssoft.sudoku.display.LineFrame; /** * 群体进化。 * * @author Mars.CN * */ public class Evolution { public final static int SIZE = 2000; // 种群大小，一般2000左右合适，400的群体运算起来可能会到局部最优。 private ArrayList<Member> tribe = new ArrayList<Member>(); // 参与进化的群体 private Member max; // 最优个体 private Member min; // 最差个体 private double count = 0; // 总得分 private ArrayList<MemberBuffer> roulette; // 轮盘赌 public Evolution() { init(); } /** * 初始化群体 */ public void init() { for (int i = 0; i < SIZE; i++) { tribe.add(new Member(Base.getRandomDNA(), Base.getSeparate())); } } /** * 开始运算。<br /> * 繁殖过程如下： 1. 算出所有个体得分； 2. 得出最高与最低个体，并获得平均分； 3. 查看最高个体有没有满分； 4. 如果有满分则计算完成； * 5. 如果没有满分，则进行下一代繁殖； 6. 重复步骤1 */ public void begin() { LineFrame lf = new LineFrame(); compute(); while (max.getScore() < 432) { Base.addAge(); // 增加一代 // 进行繁殖 ArrayList<Member> nms = new ArrayList<Member>(); while (nms.size() < SIZE) { // 选择两个进行进化操作 Member ms[] = { getMember4Roulette(), getMember4Roulette() }; while (ms[0] == ms[1]) { ms[1] = getMember4Roulette(); } Member[] newMembers = mating(ms); nms.add(newMembers[0]); nms.add(newMembers[1]); } tribe = nms;// 替换新群体 compute();// 计算 System.out.println("第" + Base.getAge() + "代群体，最高得分：" + max.getScore() + " ， 最低得分：" + min.getScore() + " ， 平均分：" + count / SIZE); //System.out.println(max); lf.addPoint(max, min, (int)count / SIZE); } System.out.println("最高个体得到！"); Base.print(max); } /** * 保留最优繁殖方式 */ // public void begin() { // LineFrame lf = new LineFrame(); // float selectance = 0.05f;//择优系数5% // int splendid = (int)(SIZE * selectance); // splendid = splendid%2==0?splendid:splendid+1; // compute(); // while (max.getScore() < 432) { // Base.addAge(); // 增加一代 // // 进行繁殖 // // ArrayList<Member> nms = new ArrayList<Member>(); // //得到一些下代个体 // while (nms.size() < SIZE-splendid) { // // // 选择两个进行进化操作 // Member ms[] = { getMember4Roulette(), getMember4Roulette() }; // while (ms[0] == ms[1]) { // ms[1] = getMember4Roulette(); // } // Member[] newMembers = mating(ms); // nms.add(newMembers[0]); // nms.add(newMembers[1]); // } // Collections.sort(tribe,new MemberSort()); //个体排序 // //选择前X名 X=splendid // for(int i=0 ; i<splendid ; i++){ // nms.add(tribe.get(i)); // } // // tribe = nms;// 替换新群体 // Collections.sort(tribe,new RandomSort()); //混乱 // compute();// 计算 // System.out.println("第" + Base.getAge() + "代群体，最高得分：" // + max.getScore() + " ， 最低得分：" + min.getScore() + " ， 平均分：" // + count / SIZE); // //System.out.println(max); // lf.addPoint(max, min, (int)count / SIZE); // } // System.out.println("最高个体得到！"); // Base.print(max); // } /** * 从轮盘中随机获取一个个体。<br /> * 因为在群体创建之前有过计算(compute())的操作，所以这里直接调用即可 * * @return */ public Member getMember4Roulette() { double rnd = Math.random() * count; // 获取一个随机数 // 遍历群组 看指针指向了谁 for (MemberBuffer mb : roulette) { if (rnd >= mb.getBegin() && rnd < mb.getEnd()) { return mb.getMember(); } } return null;// 这里不会跑到，跑到会是一个错误 } private void compute() { int count = 0; // 总分 max = tribe.get(0); min = tribe.get(0); roulette = new ArrayList<MemberBuffer>(); // 初始化轮盘 for (Member m : tribe) { m.getScore(); roulette.add(new MemberBuffer(m, count, count + m.getScore())); // 装载进轮盘 count += m.getScore(); if (m.getScore() > max.getScore()) { max = m; } if (m.getScore() < min.getScore()) { min = m; } } this.count = count; } /** * 繁殖出下一代产品。<br /> * <br /> * 交叉计算方式如下：<br /> * 1. 随机生成两个数字，分别为要交叉的两个位置；<br /> * 2. 如果要交叉的数字在同一组中，则进行对等位交叉；<br /> * 3. 然后把映射位进行交换，保证基因的完整性；<br /> * 4. 如果跨越不同区域，则把区域内的基因进行对调，跨区域的按步骤2操作。<br /> * <br /> * 变异操作：<br /> * 1. 1-9随机选择一块<br /> * 2. 随机生成快内两个数字位<br /> * 3. 进行进行数字位交叉<br /> * * @param fm * 参与进化的父母<br /> * @return */ public Member[] mating(Member[] fm) { Member[] result = new Member[2]; byte[] dna1 = new byte[fm[0].getLength()]; byte[] dna2 = new byte[fm[0].getLength()]; if (Math.random() <= 0.7) { //交叉，交叉率为0.7 // 获得开始和结束位 int begin = (int) (Math.random() * fm[0].getLength()); // 从第几位开始（第一位标识为0） int end = (int) (Math.random() * fm[1].getLength()); // 到第几位结束结束（第一位标识为0） if (begin > end) { int t = end; end = begin; begin = t; } // 添加固定位（两头不变化数据） for (int i = 0; i < fm[0].getLength(); i++) { if (i >= begin && i <= end) { continue; } dna1[i] = fm[0].getDNA()[i]; dna2[i] = fm[1].getDNA()[i]; } // 交叉 for (int i = begin; i <= end; i++) { dna1[i] = fm[1].getDNA()[i]; dna2[i] = fm[0].getDNA()[i]; } /** * 调整两段字符，保证没有重复 调整规则为： 固定位重复字符与交叉位对应字符进行交换 包含开始位的段，固定位在开始位前面 * 包含结束位的段，固定为在结束位后面 开始位和结束位在同一段中，固定为为两段 */ // 提取两个单串 byte db = 0; // 开始串所在段 byte de = 0; // 结束串所在段 for (byte i = 1; i < 10; i++) { if (begin >= Base.getSeparate()[i - 1] && begin <= Base.getSeparate()[i]) { db = i; } if (end >= Base.getSeparate()[i - 1] && end <= Base.getSeparate()[i]) { de = i; } } int sectionBegin = 0, sectionEnd = 0; // 段的开始于结束 if (db == de) { // 如果两者在同一串中，则集中处理 // 如果开始和结束对应的是开端和末端，则不予理会(整体变化) if (!(begin == Base.getSeparate()[db - 1] && begin == Base .getSeparate()[de])) { sectionBegin = begin - Base.getSeparate()[db - 1]; sectionEnd = end - Base.getSeparate()[de - 1]; byte[] dd1 = new byte[Base.getSeparate()[db] - Base.getSeparate()[db - 1]]; byte[] dd2 = new byte[dd1.length]; // 复制出数组 System.arraycopy(dna1, Base.getSeparate()[db - 1], dd1, 0, dd1.length); System.arraycopy(dna2, Base.getSeparate()[db - 1], dd2, 0, dd2.length); // 调位 testDob(dd1, dd2, sectionBegin, sectionEnd); testDob(dd2, dd1, sectionBegin, sectionEnd); // 放回 System.arraycopy(dd1, 0, dna1, Base.getSeparate()[db - 1], dd1.length); System.arraycopy(dd2, 0, dna2, Base.getSeparate()[db - 1], dd2.length); } } else { // 分别处理 // 处理开始位所在段 sectionBegin = begin - Base.getSeparate()[db - 1]; sectionEnd = Base.getSeparate()[db] - Base.getSeparate()[db - 1] - 1; byte[] dd1 = new byte[Base.getSeparate()[db] - Base.getSeparate()[db - 1]]; byte[] dd2 = new byte[dd1.length]; // 复制出数组 System.arraycopy(dna1, Base.getSeparate()[db - 1], dd1, 0, dd1.length); System.arraycopy(dna2, Base.getSeparate()[db - 1], dd2, 0, dd2.length); // 调位 testDob(dd1, dd2, sectionBegin, sectionEnd); testDob(dd2, dd1, sectionBegin, sectionEnd); // 放回 System.arraycopy(dd1, 0, dna1, Base.getSeparate()[db - 1], dd1