下载文档原格式
数学建模遗传算法例题数学建模中，遗传算法是一种基于进化思想的优化算法，可以应用于复杂的优化问题中。
本文将介绍一些遗传算法的例题，帮助读者更好地理解遗传算法的应用。
例题一：背包问题有一个体积为V的背包和n个物品，第i个物品的体积为vi，价值为wi。
求这个背包最多能装多少价值的物品。
遗传算法的解决步骤：1. 初始化种群：随机生成一定数量的个体作为初始种群。
2. 适应度函数：将每个个体代入适应度函数，计算其适应度值。
3. 选择：根据每个个体的适应度值，选择一定数量的个体进入下一代。
4. 交叉：对被选中的个体进行交叉操作，生成新的个体。
5. 变异：对新的个体进行变异操作，引入新的基因。
6. 重复以上步骤，直到符合终止条件。
在背包问题中，适应度函数可以定义为：背包中物品的总价值。
交叉操作可以选择单点交叉或多点交叉，变异操作可以选择随机变异或非随机变异。
例题二：旅行商问题有n个城市，旅行商需要依次经过这些城市，每个城市之间的距离已知。
求旅行商经过所有城市的最短路径。
遗传算法的解决步骤：1. 初始化种群：随机生成一定数量的个体作为初始种群，每个个体代表一种旅行路线。
2. 适应度函数：将每个个体代入适应度函数，计算其适应度值。
3. 选择：根据每个个体的适应度值，选择一定数量的个体进入下一代。
4. 交叉：对被选中的个体进行交叉操作，生成新的个体。
5. 变异：对新的个体进行变异操作，引入新的基因。
6. 重复以上步骤，直到符合终止条件。
在旅行商问题中，适应度函数可以定义为：旅行商经过所有城市的总距离。
交叉操作可以选择顺序交叉或部分映射交叉，变异操作可以选择交换或反转基因序列。
总结：遗传算法是一种强大的优化算法，可以应用于多种复杂的优化问题中。
在数学建模中，遗传算法的应用也越来越广泛。
本文介绍了背包问题和旅行商问题的遗传算法解决步骤，希望对读者有所帮助。
旅行售货员(TSP)，Hamilton回路的lingo程序方法一model:sets:city / 1..6/: u;! 定义6个城市;link( city, city):dist, ! 距离矩阵;x; !决策变量;endsetsn = @size( city);data: !距离矩阵;dist =0 2 100 4 100 22 0 8 100 4 100100 8 0 5 8 74 1005 06 100100 4 8 6 0 42 100 7 100 4 0 ;!这里可改为你要解决的问题的数据;enddata!目标函数;min = @sum( link: dist * x);@FOR( city( K):!进入城市K;@sum( city( I)| I #ne# K: x( I, K)) = 1;!离开城市K;@sum( city( J)| J #ne# K: x( K, J)) = 1;);!保证不出现子圈;@for(city(I)|I #gt# 1:@for( city( J)| J#gt#1 #and# I #ne# J:u(I)-u(J)+n*x(I,J)<=n-1););!限制u的范围以加速模型的求解，保证所加限制并不排除掉TSP问题的最优解;@for(city(I) : u(I)<=n-1 );@for( link: @bin( x));!定义X为0\1变量;end部分结果有：Global optimal solution found.Objective value: 26.00000Objective bound: 26.00000Infeasibilities: 0.000000Extended solver steps: 0Total solver iterations: 179V ariable V alue Reduced CostN 6.000000 0.000000U( 1) 5.000000 0.000000U( 2) 0.000000 0.000000U( 3) 3.000000 0.000000U( 4) 5.000000 0.000000U( 5) 1.000000 0.000000U( 6) 2.000000 0.000000注意，这里有两个u(1)=U(4)=5说明：（1）红色部分语句1）保证不会有某一边来回的情况假如有某(i,j)来回，则x(i,j)=x(j,i)=1,对这两个x(i,j)=x(j,i)=1分别用一次上述for语句，得到：u(i)-u(j)+n*x(i,j)<=n-1u(j)-u(i)+n*x(j,i)<=n-1将这两个不等式两边相加，则得到矛盾2n<=2(n-1)2）保证不出现子圈假如有某个子圈i->j->k->i产生，那么一定同时会有一个不包含起点1的子圈产生，所以不妨设子圈i->j->k->i不包含起点1，则有x(i,j)=x(j,k)=x(k,i)=1,但x(j,i)=x(k,j)=x(i,k)=0,对上述3个x(i,j)=x(j,k)=x(k,i)=1分别用三次上面的for语句得到：u(i)-u(j)+n*x(i,j)<=n-1u(j)-u(k)+n*x(j,k)<=n-1u(k)-u(i)+n*x(k,i)<=n-1将三个不等式相加，得到矛盾3n<=3(n-1)，所以可不能产生子圈。
资料范本本资料为word版本，可以直接编辑和打印，感谢您的下载旅行商问题数学建模地点：__________________时间：__________________说明：本资料适用于约定双方经过谈判，协商而共同承认，共同遵守的责任与义务，仅供参考，文档可直接下载或修改，不需要的部分可直接删除，使用时请详细阅读内容黄石理工学院数学建模大型作业2011—2012 学年第1学期目录一．摘要二．旅行问题问题描述符号说明模型设计建模求解模型分析三．建模过程及心得体会四．参考文件一．摘要本文是一个围绕旅行商问题和背包问题这两个经典问题的论文。
问题一，是一个依赖与每个城市去一次且仅去一次的路线确定问题，问题二类似于问题一。
问题三是一个依赖于可背重量限制的背包问题。
关键词：HAMILTON回路 LINGO 最优旅行路线 0-1模型二．旅行问题问题描述某人要在假期内从城市A出发，乘火车或飞机到城市B,C,D,E,F旅游购物。
他计划走遍这些城市各一次且仅一次，最后返回城市A。
已知城市间的路费数据见附表1，请你设计一条旅行路线使得他的总路费最少。
如果临行他因故只能去4个城市，该怎样修订旅行路线？在城市间旅游时他计划购买照相机，衣服，书籍，摄像机，渔具，白酒，食品，而受航空行李重量的限制以及个人体力所限，所买物品的总重量不能超过15kg，各种物品的价格见附表2.请你为他决策买哪些物品，使所买物品价值最大。
附表1：附表2模型设计首先给出一个定义：设v1,v2,......,vn是图G中的n个顶点，若有一条从某一顶点v1出发，经过各节点一次且仅一次，最后返回出发点v1的回路，则称此回路为HAMILTON回路。
问题1.分析：这个优化问题的目标是使旅行的总费用最少，要做的决策是如何设定旅行路线，决策受的约束条件：每个城市都必须去，但仅能去一次。
按题目所给，将决定变量，目标函数和约束条件用数学符号及式子表示出来，就可得一下模型。
走遍全中国方案的研究摘要本文通过对走遍中国各省会城市、直辖市和港澳台的最优路径选择问题进行分析，发现这是一个十分典型的旅行商问题（Traveling Salseman Problem ），即寻找一条遍历n 个城市（在本文中为34个城市）的最短路径。
我们搜索了这34个城市的经纬度和部分列车、航班时刻表等各方面信息，综合省钱、省时、方便等因素，进一步深入并细化，从而得到判断各订票方案的准则。
针对问题一，我们利用欧几里得平面知识，由公式0002901800290A B x R A y R ππ+⎧=⋅⎪⎪⎨-⎪=⎪⎩将该34个城市的经纬度转化为平面直角坐标，从而将其简化成二维平面问题。
目前，解旅行商问题（tsp 问题）的方法有许多种，本文采用了较为先进的遗传算法。
遗传算法是目前解决组合优化问题最有效的工具之一，本文介绍了遗传算法的基本原理，讨论了遗传算法中的有关遗传算子设计等方面的技术。
由于该算法在搜索空间中同时考虑了许多点，这样就减少了收敛于局部极小的可能，也增加了处理的并行性。
同时，我们利用MATLAB 软件编辑了相关程序，计算出了遍历该34个城市的最短路径，其路径长度为14661km 。
对于问题二，在只考虑旅行路线最经济的前提下，结合第一问得出的最优路径，我们收集了这34个城市的列车和航班时刻表等信息，从而找出最经济的订票方案，并得其花费为11426元。
针对问题三，在综合考虑省时、省钱、方便等诸多因素的前提下制定订票方案的评价准则，我们运用了层次分析法对其进行研究。
根据对旅行过程中省时，省钱及方便的偏重程度，我们相应地给出了判断矩阵111571513731⎡⎤⎢⎥⎢⎥⎢⎥=⎢⎥⎢⎥⎢⎥⎢⎥⎣⎦A ，然后对其进行一致性检验，发现其不一致程度在容许范围内。
因此我们利用其最大特征根max λ对应的特征向量w 作为比较因素的权向量，并得到以下评价表达式：12120.0740.2830.643*(0.8330.167)C x x x x =+++。
3 旅行商问题3.1 旅行商问题概述3.1.1 旅行商问题的定义和数学模型① 定义旅行商问题(Traveling Salesman Problem ，简记TSP)是组合数学中一个古老而又困难的问题，它易于描述但至今尚未彻底解决，现己归入所谓的NP 完全问题类，经典提法为：有一货物推销员要去若干个城市推销货物，从城市1出发，经其余各城市一次，然后回到城市1，问选择怎样的行走路线，才能使总行程最短（各城市间距离为己知）。
该问题在图论的意义下就是所谓的最小Hamilton 圈问题，由于在许多领域中都有着广泛的应用，因而寻找其实际而有效的算法就显得颇为重要了。
遗憾的是，计算复杂性理论给予我们的结论却是，这种可能性尚属未知。
若设城市数目为n 时，那么组合路径数则为(n-1)!。
很显然，当城市数目不多时要找到最短距离的路线并不难，但随着城市数目的不断增大，组合路线数将呈指数级数规律急剧增长，以至达到无法计算的地步，这就是所谓的“组合爆炸问题”。
假设现在城市的数目增为20个，组合路径数则为(20-1)! ，如此庞大的组合数目，若计算机以每秒检索1000万条路线的速度计算，也需要花上386年的时间。
尽管现在计算机的计算速度大大提高，而且已有一些指数级的算法可精确地求解旅行商问题，但随着它们在大规模问题上的组合爆炸，人们退而求其次，转向寻找近似算法或启发式算法，经过几十年的努力，取得了一定的进展。
② 数学模型设(,)G V E =为赋权图，{1,2,}V n ="为顶点集，E 为边集，各顶点间距离为ij c ，已知(0,,,)ij ij c c i j V >=+∞∈，并设则旅行商问题的数学模型可写成如下的线性规划形式：ij ij i jMinZ c x ≠=∑1,(,)0,ij i j x ⎧=⎨⎩边在最优路线上其它,1,1,.1,{0,1},ij j i ij i jij i j S ij x i V x j V s t x K K V x i j V ≠≠∈⎧=∈⎪⎪=∈⎪⎨⎪≤−⊂⎪⎪∈∈⎩∑∑∑这里，K 为V 的所有非空子集，K 为集合K 中所含图G 的顶点个数。
黄石理工学院数学建模大型作业2011—2012 学年第1学期目录一．摘要二．旅行问题1.问题描述2.符号说明3.模型设计4.建模求解5.模型分析6.三．建模过程及心得体会四．参考文件一．摘要本文是一个围绕旅行商问题和背包问题这两个经典问题的论文。
问题一，是一个依赖与每个城市去一次且仅去一次的路线确定问题，问题二类似于问题一。
问题三是一个依赖于可背重量限制的背包问题。
关键词：HAMILTON回路LINGO 最优旅行路线0-1模型二．旅行问题问题描述某人要在假期内从城市A出发，乘火车或飞机到城市B,C,D,E,F 旅游购物。
他计划走遍这些城市各一次且仅一次，最后返回城市A。
已知城市间的路费数据见附表1，请你设计一条旅行路线使得他的总路费最少。
如果临行他因故只能去4个城市，该怎样修订旅行路线？在城市间旅游时他计划购买照相机，衣服，书籍，摄像机，渔具，白酒，食品，而受航空行李重量的限制以及个人体力所限，所买物品的总重量不能超过15kg，各种物品的价格见附表2.请你为他决策买哪些物品，使所买物品价值最大。
模型设计首先给出一个定义：设v1,v2,......,vn 是图G 中的n 个顶点，若有一条从某一顶点v1出发，经过各节点一次且仅一次，最后返回出发点v1的回路，则称此回路为HAMILTON 回路。
问题1.分析：这个优化问题的目标是使旅行的总费用最少，要做的决策是如何设定旅行路线，决策受的约束条件：每个城市都必须去，但仅能去一次。
按题目所给，将决定变量，目标函数和约束条件用数学符号及式子表示出来，就可得一下模型。
模型建立：对于6个城市的旅行问题设A,B,C,D,E,F 六个城市分别对应v1,v2,v3,v4,v5,v6。
假设ij d 表示从城市i 到城市j 的费用。
定义0-1整数型变量ij x =1表示从城市i 旅行到城市j ，否则ij x =0。
则旅行问题的数学模型可表示为一个整数规划问题。
min z=661ij iji jdx =∑∑ (i ≠j)s.t.61iji x=∑=1 （i ≠j ；j=1,2, (6)61ijj x=∑=1 (i ≠j ；i=1,2, (6)1i j ij u u nx n -+≤- (i ≠j;i=2,3,……,6;j=2,3,……6)其中辅助变量i u （i=2,3,……,6）可以是连续变化的，虽然这些变量在最优解中取普通的整数值（从而在约束条件中，可以限定这些变量为整数）。
事实上，在最优解中，i u =访问城市的顺序数。
模型求解运用LINGO ，输入程序：MODEL :!Traveling Sales Problem for the cities of six city; SETS :CITY / 1..6/: U; ! U( I) = sequence no. of city;LINK( CITY, CITY): COST, ! The cost matrix;X; ! X( I, J) = 1 if we use link I, J;ENDSETSDATA: !Cost matrix, it need not be symmetric;COST= 0 120 250 330 210 150120 0 98 350 225 300250 98 0 520 430 280330 350 520 0 270 185210 225 430 270 0 420150 300 280 185 420 0 ;ENDDATAN= @SIZE( CITY);MIN= @SUM( LINK: COST * X);@FOR( CITY( K): !It must be entered;@SUM( CITY( I)| I #NE# K: X( I, K)) = 1;! It must be departed;@SUM( CITY( J)| J #NE# K: X( K, J)) = 1;!Weak form of the subtour breaking constrains;!These are not very powerful for large problems;@FOR( CITY( J)| J #GT# 1 #AND# J #NE# K:U(J)>=U(K)+X(K,J)-(N-2)*(1-X(K,J))+(N-3)*X(J,K)););@FOR( LINK: @BIN( X)); !Make the X's 0/1;! For the first and last stop we know...;@FOR( CITY( K)| K #GT# 1:U( K) <= N - 1 - (N - 2) * X( 1, K);U( K) >= 1 + ( N - 2) * X( K, 1));END得到结果：总费用为1163路线：A-B-C-F-D-E-A问题2.临时因故只能去4个城市，那么应该怎样安排旅行路线。
分析：在B,C,D,E,F五个城市中选4个城市，显然有5种可能，按照问题一中的模型，将费用矩阵稍作修改，运用LINGO分别解除5种可能的费用，进行比较，即得结果。
（1）选取B,D,E,F，计算旅行费用：MODEL:!Traveling Sales Problem for the cities of six city;SETS:CITY / 1..5/: U; ! U( I) = sequence no. of city;LINK( CITY, CITY): COST, ! The cost matrix;X; ! X( I, J) = 1 if we use link I, J;ENDSETSDATA: !Cost matrix, it need not be symmetric;COST= 0 120 330 210 150120 0 350 225 300330 350 0 270 185210 225 270 0 420150 300 185 420 0 ;ENDDATAN= @SIZE( CITY);MIN= @SUM( LINK: COST * X);@FOR( CITY( K): !It must be entered;@SUM( CITY( I)| I #NE# K: X( I, K)) = 1;! It must be departed;@SUM( CITY( J)| J #NE# K: X( K, J)) = 1;!Weak form of the subtour breaking constrains;!These are not very powerful for large problems;@FOR( CITY( J)| J #GT# 1 #AND# J #NE# K:U(J)>=U(K)+X(K,J)-(N-2)*(1-X(K,J))+(N-3)*X(J,K));); @FOR( LINK: @BIN( X)); !Make the X's 0/1;! For the first and last stop we know...;@FOR( CITY( K)| K #GT# 1:U( K) <= N - 1 - (N - 2) * X( 1, K);U( K) >= 1 + ( N - 2) * X( K, 1));END得到结果：总费用：950路线：A-B-E-D-F-A(2)选取B,C,E,F，计算旅行费用：MODEL:!Traveling Sales Problem for the cities of six city; SETS:CITY / 1..5/: U; ! U( I) = sequence no. of city;LINK( CITY, CITY): COST, ! The cost matrix;X; ! X( I, J) = 1 if we use link I, J;ENDSETSDATA: !Cost matrix, it need not be symmetric;COST= 0 120 250 210 150120 0 98 225 300250 98 0 430 280210 225 430 0 420150 300 280 420 0 ;ENDDATAN= @SIZE( CITY);MIN= @SUM( LINK: COST * X);@FOR( CITY( K): !It must be entered;@SUM( CITY( I)| I #NE# K: X( I, K)) = 1;! It must be departed;@SUM( CITY( J)| J #NE# K: X( K, J)) = 1;!Weak form of the subtour breaking constrains;!These are not very powerful for large problems;@FOR( CITY( J)| J #GT# 1 #AND# J #NE# K:U(J)>=U(K)+X(K,J)-(N-2)*(1-X(K,J))+(N-3)*X(J,K));); @FOR( LINK: @BIN( X)); !Make the X's 0/1;! For the first and last stop we know...;@FOR( CITY( K)| K #GT# 1:U( K) <= N - 1 - (N - 2) * X( 1, K);U( K) >= 1 + ( N - 2) * X( K, 1));END得到结果：总费用：963路线：A-E-B-C-F-A(3)选取B,C,D,F,计算旅行费用：MODEL:!Traveling Sales Problem for the cities of six city; SETS:CITY / 1..5/: U; ! U( I) = sequence no. of city;LINK( CITY, CITY): COST, ! The cost matrix;X; ! X( I, J) = 1 if we use link I, J;ENDSETSDATA: !Cost matrix, it need not be symmetric;COST= 0 120 250 330 150120 0 98 350 300250 98 0 520 280330 350 520 0 185150 300 280 185 0 ;ENDDATAN= @SIZE( CITY);MIN= @SUM( LINK: COST * X);@FOR( CITY( K): !It must be entered;@SUM( CITY( I)| I #NE# K: X( I, K)) = 1;! It must be departed;@SUM( CITY( J)| J #NE# K: X( K, J)) = 1;!Weak form of the subtour breaking constrains;!These are not very powerful for large problems;@FOR( CITY( J)| J #GT# 1 #AND# J #NE# K:U(J)>=U(K)+X(K,J)-(N-2)*(1-X(K,J))+(N-3)*X(J,K));); @FOR( LINK: @BIN( X)); !Make the X's 0/1;! For the first and last stop we know...;@FOR( CITY( K)| K #GT# 1:U( K) <= N - 1 - (N - 2) * X( 1, K);U( K) >= 1 + ( N - 2) * X( K, 1));END得到结果：总费用：1013路线：A-B-C-F-D-A(4)选取路线:B,C,D,E,计算旅行费用：MODEL:!Traveling Sales Problem for the cities of six city; SETS:CITY / 1..5/: U; ! U( I) = sequence no. of city;LINK( CITY, CITY): COST, ! The cost matrix;X; ! X( I, J) = 1 if we use link I, J;ENDSETSDATA: !Cost matrix, it need not be symmetric;COST= 0 120 250 330 210120 0 98 350 225250 98 0 520 430330 350 520 0 270210 225 430 270 0 ;ENDDATAN= @SIZE( CITY);MIN= @SUM( LINK: COST * X);@FOR( CITY( K): !It must be entered;@SUM( CITY( I)| I #NE# K: X( I, K)) = 1;! It must be departed;@SUM( CITY( J)| J #NE# K: X( K, J)) = 1;!Weak form of the subtour breaking constrains;!These are not very powerful for large problems;@FOR( CITY( J)| J #GT# 1 #AND# J #NE# K:U(J)>=U(K)+X(K,J)-(N-2)*(1-X(K,J))+(N-3)*X(J,K));); @FOR( LINK: @BIN( X)); !Make the X's 0/1;! For the first and last stop we know...;@FOR( CITY( K)| K #GT# 1:U( K) <= N - 1 - (N - 2) * X( 1, K);U( K) >= 1 + ( N - 2) * X( K, 1));END得到结果：总费用：1173路线:A-C-B-E-D-A(5)选取C,D,E,F,计算旅行费用：MODEL:!Traveling Sales Problem for the cities of six city;SETS:CITY / 1..5/: U; ! U( I) = sequence no. of city;LINK( CITY, CITY): COST, ! The cost matrix;X; ! X( I, J) = 1 if we use link I, J;ENDSETSDATA: !Cost matrix, it need not be symmetric;COST= 0 250 330 210 150250 0 520 430 280330 520 0 270 185210 430 270 0 420150 280 185 420 0 ;ENDDATAN= @SIZE( CITY);MIN= @SUM( LINK: COST * X);@FOR( CITY( K): !It must be entered;@SUM( CITY( I)| I #NE# K: X( I, K)) = 1;! It must be departed;@SUM( CITY( J)| J #NE# K: X( K, J)) = 1;!Weak form of the subtour breaking constrains;!These are not very powerful for large problems;@FOR( CITY( J)| J #GT# 1 #AND# J #NE# K:U(J)>=U(K)+X(K,J)-(N-2)*(1-X(K,J))+(N-3)*X(J,K)););@FOR( LINK: @BIN( X)); !Make the X's 0/1;! For the first and last stop we know...;@FOR( CITY( K)| K #GT# 1:U( K) <= N - 1 - (N - 2) * X( 1, K);U( K) >= 1 + ( N - 2) * X( K, 1));END得到结果：总费用：1195路线：A-C-F-D-E-A因此，总结以上（1），（2），（3），（4），（5）五种情况可得:应该选用路线：A-B-E-D-F-A。
