精华内容
下载资源
问答
  • 自己修改的简单遗传算法的应用实例,很好用,是个程序框架,只要根据自己的需求改参数就可以使用
  • 下参考Mitchell《机器学习》中的遗传算法解决上面问题java代码如下: import java.lang.Math; import java.util.ArrayList; import java.util.List; /** * 采用遗传算法求下列二元函数最大值 * max f(x1,x2)=...

    求下述二元函数的最大值:


    下参考Mitchell《机器学习》中的遗传算法解决上面问题的java代码如下:

    import java.lang.Math;
    import java.util.ArrayList;
    import java.util.List;
    /**
     * 采用遗传算法求下列二元函数的最大值
     * max f(x1,x2)=x1^2+x2^2;
     * s.t.x1∈{1,2,3,4,5,6,7};x2∈{1,2,3,4,5,6,7};
     */
    
    public class GAFunBVar
    {
    	private int x1,x2;
    	private int groupSize;//群体尺寸
    	private String[] group;//群体
    	private double r;//每一步通过交叉取代群体成员的比例
    	private double m;//变异率
    	private String maxFitEntity;//最大适应度个体
    	private int maxFitness;//保存最大适应度
    	private final int SWAPSIZE=100;
    	private int noSwapNum=0;//最大适应度未交换次数,当该值大于某个SWAPSIZE,算法结束,付出最大适应度和满足的个体
    	private double[] pr;
    	private String[] thrbin={"000","001","010","011","100","101","110","111"};
    	private static final int GENERATION=50;//进化多少代后停止。
    
    	public GAFunBVar(int x1,int x2,int groupSize,double r,double m)
    	{
    	  this.x1=x1;
    	  this.x2=x2;
    	  this.groupSize=groupSize;
    	  group=new String[groupSize];
    	  this.r=r;
    	  this.m=m;
    	  pr=new double[groupSize];
    	}
    	/*
    	 * 编码
    	 * @x1,x2 要编码的两个十进制数
    	 * @binStr 返回的二进制串
    	 */
    	private String coding(int x1,int x2)
    	{
    		return thrbin[x1]+thrbin[x2];
    	}
    	/*
    	 * 解码
    	 * @binStr 要解码的二进制串
    	 * @int[] x 保存解码出来的两个十进制数
    	 */
    	private int[] enCoding(String binStr)
    	{
    		int[] x=new int[2];
    		String x1Str=binStr.substring(0,3);
    		String x2Str=binStr.substring(3);
    		for(int i=0;i<thrbin.length;i++)
    		{
    			if(x1Str.equals(thrbin[i]))
    				x[0]=i;
    			if(x2Str.equals(thrbin[i]))
    				x[1]=i;
    		}
    		return x;
    	}
    	/*
    	 * 初始群体产生
    	 */
    	private void InitGroup()
    	{
    		int i,m;
    		String[] temp=new String[groupSize];//为了产生不重复的个体,设置的临时群体
    		for(int j=0;j<groupSize;j++)
    			temp[j]=null;
    		
    			for(i=0;i<groupSize;i++)
    			{
    			
    				group[i]=thrbin[(int)(7*Math.random())+1]+thrbin[(int)(7*Math.random())+1];
    				for(m=0;m<i;m++)
    				{
    					if(group[i].equals(temp[m]))//如果这个个体已经被选择,则对第i个个体重新随机选择
    					{
    						i--;
    						break;
    					}
    				}
    				if(m==i)//说明该个体第一次选择,加入临时群体
    				  temp[i]=group[i];
    			}
    					
    	}
    	/*
    	 * 适应度计算
    	 */
    	private int countFitness(String entityStr)
    	{
    	  int[] x=new int[2];
    	  x=enCoding(entityStr);
    	  return x[0]*x[0]+x[1]*x[1];
    	}
    	/*
    	 * 整个群体的每个个体适应度计算,并和最大适应度比较,选出新的最大适应度,及相应的个体
    	 * @group 群体
    	 * @fitness 群体对应的适应度
    	 */
    	private void getMaxFitness(String[] group)
    	{
    		int[] fitness=new int[groupSize];//每个个体对应的适应度
    		int flag=0;//标记交换情况
    		for(int i=0;i<groupSize;i++)
    		{
    			fitness[i]=countFitness(group[i]);
    			if(fitness[i]>maxFitness)
    			{
    				flag=1;
    				maxFitness=fitness[i];
    				maxFitEntity=group[i];
    				noSwapNum=0;
    			}
    		}
    		if(flag==0)
    		{
    			noSwapNum++;
    		}
    		
    	}
    	/*
    	 * 选择(),在此之前要进行假设被选择的概率的计算
    	 * @rnewEntNum 要选择的成员个数
    	 */
    	
    	private void chooseNewEnt(int rnewEntNum)
    	{
    		choose_Pr();
    		roulette(rnewEntNum,group);
    		
    	}
    	/*
    	 * 轮盘赌算法
    	 */
    	private void roulette(int rnewEntNum,String[] group)
    	{
    		//取[0,1]之间的概率片段对应每一个假设成员
    		double zero_one_Pr[]=new double[groupSize-1];
    		for(int i=0;i<groupSize-1;i++)
    		{
    			if(i==0)zero_one_Pr[i]=pr[0];
    			else if(i==groupSize-2)zero_one_Pr[i]=1-pr[groupSize-1];
    			else {
    				for(int j=0;j<=i;j++)
    				   zero_one_Pr[i]+=pr[j];
    			}
    			System.out.print(zero_one_Pr[i]+" ");
    		}
    		
    		double rand=0;
    		for(int i=0;i<rnewEntNum;i++)
    		{
    			rand=Math.random();
    			if(rand<zero_one_Pr[0])
    				group[i]=this.group[0];
    			else if(rand<zero_one_Pr[1]&&rand>=zero_one_Pr[0])
    				group[i]=this.group[1];
    			else if(rand<zero_one_Pr[2]&&rand>=zero_one_Pr[1])
    				group[i]=this.group[2];
    			else {
    				group[i]=this.group[3];
    			}
    				
    		}
    	}
        /*
         * 选择群体中每个成员的概率
         */
    	private void choose_Pr()
    	{
    		double sum_pr=0.0;;
    		for(String str:group)
    		{
    			sum_pr+=countFitness(str);
    		}
    		for(int i=0;i<groupSize;i++)
    		{
    			pr[i]=countFitness(group[i])/sum_pr;
    			System.out.println("成员"+group[i]+"被选择的概率(Pr(hi)):"+pr[i]);
    		}
    			
    	}
    	/*
    	 * 交叉(总是要在选择之后完成)
    	 */
    	private void intersect(int inter_pair,int inter_start_index)
    	{
    		String[] temp_Group=new String[inter_pair*2];
    		roulette(inter_pair*2,temp_Group);
    		for(String str:temp_Group)
    			System.out.println("交叉选择的成员:"+str);
    		int len=temp_Group.length;
    		int index1=0,index2=0;
    		List<Integer> list=new ArrayList<Integer>();
    		int length=len;
    		boolean flag=false;
    		int i=inter_start_index;
    		while(length!=0)
    		{
    			do {
    				index1=(int)(len*Math.random());
    				flag=isRepeatIndex(index1,list);
    			} while (flag);
    			do {
    				index2=(int)(len*Math.random());
    				flag=isRepeatIndex(index2,list);
    			} while (flag);
    			
    			String[] temp=new String[2];
    			temp=intersect_B(temp_Group[index1],temp_Group[index2]);
    			group[i++]=temp[0];
    			group[i++]=temp[1];
    			length-=2;
    		}
    		
    	}
    	/*
    	 * 在交叉时,判断一个下标(@index)对应的成员是否已经被选择过了
    	 * @temp_index 保存已选择了的成员在临时group中对应的下标
    	 */
    	private boolean isRepeatIndex(int index,List<Integer> list)
    	{
    		for(int i=0;i<list.size();i++)
    		{
    			if(index==(int)list.get(i))
    				return true;
    		}
    		list.add(index);
    		return false;
    	}
    	/*
    	 * 任意两个成员实现交叉(单点交叉)
    	 * @single_point 交叉点位置
    	 */
    	private String[] intersect_B(String entity1,String entity2)
    	{
    		String[] son_Ent=new String[2];
    		int single_point=(int)(6*Math.random());
    		son_Ent[0]=entity1.substring(0,single_point)+entity2.substring(single_point);
    		son_Ent[1]=entity1.substring(single_point)+entity2.substring(0,single_point);
    		return son_Ent;
    	}
    	/*
    	 * 变异
    	 *@group 要变异的群体
    	 *@ratio 变异率 
    	 *@
    	 */
    	private void variation(String[] group,double ratio)
    	{
    		int var_Size=(int)(groupSize*ratio);
    		boolean flag=false;
    		List<Integer> list=new ArrayList<Integer>();
    		int index;
    		while(var_Size>0)
    		{
    			do {
    				index=(int)(groupSize*Math.random());
    				flag=isRepeatIndex(index, list);
    			} while (flag);
    			int var_site=(int)(6*Math.random());
    			if(group[index].charAt(var_site)=='0')
    				group[index]=group[index].substring(0,var_site)+'1'+group[index].substring(var_site+1);
    			else if(group[index].charAt(var_site)=='1')
    				group[index]=group[index].substring(0,var_site)+'0'+group[index].substring(var_site+1);
    			var_Size--;
    		}
    	}
    
    	public static void main(String args[])
    	{
    		int x[]=new int[2];
    		String strTest=null;
    		GAFunBVar gaFunBVar=new GAFunBVar(5,6,4,0.5,0.5);
    		strTest=gaFunBVar.coding(gaFunBVar.x1,gaFunBVar.x2);
    		System.out.println(strTest);
    		x=gaFunBVar.enCoding(strTest);
    		gaFunBVar.x1=x[0];
    		gaFunBVar.x2=x[1];
    		System.out.println(gaFunBVar.x1+" "+gaFunBVar.x2);
    		
    		gaFunBVar.InitGroup();
    		System.out.println("初始随机创建一个群体:");
    		for(int i=0;i<gaFunBVar.groupSize;i++)
    		{
    			System.out.println(gaFunBVar.group[i]);
    		}
    		
    		while(gaFunBVar.noSwapNum<GENERATION)
    		{
    			//1.选择(轮盘赌方法)
    			int rnewEntNum=(int)((1-gaFunBVar.r)*gaFunBVar.groupSize);
    			System.out.println("直接从父代选择成员作为后代的个数:"+rnewEntNum);
    			gaFunBVar.chooseNewEnt(rnewEntNum);
    			
    			//2.交叉
    			int inter_pair=(int)(gaFunBVar.r*gaFunBVar.groupSize/2);
    			System.out.println("要交叉的对数:"+inter_pair);
    			gaFunBVar.intersect(inter_pair,rnewEntNum);
    			//3.变异
    			gaFunBVar.variation(gaFunBVar.group, gaFunBVar.m);
    			System.out.println("变异后的群体为:");
    			for(String str:gaFunBVar.group)
    				System.out.println(str);
    			//
    			gaFunBVar.getMaxFitness(gaFunBVar.group);
    		}
    		
    		System.out.println("最大的适应度为:"+gaFunBVar.maxFitness);
    		System.out.println("达到最大适应度的个体为:"+gaFunBVar.maxFitEntity);
    	}
    }
    

      程序整体上有点乱,第一次写,多多包含微笑

    展开全文
  • 详细介绍了遗传算法原理及其应用实例,很有用
  • 遗传算法应用实例

    2020-03-23 03:41:03
    遗传算法是一种很好求解最优问题算法工具,特别是非线性问题求解
  • 数学建模源码集锦-基于遗传算法的TSP算法应用实例
  • matlab基本遗传算法应用实例:用基本遗传算法求函数最大值
  • 数学建模源码集锦-基于多层编码遗传算法的车间调度算法应用实例
  • 数学建模源码集锦-基于遗传算法的多目标优化算法应用实例
  • 实用标准文案 基本遗传算法应用实例用基本遗传算法求下面函数最大值 3 2 f (x ) x 60x 900x 100 0 x 30 个体数目取 50最大进化代数取 100离散精度取 0.001 杂交概率取 0.9 变 异概率取 0.004 1在 editor 中建立...
  • 数学建模源码集锦-基于量子遗传算法的函数寻优算法应用实例
  • 用一个求解函数极值最简单的实例分析了应用遗传算法的求解过程!
  • 数学建模源码集锦-基于遗传算法的LQR控制器优化算法应用实例
  • 数学建模源码集锦-基于遗传算法的BP神经网络优化算法应用实例.zip
  • 遗传算法的发展现状与应用实例

    千次阅读 2018-11-08 20:19:24
    遗传算法的发展现状与应用实例

    分享一下我老师大神的人工智能教程!零基础,通俗易懂!http://blog.csdn.net/jiangjunshow

    也欢迎大家转载本篇文章。分享知识,造福人民,实现我们中华民族伟大复兴!

                   
    .
    1  引言
    近年来 ,遗传算法 (GA)的卓越性能引起人们的关注 .对于以往难以解决的函数优化问题 ,复杂的多目标规划问题 ,工农业生产中的配管、配线问题 ,以及机器学习 ,图象识别 ,人工神经网络的权系数调整和网络构造等问题 ,GA是最有效的方法之一 .虽然GA在许多优化问题中都有成功的应用 ,但其本身也存在一些不足 .例如局部搜索能力差、存在未成熟收敛和随机漫游等现象 ,从而导致算法的收敛性能差 ,需要很长时间才能找到最优解 ,这些不足阻碍了遗传算法的推广应用 .如何改善遗传算法的搜索能力和提高算法的收敛速度 ,使其更好地应用于实际问题的解决中 ,是各国学者一直探索的一个主要课题.之后世界范围内掀起了关于遗传算法的研究与应用热潮
    2  遗传算法存在的问题及相应的改进措施
    自然界早已显示出了基因的强大威力 ,通过这种机制 ,一系列的具有智能、自组织、自修整的器官产生了 .人们要在科学研究中效仿这些生物器官 ,那么就必须了解基因、进化的概念 .GA就是这样一种利用自然选择和进化思想在高维空间中寻优的方法 ,它不一定能寻得最优点 ,但是它可以找到更优 点 ,这种思路与人类行为中成功的标准是很相似的 .例如不必要求一支军队是最优的 ,要战胜对手只需它比对手更强即可 .因此 GA可能会暂时停留在某些非最优点上 ,直到变异发生使它跃居到另一个更优点上 . GA寻优过程的一个重要特点是它始终保持整个种群的进化 ,这样即使某个体在某时刻丧失了有用的特征 ,这种特征也会被其他个体所保留并延续发展下去 .由于 GA仅需知道目标函数的信息 ,而不需要其连续可微等要求 ,因而具有广泛的适应性 .同时它又是一种采用启发性知识的智能搜索算法 ,所以往往能在搜索空间高度复杂的问题上取得比以往算法 (如梯度法 )更好的效果D. B. Fogel提出的进化即智能的概念[1 0 ],虽然还没有被普遍接受 ,但进化在人类生存进步过程中的重要性已可见一斑 ,因此遗传算法作为生物进化思想在工程计算中的一种体现 ,其前途是光明的 .目前 GA在工程优化、信号处理、模式识别、管理决策、智能系统设计和人工生命等领域的成功利用正说明了这一点 .
    2. 1 编码表示
       Holland在运用模式定理分析编码机制时 ,建议使用二进制编码 ,但二进制编码不能直接反映问题的固有结构 ,精度不高 ,个体长度大 ,占用计算机内存多 . Gray编码是将二进制编码通过一个变换进行转换得到的编码 ,其目的就是克服 Hamming悬崖的缺点,动态编码 (dynamic encoding)GA是当算法收敛到某局部最优时增加搜索的精度 ,从而使得在全局最优点附近可以进行更精确的搜索 ,增加精度的办法是在保持串长不变的前提下减小搜索区域 .对于问题的变量是实向量的情形 ,可以直接采用实数进行编码 ,这样可以直接在解的表现型上进行遗传操作 ,从而便于引入与问题领域相关的启发式信息以增加算法的搜索能力.复数编码[5]的GA是为了描述和解决二维问题 ,基因用 x+yi 表示 ;其还可以推广到多维问题的描述中 .多维实数编码[6 ]GA,使无效交叉发生的可能性大大降低 ,同时其合理的编码长度也有助于算法在短时间内获得高精度的全局最优解 .在组合优化中 ,可以使用有序串编码 ,例如在文献 [7]中用自然数编码巧妙地解决了VRP问题 .当问题的表示是树和图时 ,我们还可以使用结构式编码
    2. 2 适应度函数
    适应度函数是用来区分群体中个体好坏的标准 ,是自然选择的唯一标准 ,选择的好坏直接影响算法的优劣 .引入适应值调节和资源共享策略可以加快收敛速度和跳出局部最优点 .对适应值进行调节就是通过变换改变原适应值间的比例关系 ,常用的比例变换有线性变换、乘幂变换和指数变换等 .对于一个问题具体采用什么变换才能达到较优的效果 ,V. Kreinovich等在文献 [8]中做了较详细的讨论 而在文献 [9]中则是采用共享的技术 ,对子群的形成和稳定起了一定作用 ,文中主要用子群消失时间的近似形式估计 Sharing的界 .文献 [1 0 ]中采用了依据搜索进展可变的适应值函数 ,并应用于 CuttingProblem取得较好效果 .文献 [1 1 ]中设计了自适应选取遗传算法的适应值函数的方法 ,该方法的计算量要比排序选择操作的计算量小的多 ,而且有效的避免了算法的非成熟收敛 .
    2 . 3 选择策略
      优胜劣汰的选择机制使得适应值大的个体有较大的存活机会 ,不同的选择策略对算法性能有较大的影响 .轮盘赌法是使用最多的选择策略 ,但这种策略可能会产生较大的抽样误差 ,于是对此提出了很多的改进方法 ,如繁殖池选择[1 2 ],Boltzmann选择[1 3 ]等等 .但是这几种策略都是基于适应值比例的选择 ,常常会出现早熟收敛现象和停滞现象 .为此又提出了非线性排名选择[3 ],这种选择不仅避免了上述问题 ,而且可以直接使用原始适应值进行排名选择 ,而不需对适应值进行标准化 ;但这种选择在群体规模很大时 ,其额外计算量 (如计算总体适应值和排序 )也相当可观 ,甚至在进行并行实现时有时要带来一些同步限制 .基于局部竞争机制的选择如 (λ+μ)选择[1 4],它使双亲和后代有同样的生存竞争机会在一定程度上避免了这些问题 .在 [1 5]中作者采用
    了类似梯度的方式来选择 ,不仅使较差的染色体比较好的染色体得到更大的改进 ,而且还不断产生新的个体 ,从而不断拓展了新的搜索空间 . [1 6 ]中作者
    引入了 Harvesting Strategies来分析遗传算法的性能 ,Harvesting Strategies是指在每一代交叉和突变后进行两次乃至多次筛选作为下面的群体 .采用了 Disruptive Selection,它吸收了优等和劣等个体 ,实验结果表明了两极分化有可能更容易找到最优解 .为了提高种群的多样性 ,提出一种基于免疫多样性的选择算子[1 8],该选择算子依赖于串的稠密度和适应值 ,串的稠密度越大 ,其保留下来的可能性越小 ,具体事例证明改进算法是有效的 .
    2 . 4 控制参数
      控制参数一般有群体大小 ,交换概率 ,变异概率等 ,这些参数对遗传算法性能影响较大 .在标准的遗传算法中采用经验进行估计 ,这将带来很大的盲目性 ,而影响算法的全局最优性和收敛性 .目前许多学者意识到这些参数应该随着遗传进化而自适应变化 ,Davis提出自适应算子概率方法 [1 9],即用自适应
    机制把算子概率与算子产生的个体适应性结合 ,高适应性值被分配高算子概率 . Whitley提出一种自适应突变策略与一对父串间的 Hamming距离成反比 [2 0 ],结果显示能有效地保持基因的多样性 .张良杰等通过引入 i位改进子空间概念 ,采用模糊推理技术来确定选取突变概率的一般性原则 [2 1 ].在文献[2 2 ]中设计了一种群体规模可变的遗传算法 ,它提出每个个体应当有年龄及生命期的概念并淘汰年龄大于生命期的个体从而使遗传算法动态的控制了群体数目 ,这种方法可以找出一个接近最小代价的遗传算法 ,同时尽量将群体规模保持在现有水平 ,防止群体规模的指数级增长 ,以降低计算的开销 .丁承明等提出利用正交试验法去优化选取 GA控制参数 [2 3 ],这种方法利用正交试验的均衡分散性使得通过较少的试验次数就可搜索绝大部分参数组合空间 ,而且还可以确定哪个参数对 GA结果影响最显著 ,然后有针对性地进行精确搜索 ,从而使得 GA参数问题得到圆满解决 .为保证种群的有用多样性 ,提出动态群法[2 4],即当迭代到一定代数 ,若目标函数的值相同 ,则现存种群中的较差的 N个染色体被随机产生的 N个染色体代替 ,使进化过程中不断有新个体引入 . [2 5]中用模糊规则对选择概率和变异概率进行控制 ,在线改变其值 ,相应的算例表明 ,有较好的性能
    2. 5 遗传算子
      基本遗传算法中采用单点交叉算子和简单的变异算子 .它们操作比较简单 ,计算量小 ,但是在使用过程中有很大的局限性 ,例如 :由于单点交叉破坏模式的概率较小 ,至使搜索到的模式数也较少 ,使算法具有较低的搜索能力 . Feng etal.对多维连续空间的GA的杂交多样性进行了分析 ,通过建立相应的数学模型 ,Feng解释了在多维连续空间和大规模群体中使用均匀杂交算子[2 6 ]是如何探索新的解空间区域 .为了使得变异能够根据解的质量自适应的调整搜索区域 ,从而能较明显地提高搜索能力 ,提出自适应变异算子[2 7].为了保护适应值较高的模式 ,提出自适应交叉和变异 [2 8],如果遇到适应值较高的模式 ,则通过随机引入模式外的位而进行保护 .为了克服早熟 ,引入多种群 GA[2 9],不同种群赋以不同的控制参数 ,实现不同的搜索目的 ,通过移民算子联系各种群 ,通过人工选择算子保存各种群每个进化代中的最优个体 .为了防止近亲繁殖 ,扩大种群的多样性 ,抑制超长个体的快速繁殖 ,引进近亲繁殖算子 ,两个个体是否为近亲可用基因片段的 Hamming距离来判断 ,距离越大 ,则为近亲的可能越小 ;为加强局部搜索能力 ,增加漂移算子 ,将染色体各基因片段的后二分之一的基因分别按一定的概率做 1的随机漂移 ,排位越后的基因漂移的概率越大 ,由此产生一定数量的新个体 ,用基因预选机制的小生境技术控制漂移方向 [3 0 ].因为格点法产生的点集能均匀地分布于搜索空间 ,并且佳点又是最好的格点 ,所以可以用数论中的佳点集理论设计交叉算子[3 1 ],结果表明它的搜索效果要比纯随机法好 ,而且有效的避免早熟现象 .基于生物免疫性提出的免疫算子 [3 2 ],能够明显抑制进化过程中的退化现象 ,减轻 GA后期的波动 ,从而提高了搜索效率和收敛速度 . [3 3 ]中提出的 SRM(self-reproduction)算子增强了种群的多样性 ,CM(crossove and mutation)算子促进了有利变异的增加 ,从而使算法大大节省了存贮空间和运行时间 .采用“尺度收缩”策略的混沌变异算子 [3 4]能明显的改善群体平均适应值 ,提高算法的性能 ,是解决优化问题的有效方法 .
    2 . 6 综合方面
    文献 [3 5]中提出了可分解 /可拼接 GA编码 ,并基于此编码分别在种群层次和基因层次发展了动态变异和动态选择操作 ,这种方法很大程度上避免了早熟问题 .增强型 GA[3 6 ]中 ,引入了几个新算子和新的种群迁移策略 ,并用其对模糊逻辑控制器进行设计 ,得到了便于理解的模糊集和模糊规则 .用小波分析中的多尺度分析对 GA中的染色体进行多尺度分解 ,这样分解后的染色体的长度变短 ,基因交换、变异等遗传操作更为彻底 ,有效的克服了基因丢失引起的早熟问题 [3 7].小生境技术不仅能够保证群体中解的多样性 ,而且具有很强的引导进化能力 ,所以小生境技术的引入 ,提高了 GA处理多峰函数优化问题的能力[3 8].将模拟退火过程引入遗传算法[3 9],在优选交叉和变异个体的过程中加入一定的“扰动”,以达到保持种群内位串的多样性和位串之间的竞争机制 ,克服了算法易陷于极小点的问题 ,使得搜索沿着全局最优方向进行 .广义遗传算法[40 ],它以多点突变操作为主 ,以基因交叉操作为辅 ,实现了从一个局部最优状态到另一个局部最优状态的转移 ,使算法获得全局最优 .为了使 GA用于约束优化 ,提出一种非稳态罚函数 GA[41 ],非稳态罚函数是遗传代数的函数 ,当代数增加时 ,罚函数也随着增大 ,同时给GA带来更多的选择压力 ,促使 GA找到可行解 .综合遗传算法的全局性和神经网络的并行快速性等特点 ,提出的遗传神经网络算法[42 ],可克服遗传算法最终进化至最优解较慢和神经网络易陷入局部解的缺陷 ,具有较好的全局性和收敛速度 .采用面向对象技术设计了面向对象遗传算法[43 ],这种方法改变了在传统的 GA中各个函数之间只有参数的传递 ,而没有代码的继承性的状况从概念上提高了软件的可重用性 ,用户可以更方便的设计和实现自己的编码方案和遗传算子 .变异基遗传算法[44],采用变异算子进行局部优化搜索 ,并利用随机初始化技术使算法在局部搜索能力提高的同时仍有可能寻找到全局最优解 .贪婪遗传算法[45]用在二次分配问题中取得了较好的效果 ,在该算法中引入了新的交叉算子和移民算子 ,保证了种群的多样性 ;并且通过比赛竞争使得各种群得到进化 ,很好的解决了种群多样性及对个别好个体偏爱之间的矛盾 .
    3 遗传算法的发展动向 (GA' s developmen-tal trends)
    GA在应用方面的丰硕成果 ,使人们对它的发展前景充满信心 .其主要应用领域在于函数优化 (非线性 ,多模型 ,多目标等 ),机器人学 (移动机器人路径规划 ,关节机器人运动轨迹规划 ,细胞机器人的结构优化等 ),控制 (瓦斯管道控制 ,防避导弹控制 ,机器人控制等 ),规划 (生产规划 ,并行机任务分配等 ),设计 (VLSI布局 ,通信网络设计 ,喷气发动机设计等 ),组合优化 (TSP问题 ,背包问题 ,图分划问题等 ),图象处理 (模式识别 ,特征提取 ,图象恢复等 ),信号处理 (滤波器设计等 ),人工生命 (生命的遗传进化等 ).此外遗传算法的研究出现了几个引人注目的新动向 :
    3 . 1 基于遗传算法的机器学习
    这一新的研究方向把遗传算法从历史离散的搜
    索空间的优化搜索算法扩展到具有独特的规则生成功能的崭新的机器学习算法 .这一新的学习机制对于解决人工智能中知识获取和知识优化精炼的瓶颈难题带来了希望 .遗传算法作为一种搜索算法从一开始就与机器学习有着密切联系 .分类器系统 CS-1是 GA的创立者 Holland教授等实现的第一个基于遗传算法的机器学习系统 .分类器系统在很多领域都得到了应用 .例如 ,分类器系统在学习式多机器人路径规划系统中得到的成功应用 ; Goldberg研究了用分类器系统来学习控制一个煤气管道仿真系统 ;Wilson研究了一种用于协调可移动式视频摄像机的感知—运动的分类器系统等 .分类器系统在基于遗传算法的机器学习研究中影响很大 ,但具体实现方法和要解决的具体问题有关 .基于遗传算法的概念学习是近几年来机器学习领域的一个较为引人注目的研究方向 ,由于概念学习隐含的搜索机制 ,使得遗传算法在概念学习中有用武之地 .目前也有一些嵌入领域知识的基于遗传算法的机器学习的研究 ,如将概念学习中特有的操作遗传操作化 ,并显示出一定的优点 .此外 ,学习分类系统的并行实现在基于遗传算法的机器学习研究中也占有相当的分量 .
    3 . 2 遗传算法与其他计算智能方法的相互渗透和结合
    遗传算法正日益和神经网络、模糊推理以及混沌理论等其他智能计算方法相互渗透和结合 ,必能达到取长补短的作用 .近年来在这方面已经取得不少研究成果 ,并形成了“计算智能”的研究领域 ,这对开拓 2 1世纪中新的智能计算技术将具有重要的意义 . GA的出现使神经网络的训练 (包括连接权系数的优化、网络空间结构的优化和网络的学习规则优化 )有了一个崭新的面貌 ,目标函数既不要求连续 ,也不要求可微 ,仅要求该问题可计算 ,而且它的搜索始终遍及整个解空间 ,因此容易得到全局最优解 .GA与神经网络的结合正成功的被用于从时间序列的分析来进行财政预算 ,在这些系统中 ,训练信号是模糊的 ,数据是有噪声的 ,一般很难正确的给出每个执行的定量评价 ,如采用 GA来学习 ,就能克服这个困难 ,显著提高了系统的性能 . Muhlenbein分析了多层感知机网络的局限性 ,并猜想下一代神经网络将会是遗传神经网络 .遗传算法还可以用于学习模糊控制规则和隶属度函数 ,从而更好地改善模糊系统的性能 .文献 [46 ]中将模糊逻辑、神经网络和遗传算法三者有机的结合起来应用于温室夏季温湿度控制中 ,实验结果表明得到了良好的控制效果 .混沌表现出的随机性是系统内在的随机性 ,被称为伪随机性 ,它在生物进化中起着重要的作用 ,是系统进化与信息之源 .混沌与遗传算法的结合已有人进行过尝试 ,如吴新余等[47]采用多种混沌模型构造随机开关 ,以此控制交叉操作以改进 GA的性能 .文献 [3 4]中更加直接 ,采用混沌序列构造变异算子 ,为遗传算法的实现开辟了新的途径 .
    3 . 3 并行处理的遗传算法
    并行处理的遗传算法的研究不仅是遗传算法本身的发展 ,而且对于新一代智能计算机体系结构的研究都是十分重要的 . GA在操作上具有高度的并行性 ,许多研究人员都正在探索在并行机上高效执行 GA的策略 .近几年也发表了不少这方面的论文 ,研究表明 ,只要通过保持多个群体和恰当地控制群体间的相互作用来模拟并执行过程 ,即使不使用并行计算机 ,我们也能提高算法的执行效率 .在并行GA的研究方面 ,一些并行 GA模型已经被人们在具体的并行机上执行了 ;并行 GA可分为两类 :一类是粗粒度并行 GA,它主要开发群体间的并行性 ,如Cohoon分析了在并行计算机上解图划分问题的多群体 GA的性能 ;另一类是细粒度 GA,它主要开发一个群体中的并行性 ,如 Kosak将群体中的每个个体映射到一个连接机的处理单元上 ,并指出了这种方法对网络图设计问题的有效性 .
    3 . 4 遗传算法与人工生命的渗透
    人工生命是用计算机、机械等人工媒体模拟或构造出的具有自然生物系统特有行为的人造系统 ,人工生命与遗传算法有着密切的关系 ,基于遗传算法的进化模型是研究人工生命现象的重要理论基础 .虽然人工生命的研究尚处于启蒙阶段 ,但遗传算法已在其进化模型、学习模型、行为模型、自组织模型等方面显示出了初步的应用能力 ,并且必将得到更为深入的应用和发展 .人工生命与遗传算法相辅相成 ,遗传算法为人工生命的研究提供了一个有效的工具 ,人工生命的研究也必将促进遗传算法的进一步发展 .
    3 . 5 遗传算法与进化规则及进化策略的结合
    遗传算法、进化规则及进化策略是演化计算的三个主要分支 ,这三种典型的进化算法都以自然界中生物的进化过程为自适应全局优化搜索过程的借鉴对象 ,所以三者之间有较大的相似性 ;另一方面 ,这三种算法又是从不完全相同的角度出发来模拟生物的进化过程 ,分别是依据不同的生物进化背景、不同的生物进化机制而开发出来的 ,所以三者之间也有一些差异 .随着各种进化计算方法之间相互交流深入 ,以及对各种进化算法机理研究的进展 ,要严格地区分它们既不可能 ,也没有必要 .在进化计算领域内更重要的工作是生物进化机制 ,构造性能更加优良、适应面更加广泛的进化算法 .
    4 结论
    遗传算法作为一种非确定性的拟自然算法 ,为复杂系统的优化提供了一种新的方法 ,并且经过实践证明效果显著 .尽管遗传算法在很多领域具有广泛的应用价值 ,但它仍存在一些问题 ,各国学者一直在探索着对遗传算法的改进 ,以使遗传算法有更广泛的应用领域 .
    总之,遗传算法的未来是非常的美好的,只要我们对它们进行细致的分析,对它的缺点加以改造,优点进行继承,把它应用到我们的生产当中去,这样在生产当中还可以对它的缺点进行完善.

               

    给我老师的人工智能教程打call!http://blog.csdn.net/jiangjunshow

    这里写图片描述
    展开全文
  • 遗传算法原理及应用实例

    热门讨论 2010-04-10 14:35:51
    遗传算法是一种用来解决需要搜索复杂解空间的问题的 启发式算法。...些因素的不同,遗传算法的结构也在发生变化。因此,如何根据 实际的优化问题找到相应的遗传算法的最佳结构将是非常重要 的问题。
  • 数学建模源码集锦-基于遗传算法和非线性规划函数寻优算法应用实例
  • 数学建模源码集锦-基于遗传模拟退火算法的聚类算法应用实例
  • 数学建模源码集锦-多种群遗传算法的函数优化方法应用实例
  • 使用简单遗传算法解决某函数最大值问题,本人python初学者,代码写还很一般,如有不好之处请多包涵。
  • 遗传算法电子教材以及针对一些问题的应用实例和相关代码.
  • prufer编码:用n-2位自然数唯一表达出一棵n个节点生成树。而且两者相互可逆,即给定一颗生成树连接方式,可以唯一确定这棵树编码。 Cayley定理:n个顶点完全图中有nn−2n^{n-2}nn−2棵不同生成树。 显然...

    prufer编码:用n-2位自然数唯一的表达出一棵n个节点的生成树。而且两者相互可逆,即给定一颗生成树的连接方式,可以唯一确定这棵树的编码。
    Cayley定理:n个顶点的完全图中有nn2n^{n-2}棵不同的生成树。

    显然这两个描述具有很强的联系,n个顶点编号为1,2,…n。有n-2个位置,随便填入1,2,…n中的一个数,这有nn2n^{n-2}种可能。

    所以我们要证明Cayley定理,只需要证明prufer编码

    prufer编码

    1.设有如下生成树(n=6),根据prufer编码,我们只需要6-2=4位就可以对这颗生成树完成编码。
    在这里插入图片描述
    2.树中叶子的概念。
    在这里插入图片描述
    3.prufer编码的步骤。
    在这里插入图片描述
    (i)在我们这里,1是标号最小的叶子。
    (ii)1与2相连,将2写入编码,删去边(1,2)。此时编码为2,删去边(1,2)如下图。
    (i)
    (i)在我们这里,3是标号最小的叶子。
    (ii)3与2相连,将2写入编码,删去边(3,2)。此时编码为2,2,删去边(3,2)如下图。
    在这里插入图片描述
    (i)在我们这里,4是标号最小的叶子。
    (ii)4与6相连,将6写入编码,删去边(4,6)。此时编码为2,2,6,删去边(4,6)如下图。
    在这里插入图片描述
    (i)在我们这里,5是标号最小的叶子。
    (ii)5与2相连,将2写入编码,删去边(5,2)。此时编码为2,2,6,2,删去边(5,2)如下图。
    在这里插入图片描述

    一个关键的地方来了,接下来停止编码,我们发现,只用了n-2位编码。一个疑惑当然是:现就就停止编码,能否根据编码2,2,6,2还原出这颗生成树呢?

    4.解码步骤
    在这里插入图片描述
    在这里插入图片描述
    (i)初始在这里插入图片描述
    在这里插入图片描述

    (ii)
    在这里插入图片描述
    在这里插入图片描述

    (ii)重复
    在这里插入图片描述
    在这里插入图片描述

    (ii)重复,注意到,这步很关键,P的补集中加了一个6,因为6从P中删除后,不再在P中出现了,所以这个时候要加入到P的补集中。
    在这里插入图片描述
    在这里插入图片描述

    (ii)重复
    在这里插入图片描述
    在这里插入图片描述

    (iii)结束,P为空集,连接P的补集中的顶点。

    在这里插入图片描述

    至此,prufer编码的解码也已经完成了,且这个数和之前的树一模一样,即是可逆的。
    所以一个prufer编码也唯一确定一颗树,反之亦然。


    回到标题:
    这个编码和遗传算法会有什么关系?我们知道在使用遗传算法求解一个完全图的最小生成树过程中:两个母体需要进行交叉来繁殖后代,而两个母体都是生成树,这个时候我们需要一个编码,比如采用我们这里的prufer编码:

    P1:1234456
    P2:1232144

    假设第4位交叉了一下,有了两个孩子。

    C1:1232456
    C2:1234144

    这两个孩子根据prufer编码显然还是对应一个生成树,然后我们就可以直接物竞天择,看一下这两个孩子有没有进化得更好。

    以上编码是方便的,但是你采用其他编码就非常不方便了。因为交叉之后,可能不是一颗合法的生成树,比如可能有环。
    例如采用边直接编码:

    P1:(1,2),(1,3),(1,4)
    P2:(2,3),(1,2),(3,4)

    以上对应于:
    在这里插入图片描述

    在这里插入图片描述
    交叉后,假设第二条边交叉,那么得到:

    P1:(1,2),(1,2),(1,4)
    P2:(2,3),(1,3),(3,4)

    显然,一不注意,P1就违规了,因为P1中没有顶点3,不是最小生成树!


    补充,这个prufer编码还有一个特点,就是编码所对应的生成树中,顶点v的度数d等于编码中顶点v出现次数加1。

    展开全文
  • 遗传算法实例

    2018-05-17 20:19:44
    遗传算法应用于供水管网RPV(即减压阀)一个实例
  • 遗传算法入门实例

    2013-11-07 16:38:38
    遗传算法入门实例,资料包含了遗传算法在行业中的应用,尤其在人工智能游戏中的应用
  • 很早以前在初等数学建模里碰到一个例子,给定n(n>=3)个顶点,求平面上一个点或多个点,使得所有点连通,并且点到点距离之和最小,书上给出了一个定理,就是当这些点与点连线 ...恰巧当时学了遗传算法,就...

    很早以前在初等数学建模里碰到一个例子,给定n(n>=3)个顶点,求平面上的一个点或多个点,使得所有点连通,并且点到点的距离之和最小,书上给出了一个定理,就是当这些点与点的连线 的夹角都是120度时,可以证明 距离是最小的。当n=3时,只需一个点即可,并且可以通过几何的方法 轻易地找出,但是随着 n规模的增大,问题的复杂度将不可预测,而且没有一个有效地方法解决这个问题。恰巧当时学了遗传算法,就用它 求解。遗传算法可以在有限的时间内 找到一个最优近似解。

    用遗传算法求解 ,必须解决三个问题,

    第一 基因初始种类 我们说 好马才能生出 良驹 ,好的基因初始种类 可以缩短 基因的遗传代数 从而降低算法的复杂度。但是这个 好不能是主观上的好,即便是理论上的,也最好 对种类进行混搭 。

    第二 最重要的就是基因的编码, 即设计一种较好的数据结构,这个数据结构需要尽量将每一个 独立因子分离出来,因子的数量不能太多,不然问题的复杂度就太大,也不能太少,这样就无法得到最优基因序列。具体可以参考多元统计分析里的因子分析理论,除此之外,基因在设计时还要考虑 便于衡量整个基因的好坏,因为我们要对基因进行优胜劣汰;

    第三 基因的变异与交叉 也是十分重要的,变异是为了克服初始规模太小和最优因子序列遗失 从而避免过早收敛于局部最优解,这个变异的度必须把握好;交叉是为了获得最优因子序列重而获得最优基因。

    本文以n=3为例 用遗传算法求解 ,这是最简单的一种情况。不需要 对基因,变异和交叉 进行严格设计。但是整个遗传算法的流程和思路是一样的,废话不多 上代码:

    ContractedBlock.gifExpandedBlockStart.gifView Code
     1 #include<iostream>
    2 #include<cstdio>
    3 #include<cstdlib>
    4 #include<cmath>
    5 #include<ctime>
    6 using namespace std;
    7 //***************************************************************************
    8 //This is a simple genetic algorithm implementation for function optimization
    9 //参考书籍 《人工智能原理与应用》 金聪 清华大学出版社 2009
    10 //Freeze 于2010 7 7
    11
    12 //Problem describing:assuming that there are three point in the plane xOy
    13 //which located at O(0,0),P(12,0),Q(8,6).
    14 //please find Point R to let W=5|RO|+4|RP|+3|RQ| reach the minimum value
    15 //***************************************************************************
    16 //Parametes setting
    17 #define POPSIZE 200 //population size
    18 #define MAXGENS 1000 //max number of generation
    19 #define NVARS 2 //no of problem variables
    20 #define PXOVER 0.75 //probalility of crossover
    21 #define PMUTATION 0.15 //probalility of mutation
    22 #define TRUE 1
    23 #define FALSE 0
    24 #define LBOUND 0
    25 #define UBOUND 12
    26 #define STOP 0.001
    27 int generation; //current generation no
    28 int cur_best; //best individual
    29 double diff;
    30 FILE *galog; //an output file
    31 struct genotype
    32 {
    33 double gene[NVARS]; //a string of variables基因变量
    34 double upper[NVARS]; //individual's variables upper bound 基因变量取值上确界
    35 double lower[NVARS]; //individual's batiables lower bound 基因变量取值下确界
    36 double fitness; //individual's fitness个体适应值
    37 double rfitness; //relative fitness个体适应值占种群适应值比例
    38 double cfitness; //curmulation fitness个体适应值的累加比例
    39 };
    40 struct genotype population[POPSIZE+1];
    41 //population 当前种群 population[POPSIZE]用于存放个体最优值并假设最优个体能存活下去
    42 //在某些遗传算法中最优值个体并不一定能够存活下去
    43 struct genotype newpopulation[POPSIZE+1]; //new population replaces the old generation 子种群
    44 /*Declaration of procedures used by the gentic algorithm*/
    45 void initialize(void); //初始化函数
    46 double randval(double,double); //随机函数
    47 double funtion(double x1,double x2); //目标函数
    48 void evaluate(void); //评价函数
    49 void keep_the_best(void); //保留最优个体
    50 void elitist(void); //当前种群与子代种群最优值比较
    51 void select(void);
    52 void crossover(void); //基因重组函数
    53 void swap(double *,double *); //交换函数
    54 void mutate(void); //基因突变函数
    55 double report(void); //数据记录函数
    ContractedBlock.gifExpandedBlockStart.gifView Code
      1 //**************************************************************************************
    2 //Initializaton function:Initalizes the values of genes within the variables
    3 //bounds.It also initializes all fitness values for each number of the population
    4 //**************************************************************************************
    5 void initialize(void)
    6 {
    7 int i,j;
    8 for(i=0;i<NVARS;i++)
    9 {
    10 for(j=0;j<POPSIZE+1;j++)
    11 {
    12 if(!i)
    13 {
    14 population[j].fitness=0;
    15 population[j].rfitness=0;
    16 population[j].cfitness=0;
    17 }
    18 population[j].lower[i]=LBOUND;
    19 population[j].upper[i]=UBOUND;
    20 population[j].gene[i]=randval(population[j].lower[i],population[j].upper[i]);
    21 }
    22 }
    23 }
    24 //***************************************************************************
    25 //Random value generator:generates a value within bounds
    26 //***************************************************************************
    27 double randval(double low,double high)
    28 {
    29 double val;
    30 val=((double)(rand()%10000)/10000)*(high-low)+low;
    31 return val;
    32 }
    33 //目标函数
    34 double funtion(double x,double y)
    35 {
    36 double result1=sqrt(x*x+y*y)+sqrt((x-12)*(x-12)+y*y)+sqrt((x-8)*(x-8)+(y-6)*(y-6));
    37 return result1;
    38 }
    39 //***************************************************************************
    40 //Evaluation function:evaluate the individual's fitness.评价函数给出个体适应值
    41 //Each time the function is changes,the code has to be recompl
    42 //***************************************************************************
    43 void evaluate(void)
    44 {
    45 int mem;
    46 int i;
    47 double x[NVARS];
    48 for(mem=0;mem<POPSIZE;mem++)
    49 {
    50
    51 for(i=0;i<NVARS;i++)
    52 x[i]=population[mem].gene[i];
    53 population[mem].fitness=funtion(x[0],x[1]);//将目标函数值作为适应值
    54 }
    55 }
    56 //***************************************************************************************
    57 //Keep_the_best function:This function keeps track of the best member of the population.
    58 //找出种群中的个体最优值并将其移动到最后
    59 //***************************************************************************************
    60 void keep_the_best()
    61 {
    62 int mem;
    63 int i;
    64 cur_best=0;
    65 for(mem=0;mem<POPSIZE;mem++)//找出最高适应值个体
    66 {
    67 if(population[mem].fitness<population[cur_best].fitness)
    68 {
    69 cur_best=mem;
    70 }
    71 }
    72 //将最优个体复制至population[POSIZE]
    73 if(population[cur_best].fitness<=population[POPSIZE].fitness||population[POPSIZE].fitness<1)//防止出现种群基因退化 故保留历史最优个体
    74 {
    75 population[POPSIZE].fitness=population[cur_best].fitness;
    76 for(i=0;i<NVARS;i++)
    77 population[POPSIZE].gene[i]=population[cur_best].gene[i];
    78 }
    79 }
    80 //***************************************************************************
    81 //Elitist function:The best member of the previous generation is stored as the
    82 //last in the array.If the best individual from the new populatin is better
    83 //than the best individual from the previous population ,then copy the best
    84 //from the new population;else replace the worst individual from the current
    85 //population with the best one from the previous generation.防止种群最优值退化
    86 //***************************************************************************
    87 void elitist()
    88 {
    89 int i;
    90 double best,worst;//适应值
    91 int best_mem,worst_mem;//序号
    92 best_mem=worst_mem=0;
    93 best=population[best_mem].fitness;//最高适应值初始化
    94 worst=population[worst_mem].fitness;//最低适应值初始化
    95 for(i=1;i<POPSIZE;i++)//找出最高和最低适应值 算法有待改进
    96 {
    97 if(population[i].fitness<best)
    98 {
    99 best=population[i].fitness;
    100 best_mem=i;
    101 }
    102 if(population[i].fitness>worst)
    103 {
    104 worst=population[i].fitness;
    105 worst_mem=i;
    106 }
    107 }
    108 if(best<=population[POPSIZE].fitness)//赋值
    109 {
    110 for(i=0;i<NVARS;i++)
    111 population[POPSIZE].gene[i]=population[best_mem].gene[i];
    112 population[POPSIZE].fitness=population[best_mem].fitness;
    113 }
    114 else
    115 {
    116 for(i=0;i<NVARS;i++)
    117 population[worst_mem].gene[i]=population[POPSIZE].gene[i];
    118 population[worst_mem].fitness=population[POPSIZE].fitness;
    119 }
    120 }
    121 //***************************************************************************
    122 //Select function:Standard proportional selection for maximization problems
    123 //incorporating elitist model--makes sure that the best member survives.筛选函数并产生子代
    124 //***************************************************************************
    125 void select(void)
    126 {
    127 int mem,i,j;
    128 double sum=0;
    129 double p;
    130 for(mem=0;mem<POPSIZE;mem++)//所有适应值求和
    131 {
    132 sum+=population[mem].fitness;
    133 }
    134 for(mem=0;mem<POPSIZE;mem++)
    135 {
    136 population[mem].rfitness=population[mem].fitness/sum;//个人认为还不如建一个种群类 把sum看成类成员
    137 }
    138 population[0].cfitness=population[0].rfitness;
    139 for(mem=1;mem<POPSIZE;mem++)
    140 {
    141 population[mem].cfitness=population[mem-1].cfitness+population[mem].rfitness;
    142 }
    143 for(i=0;i<POPSIZE;i++)
    144 {
    145 p=rand()%1000/1000.0;
    146 if(p<population[0].cfitness)
    147 {
    148 newpopulation[i]=population[0];
    149 }
    150 else
    151 {
    152 for(j=0;j<POPSIZE;j++)
    153 if(p>=population[j].cfitness&&p<population[j+1].cfitness)
    154 newpopulation[i]=population[j+1];
    155 }
    156 }
    157 for(i=0;i<POPSIZE;i++)//子代变父代
    158 population[i]=newpopulation[i];
    159 }

    ContractedBlock.gifExpandedBlockStart.gifView Code
      1 //***************************************************************************
    2 //Crossover:performs crossover of the selected parents.
    3 //***************************************************************************
    4 void Xover(int one,int two)//基因重组函数
    5 {
    6 int i;
    7 int point;
    8 if(NVARS>1)
    9 {
    10 if(NVARS==2)
    11 point=1;
    12 else
    13 point=(rand()%(NVARS-1))+1;//两个都重组吗?
    14 for(i=0;i<point;i++)//只有第一个基因发生重组有待改进
    15 swap(&population[one].gene[i],&population[two].gene[i]);
    16 }
    17 }
    18 //***************************************************************************
    19 //Swapp: a swap procedure the helps in swappling 2 variables
    20 //***************************************************************************
    21 void swap(double *x,double *y)
    22 {
    23 double temp;
    24 temp=*x;
    25 *x=*y;
    26 *y=temp;
    27 }
    28 //***************************************************************************
    29 //Crossover function:select two parents that take part in the crossover.
    30 //Implements a single point corssover.杂交函数
    31 //***************************************************************************
    32 void crossover(void)
    33 {
    34 int mem,one;
    35 int first=0;
    36 double x;
    37 for(mem=0;mem<POPSIZE;++mem)
    38 {
    39 x=rand()%1000/1000.0;
    40 if(x<PXOVER)
    41 {
    42 ++first;
    43 if(first%2==0)//选择杂交的个体对 杂交有待改进 事实上往往是强者与强者杂交 这里没有考虑雌雄与杂交对象的选择
    44 Xover(one,mem);
    45 else
    46 one=mem;
    47 }
    48 }
    49 }
    50 //***************************************************************************
    51 //Mutation function:Random uniform mutation.a variable selected for mutation
    52 //变异函数 事实基因的变异往往具有某种局部性
    53 //is replaced by a random value between lower and upper bounds of the variables.
    54 //***************************************************************************
    55 void mutate(void)
    56 {
    57 int i,j;
    58 double lbound,hbound;
    59 double x;
    60 for(i=0;i<POPSIZE;i++)
    61 for(j=0;j<NVARS;j++)
    62 {
    63 x=rand()%1000/1000.0;
    64 if(x<PMUTATION)
    65 {
    66 lbound=population[i].lower[j];
    67 hbound=population[i].upper[j];
    68 population[i].gene[j]=randval(lbound,hbound);
    69 }
    70 }
    71 }
    72 //***************************************************************************
    73 //Report function:Reports progress of the simulation.
    74 //***************************************************************************
    75 double report(void)
    76 {
    77 int i;
    78 double best_val;//种群内最优适应值
    79 double avg;//平均个体适应值
    80 //double stddev;
    81 double sum_square;//种群内个体适应值平方和
    82 //double square_sum;
    83 double sum;//种群适应值
    84 sum=0.0;
    85 sum_square=0.0;
    86 for(i=0;i<POPSIZE;i++)
    87 {
    88 sum+=population[i].fitness;
    89 sum_square+=population[i].fitness*population[i].fitness;
    90 }
    91 avg=sum/(double)POPSIZE;
    92 //square_sum=avg*avg*(double)POPSIZE;
    93 //stddev=sqrt((sum_square-square_sum)/(POPSIZE-1));
    94 best_val=population[POPSIZE].fitness;
    95 fprintf(galog,"%6d %6.3f %6.3f %6.3f %6.3f %6.3f\n",generation,best_val,population[POPSIZE].gene[0],population[POPSIZE].gene[1],avg,sum);
    96 return avg;
    97 }
    98 //***************************************************************************
    99 //main function:Each generation involves selecting the best members,performing
    100 //crossover & mutation and then evaluating the resulting population,until the
    101 //terminating condition is satisfied.
    102 //***************************************************************************
    103 void main(void)
    104 {
    105 int i;
    106 double temp;
    107 double temp1;
    108 if((galog=fopen("data.txt","w"))==NULL)
    109 {
    110 exit(1);
    111 }
    112 generation=1;
    113 srand(time(NULL));
    114 fprintf(galog,"number value x1 x2 avg sum_value\n");
    115 printf("generation best average standard\n");
    116 initialize();
    117 evaluate();
    118 keep_the_best();
    119 temp=report();//记录,暂存上一代个体平均适应值
    120 do
    121 {
    122 select();//筛选
    123 crossover();//杂交
    124 mutate();//变异
    125 evaluate();//评价
    126 keep_the_best();//elitist();
    127 temp1=report();
    128 diff=fabs(temp-temp1);
    129 temp=temp1;
    130 generation++;
    131 }while(generation<MAXGENS&&diff>=STOP);
    132 //fprintf(galog,"\n\n Simulation completed\n");
    133 //fprintf(galog,"\n Best member:\n");
    134 printf("\nBest member:\ngeneration:%d\n",generation);
    135 for(i=0;i<NVARS;i++)
    136 {
    137 //fprintf(galog,"\n var(%d)=%3.3f",i,population[POPSIZE].gene[i]);
    138 printf("X%d=%3.3f\n",i,population[POPSIZE].gene[i]);
    139 }
    140 //fprintf(galog,"\n\n Best fitness=%3.3f",population[POPSIZE].fitness);
    141 fclose(galog);
    142 printf("\nBest fitness=%3.3f\n",population[POPSIZE].fitness);
    143 }

    我相信对于那些没有 直接有效算法的最优值求解 使用遗传算法将是一个不错的选择。

    转载于:https://www.cnblogs.com/2010Freeze/articles/2174417.html

    展开全文
  • 之前我们介绍过一些求最优解常用算法模式,比如贪心算法、动态规划算法、穷举算法,都是采用一种确定或几乎确定方式来寻找最优解。所谓确定性是指以上这些算法都是建立在确定性基础上搜索算法,在搜索过程中...
  • 很详细的介绍遗传算法的书 还有实际操作哟
  • 主要运用简单遗传算法来求解两个示例函数最值,程序在matlab上运行,结果和源码都有。

空空如也

空空如也

1 2 3 4 5 ... 20
收藏数 470
精华内容 188
关键字:

遗传算法的应用实例