典型优化问题的遗传算法求解—8选址分配问题

典型问题

选址－分配问题

(Location Allocation Problem)

东北大学系统工程研究所

2014.09

选址－分配问题

●

选址－分配(location-allocation) 问题

也称作多韦伯(multi-Weber ) 问题或P 中位(P-median )问题。

●

单韦伯(single Weber)问题

在欧几里德空间上典型的单韦伯(single Weber) 问题是寻找一个位置，使从代表顾客位置的一些固定点到它的距离和最小。

●

问题描述：

有m 个“设施”需要选址，n 个已知位置的“顾客”分配给不同的设施，每个顾客的需求为b j ，j =1,2,…,n ；每个设施具有的能力为a i ，i =1,2,…,m 我们需要找到

设施的位置（选址）

顾客对设施的分配

使顾客和服务他们的设施间的距离总和最小。

图形描述

m : 设施总数n : 顾客总数

F i : 第i 个设施,i =1,2,…,m C j : 第j 个顾客,j =1,2,…,n a i : 第i 个设施的能力b j : 第j 个顾客的需求

F i =(x i , y i ):设备i 的未知位置，决策变量C j =(u j , v j ):顾客j 的已知位置

C 3

C 1C n

C 2

F 1F m

(x 1, y 1)

(u 1, v 1)b 1

a 1

(x m , y m )

(u n , v n )b n

a m …

数学模型

n

j m i z n

j z z g m

i a z b z g z C F t z F f ij m

i ij j m i ij n

j j i ij

m

i n

j j i ,,2,1,,,2,11,

or 0

,,2,1,1)(,,2,1,)( t.s. ),(),( min 1

1

11 =======≤=?=∑∑∑∑=+==

=

C j F i

(x i , y i )

b j

a i (u j , v j )

……

2

2)

()(),(j i j i j i v y u x C F t -+-=?

变量:

z ij : 0-1 决策变量

z ij =1,顾客j 由设施i 服务；否则z ij =0F i = (x i , y i ) :设施i 的未知位置，决策变量

?

参数：

t

(F

i

,C

j

):

由设施

i

到顾客j

的欧几里得距离。

保证不超过每个

设施的服务能力

保证每个顾客只由一个设施服务

●非线性规划问题

●既有0-1 变量，又有实数变量

●分配子问题是一个一般的指派问题

●NP-难的问题

●Cooper 是正式认识并描述多韦伯问题的第一位学者。他证明目标函数既不是凹的也不是凸的，并存在许多局部最优解。

●按能力分类：

有能力约束的LAP

无能力约束的LAP ●按阶段分类：

单阶段LAP

多阶段LAP

●其它分类：

有障碍的LAP

平衡的LAP

问题的扩展

●一般的选址-分配模型致力于为这样一些基础设施寻找

最佳选址，如：

学校、消防站、公园等，

此类基础设施对于“最佳选址”理解的共同点在于，使供需点之间的“总距离”或者“平均距离”最小。

●除此以外，这个基本模型经过扩展还可以有更广泛的

应用范围，如：

优化城市零售商业网点空间分布(通过最大化惠顾人流量来实现)、

优化制造业场所空间分布(通过最小化运输成本实现)、

优化公共服务设施空间分布(通过最优化服务质量实现)、 ……

●

物流配送中心选址问题

物流网络设计中首先必须要解决的问题

物流中心→设施；零售商→顾客；运费或距离最短

●城市医院空间布局优化

医院→设施；街区→顾客；服务质量, 距离最小等●

城市邮政局所空间布局

邮局→设施；建筑物的中心→顾客；邮政服务的平均出行距离最短

●

城市电网变电站选址问题

变、配电站→设施；小区→顾客；输电线（距离）最短

●

海上溢油应急点选址优化

应急服务点→设施；发生溢油较高的区域→顾客；到达发生事故点的距离之和最小

●

公路养护资源的选址和配置问题

养护点→设施；路段→顾客；目标是工作量均衡

C 3

C 1

C n

C 2

F 1

F m

…

●

社会考试考场选择问题

例如英语等级考试、公务员考试等涉及的人数很多；

考场→设施；生源地→顾客；距离最短、最便利等

●

零售商业点的选址问题

商业点→设施；小区（街区）→顾客；惠顾人流量最大或距离最短

●

公共设施的最优选址问题

如公园、学校、图书馆、加油站、污水处理厂、城市垃圾填埋场、消防设施等●突发事件的应急资源配置问题

如地震、海啸、流行病、

●

设备选址

如电力、通信、交通系统中相关设备或站址的选取和定位

C 3

C 1

C n

C 2

F 1

F m

…

一般求解方法

●Cooper 提出了一种称作选择选址－分配(alternative location-allocation) 的

启发式，这是一种最好的启发方法

●随着非线性规划技术的发展，通过松弛整数分配约束，同时考虑选址变量

和分配变量，产生了一些新的方法。

Murtagh和Niwattisyawong提出一种松弛0-1分配约束的方法。允许在[0,1] 区间上取值，然后用非线性规划软件包来解决选址和分配问题。

Bongartz等提出的方法，也松弛0-1 分配约束，同时还采用活动集合方法，并利用了选址－分配问题固有的特殊结构。

这些方法可用于大规模的实际问题。但都不能保证全局和近全局最优。

●Harris 等发现当可能解的数量是一个类型II 的Sterling 数时，可行解的数

量相当少。他们发现任何可行解中顾客的子集必须包括在非重叠凸域内，他们提出了一种算法，利用问题这一凸域特性产生所有可行解，并通过对这些解的完全枚举找到最优解。

●Qstresh提出了基于通行线(passing line) 解决两设施韦伯问题的不同算法。

●Rosing基于Harris 的思想提出了关于一般多韦伯问题的优化方法，然而，

只能用于小规模问题。

●Gong, Gen, Xu 和Yamazaki 提出了一种解决具有能力约束的选址－分配问题的混和进化方法●

这种方法将问题分为两层:

分配层

在分配层，因为这一子问题需经常解决，所以采用拉格朗日松弛法解决这个一般指派问题，以尽快获得解。

选址层

在选址层，采用进化方法搜索整个选址区域。通过这种方法，整个可选址区域可以被有效地搜索以找到全局或近全局最优解。

●

染色体表达

因为选址变量是连续的，所以采用浮点值染色体。染色体表达如下：

例如：

)]

