Java使用遗传算法，寻找十滴水问题的最优解-Toy模板网

这篇具有很好参考价值的文章主要介绍了Java使用遗传算法，寻找十滴水问题的最优解。希望对大家有所帮助。如果存在错误或未考虑完全的地方，请大家不吝赐教，您也可以点击"举报违法"按钮提交疑问。

近期某手游出了个活动，经确认发现本质为十滴水游戏。

简单说一下规则，棋盘大小通常为6x6，在游戏开始时，棋盘随机有若干水珠，其大小范围为1-4。点击棋盘内的一格，会消耗玩家持有的1个小水滴，同时使得该单元格的水珠大小+1。如果水珠大小超过4，则水珠发生爆炸并消失，同时向四个方向各发射1个小水滴。小水滴匀速前进，前进时遇到第一个水珠则消失，同时该水珠大小+1，或者小水滴遇到棋盘边界而消失。当棋盘被清空时这一关通过，或者玩家持有的水滴耗尽而游戏结束。如果一次操作引发多个水珠爆炸，则每爆炸3个水珠，奖励1个水滴。如果只触发爆炸一次水珠通过这一关，则视为完美通关，额外奖励1个小水滴。对于该游戏，每次通关奖励2个小水滴。

查阅了相关资料后，得到了几条关键思路，即：

1、根据一个确定的盘面和一个坐标，通过计算，可以得到一个确定的执行结果，这样的操作称为一步。

2、一般不会在空白的单元格上设置小水滴，所以随机不停地在有水珠的单元格上添加小水滴，必然在有限的步骤后清空棋盘。

3、暴力遍历的话，由于状态空间太大，只要步数稍多（7步或更长），就不能在合理的时间内找到最优解。

所以，我们可以得到进一步的推论，我们可以使用一个有限且有序的点列表，解决一个盘面，并计算出该解法的小水滴的收益，期间最大投入小水滴的数量等结果。我们最终的目的是使得小水滴的收益最大化。

因此，我决定使用遗传算法，解决本问题。

首先定义游戏关键对象：

 1 package bean;
 2 
 3 import main.Game;
 4 
 5 import java.util.HashMap;
 6 import java.util.Map;
 7 
 8 /**
 9  * 位置点
10  */
11 public class Point {
12 
13     private static final Map<Integer, Map<Integer, Point>> POINT_MAP = new HashMap<>();
14 
15     /**
16      * X坐标
17      */
18     private final int x;
19 
20     /**
21      * Y坐标
22      */
23     private final int y;
24 
25     private Point(int x, int y) {
26         this.x = x;
27         this.y = y;
28     }
29 
30     /**
31      * 获取一个点对象
32      *
33      * @param x X坐标
34      * @param y Y坐标
35      * @return 生成的点对象
36      */
37     public static Point get(int x, int y) {
38         Map<Integer, Point> subPointMap = POINT_MAP.computeIfAbsent(x, i -> new HashMap<>());
39         return subPointMap.computeIfAbsent(y, i -> new Point(x, y));
40     }
41 
42     public int getX() {
43         return x;
44     }
45 
46     public int getY() {
47         return y;
48     }
49 
50     public boolean isValidPosition() {
51         return x >= 0 && y >= 0 && x < Game.X && y < Game.Y;
52     }
53 
54     @Override
55     public String toString() {
56         return String.format("(%s,%s)", x, y);
57     }
58 }

位置点对象

 1 package bean;
 2 
 3 /**
 4  * 子弹对象，即爆裂发生时需要计算随时间变化的结果
 5  */
 6 public class Bullet {
 7 
 8     /**
 9      * X坐标
10      */
11     private int x;
12 
13     /**
14      * Y坐标
15      */
16     private int y;
17 
18     /**
19      * X变化率
20      */
21     private int dx;
22 
23     /**
24      * Y变化率
25      */
26     private int dy;
27 
28     public Bullet() {
29     }
30 
31     public Bullet(int x, int y, int dx, int dy) {
32         this.x = x;
33         this.y = y;
34         this.dx = dx;
35         this.dy = dy;
36     }
37 
38     public Bullet(Point point, int dx, int dy) {
39         this(point.getX(), point.getY(), dx, dy);
40     }
41 
42     public int getX() {
43         return x;
44     }
45 
46     public void setX(int x) {
47         this.x = x;
48     }
49 
50     public int getY() {
51         return y;
52     }
53 
54     public void setY(int y) {
55         this.y = y;
56     }
57 
58     public int getDx() {
59         return dx;
60     }
61 
62     public void setDx(int dx) {
63         this.dx = dx;
64     }
65 
66     public int getDy() {
67         return dy;
68     }
69 
70     public void setDy(int dy) {
71         this.dy = dy;
72     }
73 
74     /**
75      * 子弹移动一个回合
76      *
77      * @return 移动后的位置
78      */
79     public Point move() {
80         x += dx;
81         y += dy;
82         return Point.get(x, y);
83     }
84 }

