宜生乳业冷链物流配送方案优化设计 - 图文(6)

山东科技大学工程硕士学位论文相关理论分析

算法以一种群体中的所有个体为对象，并利用随机化技术对一个被编码的参数空间进行高效搜索。其中，遗传算法的操作主要包括选择、变异以及交叉，它通过这种遗传过程来产生不同于初始个体的新的代，并逐渐循环下去，在整个过程中，适应性较差的个体将会慢慢地被淘汰。参数编码、初始种群的设定、适应度函数的设计、遗传操作设计、控制参数设定5个要素构成了遗传算法的核心内容。2.4.2遗传算法的特点

（1）对可行解表示的广泛性。遗传算法的处理对象主要是由参数集编码后所得到的基因个体，而并非参数本身。这种编码动作能够让遗传算法对结构对象实施操作，而且这种操作相对比较直接。

（2）群体搜索特性。传统的搜索方法大都属于单点搜索，在多峰分布的空间里，单点搜索容易陷于某个单峰的最大值或最小值点，不能很好地发挥搜索性能。相对于传统搜索方法，遗传算法能够在同一时间自如地处理多个个体，并且在同一时间对搜索空间中的多个解进行评估，具备较好的全区域搜索性能，遗传算法的这种优点是传统搜索方法无法比拟的。

（3）不需要辅助信息。遗传算法只利用适应度函数的解就可以对基因个体进行评估，然后开展遗传相关的操作。同时，此适应度函数的定义域可以随意设置，且不会受到连续可微的限制。米顺强(2004)[34]认为，适应度函数唯一的要求是，编码必须与可行解区间对应，不能有死码，也就是遗传算法交叉操作中会发生非“完全性”的情况。由于限制条件的缩小，使得遗传算法的应用范围大幅扩展。

（4）内在启发随机搜索特性。遗传算法的搜索方向遵循的是几率规则而非确定性规则，这里所提到的几率演变为一种工具，引导遗传算法的搜索方向，使其向着实现搜索空间更加优化的区域移动。

（5）能找到全域最优解。遗传算法与普通求解方法很大的不同在于，它不会使搜索陷入局部最优，即便在不规则与不连续的复杂空间中，遗传算法也能在搜索过程中找到全域最优解。

15

山东科技大学工程硕士学位论文相关理论分析

遗传算法搜索到近似全局最优解全局最优解多个峰值局部最优解图2.3遗传算法与全域解

Figure2.3Geneticalgorithmandthewholedomainsolutions

（6）能快速求解复杂问题。遗传算法通过自然进化机制来表现相对比较复杂的现象，能够将复杂问题简单化，同时将问题迅速地求解出来。2.4.3遗传算法理论与应用

遗传算法擅长解决的问题是全域最优化问题，它能够跳出局部最优而找到全域最优点。遗传算法其实是一种求函数极值的随机搜索算法，但它又不是毫无规则地随机搜索，而是基于一种假设：假设函数值的分布是有一定的连续性的，换句话说函数的极值出现在一个较优值附近的概率要大于出现在一个较差值附近的概率。基于这个假设，遗传算法总是以较大概率保留较优值所代表的搜索方向，而以较低概率保留较差值所代表的搜索方向。这并不是说不去搜索较差值的附近区域，只是搜索的概率较低而已。

张松艳(2009)[35]针对群体的进化收敛性提出了下面几种策略：第一，在开始阶段，尽量保持较小的选择压力，同时尽可能地保持原始的群体规模，最大程度地发挥重组能力，避免一些欺骗问题的出现，从而避免较早陷入局部最优解；第二，在中期阶段，可保持较大的选择压力以及较小的群体规模，同时尽可能保持非常高的变异概率。另外，也可以采用非线性变换方式，利用交叉操作数来避免可能会发生的模式欺骗问题，同时摆脱陷入局部最优解的困境；第三，在后期阶段，应当尽可能地保持较大的选择压力和较小的群体规模，以有效地促进GA局部搜索，从而更快地寻找到全域最优解，尽快完成模型求解任务。

遗传算法已经在许多领域得到了广泛应用，已被公认为是一种全域搜索能力强、搜

16

山东科技大学工程硕士学位论文相关理论分析

索效率高的算法。分别介绍如下：

周辉仁，唐万生，魏颖辉(2009)[36]针对所有旅行商最小完成时间的多旅行商一类问题，用遗传算法进行优化，且提出了矩阵译码方法，种群规模为100；最大反复运算次数为800，以距离非对称的多旅行商问题的实例进行了模拟。

陶琳康(2008)[37]透过遗传算法，解决现有饲料配方设计中由纯数学思维算法本身局限性所产生的不足。同时以实数编码解决用标准遗传算法在计算饲料配方时易产生早熟现象，以及局部寻优能力差等问题，特别是在原料多，约束条件多的情况下，这种缺点表现的更为明显。

谢秉磊，李军，郭耀煌(2010)[38]将货运量约束和时间窗约束转化为目标限制，设计了基于自然数编码的可同时处理软、硬时间窗约束的遗传算法，同时，在使用遗传算法求解时，采用惩罚的方法来处理一些限制。也就是说，若某个染色体所对应的解超出了规定的限制，要根据违法规定的程度给予惩罚，从而保证适应度。这种惩罚的方式有助于一些非可行解进入群体，同时也能够使得群体中的染色体数量保持在一个相对稳定的状态，从而保证遗传算法的顺利进行。

李轶舜，徐建闽，徐鹏(2008)[39]透过遗传算法来求解VRP问题，对初始种群的设计采用扇区扫描法搜索初始种群；并对叉操作数进行创新改进，群体规模根据试算染色体个数取20～40对问题进行求解。将货运量限制和时间窗限制转化为目标限制，设计了基于自然数编码的可同时处理软、硬时间窗约束的遗传算法，实验分析肯定它们是全域满意解。对于解决有时间窗的VSP这类组合优化问题，遗传算法无疑是一种性能优良的方法。

