用遗传算法实现污水管网的优化设计

设计经验

用遗传算法实现污水管网的优化设计

伊学农

1,2

,　刘遂庆1,　周　琪

1

(1.同济大学环境科学与工程学院,上海200092;2.山东建筑工程学院环境工程

学院,山东济南250014)

摘　要:　提出用遗传算法优化大中型污水管网的设计,并与节点递归算法相结合,既满足了污水管网系统内部节点的水力衔接,也保证了管网系统的全局优化。遗传算法具有只需目标函数值而无需导数等信息的优点,并能从全局出发对管网水力参数进行优化,达到费用最低的目标。结合中型污水管网的优化设计,确定了遗传算法的运行参数。

关键词:　遗传算法;　污水管网;　优化设计

中图分类号:X703.1 文献标识码:C 文章编号:1000-4602(2005)05-0047-04

基金项目:国家高技术研究发展计划(863)项目(2002AA601023)

O pti m i za ti on of D esi gn for Sewer Network by Usi n g Geneti c A lgor ithm

YI Xue 2nong 1,2

,　L I U Sui 2qing 1

,　ZHOU Q i

1

(1.of Environm en tal Science and Engineering,Tongji U niversity,S hanghai 200092,China;2.S chool of Environm ental Engineering,Shandong Institute of A rchitectu re Engi 2

neering,J inan 250014,Ch ina )

Abstract:　U se of genetic algorith m t o op ti m ize the design for medium 2and large 2scale se wer net 2work in combinati on with the node recursive algorith m is p resented .The method can satisfy the require 2ment f or j oining hydraulically the nodes within the net w ork,and achieve the overall op ti m izati on of the net w ork .Genetic algorithm needs only the objective functi on values and needs not the derivatives,and can op ti m ize the hydraulic para meters of the whole net w ork,s o as t o attain the target with the l owest cost .The operating para meters of genetic algorith m are deter m ined based on the op ti m izati on design of medium 2scale se wer net w ork .

Key words:　genetic algorith m;　se wer net w ork;　op ti m izati on design 遗传算法用于污水管网的优化设计研究已有论述,但针对大中型污水管网系统进行应用还很少,尤其直接用于实际城市污水管网系统的优化设计更为少见,笔者以中型城市的污水管网为例,结合节点递归算法

[1]

和坐标轮换法,经实例验证遗传算法应用

于污水管网优化设计是可行的,满足工程要求,并与其他方法比较可获得更为低廉的投资方案。

1　

优化数学模型污水管网设计优化属于非线性目标函数的优化

问题,特别适合用遗传算法进行优化。污水管网系统设计优化的目的是在满足规范规定的基础上,使整个污水管网在其服务年限内基建投资和经营费用现值的总和为最小。采用如下形式的费用函数:

　m in F =∑m

i =1(k 1+k 2H +k 3H 2

+k 4D i H +k 5D i +

第21卷　第5期2005年5月 中国给水排水CH I N A WATER &WASTE WATER

Vol .21No .5

May 2005

k 6D 2

i +k 7D 3

i )l i +∑n

j =1

C pj +

K ∑n

j =1

O pj

(1)

　D i ∈ΩD ;H m in ≤H ≤H max 式中　F ———管网费用,元

D ———管径,m H ———管道埋设深度,m l i ———管网中管段长度,m K ———经营费折算成现值的系数ΩD ———实际可得管径系列C pj ———各泵站单价,元/座O pj ———各泵站经营费,元/(座?a )m 、n ———分别为管段数和泵站数H m in 、H max ———最小和最大埋深k 1、k 2、…、k 7———地方性系数和指数

2　

优化算法设计遗传算法要求必须对所求参数进行编码处理和

对目标函数进行适应度函数转换处理,并根据转换后的适应度函数的大小模仿生物进化过程,通过对参数编码的选择、交叉、变异等操作,逐步达到目标函数的最小值。2.1　可行管径集与编码

污水管网设计的遗传优化算法是在可行管径集的基础上进行的,根据管网中各设计管段的设计流量,用节点递归方法对管网进行水力计算,获得管网的初始管径,然后以此管径为准,向前后分别找出两个管径,确定各相应管段的可行管径取值范围,在遗传算法计算过程中,管径的初始化、选择、杂交和变异等操作,管径的取值均在此可行集范围内,这样就保证了遗传算法的运行速度和绝对收敛。

遗传算法中参数的编码采用可行管径集的十进制整数编码,长度与管段数相同,这样不仅提高了计

算速度,而且存在最优群体规模[2]

,为在大中型管网优化设计中使用遗传算法奠定了基础。2.2　适应度函数

遗传算法的遗传操作不是直接采用目标函数值,而是通过适应度来实现。上述管网优化的目标函数数学公式中包含了若干显式和隐式因素,在用遗传算法进行优化时,需要将目标函数值F 转换为适应度函数值f ,并且使目标函数值最小作为优化的目标,研究采用下式的转换方式,这样就保证了适应度值f 越大越好和遗传操作的正确性。在设计中考虑充满度惩罚Penalty,对不符合充满度条件或充满度较小的设计管段进行惩罚。

　f =

Penalty

F

(2)

2.3　算法及实现

遗传算法对污水管网优化的实质是随机搜索技术,根据一定规则(如选择、交叉、变异等)对管径进行操作,然后按照确定的各设计管段的管径,调用水力计算模块进行水力计算,并通过适应度函数值对目标函数(即工程造价)进行操作,最终搜索出最佳管径组合,使造价最低。污水管网系统遗传算法优化设计计算步骤如下:

①　计算各设计管段的设计流量,并据此进行水力计算,确定各设计管段的可行管径集;

②　随机产生遗传操作中的初始代群体,采用十进制整数对管径系列进行编码,初始群体的位数与管段数相同;

③　解码求出各设计管段设计管径的浮点数数值,并调用节点递归水力计算模块进行水力计算,计算出各设计管段的水力参数,同时求出整个管网的工程造价,由于遗传算法中有Max 个个体,因此通过计算可以得到Max 个可行设计方案;