子弹对象，即爆裂发生时需要计算随时间变化的结果

 1 package bean;
 2 
 3 /**
 4  * 游戏的行动结果对象，会进行缓存
 5  */
 6 public class MoveResult {
 7 
 8     /**
 9      * 行动后的盘面
10      */
11     private int[][] arr;
12 
13     /**
14      * 行动后获得的收益(可以由combo计算出)
15      */
16     private int reward;
17 
18     /**
19      * 行动连击数量，即本次行动导致多少爆炸
20      */
21     private int combo;
22 
23     public MoveResult() {
24 
25     }
26 
27     public MoveResult(int[][] arr, int reward, int combo) {
28         this.arr = arr;
29         this.reward = reward;
30         this.combo = combo;
31     }
32 
33     public int[][] getArr() {
34         return arr;
35     }
36 
37     public void setArr(int[][] arr) {
38         this.arr = arr;
39     }
40 
41     public int getReward() {
42         return reward;
43     }
44 
45     public void setReward(int reward) {
46         this.reward = reward;
47     }
48 
49     public int getCombo() {
50         return combo;
51     }
52 
53     public void setCombo(int combo) {
54         this.combo = combo;
55     }
56 }

游戏的行动结果对象，会进行缓存

 1 package bean;
 2 
 3 import java.util.ArrayList;
 4 import java.util.List;
 5 
 6 /**
 7  * 遗传算法使用的解答
 8  */
 9 public class Answer {
10 
11     /**
12      * 操作链，存储依次的执行操作
13      */
14     private final List<Point> pointList = new ArrayList<>();
15 
16     /**
17      * 爆炸次数
18      */
19     private int burstCount;
20 
21     /**
22      * 累计的收益
23      */
24     private int totalReward;
25 
26     /**
27      * 区间最低收益
28      */
29     private int minReward;
30 
31     public Answer() {
32     }
33 
34     public Answer(List<Point> pointList) {
35         this.pointList.addAll(pointList);
36     }
37 
38     public List<Point> getPointList() {
39         return pointList;
40     }
41 
42     public int getBurstCount() {
43         return burstCount;
44     }
45 
46     public void setBurstCount(int burstCount) {
47         this.burstCount = burstCount;
48     }
49 
50     public int getTotalReward() {
51         return totalReward;
52     }
53 
54     public void setTotalReward(int totalReward) {
55         this.totalReward = totalReward;
56     }
57 
58     public int getMinReward() {
59         return minReward;
60     }
61 
62     public void setMinReward(int minReward) {
63         this.minReward = minReward;
64     }
65 
66     /**
67      * 获取解的长度
68      *
69      * @return 解的长度
70      */
71     public int length() {
72         return pointList.size();
73     }
74 
75     @Override
76     public String toString() {
77         return String.format("%s, %s, %s, %s, %s", totalReward, burstCount, length(), minReward, pointList);
78     }
79 }

遗传算法使用的解答类