张庆华，刘新力，刘魁(2008)[40]考虑车辆数和行驶距离两种优化目标，提出了解决VRPTW问题的一种改进遗传算法。在算法中，通过对交叉操作数改进，增加了算法的寻优能力，同时又克服了算法对群体多样性的要求；针对遗传算法局部搜索能力弱的问题，加入了2-opt局部搜索方法，弥补了遗传算法的不足。

MetropolisN,RosenblattA,RosenblattM等(2008)[41]用遗传算法求解第三方物流企业物流配送中带时间窗的车辆路径问题，建立了一个配送优化调度模型，使配送计划的编制在任何情况下都能归约为求解某种车辆路径问题。

KirkpatrickS.,GelatoJr.C.D（2003）

[42]

为了满足卫星制导炸弹大着地角的弹道要

求，基于遗传算法进行了次最优制导律的设计。建立了卫星制导炸弹运动状态方程，利用设计所得的制导律进行了卫星制导炸弹六自由度全弹道模拟，与使用比例导引律的计

17

山东科技大学工程硕士学位论文相关理论分析

算进行了比较，弹着角增加了60%，效果显著。最后并指出由于遗传算法对问题的种类具有鲁棒性，该方法可以应用于各种带限制条件的次最优制导律的设计。

HopfieldJ.,TankD（2005）[43]认为，多目标遗传算法相较于多目标决策方法来讲具有更多优点，主要包括以下几个：首先，多目标遗传算法具有一般遗传算法的有点，而且对目标函数的要求已较低；其次，多目标遗传算法采用排序矩阵来确定群体中个体的适应度，因此可以避免不同目标之间的比较问题，使问题简单化；第三，多目标遗传算法不用经过约束转化、引入系数等步骤，可直接求出近似非劣解集，相对于其他的算法来讲，大大简化了多目标问题求解的复杂度。2.4.4遗传算法步骤

遗传算法有效性的理论依据为－模式定理(SchemaTheorem)[44]和积木块假设(BuildingBlockHypothesis)(Holland1975,Goldbery1989)[45]。以二进制串作为编码方式讨论模式定理，通过分析遗传算法的三种基本遗传操作对模式的作用来讨论模式定理，不仅保证了算法的较优解样本按照指数级来成长，而且满足了遗传算法得出最优解的必要条件。根据积木块假设理论，遗传算法根据短定义距、低阶与高平均适应度的运行模式，使个体之间相互结合，从而保证最后寻找到全域的最优解。

遗传操作数是决定算法好坏的重要的因素之一。遗传操作数包括交叉，选择和变异。基本遗传算法可表示为：SGA=(C,E,P0,M,Φ,Γ,ψ,T)，式中：

C－个体的编码方法；E－个体适应度评价函数；PO－初始种群；

M－种群大小；Φ－选择运算元；Γ－交叉运算元；

ψ－变异运算元；

T－遗传终止条件。

遗传算法的核心框架的步骤如下：（1）初始化群体

在进行遗传算法操作前，需要产生一个由若干个初始解组成的初始种群，而种群的

18

山东科技大学工程硕士学位论文相关理论分析

个体数目即是种群的大小（或规模）。初始群体是进化过程中的第一代，即初始代。在进行种群初始化时，系统会随机产生一个种群规模为M的初始群体，其中每个个体由一定长度的代码构成，该初始群体代表优化问题的部分可能解的集合。

Solomon,M.M(2007)[46]指出群体越大，则群体中个体多样性越高，遗传操作生成有意义的基因块并逐步进化为最优解的机会就越高，算法陷入局部解的危险越小。但是群体规模太大，算法的计算量、解题时间也会增加。

（2）编码

在遗传算法里，优化问题的解被称为个体，它表示为一个变量序列，叫做染色体或者基因串。染色体一般被表达为简单的字符串或数字符串，不过也有其它的依赖于特殊问题的表示方法适用，这一过程称为编码。

对于不同的问题有不同的解的形式，但要运行遗传算法就要对其进行抽象的编码，也就是确定染色体的形式，这里的染色体就是用某种特定的编码方式描述一个解，通常一个具体的解也称为个体。而多个不同的个体就组成一个种群，一个种群内有统一的编码方式。这些概念都完全等同于生物学中的概念，它们是平行的。

Solomon,M.Defrosters(2008)[47]透过有限马可夫链与齐次马氏链对GA的收敛性分析，证明SGA(SimpleGeneticAlgorithm)有可能发现全域最优解。并得出早熟现象的直接原因是模式丢失，保持种群的多样性是减少早熟的关键。归纳出在GA操作中应遵循的原则：在提高选择压力的同时，确保个体的多样性；在交叉操作中引入引导进化的准则，使交叉操作既能开辟新的搜索空间，同时又保证优良个体的延续性，这是改进GA搜索性能的关键。

目前的几种常用的编码技术有二进制编码，实数编码（浮点数编码），字符编码等编码方式：

①二进制编码：由0和1所组成的二值符号集｛0,1｝，其构成的基因是一个二进制编码符号串。

基因二进制编码

01

2

3

4

5

6

11011101001110010

②实数编码：是指个体的每个基因值用某一范围内的一个实数来表示。

基因实数编码

1100

2200

350

490

580

670

③字符编码：指个体染色体编码串中的基因值取自一个无数值含义、而只有代码含

19

百度搜索“77cn”或“免费范文网”即可找到本站免费阅读全部范文。收藏本站方便下次阅读，免费范文网，提供经典小说综合文库宜生乳业冷链物流配送方案优化设计 - 图文(6)在线全文阅读。