决策支持系统(双语)实验报告(DSS)

《决策支持系统(双语)实验报告(DSS)》由会员上传分享，免费在线阅读，更多相关内容在工程资料-天天文库。

1、《决策支持系统》实验报告开课实验室：信息中心学院年级、专业、班姓名成绩课程名称决策支持系统（双语）实验项目名称TSP问题的遗传算法求解指导教师教师评语教师签名：年月曰—、实验目的1、掌握智能程序的构造方法；2、掌握遗传算法的设计过程；3、学握概率发生器的编写过程；4、讨论TSP问题屮不同评价函数的使用结果。二、实验原理遗传算法(geneticalgorithm,GA)是模拟生物进化的自然选择和遗传机制的一种搜索寻优算法。它利用适者生存的进化原则，通过演化逐步逼近问题的最优解。基本原理是通过随机方式将问题的每一个可能的解进行数字编码，编码后的解称作染色体(个体)，随机选取N个染色体

2、构成初始种群，通过适应度函数给每个个体一个数值评价，淘汰低适应度的个体，选择适应值高的染色体进行复制，通过遗传算子(选择、交叉、变异)，产生一群新的适应环境的染色体，形成新的种群。这样一代一代不断进化，最后收敛到适应环境较好的一些个体中，求得问题的最优解。6一％尸+(儿：一儿丿其中，®表示个体第i遗传算法的执行过程中，每一代有许多不同的染色体(个体)同时存在，这些染色体中哪个保留、哪个淘汰是根据它们对坏境的适应能力來决定的，适应性强的有更多的机会保留下来。适应性强弱是由适应值函数人兀)的值来判别的。每个个体代表一条可能的路径。个体n的适应值为Fitness；2,其小，n为种群数，

3、为沿个体标示的城市序列所经过的路径长度，Q"可通过以下公式计算11!来：Dni=i位的城市编号。表示所有个体的路径长度的总和。适应值为非负，且取值越大越好。遗传算法屮主要的遗传算子有如下几种：(1)选择(selection)算子：又称复制、繁殖算子。选择是从种群中选择生命力强的染色体产生种群的过程。依据每个染色体的适应值大小，适应值越大，被选中的概率就越大，其子孙在下一代产生的个数就越多。本实验采用的是比率法，比率法的原理是每个染色体产生后代的数li正比于它的适应值，并有一个约束条件，即每一代中染色体的总数应保持不变。(2)交叉(crossover)算子又称重组、配对算子。交叉采

4、用部分匹配交叉策略，首先根据交叉概率随机地从新复制的种群屮选出要交叉的两个不同个体；然后，随机地选収一个交叉段，交叉段中两个个体的对应部分通过匹配换位实现交叉操作。例如，对个体A和B：210210交叉后得到：AP=98I410J2EM74沁贰1(3)变异(mutation)算子即根据变异概率随机地从种群中选出要变异的个体，随机地在该个体上选出两个变异位置，然后将两个位置上的城市序号进行变换。选择和交叉算子基本上完成了遗传算法地大部分搜索功能，而变异则增加了遗传算法找到接近最优解的能力。如：A=98456713210下划线部分为要变异的两个位置，变异为：A'=97456813210

5、三、使用仪器、材料计算机，VB系统四、实验步骤(1)编写适应值函数适应度值是根据适应度函数来计算的，如适应度函数代码如下：PublicFunctioncalfitness(ByRefcAsInteger)AsSingleDimtempAsSingleDimiAsIntegerTfForml.Combo1.Text=1Thencalfitness=1#/lengthchro(c)Elsetemp=0#Fori=1ToPool_Sizetemp=temp+lengthchro(i)Nextcalfitness=temp-lengthchro(c)EndIfEndFunction(2)

6、编写概率发生器即选择算子，选择的目的是为了从当前群体中选出优良的个体，使它们有机会作为父代产生后代个体，如代码：PublicSubreproduce()ReDimtemppchropool(1ToPool_Size,1ToCity_Num)AsIntegerReDimtemppro(0ToPoolSize)AsSingleDimrndnumAsSingleDimi,j,kAsIntegertemppro(0)=0#Fori=1ToPoolSizetemppro(i)=temppro(i-1)+calprobability(i)NextiFori=1ToPoolSizerndnum

7、=RndForj=1ToPool_SizeIfrndnum<=temppro(j)Andrndnum>temppro(j-1)ThenFork=1ToCity_Numtemppchropool(i,k)=chromosome(j,k)NextExitForEndIfNextNextFork=1ToPoolSizeFori=1ToCity_Numchromosome(k,i)=temppchropool(k,i)NextNextkEndSub(3)编写交叉算子实现过程是对选小用于繁