以及工具类

  1 package util;
  2 
  3 import bean.Answer;
  4 import bean.MoveResult;
  5 import bean.Point;
  6 import main.Game;
  7 
  8 import java.util.ArrayList;
  9 import java.util.List;
 10 
 11 public class Utils {
 12 
 13     /**
 14      * 可视化一个Array（用于打印）
 15      *
 16      * @param game   游戏
 17      * @param answer 解答
 18      * @return 复制后的Array
 19      */
 20     public static String answerString(Game game, Answer answer) {
 21         StringBuilder builder = new StringBuilder();
 22 
 23         int[][] arr = game.getInitArr();
 24         int[][] moveArr = new int[Game.X][Game.Y];
 25         int moved = 0;
 26         int totalReward = 0;
 27         int minReward = 0;
 28         int burstCount = 0;
 29         StringBuilder moveBuilder = new StringBuilder();
 30         for (int i = 0; i < answer.length(); i++) {
 31             Point point = answer.getPointList().get(i);
 32             if (arr[point.getX()][point.getY()] <= 0) {
 33                 continue;
 34             }
 35 
 36             // 记录本次操作的结果，并更新棋盘状态
 37             MoveResult move = Game.move(arr, point);
 38             totalReward += move.getReward();
 39             if (minReward > totalReward) {
 40                 minReward = totalReward;
 41             }
 42             if (move.getCombo() > 0) {
 43                 burstCount++;
 44                 // 发生爆炸，则打印之前的行
 45                 if (moved > 0) {
 46                     answerStringArrLine(builder, moveBuilder, arr, moveArr);
 47                     builder.append("\r\n");
 48                     moveArr = new int[Game.X][Game.Y];
 49                     moved = 0;
 50                 }
 51             }
 52             arr = move.getArr();
 53             moveArr[point.getX()][point.getY()] += 1;
 54             moved++;
 55 
 56             builder.append(i).append(", Reward: ").append(move.getReward()).append(", TotalReward: ").append(totalReward).append(", Combo: ").append(move.getCombo()).append(", ").append(point);
 57             builder.append("\r\n");
 58             if (move.getCombo() > 0) {
 59                 answerStringArrLine(builder, moveBuilder, arr, moveArr);
 60                 builder.append("\r\n");
 61                 moveArr = new int[Game.X][Game.Y];
 62                 moved = 0;
 63             }
 64         }
 65 
 66         if (burstCount <= 1) {
 67             builder.append("Full Combo!").append("\r\n");
 68         } else {
 69             builder.append("BurstCount: ").append(burstCount).append("\r\n");
 70         }
 71 
 72         builder.append(answer.getTotalReward()).append(", ").append(answer.getBurstCount()).append(", ").append(answer.length()).append(", ").append(answer.getMinReward()).append(": ").append(moveBuilder).append("\r\n");
 73 
 74         return builder.toString();
 75     }
 76 
 77     private static void answerStringArrLine(StringBuilder builder, StringBuilder moveBuilder, int[][] arr, int[][] moveArr) {
 78         List<String> moveList = new ArrayList<>();
 79         for (int x = 0; x < arr.length; x++) {
 80             for (int y = 0; y < arr.length; y++) {
 81                 builder.append(arr[x][y]).append(", ");
 82             }
 83             builder.append("    ");
 84             for (int y = 0; y < arr.length; y++) {
 85                 builder.append(moveArr[x][y]).append(", ");
 86                 if (moveArr[x][y] > 0) {
 87                     moveList.add(String.format("(%s, %s, %s)", x, y, moveArr[x][y]));
 88                 }
 89             }
 90             builder.append("\r\n");
 91         }
 92         moveBuilder.append(moveList.toString()).append(" ");
 93     }
 94 
 95     /**
 96      * 将一个数组转化为String（配合Map使用）
 97      *
 98      * @param arr 待处理数组
 99      * @return 处理结果
100      */
101     public static String arrKey(int[][] arr) {
102         StringBuilder builder = new StringBuilder();
103         for (int i = 0; i < arr.length; i++) {
104             for (int j = 0; j < arr[i].length; j++) {
105                 builder.append(arr[i][j]);
106             }
107         }
108         return builder.toString();
109     }
110 
111     /**
112      * 可视化一个Array（用于打印）
113      *
114      * @param arr 待复制数组
115      * @return 复制后的Array
116      */
117     public static String arrString(int[][] arr) {
118         StringBuilder builder = new StringBuilder();
119         for (int i = 0; i < arr.length; i++) {
120             for (int j = 0; j < arr[i].length; j++) {
121                 builder.append(arr[i][j]);
122                 builder.append(", ");
123             }
124             if (i < arr.length - 1) {
125                 builder.append("\r\n");
126             }
127         }
128         return builder.toString();
129     }
130 
131     /**
132      * 复制一个Array
133      *
134      * @param arr 待复制数组
135      * @return 复制后的Array
136      */
137     public static int[][] arrCopy(int[][] arr) {
138         int[][] result = new int[arr.length][];
139         for (int i = 0; i < arr.length; i++) {
140             result[i] = new int[arr[i].length];
141             for (int j = 0; j < arr[i].length; j++) {
142                 result[i][j] = arr[i][j];
143             }
144         }
145         return result;
146     }
147 
148     /**
149      * 返回一个在0到num之间的随机数，包含0，不包含num
150      *
151      * @param num 数字
152      * @return 返回随机数
153      */
154     public static int randInt(int num) {
155         if (num >= 0) {
156             return randInt(0, num);
157         } else {
158             return randInt(num, 0);
159         }
160     }
161 
162     /**
163      * 返回一个在min到max之间的随机数，包含min，不包含max
164      *
165      * @param min 随机数下限
166      * @param max 随机数上限
167      * @return 返回随机数
168      */
169     public static int randInt(int min, int max) {
170         int diff = max - min;
171         int rand = (int) (Math.random() * diff);
172         return min + rand;
173     }
174 
175     /**
176      * 求一组数字的最大值
177      *
178      * @param nums 输入数列
179      * @return 最大值
180      */
181     public static int max(int... nums) {
182         int result = nums[0];
183         for (int i = 1; i < nums.length; i++) {
184             if (nums[i] > result) {
185                 result = nums[i];
186             }
187         }
188         return result;
189     }
190 
191     /**
192      * 求一组数字的最小值
193      *
194      * @param nums 输入数列
195      * @return 最小值
196      */
197     public static int min(int... nums) {
198         int result = nums[0];
199         for (int i = 1; i < nums.length; i++) {
200             if (nums[i] < result) {
201                 result = nums[i];
202             }
203         }
204         return result;
205     }
206 }

工具类

接下来需要模拟游戏过程了：

这部分的重点是，需要不停地扫描当前是否有水滴在活动，以及是否有水珠发生爆炸。两者要分开并依次进行，以防止多个水滴同时命中水珠后爆炸，导致结果误判。

