遗传算法及几个例子

遗传算法，简称GA，它是一种模仿自然界生物进化过程的随机搜索方法，具有并行处理、自适应调整等特点，广泛应用于各种复杂问题的求解。

遗传算法是多学科相互结合与渗透的产物。

目前它已发展成一种自组织、自适应的多学科技术。

对于各式各样的问题kaiyun.ccm，研究者们参考了自然界生物遗传与演化的规律，从而创立了多种编码策略，用以展现问题的潜在解决方案，并在此基础上，他们成功研发出众多适应不同情境的生物遗传特性。

通过采用多样化的编码策略以及各式各样的遗传操作手段，便形成了众多各具特色的遗传算法。

这些遗传算法均具备一个共性，即通过模拟生物在遗传与进化过程中的选择、交配以及变异机制，来执行对最佳解的自适应搜寻流程。

鉴于这一共性，研究者们提炼出了最基础的遗传算法，即所谓的“基本遗传算法”。

基本遗传算法只使用选择、交叉、变异三种基本遗传操作。

遗传操作的过程也比较简单、容易理解。

同时，基本遗传算法也是其他一些遗传算法的基础与雏形。

在运用遗传算法解决编码问题时，并非直接对问题的实际决策变量实施操作，而是针对代表可行解的个体编码进行操作。此过程持续进行，不断筛选出适应度较高的个体，并在群体中扩大其数量，最终目的是找到问题的最优解或接近最优解。

因此，有必要构建问题可行解的具体表述与遗传算法中染色体位串结构之间的关联。

在遗传算法领域，将某个问题的有效解决方案从其原始解域映射至遗传算法能够进行搜索的特定域内的过程，被称作编码技术。

相反，个体将搜索空间的基因型转化为解空间的表现型的方式，我们称之为解码策略。

编码是应用遗传算法是需要解决的首要问题，也是一个关键步骤。

迄今为止人们已经设计出了许多种不同的编码方法。

基本遗传算法采用的是由二进制数字0和1构成的符号集合｛0，1｝，这表明问题空间中的参数可以通过字符集｛0，1｝构建的染色体位串来进行表示。

个体染色体所携带的数字数量，记作L，这一数值被定义为染色体的长度，亦即符号串的长度。

通常情况下，染色体的长度L是一个确定的数值，例如，当X的表示为10011100100011010100时，这代表了一个特定的个体，而该个体的染色体长度L等于20。

二进制编码符号串的长度与问题所要求的求解精度有关。

若设定某一参数的取值区间，我们采用长度为L的二进制编码序列来表征该参数，这样能够生成L^2种独特的编码方式。当参数与编码的对应关系为00000000000……00000000对应0，a00000000000……00000001对应1，a+δ……111111111111……11111111对应L^2-1即b时，二进制编码的精度可表示为Lab/δ。假设某个个体的编码为kl k k k a a a x，其中21=，那么相应的解码公式可以表示为∑(L/j)^(k_j)(a_j/x)^(L-k_j)。以x属于某个区间为例，若用长度为10的二进制编码来表示该参数，则编码序列x = 0010101111代表一个个体，其对应的参数值为x = 175。这种编码方式的精度为1。相较于其他编码方法，二进制编码的优势在于编码和解码过程简便易行，交叉遗传操作易于实现，且便于对算法进行理论上的分析。

在遗传算法中，个体适应度函数会依据个体适应度的高低来决定该个体在选优过程中被采纳的可能性。

个体适应力越强，其在后代中遗传的机会就越高；相反，若个体适应力较弱，其在后代中遗传的机会则相对较低。

基本遗传算法通过实施比例选择这一操作步骤，来判定群体中的各个成员是否有机会被遗传至下一代群体。

为确保准确估算各类情境下各独立实体的抉择几率开元棋官方正版下载，必须确保所有实体的适应性指标非负，即只能为正或等于零，绝不允许出现负值。

因此，针对各类问题，我们需事先明确目标函数值与个体适应度之间的映射规则，尤其是需事先设定当目标函数值为负数时的应对策略。

