智能计算：遗传算法、模拟退火、蚁群算法等期末自测题

本文包含填空37道、简答18道、流程图3道和计算题8道，重点为遗传算法、模拟退火、蚁群算法，包含部分免疫算法、粒子群优化算法、人工鱼群、人工蜂群算法以及模糊逻辑。参考书目为张军、詹志辉等人的《智能计算》，本资料仅用于考前复习参考，如有错误请及时指正，感激不尽！ 【智能计算】是一种模仿生物进化、自然界和社会行为的计算方法，旨在解决复杂优化问题。它主要依靠启发式随机搜索策略，能在全局空间中寻找最优解或可接受解，具有智能性、并行性和鲁棒性等特征。 【遗传算法】是智能计算的一种，源于生物的遗传和进化原理。其基本操作包括选择、交叉和变异，由J.Holland教授提出。通过适者生存原则，遗传算法逐步演化出接近最优解的解决方案。遗传算法的编码方式包括二进制编码、浮点数编码和符号编码，常见的遗传算子有比例选择算子、基本位变异和单点交叉算子。汉明悬崖问题是遗传算法面临的一个挑战，由于相邻解之间汉明距离大，导致交叉和变异困难。早熟现象是算法过早收敛，导致群体多样性下降，影响求解质量。 【模拟退火算法】借鉴了固体冷却过程中能量降低的物理过程，即使得在远离最优解的解也有一定概率被接受，以避免过早收敛。核心思想是Metropolis准则，以概率接受劣解，保持算法的全局搜索能力。 【蚁群算法】是受蚂蚁寻找食物路径启发的算法，主要特征包括分布式、自组织和正反馈。算法主要包括蚁群活动、信息素挥发和信息素增强。Ant-density、Ant-quantity和Ant-cycle是Dorigo提出的三种版本。蚂蚁通过转移概率和信息素更新公式来寻找最短路径，适用于解决旅行商问题（TSP）等组合优化问题。 【免疫算法】受到生物免疫系统启发，包括免疫识别、免疫学习和免疫记忆机制。它能在大量可能解中找到优质解，防止早熟现象。 【粒子群优化算法】和【人工鱼群算法】是另外两种生物行为模拟的算法，分别模仿鸟群飞行和鱼群游动。粒子群算法中，粒子通过调整速度和位置来优化目标函数；人工鱼群算法中，鱼的四种行为（觅食、聚群、追尾、随机行为）协同工作，探索解决问题的空间。 【模糊逻辑】是处理不精确或不确定信息的工具，模糊计算包括模糊规则库、模糊化、推理方法和去模糊化四个步骤，广泛应用于决策支持和控制等领域。 简答题主要涵盖了传统问题与现代问题的区别，启发式算法的定义、特点，以及P、NP、NPC和NP-hard问题的概念。传统问题侧重于连续性、精确解，而现代问题关注离散性、不确定性和大规模。启发式算法不保证最优解，但能在有限时间内提供可行解。P类问题能在多项式时间内求解，NP问题能在多项式时间内验证解，NPC问题既是NP也是P，若有一个NPC问题能在多项式时间内求解，则所有NP问题都能。NP-hard问题至少与NPC问题同样难，但不一定是NP问题。