第9章现代优化计算方法new11

第9章现代优化计算方法

§9.1引言§9.2计算复杂性和启发式算法的概念§9.3模拟退火优化算法§9.4遗传优化算法§9.5神经网络优化算法§9.6混合优化算法§9.7多学科设计优化§9.1引言Powell法、梯度法随机方向搜索法、复合形法、惩罚函数法常规优化算法启发式算法适于求解高非线性、多约束、多极值问题——现代优化计算方法：模拟退火算法（Simulatedannealing）遗传算法（Geneticalgorithms）神经网络优化算法（Neuralnetworksoptimization）混合优化算法（Hybridoptimization）§9.2计算复杂性和启发式算法一.计算复杂性由于计算时间和存储空间的局限，某些算法在实践中不一定能得到解算法的复杂性算法的求解方法造成（例：求二阶导数）问题的复杂性问题本身求解的复杂造成求解问题的规模（维数）n对复杂性的影响§9.2计算复杂性和启发式算法是相对于有严格数学背景的数学规划优化算法提出的。二.启发式算法是基于直观或经验构造的算法，在可接受的花费（指计算时间和空间）内寻找最好的解，但不能保证所得的解就是最优解，以及此解与最优解的近似程度。有严格数学背景——梯度法、坐标轮换法、Powell法通过揭示和模拟自然现象和过程，并综合数学、物理学、生物进化、人工智能、神经科学和统计学等所构造的算法。也称构造型算法、智能优化算法。§9.3模拟退火优化算法一.物理背景：

固体退火的物理过程和统计性质：（1）加温：随温度升高，粒子能量增高，与平衡位置的距离增大（2）等温：温度升至熔解温度，固体的规则性被打破，成为液体，粒子可以自由运动和重新排序，消除系统中原先存在的非均匀状态（3）冷却：随着温度的下降，粒子能量减弱，运动减小粒子最终进入平衡态，固化为具有最小能量的晶体§9.3模拟退火优化算法其中：

E(r)——状态r的能量k——常数E——分子能量的一个随机变量z(t)——概率分布的标准化因子

D0

——最低能量状态的个数

D

——状态空间中状态的个数相同温度下，分子停留在低能量状态的概率要更大随着温度t不断降低，分子停留在低能量状态的概率不断增大物理退火优化设计E（r）f（x）E（rmin）f（x*）温度t下，分子停留在某一状态r满足Bolztmann概率分布：分子停留在某种能量状态的概率与温度成反比§9.3模拟退火优化算法状态迁移准则（Metropolis抽样稳定性条件）：

若新状态j的能量满足条件，则被用来替代原状态i。高温下，接受能量差较大的新状态；低温下，只接受能量差较小的新状态。二.基本思想：基本思想：由某一较高的初始温度开始，利用上式在解域内随机搜索采样，随着温度不断降低，使系统的能量达到最低状态，即相当于能量函数的全局最优解。§9.3模拟退火优化算法内循环外循环设求解优化问题S.1任选一个初始解（初始状态）

x(0)，并令k=0，x(k)

=x(0)

和

tk=t0（初始退火温度t0应取较高的值），计算

f(x(k))；S.2在温度tk下做下面循环：S.2.1在当前的tk下随机产生新状态（候选解）x’=genete(x(k))S.2.2计算

f(x’)值和

Δf=

f(x’)－f(x(k))S.2.3若Δf<0

则令x(k)

=x’，转S.3；否则执行下一步S.2.4若状态接受函数

min{1,exp(-Δf/tk)}>random(0,1)，则令x(k)

=x’，转S.3；否则转S.2.1S.3若满足算法收敛（退火结束）准则，则转S.4；否则令下一循环的退火温度tk+1=updat(tk)（退温函数）和k=k+1，转向S.2；S.4终止计算，输出结果，即取x*

=x’和f(x*)=

f(x’)。三.算法基本步骤：§9.3模拟退火优化算法内循环终止条件1.规定产生有限个候选解

；2.在连续若干步候选解的目标函数值变化很小：3.目标函数值的均值已相当稳定。外循环终止条件1.设置一个终止温度

te；2.规定外循环的最大迭代次数kmax：3.算法在每个tk值搜索到的最优解的值在若干次迭代内已保持不变。三.算法基本步骤：§9.3模拟退火优化算法基本要求：应保证所产生的候选解可以遍及整个解域。一般形式：η为摄动幅度系数；ε为服从某种随机分布的变动量例：已知各变量的变动范围取式中：r——[0,1]之间均匀分布的伪随机数K——区域缩减系数，取K≥1α

——分布系数，取正奇数1，3，5，7等四.算法实现的几个技术问题——新状态产生函数

genete(x(k))§9.3模拟退火优化算法min{1,exp(-Δf/tk)}基本要求在某个退火温度tk下，接受目标函数值下降的候选解的概率要大；随着退火温度的下降，使接受目标函数值下降的候选解的概率越来越大，且当退火温度接近于0时，概率接近于1，即只能接受目标函数值下降的候选解。一般形式四.算法实现的几个技术问题——状态接受函数

§9.3模拟退火优化算法算法实现的几个技术问题

——初始温度

初温的选择方法：（初温大>>获得高质量解的概率大>>计算时间长）式中：K——一个充分大的数，可取K＝10，20，100，···等试验值；p——初始接受概率。1.均匀抽样一组状态，以各状态目标函数值的方差为初温t0

；2.随机产生一组状态，确定两状态的目标函数差值然后根据差值，利用一定的函数产生初温，如取或§9.3模拟退火优化算法算法实现的几个技术问题

——退温函数updat(tk)

常用的退温函数：退温慢，候选解数目多>>获得高质量解的概率大>>计算时间长退温快>>计算效率提高>>不能保证收敛到全局最优解，其大小可以固定（同比率下降）也可以不断变化（变比率下降）。α接近于1，温度下降得缓慢。此法简单易行，使用较多；，式中t0为初始温度；K为算法温度下降的规定总次数§9.3模拟退火优化算法四.小结优点：缺点：可防止陷入局部最小点，获得全局最优解的可能性大；对初始点的稳定性好；无需求导，算法通用易实现。为使获得全局最优解的可能性大，则所需花费的计算时间相对较长。§9.4遗传优化算法一.背景：生物进化基本循环图

依据生物进化论中的“适者生存”规律而提出：§9.4遗传优化算法

遗传算法的主要生物进化特征体现在：（1）进化发生在解的编码（染色体）上。优化问题通过编码来研究。（2）自然选择规律决定哪些染色体产生超过平均数的后代。遗传算法通过优化目标构造适应函数以达到好的染色体超过平均数的后代。（3）当染色体结合时，双亲的遗传基因的结合使得子女保持父母的特征。（4）当染色体结合后，随机的变异会造成子代与父代的不同。一.背景：§9.4遗传优化算法二.基本思想：

遗传算法在求解优化问题时首先对求解空间的各个解进行编码。在寻优过程中，通过对染色体（解的编码，个体）进行结合（基因遗传、变异和交配），不断产生新的解，进而根据适应函数在新解中选择部分染色体继续进行结合，直至最终找到最好的解。遗传基因：字符串的每一位数编码：把解用字符串表示群体：个体的集合§9.4遗传优化算法二.基本思想：

例6-1用遗传算法求minf(x1,x2)=x1+x2

，当x1和x2为整数时的整数解，且一个解（个体的染色体）适应函数（个体的表现型）

f(x1,x2)N1：1011001114N2：1101111027N3：1000110121N4：0110010111解：若用4位二进制编码表示一个设计变量xi，则一个解(x1,x2)需用8位二进制编码表示：§9.4遗传优化算法二.基本思想：

例6-1N4：01100101交配N1：10110011N4：01100101交配N3：10001101N1’：01110111=14N2’：10100001=11N3’：01000101=9N4’：10101101=23遗传算法的4个组成部分：编码和解码、适应函数、遗传算子和控制参数若以这4个个体为群体，按求解的要求，适应函数值小的染色体的生存概率较大，则能竞争上的是N1、N3和N4点，其交配方式如下：通过分别交换基因，实现了交配，得到了4个新个体N1’、N2’、N3’和N4’。若对某个个体（例如N2’）进行基因变异（1→0），可得N2”:00100001(=3)§9.4遗传优化算法三.算法的基本步骤：S.1选择优化问题求解的一种编码；S.2随机产生N个染色体的初始群体{pop(k),k=0}；S.3对群体中的每个染色体popi(k)计算适应函数

fi=fitness(popi(k))S.4若满足终止规则，则转向S.9，否则计算概率S.5以概率pi从pop

(k)中随机选一些染色体构成一个新群体（其中可以重复选pop

(k)中的元素）newpop(k+1)={popi(k),i=1,2,···,N}§9.4遗传优化算法三.算法的基本步骤：S.6通过交配，按交配概率pc得到一个有N个染色体的交配群体crosspop(k+1)；S.7以一个较小的变异概率pm，使得一个染色体的基因发生变异，形成变异群体mutpop(k+1)；S.8令k=k+1和popi(k)=mutpop(k+1)，返回S.3；S.9终止计算，输出最优结果。§9.4遗传优化算法四.算法实现的几个技术问题——编码和解码

编码——由设计空间向编码空间的映射。将设计解用字符串表示的过程。编码的选择是影响算法性能和效率的重要因素。解码——由编码空间向设计空间的映射。§9.4遗传优化算法连续变量x，在给定区间[a,b]的二进制编码策略（长度为l）：其中，二进制编码的长度为l，a1,a2,···,al取0或1，二进制码与实际变量的最大误差为(b-a)/2l四.算法实现的几个技术问题——编码和解码

例：求maxf(x)=1-x2，x∈[0,1]。假设对解的误差要求为1/16,则可采用4个二进制编码（即l＝4），b-a=1，对照上式，有：§9.4遗传优化算法几种常见的编码方式四.算法实现的几个技术问题——编码和解码

§9.4遗传优化算法对于求极大化的目标函数（即max.f(x)），可通过下面转换建立与fitness(x)的映射关系:四.算法实现的几个技术问题——适应函数fitness(x)

时时对于求极小化的目标函数（即min.f(x)），可通过下面转换建立与fitness(x)的映射关系:时时Cmin和Cmax为可调参数，所取的值应使适应函数fitness(x)恒大于0。适应函数——用于对个体进行评价，即反映个体对问题环境适应能力的强弱。是优化进程发展的依据。其值必须大于等于零§9.4遗传优化算法群体规模N——是影响算法性能和效率的因素之一。规模太小，不能提供足够多的采样点；规模太大，计算量大，耗时长。通常取N介于n（编码长度）和2n之间，或依据经验在范围内取值。四.算法实现的几个技术问题——算法参数

交配概率pc

——用于控制交配操作的频率，通常取0.4~0.9之间。概率太大，种群更新过快，会使一下高适应函数值的个体过快被破坏；概率太小，交配操作很少进行，搜索速度慢，耗时长。变异概率pm

——加大种群多样性的重要因素，通常取0.1~0.3之间。概率太大，则使遗传算法退化成随机搜索算法；概率太小，产生新个体的机会太小。§9.4遗传优化算法复制、交配、变异四.算法实现的几个技术问题——遗传算子

复制（选择）——目的是选择用于繁殖后代的双亲。体现“适者生存”，适应度高，生存概率大。依据选择概率pi=fi/Σfi进行。交配——两个相互配对的染色体（双亲）按某种方式相互交换其部分基因而生称两个新的个体。方法：对选择的双亲以交配概率pc判断是否交配，对发生交配的双亲，随机选择交配位置，彼此交换基因，产生新个体。既继承了双亲的个体特性，也产生了新的个体特性。§9.4遗传优化算法四.算法实现的几个技术问题——遗传算子

双亲A100100交配B010010后代A’100010B’010100双亲A1011001交配B0010110后代A’1010101B’0011010一点交配（二进制）：多点交配（二进制）：§9.4遗传优化算法四.算法实现的几个技术问题——遗传算子

0101010交配0101110变异——在交配之后进行。将个体染色体编码字符中的某些基因用其他等位基因替换，从而生成新的染色体。可起到恢复丢失或生成遗传信息的作用，保持群体中个体的多样性，有效地防止算法早熟收敛。方法：按位进行，以概率pm改变字符串上某一位基因。例：变异（二进制）§9.4遗传优化算法四.算法实现的几个技术问题——算法终止准则

事先规定出一个最大的进化步数，到达此步数时终止。判断当前最好的解已连续若干步没有变化。算法已找到了一个可接受的最好解。§9.4遗传优化算法五.遗传算法与其他传统搜索方法的比较

遗传算法不是直接作用在解空间上，而是作用在解的某种编码上遗传算法从一个群体解（即多个解）而不是一个解开始搜索，这是它能以较大概率找到全局最优解的主要原因。遗传算法对搜索空间无任何特殊要求（如连通性、凸性），只利用适应度信息，而传统搜索算法一般要使用导数等其他辅助信息。遗传算法使用随机转移规则而不是确定性的转移规则。§9.5神经网络优化算法一.基本概念——生物神经网络神经网络由相互关联的神经元组成，每个神经元由晶枝、内核和轴突组成。神经元通过晶枝接受信息，通过内核进行信息处理，再通过轴突及其终端的突触将信息传递给其他的神经元。生物学中神经网络简图“兴奋性”的神经元：神经元的晶枝接受兴奋性信息累计超出某一值时，神经元被激活并传递出一个信息给其他神经元。“抑制性”的神经元：神经元虽接受到了兴奋性信息，但未向外传递信息。§9.5神经网络优化算法一.基本概念——