下载掌阅APP，畅读海量书库
立即打开
标准遗传算法（Standard Genetic Algorithm，SGA）是指由美国J.H.Holland教授与他的同事和学生于1975年提出的遗传算法理论和方法。20世纪60年代中期，Holland教授提出了位串编码技术。这种编码既适用于交叉操作，又适用于变异操作，并强调将交叉作为主要的遗传操作。随后，他将该算法应用到自然和人工系统的自适应行为研究中。Holland教授早期有关遗传算法的许多概念沿用至今，遗传算法通用的编码技术和简单有效的遗传操作为其后来的成功应用奠定了坚实基础。
标准遗传算法又被称为经典遗传算法，优化变量采用二进制编码来描述，多个优化变量的二进制编码串也可连接在一起组成染色体。在创建初始群体时，代表个体的二进制编码是随机产生的。选择算子、交叉算子和变异算子构成了算法中遗传操作的核心算子。选择算子按照选择概率选择父辈个体，选择概率是通过适应度函数来构建的，适应度函数值大的个体被选中概率大，会有更多的机会将优秀基因延续到下一代。交叉算子按交叉概率作用在配对的两个父辈染色体上，随机选定交叉位置，将两个染色体对应位置上的二进制数值交换，生成两个交叉后的新个体。变异算子按变异概率随机作用在交叉后的个体上，一般是随机选定变异基因位，将该基因位的二进制值取非，生成变异后的新个体。
标准遗传算法的主要本质特征在于群体搜索策略和简单的遗传操作，这使得遗传算法获得了强大的全局解搜索能力，以及信息处理的并行性、应用的鲁棒性和操作的简明性，使之成为一种具有良好适应性和可规模化的求解方法。但大量的实践和研究表明，标准遗传算法存在局部搜索能力差，易陷入局部最优（出现“早熟”现象），收敛时间长，甚至不能保证算法收敛等不足。
针对标准遗传算法的这些不足，对遗传算法的改进主要集中在以下六个方面：编码机制、选择策略、交叉算子、变异算子、特殊算子和算法参数设计（如群体规模、交叉概率、变异概率）等。此外，遗传算法与差分进化算法、人工免疫算法、模拟退火算法等结合起来所构成的各种混合遗传算法，可以综合不同算法的优势，提高算法性能和求解精度。