进化计算,作为一种新兴的强大的智能优化技术,已经广泛地应用在工程科学的几乎所有领域。与传统优化方法相比,进化计算在全局优化、复杂设计区域、复杂目标函数及易用性等方面都显示出了其优越性。遗传算法是进化计算中最重要的算法之一。遗传算法(Genetic Algorithm—GA),是模拟达尔文的遗传选择和自然淘汰的生物进化过程的计算模型,它是由美国Michigan大学的John Holland教授于1975年首先提出的。遗传算法主要的特点在于:简单、通用、鲁棒性强。经过三十多年的发展,遗传算法已经在组合优化、生产调度、函数优化、机器学习等领域得到成功的应用。目前,许多学者已经提出了各种遗传算法,如:量子遗传算法、免疫遗传算法、佳点集遗传算法、自适应遗传算法以及各种改进的遗传算法等等。本文在众多学者研究的基础上,对已有自适应遗传算法进行深入剖析,进而提出两个新的自适应遗传算法,并且用于解决0-1背包问题。1.已有学者提出了一种只有变异的自适应遗传算法(MOGA),本文在MOGA的基础上,引入变换算子和对非法个体的贪婪处理,形成新算法MTGA(Mutation and Transposition Genetic Algorithm),它能够随时间和个体的适应度大小自动调整变换概率和变异概率,而不需要输入。MTGA用在解决0-1背包问题上,编制c程序,在vc++上编译运行。实验表明,与简单遗传算法相比,从“结果超过贪婪算法的解的次数”和“最好求解结果”上得出:MTGA在解的质量上有很大的改进;从“结果超过贪婪算法解时的平均进化代数”上得出:MTGA在求解速度方面有很大改进。与混合遗传算法相比,二者在解的质量方面比较接近;而在求解速度方面,MTGA算法明显好于混合遗传算法。另外,MTGA也明显地优于MOGA。2.在基于和环境进行能量交换的开放系统中存在着复杂性不断增长的结构,Prigog- ine将其发展为常规的热力学概念——耗散结构。可以把耗散结构理论引入到遗传算法中进行分析,初始基因和选择、交叉、变异算子的作用造就了种群的向前发展,因而形成一种耗散结构。耗散结构逐渐消失时,算法陷入局部最优,交叉和变异算子对遗传算法的收敛性起着决定作用,所以可以通过对变异算子的操作来改善。在原来基础上增大变异概率,相当于与外界进行更多的物质和能量交换,以促进系统继续向前发展。本文在含有交叉和变异的自适应遗传算法基础上,引入耗散结构理论,在交叉成功的个体数和变异概率之间建立联系,使交叉成功的个体影响变异概率,并且对非法个体进行贪婪处理,形成新算法(DAGA)。应用在0-1背包问题上,实验中物品的个数分为100、250、500三种情况。由结果得出,除了个别情况,改进后的算法比原算法更容易得到更好的个体。最后,对本文提出的两个算法进行了分析比较。