计算完毕一个状态以后，可以把它缓存，之后无需重复计算。

  1 package main;
  2 
  3 import bean.Bullet;
  4 import bean.MoveResult;
  5 import bean.Point;
  6 import util.Utils;
  7 
  8 import java.util.ArrayList;
  9 import java.util.HashMap;
 10 import java.util.List;
 11 import java.util.Map;
 12 
 13 /**
 14  * 游戏的基本参数与功能
 15  * 如果需要分析别的盘面，在这里修改参数
 16  */
 17 public class Game {
 18 
 19     /**
 20      * 棋盘X大小
 21      */
 22     public static int X = 6;
 23 
 24     /**
 25      * 棋盘Y大小
 26      */
 27     public static int Y = 6;
 28 
 29     /**
 30      * 爆裂门槛
 31      */
 32     public static int BURST = 4;
 33 
 34     /**
 35      * 奖励倒数，COMBO除以这个数后得到奖励
 36      */
 37     public static int REWARD_INV = 3;
 38 
 39     /**
 40      * 完美通关的额外奖励
 41      */
 42     public static int REWARD_PFT = 1;
 43 
 44     /**
 45      * 缓存发生爆炸后的计算结果
 46      */
 47     public static Map<String, MoveResult> MOVE_MAP = new HashMap<>(524288);
 48 
 49     /**
 50      * 待求解初始状态
 51      */
 52     private int[][] initArr = {
 53             {0, 2, 2, 1, 4, 4},
 54             {2, 1, 1, 1, 3, 0},
 55             {2, 3, 1, 2, 2, 4},
 56             {0, 3, 2, 0, 0, 4},
 57             {1, 0, 3, 2, 1, 0},
 58             {3, 3, 0, 2, 0, 0},
 59 
 60     };
 61 
 62 //    public static void main(String[] args) {
 63 //        Game game = new Game();
 64 //        MoveResult move = move(game.initArr, 5, 3);
 65 //        System.out.println(Utils.arrString(move.getArr()));
 66 //        System.out.println(move.getCombo());
 67 //    }
 68 
 69     /**
 70      * @param arr   棋盘
 71      * @param point 坐标点
 72      * @return v1: 执行后的棋盘, v2: 本次操作的收益, v3: 是否发生了爆炸
 73      */
 74     public static MoveResult move(int[][] arr, Point point) {
 75         return move(arr, point.getX(), point.getY());
 76     }
 77 
 78     /**
 79      * 执行一次加水操作，返回执行后的棋盘，本次操作收益，是否发生爆炸
 80      * 如果发生爆炸，需要缓存对应结果
 81      *
 82      * @param arr 棋盘
 83      * @param x   X坐标
 84      * @param y   Y坐标
 85      * @return v1: 执行后的棋盘, v2: 本次操作的收益, v3: 是否发生了爆炸
 86      */
 87     public static MoveResult move(int[][] arr, int x, int y) {
 88         int[][] resArr = Utils.arrCopy(arr);
 89         resArr[x][y]++;
 90         if (resArr[x][y] <= BURST) {
 91             // 本次操作不会导致爆炸，直接返回
 92             return new MoveResult(resArr, -1, 0);
 93         }
 94         String arrKey = Utils.arrKey(arr) + x + y;
 95         MoveResult result = MOVE_MAP.get(arrKey);
 96         if (result != null) {
 97             // 本次操作命中缓存，直接返回
 98             return result;
 99         }
100 
101         // 循环计算爆炸结果
102         int combo = 0;
103         List<Bullet> bulletList = new ArrayList<>();
104         do {
105             // 1. 所有水滴移动1回合
106             List<Bullet> newBulletList = new ArrayList<>();
107             for (Bullet bullet : bulletList) {
108                 Point point = bullet.move();
109                 if (!point.isValidPosition()) {
110                     // 水滴出界，则移除掉它
111                     continue;
112                 }
113                 if (resArr[point.getX()][point.getY()] > 0) {
114                     // 水滴遇到了已存在的水球，则水球大小+1，移除水滴
115                     resArr[point.getX()][point.getY()]++;
116                     continue;
117                 }
118                 // 水滴通过校验，存活进入下一个回合
119                 newBulletList.add(bullet);
120             }
121 
122             // 2. 检查是否有水珠爆炸，是的话在该位置生成4个方向的新水滴，并将所在位置的格子置空
123             List<Point> burstPointList = availablePoints(resArr, 1);
124             for (Point point : burstPointList) {
125                 newBulletList.add(new Bullet(point, 1, 0));
126                 newBulletList.add(new Bullet(point, 0, 1));
127                 newBulletList.add(new Bullet(point, -1, 0));
128                 newBulletList.add(new Bullet(point, 0, -1));
129                 resArr[point.getX()][point.getY()] = 0;
130                 combo++;
131             }
132 
133             bulletList = newBulletList;
134         } while (!bulletList.isEmpty());
135 
136         int reward = combo / REWARD_INV - 1;
137         result = new MoveResult(resArr, reward, combo);
138         MOVE_MAP.put(arrKey, result);
139         return result;
140     }
141 
142     /**
143      * 获取可选的点
144      *
145      * @param arr   棋盘
146      * @param burst 点的状态，0为任意有水滴点，1为仅满，-1为仅不满
147      * @return 返回的可选点列表
148      */
149     public static List<Point> availablePoints(int[][] arr, int burst) {
150         List<Point> pointList = new ArrayList<>();
151         for (int i = 0; i < arr.length; i++) {
152             for (int j = 0; j < arr[i].length; j++) {
153                 if (arr[i][j] > 0) {
154                     int isBurst = arr[i][j] > BURST ? 1 : -1;
155                     int result = burst * isBurst;
156                     if (result >= 0) {
157                         pointList.add(Point.get(i, j));
158                     }
159                 }
160             }
161         }
162         return pointList;
163     }
164 
165     public int[][] getInitArr() {
166         return initArr;
167     }
168 
169     public void setInitArr(int[][] initArr) {
170         this.initArr = initArr;
171     }
172 }

