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

第四章基于遗传算法的集装箱多式联运运输组合优化模型

的求解

4.1 遗传算法简介

4.1.1 遗传算法

遗传算法(Genetic Algorithm,GA)是在20世纪六七十年代由美国密歇根大学的Holland J.H.教授及其学生和同事在研究人工自适应系统中发展起来的一种随机搜索方法,通过进一步的研究逐渐形成了一个完整的理论和方法体系取名为基本遗传算法(Simple Genetic Algorithm)。在接下来几年的研究过程中Holland在研究自然和人工系统的自适应行为的过程中采用了这个算法，并在他的著作《自然系统和人工系统的适配》中对基本遗传算法的理论和方法进行了系统的阐述与描写，同时提出了在遗传算法的理论研究和发展中具有极为重要的作用的模式理论，它的编码技术和遗传操作成为了遗传算法被广泛并成功的应用的基础，经过许多学者多年来的研究，遗传算法逐渐成熟起来，到现在已经成为了一个非常大的体系，广泛的应用于组合优化、系统优化、过程控制、经济预测、模式识别以及智能控制等多个领域。De Jong于1975年在他的博士论文中设计了一系列针对于各种函数优化问题的遗传算法的执行策略，详细分析了各项性能的评价指标。在此基础上，美国伊利诺大学的Goldberg于1989年系统全面的阐述了遗传算法理论，并通过例证对遗传算法的多领域应用进行了分析，为现代遗传算法的研究和发展奠定了基础。

遗传算法是一种模仿基于自然选择的生物进化过程的随机方法，它以类似于基因的编码作为种群的个体，首先，随机的产生初始种群的个体，从这个群体开始进行搜索，根据类似于生物适应能力的适应度函数值的大小，按照不同问题各自的特点，在当前的种群中运用适当的选择策略选择适应能力大的个体，其中所选择出来的个体经过遗传操作、交叉操作以及变异操作产生下一代种群个体。如此反复，像生物的进化过程一样逐代进化，直到满足期望的终止条件为止。

4.1.2遗传算法的基本结构

遗传算法是由种群、染色体、适应度函数三个基本要素所组成的，其中种群是由作为个体的染色体组合而成的，适应度函数是对解的优劣程度进行评价的一个函数。遗传算法不同于其他搜索算法之处在于，它的搜索过程中的每一步操作都是对整个种群进行的搜索，然后再按照每个染色体被选为优质个体的概率重新安排个体在种群中的顺序，最后根据优胜劣汰、适者生存的生物进化原理对种群进行演化操作，这时候，首先需要根据个体的适应度函数从当前的种群中挑选出相对优等的染色体，其中个体被选择的概率是根据适应度函数来确定的，对选择出来的优质个体，通过一定的交叉、变异操作产生新的个体，其中，交叉操作是对已选出的优等染色体编码进行位置的互换，变异操作是对某一染色体上某个编码位置进行随机的变化。经过选择、交叉、变异操作之后，新产生的一些染色体构成了新的种群。

遗传算法的实现过程主要包括编码、初始化种群、适应度计算、选择、交叉、变异等六个主要的遗传操作。利用遗传算法对问题进行求解的流程如图4.1所示，具体操作步骤如下所述：

图4.1遗传算法的过程

第一步，确定种群（population）的规模。首先根据特定问题的大小以及可行解的多少确定合适的种群规模，也就是在应用遗传算法求解问题时初始种群中个体的数量。

第二步，对个体进行编码，产生初始种群。编码是遗传算法进化过程的基础，影响着算法的搜索能力、种群的多样性等性能。在对个体编码的时候需要根据特定问题的具体特点确定适当的编码方法，如二进制编码、浮点数编码、字符编码等编码方法（如二进制编码、浮点数编码、字符编码等编码方法），随机地产生由可行解组成的初始种群，这是应用遗传算法进行优化求解的开始，然后，该算法会通过一些模拟生物进化过程中的优胜劣汰规律的操作，包括遗传操作、选择操作、交叉操作、变异操作（包括遗传操作、选择操作、交叉操作、变异操作），得出种群中的最优个体，即为问题的最优解。

第三步，设计适应度函数（fitness function）。适应度函数是用来计算群体中的个体对环境的适应程度的函数，适应度值在遗传算法中表示个体被遗传到下一代种群的概率大小，它是个体进化的主要依据。个体的适应度值是用来对种群中的每个染色体的优劣程度进行评价的唯一依据，对种群的操作包括选择、交叉、变异等操作都是根据个体的适应度值来进行的。一般来说，适应度值越大，遗传到下一代的可能性就会越大，在求得个体的适应度值之后，一般都会将个体按照适应度值进行排序，以便于下一步所进行的选择操作。

第四步，选择操作（selection）。在对种群进行个体的选择之前，首先确定在进行选择的时候所根据的规则和方法，选择操作一般以将个体的适应度值作为依据，按照所选定的选择方法从当前的种群中选出适应度高的优质个体，作为进行下一代遗传操作的种群中的父代进一步繁殖子孙。遗传算法中的选择操作在本质上就是一种优胜劣汰的操作，选择操作所依据的原则是适应性强，即为个体为下一代的贡献能力大。

第五步，交叉操作（crossover）。交叉操作是对两个父代染色体的部分结构进行替换重组生成新的个体的运算过程，是遗传算法中产生新的个体的重要方式。具体的操作过程是这样的，首先将已经选择出来的个体，按照一定的方法搭配成对，以一定的交叉概率对每一对染色体中的部分基因进行交换重组，产生可

以描述父辈个体特性的新个体。

第六步，变异（mutation）操作。变异操作本身是一种局部随机搜索方法，其目标是保持种群个体的多样性，保证遗传算法的有效性。具体操作过程是将从群体中随机选出来的某一个个体按照一定的变异率对其染色体结构中的某个或某几个串值进行随机的改变产生新的个体，保持个体的多样性。

第七步，判断终止的条件。如果个体达到了运算终止的条件，那么该搜索过程也就完成了，然后输出群体中具有最大适应度值的个体，这就是问题的最优解，到此整个遗传算法的搜索过程也就结束了，如果没有达到终止条件，则对第二步到第六步迭代执行。

4.1.3 遗传算法的优势

1975年Holland提出并研究遗传算法主要有两个目标：第一是用简单的位串编码的形式来实现对各种复杂的结构的表示；第二要通过简单的变换来改进这种复杂的结构。遗传算法是一种具有运算速度快、容错性强、有较强的鲁棒性的、简便的随机搜索算法，在求解并优化各类结构对象的过程中优势显著。相比传统的枚举法、启发式算法、搜索方法等主要的优化算法而言，遗传算法具有以下六大优势：（1）遗传算法具有自组织性、自适应和自学习性。在运用遗传算法对问题进行求解的时候，算法将利用已经确定的编码方案、适应度函数自己组织进化过程对问题的解进行搜索，在进化的过程中按照一定的概率进行基因重组和基因突变等遗传操作。遗传算法的这种特性使得该算法能够根据环境的变化自动的发现规律；（2）传算法是以决策变量的编码为其运算对象的。因此，算法才能够根据染色体和基因的原理通过模拟生物的遗传进化过程来完成问题的求解和优化过程；（3）并行性。遗传算法在本质上是并行性的。遗传算法是按照并行的方式对种群进行搜索，主要表现在两方面，一是内在并行性（inherent parallelism）遗传算法适合大规模的并行运算。可以先让多台计算机各自进行独立的种群进化计算，各自运算完成后相互之间才进行通信比较以选择最佳的个体，二是内含并行性（implicit parallelism）遗传算法的种群方式搜索，能够同时对解空间内的多个区域进行搜索，在搜索的过程中相互交流信息，这种并行方式极大的降低了遗传算法计算过程的时间复杂度；（4）算法简单。遗传算法无需进行求导、求微积分或者其他的辅助运算等数学方面的要求，而是直接以目标函数和所确定的适应度

函数为方向进行搜索，而且遗传算法可以直接应用于问题的求解过程；（5）遗传算法对问题的求解，产生的可以是一个最优解，也可以是多个潜在解，因此问题最终的解是可以由使用者根据具体的情况进行选择确定的。（6）遗传算法适用范围广泛，任何形式的目标函数，包括单目标和多目标函数，和约束条件都可以运用遗传算法来求解。

