CHC算法讲稿.pdfVIP

CHC 算法介绍 CHC 算法，一种改进的遗传算法，关于其基本理论和分析思想的介绍比较少， 因为是源于基本遗传算法，只是出于提高收敛速度及全局最优解的可靠度，并得 到适应度更高的子代等的目的，作了些许改进而已。下面我先介绍一下基本遗传 算法，然后在基本遗传算法的基础上对CHC 算法的基本思想、特点以及其优于基 本遗传算法的改进地方作一下说明。 一、基本遗传算法 遗传算法最早是由Holland 教授于 1975 年提出来的，是建立在自然选择和 自然遗传学机理基础上的迭代自适应概率有哪些信誉好的足球投注网站最优解的方法。它模拟自然界生物 进化过程，体现了优胜劣汰的自然选择的优化思想，其算法的鲁棒自适应性强， 与常用的优化方法相比，可以寻找到全局优化解。 1、遗传算法的基本原理 遗传算法GA 把问题的解表示成 “染色体”，在算法中也即是以二进制编码 的串。并且，在执行遗传算法之前，给出一群 “染色体”，也即是假设解。然后， 把这些假设解置于问题的 “环境”中，并按适者生存的原则（也就是通过适应度 函数给每个个体一个数值评价，淘汰低适应度的个体，选择高适应度的个体）， 从中选择出较适应环境的 “染色体”进行复制，再通过交叉，变异过程产生更适 应环境的新一代 “染色体”群。这样，一代一代地进化，最后就会收敛到最适应 环境的一个 “染色体”上，它就是问题的最优解。这就是遗传算法的基本原理。 2、遗传算法的实现步骤如下： 1 基因编码： ○ 用一定比特的二进制码对自变量进行编码形成基因码链(染色体) ，每一个码 链代表一个个体；也就是把一个问题的可行解从其解空间转换到遗传算法所能处 理的有哪些信誉好的足球投注网站空间的转换方法。 2 产生初始群体： ○ n 随机产生 个染色体以形成一个初始群体P(0) ，该群体代表优化问题的一些 可能解的集合。但是，一般来说，随机产生的初始群体素质都很差，通常难以满 足解的要求。遗传算法的任务就是要从这些群体出发，模拟生物进化过程，择优 汰劣，最后选择出优秀的群体和个体，满足优化的要求。 3 评价个体优劣： ○ 计算群体中每个个体的适应度值。不同的问题，适应性函数的定义方式也不 同。适应度越大，表明所对应的个体质量越好。 4 选择： ○ 选择是在群体中选择生命力强的个体产生新的群体的过程。 根据每个个体的适应度值大小选择，适应度较高的个体被遗传到下一代群体 的概率较大。这样使得群体中个体的适应度值接近最优解。选择是遗传算法的关 键，它体现了自然界中适者生存的思想。 2 5 杂交（交叉）操作： ○ 杂交是将两个不同染色体i 与j 之间的部分遗传因子进行互换 亲代 子代 i 染色体 01 杂交 0101100101 → j 染色体 1001100111 1001001111 杂交前的染色体称为亲代(父代或母代)，杂交后的染色体称为子代，上述染 色体i 与j 的杂交，将两者第3 - 7 的基因进行了互换，形成了新的染色体。通 过杂交，染色体之间进行了信息(遗传因子)的传递，或者说某些亲代的遗传因子 被子代继承。一般来讲，子代染色体不同于亲代，有可能形成优于亲代的染色体， 也可能形成适应度更差的染色体，但只要有优于亲代的染色体产生，通过优胜劣 汰、适者生存的自然选择竞争机制，寻找优化解的过程总是向前的。至于选择哪 两个染色体配对杂交及进行一段或多段遗传因子交换且交换的各遗传因子的起 止点位置等，则是随机确定的。 6 变异（突变）操作： ○ 对于二进制数串形式的染色体，是指遗传因子发生0 和1 之间的反转变化： 0101001101 突变 01 1 100 0 101 K 染色体 → 变异操作使染色体所代表的优化变量值可能发生了较大的变化，有望跳出局 部优化解，在更大的区域内有哪些信誉好的足球投注网站最优解，从而获得全局优化解，避免出现过早收 敛的问题。至于选哪