接下来，就是使用遗传算法，计算出最优解了。

这里我想了想，找到了一个尽可能适合本问题的生成子代方法，大致是这样的：

1、分数最高的<精英个数>名后代，直接移入下一回合

2、分数最高的<精英个数>名后代，随机两两配对，独立地产生2个后代，可能变异

3、分数最高的<普通个数>名后代，随机两两配对，对立地产生2个后代，可能变异

4、分数最高的<随机个数>名后代，从随机位置截断，截断后的部分全部随机生成

配对时，以50%几率设置1个切断位点，25%几率设置2个切断位点，25%几率设置3个切断位点。重组位点在两个解长度较小值之内。

变异发生时，以50%几率修改一步，25%几率增加一步，25%几率删除一步。

生成子代后，计算它们的最终收益，爆炸次数、解的长度，以及期间最大投入成本，并排序。

如果计算出的解的最终收益、爆炸次数、解的长度发生更新，则回合数置零。当回合数超过<最大回合数>时，终止并输出结果。

经过参数调优，精英个数设置为128，普通个数为4096，随机个数为512，最大回合数为128，变异几率为0.125。

本算法和一般的遗传算法不同的地方：

1、不限制答案长度。（但理论最大是6x6x3步）

2、生成后代的方式比较丰富，但只允许适应度最高的一些解产生后代。但是，不在这范围内的解直接淘汰，而不是以几率被选择。

3、允许了最多3个重组位点，而不是固定1个。