4.1.4 遗传算法的应用

由于遗传算法具有以上所述的种种优势，同时遗传算法作为一种全新的搜索与优化方法，广泛的应用于很多的学科领域，尤其是在对复杂系统的简单化及优化操作上。最近这几年里，由于遗传算法对问题的具体领域没有什么特别的要求，其在函数优化、组合优化、机器人智能控制、生产调度问题等不同的领域都得到了成功的应用。

（1）函数优化。

函数优化作为遗传算法的经典应用领域，是评价遗传算法性能的最常用的算例，如今各种复杂形式的函数被许多的学者构造出来作为测试函数用来对遗传算法性能进行评价。既有连续函数、凸函数、确定函数，也包括离散函数、凹函数、随机函数等。在运用遗传算法对非线性、多目标、多模型的函数优化问题进行求解会比其他优化算法更方便、简单并且能够得到更好的解。

（2）组合优化

组合优化问题是运筹学的一个经典分支，它是采用数学方法对一个离散问题进行求解寻找最优分组、筛选或次序等，这类问题的搜索空间会随着问题规模的变大而迅速的增大，因此用枚举法等传统的优化算法求解会比较困难，甚至可能得不到精确的最优解。而采用遗传算法可以得到令人们满意的解，求解起来也比较简单、方便。实践证明，在求解组合优化问题中的NP完全问题时是非常有效的，比如说在对旅行商问题、装箱问题、背包问题等问题进行求解中都已经取得了非常好的效果。

（3）机器人智能控制

遗传算法本身就是起源于对人工自适应系统的研究过程中，因而机器人智能控制也就理所当然地成为了遗传算法的一个重要应用领域。目前，遗传算法已经广泛应用在移动机器人的路径规划方面、关节的运动轨迹、细胞机器人的结构优

化和行动协调等方面。

（4）生产调度问题

当前的生产调度问题主要根据调度人员的经验安排的，一般的调度问题的数学模型都很难求得精确的最优解。即使通过一系列的简化运算能够求解模型，但是太多的简化容易使所得到的结果与实际问题有很大的差距，导致模型与实际不相符合，然而在采用了遗传算法这个计算机工具后，这些复杂的问题也能够在有效地时间里求得满意解，遗传算法的出现与完善极大的简化了对车间调度、流水线生产、任务分配以及生产规划等方面问题的求解，为现实生产生活中的调度问题提供了参考依据。

除此之外，遗传算法也已经被广泛应用于自动控制、图像处理与模式识别、医学工程、人工生命等生产生活的各个方面，并取得了较大的成果，提高了生产效率，进一步提高了经济效益。

4.2 基于遗传算法的多式联运组合优化模型求解设计

遗传算法的搜索过程是从随机产生的一个种群开始的，其中，种群是由问题可行解所组成的，在种群中被称为染色体，它是由多个基因组成的一个集合。在搜索的过程中，根据优胜劣汰、适者生存的进化原理，逐代演化以得到越来越好的近似最优解，在每一代中用来评价染色体用来评价染色体好与不好的标准是适应度值，这也是用来选择进入下一代遗传的个体的依据，一般的适应度值高的染色体被遗传到下一代中的概率相对比较高。然后被选出来的染色体两两配对进行交叉和变异运算，生产组成新一代种群的新染色体，称为后代。如此反复进行，初始种群在经历了若干代的进化后，遗传算法会逐渐的收敛到适应度值最高、最接近于问题最优解的染色体，这个染色体便可以当作是问题的近似最优解或者是满意解。

4.2.1 染色体编码设计

对问题的解进行编码表示是运用标准遗传算法求解的关键问题。最初为了便于使用计算机进行运算，大都是采用0-1串的编码方法，近几年来，随着遗传算法被应用到求解各种具有不同要求的问题中去，许多学者提出了多种非0-1串的编码方法，如约束优化问题中的实数编码，组合优化问题的整数编码以及浮点数

编码等编码方法。为可行解选择适当的编码表示方法是应用遗传算法求解实际问题的前提条件，对于所有的应用问题，在应用遗传算法进行求解的时候，都要把解的编码表示方法与适用于该问题的遗传操作方法相结合起来进行考虑，设计适用于具体问题的编码方法和遗传操作对问题进行优化求解。

在该多式联运运输组合优化问题中，问题涉及到运输路径中区段运输的运输方式和进行转运换装的节点两部分，因此在对染色体进行编码的时候应该将这两种不同的因素同时作为染色体中的基因。故而在求解该多式联运组合优化模型问题的遗传算法中，其染色体由一系列的城市节点和区段运输方式序列共同组成的，其中，序列中的第，位表示该序列的总长度，奇数位表示的是在一个运输方案中所经过的节点的信息，而偶数位则表示在该运输方案中，在该偶数位前后两个节点之间进行区段运输时所采用的运输方式的信息。如图4.2所示为对一种运输方案进行编码表示的示例。

图4.2运输路径以及其编码方式

在应用遗传算法求解多式联运组合优化模型的编码过程中，要求每个个体的染色体编码中不允许有重复的节点基因码，也就是说在染色体编码的偶数位上不允许有相同的基因存在，这是为了保证在同一个运输方案中，任何一个城市节点在已经选择的路径方案中只能被经过一次。在该编码方法中，任何一个染色体编码的第1个位置（位置编号从0开始）总是源节点S，最后一个位置是目的节点D，染色体的长度不是固定的，是可变的，但是其长度不可能超过最大长度2N （N个节点，N-1条路径上的运输方式，一个0位的染色体长度）。

在该多式联运模型中，具体的编码过程如下，染色体编码的第1位基因（节点）是货物的源节点S ，从节点S 开始，第3位置基因是从与源节点通过某种方式相连接的其他节点中随机的选择的，其中第2位置基因则表示的是在这第1位节点与第3位节点之间进行区段运输时所采用的运输方式，它是从在该两个节点之间允许的运输方式中随机选择的，然后将选择的节点的信息从网络图的结构信息中删除，以避免重复选择，这样将该过程重复下去，直到达到目的节点。如此便生成了第一个染色体，重复进行该过程，便可以得到一系列的染色体个体，组成一个初始种群。

4.2.2 适应度函数设计

遗传算法的进化搜索过程是以每个个体的适应度值为选择依据的，基本上不利用外部的信息，因而适应度函数在遗传算法中具有非常重要的作用，它的好坏对算法的收敛速度以及能否得到最优解均具有直接的影响。一般地，对目标函数做一些相应的变换便能够容易的得到一个比较简单的适应度函数。最常用的适应度函数基本上有如下3种：

（1）直接将目标函数作为适应度函数。这是最简单最直观的适应度函数。但是这种适应度函数存在两个不足之处，一是适应度函数可能为正值也可能为负值，这样在采用轮盘赌方法进行选择时，可能会出现不满足条件的意外，二是有些目标函数在其值域上可能相差很大，在这种情况下得到的平均适应度值，可能体现不出来种群的真实平均性能，影响了遗传算法的整体性能。

（2）界限构造法。这种适应度函数设计方法首先要对目标函数的最值进行预先的估计，对于求最小值的问题要估计其上限，而求最大值的问题需要估计其下限。界限构造法是对前一种方法的改进，但是有些具体的问题可能很难估计其界限值，因而也有一定的局限性。

（3）改进的界限构造法。首先对目标函数的上下界限进行保守的估计。然后根据保守估计值设计适应度函数。

在以个体的适应度值来为参考标准对群体进行搜索时，适应度值越大被选择遗传到下一代的概率就更大。在该多式联运路径组合优化模型中，为了简化运算，采用以每一个运输方案的整个过程中的总运输费用的倒数作为适应度函数。假设初始种群的大小为：P=｛12,u p p p ，…｝，其中i p 其中只表示的是代表某一个运输

方案的染色体编码，()i z p 表示染色体i p 所的总代价值，因此，定义染色体i p 的适度函数为：

1

