遗传算法R实现

    摘要：遗传算法是解决最优化的搜索算法，是进化算法的一种，在数据挖掘领域、特别是在决策领域应用很广泛。目前很多关于遗传算法的介绍过于复杂且停留于理论层面，为此，本文介绍了遗传算法的思想并用R语言实现，以使该算法明了的呈现，同时也说明R语言在实现原型算法、向量运算方面的强大力量。



        R语言是一种为统计计算和统计图形而生的函数式语言[1,2,3]，可视为S语言（由AT&T开发）的方言。它是一个开放源代码的项目，由新西兰Auckland大学的Ross Ihaka 和Robert Gentleman创建。R的命名部分来源于两位作者的名字，部分来源于S语言（要和S进行对比）。R语言的可扩展性非常的强，允许用户以定义新函数的方式添加额外功能，以适应特定领域的需要。R默认安装了8个包，用户可以自己通过CRAN这个网站得到更多需要的包。
    总结起来，R语言有如下特点[2]：
    高效的数据存储及处理能力，
    为向量特别是矩阵计算提供一整套的操作符，
    为数据分析提供大的、连贯的、综合的中间工具集合，
    强大的数据分析和数据展示能力
    同时，本身也是一个良好的、简单的、有效的编程语言，包含了条件、循环，用户自定义的递归函数和输入输出功能。

    R拥有很多各领域相关的工具包，一般来说，使用者不用太注意算法的底层实现问题，而更多关注与业务本身相关的内容。同时，如有必要，也可以对其进行修改，使“一切尽在我掌握中”，兼顾通用，又不失灵活。
    R在实现原型算法方面有不可替代的巨大优势，下面将通过遗传算法的实现对其进行说明。当然，首先得了解什么是遗传算法。
遗传算法介绍
基本思想：
    遗传算法是计算数学中用于解决最优化的搜索算法[4]，是进化算法的一种。进化算法最初是借鉴了生物进化中的一些现象而发展起来的，这些现象包括遗传、突变、自然选择以及杂交等。
    遗传算法通常实现方式为一种计算模拟。对于一个最优化问题，一定数量的候选解的抽象表示（称为染色体）的种群想更好的解进化。进化从完全随机个体的种群开始，之后一代一代发生（突变）。在每一代中，整个种群的适应度被评价，从当前种群中随机的选择多个种群，通过自然选择和蜕变产生新的生命种群，该种群在算法的下一次迭代中成为当前种群。
术语：
    染色体：又叫做基因个体（individuals），一定数量的个体组成了群体（population），群体中个体的数量叫做群体大小。
    基因：基因是串中的元素，是占有一定位置的基本遗传单位。
    基因位：一个基因在串中的位置。
    适应度：各个个体对环境的适应程度叫做适应度。为了体现个体的适应能力，引入了对问题中的每个个体进行度量的函数，叫做适应度函数。
操作过程：
    该算法有三个基本的运算：选择、交叉和变异[5]。
    个体遗传的操作都是在随机情况下进行的。因此，群体向最优解进化都是随机的。
    选择：从群体中选择优胜的个体，淘汰劣质个体的操作叫做选择。其目的是是把优化的个体(或解)直接遗传到下一代或通过配对交叉产生新的个体再遗传到下一代。
    交叉：所谓交叉是指把两个父代个体的部分结构加以替换重组而生成新个体的操作
    变异：对群体中的个体串的某些基因位上的基因值作变动。



假设我们现在有一个任务，从几组随机产生的数（数在0~100之间，每组为6个数）中，通过遗传算法，得到一组数字，这些数字的和最接近于某个数，假设为300。目标就是找到这些数。
根据前面的n-s图描述的过程，结合我们的任务，将这个问题用R代码实现（R中有实现该算法的包）。尽管遗传算法不一定是最好的优化策略（收敛速度慢），但是它总能找到一个良好的解。


生成个体：

	Individual=function(length,min_,max_){
		s=sample(min_:max_,length)
	}

生成种群：

	population=function(count,length,min,max){
		matrix(sample(min:max,count*length,TRUE),count)
	}

适应度函数对于算法的速度和效果也很有影响。
评判个体适应度：

fitness <- function(individual,target){
		abs(sum(individual)-target)
	}

评判群体适应度：

	grade<- function(pop,target){
		summed=sum(abs(rowSums(pop)-target))
		(summed/length(pop[,1]))*1.0
	}

