遗传算法读书报告(共8页).docx

《遗传算法读书报告(共8页).docx》由会员分享，可在线阅读，更多相关《遗传算法读书报告(共8页).docx（8页珍藏版）》请在淘文阁 - 分享文档赚钱的网站上搜索。

1、精选优质文档-倾情为你奉上遗传算法读书报告遗传算法是基于生物进化思想的一种优化方法，因此遗传算法与数学规划类优化方法在原理、实现手段等方面有着明显的差别。一、基本概念及遗传算法简介1、基本概念（1）个体个体是遗传算法中用来模拟生物染色体的一定数目的二进制位串，该二进制位串用来表示优化问题的设计点。（2）群体群体是由一定数量的个体组成的集合。（3）基因模式基因模式是指二进制位串表示的个体中，某一或某些位置上具有相似性的个体组成的集合。（4）模式阶次模式阶次是指基因模式中包含相似位置的数目。（5）模式定义长度模式定义长度是基因模式中相似位间相距的最大距离。（6）适应度适应度是以数值方式来描述个体优

2、劣程度的指标。（7）平均适应度平均适应度是若干个个体的适应度值的算是平均值。（8）繁殖繁殖是由一代群体繁衍产生另外一代群体的方式总称。（9）选择选择算子是指在上一代群体中按照某些指标挑选参与繁殖下一代群体的一定数量的个体。（10）杂交杂交算子是指对于优选后的父代个体进行基因模式的重组而产生后代个体的繁衍机制。（11）一点杂交一点杂交是指在代表个体的二进制位串中选择一截断位，将截断位前后的二进制位串互相交换产生后代个体的方式。（12）两点杂交两点杂交是指在代表个体的二进制位串中选择两个截断位，将两个截断位间的二进制位串互相交换产生后代个体的方式。（13）突变突变算子是指模拟生物在自然的遗传进化环

3、境中由于各种偶然因素引起的基因模式突然改变的个体繁殖方式。2、遗传算法简介1）遗传算法主要包括以下内容：（1）构造适应度函数（2）群体的初始化（3）后代群体的繁殖（4）群体进化收敛判断（5）最优个体转化为优化解图1 遗传算法流程图在优化设计中，设计变量、目标函数、约束条件是优化模型的三个要素。一般可以利用编码技术对设计变量进行编码，将设计变量转化为适合于群体进化的表达形式。对目标函数进行处理，使其蕴含于遗传算法的适应度函数。这样，在群体进化过程中适应度也就反映了优化模型的目标函数。当群体进化结束后，适应度值最大的个体对应的目标函数数值最小，该个体即对应优化模型的优化解。这样，优化模型可以利用遗

4、传算法来求解。2）利用遗传算法求解该优化问题的主要过程如下：（1）构造适应度函数取5位二进制数串，这样既满足了优化问题对于设计变量的约束，有实现了对设计变量的编码。（2）群体初始化值得注意的是，为方便手工计算，群体规模数取的很小，在实际计算的时候群体规模数应该选取较大值。（3）后代群体的繁殖在后代群体的繁殖过程中，一般要进行个体的选择、杂交、突变等。（4）群体进化收敛性判别给出适应度变化许可精度，计算前后两代群体平均适应度变化率，如平均适应度变化率小于许可精度，那么说明群体进化过程基本稳定、群体进化收敛，则可结束群体的进化过程；否则仍需继续群体的繁殖过程。 （5）最优个体转化为最优解在最后一代

5、群体中选择最优个体，对最优个体进行转化，就可得出优化问题的最优解和目标函数。二、遗传算法的基本原理1、适应度函数的建立适应度是遗传算法中描述个体性能的主要指标。一般的个体适应度值越大，个体的性能越好；反之，个体的适应度值越小，个体性能也越差。在遗传算法中，适应度的值是必须大于等于0的值。由于遗传算法是依据适应度的值对个体性优胜劣汰的，因此，将无约束化问题的目标函数与个体的适应度建立映射关系，即可在群体的进化过程中实现对优化问题目标函数的寻优。将目标函数转换为适应度函数，一般需要遵循如下两个基本原则。（1）适应度值必须大于等于0（2）优化过程中目标函数的变化方向（如向目标函数最大值或者是最小值变

6、化）应与群体进化过程中适应度函数变化方向一致。对于最小值优化问题，可通过下式来建立与目标函数存在映射关系的适应度函数。(2-1)式中：适应度函数C一个可调函数，其取值应该使适应度函数恒大于等于0最小值优化问题的目标函数。为确保适应度函数不小于0，一般常采用下式建立适应度函数。(2-2)式中：一个可调参数，可取目标函数理论上的最大值。2、设计变量与个体间的映射设计变量与个体之间的映射可以通过编码来实现。编码方法一般应遵循位串定义长度最短、模式阶次最高、模式数目最大等原则。常用的编码有两种方法，一种是二进制编码，另外一种是k进制编码。假设二进制编码的位数为t，k进制编码的位数为j，则t与j有如下的

7、关系：(2-3) 3、群体初始化群体的初始化一般包括如下内容。（1）确定群体数目m，群体规模数一般在50以上;（2）对优化问题的初始解进行编码，产生与初始解对应的个体；（3）通过随机方式产生n个l位二进制串作为初始群体的一个群体；（4）不断产生初始个体，直到初始群体中个体数目为m为止。4、群体繁殖（1）选择从上带群体中选择一定数量的个体，并将为参与下代群体繁殖的父代个体。选择个体的原则是使适应度大的个体被选择的几率大。常用的方法主要有轮盘选种法、RSIS选种法、线性比例模型法等。（2）产生后代个体杂交、突变等基本繁殖算子是依靠随机的方式来选取的。随机概率在0.6到0.8范围时利用杂交算子来产生

