并行设计子任务调度的遗传算法原理与实现方法

第16卷第8期2004年8月

计算机辅助设计与图形学学报

JOURNAL OF COMPU TER 2AIDED DESIGN &COMPU TER GRAPHICS

Vol 116,No 18Aug 1,2004

原稿收到日期:2003205208;修改稿收到日期:20042012131本课题得到国家自然科学基金(50275100)和国家“八六三”高技术研究发展计划

/CIMS 主题基金(2001AA411150)资助1殷国富,男,1956年生,博士,教授,博士生导师,主要研究方向为计算机辅助设计与制造1罗　阳,男,1969年生,博士,副教授,主要研究方向为计算机辅助设计与制造1龙红能,男,1967年生,博士研究生,讲师,主要研究方向为计算机辅助设计

与制造1成尔京,男,1966年生,博士研究生,讲师,主要研究方向为计算机辅助设计与制造1

并行设计子任务调度的遗传算法原理与实现方法

殷国富　罗　阳　龙红能　成尔京

(四川大学制造科学与工程学院CAD/CAM 研究所　成都　610065)

摘要　建立了设计子任务调度的目标模型,提出了一种针对并行设计子任务调度的遗传算法1应用结果表明,在满足子任务间偏序关系条件下,文中算法能够得到设计子任务的最优调度方案1关键词　并行设计;子任务调度;任务偏序图;遗传算法中图法分类号　TP391

G enetic Algorithms for Subtask Scheduling in Concurrent Design

Y in Guofu Luo Yang Long Hongneng Cheng Erjing

(CA D/CA M Instit ute ,College of M anuf act uri ng Science &Engi neeri ng ,Sichuan U niversity ,Chengdu 610065)

Abstract Target model of subtask scheduling is established to minimize the overall time of execu 2tion 1Optimal scheduling can be realized under the constraints of partial ordering among subtasks 1K ey w ords concurrent design ;subtask scheduling ;partially 2ordered graph of tasks ;genetic algorithms

1　前 言

并行工程是对产品及其相关过程进行并行、一体化设计的一种系统化的工作模式,其主要特点是过程集成1因为设计在并行工程中占主导地位,所以并行工程的核心是并行设计[122]1其中,将分解的设计子任务分配给适宜的设计单元(完成设计子任务的个体或群体)求解是并行设计的重要内容之一1并行设计子任务的调度就是在多种匹配方法中寻找一种最合理的子任务分配方案1

文献[325]针对任务调度问题分别给出了相应的实现算法,但是这些算法都没有考虑任务间的时序关系,而这在设计任务集的分布并行求解中经常出现1文献[6]提出了一种基于任务时序关系的“均衡-适度”算法,但不是求解问题的最短时间解1文献[7]提出了一种任务优化调度算法,但重点考虑任

务均衡问题1特别地,当子任务数量较多以及子任务之间的时序关系较复杂时,任务调度问题是一个N P 难问题,也是一个组合优化问题,如果利用随机搜索法、爬山法等传统算法难以解决这类问题[829]1

为解决此类任务调度问题,本文给出了一个基于任务偏序图和子任务深度值的遗传算法,并介绍了该算法的总体框架、关键要素设计及其实现1

2　问题描述

在研究并行设计环境下设计子任务的调度问题时,针对该问题的描述所给出的假设往往各不相同1不失一般性,我们假设一个大的总任务已经按照某种分解规则被分解为若干个子任务,这些子任务的求解存在有序性和可并行性,并且各子任务将由不同的设计单元来承担,而不同的设计单元对各子任务的求解效率是不尽相同的1同时,假定需调度的

子任务数多于可提供的设计单元数,并且各设计单元中的子任务之间的关系是非抢先式的,即在同一设计单元中的一个子任务没有完成之前,其他分配在该节点上的子任务不能开始执行1

并行设计环境下的设计子任务之间的这种偏序关系我们可以用一个任务偏序图来描述,它是一个用有向非循环图(Directed Acylic Graph ,DA G )表示的各子任务之间的依赖关系和时序约束关系的子任务关系图1如图1所示为7个子任务的偏序关系图

1

图1　任务偏序图

根据任务偏序图,我们将设计任务调度问题模式化为DA G:G =(N ,P ,T ,A )1其中,N ={N S i |1≤i ≤m }是设计单元集,m 为设计单元总数,N S i 表示第i 个设计单元;P ={S T i |1≤i ≤n}是子任务集,n (n ≥m )为子任务的总数,S T i 表示第i 个子任务;T ={T ij |1≤i ≤m ,1≤j ≤n}是各子任务的执行时间集,T ij 表示设计单元N S i 执行子任务S T j 的效率(可以用时间表示);A ={A ij |1≤i ≤n ,1≤

j ≤n ,i ≠j}是有向边集,A ij (S T i →S T j )表示子任

务S T i 与子任务S T j 执行上的时序关系,即任务

S T j 在任务S T i 执行完成之后才能开始1

基于以上描述,并行设计环境下的设计任务调度的目标可以表述为:在满足任务偏序图中各子任务间时序约束关系的条件下寻找一个任务调度策略,将子任务集中的n 个子任务分别调度到设计单元集中的m 个设计单元中去执行,并使得整个任务

(总任务)的总的执行效率最高,即总的完成时间

最短1

3　基本定义和目标模型

定义11子任务相关性表示一个子任务的开始需依赖于另一个或多个子任务的结束,可表示为

{S T i ,S T i +1,…,S T i +k ;k ≥0}→S T j 1其中,{S T i ,S T i +1,…,S T i +k }中的各子任务称为子任务S T j

的前趋任务,子任务S T j 称为{S T i ,S T i +1,…,

S T i +k }中各子任务的后继任务1

定义21用任务关联矩阵A n ×n ={A ij |1≤i ≤n ,1≤j ≤n}来表示子任务之间的相关性1如果子任务S T i 完成后才能进行子任务S T j ,即S T i →

S T j ,则A ij =1;否则,A ij =01

定义31通过定义子任务的深度值来描述任务偏序图中各子任务间的相对层次关系1子任务S T i 的深度值

H (S T i )=

0,若pred (S T i )= 1+

max

S T j

∈pred (

S T i

)

(H (S T j )),否则

,

其中,pred (S T i )为子任务S T i 的前趋任务集1

定义41“单元-任务”匹配矩阵

N PM m ×n ={c ij |1≤i ≤m ,1≤j ≤n}描述了子任务与设计单元之间的调度关系1其中,

c ij =1,表示子任务S T j 调度给了设计单元N S i ;c ij

=0,表示子任务S T j 没有调度给设计单元N S i ,并

且调度在同一设计单元中的所有子任务是按其深度

值大小升序排列的1

一个“单元-任务”匹配矩阵实际上描述了满足任务偏序图中各子任务间时序约束关系条件的一个任务调度策略1

定义51“单元-任务”效率矩阵

N P T m ×n ={t ij |1≤i ≤m ,1≤j ≤n}描述了各设计单元对各子任务的执行效率1其中,t ij 表示设计单元NS i 执行子任务S T j 所需执行时间1

定义61调度在某一设计单元上的子任务的开始时间既与任务偏序图中它的前趋任务集中各子任务的结束时间有关,也与其在该设计单元中的前趋任务的结束时间有关,因此子任务的开始时间

T b (S T j )=

0,若pred (S T j )=

max S T i

∈pred (

S T j

)

(H e (S T i )),否则

,

其中,pred (S T j )为子任务S T j 在任务偏序图及其所在设计单元N S i 任务集中的所有前趋任务的集合;设T e (S T j )为结束时间,有

T e (S T j )=T b (S T j )+t ij 1

设对于一个设计子任务调度策略S ,t s (N S i )为策略S 中设计单元N S i 任务列表中的最后一个子任务的结束时间1设t (S )为整个任务调度策略S

的完成时间,

t (S )=max 1≤i ≤m

(t s (N S i ))

(1)

