1、第7章 遗传算法,7.1 遗传算法简介7.2 基本遗传算法7.3 函数优化7.4 旅行商问题,7.1 遗传算法简介,7.1.1 遗传算法的起源,自然界所提供的答案是经过漫长的自适应遗传过程获得的结果。我们也可以利用这一过程本身去解决一些复杂的问题。 遗传算法的研究主要集中在以下几个方面：函数优化、组合优化生产调度、自动控制、机器人学、图像处理、人工生命、演化编程和机器学习。,7.1.2 设计遗传算法的基本原则,适应性原则 可靠性原则 收敛性原则 稳定性原则 生物类比原则,7.1.3 设计遗传算法的基本步骤,确定编码方案选择何种编码表示有时对算法的性能、效率等产生很大的影响。 确定适应函数 解的
2、适应值是演化过程中进行选择的唯一依据。 选择策略的确定 优胜劣汰的选择机制使得适应值大的解有较高的存活率，这是遗传算法与一般搜索算法的主要区别之一。 控制参数的选取 遗传算子的设计 主要包括繁殖、杂交、变异以及其它高级操作。,7.1.3 设计遗传算法的基本步骤,procedure genetic program begin initialize /种群初始化 evaluate /评价种群 while ( not termination-condition) do begin select from /选择个体到下一种群 alter /对种群进行遗传操作 evaluate endend,7.1.
3、4 遗传算法的主要特点,智能性 遗传算法具有自组织、自适应和自学习等特性。 灵活的个体编码 灵活的个体编码使遗传算法可直接对结构对象进行描述和操作。 多点搜索能力遗传算法是同时对多个解进行处理、评估，并行地爬多个峰。这一特点使遗传算法具有较好的全局搜索能力，减少了陷于局部优解的风险。,7.1.4 遗传算法的主要特点,并行性 遗传算法是内在并行的。演化计算适合在并行机或分布式系统中做大规模的并行处理。 遗传算法是内含并行性的。由于遗传算法采用种群的方式组织搜索，从而可同时搜索空间内的多个区域，并相互交流信息 .,7.1.5 遗传算法的研究内容和应用前景,算法的理论模型研究 优化求解方法的研究 学
4、习系统的遗传算法研究 新的进化模型 遗传算法的并行分布式处理 遗传算法的应用系统 演化硬件,7.2 基本遗传算法,7.2.1 编码表示,位串编码 二进制编码即是将原问题的解空间映射到位串空间 上，然后在位串空间上进行遗传操作。优点 算法易于用生物遗传理论来解释并使得遗传操作（如杂交、变异等）很容易实现 采用二进制编码时，算法处理的模式数最多 缺点相邻整数的二进制编码可能具有较大的Hamming距离 二进制编码时，一般要先给出求解的精度以确定串长 在求解高维优化问题时，二进制编码串将非常之长,7.2.1 编码表示,实数编码 对于问题的变量是实向量的情形，可以直接采用实进制进行编码。这样，便可直接
5、在解的表现型上进行遗传操作。从而便于引入与问题领域相关的启发信息以增加遗传算法的搜索能力。 有序串编码目标函数的值不仅与表示解的字符串中各字符的值有关，而且与其所在字符串的位置有关。这样的问题称为有序问题。 需要针对具体问题专门设计有效且能保证后代合法的遗传算子。这类编码方案较多地使用在组合优化问题之中。,7.2.1 编码表示,结构式编码 将问题的解表示树或图的形式的编码称为结构式编码。因为遗传算子是直接在解的表现型上进行操作，这样使得我们比较容易加入与领域有关的知识和一些启发式的信息。,7.2.2 适应性的度量,个体的适应值即是它繁殖的能力，它将直接关系到其后代的数量，在遗传算法中，适应函数
6、是用来区分群体中个体好坏的标准，是算法演化过程的驱动力，同时也是进行自然选择的唯一依据。 原始适应函数 原始适应函数是问题求解目标的直接表示，通常采用问题的目标函数作为个体的适应度量 。定义原始适应函数的方法可能不止一种，选择时要尽量反映问题本身整体特性，而不能只追求片面的目标 。,7.2.2 适应性的度量,标准适应函数适应值会出现两种情形，一是极小情形即原始适应值越小个体性能越好；另一种是极大化情形即原始适应值越大个体性能越好 。遗传算法中的某些选择策略则要求适应函数是非负的，而且适应值越大表明个体的性能越好。 对于极小化情形，标准适应值可定义为 ： 适应值的调节存在问题：过早收敛、停滞现象
7、 改变算法性能的方法之一是对适应值进行调节，即通过变换，改变原适应值的比例关系。,7.2.3 选择策略,不同的选择策略将导致不同的选择压力，即下一代中父代个体的复制数目的不同分配关系。 转盘式选择 转盘式选择是基于适应值比例的选择中比较重要的选择策略。 先计算个体的相对适应值 ，即根据选择概率 把一个圆盘分成N份 生成一个内的随机数 r，若 ，则选择个体 i,7.2.3 选择策略,基于排名的选择 首先根据个体 的适应值在群体中的排名来分配其选择概率 。根据这个概率使用转盘选择 线性排名选择 线性排名选择方法是按适应值大小从好到坏依次排列为 ，然后根据一个线性函数分配选择概率 。,7.2.3 选
8、择策略,非线性排名选择 首先按适应值从好到坏依次排列群体成员，并按非线性函数分配选择概率 。,7.2.4 遗传算子的设计,杂交算子 杂交运算是指对两个相互配对的染色体按某种方式相互交换其部分基因，从而形成两个新的个体。单点杂交 单点杂交又称为简单杂交，它是指在个体编码串中只随机设计一个杂交点，然后在该点相互交换两个配对个体的部分染色体。,7.2.4 遗传算子的设计,双点杂交与多点杂交双点杂交是指在个体编码串中设置了二个杂交点，然后再进行部分基因交换。,7.2.4 遗传算子的设计,均匀杂交均匀杂交是指两个配对个体每一个基因座上的基因都以相同的杂交概率进行交换，从而形成两个新的个体。均匀杂交实际上
9、可归属于多点杂交的范围 .算术杂交 算术杂交是由两个个体的线性组合而产生出两个新的个体。为了能够进行线性组合运算，算术杂交的操作对象一般是浮点数所表示的个体。,7.2.4 遗传算子的设计,变异算子 变异运算是指将个体染色体编码串中的某些基因座上的基因值用该基因座的其它等为基因来替换，从而形成一个新的个体。遗传算法中使用变异算子主要有以下两个目的：1）改善遗传算法的局部搜索能力。2）维持群体的多样性，防止出现早熟现象。,7.2.4 遗传算子的设计,基本位变异 对个体的每一个基因座，依变异概率 指定其为变异点。 对每一个指定的变异点，对其基因值做取反运算或用其他等位基因值来代替，从而产生出一个新的
10、个体。 均匀变异 依次指定个体编码串中的每个基因座为变异点。对每一个变异点，以变异概率 从对应基因的取值范围内取一随机数来替代原有基因值。,7.2.4 遗传算子的设计,非均匀变异 非均匀变异的具体操作过程与均匀变异相类似，但它重点搜索原个体附近的微小区域。,7.3 函数优化,优化技术是一种以数学为基础，用于求解各种工程问题优化解的应用技术 .最优化问题可分为函数优化问题和组合优化问题两大类，其中函数优化的对象是一定区间内的连续变量，而组合优化的对象则是解空间中的离散状态。所有的搜索、优化都是对目标函数的“函数”优化。近年来，遗传算法作为一种全新的优化方法，其巨大的潜力受到越来越多学者的重视。,
11、7.3.1 问题描述,全局最大化 : 对于 ，寻求点 ，都有全局最小化：对于 ，寻求点 ，都有不论待求解问题是求最大值还是求最小值问题，我们可将待求解的问题一律看成求解最大值问题。 转化方法如下：如果优化问题是就函数 的最小值，它等同与求函数 的最大值，其中 ，即,7.3.1 问题描述,目标函数 在其值域里只取正值，若为负，可通过加入某个正数 C 使之为正，即,7.3.2 种群的初始化,对于函数优化来说，在初始化过程中需在上、下限区间内产生随机数，并将这个随机数赋给变量 。,7.3.3 选择策略,在选择策略上，本例采用基于概率的轮转盘选择策略。计算出群体的总适应值 对每个个体 ，选择概率 ，显
12、然 。 每个个体 的累积概率 ，我们可得知 且 。,7.3.4 遗传算子,杂交算子 对新群体中的每个个体产生一个在0,1区间内产生随机浮点数；如果 ，随机地选择个体配对，然后进行杂交操作。若个体中有n个分量，在1,n区间中产生随机整数 pos，pos表示杂交点的位置。若两个个体分别为： 在pos点杂交后产生子代,7.3.4 遗传算子,算法的程序描述如下：,/在0,1区间产生随机数,/判断随机数是否小于杂交概率,/进行杂交操作,7.3.4 遗传算子,/杂交点，即第几个分量进行相互交换,/在n个分量中，随机确定第pos个分量,进行相互交换,/前pos个分量进行相互交换,7.3.4 遗传算子,变异算
13、子 变异就是以很小的概率 随机地改变群体中个体(染色体)的某些基因的值。具体算法的描述如下：,/在0,1区间产生随机数,/判断随机数是否小于变异概率,/为第i个个体的j变量进行变异操作,7.4 旅行商问题,7.4.1 旅行商问题的描述,已知n个城市之间的距离，现有一推销员必须访问这n个城市，并且每个城市只能访问一次，最后必须返回出发城市。如何安排他对这些城市的访问次序，可使其旅行路线的总长最短。旅行商问题可分为对称旅行商问题和非对称旅行商问题。 TSP问题求解的研究工作主要集中在以下几个方面：采用适当的表示方法表示个体的编码；设计可用的遗传算子，以爆出父代的特性避免新个体的不可行性；防止算法过
14、早的收敛。,7.4.2 个体的编码表示,TSP问题的个体编码表示方法大致可分为两大类：在巡回旅行路线所经过的城市序列；各城市在巡回旅行路线中的邻接关系。近邻表示 近邻表示方法将路径表示成n个城市的一个排列，若排列中的第i位为城市，当且仅当路径中从城市i所到达的下一个城市为j。 次序表示 表示方法为：先取城市集合C的顺序排列如C=（1 2 3 4 5 6 7 8 9）作为次序排列的一个参照点，然后按路径中城市处在C的位置确定表示串中的点，且每确定一个则从C中删除相应的城市。,7.4.2 个体的编码表示,路径表示路径表示可能是TSP问题最自然、最直接的表示方式。它直接采用城市在路径中的相对位置来进
15、行表示。例如，路径517862934直接表示成（5 1 7 8 6 2 9 3 4）,7.4.3 杂交算子,部分映射杂交 首先随机地在父体中选取两个杂交点，并交换相应的段，再根据该段内的城市确定部分映射。在每个父体上先填入无冲突的城市，而对有冲突的城市依照映射关系选择候选的城市，直到找到无冲突的城市填入，按此方法获得了杂交后的两个后代。 次序杂交首先随机地在父体中选择两个杂交点，再交换杂交段，其它位置根据保持父体中城市的相对次序来确定。,7.4.3 杂交算子,循环杂交 循环杂交的步骤如下：根据双亲相对应的城市位置设计出一个循环链；把一个双亲的已在循环上的城市复制到一个后代上；删去另一个双亲已在
16、循环链上的城市，剩下的城市组成一序列；将3）步的序列从左到右依次填满后代空缺的位置。,7.4.3 杂交算子,基于位置的杂交 步骤:从一个双亲上随机选取一些杂交点；将第一个双亲的这些杂交点复制到一个空字符串的相应位置，产生一个后代；删去第二个双亲上已有的城市，剩下的城市构成了一个新的序列；将3）步中所得到的新序列，从左到右依次插入到后代空缺的位置上,7.4.4 变异算子,倒置变异 利用简单的倒置操作来进行变异。即首先在父体中随机地选择两个截断点，然后将该两点内的子串中的城市进行反序操作。 插入变异插入算子就是随机选择一个城市，并将它插入到一个随机位置中去。移位变异 移位算子是选择一个子路径巡回，然后把它插入一个随机的位置,7.4.4 变异算子,互换变异互换变异也被称作基于次序的变异（order-based mutation），操作方法是：随机的选择两个城市，并交换其所处的位置。 基于位置的变异 基于位置的变异首先随机地选择两个城市，然后将第二个放在第一个之前。 打乱变异 这种变异是随机选择一条子路径，打乱其次序，再重新插回原位置。,
