《韩琪遗传算法》PPT课件

《《韩琪遗传算法》PPT课件》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、遗传算法解决旅行商问题韩琪通信工程学院遗传算法解决旅行商问题问题引入：旅行商问题介绍遗传算法介绍练习：用遗传算法解决最大（小）值问题用遗传算法解决旅行商问题总结与展望旅行商问题什么是旅行商问题？旅行商问题（TravelingSalesmanProblem，TSP）是最基本的路线问题，该问题是在寻求单一旅行者由起点出发，通过所有给定的需求点之后，最后再回到原点的最小路径成本。迷茫的旅行商假设一名旅行商打算拜访一张城市列表中的所有城市，每座城市只去一次，最后回到出发地。要怎么走才能让路线最短呢？对于美国的48个州，有48！=1.241391559 ×1061种路

2、线，这是一个天文数字。任何一台超级计算机都不可能遍历这所有的路线。接下来让我们一起用遗传算法帮助他解决这个问题智能优化算法特点：1、不以找到理论上的精确最优解为目标，而是更看重计算速度和效率2、对目标函数和约束函数的要求十分宽松。3、算法的基本思想都是来自对某种自然规律的模仿，具有人工智能的特点。4、多数算法含有一个多个体的种群，寻优过程实际上就是种群的进化过程。5、这些算法的理论工作相对比较薄弱，一般来说都不能保证收敛到最优解。遗传算法的基本概念1.个体与种群：个体就是模拟生物个体而对问题中的对象（一般就是问题的解）的一种称呼，一个个体也就是搜索空间中的一

3、个点。种群(population)就是模拟生物种群而由若干个体组成的群体,它一般是整个搜索空间的一个很小的子集。2.适应度与适应度函数：适应度(fitness)就是借鉴生物个体对环境的适应程度,而对问题中的个体对象所设计的表征其优劣的一种测度。适值函数(fitnessfunction)就是问题中的全体个体与其适应度之间的一个对应关系。它一般是一个实值函数。该函数就是遗传算法中指导搜索的评价函数。3.染色体与基因染色体（chromosome）就是问题中个体的某种字符串形式的编码表示。字符串中的字符也就称为基因（gene）。例如：个体染色体9----1001（

4、2，5，6）----0101011104.遗传操作亦称遗传算子(geneticoperator)，就是关于染色体的运算。遗传算法中有三种遗传操作:（1）选择-复制(selection-reproduction)（2）交叉(crossover，亦称交换、交配或杂交)（3）变异(mutation，亦称突变)基本遗传算法流程图开始产生初始种群计算适值函数选择遗传运算更新种群判断停止条件停止YN染色体编码方法1、二进制编码每个染色体可以表示为X=(x1,x2,…xn)使用固定长度的0，1字符串表示一个染色体。例如X=（0110010）二进制编码适用于背包问题、指派

5、问题等。思考，还有什么编码方式？旅行商问题应该用什么样的编码方式？2、顺序编码用1到n的自然数来编码，此种编码不允许重复如：X=（2，3，1，5，4，7，6）为合法编码而X=（2，2，1，5，4，7，6）为不合法编码。顺序编码适合用于旅行商问题。3、实数编码X=(x1,x2,…xn)，xi∈R，R为实数集。4、整数编码X=(x1,x2,…xn)，xi∈Z，Z为整数集合。遗传运算1、交叉（1）单点交叉切点切点P1=A1

6、A2单点交叉C1=A1

7、B2P2=B1

8、B2C2=B1

9、A2（2）双点交叉切点切点P1=A1

10、A2

11、A3单点交叉C1=A1

12、B2

13、A3P2=B

14、1

15、B2

16、B3C2=B1

17、A2

18、B32、变异在种群中按变异概率Pm任选若干基因为改变其位值，对于0-1编码来说，就是反转位值。变异实际上是子代基因按照小概率扰动产生变化。思考：以上的遗传运算对TSP问题适用么？结论是不适用的，因为TSP问题采用的是顺序编码，经过以上的遗传运算可能对TSP产生不合法编码。需要合法性修复顺序编码的合法性修复1、交叉修复策略：（1）部分映射交叉（PMX）先随机产生两个交叉点，定义这两点间的区域为匹配区域，并用交换两个父代的匹配区域。父代A：872

19、130

20、9546父代B：983

21、567

22、1420变为：TEMPA:872

23、567

24、9

25、546TEMPB:983

26、130

27、1420对于TEMPA、TEMPＢ中匹配区域以外出现的数码重复，要依据匹配区域内的位置逐一进行替换。匹配关系：1<——>５　３<——>６　７<——>０子代Ａ：802

28、567

29、9143子代Ｂ：986

30、130

31、5427顺序编码的合法性修复2、顺序交叉法(OX)父代A:21

32、345

33、67父代B:43

34、125

35、76交叉后：子代A:34

36、125

37、67子代B:12

38、345

39、76列出基因：674213457643125顺序编码的合法性修复3、循环交叉（CX）（用于互换编码）P1=245389617236P2=398654271362295

40、384629346348659234692C1=29