基于遗传算法的社区发现(3)
时间:2018-07-21 14:05 来源:毕业论文 作者:毕业论文 点击:次
等复杂网络系统问题的通用框架，所以它与问题具体领域并不特定相关联，对问题本身一无 所知，它需要的只是每个染色体进行评价与进化操作，使适用性高的个体比适应性低的个体 有更多的繁殖机会。已普遍的应用在智能学习、遗传编码、自主操作、人工生命、图像识别、 成组优化等科技领域，并在求解图形划分算法、背包题、TSP 系列、装箱系列等经典问题方 面已经取得了不少收获。 遗传算法解决一般性课题的框架是，把待研究课题所提供的数据接口转换成二进制或格 雷码（或其他进制码）即基因，染色体（基因型个体）由若干基因组成，一个染色体代实际 问题的一种解决方案，对若干染色体组成的种群进行遗传、交叉、变异三个遗传算法的迭代 操作，根据具体问题设定的能够衡量个体优劣的函数去评估个体生存能力值，依据达尔文适 者生存、优胜劣汰地自然选择理论，在潜在解的种群中逐代产生近最优的方案，通过全局并 行搜索来搜索当代群体中的最优个体，整体流程构成群体中染色体的变化，新染色体构成的 个体应比原来的染色体更适应生存，与人类在这几千来的进化过程类似。一般情况下，解的 质量越好的个体代表生存能力越强，所以如果求解最小化问题，则通过取反来转化成最大化 的问题。 2.2 遗传算法的主要优点（1）表示可行解的广泛性。比如：邻接矩阵、集合、树结构、任务序列等问题参数形式； （2）群体搜索特性。许多传统搜索方式都是点对点的单点搜索，对于存在多个峰值的搜 索空间，易局限于单峰极值点。而遗传算法是以整个群体为基础搜索点，因此多个峰值点均 能遍及，不容易导致局部最优； （3）不需要附加信息。遗传算法评价个体只需适应度函数。并且，遗传算法的适应度函 数无需连续可微，而且问题定义域可以随意转换设定。限制条件的减少大大扩展了算法的应 用范围。 （4）启发式随机搜索。采用概率变换来控制其搜索方向，概率是引导其搜索过程向更优 的解空间前进的手段。搜索方向明确，内在搜索并行进行。 2.3 遗传算法流程介绍 遗传算法通过选择、交叉和变异操作，对种群进行遗传进化，直至得到最优状态的个体。 选择操作实现适者生存原则，提高群体平均适应度值。交叉操作是群体产生新个体的主要方 法，它使种群中随机两个体按规则互换部分基因信息。变异对随机个体某部分基因以一定概 率进行改变，反映遗传算法的局部搜索能力。交叉与变异配合实现了在问题的所有求解空间 上的近似遍历。 以下为遗传算法基本流程： （1）基础数据形式编码成个体，并根据编码方式构造一个初始种群； （2）个体解码。它是将通过遗传算法所运算得到的基因型方法转变成所求问题的表现 型值，得出个体适应度值； （3）选择操作。根据适应度评估函数，选择初始群体中适应度值较好的部分个体构成 初代群体。在遗传算法中，个体的好坏程度是通过能够评定其目标值的函数来计算的。对于 求解不同的问题，个体生存能力评估函数的构造方式也有所不一样； （4）对初代群体进行交叉和变异操作，形成新一代群体； （5）循环运行2~4 步骤，当遗传算法运行到指定的代数或者已经寻找到全局最优解时， 遗传算法则停止相应的遗传操作和迭代过程。 2.3.1 编码与解码 编码（Coding）就是问题可行解的遗传表述形式，遗传算法运行需要的首要基本参数是 (责任编辑：qin) |