4、允许突变发生增加和删除操作，而不是只有修改操作。

  1 package main;
  2 
  3 import bean.Answer;
  4 import bean.MoveResult;
  5 import bean.Point;
  6 import util.Utils;
  7 
  8 import java.util.ArrayList;
  9 import java.util.Collections;
 10 import java.util.Comparator;
 11 import java.util.List;
 12 
 13 /**
 14  * 遗传算法，寻找一个尽可能收益最高的解
 15  */
 16 public class Resolve {
 17 
 18     /**
 19      * 种群容量
 20      * 初始生成数量、生成普通后代时的配对数量
 21      */
 22     private int capacity = 4096;
 23 
 24     /**
 25      * 精英种群容量
 26      * 精英种群直接移入下一回合，同时两两配对产生2个后代
 27      */
 28     private int eliteCapacity = 128;
 29 
 30     /**
 31      * 随机种群容量
 32      * 每回合对该数量的成员，在某位置截断，之后部分重新生成
 33      * 它负责同时引入大量突变
 34      */
 35     private int randomCutCapacity = 512;
 36 
 37     /**
 38      * 经过该回合数，最优解的适应度不发生变化，则终止并退出遗传算法，输出结果
 39      */
 40     private int stableExitTurn = 128;
 41 
 42     /**
 43      * 重组时发生变异的几率
 44      * 一旦发生，随机位置以25%几率新增1个操作，25%删除1个操作，50%修改1个操作（修改后可能与原操作相同）
 45      */
 46     private double variationRate = 0.125D;
 47 
 48     public int getCapacity() {
 49         return capacity;
 50     }
 51 
 52     public void setCapacity(int capacity) {
 53         this.capacity = capacity;
 54     }
 55 
 56     public int getEliteCapacity() {
 57         return eliteCapacity;
 58     }
 59 
 60     public void setEliteCapacity(int eliteCapacity) {
 61         this.eliteCapacity = eliteCapacity;
 62     }
 63 
 64     public int getRandomCutCapacity() {
 65         return randomCutCapacity;
 66     }
 67 
 68     public void setRandomCutCapacity(int randomCutCapacity) {
 69         this.randomCutCapacity = randomCutCapacity;
 70     }
 71 
 72     public int getStableExitTurn() {
 73         return stableExitTurn;
 74     }
 75 
 76     public void setStableExitTurn(int stableExitTurn) {
 77         this.stableExitTurn = stableExitTurn;
 78     }
 79 
 80     public double getVariationRate() {
 81         return variationRate;
 82     }
 83 
 84     public void setVariationRate(double variationRate) {
 85         this.variationRate = variationRate;
 86     }
 87 
 88     public static void main(String[] args) {
 89         Resolve resolve = new Resolve();
 90         Game game = new Game();
 91 
 92 //        for (int i = 0; i < game.getInitArr().length; i++) {
 93 //            for (int j = 0; j < game.getInitArr()[i].length; j++) {
 94 //                game.getInitArr()[i][j] = Utils.randInt(5);
 95 //            }
 96 //        }
 97 //        System.out.println(Utils.arrString(game.getInitArr()));
 98 //        System.out.println();
 99 
100         Answer answer = resolve.select(game);
101         System.out.println(answer);
102     }
103 
104     /**
105      * 遗传算法执行入口
106      *
107      * @param game 游戏
108      * @return 找到的最优解
109      */
110     public Answer select(Game game) {
111         int turn = 0;
112         int stableTurn = 0;
113         int lastTotalReward = 0;
114         int lastBurstCount = 0;
115         int lastLength = 0;
116         List<Answer> answerList = new ArrayList<>(capacity);
117 
118         // 初始化，产生最初的答案
119         for (int i = 0; i < capacity; i++) {
120             Answer answer = new Answer();
121             calcTotalReward(game, answer);
122             answerList.add(answer);
123         }
124         sortAnswerList(answerList);
125 
126         // 执行遗传算法
127         while (stableTurn < stableExitTurn) {
128             // 1. 生成下一代，同时计算总奖励
129             List<Answer> newAnswerList = new ArrayList<>(capacity + eliteCapacity * 2 + randomCutCapacity);
130 
131             // A. 分数最高的<精英个数>名后代，直接移入下一回合
132             for (int i = 0; i < eliteCapacity; i++) {
133                 newAnswerList.add(answerList.get(i));
134             }
135 
136             // B. 分数最高的<精英个数>名后代，随机两两配对，独立地产生2个后代，可能变异
137             List<Answer> eliteMateAnswerList = mate(game, answerList, eliteCapacity, 0);
138             newAnswerList.addAll(eliteMateAnswerList);
139 
140             // C. 分数最高的<普通个数>名后代，随机两两配对，对立地产生2个后代，可能变异
141             List<Answer> mateAnswerList = mate(game, answerList, capacity, 2);
142             newAnswerList.addAll(mateAnswerList);
143 
144             // D. 分数最高的<随机个数>名后代，从随机位置截断，截断后的部分全部随机生成
145             for (int i = 0; i < randomCutCapacity; i++) {
146                 newAnswerList.add(randomCut(game, answerList.get(i)));
147             }
148 
149             // 2. 更新循环状态
150             Collections.shuffle(newAnswerList);
151             sortAnswerList(newAnswerList);
152             Answer bestAnswer = newAnswerList.get(0);
153             turn++;
154             if (bestAnswer.getTotalReward() == lastTotalReward && bestAnswer.getBurstCount() == lastBurstCount && bestAnswer.length() == lastLength) {
155                 stableTurn++;
156             } else {
157                 stableTurn = 0;
158             }
159             lastTotalReward = bestAnswer.getTotalReward();
160             lastBurstCount = bestAnswer.getBurstCount();
161             lastLength = bestAnswer.length();
162             answerList = newAnswerList;
163             System.out.println(turn + ", " + stableTurn + ": " + bestAnswer);
164         }
165 
166         // 打印最终找到的最优解（16个）
167         System.out.println();
168         System.out.println("最优Top16：");
169         for (int i = 0; i < 16; i++) {
170             Answer answer = answerList.get(i);
171             System.out.println(answer);
172         }
173 
174         // 打印最优解
175         System.out.println();
176         System.out.println("最优解关键盘面：");
177         Answer bestAnswer = answerList.get(0);
178         System.out.println(Utils.answerString(game, bestAnswer));
179         return bestAnswer;
180     }
181 
182     /**
183      * 两两配对，每一对产生2个后代
184      * 重组断点50%为1个，25%为2个，25%为3个。
185      *
186      * @param game       游戏
187      * @param answerList 排序后的解答列表
188      * @param limit      数量限制，只有最前面的解答有资格产生后代
189      * @param policy     0: 对立产生后代，生成2个子代，分别随机地独占亲代的基因，亲代基因不会丢失，1或以上：独立产生policy个后代，子代基因从亲代完全随机获得，互不影响
190      * @return 生成的子代列表
191      */
192     public List<Answer> mate(Game game, List<Answer> answerList, int limit, int policy) {
193         int pairNum = limit >> 1;
194         ArrayList<Answer> parentAnswerList = new ArrayList<>(answerList.subList(0, limit));
195         Collections.shuffle(parentAnswerList);
196         List<Answer> childAnswerList = new ArrayList<>();
197         for (int pairNo = 0; pairNo < pairNum; pairNo++) {
198             Answer parentAnswer0 = parentAnswerList.get(2 * pairNo);
199             Answer parentAnswer1 = parentAnswerList.get(2 * pairNo + 1);
200             List<Point> parentPointList0 = parentAnswer0.getPointList();
201             List<Point> parentPointList1 = parentAnswer1.getPointList();
202             int minLength = Utils.min(parentAnswer0.length(), parentAnswer1.length());
203 
204             if (policy > 0) {
205                 // 独立产生后代，子代基因从亲代完全随机获得，互不影响
206                 for (int childNo = 0; childNo < policy; childNo++) {
207                     int breakPointNum = Utils.max(Utils.randInt(4), 1);
208                     List<Integer> matePositionList = new ArrayList<>();
209                     for (int i = 0; i < breakPointNum; i++) {
210                         matePositionList.add(Utils.randInt(minLength));
211                     }
212                     matePositionList.sort(Integer::compareTo);
213 
214                     List<Point> childPointList = new ArrayList<>();
215                     int starts = Utils.randInt(2);
216                     int lastMatePosition = 0;
217                     for (int i = 0; i < breakPointNum + 1; i++) {
218                         List<Point> fragmentPointList;
219                         List<Point> parentPointList = (i + starts) % 2 == 0 ? parentPointList0 : parentPointList1;
220                         if (i < breakPointNum) {
221                             int matePosition = matePositionList.get(i);
222                             fragmentPointList = parentPointList.subList(lastMatePosition, matePosition);
223                             lastMatePosition = matePosition;
224                         } else {
225                             fragmentPointList = parentPointList.subList(lastMatePosition, parentPointList.size());
226                         }
227                         childPointList.addAll(fragmentPointList);
228                     }
229                     childAnswerList.add(new Answer(childPointList));
230                 }
231             } else {
232                 // 对立产生后代，生成2个子代，分别随机地独占亲代的基因，亲代基因不会丢失
233                 int breakPointNum = Utils.max(Utils.randInt(4), 1);
234                 List<Integer> matePositionList = new ArrayList<>();
235                 for (int i = 0; i < breakPointNum; i++) {
236                     matePositionList.add(Utils.randInt(minLength));
237                 }
238                 matePositionList.sort(Integer::compareTo);
239 
240                 List<Point> childPointList0 = new ArrayList<>();
241                 List<Point> childPointList1 = new ArrayList<>();
242                 int lastMatePosition = 0;
243                 for (int i = 0; i < breakPointNum + 1; i++) {
244                     // 按照断点指定的位置，获得亲代基因的碎片
245                     List<Point> fragmentPointList0;
246                     List<Point> fragmentPointList1;
247                     if (i < breakPointNum) {
248                         int matePosition = matePositionList.get(i);
249                         fragmentPointList0 = parentPointList0.subList(lastMatePosition, matePosition);
250                         fragmentPointList1 = parentPointList1.subList(lastMatePosition, matePosition);
251                         lastMatePosition = matePosition;
252                     } else {
253                         fragmentPointList0 = parentPointList0.subList(lastMatePosition, parentPointList0.size());
254                         fragmentPointList1 = parentPointList1.subList(lastMatePosition, parentPointList1.size());
255                     }
256 
257                     // 拼接亲代基因碎片，得到子代基因
258                     if (i % 2 == 0) {
259                         childPointList0.addAll(fragmentPointList0);
260                         childPointList1.addAll(fragmentPointList1);
261                     } else {
262                         childPointList0.addAll(fragmentPointList1);
263                         childPointList1.addAll(fragmentPointList0);
264                     }
265                 }
266                 childAnswerList.add(new Answer(childPointList0));
267                 childAnswerList.add(new Answer(childPointList1));
268             }
269         }
270 
271         // 引入变异
272         for (Answer answer : childAnswerList) {
273             if (Math.random() < variationRate && answer.length() > 0) {
274                 int variationType = Utils.max(Utils.randInt(4), 1);
275                 int position = Utils.randInt(answer.length());
276                 switch (variationType) {
277                     case 1:
278                         // 修改一个步骤
279                         answer.getPointList().remove(position);
280                         // BREAK-THROUGH
281                     case 2:
282                         // 插入一个步骤，需要遍历到当前为止的棋盘状态，然后随机插入一个合法的位置
283                         int[][] arr = game.getInitArr();
284                         for (int i = 0; i < position; i++) {
285                             Point point = answer.getPointList().get(i);
286                             if (arr[point.getX()][point.getY()] <= 0) {
287                                 continue;
288                             }
289                             // 记录本次操作的结果，并更新棋盘状态
290                             MoveResult move = Game.move(arr, point);
291                             arr = move.getArr();
292                         }
293                         List<Point> remainPointList = Game.availablePoints(arr, 0);
294                         if (!remainPointList.isEmpty()) {
295                             Point point = remainPointList.get(Utils.randInt(remainPointList.size()));
296                             answer.getPointList().add(position, point);
297                         }
298                         break;
299                     case 3:
300                         // 删除一个步骤
301                         answer.getPointList().remove(position);
302                         break;
303                 }
304             }
305             calcTotalReward(game, answer);
306         }
307         return childAnswerList;
308     }
309 
310     /**
311      * 从随机位置斩断一个解，之后部分随机生成
312      *
313      * @param game   游戏
314      * @param answer 解答
315      * @return 生成的新解答
316      */
317     public Answer randomCut(Game game, Answer answer) {
318         int saveLength = Utils.randInt(answer.length());
319         List<Point> savePointList = answer.getPointList().subList(0, saveLength);
320         Answer newAnswer = new Answer(savePointList);
321         calcTotalReward(game, newAnswer);
322         return newAnswer;
323     }
324 
325     /**
326      * 验证解答，并计算总奖励
327      * 如果解答序列不完整，则随机生成之后序列，使其补充完整。
328      *
329      * @param game   游戏
330      * @param answer 答案
331      * @return 总奖励
332      */
333     public static int calcTotalReward(Game game, Answer answer) {
334         int totalReward = 0;
335         int minReward = 0;
336         int burstCount = 0;
337         int[][] arr = game.getInitArr();
338 
339         // 遍历已有点的列表，验证并计算结果
340         List<Point> pointList = new ArrayList<>(answer.getPointList());
341         for (Point point : answer.getPointList()) {
342             if (arr[point.getX()][point.getY()] <= 0) {
343                 // 这个点已经被清空了，因此跳过它，将其从列表中删除
344                 pointList.remove(point);
345                 continue;
346             }
347 
348             // 记录本次操作的结果，并更新棋盘状态
349             MoveResult move = Game.move(arr, point);
350             arr = move.getArr();
351             totalReward += move.getReward();
352             if (minReward > totalReward) {
353                 minReward = totalReward;
354             }
355             if (move.getCombo() > 0) {
356                 burstCount++;
357             }
358         }
359 
360         // 检查是否棋盘未被清空，是的话则随机生成之后的解答
361         List<Point> remainPointList = Game.availablePoints(arr, 0);
362         while (!remainPointList.isEmpty()) {
363             Point point = remainPointList.get(Utils.randInt(remainPointList.size()));
364             pointList.add(point);
365 
366             // 记录本次操作的结果，并更新棋盘状态
367             MoveResult move = Game.move(arr, point);
368             arr = move.getArr();
369             totalReward += move.getReward();
370             if (minReward > totalReward) {
371                 minReward = totalReward;
372             }
373             if (move.getCombo() > 0) {
374                 burstCount++;
375             }
376 
377             remainPointList = Game.availablePoints(arr, 0);
378         }
379 
380         // 追加完美通关奖励
381         if (burstCount <= 1) {
382             totalReward += Game.REWARD_PFT;
383         }
384 
385         answer.getPointList().clear();
386         answer.getPointList().addAll(pointList);
387         answer.setBurstCount(burstCount);
388         answer.setTotalReward(totalReward);
389         answer.setMinReward(minReward);
390         return totalReward;
391     }
392 
393     public static void sortAnswerList(List<Answer> answerList) {
394         answerList.sort(Comparator.comparing(Answer::getTotalReward).reversed().thenComparing(Answer::getBurstCount).thenComparing(Answer::length));
395     }
396 }