,(,),,(,),,(),,[(2211k

m k m k i k i k k k k k y x y x y x y x v =)]

7.1,1.3(),4.0,5.2(),8.3,3.1[()],(),,(),,[(13

13

12

12

11

11

1==y x y x y x v

●

初始化

最优选址应在包括所有顾客的矩形区域内，因此设施初始选址可以从这个矩形区域内任取位置。

C 3

C 1

C n

C 2

F 1

F m

(x m , y m )

(u n , v n )

y

x

y max

x min

x max

y min

●

交叉

对于实数编码，可以采用线性凸组合交叉(Linear Convex Combination)

假设选择具有如下染色体的两个双亲产生后代

后代染色体中的基因由下面等式确定

其中，αi 是(0, 1)内的独立随机数(i =1,2,…,m )。

)]

,(,),,(,),,(),,[(1

11112

1211111m m i i y x y x y x y x v =)]

,(,),,(,),,(),,[(2

2

2

2

2

22

22

12

12m m i i y x y x y x y x v =2

12

212

211

211

)1()1()1()1(i i i i i i i i i i i

i i

i i i i i i i y y y x x x y

y y x

x x ?+?-=?+?-=?-+?=?-+?=αααααααα

●

变异

采用两类变异算子在进化过程中交替进行

精细变异(subtle mutation)：双亲染色体进行较小的随

机改变，产生一个新的后代染色体；

强烈变异(violent mutation)：采用与初始化过程相同的方法产生后代

??

?Θ

+=δv v Subtle mutation Violent mutation

是一个较小的正数

之间的随机数是 )1,2,...,2)(,(- ],

,,...,,[21221αααδδδδδδm i i m m ==-之间的随机数

是之间的随机数是],[ ],[max min max min y y x x y i x i θθ)]

