毕业论文资料
武汉理工大学硕士学位论文
传算法作为一种实用、高效、鲁棒性强的优化技术,发展极为迅速,已引起国内外学者的高度重视。
2.2遗传算法的基本思想
遗传算法是建立在自然选择和群体遗传学机理基础上的随机、选代、进化,具有广泛适用性的搜索方法,所有的自然种类都是适应环境而得以生存,这一自然适应性是遗传算法的主旋律,遗传算法结合了达尔文适者生存和随机信息交换,前者消除了解中不适应因素,后者利用了原有解已有的知识,从而有力地加快了搜索过程。
遗传算法和传统的搜索算法不同,它从一组随机产生的初始解,称为“种群(Population)”开始搜索过程。种群中的每个个体是问题的一个解,称为“染色体(Chromosome)”。在遗传算法中最重要的概念是染色体,染色体通常是一串数据(或数组),用来作为优化问题的解的代码,其本身不一定是解。这些染色体在后续迭代中不断进化,称为遗传。在每一代中用“适值(Fitness)”来测量染色体的好坏。生成的下一代染色体称为后代(Offspring)。后代是由前一代染色体通过交叉(Crossover)或者变异(Mutation)运算形成的。新一代形成中,根据适值的大小选择部分后代,淘汰部分后代,从而保持种群大小是常数。适值高的染色体被选中的概率较高。据此,经过若干代之后,算法收敛于最好的染色体,它很可能就是问题的最优解或次优解。
遗传算法的基本步骤是:
1.确定问题的编码方案。由于GA通常不直接作用于问题的解空间,而是利用解的某种编码表示来进行进化,因此选择合理的编码机制对算法质量和效率有很大影响。
2.确定适应度函数。由于GA通常基于适应度进行遗传操作,因此合理的适应度能够将各个体的优劣程度得以体现,并适应算法的进化过程。
3.算法参数的选取。通常包括种群数目、交叉概率、变异概率、进化代数等。
4.遗传算子的设计。通常包括初始化、选择、交叉、变异和替换操作等。5.确定算法的终止条件。终止准则应根据所求解问题的性质,在优化质量和效率方面作合理均衡或侧重。