()()i i fitness p z p =。 4.2.3 选择运算

选择操作是用来确定父代种群中哪些个体能够以多大可能性被选中并遗传到下一代的进化操作。选择操作一般要包含两个阶段，第一是计算每个个体的适应度值，即根据所选择的个体适应度函数，计算出来每个个体的适度值，第二是根据所确定的选择方法对染色体进行选择。

在对多式联运组合优化模型进行求解的选择方法进行设计之前，首先介绍最常用的基本的选择算法。

（1）轮盘赌选择法。这种选择方法是比较简单的一种方法，它根据个体的适应度值、随机产生的选择概率以及累积概率通过多轮选择，确定进入下一代的个体。

（2）随机遍历抽样法。应用这种选择方法对个体进行选择的时候，首先需要随机的选择第一个位置，然后根据已确定的间隔等距离的从种群中选择个体。

（3）局部选择法。在这种选择算法中，首先将当前待搜索的种群按照一定的原则划分成若干个局部的小种群，个体之间的交配只在个体所在的小种群内部进行，为了保证所有的个体直接能够交换信息，不同的小种群之间要有一定的重叠性。

（4）截断选择法。这是一种适用于大种群的人工选择算法。这种选择方法首先将个体按照适应度值进行排序，根据截断阈值、选择强度对种群中的个体进行选择。

在应用遗传算法对该多式联运运输组合优化问题进行求解时，该问题的目标函数就是为了寻求一个满足约束条件的最小的成本值，因此我们采用改进的截断选择方法，在此，确定选择的规则是适度值大的被选择出来作为下一代种群的父代，继续进行运算。因此，首先需要按照染色体的适度值从大到小排列顺序，即：12()()()u fitness p fitness p fitness p ≥≥≥… 4-（2）

这样，适度值比较大的个体就是我们所需要的，这些能够被优先选择作为下

一代种群的父代来继续进行运算，其中，每一个个体被选择的概率和染色体的适度函数值成正比例，即个体的适度值越大，被选择的概率就会越高。在进行选择的过程中，如果出现了两个相同的染色体，那么只需要保留一个染色体即可，将另外一个染色体删掉，重复这个过程以选择新一代的染色体个体。

4.2.4 交叉运算

交叉操作也被称为基因重组，是指把从种群中选取出来的两个父代个体的部分结构按照一定的规则相互替换重新组合，产生两个新的个体。交叉操作是遗传算法中产生新的优等个体的最重要的手段，通过个体交叉操作而产生的两个新个体，同时包含着两个亲代个体的遗传基因，但又与亲代个体不完全相同。因此，交叉操作使得遗传算法的搜索能力得以飞跃的提高。

常用的交叉操作方法有：实值重组（包括离散重组、中间重组、线性重组）、二进制交叉（有单点交叉、多点交叉、均匀交叉）、部分匹配交叉、顺序交叉、洗牌交叉等多种交叉方法，在具体应用时需要根据特定问题的具体特点选择适合的交叉方法完成基因的重组，使得种群向着多样化发展，进而使搜索能够到达更多的个体，使最后的得到的解是最优的。

在该多式联运路径运输组合优化问题中，交叉不同于传统的单点交叉，两个染色体选择一个公共的节点基因（除第一个节点和最后一个节点外）作为交叉基因，该节点不依赖于节点在路径中的位置，当有两个以上的公共节点时，只需要选择其中一个作为交叉点即可，通常选择第一个公共点进行交叉。如果不存在公共的基因节点，那么将两个父代个体作为子代个体遗传到下一代中。

如图4.3所示为染色体交叉处理过程示例：

图4.3染色体交叉的处理过程

4.2.5 变异运算

变异运算是在选择和交叉操作之后进行的，它是在染色体上以一个很小的概率或步长随机产生的基因变化。变异能够提供初始种群中没有的基因，或者是找回在进行选择操作时所丢失的基因，为种群补充新的基因，防止基因丢失现象的出现。一般的变异概率都是一个很小的随机数，与种群的规模没有关系。变异是一种局部随机搜索方式，它与选择操作相结合，共同保证遗传算法的有效性和多样性，避免了非成熟收敛现象的出现。变异操作依赖于具体的染色体编码方式，一般有两种最常用的方式：实值变异和二进制变异。

如图4.4所示为在该多式联运运输组合优化问题中染色体变异操作的处理过程。首先从染色体中随机的选择一个基因（比如2v）作为变异点，保持从源节点到变异点的基因不改变，而变异点之后的基因是从与该变异点相连接的节点中随

机选择的，选择方法同染色体编码过程，直到到达目的节点为止。

图4.4染色体变异的处理过程

4.3 算例分析

4.3.1 已知条件

假设有一批货物需要从一个城市运往到另一个城市，在这两个城市之间存在着多条运输路线、多种运输方式供联运经营人从中选择，不同的运输方式之间进行转运时需要一定的转运时间和转运成本，而且转运只能在城市节点进行而不能在运输途中完成。

我们以一个具有6节点的运输网络为例，如图4.5所示：从源节点S 有一批运量为q 的集装箱货物计划运输到目的城市D ，在运输途中需要经过若干城市并通过一定的运输方式进行组合运输，以将货物送达目的城市D 。其中允许经过的城市有1234v v v v 、、、四个城市各个城市之间允许的运输路线以及运输方式如图

4.5所示，每条连接两个节点的线段代表了再这两个节点之间存在着该种运输方式可以直达运输，该网络图中共有18条直达运输路线（包括公路运输、铁路运输、水路运输三种不同方式的运输路线）。

图4.5运输网络图

表4.1给出了运输网络中所存在的路径以及不同路段上的不同运输方式的运输单价、单位距离的运输时间以及运输能力；表4.2给出了在每个城市进行不同运输方式之间进行转运换装时的转换单价以及转换时间。

表4.1各个城市之间运输单价、单位距离的运输时间及运输能力

注：运输单价的单位是：元/t?km运输时间的单位是：h/1000km,运输能力的

单位是:t

表4.2每个城市进行不同运输方式转换的中转费用和中转时间

注:a/b,a 表示单位量的中转费用,单位:元/t;b 为单位量的中转时间,单

位:h/1000t

4.3.2 仿真结果

对于上文所设计的运输费用模型,运用C#进行编程,假设货运量分别为:q=850t 和q=1000t ，要求的运输时间分别为18.5小时和19小时，进行仿真计算，迭代次数设置为150次，种群的规模为40，按照网络图4.5作为交通网进行仿真计算并求解，得出计算结果分别为：

4.4 本章小结

本章首先对基本遗传算法的结构、特点以及应用进行了简单的介绍，然后根据集装箱多式联运组合优化问题的具体特点，结合着本文中所建立起来的多式联运运输方式与运输路线组合模型，详细叙述了本文所使用的改进的遗传算法的具

体的各个遗传操作的算法，包括染色体的编码设计、适应度函数的选择、选择操作的依据、交叉运算的操作方法、变异算法的操作过程等，并对一个仿真的运输网络算例应用文中的多式联运运输方式和运输路线组合模型采用改进的遗传算法进行了仿真求解，从算例中得出的结果我们能够看出，该改进的遗传算法采用了非固定长度的染色体对问题进行编码并进行各种遗传操作，改变了传统的遗传算法只能使用固定长度的染色体编码对问题进行求解的限制，而且该改进的遗传算法可以在比较短的时间里求得相对比较满意的结果，为多式联运经营人合理的安排运输路线和选择运输方式提供了一定的依据，为后续的研究工作提供了一定的参考。

MATLAB实验遗传算法和优化设计