在解决优化问题时，若需最大化目标函数，我们通常面临的问题可以表述为：在定义域D内，最大化函数f(x)。对于需要最小化目标函数的优化问题，从理论上讲，我们只需对目标函数取负，便可将其转化为寻找最大值的问题，即求min(-max(f(x)))。然而，当优化目标为求函数最大值且目标函数始终为正值时，可以直接将个体的适应度函数F(x)等同于目标函数f(x)，即F(x) = f(x)。但在实际中，目标函数可能包含正值和负值，优化目标既可以是求最大值也可以是求最小值，上述方法并不能确保在所有情况下个体的适应度值都保持非负。因此，有必要探索一种通用的、有效的转换关系，以确保从目标函数值到适应度函数值的转换始终保证适应度值为非负。

为了满足适应度取负值的需求，基本遗传算法通常采取以下方式将目标函数值f(x)转换为个体的适应度F(x)：在寻求目标函数最大值的优化问题中，转换策略是先取f(x)的负值，然后加上一个最小值，若f(x)的负值大于该最小值，则F(x)等于0；若f(x)的负值小于或等于该最小值，则F(x)等于该最小值。其中，min(C)是一个相对较小的适当数值，它可能是一个预先设定的较小数，也可能是进化到当前代为止的最小目标函数值，还可能是当前代或最近几代群体中的最小目标函数值。

基本遗传操作方法之一是比例选择，这种方法亦称作复制，其核心在于对个体适应度进行评估后进行选择。

该功能旨在从现有群体中挑选出若干较为优秀的个体，并将这些优秀基因传承至下一代群体之中。

基本遗传算法中运用了比例选择机制，这种选择机制意味着，在选优过程中，每个个体被挑选的机会与其适应性的高低直接相关。

（2）单点交叉。

单点交叉又称简单交叉，是遗传算法所使用的交叉操作方法。

（3）基本位变异。

基本位变异是进行最简单、最基础的变异操作，同时它也是基本遗传算法中常用的变异策略。

在基本遗传算法中，个体通常以二进制编码的符号串形式存在。若某一基因原本的值为0，变异操作将使其变为1；相反，若基因值原本为1，变异操作则会将其转换为0。此外，在执行基本遗传算法的过程中，必须预先设定四个关键参数。

这些参数包括群体规模M、相互交叉的概率cp、变异的概率mp以及终止的代数T。其中，群体规模M指的是群体中个体的总数。

当M的数值较小，能够提升遗传算法的计算速度kaiyun全站app登录入口，然而却可能减少群体的遗传多样性，从而导致遗传算法过早收敛；相反，若M的数值较大，遗传算法的执行效率则会相应降低。

一般建议范围是20~100. （2） 交叉概率c p 。

交叉操作室中，遗传算法用于生成新个体的关键途径，因此，交叉概率通常应当设定得较高。

然而，若数值过大，便会损害群体协作的优质形态，对进化计算带来负面影响；反之，若数值过小，新个体的生成速度便会过于缓慢。

通常推荐的数值区间为0.4至1.0，此外，还需考虑变异概率m p。

当变异概率m p 较高时，虽然可以生成大量新个体，但同时也可能损害众多优良模式，导致遗传算法的表现接近随机搜索算法；反之，若变异概率m p 较低，变异操作在生成新个体和防止过早收敛方面的效果就会较弱。

通常推荐的数值区间为0.001至0.1。（4）代数T的终止条件是遗传算法运行结束的一个参数，该参数设定了算法在达到既定的进化代数后停止，并将此时群体中表现最佳的个体作为问题的最佳解输出。

通常推荐的数值区间为100至1000。至于遗传算法的结束标准，可以通过特定的评估标准来确定，一旦判断出种群已经达到成熟状态且不再显现进一步演化的迹象，便可以停止算法的执行流程。

若多代个体间的平均适应性变化幅度低于一个极其微小的界限；又或者群体内所有成员的适应性差异的平方和小于一个极小的界限。

