Genetic Algorithm - Traveller in Space
遗传算法是我见过的最有趣的算法,尤其是拿它来解决一些问题的时候.
在这里,我使用这个算法来解决了一个简单的问题.这个问题是著名的旅行者问题,假设这位旅行者要经过n座城市并最终回到起点,怎样的路线是最经济的(最短的).
抽象起来说就是,假设空间中有一组任意的点,找到连通它们的最短路径.我的程序解决的步骤是这样的: 首先创建一组随机的路径(当然要确保它们是合法的),然后对它们进行测试,这里所谓的测试就是计算出每一条路径的实际长度.之后进行排序,按照从最短向最长排序.这样就得到了一组排序后的路径集合,排在最前面的越接近所期望的答案.
之后我将这个集合头部的20%左右的数据复制到总集合中去,当然是存在一个复制概率问题的,这个值相对来说非常小.然后我用了大致是前40%的路径集合去和整个路径集合进行杂交与变异.重复这个过程就可以非常有效地推动整个系统的进化.
更多的细节问题,比如交叉的实现和精英主义的引入,请到论坛讨论 http://arc.net.cn/bbs/ , 同时可以下载这个程序的源代码: http://arc.net.cn/dl/gats.tar.bz2
Genetic Algorithm Outline
Initialize population.
|
V
+-> Evaluate the fitness of each chromosome.
| |
| V
| Selection two parent chromosomes according to fitness.
| |
| V
| Crossover.
| |
| V
| Mutation.
| |
| V
| Insert offspring into population.
| |
| V
+-- Test, If the end condition is satisfied, stop.
|
V
Return the best solution in current population.
[ Encoding ]
(Binary Encoding) The most used way of encoding is a binary string, the chromosome then could look like this:
101011010001101 010100010101011
(Permutation Encoding) The permutation encoding of each chromosome then could look like that:
2 5 7 9 2 3 4 2 8 7 3 5 3 9 1 7
(Value encoding) and in value encoding, every chromosome is a string of some values. Values can be anything connected to problem.
2.43 3.32 7.54 4.31 2.97 (Right) (Left) (Stop) (Right) (Left)
(Tree encoding) Tree encoding is used mainly for evolving programs or expressions, for genetic programming. The chromosome look like this:
+--- WALL DO_UNTILS ---+--- DOOR
| |
DO_UNTIL ---+--- WINDOW +--- WALL
[ Binary Encoding Crossover and Mutation ] Crossover:
Single point crossover: (The crossover point can be any where in each chromosome.)
IF |
Parent.A = 00000|000000
Parent.B = 11111|111111
THEN |
Offspring = 00000|111111
|
+------ Crossover Point.
Two point crossover: (The crossover points can be any where in each chromosome.)
IF | |
Parent.A = 00000|000|000
Parent.B = 11111|111|111
THEN | |
Offspring = 00000|111|000
| |
+---+--- Crossover Points.
Uniform crossover: (bits are randomly copied from the first or from the second parent.)
IF
Parent.A = 00000000000
Parent.B = 11111111111
THEN
Offspring = 01010100111
Arithmetic crossover: (For example, Boolean algorithm)
IF
Parent.A = 01010101010
Parent.B = 10101010101
Parent.A (AND) Parent.B
THEN
Offspring = 00000000000
Mutation: (Selected bits are inverted)
IF
Offspring = 00000000000
THEN | |
Mutation = 00000100100
| |
+--+-- Mutation Points.
Mutation Rate:
This is the chance that a bit within a chromosome will be inversed. (0 becomes 1, 1 becomes 0). This is usually a very low value for binary encoding, for example: 0.001.
[ Permutation Encoding Crossover and Mutation ] Crossover: Single point crossover:
IF |
Parent.A = 12345|67890
Parent.B = 09876|54321
THEN |
Offspring = 12345|54321
|
+------ Crossover Point.
Mutation: (Order changing)
IF
Offspring = 1234554321
THEN | |
Mutation = 1234524351
| |
+--+--- Mutation Points.
[ Value Encoding Crossover and Mutation ] Crossover: (All crossovers from binary encoding can be used)
Mutation: (Added or subtracted a values to an element)
IF
Offspring = (2.43 3.32 7.54 4.31 2.97)
THEN | |
Mutation = (2.43 3.32 7.04 4.81 2.97)
| |
+-----+--- Mutation Points.
[ Tree Encoding Crossover and Mutation ] Crossover:
IF
Parent.A = DO_UNTIL ---+--- WALL
|
+-|- WINDOW
|
+----------- Mutation Points.
|
Parent.B = DO_UNTIL ---+-|- WINDOW
|
+--- DOOR
THEN
Offspring = DO_UNTIL ---+--- WALL
|
+--- DOOR