工学]基于遗传算法控制直线多级倒立摆

工学]基于遗传算法控制直线多级倒立摆内容摘要：

选择、繁衍和替换过程，直到整个过程满足一定的结束条件为止。 通常情况下，进化过程的最后一改善或解决实际问题 实际问题 参数 集 编码成位串 计算适应度值 统计结果 遗传操作 种群 2 种群 1 三种遗传算子： 选择算子 交叉算子 变异算子 经过优化的一个或多个参数集（解码后） 随机算子 种群 1 种 群 2 代群体中的适应 度值最高的个体，就是利用遗传算法求解的优化问题的最终结果。 遗传算法的实现步骤 基本遗传算法（ Simple Geic Algorithm）可定义为一个 8 元组： ),,( 0 TMPECS GA  （ ） 式中， C—— 个体编码方法， SGA 采用二进制编码方法； E—— 个体适应度评价函数； P0—— 初始群体； M—— 群体的大小，通常取 20～ 100；  —— 选择算子， SGA 使用比例选择算子；  —— 交叉算子， SGA 采用单点交叉算子；  —— 变异算子， SGA 采用基本位变异算子；  —— 算法终止条件，一般终止进化代数为 100~500。 1. 参数编码与解码 遗传算法主要是通过遗传算子对群体中具有某种结构形式的个体施加重组处理，从而不断地搜索出群体中个体间的结构相似性，逐代优化参数以趋近最优解。 遗传算法不能直接处理问题空间的参数，必须在目标问题的实际描述与遗传算法的染色体位串结构之间建立联系。 由问题空间向遗传编 码空间的映射称作编码（ Encoding），而由编码空间向问题空间的映射称作解码（ Decoding）。 编码将问题域知识转化为遗传算法空间的码串描述。 理论上，编码应该适合要解决的问题，并非是简单的描述问题。 因而在具体的应用中，编码设计应遵循如下原则： （ 1） 完全性 原则上，分布在所有问题域的解都有可能被构造出来。 （ 2） 分闭性 每个基因码，对应一个可接受的个体，封闭性保证系统不会产生无效的个体。 （ 3） 紧致性 若两种基因码 g1和 g2都被解码成相同的个体，若 g1比 g2占的空间少，就认为 g1比 g2紧致。 （ 4） 可扩展性 对于具体的问题， 编码的大小确定了解码的时间，两 者存在一定的函数关系，若增加一种表现型，作为基因型的编码大小也做 出相应的增加。 （ 5） 多重性 多个基因型解码成一个表现型，即从基因型到相应的表现型空间是多对一的关系，这是基因的多重性。 若相同的基因型被解码成不同的表现型，这是表现型的多重性。 （ 6） 个体可塑性 决定表现型与相应给定基因型是受环境影响的。 （ 7） 模块性 若表现型的构成中有多个重复的结构，在基因型编码中这种重复是应该避免的。 （ 8） 冗余性 冗余性能够提高可靠性和鲁棒性。 （ 9） 复杂性 包括基因型的结构复杂性，解码复杂性，计算时空复杂性（基因解码、 适应值、再生等） [30]。 编码方式常用的有二进制编码和浮点数编码。 （ 1）二进制编码 二进制编码是遗传算法中常用的一种编码方法，即将原问题的解映射为 0， 1 组成的位串，然后在位串空间上进行遗传操作。 得到的结果再通过解码过程还原为原问题解的解空间，接着进行适应度值的计算。 设种群中的个体数目为 n， itx 表示第 t 代的 i 个个体， )...,2,1{ ni。 每个个体用 l 位二进制表示。 这样每个个体 }1,0{,}{  IBIBx mlit ，这样每个个体基 因位数目 L=ml。 个体 itx 可以表示为 ml 维的行向量，即 ].. ... ... ... .[ )()1)1((2)1()()1( mlitlmitltltlititit xxxxxxx 。 第 t 代种群 tX 可以表示为一个 mln 的矩阵 ]...[ 21 ntttt xxxX 。 个体 itx 的第 k 个长度为 l 的二进制码串转化为实数的解码函数  为 )2(12),( 11)(   jtjjklitl kkkit xuvukx （ ） 式（ ）中 kv 和 ku 分别为第 k 个实数范围的上限和下限。 很多数值计算与非数值优化问题都可以用二进制编码来实现，该方法具有如下优点：编码方式简单且操作方便；符合最小字符集编码原则，便于用模式定理进行分析。 但当二进制编码在求解连续优化问题存在以下缺点：相邻整数的二进制可能有较大的 Hamming 距离，例如 15 和 16 的二进制表示为 0 1 1 1 1 和 1 0 0 0 0。 因此算法要从 15 改进到 16 则必须改变所有的位。 这种缺陷将降低遗传算子的搜索效率 [17,31]。 （ 2）浮点数编码 为了克服二进制编码对于一些多维、高精度要求的连续函数优化问题弊端可以采用十进制或浮点数进行编码。 所谓浮点数编码方法，是指个体的每个基因值用某一范围内的浮点数来表示，个体编码的长度等于其决策变量的个体。 浮点数编码必须保证基因值在给定的区间限制范围内。 同时，遗传操作中所使用的交叉、变异等也引入了专门的遗传算子，保证其运算结果所产生的新个体的基因值也在这个区间限制范围内 [32]。 浮点数编码适用于搜索空间较大、精度要求较高的遗传方案中，其运算简 单，提高了遗传算法的运算效率，有利于遗传算法与经典优化方法的混合应用，便于处理具有约束条件的复杂决策变量。 2. 适应度函数值计算 在生物的遗传和进化过程中，对环境适应度较高的物种将有更多的繁殖机会，遗传算法中也使用类似的概念来度量群体中各个个体在优化计算中有可能、或有助于找到最佳解的寻优过程。 适应度值较高的个体遗传到下一代的概率就较大，而适应度值较低的个体遗传到下一代的概率就相对小些。 度量个体适应度值的函数称为适应度函数（ Fitness Function）。 适应度函数的选取至关重要，它直接影响遗传算法的收 敛速度以及能否找到最优解。 设计适应度函数要保证其：①单值、连续、非负、最大化；②满足合理性和一致性③计算量小、通用性强。 在遗传算法的实际应用中，适应度函数的确定方法通常有以下三种： （ 1） 直接以待求解的目标函数转化为适应度函数，即 若目标函数为最大化问题则取 )())(( xfxfF it  （ ） 若目标函数为最小问题则取 )())(( xfxfF i t  （ ） 这种适应度函数简单直观，但是存在两个问题，其一是可能不满足常用的轮盘赌选择中概率非负的要求；其 二是某些待求解的函数在函数值分布上相差很大，由此得到的平均适应度可能不利于体现种群的平均性能，影响整个遗传算法的性能。 （ 2）界限构造法 若目标函数为最大化问题则   其他,0 )(,)())(( m inm in cxfcxfxfF i t （ ） 式（ ）中， minc 为 )(xf 的最小估计。 若目标函数为最小问题   其他,0 )(),())(( m axm ax cxfxfcxfF i t （ ） 这种方法是对第一种方法的改进，在具体的应用中优势会存在预先估计困难、不精 确的问题。 （ 3） 若目标函数为最大问题取 0)(,0,)(1 1))((  xfccxfcxfF i t （ ） 若目标函数为最小问题取 0)(,0,)(1 1))((  xfccxfcxfF i t （ ） 该方法与第二种方法类似， c 为目标函数界限的保守估计值 [17,33,34]。 3 遗传操作 遗传算法的操作算子包括选择、交叉（又称重组）和变异三种基本形式。 三种遗传算子是遗传算法具备强大搜索能力的核心，是模拟自然选择以及遗传过程中的繁殖恶化突变现象的主要载体。 遗传算法利用交叉和变异算子产生新的群体进而实现种群进化，遗 传算子的设计是遗传策略的主要组成部分，也是调整和控制进化过程的基本工具。 （ 1）选择算子 选择是从群体中挑选优良的个体同时淘汰劣质个体的遗传操作过程。 它建立在适应度评估的基础上，个体适应度越大，其被选中的可能性就越大，它的子代保留到匹配池（ mating pool）中的个数就越多。 常用的遗传方法有 [17,35]： ① 轮盘赌方法（ roulette wheel model） 轮盘赌方法是遗传算法中最基本也最常用的选择方法。 设群体为 P，个体的适应度为Fitness，则个体 i 被选择的概率为  Pj ji FitnessFitnessP1 （ ） 其累计概率为 ij ii Pq 1 （ ） 式（ ）中， Pj jFithess1表示该种群在这一代中的总适应度值。 选择按旋转轮盘（轮盘上按 Pi 的大小划分为不等的扇区），显然适应度大的个体其选择概率越大，在轮盘中所占的位置越大，被选中的概率也就越大。 ② 排序选择法（ rankbased model） 排序选择法以标准化几何分布规律随机对种群中染色体进行选择，以最佳染色体的选择概率 Ps作为基本参数，按染色体的 排列序号确定其选择概率。 排序法的最大优点在于排序法忽略实际染色体的适应度值，用染色体的顺序来换算出相应的生存概率，换算原则为大适应度值对高选择概率，小适应度值对低选择概率。 这样既能保证大适应度值染色体获得高选择概率，同时又阻止某些超级染色体过快地控制遗传过程。 排序选择法首先需根据最佳染色体选择概率计算标准分布值，表达式如下 Pss PPt )1(1  （ ） 接着根据上式计算染色体选择概率： PkPtP kNsk ,. ..2,1,)1( 1)(   （ ） 式（ ）中 )(kN 为第 k 个染色体的适应值在种群中由大到小排列的序号。 Ps为最佳染色体选择概率， P 为样本数。 最后计算染色体的累计选择概率值 qk Pkpq kj jk ,...2,1,1   （ ） ③ 最佳个体保存法 最佳个体保存法把群体中适应度值最高的个体不进行配对交叉而直接复制到下一代。 该方法的好处在于保证了进化过程中的某一代的最优解不被交叉和变异操作所破坏。 然而该方法使一些局部优化个体的遗传基因会急速增加而达到局部优化解，其全局搜索能力差，不利于多峰值的搜索问题，因而该 方法一般与其他选择方法相结合而使用。 （ 2）交叉算子 在遗传操作中，交叉操作因其全局搜索能力而成为主要算子。 交叉操作的作用在于它不仅使原来种群中的优良个体的特性能够在一定程度上保持，而且其探索新的空间的能力使得种群中的个体具有多样性。 它是 GA 获取新的优良个体的最重要手段。 交叉是指把两个父串个体的部分结构加以替换重组而成新个体的操作，交叉算子分为两类，一类为二进制交叉，一类为浮点数交叉。 ① 二进制交叉运算 该操作按一定的概率 Pc在匹配池中随机地选取两个个体进行，交叉的位置也是随机确定的。 其二进制编码操作又可 分为单点交叉、两点交叉和多点交叉。 单点交叉：是在个体中随机地选定一个交叉点，两个个体在该点前后进行部分互换以产生新的个体，如： 父辈个体 1 AAAAAA|AAAAAA → BBBBBB|AAAAAA 父辈个体 2 BBBBBB|BBBBBB → AAAAAA|BBBBBB 两点交叉：与单点交叉类似，只是随机设置两个交叉点进行部分乎换，以产生新的个体，如： 父辈个体 1 AAAA|AAAA|AAAA → AAAA|BBBB|AAAA 父辈个体 2 BBBB|BBBB|BBBB → BBBB|AAAA|BBBB 多点交叉：该交叉操作即前述两种交叉操作的推广，多点交叉有时又被叫作广义交叉。 当用 c 表示交叉参数时，则 c=1 或 c=2 时即为单点交叉和两点交叉。 ② 浮点数编码的交叉运算 常用的浮点数编码的交叉运算为线性交叉又称算术交叉。 即两个父代以线性组合的方式产生子代。 对于凸搜索空间，算术交叉保证其子代的闭合性。 也就是问题空间内的任何两个染色体的线性组合仍属于问题空间。 该方法在种群中均匀随机选取两条染色体)...2,1(21 nlvv ll 、 作为交叉双亲；然后在 [0,1]区间内产生随机数 lr ；对染色体按交叉次数进行如式（ ）操作 llllllllll rvrvv rvrvv212211 )1(39。 )1(39。   （ ） 式中 39。 39。 21 ll vv 、 为产生的新染色体。 （ 3）变异运算 变异运算使得遗传算法具有局部随机搜索能力，配合交叉操作以维持种群的多样性，防止出现过早收敛。 变异算子也具有两类，一类为基本的二进制变异操作，另一类为针对浮点数而言的浮点数变异。 ① 二进制变异运算 变异是以很小的概率 Pm 随机地改变个体串中染色体的某些基因值。 在二进制编码方式中，变异操作基本过程是变 异算子随机地将某个基因值取反，即“ 0”变为“ 1”，“ 1”变为“ 0”。 如： [01000101000101011010] → [01010101000101001010] ② 浮点数变异运算 对于浮点数则常用的变异手段有均匀变异、边界变异和非均匀变异等。 浮点数变异目的在于扩大染色体基因的取值范围。 均匀变异：设种群中有染色体 ),...,( 21 ml v。