论文摘要
遗传算法是模拟生物在自然环境中的遗传和进化过程而形成的一种自适应全局优化概率搜索算法,它提供了一种求解复杂系统优化问题的通用框架,目前已广泛应用于许多学科。在对遗传算法进行深入研究的基础上,针对传统遗传算法在求解一类容易用0-1表示的问题时存在的不足,提出了一种改进的遗传算法——长模式遗传算法。针对定义距较长的模式提出了三个具体的再生算子,并以再生算子代替交叉算子,采用简单位变异算子,从而获得长模式遗传算法,它在一类容易用0-1来表示的问题中比采用交叉算子的传统遗传算法具有更好的反映问题特性的特点。长模式遗传算法的编码方式主要有二进制编码、格雷编码和符号编码,而选择方式、运行过程、适应度计算等与传统遗传算法基本相同;并且针对问题的需要提出了三种终止条件以满足不同需求。为了研究编码方式、选择方式、再生算子、再生概率和变异概率等因素对长模式遗传算法性能的影响,采用多个通用的测试函数,提出了成功比例、平均世代数、平均运行时间等具有平均思想的性能评价指标,通过大量的数值仿真实验,获得了长模式遗传算法在测试函数的仿真实验中具有较好性能指标的一些策略和参数选择。为了研究高阶、长定义距以及平均适应度高的模式的遗传,将长模式遗传算法应用于One-Max函数和皇家大道问题,仿真结果证实了再生算子的有效性以及再生算子和变异算子在模式的重组和遗传过程中的良好作用。我们将长模式遗传算法,基本遗传算法,模拟退火算法,遗传模拟退火算法,基于价值密度的贪婪算法,回溯法,分支定界法和动态规划法应用于0-1背包问题,实验结果表明:长模式遗传算法同其它算法相比,它所获得的最优解的质量和回溯法、动态规划法等精确算法获得的结果相同,比基本遗传算法、模拟退火算法、遗传模拟退火算法、基于价值密度的贪婪算法等算法获得的最优解更好,而且长模式遗传算法获得最优解时的评价指标比基本遗传算法、遗传模拟退火算法等算法的相应指标更好,证明了长模式遗传算法的有效性。在分析多选择背包问题和多约束背包问题的基础上,分别提出了基于物品的类别及项目号的编码方法和基于背包编号的编码方法,设计了相应的再生算子和变异算子,并提出了相应的染色体修正方法和适应度计算方法,最后通过仿真实例验证长模式遗传算法求解这两个问题的有效性。