我们可以将并行设计环境下的设计子任务调度问题的目标模型描述为寻找一个设计子任务调度策略S ,使得t (S )最小,即优化目标函数为min S

(t (S ))1

3

2118期殷国富等:并行设计子任务调度的遗传算法原理与实现方法

此外,为了充分利用所有设计资源,一般每个设计单元至少应分配一个子任务,并且一个子任务只能调度给一个设计单元1根据这些边界约束条件,一个合法的、能够准确描述子任务调度的任务调度策略还应满足以下条件:

∑n

j=1

c ij≥1;

∑m

i=1

c ij=11

因此,一个基于任务之间时序关系的调度策略必须表示出两方面的信息:

(1)各个子任务被映射到哪个设计单元中去执行,即对ΠS T i∈P,要给出所在的设计单元N S i∈N;

(2)每个子任务在其所映射的设计单元上的开始时间,即对ΠS T i∈P,要给出其所在的设计单元N S i上的开始时间T b(S T i)1

4　任务调度问题的遗传算法设计遗传算法是模拟生物在自然环境中的遗传和进化过程的一种自适应全局优化概率搜索算法[9],其基本要素主要有染色体结构设计、个体适应度评价、遗传算子设计以及运行参数设定等1

411　算法总体框架

设计子任务调度问题的遗传算法的框架如下:

Step11读入一个任务偏序图,构造相应的任务关联矩阵,计算矩阵中各子任务的深度值H(S T i)1

Step21生成初始种群PO P(t),t=01

Step31如果不满足算法的终止条件,执行Step4;否则,转Step91

Step41计算种群中每个染色体的适应度1

Step51执行选择运算,形成下一代种群PO P(t+1)1

Step61以概率p ci和p co分别执行内部交叉运算和外部交叉运算1

Step71以概率p m执行变异运算1

Step81计算种群中的每个染色体的调度时间t(S(i)),保存最好(t(S)最小)的染色体,t=t+1,转Step31

Step91输出最好解,算法结束1

412　染色体结构设计

遗传算法中染色体结构主要有一维串结构、多参数的映射结构、变长串编码结构以及树结构编码等1由于在任务调度问题中,被调度的子任务之间以及同一设计单元的子任务之间存在一些关联信息,一维的数据结构难以表达这些信息,而树结构的特性又不能用来适应度评估,因此我们采用第3节定义的二维矩阵———“单元-任务”匹配矩阵N PM m×n来描述1

矩阵中的每一行可称为基因行,如{c ij|1≤j≤n}反映了调度在某个设计单元中的任务列表及其执行顺序;矩阵中的每一列称为基因列,如{c ij|1≤i ≤n}反映了某一设计子任务与设计单元之间的映射关系1

一个用二维矩阵描述的染色体,也就是设计子任务调度问题的一个解1

413　初始种群的生成

初始种群的生成方法是,将任务偏序图中的所有子任务按其深度值划分为h+1个子集DA G(i),其中0≤i≤h,h为DA G中所有子任务深度值中的最大值1对每个子集DA G(i),随机地将子集中的所有子任务指派到m个设计单元中去,然后将所有调度到同一设计单元中的子任务按照其深度值作升序排列,从而得到一个子任务调度策略,即种群中的一个个体,也就是如前所述的一个用二维矩阵描述的染色体1重复执行以上过程就可以生成具有一定规模的初始种群1

初始种群的规模是初始种群生成的一个关键因素,它对遗传算法具有直接的影响1初始种群的规模越大,其适应度函数评估次数越多,算法陷入局部解的危险性越小;但另一方面,初始种群规模越大,计算量相应增加,从而会影响算法的效能1所以一般应根据具体问题,依靠经验来确定初始种群的规模1

414　个体适应度评价

在遗传算法中,以个体适应度的大小来确定该个体被遗传到下一代群体中的概率1为正确计算不同情况下各个体的遗传概率,要求所有个体的适应度必须为正数或零,不能为负数1

在设计子任务的调度问题中,可以使用任务调度策略S的完成时间t(S)作为评价该策略优劣的标准1遗传算法按概率机制进行选择操作时,适应度值应满足非负性要求,使用如下适应度函数f(S)

=T max-t(S)1其中,T max=∑

n

j=1

max

1≤i≤m

(t ij)为常数,表示所有子任务在各设计单元中执行所需时间最大值的总和,显然f(S)≥01

415　遗传算子设计

41511　选择算子

选择算子的算法很多[10],本文采用适应度比例

4211计算机辅助设计与图形学学报2004年

方法1适应度比例方法按个体适应度的大小计算选择概率1设群体大小为k ,对于一个任务调度策略S (i ),即一个个体相应的遗传选择概率

P si =f (S (i ))

∑k

i =1

f (S (i ))1

其中,P si 反映个体S (i )的适应度在整个群体中的个

体适应度总和所占的比例,个体的适应度越高,其被选择的概率也越大;此外,为了使进化过程中优良的个体不被交叉和变异操作所破坏,对于选择概率较高的个体不参与交叉变异操作,而直接进入下一代群体141512　交叉算子

本文提出两种交叉算子:两个染色体部分对应基因列之间的外部交叉运算,即外部交叉算子;同一染色体内部的两个基因行对应基因片段之间的内部交叉运算,即内部交叉算子1

(1)外部交叉算子

对于子任务调度策略(个体)S (i )和S (j )的外部交叉算子的操作过程如下:

Step11随机生成一个数q (0≤q ≤h ),根据q 在S (i )和S (j )的基因列中选择交叉点,把S (i )和S (j )按基因列分成

前后两部分;

Step21相互交换S (i )和S (j )对应交叉点后的所有基因列,生成新的个体S ′

(i )和S ′(j )1显然,这种染色体间对应基因列交叉运算不会

破坏各设计单元(基因行)中各子任务深度值的升序

排列顺序1因此,新生成的个体S ′

(i )和S ′(j )仍然是满足定义4的1

(2)内部交叉算子

我们交换同一染色体中不同基因行之间对应的基因片段也可能产生新的个体1个体S (i )的内部交叉过程如下:

Step11随机生成一个数q (0≤q ≤h ),从S (i )中随机选

择两个基因行,根据q 在这两个基因行中选择交叉点,把它们分成前后两部分;

Step21将这两个基因行的后半部分所有任务相互交换,生成新的个体S ′

(i )1容易证明,这两个基因行在经过内部交叉运算

后,它们中的各基因(子任务)仍然是按照其深度值

升序排列的1因此,新生成的个体S ′

(i )也仍然是能够满足定义4的141513　变异算子

在子任务调度问题中,个体S (i )中的变异操作实质是子任务迁徙的过程,即某个设计单元中的一个子任务被重新调度到另一个设计单元中的过程,

具体操作过程如下:

Step11随机生成一个数q (0≤q ≤h ),计算个体S (i )中

各基因行中深度值等于q 的子任务数N i ,0≤i ≤n ;

Step21从N i 最大的基因行中随机选择一个深度值等

于q 的基因(子任务),将其迁徙到N i 最小的基因行中,从而

生成一个新的个体S ′

(i )1显然子任务经迁徙后,这两个基因行中的各基因仍然是按基因(子任务)深度值升序排列的1因

此,新生成的个体S ′

(i )也是满足定义4的15　遗传算法实现

下面以图1所示的7个任务的调度过程为例,说明本文提出的遗传算法的实现过程1

(1)从图1中我们可以得到这7个任务的任务

关联矩阵、前趋任务集和深度值,如表1所示1

表1　任务关联矩阵、前趋任务集和深度值

S T 1S T 2S T 3S T 4S T 5S T 6S T 7

前趋任务集

深度值

S T 10100000

0S T 20011100{S T 1}1S T 30000010{S T 2}2S T 40000001{S T 2}2S T 50000001{S T 2}2S T 60000001{S T 3}3S T 7

{S T 4,S T 5,S T 6}

4

(2)设有3个设计单元N S 1,N S 2和N S 3,我们