计算出的结果最终打印到控制台中。

实际用于解决该游戏后，发现了以下现象与问题：

1、最优解几乎总是先在棋盘上设置大量小水滴，之后一把将其全部引爆。

2、最优解如果直接打印，很多在同一个单元格的操作不放在一起，增加操作难度，比如一不小心点错单元格。

3、不是每次都能找到最优解，有的最优解出现概率很低，需要多次执行确认。

4、直接照着盘面改Array太麻烦了。

最终，我采取了以下措施：

1、输出解时。将一组不引爆水珠的一系列操作合并，增加一个次数参数。

2、将执行入口设置为了允许并发运行。一般同时执行3个实例，若找到的解的收益不同，则再执行几个看看。

3、我写了个程序，辅助将盘面录入为Array，以便粘贴。

 1 package main;
 2 
 3 import java.util.Scanner;
 4 
 5 public class FormatArray {
 6     public static void main(String[] args) {
 7         System.out.println("粘贴纯数字格式，获得格式化的Array对象。注意最后需要多加一个空行。");
 8         Scanner scanner = new Scanner(System.in);
 9         while (scanner.hasNext()) {
10             String line = scanner.next();
11             char[] chars = line.toCharArray();
12             StringBuilder builder = new StringBuilder();
13             builder.append("{");
14             for (int i = 0; i < chars.length; i++) {
15                 builder.append(chars[i]);
16                 if (i < chars.length - 1) {
17                     builder.append(", ");
18                 }
19             }
20             builder.append("},");
21             System.out.println(builder.toString());
22         }
23     }
24 }