利用工作之余，實現了這個算法。
從小便喜歡人工智能，夢想長大成為科學家，去研究機器人。
實現這個算法，也算是對小時候的夢想邁出了一小步吧！
網上找了很久，找不到java實現，所以就自己切身寫了一下。
如果也有同樣愛好者，請聯系我：
msn be_heackAThotmail.com
程序模擬的是在10*10的一個城市當中，在ENV.java里面定義了15個城市(城市數目可以調整)
現在貼源代碼如下。
ENV.java 一些環境信息，也包含進化的一些數據，比如變異率，等等。
1 /**
2 *
3 */
4 package geneAlgo;
5
6 import java.util.ArrayList;
7 import java.util.List;
8
9 /**
10 * @author KONGHE
11 *
12 */
13 public class ENV {
14 public static int GENE_LENGTH = 15;//如果要添加新的城市，必須要修改這里對應
15
16 public static int GROUP_SIZE = 50;
17
18 public static double DISSOCIATION_RATE = 0.01;
19
20 public static double ADAPT_GOAL = 26.6;
21
22 public static int SEQ_MAX_GROUP = 8;
23
24 public static int SEQ_GROUP_MAX_LENGTH = 13;
25
26 public static int SEQ_BREAK_START = 1;
27
28 public static double CHANGE_FIRST_SEQ = 0.5;
29
30 public static double IF_HAVE_CHILDREN = 0.8;
31
32 public static int KEEP_BEST_NUM = 1;// keep the best to next generation
33
34 public static int DIS_AFTER_MAX_GENE = 40;//after how many generation will it change itself
35
36 // how much rate to keep bad rate while compare
37 public static double KEEP_BAD_INDIVIDAL = 0.0;
38
39 public static double KEEP_BAD_INDIVIDAL_MAX = 0.5;
40
41 public static double KEEP_BAD_INDIVIDAL_MIN = 0.0;
42
43 public static int CITIES_LIST[][] = new int[ENV.GENE_LENGTH][2];
44 static {
45 CITIES_LIST[0][0] = 1;
46 CITIES_LIST[0][1] = 1;
47 CITIES_LIST[1][0] = 3;
48 CITIES_LIST[1][1] = 1;
49 CITIES_LIST[2][0] = 2;
50 CITIES_LIST[2][1] = 2;
51 CITIES_LIST[3][0] = 1;
52 CITIES_LIST[3][1] = 4;
53 CITIES_LIST[4][0] = 3;
54 CITIES_LIST[4][1] = 5;
55 CITIES_LIST[5][0] = 5;
56 CITIES_LIST[5][1] = 4;
57 CITIES_LIST[6][0] = 6;
58 CITIES_LIST[6][1] = 2;
59 CITIES_LIST[7][0] = 7;
60 CITIES_LIST[7][1] = 4;
61 CITIES_LIST[8][0] = 8;
62 CITIES_LIST[8][1] = 5;
63 CITIES_LIST[9][0] = 8;
64 CITIES_LIST[9][1] = 7;
65 CITIES_LIST[10][0] = 4;
66 CITIES_LIST[10][1] = 8;
67 CITIES_LIST[11][0] = 6;
68 CITIES_LIST[11][1] = 6;
69 CITIES_LIST[12][0] = 4;
70 CITIES_LIST[12][1] = 2;
71 CITIES_LIST[13][0] = 7;
72 CITIES_LIST[13][1] = 6;
73 CITIES_LIST[14][0] = 2;
74 CITIES_LIST[14][1] = 7;
75 }
76
77 public static long getRandomInt(long from, long to) {
78
79 return from > to ? from : (long) Math.round(Math.random() * (to - from) + from);
80 }
81
82 public static boolean doOrNot(double rate) {
83 return Math.random() <= rate;
84 }
85
86 public static List getGeneLinkList() {
87 List geneList = new ArrayList();
88 for (int i = 1; i <= ENV.GENE_LENGTH - 1; i++) {
89 geneList.add(i);
90 }
91 return geneList;
92 }
93 }
94
Evolution.java 主程序
1 package geneAlgo;
2
3 public class Evolution {
4
5 public static void main(String[] args) {
6 Population originalPopulation = Population.getOriginalPopulation();
7
8 Individal x = Individal.getRandomIndividal();
9
10 int i = 0;
11 while (originalPopulation.getBestAdapt().getAdaptability() > ENV.ADAPT_GOAL) {
12 // while(i<20){
13 originalPopulation.evolute();
14 originalPopulation.printBest();
15 // originalPopulation.print();
16 i++;
17 }
18 originalPopulation.printBest();
19 // Individal y = Individal.getRandomIndividal();
20 // x.print();
21 // y.print();
22 // // //x.print();
23 // x.makeBabyWith(y);
24
25 // GeneSeqMap map = new GeneSeqMap();
26 // map.addObjects(3, 4);
27 // map.addObjects(4, 6);
28 // map.addObjects(7, 3);
29 // map.print();
30 // Population x = evolution.getOriginalPopulation();
31 // //System.out.println(x.getAdaptability());
32 // x.print();
33 // System.out.println(ENV.doOrNot(1));
34 }
35
36 }
37
GeneSeqMap.java 工具類
1 package geneAlgo;
2
3 import java.util.HashMap;
4 import java.util.Iterator;
5 import java.util.Map;
6 import java.util.Set;
7
8 public class GeneSeqMap {
9 private Map<Integer, Integer> seqMap = new HashMap<Integer, Integer>();
10
11 public void addObjects(int a, int b) {
12 if (seqMap.containsKey(b) && seqMap.get(b) == a) {
13 seqMap.remove(b);
14 return;
15 }
16 if (seqMap.containsKey(a)) {
17 // in this project, it's not possible
18 int tempValue = seqMap.get(a);
19 seqMap.remove(a);
20 seqMap.put(b, tempValue);
21 return;
22 } else if (seqMap.containsValue(a)) {
23 Set entries = seqMap.entrySet();
24 Iterator iter = entries.iterator();
25 while (iter.hasNext()) {
26 Map.Entry entry = (Map.Entry) iter.next();
27 Integer key = (Integer) entry.getKey();
28 Integer value = (Integer) entry.getValue();
29 if (value == a) {
30 seqMap.remove(key);
31 seqMap.put(key, b);
32 if(seqMap.containsKey(b)){
33 int val=seqMap.get(b);
34 seqMap.remove(b);
35 seqMap.remove(key);
36 seqMap.put(key, val);
37 }
38 return;
39 }
40 }
41 }
42 if (seqMap.containsKey(b)) {
43 int value = seqMap.get(b);
44 seqMap.remove(b);
45 seqMap.put(a, value);
46 return;
47 } else if (seqMap.containsValue(b)) {
48 // it's not possible
49 return;
50 }
51 seqMap.put(a, b);
52 }
53
54 public Integer getValueByKey(Integer key) {
55 if (seqMap.containsKey(key)) {
56 return seqMap.get(key);
57 } else {
58 return null;
59 }
60 }
61
62 public Integer getKeyByValue(Integer value) {
63 if (seqMap.containsValue(value)) {
64 Set entries = seqMap.entrySet();
65 Iterator iter = entries.iterator();
66 while (iter.hasNext()) {
67 Map.Entry<Integer, Integer> entry = (Map.Entry<Integer, Integer>) iter.next();
68 Integer key = entry.getKey();
69 Integer val = entry.getValue();
70 if (value == val) {
71 return key;
72 }
73 }
74 }
75 return null;
76
77 }
78
79 public void print() {
80 Set<Integer> keys = seqMap.keySet();
81 Iterator iter = keys.iterator();
82 while (iter.hasNext()) {
83 Integer key = (Integer) iter.next();
84 System.out.println(key + " " + seqMap.get(key) + ";");
85 }
86 }
87 }
88
Individal.java 個體類
1 package geneAlgo;
2
3 import java.util.ArrayList;
4 import java.util.List;
5
6 public class Individal {
7 private int genes[] = new int[ENV.GENE_LENGTH];
8
9 public int[] getGenes() {
10 return genes;
11 }
12
13 public void setGenes(int[] genes) {
14 this.genes = genes;
15 }
16
17 private int[] getClone(int[] source) {
18 int result[] = new int[source.length];
19 for (int i = 0; i < source.length; i++) {
20 result[i] = source[i];
21 }
22 return result;
23 }
24
25 public Individal[] makeBabyWith(Individal partner) {
26 // parents have only two children
27 Individal children[] = new Individal[2];
28 int genes1[] = getClone(this.genes);
29 int genes2[] = getClone(partner.getGenes());
30 if (ENV.doOrNot(ENV.IF_HAVE_CHILDREN)) {
31 GeneSeqMap seqMap = new GeneSeqMap();// used to correct illegal exchange
32 List<Integer> seqBreak = new ArrayList<Integer>();
33 List<Integer> seqChange = new ArrayList<Integer>();
34 seqBreak.add(ENV.SEQ_BREAK_START);
35 int i = (int) ENV.getRandomInt(1, ENV.GENE_LENGTH - ENV.SEQ_BREAK_START - 1);
36 int j = 1;
37 while (seqBreak.get(seqBreak.size() - 1) + i <= ENV.GENE_LENGTH - 1 && j <= ENV.SEQ_MAX_GROUP) {
38 seqBreak.add(seqBreak.get(seqBreak.size() - 1) + i);
39 i = (int) ENV.getRandomInt(i + 1, ENV.GENE_LENGTH);
40 }
41
42 j = 0;
43 boolean changeFirstSeq = ENV.doOrNot(ENV.CHANGE_FIRST_SEQ);
44 for (i = 0; i < seqBreak.size(); i++) {
45 int nextBreakPos = (i == seqBreak.size() - 1 ? ENV.GENE_LENGTH : seqBreak.get(i + 1));
46 for (int m = seqBreak.get(i); m < nextBreakPos; m++) {
47 if ((j == 0 && changeFirstSeq) || (j == 1 && !changeFirstSeq)) {
48 seqMap.addObjects(genes1[m], genes2[m]);
49 int temp = genes1[m];
50 genes1[m] = genes2[m];
51 genes2[m] = temp;
52 seqChange.add(m);
53 } else {
54 break;
55 }
56 }
57 j = 1 - j;
58 }
59
60 for (int m = 0; m < ENV.GENE_LENGTH; m++) {
61 if (seqChange.contains(m)) {
62 continue;
63 }
64 Integer genes1Change = seqMap.getKeyByValue(genes1[m]);
65 Integer genes2Change = seqMap.getValueByKey(genes2[m]);
66 if (genes1Change != null) {
67 genes1[m] = genes1Change.intValue();
68 }
69 if (genes2Change != null) {
70 genes2[m] = genes2Change.intValue();
71 }
72 }
73
74 }
75 children[0] = new Individal();
76 children[1] = new Individal();
77 children[0].setGenes(genes1);
78 children[1].setGenes(genes2);
79 return children;
80 }
81
82 public void dissociation() {
83 // change own gene sequence by dissociation percente.
84 for (int i = 1; i < genes.length; i++) {
85 // boolean ifChange = ENV.doOrNot(ENV.DISSOCIATION_RATE * (ENV.GENE_LENGTH - 1));
86 boolean ifChange = ENV.doOrNot(ENV.DISSOCIATION_RATE);
87 if (ifChange) {
88 // long start = ENV.getRandomInt(1, ENV.GENE_LENGTH - 1);
89 long start = i;
90 long goStep = ENV.getRandomInt(1, ENV.GENE_LENGTH - 2);
91 long changePos = start + goStep;
92 if (changePos >= ENV.GENE_LENGTH) {
93 changePos = changePos - ENV.GENE_LENGTH + 1;
94 }
95 int temp = genes[(int) start];
96 genes[(int) start] = genes[(int) changePos];
97 genes[(int) changePos] = temp;
98 }
99
100 }
101 }
102
103 public void print() {
104 for (int i = 0; i < genes.length; i++) {
105 System.out.print(genes[i] + ";");
106 }
107 System.out.print("--" + this.getAdaptability());
108 System.out.println();
109 }
110
111 public double getAdaptability() {
112 int seq[] = this.getGenes();
113 double totalLength = 0;
114 for (int i = 0; i < seq.length - 1; i++) {
115 double length = Math.hypot(ENV.CITIES_LIST[seq[i]][0] - ENV.CITIES_LIST[seq[i + 1]][0],
116 ENV.CITIES_LIST[seq[i]][1] - ENV.CITIES_LIST[seq[i + 1]][1]);
117 totalLength += length;
118 }
119 return totalLength;
120 }
121
122 public static Individal getRandomIndividal() {
123 Individal individal = new Individal();
124 int[] geneSeq = individal.getGenes();
125 List geneList = ENV.getGeneLinkList();
126 int tempLength = geneList.size();
127 for (int i = 1; i <= tempLength; i++) {
128 long random = ENV.getRandomInt(0, ENV.GENE_LENGTH * 5);
129 int seq = (int) random % geneList.size();
130 geneSeq[i] = (Integer) geneList.get(seq);
131 geneList.remove(seq);
132 }
133 return individal;
134 }
135
136 }
137
Population.java 群體類
1 package geneAlgo;
2
3 import java.util.ArrayList;
4 import java.util.List;
5
6 public class Population {
7
8 private long eras = 0;
9
10 private double historyBest = ENV.ADAPT_GOAL + 50;
11
12 private List<Individal> individals = new ArrayList<Individal>();
13
14 public List<Individal> getIndividals() {
15 return individals;
16 }
17
18 public void setIndividals(List<Individal> individals) {
19 this.individals = individals;
20 }
21
22 public boolean addIndividal(Individal individal) {
23 boolean result = true;
24 if (this.individals.size() >= ENV.GROUP_SIZE) {
25 result = false;
26 } else {
27 this.individals.add(individal);
28 }
29 return result;
30 }
31
32 public void print() {
33 for (int i = 0; i < individals.size(); i++) {
34 individals.get(i).print();
35 }
36 }
37
38 public static Population getOriginalPopulation() {
39 Population original = new Population();
40 Individal a = Individal.getRandomIndividal();
41 Individal b = Individal.getRandomIndividal();
42 while (original.addIndividal(a.getAdaptability() < b.getAdaptability() ? a : b)) {
43 a = Individal.getRandomIndividal();
44 b = Individal.getRandomIndividal();
45 }
46 return original;
47 }
48
49 public void evolute() {
50 Population evoPool = new Population();
51 // make evolution pool
52 while (evoPool.individals.size() < ENV.GROUP_SIZE) {
53 int indi1 = (int) ENV.getRandomInt(0, ENV.GROUP_SIZE - 1);
54 int indi2 = (int) ENV.getRandomInt(0, ENV.GROUP_SIZE - 1);
55 while (indi2 == indi1) {
56 indi2 = (int) ENV.getRandomInt(0, ENV.GROUP_SIZE - 1);
57 }
58 if (this.individals.get(indi1).getAdaptability() == this.individals.get(indi2).getAdaptability()) {
59 if (ENV.KEEP_BAD_INDIVIDAL <= ENV.KEEP_BAD_INDIVIDAL_MAX) {
60 ENV.KEEP_BAD_INDIVIDAL += 0.0004;
61 }
62 } else {
63 if (ENV.KEEP_BAD_INDIVIDAL >= ENV.KEEP_BAD_INDIVIDAL_MIN)
64 ENV.KEEP_BAD_INDIVIDAL -= 0.00005;
65 }
66 boolean ifKeepBad = ENV.doOrNot(ENV.KEEP_BAD_INDIVIDAL);
67 if (ifKeepBad) {
68 evoPool.addIndividal(this.individals.get(indi1).getAdaptability() > this.individals.get(indi2)
69 .getAdaptability() ? this.individals.get(indi1) : this.individals.get(indi2));
70 } else {
71 evoPool.addIndividal(this.individals.get(indi1).getAdaptability() <= this.individals.get(indi2)
72 .getAdaptability() ? this.individals.get(indi1) : this.individals.get(indi2));
73 }
74 // if (this.individals.get(indi1).getAdaptability() <= this.individals.get(indi2).getAdaptability()) {
75 // evoPool.addIndividal(individals.get(indi1));
76 // } else {
77 // evoPool.addIndividal(individals.get(indi2));
78 // }
79 }
80 Population newPopulation = new Population();
81 for (int i = 0; i < ENV.GROUP_SIZE - 1; i = i + 2) {
82 Individal children[] = evoPool.getIndividals().get(i).makeBabyWith(evoPool.getIndividals().get(i + 1));
83 children[0].dissociation();
84 children[1].dissociation();
85 newPopulation.addIndividal(children[0]);
86 newPopulation.addIndividal(children[1]);
87 }
88 this.setIndividals(newPopulation.getIndividals());
89 this.eras++;
90 }
91
92 public long getEras() {
93 return eras;
94 }
95
96 public void setEras(long eras) {
97 this.eras = eras;
98 }
99
100 public void printBest() {
101 Individal x = getBestAdapt();
102 x.print();
103 System.out.print("eras:" + this.getEras());
104 System.out.print(" historyBest:" + this.historyBest);
105 System.out.print(" keep bad rate:" + ENV.KEEP_BAD_INDIVIDAL);
106 System.out.println();
107 }
108
109 public Individal getBestAdapt() {
110 Individal x = null;
111 for (int i = 0; i < ENV.GROUP_SIZE; i++) {
112 if (x == null) {
113 x = this.getIndividals().get(i);
114 } else {
115 if (this.getIndividals().get(i).getAdaptability() < x.getAdaptability()) {
116 x = this.getIndividals().get(i);
117 }
118 }
119 }
120 if (x.getAdaptability() < this.historyBest) {
121 this.historyBest = x.getAdaptability();
122 }
123 return x;
124 }
125 }
126