,(),...,,(),,[(Θ2211y m

x m y x y x θθθθθθ=

●

评价

对于指定的染色体v k ，设施的位置是固定的 我们可将最优分配的距离和映射为v k 的适值 为计算距离和，需要解决分配子问题。

对于固定的设施选址问题，采用拉格朗日松弛法解决分

配子问题

调整松弛解使之可行(考虑能力约束)

指定染色体v k

的适值函数如下:

)

,(1

)(z F f v eval k

●

相对禁止的选择策略

(μ+λ)选择策略，在双亲和他们的后代中选出较好的个体形成下一代。

然而，这一策略通常导致进化过程退化，陷入局部最优。为了避免退化，提出了一种称作相对禁止(relative prohibition)的选择策略。

选择最好的个体作为下一代的第一个成员 在剩余的个体中选择最好的个体

如果它属于已选择的个体的禁止邻域，则忽略；否则作为下一代成员。 重复上述过程直至所有成员都被选择。

如果未满足种群规模要求，则采用随机选择进行补充。

禁止邻域的定义：

适值意义上的邻域

选址意义上的邻域

其中v k 已被选入下一代，v 尚未选入下一代的染色体。

较小的正参数

-≤-αα)()(v eval v eval k 较小的正参数

-≤-γγ

v v k

典型问题

无能力约束的选址－分配问题(Uncapacitated Location Allocation Problem)

无能力约束的选址－分配问题

●如果设施在能力上没有限制，则问题被称为无能力约束的选址－分配问题（uLAP）

●在uLAP问题当中，一些设施在n个可能的客户之间进行分配，目标是以最小的费用在m

个给定位置建立设施，以满足所有客户的需求。

●费用由建立设施的固定费用和完成需求的运输（或供应)费用组成。

图形描述

设施的选址和客户的分配

m : 设施总数n : 客户总数

F i : 第i 个设施,i =1,2,…,m C j : 第j 个客户,j =1,2,…,n d i :建立第i 个设施的费用

c ij :第i 个设施向第j 个客户提供服务的费用F i =(x i , y i ):设备i 的已知位置C j =(u j , u j ):客户j 的已知位置

C 3C 1

C n F 1F m

d 1

c 11

d m

…

c 13

c mn

(x i , y i ) (u j , v j )

(x 1, y 1)

(u 1, v 1)

数学模型

变量:

x ij : 0-1 决策变量

x ij =1,顾客j 由设施i 服务；否则x ij =0y i : 0-1 决策变量

y i =1,设施i 被建立，否则y i

=0

如果设施不被建立

，则不提供服务

保证每个顾客只由一个设施服务{}

)

