单亲遗传算法理方法和应用.pptVIP

单亲遗传算法理论、方法及应用 本人对单亲遗传算法的主要研究工作 提出了亲单遗传算法,包括单亲遗传算法的基本概念和基 本理论。 研究了单亲遗传算法的运行机理,认为单亲遗传算法具有 与传统遗传算法类似的进化机制。 研究了单亲遗传算法的全局收敛性,指出含最优保特操作 的单亲遗传算法是全局收敛的 ·研究了单亲遗传算法图式定理,基于图式定理研究了单亲 遗传算法的隐含并行性。 研究了单亲遗传算法的计算效率,提出了提高单亲遗传算 法计算效率的措施。 ·研究了单亲遗传算法在旅行商问题、模式聚类问题、生产 调度问题和电力系统机组优化组合问题等方面的应用 单亲遗传算法的描述 单亲遗传算法的计算步骤 单亲遗传算法的编码方式 单亲遗传算法的遗传算子 单亲遗传算法的个体评价 单亲遗传算法的选择方式 单亲遗传算法的特点 单亲遗传算法的描述 单亲遗传算法取消了传统遗传算法的交 叉算子,全部遗传操作都只在一个个体 上进行。 单亲遗传算法不能完全取代传统遗传算 法,只有在传统遗传算法的交叉算子作 用效果不好时才使用单亲遗传算法 按照目前对单亲遗传算法的研究进展, 主要是以下两方面问题适合使用单亲遗 传算法:一是组合优化问题;另一是有 约束的复杂工程优化问题。 单亲遗传算法的计算步骤 第一种计算步骤: · Stepl:编码,根据所求解的具体问题确定一种编码方式, 组合优化问题采取序号编码方式;有约束的复杂工程优化问 题采取实数编码方式 Step2:确定个体的评价函数,即适应度函数。 ·Step3:产生初始群体。 Step4:评价初始群体中的各个个体 · Step5:繁殖新个体。对上一代群体中的个体进行遗传操作, 产生新个体。 Step6:评价新个体。若满足停机条件则停机,否则转下一 步 Step7:选择下一代群体。从上一代群体中的个体和本次遗 传操作所产生的新个体中选择N(N为群体规模)个个体构 成下一代群体,转Step5 单亲遗传算法的计算步骤 第二种计算步骤 Step1:编码,根据所求解的具体问题确定一种编码方式。 ·Step2:确定个体的评价函数,即适应度函数 Step3:产生初始群体 Step4:评价群体中的各个个体。 ·Step5:选择下一代群体。从上一代群体的个体中按某 种选择策略选择N(N为群体规模)个个体构成下一代 群体。若满足停机条件则停机,否则转下一步。 Step6:繁殖新个体。对上一代群体中的个体进行遗传 操作,产生新个体,转Step4 单亲遗传算法的编码方式 遗传算法的编码方式有非序号编码和序号编码 两大类。非序号编码方式又有二进制编码(又 称二值编码)和浮点编码(又称实数编码)等。 单亲遗传算法的编码方式主要是序号编码和实 数编码。求解组合优化问题时采取序号编码方 式;求解有约束的复杂工程优化问题时采取实 数编码方式。 序号编码方式: 序号编码方式所形成的染色体是一有序符号串, 其中的各个字符分别代表一个事物序号,每条染色 体分别代表所求解问题的一个解,即代表一种组合 方式 对于序号编码方式,在不改变事物序号排列顺 序的条件下,染色体中某一确定位置上的基因可能 取值的全体称为同序基因集,用G表示。同序基因 集中元素的个数称为同序基因数,用g表示。 序号编码方式举例: 对于10个城市的旅行商问题: (1)将10个城市分别编号为1、2、3、4、5、6 7、8、9、10 (2)以城市序号作为基因,各基因在染色体中 的排列顺序即为商人的旅行顺序。如有染色体3、2 1、4、10、6、10、8、9、5,表示商人从3号城市 出发,先到2号城市,再到1号城市,∴,最后到 达5号城市,并返回3号城市。 实数编码方式: 实数编码方式所形成的染色体是一实数串, 其中每个实数项为一个问题参数的取值,可以把 个实数项当作一个基因参与遗传操作,也可以 把实数项中的各个数值字符当作一个基因参与遗 传操作。单亲遗传算法一般把一个实数项当作 个基因参与遗传操作。在用遗传算法解决复杂工 程优化问题时,个体的编码方式宜用一个参数 对应一个基因的实数编码方式,这样可以压缩染 色体串长,且无需解码