将这7个子任务按其深度值升序排列(H (S T 1)≤

H (S T 2)≤H (S T 3)≤H (S T 4)≤H (S T 5)≤H (S T 6)≤H (S T 7))及边界约束条件调度到这3个设

计单元中去,表2所示为一种可能的调度策略,即初始种群中的一个个体S ,显然该调度策略是满足定义4的1

表2　初始种群中的一个调度策略

S T 1S T 2S T 3S T 4S T 5S T 6S T 7深度值关系任务偏序关系NS 1

1010001H (S T 1)≤H (S T 3)≤H (S T 7)

S T 1→S T 3

→S T 7

NS 20100100H (S T 2)≤H (S T 5)

S T 2→S T 5

NS 30001010H (S T 4)≤H (S T 6)

S T 4→S T 6

(3)设各设计单元对各子任务的完成时间,即

“单元-任务”效率矩阵如表3所示1

5

2118期殷国富等:并行设计子任务调度的遗传算法原理与实现方法

表3　效率矩阵

S T1S T2S T3S T4S T5S T6S T7T max NS12314254

NS2423172333 NS31426122

(4)由表1～3,我们可以得到各子任务的所有前趋任务集,各任务的开始时间和结束时间,如表4所示1

表4　开始时间和结束时间

所有前趋任务集子任务开始时间子任务结束时间S T1 02

S T2{S T1}24

S T3{S T1,S T2}45

S T4{S T2}410

S T5{S T2}411

S T6{S T3,S T4}1012

S T7{S T3,S T4,S T5,S T6}1216

从表4中我们可以得到各设计单元最后一个子任务的结束时间t s(N S i)分别为16,11和121因此,由式(1)可得该任务调度策略S的完成时间t(S)=161这样我们就可以得到种群中每个个体的t(S),通过计算它们的适应度以及选择合适的交叉概率和变异概率,进行选择、交叉和变异等操作,最终生成新一代种群,计算并保存种群中t(S)最小的染色体1重复以上过程,当满足算法终止条件,如达到最多迭代代数或种群连续一定代数没有进化时,即可得到该子任务调度问题的最好解,即子任务的最优调度策略1

我们在PⅣ上用VC++编程实现了本文算法1针对文中实例,设定相同的算法参数,种群规模设为100,计算速度约为每分钟进化100代1进化代数设为200时,计算100次,最好结果是19,平均为201进化代数设为1000和2000时效果相似,都计算100次,得到的最好结果是14,平均为151用近似算法得到的结果是191从计算结果来看,遗传算法经过大量计算后能够得到相当好的方案,但进化代数没有必要超过10001

6　结 论

应用结果表明,本文算法可以得到相当好的调度方案1该算法的基本思想也可用于解决其他相似的调度问题,如生产调度1但是,由于遗传算法在求解大规模任务调度时计算效率偏低,因此应进一步研究多种优化方法混合求解的算法模型,以在计算效率和计算效果之间取得更好的平衡1

参　考　文　献

[1]Meng Mingchen,Han Xiangli1Concurrent Design[M]1Bei2

jing:China Machine Press,1999(in Chinese)

(孟明辰,韩向利1并行设计[M]1北京:机械工业出版社,

1999)

[2]Tong Bingshu1Modern CAD Technology[M]1Beijing:Ts2

inghua University Press,2000(in Chinese)

(童秉枢1现代CAD技术[M]1北京:清华大学出版社,

2000)

[3]K eyser Thomas K,Davis Robert P1Distributed computing ap2

proaches toward manufacturing scheduling problems[J]1IIE

Transactions,1998,30(4):379～390

[4]Vigo Daniele,Maniezzo Vittorio1A genetic/tabu thresholding

hybrid algorithm for the process allocation problem[J]1Journal

of Heuristics,1997,3(2):91～110

[5]Liu Zhenying,Fang Binxing,Jiang Yu,et al1A new algorithm

for scheduling Fork2Join task graph[J]1Journal of Software,

2002,13(4):693～697(in Chinese)

(刘振英,方滨兴,姜　誉,等1一个调度Fork2Join任务图的

新算法[J]1软件学报,2002,13(4):693～697)

[6]Li Bingtian,Yuan Qingke,Wang Yuegeng,et al1The equilib2

rium2moderation method of concurrent design task scheduling

[J]1Machine Tools and Fluid Drive,2002(5):80～83(in Chi2

nese)

(李炳田,袁清珂,王约庚,等1设计任务调度的均衡2适度法

[J]1机床与液压,2002(5):80～83)

[7]Ji Fengwei,Chen K en1Research on task scheduling based on

PDM[J]1Computer Integrated Manufacturing Systems,2002,

8(7):511～514(in Chinese)

(纪丰伟,陈　恳1基于PDM平台的任务调度技术研究[J]1

计算机集成制造系统,2002,8(7):511～514)

[8]Xing Wenxun,Xie Jinxing1Modern Optimal Algorithms[M]1

Beijing:Tsinghua University Press,1999(in Chinese)

(邢文训,谢金星1现代优化计算方法[M]1北京:清华大学

出版社,1999)

[9]Zhou Ming,Sun Shudong1G enetic Algorithms:Theory and Ap2

plications[M]1Beijing:National Defence Industry Press,1999

(in Chinese)

(周　明,孙树栋1遗传算法原理及应用[M]1北京:国防工

业出版社,1999)

[10]Zhong Qiuxi,Chen Huowang1G enetic operators in task match2

ing and scheduling[J]1Journal of National University of De2

fense Technology,2000,22(3):34～38(in Chinese)

(钟求喜,陈火旺1任务分配与调度中遗传算子的设计[J]1

国防科技大学学报,2000,22(3):34～38)

6211计算机辅助设计与图形学学报2004年

遗传算法并行化的研究.doc

遗传算法并行化的研究 学号：SC02011036 姓名：黄鑫 摘要 本文是针对遗传算法并行化进行了研究，首先简要给出了基本遗传算法的形式化描述，然后做了并行性的分析，详细介绍了遗传算法的结构化并行模型：步进模型，岛屿模型，邻接模型，最后指出了进一步要研究的课题。 关键词：遗传算法，并行计算，结构化GA 1引言 遗传算法（GA）是根据达尔文进化论“优胜劣汰，适者生存”的一种启发式搜索算法。采用选择，交叉，变异等基本变化算子在解空间同时进行多点搜索，本身固有并行性。随着大规模并行机的迅速发展，将并行机的高速性与遗传算法并行性结合起来，从而促进遗传算法的发展。然而，仅仅将基本遗传算法硬件并行化伴随着大量通讯开销等问题，从而必须对标准GA的进行改进，使得并行遗传算法不单单是遗传算法硬件并行实现，更重要的是结构化的遗传算法。本文首先给出了GA形式化描述，对基本GA的可并行性做出分析，然后给出了并行GA的模型，最后指出了并行遗传算法还需要解决的问题。 2 基本遗传算法 在这里我们不对遗传算法做过多的介绍，只是给出基本遗传算法的形式化描述：begin (1)initialization (1.1)产生一个初始群体 (1.2)评估第一代整个群体的适应度值 （2）while running do (2.1)选择父代 (2.2)交叉操作 (2.3)子代变异 (2.4)评估子代的适应度 (2.5)子代取代父代，形成新的一带个体 endwhile end 3 遗传算法的并行性分析 从第一节对遗传算法的描述，我们可以看出基本遗传算法模型是一个反复迭代的进化计算过程，通过对一组表示候选解的个体进行评价、选择、交叉、变异等操作，来产生新一代的个体(候选解)，这个迭代过程直到满足某种结束条件为止。对应于基本遗传算法的运行过程，为实现其并行化要求，可以从下面四种并行性方面着手对其进行改进和发展。 并行性Ⅰ：个体适应度评价的并行性。 个体适应度的评价在遗传算法中占用的运行时间比较大。通过对适应度并行计算方法的研究，可提高个体适应度评价的计算效率。 并行性Ⅱ：整个群体各个个体适应度评价的并行性。

遗传算法与优化问题

实验十遗传算法与优化问题 一、问题背景与实验目的 遗传算法(Genetic Algorithm —GA),就是模拟达尔文的遗传选择与自然淘汰的生物进化过程的计算模型，它就是由美国Michigan大学的J、Holla nd教授于1975 年首先提出的?遗传算法作为一种新的全局优化搜索算法，以其简单通用、鲁棒性强、适于并行处理及应用范围广等显著特点，奠定了它作为21世纪关键智能计算之一的地位. 本实验将首先介绍一下遗传算法的基本理论，然后用其解决几个简单的函数最值问题,使读者能够学会利用遗传算法进行初步的优化计算? 1. 遗传算法的基本原理 遗传算法的基本思想正就是基于模仿生物界遗传学的遗传过程?它把问题的参数用基因代表，把问题的解用染色体代表(在计算机里用二进制码表示),从而得到一个由具有不同染色体的个体组成的群体?这个群体在问题特定的环境里生存 竞争,适者有最好的机会生存与产生后代?后代随机化地继承了父代的最好特征，并也在生存环境的控制支配下继续这一过程.群体的染色体都将逐渐适应环境，不断进化,最后收敛到一族最适应环境的类似个体，即得到问题最优的解?值得注意的一点就是，现在的遗传算法就是受生物进化论学说的启发提出的，这种学说对我们用计算机解决复杂问题很有用，而它本身就是否完全正确并不重要(目前生物界对此学说尚有争议). (1)遗传算法中的生物遗传学概念 由于遗传算法就是由进化论与遗传学机理而产生的直接搜索优化方法；故而 在这个算法中要用到各种进化与遗传学的概念? 首先给出遗传学概念、遗传算法概念与相应的数学概念三者之间的对应关系这些概念

（2）遗传算法的步骤 遗传算法计算优化的操作过程就如同生物学上生物遗传进化的过程，主要有三个基本操作（或称为算子）:选择（Selection）、交叉（Crossover）、变异（Mutation）. 遗传算法基本步骤主要就是：先把问题的解表示成“染色体”，在算法中也就就是以二进制编码的串，在执行遗传算法之前，给出一群“染色体”，也就就是假设的可行解.然后，把这些假设的可行解置于问题的“环境”中,并按适者生存的原则从中选 择出较适应环境的“染色体”进行复制 ，再通过交叉、变异过程产生更适 应环境的新一代“染色体”群.经过这样的一代一代地进化，最后就会收敛到最适应环境的一个“染色体”上，它就就是问题的最优解. 下面给出遗传算法的具体步骤，流程图参见图1: 第一步:选择编码策略，把参数集合（可行解集合）转换染色体结构空间； 第二步:定义适应函数，便于计算适应值； 第三步:确定遗传策略，包括选择群体大小，选择、交叉、变异方法以及确定交叉概率、变异概率等遗传参数； 第四步:随机产生初始化群体； 第五步:计算群体中的个体或染色体解码后的适应值； 第六步:按照遗传策略，运用选择、交叉与变异算子作用于群体，形成下一代群体； 第七步:判断群体性能就是否满足某一指标、或者就是否已完成预定的迭代次数,不满足则返回第五步、或者修改遗传策略再返回第六步. 图1 一个遗传算法的具体步骤

第三章-遗传算法的理论基础