4(,1,0,

)3(, )2(1

)( t.s.)1()(min 1

1

11

J

j I i y x J j I i y x J j x x g y d x c x f i ij i

ij n

i ij m

i i

i m

i n

j ij ij ∈∈?∈∈∈?≤∈?==+=∑∑∑∑====

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 问题等有着多方面的重要意义。

4遗传算法与函数优化

第四章遗传算法与函数优化 4.1 研究函数优化的必要性： 首先，对很多实际问题进行数学建模后，可将其抽象为一个数值函数的优化问题。由于问题种类的繁多，影响因素的复杂，这些数学函数会呈现出不同的数学特征。除了在函数是连续、可求导、低阶的简单情况下可解析地求出其最优解外，大部分情况下需要通过数值计算的方法来进行近似优化计算。 其次，如何评价一个遗传算法的性能优劣程度一直是一个比较难的问题。这主要是因为现实问题种类繁多，影响因素复杂，若对各种情况都加以考虑进行试算，其计算工作量势必太大。由于纯数值函数优化问题不包含有某一具体应用领域中的专门知识，它们便于不同应用领域中的研究人员能够进行相互理解和相互交流，并且能够较好地反映算法本身所具有的本质特征和实际应用能力。所以人们专门设计了一些具有复杂数学特征的纯数学函数，通过遗传算法对这些函数的优化计算情况来测试各种遗传算法的性能。 4.2 评价遗传算法性能的常用测试函数 在设计用于评价遗传算法性能的测试函数时，必须考虑实际应用问题的数学模型中所可能呈现出的各种数学特性，以及可能遇到的各种情况和影响因素。这里所说的数学特性主要包括： ●连续函数或离散函数； ●凹函数或凸函数； ●二次函数或非二次函数； ●低维函数或高维函数； ●确定性函数或随机性函数； ●单峰值函数或多峰值函数，等等。 下面是一些在评价遗传算法性能时经常用到的测试函数： (1)De Jong函数F1： 这是一个简单的平方和函数，只有一个极小点f1(0, 0, 0)＝0。

(2)De Jong 函数F2： 这是一个二维函数，它具有一个全局极小点f 2(1，1) = 0。该函数虽然是单峰值的函数，但它却是病态的，难以进行全局极小化。 (3)De Jong 函数F3： 这是一个不连续函数，对于]0.5,12.5[--∈i x 区域内的每一个点，它都取全局极小值 30),,,,(543213-=x x x x x f 。

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

实验十遗传算法与优化问题 一、问题背景与实验目的 遗传算法（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年系统全面的阐述了遗传算法理论，并通过例证对遗传算法的多领域应用进行了分析，为现代遗传算法的研究和发展奠定了基础。 遗传算法是一种模仿基于自然选择的生物进化过程的随机方法，它以类似于基因的编码作为种群的个体，首先，随机的产生初始种群的个体，从这个群体开始进行搜索，根据类似于生物适应能力的适应度函数值的大小，按照不同问题各自的特点，在当前的种群中运用适当的选择策略选择适应能力大的个体，其中所选择出来的个体经过遗传操作、交叉操作以及变异操作产生下一代种群个体。如此反复，像生物的进化过程一样逐代进化，直到满足期望的终止条件为止。

基于遗传算法的改进多重心选址方法

基于遗传算法的改进多重心选址方法 基于遗传算法的改进多重心选址方法 摘要：近年来，由于传统重心法存在对现实问题过于简化的不足而逐渐被其它新方法所替代。首先分析了重心法的优点和缺点，提出了一种基于遗传算法的多重心选址方法。结合具体算例与相关研究成果进行了比较，新方法消除了聚类方法“孤立点”问题，选址结果优化程度显著提高。 关键词：物流工程；改进措施；遗传算法；多重心法；选址决策 中图分类号：F2 文献标识码：A 文章编号：1672.3198（2013）04.0032.02 1引言 在物流管理领域，物流/配送中心选址决策、运输决策和库存决策被称为物流管理的三大核心业务。其中选址决策长期以来是学术界研究的重点。在众多选址决策方法中，重心法操作最简便，不失为一种理想的工具，这也是长期以来重心法虽然被学术界批评但在实践中却没有被替代、舍弃的根本原因。但不可否认，重心法无论从理论还是从实践中都被证明存在对问题空间过度简化的缺陷，如：（1）未考虑固定成本与管理成本因素，包括建设成本、固定管理成本和可变管理成本；（2）未考虑候选地址的地租、规模等因素；（3）应用于多中心选址时，没有准确的区域划分标准等。如果针对这些问题加以完善，重心法的求解结果质量会更高，实用性会更强。 针对存在的诸多问题，学术界对重心法进行了改进和完善。如在传统重心法模型基础上，加入了物流/配送中心的固定费用（建设成本）和管理费用（可变成本），使决策模型更加附合实际。这种改进极具价值。在多物流/配送中心选址方面，关于重心法的研究成果多集中在聚类方法的应用上。 现有改进措施仍然存在进一步完善的空间。首先，在选址决策中，

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问题。

遗传算法的计算性能的统计分析

第32卷 第12期2009年12月 计 算 机 学 报 CH INESE JOURNA L OF COMPU TERS Vol.32No.12 Dec.2009 收稿日期:2008210219;最终修改稿收到日期:2009209227.本课题得到国家自然科学基金(60774084)资助.岳 嵚,男,1977年生,博士研究生,主要研究方向为进化算法.E 2mail:yueqqin@si https://www.wendangku.net/doc/c712426882.html,.冯 珊,女,1933年生,教授,博士生导师,主要研究领域为智能决策支持系统. 遗传算法的计算性能的统计分析 岳 嵚 冯 珊 (华中科技大学控制科学与工程系 武汉 430074) 摘 要 通过对多维解析函数的多次重复计算并对计算结果进行统计分析来讨论遗传算法的可靠性和可信度,结果表明:遗传算法的计算结果具有一定的稳定性,可以通过采用多次重复计算的方法提高计算结果的可信度,并用以评价算法及其改进的实际效果.关键词 遗传算法;计算可靠性;置信区间 中图法分类号TP 18 DOI 号:10.3724/SP.J.1016.2009.02389 The Statistical Analyses for Computational Performance of the Genetic Algorithms YU E Qin FENG Shan (Dep artment of Contr ol Science and Eng ineering ,H uazhong University of Science and T ech nology ,W u han 430074) Abstr act In this paper,the author s discuss the reliability of the GAs by reiteratively computing the multi 2dimensional analytic functions and statistical analysis of the results.The analysis re 2sults show that the GAs have certain stability;it could improve the reliability by reiteratively computation and estimates the effects of improvements. Keywor ds genetic algorithms;computational stability;confidence interval 1 遗传算法的随机性 遗传算法是将生物学中的遗传进化原理和随机优化理论相结合的产物,是一种随机性的全局优化算法[1].遗传算法作为一种启发式搜索算法,其计算结果具有不稳定性和不可重现性;遗传算法的进化过程具有有向随机性,整体上使种群的平均适应度不断提高.现在学术界对遗传算法中的某些遗传操作的作用机制还不十分清楚,遗传算法的许多性能特点无法在数学上严格证明.遗传算法的计算过程会受到各种随机因素的影响,如随机产生的初始种群和随机进行的变异操作等,尤其初始种群对计算结果影响较大.但另一方面,大量的实算结果表明,遗传算法的计算结果具有一定的规律性,在统计意义上具有一定的可靠性,这样就可以对待求解问题 进行多次重复计算后取平均值的方法,提高遗传算 法在实际计算中的准确性和可信度. 包括遗传算法在内的启发式搜索算法主要用于解决大型的复杂优化问题,这些问题一般难以使用传统的优化算法解决.遗传算法对这类问题的计算结果也难达到精确的最优解.这给对用遗传算法解决实际工程优化问题的计算结果的评价带来了困难,在实际工程计算中也难以评价遗传算法及其改进型的计算效果的优劣. 为了分析遗传算法的计算性能,本文采用的计算对象是一个复杂的多维解析函数.使用这类函数评价遗传算法计算性能的好处是可以事先通过其他方法求得最优解,这样便于评价遗传算法及其改进型的计算效果.本文从统计学角度对多次重复计算的结果进行分析,试图得到遗传算法的稳定性和可信度方面的相关结论,通过分析遗传算法及其改进

典型优化问题的遗传算法求解— 选址分配问题

典型问题 选址－分配问题 (Location Allocation Problem) 东北大学系统工程研究所 2014.09

选址－分配问题 ● 选址－分配(location-allocation) 问题 也称作多韦伯(multi-Weber ) 问题或P 中位(P-median )问题。 ● 单韦伯(single Weber)问题 在欧几里德空间上典型的单韦伯(single Weber) 问题是寻找一个位置，使从代表顾客位置的一些固定点到它的距离和最小。 ● 问题描述： 有m 个“设施”需要选址，n 个已知位置的“顾客”分配给不同的设施，每个顾客的需求为b j ，j =1,2,…,n ；每个设施具有的能力为a i ，i =1,2,…,m 我们需要找到 设施的位置（选址） 顾客对设施的分配 使顾客和服务他们的设施间的距离总和最小。

图形描述 m : 设施总数n : 顾客总数 F i : 第i 个设施,i =1,2,…,m C j : 第j 个顾客,j =1,2,…,n a i : 第i 个设施的能力b j : 第j 个顾客的需求 F i =(x i , y i ):设备i 的未知位置，决策变量C j =(u j , v j ):顾客j 的已知位置 C 3 C 1C n C 2 F 1F m (x 1, y 1) (u 1, v 1)b 1 a 1 (x m , y m ) (u n , v n )b n a m …

数学模型 n j m i z n j z z g m i a z b z g z C F t z F f ij m i ij j m i ij n j j i ij m i n j j i ,,2,1,,,2,11, or 0 ,,2,1,1)(,,2,1,)( t.s. ),(),( min 1 1 11 =======≤=?=∑∑∑∑=+== = C j F i (x i , y i ) b j a i (u j , v j ) …… 2 2) ()(),(j i j i j i v y u x C F t -+-=? 变量: z ij : 0-1 决策变量 z ij =1,顾客j 由设施i 服务；否则z ij =0F i = (x i , y i ) :设施i 的未知位置，决策变量 ? 参数： t (F i ,C j ): 由设施 i 到顾客j 的欧几里得距离。 保证不超过每个 设施的服务能力 保证每个顾客只由一个设施服务

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

煤矿机械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

遗传算法的计算性能的统计分析

遗传算法遗传算法的计算性能的统计分析 岳嵚冯珊 （华中科技大学控制科学与工程系） 摘要：本文通过对多维解析函数的多次重复计算并对计算结果的进行统计分析来讨论遗传算法的可靠性和可信度，结果表明：遗传算法的计算结果具有一定的稳定性，可以通过采用多次重复计算的方法提高计算结果的可信度，并用以评价算法及其改进的实际效果。 关键词：遗传算法；计算可靠性；置信区间 分类号：TP18 1遗传算法的随机性 遗传算法是将生物学中的遗传进化原理和随机优化理论相结合的产物，是一种随机性的全局优化算法[1]。遗传算法作为一种启发式搜索算法，其计算结果具有不稳定性和不可重现性；遗传算法的进化过程具有有向随机性，整体上使种群的平均适应度不断提高。现在学术界对遗传算法中的某些遗传操作的作用机制还不十分清楚，遗传算法的许多性能特点无法在数学上严格证明。遗传算法的计算过程会受到各种随机因素的影响，如随机产生的初始种群和随机进行的变异操作等，尤其初是始种群对计算结果影响较大。但另一方面，大量的实算结果表明，遗传算法的计算结果具有一定的规律性，在统计意义上具有一定的可靠性，这样就可以对待求解问题进行多次重复计算后取平均值的方法，提高遗传算法在实际计算中的准确性和可信度。 包括遗传算法在内的启发式搜索算法主要用于解决大型的复杂优化问题，这些问题一般难以使用传统的优化算法解决。遗传算法对这类问题的计算结果也难达到精确的最优解。这给对用遗传算法解决实际工程优化问题的计算结果的评价带来了困难，在实际工程计算中也难以评价遗传算法及其改进型的计算效果的优劣。 为了分析遗传算法的计算性能，本文采用的计算对象是一个复杂的多维解析函数。使用这类函数评价遗传算法计算性能的好处是可以事先通过其他方法求得最优解，这样便于评价遗传算法及其改进型的计算效果。本文从统计学角度对多次重复计算的结果进行分析，试图得到遗传算法的稳定性和可信度方面的相关结论，通过分析遗传算法及其改进型求解解析问题的计算效果，再把所得到的相关结论推广应用到复杂的工程实际问题中去。 遗传算法在实际使用中有多种形式的变型，经典遗传算法是遗传算法的最简单的形式，但是经典遗传算法并不理想。本文使用的是粗粒度并行遗传算法。粗粒度并行遗传算法是遗传算法的一个重要改进型。它具有比经典遗传算法更好的计算性能。 2算例、实验方法和实验结果 2.1算例 本文所使用的算例是Deb 函数： ]10,10[,)]4cos(10[10)(12?∈??+=∑=i n i i i Deb x n x x x f i π（1） Deb 函数是一个高维的非凸函数，该函数在点（9.7624，9.7624，…，9.7624）上取得最大

基于遗传算法的应急物资供应点定位―分配问题研究综述

基于遗传算法的应急物资供应点定位―分配问题研究综述 摘要：本文总结、分析了近年来国内研究中基于遗传算法求解的应急物资供应点定位-分配相关问题的文献，主要包括应急定位问题、应急物资分配问题、应急定位-分配集成问题的研究综述，最后总结得出研究现状和未来研究的发展趋势。 关键词：遗传算法；应急物流；定位-分配问题 一、引言震后应急物流是保障生命安全、减少财产损失的重要环节。以往的震后应急管理实践过程中出现了很多诸如应急物资供应点的定位不合理、应急物资分配不公平等一系列降低应急物流运作效率的问题，这就对我国的应急物流组织体系的构建和完善提出了迫切要求，因此，研究震后应急物资供应点的定位-分配问题，具有十分重大的现实意义。而针对应急物资供应点定位- 分配问题的研究一般都属于NP-hard 问题，往往是基于遗传算法进行求解的，下面分别对基于遗传算法的应急物资供应点定位-分配问题包含的三个方面进行研究综述。 基于遗传算法的应急物资供应点定位-分配问题研

一）基于遗传算法的应急定位问题。刘红娟等（2010）［1］考虑设施点间距离、流量与安全性等道路特性，将其转换为道路的综合权值，建立了应急物流多设施选址模型，并采用遗传算法求解，最后用实例对模型进行了验证分析。李周清等（2011）［2］考虑震后物资调度的中转设施定位，以时间和成本最优为目标，建立了中转网点的定位模型，并用遗传算法求解。于鹏等（2012）［3］考虑设备应急抢修的时限要求和整个应急抢修系统的服务质量要求，采用0-1 整数规划模型描述应急抢修点选址定位问题，针对该问题设计了一种混合遗传算法，并通过算例计算结果表明，该算法求得的结果要优于基于罚函数和采用简单修复算法的遗传算法。张刚红（2013）［4］考虑大规模应急设施的选址定位成为应急管理系统的关键，构建应急设施选址问题的集合覆盖模型，提出一种改进的并行遗传算法，并在Hadoop 平台上编程实现。付德强等（2014）［5］研究了应急物资储备库的多目标选址决策模型，并设计了相应的多目标非支配排序遗传算法。 （二）基于遗传算法的应急物资分配问题。重大地震灾害发生以后，对应急物资进行科学合理的分配是震后应急物资保障系统的关键。 于振涛（2011）［6］研究应急物流系统中多级设施和多式联运救灾情况下的应急物资分配与调运问题，建立一个具有主从递阶关系结构的双层优化模型，并根据所建立的模型提出了一种改进的遗传算法。王增（2011）[7] 考虑连续软时间窗限制，构建人员

人工智能之遗传算法论文含源代码

30维线性方程求解 摘要：非线性方程组的求解是数值计算领域中最困难的问题，大多数的数值求解算法例如牛顿法的收敛性和性能特征在很大程度上依赖于初始点。但是对于很多高维的非线性方程组，选择好的初始点是一件非常困难的事情。本文采用了遗传算法的思想，提出了一种用于求解非线性方程组的混合遗传算法。该混合算法充分发挥了遗传算法的群体搜索和全局收敛性。选择了几个典型非线性方程组，考察它们的最适宜解。 关键词：非线性方程组；混合遗传算法；优化 1. 引言遗传算法是一种通用搜索算法，它基于自然选择机制和自然遗传规律来模拟自然界的进化过程，从而演化出解决问题的最优方法。它将适者生存、结构化但同时又是 随机的信息交换以及算法设计人的创造才能结合起来，形成一种独特的搜索算法，把一些解决方案用一定的方式来表示，放在一起成为群体。每一个方案的优劣程度即为适应性，根据自然界进化“优胜劣汰”的原则，逐步产生它们的后代，使后代具有更强的适应性，这样不断演化下去，就能得到更优解决方案。 随着现代自然科学和技术的发展，以及新学科、新领域的出现，非线性科学在工农业、经济政治、科学研究方面逐渐占有极其重要的位置。在理论研究和应用实践中，几乎绝大多数的问题都最终能化为方程或方程组，或者说，都离不开方程和方程组的求解。因此，在非线性问题中尤以非线性方程和非线性方程组的求解最为基本和重要。传统的解决方法，如简单迭代法、牛顿法、割线法、延拓法、搜索法、梯度法、共轭方向法、变尺度法，无论从算法的选择还是算法本身的构造都与所要解决的问题的特性有很大的关系。很多情况下,算法中算子的构造及其有效性成为我们解决问题的巨大障碍。而遗传算法无需过多地考虑问题的具体形式，因为它是一种灵活的自适应算法，尤其在一些非线性方程组没有精确解的时候，遗传算法显得更为有效。而且，遗传算法是一种高度并行的算法，且算法结构简单，非常便于在计算机上实现。本文所研究的正是将遗传算法应用于求解非线性方程组的问题。 2. 遗传算法解非线性方程组为了直观地观察用遗传算法求解非线性方程组的效果，我们这里用代数非线性方程组作为求解的对象问题描述：非线性方程组指的是有n 个变量（为了简化讨论，这里只讨论实变量方程组）的方程组 中含有非线性方程。其求解是指在其定义域内找出一组数能满足方程组中的每 个方程。这里，我们将方程组转化为一个函数则求解方程组就转化为求一组值使得成立。即求使函数取得最小值0 的一组数，于是方程组求解问题就转变为函数优化问题 3. 遗传算子 遗传算子设计包括交叉算子、变异算子和选择算子的设计。

第七章遗传算法应用举例

第七章 遗传算法应用举例 遗传算法提供了一种求解非线性、多模型、多目标等复杂系统优化问题的通用框架，它不依赖于问题具体的领域。随着对遗传算法技术的不断研究，人们对遗传算法的实际应用越来越重视，它已经广泛地应用于函数优化、组合优化、自动控制、机器人学、图象处理、人工生命、遗传编码、机器学习等科技领域。遗传算法已经在求解旅行商问题、背包问题、装箱问题、图形划分问题等多方面的应用取得了成功。本章通过一些例子，介绍如何利用第五章提供的遗传算法通用函数，编写MATLAB 程序，解决实际问题。 7.1 简单一元函数优化实例 利用遗传算法计算下面函数的最大值： ()sin(10) 2.0[1,2]f x x x x π=?+∈-， 选择二进制编码，种群中个体数目为40，每个种群的长度为20，使用代沟为0.9，最大遗传代数为25。 下面为一元函数优化问题的MA TLAB 代码。 figure(1); fplot ('variable.*sin(10*pi*variable)+2.0',[-1,2]); %画出函数曲线 % 定义遗传算法参数 NIND= 40; % 个体数目(Number of individuals) MAXGEN = 25; % 最大遗传代数(Maximum number of generations) PRECI = 20; % 变量的二进制位数(Precision of variables) GGAP = 0.9; % 代沟(Generation gap) trace=zeros (2, MAXGEN); % 寻优结果的初始值 FieldD = [20;-1;2;1;0;1;1]; % 区域描述器(Build field descriptor) Chrom = crtbp(NIND, PRECI); % 初始种群 gen = 0; % 代计数器 variable=bs2rv(Chrom,FieldD); % 计算初始种群的十进制转换 ObjV = variable.*sin (10*pi*variable)+2.0; % 计算目标函数值 while gen < MAXGEN, FitnV = ranking (-ObjV); % 分配适应度值(Assign fitness values) SelCh = select ('sus', Chrom, FitnV , GGAP); % 选择 SelCh = recombin ('xovsp',SelCh,0.7); % 重组 SelCh = mut(SelCh); % 变异 variable=bs2rv(SelCh,FieldD); % 子代个体的十进制转换 ObjVSel =variable.*sin(10*pi*variable)+2.0; % 计算子代的目标函数值 [Chrom ObjV]=reins(Chrom,SelCh,1,1,ObjV ,ObjVSel); % 重插入子代的新种群 gen = gen+1; % 代计数器增加 % 输出最优解及其序号，并在目标函数图象中标出，Y 为最优解，I 为种群的序号 [Y,I]=max(ObjV),hold on; plot (variable (I),Y , 'bo'); trace (1,gen)=max (ObjV); %遗传算法性能跟踪

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

收稿日期: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期