④　评价适应度函数值,将管网造价之目标函数值转化为遗传算法操作中的适应度函数值;

⑤　采用比例选择法进行选择,并通过单点交叉和变异等操作产生下一代群体;

⑥　如果达到停止条件,输出优化结果后停止,否则,转③继续。

根据上述算法,用Del phi6.0编写了污水管网遗传算法优化计算程序。程序中用到的管网数据采用数据文件的形式输入。管网的流量和水力计算遵循国家有关规范的规定,同时设计方便、灵活。为了验证算法在污水管网优化设计上的可行性,选择了山东省一个中型城市的部分污水管网作为实例,该部分污水管网由197个管段组成,管道总长度为75.5k m,管网所在城区有较大的地面坡度变化,变化范围为-10%～30%,但从计算结果看是令人满意的。

3　

管网遗传优化运行参数分析与确定遗传算法运行参数的大小决定着遗传算法的运行性能。需要确定的运行参数主要有群体规模M 、交叉概率P c 、变异概率P m 、终止代数T 等。

以上述污水管网作为研究对象,以管网的造价为目标,分别对群体规模、交叉概率、变异概率、终止代数等运行参数进行了研究和确定。根据遗传算法的理论和以往的计算结果,首先确定终止代数为T =2000,然后在此基础上对其余三个参数进行计算

第5期 中国给水排水 第21卷

测试,各参数测试取值范围如下:群体大小M =20、40、70、100;交叉概率P c =0.4、0.5、0.6、0.7、0.8;变异概率P m =0.002、0.004、0.006、0.008、0.01、0.02、0.04、0.06、0.08。为此,依据上述假设的取值范围,作了大量的运行计算,图1～3为其中一部分结果,并且包括最好目标函数值为1816.8457万元的结果

。

图1　变异概率与管网造价的关系

Fig .1　Relati

on of net w ork cost t o p r obability of mutati on

图2　群体规模和变异概率与管网造价的关系

Fig .2　Relati on of

net w ork cost t o p r obability of mutati on

and populati on size

图3　交叉概率与群体规模对管网造价的影响曲线

Fig .3　Curve of net w ork cost t o cr oss over rate

and populati on size

①　终止代数T 是表示遗传算法运行结束条件的一个遗传参数,当运行到该代数时,遗传算法结束运行,并将当前群体中最佳个体作为所求问题的最优解输出。从图1还可以看出,当遗传代数>1600代时优化的结果已经基本达到满意解,因此在设计应用中可确定遗传代数为1600～2000。

②　变异概率P m 决定了遗传个体的多样性。若变异概率取值较大,虽然能够产生出较多的新个体,但也有可能破坏掉很多较好的模式,使得遗传算法的性能近似于随机搜索算法的性能;若变异概率取值太小,则可能导致变异操作产生新个体的能力与抑制早熟现象的能力较差。由图1、2可以看出,在群体大小M =40、交叉概率P c =0.7、终止代数T =2000代的情况下,当P m ≥0.02时目标函数的值明显增大,并随着变异概率的增大则其结果越来越大,这与其他运行计算结果是吻合的。由此可以得出较好变异概率范围为0.002～0.01。

③　群体规模M 表示群体中所含遗传个体的数量,影响到遗传算法的最终性能和效率。由图2可知,当M =20时,该曲线随着变异概率的增大而出现上升的趋势,属于不稳定的趋势,因此当P m =0.002～0.1时,结合图3和其他交叉概率下的计算结果与关系曲线,确定M =40～70。

④　交叉概率P c 是遗传算法中产生新个体的主要方法,所以交叉概率一般应取较大值,但是若取值过大,会破坏群体中的优良模式,对进化运算反而产生不利影响;若取值过小则会影响产生新个体的速度。从图3可以看出,在P c =0.4～0.8和P m =0.002～0.01的范围内,当M =100时其造价曲线随

着交叉概率的增大而增大,呈上升趋势,再次说明群

体规模不宜大于100;当M 为40和70时,交叉概率与造价的关系曲线为上下波动,并分别在不同的交叉概率值达到最低值,因此在此范围内,可以确定P c =0.4～0.7。

4　结论

根据所设计的算法和程序,通过对中型城市的污水管网系统的遗传算法优化计算分析,认为结合节点递归算法将遗传算法用于城市污水管网的优化设计是可行的,可获得较为满意的结果,并可得出以

下规律:①不管其他遗传参数设置如何,较高的变异

概率都会使管网优化的性能降低,一般不宜高于0.01;②在小规模群体时(如M =40)高交叉概率与第5期 伊学农,等:用遗传算法实现污水管网的优化设计 第21卷

低变异概率相结合可以得到较好的效果;③对于中等规模的群体(如M=70),最优交叉概率出现减小的现象,因此在实际应用中可采用M=40～70、T= 1600～2000、P c=0.4～0.7、P m=0.002～0.01,并针对不同的群体规模,取不同的交叉概率和变异概率,以获得较优的管网优化结果。经与传统设计方法比较,该方法可以节省8%～25%的工程投资,具有明显的优化效果。参考文献:

[1]　伊学农,刘遂庆.污水管网优化的节点递归算法[J].

中国给水排水,2002,18(10):58-60.

[2]　孙艳丰,王众托.自然编码遗传算法的最优群体规模

[J].信息与控制,1996,25(5):317-320.

E-ma il:yijack@hot m https://www.wendangku.net/doc/dd15205788.html,　jackyi@https://www.wendangku.net/doc/dd15205788.html,

收稿日期:2004-10-26

?技术交流?

嘉兴城市雨水利用途径探讨

城市雨水利用方法主要有完全渗透性排水、部分渗透和部分收集排放、部分收集利用和部分渗透等。北方缺水干旱地区雨水资源利用的出发点是为了解决旱季用水问题,所以它以收集利用为主,渗透、排放为辅。而嘉兴市雨水利用的方法应不仅着眼于开发水资源的新途径上,更多的还应从缓解城区雨水洪涝灾害和减少地面沉降等方面来考虑,所以可采取以渗透为主、排放和利用为辅的方法。结合当前嘉兴城市建设进程及嘉兴城市的气候、水文、地质等情况,雨水渗透设施可采用渗透地面、绿地、渗透管和渗透池等。

①　渗透地面

渗透地面可采用多孔沥青及混凝土地面或草皮砖,一般用于停车场、人流量较少的道路及人行道,特别适用于居民小区。

②　绿地

当前嘉兴城市建设正以“生态嘉兴”为目标,大力开展绿化造林工作,2003年市区新增绿地面积约524.6 h m2,人均公共绿地面积达12.3m2。如城区内原先的公园、苗圃、草坪等现有绿地都能按入渗场地来接纳居民区和道路上的雨水径流,则雨水入渗量就可加大,但早先的规划设计未考虑雨水渗透利用,现在要改造则工作量太大,这个设想不可能实现。但在规划新开发区或旧城改造区时,可将未建绿地设计成为缓坡下凹式绿地,具体做法是:设计和建造时合理调整路面高程、绿地高程、雨水口坎高程的关系,使路面高程高于绿地高程,雨水口设在绿地内,而且雨水口坎高程高于绿地高程而低于路面高程,这样就可形成下凹式绿地,降雨后的雨水径流可流入绿地,经绿地蓄渗后多余的雨水径流再从雨水口流走。下凹式绿地的设计最使人担心的是植被被淹问题,但北京市科学研究所和园林所曾联合开展高、平、低于路面不同形式草坪的蓄雨入渗试验和常用观赏草种的耐淹试验表明:城区土质入渗能力一般较好,遇雨强>150mm的暴雨时基本上不积水或积水时间很短,而且一般植物耐淹时间为1～3d,所以可以接纳一些路面雨水,同时提倡多种植一些允许短期淹没植物,如耐淹的早熟禾、野牛草等草种。由此可知,合理降低绿地高程、加大坎高、选择较耐淹的草种,就可以使绿地尽可能多地滞蓄汛期雨水。

③　渗透地、渗透管

由于嘉兴雨量较大,一般还需考虑收集、排放设备,渗透池、渗透管既可作渗透设备,又可兼作收集、排放设备,根据具体工程条件也可将各种渗透装置进行组合,如在一个小区内可将渗透地面、绿地、渗透池和渗透管等组合成一个渗透系统。超出其渗透能力的雨水通过渗透管、渗透池收集利用,用于浇洒道路、绿化或作为小区景观用水。在汛期雨量更大时,则利用嘉兴众多的河道和原有的管道进行直接排放。

(嘉兴学院机电与建筑工程分院　戚玉丽　吕秀杰　嘉兴市规划管理处　倪晓荣)

第5期 中国给水排水 第21卷

遗传算法的c语言程序

一需求分析 1．本程序演示的是用简单遗传算法随机一个种群，然后根据所给的交叉率，变异率，世代数计算最大适应度所在的代数 2．演示程序以用户和计算机的对话方式执行，即在计算机终端上显示“提示信息”之后，由用户在键盘上输入演示程序中规定的命令；相应的输入数据和运算结果显示在其后。3．测试数据 输入初始变量后用y=100*(x1*x1-x2)*(x1*x2-x2)+(1-x1)*(1-x1)其中-2.048<=x1,x2<=2.048作适应度函数求最大适应度即为函数的最大值 二概要设计 1．程序流程图 2．类型定义 int popsize; //种群大小 int maxgeneration; //最大世代数 double pc; //交叉率 double pm; //变异率 struct individual

{ char chrom[chromlength+1]; double value; double fitness; //适应度 }; int generation; //世代数 int best_index; int worst_index; struct individual bestindividual; //最佳个体 struct individual worstindividual; //最差个体 struct individual currentbest; struct individual population[POPSIZE]; 3．函数声明 void generateinitialpopulation(); void generatenextpopulation(); void evaluatepopulation(); long decodechromosome(char *,int,int); void calculateobjectvalue(); void calculatefitnessvalue(); void findbestandworstindividual(); void performevolution(); void selectoperator(); void crossoveroperator(); void mutationoperator(); void input(); void outputtextreport(); 4．程序的各函数的简单算法说明如下： （1）．void generateinitialpopulation ()和void input ()初始化种群和遗传算法参数。 input() 函数输入种群大小，染色体长度，最大世代数，交叉率，变异率等参数。 （2）void calculateobjectvalue();计算适应度函数值。 根据给定的变量用适应度函数计算然后返回适度值。 （3）选择函数selectoperator() 在函数selectoperator()中首先用rand ()函数产生0～1间的选择算子，当适度累计值不为零时，比较各个体所占总的适应度百分比的累计和与选择算子，直到达到选择算子的值那个个体就被选出，即适应度为fi的个体以fi/∑fk的概率继续存在； 显然，个体适应度愈高，被选中的概率愈大。但是，适应度小的个体也有可能被选中，以便增加下一代群体的多样性。 （4）染色体交叉函数crossoveroperator() 这是遗传算法中的最重要的函数之一，它是对个体两个变量所合成的染色体进行交叉，而不是变量染色体的交叉，这要搞清楚。首先用rand ()函数产生随机概率，若小于交叉概率，则进行染色体交叉，同时交叉次数加1。这时又要用rand()函数随机产生一位交叉位，把染色

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)

遗传算法的C#实现及应用

