努力,成长,提高

在追求中进步
数据加载中……
用遗传算法实现旅行商问题的Java实现
利用工作之余,实现了这个算法。
从小便喜欢人工智能,梦想长大成为科学家,去研究机器人。
实现这个算法,也算是对小时候的梦想迈出了一小步吧!
网上找了很久,找不到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 


posted on 2009-02-08 19:03 孔阳 阅读(2083) 评论(0)  编辑  收藏


只有注册用户登录后才能发表评论。


网站导航: