第23章 现代优化算法

现代优化算法是 80 年代初兴起的启发式算法。这些算法包括禁忌搜索(tabu search),模拟退火(simulated annealing),遗传算法(genetic algorithms),人工神经网 络(neural networks)。它们主要用于解决大量的实际应用问题。目前,这些算法在理论 和实际应用方面得到了较大的发展。无论这些算法是怎样产生的,它们有一个共同的目 标-求 NP-hard 组合优化问题的全局最优解。虽然有这些目标,但 NP-hard 理论限制它 们只能以启发式的算法去求解实际问题。 启发式算法包含的算法很多,例如解决复杂优化问题的蚁群算法(Ant Colony Algorithms)。有些启发式算法是根据实际问题而产生的,如解空间分解、解空间的限 制等;另一类算法是集成算法,这些算法是诸多启发式算法的合成。 现代优化算法解决组合优化问题,如 TSP(Traveling Salesman Problem)问题,QAP (Quadratic Assignment Problem)问题,JSP(Job-shop Scheduling Problem)问题等效 果很好。 §1 模拟退火算法 1.1 算法简介 模拟退火算法得益于材料的统计力学的研究成果。统计力学表明材料中粒子的不 同结构对应于粒子的不同能量水平。在高温条件下,粒子的能量较高,可以自由运动和 重新排列。在低温条件下,粒子能量较低。如果从高温开始,非常缓慢地降温(这个过 程被称为退火),粒子就可以在每个温度下达到热平衡。当系统完全被冷却时,最终形 成处于低能状态的晶体。 如果用粒子的能量定义材料的状态,Metropolis 算法用一个简单的数学模型描述了 退火过程。假设材料在状态i 之下的能量为 E(i) ,那么材料在温度T 时从状态i 进入状 态 j 就遵循如下规律: (1)如果 E( j) ≤ E(i) ,接受该状态被转换。 (2)如果 E( j) > E(i) ,则状态转换以如下概率被接

  • 2021-10-30
  • 阅读484
  • 下载0
  • 20页
  • pdf

第11章 方差分析

我们已经作过两个总体均值的假设检验,如两台机床生产的零件尺寸是否相等,病 人和正常人的某个生理指标是否一样。如果把这类问题推广一下,要检验两个以上总体 的均值彼此是否相等,仍然用以前介绍的方法是很难做到的。而你在实际生产和生活中 可以举出许多这样的问题:从用几种不同工艺制成的灯泡中,各抽取了若干个测量其寿 命,要推断这几种工艺制成的灯泡寿命是否有显著差异;用几种化肥和几个小麦品种在 若干块试验田里种植小麦,要推断不同的化肥和品种对产量有无显著影响。 可以看到,为了使生产过程稳定,达到优质、高产,需要对影响产品质量的因素进 行分析,找出有显著影响的那些因素,除了从机理方面进行研究外,常常要作许多试验, 对结果作分析、比较,寻求规律。用数理统计分析试验结果、鉴别各因素对结果影响程 度的方法称为方差分析(Analysis Of Variance),记作 ANOVA。 人们关心的试验结果称为指标,试验中需要考察、可以控制的条件称为因素或因子, 因素所处的状态称为水平。上面提到的灯泡寿命问题是单因素试验,小麦产量问题是双 因素试验。处理这些试验结果的统计方法就称为单因素方差分析和双因素方差分析。 §1 单因素方差分析 只考虑一个因素 A 对所关心的指标的影响, A 取几个水平,在每个水平上作若干 个试验,试验过程中除 A 外其它影响指标的因素都保持不变(只有随机因素存在),我 们的任务是从试验结果推断,因素 A 对指标有无显著影响,即当 A 取不同水平时指标 有无显著差别。 A 取某个水平下的指标视为随机变量,判断 A 取不同水平时指标有无显著差别, 相当于检验若干总体的均值是否相等

  • 2021-10-31
  • 阅读480
  • 下载0
  • 13页
  • pdf