，………………………………………………“………“ 实用第一／智慧密集。．．．．．。。。。。。。。，。．。．。。。。．。。。。。．。。。。。。。。。。。．。。。．．。。。。。。。。。。。。．．。。。。。，。√， ≯｜｜ｊ—Ａ疆蕊嗡嗡镧鹣潲瞒虢滁酗确斓蛹鹳曩ｊｉｉ１１｜｜｜｜璐彀豫澡毽畿瓷罐甍谶羲｜遵麓囊鬻谶赢薏篱瀑每｜｜？ｉ。｜？≯，鬣壤鋈国潆巢镶倦奄誊缝绥舔蔑善嚣≤譬Ｉ ｊｌ。ｊ０ｊ。ｊ瓷蚤尊嶙≮啪獬ｉ毽赫馘每蛹戳ｊ蠢。‰酶鸯峨誓曩薯｜≥ｉｌ ｊｉ ｊ ｊ。一ｉＩ｜薯０Ｉ奄§畦姻镦添。每孳舔溺警ｊｌｊ；｜０一『ｊ＿ｌｔ－？甍遴！ｌ邀纛纛瓣｜鬣瓣◇｜ｌｉｉ｜Ｉｌ｜｜Ｉ弩酶冁醚嗡婚穆穗姆ｔ◇９鬟湖瀵哮咚◇ｉ谚峰岭譬ｉｊ¨¨｜：鬻攀谶一≥。｜？｜“ｊｉ？ｌ疆黼誊眷懿ｔ诵蕊囊酿褥酶姆螭ｔ豳ｊ酶Ｉ≮媾龋穗电鹱穰誊ｊ｜。。ｊ｜。。麓国隧嫱毒撼媳誊『：ｉ－ｊｌ｜｜ｉ溪誉攀ｌｊ豢篱鬣蔷淄鬻｜ｌ｜一ｉｊ鼍≥ｌ篱鬻ｉｌ豢 ≤奠ｄｏ≯Ｚ处理其余的基因ｌ城市点卜 ？ｊ。一鼍＿ｉ『瓢ｊ树蛹嗽Ｎ哟ｈｂｏｒ＝｛Ｇ＿ｅ制ｅａ淑Ｎｅｊｇｈｂｏｒ誊ｌ｜ｌｌ｝ｉｇ髓瞄蝴ａ｝弼鼯礁ｕ确瞅ｅ脚Ｓ攀ｊ。 一毫?。／｜ｌ，，熊到与翦学纂蜀溉避的一个基因，并加入新染色体曩ｏ、。潮黼溉憾ｒｆ＿｛ｌａ鳓ｍ鸯，Ａ酬Ｇｅｎｅ椭ｅｗＧＡＧｅｎｅ ｊ删删Ｎ磅ｉ鳓￡躜ｒ｜Ｉ；¨警自赋￡ｌＩ：＿ｌ§¨＇｜）： 、。－。：，薯￡酒ｆｔＰ舀黼黯一一：。ｉ ｊ－ｊ？ｉ。昭铀柏舔嚣ｉ蜩酚鳓Ｎ∞ｒｓ悄ｅｊｇｈｂｏＢ ＋寥 ＿＿ｌ蝴Ⅺ蠢ｌｍ白赠鳓ｆ￥缓警ｉＯ戳『；ｊ ｉ毒ｊ碜净磅囊ｉ÷ｉ；ｉ喹哆？簿簪两ｏｈｒ９哆ｊ舀锣ｍｅ｛ｎ。ｗｃｈｒ｜。而ｏｓｏｍｅ｝：ｊ雾雾鬻雾耩韵秘穆然取代原染色体ｉ． 准备好以上的方法后，还要注意四个参数的设定。交叉率一般为Ｏ．８左右，变异率一般为Ｏ．０５左右，群体大小、繁殖次数要根据城市数目有所变化。调试程序时，可以修改这些参数来观察优化过程的收敛快慢、最优解的跳变等。 三、程序调试 在Ｖｓ２００５中建立ｗｉｎｄｏｗｓ组件解决方案，添加现有项：基因类（ＧＡＧｅｎｅ）、染色体类（ＧＡＣｈｆｏｍｏｓｏｍｅ）、染色体比较类（ｃｈｒｏｍｏｓｏｍｅｃｏｍｐａｒｅｒ．ｃｓ）、遗传算法类（ＧＡ），调试生成（ｇａ．衄）组件。 建立ｇａＴｓＰ解决方案，添加现有项ｔｓｐＦＯＲＭ．ｃｓ窗体，添加引用ｇａ．ｄｌｌ。运行程序如下图所示。工具栏第一个按钮的作用是设置一个文本文件，以记录每一代群体的染色体组成及其适应度的值。红色曲线为每一群体中最优染色体的适应度的变化，从中可以看到优化过程的收敛情况。读者可以模仿本文的第二部分，利用ｇａ．ｄＵ解决其他问题。 旅行商问题运行图 参考文献 １．陈国良、王煦法、庄镇．遗传算法及其应用．人民邮电出版社 ２．李敏强．遗传算法的基本理论与应用．科学出版社 （收稿日期：２００７年１月２６日）

基本遗传算法的C源程序。doc【精品毕业设计】(完整版)

/********************************************************** ********/ /* 基于基本遗传算法的函数最优化SGA.C */ /* A Function Optimizer using Simple Genetic Algorithm */ /* developed from the Pascal SGA code presented by David E.Goldberg */ //********************************************************** ********/ #include #include #include #include "graph.c" /* 全局变量*/ struct individual /* 个体*/ { unsigned *chrom; /* 染色体*/ double fitness; /* 个体适应度*/ double varible; /* 个体对应的变量值*/ int xsite; /* 交叉位置*/ int parent[2]; /* 父个体*/ int *utility; /* 特定数据指针变量*/ };

struct bestever /* 最佳个体*/ { unsigned *chrom; /* 最佳个体染色体*/ double fitness; /* 最佳个体适应度*/ double varible; /* 最佳个体对应的变量值*/ int generation; /* 最佳个体生成代*/ }; struct individual *oldpop; /* 当前代种群*/ struct individual *newpop; /* 新一代种群*/ struct bestever bestfit; /* 最佳个体*/ double sumfitness; /* 种群中个体适应度累计*/ double max; /* 种群中个体最大适应度*/ double avg; /* 种群中个体平均适应度*/ double min; /* 种群中个体最小适应度*/ float pcross; /* 交叉概率*/ float pmutation; /* 变异概率*/ int popsize; /* 种群大小*/ int lchrom; /* 染色体长度*/ int chromsize; /* 存储一染色体所需字节数*/ int gen; /* 当前世代数*/ int maxgen; /* 最大世代数*/ int run; /* 当前运行次数*/

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

实验十遗传算法与优化问题 一、问题背景与实验目的 遗传算法（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 变异染色体水平上基因变化编码的某些元素被改变