实验六 遗传算法与优化设计 一、实验目的 1. 了解遗传算法的基本原理和基本操作（选择、交叉、变异）； 2. 学习使用Matlab 中的遗传算法工具箱(gatool)来解决优化设计问题； 二、实验原理及遗传算法工具箱介绍 1. 一个优化设计例子 图1所示是用于传输微波信号的微带线(电极)的横截面结构示意图，上下两根黑条分别代表上电极和下电极，一般下电极接地，上电极接输入信号，电极之间是介质(如空气，陶瓷等)。微带电极的结构参数如图所示，W 、t 分别是上电极的宽度和厚度，D 是上下电极间距。当微波信号在微带线中传输时，由于趋肤效应，微带线中的电流集中在电极的表面，会产生较大的欧姆损耗。根据微带传输线理论，高频工作状态下（假定信号频率1GHz ），电极的欧姆损耗可以写成（简单起见，不考虑电极厚度造成电极宽度的增加）： 图1 微带线横截面结构以及场分布示意图 {} 28.6821ln 5020.942ln 20.942S W R W D D D t D W D D W W t D W W D e D D παπππ=+++-+++?????? ? ??? ??????????? ??????? (1) 其中πρμ0=S R 为金属的表面电阻率， ρ为电阻率。可见电极的结构参数影响着电极损耗，通过合理设计这些参数可以使电极的欧姆损耗做到最小，这就是所谓的最优化问题或者称为规划设计问题。此处设计变量有3个：W 、D 、t ，它们组成决策向量[W, D ,t ] T ，待优化函数(,,)W D t α称为目标函数。 上述优化设计问题可以抽象为数学描述： ()()min .. 0,1,2,...,j f X s t g X j p ????≤=? (2)

遗传算法与组合优化.

