遗传算法实验报告

遗传算法实验报告 专业 自动化 姓名 张俊峰 学号 13351067 摘要摘要 遗传算法 是基于达尔文进化理论发展起来的一种应用广泛 高效的随机搜索与优化方法 本实验利用遗传算法来实现求函数最 大值的优化问题 其中的步骤包括初始化群体 个体评价 选择运 算 交叉运算 变异运算 终止条件判断 该算法具有覆盖面大 减少进入局部最优解的风险 自主性等特点 此外 遗传算法不是 采用确定性原则而是采用概率的变迁规则来指导搜索方向 具有动 态自适应的优点 关键词 串集 最优化评估 迭代 变异 一 实验目的一 实验目的 熟悉和掌握遗传算法的运行机制和求解的基本方法 遗传算法是一种基于空间搜索的算法 它通过自然选择 遗传 变异等操 作以及达尔文的适者生存的理论 模拟自然进化过程来寻找所求问题的答案 其求解过程是个最优化的过程 一般遗传算法的主要步骤如下 1 随机产生一个确定长度的特征字符串组成的初始种群 2 对该字符春种群迭代地执行下面的步骤 a 和步骤 b 直到满足停止准 则为止 a 计算种群中每个个体字符串的适应值 b 应用复制 交叉和变异等遗传算子产生下一代种群 3 把在后代中表现的最好的个体字符串指定为遗传算法的执行结果 即 为问题的一 个解 二 实验要求二 实验要求 已知函数 y f x1 x2 x3 x4 1 x12 x22 x32 x42 1 其中 5 x1 x2 x3 x4 5 用遗传算法求 y 的最大值 三 实验环境三 实验环境 操作系统 Microsoft Windows 7 软件 Microsoft Visual studio 2010 四 实验原理与步骤四 实验原理与步骤 1 遗传算法的思想 生物的进化是以集团为主体的 与此相对应 遗传算法的运算对象是由 M 个 个体所组成的集合 称为群体 与生物一代一代的自然进化过程相类似 遗传 算法的运算过程也是一个反复迭代过程 第 t 代群体极为 P t 进过一代遗 传和进化后 得到第 t 1 代群体 他们也是由多个个体组成的集合 记做 P t 1 这个群体不断地经过遗传和进化操作 并且每次都按照有优胜劣汰的 规则将适应度较高的个体更多地遗传到下一代 这样最终在群体中将会得到一 个优良的个体 X 它所对应的表现性 X 将达到或接近于问题的最优解 2 算法实现步骤 产生初始种群 产生初始种群的方法通常有两种 一种是完全随机的方 法产生的 适合于对问题的解无任何先验知识的情况 另一种是将某些先验知 识转变为必须满足的一组要求 然后在满足这些要求的解中再随机地选择样本 t 0 随机产生 n 个个体形成一个初始群体 P t 该群体代表优化问题的一些 可能解的集合 适应度评价函数 按编码规则 将群体 P t 中的每一个个体的基因码 所对应的自变量取值代入目标函数 算出其函数值 f i 1 2 n f 越大 表 示该个体有较高的适应度 更适合于 f 所定义的生存环境 适应度 f 为群体进 化提供了依据 选择 按一定概率从群体 P t 中选出 m 个个体 作为双亲用于繁殖后 代 产生新的个体加入下一个群体 P t 1 中 此处选用轮盘算法 也就是比 例选择算法 个体被选择的概率与其适应度成正比 交叉 重组 对于选中的用于繁殖的每一个个体 选择一种交叉方法 产生新的个体 此处采取生成随机数决定交叉的个体与交叉的位置 变异 以一定的概率 Pm 从群体 P t 1 中随机选择若干个个体 对于选 中的个体随机选择某个位置 进行变异 对产生新一代的群体返回步骤 再进行评价 交叉 变异如此循环往复 使群体中个体的适应度和平均适应度不断提高 直至最优个体的适应度达到某 一限值或最优个体的适应度和群体的平均适应度不再提高 则迭代过程收敛 算法结束 五 实验结果五 实验结果 实验结果的显示取决于判断算法终止的条件 这里可以有两种选择 1 在 程序中设定迭代的次数 2 在程序中设定适应值 本实验是在程序中实验者输 入需要迭代的次数来判断程序终结的 六 实验小结六 实验小结 在实验过程中 我觉得发现算子的选择对实验结果有一定程度的影响 所以 除了采用 PPT 上的算子选取外 也同样尝试了其他的算子选择方法 1 选择算子 排序选择方法 基于个体按适应度大小的排序来分配个体被选中的 概率 这种算法与轮盘算法的思路差不多 保存最佳个体策略 由于选择 交配 变异等操作的随机性 当代 最优秀的个体可能会被破坏 所以可以采用保存当代最优秀的个体 参与到下 一代的选择过程中 不过总的来说 轮盘算法还是选取选择算子最有效 最常用的算法 2 交叉算子 单点交叉 是指在个体编码串中随机设置一个交叉点 在该店交换配 对的两条染色体上的基因 两点交叉与多点交叉 在选择交叉算子的过程中 单点交叉是最简单 的方法 又称简单交叉 两点甚至多点交叉 是交配两点之间的染色体 比单 点交叉的适应性更高 不过程序略复杂 本实验采用的是均匀交叉 在选定位置后每一位基因都以相同的概率进行 交叉 附上实验代码 visual studio 2010 环境下运行 include include include include using namespace std int main srand time 0 double arr 5 4 初始化 cout 初始化 endl for int i 0 i 5 i cout C i for int j 0 j 4 j arr i j 5000 rand 100000 0 0001 cout setiosflags ios left setw 8 arr i j cout endl double result 5 double best result double result1 5 适应值计算 for int i 0 i 5 i double sum 0 for int j 0 j 4 j sum arr i j arr i j result i 1 sum 1 for int i 0 i 5 i result1 i result i sort result1 result1 5 best result result1 4 cout 初始化后进行适应值计算 最大值 best result best result endl int n cout n int test num 1 double test result while test num n cout 第 test num 次迭代 endl double sum result 0 double pecentage 5 选择 for int i 0 i 5 i sum result result i for int i 0 i 5 i pecentage i result i sum result double a double arr1 5 4 for int i 0 i 5 i for int j 0 j 5 j arr1 i j arr i j for int i 0 i 5 i a rand 100 0 01 if a pecentage 0 for int j 0 jpecentage 0 j pecentage 0 pecentage 1 j pecentage 0 pecentage 1 pecentage 2 j pecentage 0 pecentage 1 pecentage 2 pecentage 3 j 4 j arr i j arr1 4 j double mating pecentage 0 88 double mating 5 int num double tend 4 0 交配 for int i 0 i 5 i mating i rand 100 0 01 for int i 0 i 5 i if mating i 0 88 for int k i 1 k 5 k if mating k 0 88 for int l num 1 l 4 l tend l arr i l for int m num 1 m 4 m arr i m arr k m arr k m tend m mating k 1 break double variation 5 4 变异 for int i 0 i 5 i for int j 0 j 4 j variation i j rand 100 0 01 for int i 0 i 5 i for int j 0 j 4 j if variation i j 0 1 arr i j 5000 rand 10000 0 0001 cout 新群体 endl for int i 0 i 5 i for int j 0 j 4 j cout setiosflags ios left setw 8 arr i j cout endl for int i 0 i 5 i