第三章 遗传算法的理论基础 遗传算法有效性的理论依据为模式定理和积木块假设。模式定理保证了较优的模式(遗传算法的较优解)的样本呈指数级增长，从而满足了寻找最优解的必要条件，即遗传算法存在着寻找到全局最优解的可能性。而积木块假设指出，遗传算法具备寻找到全局最优解的能力，即具有低阶、短距、高平均适应度的模式(积木块)在遗传算子作用下，相互结合，能生成高阶、长距、高平均适应度的模式，最终生成全局最优解。Holland 的模式定理通过计算有用相似性，即模式(Pattern)奠定了遗传算法的数学基础。该定理是遗传算法的主要定理，在一定程度上解释了遗传算法的机理、数学特性以及很强的计算能力等特点。 3.1 模式定理 不失一般性，本节以二进制串作为编码方式来讨论模式定理(Pattern Theorem)。 定义3.1 基于三值字符集{0，1，*}所产生的能描述具有某些结构相似性的0、1字符串集的字符串称作模式。 以长度为5的串为例，模式*0001描述了在位置2、3、4、5具有形式“0001”的所有字符串，即(00001，10001) 。由此可以看出，模式的概念为我们提供了一种简洁的用于描述在某些位置上具有结构相似性的0、1字符串集合的方法。 引入模式后，我们看到一个串实际上隐含着多个模式(长度为 n 的串隐含着2n 个模式) ，一个模式可以隐含在多个串中，不同的串之间通过模式而相互联系。遗传算法中串的运算实质上是模式的运算。因此，通过分析模式在遗传操作下的变化，就可以了解什么性质被延续，什么性质被丢弃，从而把握遗传算法的实质，这正是模式定理所揭示的内容 定义3.2 模式H 中确定位置的个数称作该模式的阶数，记作o(H)。比如，模式 011*1*的阶数为4，而模式 0* * * * *的阶数为1。 显然，一个模式的阶数越高，其样本数就越少，因而确定性越高。 定义3.3 模式H 中第一个确定位置和最后一个确定位置之间的距离称作该模式的定义距，记作)(H δ。比如，模式 011*1*的定义距为4，而模式 0* * * * *的定义距为0。 模式的阶数和定义距描述了模式的基本性质。 下面通过分析遗传算法的三种基本遗传操作对模式的作用来讨论模式定理。令)(t A 表示第t 代中串的群体，以),,2,1)((n j t A j =表示第t 代中第j 个个体串。 1．选择算子 在选择算子作用下，与某一模式所匹配的样本数的增减依赖于模式的平均适值，与群体平均适值之比，平均适值高于群体平均适值的将呈指数级增长；而平均适值低于群体平均适值的模式将呈指数级减少。其推导如下： 设在第t 代种群)(t A 中模式所能匹配的样本数为m ，记为),(t H m 。在选择中，一个位串 j A 以概率/j j i P f f =∑被选中并进行复制，其中j f 是个体)(t A j 的适应度。假设一代中群体 大小为n ，且个体两两互不相同，则模式H 在第1+t 代中的样本数为：

遗传算法的基本原理

第二章 遗传算法的基本原理 2.1 遗传算法的基本描述 2.1.1 全局优化问题 全局优化问题的定义：给定非空集合S 作为搜索空间，f ：S —>R 为目标函数，全局优化问题作为任务)(max x f S x ∈给出，即在搜索空间中找到至少一个使目标函数最大化的点。 全局最大值（点）的定义：函数值+∞<=)(**x f f 称为一个全局最大值，当且仅当x ? S x ∈，(ρi i b a <，i 12）定义适应度函数f(X)； 3）确定遗传策略，包括群体规模，选择、交叉、变异算子及其概率。 4）生成初始种群P ； 5）计算群体中各个体的适应度值； 6）按照遗传策略，将遗传算子作用于种群，产生下一代种群； 7）迭代终止判定。 遗传算法涉及六大要素：参数编码，初始群体的设定，适应度函数的设计，遗传操作的设计，控制参数的设定，迭代终止条件。

2.1.3 遗传编码 由于GA 计算过程的鲁棒性，它对编码的要求并不苛刻。原则上任何形式的编码都可以，只要存在合适的对其进行操作的遗传算子，使得它满足模式定理和积木块假设。 由于编码形式决定了交叉算子的操作方式，编码问题往往称作编码-交叉问题。 对于给定的优化问题，由GA 个体的表现型集合做组成的空间称为问题（参数）空间，由GA 基因型个体所组成的空间称为GA 编码空间。遗传算子在GA 编码空间中对位串个体进行操作。 定义：由问题空间向GA 编码空间的映射称为编码，而有编码空间向问题空间的映射成为译码。 1）2）3）它们对1） 2） k =1,2,…,K; l =1,2,…,L; K=2L 其中，个体的向量表示为),,,(21kL k k k a a a a =，其字符串形式为kL k k k a a a s 21=，s k 称为个体a k 对应的位串。表示精度为)12/()(--=?L u v x 。 将个体又位串空间转换到问题空间的译码函数],[}1,0{:v u L →Γ的公式定义为： 对于n 维连续函数),,2,1](,[),,,,(),(21n i v u x x x x x x f i i i n =∈=，各维变量的二进制

遗传算法基本理论实例

目录 _ 一、遗产算法的由来 (2) 二、遗传算法的国内外研究现状 (3) 三、遗传算法的特点 (5) 四、遗传算法的流程 (7) 五、遗传算法实例 (12) 六、遗传算法编程 (17) 七、总结 ......... 错误!未定义书签。附录一：运行程序.. (19)

遗传算法基本理论与实例 一、遗产算法的由来 遗传算法（Genetic Algorithm，简称GA）起源于对生物系统所进行的计算机模拟研究。20世纪40年代以来，科学家不断努力从生物学中寻求用于计算科学和人工系统的新思想、新方法。很多学者对关于从生物进化和遗传的激励中开发出适合于现实世界复杂适应系统研究的计算技术——生物进化系统的计算模型，以及模拟进化过程的算法进行了长期的开拓性的探索和研究。John H.Holland教授及其学生首先提出的遗传算法就是一个重要的发展方向。 遗传算法借鉴了达尔文的进化论和孟德尔、摩根的遗传学说。按照达尔文的进化论，地球上的每一物种从诞生开始就进入了漫长的进化历程。生物种群从低级、简单的类型逐渐发展成为高级复杂的类型。各种生物要生存下去及必须进行生存斗争，包括同一种群内部的斗争、不同种群之间的斗争，以及生物与自然界无机环境之间的斗争。具有较强生存能力的生物个体容易存活下来，并有较多的机会产生后代；具有较低生存能力的个体则被淘汰，或者产生后代的机会越来越少。，直至消亡。达尔文把这一过程和现象叫做“自然选择，适者生存”。按照孟德尔和摩根的遗传学理论，遗传物质是作为一种指令密码封装在每个细胞中，并以基因的形式排列在染色体上，每个基因有特殊的位置并控制生物的某些特性。不同的基因组合产生的个体对环境的适应性不一样，通过基因杂交和突变可以产生对环境适应性强的后代。经过优胜劣汰的自然选择，适应度值高的基因结构就得以保存下来，从而逐渐形成了经典的遗传学染色体理论，揭示了遗传和变异的

并行遗传算法

并行遗传算法及其应用 1、遗传算法（GA）概述 GA是一类基于自然选择和遗传学原理的有效搜索方法，它从一个种群开始，利用选择、交叉、变异等遗传算子对种群进行不断进化，最后得到全局最优解。生物遗传物质的主要载体是染色体，在GA中同样将问题的求解表示成“染色体Chromosome”，通常是二进制字符串表示，其本身不一定是解。首先，随机产生一定数据的初始染色体，这些随机产生的染色体组成一个种群（Population），种群中染色体的数目称为种群的大小或者种群规模。第二：用适值度函数来评价每一个染色体的优劣，即染色体对环境的适应程度，用来作为以后遗传操作的依据。第三：进行选择（Selection），选择过程的目的是为了从当前种群中选出优良的染色体，通过选择过程，产生一个新的种群。第四：对这个新的种群进行交叉操作，变异操作。交叉、变异操作的目的是挖掘种群中个体的多样性，避免有可能陷入局部解。经过上述运算产生的染色体称为后代。最后，对新的种群（即后代）重复进行选择、交叉和变异操作，经过给定次数的迭代处理以后，把最好的染色体作为优化问题的最优解。 GA通常包含5个基本要素：1、参数编码：GA是采用问题参数的编码集进行工作的，而不是采用问题参数本身，通常选择二进制编码。2、初始种群设定：GA随机产生一个由N个染色体组成的初始种群（Population），也可根据一定的限制条件来产生。种群规模是指种群中所含染色体的数目。3、适值度函数的设定：适值度函数是用来区分种群中个体好坏的标准，是进行选择的唯一依据。目前主要通过目标函数映射成适值度函数。4、遗传操作设计：遗传算子是模拟生物基因遗传的操作，遗传操作的任务是对种群的个体按照它们对环境的适应的程度施加一定的算子，从而实现优胜劣汰的进化过程。遗传基本算子包括：选择算子，交叉算子，变异算子和其他高级遗传算子。5、控制参数设定：在GA的应用中，要首先给定一组控制参数：种群规模，杂交率，变异率，进化代数等。 GA的优点是擅长全局搜索，一般来说，对于中小规模的应用问题，能够在许可的范围内获得满意解，对于大规模或超大规模的多变量求解任务则性能较差。另外，GA本身不要求对优化问题的性质做一些深入的数学分析，从而对那些不

遗传算法的并行实现

遗 传 算 法 （基于遗传算法求函数最大值） 指导老师：刘建丽 学号：S201007156 姓名：杨平 班级：研10级1班

遗传算法 一、 遗传算法的基本描述 遗传算法（Genetic Algorithm ，GA ）是通过模拟自然界生物进化过程来求解优化问题的一类自组织、自适应的人工智能技术。它主要基于达尔文的自然进化论和孟德尔的遗传变异理论。多数遗传算法的应用是处理一个由许多个体组成的群体，其中每个个体表示问题的一个潜在解。对个体存在一个评估函数来评判其对环境的适应度。为反映适者生存的思想，算法中设计一个选择机制，使得：适应度好的个体有更多的机会生存。在种群的进化过程中，主要存在两种类型的遗传算子：杂交和变异。这些算子作用于个体对应的染色体，产生新的染色体，从而构成下一代种群中的个体。该过程不断进行，直到找到满足精度要求的解，或者达到设定的进化代数。显然，这样的思想适合于现实世界中的一大类问题，因而具有广泛的应用价值。遗传算法的每一次进化过程中的，各个体之间的操作大多可以并列进行，因此，一个非常自然的想法就是将遗传算法并行化，以提高计算速度。本报告中试图得到一个并行遗传算法的框架，并考察并行化之后的一些特性。为简单起见（本来应该考虑更复杂的问题，如TSP 。因时间有些紧张，做如TSP 等复杂问题怕时间不够，做不出来，请老师原谅），考虑的具有问题是：对给定的正整数n 、n 元函数f ，以及定义域D ，求函数f 在D 内的最大值。 二、 串行遗传算法 1． 染色体与适应度函数 对函数优化问题，一个潜在的解就是定义域D 中的一个点011(,,...,)n x x x -，因此，我们只需用一个长度为n 的实数数组来表示一个个体的染色体。由于问题中要求求函数f 的最大值，我们可以以个体所代表点011(,,...,)n x x x -在f 函数下的值来判断该个体的好坏。因此，我们直接用函数f 作为个体的适应度函数。 2． 选择机制 选择是遗传算法中最主要的机制，也是影响遗传算法性能最主要的因素。若选择过程中适应度好的个体生存的概率过大，会造成几个较好的可行解迅速占据种群，从而收敛于局部最优解；反之，若适应度对生存概率的影响过小，则会使算法呈现出纯粹的随机徘徊行为，算法无法收敛。下面我们介绍在实验中所使用的选择机制。

谈谈遗传算法的原理

谈谈遗传算法的原理 发表时间：2011-08-24T09:52:45.450Z 来源：《魅力中国》2011年7月上供稿作者：朱小宝 [导读] 从上表中可以看出，群体经过一代进化之后，其适应度的最大值、平均值都得到了明显的改进。 朱小宝 (南昌航空大学飞行器工程学院江西南昌 330029) 中图分类号：TP301.6 文献标识码：A 文章编号：1673-0992（2011）07-0000-01摘要：自从霍兰德于1975年在他的著作《Adaption im Natural and artificial Systems》中首次提出遗传算法以来，经过了近30年的研究，现在已经发展到了一个比较成熟的阶段，并且在实际中得到了很好的应用。为了更好的了解遗传算法，本文通过最简单的一个手工计算实例来还原遗传算法的全过程。 关键词：遗传算法生物进化染色体种群 自然界的生物进化是按“适者生存，优胜劣汰”规律进行的，而遗传算法就是模拟达尔文的自然选择学说和自然界的生物进化过程的一种计算模型。其基本思想是力求充分模仿这一自然寻优过程的随机性、鲁棒性和全局性，这是一种全局优化搜索算法，因为其直接对结构对象进行操作，不存在求导和函数连续性的限定。 遗传算法采用简单的编码技术来表示各种复杂的结构，并通过对一组编码表示进行简单的遗传操作和优胜劣汰的自然选择来指导学习和确定搜索的方向。遗传算法的操作对象是一群二进制串(称为染色体)，即种群。这里每一个染色体都对应问题的一个解。从初始种群出发，采用基于适应值比例的选择策略在当前种群中选择个体，使用杂交和变异来产生下一代种群。如此模仿生命的进化一代代演化下去，直到满足期望的终止条件为止。 遗传算法主要步骤： （1）编码：由于遗传算法不能直接处理解空间的数据，必须通过编码将它们表示成遗传空间的基因型串结构数据。 （2）选择初始种群：随机产生N个初始串结构数据，每个串结构数据称为一个个体，也称为染色体，N个个体体构成了一个种群。 （3）选择适应度函数：遗传算法在搜索过程中一般不需要其他外部信息或知识，仅用适应度函数来评价个体的适应度。 （4）选择：利用选择概率再随机的选择个体和复制数量。选择算子的设计可依据达尔文适者生存的进化论原则，选择概率大的被选中的机会较多。 （5）杂交：对被选中的个体进行随机配对并随机的选择基因交换位，交换基因后产生新的个体，全体新个体构成新的（下一代）种群。 （6）变异：变异操作是按位进行求反，对二二进制编码的个体而言，就是对随机选中的某位进行求反运算，即“0”变“1”，“1”变大“0”。 （7）一代种群通过遗传，即选择、杂交和变异产生下一代种群。新种群又可重复上述的选择、杂交和变异的遗传过程。 为更好地理解遗传算法的运算过程，下面用手工计算来简单地模拟遗传算法的各个主要执行步骤。 求下述二元函数的最大值： Max f(x1,x2)= x12+ x22 S,t, x1∈{1,2,3,4,5,6,7} x2∈{1,2,3,4,5,6,7} (1) 个体编码 遗传算法的运算对象是表示个体的符号串，所以必须把变量 x1, x2 编码为一种符号串。本题中，用无符号二进制整数来表示。因 x1, x2 为 0 ~ 7之间的整数，所以分别用3位无符号二进制整数来表示，将它们连接在一起所组成的6位无符号二进制数就形成了个体的基因型，表示一个可行解。例如，基因型 X＝101110 所对应的表现型是：x＝[5，6]。个体的表现型x和基因型X之间可通过编码和解码程序相互转换。 (2) 初始群体的产生 群体规模的大小取为4，即群体由4个个体组成，每个个体可通过随机方法产生。 如：011101，101011，011100，111001 (3) 适应度汁算 目标函数总取非负值，并且是以求函数最大值为优化目标，故可直接用目标函数值作为个体的适应度。 (4) 选择运算 我们采用与适应度成正比的概率来确定各个个体复制到下一代群体中的数量。其具体操作过程是： 1.先计算出群体中所有个体的适应度的总和 fi ( i=1.2,…,M )； 2.fi其次计算出每个个体的相对适应度的大小 fi / ，它即为每个个体被遗传到下一代群体中的概率， 3.每个概率值组成一个区域，全部概率值之和为1； 4.最后再产生一个0到1之间的随机数，依据该随机数出现在上述哪一个概率区域内来确定各个个体被选中的次数。

遗传算法的基本原理

遗传算法的基本原理 LG GROUP system office room 【LGA16H-LGYY-LGUA8Q8-LGA162】

第二章 遗传算法的基本原理 遗传算法的基本描述 2.1.1 全局优化问题 全局优化问题的定义：给定非空集合S 作为搜索空间，f ：S —>R 为目标函数，全局优化问题作为任务)(max x f S x ∈给出，即在搜索空间中找到至少一个使目标函数最大化的点。 全局最大值（点）的定义：函数值+∞<=)(**x f f 称为一个全局最大值，当且仅当)()(*x f x f S x ≤?∈?成立时，S x ∈*被称为一个全局最大值点（全局最大解）。 局部极大值与局部极大值点（解）的定义： 假设在S 上给定了某个距离度量ρ，如果对S x ∈'，0>?ε，使得对S x ∈?， )()(),(''x f x f x x ≤?<ερ，则称x ’为一个局部极大值点，f (x ’)为一个局部极大值。当目标函数有多个局部极大点时，被称为多峰或多模态函数（multi-modality function ）。 主要考虑两类搜索空间： 伪布尔优化问题：当S 为离散空间B L ={0,1}L ,即所有长度为L 且取值为0或1的二进制位串的集合时，相应的优化问题在进化计算领域称为伪布尔优化问题。 连续参数优化问题：当取S 伪n 维实数空间R n 中的有界集合],[1i i n i b a S =∏=，其中i i b a <，i = 1, 2, … , n 时，相应的具有连续变量的优化问题称为连续参数优化问题。 对S 为B L ={0,1}L ，常采用的度量时海明距离，当],[1i i n i b a S =∏=时，常采用的度量就是欧氏距离。 2.1.2 遗传算法的基本流程 遗传算法的基本步骤如下： 1）选择编码策略，把参数集合X 和域转换为位串结构空间S ； 2）定义适应度函数f(X)； 3）确定遗传策略，包括群体规模，选择、交叉、变异算子及其概率。 4）生成初始种群P ； 5）计算群体中各个体的适应度值； 6）按照遗传策略，将遗传算子作用于种群，产生下一代种群； 7）迭代终止判定。 遗传算法涉及六大要素：参数编码，初始群体的设定，适应度函数的设计，遗传操作的设计，控制参数的设定，迭代终止条件。 2.1.3 遗传编码 由于GA 计算过程的鲁棒性，它对编码的要求并不苛刻。原则上任何形式的编码都可以，只要存在合适的对其进行操作的遗传算子，使得它满足模式定理和积木块假设。 由于编码形式决定了交叉算子的操作方式，编码问题往往称作编码-交叉问题。 对于给定的优化问题，由GA 个体的表现型集合做组成的空间称为问题（参数）空间，由GA 基因型个体所组成的空间称为GA 编码空间。遗传算子在GA 编码空间中对位串个体进行操作。

遗传算法基本原理111

第二章遗传算法的基本原理 2.1 遗传算法的基本描述 2.1.1 全局优化问题 全局优化问题的定义：给定非空集合S作为搜索空间，f：S—>R为目标函数，全局优化问题作为任务给出，即在搜索空间中找到至少一个使目标函数最大化的点。 全局最大值（点）的定义：函数值称为一个全局最大值，当且仅当成立时，被称为一个全局最大值点（全局最 大解）。 局部极大值与局部极大值点（解）的定义： 假设在S上给定了某个距离度量，如果对，，使得对， ，则称x’为一个局部极大值点，f(x’)为一个局部极大 值。当目标函数有多个局部极大点时，被称为多峰或多模态函数（multi-modality function）。 主要考虑两类搜索空间： 伪布尔优化问题：当S为离散空间B L={0,1}L,即所有长度为L且取值为0或1的二进制位串的集合时，相应的优化问题在进化计算领域称为伪布尔优化问题。 连续参数优化问题：当取S伪n维实数空间R n中的有界集合，其中，i = 1, 2, … , n时，相应的具有连续变量的优化问题称为连续参数优化问题。 对S为B L={0,1}L，常采用的度量时海明距离，当时，常采用的度量就是欧氏距离。 2.1.2 遗传算法的基本流程

遗传算法的基本步骤如下： 1）选择编码策略，把参数集合X和域转换为位串结构空间S； 2）定义适应度函数f(X)； 3）确定遗传策略，包括群体规模，选择、交叉、变异算子及其概率。 4）生成初始种群P； 5）计算群体中各个体的适应度值； 6）按照遗传策略，将遗传算子作用于种群，产生下一代种群； 7）迭代终止判定。 遗传算法涉及六大要素：参数编码，初始群体的设定，适应度函数的设计，遗传操作的设计，控制参数的设定，迭代终止条件。 2.1.3 遗传编码 由于GA计算过程的鲁棒性，它对编码的要求并不苛刻。原则上任何形式的编码都可以，只要存在合适的对其进行操作的遗传算子，使得它满足模式定理和积木块假设。 由于编码形式决定了交叉算子的操作方式，编码问题往往称作编码-交叉问题。 对于给定的优化问题，由GA个体的表现型集合做组成的空间称为问题（参数）空间，由GA基因型个体所组成的空间称为GA编码空间。遗传算子在GA

遗传算法的原理及MATLAB程序实现

1 遗传算法的原理 1.1 遗传算法的基本思想 遗传算法（genetic algorithms，GA）是一种基于自然选择和基因遗传学原理，借鉴了生物进化优胜劣汰的自然选择机理和生物界繁衍进化的基因重组、突变的遗传机制的全局自适应概率搜索算法。 遗传算法是从一组随机产生的初始解（种群）开始，这个种群由经过基因编码的一定数量的个体组成，每个个体实际上是染色体带有特征的实体。染色体作为遗传物质的主要载体，其内部表现（即基因型）是某种基因组合，它决定了个体的外部表现。因此，从一开始就需要实现从表现型到基因型的映射，即编码工作。初始种群产生后，按照优胜劣汰的原理，逐代演化产生出越来越好的近似解。在每一代，根据问题域中个体的适应度大小选择个体，并借助于自然遗传学的遗传算子进行组合交叉和变异，产生出代表新的解集的种群。这个过程将导致种群像自然进化一样，后代种群比前代更加适应环境，末代种群中的最优个体经过解码，可以作为问题近似最优解。 计算开始时，将实际问题的变量进行编码形成染色体，随机产生一定数目的个体，即种群，并计算每个个体的适应度值，然后通过终止条件判断该初始解是否是最优解，若是则停止计算输出结果，若不是则通过遗传算子操作产生新的一代种群，回到计算群体中每个个体的适应度值的部分，然后转到终止条件判断。这一过程循环执行，直到满足优化准则，最终产生问题的最优解。图1-1给出了遗传算法的基本过程。 1.2 遗传算法的特点 1.2.1 遗传算法的优点 遗传算法具有十分强的鲁棒性，比起传统优化方法，遗传算法有如下优点： 1. 遗传算法以控制变量的编码作为运算对象。传统的优化算法往往直接利用控制变量的实际值的本身来进行优化运算，但遗传算法不是直接以控制变量的值，而是以控制变量的特定形式的编码为运算对象。这种对控制变量的编码处理方式，可以模仿自然界中生物的遗传和进化等机理，也使得我们可以方便地处理各种变量和应用遗传操作算子。 2. 遗传算法具有内在的本质并行性。它的并行性表现在两个方面，一是遗传

并行遗传算法

1、遗传算法（GA）概述 GA是一类基于自然选择和遗传学原理的有效搜索方法，它从一个种群开始，利用选择、交叉、变异等遗传算子对种群进行不断进化，最后得到全局最优解。生物遗传物质的主要载体是染色体，在GA中同样将问题的求解表示成“染色体Chromosome”，通常是二进制字符串表示，其本身不一定是解。首先，随机产生一定数据的初始染色体，这些随机产生的染色体组成一个种群（Population），种群中染色体的数目称为种群的大小或者种群规模。第二：用适值度函数来评价每一个染色体的优劣，即染色体对环境的适应程度，用来作为以后遗传操作的依据。第三：进行选择（Selection），选择过程的目的是为了从当前种群中选出优良的染色体，通过选择过程，产生一个新的种群。第四：对这个新的种群进行交叉操作，变异操作。交叉、变异操作的目的是挖掘种群中个体的多样性，避免有可能陷入局部解。经过上述运算产生的染色体称为后代。最后，对新的种群（即后代）重复进行选择、交叉和变异操作，经过给定次数的迭代处理以后，把最好的染色体作为优化问题的最优解。 GA通常包含5个基本要素：1、参数编码：GA是采用问题参数的编码集进行工作的，而不是采用问题参数本身，通常选择二进制编码。2、初始种群设定：GA随机产生一个由N个染色体组成的初始种群（Population），也可根据一定的限制条件来产生。种群规模是指种群中所含染色体的数目。3、适值度函数的设定：适值度函数是用来区分种群中个体好坏的标准，是进行选择的唯一依据。目前主要通过目标函数映射成适值度函数。4、遗传操作设计：遗传算子是模拟生物基因遗传的操作，遗传操作的任务是对种群的个体按照它们对环境的适应的程度施加一定的算子，从而实现优胜劣汰的进化过程。遗传基本算子包括：选择算子，交叉算子，变异算子和其他高级遗传算子。5、控制参数设定：在GA的应用中，要首先给定一组控制参数：种群规模，杂交率，变异率，进化代数等。 GA的优点是擅长全局搜索，一般来说，对于中小规模的应用问题，能够在许可的范围内获得满意解，对于大规模或超大规模的多变量求解任务则性能较差。另外，GA本身不要求对优化问题的性质做一些深入的数学分析，从而对那些不太熟悉数学理论和算法的使用者来说，无疑是方便的。 2、遗传算法的运行机理： 对GA运行机理的解释有两类: 一是传统的模式理论；二是1990 年以后发展起来的有限状态马尔可夫链模型。 （1）模式理论：由Holland创建，主要包括模式定理，隐并行性原理和积木块假说三部分。模式是可行域中某些特定位取固定值的所有编码的集合。模式理论认为遗传算法实质上是模式的运算，编码的字母表越短，算法处理一代种群时隐含处理的模式就越多。当算法采用二进制编码时，效率最高，处理规模为N的一代种群时，可同时处理O(N3)个模式。遗传算法这种以计算少量编码适应度而处理大量模式的性质称为隐并行性。模式理论还指出，目标函数通常满足积木块假说，即阶数高，长度长，平均适应度高的模式可以由阶数低，长度短，平均适应度高的模式(积木块)在遗传算子的作用下，接合而生成。而不满足积木块假说的优化问题被称为骗问题(deceptive problem)。模式理论为遗传算法构造了一条通过在种群中不断积累、拼接积木块以达到全局最优解的寻优之路。但近十多年的研究，特别是实数编码遗传算法的广泛应用表明，上述理论与事实不符。 （2）有限状态马尔可夫链模型：由于模式理论的种种缺陷，研究者开始尝试利用有限状态马尔可夫链模型研究遗传算法的运行过程。对于遗传算法可以解决的优化问题，问题的可行域都是由有限个点组成的，即便是参数可以连续取值的问题，实际上搜索空间也是以要求精度为单位的离散空间，因此遗传算法的实际运行过程可以用有限状态马尔可夫链的状态转移过程建模和描述。对于有m 个可行解的目标函数和种群规模为N的遗传算法，N 个个体共有种组合，相应的马尔可夫模型也有个状态。实际优化问题的可行解数量m 和种群规模

遗传算法的基本原理

遗传算法的基本原理 遗传算法类似于自然进化，通过作用于染色体上的基因寻找好的染色体来求解问题。与自然界相似，遗传算法对求解问题的本身一无所知，它所需要的仅是对算法所产生的每个染色体进行评价，并基于适应值来选择染色体，使适应性好的染色体有更多的繁殖机会。在遗传算法中，通过随机方式产生若干个所求解问题的数字编码，即染色体，形成初始群体；通过适应度函数给每个个体一个数值评价，淘汰低适应度的个体，选择高适应度的个体参加遗传操作，经过遗传操作后的个体集合形成下一代新的种群。对这个新种群进行下一轮进化。这就是遗传算法的基本原理。 下面就是遗传算法思想： (1) 初始化群体; (2) 计算群体上每个个体的适应度值; (3) 按由个体适应度值所决定的某个规则选择将进入下一代的个体; (4) 按概率PX进行交叉操作; (5) 按概率PM进行突变操作; (6) 没有满足某种停止条件，则转第(2)步，否则进入(7)。 (7) 输出种群中适应度值最优的染色体作为问题的满意解或最优解。 程序的停止条件最简单的有如下二种：完成了预先给定的进化代数则停止；种群中的最优个体在连续若干代没有改进或平均适应度在连续若干代基本没有改进时停止。 根据遗传算法思想可以画出如右图所示的简单遗传算法框图： 图 3.22 简单遗传算法框图 遗传算法的选择算子 选择即从当前群体中选择适应值高的个体以生成交配池的过程. 遗传算法中最常用的选择方式是轮盘赌(Roulette Wheel)选择方式, 也称比例选择或复制. 在该方法中, 各个个体被选择的概率和其适应度值成比例. 设群体规模大小为N, 个体i 的适应度值为Fi , 则这个个体

遗传算法的并行实现

遗传算法的并行实现 章衡 2007310437 一、 问题描述 遗传算法是通过模拟自然界生物进化过程来求解优化问题的一类自组织、自适应的人工智能技术。它主要基于达尔文的自然进化论和孟德尔的遗传变异理论。多数遗传算法的应用是处理一个由许多个体组成的群体，其中每个个体表示问题的一个潜在解。对个体存在一个评估函数来评判其对环境的适应度。为反映适者生存的思想，算法中设计一个选择机制，使得：适应度好的个体有更多的机会生存。在种群的进化过程中，主要存在两种类型的遗传算子：杂交和变异。这些算子作用于个体对应的染色体，产生新的染色体，从而构成下一代种群中的个体。该过程不断进行，直到找到满足精度要求的解，或者达到设定的进化代数。显然，这样的思想适合于现实世界中的一大类问题，因而具有广泛的应用价值。 遗传算法的每一次进化过程中的，各个体之间的操作大多可以并列进行，因此，一个非常自然的想法就是将遗传算法并行化，以提高计算速度。本报告中试图得到一个并行遗传算法的框架，并考察并行化之后的一些特性。为简单起见（本来应该考虑更复杂的问题，如TSP 。因时间有些紧张，请老师原谅），考虑的具有问题是：对给定的正整数n 、n 元函数f ，以及定义域D ，求函数f 在D 内的最大值。 二、 串行遗传算法 1． 染色体与适应度函数 对函数优化问题，一个潜在的解就是定义域D 中的一个点011(,,...,)n x x x -，因此，我 们只需用一个长度为n 的实数数组来表示一个个体的染色体。由于问题中要求求函数f 的最大值，我们可以以个体所代表点011(,,...,)n x x x -在f 函数下的值来判断该个体的好坏。因此，我们直接用函数f 作为个体的适应度函数。 2． 选择机制 选择是遗传算法中最主要的机制，也是影响遗传算法性能最主要的因素。若选择过程中 适应度好的个体生存的概率过大，会造成几个较好的可行解迅速占据种群，从而收敛于局部最优解；反之，若适应度对生存概率的影响过小，则会使算法呈现出纯粹的随机徘徊行为，算法无法收敛。下面我们介绍在实验中所使用的选择机制。

(完整版)遗传算法的基本原理

遗传算法的基本原理和方法 一、编码 编码：把一个问题的可行解从其解空间转换到遗传算法的搜索空间的转换方法。 解码（译码）：遗传算法解空间向问题空间的转换。 二进制编码的缺点是汉明悬崖（Hamming Cliff），就是在某些相邻整数的二进制代码之间有很大的汉明距离，使得遗传算法的交叉和突变都难以跨越。 格雷码（Gray Code）：在相邻整数之间汉明距离都为1。 （较好）有意义的积木块编码规则：所定编码应当易于生成与所求问题相关的短距和低阶的积木块；最小字符集编码规则，所定编码应采用最小字符集以使问题得到自然的表示或描述。 二进制编码比十进制编码搜索能力强，但不能保持群体稳定性。 动态参数编码（Dynamic Paremeter Coding）：为了得到很高的精度，让遗传算法从很粗糙的精度开始收敛，当遗传算法找到一个区域后，就将搜索现在在这个区域，重新编码，重新启动，重复这一过程，直到达到要求的精度为止。 编码方法：

1、二进制编码方法 缺点：存在着连续函数离散化时的映射误差。不能直接反映出所求问题的本身结构特征，不便于开发针对问题的专门知识的遗传运算算子，很难满足积木块编码原则 2、格雷码编码：连续的两个整数所对应的编码之间仅仅只有一个码位是不同的，其余码位都相同。 3、浮点数编码方法：个体的每个基因值用某一范围内的某个浮点数来表示，个体的编码长度等于其决策变量的位数。 4、各参数级联编码：对含有多个变量的个体进行编码的方法。通常将各个参数分别以某种编码方法进行编码，然后再将他们的编码按照一定顺序连接在一起就组成了表示全部参数的个体编码。 5、多参数交叉编码：将各个参数中起主要作用的码位集中在一起，这样它们就不易于被遗传算子破坏掉。评估编码的三个规范：完备性、健全性、非冗余性。 二、选择 遗传算法中的选择操作就是用来确定如何从父代群体中按某种方法选取那些个体遗传到下一代群体中的一种遗传运算，用来确定重组或交叉个体，以及被选个体将产生多少个子代个体。 常用的选择算子： 1、轮盘赌选择（Roulette Wheel Selection）：是一种回放式随机采样方法。每个个体进入下一代的概率等于它的适应度值与整个种群中个体适应度值和的比例。选择误差较大。

遗传算法搜索最优解

实验一：基于遗传算法的函数优化 1、实验目的 1) 掌握Matlab子函数的编写与调用。 2) 理解基本遗传算法的原理，并利用程序实现利用遗传算法优化非线性函数的解。 2、实验内容与实验要求 1) 掌握基本遗传算法方法原理。 2) 掌握matlab子函数的编写方法及调用方法。 3) 根据基本遗传算法方法原理，编写Matlab程序，优化非线性函数的解。 4) 设f(x) = -x^2 - 4x + 1，求max f(x), x [-2, 2],解的精度保留二位小数 3、遗传算法原理 遗传算法模拟自然选择和自然遗传过程中发生的繁殖、交叉和基因突变现象，在每次迭代中都保留一组候选解，并按某种指标从解群中选取较优的个体，利用遗传算子(选择、交叉和变异)对这些个体进行组合，产生新一代的候选解群，重复此过程，直到满足某种收敛指标为止。

4、主程序及子函数： 主函数: clear clc my_scale=80; %种群规模 gen_len=22; %基因长度 M=100; %迭代次数 pc=0.7; %交叉概率 pm=0.05; %变异概率 new_scale=produscale(my_scale,gen_len); %产生初始种群 fitfit=[]; fittimer=[]; best_f1=[]; best_x1=[]; for i=1:M my_f=cal_my_f(new_scale); %计算函数值 my_fit=cal_my_fit(my_f); %计算适应度值 next_scale=my_sellect(new_scale,my_fit); %采用赌轮盘法选择 cross_scale=my_cross(next_scale,pc); %按概率交叉 mut_scale=my_mutat(cross_scale,pm); %按概率变异 %寻找每一代中的最优适应度值所对应的个体 best_fit=my_fit(1); [sx,sy]=size(new_scale); for j=2:length(my_fit) if best_fit