(遗传算法与优化问题.doc

 遗传算法与优化问题 摘要：遗传算法中的生物遗传学概念由于遗传算法是由进化论和遗传学机理而产生的直接搜索...则标准遗传算法的变换矩阵P是基本的.定理2 标准遗传算法(参数如定理1)不能收敛... 关键词：算法,矩阵 类别：专题技术 来源：牛档搜索（Niudown.COM）  　　本文系牛档搜索（Niudown.COM）根据用户的指令自动搜索的结果，文中内涉及到的资料均来自互联网，用于学习交流经验，作品其著作权归原作者所有。不代表牛档搜索（Niudown.COM）赞成本文的内容或立场，牛档搜索（Niudown.COM）不对其付相应的法律责任！ 实验十 遗传算法与优化问题 一、问题背景与实验目的 遗传算法（Genetic Algorithm—GA），是模拟达尔文的遗传选择和自然淘汰的生物进化过程的计算模型，它是由美国Michigan大学的J.Holland教授于1975年首先提出的．遗传算法作为一种新的全局优化搜索算法，以其简单通用、鲁棒性强、适于并行处理及应用范围广等显著特点，奠定了它作为21世纪关键智能计算之一的地位． 本实验将首先介绍一下遗传算法的基本理论，然后用其解决几个简单的函数最值问题，使读者能够学会利用遗传算法进行初步的优化计算． 1．遗传算法的基本原理 遗传算法的基本思想正是基于模仿生物界的遗传过程．它把问题的参数用基因代表，把问题的解用染色体代表在计算机里，从而得到一个由具有不同染色体的个体组成的群体．这个群体在问题特定的环境里生存竞争，适者有最好的机会生存和产生后代．后代随机化地继承了父代的最好特征，并也在生存环境的控制支配下继续这一过程．群体的染色体都将逐渐适应环境，不断进化，最后收敛到一族最适应环境的类似个体，即得到问题最优的解．值得注意的一点是，现在的遗传算法是受生物进化论学说的启发提出的，这种学说对我们用计算机解决复杂问题很有用，而它本身是否完全正确并不重要目前生物界对此学说尚有争议．由于遗传算法是由进化论和遗传学机理而产生的直接搜索优化方法；故而在这个算法中要用到各种进化和遗传学的概念．这些概念如下概率概率值变异概率概率值，求 ． 注：这是一个非常简单的二次函数求极值的问题，相信大家都会做．在此我们要研究的不是问题本身，而是借此来说明如何通过遗传算法分析和解决问题． 在此将细化地给出遗传算法的整个过程． （1）编码和产生初始群体 首先第一步要确定编码的策略，也就是说如何把到2这个区间内的数用计算机语言表示出来． 编码就是表现型到基因型的映射，编码时要注意以下三个原则： 完备性：问题空间中所有点（潜在解）都能成为GA编码空间中的点（染色体位串）的表现型； 健全性：GA编码空间中的染色体位串必须对应问题空间中的某一潜在解； 非冗余性：染色体和潜在解必须一一对应． 这里我们通过采用二进制的形式来解决编码问题，将某个变量值代表的个体表示为一个{0，1}二进制串．当然，串长取决于求解的精度．如果要设定求解精度到六位小数，由于区间长度为，则必须将闭区间 分为等分．因为 所以编码的二进制串至少需要22位． 将一个二进制串（b21b20b19…b1b0）转化为区间内对应的实数值很简单，只需采取以下两步（Matlab程序参见附录4）： 1）将一个二进制串（b21b20b19…b1b0）代表的二进制数化为10进制数： 2） 对应的区间内的实数： 例如，一个二进制串a=1000101110110101000111表示实数0.637197． =(1000101110110101000111)2=2288967 二进制串0000000000000000000000，1111111111111111111111，则分别表示区间的两个端点值-1和2． 利用这种方法我们就完成了遗传算法的第一步——编码，这种二进制编码的方法完全符合上述的编码的三个原则． 首先我们来随机的产生一个个体数为4个的初始群体如下： pop(1)={ 1101011101001100011110， %% a1 1000011001010001000010， %% a2 0001100111010110000000， %% a3 0110101001101110010101} %% a4（Matlab程序参见附录2） 化成十进制的数分别为： pop(1)={ 1.523032，0.574022 ，-0.697235 ，0.247238 } 接下来我们就要解决每个染色体个体的适应值问题了． （2）定义适应函数和适应值 由于给定的目标函数在内的值有正有负，所以必须通过建立适应函数与目标函数的映射关系，保证映射后的适应值非负，而且目标函数的优化方向应对应于适应值增大的方向，也为以后计算各个体的入选概率打下基础．