生物-AI章 遗传算法

《生物-AI章 遗传算法》由会员分享，可在线阅读，更多相关《生物-AI章 遗传算法（44页珍藏版）》请在金锄头文库上搜索。

1、第7章 遗传算法7.1 遗传算法简介 7.2 基本遗传算法 7.3 函数优化 7.4 旅行商问题7.1 遗传算法简介 7.1.1 遗传算法的起源n自然界所提供的答案是经过漫长的自适应遗传 过程获得的结果。n我们也可以利用这一过程本身去解决一些复杂的问 题。 n遗传算法的研究主要集中在以下几个方面：函数优 化、组合优化生产调度、自动控制、机器人学、图 像处理、人工生命、演化编程和机器学习。7.1.2 设计遗传算法的基本原则n适应性原则 n可靠性原则 n收敛性原则 n稳定性原则 n生物类比原则 7.1.3 设计遗传算法的基本步骤n确定编码方案n选择何种编码表示有时对算法的性能、效率等产生很大的 影

2、响。 n确定适应函数 n解的适应值是演化过程中进行选择的唯一依据。 n选择策略的确定 n优胜劣汰的选择机制使得适应值大的解有较高的存活率， 这是遗传算法与一般搜索算法的主要区别之一。 n控制参数的选取 n遗传算子的设计 n主要包括繁殖、杂交、变异以及其它高级操作。 7.1.3 设计遗传算法的基本步骤procedure genetic programbegininitialize /种群初始化evaluate /评价种群while ( not termination-condition) dobegin select from /选择个体到下一种群alter /对种群进行遗传操作evaluate

3、 end end 7.1.4 遗传算法的主要特点n智能性 n遗传算法具有自组织、自适应和自学习等特性。 n灵活的个体编码 n灵活的个体编码使遗传算法可直接对结构对象进行描述和 操作。 n多点搜索能力n遗传算法是同时对多个解进行处理、评估，并行地爬多个 峰。这一特点使遗传算法具有较好的全局搜索能力，减少 了陷于局部优解的风险。 7.1.4 遗传算法的主要特点n并行性 n遗传算法是内在并行的。演化计算适合在并行机或分布式 系统中做大规模的并行处理。 n遗传算法是内含并行性的。由于遗传算法采用种群的方式 组织搜索，从而可同时搜索空间内的多个区域，并相互交 流信息 .7.1.5 遗传算法的研究内容和应

4、用前景n算法的理论模型研究 n优化求解方法的研究 n学习系统的遗传算法研究 n新的进化模型 n遗传算法的并行分布式处理 n遗传算法的应用系统 n演化硬件 7.2 基本遗传算法7.2.1 编码表示n位串编码 二进制编码即是将原问题的解空间映射到位串空 间 上，然后在位串空间上进行遗传操作。l优点 l算法易于用生物遗传理论来解释并使得遗传操作（如杂 交、变异等）很容易实现 l采用二进制编码时，算法处理的模式数最多 l缺点l相邻整数的二进制编码可能具有较大的Hamming距离 l 二进制编码时，一般要先给出求解的精度以确定串长 l在求解高维优化问题时，二进制编码串将非常之长 7.2.1 编码表示n实

5、数编码 l对于问题的变量是实向量的情形，可以直接采用实进制进 行编码。这样，便可直接在解的表现型上进行遗传操作。 从而便于引入与问题领域相关的启发信息以增加遗传算法 的搜索能力。 n有序串编码l目标函数的值不仅与表示解的字符串中各字符的值有关， 而且与其所在字符串的位置有关。这样的问题称为有序问 题。 l需要针对具体问题专门设计有效且能保证后代合法的遗传 算子。l这类编码方案较多地使用在组合优化问题之中。 7.2.1 编码表示n结构式编码 l将问题的解表示树或图的形式的编码称为结构式编码。l因为遗传算子是直接在解的表现型上进行操作，这样使得 我们比较容易加入与领域有关的知识和一些启发式的信息

