实验十遗传算法与优化问题VIP专享VIP免费

实验十遗传算法与优化问题数学实验问题背景和实验目的遗传算法（GeneticAlgorithm，简称GA），是模拟达尔文的遗传选择和自然淘汰的生物进化过程的计算机算法，它由美国Holland教授1975年提出。遗传算法作为一种新的全局优化搜索算法，以其简单通用、鲁棒性强、适合并行处理及应用范围广等显著特点，奠定了它作为21世纪关键智能计算之一的地位。本实验主要介绍遗传算法的基本理论，然后通过求解几个简单的函数最值问题，来说明如何利用遗传算法进行初步的优化计算。遗传算法基本原理基本思想：基于模仿生物界遗传学的遗传过程，把问题的参数用基因来表示，把问题的解用染色体来表示代表（在计算机里用二进制码表示），从而得到一个由具有不同染色体的个体组成的群体。这个群体在问题特定的环境里生存竞争，适者有最好的机会生存和产生后代，后代随机化地继承父代的最好特征，并也在生存环境的控制支配下继续这一过程。群体的染色体都将逐渐适应环境，不断进化，最后收敛到一族最适应环境的类似个体，即得到问题最优解。遗传学相关概念遗传学遗传算法数学1个体要处理的基本对象、结构也就是可行解2群体个体的集合被选定的一组可行解3染色体个体的表现形式可行解的编码4基因染色体中的元素编码中的元素5基因位某一基因在染色体中的位置元素在编码中的位置6适应值个体对于环境的适应程度，可行解所对应的适应或在环境压力下的生存能力函数值7种群被选定的一组染色体或个体根据入选概率定出的一组可行解8选择从群体中选择优胜的个体，淘汰劣质个体的操作保留或复制适应值大的可行解，去掉小的可行解遗传学相关概念遗传学遗传算法数学9交叉一组染色体上对应基因段的交换根据交叉原则产生的一组新解10交叉概率染色体对应基因段交换的概率（可能性大小）闭区间[0,1]上的一个值，一般为0.65~0.9011变异染色体水平上基因变化编码的某些元素被改变12变异概率染色体上基因变化的概率（可能性大小）开区间(0,1)内的一个值,一般为0.001~0.0113进化、适者生存个体进行优胜劣汰的进化一代又一代地优化，目标函数取到最大值，最优的可行解遗传算法的步骤遗传算法计算优化的过程就如同生物学上生物遗传进化的过程，主要有三个基本操作（或算子）：选择（Selection）交叉（Crossover）变异（Mutation）遗传算法的步骤遗传算法基本步骤：把问题的解表示成“染色体”，在算法中就是以二进制编码的串，给出一群“染色体”，也就是假设的可行解把这些可行解置于问题的“环境”中，按适者生存的原则，选取较适应环境的“染色体”进行复制，并通过交叉、变异过程产生更适应环境的新一代“染色体”群经过这样的一代一代地进化，最后就会收敛到最适应环境的一个“染色体”上，它就是问题的最优解遗传算法有很多种具体的不同实现过程，这里仅介绍标准遗传算法的主要步骤。遗传算法具体步骤①选择编码策略，把参数集合（可行解集合）转换染色体结构空间；②定义适应函数，便于计算适应值；③确定遗传策略，包括选择群体大小，选择、交叉、变异方法以及确定交叉概率、变异概率等遗传参数；④随机产生初始化群体；⑤计算群体中的个体或染色体解码后的适应值；⑥按照遗传策略，运用选择、交叉和变异算子作用于群体，形成下一代群体；⑦判断群体性能是否满足某一指标，或者已完成预定的迭代次数，不满足则返回第五步，或者修改遗传策略再返回第六步．产生初始群体是否满足终止条件得到结果是结束程序否计算每个个体的适应值以概率选择遗传算子选择一个个体复制到新群体选择两个个体进行交叉插入到新群体选择一个个体进行变异插入到新群体得到新群体例1.设f(x)=-x2+2x+0.5，求maxf(x),x∈[-1,2]。遗传算法的实际应用我们将通过这个简单的求最值问题来详细给出遗传算法的整个过程。1编码和产生初始群体首先需要确定编码的策略，也就是说如何把[-1,2]区间内的数用计算机语言表示出来。编码就是从表现型到基因型的映射，编码时要注意以下三个原则：完备性：问题空间中所有点（潜在解）都能成为GA编码空间中的点（染色体位串）的表现型；健全性：GA编码空间中的染色体位串必须对应问...