基于遗传算法的多式联运组合优化.docx

第四章基于遗传算法的集装箱多式联运运输组合优化模型的求解
4.1遗传算法简介
遗传算法
遗传算法(GeneticAlgorithm,GA)是在20世纪六七十年代由美国密歇根大学的HollandJ.H.教授及其学生和同事在研究人工自适应系统中发展起来的一种随机搜索方法,通过进一步的研究逐渐形成了一个完整的理论和方法体系􀊊取名为基本遗传算法(SimpleGeneticAlgorithm)。在接下来几年的研究过程中Holland在研究自然和人工系统的自适应行为的过程中采用了这个算法，并在他的著作《自然系统和人工系统的适配》中对基本遗传算法的理论和方法进行了系统的阐述与描写，同时提出了在遗传算法的理论研究和发展中具有极为重要的作用的模式理论，它的编码技术和遗传操作成为了遗传算法被广泛并成功的应用的基础，经过许多学者多年来的研究，遗传算法逐渐成熟起来，到现在已经成为了一个非常大的体系，广泛的应用于组合优化、系统优化、过程控制、经济预测、模式识别以及智能控制等多个领域。DeJong于1975年在他的博士论文中设计了一系列针对于各种函数优化问题的遗传算法的执行策略，详细分析了各项性能的评价指标。在此基础上，美国伊利诺大学的Goldberg于1989年系统全面的阐述了遗传算法理论，并通过例证对遗传算法的多领域应用进行了分析，为现代遗传算法的研究和发展奠定了基础。
遗传算法是一种模仿基于自然选择的生物进化过程的随机方法，它以类似于基因的编码作为种群的个体，首先，随机的产生初始种群的个体，从这个群体开始进行搜索，根据类似于生物适应能力的适应度函数值的大小，按照不同问题各自的特点，在当前的种群中运用适当的选择策略选择适应能力大的个体，其中所选择出来的个体经过遗传操作、交叉操作以及变异操作产生下一代种群个体。如此反复，像生物的进化过程一样逐代进化，直到满足期望的终止条件为止。
遗传算法的基本结构
遗传算法是由种群、染色体、适应度函数三个基本要素所组成的，其中种群是由作为个体的染色体组合而成的，适应度函数是对解的优劣程度进行评价的一个函数。遗传算法不同于其他搜索算法之处在于，它的搜索过程中的每一步操作都是对整个种群进行的搜索，然后再按照每个染色体被选为优质个体的概率重新安排个体在种群中的顺序，最后根据优胜劣汰、适者生存的生物进化原理对种群进行演化操作，这时候，首先需要根据个体的适应度函数从当前的种群中挑选出相对优等的染色体，其中个体被选择的概率是根据适应度函数来确定的，对选择出来的优质个体，通过一定的交叉、变异操作产生新的个体，其中，交叉操作是对已选出的优等染色体编码进行位置的互换，变异操作是对某一染色体上某个编码位置进行随机的变化。经过选择、交叉、变异操作之后，新产生的一些染色体构成了新的种群。
遗传算法的实现过程主要包括编码、初始化种群、适应度计算、选择、交叉、变异等六个主要的遗传操作。利用遗传算法对问题进行求解的流程如图4.1所示，具体操作步骤如下所述：否
是
开始
产生种群
计算个体的适应度函数值
个体编码
满足终止条件
结束
遗传操作
群体更新

图4.1遗传算法的过程
第一步，确定种群（population）的规模。首先根据特定问题的大小以及可行解的多少确定合适的种群规模，也就是在应用遗传算法求解问题时初始种群中个体的数量。
第二步，对个体进行编码，产生初始种群。编码是遗传算法进化过程的基础，影响着算法的搜索能力、种群的多样性等性能。在对个体编码的时候需要根据特定问题的具体特点确定适当的编码方法，如二进制编码、浮点数编码、字符编码等编码方法（如二进制编码、浮点数编码、字符编码等编码方法），随机地产生由可行解组成的初始种群，这是应用遗传算法进行优化求解的开始，然后，该算法会通过一些模拟生物进化过程中的优胜劣汰规律的操作，包括遗传操作、选择操作、交叉操作、变异操作（包括遗传操作、选择操作、交叉操作、变异操作），得出种群中的最优个体，即为问题的最优解。
第三步，设计适应度函数（fitnessfunction）。适应度函数是用来计算群体中的个体对环境的适应程度的函数，适应度值在遗传算法中表示个体被遗传到下一代种群的概率大小，它是个体进化的主要依据。个体的适应度值是用来对种群中的每个染色体的优劣程度进行评价的唯一依据，对种群的操作包括选择、交叉、变异等操作都是根据个体的适应度值来进行的。一般来说，适应度值越大，遗传到下一代的可能性就会越大，在求得个体的适应度值之后，一般都会将个体按照适应度值进行排序，以便于下一步所进行的选择操作。
第四步，选择操作（selection）。在对种群进行个体的选择之前，首先确定在进行选择的时候所根据的规则和方法，选择操作一般以将个体的适应度值作为依据，按照所选定的选择方法从当前的种群中选出适应度高的优质个体，作为进行下一