6、。 7.2.2 适应性的度量个体的适应值即是它繁殖的能力，它将直接关 系到其后代的数量，在遗传算法中，适应函数是用 来区分群体中个体好坏的标准，是算法演化过程的 驱动力，同时也是进行自然选择的唯一依据。 n原始适应函数 l原始适应函数是问题求解目标的直接表示，通常采用问题 的目标函数作为个体的适应度量 。l定义原始适应函数的方法可能不止一种，选择时要尽量反 映问题本身整体特性，而不能只追求片面的目标 。7.2.2 适应性的度量n标准适应函数l适应值会出现两种情形，一是极小情形即原始适应值越小 个体性能越好；另一种是极大化情形即原始适应值越大个 体性能越好 。l遗传算法中的某些选择策略则要求适应

7、函数是非负的，而 且适应值越大表明个体的性能越好。 l对于极小化情形，标准适应值可定义为 ：n适应值的调节l存在问题：过早收敛、停滞现象 l改变算法性能的方法之一是对适应值进行调节，即通过变 换，改变原适应值的比例关系。 7.2.3 选择策略n不同的选择策略将导致不同的选择压力，即下一代 中父代个体的复制数目的不同分配关系。 n转盘式选择 l转盘式选择是基于适应值比例的选择中比较重要的选择策 略。 l先计算个体的相对适应值 ，即l根据选择概率 把一个圆盘分成N份 l生成一个内的随机数 r，若 ，则选择个 体 i7.2.3 选择策略n基于排名的选择 l首先根据个体 的适应值在群体中的排名来分配其

8、选择 概率 。l根据这个概率使用转盘选择 l线性排名选择 l线性排名选择方法是按适应值大小从好到坏依次排列为 ，然后根据一个线性函数分配选择概率 。 7.2.3 选择策略n非线性排名选择 l首先按适应值从好到坏依次排列群体成员，并按非线性函 数分配选择概率 。7.2.4 遗传算子的设计n杂交算子 l杂交运算是指对两个相互配对的染色体按某种方式相互交 换其部分基因，从而形成两个新的个体。l单点杂交 单点杂交又称为简单杂交，它是指在个体编码串 中只随机设计一个杂交点，然后在该点相互交换两个 配对个体的部分染色体。7.2.4 遗传算子的设计n双点杂交与多点杂交n双点杂交是指在个体编码串中设置了二个杂

9、交点，然 后再进行部分基因交换。 7.2.4 遗传算子的设计n均匀杂交l均匀杂交是指两个配对个体每一个基因座上的基因都 以相同的杂交概率进行交换，从而形成两个新的个体 。l均匀杂交实际上可归属于多点杂交的范围 .l算术杂交 l算术杂交是由两个个体的线性组合而产生出两个新的 个体。l为了能够进行线性组合运算，算术杂交的操作对象一 般是浮点数所表示的个体。 7.2.4 遗传算子的设计n变异算子 l变异运算是指将个体染色体编码串中的某些基因座上的基 因值用该基因座的其它等为基因来替换，从而形成一个新 的个体。l遗传算法中使用变异算子主要有以下两个目的：l1）改善遗传算法的局部搜索能力。l2）维持群体

10、的多样性，防止出现早熟现象。7.2.4 遗传算子的设计n基本位变异 l对个体的每一个基因座，依变异概率 指定其为变 异点。 l对每一个指定的变异点，对其基因值做取反运算或用 其他等位基因值来代替，从而产生出一个新的个体。 l均匀变异 n依次指定个体编码串中的每个基因座为变异点。n对每一个变异点，以变异概率 从对应基因的取值 范围内取一随机数来替代原有基因值。7.2.4 遗传算子的设计n非均匀变异 l非均匀变异的具体操作过程与均匀变异相类似，但它重点 搜索原个体附近的微小区域。 7.3 函数优化n优化技术是一种以数学为基础，用于求解各种工程 问题优化解的应用技术 .n最优化问题可分为函数优化问题