这四个参数对遗传算法的搜索效果及效率产生了一定影响，目前尚无明确的理论依据来指导它们在遗传算法实际应用中的合理选取。在实际应用中，通常需要通过多次尝试计算，才能确定这些参数的合理取值范围或具体大小。

基本遗传算法是一种迭代式方法，它借鉴了生物在自然环境中遗传与进化的原理，通过不断对群体实施选择、交叉和变异等操作，最终能够找到问题的最佳解或接近最佳解的解法。

算法的核心理念虽不复杂，却蕴含着实用价值，能有效应对复杂系统中的优化计算挑战。

遗传算法的实施过程主要包括以下环节；该算法构建了一个通用的求解复杂系统优化问题的模型，其特点是不受问题领域和类型的影响。

对于需要改进计算效率的实际应用问题，通常可以依照以下步骤来设计用于求解该问题的遗传算法。

首先，构建一个优化模型，这包括明确目标函数、识别决策变量、设定各类约束条件，并采用数学表述或量化技术来描述这些条件。

在第二步中，需明确用于生成可行解的染色体编码策略，这包括确定个体的基因型x以及遗传算法的搜索范围。

第三步，需明确解码的具体方法，这包括确立从个体基因型x至个体表现型x之间的对应关系或转换途径。

第四步，需明确个体适应度量化的评估手段，这包括确立从目标函数的值\(x f\)到个体适应度\(x F\)之间的转换法则。

第五步，我们需要制定遗传操作的具体策略，这包括明确选择运算、交叉运算以及变异运算等各项操作的具体实施办法。

第六步，需明确遗传算法的运行参数，具体包括遗传算法的M、T、cp、mp等关键参数的设定。

从上述构建过程我们可以观察到，在构建遗传算法时，必须关注两个核心问题：一是可行解的编码策略，二是遗传操作的具体设计。这两个问题不仅是遗传算法构建过程中的关键环节，也是算法设计中的核心步骤。

解决各种优化问题时，必须采用相应的编码策略和遗传操作技术，这些方法与待解问题的特性紧密相连，因此，对问题本身的理解深度直接影响到遗传算法能否成功应用。

求解该规划问题，目标是最大化函数f，其表达式为x1*x2*x3*x4，同时满足约束条件x1属于[7,2,1,01]，x2属于[7,2,1,02]。主要运算步骤详见表7-3。

个体编码是遗传算法运作的核心，其处理的对象为个体的符号序列。因此，变量1x和2x，作为基本遗传算法的构成要素，需被转换成相应的符号串形式。

在例题中，1x和2x的取值范围是0到7的整数，它们各自可以用三位无符号二进制数来表示。当这两个数被连接起来时，它们共同构成了一个六位的无符号二进制数，这个数即为个体的基因型，代表了可行的解法。

基因型x等于101110所对应的表现型即为x等于（5，6）T。

个体的表现型与基因型x之间能够通过编码与解码的方式进行相互转化。

（2）初始群体的产生。

遗传算法涉及对群体进行一系列模拟遗传过程，为此，必须构建一组代表初始搜索位置的初始群体数据。

在本例中，我们设定群体规模M为4，这意味着该群体由4个独立的个体构成，而这些个体均能通过随机的方式生成。

一个随机产生的初始群体如表7-3中第2栏所示。

（3）适应度计算。

在本例中，目标函数始终呈现非负状态，其优化目标在于寻求函数的最大值，因此我们可以直接将目标函数的数值作为个体适应度的衡量标准，即通过()()F x f x =来确定。

为计算函数的目标值，需先对个体基因型x 进行解码。

表7-3的第3、第4列呈现了初始群体中各成员的解码成效，第5列则列出了每位成员对应的目标函数数值，这同样反映了其适应度。此外，第5列还包含了群体(4)所执行的选择操作。该操作流程包括：首先计算群体内所有个体适应度的总和if∑，以及每个个体的相对适应度/i if f ∑，具体数值可参考表7-3的第5、第6列。

表7-3中第7、8栏表示随机产生的选择结果。

（5）交叉操作。

在本例中，我们采用了单点交叉技术，并且设定了交叉概率c p为1.00。