本文介绍的是基于GP，并非A*算法，算是另类实现吧。
先看看地图定义，在文本文件中定义如下字符串，代表30列11行大小的地图
初始位置在左上角（0,0） ，值为1的是允许走的通的路，目标位置为右下角（29,10）
1 1 1 1 1 1 1 0 0 0 0 0 0 0 1 0 0 0 0 0 0 0 0 0 1 0 0 0 0 0 0 0 0 1 0 0 0 0 0 0 0 0 0 1 1 0 0 0 0 0 0 0 1 0 0 0 0 0 0 0 0 1 1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 1 0 0 0 0 0 0 0 0 0 1 0 0 0 0 0 0 0 1 1 0 0 0 0 0 0 0 0 0 1 0 0 0 0 0 0 0 1 0 0 0 0 0 0 0 0 0 0 1 0 0 0 0 0 0 0 1 1 1 1 1 1 0 0 0 0 0 1 0 0 0 0 0 0 0 0 0 0 0 0 1 0 0 0 0 0 1 0 0 0 0 0 0 0 0 0 0 0 0 1 0 0 0 0 0 1 0 0 0 0 0 0 0 0 0 0 0 0 1 1 1 1 1 1 1 1 1 1 1
算法运行效果如下：
"C:\Program Files\Java\jdk1.8.0_211\bin\java.exe" "-javaagent:C:\Program Files\JetBrains\IntelliJ IDEA 2019.1.2\lib\idea_rt.jar=54171:C:\Program Files\JetBrains\IntelliJ IDEA 2019.1.2\bin" -Dfile.encoding=UTF-8 -classpath "C:\Program Files\Java\jdk1.8.0_211\jre\lib\charsets.jar;C:\Program Files\Java\jdk1.8.0_211\jre\lib\deploy.jar;C:\Program Files\Java\jdk1.8.0_211\jre\lib\ext\access-bridge-64.jar;C:\Program Files\Java\jdk1.8.0_211\jre\lib\ext\cldrdata.jar;C:\Program Files\Java\jdk1.8.0_211\jre\lib\ext\dnsns.jar;C:\Program Files\Java\jdk1.8.0_211\jre\lib\ext\jaccess.jar;C:\Program Files\Java\jdk1.8.0_211\jre\lib\ext\jfxrt.jar;C:\Program Files\Java\jdk1.8.0_211\jre\lib\ext\localedata.jar;C:\Program Files\Java\jdk1.8.0_211\jre\lib\ext\nashorn.jar;C:\Program Files\Java\jdk1.8.0_211\jre\lib\ext\sunec.jar;C:\Program Files\Java\jdk1.8.0_211\jre\lib\ext\sunjce_provider.jar;C:\Program Files\Java\jdk1.8.0_211\jre\lib\ext\sunmscapi.jar;C:\Program Files\Java\jdk1.8.0_211\jre\lib\ext\sunpkcs11.jar;C:\Program Files\Java\jdk1.8.0_211\jre\lib\ext\zipfs.jar;C:\Program Files\Java\jdk1.8.0_211\jre\lib\javaws.jar;C:\Program Files\Java\jdk1.8.0_211\jre\lib\jce.jar;C:\Program Files\Java\jdk1.8.0_211\jre\lib\jfr.jar;C:\Program Files\Java\jdk1.8.0_211\jre\lib\jfxswt.jar;C:\Program Files\Java\jdk1.8.0_211\jre\lib\jsse.jar;C:\Program Files\Java\jdk1.8.0_211\jre\lib\management-agent.jar;C:\Program Files\Java\jdk1.8.0_211\jre\lib\plugin.jar;C:\Program Files\Java\jdk1.8.0_211\jre\lib\resources.jar;C:\Program Files\Java\jdk1.8.0_211\jre\lib\rt.jar;C:\Research-Code\demo1\target\classes;C:\Users\McKay\.m2\repository\io\jenetics\jenetics\5.1.0\jenetics-5.1.0.jar;C:\Users\McKay\.m2\repository\io\jenetics\jenetics.ext\5.1.0\jenetics.ext-5.1.0.jar;C:\Users\McKay\.m2\repository\io\jenetics\jenetics.prog\5.1.0\jenetics.prog-5.1.0.jar;C:\Users\McKay\.m2\repository\commons-lang\commons-lang\2.6\commons-lang-2.6.jar" MapGame.GameDemo 1 1 1 1 1 1 1 0 0 0 0 0 0 0 1 0 0 0 0 0 0 0 0 0 1 0 0 0 0 0 0 0 0 1 0 0 0 0 0 0 0 0 0 1 1 0 0 0 0 0 0 0 1 0 0 0 0 0 0 0 0 1 1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 1 0 0 0 0 0 0 0 0 0 1 0 0 0 0 0 0 0 1 1 0 0 0 0 0 0 0 0 0 1 0 0 0 0 0 0 0 1 0 0 0 0 0 0 0 0 0 0 1 0 0 0 0 0 0 0 1 1 1 1 1 1 0 0 0 0 0 1 0 0 0 0 0 0 0 0 0 0 0 0 1 0 0 0 0 0 1 0 0 0 0 0 0 0 0 0 0 0 0 1 0 0 0 0 0 1 0 0 0 0 0 0 0 0 0 0 0 0 1 1 1 1 1 1 1 1 1 1 1 G: 15769 -------------------- map-->Right-->Right-->Right-->Right-->Right-->Down-->Down-->Down-->Left-->Down-->Down-->Left-->Down-->Down-->Right-->Right-->Right-->Right-->Right-->Down-->Down-->Down-->Right-->Right-->Right-->Right-->Right-->Right-->Right-->Right-->Right-->Right--> E: 1320.0 Process finished with exit code 0
这边由于是套遗传编程，因此会定义几个固定操作算子：上移、下移、左移、右移；看看上移算子代码：
public class GoUpOp implements Op<TempMapInfo> { private MapController mapController; //地图控制工具类，比如判断能否移动到某个坐标、是否完成地图等 public GoUpOp(MapController mapController) { this.mapController=mapController; } @Override public String name() { return "Up"; } @Override public int arity() { return 1; } @Override public String toString() { return "Up"; } @Override public TempMapInfo apply(TempMapInfo[] tempMapInfos) { TempMapInfo newInfo=tempMapInfos[0].cloneMe(); //需要深度克隆，防止多线程对象直接互相影响 if(newInfo.currentLocationY==0) { newInfo.score-=1000; //已经在最上方了，不能再做上移动作了 newInfo.tag+="-UP"; //惩罚分，扣除1000分 return newInfo; } if(!mapController.canMove2(newInfo.currentLocationX, newInfo.currentLocationY-1)) //是否上移位置是路 { newInfo.score-=1000; //惩罚扣除1000分 newInfo.tag+="-UP"; return newInfo; } newInfo.score+=10; //可以走，奖励10分 newInfo.currentLocationY--; //递减y坐标 if(newInfo.visited.contains(newInfo.currentLocationX+","+newInfo.currentLocationY)) //不能重复访问点 newInfo.score-=1000; else newInfo.visited.add(newInfo.currentLocationX+","+newInfo.currentLocationY); if(mapController.isSuccess(newInfo.currentLocationX, newInfo.currentLocationY)) //判断是否地图完成 newInfo.score+=1000; newInfo.tag+="-UP"; return newInfo; } }
下面需要将这些操作算子嵌进GP中：
public static void main(String[] args) { Integer[][] map=GetMap(); dispalyMap(map); TempMapInfo mapInfo=new TempMapInfo(); mapInfo.score=0; mapInfo.currentLocationX=0; mapInfo.currentLocationY=0; //左上角为起点 List<Op<TempMapInfo>> terminals=new ArrayList<>(); terminals.add(Const.of("map", mapInfo)); MapController mapController=new MapController(map); final ISeq<Op<TempMapInfo>> TMS = ISeq.of(terminals); final ISeq<Op<TempMapInfo>> OPS = ISeq.of(new GoLeftOp(mapController), new GoRightOp(mapController), new GoUpOp(mapController), new GoDownOp(mapController)); final GameSearcher gameSearcher = GameSearcher.of( GameSearcher.codecOf( OPS, TMS, 20, t -> t.getGene().size() < 60 ) ); final Engine<ProgramGene<TempMapInfo>, Double> engine = Engine .builder(gameSearcher) .populationSize(500) .maximizing() .alterers( new SingleNodeCrossover<>(0.1), new Mutator<>(0.3), new UniformCrossover<>(0.5) ) .offspringSelector(new TournamentSelector<>(2)) .survivorsSelector(new TournamentSelector<>()) .build(); final EvolutionResult<ProgramGene<TempMapInfo>, Double> er = engine.stream() .limit(Limits.byExecutionTime(Duration.ofSeconds(60))) .collect(EvolutionResult.toBestEvolutionResult()); final ProgramGene<TempMapInfo> program = er.getBestPhenotype() .getGenotype() .getGene(); final TreeNode<Op<TempMapInfo>> tree = program.toTreeNode(); System.out.println("G: " + er.getTotalGenerations()); printTree(tree.depthFirstStream().collect(Collectors.toList())); System.out.println("E: " + gameSearcher._fitness(tree)); } private static void printTree(List<TreeNode<Op<TempMapInfo>>> lst) { System.out.println("--------------------"); for(TreeNode<Op<TempMapInfo>> node:lst) System.out.print(node.getValue()+"-->"); System.out.println(); }
上面的terminals变量是存放终结符的，此处是直接把操作动作放进去了，包含了分数、访问步骤、当前xy坐标等，只有1个变量
public class TempMapInfo { public int currentLocationX; public int currentLocationY; public double score; public List<String> visited=new ArrayList<>(); public String tag=""; public TempMapInfo() { visited.add("0,0"); } public TempMapInfo cloneMe() { TempMapInfo info=new TempMapInfo(); info.currentLocationX=this.currentLocationX; info.currentLocationY=this.currentLocationY; info.score=this.score; info.tag=this.tag; info.visited=new ArrayList<>(); for(String i:this.visited) info.visited.add(i); return info; } }
GameSearcher是对GP算法的编码、解码封装、计算分值，算是核心：
public final class GameSearcher implements Problem<Tree<Op<TempMapInfo>, ?>, ProgramGene<TempMapInfo>, Double> { private final Codec<Tree<Op<TempMapInfo>, ?>, ProgramGene<TempMapInfo>> _codec; private GameSearcher( final Codec<Tree<Op<TempMapInfo>, ?>, ProgramGene<TempMapInfo>> codec ) { _codec = requireNonNull(codec); } @Override public Function<Tree<Op<TempMapInfo>, ?>, Double> fitness() { return this::_fitness; } @Override public Codec<Tree<Op<TempMapInfo>, ?>, ProgramGene<TempMapInfo>> codec() { return _codec; } public double _fitness(final Tree<Op<TempMapInfo>, ?> program) { List<TempMapInfo> lst=new ArrayList<>(); lst.add(new TempMapInfo()); List<TempMapInfo> results=lst.stream().map(args -> Program.eval(program, args)).collect(Collectors.toList()); double score=results.stream().mapToDouble(a->a.score).sum(); //这行是用来统计整个操作算子序列总得分用的，很重要 return score; } public static GameSearcher of( final Codec<Tree<Op<TempMapInfo>, ?>, ProgramGene<TempMapInfo>> codec ) { return new GameSearcher(codec); } public static Codec<Tree<Op<TempMapInfo>, ?>, ProgramGene<TempMapInfo>> codecOf( final ISeq<Op<TempMapInfo>> operations, final ISeq<Op<TempMapInfo>> terminals, final int depth, final Predicate<? super ProgramChromosome<TempMapInfo>> validator ) { if (depth > 200 || depth < 0) { throw new IllegalArgumentException(format( "Tree depth out of range [0, 30): %d", depth )); } return Codec.of( Genotype.of(ProgramChromosome.of( depth, validator, operations, terminals )), Genotype::getGene ); } }
算法介绍完毕，pom依赖如下：
<dependencies> <!-- https://mvnrepository.com/artifact/io.jenetics/jenetics --> <dependency> <groupId>io.jenetics</groupId> <artifactId>jenetics</artifactId> <version>5.1.0</version> </dependency> <dependency> <groupId>io.jenetics</groupId> <artifactId>jenetics.ext</artifactId> <version>5.1.0</version> </dependency> <dependency> <groupId>io.jenetics</groupId> <artifactId>jenetics.prog</artifactId> <version>5.1.0</version> </dependency> <dependency> <groupId>commons-lang</groupId> <artifactId>commons-lang</artifactId> <version>2.6</version> </dependency> </dependencies>