11、和组合优化问题两 大类，其中函数优化的对象是一定区间内的连续变 量，而组合优化的对象则是解空间中的离散状态。n所有的搜索、优化都是对目标函数的“函数”优化。n近年来，遗传算法作为一种全新的优化方法，其巨 大的潜力受到越来越多学者的重视。 7.3.1 问题描述 n全局最大化 : 对于 ，寻求点 ，都 有n全局最小化：对于 ，寻求点 ，都 有n不论待求解问题是求最大值还是求最小值问题，我们可将待 求解的问题一律看成求解最大值问题。 n转化方法如下：如果优化问题是就函数 的最小值，它等同 与求函数 的最大值，其中 ，即 7.3.1 问题描述n目标函数 在其值域里只取正值，若为负，可通 过加入某个正数

12、 C 使之为正，即 7.3.2 种群的初始化n对于函数优化来说，在初始化过程中需在上、下限 区间内产生随机数，并将这个随机数赋给变量 。7.3.3 选择策略 n在选择策略上，本例采用基于概率的轮转盘选择策 略。计算出群体的总适应值 n对每个个体 ，选择概率 ，显然 。 n每个个体 的累积概率 ，我们 可得知 且 。 7.3.4 遗传算子n杂交算子 n对新群体中的每个个体产生一个在0,1区间内产生随机 浮点数；n如果 ，随机地选择个体配对，然后进行杂交操作 。若个体中有n个分量，在1,n区间中产生随机整数 pos ，pos表示杂交点的位置。n若两个个体分别为：在pos点杂交后产生子代 7.3.4

13、 遗传算子n算法的程序描述如下： /在0,1区间产生随机数/判断随机数是否小于杂交概率/进行杂交操作7.3.4 遗传算子/杂交点，即第几个分量进行相互交换/在n个分量中，随机确定第pos个分量进行相互交换/前pos个分量进行相互交换7.3.4 遗传算子n变异算子 l变异就是以很小的概率 随机地改变群体中个体(染色体) 的某些基因的值。l具体算法的描述如下： /在0,1区间产生随机数/判断随机数是否小于变异概率/为第i个个体的j变量进行变异 操作7.4 旅行商问题7.4.1 旅行商问题的描述n已知n个城市之间的距离，现有一推销员必须访问这 n个城市，并且每个城市只能访问一次，最后必须返 回出发城

14、市。如何安排他对这些城市的访问次序， 可使其旅行路线的总长最短。n旅行商问题可分为对称旅行商问题和非对称旅行商 问题。 nTSP问题求解的研究工作主要集中在以下几个方面 ：n采用适当的表示方法表示个体的编码；n设计可用的遗传算子，以爆出父代的特性避免新个体的不 可行性；n防止算法过早的收敛。 7.4.2 个体的编码表示nTSP问题的个体编码表示方法大致可分为两大类：n在巡回旅行路线所经过的城市序列；n各城市在巡回旅行路线中的邻接关系。n近邻表示 n近邻表示方法将路径表示成n个城市的一个排列，若排列 中的第i位为城市，当且仅当路径中从城市i所到达的下一 个城市为j。 n次序表示 l表示方法为：先取城市集合C的顺序排列如C=（1 2 3 4 5 6 7 8 9）作为次序排列的一个参照点，然后按路径中 城市处在C的位置确定表示串中的点，且每确定一个则从 C中删除相应的城市。 7.4.2 个体的编码表示n路径表示l路径表示可能是TSP问题最自然、最直接的表示方式。它 直接采用城市在路径中的相对位置来进行表示。l例如，路径51786293 4直接表示成（5 1 7 8 6 2 9 3 4） 7.4.3 杂交算子n部分映射杂交 l