下载文档原格式
数学建模第二讲简单的优化模型数学建模是利用数学方法对实际问题进行建模、分析和求解的过程。
在实际问题中，常常需要针对一些指标进行优化，以达到最优的效果。
本讲将介绍一些简单的优化模型。
一、线性规划模型线性规划是一种重要的数学优化方法，广泛应用于工程、经济、管理等领域。
其数学模型可以表示为：\begin{aligned}&\text{max} \quad c^Tx \\&\text{s.t.} \quad Ax \leq b, \quad x \geq 0\end{aligned}\]其中，$x$为决策变量，$c$为目标函数系数，$A$为约束条件系数矩阵，$b$为约束条件右端向量。
线性规划模型指的是目标函数和约束条件都是线性的情况。
通过线性规划模型，可以求解出使得目标函数取得最大（或最小）值时的决策变量取值。
二、非线性规划模型非线性规划模型指的是目标函数或约束条件中存在非线性部分的情况。
非线性规划模型相对于线性规划模型更为复杂，但在实际问题中更为常见。
对于非线性规划问题，通常采用数值优化方法进行求解，如梯度下降法、牛顿法等。
这些方法通过迭代的方式逐步靠近最优解。
三、整数规划模型整数规划模型是指决策变量必须为整数的规划模型。
整数规划在实际问题中应用广泛，如物流配送问题、工程调度问题等。
整数规划模型通常难以求解，因为整数规划问题是一个NP难问题。
针对整数规划问题，常用的求解方法有枚举法、分支定界法、遗传算法等。
四、动态规划模型动态规划模型是指将问题划分为子问题，并通过求解子问题最优解来求解原问题最优解的方法。
动态规划通常用于求解具有重叠子问题和最优子结构性质的问题。
动态规划模型具有递推性质，通过递归或迭代的方式求解子问题的最优解，并保存中间结果，以提高求解效率。
五、模拟退火模型模拟退火是一种用来求解组合优化问题的随机优化算法。
模拟退火算法基于固体退火过程的模拟，通过温度的控制和随机跳出来避免陷入局部最优解。
遗传算法的基本结构一、引言遗传算法是一种模拟自然进化过程的优化算法，被广泛应用于求解复杂问题。
本文将介绍遗传算法的基本结构。
二、遗传算法的基本概念1.个体：表示问题的一个解，也称为染色体。
2.种群：由多个个体组成的集合。
3.适应度函数：用于评价个体的优劣程度。
4.选择操作：根据适应度函数选择优秀的个体。
5.交叉操作：将两个个体进行配对，并通过交叉操作产生新的个体。
6.变异操作：对某些个体进行随机变异，以增加种群的多样性。
三、遗传算法流程1.初始化种群：随机生成一定数量的初始解作为种群。
2.计算适应度函数：对每一个个体计算其适应度值。
3.选择操作：根据适应度函数选择优秀的个体作为下一代种群。
4.交叉操作：对选出来的优秀个体进行配对，并通过交叉操作产生新的个体加入下一代种群。
5.变异操作：对某些选出来的优秀个体进行随机变异，以增加下一代种群的多样性。
6.重复步骤2-5，直到满足终止条件（如达到最大迭代次数或找到最优解）。
四、遗传算法的优点1.能够在大规模搜索空间中寻找全局最优解。
2.对于复杂问题，遗传算法比其他优化算法更具有鲁棒性。
3.易于实现和理解，不需要对问题进行过多的数学建模。
五、遗传算法的应用1.组合优化问题：如旅行商问题、背包问题等。
2.函数优化问题：如函数极值求解等。
3.机器学习中的特征选择和参数调整等。
六、总结遗传算法是一种基于自然进化过程的优化算法，具有广泛的应用前景。
本文介绍了遗传算法的基本概念、流程、优点和应用，并希望能够为读者提供一些参考和启示。
数学建模常用算法和模型全集数学建模是一种将现实世界的问题转化为数学问题，并通过建立数学模型来求解的方法。
在数学建模中，常常会用到各种算法和模型，下面是一些常用的算法和模型的全集。
一、算法1.线性规划算法：用于求解线性规划问题，例如单纯形法、内点法等。
2.非线性规划算法：用于求解非线性规划问题，例如牛顿法、梯度下降法等。
3.整数规划算法：用于求解整数规划问题，例如分支定界法、割平面法等。
4.动态规划算法：用于求解具有最优子结构性质的问题，例如背包问题、最短路径问题等。
5.遗传算法：模拟生物进化过程，用于求解优化问题，例如遗传算法、粒子群算法等。
6.蚁群算法：模拟蚂蚁寻找食物的行为，用于求解优化问题，例如蚁群算法、人工鱼群算法等。
7.模拟退火算法：模拟固体退火过程，用于求解优化问题，例如模拟退火算法、蒙特卡罗模拟等。
8.蒙特卡罗算法：通过随机抽样的方法求解问题，例如蒙特卡罗模拟、马尔科夫链蒙特卡罗等。
9.人工神经网络：模拟人脑神经元的工作原理，用于模式识别和函数逼近等问题，例如感知机、多层感知机等。
10.支持向量机：用于分类和回归问题，通过构造最大间隔超平面实现分类或回归的算法，例如支持向量机、核函数方法等。
二、模型1.线性模型：假设模型的输出与输入之间是线性关系，例如线性回归模型、线性分类模型等。
2.非线性模型：假设模型的输出与输入之间是非线性关系，例如多项式回归模型、神经网络模型等。
3.高斯模型：假设模型的输出服从高斯分布，例如线性回归模型、高斯朴素贝叶斯模型等。
4.时间序列模型：用于对时间序列数据进行建模和预测，例如AR模型、MA模型、ARMA模型等。
5.最优化模型：用于求解优化问题，例如线性规划模型、整数规划模型等。
6.图论模型：用于处理图结构数据的问题，例如最短路径模型、旅行商问题模型等。
7.神经网络模型：用于模式识别和函数逼近等问题，例如感知机模型、多层感知机模型等。
8.隐马尔可夫模型：用于对具有隐藏状态的序列进行建模，例如语音识别、自然语言处理等。
优化方案数学导言在计算机科学和信息技术领域，优化方案数学是一个重要而且广泛应用的领域。
它是指通过数学建模和优化算法，在给定的约束条件下寻找最优解的一种方法。
这种方法可以应用于各种问题，包括调度问题、路径规划、网络优化等等。
本文将介绍优化方案数学的基本概念、常用的优化算法以及一些实际应用案例。
基本概念目标函数在优化问题中，目标函数是一个用来评估解的好坏的函数。
它通常由优化问题的具体目标决定，例如最小化成本、最大化利润等等。
目标函数的设计需要考虑问题的特点和要求，以及数学模型的建立。
约束条件约束条件是指限制解的取值范围的条件。
在优化问题中，约束条件可以是线性的、非线性的、等式约束或者不等式约束。
约束条件的设计需要考虑问题的特性以及问题的可行解空间。
优化算法优化算法是求解优化问题的关键。
常见的优化算法包括穷举法、贪心算法、动态规划、遗传算法等等。
这些算法的选择需要根据问题的复杂度、目标函数的性质、约束条件的特点来进行。
常用的优化算法穷举法穷举法是一种简单直观的优化算法。
它通过枚举所有可能的解，并计算它们的目标函数值，然后选取最优解作为最终结果。
穷举法的优点是简单易懂，但是在问题规模较大时会导致计算量的巨大增加。
贪心算法贪心算法是一种贪心思想导向的优化算法。
它通过每一步选择当前最优解，以期望最终能得到整体的最优解。
贪心算法的优点是计算效率高，但是不一定能得到全局最优解，可能会陷入局部最优解。
动态规划动态规划是一种基于最优子结构和重叠子问题的优化算法。
它将问题分解成多个子问题，并通过寻找子问题之间的递推关系来求解最优解。
动态规划的优点是能够得到全局最优解，但是需要用额外的空间来存储中间结果。
遗传算法遗传算法是一种模拟生物进化的优化算法。
它通过模拟自然选择、交叉和变异等遗传操作，来不断优化解的质量。
遗传算法的优点是适应性强，能够在较短的时间内找到较好的解，但是需要设置合适的参数和操作。
实际应用案例任务调度问题任务调度是一个经典的优化问题。
运用数学模型优化旅游线路设计
一、最短路径算法
在旅游线路设计中，最短路径算法可以用于寻找旅游路线中的最短路径。
以图的方式
表示旅游路线，通过算法得到旅游者能够最短时间到达各个景点的路径，从而为旅游者提
供更高效的旅游体验。
该算法主要用于处理两点之间的最短路径问题。
二、线性规划算法
三、遗传算法
四、模拟退火算法
在进行旅游线路设计时，我们也需要注意以下几点：
1. 考虑旅游者的喜好和需求，量身定制旅游线路；
2. 合理安排旅游的时间和成本，避免浪费时间和金钱；
3. 考虑景点间的距离和交通情况，合理安排旅游路线；
4. 考虑景点的开放时间和规定，避免因为时间问题错过美景；
5. 考虑旅游的季节和天气情况，避免因为天气问题影响旅游效果。
总之，通过运用数学模型优化旅游线路设计，可以为旅游者提供更加优质的旅游体验。
同时，在进行旅游线路设计时，我们也需要充分考虑旅游者的需求和情况，以确保为旅游
者提供有效的服务和建议。
控制系统的数学建模方法控制系统是指借助外部设备或内部程序，以使被控对象按照预定的要求或指令完成某种控制目标的系统。
在控制系统的设计过程中，数学建模是十分重要的一步。
通过数学建模，可以将实际的控制过程转化为数学方程，使得系统的行为可以被合理地分析和预测。
本文将介绍几种常用的数学建模方法，包括常微分方程模型、传递函数模型和状态空间模型。
1. 常微分方程模型常微分方程模型是控制系统数学建模中常用的方法。
对于连续系统，通过对系统的动态特性进行描述，可以得到常微分方程模型。
常微分方程模型通常使用Laplace变换来转化为复频域的传递函数形式，从而进行进一步的分析和设计。
2. 传递函数模型传递函数模型是描述线性时不变系统动态特性的一种方法。
它以输入和输出之间的关系进行建模，该关系可以用一个分子多项式与一个分母多项式的比值来表示。
传递函数模型常用于频域分析和控制器设计中，其数学形式直观且易于理解，适用于单输入单输出系统和多输入多输出系统。
3. 状态空间模型状态空间模型是一种将系统的状态表示为向量形式，并以状态方程描述系统动态行为的方法。
通过状态变量的引入，可以将系统行为从时域转换到状态空间，并进行状态变量的观测和控制。
状态空间模型具有较强的直观性和适应性，能够较好地描述系统的内部结构和行为特性，广泛应用于现代控制理论和控制工程实践中。
4. 神经网络模型神经网络模型是一种模拟人脑神经元间相互连接的计算模型，可以用于控制系统的建模与控制。
通过训练神经网络，可以实现对系统的非线性建模和控制，对于复杂控制问题具有较强的适应性和鲁棒性。
5. 遗传算法模型遗传算法是一种通过模拟生物进化过程，优化系统控制器参数的方法。
通过设定适应度函数和基因编码方式，利用遗传算法优化求解出最优控制器参数。
遗传算法模型广泛应用于控制系统自动调参和优化设计中，具有较强的全局寻优能力和较高的收敛性。
数学建模是控制系统设计的重要环节，通过合理选择建模方法，可以更好地描述和分析系统的动态特性，并基于此进行控制器设计和性能评估。
优化算法的比较分析优化算法是指在解决问题时，通过改进现有算法或提出新的算法来增加算法的效率或减少资源消耗的过程。
优化算法的比较分析是指对多个不同的优化算法进行比较和评估，以确定哪个算法最适合解决一些特定问题。
本文将介绍优化算法的比较分析方法、常用的优化算法以及如何选择最合适的优化算法。
一、优化算法的比较分析方法1.理论分析：通过对算法进行数学建模和分析，推导出算法的时间复杂度和空间复杂度等指标。
根据指标的大小比较算法的效率和资源消耗。
理论分析可以提供算法之间的大致性能比较，但是不考虑具体的实际问题和实际运行环境。
2.实验评估：通过在真实的问题场景下实施算法并进行测试，根据测试结果进行算法性能的评估。
实验评估能够考虑实际问题和实际运行环境的影响，比理论分析更接近实际情况。
实验评估的方法包括对算法在不同数据规模、不同输入特征、不同硬件环境等条件下进行测试，并记录算法的运行时间、资源消耗等指标进行比较。
3.综合比较：将理论分析和实验评估相结合，综合考虑算法的理论性能和实际性能，进行最终的比较和评估。
综合比较方法可以提供更全面、更准确的算法性能比较结果。
二、常用的优化算法1.贪婪算法：贪婪算法是一种通过在每一步选择当前最佳选项来构建最优解的算法。
贪婪算法通常具有较低的计算复杂度，但是不能保证获得全局最优解。
2.动态规划算法：动态规划算法是将问题划分为多个子问题，并通过解决子问题来构建最优解的算法。
动态规划算法通常使用递归或迭代的方式来解决问题，可以获得全局最优解，但是计算复杂度较高。
3.遗传算法：遗传算法是一种通过模拟自然选择和遗传机制来解决优化问题的算法。
遗传算法通过模拟遗传过程中的交叉、变异和选择等操作来不断进化，最终找到适应度最高的解。
4.模拟退火算法：模拟退火算法是一种模拟金属退火过程来解决优化问题的算法。
模拟退火算法通过随机和概率迭代的方式，在局部最优解中跳出，寻找更好的解。
5.粒子群算法：粒子群算法是一种模拟鸟群行为来解决优化问题的算法。
中国研究生数学建模题目数学建模是国内外高校研究生数学教育的核心课程之一，也是研究生培养综合能力的重要手段。
下面给出一道数学建模题目，并展示可以参考的内容，供研究生们参考。
题目：某城市公交系统定价优化问题背景：某城市的公交系统有多条线路，其中每条线路设有若干个站点。
市民可以通过一卡通刷卡乘坐公交车，每次乘坐的价格根据线路的长度而定。
为了提高公交系统的运营效益和市民的乘坐体验，需要对公交系统的定价策略进行优化。
问题：如何确定每个线路的乘坐价格，使得公交系统的总收益最大化，同时不影响市民的出行需求？1. 首先，可以建立一个数学模型，来描述公交系统的运营和市民的乘坐需求。
模型中可以考虑以下因素：- 每个站点之间的距离和交通状况；- 市民的出行需求和乘车意愿；- 已有的公交线路和站点分布情况；- 公交车辆数量和运行时间。
2. 在模型的基础上，可以进行一系列的假设和推导，以得到一个可行的数学表达式。
例如，可以假设市民的乘车需求与价格呈线性关系，拟合出一个合适的函数模型。
3. 在将问题转化为数学表达式后，可以采用优化算法来求解最优解。
常用的优化算法包括线性规划、非线性规划、遗传算法等。
对于公交系统定价问题，可以考虑使用非线性规划算法，以最大化总收益为目标，同时约束市民的出行需求。
4. 在求解最优解后，需要对结果进行分析和评估。
可以通过计算公交系统的总收益、乘客的出行时间和满意度等指标，来评估定价方案的有效性。
5. 最后，根据实际情况，可以对模型和算法进行改进和优化。
例如，可以考虑引入更多的因素，如乘车时间段、交通拥堵情况、收入水平等，以提高模型的准确性和可行性。
以上是一种解决某城市公交系统定价优化问题的思路和方法，并展示了相关参考内容。
当然，具体问题的解决方案会因城市的特点、数据的可用性、算法的选择等因素而有所不同。
研究生们在解决这类数学建模问题时，可以深入分析问题的背景和要求，合理选择数学模型和算法，并通过实际数据的验证来优化解决方案。
数学建模中的随机过程与随机优化理论研究随机过程是一类重要的数学模型，广泛应用于自然、社会、经济等各领域的研究中。
在数学建模中，随机过程能够对问题进行精确的表述，并且通过对其进行优化能够最优地解决问题。
随机优化理论是基于随机过程的优化理论，通过对随机过程进行分析和改进来提高问题的优化效果。
一、随机过程随机过程是描述随机事件在时间或空间上的演化过程的数学模型。
通俗地讲，就是在一个长时间内，随机事件会发生一些令人难以预料的变化，但是这些变化仍然具有一定的规律性。
随机过程可以用数学语言来描述这种变化的规律性，从而帮助我们更好地理解和应对这种随机性。
随机过程中的随机性可以是在时间上的随机，例如某个事件的发生概率可能在某个时间点会突然增大，也可以是在空间上的随机，例如在一张土地利用图中，某个区域的耕地数量可能会因为自然灾害等原因发生变化。
常见的随机过程有马尔科夫链、布朗运动、泊松过程等等。
二、随机优化理论随机优化理论是在随机过程的基础上发展而来的，旨在通过对随机过程的优化来解决实际问题。
在随机过程中，我们可以使用各种方法来分析变化的规律性，包括概率论、统计学、微积分等等。
而在随机优化理论中，我们需要对这种规律性进行探究和改进，以实现更加准确和有效的优化。
一个典型的随机优化问题是参数优化问题。
在参数优化问题中，我们需要找到一个最好的参数值，以使得某个目标函数达到最优状态。
一般来说，目标函数可能会受到各种随机性的影响，因此需要使用随机优化理论来解决。
三、应用实例随机过程与随机优化理论广泛应用于物理学、统计学、经济学、天文学、信息学、信号处理、控制论等多个领域。
以下列举几个实例：1. 声波传递模型声波传递模型是一种描述声波在空间传递的数学模型。
声波在传递过程中可能受到各种干扰和随机性的影响，因此需要使用随机过程来描述其变化规律，并使用随机优化理论来优化传递过程中的参数，以实现最佳效果。
2. 股市预测分析股市行情的变化受到众多因素的影响，包括政治、经济等多种因素。
实验十遗传算法与优化问题一、问题背景与实验目的遗传算法（Genetic Algorithm—GA），是模拟达尔文的遗传选择和自然淘汰的生物进化过程的计算模型，它是由美国Michigan大学的J.Holland教授于1975年首先提出的．遗传算法作为一种新的全局优化搜索算法，以其简单通用、鲁棒性强、适于并行处理及应用范围广等显著特点，奠定了它作为21世纪关键智能计算之一的地位．本实验将首先介绍一下遗传算法的基本理论，然后用其解决几个简单的函数最值问题，使读者能够学会利用遗传算法进行初步的优化计算．1．遗传算法的基本原理遗传算法的基本思想正是基于模仿生物界遗传学的遗传过程．它把问题的参数用基因代表，把问题的解用染色体代表（在计算机里用二进制码表示），从而得到一个由具有不同染色体的个体组成的群体．这个群体在问题特定的环境里生存竞争，适者有最好的机会生存和产生后代．后代随机化地继承了父代的最好特征，并也在生存环境的控制支配下继续这一过程．群体的染色体都将逐渐适应环境，不断进化，最后收敛到一族最适应环境的类似个体，即得到问题最优的解．值得注意的一点是，现在的遗传算法是受生物进化论学说的启发提出的，这种学说对我们用计算机解决复杂问题很有用，而它本身是否完全正确并不重要（目前生物界对此学说尚有争议）．（1）遗传算法中的生物遗传学概念由于遗传算法是由进化论和遗传学机理而产生的直接搜索优化方法；故而在这个算法中要用到各种进化和遗传学的概念．首先给出遗传学概念、遗传算法概念和相应的数学概念三者之间的对应关遗传算法计算优化的操作过程就如同生物学上生物遗传进化的过程，主要有三个基本操作（或称为算子）：选择（Selection）、交叉（Crossover）、变异（Mutation）．遗传算法基本步骤主要是：先把问题的解表示成“染色体”，在算法中也就是以二进制编码的串，在执行遗传算法之前，给出一群“染色体”，也就是假设的可行解．然后，把这些假设的可行解置于问题的“环境”中，并按适者生存的原则，从中选择出较适应环境的“染色体”进行复制，再通过交叉、变异过程产生更适应环境的新一代“染色体”群．经过这样的一代一代地进化，最后就会收敛到最适应环境的一个“染色体”上，它就是问题的最优解．下面给出遗传算法的具体步骤，流程图参见图1：第一步：选择编码策略，把参数集合（可行解集合）转换染色体结构空间；第二步：定义适应函数，便于计算适应值；第三步：确定遗传策略，包括选择群体大小，选择、交叉、变异方法以及确定交叉概率、变异概率等遗传参数；第四步：随机产生初始化群体；第五步：计算群体中的个体或染色体解码后的适应值；第六步：按照遗传策略，运用选择、交叉和变异算子作用于群体，形成下一代群体；第七步：判断群体性能是否满足某一指标、或者是否已完成预定的迭代次数，不满足则返回第五步、或者修改遗传策略再返回第六步．图1 一个遗传算法的具体步骤遗传算法有很多种具体的不同实现过程，以上介绍的是标准遗传算法的主要步骤，此算法会一直运行直到找到满足条件的最优解为止．2．遗传算法的实际应用例1：设2()20.5f x x x =-++，求 max (), [1,2]f x x ∈-．注：这是一个非常简单的二次函数求极值的问题，相信大家都会做．在此我们要研究的不是问题本身，而是借此来说明如何通过遗传算法分析和解决问题．在此将细化地给出遗传算法的整个过程．（1）编码和产生初始群体首先第一步要确定编码的策略，也就是说如何把1-到2这个区间内的数用计算机语言表示出来．编码就是表现型到基因型的映射，编码时要注意以下三个原则：完备性：问题空间中所有点（潜在解）都能成为GA 编码空间中的点（染色体位串）的表现型；健全性：GA 编码空间中的染色体位串必须对应问题空间中的某一潜在解； 非冗余性：染色体和潜在解必须一一对应．这里我们通过采用二进制的形式来解决编码问题，将某个变量值代表的个体表示为一个{0，1}二进制串．当然，串长取决于求解的精度．如果要设定求解精度到六位小数，由于区间长度为2(1)3--=，则必须将闭区间 [1,2]-分为6310⨯等分．因为216222097152231024194304=<⨯<= 所以编码的二进制串至少需要22位．将一个二进制串（b 21b 20b 19…b 1b 0）转化为区间[1,2]-内对应的实数值很简单，只需采取以下两步（Matlab 程序参见附录4）：1）将一个二进制串（b 21b 20b 19…b 1b 0）代表的二进制数化为10进制数：21212019102100()(2)'i i i b b b b b b x =⋯=⋅=∑2）'x 对应的区间[1,2]-内的实数：12)1(2'122---⋅+-=x x 例如，一个二进制串a=<1000101110110101000111>表示实数0.637197．'x =(1000101110110101000111)2=2288967637197.01232288967122=-⋅+-=x 二进制串<0000000000000000000000>，<1111111111111111111111>，则分别表示区间的两个端点值-1和2．利用这种方法我们就完成了遗传算法的第一步——编码，这种二进制编码的方法完全符合上述的编码的三个原则．首先我们来随机的产生一个个体数为4个的初始群体如下：pop(1)={<1101011101001100011110>， %% a1<1000011001010001000010>， %% a2<0001100111010110000000>， %% a3<0110101001101110010101>} %% a4（Matlab 程序参见附录2）化成十进制的数分别为：pop(1)={ 1.523032，0.574022 ，-0.697235 ，0.247238 }接下来我们就要解决每个染色体个体的适应值问题了．（2）定义适应函数和适应值由于给定的目标函数2()20.5f x x x =-++在[1,2]-内的值有正有负，所以必须通过建立适应函数与目标函数的映射关系，保证映射后的适应值非负，而且目标函数的优化方向应对应于适应值增大的方向，也为以后计算各个体的入选概率打下基础．对于本题中的最大化问题，定义适应函数()g x ，采用下述方法：min min (), ()0()0,f x F f x F g x -->⎧=⎨⎩若其他 式中min F 既可以是特定的输入值，也可以是当前所有代或最近K 代中()f x 的最小值，这里为了便于计算，将采用了一个特定的输入值．若取min 1F =-，则当()1f x =时适应函数()2g x =；当() 1.1f x =-时适应函数()0g x =．由上述所随机产生的初始群体，我们可以先计算出目标函数值分别如下（Matlab 程序参见附录3）：f [pop(1)]={ 1.226437 , 1.318543 , -1.380607 , 0.933350 }然后通过适应函数计算出适应值分别如下（Matlab 程序参见附录5、附录6）： 取min 1F =-，g[pop(1)]= { 2.226437 , 2.318543 , 0 , 1.933350 }（3）确定选择标准这里我们用到了适应值的比例来作为选择的标准，得到的每个个体的适应值比例叫作入选概率．其计算公式如下：对于给定的规模为n 的群体pop={123,,,,n a a a a }，个体i a 的适应值为()i g a ，则其入选概率为1()(),1,2,3,,()i s i n ii g a P a i n g a ===⋯∑由上述给出的群体，我们可以计算出各个个体的入选概率．首先可得 41() 6.478330ii g a ==∑， 然后分别用四个个体的适应值去除以41()i i g a =∑，得：P (a 1)=2.226437 / 6.478330 = 0.343675 %% a 1P (a 2)=2.318543 / 6.478330 = 0.357892 %% a 2P (a 3)= 0 / 6.478330 = 0 %% a 3P (a 4)=1.933350 / 6.478330 = 0.298433 %% a 4（Matlab 程序参见附录7）（4）产生种群计算完了入选概率后，就将入选概率大的个体选入种群，淘汰概率小的个体，并用入选概率最大的个体补入种群，得到与原群体大小同样的种群（Matlab 程序参见附录8、附录11）．要说明的是：附录11的算法与这里不完全相同．为保证收敛性，附录11的算法作了修正，采用了最佳个体保存方法（elitist model），具体内容将在后面给出介绍．由初始群体的入选概率我们淘汰掉a3，再加入a2补足成与群体同样大小的种群得到newpop(1)如下：newpop(1)={<1101011101001100011110>，%% a1<1000011001010001000010>，%% a2<1000011001010001000010>，%% a2<0110101001101110010101>} %% a4（5）交叉交叉也就是将一组染色体上对应基因段的交换得到新的染色体，然后得到新的染色体组，组成新的群体（Matlab程序参见附录9）．我们把之前得到的newpop(1)的四个个体两两组成一对，重复的不配对，进行交叉．（可以在任一位进行交叉）<110101110 1001100011110>，<1101011101010001000010>交叉得：<100001100 1010001000010>，<1000011001001100011110><10000110010100 01000010>，<1000011001010010010101>交叉得：<01101010011011 10010101>，<0110101001101101000010>通过交叉得到了四个新个体，得到新的群体jchpop (1)如下：jchpop(1)={<1101011101010001000010>，<1000011001001100011110>，<1000011001010010010101>，<0110101001101101000010>}这里采用的是单点交叉的方法，当然还有多点交叉的方法，不过有些烦琐，这里就不着重介绍了．（6）变异变异也就是通过一个小概率改变染色体位串上的某个基因（Matlab程序参见附录10）．现把刚得到的jchpop(1)中第3个个体中的第9位改变，就产生了变异，得到了新的群体pop(2)如下：pop(2)= {<1101011101010001000010>，<1000011001001100011110>，<1000011011010010010101>，<0110101001101101000010> }然后重复上述的选择、交叉、变异直到满足终止条件为止．（7）终止条件遗传算法的终止条件有两类常见条件：（1）采用设定最大（遗传）代数的方法，一般可设定为50代，此时就可能得出最优解．此种方法简单易行，但可能不是很精确（Matlab 程序参见附录1）；（2）根据个体的差异来判断，通过计算种群中基因多样性测度，即所有基因位相似程度来进行控制．3．遗传算法的收敛性前面我们已经就遗传算法中的编码、适应度函数、选择、交叉和变异等主要操作的基本内容及设计进行了详细的介绍．作为一种搜索算法，遗传算法通过对这些操作的适当设计和运行，可以实现兼顾全局搜索和局部搜索的所谓均衡搜索，具体实现见下图2所示．图2 均衡搜索的具体实现图示应该指出的是，遗传算法虽然可以实现均衡的搜索，并且在许多复杂问题的求解中往往能得到满意的结果，但是该算法的全局优化收敛性的理论分析尚待解决．目前普遍认为，标准遗传算法并不保证全局最优收敛．但是，在一定的约束条件下，遗传算法可以实现这一点．下面我们不加证明地罗列几个定理或定义，供读者参考（在这些定理的证明中，要用到许多概率论知识，特别是有关马尔可夫链的理论，读者可参阅有关文献）．定理 1 如果变异概率为)1,0(∈m P ，交叉概率为]1,0[∈c P ，同时采用比例选择法（按个体适应度占群体适应度的比例进行复制），则标准遗传算法的变换矩阵P 是基本的．定理2 标准遗传算法（参数如定理1）不能收敛至全局最优解．由定理2可以知道，具有变异概率)1,0(∈m P ，交叉概率为]1,0[∈c P 以及按比例选择的标准遗传算法是不能收敛至全局最最优解．我们在前面求解例1时所用的方法就是满足定理1的条件的方法．这无疑是一个令人沮丧的结论．然而，庆幸的是，只要对标准遗传算法作一些改进，就能够保证其收敛性．具体如下：我们对标准遗传算法作一定改进，即不按比例进行选择，而是保留当前所得的最优解（称作超个体）．该超个体不参与遗传．最佳个体保存方法（elitist model ）的思想是把群体中适应度最高的个体不进行配对交叉而直接复制到下一代中．此种选择操作又称复制（copy ）．De Jong 对此方法作了如下定义：定义设到时刻t（第t代）时，群体中a*（t）为最佳个体．又设A（t＋1）为新一代群体，若A（t＋1）中不存在a*（t），则把a*(t)作为A（t＋1）中的第n+1个个体（其中，n为群体大小）（Matlab程序参见附录11）．采用此选择方法的优点是，进化过程中某一代的最优解可不被交叉和变异操作所破坏．但是，这也隐含了一种危机，即局部最优个体的遗传基因会急速增加而使进化有可能限于局部解．也就是说，该方法的全局搜索能力差，它更适合单峰性质的搜索空间搜索，而不是多峰性质的空间搜索．所以此方法一般都与其他选择方法结合使用．定理3具有定理1所示参数，且在选择后保留当前最优值的遗传算法最终能收敛到全局最优解．当然，在选择算子作用后保留当前最优解是一项比较复杂的工作，因为该解在选择算子作用后可能丢失．但是定理3至少表明了这种改进的遗传算法能够收敛至全局最优解．有意思的是，实际上只要在选择前保留当前最优解，就可以保证收敛，定理4描述了这种情况．定理4具有定理1参数的，且在选择前保留当前最优解的遗传算法可收敛于全局最优解．例2：设2=-+，求max(),[0,2]f x x x()3f x x∈，编码长度为5，采用上述定理4所述的“在选择前保留当前最优解的遗传算法”进行．此略，留作练习．二、相关函数（命令）及简介本实验的程序中用到如下一些基本的Matlab函数：ones, zeros, sum, size, length, subs, double 等，以及for, while 等基本程序结构语句，读者可参考前面专门关于Matlab的介绍，也可参考其他数学实验章节中的“相关函数（命令）及简介”内容，此略．三、实验内容上述例1的求解过程为：群体中包含六个染色体，每个染色体用22位0—1码，变异概率为0.01，变量区间为[1,2]-，取Fmin=2-，遗传代数为50代，则运用第一种终止条件（指定遗传代数）的Matlab程序为：[Count,Result,BestMember]=Genetic1(22,6,'-x*x+2*x+0.5',-1,2,-2,0.01,50)执行结果为：Count =50Result =1.0316 1.0316 1.0316 1.0316 1.0316 1.03161.4990 1.4990 1.4990 1.4990 1.4990 1.4990BestMember =1.03161.4990图2 例1的计算结果（注：上图为遗传进化过程中每一代的个体最大适应度；而下图为目前为止的个体最大适应度——单调递增）我们通过Matlab软件实现了遗传算法，得到了这题在第一种终止条件下的最优解：当x取1.0316时，Max () 1.4990f x=．当然这个解和实际情况还有一点出入（应该是x取1时，Max () 1.5000f x=），但对于一个计算机算法来说已经很不错了．我们也可以编制Matlab程序求在第二种终止条件下的最优解．此略，留作练习．实践表明，此时的遗传算法只要经过10代左右就可完成收敛，得到另一个“最优解”，与前面的最优解相差无几．四、自己动手1．用Matlab编制另一个主程序Genetic2.m，求例1的在第二种终止条件下的最优解．提示：一个可能的函数调用形式以及相应的结果为：[Count,Result,BestMember]=Genetic2(22,6,'-x*x+2*x+0.5',-1,2,-2,0.01,0.00001) Count =13Result =1.0392 1.0392 1.0392 1.0392 1.0392 1.03921.4985 1.4985 1.4985 1.4985 1.4985 1.4985 BestMember =1.03921.4985可以看到：两组解都已经很接近实际结果，对于两种方法所产生的最优解差异很小．可见这两种终止算法都是可行的，而且可以知道对于例1的问题，遗传算法只要经过10代左右就可以完成收敛，达到一个最优解．2．按照例2的具体要求，用遗传算法求上述例2的最优解．3．附录9子程序Crossing.m中的第3行到第7行为注解语句．若去掉前面的%号，则程序的算法思想有什么变化？4．附录9子程序Crossing.m中的第8行至第13行的程序表明，当Dim(1)>=3时，将交换数组Population的最后两行，即交换最后面的两个个体．其目的是什么？5．仿照附录10子程序Mutation.m，修改附录9子程序Crossing.m，使得交叉过程也有一个概率值（一般取0.65~0.90）；同时适当修改主程序Genetic1.m或主程序Genetic2.m，以便代入交叉概率．6．设2f x x∈-，要设定求解精度到15位小数．=--+，求max(),[2,2]f x x x()41五、附录附录1：主程序Genetic1.mfunction[Count,Result,BestMember]=Genetic1(MumberLength,MemberNumber,FunctionFitn ess,MinX,MaxX,Fmin,MutationProbability,Gen)Population=PopulationInitialize(MumberLength,MemberNumber);global Count;global CurrentBest;Count=1;PopulationCode=Population;PopulationFitness=Fitness(PopulationCode,FunctionFitness,MinX,MaxX,Mumbe rLength);PopulationFitnessF=FitnessF(PopulationFitness,Fmin);PopulationProbability=Probability(PopulationFitnessF);[Population,CurrentBest,EachGenMaxFitness]=Elitist(PopulationCode,Populatio nFitness,MumberLength);EachMaxFitness(Count)=EachGenMaxFitness;MaxFitness(Count)=CurrentBest(length(CurrentBest));while Count<GenNewPopulation=Select(Population,PopulationProbability,MemberNumber);Population=NewPopulation;NewPopulation=Crossing(Population,FunctionFitness,MinX,MaxX,MumberLength);Population=NewPopulation;NewPopulation=Mutation(Population,MutationProbability);Population=NewPopulation;PopulationFitness=Fitness(Population,FunctionFitness,MinX,MaxX,MumberLength);PopulationFitnessF=FitnessF(PopulationFitness,Fmin);PopulationProbability=Probability(PopulationFitnessF);Count=Count+1;[NewPopulation,CurrentBest,EachGenMaxFitness]=Elitist(Population,PopulationFitn ess,MumberLength);EachMaxFitness(Count)=EachGenMaxFitness;;MaxFitness(Count)=CurrentBest(length(CurrentBest));Population=NewPopulation;endDim=size(Population);Result=ones(2,Dim(1));for i=1:Dim(1)Result(1,i)=Translate(Population(i,:),MinX,MaxX,MumberLength);endResult(2,:)=PopulationFitness;BestMember(1,1)=Translate(CurrentBest(1:MumberLength),MinX,MaxX,Mumb erLength);BestMember(2,1)=CurrentBest(MumberLength+1);close allsubplot(211)plot(EachMaxFitness)subplot(212)plot(MaxFitness)【程序说明】主程序Genetic1.m包含了8个输入参数：(1) MumberLength：表示一个染色体位串的二进制长度．（例1中取22）(2) MemberNumber：表示群体中染色体的个数．（例1中取6个）(3) FunctionFitness：表示目标函数，是个字符串，因此用表达式时，用单引号括出．（例1中是2=-++）f x x x()20.5(4) MinX：变量区间的下限．（例1中是[1,2]-中的）(5) MaxX：变量区间的上限．（例1中是[1,2]-中的2）(6) Fmin：定义适应函数过程中给出的一个目标函数的可能的最小值，由操作者自己给出．（例1中取Fmin=2-）(7) MutationProbability：表示变异的概率，一般都很小．（例1中取0.01）(8) Gen：表示遗传的代数，也就是终止程序时的代数．（例1中取50）另外，主程序Genetic1.m包含了3个输出值：Count 表示遗传的代数；Result 表示计算的结果，也就是最优解；BestMember表示最优个体及其适应值．附录2：子程序PopulationInitialize.mfunction Population=PopulationInitialize(MumberLength,MemberNumber)Temporary=rand(MemberNumber,MumberLength);Population=(Temporary>=0.5*ones(size(Temporary)));【程序说明】子程序PopulationInitialize.m用于产生一个初始群体．这个初始群体含有MemberNumber个染色体，每个染色体有MumberLength个基因（二进制码）．附录3：子程序Fitness.mfunction PopulationFitness=Fitness(PopulationCode,FunctionFitness,MinX,MaxX,MumberLength) Dim=size(PopulationCode);PopulationFitness=zeros(1,Dim(1));for i=1:Dim(1)PopulationFitness(i)=Transfer(PopulationCode(i,:),FunctionFitness,MinX,MaxX,MumberLength);end【程序说明】子程序Fitness.m用于计算群体中每一个染色体的目标函数值．子程序中含有5个输入参数：PopulationCode表示用0—1代码表示的群体，FunctionFitness 表示目标函数，它是一个字符串，因此写入调用程序时，应该用单引号括出，MumberLength表示染色体位串的二进制长度．MinX和MaxX 分别指变量区间的上下限．附录4：子程序Translate.mfunction PopulationData=Translate(PopulationCode,MinX,MaxX,MumberLength) PopulationData=0;Dim=size(PopulationCode);for i=1:Dim(2)PopulationData=PopulationData+PopulationCode(i)*(2^(MumberLength-i));endPopulationData=MinX+PopulationData*(MaxX-MinX)/(2^Dim(2)-1);【程序说明】子程序Translate.m把编成码的群体翻译成变量的数值．含有4个输入参数，PopulationCode, MinX, MaxX, MumberLength．附录5：子程序Transfer.mfunction PopulationFitness=Transfer(PopulationCode,FunctionFitness,MinX,MaxX,MumberLength) PopulationFitness=0;PopulationData=Translate(PopulationCode,MinX,MaxX,MumberLength);PopulationFitness=double(subs(FunctionFitness,'x',sym(PopulationData)));【程序说明】子程序Transfer 把群体中的染色体的目标函数值用数值表示出来，它是Fitness的重要子程序．其有5个输入参数分别为PopulationCode, FunctionFitness, MinX, MaxX，MumberLength．附录6：子程序FitnessF.mfunction PopulationFitnessF=FitnessF(PopulationFitness,Fmin)Dim=size(PopulationFitness);PopulationFitnessF=zeros(1,Dim(2));for i=1:Dim(2)if PopulationFitness(i)>FminPopulationFitnessF(i)=PopulationFitness(i)-Fmin;endif PopulationFitness(i)<=FminPopulationFitnessF(i)=0;endend【程序说明】子程序FitnessF.m是用于计算每个染色体的适应函数值的．其输入参数如下：PopulationFitness 为群体中染色体的目标函数值，Fmin为定义适应函数过程中给出的一个目标函数的可能的最小值．附录7：子程序Probability.mfunction PopulationProbability=Probability(PopulationFitness)SumPopulationFitness=sum(PopulationFitness);PopulationProbability=PopulationFitness/SumPopulationFitness;【程序说明】子程序Probability.m 用于计算群体中每个染色体的入选概率，输入参数为群体中染色体的适应函数值PopulationFitness．附录8：子程序Select.mfunction NewPopulation=Select(Population,PopulationProbability,MemberNumber)CProbability(1)=PopulationProbability(1);for i=2:MemberNumberCProbability(i)=CProbability(i-1)+PopulationProbability(i);endfor i=1:MemberNumberr=rand(1);Index=1;while r>CProbability(Index)Index=Index+1;endNewPopulation(i,:)=Population(Index,:);end【程序说明】子程序Select.m 根据入选概率（计算累计概率）在群体中按比例选择部分染色体组成种群，该子程序的3个输入参数分别为：群体Population，入选概率PopulationProbability，群体中染色体的个数MemberNumber．附录9：子程序Crossing.mfunction NewPopulation=Crossing(Population,FunctionFitness,MinX,MaxX,MumberLength)%%PopulationFitness=%% Fitness(Population,FunctionFitness,MinX,MaxX,MumberLength);%%PopulationProbability=Probability(PopulationFitness);%%[SortResult,SortSite]=sort(PopulationProbability);%%Population=Population(SortSite,:);Dim=size(Population);if Dim(1)>=3Temp=Population(Dim(1),:);Population(Dim(1),:)=Population(Dim(1)-1,:);Population(Dim(1)-1,:)=Temp;endfor i=1:2:Dim(1)-1SiteArray=randperm(Dim(2));Site=SiteArray(1);Temp=Population(i,1:Site);Population(i,1:Site)=Population(i+1,1:Site);Population(i+1,1:Site)=Temp;endNewPopulation=Population;【程序说明】子程序Crossing.m 用于群体中的交叉并产生新群体．其输入参数为：Population, FunctionFitness，MinX，MaxX，MumberLength．附录10：子程序Mutation.mfunction NewPopulation=Mutation(Population,MutationProbability)Dim=size(Population);for i=1:Dim(1)Probability=rand(1);Site=randperm(Dim(2));if Probability<MutationProbabilityif Population(i,Site(1))==1Population(i,Site(1))=0;endif Population(i,Site(1))==0Population(i,Site(1))=1;endendendNewPopulation=Population;【程序说明】子程序Mutation.m用于群体中少量个体变量并产生新的群体．输入参数为：群体Population和变异概率MutationProbability．附录11：子程序Elitist.mfunction [NewPopulationIncludeMax,CurrentBest,EachGenMaxFitness]=Elitist(Population,PopulationFitness,MumberLength)global Count CurrentBest;[MinFitness,MinSite]=min(PopulationFitness);[MaxFitness,MaxSite]=max(PopulationFitness);EachGenMaxFitness=MaxFitness;if Count==1CurrentBest(1:MumberLength)=Population(MaxSite,:);CurrentBest(MumberLength+1)=PopulationFitness(MaxSite);elseif CurrentBest(MumberLength+1)<PopulationFitness(MaxSite);CurrentBest(1:MumberLength)=Population(MaxSite,:);CurrentBest(MumberLength+1)=PopulationFitness(MaxSite);endPopulation(MinSite,:)=CurrentBest(1:MumberLength);endNewPopulationIncludeMax=Population;【程序说明】子程序Elitist.m用到最佳个体保存方法（“优胜劣汰”思想）．输入参数为：群体Population, 目标函数值PopulationFitness和染色体个数MumberLength．“遗传算法”专题一、遗传算法的主要特征：我们的目的是获得“最好解”，可以把这种任务看成是一个优化过程。
