2.3  人工智能算法

所谓人工智能算法，即通过人的智慧来模拟人的本能行为的算法。

2.3.1  遗传算法(Genetic Algorithm，GA)

Holland在1975年得出简单的遗传算法，它是一种模拟自然界中各个生物种群的繁衍过程中，随着时间推移，种群中的个体按不断被自然环境半随机的选择。遗传过程中，合适的两个个体交配，基因随环境发生变异，遵循“适者生存，不适者淘汰”的自然生存原则。随着遗传代数增加或者说时间的延长，种群中得以留下的个体相对于被淘汰的个体更加适应环境，从而使种群往更加适应环境的方向发展，最终种群和自然环境无限逼近切合，但不排超凡个体。在当前的研究工作当中，将遗传算法用于解决实际问题时，都是将实际问题的解空间看做环境可选择的最大范围，一般情况下，按照适应度函数进化。

基本遗传算法步骤

1. 确定实际问题的编码方式，初始化种群遗传参数。

2. 基于产生集初始化种群，当前代数为1

3. 用适应度函数对初始种群的个体进行评价

4. 在初始种群中按选择概率选择出两个个体

5. 执行相关遗传操作，子女个体代替父母个体进入下一代。

6. 判断新一代种群的个体数量是否达到环境的最大承载值，若未达到，继续繁衍，遗传代数增加

7. 判断繁衍是否满足终止条件，若达到，停止繁衍，输出结果，否则返回执行3

相关参数设定会对遗传算法性能产生重要的影响。

对于交叉概率，主要是保证算法的全局搜索能力，交叉概率越大，开辟新的搜索空间的能力越强，但容易破坏优秀个体，反之，容易陷入局部停滞。

设计交叉算子时具有较高的新生个体能力和能产生适应值更高的新个体执行算子。变异概率保证算法的局部搜索能力。

变异概率越大，种群的多样性越高，带有的随机性也越强，反之，种群的多样性比较低。设计变异算子时以增大种群的多样性为原则。

算法终止条件通常情况下可用最大遗传代数，最低适应度等，当采用最大遗传代数最为算法终止条件时，遗传代数越多，对找到最优解越有利，但与此同时计算量也会增多，当采用适应度阀值作为算法终止条件时，必须明确解空间的适应度值范围，设置不当则容易使算法陷入无休止的遗传过程。

2.3.2  粒子群算法（Particle Swarm Optimization，PSO)

假设粒子群含有m个粒子，m个粒子在空间中参考自身当前记录的最优位置和整个粒子群当前的最优位置按照自己的速度在解空间运动寻找最优位置，历史最优和群体最优不断改变为当前最优，从而找到最优位置。

基本实现步骤：

1. 确定解空间，即粒子的位置变化范围，初始化粒子群学习因子，惯性因子等参数，初始化威哥粒子的初始速度和位置

2. 对每个例子用适应度函数对粒子的当前位置进行评价

3. 每个粒子按照速度变化公式和位置变化公式更新位置，直到达到指定适应度值或者最大迭代次数。

位置变化公式：：v k+1id =wvk id  +c1a(pkid   - Xkid)+c2b(pkgd   - Xkid)

粒子的速度变化公式：X k+1id =Xkid    - Vk+1id

将PSO用于TCP技术时需要将粒子的解空间离散化，粒子可能达到的每一个位置空间均为测试用例排序

PSO适合解决具有连续解空间的实际问题，但显然TCP问题属于离散解空间求解最优。一般情况下，有两种方式将粒子群思想用于求解此类问题，其一，将离散的求解问题映射到连续PSO，其二，改变PSO中位置和速度的更新函数，使其离散化处理离散的问题。

2.3.3  遗传粒子群混合优化算法(Hybrid GA and PSO,HGAPSO) [2]