第四章 遗传算法与组合优化 4.1 背包问题（knapsack problem ） 4.1.1 问题描述 0/1背包问题：给出几个尺寸为S 1，S 2，…，S n 的物体和容量为C 的背包，此处S 1，S 2，…，S n 和C 都是正整数；要求找出n 个物件的一个子集使其尽可能多地填满容量为C 的背包。 数学形式： 最大化 ∑=n i i i X S 1 满足 ,1C X S n i i i ≤∑= n i X i ≤≤∈1},1,0{ 广义背包问题：输入由C 和两个向量C ＝(S 1，S 2，…，S n )和P ＝(P 1，P 2，…，P n )组成。设X 为一整数集合，即X ＝1，2，3，…，n ，T 为X 的子集，则问题就是找出满足约束条件∑∈≤T i i C X ，而使∑∈T i i P 获得最大的子集T ，即求S i 和P i 的下标子集。 在应用问题中，设S 的元素是n 项经营活动各自所需的资源消耗，C 是所能提供的资源总量，P 的元素是人们从每项经营活动中得到的利润或收益，则背包问题就是在资源有限的条件下，追求总的最大收益的资源有效分配问题。 广义背包问题可以数学形式更精确地描述如下： 最大化 ∑=n i i i X P 1 满足 ,1C X S n i i i ≤∑= n i X i ≤≤∈1},1,0{ 背包问题在计算理论中属于NP —完全问题，其计算复杂度为O (2n )，若允许物件可以部分地装入背包，即允许X ，可取从0.00到1.00闭区间上的实数，则背包问题就简化为极简单的P 类问题，此时计算复杂度为O (n )。

4.1.2 遗传编码 采用下标子集T 的二进制编码方案是常用的遗传编码方法。串T 的长度等于n(问题规模)，T i (1≤i ≤n )＝1表示该物件装入背包，T i ＝0表示不装入背包。基于背包问题有近似求解知识，以及考虑到遗传算法的特点（适合短定义距的、低阶的、高适应度的模式构成的积木块结构类问题），通常将P i ，S i 按P i /S i 值的大小依次排列，即P 1/S 1≥P 2/S 2≥…≥P n /S n 。 4.1.3 适应度函数 在上述编码情况下，背包问题的目标函数和约束条件可表示如下。 目标函数：∑==n i i i P T T J 1 )( 约束条件：C S T n i i i ≤∑=1 按照利用惩罚函数处理约束条件的方法，我们可构造背包问题的适应度函数f (T )如下式： f (T ) = J (T ) + g (T ) 式中g (T )为对T 超越约束条件的惩罚函数，惩罚函数可构造如下: 式中E m 为P i /S (1≤i ≤n )i 的最大值，β为合适的惩罚系数。 4.2 货郎担问题（Traveling Salesman Problem ——TSP ） 在遗传其法研究中，TSP 问题已被广泛地用于评价不同的遗传操作及选择机制的性能。之所以如此，主要有以下几个方面的原因： (1) TSP 问题是一个典型的、易于描述却难以处理的NP 完全（NP-complete ）问题。有效地 解决TSP 问题在可计算理论上有着重要的理论价值。 (2) TSP 问题是诸多领域内出现的多种复杂问题的集中概括和简化形式。因此，快速、有效 地解决TSP 问题有着极高的实际应用价值。 (3) TSP 问题因其典型性已成为各种启发式的搜索、优化算法的间接比较标准，而遗传算法 就其本质来说，主要是处理复杂问题的一种鲁棒性强的启发式随机搜索算法。因此遗传算法在TSP 问题求解方面的应用研究，对于构造合适的遗传算法框架、建立有效的遗传操作以及有效地解决TSP 问题等有着多方面的重要意义。

遗传算法与优化问题(重要,有代码)

实验十遗传算法与优化问题 一、问题背景与实验目的 遗传算法（Genetic Algorithm—GA），是模拟达尔文的遗传选择和自然淘汰的生物进化过程的计算模型，它是由美国Michigan大学的J.Holland教授于1975年首先提出的．遗传算法作为一种新的全局优化搜索算法，以其简单通用、鲁棒性强、适于并行处理及应用范围广等显著特点，奠定了它作为21世纪关键智能计算之一的地位． 本实验将首先介绍一下遗传算法的基本理论，然后用其解决几个简单的函数最值问题，使读者能够学会利用遗传算法进行初步的优化计算．1．遗传算法的基本原理 遗传算法的基本思想正是基于模仿生物界遗传学的遗传过程．它把问题的参数用基因代表，把问题的解用染色体代表（在计算机里用二进制码表示），从而得到一个由具有不同染色体的个体组成的群体．这个群体在问题特定的环境里生存竞争，适者有最好的机会生存和产生后代．后代随机化地继承了父代的最好特征，并也在生存环境的控制支配下继续这一过程．群体的染色体都将逐渐适应环境，不断进化，最后收敛到一族最适应环境的类似个体，即得到问题最优的解．值得注意的一点是，现在的遗传算法是受生物进化论学说的启发提出的，这种学说对我们用计算机解决复杂问题很有用，而它本身是否完全正确并不重要（目前生物界对此学说尚有争议）． （1）遗传算法中的生物遗传学概念 由于遗传算法是由进化论和遗传学机理而产生的直接搜索优化方法；故而在这个算法中要用到各种进化和遗传学的概念． 首先给出遗传学概念、遗传算法概念和相应的数学概念三者之间的对应关系．这些概念如下： 序号遗传学概念遗传算法概念数学概念 1 个体要处理的基本对象、结构也就是可行解 2 群体个体的集合被选定的一组可行解 3 染色体个体的表现形式可行解的编码 4 基因染色体中的元素编码中的元素 5 基因位某一基因在染色体中的位置元素在编码中的位置 6 适应值个体对于环境的适应程度， 或在环境压力下的生存能力可行解所对应的适应函数值 7 种群被选定的一组染色体或个体根据入选概率定出的一组 可行解 8 选择从群体中选择优胜的个体， 淘汰劣质个体的操作保留或复制适应值大的可行解，去掉小的可行解 9 交叉一组染色体上对应基因段的 交换根据交叉原则产生的一组新解 10 交叉概率染色体对应基因段交换的概 率（可能性大小）闭区间[0,1]上的一个值，一般为0.65~0.90 11 变异染色体水平上基因变化编码的某些元素被改变

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

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

遗传算法和蚁群算法的比较

全局优化报告 ——遗传算法和蚁群算法的比较 某：X玄玄 学号：3112054023 班级：硕2041

1遗传算法 1.1遗传算法的发展历史 遗传算法是一种模拟自然选择和遗传机制的寻优方法。20世纪60年代初期，Holland教授开始认识到生物的自然遗传现象与人工自适应系统行为的相似性。他认为不仅要研究自适应系统自身，也要研究与之相关的环境。因此，他提出在研究和设计人工自适应系统时，可以借鉴生物自然遗传的基本原理，模仿生物自然遗传的基本方法。1967年，他的学生Bagley在博士论文中首次提出了“遗传算法”一词。到70年代初，Holland教授提出了“模式定理”，一般认为是遗传算法的基本定理，从而奠定了遗传算法的基本理论。1975年，Holland出版了著名的《自然系统和人工系统的自适应性》，这是第一本系统论述遗传算法的专著。因此，也有人把1975年作为遗传算法的诞生年。 1985年，在美国召开了第一届两年一次的遗传算法国际会议，并且成立了国际遗传算法协会。1989年，Holland的学生Goldberg出版了《搜索、优化和机器学习中的遗传算法》，总结了遗传算法研究的主要成果，对遗传算法作了全面而系统的论述。一般认为，这个时期的遗传算法从古典时期发展了现代阶段，这本书则奠定了现代遗传算法的基础。 遗传算法是建立在达尔文的生物进化论和孟德尔的遗传学说基

础上的算法。在进化论中，每一个物种在不断发展的过程中都是越来越适应环境，物种每个个体的基本特征被后代所继承，但后代又不完全同于父代，这些新的变化，若适应环境，则被保留下来；否则，就将被淘汰。在遗传学中认为，遗传是作为一种指令遗传码封装在每个细胞中，并以基因的形式包含在染色体中，每个基因有特殊的位置并控制某个特殊的性质。每个基因产生的个体对环境有一定的适应性。基因杂交和基因突变可能产生对环境适应性强的后代，通过优胜劣汰的自然选择，适应值高的基因结构就保存下来。遗传算法就是模仿了生物的遗传、进化原理，并引用了随机统计原理而形成的。在求解过程中，遗传算法从一个初始变量群体开始，一代一代地寻找问题的最优解，直到满足收敛判据或预先假定的迭代次数为止。 遗传算法的应用研究比理论研究更为丰富，已渗透到许多学科，并且几乎在所有的科学和工程问题中都具有应用前景。一些典型的应用领域如下： （1）复杂的非线性最优化问题。对具体多个局部极值的非线性最优化问题，传统的优化方法一般难于找到全局最优解；而遗传算法可以克服这一缺点，找到全局最优解。 （2）复杂的组合优化或整数规划问题。大多数组合优化或整数规划问题属于NP难问题，很难找到有效的求解方法；而遗传算法即特别适合解决这一类问题，能够在可以接受的计算时间内求得满意的近似最优解，如著名的旅行商问题、装箱问题等都可以用遗传算法得到满意的解。

TSP问题的遗传算法求解 优化设计小论文

TSP问题的遗传算法求解 摘要：遗传算法是模拟生物进化过程的一种新的全局优化搜索算法，本文简单介绍了遗传算法，并应用标准遗传算法对旅行包问题进行求解。 关键词：遗传算法、旅行包问题 一、旅行包问题描述： 旅行商问题，即TSP问题（Traveling Saleman Problem）是数学领域的一个著名问题，也称作货郎担问题，简单描述为：一个旅行商需要拜访n个城市（1，2，…，n），他必须选择所走的路径，每个城市只能拜访一次，最后回到原来出发的城市，使得所走的路径最短。其最早的描述是1759年欧拉研究的骑士周游问题，对于国际象棋棋盘中的64个方格，走访64个方格一次且最终返回起始点。 用图论解释为有一个图G=（V,E），其中V是顶点集，E是边集，设D=（d ij）是有顶点i和顶点j之间的距离所组成的距离矩阵，旅行商问题就是求出一条通过所有顶点且每个顶点只能通过一次的具有最短距离的回路。若对于城市V={v1，v2，v3，...，vn}的一个访问顺序为T=(t1，t2，t3，…，ti，…，tn)，其中ti∈V(i=1，2，3，…，n)，且记tn+1= t1，则旅行商问题的数学模型为：min L=Σd(t(i),t(i+1)) （i=1，…，n） 旅行商问题是一个典型组合优化的问题，是一个NP难问题，其可能的路径数为（n-1）！，随着城市数目的增加，路径数急剧增加，对与小规模的旅行商问题，可以采取穷举法得到最优路径，但对于大型旅行商问题，则很难采用穷举法进行计算。 在生活中TSP有着广泛的应用，在交通方面，如何规划合理高效的道路交通，以减少拥堵；在物流方面，更好的规划物流，减少运营成本；在互联网中，如何设置节点，更好的让信息流动。许多实际工程问题属于大规模TSP，Korte于1988年提出的VLSI芯片加工问题可以对应于1.2e6的城市TSP，Bland于1989年提出X-ray衍射问题对应于14000城市TSP，Litke于1984年提出电路板设计中钻孔问题对应于17000城市TSP，以及Grotschel1991年提出的对应于442城市TSP的PCB442问题。

基于遗传算法的库位优化问题

Logistics Sci-Tech 2010.5 收稿日期：2010－02－07 作者简介：周兴建（1979-），男，湖北黄冈人，武汉科技学院经济管理学院，讲师，武汉理工大学交通学院博士研究生，研究方向：物流价值链、物流系统规划；刘元奇（1988-），男，甘肃天水人，武汉科技学院经济管理学院；李泉（1989-），男，湖北 武汉人，武汉科技学院经济管理学院。 文章编号：1002-3100(2010)05-0038-03 物流科技2010年第5期Logistics Sci-Tech No.5,2010 摘 要：应用遗传算法对邯运集团仓库库位进行优化。在充分考虑邯运集团仓库所存放的货物种类、货物数量、出入库频 率等因素的基础上进行库位预分区规划，建立了二次指派问题的数学模型。利用遗传算法对其求解，结合MATLAB 进行编程计算并得出最优划分方案。 关键词：遗传算法；预分区规划；库位优化中图分类号：F253.4 文献标识码：A Abstract:The paper optimize the storage position in warehouse of Hanyun Group based on genetic algorithm.With thinking of the factors such as goods categories,quantities and frequencies of I/O,etc,firstly,the storage district is planned.Then the model of quadratic assignment problems is build,and genetic algorithm is utilized to resolve the problem.The software MATLAB is used to program and figure out the best alternatives. Key words:genetic algorithm;district planning;storage position optimization 1 库位优化的提出 邯郸交通运输集团有限公司（简称“邯运集团”）是一家集多种业务为一体的大型综合性物流企业。邯运集团的主要业务板块有原料采购（天信运业及天昊、天诚、天恒等）、快递服务（飞马快运）、汽贸业务（天诚汽贸）及仓储配送（河北快运）等。其中，邯运集团的仓储配送业务由河北快运经营，现有仓库面积总共40000㎡，主要的业务范围为医药、日用百货、卷烟、陶瓷、化工产品的配送，其中以医药为主。邯运集团库存货物主要涉及两个方面：一个是大宗的供应商货物，如医药，化工产品等；另一方面主要是大规模的小件快递货物，如日用百货等[1]。经分析，邯运集团在仓储运作方面存在如下问题： （1）存储货物繁多而分拣速度低下。仓库每天到货近400箱，有近200多种规格，缺乏一套行之有效的仓储管理系统。（2）货架高度不当而货位分配混乱。现在采用的货架高度在2米以上，而且将整箱货物直接码垛在货架上，不严格按货位摆放。当需要往货架最上层码放货物需要借助梯子，增加操作难度且操作效率较低。货物在拣货区货架摆放是以件为单位的，分拣和搬运速度较慢。 （3）拣货货架设计不当而仓储效率低下。发货前装箱工作主要由人工协同完成，出库效率低，出错率难以控制。 （4）存储能力和分拣能力不能满足需求。根据邯运集团的业务发展现状及趋势，现有的仓库储存和分拣能力远远达不到集团公司对配送业务量的需求。 当前邯运集团的货位分配主要采用物理地址编码的方式，很少考虑货位分配对仓储管理员工作效率的影响。对其进行库位优化设计不仅直接影响到其库存量的大小、出入库的效率，还间接影响到邯运集团的整体经营效益。本文对邯运集团的仓库货位进行优化时，结合考虑仓库所存放的货物种类、货物数量、出入库频率等因素，对仓库货位进行规划，以提高仓储效率。 2库位预分区规划 在进行仓库货位规划时，作如下假设： （1）货物的存放种类已知； （2）货物每种类的单位时间内存放的数量己知； （3） 每一种货物的存取频率已知。 在仓库货位优化中一个重要的环节即预分区。所谓预分区，是指没有存放货物时的分区，分区时只考虑仓储作业人员的速基于遗传算法的库位优化问题 Optimization of Storage Position in Warehouse Based on Genetic Algorithm 周兴建1,2，刘元奇1，李泉1 ZHOU Xing-jian 1,2,LIU Yuan-qi 1,LI Quan 1 （1.武汉科技学院经济管理学院，湖北武汉430073；2.武汉理工大学交通学院，湖北武汉430063） (1.College of Economics &Management,Wuhan University of Science &Engineering,Wuhan 430073,China; 2.School of Transportation,Wuhan University of Technology,Wuhan 430063,China) !!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!! 38

基于遗传算法的齿轮减速器优化设计

煤矿机械Coal Mine Machinery Vol.30No.12 Dec.2009 第30卷第12期2009年12月 0引言 工程机械中所用电动机的转速较高，为了满足工作机低转速的需要，一般在电动机和工作机之间安装减速器，用来降低电机的转速或增大转矩，减速器是一种机械传动装置，广泛地应用于运输机械、矿山机械和建筑机械等重型机械中。因此，减速器的设计非常重要。 遗传算法（GA）是模拟生物在自然界中优胜劣汰的自然进化过程而形成的一种具有全局范围内优化的启发式搜索算法。这种方法已在很多学科得到广泛的应用，为减速器的优化设计提供有力的保证。因此，本文采用遗传算法对两级齿轮减速器进行优化设计，并通过与惩罚函数法和模拟退火算法等优化方法计算结果进行比较，来探讨适合于减速器的优化设计方法。 1建立数学模型 两级齿轮传动减速器结构如图1所示。该减速器的总中心距 a∑＝［m n1z1（1＋i1）+m n2z3（1＋i2）］/2cosβ（1）式中m n1、m n2—— —高速级与低速级的齿轮法面模 数； i1、i2—— —高速级与低速级传动比； z1、z3—— —高速级与低速级的小齿轮齿数： β—— —2组齿轮组的螺旋角。 1.1设计变量的确定 在进行两级齿轮传动减速器设计时，一般选择齿轮传动独立的基本参数或性能参数，如齿轮的齿数、模数、传动比、螺旋角等为设计变量。两级齿轮传动由4个齿轮组成，分别用z1、z2、z3、z4表示，高速级的传动比由i1表示，低速级传动比由i2表示，两组齿轮组的法面模数分别由m n1和m n2表示，2组齿轮的螺旋角用β表示，由于两级齿轮传动减速器的总传动比i0，在设计时会给出具体数据，并且满足i0＝i1i2，可以得出i2＝i0/i1，可以确定独立的参数有z1、z3、m n1、m n2、i1和β。因此，可以确定该设计变量X＝［z1，z3，m n1，m n2，i1，β］T=［x1，x2，x3，x4，x5，x6］T。 图1减速器结构简图 1.2目标函数的建立 在对减速器进行优化设计时，首先要确定目标函数。确定目标函数的原则是在满足各种性能要求的前提下，使减速器的体积最小，这样设计的减速器既经济又实用，从而达到了优化的目的。要使减速器的体积最小，必须使减速器的总中心距最小。因此，以减速器的中心距最小建立目标函数为 a∑＝［x3x1（1＋x5）+x4x2(1+i0/x5)］ 6 （2）1.3约束条件的确定 为使两级齿轮传动减速器满足强度、设计变量 基于遗传算法的齿轮减速器优化设计* 吴婷，张礼兵，黄磊 （安徽建筑工业学院机电学院，合肥230601） 摘要：对两级齿轮减速器优化设计进行了分析，建立了其优化设计的数学模型，确定了优化设计的约束条件，采用遗传算法对两级齿轮减速器进行优化设计，并通过实例说明，采用遗传算法对减速器进行优化，可以得到更加优化的设计结果。 关键词：减速器；遗传算法；优化设计 中图分类号：TH132文献标志码：A文章编号：1003－0794（2009）12－0009－03 Gear Reducer Optimal Design Based on Genetic Algorithm WU Ting，ZHANG Li-bing，HUANG Lei （School of Mechanical and Electrical Engineering,Anhui University of Architecture,Hefei230601,China）Abstract:T he optimal design of a gear reducer was analyzed,the mathematic model was established, and the restriction condition was confirmed.Design of the gear reducer was optimized with genetic algorithm and the examples showed that design of the gear reducer based on genetic algorithm can gain more optimized result. Key words:reducer；genetic algorithm；optimal design *安徽省教育厅自然基金项目（2006KJ015C） 轴1轴2轴3 z1z2 z3z4 9

比较专家系统、模糊方法、遗传算法、神经网络、蚁群算法的特点及其适合解决的实际问题

比较专家系统、模糊方法、遗传算法、神经网络、蚁群算法的特点及其适合解决的实际问题 一、专家系统(Expert System) 1，什么是专家系统？ 在日常生活中大家所认知的“专家”一般都拥有某一特定领域的大量专业知识，以及丰富的实际经验。在解决问题时，专家们通常拥有一套独特的思维方式，能较圆满地解决一类困难问题，或向用户提出一些建设性的建议等。 专家系统一般定义为一个具有智能特点的计算机程序。 它的智能化主要表现为能够在特定的领域内模仿人类专家思维来求解复杂问题。因此，专家系统必须包含领域专家的大量知识，拥有类似人类专家思维的推理能力，并能用这些知识来解决实际问题。 专家系统的基本结构如图1所示，其中箭头方向为数据流动的方向。 图1 专家系统的基本组成 专家系统通常由知识库和推理机两个主要组成要素。 知识库存放着作为专家经验的判断性知识,例如表达建议、 推断、 命令、 策略的产生式规则等, 用于某种结论的推理、 问题的求解,以及对于推理、 求解知识的各种控制知识。 知识库中还包括另一类叙述性知识, 也称作数据,用于说明问题的状态,有关的事实和概念,当前的条件以及常识等。

专家系统的问题求解过程是通过知识库中的知识来模拟专家的思维方式的，因此，知识库是专家系统质量是否优越的关键所在，即知识库中知识的质量和数量决定着专家系统的质量水平。一般来说，专家系统中的知识库与专家系统程序是相互独立的，用户可以通过改变、完善知识库中的知识内容来提高专家系统的性能。 推理机实际上是一个运用知识库中提供的两类知识,基于木某种通用的问题求解模型,进行自动推理、 求解问题的计算机软件系统。 它包括一个解释程序, 用于决定如何使用判断性知识推导新的知识, 还包括一个调度程序, 用于决定判断性知识的使用次序。 推理机的具体构造取决于问题领域的特点,及专家系统中知识表示和组织的方法。 推理机针对当前问题的条件或已知信息，反复匹配知识库中的规则，获得新的结论，以得到问题求解结果。在这里，推理方式可以有正向和反向推理两种。正向推理是从前件匹配到结论，反向推理则先假设一个结论成立，看它的条件有没有得到满足。由此可见，推理机就如同专家解决问题的思维方式，知识库就是通过推理机来实现其价值的。 人机界面是系统与用户进行交流时的界面。通过该界面，用户输入基本信息、回答系统提出的相关问题，并输出推理结果及相关的解释等。 综合数据库专门用于存储推理过程中所需的原始数据、中间结果和最终结论，往往是作为暂时的存储区。解释器能够根据用户的提问，对结论、求解过程做出说明，因而使专家系统更具有人情味。 知识获取是专家系统知识库是否优越的关键，也是专家系统设计的“瓶颈”问题，通过知识获取，可以扩充和修改知识库中的内容，也可以实现自动学习功能。 2，专家系统的特点 在功能上, 专家系统是一种知识信息处理系统, 而不是数值信息计算系统。在结构上, 专家系统的两个主要组成部分 – 知识库和推理机是独立构造、分离组织, 但又相互作用的。在性能上, 专家系统具有启发性, 它能够运用专家的经验知识对不确定的或不精确的问题进行启发式推理, 运用排除多余步骤或减少不必要计算的思维捷径和策略；专家系统具有透明性, 它能够向用户显示为得出某一结论而形成的推理链, 运用有关推理的知识(元知识)检查导出结论的精度、一致性和合理性, 甚至提出一些证据来解释或证明它的推理；专家系统具有灵活性, 它能够通过知识库的扩充和更新提高求解专门问题的水平或适应环境对象的某些变化,通过与系统用户的交互使自身的性能得到评价和监护。 3，专家系统适合解决的实际问题 专家系统是人工智能的一个应用，但由于其重要性及相关应用系统之迅速发展，它已是信息系统的一种特定类型。专家系统一词系由以知识为基础的专家系统(knowledge-based expert system)而来，此种系统应用计算机中储存的人类知识，解决一般需要用到专家才能处理的问题，它能模仿人类专家解决特定问题时的推理过程，因而可供非专家们用来增进问题解决的能力，同时专家们也可把它视为具备专业知识的助理。由于在人类社会中，专家资源确实相当稀少，有了专家系统，则可使此珍贵的专家知识获得普遍的应用。 专家系统技术广泛应用在工程、科学、医药、军事、商业等方面，而且成果相当丰硕，甚至在某些应用领域，还超过人类专家的智能与判断。其功能应用领

遗传算法电机优化设计简介

收稿日期:20001225 综 述 遗传算法电机优化设计简介 李鲲鹏,胡虔生 (东南大学,南京210096) B rief I ntroduction of Motor Optimizing Design B ased on G enetic Algorithms L I Kun -peng ,HU Qian -sheng (S outheast University ,Nanjing 210096,China ) 摘　要:介绍了遗传算法的基本思想及其特点,实现了基于遗传算法的电机优化设计,讨论了保证其全局收敛性的方法,最后给出了基于遗传算法的电机优化设计实例。 关键词:电机优化设计;遗传算法;全局收敛性中图分类号:T M302 文献标识码:A 文章编号:1004-7018(2001)04-0032-02 Abstract :In this paper ,the essence and a pplications of genetic alg orithms are friendly introduced.Based on com paris ons between ge 2netic alg orithms and conventional methods ,the a pplication of genetic alg orithm to motor design is im plemented.In this process ,the meth 2ods to improve the global convergence of genetic alg orithm are dis 2cussed.Finally ,the results of the optimization of three -phase electri 2cal machine design based on genetic alg orithms are presented. K eyw ords :motor optimal design ;genetic alg orithms (G A );glob 2al convergence 1遗传算法的基本思想及其特点 遗传算法是模拟生物进化机制的一种现代优化计算方法。其基本思想是:首先通过编码操作将问题空间映射到编码空间(如[0,1]L ),然后在编码空间内进行选择、交叉、变异三种遗传操作及其循环迭代操作,模拟生物遗传进化机制,搜索编码空间的最优解,最后逆映射到原问题空间,从而得到原问题的最优解。选择操作模拟了个体之间和个体与环境之间的生存竞争,优良个体有更多的生存繁殖机会。在这种选择压力作用下,个体之间通过交叉、变异遗传操作进行基因重组,期望得到更优秀的后代个体,在这场竞争中胜出。选择、交叉、变异遗传操作都是以概率值进行的。这些概率值与当时生存环境和个体适应能力密切相关。从这里可以看出遗传算法是一种随机性搜索算法,但是它不同于传统的随机搜索算法。遗传算法通过交叉算子(Cross over operator )和变异算子(Mutation Operator )的协同作用确保状态空间([0,1]L )各点的概 率可达性,在选择算子(Selection Operator )的作用下保证迭代进程的方向性。 2电机优化设计的数学模型和一般优化方法 电机优化设计的一般数学模型: min/max :f (x ) g i (X )≤0,i =1,2,3,…,m X j ∈[a j ,b j ],j =1,2,3,…,n (1) 其中:X =[x 1,x 2,x 3,…,x n ]为设计参量即电磁系统的参数,如冲片尺寸、绕组参量等。g i (X )(i =1,2,3,…,m )为约束条件,如性能约束和一般约束。由于目标函数f (X )和约束条件g i (X )都是X 的高度非线性函数,因此电机优化设计问题是求解约束非线性最优化问题。 由于电机设计的目标函数f (X )不是一个单纯的数学表达式,而是一段电机设计分析计算程序,在计算目标函数值的同时还计算各个性能指标值,即约束条件函数值,因此利用目标函数的梯度确定搜索方向的优化方法在电机优化设计中是相当繁琐,直接利用目标函数值的优化方法在电机优化设计中具有优势,遗传算法通过选择、交叉、变异算子的协同作用,既保证了搜索的方向性,又满足了状态空间各点的概率可达性,具有概率意义下的全局收敛性。遗传算法继承了传统确定性算法和一般随机算法的优点,是一种新的启发式随机搜索算法。 遗传算法对约束的处理有两种思路:增加修正算子将约束条件反映在遗传算子的设计中;利用惩罚函数法将有约束优化问题转化为无约束优化问题。在电机优化设计中常采取后者。基于遗传算法的惩罚函数主要分为静态惩罚函数、动态惩罚函数和自适应惩罚函数三种[4]。自适应惩罚函数法效果较好,但较复杂; 静态、动态惩罚函数相对较简单,经常使用。约束条件 23 微特电机　2001年第4期

遗传算法和蚁群算法的比较

全局优化报告——遗传算法和蚁群算法的比较 姓名：玄玄 学号：3112054023 班级：硕2041

1遗传算法 1.1遗传算法的发展历史 遗传算法是一种模拟自然选择和遗传机制的寻优方法。20世纪60年代初期，Holland教授开始认识到生物的自然遗传现象与人工自适应系统行为的相似性。他认为不仅要研究自适应系统自身，也要研究与之相关的环境。因此，他提出在研究和设计人工自适应系统时，可以借鉴生物自然遗传的基本原理，模仿生物自然遗传的基本方法。1967年，他的学生Bagley在博士论文中首次提出了“遗传算法”一词。到70年代初，Holland教授提出了“模式定理”，一般认为是遗传算法的基本定理，从而奠定了遗传算法的基本理论。1975年，Holland出版了著名的《自然系统和人工系统的自适应性》，这是第一本系统论述遗传算法的专著。因此，也有人把1975年作为遗传算法的诞生年。 1985年，在美国召开了第一届两年一次的遗传算法国际会议，并且成立了国际遗传算法协会。1989年，Holland的学生Goldberg 出版了《搜索、优化和机器学习中的遗传算法》，总结了遗传算法研究的主要成果，对遗传算法作了全面而系统的论述。一般认为，这个

时期的遗传算法从古典时期发展了现代阶段，这本书则奠定了现代遗传算法的基础。 遗传算法是建立在达尔文的生物进化论和孟德尔的遗传学说基础上的算法。在进化论中，每一个物种在不断发展的过程中都是越来越适应环境，物种每个个体的基本特征被后代所继承，但后代又不完全同于父代，这些新的变化，若适应环境，则被保留下来；否则，就将被淘汰。在遗传学中认为，遗传是作为一种指令遗传码封装在每个细胞中，并以基因的形式包含在染色体中，每个基因有特殊的位置并控制某个特殊的性质。每个基因产生的个体对环境有一定的适应性。基因杂交和基因突变可能产生对环境适应性强的后代，通过优胜劣汰的自然选择，适应值高的基因结构就保存下来。遗传算法就是模仿了生物的遗传、进化原理，并引用了随机统计原理而形成的。在求解过程中，遗传算法从一个初始变量群体开始，一代一代地寻找问题的最优解，直到满足收敛判据或预先假定的迭代次数为止。 遗传算法的应用研究比理论研究更为丰富，已渗透到许多学科，并且几乎在所有的科学和工程问题中都具有应用前景。一些典型的应用领域如下： （1）复杂的非线性最优化问题。对具体多个局部极值的非线性最优化问题，传统的优化方法一般难于找到全局最优解；而遗传算法可以克服这一缺点，找到全局最优解。 （2）复杂的组合优化或整数规划问题。大多数组合优化或整数规划问题属于NP难问题，很难找到有效的求解方法；而遗传算法即特别

遗传算法及其在TSP问题中的应用

遗传算法及其在TSP问题中的应用 摘要：本文首先介绍了遗传算法的基本理论与方法，从应用的角度对遗传算法做了认真的分析和研究，总结了用遗传算法提出求解组合优化问题中的典型问题——TSP问题的最优近似解的算法。其次，本文在深入分析和研究了遗传算法基本理论与方法的基础上，针对旅行商问题的具体问题，设计了基于TSP的遗传算法的选择、交叉和变异算子等遗传算子，提出了求解旅行商问题的一种遗传算法，并用Matlab语言编程实现其算法，最后绘出算法的仿真结果，并对不同结果作出相应的分析。然后，本文还针对遗传算法求解TSP时存在的一些问题对该算法进行了适当的改进。如针对初始群体、遗传算子作出适当改进，或者将遗传算法与其他方法相结合，以及在编程过程中对算法流程的改进。本人在用计算机模拟遗传算法求解TSP问题时，首先分析了用Matlab语言设计遗传算法程序的优越性，接着以遗传算法求解TSP问题为例，深入讨论了各个遗传算子的程序实现，并通过分析实验数据，得到各个遗传算子在搜索寻优过程中所起的作用，最后指出了用Matlab语言编程同用其它高级程序语言编程的差异所在，以及运用Matlab编写遗传算法程序的一些注意事项。最后，本文提出将遗传算法与其它算法相结合来求解一般问题的想法；并将遗传算法的应用范围扩展，提出可以运用遗传算法求解由TSP衍生出的各类TSP扩展问题，如求解配送/收集旅行商问题的遗传算法（TSPD）、遗传算法在货物配送问题中的应用（ST－TSP）、多旅行商问题（MTSP）等。 引言：优化问题可以自然地分为两类：一类是连续变量的优化问题；另一类是离散变量的优化问题，即所谓组合优化问题。对于连续变量的优化问题，一般是求一组实数或一个函数；而在组合优化问题中，一般是从一个无限集或有限的几个无限集中寻找一个对象——它可以是一个整数，一个集合，一个排列或者一个图，也即是从可行解中求出最优解的问题。TSP问题就是其中的典型例子，就本质上而言它可抽象为数学上的组合优化，它描述的是旅行商经N个城市的最短路径问题，因而对TSP问题的求解是数学上，同时也是优化问题中普遍关注的。旅行商问题（Traveling Salesman Problem，简称TSP）也称为货担郎问题，是一个较古的问题，最早可以追溯到1759年Euler提出的骑士旅行问题[9]。旅行商问题可以解释为，一位推销员从自己所在城市出发，必须邀访所有城市且每个城市只能访问一次之后又返回到原来的城市，求使其旅行费用最小（和旅行距离最短）的路径。 TSP是一个典型的组合优化问题，并且是一个NP难题，所以一般很难精确地求出其最优解，因而寻找出其有效的近似求解算法就具有重要的理论意义。另一方面，很多实际应用问题，如公安执勤人员的最优巡回路线、流水作业生产线的顺序问题、车辆调度问题、网络问题、切割问题以至机组人员的轮班安排、教师任课班级负荷分配等问题，经过简化处理后，都可建模为TSP问题，因而对旅行商问题求解方法的研究也具有重要的应用价值。再者，在各种遗传算法应用实例中，其个体编码方法大多都是采用二进制编码方法或浮点数编码方法，而TSP问题是一种典型的需要使用符号编码方法的实际问题，所以，研究求解TSP问题的遗传算法，对促进遗传算法本身的发展也具有重要意义。在过去的20年里，在求解旅行商问题的最优解方面取得了极大的进展。尽管有这些成就，但旅行商问题还远未解决，问题的许多方面还要研究，很多问题还在期待满意的回答。 另外，遗传算法就其本质来说，主要是解决复杂问题的一种鲁棒性强的启发式随机

遗传算法

遗传算法 开放分类：编程、程序、数学、计算机、算法 目录 ? 遗传算法定义 ? 遗传算法特点 ? 遗传算法的应用 ? 遗传算法的现状 ? 遗传算法的一般算法 ? 遗传算法实例 遗传算法定义 [编辑本段] 遗传算法（Genetic Algorithm）是模拟达尔文的遗传选择和自然淘汰的生物进化过程的计算模型，是一种通过模拟自然进化过程搜索最优解的方法，它是有美国Michigan大学J.Holland教授于1975年首先提出来的，并出版了颇有影响的专著《Adaptation in Natural and Artificial Systems》，GA这个名称才逐渐为人所知，J.Hilland教授所提出的GA通常为简单遗传算法（SGA）。 遗传算法是从代表问题可能潜在的解集的一个种群（population）开始的，而一个种群则由经过基因（gene）编码的一定数目的个体(individual)组成。每个个体实际上是染色体(chromosome)带有特征的实体。染色体作为遗传物质的主要载体，即多个基因的集合，其内部表现（即基因型）是某种基因组合，它决定了个体的形状的外部表现，如黑头发的特征是由染色体中控制这一特征的某种基因组合决定的。因此，在一开始需要实现从表现型到基因型的映射即编码工作。由于仿照基因编码的工作很复杂，我们往往进行简化，如二进制编码，初代种群产生之后，按照适者生存和优胜劣汰的原理，逐代（generation）演化产生出越来越好的近似解，在每一代，根据问题域中个体的适应度（fitness）大小挑选（selection）个体，并借助于自然遗传学的遗传算子（genetic operators）进行组合交叉（crossover）和变异（mutation），产生出代表新的解集的种群。这个过程将导致种群像自然进化一样的后生代种群比前代更加适应于环境，末代种群中的最优个体经过解码（decoding），可以作为问题近似最优解。 遗传算法特点 [编辑本段] 遗传算法是一类可用于复杂系统优化的具有鲁棒性的搜索算法，与传统的优化算法相比，主要有以下特点：1、遗传算法以决策变量的编码作为运算对象。传统的优化算法往往直接决策变量的实际植本身，而遗传算法处理决策变量的某种编码形式，使得我们可以借鉴生物学中的染色体和基因的概念，可以模仿自然界生物的遗传和进化机理，也使得我们能够方便的应用遗传操作算子。 2、遗传算法直接以适应度作为搜索信息，无需导数等其它辅助信息。 3、遗传算法使用多个点的搜索信息，具有隐含并行性。 4、遗传算法使用概率搜索技术，而非确定性规则。 遗传算法的应用 [编辑本段] 由于遗传算法的整体搜索策略和优化搜索方法在计算是不依赖于梯度信息或其它辅助知识，而只需要影响

遗传算法及蚂蚁算法作业

（1）用遗传算法来做： 第一步：确定决策变量及其约束条件 s.t. -5<=x<=5 第二步：建立优化模型 第三步：确定编码方法，用长度为50位的二进制编码串来表示决策 变量x 第四步：确定解码方法 第五步：确定个体评价方法 个体的适应度取为每次迭代的最小值的绝对值加上目标函数值，即 第六步：确定参数 本题种群规模n=30,迭代次数ger=200,交叉概率pc=0.65,变异概率 pm=0.05 代码： clear all; close all; clc; tic; n=30; ger=200; pc=0.65; pm=0.05; % 生成初始种群

v=init_population(n,50); [N,L]=size(v); disp(sprintf('Number of generations:%d',ger)); disp(sprintf('Population size:%d',N)); disp(sprintf('Crossover probability:%.3f',pc)); disp(sprintf('Mutation probability:%.3f',pm)); % 待优化问题 xmin=-5; xmax=5; ymin=-5; ymax=5; f='-(2-exp(-(x.^2+y.^2)))'; [x,y]=meshgrid(xmin:0.1:xmax,ymin:0.1:ymax); vxp=x; vyp=y; vzp=eval(f); figure(1); mesh(vxp,vyp,-vzp); hold on; grid on; % 计算适应度，并画出初始种群图形x=decode(v(:,1:25),xmin,xmax);