内容发布更新时间 : 2024/12/26 13:55:07星期一 下面是文章的全部内容请认真阅读。
青岛科技大学研究生学位论文
时对搜索空间中的多个解进行评估。这一特点使遗传算法具有较好的全局搜索性能，从而减少了陷入局部最优解的可能。
(3) 仅用适应度函数来指导搜索。以往很多的搜索方法都需要辅助信息才能正常工作，如梯度法需要有关导数的信息才能爬上当前的峰值点，这就要求目标函数可导。而遗传算法则不需要类似的辅助信息，为了有效的搜索越来越好的编码结构，它仅需要与该编码串有关的适应度函数即可。
(4) 内在启发式随机搜索特性。遗传算法不是采用确定性规则，而是采用概率的变迁规则来指导它的搜索方向。概率仅作为一种工具来引导其搜索过程朝着搜索空间的最优化的解区域移动。
(5) 遗传算法易于介入已有模型，具有可扩展性，易于同别的技术混合。本文正是遗传算法应用于计算机科学和管理科学的交叉学科——数据挖掘技术的一个典型例子。
3.4遗传算法的基本要素
遗传算法包含了如下5个基本要素：问题编码，初始群体的设定，适应度函数的设计，遗传操作设计，控制参数的设定。这5个要素构成了遗传算法的核心内容。
1．问题编码
编码机制是遗传算法的基础。通常遗传算法不直接处理问题空间的数据，而是将各种实际问题变换为与问题无关的串个体。目前遗传算法中最常用的是二进制编码，其次还有实数编码、字符编码、整数编码等多种编码方法。
2．初始群体的生成
遗传算法处理流程中，编码设计之后的任务是初始群体的设定，并以此为起点一代的进化直到按照某种进化终止准则终止，最常用的初始方法是无指导的随机初始化。
3．适应度函数(Fitness Function)的确定
在遗传算法中，按与个体适应度成正比的概率来决定当前群体中的每个个体遗传到下一代群体中的机会多少，一般希望适应值越大越好，且要求适应值非负。因此适应值函数的选取至关重要，它直接影响到算法的收敛速度及最终能否找到最优解。
适应度函数是根据目标函数确定的，针对不同种类的问题，目标函数有正有负，因此必须确定由目标函数值到适应度函数之间的映射规则，以适应上述的要求。
25
基于遗传算法的k-means聚类挖掘方法研究
4．遗传操作
遗传操作主要包括：选择、交叉、变异三个算子。关于每个算子的作用前面己提及了，此处不在赘述。这里主要说一下每种算子常用的方法。
(1) 选择算子
在适应度计算之后是实际的选择，选择的目的是为了从当前群体中选出优良的个体，使它们作为父代进行下一代繁殖。采用基于适应度的选择原则，适应度越强被选中概率越大，体现优胜劣汰进化机制。可以挑选以下的算法：
①赌轮选择法。该方法中个体被选中的概率与其适应度大小成正比。 ②最优保存策略。群体中适应度最高的个体不进行交叉变异，用它替换下一代种群中适应度最低的个体。
③锦标赛选择法。随机从种群中选取一定数目的个体，然后将适应度最高的个体遗传到下一代群体中。这个过程重复进行完成个体的选择。
④排序选择法。根据适应度对群体中个体排序，然后把事先设定的概率表分配给个体，作为各自的选择概率。这样，选择概率和适应度无关而仅与序号有关。
选择算子确定的好坏，直接影响遗传算法的计算结果。如果选择算子确定不当，会导致进化停滞不前或出现早熟问题。选择策略与编码方式无关。
(2)交叉算子
交叉算子是遗传算法中最主要的遗传操作，也是遗传算法区别于其他进化运算的重要特征。通过交叉操作可以产生新个体。遗传算法的有效性主要来自选择和交叉操作，尤其是交叉操作，它决定遗传算法的收敛性和全局搜索能力。
交叉算子的设计与实现与所研究的问题密切相关，一般要求它既不要破坏原个体的优良性，又能够产生出一些较好的新个体，而且，还要和编码设计一同考虑。目前适合于二进制编码的个体和浮点数编码的个体的变异算法主要有：单点交叉、两点交叉与多点交叉、均匀交叉、算术交叉。
(3) 变异算子
选择和交叉算子基本上完成了遗传算法的大部分搜索功能，变异操作只是对产生的新个体起辅助作用，但是它必不可少，因为变异操作决定了遗传算法的局部搜索能力。变异算子与交叉算子相互配合，共同完成对搜索空间的全局搜索和局部搜索，从而增加遗传算法找到接近最优解的能力。
目前适合于二进制编码的个体和浮点数编码的个体的变异算法主要有：基本位变异、均匀变异、非均匀变异、边界变异、高斯近似变异等等。
5．控制参数
控制参数主要有群体规模、迭代次数、交叉概率、变异概率等，对此基本的遗传算法都需要提前设定：
26
青岛科技大学研究生学位论文
N：群体大小，即群体中所含个体的数量，如果群体规模大，可提供大量模式，使遗传算法进行启发式搜索，防止早熟发生，但会降低效率；如果群体规模小，可提高速度，但却会降低效率。一般取为20～100。
T：遗传运算的终止进化代数，一般取为100～500。
Pc：交叉概率，它影响着交叉算子的使用频率，交叉率越高，可以越快地收敛到全局最优解，因此一般选择较大的交叉率。但如果交叉率太高，也可能导致过早收敛，而交叉率太低，可能导致搜索停滞不前，一般取为0.4～0.99。
Pm：变异概率，变异率控制着变异算子的使用频率，它的大小将影响群体的多样性及成熟前的收敛性能。变异率的选取一般受种群大小、染色体长度等因素影响，通常选取很小的值。但变异率太低可能使某基因值过早丢失、信息无法恢复；变异率太高，遗传算法可能会变成了随机搜索。一般取为0.0001～0.1。
这四个运行参数对遗传算法的求解结果和求解效率都有一定的影响，但目前尚无合理选择它们的理论依据。在实际应用中，常常需要经过多次实验后才确定参数或其范围。
3.5遗传算法的描述及流程
3.5.1 遗传算法的描述[47]
现在，我们引用上面的术语来描述遗传算法的基本思想。遗传算法首先将问题的每个可能的解按某种形式编码成个体，然后随机选取N个个体构成初始种群，再根据预定的适应度函数计算每个个体的适应值。选择适应值高的染色体作为父代，在通过交叉、变异，来产生一群新的更适应环境的个体，形成新的种群。这样一代一代不断繁殖、进化，最后收敛到一个个体上，该个体很有可能代表着问题的最优或次优解。
基本遗传算法的伪代码描述如下： Procedure SGA
{ Initialize P(0); /*初始化群体*/
t=0; /*t为进化代数计数器*/ While (t Evaluate fitness of P(t); /*计算第t代群体中个体适应度值*/ End for For i=1 to M do 27 基于遗传算法的k-means聚类挖掘方法研究 Select operation to P(t); /*进行选择操作 */ End for For i=1 to (M/2) do Crossover operation to P(t); /*进行交叉操作*/ End for For i=1 to M do Mutation operation to P(t); /*进行变异操作*/ End for For i=1 to M do P(t+1)=P(t); /*生成新的群体*/ End for t=t+1; end while } 3.5.2遗传算法的执行过程 根据上面遗传算法的思想，遗传算法的基本处理过程可描述如下： 输入参数：种群规模M、交叉概率Pc、变异概率Pm 。 (1) 编码：遗传算法在进行搜索之前先将解空间的解数据表示成遗传空间的基因型串结构数据，即从表现型映射到基因型X； (2) 初始化。随机选择N个初始点构成初始种群P(0)，设置进化代数计数器t=0，设置最大进化代数T； (3) 适应度评价。根据确定的适应度函数，计算群体P(t)中每个个体的适应值； (4) 选择。将选择算子作用于群体； (5) 交叉。将选择算子作用于群体； (6) 变异。将变异算子作用于群体； 种群经过选择、交叉、变异操作之后得到下一代种群P(t+1)。 (7) 终止条件判断。若t?T，则t?t?1，并转向(3)；若t?T，则以进化过程中所得到的具有最大适应度的个体作为最优解输出，终止运算。 具体的流程图如图3-1所示。 28 青岛科技大学研究生学位论文 实际问题编码成位串种群p(t)计算适应度值输出适应度最优个体是是否满足终止条件否选择操作交叉操作变异操作遗传算子t=t+1产生新一代种群p(t+1)图3-1遗传算法的流程图 Fig.3-1 The flow chart of genetic algorithms 3.6遗传算法的应用 遗传算法提供了一种求解复杂系统优化问题的通用框架，它不依赖于问题具体的领域，对问题的种类有很强的鲁棒性，所以广泛应用与许多学科。下面列出遗传算法一些主要的应用领域。 (1) 函数优化 函数优化是遗传算法的经典应用领域，也是对遗传算法进行性能评价的常用算例。可以用各种各样的函数来验证遗传算法的性能。对一些非线性、多模型、多目标的函数优化问题，使用遗传算法可得到较好的结果。 (2) 组合优化 随着问题规模的增大，组合优化问题的搜索空间也急剧扩大，有时在目前的 29