8、后代个体，随机概率在0.01到0.02范围时采用突变算子来产生后代个体，对大多数优化问题比较合适。利用选择的基本繁殖算子产生个体，直到产生的后代个体数目达到群体规模数。5、群体收敛判别群体进化收敛性可以通过各个代群体平均适应度变化率和最优个体适应度变化率等指标来判别。如果群体平均适应度变化率和最优个体适应度变化率小于许可精度，则可以认为群体进化处于稳定状态，群体进化基本收敛，可结束群体进化过程，否则继续群体的进化过程。6、输出最优解在群体中选择适应度值最大的个体，然后对最优个体进行转化，就可得到优化问题的最优解和目标函数值。对于约束优化问题，可先将约束优化问题转化为无约束优化问题，然后利用遗传

9、算法来求解。三、个体适应度值比例变换法在遗传算法中，有必要对个体的适应度值进行适当的调整。在对个体的适应度值进行调整的时候应该遵循不可以使得适应度值相差太大，又要使得个体之间保持一定的极差这一原则。通过对群体中各个个体的适应度值进行调整，可一直保持个体之间的竞争性。常用的对个体适应度值进行比例变换的方法有线性比例变换法、幂比例变换法、指数比例变换法等几种.1、线性比例变换法假设个体的适应度函数为f，经过线性比例变换之后个体的适应度函数为F，则适应度线性比例饿变换关系是为：(3-1)式中，系数a和b的选取应满足以下条件。（1）线性比例变换后个体的平均适应度值等于原来个体的平均适应度。（2）线性比

10、例变换后个体的最大适应度值应该是原来个体平均适应度值的一定的倍数，既满足以下关系式：(3-2)式中：线性比例变换后个体的最大适应度值；原个体平均适应度值；可调整参数，一般在1.2到2范围内选取。2、幂比例变换法幂比例变换法是由Gillies在1985年提出的一中比例变换法。利用幂比例变换法，可使得比例变换后的适应度值与原来的适应度值满足如下关系：(3-3)式中：幂比例变换后个体的适应度值；幂比例变换前的个体的适应度值；经验系数，随着问题的不同而变化，并在群体进化过程中可做适当的变化，对于机器视觉优化问题，一般取值为1.005。经过幂比例变换后，群体的进化效率不如线性比例变换法高。3、指数比例变

11、换法利用指数比例变换法，可使得比例变换后个体的适应度值与原来的适应度值满足如下的指数变换关系：(3-4)指数比例变换后个体的适应度值；指数比例变换前的个体的适应度值；经验系数。采用指数比例变换方法，可是的适应度较高的优良个体在有较多的被选择机会的同时，优良个体被选择的次数受到一定的限制，这样就可避免少数优良个体在几次进化之后控制整个群体繁殖的现象。采用指数比例变换法提高了群体中一部分个体的竞争能力。常用的交叉编码的方法：（1）在任意点进行交叉编码（2）在特定某位置进行交叉编码（3）在设计变量编码的局部为进行交叉，其他编码位置不变（4）将上述三种方法结合起来进行交叉编码。如以概率进行任意位置的交

12、叉编码，以概率进行特定位置的交叉编码，以概率进行局部位置的交叉编码，其中三者概率之和为1。四、遗传算法的其他繁殖算子1、置换位算子置换算子的具体内容为，在个体位串中任意选择两点，将两点间的位串进行颠倒，其余位串次序不变，即可以形成新的位串。个体经过置位与杂交操作后没能保留个体完整的基因模式，因此，对个体进行职位操作后，需要再进行杂交繁殖，主要有以下的方法：（1）对等杂交法 在对等杂交中，个体经过置为操作后基因模式的编号一致时才能进行杂交繁殖。（2）生存杂交法 在生存杂交中，个体经过置为操作后均可进行杂交繁殖。如杂交操作后获得的新个体中不包含原个体完整的基因模式，则取消该个体的“生存权”，放弃该

13、个体，否则保留该个体。（3）主从杂交法 在主从杂交法中，先对个体进行置为操作，然后将其中一个个体作为主要个体，依据主要个体中的基因模式顺序对另外一个个体的位串进行相应的调整，使得个体之间存在着对应关系，最后再进行杂交。依据不同的判别指标，主要个体的选取方法亦有不同的方法。常用的主要个体选取方法中选取依据是个体适应度值。2、部分匹配杂交算子1985年由Goldberg和Lingle解决了组合优化问题中的具有代表性的旅行推销商问题时，提出了部分匹配杂交算子。3、排序杂交算子排序杂交算子与部分匹配杂交算子相类似，排序杂交算子主要内容如下：（1）在个体中随机产生两个杂交点，确定个体的匹配段。（2）按照另外个体匹配段中的基因模式，将个体中相应的基因模式映射为空位串。（3）将匹配段的第一位作为个体位串的第一位，其后的位串作为个体的第二位，依次进行上述置为。（4）对第二个个体进行上述操作。（5）对两个个体的匹配段进行杂交。4、本地算子De Jong也提出了在遗传算法中实现共享机制的一种方法。在这种方法中，根据某类个体数目的多少，给出拥挤因子，在产生新个体时，放弃一个已存在的个体，被弃的个体可以按照下列方法选取。（1）从相似个体群中随机选取CF个个体。（2）对于选出的CF个个体与新产生的个体做相似度对比，将具有最高相似度的个体作为被放弃的个体。专心-专注-专业