遗传算法求解VRP问题的技术报告

遗传算法求解VRP 问题的技术报告 摘要：本文通过遗传算法解决基本的无时限车辆调度问题。采用车辆和客户对应排列编码的遗传算法，通过种群初始化，选择，交叉，变异等操作最终得到车辆配送的最短路径。通过MA TLAB 仿真结果可知，通过遗传算法配送的路径为61.5000km,比随机配送路径67km 缩短了5.5km 。此结果表明遗传算法可以有效的求解VRP 问题。 一、 问题描述 1.问题描述 车辆调度问题（Vehicle Scheduling/Routing Problem,VSP/VRP ）的一般定义为[1]：对一系列送货点和/或收货点，组织适当的行车路线，使车辆有序地通过它们，在满足一定的约束条件（如货物需求量、发送量，送发货时间、车辆容量限制、行驶里程限制、时间限制等）下，达到一定的目标（如路程最短、费用极小、时间尽量少、使用车辆数尽量少等）。问题描述如下[2]：有一个或几个配送中心),...,1(n i D i =，每个配送中心有K 种不同类型的车型，每种车型有n 辆车。有一批配送业务),...,1(n i R i =，已知每个配送业务需求量),...,1(n i q i =和位置或要求在一定的时间范围内完成，求在满足不超过配送车辆载重等的约束条件下，安排配送车辆在合适的时间、最优路线使用成本最小。 2.数学模型 设配送中心有K 台车，每台车的载重量为),...,2,1(K k Q k =，其一次配送的最大行驶距离为k D ，需要向L 个客户送货，每个客户的货物需求量为),...,2,1(L i q i =，客户i 到j 的运距为ij d ，配送中心到各个客户的距离为),...,2,1,(0L j i d j =，再设k n 为第K 台车配送的客户数（k n =0表示未使用第K 台车），用集合k R 表示第k 条路径，其中ki r 表示客户ki r 在路径 k 中的顺序为 （不包括配送中心），令 0k r 表示配送中心，若以配送总里程最短为目标函数，则可建立如下数学模型： ∑∑==?+=-K k k rk r n i r r n sign d d Z k kn k ki i k 1 1 )] ([min )1( (1) k n i ki Q qr k ≤∑=1 (2) k k rk r n i r r D n sign d d k kn k ki i k ≤?+∑=-)(0 1 )1( (3) L n k ≤≤0 (4)

遗传算法——耐心看完-你就掌握了遗传算法【精品毕业设计】(完整版)

遗传算法入门到掌握 读完这个讲义，你将基本掌握遗传算法，要有耐心看完。 想了很久，应该用一个怎么样的例子带领大家走进遗传算法的神奇世界呢？遗传算法的有趣应用很多，诸如寻路问题，8数码问题，囚犯困境，动作控制，找圆心问题（这是一个国外网友的建议：在一个不规则的多边形中，寻找一个包含在该多边形内的最大圆圈的圆心。），TSP问题（在以后的章节里面将做详细介绍。），生产调度问题，人工生命模拟等。直到最后看到一个非常有趣的比喻，觉得由此引出的袋鼠跳问题（暂且这么叫它吧），既有趣直观又直达遗传算法的本质，确实非常适合作为初学者入门的例子。这一章将告诉读者，我们怎么让袋鼠跳到珠穆朗玛峰上去(如果它没有过早被冻坏的话)。 问题的提出与解决方案 让我们先来考虑考虑下面这个问题的解决办法。 已知一元函数： 图2-1 现在要求在既定的区间内找出函数的最大值。函数图像如图2-1所示。 极大值、最大值、局部最优解、全局最优解

在解决上面提出的问题之前我们有必要先澄清几个以后将常常会碰到的概念：极大值、最大值、局部最优解、全局最优解。学过高中数学的人都知道极大值在一个小邻域里面左边的函数值递增，右边的函数值递减，在图2.1里面的表现就是一个“山峰”。当然，在图上有很多个“山峰”，所以这个函数有很多个极大值。而对于一个函数来说，最大值就是在所有极大值当中，最大的那个。所以极大值具有局部性，而最大值则具有全局性。 因为遗传算法中每一条染色体，对应着遗传算法的一个解决方案，一般我们用适应性函数（fitness function）来衡量这个解决方案的优劣。所以从一个基因组到其解的适应度形成一个映射。所以也可以把遗传算法的过程看作是一个在多元函数里面求最优解的过程。在这个多维曲面里面也有数不清的“山峰”，而这些最优解所对应的就是局部最优解。而其中也会有一个“山峰”的海拔最高的，那么这个就是全局最优解。而遗传算法的任务就是尽量爬到最高峰，而不是陷落在一些小山峰。（另外，值得注意的是遗传算法不一定要找“最高的山峰”，如果问题的适应度评价越小越好的话，那么全局最优解就是函数的最小值，对应的，遗传算法所要找的就是“最深的谷底”）如果至今你还不太理解的话，那么你先往下看。本章的示例程序将会非常形象的表现出这个情景。 “袋鼠跳”问题 既然我们把函数曲线理解成一个一个山峰和山谷组成的山脉。那么我们可以设想所得到的每一个解就是一只袋鼠，我们希望它们不断的向着更高处跳去，直到跳到最高的山峰（尽管袋鼠本身不见得愿意那么做）。所以求最大值的过程就转化成一个“袋鼠跳”的过程。下面介绍介绍“袋鼠跳”的几种方式。 爬山法、模拟退火和遗传算法 解决寻找最大值问题的几种常见的算法： 1. 爬山法（最速上升爬山法）： 从搜索空间中随机产生邻近的点，从中选择对应解最优的个体，替换原来的个体，不断重复上述过程。因为只对“邻近”的点作比较，所以目光比较“短浅”，常常只能收敛到离开初始位置比较近的局部最优解上面。对于存在很多局部最优点的问题，通过一个简单的迭代找出全局最优解的机会非常渺茫。（在爬山法中，袋鼠最有希望到达最靠近它出发点的山顶，但不能保证该山顶是珠穆朗玛峰，或者是一个非常高的山峰。因为一路上它只顾上坡，没有下坡。） 2. 模拟退火： 这个方法来自金属热加工过程的启发。在金属热加工过程中，当金属的温度超过它的熔点（Melting Point）时，原子就会激烈地随机运动。与所有的其它的物理系统相类似，原子的这种运动趋向于寻找其能量的极小状态。在这个能量的变

MATLAB课程遗传算法实验报告及源代码

硕士生考查课程考试试卷 考试科目： 考生姓名：考生学号： 学院：专业： 考生成绩： 任课老师(签名) 考试日期：年月日午时至时

《MATLAB 教程》试题： A 、利用MATLA B 设计遗传算法程序，寻找下图11个端点最短路径，其中没有连接端点表示没有路径。要求设计遗传算法对该问题求解。 a e h k B 、设计遗传算法求解f (x)极小值，具体表达式如下： 321231(,,)5.12 5.12,1,2,3i i i f x x x x x i =?=???-≤≤=? ∑ 要求必须使用m 函数方式设计程序。 C 、利用MATLAB 编程实现：三名商人各带一个随从乘船渡河，一只小船只能容纳二人，由他们自己划行，随从们密约，在河的任一岸，一旦随从的人数比商人多，就杀人越货，但是如何乘船渡河的大权掌握在商人手中，商人们怎样才能安全渡河？ D 、结合自己的研究方向选择合适的问题，利用MATLAB 进行实验。 以上四题任选一题进行实验，并写出实验报告。

选择题目： B 、设计遗传算法求解f (x)极小值，具体表达式如下： 321231(,,)5.12 5.12,1,2,3i i i f x x x x x i =?=???-≤≤=? ∑ 要求必须使用m 函数方式设计程序。 一、问题分析（10分） 这是一个简单的三元函数求最小值的函数优化问题，可以利用遗传算法来指导性搜索最小值。实验要求必须以matlab 为工具，利用遗传算法对问题进行求解。 在本实验中，要求我们用M 函数自行设计遗传算法，通过遗传算法基本原理，选择、交叉、变异等操作进行指导性邻域搜索，得到最优解。 二、实验原理与数学模型（20分） （1）试验原理： 用遗传算法求解函数优化问题，遗传算法是模拟生物在自然环境下的遗传和进化过程而形成的一种自适应全局优化概率搜索方法。其采纳了自然进化模型，从代表问题可能潜在解集的一个种群开始，种群由经过基因编码的一定数目的个体组成。每个个体实际上是染色体带有特征的实体；初始种群产生后，按照适者生存和优胜劣汰的原理，逐代演化产生出越来越好的解：在每一代，概据问题域中个体的适应度大小挑选个体；并借助遗传算子进行组合交叉和主客观变异，产生出代表新的解集的种群。这一过程循环执行，直到满足优化准则为止。最后，末代个体经解码，生成近似最优解。基于种群进化机制的遗传算法如同自然界进化一样，后生代种群比前生代更加适应于环境，通过逐代进化，逼近最优解。 遗传算法是一种现代智能算法，实际上它的功能十分强大，能够用于求解一些难以用常规数学手段进行求解的问题，尤其适用于求解多目标、多约束，且目标函数形式非常复杂的优化问题。但是遗传算法也有一些缺点，最为关键的一点，即没有任何理论能够证明遗传算法一定能够找到最优解，算法主要是根据概率论的思想来寻找最优解。因此，遗传算法所得到的解只是一个近似解，而不一定是最优解。 （2）数学模型 对于求解该问题遗传算法的构造过程： （1）确定决策变量和约束条件；

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

一个简单实用的遗传算法c程序完整版

一个简单实用的遗传算 法c程序 HEN system office room 【HEN16H-HENS2AHENS8Q8-HENH1688】

一个简单实用的遗传算法c程序（转载） 2009-07-28 23:09:03 阅读418 评论0 字号：大中小 这是一个非常简单的遗传算法源代码，是由Denis Cormier (North Carolina State University)开发的，Sita (University of North Carolina at Charlotte)修正。代码保证尽可能少，实际上也不必查错。对一特定的应用修正此代码，用户只需改变常数的定义并且定义“评价函数”即可。注意代码的设计是求最大值，其中的目标函数只能取正值；且函数值和个体的适应值之间没有区别。该系统使用比率选择、精华模型、单点杂交和均匀变异。如果用Gaussian变异替换均匀变异，可能得到更好的效果。代码没有任何图形，甚至也没有屏幕输出，主要是保证在平台之间的高可移植性。读者可以从,目录 coe/evol中的文件中获得。要求输入的文件应该命名为‘’；系统产生的输出文件为‘’。输入的文件由几行组成：数目对应于变量数。且每一行提供次序——对应于变量的上下界。如第一行为第一个变量提供上下界，第二行为第二个变量提供上下界，等等。 /**************************************************************************/ /* This is a simple genetic algorithm implementation where the */ /* evaluation function takes positive values only and the */ /* fitness of an individual is the same as the value of the */ /* objective function */ /**************************************************************************/ #include <> #include <> #include <> /* Change any of these parameters to match your needs */ #define POPSIZE 50 /* population size */

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

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

6-第二篇 第2章 遗传算法的基本实现技术

2.4 遗传算子 遗传算法中包括三个遗传操作（或称遗传算子）：即选择算子、交叉算子和变异算子，它们构成了遗传算法具备强大搜索能力的核心。利用遗传算子产生新一代群体实现群体进化，下面分别介绍这三种遗传算子。 2.4.1选择算子 在生物的遗传和自然进化过程中，对生存环境适应程度较高的物种将有更多机会遗传到下一代；而对生存环境适应程度较低的物种遗传到下一代的机会就相对较少。模仿这个过程，遗传算法使用选择算子(或称复制算子，Reproduction Operator)来对群体中的个体进行优胜劣汰操作：适应度较高的个体被遗传到下一代群体中的概率较大；适应度较低的个体被遗传到下一代群体中的概率较小。遗传算法中的选择操作就是用来确定如何从父代群体中按某种方法选取哪些个体遗传到下一代群体中的一种遗传运算。通过选择操作可以避免基因缺失，提高全局收敛性和计算效率。 1． 比例选择法(proportional model) 适应度比例选择方法是基本的选择方法，也叫赌轮选择(roulette wheel selection)或蒙特卡罗选择，是一种回放式随机采样方法。该方法的基本思想是：各个个体的被选中的概率与其适应度大小成正比。 设群体规模为M ，个体i 的适应度为i F ，则个体i 被选中的概率is P 为： 1 i is M i i F P F == ∑ （1,2, ,i M =） （2-14） 显然，概率is P 反映了个体i 的适应度在整个群体的个体适应度总和中所占的比例，个体适应度越大，其被选择的概率就越高，反之亦然。 2． 最佳个体保存方法(elitist model) 最佳个体保存法的思想是群体中适应度最高的个体不参与交叉运算和变异运算，而是用它来替换掉本代群体中经过交叉、变异等遗传操作后所产生的适应度最低的个体 采用这样选择方法的优点是，进化过程中某一代的最优解可不被交叉或变异操作破坏。但是，这也隐含了一种危机，即局部最优个体的遗传基因会急速增加而使进化有可能陷于局部解，也就是说，该方法的全局搜索能力差。它适合于单峰性质的优化问题的空间搜索，而不适于多峰性质的空间搜索。所以，此方法一般都与其他选择方法结合使用。 3． 期望值方法(expected value model) 在赌轮选择方法中，当个体数不太多时，产生的随机数有可能会出现不正确地反映个体适应度的选择。这时存在统计误差，也就是就，适应度高的个体有可能被淘汰，适应度低的个体也有可能被选择。为了克服这种缺点，期望值方法根据每个个体在下一代群体中的生存期望值来进行随机选择运算，是一种无回放的随机采样方法，其步骤如下： （1）计算群体中每个个体在下一代生存的期望数目i N 1 i i i M avg i i F M F N F F =?= =∑ （1,2,,i M =） （2-15）

matlab遗传算法学习和全局化算法【精品毕业设计】(完整版)

1 遗传算法步骤 1 根据具体问题选择编码方式，随机产生初始种群，个体数目一定，每个个体表现为染色 体的基因编码 2 选择合适的适应度函数，计算并评价群体中各个体的适应。 3 选择(selection)。根据各个个体的适应度，按照一定的规则或方法，从当前群体中选择出 一些优良的个体遗传到下一代群体 4 交叉(crossover)。将选择过后的群体内的各个个体随机搭配成对，对每一对个体，以一定 概率(交叉概率)交换它们中的部分基因。 5 变异(mutation)。对交叉过后的群体中的每一个个体，以某个概率(称为变异概率)改n 变某一个或某一些基因位上的基因值为其他的等位基因 6 终止条件判断。若满足终止条件，则以进化过程中得到的具有最大适应度的个体作为最 优解输出，终止运算。否则，迭代执行Step2 至Step5。 适应度是评价群体中染色体个体好坏的标准，是算法进化的驱动力，是自然选择的唯一依据，改变种群结构的操作皆通过适应度函数来控制。在遗传算法中，以个体适应度的大小 来确定该个体被遗传到下一代群体中的概率。个体的适应度越大，被遗传到下一代的概率 就越大，相反，被遗传到下一代的概率就越小。 1 [a,b,c]=gaopt(bound,fun)其中，bound=[xm，xM]为求解区间上届和下届构成的矩阵。Fun 为用户编写的函数。a为搜索的结果向量，由搜索的出的最优x向量与目标函数构成，b为最终搜索种群，c为中间搜索过程变参数，其第一列为代数，后边列分别为该代最好的的个 体与目标函数的值，可以认为寻优的中间结果。 2 ga函数。[X,F, FLAG,OUTPUT] = GA(fun, n,opts).n为自变量个数，opts为遗传算法控制选项，用gaoptimset（）函数设置各种选项，InitialPopulation可以设置初始种群，用PopulationSize 可以设置种群规模，SelectionFcn可以定义选择函数， 3 gatool 函数用于打开，GATOOL is now included in OPTIMTOOL。 2.2 通过GUI 使用遗传算法 在Matlab 工作窗口键入下列命令>>gatool，或通过Start 打开其下子菜单Genetic Algorithm Tool，如图1。只要在相应的窗格选择相应的选项便可进行遗传算法的计算。其中fitnessfun 窗格为适应度函数，填写形式为@fitnessfun，Number of variable 窗格为变量个数。其它窗格参数根据情况填入。填好各窗格内容，单击Start 按钮，便可运行遗传算法 例子1 应用实例 已知某一生物的总量y（单位：万个）与时间t（月）之间的关系为y=k0(1-exp(-k1*t))， 统计十个月得到数据见表1，试求关系式中的k0，k1。先编写目标函数，并以文件名myfung.m

4-第二篇 第2章 遗传算法的基本实现技术

第 2 章 遗传算法的基本实现技术
在第一章中，以实例简述的形式提供了遗传算法的一个基本框架。基于对自然界中生物遗传和进化机 理的模仿，许多学者针对不同的问题，设计了不同的编码方法和不同的遗传算子来模仿不同环境下生物的 遗传特性。这样，由不同的编码方法和不同的遗传算子就构成了各种特点的遗传算法，下面我们根据遗传 算法的基本构成要素来阐述其基本的实现技术。
2.1 编码方法
遗传算法的特点之一是不对求解问题的决策变量直接进行操作，而是通过对个体编码，并进行交叉与 变异的进化运算过程，不断搜索出适应度较高的新个体，最终寻求出问题的最优解或近似最优解。由于遗 传算法不能直接处理问题空间或解空间的参数，必须把它们转换成表达空间或搜索空间的染色体，这一转 换操作称为编码。
2.1.1 编码原则 应用遗传算法计算时，遇到的首要问题就是编码，可以说它是整个计算的一个关键步骤。编码方法除
决定了个体的染色体排列形式，还决定了个体从搜索空间的基因型变换到解空间的表现型时的解码方法。 编码方法也影响到交叉算子、变异算子等遗传算子的运算方法。由此可见，编码方法在很大程度上决定了 如何进行群体的遗传进化运算以及遗传进化运算的效率。一个好的编码方法，有可能使遗传运算和操作过 程简单地执行；一个差的编码方法，一方面影响运算精度和储存量，另一方面可能使交叉及变异等运算难 以实现。如果编码方法和交叉处理不当，在遗传算法中因交叉而生成的个体有可能成为无用解或无效解。
另外，编码和交叉的策略是互相依存的，恰当地设计编码和交叉的策略与方法，对充分发挥遗传算法 的效能是十分重要的，在设计编码策略时，常考虑以下三个问题：
1. 完备性：对问题空间的任何一个点有搜索空间的一个点与之对应。即问题空间的所有可能解都能 表示为所设计的基因编码形式。
2. 健全性：对于表达空间中的任何一个点都有问题空间中的一个点与之对应。即任何一个基因编码 都对应于一个可能解；
3. 非冗余性：问题空间和表达空间一一对应。 上述三点表明，编码策略必须保证从问题空间到表达空间有一对一的映射关系。 应该注意的是，对于很多问题，很难设计出同时满足上述 3 个性质的编码方案，不管怎样，完备性是 必须满足的性质，在有些情况下，虽然产生无效解并不完全都是有害的，在大部分情况下是影响运算效率 的。 上述三个编码评估规范虽然带有普遍意义，但缺乏具体的指导思想，特别是满足这些规范的编码不一 定能有效地提高遗传算法的搜索效率。 De Jong 提出了较为客观明确的编码评估准则，他称之为编码原则，又称之为编码规则： 1. 有意义基因块编码规则：应使用能易于产生与所求问题相关的低阶、短定义长度模式的编码方案。 在此原则中，模式是指具有某些基因相似性的个体集合，而具有低阶、短定义长度且适应度较高的模 式称为构造优良个体的基因块。该编码原则理解为应使用易于生成适应度较高的个体编码方案。 2. 最小字符集编码原则：所设计的编码方案应采用最小字符集以使问题得到自然的表示或描述。 在此原则中说明常常使用二进制编码方法的原因，因为它满足这条编码原则的要求。根据理论分析表 明，与其他编码字符集相比，二进制编码方案能包含最大的模式数，它可使得遗传算法在确定的规模群体 中能够处理最多的模式。 上述 De Jong 编码原则，仅仅是为编码设计提出了一定的准则，它并不适合于所有的问题，在处理实 际应用问题时，必须对编码方法、交叉运算方法、变异运算方法、解码方法等统筹考虑。以便对问题求解 简便，寻求遗传运算效率最高的编码方法。

遗传算法小生境技术简介

遗传算法小生境技术简介 生物学上，小生境是指特定环境下的一种组织结构。在自然界中，往往特征，形状相似的物种相聚在一起，并在同类中交配繁衍后代。在SGA 中，交配完全是随机的，在进化的后期，大量的个体集中于某一极值点上，在用遗传算法求解多峰值问题时，经常只能找到个别的几个最优值，甚至往往得到是局部最优解。利用小生境我们可以找到全部最优解。 小生境技术就是将每一代个体划分为若干类，每个类中选出若干适应度较大的个体作为一个类的优秀代表组成一个群，再在种群中，以及不同种群中之间，杂交，变异产生新一代个体群。同时采用预选择机制和排挤机制或分享机制完成任务。基于这种小生境的遗传算法（Niched Genetic Algorithms，NGA），可以更好的保持解的多样性，同时具有很高的全局寻优能力和收敛速度，特别适合于复杂多峰函数的优化问题。 模拟小生境技术主要建立在常规选择操作的改进之上。Cavichio 在1970年提出了基于预选择机制的选择策略，其基本做法是：当新产生的子代个体的适应度超过其父代个体的适应度时，所产生的子代才能代替其父代而遗传到下一代群体中去，否则父代个体仍保留在下一代群体中。由于子代个体和父代个体之间编码结构的相似性，所以替换掉的只是一些编码结构相似的个体，故它能够有效的维持群体的多样性，并造就小生境的进化环境。De Jong在1975年提出基于排挤机制的选择策略，其基本思想源于在一个有限的生存环境中，各种不同的生物为了能够延续生存，他们之间必须相互竞争各种有限的生存资源。因此，在算法中设置一个排挤因子CF（一般取CF=2或3），由群体中随机选取的1/CF 个个体组成排挤成员，然后依据新产生的的个体与排挤成员的相似性来排挤一些与预排挤成员相类似的个体，个体之间的相似性可用个体编码之间的海明距离来度量。随着排挤过程的进行，群体中的个体逐渐被分类，从而形成一个个小的生成环境，并维持群体的多样性。 Goldberg等在1987年提出了基于共享机制（Sharing）的小生境实现方法。这种实现方法的基本思想是：通过反映个体之间的相似程度的共享函数来调节群体中各个个体的适应度，从而在这以后的群体进化过程中，算法能够依据这个调整后的新适应度来进行选择运算，以维持群体的多样性，创造出小生境的进化环境。 共享函数（Sharing Function）是表示群体中两个个体之间密切关系程度的一个函数，可记为S（d ）其中表示个体i和j之间的关系。例如，个体基因型之间的海明距离就可以为一种共享函数。这里，个体之间的密切程度主要体现为个体基因型的相似性或个体表现型的相似性上。当个体之间比较相似时，其共享函数值就比较大；反之，当个体之间不太相似时，其共享函数值比较小。 共享度是某个个体在群体中共享程度的一中度量，它定义为该个体与群体内其它各个个体之间的共享函数值之和，用S 表示： S = （i=1，，M） 在计算出了群体中各个个体的共享度之后，依据下式来调整各个个体的适应度：F （X）=F （X）/S （i=1，，M） 由于每个个体的遗传概率是由其适应度大小来控制的，所以这种调整适应度的方法就能够限制群体中个别个体的大量增加，从而维护了群体的多样性，并造就了一种小生境的进化环境。