遗传算法中最关键的阶段是进化，这个过程中有几个参数特别的重要，包括个体的数目，变异率，如果设置不当会使收敛过慢或者丢掉最优解。
evolve<- function(pop,target,retain=0.2,random_select=0.05,mutate=0.01)
Retain就是留种的比例，random_select是指在那些被淘汰的那一代中选择一些（为了保持多样性）作为种的比率，mutate当然指的就是变异的频率了。
变异的函数为：

	fmutate=function(x){
			if(mutate>runif(1)){
				pos_to_mutate=sample(1:length(x),1)
				x[pos_to_mutate]=sample(min(x):max(x),1)
			}
			 x
		}

这样得到父本为：
parents<-  t(apply(parents,1,fmutate))

生成新的子代的方法：

male  =parents[male,]
			female=parents[female,]
			half=length(male)%/% 2
			child=c(male[1:half],female[-(1:half)])
			children<-rbind(children,child)
			child_len=child_len+1

得到进化后的子代。
可以看到，算法得到的结果类似是：

child   23   63   61   32   90   31


代码：

individual=function(length,min_,max_){
	s=sample(min_:max_,length)
}

population=function(count,length,min,max){
	matrix(sample(min:max,count*length,TRUE),count)
}
	
	
fitness <- function(individual,target){
	abs(sum(individual)-target)
}

grade<- function(pop,target){
	summed=sum(abs(rowSums(pop)-target))
	(summed/length(pop[,1]))*1.0
}

evolve<- function(pop,target,retain=0.2,random_select=0.05,mutate=0.01){
	
	#<-vector()
	#for(i in 1:nrow(pop)){
	#}	
	
	#> cbind(apply(pop,1,fitness,target=200),pop)
	#           c                
	#[1,]  90  45 88 68  48 26 15
	#[2,] 172  86 83 69  58 17 59
	#[3,] 356 178 64 99 100 18 97	
	#pop[c(1:2),]取pop的前两行，我怀疑向量默认是竖着的，即是列。但是显示的是横向量。
	
	#/*生成矩阵用行排列*/
	#t(apply(ssss,1,sort))
	#/*再按照某列进行排序*/
	#ssss[order(ssss[,1]),]
	
	
	#通过这个例子可以理解order的用法：
	#a <- c(4, 3, 2, NA, 1)
	#   b <- c(4, NA, 2, 7, 1)
	#   z <- cbind(a, b)
	#   (o <- order(a, b)); z[o, ]

	pop<-cbind(apply(pop,1,fitness,target),pop)#得到经过计算fitness值的矩阵，接着是排序
	pop<- pop[order(pop[,1]),][,-1]
	retain_length=round(nrow(pop)*retain)
	parents=pop[1:retain_length,]
	pop_<- pop[-(1:retain_length),]#这个地方有点问题
	#apply(pop[-(1:retain_length),],1,function(x)if(random_select>runif(1))rbind(x,parents))
	#n=nrow(parents):nrow(pop)
	for(i in 1:nrow(pop_)){
		if (random_select>runif(1)){
			parents<- rbind(parents,pop_[i,])
		}
	}
	
	#for(i in 1:nrow(parents)){
	#	if(mutate>runif(1)){
	fmutate=function(x){
		if(mutate>runif(1)){
			pos_to_mutate=sample(1:length(x),1)
			x[pos_to_mutate]=sample(min(x):max(x),1)
		}
		 x
	}
	parents<-  t(apply(parents,1,fmutate))
	parents_len=nrow(parents)
	desired_len=nrow(pop)-parents_len
	children=vector()
	
	child_len=0
	while(child_len<desired_len){
		male  =sample(1:parents_len,1)
		female=sample(1:parents_len,1)
		if (male!=female){
			male  =parents[male,]
			female=parents[female,]
			half=length(male)%/% 2
			child=c(male[1:half],female[-(1:half)])
			children<-rbind(children,child)
			child_len=child_len+1
		}
	}
	parents=rbind(parents,children)
}




target = 371
p_count = 100
i_length = 6
i_min = 0
i_max = 100

p=population(p_count, i_length, i_min, i_max)
fitness_history=grade(p,target)

for (i in 1:100){
	p=evolve(p,target)
	fitness_history=append(fitness_history,grade(p,target))
}