基因学习算法在调度问题中的应用

摘要

进化计算是一类借鉴生物遗传与进化思想发展起来的搜索方法.进化计算的特点是使用了一种群体搜索机制,使算法不易过早地陷入某个局部极值点.进化计算的算法设计简单、应用领域适应性广,适用于用传统方法难以处理的各种组合优化问题(尤其是NP难题).遗传算法是进化计算中使用最广泛的算法之一.但是,针对问题设计的遗传、变异、杂交等算法比较复杂,通用性不好,BalujaS提出的PBIL(Population-BasedIncrementalLearning)算法则比较好地解决了这个问题.该算法使用基因位的概率来描述群体信息,用概率来产生临时评价群体,并使用一个最优个体来修正概率的进化机制,因而使算法对不同问题的通用性更强.本文对该算法进行了一些改进(称为基因学习算法),并对该算法在一些组合优化问题中的应用进行了研究.