Skip to content

Instantly share code, notes, and snippets.

@kishida
Last active Feb 5, 2016
Embed
What would you like to do?
TSP with GA
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);
}
}
@kishida
Copy link
Author

kishida commented Feb 5, 2016

POINTS = 30;
COUNT = 50;
NEW_COUNT = 5;
MUTATION = 1;
STEP = 5;
d = 2367.0079746254396
2016-02-05 17 50 50

Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment