进化算法及其在数值计算中的应用.ppt

进化算法及其在数值计算中的应用,最优化问题：在满足一定的约束条件下，寻找一组参数值，使某些最优性度量得到满足，即使系统的某些性能指标达到最大或最小。最优化问题的应用涉及工业技术、社会、经济、管理等各个领域，具有重要意义。最优化问题的一般形式为：式中，称为目标函数，称为约束函数。极大极小的转换：,数学规划：在一些等式或不等式约束条件下，求一个目标函数的极大（或极小）的优化模型称为数学规划。根据有、无约束条件可以分为约束数学规划和无约束数学规划；根据目标函数 和约束函数 是否为线性函数，分为线性规划和非线性规划；根据问题中是否只有一个目标函数，分为单目标规划和多目标规划。很多非常重要的问题是线性的（或者用线性函数能够很好地近似表示），因此线性规划的研究具有重要意义。与非线性规划相比，线性规划的研究更加成熟。,进化算法及其在数值计算中的应用,在数学规划中，把满足所有约束条件的点 称为可行点（或可行解），所有可行点组成的点集称为可行域，记为 于是数学规划即为求，并且使得 在 上达到最大（或最小），把 称为最优点（最优解），称为最优值。,进化算法及其在数值计算中的应用,进化计算（Evolutionary Computation，EC）受生物进化论和遗传学等理论的启发，是一类模拟生物进化过程与机制，自组织、自适应的对问题进行求解的人工智能技术。进化计算的具体实现方法与形式称为进化算法（Evolutionary Algorithm，EA）。进化算法是一种具有“生成+检测”（generate-and-test）迭代过程的搜索算法，算法体现群体搜索和群体中个体之间信息交换两大策略，为每个个体提供了优化的机会，使得整个群体在优胜劣汰（survival of the fittest）的选择机制下保证进化的趋势。,进化算法及其在数值计算中的应用,进化算法采用编码的形式来表示复杂结构，并将每个编码称为一个个体（individual），算法维持一定数目的编码集合，称为种群或群体（population）。通过对群体中个体进行相应的操作，最终获得一些具有较高性能指标的个体。进化算法的研究始于20世纪60年代，Holland针对机器学习问题发展了遗传算法（genetic algorithm，GA），Fogel对于优化模型系统提出了进化规划（evolutionary programming，EP）Rechenberg和Schwefel对于数值优化问题提出了进化策略（evolutionary strategy，ES）。,进化算法及其在数值计算中的应用,遗传算法是一种宏观意义下的仿生算法，它模仿的机制是一切生命与智能的产生与进化过程。遗传算法通过模拟达尔文“优胜劣汰、适者生存”的原理，激励好的结构；通过模拟孟德尔遗传变异理论，在迭代过程中保持已有的结构，同时寻找更好的结构。适应度：遗传算法中使用适应度这个概念来度量群体中的每个个体在优化计算中可能达到或接近最优解的程度。适应度较高的个体遗传到下一代的概率较大，而适应度较低的个体遗传到下一代的概率相对较小。度量个体适应度的函数称为适应度函数（Fitness Function）。,进化算法及其在数值计算中的应用,遗传操作是遗传算法的核心，它直接影响和决定遗传算法的优化能力，是生物进化机理在遗传算法中的最主要体现，遗传算法的遗传操作包括选择、变异和交叉。选择（selection）：选择操作与生物的自然选择机制相类似，体现了“适者生存，优胜劣汰”的生物进化机理。根据适应度的大小来判断个体的优良，性状优良的个体有更大的机会被选择，产生后代。比例选择：个体被选中的概率与其适应度大小成正比。假设群体规模为M，个体i的适应度为，则个体i被选中的概率为,进化算法及其在数值计算中的应用,交叉（crossover）：交叉操作是指对两个相互配对的染色体按某种方式相互交换其部分基因，从而形成两个新的个体。交叉运算是遗传算法区别于其它进化算法的重要特征，它在遗传算法中起着关键作用，是产生新个体的主要方法，决定了遗传算法的全局搜索能力。,进化算法及其在数值计算中的应用,单点交叉：,算术交叉：,变异（mutation）：变异运算是指将个体染色体编码串中的某些基因座上的基因值用该基因座上的其它等位基因来替换从而形成一个新的个体。变异运算只是产生新个体的辅助方法，但也是一个必不可少的运算步骤，它决定了遗传算法的局部搜索能力。通过变异操作可以维持群体多样性，防止出现早熟现象，改善遗传算法的局部搜索能力。基本位变异：对个体编码串中以变异概率随机指定的某一位或某几位基因座上的基因值做变异运算。二进制中，把基因值取反，即0变1，1变0。浮点数编码中对选定的第i个个体进行逆转操作，如果浮点数变化范围是，则,进化算法及其在数值计算中的应用,遗传算法是一个迭代过程，它模拟生物在自然环境中的遗传和进化机理，反复将选择算子、交叉算子、变异算子作用于群体，最终可得到问题的最优解或近似最优解。遗传算法提供了一种求解复杂系统优化问题的通用框架，它不依赖于问题的领域和种类。对于一个需要进行优化计算的实际应用问题，可按下述步骤构造求解该问题的遗传算法:第一步：确定决策变量及其各种约束条件，即确定出个体的表现型和问题的解空间；第二步：建立优化模型，即确定出目标函数的类型（求解目标函数的最大值还是最小值）及其数学描述形式或量化方法,进化算法及其在数值计算中的应用,第三步：确定表示可行解的染色体编码方法，即确定出个体的基因型及遗传算法的搜索空间；第四步：确定解码方法，即确定出由个体基因型到个体表现型的对应关系或转换方法；第五步：确定个体适应度的量化评价方法，即确定出由目标函数值 到个体适应度值 的转换规则；第六步：设计遗传算法，即确定出选择、交叉、变异等遗传算子的具体操作方法；第七步：确定遗传算法的有关运行参数，包括个体数、进化代数、变异概率、交叉概率等。,进化算法及其在数值计算中的应用,进化算法及其在数值计算中的应用,具体的运算步骤：第一步：初始化，设置进化代数记数器，设置最大进化代数T，随机生成M个个体作为初始群体；第二步：个体评价，计算群体 中每个个体的适应度第三步：选择运算；第四步：交叉运算；第五步：变异运算，群体 经过选择、交叉、变异运算得到下一代群体；第六步：终止条件判断，若，则，转到第二步；若，则以进化过程中所得到的具有最大适应度的个体作为最优解输出，终止计算。,进化算法及其在数值计算中的应用,进化算法及其在数值计算中的应用,群体智能算法（Swarm Intelligence Algorithm）的研究开始于20世纪90年代，其基本思想是模拟自然界生物的群体行为来构造随机优化算法。典型的有蚁群算法、粒子群算法、人工鱼群算法等。粒子群优化（Particle Swarm Optimization，PSO）算法由美国社会心理学家James Kennedy和电气工程师Eberhart共同提出。基本思想是受到鸟群和鱼群群体觅食行为研究结果的启发，与基于达尔文“适者生存，优胜劣汰”进化思想不同，粒子群优化算法是通过个体间的协作来寻找最优解的。作为一种新的并行优化进化算法，粒子群优化算法具有很强的通用性，可用于解决大量非线性、不可微和多峰值的复杂问题优化，并已广泛应用于科学和工程领域。,进化算法及其在数值计算中的应用,自然界中各种生物体均具有一定的群体行为，人工生命的主要研究领域之一就是探索自然界生物的群体行为，从而在计算机上构建其群体模型。通常，群体行为可以由几条简单的规则进行建模，但群体表现出的行为却非常复杂。在对鸟群行为进行仿真时，可以采用下面三条简单规则：（1）飞离最近的个体，避免碰撞。（2）飞向目标。（3）飞向群体的中心。群体内的每一个体的行为可采用上述规则描述，这是粒子群算法的基本概念之一。,进化算法及其在数值计算中的应用,在研究人类的决策过程中，人们提出了个体学习和文化传递的概念。一个人在决策过程中，会使用两类重要的信息：一是自身的经验，二是其他人的经验。也就是说，人们根据自身的经验和他人的经验进行自己的决策。这是粒子群算法的另一基本概念。粒子群（PSO）算法与其它进化类算法相类似，也采用“群体”与“进化”的概念，同样也是依据个体（粒子）的适应度大小进行操作。粒子群算法将每个个体看作是在N维搜索空间中的一个没有重量和体积的粒子，并在搜索空间中以一定的速度飞行。飞行速度由个体的飞行经验和群体的飞行经验进行动态调整。,进化算法及其在数值计算中的应用,假设 为粒子 的当前位置，为粒子 的当前飞行速度，为粒子 所飞过的最好位置，也就是粒子 所经历过的具有最好适应度的位置，称为个体最好位置。对于最小化问题，目标函数值越小，对应的适应度越好。为了讨论方便，设 为最小化的目标函数，则粒子 的当前最好位置由下式确定：,进化算法及其在数值计算中的应用,假设群体中的粒子数为，群体中所有的粒子所飞过的最好位置为，称为全局最好位置，则：有了上面的定义，基本粒子群算法的进化方程可描述为：式中，下标 表示粒子的第 维，即第 个决策变量；表示第 个粒子；表示代数；表示加速常数，通常在02之间取值；为两个相互独立均匀分布的随机函数。,进化算法及其在数值计算中的应用,从上述粒子进化方程可以看出，调节粒子飞向自身最好位置方向的步长，调节粒子向全局最好位置飞行的步长。为了减少在进化过程中，粒子离开搜索空间的可能性，通常限定于一定范围内，即。微粒的最大速度取决于当前位置与最好位置间区域的分辨率。若 太高，则微粒可能会飞过最好解；若 太小，则又将导致微粒移动速度过慢而影响搜索效率；而且当微粒聚集到某个较好解附近时，由于 过小而不利于微粒跳出局部最优解。通常设定为每个决策变量变化范围的10%20%，即如果问题的搜索空间限定在内，则可设定,进化算法及其在数值计算中的应用,基本粒子群算法的初始化过程为：（1）设定群体规模M，即个体的数量；（2）对任意i、j，在 内服从均匀分布产生；（3）对任意i、j，在 内服从均匀分布产生；（4）对任意i，设定。算法的运算过程：（1）依照上述初始化过程，对粒子群的随机位置和速度进行初始设定；（2）计算每个粒子的适应度；（3）对于每个粒子，将其适应度与所飞过的最好位置 的适应度进行比较，若较好，则将其作为当前的最好位置；,进化算法及其在数值计算中的应用,（4）对于每个粒子，将其适应度与全局所经历的最好位置的适应度进行比较，若较好，则将其作为当前的全局最好位置（5）根据公式对粒子的速度和位置进行进化计算；（6）如果没有达到结束条件，即适应度不够好或没有达到预先设定的最大进化代数，则返回步骤（2）。,进化算法及其在数值计算中的应用,基本粒子群算法的社会行为分析：速度进化方程分为三部分，第一部分为粒子原速度；第二部分为认知部分，仅考虑了粒子自身的经验，表示的是粒子自身的思考。如果速度进化方程只包含认知部分，即则算法性能变差。因为不同粒子之间缺乏信息交流，粒子间没有交互和社会信息共享，使得规模为N的群体等价于运行了N个单个粒子，得到最优解的概率非常小。,进化算法及其在数值计算中的应用,速度进化方程中第三部分为社会部分，表示粒子间的社会信息共享。如果方程只包含社会部分，则粒子没有认知能力，这样粒子在相互作用下，有能力达到新的搜索空间，虽然收敛速度比基本粒子群算法更快，但对于复杂问题，容易陷入局部最优点。,进化算法及其在数值计算中的应用,量子粒子群优化（Quantum-behaved Particle Swarm Optimization，QPSO）算法：从量子力学的角度，通过对粒子收敛行为的研究，基于粒子群优化算法提出的一种新的算法模型。在QPSO中，由于粒子满足聚集态的性质完全不同，使粒子在整个可行解空间中进行搜索寻求最优解，因而QPSO在搜索能力上远远优于所有已开发的PSO，通过理论分析证明QPSO是一个全局收敛算法。同时，QPSO具有参数少、易于编码实现等特点。,进化算法及其在数值计算中的应用,QPSO中粒子的位置更新方程为：式中t是算法的当前迭代次数，D为粒子的维数，N为粒子个数，是均匀分布在（0,1）上的随机数，当时，上式 前面取负号，否则取正号。由下式确定：式中 为在（0,1）上均匀分布的随机数，为第i个粒子的当前最优位置，为当前群体的全局最优位置。,进化算法及其在数值计算中的应用,称为压缩-扩张因子，是QPSO中的唯一参数，调节其值能控制算法的收敛速度，一般采用线性减小的取值策略，即 的值随迭代次数的增加而线性减小，方程如下：式中 分别是迭代初始值和终止值，一般取值为或 效果较好。称为平均最优位置，是所有粒子自身最优位置的中心点，由下式计算得到：,进化算法及其在数值计算中的应用,进化算法及其在数值计算中的应用,pNum=1000;%粒子数pDim=4;%粒子维数gen=300;%迭代次数X1min=-100;X2min=-100;X3min=-100;X4min=-100;X1max=100;X2max=100;X3max=100;X4max=100;%变量范围%粒子初始化am=rand(pNum,pDim);%随机数辅助变量Pc(:,1)=X1min+(X1max-X1min)*am(:,1);Pc(:,2)=X2min+(X2max-X2min)*am(:,2);Pc(:,3)=X3min+(X3max-X3min)*am(:,3);Pc(:,4)=X4min+(X4max-X4min)*am(:,4);,进化算法及其在数值计算中的应用,%计算适应度fitness=zeros(pNum,1);for kk=1:pNum a1=abs(5*Pc(kk,1)+Pc(kk,2)-Pc(kk,3)-2*Pc(kk,4)+2);a2=abs(2*Pc(kk,1)+8*Pc(kk,2)+Pc(kk,3)+3*Pc(kk,4)+6);a3=abs(Pc(kk,1)-2*Pc(kk,2)-4*Pc(kk,3)-Pc(kk,4)-6);a4=abs(-Pc(kk,1)+3*Pc(kk,2)+2*Pc(kk,3)+7*Pc(kk,4)-12);fitness(kk,1)=(a1+a2+a3+a4);endpBestp=Pc;%粒子局部最优pBestf=fitness;gBestf index=max(fitness);%全局最优值(适应度)gBestp=Pc(index,:);%全局最优值(个体)Best=zeros(gen+1,pDim+1);%记录最优值变化Best(1,1)=gBestf;Best(1,2:pDim+1)=gBestp;,进化算法及其在数值计算中的应用,for gm=1:gen gm mbest=mean(pBestp);%中值最优位置 c=rand(pNum,1);pp=c c c c.*pBestp+(1-c)*gBestp;u=rand;beita=1.2-0.8*gm/gen;if u0.5 Pc=pp-beita*abs(ones(pNum,1)*mbest-Pc)*log(1/u);else Pc=pp+beita*abs(ones(pNum,1)*mbest-Pc)*log(1/u);end%适应度 for kk=1:pNum a1=abs(5*Pc(kk,1)+Pc(kk,2)-Pc(kk,3)-2*Pc(kk,4)+2);a2=abs(2*Pc(kk,1)+8*Pc(kk,2)+Pc(kk,3)+3*Pc(kk,4)+6);a3=abs(Pc(kk,1)-2*Pc(kk,2)-4*Pc(kk,3)-Pc(kk,4)-6);a4=abs(-Pc(kk,1)+3*Pc(kk,2)+2*Pc(kk,3)+7*Pc(kk,4)-12);fitness(kk,1)=(a1+a2+a3+a4);end,进化算法及其在数值计算中的应用,for gn=1:pNum%限定范围 if Pc(gn,1)X1max Pc(gn,1)=2*X1max-Pc(gn,1);end,%选择个体局部最优和全局最优 if fitness(gn,1)pBestf(gn,1)pBestp(gn,:)=Pc(gn,:);pBestf(gn,1)=fitness(gn,1);end if fitness(gn,1)gBestf gBestf=fitness(gn,1);gBestp=Pc(gn,:);end end Best(gm+1,1)=gBestf;Best(gm+1,2:pDim+1)=gBestp;end,非线性方程组：精确解为（4,3,1）,进化算法及其在数值计算中的应用,进化算法及其在数值计算中的应用,for kk=1:pNum a1=abs(Pc(kk,1)Pc(kk,2)+Pc(kk,2)Pc(kk,1)-5*Pc(kk,1)*Pc(kk,2)*Pc(kk,3)-85);a2=abs(Pc(kk,1)Pc(kk,3)-Pc(kk,2)Pc(kk,3)-Pc(kk,3)Pc(kk,2);a3=abs(Pc(kk,1)Pc(kk,3)+Pc(kk,3)Pc(kk,1)-Pc(kk,2)-2);fitness(kk,1)=(a1+a2+a3);end,参考文献：1 曾建潮，介婧，崔志华。微粒群算法。科学出版社，20042 施光燕，董加礼。最优化方法。高等教育出版社，19993 周明，孙树栋。遗传算法原理及应用。国防工业出版社，19994 张文修，梁怡。遗传算法的数学基础。西安交通大学出版社，20005 李守巨，刘迎曦，孙伟。智能计算与参数反演。科学出版社，20086 焦李成，杜海峰，刘芳，公茂果。免疫优化计算、学习与识别。科学出版社，20077 Sun J,Feng B,Xu WB.Particle swarm optimization with particles having quantum behavior.IEEE Con.Evolutionary Computation.2004:325-331P8 方伟，孙俊，谢振平 等.量子粒子群优化算法的收敛性分析及控制参数研究.物理学报，2010,59(6):3687-3694页,进化算法及其在数值计算中的应用,