资源描述：
《遗传算法及其改进_段玉倩》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。
1、第10卷第1期电力系统及其自动化学报Vol.10No.11998年3月ProceedingsoftheEPSAMarch1998X遗传算法及其改进段玉倩贺家李(天津大学自动化学院电力系,天津,300072)摘要本文首先对遗传算法的来源、基本原理、数学机理、特点及其应用进行了论述;为了提高遗传算法的收敛性能,同时考虑到交叉率和变异率的选取问题,本文简要介绍了一种基于个体适应度值的自适应调整交叉率和变异率的自适应遗传算法。分析其不足后,提出了本文的改进方法——改进的自适应遗传算法。在文章的最后,针对几种优化问题对本文所提出的方法和其它两种方法进行了性能比较,证
2、明本文提出的改进方法达到最优解的收敛速度有了明显的提高。关键词遗传算法自适应遗传算法1遗传算法简介早在1967年J.D.Bagley就首次提出了遗传算法(GeneticAlgorithm,简称GA)的概[1]念。但是具有开创意义的遗传算法的理论和方法则是1975年左右由美国密执安(Michi-gan)大学的心理学教授、电工及计算机科学教授JohnH.Holland和他的同事、学生共同研究出的。近年来遗传算法已经吸引了大量的研究者和探索者,其中以D.E.Goldberg的贡献最为卓越。他不但建立和完善了整个GA的体系,而且成功地将其应用到搜索、优化及机器学习
3、等多个领域,为GA的应用开辟了广阔的天地。经过数年的努力,GA已经成为一种成熟的具有极高鲁棒性和广泛适用性的全局优化算法。遗传算法是建立在达尔文(Darwin)的生物进化论和孟德尔(Mendel)的遗传学说基础上的算法。生物体可以通过遗传和变异来适应于外界环境。在进化论中,每一物种在不断的发展过程中都是越来越适应环境,物种的每个个体的基本特征被后代所继承,但后代又不完全同于父代,这些新的变化,若适应环境,则被保留下来,否则,就将被淘汰。亦即适者生存,不适者被淘汰。在遗传学中认为,遗传是作为一种指令遗传码封装在每个细胞中,并以基因的形式包含在染色体中,每个基
4、因有特殊的位置并控制某个特殊的性质。每个基因产生的个体对环境有一定的适应性。基因杂交和基因突变可能产生对环境适应性强的后代,通过优胜[2]劣汰的自然选择,适应值高的基因结构就保存下来。遗传算法就是模仿了生物的遗传、进化原理,并引用了随机统计理论而形成的。在求解过程中,遗传算法从一个初始变量群体开始,一代一代地寻找问题的最优解,直至满足收敛判据或预先设定的迭代次数为止。它是一种迭代式算法。2遗传算法的基本原理X本文系国家教委博士学科点基金资助项目本文97年6月20日收到·40·电力系统及其自动化学报1998年第1期遗传算法是一种基于自然选择和群体遗传机理的搜
5、索算法,它模拟了自然选择和自然遗传过程中发生的繁殖、杂交和突变现象。在利用遗传算法求解问题时,问题的每个可能的解都被编码成一个“染色体”,即个体,若干个个体构成了群体(所有可能解)。在遗传算法开始时,总是随机地产生一些个体(即初始解),根据预定的目标函数对每个个体进行评价,给出了一个适应度值。基于此适应度值,选择个体用来复制下一代。选择操作体现了“适者生存”原理,“好”的个体被选择用来复制,而“坏”的个体则被淘汰。然后选择出来的个体经过交叉和变异算子进行再组合生成新的一代。这一群新个体由于继承了上一代的一些优良性状,因而在性能上要优于上一代,这样逐步朝着更
6、优解的方向进化。因此,遗传算法可以看作是一个由可行解组成的群体逐代进化的过程。图1示出了简单遗传算法的基本过程。图1简单遗传算法基本流程图遗传算法的操作过程详述如下。2.1编码(encoding)利用遗传算法进行问题求解时,首先确定问题的目标函数和变量,然后对变量进行编码。这样做主要是因为在遗传算法中,问题的解是用数字串来表示的,而且遗传操作算子也是直接对串进行操作的。编码方式可分为二进制编码和所谓的实数编码,即十进制编码。遗传算法的创始人Holland认为,将一个十进制数利用二进制编码后,其占的位数增多,描述的比较细致,相当于加大了搜索范围,从而能以较大
7、的概率搜索到全局最优解。同时通过一些简单的变换规则就可以逐步地改进这些二进制编码表示的结构,使之往好的方向“进化”,因此,在他的专著中基本上采用这种传统的编码方式。总的说来,采用二进制编码方式有如下优点:它与计算机码制相一致,适于计算机应用;对于码串的每一位,只有1和0两个码值,在交叉和变异等操作中原理清晰,操作简单;表示的变量范围大,如长为L的码串L最多可表示2个不同的变量;适合于表示离散变量,而对于连续变量,只要群体总数取足够[3]多,就可以达到足够的精度。但是,利用二进制编码方式也存在着缺点。对于一些大规模的多变量的优化问题,如果其各变量用二进制表示
8、,同时为了保证问题的解具有一定的精度,那么得到的数字串将会很199
