TSP with GA

TSPGA.java

import java.awt.Graphics;
import java.awt.GridLayout;
import java.awt.image.BufferedImage;
import java.util.ArrayList;
import java.util.Arrays;
import java.util.Collections;
import java.util.DoubleSummaryStatistics;
import java.util.List;
import java.util.Random;
import java.util.stream.Collectors;
import java.util.stream.IntStream;
import java.util.stream.Stream;
import javax.swing.ImageIcon;
import javax.swing.JFrame;
import javax.swing.JLabel;

/**
 * @author naoki
 */
public class TSPGA {
    public static void main(String[] args) {
        JFrame f = new JFrame("TSP Genetic Algorithm");
        f.setDefaultCloseOperation(JFrame.EXIT_ON_CLOSE);
        f.setSize(500, 700);
        f.setLayout(new GridLayout(2, 1));

        List<Double> ds = Arrays.asList(3., 4., 5.);
        Collections.sort(ds, Double::compare);
        System.out.println(ds);

        final int POINTS = 30;
        Random r = new Random(1235);
        int[] xs = r.ints(POINTS, 0, 300).toArray();
        int[] ys = r.ints(POINTS, 0, 300).toArray();

        BufferedImage route = new BufferedImage(320, 320, BufferedImage.TYPE_INT_RGB);
        Graphics grp = route.getGraphics();
        for(int i = 0; i < xs.length; ++i) {
            grp.drawRect(xs[i] + 9, ys[i] + 9, 3, 3);
        }
        f.add(new JLabel(new ImageIcon(route)));

        class Gene {
            int[] gene;
            int[] route;
            double dist;
            Gene() {
                this(IntStream.range(0, xs.length).map(i -> r.nextInt(xs.length - i)).toArray());
            }
            Gene(int[] gene) {
                this.gene = gene;
                List<Integer> list = IntStream.range(0, xs.length).boxed().collect(Collectors.toList());
                route = IntStream.of(gene).map(list::remove).toArray();
                for(int i = 0; i < route.length; ++i){
                    int j = (i + 1) % route.length;
                    dist += Math.sqrt((xs[route[i]] - xs[route[j]]) * (xs[route[i]] - xs[route[j]]) +
                            (ys[route[i]] - ys[route[j]]) * (ys[route[i]] - ys[route[j]]));
                }
            }
        }

        List<DoubleSummaryStatistics> hist = new ArrayList<>();

        // 最初の世代
        final int COUNT = 50;
        final int NEW_COUNT = 5;
        final int MUTATION = 1;
        Gene[] genes = Stream.generate(() -> new Gene()).limit(COUNT).toArray(Gene[]::new);
        hist.add(Stream.of(genes).mapToDouble(g -> g.dist).summaryStatistics());
        for(int ii = 0; ii < 300; ++ii){
            List<Gene> generation = new ArrayList(Arrays.asList(genes));
            for(int i = 0; i < COUNT - NEW_COUNT; ++i) {
                //交差
                int g1 = r.nextInt(genes.length);
                int g2 = r.nextInt(genes.length - 1);
                if (g2 >= g1) ++g2;
                int p = r.nextInt(POINTS - 2) + 1;
                int[] newg = IntStream.concat(
                        IntStream.of(genes[g1].gene).limit(p),
                        IntStream.of(genes[g2].gene).skip(p)).toArray();
                //突然変異
                int s = r.nextInt(MUTATION + 1);
                for (int j = 0; j < s; ++j) {
                    int sp = r.nextInt(POINTS);
                    newg[sp] = r.nextInt(POINTS - sp);
                }
                generation.add(new Gene(newg));
            }
            // 新しいものも追加
            Stream.generate(() -> new Gene()).limit(NEW_COUNT).forEach(generation::add);

            Collections.sort(generation, (gl, gr) -> Double.compare(gl.dist, gr.dist));
            List<Gene> newGen = Stream.generate(() -> generation.remove(0)).limit(3).collect(Collectors.toList());

            // 淘汰
            genes = Stream.concat(newGen.stream(),
                    IntStream.generate(() -> r.nextInt(COUNT - 3)).limit(COUNT - 3).mapToObj(i -> generation.remove(i))).toArray(Gene[]::new);
            hist.add(Stream.of(genes).mapToDouble(g -> g.dist).summaryStatistics());
        }
        Gene minGene = Collections.min(Arrays.asList(genes), (gl, gr) -> Double.compare(gl.dist, gr.dist));
        System.out.println(minGene.dist);
        int[] minRoute = minGene.route;

        // ルート描画
        for(int i = 0; i < minRoute.length; ++i){
            int j = (i + 1) % minRoute.length;
            grp.drawLine(xs[minRoute[i]] + 10, ys[minRoute[i]] + 10, xs[minRoute[j]] + 10, ys[minRoute[j]] + 10);
        }

        // グラフ描画
        double max = hist.stream().mapToDouble(h -> h.getMax()).max().getAsDouble();
        double min = hist.stream().mapToDouble(h -> h.getMin()).min().getAsDouble();
        BufferedImage img = new BufferedImage(500, 300, BufferedImage.TYPE_INT_RGB);
        Graphics gg = img.getGraphics();
        double solved = min;
        double range = max - solved;
        gg.drawLine(20, 275, 470, 275);
        final int STEP = 5;
        for(int i = STEP; i < hist.size(); i += STEP){
            {
                int y1 = (int)((hist.get(i - STEP).getMin() - solved) / range * 250);
                int y2 = (int)((hist.get(i).getMin() - solved) / range * 250);
                gg.drawLine(i * 450 / hist.size() + 20, 275 - y1, (i + STEP) * 450 / hist.size() + 20, 275 - y2);
            }
            {
                int y1 = (int)((hist.get(i - STEP).getMax() - solved) / range * 250);
                int y2 = (int)((hist.get(i).getMax() - solved) / range * 250);
                gg.drawLine(i * 450 / hist.size() + 20, 275 - y1, (i + STEP) * 450 / hist.size() + 20, 275 - y2);
            }
            {
                int y1 = (int)((hist.get(i - STEP).getAverage()- solved) / range * 250);
                int y2 = (int)((hist.get(i).getAverage()- solved) / range * 250);
                gg.drawLine(i * 450 / hist.size() + 20, 275 - y1, (i + STEP) * 450 / hist.size() + 20, 275 - y2);
            }
        }
        f.add(new JLabel(new ImageIcon(img)));

        f.setVisible(true);
    }
}

POINTS = 30;
COUNT = 50;
NEW_COUNT = 5;
MUTATION = 1;
STEP = 5;
d = 2367.0079746254396