下载文档原格式
数学建模遗传算法例题数学建模中，遗传算法是一种基于进化思想的优化算法，可以应用于复杂的优化问题中。
本文将介绍一些遗传算法的例题，帮助读者更好地理解遗传算法的应用。
例题一：背包问题有一个体积为V的背包和n个物品，第i个物品的体积为vi，价值为wi。
求这个背包最多能装多少价值的物品。
遗传算法的解决步骤：1. 初始化种群：随机生成一定数量的个体作为初始种群。
2. 适应度函数：将每个个体代入适应度函数，计算其适应度值。
3. 选择：根据每个个体的适应度值，选择一定数量的个体进入下一代。
4. 交叉：对被选中的个体进行交叉操作，生成新的个体。
5. 变异：对新的个体进行变异操作，引入新的基因。
6. 重复以上步骤，直到符合终止条件。
在背包问题中，适应度函数可以定义为：背包中物品的总价值。
交叉操作可以选择单点交叉或多点交叉，变异操作可以选择随机变异或非随机变异。
例题二：旅行商问题有n个城市，旅行商需要依次经过这些城市，每个城市之间的距离已知。
求旅行商经过所有城市的最短路径。
遗传算法的解决步骤：1. 初始化种群：随机生成一定数量的个体作为初始种群，每个个体代表一种旅行路线。
2. 适应度函数：将每个个体代入适应度函数，计算其适应度值。
3. 选择：根据每个个体的适应度值，选择一定数量的个体进入下一代。
4. 交叉：对被选中的个体进行交叉操作，生成新的个体。
5. 变异：对新的个体进行变异操作，引入新的基因。
6. 重复以上步骤，直到符合终止条件。
在旅行商问题中，适应度函数可以定义为：旅行商经过所有城市的总距离。
交叉操作可以选择顺序交叉或部分映射交叉，变异操作可以选择交换或反转基因序列。
总结：遗传算法是一种强大的优化算法，可以应用于多种复杂的优化问题中。
在数学建模中，遗传算法的应用也越来越广泛。
本文介绍了背包问题和旅行商问题的遗传算法解决步骤，希望对读者有所帮助。
关于旅行商问题的数学模型旅行商问题（TravelingSalesmanProblem，TSP）是著名的组合优化问题，它的目标是找到一条路径，使得一个旅行商可以经过所有给定的城市，路径总长度最短。
这个问题在实际生活中有着广泛的应用，例如物流配送、电路板布线、DNA序列比对等领域。
本文将介绍旅行商问题的数学模型和解法。
1. 问题描述假设有n个城市，它们的位置分别为(xi,yi)，i=1,2,...,n。
旅行商要从一个城市出发，经过所有城市恰好一次，最后回到出发城市。
城市之间的距离可以用欧几里得距离表示：d(i,j) = sqrt((xi-xj)^2 + (yi-yj)^2)旅行商问题的目标是找到一条路径，使得路径总长度最短。
2. 数学模型2.1 定义变量我们定义变量xij表示从城市i到城市j的路径是否被选择，如果被选择则xij=1，否则xij=0。
例如，x12表示从城市1到城市2的路径是否被选择。
2.2 目标函数旅行商问题的目标是找到一条路径，使得路径总长度最短。
因此，我们可以定义目标函数为：minimize ∑i∑j d(i,j)xij其中，i,j表示城市的编号，d(i,j)表示城市i和城市j之间的距离，xij表示从城市i到城市j的路径是否被选择。
2.3 约束条件旅行商需要经过所有城市恰好一次，因此我们需要添加以下约束条件：1. 每个城市只能被经过一次：∑j xij = 1, i=1,2,...,n2. 每个城市离开后只能到达一个城市：∑i xij = 1, j=1,2,...,n3. 不能出现子回路：∑i∈S ∑j∈S xij ≤ |S|-1, S{1,2,...,n}, |S|≥2其中，第一个约束条件表示每个城市只能被经过一次，第二个约束条件表示每个城市离开后只能到达一个城市，第三个约束条件表示不能出现子回路。
3. 解法旅行商问题是一个NP难问题，没有多项式时间算法可以求解。
因此，我们需要使用一些启发式算法来求解这个问题。
《物流软件》实验报告实验编号：实验2学号：序号：姓名：班级：2015年10月一、旅行商问题（1）数学模型设di是两点i与j之间的距离，Xij=0或1（1表示连接，0表示不连接）则有Min∑∈VjXij dij*s.t. ∑∈VjXij=1 ，（每个点只有一条边出去），i∈V∑∈VjXji=1，（每个点只有一条边进入），i∈V(除起点与重点外，个边不构成圈)（2）L INGO程序MODEL:SETS:CENTERS/1..8/:LEVEL;LINK(CENTERS,CENTERS):DISTANCE,X;ENDSETSDATA:DISTANCE = 0 3 2 3 4 3 5 63 0 2 3 2 3 1 42 2 0 1 43 2 53 3 1 0 1 14 3 44 2 4 1 0 2 2 33 3 3 14 2 0 8 45 1 2 3 2 8 0 36 4 5 4 3 4 3 0;ENDDATAN=@SIZE(CENTERS);MIN=@SUM(LINK(I,J)|i #ne# j :distance(i,j)*x(i,j));@for(centers(i):@sum(centers(j)|j #ne# i:x(j,i))=1;@SUM(CENTERS(J)|J #NE# I:X(I,J)) = 1;@FOR(CENTERS(j)|J #GT# 1 #AND# J #NE# I :LEVEL(J)>=LEVEL(I)+X(I,J)-(N-2)*(1-X(i,J))+(N-3)*X(J,I););); @FOR(LINK:@BIN(X));@FOR(CENTERS(I)|I #GT# 1:LEVEL(I)<=N-1-(N-2)*X(1,I);LEVEL(I)>=1+(N-2)*X(I,1););ENDCENTERS/1..8/是基本集合名字，元素为1到8。
LEVEL 为其元素。
图算法--旅⾏商问题旅⾏商问题的描述试想⼀下，⼀个业务员因⼯作需要必须访问多个城市。
他的⽬标是每个城市只访问⼀次，并且尽可能地缩短旅⾏的距离，最终返回到他开始旅⾏的地点，这就是旅⾏商问题的主要思想。
在⼀幅图中，访问每个顶点⼀次，并最终返回起始顶点，这个访问的轨迹称为哈密顿圈。
要解决旅⾏商问题，需要⽤图G=（V，E）作为模型，寻找图中最短的哈密顿圈。
G是⼀个完整的、⽆⽅向的带权图，其中V代表将要访问的顶点的集合，E为连接这些顶点的边的集合。
E中每条边的权值由顶点之间的距离决定。
由于G中⼀个完整的、⽆⽅向的图，因此E包含V（V-1）/2条边。
事实上，旅⾏商问题是⼀种特殊的⾮多项式时间问题，称为NP完全问题。
NP完全问题是指那些多项式时间算法未知，倘没有证据证明没有解决的可能性的问题。
考虑到这种思想，通常⽤⼀种近似算法来解决旅⾏商问题。
最近邻点法的应⽤⼀种近似的计算旅⾏商路线的⽅法就是使⽤最近邻点法。
其运算过程如下：从⼀条仅包含起始顶点的路线开始，将此顶点涂⿊。
其他顶点为⽩⾊，在将其他顶点加⼊此路线中后，再将相应顶点涂⿊。
接着，对于每个不在路线中的顶点v，要为最后加⼊路线的顶点u与v之间的边计算权值。
在旅⾏商问题中，u与v之间边的权值就是u到v 之间的距离。
这个距离可以⽤每个顶点的坐标计算得到。
两个点（x1，y1）与（x2，y2）之间距离的计算公式如下：r = √（x2 - x1）2 + （y2 - y1）2 （注意是求和的平⽅根）利⽤这个公式，选择最接近u的顶点，将其涂⿊，同时将其加⼊路线中。
接着重复这个过程，直到所有的顶点都涂成⿊⾊。
此时再将起始顶点加⼊路线中，从⽽形成⼀个完整的回路。
下图展⽰了使⽤最近邻点法来解决旅⾏商问题的⽅法。
通常，在为旅⾏商问题构造⼀个图时，每个顶点之间相连的边不会显⽰表⽰出来，因为这种表⽰会让图不清晰了，也没有必要。
在图中，每个顶点旁边都显⽰其坐标值，虚线表⽰在此阶段需要⽐较距离的边。
理工学院数学建模大型作业2011—2012 学年第1学期目录一．摘要二．旅行问题1.问题描述2.符号说明3.模型设计4.建模求解5.模型分析三．建模过程及心得体会四．参考文件一．摘要本文是一个围绕旅行商问题和背包问题这两个经典问题的论文。
问题一,是一个依赖与每个城市去一次且仅去一次的路线确定问题,问题二类似于问题一。
问题三是一个依赖于可背重量限制的背包问题。
关键词：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 ij i j dx =∑∑ <i ≠j>s.t.61ij i x=∑=1 〔i ≠j ；j=1,2,……,6 61ij j 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可以是连续变化的,虽然这些变量在最优解中取普通的整数值〔从而在约束条件中,可以限定这些变量为整数。
走遍全中国方案的研究摘要本文通过对走遍中国各省会城市、直辖市和港澳台的最优路径选择问题进行分析，发现这是一个十分典型的旅行商问题（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 =+++。
黄石理工学院数学建模大型作业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。
