软硬件协同的遗传算法设计

聂 鑫，殷若兰，刘海峰

(1.智能机器人湖北省重点实验室，湖北 武汉 430205；2.武汉工程大学 计算机科学与工程学院，湖北 武汉 430205；3.华为技术有限公司，广东 深圳 518000)

0 引 言

遗传算法是Holland在1975年提出的一种概率搜索算法[1]。遗传算法通过有组织地然而是随机的信息交换来重新结合那些适应性好的串。类似于生物的进化，遗传算法作用于类似于基因的二进制串上，通过寻找好的二进制串来求解问题。在每一代中，算法使用上一代适应值较好的个体通过杂交变异的方式生成一个新的种群。由于它不是直接作用于解空间，所以不受搜索空间的限制，同时也不需要丰富的先验知识，以及其内含的天然并行性。因此遗传算法作为一种有效的优化算法在多个领域得到了应用。

目前遗传算法的应用研究中存在若干问题：算法的执行效率低下、算法收敛速度慢以及算法无法找到最优解(即算法过早收敛)。对于后两个问题，不少学者通过不断的改进算法的因子以及算法的整体结构，或者是将算法与其他新算法进行融合来提高算法的收敛速度。针对算法执行效率低下的问题，现在也有不少学者试图使用硬件化的方式来实现遗传算法[2-4]，或者在大型的工作站中利用遗传算法所具有的天然并行性来解决，这些方法都取得了一定的效果。这些方法在一定程度上也代表了今后遗传算法的发展方向，同时也为遗传算法在更多领域甚至在实际场合种应用创造了条件。……