<急> 关于 GENETIC ALGORITHM

山羊座

由于小弟要被抽中要做一份报告
而且还要PRESENT
题目是＂GENETIC ALGORITHM＂
但小弟没有接触过这些知识
请问你们知道有关资料吗？
其实
主要是介绍什么是GENETIC ALGORITHM
不需要太复杂的解释
你们有什么网站可以介绍吗？
最好有一些图片和英文解释

希望可以得到热心人士的协助

agsd121

今天心情好,就回答这问题....

中文:进化算法.  john holland算是创始人. Beam search的一种. 属于AI里的一个sub-branch.
一下大概列出它的分类:
1. AI
   A. Hard computing
     I. Expert systems
     II. Ontology
     ...
   B. Soft computing
     I. Artifician Neural Networks
     II. Fuzzy logic
     III. Evolutionary Algorithms (包括Genetic algorithms)

在GA里头, 有几个名字:gene, chromosome, population,fitness function, evolution cycles.
genes 是最小的unit (一般来说), 可以代表一个大function里的一个variable,或者一个组里的一个成员.

chromosome是几个genes的整合. 可以代表一个完整的candidate solution或这一个solution的一部分.

population是几个chromosomes的整和. 代表一个当前的problem space samples.

fitness function是用来叛变一个chromosome被挑选的机率. 因为进化论是说: 比较强壮的individuals更有可能活下来生产新的下一代, 所以fitness function是个带动selection 的mechanism.

evolution cycle - 在soft computing里, 很多时候不会有明确目标或者最好的目标. 所以evolution cycle是termination conditions之一. 例如说让GA跑上75 cycles,挑出最好成绩来做答案是很平常的事. 不过一个好的的设计一般convergence是20-40 cycles之内.
----------------------------------------------------
Encoding: genes 一般要么是binary, float或者是string representations. binary是john holland最早proposed的, 后来floating points 的被提出而且被正式performance很不错. string representations就看问题而定.

decoding: encoding 的相反.
由于encoding和decoding让representations跟问题隔了少许, 一般那些人要批评的都会批评这里因为有时候每个chromosomes被fitness function evaluate时都得一个个decode.
如何encode和decode是GA里最头痛的地方. 没有好的guidelines来指导, 唯一的是经验和对问题的认识.. 就如设计fuzzy sets 一样样.待会给你个例子...
------------------------------------------------------------------------------------
Genetic operators: RNA和DNA里头时常有splicing,crossover, mutation的情况. 所以GA也有这类的operators来让它更有效的sample problem space.最传统的是:crossover和mutation.

standard crossovers有两种:single point crossover和multipoint crossover.
以下是multipoint crossover的例子:

之前            |     |    <-- crossover points
Chromosome A: 1 2 3 4 5 6
Chromosome B: 7 8 9 A B C
过后:
Chromosome A': 1 8 9 A B 6
Chromosome B': 7 2 3 4 5 C
single point的就只挑个offset而已.

mutation operator:
                  |       <-- mutate
Chromosome A: 1 2 3 4 5 6
to
Chromosome A':1 2 Z 4 5 6

两个用处都不同, 简单的来说, crossover ops promote exchange of genetic materials, whereas mutate operator promotes population diversity and resets a part of the sampling process to new areas in the problem space.

在nature里, 这些都有一定机率的, 虽然现在科学还不知道他们的机率, 但是试验的成绩是建议将 这些operators的机率保持在5%-10%之间. 太高,就变random walk,太低就是gradient based methods了.
------------------------------------------------------------------------------------------
如何做selection:
每个individual都有自己的fitness (用fitness function 来定),所以一个很普遍的方法是说:
Let S = Sum of Fi for i = 1 to n ,and  Fi = fitness of individual(chromosome) i.
那么i 的fitness(针对于整个population): Ni = Fi / S
有了这植,就可以造个cumulative fitness function, 基本上是将 Ni for i = 1 - n,全加起来,然后用uniform random number generator来制造随机数,来挑选一个individual进新的population.
例子:
F1 = 0.1 (for chromosome C1)
F2 = 0.3 (for chromosome C2)
F3 = 0.2 (for chromosome C3)
F4 = 0.1 (for chromosome C4)
那么:
N1 = 0.1
N2 = 0.4
N3 = 0.6
N4 = 0.7
所以random number 的range是0.0 - 0.7, 假如说新的population有四个individuals,那么说我们拿到的random numbers 是:0.092, 0.456, 0.521, 0.4, 新的population就是: C1, C2, C2, C2.

--------------------------------------------------------------------------------------
GA (pseudo code):
Pc = crossover probability, Pm = mutation probability, P = population, I = individual.
1. Initialize population P1 with random individuals
2. While(not termination conditions)
3.    Evaluate individual fitness
4.    Select individuals from Pi to form new population Pi+1.
5.    For each I in Pi+1, Perform Crossover based on Pc
6.    For each I in Pi+1, Perform mutation based on Pm
7  End While
------------------------------------------------------------------------

agsd121

强点: 简单,容易明白,parallel, informed and heuristics based search, 超级快(不过有可能解决不了问题).
缺点: 蛮容易stuck在local maxima/minima假如设计不好
      有些free parameters都要看问题情况而定, 所以需要跑实验.
      这个是个跟nature来比很不真实的model... 以为漏了RNA和protein那两层. 所以是个注重与phenotype而不是genotypical的算法. (这句是指说encoding跟问题本身的直接关系)
       能够解决low - medium dimensionality 的问题... (high dimensionality的问题就如那些改变一个小地方就能导致整个系统状态的改变, medium的可以说是改变某某一个值就只影响一部分系统的指数而已, 最low的就可能说有one to one correspondence的改变..)

jytou

明年学AI Programming也要学Genetic algol，生物学的知识竟然能在电脑内使用。。。