《算法的乐趣》第五十节

本节收束了离散傅里叶变换（FFT）一章，指出其在工业与信号处理领域应用广泛，本章算法虽非最高效，但适合研究算法原理，目的是让读者了解生活中隐藏的算法、消除对算法的神秘感。

本节收束了离散傅里叶变换（FFT）一章，指出其在工业与信号处理领域应用广泛，本章算法虽非最高效，但适合研究算法原理，目的是让读者了解生活中隐藏的算法、消除对算法的神秘感。随后列出本章参考资料。

接着进入第16章“全局最优解与遗传算法”。本章要介绍一种充满随机性的启发式方法寻找最优解，与贪心、动态规划、穷举等确定性方法不同。这类随机化算法（如模拟退火、蚁群算法、遗传算法等）各有理论基础，不依赖目标函数信息，适合复杂或非线性问题，在人工智能、机器学习等领域应用广泛。

16.1节介绍遗传算法的原理：它借鉴生物“物竞天择，适者生存”的进化机制，把问题的解作为个体组成种群，通过评估函数优胜劣汰，并以交叉和变异模拟进化，经过若干代后得到接近最优解的个体。16.1.1节解释基本概念：基因是不可再拆分的遗传因子，染色体是基因的组合；种群中的个体相互影响；适应度高的个体繁衍机会多。交叉是两两互换部分基因编码，变异是替换个别或全部编码，二者都需用概率控制频度——太频繁则无法收敛，太少则易陷入局部最优。选择则是按适应度把优良个体遗传到下一代。

16.1.2节给出处理流程：种群逐代演化，经历个体评价、选择、交叉、变异四个步骤，后三者称为遗传算子。遗传算法并非具体算法而是一种思想，针对不同问题需解决三个设计问题：基因的选择与编码、适应度评估函数、遗传算子。基因即问题解的某种编码形式，编码须满足完备性、健全性、非冗余性三个条件。常用编码方式有二进制编码（存在汉明悬崖问题，小改动导致结果差异巨大）、格雷编码（相邻码仅一位不同，连续性好，可避免汉明悬崖）、符号编码（用字母等符号表示非数字问题，如26门课程用A～Z表示）和属性序列编码（为每个属性分别编码后按序列组合，如背包问题中每件物品的选择状态用0、1表示）。