主要介绍几种典型的智能计算理论与方法. 1讲述基于热力学退火过程产生的模拟退火算法； 2介绍一类从智能观点模拟生物智能的计算理论与方法—遗传算法；
3与§4分别介绍模仿蚁群迁徙与觅食过程以及模拟鸟类群体行为而建立起来的蚁群算法和粒子群算法；
5 元胞自动机的概念与算法，支持向量机等
智能计算产生的背景
优化问题的数学语言
max ()
..{|()0,1,2,,}
i f x s t X S X g X i n ∈=≥=
其中，()f X 为目标函数，()i g X 为n 个约束条件（函数）。
不难看出，优化问题是指在一定约束条件下，寻找一组参数使其最优性得到满足。
根据目标与约束条件中变量是否满足线性、连续、目标函数的个数等，优化问题又可以分为线性和非线性规划，或单目标规划与多目标规划等。
线性规划中，当变量为整数或仅取0与1时，又得到整数规划或0-1整数规划。在一般情形下，非线性规划问题远远高于线性规划问题的求解难度。
当考虑(1)k k >个目标函数时，上述优化问题可以描述为
12max (),()((),(),,())..{|()0,1,2,,}
T
k i F X F X f X f X f X s t X S X g X i n =∈=≥=
其中，()F X 为多目标变量。
对于多目标优化问题而言，所包含的不同目标函数之间往往存在着目标不一致的地方，因此在求解过程中，很难满足同时达到最优的情形。
根据变量的特性，优化问题又可以分为函数优化与组合优化两种，其中，优化对象约束在一定的区域时，呈现为函数
优化问题，而优化对象为解空间中的离散状态时，则为组合优化问题。组合优化问题可以描述为：
12m ax ()
{,,,}i i n C s s S s s s ?∈=
本节后面介绍的旅行商问题（TSP ）、最大截问题、0-1背包问题以及调度问题等都属于组合优化问题。
最优化问题的求解可以分为经典优化算法与启发式优化算法。1947年。美国数学家Dantzig 提出了求解线性规划问题的单纯性算法，随后，Kamaka 提出多项式级的椭球算法与内点算法。
对于非线性问题，人们从二次规划问题入手，建立了许多经典算法，如最速下降法、共轭梯度法、牛顿法与拟牛顿法等。
经典算法的局限性：
一般使用局部信息，如需要初始点以及导数等信息，从
智能计算的兴起：受到大自然运行规律的启发，上世纪50年代开始启发式算法得到广泛采用，尤其是启发式算法思想与人工智能领域中的各种有关问题求解方法相结合，产生
一、模拟退火算法
模拟退火算法属于一种典型的启发式算法 Kirpatrick （1982）
基本思想：观察到固体退火过程与离散系统中的组合优化问题的求解存在某种相似性，并将Metropolis 准则引入到组和优化问题的求解中，建立了一种对Metropolis 算法进行迭代的组合优化算法，由于该算法模拟固体退火原理，因此经常称之为“模
拟退火算法”。 1．Metropolis 准则
Monte Carlo 方法 固体在指定温度下达到热平衡的过程可以通过Motel Carlo 方法进行仿真来实现，原理简单，算法易于编程实现
问题：为了保证算法的精确性则必须进行大量采样，从而存在计算量巨大的问题。
Metropolis 准则，Metropolis 于1953年提出
思想: 借鉴Monte Carlo 方法的思想,只对”重要贡献”的状态进行采样,目的: 减少运算量
通过随机方式达到最优解，其方法可以描述如下（优异者一定接受，劣者按概率接受）：
先给定以粒子相对位臵表征的初始状态i ，作为固体的当前状态，该状态的能量设为i
E ，然后利用摄动装臵使随机选取的某
个粒子的位移产生微小的变化，得到一个新的状态j,该状态的能量记为j
E ，如果j
i E
E <，则该新状态就作为“重要”状态，如
果j
i E
E >，则考虑到热运动的影响，该新状态是否“重要”需要
设臵一个概率数来进行判断，具体做法是设固体处于状态I 与状态j 的概率比值设为r ，r 为一个小于1的数，用随机数产生器产生一个位于[0,1)区间的随机数ξ，若r ξ>，则新状态j 仍然作为“重要”状态，否则舍去。
若新状态j 是重要状态，就以j 取代I 成为当前状态，否则
仍以I 为当前状态，一直重复上述新状态的产生过程，当固体经过大量变换（或称为迁移）后，系统趋于能量较低的平衡状态。
上述随机接受新状态的准则称之为Metropolis 准则，相应的算法称之为Metropolis 算法。由于采用随机方法，一般情况下Metropolis 算法的运算量明显少于Mote Carlo 方法的运算量。
2 模拟退火算法(Simulated Annealing —SA)
1982年，Kirkpartrick 提出
将固体加温至充分高（能量达到最大），再让其徐徐冷却，加温时，固体内部粒子随温升变为无序状，内能增大，而徐徐冷却时粒子渐趋有序，在每个温度都达到平衡态，最后在常温时达到基态，内能减为最小。
统计力学的研究表明，当温度为T 时，分子停留在状态r 满足Boltzmann 概率分布，即
1(){()}exp{}
()
E r P E E r Z T bT
==
-
其中()E r 为状态r 的能量，E 为分子能量的一个随机变量，()Z T 为概率分布的标准化因子：
()()exp{}
s D
E s Z T bT
∈=
-
∑
将优化问题类比成退火过程，当满足接受条件时，以概率为
1的形式接受新解，否则，根据Boltzmann 概率分布的形式接受劣解. 因此，不考虑标准化因子，粒子在温度T 时趋于平衡的概率为
exp{}
E bT
?-
，其中E 为温度T 时的内能，ΔE 为其改变量，b 为
Boltzmann 常数.
将固体退火的思想引入到组合优化问题的求解中，将内能E 模拟为目标函数值f ，温度T 演化成控制参数t ，即得到解组合优化问题的模拟退火算法：由初始解i 和控制参数初值t 开始，对当前解重复“产生新解→计算目标函数差→接受或舍弃”的迭代，并逐步衰减t 值，算法终止时的当前解即为所得近似最优解，这是基于蒙特卡罗迭代求解法的一种启发式随机搜索过程。退火过程由冷却进度表(Cooling Schedule)控制，包括控制参数的初值t 及其衰减因子Δt 、每个t 值时的迭代次数L 和停止条件S 。 上述模拟退火过程可以通过下列算法来实现.
(1) 初始化：初始温度T(充分大)，初始解状态S(是算法迭代的起点)， 每个T 值的迭代次数L
(2) 对k=1，……，L 做第(3)至第（6）步： (3) 产生新解S ′
(4) 计算增量(')()T C S C S ?=-，其中C(S)为评价函数
(5) 若0T ?<则以概率为1的形式接受S ′作为新的当前解，
否则计算概率exp{}
E
bT ?-
，并按照接照Metropolis 准则将S ′作为
新的当前解.
(6) 如果满足终止条件则输出当前解作为最优解，结束程序.
终止条件通常取为连续若干个新解都没有被接受时终止算法.
(7) T 逐渐减少，且T->0，然后转第2步.
算法中新解的产生和接受可分为如下四个步骤：
第一步是由一个产生函数从当前解产生一个位于解空间的新解；
为便于后续的计算和接受，减少算法耗时，通常选择由当前新解经过简单地变换即可产生新解的方法，如对构成新解的全部或部分元素进行臵换、互换等，注意到产生新解的变换方法决定
了当前新解的邻域结构，因而对冷却进度表的选取有一定的影响。
第二步是计算与新解所对应的目标函数差。
目标函数差仅由变换部分产生，所以目标函数差的计算最好按增量计算。事实表明，对大多数应用而言，这是计算目标函数差的最快方法。
第三步判断新解是否被接受
判断的依据是一个接受准则,最常用的接受准则是Metropo1is 准则: 若Δt′<0则接受S′作为新的当前解S，否则以概率exp(-Δt′/T)接受S作为新的当前解S。
第四步当新解被确定接受时，用新解代替当前解
这只需将当前解中对应于产生新解时的变换部分予以实现，同时修正目标函数值即可。此时，当前解实现了一次迭代。可在此基础上开始下一轮试验。而当新解被判定为舍弃时，则在原当前解的基础上继续下一轮试验。
模拟退火算法评价:
模拟退火算法与初始值无关，算法求得的解与初始解状态S(是算法迭代的起点)无关；模拟退火算法具有渐近收敛性，已在理论上被证明是一种以概率l 收敛于全局最优解的全局优化算法；模拟退火算法具有并行性。模拟退火算法的应用很广泛，可以求解NP完全问题。
模拟退火算法的数学理论支持
从数学的角度来看，可以通过马尔科夫（Markov）过程来描述模拟退火算法：在给定领域结构后，模拟退火过程是一个从一个状态到另一个状态不断的随机游动，具体地说，当温度t为确定值后，两个
状态的转移概率（transition probability ）定义为
1,()(),()1()(),ij ij N
ij il il k k i g y A t j i p t g t A t j i =≠≠??=?
-=?
?
∑ 其中，N 表示状态集合中状态的个数， ()ij
g t 称为从i 到j 的产生概率，表示在状态i 时，j 状态被选取的概率。当j 为i 的邻域时，如果采用等概率选取方法，则j 被选中的概率为
1|()|(),()0,()ij N e i g t j N e i j N e i ??
=∈????
其中(),|()|Ne i Ne i 分别表示i 的邻域以及邻域所含元素的个数，
()ij A t 为接受概率，()ij A t 表示从状态i 产生状态j 后，接受状态j 的概率，在模拟退火算法中，接受概率值为
1,()()()exp(/),()()ij ij f i f j A t f t f i f j ≥?
=?
-?
()(()),()(())ij N N ij N N G t g t A t A t ??==和
()(())ij N N P t p t ?=分别称之为产生矩阵、接受矩阵和一步转移概率矩阵。
模拟退火算法的难点: 参数难以控制，其主要问题有以下三点： (1) 温度T 的初始值设置问题.
温度T 的初始值设置是影响模拟退火算法全局搜索性能的重要因素之一、初始温度高，则搜索到全局最优解的可能性大，但因此要花费大量的计算时间；反之，则可节约计算时间，但全局搜索性能可能受到影响 .实际应用过程中，初始温度一般需要依据实验结果进行若干次调整.
(2) 退火速度问题.
模拟退火算法的全局搜索性能也与退火速度密切相关 .一般来说，同一温度下的“充分”搜索(退火)是相当必要的，但这需要计算时间 .实际应用中，要针对具体问题的性质和特征设置合理的退火平衡条件.
(3) 温度管理问题.
温度管理问题也是模拟退火算法难以处理的问题之一,降温方
式对算法影响最大，如果降温过快，可能丢失最优值点；如果降温速度太慢，算法的收敛速度又会受到较大的影响，收敛速度大大降低.实际应用中，由于必须考虑计算复杂度的切实可行性等问题，常采用如下所示的降温方式：
(1)(),1,1t t t T t T t ααα+=< .
另外，为了便于操作，也常采用下面两种取法： （1）经典退火方式 降温公式为0()ln(1)
T T t t =+，特点是温度下
降较慢，因此，算法的收敛速度也很慢；
（2） 快速退火方式 降温公式为 0()1T T t t α=
+；这种退火方式
的特点是在高温区退火速度较快、在低温区退火速度逐渐变慢，降温速度减弱，这符合在热力学分子运动理论中，在高温时某粒子所具有较低能量的概率比在低温时小得多的规律.因此，寻优的重点应该放在低温区，式中α用以改善退火曲线的形态.
上述算法可以通过程序的方式来描述，具体过程为：
SA_Algorithm
Procedure SA-Algorithm(00,i T );
/* 0
i S 为任一初始状态，0T 为初始控制参数*/
begin
(1) 0
;*;0i i S S C C k ←←←
/*简记(),*i i C C S C =为当前代价值*/ （2）repeat (2.1) repeat
(2.1.1) ()j S G enerate S ← (2.1.2) if *j C C ≤ then j S S ←
else if Accept (,)j s then j S S ← end if endig
(2.1.3) until 内循环结束；
(2.2) 1();1k i T U pdate T k k +←←+ (3) Until k T ε≤
end.
在上述算法中，（1）为初始化，（2.1.1）的Generate(S)表示从S 的邻域中随机产生下一个状态0
j S ，若*j C C ≤，则接受j 为新的当前状态；否则仅以一定的概率接受j 为新的状
态，这也是Accept(j,s0函数的功能。Accept 函数的常见形式为
function Accept(j,s) begin
'*j C C C ?←-;
if exp('/k C bT -?)>Random(0,1)/*b 为Boltzmann 常数*/ then Accept ←trie else Accept ←false endif end.
(2.1.3) 中的内循环结束条件是指在每一温度k T 下迭代多次以达到平衡状态，而（2.2）中的Update(k T ) 函数则表示温度每次下降的速度。由此可知，SA 算法有三个重要函数：生成函数generate ，接受函数Accept 和温度控制函数Update.在算法实现过程中，伪温度函数k T 和内循环次数k L 的选择直接决定了模拟退火算法的收敛速度。在组合优化算法问题的模拟退火算法求解过程中，一般取0
(),T P n =其中
n 为问题的规模，()P x 为关于x 的多项式函数；1,01k k k k
T T αα+=<<，如
0.80.9;0,1,2,k k α≈= ；迭代终止参数k ε取值范围一般为510k ε- ，当
k k T ε≤时迭代结束。
3 模拟退火算法的典型应用
模拟退火算法引入
Metropolis 准则接受新解，因此，除了接收
到较理想的解外，同时也有可能在一定范围内接受劣解。这是具有随机特色的模拟退火算法与局部搜索等确定性算法的区别。由于开始时温度T 取值较大，存在接受劣解的可能；随着T 值不断变小，可行解越来越接近最优解，当T 值趋近于0时，逐步接近最优解，从而有
可能避免局部搜索算法陷入局部最优的“陷阱”，得到整体最优解。实际例子表明，对于大多数组合优化问题而言，模拟退火算法要优于局部搜索算法。
利用模拟退火算法求解应用问题的数学模型由：
解空间、目标函数、新解的产生、代价函数差以及接受准则等五个方面组成。
问题 1．旅行商问题(Travelling Salesman Problem ，简记为
TSP) TSP 问题描述如下：设有n 个城市，用数码1,…,n 代表.城市
i 和城市j 之间的距离为
(,),.1,2,,d i j i j n = ．TSP 问题是要找
遍访每个域市恰好一次的一条回路，且其路径总长度为最短.
求解TSP 的模拟退火算法模型可描述如下： （1）解空间
解空间S 是遍访每个城市恰好一次的所有回路，是{1，……，n}的所有循环排列的集合，即11{(,,)/(,,)n n S ππππ= 为
(1,2,,)n 的排列}.j
i π
=表示在第I 次访问第j 个城市，并记
11n ππ+=以及初始解可选为(1，……，n) .
（2）目标函数
目标函数即为访问所有城市的路径总长度或称为代价函数的最小值，即求
12121(,,,)1
min
(,,,)(,)n n
n i
i S
i f d πππππππ
π+∈==
∑ (1)
其中11n ππ+=. (1)的求解通过迭代来完成,每一次迭代,需要完成下面三个任务:
(3) 产生新解
新解一般按照某种规则对序号实现变换得到,下面介绍分别或交替采用的三种变换过程.
①2变换法
随机生成两个序号,()i j i j <,交换上述序号之间的访问顺序,此时新路径变为
1111
1
i j i j i j n πππππ
ππ
π-+-+ （2）
② 3变换法
随机生成三个序号,,()i j k i j k <<,将,i j
之间的序号插入
到序号
k
之后再来访问,对应的新路径为
111i k i j k n πππππππ-+ （3）
③ 逆转中间或者逆转两端变换法 随机产生两个序号,
i j ，若i j <，则对应新的路径为
111k k i i n ππππππ-+ （4）
如果是i j >,则对应的新路径为
1
11
1j j j i i n ππ
ππ
πππ-+- （5）
也可以采用其他的变换方法，有些变换有独特的优越性，有时也将它们交替使用，得到一种更好方法.
(4) 代价函数差
设将路径12n πππ 变为新路径12n v v v ，则代价函数差为
111
[(,)(,)]n
i
i i i i f d d v v π
π++=?=
-∑ （6）
例如，相应于（2）的代价函数差为
11
11
11
11
((,)(,)(,)))((,)(,)(,)))
n
i j i j k k k i n
i i j j k k k i f d d d d d d ππππ
ππππππ
ππ-+-=+-+-=+?=++
-++
∑
∑
（7）
特别地，当问题具有对称性时，对应矩阵[(,)]D d i j =为对称矩阵，此时，(,)(,)d i j d j i =，（7）可以简化为
11
11
((,)(,))((,)(,))
i j i j i i j j F d d d d ππππ
ππππ
-+-+?=+-+
（5）接受准则
1,0exp{/},0f P f bT f ?
=?-??≥?
（8） 为简单计，讨论二维平面上的TSP 问题，其距离矩阵满足对称性
以及三角不等式：
(,)(,),(,)(,)(,)d i j d j i d i k d k j d i j =+≥
当退火过程完成以后，由变量形参
p 输出的数值即为近似最短路经，
而f 为对应的最短路长度。
下面用一个实例说明模拟退火算法求解TSP 问题的有效性. 例1 随机产生一个包含30座城市的TSP 问题 其示意图如下：
图1 TSP 问题示意图
求解本问题的模拟退火算法模型可描述如下：
解空间：解空间S 是遍访每个点恰好一次的所有路径，解可以表示为 {}1230,,......,w w w ，1230,,......,w w w 是1,2,......,30的一个排列，其中1w 为起始城市，表明从1w 出发，依次经过230,......,w w 点，再返回1w .初始解可选为(1,2,......,30)；
目标函数：访问所有城市的路径总长度；
我们要求的最优路径为目标函数为最小值时对应的路径. 新路径的产生：随机产生1和30之间的两相异数k 和m ，不妨假设k m <，则将原路径:
121112(,,...,,,...,,,...,)k k m m w w w w w w w ++
变为新路径：
121112(,,...,,,...,,,...,)m k k m w w w w w w w ++.
上述变换方法就是将k和m对应的两个垃圾站点在路径序列中交换位置，称为2-opt映射. 根据上述描述，模拟退火算法求解该TSP 问题的流程框图如下：
图2 TSP模拟退火算法流程图
通过采用Matlab编程求解，迭代效果见图3.
图3 算法迭代过程
由图3 可以看出，仅仅经过10次左右迭代便得到了问题的解，该解即使不是全局最优解，也应该是最接近最优解的近似解.
问题2．最大截问题((Max Cut Problem ，简计为MCP) 给定带权图(,)G V E =，其中
12{,,,}n V v v v =
为顶点集，E 为边界集，权矩阵为[]ij W
w =。最大截问题要求将V 划
分为子集01,V V ，使E 中所有顶点分属0V 和1V 的边的权之和最大。
问题3 0-1背包问题（Zero One Knapsack Problem ），简记为ZOKP ） 0-1背包问题是一个有约束的优化问题，问题定义如下：有n 个物品，其重量分别为W={w1, w1, w3, ... wn}，其价值分别为V={c1, c2, c3, .. cn}。现在要将这N 个物品放入允许的最大重量为w 的包中，问怎样选择物品能使包中的物品总价值最大。
0-1背包问题采用模拟退火算法求解描述如下： （1） 解空间
0-1背包问题作为有约束的优化问题，其解空间可以限定为所有可行解的集合，即
121122{(,,,)/,{0,1}}n n n i S x x x w x w x w x W x =+++≤∈
（9）
其中1i x =表示物品i 被装入背包，初始解选为(0,0,,0) .
（2） 目标函数 求下列函数的最大值
1211
m ax (,,,)..,{0,1}
n i i
i n
n
i i i i f x x x c x s t w x W x ≤≤==
≤∈∑
∑ （10）
（3）新解的产生
随机选取物品i ，若i 不在背包中，则将其直接装入背包，或同时从背包中随机取出另一物品j ；若i 已在背包中，则将其取出，
并同时随机装入另一物品
j ，即
:1i i x x =- 且（或） :1,j j x x i j =-≠ （11） (4) 背包的价值差于重量差
根据产生新解的三种可能，相应的背包价值差为
,,,i i j j
i i i j c f c c c c ??
?=-??-?将物品直接装入将装入而将取出
将j装入而将i取出
（12）
而对应背包的重量差为
,,,i i j j
i i i j w w w w w w ??
?=-??-?将物品直接装入将装入而将取出
将j装入而将i取出 （13）
w
?反映了当前重量的增量变化情况 . (5) 接受准则
0,1,,0
exp{/},,0w w W P w w W f f bT w w W f +?>?
?=+?≤?>???+?≤?≤?
（14）
问题4 调度问题（Scheduling Problem ，简记为SCP ） 设完成n 个相互独立的任务12,,,n J J J 所需的时间分别为12,,,n t t t ，
这些任务可以由m 台机器12,,,m M M M ，且每台机器每一个
时间段内只能承接一项任务。假设m 台机器同时开工，要求寻找一个分配方案，使完成任务的时间最短。
二、遗传算法
遗传算法（Genertic Algorithm,GA ）是一类模拟达尔文生
物进化论的自然选择和遗传学机理的计算模型，是一种通过模拟自然进化过程搜索最优解的方法。它最初由美国Michigan 大学J.Holland 教授于1975年提出来，颇有影响的专著《Adaptation in Natural and Artificial Systems 》出版后，GA 这个名称逐渐为人所知，J.Holland 教授所提出的GA 通常为标准遗传算法（SGA ）.
遗传算法的特点
一个例子：求解非线性方程()0f x =根的牛顿迭代法描述为
（1） 给定初始解（猜测）0x ； （2） 对于0,1,2,k = ，实施
1()
'()k k k k f x x x f x +=-
（3） 直到 ||k p k x x ε+-<中止
算法特点：（1）初始解只有一个，有可能得不到需要的根；（2）要求函数具有导函数且导函数值不能为0。
遗传算法与上述求解过程相同的是迭代部分，但不同之处在于：遗传算法的工作过程是模仿生物的进化过程。因此，首先需要确定一种编码方法，使得你的问题中的任何一个潜在的可行解都能表示为一个“数字”染色体。然后创建一个由随机的染色体组成的初始群体（不是一个单一的初始值，每个染色体代表一种不同的选择）；在一段时间内，通过适应度函数给每个个体一个数值评价，淘汰适应度低的个体（该过程称之为选择），经过复制、交叉、变异等遗传操作的个体集合形成一个新的种群，对这个种群进行下一轮进化，从而达到最优化的目的，这便是遗传算法的基本原理。
因此，遗传算法的具有如下典型特征：
（1）与自然界相似，遗传算法对求解问题的本身一无所知， 对搜索空间没有任何要求（如函数可导、光滑性、连通性等），只以决策编码变量作为运算对象并对算法所产生的染色体进行评价，可用于求解无数值概念或很难有数值概念的优化问题，应用范围广泛；
（2） 搜索过程不直接作用到变量上，直接对参数集进行编码操作，操作对象可以是集合、序列、矩阵、树、图、链和表等；
（3）搜索过程是一组解迭代到另一组解，采用同时处理群体中多个个体的方法，因此，算法具有并行特性；
（4）遗传算法利用概率转移规则，可以在一个具有不确定性的空间寻优，与一般的随机性优化方法相比，它不是从一点出发按照一条固定路线寻优，而是在整个可行解空间同时搜索，可以有效避免陷入局部极值点，具有全局最有特性；
（5）遗传算法有很强的容错能力。由于遗传算法初始解是一个种群，通过选择、交叉、变异等操作能够迅速排除与最优解相差较大的劣解。
三、遗传算法的应用
由于遗传算法的整体搜索策略和优化搜索方法在计算是不依赖于梯度信息或其它辅助知识，而只需要影响搜索方向的目标函数和相应的适应度函数，所以遗传算法提供了一种求解复杂系统问题的通用框架，它不依赖于问题的具体领域，对问题的种类有很强的鲁棒性，所以广泛应用于许多科学，下面我们将介绍遗传算法的一些主要应用领域：
1、函数优化。
函数优化是遗传算法的经典应用领域，也是遗传算法进行性能评价的常用算例，许多人构造出了各种各样复杂形式的测试函数：连续函数和离散函数、凸函数和凹函数、低维函数和高维函数、单峰函数和多峰函数等。对于一些非线性、多模型、多目标的函数优化问题，用其它优化方法较难求解，而遗传算法可以方
便的得到较好的结果。 2、 组合优化
随着问题规模的增大，组合优化问题的搜索空间也急剧增大，有时在目前的计算上用枚举法很难求出最优解。对这类复杂的问题，人们已经意识到应把主要精力放在寻求满意解上，而遗传算法是寻求这种满意解的最佳工具之一。实践证明，遗传算法对于组合优化中的NP 问题非常有效。例如遗传算法已经在求解旅行商问题、 背包问题、装箱问题、图形划分问题等方面得到成功的应用。
此外，GA 也在生产调度问题、自动控制、机器人学、图象处理、人工生命、遗传编码和机器学习等方面获得了广泛的运用。
遗传算法基本原理
遗传算法工作过程：模仿生物的进化过程
首先需要确定一种编码方法，使得所讨论的问题中的任何一个潜在的可行解都能表示为一个“数字”染色体.
然后创建一个由随机的染色体组成的初始群体（不是一个单一的初始值，每个染色体代表一种不同的选择）；
在一段时间内，通过适应度函数给每个个体一个数值评价，淘汰适应度低的个体（该过程称之为选择），经过复制、交叉、变异等遗传操作的个体集合形成一个新的种群，对这个种群进行下一轮进化，从而达到最优化的目的。
实施步骤：（1）通过随机方式产生问题的初始种群； （2）将问题编码为染色体，即将优化变量12(,,,)
T
n X
x x x = 对
应到生物中的个体，一般用字符串表示为：12L A a a a = ，该字符串称之为编码.
（从生物学的角度来看，编码相当于遗传物质的选择，每一个字符串与一个染色体对应.为了便于在计算机进行表示和处
理，在遗传算法设计中，最为常见的方式为0/1二进制编码体制）. 例如：以8座城市的TSP 问题为例，此时，TSP 问题中的两个路径与编码分别为
周游路线 二进制编码
3 4 0 7 2 5 1 6 011 100 000 111 010 101 001 110 2 5 0 3 6 1 4 7 010 101 000 011 110 001 100 111
（3）为了衡量每一个个体的优劣，我们通过定义适应度对其进行评价，对每一个个体计算适应度，实现个体的“优胜劣汰”.与生物一代一代进化类似，遗传算法的运算过程本质上为利用迭代产生种群的过程.例如，设第t 代种群为
()X t
，则通过遗传和进
化操作后，得到第1t +代种群(1)
X t +
，该种群由多个更优异的个体
组成.该个体不断重复，按照选择、交叉与变异以及“优胜劣汰”规则产生新的个体.
遗传算法流程图
新概念：初始种群、编码、个体适应度、选择、交叉、变异、解码、染色体的定义。
数学建模与计算机关系研究 【摘要】高等数学与计算机教学具有内在相关性，尤其是在数学建模应用中，根据计算机学科发展来发挥数学建模理论的作用及效果，有助于增强学生对高等数学的理解和应用能力。基于此，本文笔者就从高等数学建模理论与计算机技术的关系研究入手，来阐述建模嵌入在计算机辅助教学中的重要潜力。 【关键词】计算机；高等数学；教学改革；数学建模 1.高等数学与计算机学科发展 有人说，计算机技术的发展可以省去学习数学的麻烦，即便是很多专业计算机教师也抱有同样的想法。然而，对于计算机应用领域及实践中，计算机技术确实给很多从业者带来了便捷与高效，但计算机技术不等于数学，更不能替代数学。从高等数学教学实践来看，对于我们常见的数学概念，如比率、概率、图像、逻辑、误差、机会，以及程序等知识的认识，很多行业都在进行数字化、数量化转变，对数学知识的应用也日益广泛。从这些应用中，数学理论及知识，尤其是数学基本理论研究就显得更为重要。数学，在数学知识的应用中，更需要从练习中来提升对数学知识及概念的理解，也需要通过练习来提升运算能力。如果对数学概念及方法应用的不过，对数学单调性的知识缺乏深刻的认识，就会影响数学知识在实践应用中出现偏差。计算机技术的出现，尤其是程序化语言的应用，使得数学知识在表达与反映中能够依据不同的应用灵活有效、准确的运算，从而减少了不必要的验证，也提升了数学在各行业中的应用效率。 数学软件学科的发展，成为计算机重要的辅助教学的热门领域，也使得计算机技术能够发挥其数学应用能力。在传统的数学教学中，逻辑与直观、抽象与具体始终是研究的矛盾主体，如有些太简单的例子往往无法进行全面的计算；有些复杂的例子又需要更多的计算量。在课堂表现与讲解中，对于理性与感性知识的认知，学生缺乏有效的理解和应用，而强大的计算机运算功能却能够直观的表达和弥补这些缺陷，并依托具体的演示过程中来营造概念间的差异性，帮助学生从中领会知识及方法。在计算机的辅助教学下，教师利用对数学理论课题或应用课题，从鲜活的思维及形象的表达上借助于软件来展现，让学生从失败与成功中得到知识的应用体验，从而将被动的知识学习转变为主动的参与实践，更有助于通过实践来激发学生的创新精神。这种将数学教学思维与逻辑与计算机技术的融合，便于从教学中调整教学目标，依据学生所需知识及专业需求来分配侧重点。数学建模就是从数学学科与计算机学科的融合与实践中帮助学生协作学习，提升自身的能力。 2.信息技术是高等数学应用的产物 现代信息技术的发展及应用无处不在，对数学知识的渗透也是日益深入。当前，各行业在多种协作、多种专业融合中，借助于先进的信息技术都可以实现畅通的表达与物化。如天气预报技术、卫星电视技术、网络通讯技术等都需要从数
数学模型按照不同的分类标准有许多种类： 1.按照模型的数学方法分，有几何模型，图论模型，微分方程模型。概率模型，最优控制模型，规划论模型，马氏链模型。 2.按模型的特征分，有静态模型和动态模型，确定性模型和随机模型，离散模型和连续性模型，线性模型和非线性模型。 3.按模型的应用领域分，有人口模型，交通模型，经济模型，生态模型，资源模型。环境模型。 4.按建模的目的分，有预测模型，优化模型，决策模型，控制模型等。 5.按对模型结构的了解程度分，有白箱模型，灰箱模型，黑箱模型。 数学建模的十大算法： 蒙特卡洛算法（该算法又称随机性模拟算法，是通过计算机仿真来解决问题的算法，同时可以通过模拟可以来检验自己模型的正确性，比较好用的算法。） 数据拟合、参数估计、插值等数据处理算法（比赛中通常会遇到大量的数据需要处理，而处理数据的关键就在于这些算法，通常使用matlab作为工具。） 线性规划、整数规划、多元规划、二次规划等规划类问题（建模竞赛大多数问题属于最优化问题，很多时候这些问题可以用数学规划算法来描述，通常使用lingo、lingdo软件实现）图论算法（这类算法可以分为很多种，包括最短路、网络流、二分图等算法，涉及到图论的问题可以用这些方法解决，需要认真准备。） 动态规划、回溯搜索、分治算法、分支定界等计算机算法（这些算法是算法设计中比较常用的方法，很多场合可以用到竞赛中） 最优化理论的三大非经典算法：模拟退火法、神经网络、遗传算法（这些问题时用来解决一些较困难的最优化问题的算法，对于有些问题非常有帮助，但是算法的实现比较困难，需谨慎使用） 网格算法和穷举法（当重点讨论模型本身而情史算法的时候，可以使用这种暴力方案，最好使用一些高级语言作为编程工具） 一些连续离散化方法（很多问题都是从实际来的，数据可以是连续的，而计算机只认得是离散的数据，因此将其离散化后进行差分代替微分、求和代替积分等思想是非常重要的。 数值分析算法（如果在比赛中采用高级语言进行编程的话，那一些数值分析中常用的算法比如方程组求解、矩阵运算、函数积分等算法就需要额外编写库函数进行调用。） 图像处理算法（赛题中有一类问题与图形有关，即使与图形无关，论文中也应该要不乏图片的，这些图形如何展示以及如何处理就是需要解决的问题，通常使用matlab来处理问题。） 数学建模方法 统计：1.预测与预报2.评价与决策3.分类与判别4.关联与因果 优化：5.优化与控制 预测与预报 ①灰色预测模型（必须掌握） 满足两个条件可用： a数据样本点个数少，6-15个 b数据呈现指数或曲线的形式 ②微分方程预测（备用） 无法直接找到原始数据之间的关系，但可以找到原始数据变化速度之间的关系，通过公式
第八章 层次分析法 层次分析法（Analytic Hierarchy Process ，简称AHP ）是对一些较为复杂、较为模糊的问题作出决策的简易方法，它特别适用于那些难于完全定量分析的问题。它是美国运筹学家T. L. Saaty 教授于70年代初期提出的一种简便、灵活而又实用的多准则决策方法。 §1 层次分析法的基本原理与步骤 人们在进行社会的、经济的以及科学管理领域问题的系统分析中，面临的常常是一个由相互关联、相互制约的众多因素构成的复杂而往往缺少定量数据的系统。层次分析法为这类问题的决策和排序提供了一种新的、简洁而实用的建模方法。 运用层次分析法建模，大体上可按下面四个步骤进行： （i ）建立递阶层次结构模型； （ii ）构造出各层次中的所有判断矩阵； （iii ）层次单排序及一致性检验； （iv ）层次总排序及一致性检验。 下面分别说明这四个步骤的实现过程。 1.1 递阶层次结构的建立与特点 应用AHP 分析决策问题时，首先要把问题条理化、层次化，构造出一个有层次的结构模型。在这个模型下，复杂问题被分解为元素的组成部分。这些元素又按其属性及关系形成若干层次。上一层次的元素作为准则对下一层次有关元素起支配作用。这些层次可以分为三类： （i ）最高层：这一层次中只有一个元素，一般它是分析问题的预定目标或理想结果，因此也称为目标层。 （ii ）中间层：这一层次中包含了为实现目标所涉及的中间环节，它可以由若干个层次组成，包括所需考虑的准则、子准则，因此也称为准则层。 （iii ）最底层：这一层次包括了为实现目标可供选择的各种措施、决策方案等，因此也称为措施层或方案层。 递阶层次结构中的层次数与问题的复杂程度及需要分析的详尽程度有关，一般地层次数不受限制。每一层次中各元素所支配的元素一般不要超过9个。这是因为支配的元素过多会给两两比较判断带来困难。 下面结合一个实例来说明递阶层次结构的建立。 例1 假期旅游有1P 、2P 、3P 3个旅游胜地供你选择，试确定一个最佳地点。 在此问题中，你会根据诸如景色、费用、居住、饮食和旅途条件等一些准则去反复比较3个侯选地点。可以建立如下的层次结构模型。 目标层O 选择旅游地 准则层C 景色 费用 居住 饮食 旅途 措施层P 1P 2P 3P 1.2 构造判断矩阵 层次结构反映了因素之间的关系，但准则层中的各准则在目标衡量中所占的比重并不一定相同，在决策者的心目中，它们各占有一定的比例。 在确定影响某因素的诸因子在该因素中所占的比重时，遇到的主要困难是这些比重常常不易定量化。此外，当影响某因素的因子较多时，直接考虑各因子对该因素有多大程度的影响时，常常会因考虑不周全、顾此失彼而使决策者提出与他实际认为的
一、引言 (2) 二、数学建模的特点 (2) 三、数学建模与计算机的关系 (3) 四、计算机在数学建模中的运用 (3) 1、通用数学软件 (4) 2、Lingo/Lindo 计算最优化问题的专用数学软件 (4) 3、统计分析软件 (4) 4、绘图软件 (4) 五、程序案例 (5) 1、代码 (5) 2、运行结果 (5) 3、图例 (6) 六、结束语 (6) 七、参考文献 (6)
一、引言 在利用数学方法分析和解决实际问题时，要求从实际错综复杂的关系中找出其内在的规律，然后用数学的语言--即数字、公式、图表、符号等刻画和描述出来，然后经过数学与计算机的处理--即计算、迭代等得到定量的结果，供人们进行分析、预报、决策和控制，这种把实际问题进行合理的简化假设归结为数学问题并求解的过程就是建立数学模型，简称建模。而这种成功的方法和技术反映在培养专门人才的大学教学活动中，就是数学建模教学和竞赛。数学建模简而言之就是应用数学模型来解决各种实际问题的过程，也就是通过对实际问题的抽象、简化、确定变量和参数，并应用某些规律建立变量与参数间的关系的数学问题(或称一个数学模型)，再借用计算机求解该数学问题，并解释、检验、评价所得的解，从而确定能否将其用于解决实际问题的多次循环、不断深化的过程。 二、数学建模的特点 从1985年开始美国都会举办一年一度的数学建模竞赛(MathematicalContestinModeling，缩写：MCM)，而我国自1992年举办首届全国大学生数学建模竞赛以来，它已经成为全国大学生科技竞赛的重要项目之一，全国大学生数学建模竞赛是面向全国大学生的群众性科技活动；竞赛要求学生(可以是任何专业)以三人为一组参加竞赛，可以自由的收集信息、调查研究，包括使用计算机和任何软件，甚至上网查询，但不得与团队以外的任何人讨论，在三天时间内，完成一篇包括模型的假设、建立、求解，计算方法的设计和用计算机对解的实现，以及结果的分析和检验，模型的改进等方面的论文。这一活动对于提高大学生素质，促进高校数学与计算机教学改革都起着积极的推动作用。 多年来，一年一度的全国大学生数学建模竞赛和国际大学生数学建模竞赛，给传统的高等数学教育改革带来了新的思路和评价标准，《数学建模》课也从仅仅为参赛队员培训，扩展为一门比较普及的选修课，同时，《数学试验》作为一门新的课程也应运而生。数学建模与数学试验教学的重点是高等与现代数学的深层应用和面向问题的设计，而不是经典理论的深入研讨和系统论证。数学建模问题绝大部分来自一些具体的科研课题或实际工程问题，而不同于普通的数学习题或竞赛题。数学建模问题的特点是：面向现实生活的应用，有相关的科研背景，综合性强，涉及面广，因素关系复杂，缺乏足够的规范性，难以套用传统成熟的解决手段，数据量庞大，可采取的算法也比较复杂，结果具有一定的弹性空间，需要一定的伴随条件，许多问题得到的只能是近似解。 另一方面，建模问题不同于理论研究，它重在对实际问题的处理，而不是深层次纯粹数学理论或者世界难题。所以，求解建模问题大都借助各种辅助工具或手段，尤其是计算机软件的应用，大大地提高了解题效率和质量。总之,《数学建模》是一门技术应用的课程，而不是基础教育课程，它强调的是如何更好更快地解决问题，如何充分利用各种科技手段作为技术支持，因而计算机的应用已经成为其不可或缺的一项基本组成。与此相关的计算机技术主要有两部分：一是如何将实际问题或模型转化或表述为可用计算机软件或编程实现的算法；二是采用哪些应用软件或编程技术可以解决这些问题。显然，后者是前者的基础，确定了工具方案，才有相应的解决方案。 由于数学建模的以上特点，决定了数学建模与计算机具有密切相关的联系，计算机在数学建模思想意识培养中发挥了重要的作用，主要是提供了有力工具和技术支持，它是更好更
1. 什么是数学模型与数学建模 简单地说：数学模型就是对实际问题的一种数学表述。 具体一点说：数学模型是关于部分现实世界为某种目的的一个抽象的简化的数学结构。 更确切地说：数学模型就是对于一个特定的对象为了一个特定目标，根据特有的内在规律，做出一些必要的简化假设，运用适当的数学工具，得到的一个数学结构。数学结构可以是数学公式，算法、表格、图示等。 数学建模就是建立数学模型，建立数学模型的过程就是数学建模的过程（见数学建模过程流程图）。数学建模是一种数学的思考方法，是运用数学的语言和方法，通过抽象、简化建立能近似刻划并"解决"实际问题的一种强有力的数学手段。 2.美国大学生数学建模竞赛的由来： 1985年在美国出现了一种叫做MCM的一年一度大大学生数学模型（1987年全称为Mathematical Competition in Modeling,1988年改全称为Mathematical Contest in Modeling,其所写均为MCM）。这并不是偶然的。在1985年以前美国只有一种大学生数学竞赛（The william Lowell Putnam mathematial Competition,简称Putman(普特南）数学竞赛），这是由美国数学协会（MAA--即Mathematical Association of America的缩写）主持，于每年12月的第一个星期六分两试进行，每年一次。在国际上产生很大影响，现已成为国际性的大学生的一项著名赛事。该竞赛每年2月或3月进行。 我国自1989年首次参加这一竞赛，历届均取得优异成绩。经过数年参加美国赛表明，中国大学生在数学建模方面是有竞争力和创新联想能力的。为使这一赛事更广泛地展开，1990年先由中国工业与应用数学学会后与国家教委联合主办全国大学生数学建模竞赛（简称CMCM），该项赛事每年9月进行。
数学建模常用的十大算法==转 (2011-07-24 16:13:14) 转载▼ 1. 蒙特卡罗算法。该算法又称随机性模拟算法，是通过计算机仿真来解决问题的算法，同时可以通过模拟来检验自己模型的正确性，几乎是比赛时必用的方法。 2. 数据拟合、参数估计、插值等数据处理算法。比赛中通常会遇到大量的数据需要处理，而处理数据的关键就在于这些算法，通常使用MA TLAB 作为工具。 3. 线性规划、整数规划、多元规划、二次规划等规划类算法。建模竞赛大多数问题属于最优化问题，很多时候这些问题可以用数学规划算法来描述，通常使用Lindo、Lingo 软件求解。 4. 图论算法。这类算法可以分为很多种，包括最短路、网络流、二分图等算法，涉及到图论的问题可以用这些方法解决，需要认真准备。 5. 动态规划、回溯搜索、分治算法、分支定界等计算机算法。这些算法是算法设计中比较常用的方法，竞赛中很多场合会用到。 6. 最优化理论的三大非经典算法：模拟退火算法、神经网络算法、遗传算法。这些问题是用来解决一些较困难的最优化问题的，对于有些问题非常有帮助，但是算法的实现比较困难，需慎重使用。 7. 网格算法和穷举法。两者都是暴力搜索最优点的算法，在很多竞赛题中有应用，当重点讨论模型本身而轻视算法的时候，可以使用这种暴力方案，最好使用一些高级语言作为编程工具。 8. 一些连续数据离散化方法。很多问题都是实际来的，数据可以是连续的，而计算机只能处理离散的数据，因此将其离散化后进行差分代替微分、求和代替积分等思想是非常重要的。 9. 数值分析算法。如果在比赛中采用高级语言进行编程的话，那些数值分析中常用的算法比如方程组求解、矩阵运算、函数积分等算法就需要额外编写库函数进行调用。 10. 图象处理算法。赛题中有一类问题与图形有关，即使问题与图形无关，论文中也会需要图片来说明问题，这些图形如何展示以及如何处理就是需要解决的问题，通常使用MA TLAB 进行处理。 以下将结合历年的竞赛题，对这十类算法进行详细地说明。 以下将结合历年的竞赛题，对这十类算法进行详细地说明。 2 十类算法的详细说明 2.1 蒙特卡罗算法 大多数建模赛题中都离不开计算机仿真，随机性模拟是非常常见的算法之一。 举个例子就是97 年的A 题，每个零件都有自己的标定值，也都有自己的容差等级，而求解最优的组合方案将要面对着的是一个极其复杂的公式和108 种容差选取方案，根本不可能去求解析解，那如何去找到最优的方案呢？随机性模拟搜索最优方案就是其中的一种方法，在每个零件可行的区间中按照正态分布随机的选取一个标定值和选取一个容差值作为一种方案，然后通过蒙特卡罗算法仿真出大量的方案，从中选取一个最佳的。另一个例子就是去年的彩票第二问，要求设计一种更好的方案，首先方案的优劣取决于很多复杂的因素，同样不可能刻画出一个模型进行求解，只能靠随机仿真模拟。 2.2 数据拟合、参数估计、插值等算法 数据拟合在很多赛题中有应用，与图形处理有关的问题很多与拟合有关系，一个例子就是98 年美国赛A 题，生物组织切片的三维插值处理，94 年A 题逢山开路，山体海拔高度的插值计算，还有吵的沸沸扬扬可能会考的“非典”问题也要用到数据拟合算法，观察数据的
数学建模常用方法 建模常用算法,仅供参考： 1、蒙特卡罗算法（该算法又称随机性模拟算法,是通过计算机仿真来解决问题的算法,同时可以通过模拟可以来检验自己模型的正确性,是比赛时必 用的方法） 2、数据拟合、参数估计、插值等数据处理算法（比赛中通常会遇到大量的数据需要处理,而处理数据的关键就在于这些算法,通常使用M a t l a b作为工具） 3、线性规划、整数规划、多元规划、二次规划等规划类问题（建模竞赛大多数问题属于最优化问题,很多时候这些问题可以用数学规划算法来描述,通 常使用L i n d o、L i n g o软件实现） 4、图论算法（这类算法可以分为很多种,包括最短路、网络流、二分图等算法,涉及到图论的问题可以用这些方法解决,需要认真准备） 5、动态规划、回溯搜索、分治算法、分支定界等计算机算法（这些算法是算法设计中比较常用的方法,很多场合可以用到竞赛中） 6、最优化理论的三大非经典算法：模拟退火法、神经网络、遗传算法（这些问题是用来解决一些较困难的最优化问题的算法,对于有些问题非常有帮助,但是算法的实现比较困难,需慎重使用） 7、网格算法和穷举法（网格算法和穷举法都是暴力搜索最优点的算法,在很多竞赛题中有应用,当重点讨论模型本身而轻视算法的时候,可以使用这种 暴力方案,最好使用一些高级语言作为编程工具） 8、一些连续离散化方法（很多问题都是实际来的,数据可以是连续的,而计 算机只认的是离散的数据,因此将其离散化后进行差分代替微分、求和代替积分等思想是非常重要的） 9、数值分析算法（如果在比赛中采用高级语言进行编程的话,那一些数值分析中常用的算法比如方程组求解、矩阵运算、函数积分等算法就需要额外编写库函数进行调用） 10、图象处理算法（赛题中有一类问题与图形有关,即使与图形无关,论文 中也应该要不乏图片的,这些图形如何展示以及如何处理就是需要解决的问题,通常使用M a t l a b进行处理） 一、在数学建模中常用的方法： 1.类比法 2.二分法 3.量纲分析法 4.差分法 5.变分法 6.图论法 7.层次分析法 8.数据拟合法 9.回归分析法 10.数学规划（线性规划、非线性规划、整数规划、动态规划、目标规划） 11.机理分析 12.排队方法
数学建模的基本步骤 一、数学建模题目 1）以社会，经济，管理，环境，自然现象等现代科学中出现的新问题为背景，一般都有一个比较确切的现实问题。 2）给出若干假设条件： 1. 只有过程、规则等定性假设； 2. 给出若干实测或统计数据； 3. 给出若干参数或图形等。 根据问题要求给出问题的优化解决方案或预测结果等。根据问题要求题目一般可分为优化问题、统计问题或者二者结合的统计优化问题，优化问题一般需要对问题进行优化求解找出最优或近似最优方案，统计问题一般具有大量的数据需要处理，寻找一个好的处理方法非常重要。 二、建模思路方法 1、机理分析根据问题的要求、限制条件、规则假设建立规划模型，寻找合适的寻优算法进行求解或利用比例分析、代数方法、微分方程等分析方法从基本物理规律以及给出的资料数据来推导出变量之间函数关系。 2、数据分析法对大量的观测数据进行统计分析，寻求规律建立数学模型，采用的分析方法一般有： 1）. 回归分析法(数理统计方法)-用于对函数f（x）的一组观测值（xi,fi）i=1,2,…,n，确定函数的表达式。 2）. 时序分析法--处理的是动态的时间序列相关数据，又称为过程统计方法。 3）、多元统计分析（聚类分析、判别分析、因子分析、主成分分析、生存数据分析）。 3、计算机仿真（又称统计估计方法）：根据实际问题的要求由计算机产生随机变量对动态行为进行比较逼真的模仿，观察在某种规则限制下的仿真结果（如蒙特卡罗模拟）。 三、模型求解： 模型建好了，模型的求解也是一个重要的方面，一个好的求解算法与一个合
适的求解软件的选择至关重要，常用求解软件有matlab，mathematica，lingo，lindo，spss，sas等数学软件以及c/c++等编程工具。 Lingo、lindo一般用于优化问题的求解，spss，sas一般用于统计问题的求解，matlab，mathematica功能较为综合，分别擅长数值运算与符号运算。 常用算法有：数据拟合、参数估计、插值等数据处理算法,通常使用spss、sas、Matlab作为工具. 线性规划、整数规划、多元规划、二次规划、动态规划等通常使用Lindo、Lingo,Matlab软件。 图论算法,、回溯搜索、分治算法、分支定界等计算机算法, 模拟退火法、神经网络、遗传算法。 四、自学能力和查找资料文献的能力： 建模过程中资料的查找也具有相当重要的作用，在现行方案不令人满意或难以进展时，一个合适的资料往往会令人豁然开朗。常用文献资料查找中文网站：CNKI、VIP、万方。 五、论文结构： 0、摘要 1、问题的重述，背景分析 2、问题的分析 3、模型的假设，符号说明 4、模型的建立（局部问题分析，公式推导，基本模型，最终模型等） 5、模型的求解 6、模型检验:模型的结果分析与检验，误差分析 7、模型评价:优缺点，模型的推广与改进 8、参考文献 9、附录 六、需要重视的问题 数学建模的所有工作最终都要通过论文来体现，因此论文的写法至关重要：
第1节数学建模与数学探究 【内容要求】 数学建模活动是对现实问题进行数学抽象，用数学语言表达问题、用数学方法构建模型解决问题的过程.主要包括：在实际情境中从数学的视角发现问题、提出问题，分析问题、构建模型，确定参数、计算求解，检验结果、改进模型，最终解决实际问题.数学建模活动是基于数学思维运用模型解决实际问题的一类综合实践活动，是高中阶段数学课程的重要内容. 【基本过程】 数学建模活动的基本过程如下： 数学探究活动是围绕某个具体的数学问题，开展自主探究、合作研究并最终解决问题的过程.具体表现为：发现和提出有意义的数学问题，猜测合理的数学结论，提出解决问题的思路和方案，通过自主探索、合作研究论证数学结论.数学探究活动是运用数学知识解决数学问题的一类综合实践活动，也是高中阶段数学课程的重要内容. 【过程解读】 掌握建模基本过程，会对实际问题进行问题分析，善于合理假设. ·问题分析也常称为模型准备或问题重述.由于数学模型是建立数学与实际现象之
间的桥梁，因此，首要的工作是要设法用数学的语言表述实际现象.所谓问题重述是指把实际现象尽量地使用贴近数学的语言进行重新描述.为此，要充分了解问题的实际背景，明确建模的目的，尽可能弄清对象的特征，并为此搜集必需的各种信息或数据.要善于捕捉对象特征中隐含的数学因素，并将其一一列出.至此，我们便有了一个很好的开端，而有了这个良好的开端，不仅可以决定建模方向，初步确定用哪一类模型，而且对下面的各个步骤都将产生影响. ·模型假设(即合理假设)是与问题分析紧密衔接的又一个重要步骤.根据对象的特征和建模目的，在问题分析基础上对问题进行必要的、合理的取舍简化，并使用精确的语言作出假设，这是建模至关重要的一步.这是因为，一个实际问题往往是复杂多变的，如不经过合理的简化假设，将很难于转化成数学模型，即便转化成功，也可能是一个复杂的难于求解的模型从而使建模归于失败.当然，假设作得不合理或过分简单也同样会因为与实际相去甚远而使建模归于失败.一般地，作出假设时要充分利用与问题相关的有关学科知识，充分发挥想象力和观察判断力，分清问题的主次，抓住主要因素，舍弃次要因素. 【实际意义】 数学建模的实际意义 1.在一般工程技术领域，数学建模仍然大有用武之地. 在以声、光、热、力、电这些物理学科为基础的诸如机械、电机、土木、水利等工程技术领域中，数学建模的普遍性和重要性不言而喻，虽然这里的基本模型是已有的，但是由于新技术、新工艺的不断涌现，提出了许多需要用数学方法解决的新问题；高速、大型计算机的飞速发展，使得过去即便有了数学模型也无法求解的课题(如大型水坝的应力计算，中长期天气预报等)迎刃而解；建立在数学模型和计算机模拟基础上的CAD技术，以其快速、经济、方便等优势，大量地替代了传统工程设计中的现场实验、物理模拟等手段. 2.在高新技术领域，数学建模几乎是必不可少的工具. 无论是发展通讯、航天、微电子、自动化等高新技术本身，还是将高新技术用于传统工业去创造新工艺、开发新产品，计算机技术支持下的建模和模拟都是经常使用的有效手段.数学建模、数值计算和计算机图形等相结合形成的计算机软件，已经被固化于产品中，在许多高新技术领域起着核心作用，被认为是高新技术的特征之一.
数学建模有下面十种常用算法, 可供参考： 1.蒙特卡罗算法（该算法又称随机性模拟算法，是通过计算机仿真来解决问 题的算法，同时可以通过模拟可以来检验自己模型的正确性，是比赛时必用的方法） 2.数据拟合、参数估计、插值等数据处理算法（比赛中通常会遇到大量的数 据需要处理，而处理数据的关键就在于这些算法，通常使用Matlab作为工具） 3.线性规划、整数规划、多元规划、二次规划等规划类问题（建模竞赛大多 数问题属于最优化问题，很多时候这些问题可以用数学规划算法来描述，通常使用Lindo、Lingo软件实现） 4.图论算法（这类算法可以分为很多种，包括最短路、网络流、二分图等算 法，涉及到图论的问题可以用这些方法解决，需要认真准备） 5.动态规划、回溯搜索、分治算法、分支定界等计算机算法（这些算法是算 法设计中比较常用的方法，很多场合可以用到竞赛中） 6.最优化理论的三大非经典算法：模拟退火法、神经网络、遗传算法（这些 问题是用来解决一些较困难的最优化问题的算法，对于有些问题非常有帮助，但是算法的实现比较困难，需慎重使用） 7.网格算法和穷举法（网格算法和穷举法都是暴力搜索最优点的算法，在很 多竞赛题中有应用，当重点讨论模型本身而轻视算法的时候，可以使用这种暴力方案，最好使用一些高级语言作为编程工具） 8.一些连续离散化方法（很多问题都是实际来的，数据可以是连续的，而计 算机只认的是离散的数据，因此将其离散化后进行差分代替微分、求和代替积分等思想是非常重要的） 9.数值分析算法（如果在比赛中采用高级语言进行编程的话，那一些数值分 析中常用的算法比如方程组求解、矩阵运算、函数积分等算法就需要额外编写库函数进行调用） 10.图象处理算法（赛题中有一类问题与图形有关，即使与图形无关，论文中 也应该要不乏图片的，这些图形如何展示以及如何处理就是需要解决的问题，通常使用Matlab 进行处理）
数学建模参赛真实经验（强烈推荐） 本文档节选自： Matlab在数学建模中的应用，卓金武等编著，北航出版社，2011年4月出版 以下内容根据作者的讲座整理出来，多年数学建模实践经历证明这些经验对数学建模参赛队员非常有帮助，希望大家结合自己的实践慢慢体会总结，并祝愿大家在数学建模和Matlab世界能够找到自己的快乐和价值所在。 一、如何准备数学建模竞赛 一般，可以把参加数学建模竞赛的过程分成三个阶段：第一阶段，是个人的入门和积累阶段，这个阶段关键看个人的主观能动性；第二阶段，就是通常各学校都进行的集训阶段，通过模拟实战来提高参赛队员的水平；第三阶段是实际比赛阶段。这里讲的如何准备数学建模竞赛是针对第一阶段来讲的。 回顾作者自己的参赛过程，认为这个阶段是真正的学习阶段，就像是修炼内功一样，如果在这个阶段打下深厚的基础，对后面的两个阶段非常有利，也是个人是否能在建模竞赛中占优势的关键阶段。下面就分几个方面谈一下如何准备数学建模竞赛。 首先是要有一定的数学基础，尤其是良好的数学思维能力。并不是数学分数高就说明有很高的数学思维能力，但扎实的数学知识是数学思维的根基。对大学生来说，有高等数学、概率和线性代数就够了，当然其它数学知识知道的越多越好了，如图论、排队论、泛函等。我大一下学期开始接触数学建模，大学的数学课程只学习过高等数学。说这一点，主要想说明只要数学基础还可以，平时的数学考试都能在80分以上就可以参加数学建模竞赛了，数学方面的知识可以在以后的学习中逐渐去提高，不必刻意去补充单纯的数学理论。 真正准备数学建模竞赛应该从看数学建模书籍开始，要知道什么是数学建模，有哪些常见的数学模型和建模方法，知道一些常见的数学建模案例，这些方面都要通过看建模方面的书籍而获得。现在数学建模的书籍也比较多，图书馆和互联网上都有丰富的数学建模资料。作者认为姜启源、谢金星、叶齐孝、朱道元等老师的建模书籍都非常的棒，可以先看二三本。刚开始看数学建模书籍时，一定会有很多地方看不懂，但要知道基本思路，时间长了就知道什么问题用什么建模方法求解了。这里面需要提的一点是，运筹学与数学建模息息相关，最好再看一二本运筹学著作，仍然可以采取诸葛亮的看书策略，只观其大略就可以了，等知道需要具体用哪块知识后，再集中精力将其消化，然后应用之。 大家都知道，参加数学建模竞赛一定要有些编程功底，当然现在有Matlab这种强大的工程软件，对编程的的要求就降低了，至少入门容易多了，因为很容易用1条Matlab命令解决以前要用20行C语言才能实现的功能。因为Matlab的强大功能，Matlab在数学建模中已经有了非常广泛的应用，在很多学校，数学建模队员必须学习Matlab。当然Matlab的入门也非常容易，只要有本Matlab参考书，照猫画虎可以很快实现一些基本的数学建模功能，如数据处理、绘图、计算等。我的一个队友，当年用一天时间把一本二百多页的Matlab 教程操作完了，然后在经常运用中，慢慢地就变成了一名Matlab高手了。 对于有些编程基础的同学，最好再看一些算法方面的书籍，了解常见的数据结构和基本
第1章数学建模与误差分析 1.1 数学与科学计算 数学是科学之母，科学技术离不开数学，它通过建立数学模型与数学产生紧密联系，数学又以各种形式应用于科学技术各领域。数学擅长处理各种复杂的依赖关系，精细刻画量的变化以及可能性的评估。它可以帮助人们探讨原因、量化过程、控制风险、优化管理、合理预测。近几十年来由于计算机及科学技术的快速发展，求解各种数学问题的数值方法即计算数学也越来越多地应用于科学技术各领域，相关交叉学科分支纷纷兴起，如计算力学、计算物理、计算化学、计算生物、计算经济学等。 科学计算是指利用计算机来完成科学研究和工程技术中提出的数学问题的计算，是一种使用计算机解释和预测实验中难以验证的、复杂现象的方法。科学计算是伴随着电子计算机的出现而迅速发展并获得广泛应用的新兴交叉学科，是数学及计算机应用于高科技领域的必不可少的纽带和工具。科学计算涉及数学的各分支，研究它们适合于计算机编程的数值计算方法是计算数学的任务，它是各种计算性学科的联系纽带和共性基础，兼有基础性和应用性的数学学科。它面向的是数学问题本身而不是具体的物理模型，但它又是各计算学科共同的基础。 随着计算机技术的飞速发展，科学计算在工程技术中发挥着愈来愈大的作用,已成为继科学实验和理论研究之后科学研究的第三种方法。在实际应用中所建立的数学模型其完备形式往往不能方便地求出精确解，于是只能转化为简化模型，如将复杂的非线性模型忽略一些因素而简化为线性模型，但这样做往往不能满足精度要求。因此，目前使用数值方法来直接求解较少简化的模型，可以得到满足精度要求的结果，使科学计算发挥更大作用。了解和掌握科学计算的基本方法、数学建模方法已成为科技人才必需的技能。因此，科学计算与数学建模的基本知识和方法是工程技术人才必备的数学素质。 1.2 数学建模及其重要意义 数学，作为一门研究现实世界数量关系和空间形式的科学，在它产生和发展的历史长河中，一直是和人们生活的实际需要密切相关。用数学方法解决工程实际和科学技术中的具体问题时，首先必须将具体问题抽象为数学问题，即建立起能描述并等价代替该实际问题的数学模型，然后将建立起的数学模型，利用数学理论和计算技术进行推演、论证和计算，得到欲求解问题的解析解或数值解，最后用求得的解析解和数值解来解决实际问题。本章主要介绍数学建模基本过程和求解数学问题数值方法的误差传播分析。 1.2.1 数学建模的过程 数学建模过程就是从现实对象到数学模型，再从数学模型回到现实对象的循环，一般通过表述、求解、解释、验证几个阶段完成。数学建模过程如图1.2.1所示，数学模型求解方法可分为解析法和数值方法，如图1.2.2所示。 表述是将现实问题“翻译”成抽象的数学问题，属于归纳。数学模型的求解方法则属于演绎。归纳是依据个别现象推出一般规律；演绎是按照普遍原理考察特定对象，导出结论。演绎利用严格的逻辑推理，对解释现象做出科学预见，具有重要意义，但是它要以归纳的结论作为公理化形式的前提，只有在这个前提下
数学建模方法详解--三种最常用算法 一、层次分析法 层次分析法[1] (analytic hierarchy process，AHP)是美国著名的运筹学家T．L．Saaty教授于20世纪70年代初首先提出的一种定性与定量分析相结合的多准则决策方法[2，3，4]．该方法是社会、经济系统决策的有效工具，目前在工程计划、资源分配、方案 排序、政策制定、冲突问题、性能评价等方面都有广泛的应用． (一) 层次分析法的基本原理 层次分析法的核心问题是排序，包括递阶层次结构原理、测度原理和排序原理[5]．下面分别予以介绍． 1．递阶层次结构原理 一个复杂的结构问题可以分解为它的组成部分或因素，即目标、准则、方案等．每一个因素称为元素．按照属性的不同把这 些元素分组形成互不相交的层次，上一层的元素对相邻的下一层的全部或部分元素起支配作用，形成按层次自上而下的逐层支配 关系．具有这种性质的层次称为递阶层次． 2．测度原理 决策就是要从一组已知的方案中选择理想方案，而理想方案一般是在一定的准则下通过使效用函数极大化而产生的．然而对 于社会、经济系统的决策模型来说，常常难以定量测度．因此，层次分析法的核心是决策模型中各因素的测度化．3．排序原理
层次分析法的排序问题，实质上是一组元素两两比较其重要性，计算元素相对重要性的测度问题．(二) 层次分析法的基本步骤 层次分析法的基本思路与人对一个复杂的决策问题的思维、判断过程大体上是一致的[1] ． 1．成对比较矩阵和权向量 为了能够尽可能地减少性质不同的诸因素相互比较的困难，提高结果的准确度．T ．L ．Saaty 等人的作法，一是不把所有因 素放在一起比较，而是两两相互对比，二是对比时采用相对尺度． 假设要比较某一层n 个因素n C C ,,1对上层一个因素O 的影响，每次取两个因素i C 和j C ，用ij a 表示i C 和j C 对O 的影响之比， 全部比较 结 果 可 用 成 对 比 较 阵 1 ,0,ij ij ji n n ij A a a a a 表示，A 称为正互反矩阵．一般地，如果一个正互反阵 A 满足： , ij jk ik a a a ,,1,2,,i j k n （1） 则A 称为一致性矩阵，简称一致阵．容易证明n 阶一致阵A 有下列性质： ①A 的秩为1，A 的唯一非零特征根为n ；②A 的任一列向量都是对应于特征根 n 的特征向量． 如果得到的成对比较阵是一致阵，自然应取对应于特征根n 的、归一化的特征向量（即分量之和为1）表示诸因素n C C ,, 1对 上层因素O 的权重，这个向量称为权向量．如果成对比较阵A 不是一致阵，但在不一致的容许范围内，用对应于A 最大特征根(记
数学建模背景： 数学技术 近半个多世纪以来，随着计算机技术的迅速发展，数学的应用不仅在工程技术、自然科学等领域发挥着越来越重要的作用，而且以空前的广度和深度向经济、管理、金融、生物、医学、环境、地质、人口、交通等新的领域渗透，所谓数学技术已经成为当代高新技术的重要组成部分。 数学模型（Mathematical Model）是一种模拟，是用数学符号、数学式子、程序、图形等对实际课题本质属性的抽象而又简洁的刻划，它或能解释某些客观现象，或能预测未来的发展规律，或能为控制某一现象的发展提供某种意义下的最优策略或较好策略。数学模型一般并非现实问题的直接翻版，它的建立常常既需要人们对现实问题深入细微的观察和分析，又需要人们灵活巧妙地利用各种数学知识。这种应用知识从实际课题中抽象、提炼出数学模型的过程就称为数学建模（Mathematical Modeling）。[1] 不论是用数学方法在科技和生产领域解决哪类实际问题，还是与其它学科相结合形成交叉学科，首要的和关键的一步是建立研究对象的数学模型，并加以计算求解（通常借助计算机）。数学建模和计算机技术在知识经济时代的作用可谓是如虎添翼。 建模应用 数学是研究现实世界数量关系和空间形式的科学，在它产生和发展的历史长河中，一直是和各种各样的应用问题紧密相关的。数学的特点不仅在于概念的抽象性、逻辑的严密性，结论的明确性和体系的完整性，而且在于它应用的广泛性，自从20世纪以来，随着科学技术的迅速发展和计算机的日益普及，人们对各种问题的要求越来越精确，使得数学的应用越来越广泛和深入，特别是在21世纪这个知识经济时代，数学科学的地位会发生巨大的变化，它正在从国家经济和科技的后备走到了前沿。经济发展的全球化、计算机的迅猛发展，数理论与方法的不断扩充使得数学已经成为当代高科技的一个重要组成部分和思想库，数学已经成为一种能够普遍实施的技术。培养学生应用数学的意识和能力已经成为数学教学的一个重要方面。 2建模过程 模型准备 了解问题的实际背景，明确其实际意义，掌握对象的各种信息。以数学思想来包容问题的精髓，数学思路贯穿问题的全过程，进而用数学语言来描述问题。要求符合数学理论，符合数学习惯，清晰准确。 模型假设 根据实际对象的特征和建模的目的，对问题进行必要的简化，并用精确的语言提出一些恰当的假设。 模型建立 在假设的基础上，利用适当的数学工具来刻划各变量常量之间的数学关系，建立相应的数学结构（尽量用简单的数学工具）。 模型求解 利用获取的数据资料，对模型的所有参数做出计算（或近似计算）。 模型分析 对所要建立模型的思路进行阐述，对所得的结果进行数学上的分析。 模型检验 将模型分析结果与实际情形进行比较，以此来验证模型的准确性、合理性和适用性。如果模型与实际较吻合，则要对计算结果给出其实际含义，并进行解释。如果模型与实际吻合较差，则应该修改假设，再次重复建模过程。
数学建模竞赛中应当掌握的十类算法 排名如下： 1、蒙特卡罗算法（该算法又称随机性模拟算法，是通过计算机仿真来解决问题的算法，同时可以通过模拟可以来检验自己模型的正确性，是比赛时必用的方法） 2、数据拟合、参数估计、插值等数据处理算法（比赛中通常会遇到大量的数据需要处理，而处理数据的关键就在于这些算法，通常使用Matlab作为工具） 3、线性规划、整数规划、多元规划、二次规划等规划类问题（建模竞赛大多数问题属于最优化问题，很多时候这些问题可以用数学规划算法来描述，通常使用Lindo、Lingo软件实现） 4、图论算法（这类算法可以分为很多种，包括最短路、网络流、二分图等算法，涉及到图论的问题可以用这些方法解决，需要认真准备） 5、动态规划、回溯搜索、分治算法、分支定界等计算机算法（这些算法是算法设计中比较常用的方法，很多场合可以用到竞赛中） 6、最优化理论的三大非经典算法：模拟退火法、神经网络、遗传算法（这些问题是用来解决一些较困难的最优化问题的算法，对于有些问题非常有帮助，但是算法的实现比较困难，需慎重使用） 7、网格算法和穷举法（网格算法和穷举法都是暴力搜索最优点的算法，在很多竞赛题中有应用，当重点讨论模型本身而轻视算法的时候，可以使用这种暴力方案，最好使用一些高级语言作为编程工具） 8、一些连续离散化方法（很多问题都是实际来的，数据可以是连续的，而计算机只认的是离散的数据，因此将其离散化后进行差分代替微分、求和代替积分等思想是非常重要的） 9、数值分析算法（如果在比赛中采用高级语言进行编程的话，那一些数值分析中常用的算法比如方程组求解、矩阵运算、函数积分等算法就需要额外编写库函数进行调用） 10、图象处理算法（赛题中有一类问题与图形有关，即使与图形无关，论文中也应该要不乏图片的，这些图形如何展示以及如何处理就是需要解决的问题，通常使用Matlab进行处理） 8.1 遗传算法的概念 是建立在自然选择和自然遗传学机理基础上的迭代自适应概率性搜索算法，在1975年由Holland教授提出。 生物的进化是一个奇妙的优化过程，它通过选择淘汰，突然变异，基因遗传等规律产生适应环境变化的优良物种。遗传算法是根据生物进化思想而启发得出的一种全局优化算法。 遗传算法的概念最早是由Bagley J.D在1967年提出的；而开始遗传算法的理论和方法的系统性研究的是1975年，这一开创性工作是由Michigan大学的 J.H.Holland所实行。当时，其主要目的是说明自然和人工系统的自适应过程。
摘要 本文研究的是联想、惠普、东芝、戴尔、索尼、华硕、苹果、神州、ACER等主要厂家产品的价格与公司知名度、产品主要配置、大众消费倾向、产品附加值的定量关系。 首先，本文在对笔记本配置，大众消费倾向，附加值等因素进行详细深入的比较的基础上，制定了适应于所有笔记本的各影响因素的标度标准，并在该标准的前提下，统计了九大电脑公司、受关注较高的各个系列（每个品牌取六大不同系列，每个系列各取一台）的电脑的价格、配置、产品附加值等大量数据，并用均值法得到了一组具有代表性的数据。基于数据分析，借鉴层次分析法建立了模型，并且在建立模型的过程中采用了九级标度法，将对价格影响的各因素定量化，并在此基础上列出判断矩阵。 然后，求判断矩阵的相对权重。通过资料得到了三种不同的求权重方法，分别为和法、根法、特征根法。本文采取的是特特征根法。利用MATLAB软件，算出了判断矩阵的最大特征值，并将与之对应的特征向量归一化，得到相应元素对应的权重，并进行一致性检验。 最后，利用公式算出组合权重，组合一致性指标，便得出各因素对公司定价的影响程度，分析得出结论。 关键词：制定标准均值法借鉴层次分析法九级标度法判断矩阵特征根法一致性检验
目录 1.问题重述与分析………………4-5 1.1问题重述 (4) 1.2 问题分析 (5) 2.符号说明 (6) 3.数据说明……………………….. 6-7 4.主要电脑厂家产品的价格与公司知名度，产品主要配置，大众消费倾向，产品附加值等的定量关系研究——借鉴层次分析法…………………………………. 7-38 4.1 模型建立………………………7-14 4.2 模型求解……………………14-38 4.2.1 构造求解判断矩阵....... 14-32 4.2.2 一致性检验………………. 32-38 5.比较分析各厂家产品定价的优越…38-39 6.根据结论，提出建议………. 39-42 7.模型的总结与改进…………. 42-43 7.1 模型总结 (42) 7.2 模型改进 (43)