李孝忠，任吉栋

(天津科技大学计算机科学与信息工程学院，天津 300222)

改进的DNA遗传算法在指派问题中的应用

李孝忠，任吉栋

(天津科技大学计算机科学与信息工程学院，天津 300222)

提出了一种基于优秀基因片段思想的DNA遗传算法，将这段基因片段提取出来并将它遗传到后代中，可以加快收敛速度．给出了DNA遗传算法的结构，讨论了选择、交叉和变异算子的具体操作，并将其运用到指派问题最优解的求解中，给出了具体的实现方法．仿真实验验证了算法的有效性和实用性．

DNA计算；遗传算法；指派问题

Abstract：A DNA genetic algorithm based on the thought of excellent gene was proposed，extracting the excellent gene and inheriting it to future generations can speed up the convergence. The structure of DNA genetic algorithm was given and its specific operations including select，crossover and mutation operator were discussed. The method mentioned above was applied to the optimal solution of assignment problem and the concrete implementation was given. The effectiveness and practicality of the algorithm were verified by computer simulation at last.

Keywords：DNA calculation；genetic algorithm；assignment problem

遗传算法是近年来迅速发展起来的一种全新的随机搜索与优化算法，它具有不依赖于问题模型、易于并行处理、有较强的全局搜索功能、鲁棒性强等特点，适用于处理传统搜索方法难以解决的复杂和非线性问题[1]．但是，遗传算法也存在早期收敛[2]和微调能力差[3]等不足．

DNA计算是一种新的计算模式．1994年Adelman首次用实验显示了DNA计算的可能性[4].其最大优点是充分利用了DNA分子具有海量存储遗传密码以及生化反应的海量并行性．近年来，一大批科学家投身于DNA计算这一新的研究领域，提出了许多组合优化问题的DNA计算模型[5]．

为了进一步模拟生物的遗传机理和基因调控机理，一些学者提出了基于DNA编码的遗传算法[6]，并将其用到组合优化问题的求解当中[7]．DNA遗传算法既可以提高DNA计算的效率，又可以拓宽遗传算法的应用范围．DNA遗传算法还需要在常规的遗传算……