进化计算

2024-07-14 19:19| 来源: 网络整理| 查看: 265

进化计算——求解优化问题

文章目录一、优化问题是什么？二、优化问题分类1.依据目标数量分类2.依据变量类型分类3.依据约束条件分类三、优化问题的数学模型四、最优化方法1.两者对比-求解步骤2.两者对比-优缺点五、生物学遗传进化观点进化计算的一般步骤：六、遗传算法（GA）（重点）1.遗传算法基本原理几个概念说明： 2. 遗传算法的基本结构3.遗传算法与传统优化方法比较：七、用遗传算法求解问题（重点）1.编码（染色体的表示）表现型空间与基因型空间编码注意可行性和合法性编码的评价编码方式（分类） 2. 种群初始化

一、优化问题是什么？

我们开车上班，怎样选择路线才能最快的到达单位？

旅游如何选择航班和宾馆才能即省钱又参观更多的景点？

现实世界中，优化问题与我们的衣、食、住、行息息相关，并广泛存在于科学研究、工程实践以及经济管理等众多领域中。

优化问题是指在满足一定条件下，在众多方案或者参数值中寻找最优方案或参数值，使得某个或多个优化指标达到最优（最大值或最小值）。

二、优化问题分类 1.依据目标数量分类

单目标优化问题（例如最短路程）：单峰优化问题——一个极值多峰优化问题——多个局部极值

多目标优化问题（例如路程最短且用时最少）：二、三维多目标优化问题——多个目标之间会发生冲突高维多目标优化问题——优化难度急剧增加，是优化领域的研究难点和热点在这里插入图片描述

2.依据变量类型分类连续变量——函数优化问题离散变量——组合优化问题

组合优化问题例如：旅行商问题、背包问题、聚类问题、路由问题

3.依据约束条件分类无约束优化有约束优化

有约束优化：约束条件，使变量空间分成可行域和不可行域

三、优化问题的数学模型

通过一个求函数最大值的优化问题，给出数学模型。模型有三要素：目标函数，约束条件，决策变量

在这里插入图片描述

四、最优化方法传统方法：牛顿法、共轭梯度法等进化算法：对目标函数有要求；按照固定的搜索方式来寻求最优解 1.两者对比-求解步骤

在这里插入图片描述

2.两者对比-优缺点

在这里插入图片描述

五、生物学遗传进化观点

生物的所有遗传信息都包含在其染色体中，染色体决定了生物的性状。

染色体是由基因及其有规律的排列所构成的，生物的繁殖过程由基因的复制过程来完成，遗传和进化都发生在基因上。

通过同源染色体之间的交叉或染色体的变异会产生新的物种，使生物呈现新的性状。

对环境适应性好的基因或染色体经常比适应性差的基因或染色体有更多的机会遗传到下一代。

进化计算的一般步骤：

（1）随机选定一组初始解（2）评价当前解的性能（3）若当前解满足要求或者进化过程达到一定代数，计算结束（4）从当前解选择一定数量的解作为基因操作对象（5）对所选择的解进行基因操作(如交叉，变异等)，得到新解，转到第2步。

分支： Genetic Algorithms (GA), Evolution Strategies (进化策略)， Evolutionary Programming (进化规划) 六、遗传算法（GA）（重点）

遗传算法是进化计算的一个分支。是一种模拟自然界生物进化过程的随机搜索算法。它最早由美国密歇根大学教授 Holland提出，现在已经广泛应用于各种工程领域的优化问题之中。

1.遗传算法基本原理种群：随机选择的一组可行解（N个）染色体：可行解的编码表示，即“位串”基因：位串中的任一一位适应能力：适应值，由适应度函数计算交叉、变异：交叉算子、变异算子进化结束：算法的终止条件几个概念说明：

编码：在遗传算法中，不是直接对决策变量的值来进行操作，而是对决策变量进行某种形式的编码

交叉：编码的交叉重组，类似于染色体的交叉重组。

变异：编码按小概率扰动产生的变化，类似于基因的突变。

选择：通过适应度的计算，选择好的个体，淘汰不合理的个体。类似于自然界的物竞天择，优胜劣汰.

最优解：末代种群中得到的最优个体经过解码

2. 遗传算法的基本结构

在这里插入图片描述

伪代码：

3.遗传算法与传统优化方法比较：

在这里插入图片描述全局探索用在算法开始阶段，扩大搜索范围；局部开发用在算法结束时，提高精度。

遗传算法是结合上述两种搜索能力的算法，对深度搜索和广度搜索进行平衡。

在这里插入图片描述

七、用遗传算法求解问题（重点）

用遗传算法求解问题需要解决以下五个问题：

编码：A genetic representation群体初始化：an initial population个体评价：An evaluation function ，fitness遗传算子：Genetic operators (selection, crossover, mutation)参数选择：Parameter values (population size, probabilities of applying genetic operators, etc.) 1.编码（染色体的表示）

在这里插入图片描述